15.06.2007
Przedmot: Metody i algorytmy sztucznej inteligencji ARE3513
Prowadzący: dr inż. Witold Paluszyński
Autor Projektu: Michał Antosz 133050
rok studiów: IV, semestr: VIII
Wydział: W-4: Elektronika
Kierunek: AIR, Specjalność: ARS
Rozpoznawanie odcisków palców
1. Wstęp.
Rozpoznawanie odcisków palców jeszcze do niedawna było zagadnieniem wyłącznie z dziedziny kryminologii. Ostatnio jednak jest coraz bardziej rozpowszechnione m.in. do reprezentacji paszportowych danych biometrycznych, a także do wszelkiego rodzaju zabezpieczeń i autoryzacji ( ostatnio nawet w laptopach).
Celem projektu było zrealizowanie programu klasyfikującego odciski palców. Aby można było to wykonać trzeba dysponować bazą danych zawierającą odciski palców w formie która będzie poddawana klasyfikacji. Projekt swoim zakresem obejmuje:
1) zagadnienie zbudowania bazy danych pozwalającej na przechowywanie informacji o osobach i ich odciskach palców.
2) filtrowania obrazów i ich obróbki polegającej na przygotowaniu do klasyfikacji.
3) rozpoznawania obrazów i ich klasyfikacji
2. Metoda rozwiązania problemu.
Zadanie rozpoznawania odcisków palców jest dość skomplikowane zarówno implementacyjnie jak i trudne do zrealizowania manualnie. Tak też podzieliłem problem na trzy podproblemy: ściągnie odcisków palców i ich skanowanie, obróbka graficzne próbek oraz rozpoznawanie i klasyfikacja.
2.1. Skanowanie odcisków palców
Samo przygotowanie próbek odcisków palców było dość kłopotliwe. Głównym problemem była technika ściągania odcisków palców. Pierwotnie były testowane techniki cyfrowe- bezpośrednie skanowanie palca oraz robienie zdjęć. W pierwszym przypadku obraz praktycznie nigdy nie był zadowalający. Palec z racji na swój kształt nie mógł być poprawnie zeskanowany skanerem biurowym. Przy za małym docisku linie papilarne były dobrze widoczne tylko na małym obszarze, a przy za dużym docisku nie były praktycznie wcale widoczne. Sytuacje tą przedstawiają poniższe rysunki- zdjęcia oryginalne ze skanera i po nałożeniu filtru:
|
|
|
|
Technika ta okazała się niewystarczająca. Nawet jeżeli dało by się powtarzalnie uchwycić linie papilarne, to i tak ciężko by było je okonturować, ponieważ kontrast skóry na liniach jest praktycznie niezauważalny. Z tego samego powodu odpadły metody robienia zdjęć.
Zdecydowałem się użyć starej sprawdzonej metody odbiciowej. Pozwala ona zachować duży kontrast i jest wygodna do dalszej obróbki po zeskanowaniu. Wypróbowano kilka różnych technik, ale w domowych warunkach najskuteczniejsze okazało się korzystanie z tuszownicy używanej normalnie wraz z pieczątką. Odbicia wykonywano na kartce A4, a następnie skanowano w rozdzielczości 200dpi:
Ta technika wprawdzie była najlepsza, ale jak widać na powyższym obrazku nie była idealna. Aby zminimalizować błąd metody, odbicia które były bardzo kiepskiej jakości były od razu eliminowane.
2.2. Obróbka graficzna
Po zeskanowaniu otrzymywany był obraz w formacie BMP o wymiarach 180x300 pikseli. Aby wygodnie przetwarzać obrazy dobrze mieć ich łatwą reprezentację. Dlatego też pliki zostały zamienione na format PGM( Portable GrayMap), który charakteryzuje się zapisem odcieni szarości w skali zdefiniowanej w nagłówku pliku(domyślnie 256 odcieni, przy czym 255 oznacza kolor czarny, a 0 kolor biały). W nagłówku jest też zdefiniowana wysokość i szerokość obrazka.
Dzięki tak łatwej reprezentacji można w prosty sposób używać przetważania obrazów za pomocą macierzy konwolucji[2]. Spośród gotowych filtrów trudno było znaleźć jakiś, który dobrze wyostrzał by krawędzie biegnące we wszystkich kierunkach, bo tak właśnie zachowują się linie papilarne. Ostatecznie wybór padł na lekko zmodyfikowany filtr Prewitta. Macierz konwolucji ma następującą postać:
Odcisk palca jest dość trudny do filtrowania, ponieważ nie ma krawędzi, które się rozchodzą w podobnych kierunkach. Po filtracji macierzą konwolucji, zastosowałem jeszcze binaryzację obrazu i na tym skończyła się jego obróbka graficzna. Efekt jest widoczny poniżej:
 Odcisk palca 1 |
 Odcisk palca 2 |
 Odcisk palca 1 z filtrem i binearyzacją |
 Odcisk palca 2 z filtrem i binearyzacją |
2.3. Rozpoznawanie i klasyfikacja
Ostatnią rzeczą jaką należało zrobić przed rozpoznawaniem, było poprawne zorientowanie obrazu. Z założenia obraz był odbijany pod dobrym kątem, więc zorientowanie sprowadzało się jedynie do zlokalizowania odcisku palca na obrazie 180x300 pikseli. Było to realizowane poprzez wyznaczanie pionowej i poziomej linii, stycznych do odcisku od góry i od lewej strony. Te wirtualne linie pomocnicze będą też wykorzystywane do rozpoznawania obrazu.
Cechą pod względem której obraz jest rozpoznawany jest ilość występowania czarnych prążków wzdłuż kilku linii pionowych i poziomych. Linie pionowe występują w odległości +25 +50 i +75 pikseli w prawo od linii pomocniczej pionowej. Linie poziome występują w odległości +30,+75,+100,+125 oraz +150 pikseli w dół od linii pomocniczej poziomej, tak jak na poniższym rysunku:
, gdzie wr to wartość liczbowa znacznika obrazu rozpoznanego, a ww, to wartość liczbowa znacznika wzorca. Następnie przechodząc do klasyfikacji- wybieramy dla każdej z charakterystycznych ośmiu liczb te, które mają jak najmniejszy błąd. Tak uzyskujemy osiem liczb, które również mówią nam do której osoby (w każdej z ośmiu dziedzin) odcisk palca jest najbardziej podobny. Ostatecznie klasyfikujemy rozpoznawany obraz do klasy osoby, do której należy większość ze znaczników z minimalnym błędem.
3. Opis programu.
Program został napisany w języku C++, jest aplikacją konsolową, z podręcznym menu wyboru. Program został napisany w oparciu o tablice o stałej wielkości. Baza danych przechowywana jest w pliku tekstowym, który przy uruchomieniu jest przepisywany do pamięci programu i na niej wykonują się wszelkie operacje. Po wyrażeniu przez użytkownika chęci wyjścia z programu, plik bazy jest nadpisywany aktualnymi wartościami. Ogólny schemat działania programu przedstawia poniższy schemat blokowy:
4. Przykłady działania programu.
Program może działać z trzech trybach. W trybie Dodawania nowej osoby do bazy danych; dodawania odcisku palca osobie zapisanej do bazy danych oraz w trybie rozpoznawania odcisku palca.4.1. Dodawanie nowej osoby
Każda osoba w bazie danych ma przyporządkowaną sobie strukturę składającą się z: imienia, nazwiska, ilości próbek oraz ośmiu liczb definiujących charakterystyczne wartości liczbowe prostych. Gdy dodajemy nowego użytkownika wszystkie pola oprócz imienia i nazwiska są wypełniane zerami.
4.2. Dodawanie odcisku palca
Gdy dodajemy odcisk, to danemu użytkownikowi zwiększa się o jeden liczby próbek. Liczby określające osiem charakterystycznych liczb użytkownika zmieniają się wg. średniej ważonej z aktualnych wartości i nowej wartości z wagami dla aktualnych wartości równymi ilości próbek i waga nowej próbki równa jeden. Jest to oczywiście równoznaczne ze średnią arytmetyczną wszystkich wartości danej liczby charakterystycznej, które kiedykolwiek zostały dodane. Kiedy mamy już kilka odcisków danej osoby, możemy przejść do punktu 4.3 gdzie następuje rozpoznawanie.
4.3. Rozpoznawanie odcisku palca
Algorytm rozpoznawania i klasyfikacji był omawiany w punkcie 2.3. Program prosi o podanie pliku wejściowego z odciskiem palca i następuje rozpoznawanie i klasyfikacja do wzorców istniejących w bazie.
4.4. Reprezentacja bazy danych
Po wykonanych czynnościach nasza baza danych reprezentowana jest poniższym plikiem:
7Pierwsza cyfra to ilość osób w bazie danych. Przy Nazwisku pierwsza liczba to ilość próbek, a reszta to osiem charakterystycznych liczb, głębiej opisanych w punkcie 2.3.
5. Badania i wyniki.
W badaniach uczestniczyło sześć osób w wieku 18-57 lat, trzy kobiety i trzej mężczyźni. Każda osoba dodana do bazy dodała przynajmniej 11 próbek (a cztery osoby ponad 15 próbek). Poglądowe spojrzenie na próbki daje poniższa tabela:
 Michał A- nr 1 |
 Ewelina P- nr 2 |
 Jan A- nr 3 |
 Kasia N- nr 4 |
 Andrzej A- nr 5 |
 Maria A- nr 6 |
Przed samą implementacją programu przeprowadzono wstępne badania mające na celu m.in. ustalenie ile prostych charakterystycznych należy użyć aby dobrze rozpoznawać obraz. Wybrano trzy proste pionowe i pięć poziomych. Wprawdzie w punkcie 2.3 widać jakoby można było jeszcze dołożyć 3-4 proste, to trzeba mieć na uwadze, że przykład 2.3 jest reprezentowany na dużym odcisku palca, a mogą się zdarzyć mniejsze, a wtedy proste leżały by poza odciskiem. Badania wstępne wykazały również, że znaczne zagęszczanie prostych nie poprawia tak bardzo wyników, ponieważ linie papilarne nie zmieniają bardzo szybko kierunków.
Główny test polegał na podaniu do systemu 5 dodatkowych próbek do rozpoznania od każdej osoby ( próbki te były tylko dane do rozpoznania- nie były wcześniej ani później zapamiętywane w bazie). Testy wypadły następująco:
| Osoba | Wynik testu[1..5] |
| Michał A (nr 1) | 1,1,5,1,1 |
| Ewelina P (nr 2) | 6,2,2,2,2 |
| Jan A (nr 3) | 3,3,3,6,6 |
| Kasia N (nr 4) | 4,4,6,4,6 |
| Andrzej A (nr 5) | 5,5,5,5,1 |
| Maria A (nr 6) | 6,6,6,6,6 |
6. Wnioski.
-Projekt byl ciekawym doswiadczeniem, choc jego wyniki nie sa w pelni satysfakcjonujace. Niestety u niektórych osób różnice w rozpoznawaniu są bardzo duże- u dwóch osób tylko 3/5 próbek zostało pomyślnie rozpoznanych. Tylko u jednej osoby zostały rozpoznane wszystkie próbki testowe. Można przewidzieć, że dla większej ilości osób jakość rozpoznawania będzie się coraz bardziej pogarszać.
- Widać powiązanie między wynikami testów a przykładowymi próbkami zamieszczonymi w tabeli. Odciski palców nr 1 i nr 5 są bardzo podobne wielkościowo- system okazał się w błędzie w 20% przypadków dla tych próbek wnioskując na rzecz przeciwnej. Myślę też, że nie bez faktu pozostał wyjątkowy kształt odcisku nr 6- był on rozpoznawany w 100%.
- Wprawdzie ilość osób testujących była mała, ale wydaje się zauważać zależność, że im odcisk mniejszy tym łatwiej go pomylić ( chyba, że ma wyjątkowy kształt jak nr 6). Odciski 1 i 5 są duże, a ich linie papilarne dość wyraźne, wiec system nie ma tu gdzie się pomylić, choć czasem mu się zdarza. Istnieje też jakieś prawdopodobieństwo, że system miał trochę utrudnione zadanie, z racji tego, że 4 osoby są z jednej rodziny i niewielkie podobieństwa w ogólnej budowie linii papilarnych mogą występować.
-Ciekawym doświadczeniem było by skonfrontowanie powyższego systemu z sieciami neuronowymi. Jest wielce prawdopodobne, że sieci neuronowe działały by lepiej, szczególnie dla większej ilości osób, jeżeli cykl uczenia był by wystarczająco długi. Aczkolwiek, jak na prostotę tego systemu rozpoznającego i tak jestem zadowolony z wyników jakie osiąga.
-Nie udało się znaleźć filtru, który dobrze eksponował krawędzie we wszystkich kierunkach. Możliwe, że gdyby odciski były mniej zamazane ( czasem sąsiednie linie papilarne nawet na siebie zachodzą), to wyniki były by lepsze. Można by nawet pokusić się o stwierdzenie, że przy bardzo dokładnym odbiciu wystarczył by jedynie filtr binarny.
-Na wynik rozpoznawania duży wpływ mają cechy indywidualne osoby- jak dokładnie przytknie palec, jaką jego część przyłoży do kartki, jak mocno naciśnie itp. Choć nie wiadomo za bardzo jak to zinterpretować, ponieważ może mieć to skutki pozytywne dla realizowanej metody rozpoznawania ( osoba może zawsze tak samo przytykać palec), jak i negatywne- niestałość warunków początkowych.
7. Literatura.
3. Externalized Fingerprint Matching
4. Minutia vs. Pattern Based Fingerprint Templates. (2003)