KLASYFIKACJA

 ODCISKÓW PALCÓW

 

inż. Bartłomiej Dorna

inż. Jan Bogusławski

 

Politechnika Poznańska

projekt z przedmiotu Rozpoznawanie obrazów

 

1.                Wprowadzenie

 

Każdy człowiek ma niepowtarzalne odciski palców, dlatego właśnie odciski palców są jedną z najbardziej wiarygodnych metod identyfikacji ludzi. Pośród odcisków palców możemy wyróżnić 6 klas odcisków, które pokazane są na poniższym rysunku.

 

Chociaż sama klasyfikacja do danej klasy nie wystarcza do tego, aby porównać dwa odciski, to jednak może znacznie ułatwić przeszukiwanie bazy danych – wystarczy porównywać tylko z odciskami należącymi do danej klasy. Dzięki temu można szybciej znaleźć pasujący odcisk lub otrzymać odpowiedź o jego braku w bazie.

 

2.     Punkty szczególne odcisku palca

 

W każdej klasie odcisków (poza ARCH) można wyróżnić punkty szczególne dwóch typów. Są to tzw. core i delta. Poniższy rysunek obrazuje ich położenie dla poszczególnych klas odcisków.

 

 

3.     Opis algorytmu

 

Wejście dla algorytmu stanowi obraz o rozdzielczości 512x512 punktów. Nasz algorytm jest algorytmem iteracyjnym. Można go podzielić na dwa etapy:

-                etap preprocesingu

-                etap klasyfikacji

 

3.1.    Etap preprocesingu

 

Poszczególne fazy tego etapu pokazane są na poniższym diagramie:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Gradienty

 

Do obliczenia gradientów poziomego i pionowego można zastosować jeden z filtrów górnoprzepustowych, my zastosowaliśmy filtr Sobela.

            Obliczenie gradientu polega na obliczeniu pierwiastka z sumy kwadratów gradientu pionowego i poziomego, następnie jeśli wartości większe od 255 są zmniejszane do 255.

Wyznaczenie maski to wyliczenie średniej arytmetycznej z wartości gradientu i jasności w kolejnych punktach obrazu. (Jasność podajemy przekształceniu w negatyw tzn. kolor czarny ma wartość 255, a biały 0).

 

Maska informuje nas o stopniu w jaki punkt należy do odcisku lub do tła. Posłuży nam do usunięcia szumów z directional image.

 

 

Directional image

 

 

     Dla każdego punktu obrazu wyznaczamy w jakim kierunku przebiega linia przechodząca przez ten punkt. Sprawdzenie to odbywa poprzez obliczenie sum odzwierciedlających siłę danego kierunku. Obliczenia przeprowadzamy dla 8 kierunków: 0º, 22,5º, 45º, 67,5º, 90º, 112,5º, 135º, 157,5º. Sumy wyliczamy za pomocą maski 9x9 osobno dla każdego kierunku. Rozmieszczenie punktów szczególnych na masce dla każdego z kierunku pokazuje rysunek (na rysunku kierunki są kodowane kolejnymi liczbami tak więc 0 to 0º, 2 to 45º itp.).

 

 

Następnie z obliczonych sum wyznaczamy kierunek w dla którego suma ma wartość minimalną (p) i maksymalną (q). Kierunek w danym punkcie będzie miał wartość p jeśli punkt leży na grzbiecie (ciemny obszar) i wartość q jeśli leży w dolinie (jasny obszar). Jeśli jasność w punkcie ma wartość C, to kierunek można wyznaczyć jako:

 

Dzięki temu w każdym punkcie kierunek jest skwantowany do 8 wartości. Wartości te są z reguły bardzo zaszumione, dlatego należałoby je uśrednić w lokalnym sąsiedztwie. Ponieważ wartości te reprezentowane są w postaci modulo 8 zwykłe uśrednianie nie da poprawnych rezultatów. Dlatego też przekształcamy te do postaci wektorowej.

Dla każdego punktu jego kierunek reprezentuje wektor v = (cos 2α, sin 2α), gdzie α to kierunek w danym punkcie. Dla takiej reprezentacji uśrednianie daje poprawne wyniki, po prostu uśredniamy najpierw pierwszy składnik wektora, a potem drugi.

 

Po obliczeniu directonal image dla obrazu 512x512 dzielimy go na bloki 8x8 i uśredniamy wektory kierunków w każdym bloku. Jako wynik mamy directional image o rozmiarze 64x64 nazywany dalej block directional image. Na tym obrazie będą przeprowadzane wszystkie dalsze obliczenia.

 

Usuwanie szumów odbywa się podobnie jak obliczanie block directional image z tym, że działamy teraz na masce. W każdym bloku 8x8 maski obliczamy średnią wartość i jeśli jest ona większa od pewnego progu (u nas 75) to dany punkt w block directional image będzie brany pod uwagę w dalszych obliczeniach, jeśli jest mniejsza to nie będzie brany pod uwagę. W ten sposób usuwamy bloki zawierające tło i szumy.

 

3.2.         Etap klasyfikacji

 

Postępowanie podczas etapu klasyfikacji pokazuje poniższy diagram.

 

 

 

Operujemy tutaj na obrazie 64x64 (block directional image), znajdujemy na nim punkty core i delta. Dopóki ich ilość ich par nie będzie mniejsza od 2 uśredniamy obraz i szukamy punktów ponownie (uśrednianie przerywamy w momencie gdy ilość punktów obu typów będzie równa sobie i zarazem mniejsza od 2).

 

 

Znajdowanie punktów szczególnych

 

 

Niech S(x,y) oznacza kierunek w punkcie (x,y).

 

Punkty typu delta znajdujemy w następujący sposób:

 

Punkt jest możliwym punktem typu delta jeśli:

 

S(x-1,y+1)<= S(x,y) < S(x+1.y+1) ,  0˚<S(x-1,y+1)< 90˚ , S(x+1, y+1) > 90˚.

 

Punkt który  spełnia powyższe zależności jest następnie weryfikowany przez sprawdzenie jego sąsiedztwa:

 

22.5˚ < S(x-1,y) <= 90˚ ,  90˚ <= S(x+1,y) <157,5˚ ,

S(x,y+1) < 45˚  ,  45˚ <= S(x, y-1) <= 135˚

 

Jeśli sąsiedztwo spełnia te zależności to punkt zostaje zakwalifikowany jako delta.

 

Punkty typu core znajdujemy w następujący sposób:

 

Punkt jest możliwym punktem typu core jeśli:

 

45˚ < (S(x,y) – S(x,y-1)) < 135˚

 

Następnie sprawdzane jest jego sąsiedztwo:

 

0˚ < (S(x-1, y-1) – S(x,y-1)) <45˚ , 90˚ < (S(x+1, y-1) – S(x, y-1)) <= 157,5˚

 

Jeśli sąsiedztwo punktu spełnia powyższe zależności to punkt jest zakwalifikowany jako core.

 

Ponieważ taki sposób wykrywania punktów szczególnych jest podatny na rotację, dlatego też punkty są sprawdzane w sąsiedztwie względem rotacji o kąt 0˚, 45˚, 90˚, 135˚, 180˚, 225˚, 270˚, 315˚. Aby przyspieszyć obliczenia nie wszystkie kąty są  sprawdzane. O tym które kąty są sprawdzane decyduje kierunek w punkcie. Jeśli jest on np. równy 45˚ to sprawdzane są kąty 45˚ i 215˚, ponieważ względem innym na pewno nie spełni warunków koniecznych.

Jak łatwo zauważyć podane powyżej warunki na znalezienie punktów szczególnych pasują tylko dla kąta 0˚. Dla pozostałych należy je nieco zmodyfikować. Modyfikacji ulegają zarówno współrzędne punktów sąsiedztwa jak i kierunki w  punktach.

Modyfikacja współrzędnych polega na obróceniu ich o dany kąt np. dla kąta 90˚ punkt który w wzorze miał współrzędne S(x,y-1) po obrocie ma współrzędne S(x-1,y).

Modyfikacja kierunków w punktach polega na dodaniu do kierunku w punkcie wartości o jaki kąt zachodzi rotacja, a następnie obliczeniu modulo 180˚ (ponieważ kierunki w punktach mogą mieć tylko wartości z przedziału <0˚, 157,5˚>).

 

Po odnalezieniu wszystkich punktów szczególnych następuje ich odfiltrowanie. Jeśli jakiś punkt delta jest w bezpośrednim sąsiedztwie punktu core, to oba punkty zostawały usuwane. Jeśli punkt znajdował się w odległości 10 punktów (w obrazie 64x64) od granicy obrazu to punkt ten zostawał usunięty. Te czynności mają za zadanie pozbycie się punktów z obrzeży odcisku, gdyż są to fałszywe punkty.

 

 

Klasyfikacja

 

Jak widać na diagramie o tym do jakiej klasy zostanie przydzielony odcisk zależy od ilości par core – delta. Jeśli nie ma takiej pary to klasyfikowany jest jako ARCH. Jeśli jest jedna to może to być TENTED ARCH albo LOOP. Jeśli są dwie pary to może to być WHORL albo TWIN LOOP. Położenie punktów core  i delta dla tych klas pokazuje poniższy rysunek

 

 

 

 

Rozróżnienie TENTED ARCH od LOOP

 

Aby rozróżnić te dwa typy odcisków łączy się punkt core i delta linią prostą i obliczenie poniższego wyrażenia:

 

 

gdzie β to kąt nachylenia prostej, a α1, α2, ... αn to kierunki w poszczególnych blokach przez które przechodzi prosta. Jeśli ta wartość jest mniejsza od progu (u nas 0,2) to odcisk zostaje sklasyfikowany jako TENTED ARCH w przeciwnym wypadku jest to LOOP.

            Rozróżnienie LEFT LOOP od RIGHT LOOP polega na określeniu po której stronie punktu delta znajduje się punkt core. Jeśli jest po lewej to odcisk klasyfikujemy jako LEFT LOOP, w przeciwnym wypadku jest to RIGHT LOOP. Sprawdzenie na obliczeniu różnic pomiędzy współrzędnymi punktu delta i core i pomnożeniu ich. Jeśli wynik jeśli wynik jest mniejszy od zera to punkt core leży na prawo od punktu delta.

 

 

Rozróżnienie WHORL od TWIN LOOP

 

Rozróżnienie tych dwóch klas jest podobne do rozróżnienia TENTED ARCH od LOOP z tą różnicą, że łączymy dwa punkty core Jeśli wynik jest mniejszy od progu (u nas 0.2) to odcisk klasyfikujemy jako WHORL w przeciwnym wypadku jest to TWIN LOOP.

 

 

4.           Referencje

 

 

1.             N. Ratha, S. Chen, A.K. Jain, K. Karu, A Real-time Matching System for Large Fingerprint Databases

2.             K. Karu, A.K. Jain, Fingerprint Classification, 1995

3.             M. Ballan, F.A. Sakaraya, B. Evans, A Fingerprint Classification Technique Using Directional Images