Rozpoznawanie zeskanowanych obrazów podpisów ręcznych wykonywanych przez poszczególne osoby

Wroclaw, June 9 2009

This report has been prepared as a requirement for the course: ARE3513 "Methods and algorithms of artificial intelligence."

Author: Tomasz Doroziński 148442,
Mirosław Nowacki 148877

Recognition of scanned images of signatures of hand performed by individuals

Abstract

Pictures of person's signatures are in BMP files ( bitmaps ) in 256-colors ( grey or any other ) in any size ( limited to the max size of 460x200 pixels ). The line (bar) should be darker then the backround. Recognition of picture's signatures is done by SSN. The system's input is a set of files, containing scanned signatures of different people. For each person there're few pictures. If there'ss more pictures, the system can better recognize signatures. Pictures from files in BMP are properly converted and transferred to the input of SNN.
After conversion ( f.e.: changes of contrast, scale ) the image of signature is transferred to SNN input. The size is determined to : 96x24pixels = 2304 pixels.

Spis Treści

1. Cel projektu.

2. Wstęp.

3. Sztuczna sieć nauronowa.

4. Uczenie SSN.

5. Proces uczenia SSN.

6. Parametry uczenia SSN.

7. Testowanie poprawności nauki SSN.

8. Literatura i przydatne linki.

1. Cel projektu.

Projekt przedstawia rozpoznywnaie podpisu ręcznego wykonanego na kartce papieru a następnie zeskanownownie obrazu do postaci BMP.
Program pobraliśmy ze strony internetowej.

wykonujemy podpis na białej kartce papieru;
przetwarzamy po przez skanowanie do postaci BMP w 256-kolorach;
obrabiamy na podstawie dostarczonego obrazu (bmp)) uczyć sieć neuronową;
przy użyciu nauczonej wcześniej sieci neuronowej, rozpoznajemy wykonany podpis do danej osoby znajdującej się w bazie.

2. Wstęp.

System rozpoznawania zeskanowanych obrazów podpisów osób.
Obrazy podpisów osób są podawane w plikach BMP (bitmapa) w 256-kolorach (szarości lub dowolnych) o dowolnych rozmiarach (ograniczonych do maksymalnej wielkości 460x200 pikseli). Linia (kreska) podpisu powinna być ciemniejsza od jego tła.
Rozpoznawanie obrazów podpisów odbywa się za pomocą SSN.

Możliwe sposoby użycia SSN do rozwiązania tego problemu.
1. SSN jest uczona wielu podpisów jednej osoby X i ma rozstrzygać czy podany podpis należy do osoby X, czy nie. Dla możliwości rozstrzygania o przynależności podpisu wśród N osób należy wtedy użyć N takich SSN. Każda SSN byłaby uczona podpisów jednej osoby. Takie SSN dawałyby na wyjściu odpowiedź "Tak" lub "Nie". W warstwie wyjściowej należałoby użyć jeden neuron. Odpowiedź ustalano by przez ustalenie SSN, która daje odpowiedź najbardziej zbliżoną do odpowiedzi "Tak".
Zaletą tego rozwiązania jest to, że przy dodaniu nowej osoby do bazy, należy wtedy tylko stworzyć nową SSN i nauczyć ją obrazów podpisów tylko tej osoby. Nie trzeba także trzymać w bazie obrazów podpisów pozostałych osób.
Wadą zaś jest to, że dla każdej nowej nauczonej SSN należy trzymać na dysku jej zbiór parametrów.
Rozwiązanie to nadaje się do użycia tylko na stacjonarnym komputerze, gdzie ograniczeniem na liczbę osób, których obrazy podpisów są rozpoznawanie jest ilość dostępnej pamięci masowej.

2. SSN jest uczona podpisów kilku osób naraz i ma odpowiadać, do której osoby należy podany podpis.
Dla N osób taka SSN dawałaby na wyjściu jedną z N odpowiedzi. W warstwie wyjściowej należałoby wtedy użyć N neuronów.
Odpowiedź ustalano by przez ustalenie numeru neuronu wyjściowego o największej wartości. Wadą tego rozwiązania jest to, że przy dodaniu nowej osoby do bazy, należy wtedy nauczyć SSN od nowa wszystkich obrazów podpisów wszystkich osób. Należy wtedy trzymać w bazie obrazy podpisów wszystkich osób.
Zaletą zaś jest to, że mamy tylko jeden zbiór parametrów nauczonej SSN, co oznacza oszczędność miejsca na dysku.
Rozwiązanie to można by wykorzystać w przenośnych urządzeniach, które dysponują ograniczoną ilością pamięci. Proces nauki SSN byłby przeprowadzany na stacjonarnym komputerze, a końcowy zbiór parametrów tej jednej SSN kopiowany byłby na urządzenie przenośne. Taką SSN można by nauczyć rozpoznawania obrazów podpisów do kilkuset osób.

W tym przypadku wykonano wariant nr 2.

Wejście systemu stanowi zbiór plików obrazów zeskanowanych podpisów kilku osób. Dla każdej osoby po kilka obrazów.
Im więcej będzie obrazów podpisów dla każdej osoby tym system lepiej będzie mógł rozpoznawać obrazy danej osoby.
Obrazy z plików w postaci bitmap (BMP) są odpowiednio przetwarzane i podawane na wejście SSN.

Wynikowy obraz - to końcowy obraz podpisu po przetworzeniu (m.in. kontrastowanie, skalowanie), podawany do SSN. Jego rozmiary ustalono na: 96x24 pikseli = 2304 pikseli.

3. Sztuczna sieć neuronowa.

Na wejście SSN podawane są wartości kolorów pikseli wynikowego obrazu, znormalizowane do przedziału [0.0 -1.0] liczb rzeczywistych. Warstwa wejściowa zawiera 96*24 = 2304 neuronów. Warstwa wyjściowa zawiera tyle neuronów ile różnych osób podpisów uczymy SSN.

Zmod. macierz konwulsji Prewitta

Sieci jednokierunkowe to sieci neuronowe, w których nie występuje sprzężenie zwrotne, czyli pojedynczy wzorzec lub sygnał przechodzi przez każdy neuron dokładnie raz w swoim cyklu.
Najprostszą siecią neuronową jest pojedynczy perceptron progowy, opracowany przez McCullocha i Pittsa w roku 1943.
W programie uczącym SSN zaimplementowano czterowarstwową nieliniową sztuczną sieć neuronową jednokierunkową (wielowarstwowa sieć perceptronowa (ang. Multi-Layered Perceptron MLP)).
Zgodnie z teorią sieć o dwóch lub trzech warstwach perceptronowych może być użyta do aproksymacji większości funkcji.

Kolejne warstwy sieci, to: warstwa danych wejściowych, dwie warstwy ukryte i warstwa danych wyjściowych.

Użycie dwóch warstw ukrytych zamiast tylko jednej znacząco poprawia uczenie się SSN i jej możliwości generalizacji wiedzy. Trzy warstwy to już przesada, a dwie w zupełności wystarczają do poprawnej nauki.

Połączenia neuronów między warstwami - każdy z każdym.

Każdy neuron posiada tyle wejść, ile jest neuronów w warstwie poprzedniej oraz dodatkowe jedno wejście tzw. bias o stałej wartości równej 1.0. Zmieniają się jednak wagi związane z biasem. Z każdym wejściem sygnału do neuronu związana jest waga, czyli liczba określająca wpływ tego sygnału wejściowego na wynik wyjściowy neuronu.

Łączna liczba wszystkich wag w SSN wynosi zatem:
LiczbaNeuronówUk1*(LiczbaDanychWe+1) + LiczbaNeuronówUk2*(LiczbaNeuronówUk1+1) + LiczbaNeuronówWy*(LiczbaNeuronówUk2+1),
gdzie:
LiczbaDanychWe - liczba wejść
LiczbaNeuronówUk1 - liczba neuronów w pierwszej warstwie ukrytej
LiczbaNeuronówUk2 - liczba neuronów w drugiej warstwie ukrytej
LiczbaNeuronówWy - liczba neuronów w warstwie wyjściowej

Wektorem uczącym są następujące dwa ciągi danych: uczący (wejściowy) i weryfikujący (wyjściowy).

Wektorem wejściowym jest 2304 liczb rzeczywistych, o wartościach z przedziału [0.0 ; 1.0]. Wektorem wyjściowym jest N liczb rzeczywistych; wszystkie oprócz jednej równe 0.0.
Warstwy ukryte zawierają dowolnie ustalaną liczbę neuronów. Dla neuronów ukrytych w liczbie około 40-70 sieć wydaje się uczyć najszybciej.
Liczbę neuronów w każdej warstwie ukrytej można dowolnie ustalać w programie uczącym SSN. Dla wielu warstw ukrytych stosuje się zwykle metodę piramidy geometrycznej, która zakłada, że liczba neuronów w kolejnych warstwach tworzy kształt piramidy i maleje od wejścia do wyjścia. Zatem liczba neuronów w kolejnych warstwach powinna być coraz mniejsza (większa liczba neuronów w kolejnej warstwie nie zwiększa możliwości nauki SSN).
Zatem w naszym przypadku SSN może ostatecznie mieć rozmiar np.: 2304 - 70 - 40 - N. Liczba osób (N) nie powinna, zatem przekroczyć liczby neuronów w ostatniej (drugiej) warstwie ukrytej. Generalnie uczenie rozpoczyna się z małą liczbą neuronów w warstwach ukrytych a następnie, obserwując postępy tego procesu, doświadczalnie zwiększa się ich liczbę.

Funkcja aktywacji
Wartość funkcji aktywacji jest sygnałem wyjściowym neuronu i propagowana jest do neuronów warstwy następnej. Funkcja aktywacji może przybierać jedną z trzech postaci:
- nieliniowa
- liniowa
- skoku jednostkowego tzw. funkcja progowa
Argumentem funkcji aktywacji neuronu są zsumowane iloczyny sygnałów wejściowych i wag tego neuronu (tzw. suma ważona): F(u₁*w₁+...+u_m*w_m).

Zmod. macierz konwulsji Prewitta

Wybór funkcji aktywacji zależy od rodzaju problemu, jaki stawiamy przed siecią do rozwiązania. Dla sieci wielowarstwowych najczęściej stosowane są funkcje nieliniowe, gdyż neurony o takich charakterystykach wykazują największe zdolności do nauki, polegające na mozliwości odwzorowania w sposób płynny dowolnej zależności pomiędzy wejściem a wyjściem sieci. Umożliwia to otrzymanie na wyjściu sieci informacji ciągłej a nie tylko postaci: TAK - NIE.

4. Uczenie SSN.

Działanie SSN polega na tym, że sygnały pobudzające zawarte w wektorze wejściowym podawane na wejścia sieci, przetwarzane są w poszczególnych neuronach. Po tej projekcji na wyjściach sieci otrzymuje się wartości liczbowe, które stanowią odpowiedź sieci na pobudzenie i stanowią rozwiązanie postawionego problemu. Sieć uczymy "na przykładach".
Celem jest uzyskanie oczekiwanych zadawalających (tzn. nie przekraczających dopuszczalnego błędu) wartości na wyjściu przy danych wartościach wejściowych. Gdy błąd jest zbyt duży należy skorygować odpowiednio wagi.

Zmod. macierz konwulsji Prewitta

Jednak, aby takie rozwiązanie uzyskać, należy przejść żmudną drogę uczenia sieci. Jedną z metod jest uczenie metodą wstecznej propagacji błędów - EBP (ang. Error Back Propagation). Jest to podstawowa (i jedna z najskuteczniejszych) metoda uczenia sieci wielowarstwowych. Została opracowana w 1974 roku przez P. J. Werbosa jako uczenie z nadzorem lub inaczej - z nauczycielem. Taka metoda została zastosowana w programie. Algorytm opiera się na sprowadzeniu wartości funkcji błędu sieci poniżej pewnego założonego minimum. Jako miarę błędu stosuje się błąd średniokwadratowy na neuronach wyjściowych. Poprawianie wag odbywa się po prezentacji każdego wzorca, o ile błąd dla tego wzorca jest za duży (parametr epsilon).

5. Proces uczenia SSN.

Zastosowany sposób uczenia SSN wygląda w ogólności następująco:
Pętla po wszystkich wzorcach (tzw. epoka):
Oblicz błąd dla danego wzorca.
Jeżeli błąd ten jest większy niż parametr epsilon, to popraw wagi jeden RAZ!, (czyli nie poprawiaj wag, aż nie będzie błędu dla tego wzorca (tzw. cykl) i dopiero badaj następny).
Sprawdź następny wzorzec.
Powtarzaj tę pętlę, aż nie będzie błędu większego niż "epsilon" dla wszystkich wzorców (w całej epoce) oraz suma tych błędów nie będzie większa od parametru ""Suma epsilon".

Zatem tutaj cykl składa się z jednej poprawy wag. Taki sposób uczenia okazuje się być szybszy, niż stosowanie pełnych cykli.

Błąd sieci to suma po wszystkich neuronach wyjściowych kwadratów różnicy między obliczonym wynikiem sieci (dla podanych danych wejściowych) a oczekiwanym wynikiem (dla tych danych).

Przykład pojedynczego wiersza opisującego stan po przejściu jednej epoki:
Epk: 26; LB: 15; Nrp: 9; MaxB:0.609109; SumB=8.23149034;
SO-SE=-2.2349127 | Eta: Uk1=0.0777778; Uk2=0.0577778; Wy=0.0333333

Kolejne elementy wiersza zawierają:
Epk - Numer kolejnej epoki
LB - liczba błędów w ostatniej epoce
Nrp - nr ostatniego wzorca w epoce, dla którego był błąd (Uwaga: nr wzorca, od którego zaczynamy epokę jest losowy, więc ten ostatni, to nie musi być ostatni w kolejności tak, jak w bazie danych.)
NrpMaxB - nr wzorca, dla którego był największy błąd
MaxB - wartość maksymalnego błędu dla pojedynczego wzorca w ostatniej epoce
SumB - Suma błędów ze wszystkich wzorców w całej epoce
SO-SE - różnica między sumą błędów w poprzedniej epoce i obecnej
EtaUk1, Uk2, Wy - bieżące wartości parametrów eta dla każdej warstwy (zmieniają się dynamicznie; zależą od liczby błędów w ostatniej epoce)

Po poprawnym nauczeniu SSN program zapisuje do pliku ''ParametryNaukiSSN.txt''

6. Parametry uczenia SSN.

Panel główny programu do nauczania rozpoznawania sieci SSN w naszym przypadku rozpoznawanie zeskanowanych obrazów podpisów ręcznych wykonywanych przez poszczególne osoby

Zakończenie się procesu nauki SSN może wystąpić z dwóch powodów:

SSN nauczyła się, tzn. osiągnęła wymagane parametry, tzn. wartość epsilon i Suma epsilon. W tym przypadku program podaję liczbę przeprowadzonych kroków nauki.
SSN nie nauczyła się a osiągnięto już maksymalną liczbę iteracji (kroków nauki: popraw wag lub liczby epok). W tym przypadku program podaje liczbę błędów, tzn. przypadków, dla których błąd jest > epsilon.

Liczba wzorców- to liczba obrazów, których SSN ma się uczyć i na ich podstawie rozpoznawać inne obrazy.

eta współczynnik szybkości uczenia- określa jak bardzo w danym kroku zmieniane są wagi (kierunek uczenia sieci). Zwiększenie tej wartości może zwiększać szybkość uczenia się SSN pojedynczych wzorców, ale może to powodować, że w znajdowaniu globalnego minimum funkcji, algorytm wpadnie w minimum lokalne i nie będzie możliwe nauczenie się wszystkich wzorców. Mała wartość powoduje, że SSN uczy się małymi kroczkami, ale za to konsekwentnie dąży do celu i nierzadko przez to zwiększa się całościowa szybkość nauczenia się wszystkich wzorców. W programie zastosowano dynamiczne ustalanie parametru eta proporcjonalnie od aktualnej liczby błędów sieci. Ponadto można ustalić wartości eta dla każdej warstwy osobno, przykładowo:
EtaUk1 = 0.3, A_EtaUk1 = 6, AlfaUk1 = 0.88,
EtaUk2 = 0.2, A_EtaUk2 = 5, AlfaUk2 = 0.88,
EtaWy = 0.1, A_EtaWy = 4, AlfaWy = 0.88,
A_Eta - określa jak bardzo ma maleć wartość Eta w zależności od liczby błędów w ostatniej epoce. Im większa wartość A_Eta tym eta bardziej maleje, proporcjonalnie do liczby błędów. A_Eta musi być >= 1.0. Gdy A_Eta = 1.0, to eta nie zmienia się. Dokładnie obliczanie końcowego parametru eta wygląda następująco: eta = Eta * F(LBłędów/Wzorców, A_Eta), gdzie F(x, n) = (1+(n-1)*x)/n
Alfa- parametr określający wpływ członu momentum dla każdej z warstw osobno. Im większa jego wartość, tym większy wpływ na kierunek uczenia mają poprzednie wartości popraw wag sieci. Odpowiednio użyty może bardzo poprawić szybkość uczenia. Najczęściej przyjmuje się wartość 0.7 - 0.95. Wartość równa 0.0 oznacza brak wpływu członu momentum na zmianę wag.
Epsilon - maksymalny błąd SSN dla pojedynczego wzorca. Zwykle ustala się jego wartość na nie większą niż 0,5 (lub 0,25 gdy jest jeden neuron na wyjściu). Zmniejszanie tej wartości powoduje zwiększanie dokładności sieci i co za tym idzie precyzji predykcji lub generalizacji, ale też nieuchronnie wydłuża czas trwania procesu uczenia lub całkowicie uniemożliwia poprawną naukę SSN przy dużej liczbie wzorców do nauczenia. Zwiększanie wartości tego parametru powoduje natomiast szybsze zakończenie uczenia sieci, ale tak nauczona sieć może dawać złe odpowiedzi nawet dla uczonych wzorców.
Suma epsilon maksymalna suma błędów SSN dla wszystkich uczonych wzorców. Dodatkowy parametr określający jakość nauczonej SSN. Jeżeli nie interesuje nas ten parametr, to należy go ustawić na odpowiednio dużą wartość ( liczby wzorców).
Maksymalna liczna popraw wag - określa maksymalną liczbę kroków, tzn. popraw wag sieci, jaką można przeprowadzić w procesie uczenia, po to, aby proces mógł się zatrzymać, gdy SSN nie chce się nauczyć (, gdy np. wpadnie w minimum lokalne).
Maksymalna liczba epok - określa maksymalną liczbę epok, jaka może być w procesie uczenia również dla zatrzymania tego procesu.

Zakończenie procesu nauki nie musi oznaczać, że SSN nauczyła się poprawnie, tzn. że daje poprawne odpowiedzi dla uczonych wzorców (, bo np. parametr epsilon był za duży - np. >0,5). Zatem po zakończeniu procesu nauki, sprawdzana jest POPRAWNOŚĆ rozpoznawania uczonych wzorców, tzn. czy SSN poprawnie się ich nauczyła. Polega to na podaniu na wejście sieci kolejno wszystkich uczonych wzorców i sprawdzaniu czy sieć daje oczekiwane wyniki. Następną sprawą jest test możliwości generalizacji SSN, tzn. jak sieć radzi sobie z rozpoznawaniem nieuczonych przypadków.