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

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).

Kontynuując jeden z ostatnich wpisów (OCR – problemy z życia) chciałbym zwrócić uwagę na sposób rozróżniania znaków w systemach rozpoznawania pisma.

Jak zacząć?

Wyznaczenie pojedynczych linii zawierających tekst (nawet z grafiki takiej jak poniżej) nie jest trudne. Nieco większy problem stanowi podział na znaki (chociaż z tym też zwykle sobie radzę), a największą trudnością jest dopasowanie znaku do wzorca. Jak wspomniałem poprzednio, można to zrobić na trzy sposoby: zbudować dużą bazę wzorców i porównywać z nimi każdy ze znaków, stworzyć uczącą się sieć neuronową lub szukać w znakach cech charakterystycznych.

Czas OSD z kanciastymi literkami minął…

Wybrana przeze mnie metoda, to połączenie porównywania ze wzorcem i wyszukiwania cech charakterystycznych (co ciekawe, wstępnie odrzuciłem ten ostatni sposób). Porównanie ze wzorcem ma podstawową zaletę – jest bardzo szybkie. Znalezienie najlepiej pasującego elementu z powiedzmy 500 czy 1000 trwa bardzo krótko dzięki wykorzystaniu hashtables (jest jakieś polski odpowiednik tego słowa?). Aby nie zapisywać każdego nowego znaku osobno litery są rozciągane do kwadratu, a następnie dzielone na 25 części (obrazek niżej). Mały kwadracik jest zapisywany jako 1, jeśli większość jego pikseli jest biała, a zero – jeśli czarna. Dzięki temu rozwiązaniu prawie wszystkie rozmiary danego fonta są opisane tak samo – za pomocą dwudziestopięcioelementowego słowa.

Podobne znaki

Niestety, taki opis nie zawsze jest skuteczny. Często okazuje się, że il są opisane tak samo, jeśli odstęp od kropki jest mały, C różni się tylko jednym kwadratem od O itp. (dotyczy to pojedynczych krojów, nie zawsze tak jest). W takiej sytuacji przeprowadzam dodatkowe testy odróżniające znaki na podstawie cech charakterystycznych – np. i zawsze ma poziomy biały pasek.

Aby wyeliminować ten problem należy w niektórych przypadkach wykonać jeszcze jeden test. Mogłoby się wydawać, że liczba krojów jest na tyle duża, że testów takich będą setki. Na szczęście sprawa nie jest zbyt skomplikowana i do odróżnienia np. h od b wystarczy sprawdzić środkowy dolny punkt – jeśli jest pusty znak uznajemy za h. Dla bezpieczeństwa można analizować grupę punktów w jego otoczeniu. Jak się okazuje takich par (lub większych grup) jest tylko kilkanaście.

Dalej zgadujemy

Wykorzystanie logiki rozmytej jest bardzo pomocne, bo rzadko kiedy mamy 100% pewność co do poprawności znaku (chyba, że wzorzec został dodany ręcznie). Po znalezieniu wzorców, które najbardziej pasują do znaku składamy je w słowa. Tu również musimy zgadywać – mając słowa KOT i K0T (środkowy znak w drugim słowie to zero) człowiek bez problemu domyśli się prawidłowego rozwiązania. Program musi bazować na kontekście i wybrać odpowiednią opcję. W tym przypadku nie jest to trudne, gdyż między dwoma wielkimi literami raczej nie spodziewamy się cyfry, ale takie podejście może okazać się zgubne. Przykładowo, sprawdzając wersję oprogramowania możemy natknąć się na ciąg typu V.0S.1. Czy drugi znak (nie licząc kropek) to duże o czy zero? Czy obok niego jest litera S czy cyfra 5 (zdjęcie nie zawsze jest wyraźne)?

W takiej sytuacji wystarczy zastosować słownik spodziewanych słów i dopasować najbardziej prawdopodobne lub, jeśli wiemy czego się spodziewać, na sztywno ustawić, że np. wszystkie zera nieotoczone cyframi traktujemy jako o. Jak widać zgadywanek jest coraz więcej…

Nie za szybko

Jak ostatnio wspominałem, jednym z wymagań projektu jest zastosowanie C#. Niestety nie grzeszy on szybkością, zwłaszcza jeśli stosujemy domyślne metody. Przykładowo, przy analizie bitmapy warto pobrać wartości składowych pikseli. Możemy przyśpieszyć tę operację aż kilkadziesiąt razy jeśli zamiast domyślnego GetPixel dla każdego punktu skopiujemy wszystko na raz do tablicy i na niej będziemy operować. Służy do tego poniższy kod, który pomimo swojej długości jest bardzo efektywny.

using System.Runtime.InteropServices.Marshal

Bitmap bmp = …//bitmapa wejściowa
BitmapData bmpData = 
 bmp.LockBits(new Rectangle(0, 0, bmp.Width, bmp.Height),
 ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);
IntPtr ptr = bmpData.Scan0;
int bytes = bmpData.Stride * bmp.Height;
byte[] rgbValues = new byte[bytes]
Copy(ptr, rgbValues, 0, bytes);

Tak wolno działających klas i metod jest dużo więcej, ale szybkości pisania aplikacji w wersji demo nie można C#-owi zarzucić. Również MS Visual Studio jest bardzo dobrym produktem… przynajmniej jeśli chodzi o C#, który bądź co bądź nie jest skomplikowanym (składniowo) językiem.

Wracając do tematu, rozpoznawane tekstu polega w dużej mierze na zgadywaniu i przypasowaniu znaku do wzorca uwzględniając kontekst w jakim się pojawia. Analiza tego co udało się odczytać jest dość skomplikowaną sprawą – trzeba uwzględnić wielkie i małe litery, cyfry, różne alfabety, znaki diaktryczne itp. O tym napiszę w kolejnym artykule dotyczącym rozpoznawania tekstu mając nadzieję, że komuś może się to kiedyś przydać (a także z chęci uzewnętrznienia swoich wrażeń;).

Autor artykułu: Marcin Kosedowski.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *