Wrocław, 11 czerwca 2008

Raport opracowany na zaliczenie przedmiotu:
ARE3513 "Metody i algorytmy sztucznej inteligencji"

Temat:
Rozpoznawanie odcisków palców

Autorzy:
Paweł Kołodka 140343 (ARS)
Maciej Moskwa 140372 (ARS)

Prowadzący:
dr inż. Witold Paluszyński

Wrocław, June 11 2008

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

Subject:
Fingerprint identification

Authors:
Paweł Kołodka 140343 (ARS)
Maciej Moskwa 140372 (ARS)

Conducted by:
Dr Witold Paluszyński

Fingerprint identification and fingerprint authorization is becoming now a days more and more popular method of person identification. We decided that subject of our project will be the fingerprint recognizing and classification.
Our project took issue of image processing, image characteristic's extraction and classification. We also shortly described methods of a fingerprint collection.
In our project we decided to recognize fingerprint by it's unique marks, called minutiae. Our program is searching them on image of a fingerprint, and remembers theirs positions. This positions are compared with positions of minutiae in pattern, and program decides witch pattern corresponds to analysed fingerprint.
We gain good results, our program recognized test fingerprints with 90 percent effectiveness. We noticed a few problems with our fingerprint collection's method, and suggested to use in classification other method, more resistant to fingerprint position and orientation on image.

1. Wstęp

Odcisk palca jest jedną z cech, którą można jednoznacznie przyporządkować do określonej osoby. Każdy człowiek, ma własny, unikalny układ linii papilarnych, nie powtarzający się u nikogo innego w całej populacji. Dlatego też na przestrzeni kilkudziestu ostatnich lat zyskał tak duże znaczenie w kryminologii, jako element stanowiący niezbity dowód obecności podejrzanego na miejscu przestępstwa. Z czasem i rozwojem elektronicznych technik pobierania odcisków palców, dogodności płynące z tego rodzaju identyfikacji zaczęły być dostrzegane przez firmy prywatne. I tak czytniki odcisków i systemy identyfikacji osób po nich pojawiły się w systemach bezpieczeństwa, by wraz z czasem i rosnącą popularnością zawitać do takich przedmiotów codziennego użytku jak komputer przenośny, czy nawet pendrive.

Jako cel naszego projektu obraliśmy sobie właśnie stworzenie aplikacji rozpoznającej i klasyfikującej odciski palców. Ma ona za zadanie przyporządkowywać analizowane odciski do wzorców w bazie i co za tym idzie rozpoznawać do których osób one należą.

Zakres zagadnień jakimi zajmowaliśmy się w trakcie realizacji projektu objął:
- obróbka, przetwarzanie i filtrowanie obrazów, tak aby przygotować do klasyfikacji przedstawione na nich odciski
- ekstrahowania wzorców z obrazów i ich klasyfikacji
- stworzenia odpowiedniej do potrzeb bazy, oraz umieszczania, przechowywania i porównywania wzorców w niej

2. Realizacja projektu

Zagadnienie identyfikacji odcisków palców stanowi pewien zbiór problemów, wynikających z poszczególnych etapów jej przeprowadzania. Można tutaj wydzielić cztery fazy działania:
1. uzyskanie cyfrowej formy rzeczywistego odcisku, w naszym przypadku jest to plik graficzny
2. obróbka obrazu tak aby dostosować go do dalszej klasyfikacji
3. wyekstrahowanie z tegoż obrazu pewnych cech właściwych danemu odciskowi, umożliwiających jednoznaczne identyfikowanie go
4. klasyfikacja cech i porównywanie ich z istniejącymi wzorcami

2.1. Przetwarzanie fizycznego odcisku na formę cyfrową

Istnieje wiele metod umożliwiających "ściągnięcie" odcisków palców i przetworzenie ich na formę cyfrową. Popularne są tutaj czujniki pojemnościowe, będące matrycą płytek przewodnika i wykorzystujące zjawisko kondensacji ładunku elektrycznego między przerwami linii papilarnych, a czujnikiem. Wykorzystywane są także czujniki optyczne, działające w paśmie podczerwieni i wykorzystujące zjawisko całkowitego wewnętrznego odbicia, a także czujniki termiczne wykrywające zmiany temperatury w miejscu styku linii papilarnej z czujnikiem. Mają one wiele zalet, a także swoje wady, oraz jedną wadę wspólną: są stosunkowo drogie i niezbyt powszechnie dostępne. Niestety wszystkie z nich znajdowały się poza naszym zasięgiem.

Dlatego też zdecydowaliśmy się na skorzystanie z tradycyjnej metody, polegającej na przeniesieniu odcisku na kartę przy pomocy tuszu, a następnie użyciu skanera do przetworzenia obrazu kartki na plik graficzny. Odciski na kartce odbijaliśmy korzystając z podstawki z tuszem do pieczątek, a do skanowania popularny skaner komputerowy do zastosowań biurowych. Rozdzielczość skanowania ustaliliśmy na 600dpi.
Zaletą metody jest duża dostępność i stosunkowo niewielki koszt potrzebnych materiałów i urządzeń, a także względna łatwość w realizacji.

Przykładowe zeskanowane obrazy odcisków jakie uzyskaliśmy:

Niestety rozwiązanie to nie jest pozbawione wad. Pierwszą z nich jest brak powtarzalności w przenoszeniu na kartkę odcisków danej osoby. To jak odcisk będzie ostatecznie wyglądał zależy od wielu czynników, takich jak ilość tuszu nabranego na palec, pozycja palca w trakcie docisku, czy jego siła. Wszystkie te elementy trudno perfekcyjnie powtarzać, dlatego też mogą występować znaczne różnice pomiędzy różnymi odbiciami odcisków jednej osoby. Duże znaczenie ma tu także kształt opuszka danej osoby. U jednej z nich, od której zbieraliśmy odciski, był on mocno wypukły, co powodowało, iż na środku linie odbijały się za mocno i zlewały się w jedną całość, natomiast na krawędziach były mało wyraźne, bo docisk był za mały. Inną wadą stosowania płynnego tuszu jest fakt, iż ma on tendencję do zlewania się w miejscach gdzie odległości między liniami papilarnymi są niewielkie.
Nie mniej metoda ta była jedyną dla nas dostępną w czasie realizacji projektu, dlatego też z niej korzystaliśmy.

2.2 Obróbka obrazu

Obraz zeskanowanego odcisku jest niezbyt praktyczny do wyodrębniania cech. Znacznie lepszym rozwiązaniem jest jego przetworzenie na postać bardziej dogodną.
Ponieważ naszą aplikację postanowiliśmy napisać w środowisku Matlab, zdecydowaliśmy się w niej zawrzeć także moduł przetwarzający na wejściu obraz do bardziej praktycznej formy, szczególnie, że Matlab charakteryzuje się bardzo dobrym wsparciem dla wielu operacji na obrazach.

Skanowanie i przycinanie obrazów, tak aby jeden plik zawierał jeden odcisk, wykonywaliśmy w programie Presto ImageFolio. Gotowe grafiki zapisywaliśmy jako bitmapy BMP. Format ten jest bez problemu obsługiwany przez aplikację Matlab wyposażoną w toolbox Image Processing, więc nie było problemów z wczytywaniem plików do programu przy użyciu gotowych funkcji, a następnie jego konwersją na barwy odcieni szarości (256 odcieni, 255 - czarny i 0 - biały).

Przetwarzanie obrazu zaczęliśmy od wykrywania krawędzi. Po sprawdzeniu kilku wariantów gotowych filtrów, zdecydowaliśmy się na zmodyfikowany filtr Prewitta, którego macierz konwolucji prezentuje się następująco:

Potem dokonywaliśmy binaryzacji zgodnie z zadanym dolnym progiem. Operacja ta polega na zamianie na białe wszystkich pikseli obrazu o odcieniu reprezentowanym wartością poniżej zadanego progu, natomiast na czarne wszystkich o wartości odcienia równej lub wyższej od progu. Próg binaryzacji był każdorazowo dobierany do obrazu.

Następnie korzystając z funkcji bwmorph wykonującej morfologiczne operacje na obrazach binarnych, realizowaliśmy kolejno nastepujące operacje:
1. usuwanie pojedynczych czarnych pikseli znajdujących się na białych polach
2. zapełnianie pojedynczych białych pikseli znajdujących się na czarnych polach
3. zapełnianie "dziur", czyli białych pól zamkniętych w polu czarnym - jest to operacja bardzo ważna dla zagadnienia identyfikacji odcisków, ponieważ owe białe pola, będące wynikiem błędów w pobieraniu odcisków, mogą wprowadzać dodatkowe, wadliwe cechy
4. odchudzanie linii

I tak z przykładowego obrazu:

otrzymaliśmy:

2.3 Ekstrahowanie cech

W kształtach linii papilarnych znajdują się pewne charakterystyczne miejsca zwane minucjami. Są to kombinację dwóch podstawowych elementów linii: zakończeń i rozwidleń grzbietów. Na każdym palcu znajduje się ich od 30 do 40. Zakłada się że już 20 minucji wystarczy do jednoznacznego określenia osoby. Wyróżnia się ich ok. 20 typów:

W naszym projekcie cechami klasyfikowanymi postanowiliśmy uczynić pozycje minucji na odcisku. Zajęliśmy się konkretnie jedną z dwóch podgrup, składającą się z rozwidleń grzbietów, szczególnie: rozwidleń pojedynczych i złączeń pojedynczych. Te dwa typy są najczęściej spotykane u każdego człowieka i stosunkowo łatwo je wykryć na obrazie przedstawiającym odcisk.

Procedura wyszukiwania minucji w naszym programie prezentuje się następująco:
Kolejno dokoła każdego piksela w obrazie są wyznaczane dwa kwadraty. Jeden mniejszy o boku 5pix, jeden większy mierzący 9pix, tak ja zostało to zaprezentowane na poniższym rysunku:

Następnie sprawdzane jest, ile razy każdy z tych kwadratów zostanie przecięty przez pola o kolorze czarnym. Jeśli oba zostaną przecięte dokładnie po 3 razy, oznacza, że wykryły rozchodzące się trzy linie z punktem styku gdzieś w pobliżu punktu (i,j), a więc mamy minucję. Jeśli tylko jeden z nich zostanie przecięty 3 razy, inny z inną ilością - oznacza to, że trafił na jakieś fragmenty linii papilarnych nie będące minucjami interesujących nas typów.
Dwa kwadraty zostały tutaj wykorzystane, aby maksymalnie zniwelować wpływ zanieczyszczeń obrazu na wyniki wyszukiwania cech. Duży kwadrat ma za zadanie odfiltrowywać te wyniki kwadratu mniejszego, które są jedynie niewielkimi wypustkami, a mały kwadrat pilnuje, aby nie zostały zakwalifikowane luźne linie przechodzące blisko i wykryte przez kwadrat większy, ale nie stykające się w jednym punkcie.

Minucja wykryta (każdy kwadrat przecięty 3 razy)	Brak minucji (tylko jeden kwadrat przecięty 3 razy)	Brak minucji (tylko jeden kwadrat przecięty 3 razy)	Brak minucji (kwadraty przecięte więcej niż 3 razy))

Kiedy na obu kwadratach zostaną wykryte po 3 przecięcia, a więc będzie wykryta minucja, zapamiętane zostają współrzędne punktu środka kwadratów (i,j), a cała operacja powtarzana jest dla kolejnego piksela.
Po przejściu przez wszystkie piksele w obrazie, z listy współrzędnych zapamiętanych podczas wyszukiwania cech zostają usunięte te współrzędne, które znajdują się w odległości mniejszej niż 20 jednostek od innej (odległość wyznaczana średniokwadratowo). Ma to za zadanie zniwelować zwielokrotnienie współrzędnych wskazujących na jedną minucję. Nie rzadko bowiem jeśli w danym punkcje (i,j) zostanie wykryta minucja, jest ona też wykrywana w punktach sąsiednich, np. (i+1,j). Dzięki sprawdzaniu odległości i usuwaniu tych współrzędnych, które są za blisko, mamy pewność, że każda minucja na liście końcowej wymieniona będzie tylko raz.

Metoda ta jest generalnie bardzo skuteczna. Podczas testów wykrywała zdecydowaną większość minucji i kwalifikowała jako cechy niewielką ilość punktów, które minucjami nie były. Wadą jej jest to, że jest ona bardzo wymagająca co do obrazu na którym pracuje. Grafika odcisku musi być bardzo czytelna, z niewielką ilością zanieczyszczeń, a obecne zanieczyszczenia muszą być niewielkie. Wymaga także aby linie reprezentujące linie papilarne były cienkie, najlepiej o szerokości nie większej jak dwa, maksymalnie trzy piksele. Dlatego też jej zastosowanie musi być poprzedzone dobrym i dokładnym przetworzeniem obrazu na odpowiednią postać, co niestety z kolei wymaga posiadania obrazu oryginalnego dobrej jakości.

W naszym przypadku sprawowała się bardzo dobrze z pewnym wyjątkiem. Niestety w zdecydowanej większości obrazów zeskanowanych odcisków palców, dolne obszary odcisku, w pobliżu środka opuszka palca, były bardzo nieczytelne. Obszar ten podczas odbijania struktury palca na kartce miał tendencję do zlewania się, co wynikało z wypukłości tego fragmentu palca, oraz większego zagęszczenia linii papilarnych niż w innych miejscach. W efekcie był on bardzo mocno zanieczyszczony, także po całym procesie obróbki. Dlatego też zdecydowaliśmy się, w trakcie wyszukiwania cech, ograniczyć jedynie do górnej połowy obrazu prezentującego odcisk. Mogliśmy to zrobić bez większej szkody, gdyż obszar ten powinien zawierać wystarczającą ilość cech, aby móc dokonywać jednoznacznej klasyfikacji, a pomogło nam to uniknąć problemów z wieloma fałszywymi wskazaniami na dolnej, zanieczyszczonej, połowie obrazu.

2.4 Klasyfikacja i rozpoznawanie

Po rozpoznaniu cech, kiedy dysponujemy już listą pozycji minucji, mogliśmy przystąpić do klasyfikacji. Lista pozycji była kolejno porównywana z listami pozycji we wzorcach przechowywanych w bazie. Dla każdej cechy, określana była cecha we wzorcu, która znajduje się najbliżej. Następnie sprawdzana była odległość średniokwadratowa ich pozycji od siebie. Następnie odległości wszystkich tych par cech sumowane były w jedną wartość. Wartość ta była kryterium podobieństwa odcisku do wzorca. Odcisk był przyporządkowywany temu wzorcowi, dla którego suma odległości par cech była najmniejsza.

Metoda ta posiada jedną wadę: jest czuła na pozycję i orientację odciska na oryginalnym obrazie. W przypadku gdy wszystkie odciski są umieszczone mniej więcej na podobnych pozycjach i o podobnym kącie obrotu wokół środka, metoda jest bardzo skuteczna. Ale wystarczy umieścić odcisk trochę obrócony lub przesunięty, a wyniki mogą się pogorszyć.

3. Aplikacja

Program do rozpoznawania odcisków napisaliśmy w środowisku Matlab. Komunikuje się z użytkownikiem poprzez Command Window i dysponuje prostym menu wyboru. W trakcie przetwarzania obrazu odcisku otwierane jest osobne okno prezentujące aktualny wygląd przetwarzanego obrazu.
Zdecydowaliśmy się na aplikację Matlab, ze względu na dobry Image Processing toolbox zawarty w tym środowisku, oraz możliwość bardzo wygodnych operacji na macierzach, które stanowią większość wszystkich operacji wykonywanych w naszym programie. Nie bez znaczenia jest też świetna optymalizacja tego środowiska do pracy na macierzach, szczególnie pomocna podczas przetwarzania całych tablic obrazów i pozwalająca na znaczne skrócenie czasów tych czynności.

Schemat aplikacji prezentuje się następująco:

Baza odcisków składa się z pliku stan_sys.dat zawierającego informację o ilości zgromadzonych wzorców, oraz szeregu plików wzodc1.dat, wzodc2.dat, ..., wzodcN.dat. W każdym z tych plików jest przechowywany jeden wzorzec w postaci szeregu liczb odpowiadających pozycjom cech tego wzorca. Plików ze wzorcami jest dokładnie tyle, ile wzorców zgromadził program.

4. Badania i wyniki

W celu badań zgromadziliśmy odciski od 5 osób, trzech mężczyzn i dwóch kobiet, w różnym wieku z przedziału 20-60lat. Od każdej z nich pobraliśmy po 5 odcisków prawego kciuka. Jeden służył nam jako wzorzec, pozostałe cztery do klasyfikacji. Obrazy odcisków, które posłużyły za wzorzec prezentują się następująco:

osoba 1	osoba 2	osoba 3	osoba 4	osoba 5

Po wprowadzeniu wzorców do bazy programu, przeprowadziliśmy test polegający na wprowadzeniu do programu wszystkich pozostałych odcisków i sprawdzeniu na ile dobrze przyporządkuje je do wzorców. Wyniki klasyfikacji prezentują się następująco:

Skuteczność klasyfikacji odcisków na tej próbie wyniosła 90%.

Jak widać zdecydowana większość odcisków została sklasyfikowana prawidłowo. Źle natomiast sklasyfikowane zostały 2 z 4 odcisków osoby numer 2. Z odciskami tej osoby (wspominałem o niej w punkcie 2.1) mieliśmy problemy od początku. Posiadała ona niewielkie palce z bardzo wypukłymi opuszkami i w jej przypadku już uzyskanie w miarę czytelnych odcisków na kartce stanowiło nie lada wyzwanie. Potem podczas obróbki obrazy z odciskami tej osoby sprawiały dużo problemów, gdyż ciężko nam było przekształcić je na formę możliwą do dalszego przetwarzania. Także słabe wyniki w przypadku próbek odcisków tej osoby nie stanowią dla nas zaskoczenia.

5. Podsumowanie

Na początek musimy stwierdzić, że jesteśmy zadowoleni z otrzymanych wyników. Osiągnęliśmy dużą skuteczność, a błędy w klasyfikacji wystąpiły jedynie w przypadku tych odcisków, z którymi od samego początku przypuszczaliśmy, że będziemy mieć problemy. Co ważne dzięki zastosowanej metodzie system nie miał problemów z klasyfikacją odcisków o zbliżonej wielkości i kształcie, wyglądających na pierwszy rzut oka na bardzo podobne. Tym samym udało nam się poprawić wynik autora zeszłorocznego projektu, który tutaj wskazywał jedną z głównych przyczyn błędów w klasyfikacji swojej aplikacji.

Jak widać też po tej stosunkowo niewielkiej próbie testowej program zdecydowanie przedkłada dokładne i czyste odwzorowanie odcisków nad ich charakterystyczność. Odcisk osoby 2 kształtem i wyglądem zdecydowanie odstawał od reszty próbek, ale poprzez odwzorowanie o złej jakości był źle klasyfikowane. Inne odciski, mimo iż zbliżone wyglądem do siebie (szczególnie 1 i 5 osoby), były klasyfikowane bardzo dobrze, ale też ich odwzorowanie było wysokiej jakości.

Myślę, że prawdziwym założeniem będzie stwierdzenie, iż wraz ze zwiększeniem ilości odcisków w bazie, skuteczność klasyfikacji będzie spadać. Nie mniej jest wiele rzeczy, które przy większym nakładzie środków i czasu można poprawić, tak aby zachować dobrą skuteczność, lub nawet ją poprawić.

Przede wszystkim konieczne byłoby wykorzystanie innej metody zbierania odcisków. Podczas poszukiwań informacji mieliśmy okazję oglądać przykłady odcisków pobranych przy pomocy bardziej zaawansowanych, elektronicznych metod wymienionych we wstępie do punktu 2 i musimy stwierdzić, iż w porównaniu do obrazów które my uzyskiwaliśmy przy pomocy tuszu, kartki i skanera biurowego, ich jakość była rewelacyjna. Szczególnie dobrze przedstawiał się tu czytnik pojemnościowy, gwarantujący czyste, ładne linie, bez żadnych rozmazań, o wysokiej dokładności reprezentowania wszystkich detali.

Innym elementem, który można byłoby poprawić, jest sposób klasyfikacji odcisków. O ile wykrywanie minucji i zapisywanie ich pozycji spisuje się bardzo dobrze, o tyle ich porównywanie już nie funkcjonuje najlepiej. Niestety bezpośrednie przypasowywanie pozycji cech ma tą wadę, że wyniki są mocno uzależnione od pozycji i orientacji odcisku na obrazie pierwotnym. Bardzo pomocne i na pewno gwarantujące znaczne poprawienie wyników, byłoby opracowanie metody porównywania dwóch zestawów cech, które niezależne byłoby od tych czynników, czyli opierało się na wielkościach stosunkowo niezmiennych. Na myśl przychodzi nam tu jedynie wyznaczanie odległości między poszczególnymi cechami dla każdego odcisku osobno, a następnie ich porównywanie. Jak wiadomo niezależnie jaka będzie orientacja i pozycja odciska, odległości pomiędzy poszczególnymi jego punktami będą jednakowe. Możliwe, że można także opracować inne sposoby.

Reasumując jesteśmy usatysfakcjonowani uzyskanymi wynikami, uważamy, że udało nam się opracować dobre metody, szczególnie przy zasobach jakimi dysponowaliśmy. Nie mniej mamy świadomość, że jest w naszym projekcie kilka rzeczy, które można by poprawić, nie mniej wymagałoby to nakładu większych środków i czasu.

6. Literatura

1. Zygmunt Wróbel, Robert Koprowski; "Praktyka przetwarzania obrazów w programie Matlab"; Akademicka Oficyna Wydawnicza EXIT 2004

2. Krzysztof Jackiewicz, Wojciech Olejowski; "Interfejs do akwizycji danych biometrycznych"; Praca dyplomowa 2004-2005

3. Claude Barral, Jean-Sebastien Coron, David Naccache; "Externalized Fingerprint Matching"