Znalezienie cyfr w kodzie pocztowym.
Autor: Mariusz Dymarek
Raport z projektu: Metody i algorytmy sztucznej inteligencji, ARE3513
Prowadzący: dr inż. Witold Paluszyński
Data: 16 czerwca 2008r.
Wroclaw, June 16 2008
This report has been prepared as a requirement for the course:
ARE3513 "Methods and algorithms of artificial intelligence.
Author: Mariusz Dymarek.
Finding numbers in image with post code
This project is middle part of identifying post code from envelope. Whole process consist 3 parts:
- finding location of post code in the envelope
- segmentation of picture with post code to pictures with numbers
- recognition of numbers
It was assumed, that image from entry is bitmap with post code on it(problem of localization of post code in envelope was skipped).
Entry image should include 6 signs in following order: xx-xxx.
The aim of this project is to extract 5 images (each with one number) from image with post code.
Description of the algorithm
First picture picture is being thresheld, next algoritm uses
- median filter,
- erosion,
- dilate,
to reduce noises in picture.
To solve main problem(extracting numbers) algorithm uses vertical and horizontal projection.
Opis problemu i założenia
Projekt jest częścią procesu odczytywania kodu pocztowego z koperty.
Proces ten można podzielić na trzy etapy:
- odnalezienie kodu pocztowego na kopercie
- segmentacja kodu pocztowego na znaki
- rozpoznanie zlokalizowanych wcześniej znaków
Zrealizowany projekt jest środkowym etapem tego procesu. Pismo może być zarówno odręczne jak i maszynowe.
W projekcie zalożono, że dane wejściowe do aplikacji to mapa bitowa z kodem pocztowym (pominięto problem lokalizacji kodu na kopercie). Zadanie polega na segmentacji obrazu wejściowego w taki sposób, aby wyłuskać z niego pięć mniejszych obrazów reprezentujących cyfry kodu pocztowego. Obraz wejściowy
powinien zawierać 6 znaków w nastepującym formacie xx-xxx, cyfry nie powinny zachodzic na siebie(jeśli zachodzą program próbuje odtworzyć cyfry, ale w większości przypadków jest tracona część cyfry).
Rozpoznawanie liter z wyłuskanych obrazów nie jest realizowane.
Przykładowy obraz wejściowy:
Algorytm rozwiązujący problem
Przygotowanie obrazu do segmentacji
Wejściowy obraz jest konwertowany do skali szarości, następnie jest progowany
(próg jest zmienny - średnia szarość danego obrazu). Umożliwia wydobycie znaków z obrazów
o różnych stopniach kontrastu. Przykładowy obraz po progowaniu:
Następnie obraz jest przepuszczany przez filtr medianowy
oraz poddany jest kolejno operacji erozji i dylatacji.
Jako element strukturalny jest użyta macierz:
Operacje te mają na celu usunięcie wszystkich szumów, które podczas progowania
zostały błędnie zaklasyfikowane jako znak.
Obraz przygotowany do segmentacji:
Niestety jak widać na powyższym obrazku, czasami filtry usuwają nie tylko szumy, ale też część cyfry, która zanika po procesie erozji. W projekcie nie ma to dużego wpływu na efekt końcowy. Natomiast stanowiłoby to problem przy ostatnim etapie odczytywania kodu pocztowego, czyli
rozpoznawaniu znaków z obrazków.
Wyliczenie projekcjii pinowej przetworzonego obrazu.
Algorytm wyłuskiwania cyfr bazuje, na rzutowaniu pionowym, ktore jest
wykresem średnich poziomów szarości w liniach pionowych.
Ponad to, w programie odwrócono wykres. Tak, że liczba zero oznacza że wszystkie punkty w rzutowaniu są białe i analogicznie - 255 wszystkie punkty w linii są czarne.
Algorytm wyliczający projekcję pionową:
gdzie:
- N - szerokość obrazu
- M - wysokość obrazu
Projekcja pionowa przykładowego obrazu wygląda następująco:
Jeśli obrazy wejściowe zawierają kod pocztowy w formacie xx-xxx, to ich projekcje pionowe posiadają stałe cechy, dzięki którym można podzielić obrazy na znaki.
Punkty z wykresu, które mają wartość zero są białymi paskami, które oddzielają kolejne litery od siebie. Korzystając z tej zależności i znając rozkład cyfr w obrazku łatwo wyłuskiwać kolejne znaki. Jednak, jeżeli liczby nachodzą na siebie sytuacja jest trudniejsza(alogrytm stara się znaleźć wtedy wartość jak najbliższą białej linii). Można również łatwo rozpoznać kreskę pionową w tuż przed środkiem obrazu.
Opis Algorytmu
Kolejne kroki algorytmu:
- usunięcię białych pasków z początku i końca obrazu wejściowego, kod pocztowy jest teraz w środku obrazu
- korzystając z założenia, że obraz wejściowy ma posiadać znaki w formacie xx-xxx algorytm znajduje kreskę poziomą. Powinna ona się znajdować przed połową obrazka(algorytm zaczyna pracę w punkcie 0.42*szer ).
Algorytm szuka w pobliżu tego miejsca punków z projekcji, które są równe zero.
Jeśli takich punktów nie ma, to na bazie wzrostu wartosci kolejnych punktów z projekcji próbuje znaleźć początek i koniec kreski, realizuje to funkcja przetworz. Funkcja uwzględnia również fakt, że rzut pionowy linii należących do kreski powinien być znacznie mniejszy od rzutu linii należącej do cyfry,
- na podstawie położenia kreski algorytm wyznacza koniec drugiej liczby i początek trzeciej
- następnie zostaje wywołana funkcja znajdz, która znajduje koniec pierwszej cyfry i początek drugiej.
- funkcja znajdz zostaje wywołana również żeby rodzielić kolejno trzecią i czwartą liczbę i kolejny raz, żeby rozdzielić czwartą i piątą.
- następnie obrazy zostają podzielone na paski z znalezionymi cyframi
- za pomoca projekcjii poziomej z pasków wycinane są liczby(projekcja pozioma jest analogicznie realizowana do projekcji pionowej)
Funkcja znajdz, próbuje na podstawie projekcji pionowej rozdzielic dwie cyfry.
Jako parametr przekazywany jest do niej linia, od której funkcja zaczyna szukać linii z końcem pierwszej i początkiem drugiej cyfry, linia z końcem drugiej w kolejności cyfr.Funkcja szuka minimalnej wartości histogramu na podanym przedziale.
Rozdzielenie liczby trzeciej i czwartej wywoływane jest z punktem końcowym w linii o maksymalnej wartości projekcji pionowej z oczekiwanego zakresu położenia 4 cyfry.
Implementacja programowa.
Program został napisany w całości na potrzeby projektu. Aplikacja została napisana w środowisku Matlab w wersji 7.4 .
Okno z wynikiem działania programu zostało przedstawione poniżej.
Program wywołuje się wpisując w linii komend wpisując "rysunek" i naciskając enter:
Po wpisaniu nazwy pliku do analizy zostaje wyświetlone okno z wynikiem:
Przeprowadzone eksperymenty.
Z uwagi na to, że problem został rozwiązany metodami geometrycznymi nie potrzeba było dużej ilości danych testowych.
Program był testowany 50 obrazami wejściowymi. Obrazy te były różnorodne(np przykłady na kartce w kratkę, różne kolory liter, dane pisane długopisem, mazakiem, dane o różnych kontrastach itp...) Podczas procesu tworzenia aplikacji
użyto 40 obrazów do kontroli postępu prac. Natomiast pozostałe 10 obrazów zostało sprawdzonych po napisaniu programu jako dane testujące program.
Wyniki badań:
Wszystkie próbki zostały rozdzielone poprawnie na cyfry, mimo tego wystąpiły problemy z liczbami nachodzącymi na siebie i zbyt podobnymi do podłoża.
Wynik dla prawidłowego podziału:
Uwagi z przeprowadzonych testów:
- gdy liczby nachodzą na siebie, nie można oddzielić liczb pionową linią.
Wynikiem wtedy jest zaklasyfikowanie części nachodzącej cyfry do drugiej cyfry
- jeżeli pismo z kodem pocztowym napisane jest na papierze w kratkę i pismo za mało odróżnia się od kratki. Część kratki zostaje zaklasyfikowana
jako liczba. Liczby w dalszym ciągu są dobrze rozpoznawane, ale występują w nich dodatkowe składowe:
- jeżeli pismo wyraźnie się odróżnia od kratki problem znika:
Wnioski:
- Po wprowadzeniu 10 nie używanych wcześniej przykładów zaobserwowano w 2 przypadkach dokładnie
te same problemy, jak opisane w poprzednim rozdziale. Cyfry są rozpoznawane w sposób prawidłowy, ale widać na nich
w 1 przypadku cyfrę nachodzącą na inną cyfrę i w kolejnym pozostałości po kratce z kartki.
- Żeby program dawał dobre wyniki trzeba więc pisać kolorem odróżniającym się od tłą (najlepiej czarnym) oraz robić odstępy między
kolejnymi literami, mamy wtedy pewność, że program będzie działał prawidłowo.
- Wszystkie cele projetku zostały zrealizowane (w założeniach było wymienione, że cyfry nie powinny zachodzić na siebie), z uwagi na brak czasu nie zrealizowano dodatkowego celu - rozpoznanie cyfr z wyłuskanych obrazów.
- Pomysłem na ominięcie problemu z nachodzącymi cyframi jest sprawdzanie spójści czarnych obiektów w podzielonym już obrazie
Natomiast z uwagi na bark czasu idea nie została zrealizowana.
Bibliografia:
- "Progowanie - globalna metoda segmentacji", dr inż. M. Wnuk
link
- "Transformacje lokalne (operatory liniowe i nieliniowe)", dr inż. M. Wnuk
link
- "EXPERIMENTAL ANALYSIS ON OLD BULGARIAN TEXT CHARACTER RECOGNITION",
Geortchev V., Krusteva R., Boneva A., Stanishev K.
link
- Przykłady do testowania programu pobrano ze strony:
kody pocztowe
