Wrocław, 17 czerwca 2009
Raport na projekt z przedmiotu
ARE3513 Metody i algorytmy sztucznej inteligencji
Temat:
Identyfikacja osób poprzez ich odciski palców
Wykonanie:
Sebastian Gońda
Damian Juszczak
Prowadzący:
dr inż. Witold Paluszyński
Streszczenie:
Celem poniższego projektu było testowanie programu do identyfikacji osób poprzez rozpoznawanie ich odcisków palców. Dodatkowo przeanalizowaliśmy wpływ kluczowych parametrów podczas uczenia się sztucznej sieci neuronowej na otrzymywane wyniki.
Wrocław, 17th of June 2009
This report has been prepared as a requirement for the course:
ARE3513 Methods and algorithms of artificial intelligence
Subject:
Fingerprint identification
Author:
Sebastian Gońda
Damian Juszczak
Conducted by:
Witold Paluszyński, PhD
Abstract:
The aim of this project was to test the program to identify people by identifying their fingerprints. In addition, examined the impact of key parameters during the learning of artificial neural networks on obtain results.
1. Wstęp
Celem naszego projektu było stworzenie programu do identyfikacji osób poprzez rozpoznanie ich odcisków palców. Jednak nie było sensu "wywarzania otwartych drzwi" i skorzystaliśmy z darmowego programu do rozpoznawania odcisków palców.
Układ linii papilarnych jest różny u każdego człowieka, co sprawia, że jest cechą charakterystyczną. Linie papilarne są cechą, która jest prawie nie do usunięcia w przypadkowy sposób. Można się ich jedynie pozbyć celowo, np. poprzez usunięcie naskórka, wypalenie ich do tego stopnia żeby się zabliźniły itp. Układ linie papilarne opisuje się za pomocą tzw. minucji - charakterystycznych cech, takich jak początki, zakończenia, rozwidlenia, haczyki itp. Wzajemny układ minucji jednoznacznie identyfikuje daną osobę.
Programy do rozpoznawania odcisków palców korzystają z rozmieszczenia minucji, porównywanie obrazów odcisków jest niemożliwe, gdyż każdy obrazy odcisku tego samego palca prawie na pewno różnią się od siebie (szumy, stosowanie innego urządzenia). W tym celu w programach stosuje się sztuczne sieci neuronowe które potrafią poradzić sobie z tymi problemami.
2. Struktura opuszka palca
Opuszek ludzkiego palca stanowi warstwa skóry z charakterystyczną warstwą chropowatą tworzącą grzbiety i doliny. Kształt i formy grzbietów są elementem unikalnym i tym samym stanowią przedmiot badań biometrycznych. Wszystkie typy minucji są kombinacją dwóch podstawowych elementów: rozwidlenia oraz zakończenia grzbietu.
Wyznaczone typy minucji:
Początek |
Zakończenie |
Rozwidlenie pojedyncze |
Rozwidlenie podwójne |
Rozwidlenie potrójne |
Złączenie pojedyncze |
Złączenie podwójne |
Złączenie potrójne |
Haczyk |
Oczko pojedyncze |
Oczko podwójne |
Mostek pojedynczy |
Mostek podwójny |
Punkt |
Odcinek |
Styk boczny |
Linia przechodząca |
skrzyżowanie |
Trójnóg |
Linia szczątkowa |
Minucja typu M |
|
Oprócz szczegółowych cech grzbietów (minucji) wyróżnia się struktury, które są podstawą do budowy złożonych wzorów rozpoznawanych na opuszku palca:
- Delta
Tworzą ją dwie linie równoległe, które rozchylają się w pewnym punkcie w kształt lejka. Ramiona delty dzielą wzór na trzy zasadnicze części: podstawę, rdzeń i pokrywę.
- Termin wewnętrzny
Jest to punkt wyznaczony w centrum wzoru.
- Termin zewnętrzny
Jest to punkt wyznaczony w obrębie delty.
- linia Galtona
Łączy termin zewnętrzny z terminem wewnętrznym.
Rozróżnia się następujące typy wzorów:
- Wzory łukowe
Są najrzadziej spotykane (ok.6%). Proste charakteryzują się brakiem delty i rdzenia. Wzory łukowe namiotowe różnią się od wzorów łukowych prostych tym, ze w centrum mają jeden lub kilka elementów, przeważnie odcinków, które są ustawione pionowo lub ukośnie do podstawy wzoru i tworzą tzw. maszt.
- Wzory pętlicowe
Występują najczęściej (64%) Wzór taki musi posiadać: tylko jedną deltę, przynajmniej jedną pętlicę, przynajmniej linię papilarną przecinającą linie Galtona.
- Wzory wirowe
(30%) charakteryzują się najbardziej złożoną budową. Ich rdzeń tworzą koła elipsy, spirale, pętlice i inne wzory.
![[Rozmiar: 114706 bajtów]](gutenkurst.jpg)
3. Opis programu
Program którego użyliśmy jest autorstwa Pana Artura Czekalskiego i jest dostępny za darmo na jego stronie www.
![[Rozmiar: 145958 bajtów]](prog.jpg)
Program używa SSN i korzysta z danych wejściowych w formacie bmp o rozmiarze 110x150 pikseli. Z danymi wejściowymi był problem, gdyż program nie posiada możliwości wczytania własnej bazy danych. Problem ten udało nam się obejść w bardzo prosty sposób, a mianowicie aplikacja wczytuje podczas uruchomienia pliki graficzne o nazwach od 00.bmp do 05.bmp, wystarczyło podmienić te pliki aby wczytać własną bazę.
Program sam w sobie nie posiada rozbudowanej obróbki obrazu, ponieważ skan odcisku palcu zawiera same dane użyteczne.
Aplikacja ma 2 zakładki. Pierwsza służy do rozpoznawania odcisków palców i jest częścią czysto mechaniczną. Druga natomiast służy do obsługi SSN, w niej możemy zmieniać istotne parametry programu (jest to warstwa "myśląca").
W programie zaimplementowano czterowarstwową nieliniową sztuczną sieć neuronową jednokierunkową.
Kolejne warstwy sieci, to: warstwa danych wejściowych, dwie warstwy ukryte i warstwa danych wyjściowych.
Wektorem uczącym są następujące dwa ciągi danych: uczący (wejściowy) i weryfikujący (wyjściowy).
Wektorem wejściowym, są dane z obrazu w postaci tablicy pikseli, czyli 110x150 liczb zamienionych na typ rzeczywisty "double", o wartościach z przedziału <0.0 ; 0.1> w zależności od jasności danego piksela. (dokładnie liczba ta wynosi: średnia z jasności składowych koloru R, G ,B dzielona prze 255)
Zatem standardowo na wejściu sieci jest 110*150 = 16500 neuronów - jest to całkiem spora ilość, co powoduje znaczne spowolnienie procesu uczenia SSN. Ilość neuronów w warstwach ukrytych jest dostępna do modyfikacji przez użytkownika, lecz zostały nałożone na nie ograniczenia:
- pierwsza warstwa ukryta musi posiadać liczbę neuronów w przedziale <30,500>
- druga warstwa ukryta musi posiadać liczbę neuronów w przedziale <3, liczba neuronów pierwszej warstwy -1>
Wektorem wyjściowym, jest dwuelementowy wektor o oczekiwanych wartościach: [1; 0] - oznacza odpowiedź "Tak" oraz [0; 1] - oznacza odpowiedź "Nie". Zatem warstwa wyjściowa zawiera dwa neurony.
Funkcją aktywacji neuronu jest funkcja sigmoidalna unipolarna: f(x) = 1.0/(1.0+exp(-beta*x)).
Po obliczeniu wyniku sieci, neurony na wyjściu dają wartości z przedziału <0.0 ; 1.0>. Numer neuronu (0 lub 1) o największej wartości reprezentuje daną odpowiedź ("Tak" lub "Nie").
Im liczba jest większa tym odpowiedź sieci jest bardziej prawdopodobna (zgodna z rzeczywistością).
Uczenie SSN danego jednego obrazu odcisku palca odbywa się przez podanie na wejście SSN obrazu tego odcisku palca i oczekiwaniu odpowiedzi "Tak" oraz podawaniu kilku generowanych losowych obrazów (tzn. mające losowe wartości pikseli) i oczekiwaniu odpowiedzi "Nie".
Zatem liczba wzorców do nauczenia przez SSN wynosi: 1 + liczba losowych obrazów.
Pierwsze trzy z tzw. losowych obrazów, to takie, których wszystkie piksele mają wartości równe odpowiednio: 1.0, 0.0, 0.5.
Użyta metoda uczenia to wsteczna propagacja błędów, jako uczenie z nadzorem lub inaczej - z nauczycielem.
4. Testowanie
Wpływ parametrów na proces identyfikacji został przeprowadzony w następujący sposób.
Każdy parametr był zmieniany indywidualnie, tzn. że pozostałe parametry pozostały na poziomie startowym. Jedyny parametr który został zmodyfikowany to liczba neuronów w pierwszej i drugiej warstwie ukrytej. Poziom ten został ustalony na 150/110, ponieważ we wstępnych testach dla tych parametrów uzyskiwaliśmy najlepsze wyniki działania programu.
4.1 Wpływ maksymalnej liczby liczby iteracji
Maksymalna liczba iteracji nie ma znaczącego wpływu na działanie aplikacji i otrzymywane wyniki, ponieważ program nie przekracza 50 iteracji podczas uczenia się. Parametr ten można zostawić na startowym poziomie (tzn. 100). SSN zatrzymuje proces uczenia się w momencie jak zostaną osiągnięte warunki wystarczające do tego, że sieć została poprawnie nauczona.
Wartość liczby iteracji musi się znajdować w zakresie <10;500>
4.2 Wpływ epsilona (stopnia błędu)
Epsilon jest parametrem znacznie wpływającym na szybkość uczenia się sieci neuronowej (dokładnie na liczbę iteracji). Wraz ze wzrostem epsilona wzrasta liczba iteracji, pomniejszanie epsilona nie daje odwrotnego wyniku, nie widać znaczącego wzrostu uczenia się SSN. Szybkość z jaką wzrasta długość uczenia się sieci przedstawia poniższy wykres.
![[Rozmiar: 17822 bajtów]](test1.jpg)
4.3 Wpływ sumy epsilona
Parametr sumy epsilona jest ograniczony jedynie poprzez to, że musi być większy od 0.
Nie zaobserwowaliśmy żadnego znaczącego wpływu na otrzymywane wyniki. Program podaje ciągle takie same prawdopodobieństwa swoich odpowiedzi i nie nastąpiła zmiana długości uczenia się sieci.
Testowaliśmy epsilon w zakresie <0.1; 200>. Zauważyliśmy, że suma epsilona poniżej 3 nie pozwala na poprawne nauczenie się sieci.
4.4 Wpływ parametru eta (szybkość uczenia)
Parametr eta musi zawierać się w przedziale <0,1; 1>
Wpływ tego parametru przedstawia się następująco, im większa eta tym mniej iteracji podczas uczenia się SSN, ale program popełnia większe błędy podczas podejmowania decyzji. Proponowany poziom eta jest na optymalnym poziomie i nie ma sensu go zmieniać (poziom startowy jest równy 0.2).
Wpływ eta na szybkość uczenia się i poziom popełnianego błędu przedstawia poniższy wykres.
![[Rozmiar: 17822 bajtów]](test2.jpg)
Wartość (-5) została wprowadzona, ponieważ dla parametru eta=0.7 program przestaje poprawnie działać, są jakieś błędy i pomiar nie był możliwy do przeprowadzenia.
Wartości łamanej błędów zostały wyliczone w następujący sposób: dla wczytanej bazy i nauczonej sieci błąd jest równy liczbie błędnych decyzji SSN.
4.4 Wpływ alfa (bezwładność sieci)
Parametr ten jest ograniczony przez wartości min=0 i max=1.
Jego wpływu nie da się zobrazować ani wyciągnąć na jego temat sensownych wniosków, gdyż jego zmiany powodują powstawanie chaosu w wynikach, niezależnie od tego czy jest wysoka wartość czy niska sieć zachowuje się nieprzewidywalnie. Uznaliśmy, że najlepiej jest zgodzić się z autorem aplikacji i pozostawić go niezmienionego.
4.5 Liczba losowych obrazów
Niestety tego parametru nie udało nam się zbadać ponieważ w dokumentacji nic na jego temat nie pisze.
Na pewno jego wartość musi się zawierać w przedziale <3; 20>.
Jedną zależność jedynie zauważyliśmy, że wpisanie wartości większej niż 6 (czyli większej niż dopuszczalny rozmiar bazy) powoduje poważne błędy w działaniu sieci (sieć przestaje poprawnie identyfikować odciski). Większego wpływu tego parametru nie zauważyliśmy na działanie sieci (o ile wartość nie jest większa niż 6).
4.6 Testowanie programu na uszkodzonych obrazach odcisków
Przeprowadziliśmy testy również na uszkodzonych obrazach. Niestety program nie dał rady rozpoznać identycznego obrazu, w przypadku wprowadzenia lekko zaszumionego odcisku. Identycznie sprawa wyglądała w przypadku rozmazanych odcisków. Przyczyną tego jest to, że program jest darmowy i nie został stworzony przez profesjonalnych programistów.
Przykłady uszkodzonych obrazów:
![[Rozmiar: 17878 bajtów]](usz1.bmp)
Odcisk zaszumiony |
![[Rozmiar: 17878 bajtów]](usz2.jpg)
Odcisk rozmazany |
5. Wnioski
Temat projektu, który wybraliśmy, a mianowicie rozpoznawanie osób poprzez identyfikacje odcisków palców okazał się bardzo obszerny. Musieliśmy znaleźć bazę odcisków kilkunastu osób, które dawały odcisk tego samego kciuka kilka razy, tak aby zweryfikować czy dana sieć się poprawnie nauczyła i rozpoznaje poprawnie daną osobę poprzez tą identyfikację.
Wyniki testu wychodziły różne, i bardzo ważnym czynnikiem, które utrudniały tą czynność było kilka niekorzystnych parametrów takich jak: szumy, mokry kciuk, a największy problem jest wtedy gdy opuszek palca jest całkowicie naruszony bądź w ogóle usunięty.
Następnym problemem na który się natknęliśmy były oczywiście zaszumione i niewyraźne obrazki tych właśnie odcisków palców. Testy które przeprowadziliśmy były wykonywane na darmowym programie komputerowym, stworzonym przez jedna osobę i dlatego iż jest on darmowy nie jest na pewno dopracowany do perfekcji, jest wiele innych lepszych programów do identyfikacji odcisków palców lecz są już płatne.
Podczas wykonywania testów można stwierdzić, że przystawienie dwóch odcisków palców zdefiniujemy jako uznanie ich za tożsame przez algorytm, to tak zdefiniowana relacja nie jest przechodnia.
Reasumując całą naszą prace, jesteśmy ogólnie zadowoleni z naszych wyników, które otrzymaliśmy.
6. Źródła
1. "Wprowadzenie do sieci neuronowych", przeł. z jęz. ang. i oprac. Paweł Lula, Ryszard Tadeusiewicz
2. http://www.epokay.net/artur
3. Baza odcisków palców
