OCR – problemy z życia

Tekst przeniesiony z like-a-geek.jogger.pl.

frame grabber

Jak niektórzy z was wiedzą, od niedawna zajmuję się pracą nad systemem rozpoznawania tekstu (OCR).

W związku z częstymi pytaniami o dostęp do kodu lub dokumentacji programu chciałbym zaznaczyć, że nie mogę dać do nich dostępu. Po pierwsze, prawa do programu należą do firmy dla której wówczas pracowałem, a po drugie po prostu ich nie mam (tekst powstał w 2008 roku).

Sytuacja w  której system będzie wykorzystywany (bieżąca produkcja w  fabryce telewizorów) wymusiła użycie wyspecjalizowanego programu. Z góry uprzedzam, że dostępne rozwiązania nie sprawdzają się i ponowne wynalezienie koła jest konieczne. Na końcu artykułu znajdują się obrazki będące wynikiem działania programu wraz z krótkim opisem.

W czym problem?

Ogólna zasada działania OCr-ów jest prosta: znajdź w obrazie tekst, wyszczególnij w nim pojedyncze znaki, porównaj je ze wzorcem i podaj gotowy tekst na wyjście. Niestety, sprawa nie jest tak prosta jak mogłoby się wydawać a panowie Inżynierii Testu nie mają czasu/ środków/ ochoty bawić się z tym sami. Główne problemy pojawiające się w tym przypadku to:

  1. Niska rozdzielczość obrazu
  2. Duże zaszumienie
  3. Duża ilość krojów pisma
  4. Alfabety inne niż łaciński
  5. Wolno działające oprogramowanie

Co z tym zrobić

Część z was na pewno wie, że na produkcji liczy się każda sekunda. Przyśpieszenie działania linii o  sekundę na jednym elemencie daje po miesiącu produkcji w  systemie 24h/dobę całkiem pokaźnie oszczędności dla firmy (i premię dla mnie;). Niestety jestem skazany na C#, którego nie można posądzić o szczyt wydajności, ale wąskim gardłem nie są tu obliczenia, a wykonanie zrzutu ekranu i przetransportowanie go do komputera. Urządzenie dokonujące tej sztuki potrzebuje dobrych 10s, żeby wysłać dane do komputera – tu spodziewam się największej oszczędności czasu.

Problem wolnego wykonywania obliczeń po części rozwiązuje się sam – przetwarzany obraz ma maksymalnie 2 miliony punktów (przy Full HD), dzięki czemu tablice na których trzeba operować nie są duże, więc obliczeń jest mało. Niestety, to także jest problemem, gdyż rozdzielczość taka jest za mała, żeby poszczególne znaki składały się z rozsądnej ilości pikseli. O co chodzi? Przy ograniczonej ilości punktów znaki takie jak duże i, małe L, czy cyfra 1 różnią się jednym lub dwoma pikselami. Warto dodać, że nie każdy telewizor obsługuje Full HD, a menu z którego pobieram tekst zajmuje maksymalnie 1/4 ekranu (łącznie z ramkami, cieniami wokół okna itp.). Swoją drogą czasem aż dech zapiera jeśli widzi się system operujący telewizorem i 1GB RAM-u wewnątrz…

Usuwamy szum

Jeśli dwa znaki różnią się pojedynczymi pikselami wystarczy drobny błąd (np. szum, poruszenie ekranu czy zwyczajne przekłamanie), żeby program nie rozpoznał poprawnie znaku. Odszumienie nie jest trudne – zastosowanie filtra dolnoprzepustowego spowoduje rozmycie obrazu i przyczyni się do połączenia liter mających wąskie punkty – np. połączenie w małym k albo kreski w w. Bez rozmycia litery te zwykle dzielą się na dwie części. Aby rozmyć obraz pobiera się wartości pikseli leżących wokół danego punktu (oraz tego punktu), sumuje je i dzieli przez ilość punktów. Operację trzeba wykonać dla każdej ze składowych R, G i B obrazu. Dodatkowo siłę rozmycia można regulować poprzez nadanie aktualnemu punktowi wagi większej niż 1 (i odpowiednie zwiększenie mianownika). Im więcej punktów wokół zbadamy tym lepszy będzie efekt, jednak zwiększy się też ilość obliczeń. Ponadto, dla punktów leżących dalej od aktualnego można zmniejszyć wagę. Pozostaje jeszcze pytanie, co zrobić z punktami na krawędzi. Najlepszym rozwiązaniem okazało się skopiowanie skrajnych pikseli tworząc wokół różnokolorową ramkę.

Jakie ładne literki…

Mając rozmyty obraz należy przekształcić go do obrazu czarno-białego. Aby to zrobić sumujemy wartości R, G i B danego piksela. Jeśli suma jest większa od wyznaczonego progu piksel był jasny i oznaczymy go jako biały (np. binarne 1). Jeśli suma była mała piksel uznajemy jako czarny. Jak dobrać próg? Najprościej wybrać połowę maksymalnej wartości (3*256), ale skuteczniej jest dostosować próg do jasności obrazu – dla jasnych obrazów próg ustawia się wyżej. Aby jeszcze polepszyć ten etap subpikselom można nadać odpowiednie wagi (największą dla zielonego). Ten etap jest bardzo ważny i najlepiej wykonać dużą liczbę testów dla różnych obrazów.

Na tak przygotowanym obrazie możemy użyć kolejnych filtrów – minimalnego i maksymalnego. Filtr minimalny pozostawi czarny piksel czarnym tylko jeśli określona liczba jego sąsiadów jest również czarna. Eliminuje to wszystkie jednopikselowe ramki, małe kropki, ikonki, pozostałości po szumie itp. Niestety litery staną się cieńsze (chociaż wcześniejsze rozmycie nieco je pogrubiło). Na to również mamy rozwiązanie – filtr maksymalny. Zamieni on piksel białym na czarny jeśli posiada on jakiegoś czarnego sąsiada.

Jak odróżnić znaki?

Tak przetworzony tekst daje się już łatwo obrabiać. Po podzieleniu tekstu na pojedyncze znaki zajmujemy się każdym z nich po kolei (a właściwie jednocześnie dzięki wykorzystaniu wielowątkowości). Wykorzystuje się praktycznie trzy metody rozpoznawania liter. Pierwsza to porównanie z wzorcem i dopasowanie do najlepiej pasującego (na zasadzie odległości Hamminga), druga to szukanie cech charakterystycznych (np. U to jedyny znak posiadający poziomy łuk i dwa końce, B ma dwa puste obszary w środku itd.), a trzecia to sieć neuronowa.

Z miejsca wyeliminowałem rozróżnianie liter po cechach szczególnych, gdyż rozpoznawane znaki należą m.in. do któregoś z alfabetów arabskich i jakichś azjatyckich krzaków;). Prawdopodobnie w tym przypadku najlepiej sprawdzi się sieć neuronowa – system powinien być przygotowany na nowe kroje pisma pochodzące z nowych telewizorów oraz zniekształcenia. Ponadto warto, po złożeniu wyrazu, sprawdzić go ze słownikiem i jeśli wyrazu takiego nie ma – znów znaleźć najlepiej pasujący (również licząc odległość Hamminga). Dodam jeszcze, że klasyczne porównanie ze wzorcem również ma dużą szansę na użycie (wymaga znacznie mniej obliczeń), ale wymaga stosunkowo długiej nauki programu i w początkowym okresie działania oraz po wprowadzeniu nowych krojów pisma nie będzie zbyt skuteczne. Wybór odpowiedniej metody czeka na akceptację zwierzchników, ale w przeciągu mniej więcej miesiąca będę już wiedział na ten temat więcej i na pewno powstanie druga część artykułu dotycząca samego rozpoznawania pojedynczych znaków.

Podsumowując, w nieco rozwlekłym artykule opisałem w jaki sposób zabrać się do komputerowego przetwarzania tekstów. Ważną sprawą jest rozmycie tekstu (filtr dolnoprzepustowy), usunięcie szumu i drobnych przeszkadzających elementów (filtr minimalny) oraz pogrubienie liter (filtr maksymalny). Aby znacząco zmniejszyć ilość obliczeń obraz z 24-bitowego przekształca się do tablicy typu bool. Najskuteczniejsze metody rozpoznawanie pojedynczych znaków polegają na porównaniu ich ze wzorcem lub użyciu wyćwiczonej sieci neuronowej – o tym w kolejnej części.

Ilustrowany przykład

Jako że artykuł się spodobał, a w komentarzach prosiliście o zrzuty tymczasowo poprawiłem program, żeby po każdym kroku tworzył plik graficzny z aktualnym postępem prac. Poniżej pokazuję krok po kroku działanie użytych filtrów (wraz z opisem). Niestety nie jestem upoważniony do wyniesienia rzeczywistych zrzutów, przedstawione pliki są danymi testowymi.

  • Powiedzmy, że na wejście dostaliśmy obrazek w dość dużej rozdzielczości, otoczony ramką. Są to dwa wyrazy Jogger napisane różnymi krojami pisma. Co ważne, w moim przypadku nie spodziewam się tekstów pisanych Georgią (dolne słowo).

    poczatkowy obraz

  • Pierwszym krokiem jest rozmycie obrazu – bardzo prosty, ale wymagający stosunkowo dużo obliczeń (ze względu na operowanie na 24-bitowym kolorze) filtr.

    rozmycie obrazu

  • Krok drugi to przekształcenie obrazu do tablicy typu bool – od tej chwili mamy tylko dwa kolory. W przykładzie nic ciekawego się nie dzieje, bo od początku był czarno-biały;). Widać tylko, że szare piksele stały się albo białe, albo czarne (jeśli były odpowiednio jasne i ciemne, przy czym poziom graniczny trzeba ustalić samemu).

    binaryzacja obrazu

  • Następny filtr (minimalny) ostatecznie pozbywa się ramki, ewentualnego szumu i innych drobnych przeszkadzajek (gdyby istniały). Widać tu, że litery są mocno postrzępione i wyraźnie cieńsze.

    filtr minimalny

  • Filtr maksymalny (erozja) pogrubia litery i z powrotem łączy ze sobą znaki takie jak podzielone poprzednio e (jak widać w dolnym napisie – niedokładnie). Ustawienia tego i poprzedniego filtra najbardziej wpływają na końcowy wygląd obrazu.

    filtr maksymalny

  • Ostatnim krokiem jest podział tekstu na poszczególne znaki (białe prostokąty). Mój skrypt robił to tak, że najpierw szukał poziomych linii, w których nie ma ani jednego pustego piksela, żeby ustalić górną i dolną granicę wiersza. Następnie dla każdego wiersza szukał linii pionowych, w których nie ma żadnego czarnego piksela. Na obrazie poniżej te linie są zaznaczone na szaro.

    W przypadku Georgii J zostało podzielone na dwie części, a dwie litery g połączyły się w jeden znak co jest zdecydowanym błędem i wymaga poprawy.

    rozdzielone znaki

Jak widać zasada działania mojego OCR-a nie jest trudna, wymaga jednak bardzo dużo testów. Na szczęście jest to sam początek prac, a mój system już potrafi wykryć literki u z dużą skutecznością (rzędu 90%).