Sprawozdanie z projektu zaliczeniowego ze sztucznej inteligencji

Rozpoznawanie kodów pocztowych

Leszek Kurasz
Uniwersytet Wrocławski
czerwiec 2004

Cel zadania

Celem projektu było wykonanie systemu rozpoznającego ręcznie pisane kody pocztowe. Danymi wejściowymi miały być pliki graficzne będące obrazami zawierającymi sam kod pocztowy, otrzymane np. z zeskanowanych z kart pocztowych. Jako wynik działania programu, powinien być zwrócony ciąg pięciu cyfr rozpoznanego kodu pocztowego.

Szczegółowy opis danych wejściowych

Danymi wejściowymi powinny być prostokątne fragmenty obrazów zeskanowane z kart pocztowych bądź innych przesyłek, zawierające tylko poprawny kod pocztowy. Program czeka na pliki graficzne w formacie BMP. Na ich rozmiar, praktycznie nie są nałożone żadne ograniczenia, chociaż działanie programu sprawdzono dla plików o rozmiarach od 60x15 do 300x90 pikseli. Na rysunkach powinny mieścić się zaciemnione punkty tworzące obraz kodu na stosunkowo jasnym tle. Wprawdzie program wczytuje obrazy w pełnej palecie barw RGB, jednak na samym początku są one konwertowane do 256 poziomowej skali szarości. Rozpoznawane kody powinny być w standardzie obowiązującym w Polsce, tzn. składać się z pięciu cyfr i łącznika w postaci kreski, między drugą, a trzecią cyfrą. Nieistotne jest jaką część obrazu zajmuje właściwy kod, oraz w której części rysunku się znajduje, jednak obraz nie może zawierać innych zaciemnionych pól, które nie są częscią kodu. W dodatku całość powinna być poprawnie zorientowana na rysunku, tzn. poziomo, tak jak jest czytana.

Znane rozwiązania podobnych problemów

Podobne systemy zostały już stworzone. Klasyfikuje się je jako ICR, rodzaj systemu OCR. Skrót ICR pochodzi od pierwszych liter angielskich słów Intelligent Character Recognition lub Image Character Recognition. Oznacza on technologię rozpoznawania ręcznego pisma blokowego. Technologia ICR wykorzystywana jest w systemach, które służą do przetwarzania danych z dokumentów typu formularze na interpretowalną postać elektroniczną. Metody rozpoznawania znaku oparte są zwykle na technologiach sieci neuronowych. Możliwe jest dołączenie tablic walidacji np. numerów PESEL, kodów pocztowych, imion, itp., które podwyższają poziom rozpoznania pola.

W szczególności systemy rozpoznawania kodów pocztowych wykorzystywane są w urzędach pocztowych do automatycznej segregacji przesyłek. Przykładem takiego urządzenia może być Flat Sorting Machine firmy NEC.

Środowisko programowania

Cały program wykonałem w systemie Matlab 6.5. Wykorzystałem pakiet netlab v3.3, w którym zaimplementowane są sieci neuronowe GLM oraz MLP.

Sposób działania systemu

Obraz kodu pocztowego, po wczytaniu, jest konwertowany do 256 poziomowej skali szarości. Następnie dzielony jest na, w pewnym stopniu spójne, obszary będące rysunkami pewnych symboli składających się na obraz kodu (cyfr i łącznika). Jeśli tych obszarów nie jest dokładnie 6 (5 cyfr i myślnik), to program próbuje zlokalizować gdzie dokładnie na rysunku jest owy łącznik. Następnie po jego lewej stronie wyszukiwane są dwie cyfry, a po prawej stronie trzy.

Gdy już zostało zlokalizowanych 5 prostokątnych obszarów zawierających cyfry, każdy z nich jest transformowany do rozmiaru 20x20, aby mógł być skierowany do sieci neuronowej. 400-wymiarowy obraz cyfry jest rzutowany do 42 wymiarów, zgodnie z opisaną niżej zasadą, i rozpoznawany przez sieć GLM.

Każda cyfra rozpoznawana jest przez pewną liczbę niezależnie wytrenowanych sieci (np. 5 lub 7) i metodą głosowania wybierana jest wartość, jaką reprezentuje. Ciąg pięciu wartości jest wynikiem rozpoznania danego kodu.

Wybór sieci neuronowej

Do rozpoznawania cyfr wykorzystano technikę sieci neuronowych. Dane uczące, jak również dane testowe są pobrane z bazy MNIST znajdującej się pod adresem http://yann.lecun.com/exdb/mnist/ Jest to olbrzymia baza zawierająca dane uczące w liczbie 60000 cyfr, oraz dane testowe, w liczbie 10000. Każda cyfra zapamiętana jest jako mapa pikseli w 256 odcieniach szarości i mieszcząca się w kwadracie 20x20. Oto losowa próbka cyfr z bazy MNIST:

Sieci neuronowe na danych o 400 wymiarach działają bardzo wolno. Przeciętny czas uczenia sieci dla próbki uczącej o liczności kilku tysięcy przewyższa kilkadziesiąt minut. Zasadniczo ogranicza to ich stosowalność. Zatem spróbowałem zmniejszyć tą liczbę. Pierwsze wynikowe wymiary to sumy wartości pikseli w 28 obszarach, których wielkość zależna jest od odległości od środka cyfry. Jednak jest to za mało, aby skutecznie rozpoznawać cyfry za pomocą sieci. Dodano więc dodatkowych 14 wartości, które określały grubość cyfry w 10 miejscach w poziomie i 4 w pionie. To dało 42 wymiary, dla których obliczenia odbywały się w racjonalnym czasie.

Porównywałem działanie dwóch sieci: jednowarstwowej GLM, oraz dwuwarstwowej MLP. W przypadku pierwszej, istotnym parametrem jest maksymalna liczba iteracji wykonywanych podczas uczenia się sieci. W przypadku drugiej, do maksymalnej liczby iteracji dochodzi również liczba neuronów w warstwie ukrytej. Po kilku testach, wybierając różne parametry, okazało się, że obydwie sieci cechują się podobną sprawnością w rozpoznawaniu cyfr, lecz dla MLP, w zależności od wybranego algorytmu uczenia się, owy proces przebiega od kilku do kilkunastu razy wolniej. Zatem do dalszej pracy wykorzystałem sieć GLM, dla której liczbę iteracji ustaliłem na 10. Sprawność takiej sieci wynosi około 91.4%. Nie jest to zbyt wysoka wartość, jednak różnorakość krojów pisma jest ogromna, co przysparza sieci wiele problemów w odpowiednim dostosowaniu swoich wag.

Właściwy algorytm

Zasadniczym fragmentem projektu, jest algorytm podziału rysunku na cyfry. Stosuję różne heurystyki, wykorzystywane głównie przy wykrywaniu łącznika, w szczególności liczę średnią grubość zaciemnionych obszarów rysunku, szacuje na osi poziomej miejsce prawdopodobnego położenia myślnika, jak również szukam linii podziałów biegnących od góry rysunku ku dołowi po drodze w przybliżeniu pionowej, z określonym poziomem odchylenia.

Podstawowym celem było prawidłowe wydzielenie pięciu fragmentów obszaru zawierających dobrze odseparowane od siebie cyfry. Prawidłowe rozpoznanie tych fragmentów pozostało trochę na uboczu, z uwagi na niewysoką sprawność rozpoznawania cyfr przez sieć neuronową dla oryginalnej próbki MNIST.

Dane testowe

Przygotowanych zostało ponad 50 zeskanowanych rysunków kodów pocztowych pisanych przez różne osoby. Celowo pozostawiono w tej grupie kilka kodów, które powinny sprawić problem podczas podziału na cyfry.

Testowanie

Podział kodów na rozłączne cyfry

Po przeprowadzeniu pierwszych testów na całej grupie danych, okazało się, że wprawdzie kody, które można podzielić na cyfry za pomocą pionowych linii, są dobrze rozpoznawane, to jednak z pozostałymi jest problem. Dlatego starałem się tak ustalić parametry w wykorzystywanych heurystykach, aby jak największą liczbę kodów prawidłowo podzielić. Jednak bez zaawansowanych metod nie można było osiągnąć pełnego sukcesu. Niestety próba dostosowania parametrów do przyzwoitego podzielenia danego kodu, powoduje, że inne, w których cyfry nachodzą na siebie w odmienny sposób, zostają nieprawidłowo dzielone. Zatem starałem się osiągnąć pewien kompromis, dążąc do jak największej liczby poprawnie podzielonych kodów.

Rozpoznawanie cyfr za pomocą sieci

Jednak dobry podział całego rysunku kodu na składowe cyfry to nie wszystko. Należy jeszcze prawidłowo je sklasyfikować. Jednak to zadanie okazało się być znacznie trudniejsze do przezwyciężenia. Wprawdzie sieć GLM na próbce MNIST właściwie klasyfikowała cyfry ze skutecznością powyżej 90%, jednak dla cyfr wyodrębnionych z kodów, sprawność klasyfikacji wyniosła tylko około 67,8%. Powodów takiego spadku jest wiele, jednak do najważniejszych należy zaliczyć:

Rozpoznawanie całych kodów

Tak niewielka skuteczność w rozpoznawaniu pojedynczych cyfr spowodowała, iż tylko 11 z 51 kodów zostało trafnie rozpoznanych, co daje 21.6% skuteczności. Zatem można zauważyć, że właściwie rozpoznawane cyfry nie są regularnie rozłożone w testowanej próbce kodów. Gdyby tak było, to prawdopodobieństwo prawidłowego sklasyfikowania kodu, jako ciągu pięciu cyfr, powinno wynieść w przybliżeniu (0.678)5=0.14. Uzyskany wynik dosyć znacznie przewyższa tę wartość, co sugeruje, że niektóre kody są łatwiejsze do rozpoznania.

Przykładowe wyniki działania programu

Prawidłowo rozpoznane kody:
Właściwie rozdzielone i sklasyfikowane grupy cyfr:
Oddzielony łącznik oraz zlepka dwóch cyfr:
Błędnie sklasyfikowane:
Trudne problemy:

Propozycje udoskonalania projektu

Uważam, że w celu poprawy osiągniętej w projekcie skuteczności, należałoby skoncentrować się na odszumieniu i wyważeniu obrazów poszczególnych cyfr, tak by ich charakterystyka bardziej przypominała rozkład danych uczących sieć neuronową. Dysponując znaczną próbką cyfr wyodrębnionych za pomocą powyższego programu, można pokusić się o utworzenie własnej próbki uczącej, co mogłoby skutkować w lepszej klasyfikacji przez sieć neuronową. Również pewną poprawę mogłaby przynieść zmiana sposobu rzutowania 400 wymiarowych danych do mniejszego formatu.

Odnośniki