Weryfikacja odcisków palców

Krzysztof Mieloch
30.06.2003
Raport z projektu ze Sztucznej Inteligencji

Porównywanie odcisków palców jest jedną z najbardziej niezawodnych metod identyfikacji osób. Jednakże ręczne porównywanie odcisków jest tak czasochłonne, nużące i kosztowne, że nie może być wykorzystywane w codziennych procedurach identyfikacji. Dlatego ważne jest rozwijanie automatycznego systemu identyfikacji i weryfikacji osób. W tej pracy zostanie przedstawiony i zaimplementowany sposób weryfikacji osób wykorzystujący lokalne podobieństwo strukturalne obrazów odcisków.

1. Wstęp

Problem rozpoznawania osób na podstawie odcisków palców może być podzielony na dwa zasadniczo różne problemy:

weryfikacja - polega na stwierdzeniu, czy osoba, której odcisk palca został zeskanowany, jest osobą, za którą się podaje.
identyfikacja - polega na określeniu tożsamości tej osoby.

Do wykonania któregokolwiek z tych dwóch zadań potrzebujemy bazy danych, w której będą przechowywane, zeskanowane wcześniej i odpowiednio przetworzone odciski palców. Weryfikacja będzie polegać na porównaniu elementu otrzymanego z odpowiednim elementem w bazie, identyfikacja natomiast na wyszukaniu pasującego elementu w bazie. Identyfikacja może być również rozpartywana jako weryfikacja otrzymanego odcisku palca z każdym posiadanym w bazie.

W rozdziale 3. zostały przedstawione metody przygotowania obrazu odcisku do obróbki. Wybrałem metody, które wg mnie przygotowuja najlepiej obraz dla algorytmu weryfikacji opisane w rozdziale 4. Algorytm ten został zaczerpnięty z pracy [2]. W rozdziale 5. przedstawione zostaną wyniki działania.

2. Opis odcisku palca

Na rysunku 2 przedstawiony jest przykładowy odcisk palca.

Odcisk palca składa sie z linii papilarnych. Na nich możemy wyróżnić punkty szczególne. Jedną z grup punktów szczególnych są tzw. minucje. Są one lokalnymi nieciągłościami w obrazie odcisku palca, które odpowiadają zakończeniu bądź rozgałęzieniu się grzbietu linii papilarnej.

**Rysunek 1:** Minucje
$\includegraphics{2.eps}$

Weryfikacja przedstawiona tutaj będzie polegała na znajdowaniu podobieństw i różnic między odpowiednimi minucjami w obudwu obrazach.

3. Przygotowanie obrazu

Ten etap ma na celu przygotowanie obrazu wejściowego do obróbki, jak również wyeliminowanie zniekszktałceń powstałych podczas pobierania próbki.

**Rysunek 2:** Obraz odcisku palca otrzymany ze skanera
$\includegraphics{finger_1.eps}$

Binaryzacja

Na wejściu dostajemy obraz odcisku palca w 256 odcieniach szarości (jako macierz rozmiaru N×N). Procedura binaryzacji redukuje liczbę kolorów do dwóch. Kolor biały jest kolorem tła, a czarny - linii papilarnych.

Obraz jest przetwarzany wg wzoru:

B(x, y) = $\displaystyle \left\{\vphantom{ \begin{array}{ll} 1 & \textrm{jeśli $G(x,y)>T$} \\ 0 & \textrm{w.p.p.} \end{array} }\right.$ $\displaystyle \begin{array}{ll} 1 & \textrm{jeśli $G(x,y)>T$} \\ 0 & \textrm{w.p.p.} \end{array}$

gdzie T jest odpowiednio dobranym progiem. Dobór odpowiedniego progu dla całego obrazu jest zazwyczaj niemożliwy. Dlatego obraz jest dzielony na cześci rozmiaru n_bin×n_bin. Kolejno w każdej z nich obliczana jest wartość średnia intensywności czerni i ona jest progiem w odpowiadającej części.

**Rysunek 3:** Po binaryzacji
$\includegraphics{finger_2.eps}$

Wypełnianie dziur

Bardzo często można zauważyć, że na zeskanowanym obrazie linie mają małe obszary w kolorze tła. Niestety, te obszary (zwane dziurami) w momencie wyszczuplania linii (patrz następny rozdział) powoduja powstawanie pętli.

$\includegraphics{hole1.eps}$			$\includegraphics{hole2.eps}$
niewypełniona dziura			wypełniona dziura

Dla każdego obszaru w kolorze tła wyliczany jest jego rozmiar. Jeśli nie przekracza on pewnej wartości progowej (ustalonej doświadczalnie w zależności od skanera), to ten obszar wypełniany jest kolorem linii.

**Rysunek 4:** Obraz odcisku palca po wypełnieniu dziur
$\includegraphics{finger_holes.eps}$

Wyszczuplanie

Grubość wszystkich linii papilarnych zostaje zredukowana do jedności. Zastosowany został algorytm dwufazowy (A two-pass thinning algorithm) opisany w [1].

**Rysunek 5:** Obraz odcisku palca po wyszczupleniu linii
$\includegraphics{finger_thined.eps}$

Znajdowanie minucji

Jeśli narysujemy okrąg o środku w zakończeniu linii (rys 1) i odpowiednio małym promieniu, to powinien być dokładnie jeden punkt przecięcia okręgu z liniami papilarnymi. Dla rozdzielenia powinny być dokładnie trzy punkty przecięcia. Dlatego, aby znaleść minucje postępujemy następująco: W każdym punkcie q obrazu obliczana jest formuła:

C_q = $\displaystyle \sum_{k=0}^{7}$ B((k + 1) mod 8) - B(k)

gdzie indeks k przebiega po wszystkich ośmiu sąsiadach punktu q. Liczba C_q określa liczbę zmian kolorów na ,,okręgu'', czyli jest dwa razy większa od liczby przecięc. Zatem jeśli C_q = 2, to punkt q jest zakończeniem, a gdy C_q = 6 - rozdzieleniem. Pozostałe wartości C_q są ignorowane.

Dla każdej minucji zapamiętywane jest:

współrzędne x i y.
wartości funkcji sinus i cosinus dla kąta $\theta$ między linią, do której znaleziona minucja należy, a osią X
typ minucji: zakończenie lub rozdzielenie.

**Rysunek 6:** Obraz odcisku palca z zaznaczonymi minucjami i ich kierunkami (kolor czerwony - zakończenia, niebieski - rozdzielenie)
$\includegraphics{finger_minutiae.eps}$

Usuwanie przerw w liniach

Na skutek zniekształceń obrazu może dojść do przerwania linii. Dlatego dla każdej pary zakończeń leżących odpowiednio blisko sprawdzane jest, czy różnica kątów jest w okolicy $\pi$ (kierunki obydwu zakończeń są przeciwne). Jeśli tak, to te zakończenia są usuwane, a linie łączone.

**Rysunek 7:** Obraz odcisku palca z zaznaczonymi minucjami po usunięciu przerw w liniach
$\includegraphics{finger_found_breaks.eps}$

4. Weryfikacja

Do weryfikacji użyto algorytmu opisanego w [2].

Reprezentacja i definicje

DEFINICJA MAG (Minutiae Adjacency Graph)

MAG jest reprezentowany przez G = (V, E), gdzie:

V jest zbiorem wierzchołków reprezentujących minucje
E jest zbiorem krawędzi (krawędź w grafie istnieje, gdy minucje odpowiadające wierzchołkom krawędzi są połączone bezpośrednią linią)
Wierzchołek v $\in$ V jest reprezentowany przez krotkę v = (x, y, sin $\theta$ , cos $\theta$ ). Gdzie v.x i v.y - współrzędne minucji; $\theta$ - kąt nachylenia między linia do której minucja należy a osią x.
Krawędź e $\in$ E jest reprezentowana przez krotkę e = (u, v, rad, rc, sin $\phi$ , cos $\phi$ ) e.u - wierzchołek początkowy; e.v - wierzchołek końcowy; e.rad - odleglość Euklidesowa między tymi wierzchołkami; e.rc - liczba krawędzi, które przecina odcinek łączący te wierzchołki; $\phi$ - kąt miedzy odcinkiem łączącym, a osią X.

DEFINICJA Otoczenie

Zbiór wierzchołków, nbr(u) = {x : dist(u, v) $\leq$ d_max}, gdzie dist(u, v) jest odległością euklidesową między punktami u i v na obrazie; d_max jest odpowiednio dobraną stałą

DEFINICJA Gwiazda

Zbiór krawędzi, star(u) = {ux : x $\in$ Nbr(u)}

Algorytm weryfikacji

Wejściem są dwa odciski palców reprezentowane przez ich MAGi, MAG₁ = (V₁, E₁) i MAG₂ = (V₂, E₂). Wyjściem jest znormalizowana miara podobieństwa, która ma wartości między 0 (obrazy nie przedstawiają tego samego odcisku palca) a 100 (obrazy przedstawiają ten sam odcisk palca).

Algorytm można podzielić na etapy:

Rozpatrzmy pary wierzchołków: u $\in$ V₁ i v $\in$ V₂. Jeśli MAG₁ i MAG₂ reprezentują obrazy tego samego odcisku palca, to można zaobserwować, że gwiazdy wokół odpowiadających sobie u i v wyglądają podobnie pod wzgędem odległości, kątów i liczby przecinanych krawędzi. Strict matching phase próbuje znaleść takie dobre dopasowania przez porównywanie gwiazd wszystkich możliwych par.
Jeśli (u₁, v₁) i (u₂, v₂) są dwoma dobrymi dopasowaniami, to krawędź u₁u₂ powinna być podobna do v₁v₂. Jest to sprawdzane w consistency check phase

Strict matching phase

W tej fazie minucje z obydwu obrazów są parowane. Dla każdej pary wierzchołków m i n obliczana jest funkcja kosztu ich sparowania - C_{m, n}.

Niech N₁ i N₂ będą otoczeniami odpowiednio m i n. Para (m, n) jest brana pod uwagę tylko, jeśli

min(size(N₁), size(N₂)) $\displaystyle \geq$ N_min

gdzie N_min jest stała dobraną doświadczalnie.

DEFINICJE:

Krawędzie do dopasowania
Dwie krawędzie e₁ i e₂, dla których różnica kątów jest mniejsza od stałej c_diff i
$\displaystyle {\frac{\vert e_1.rad-e_2.rad\vert}{\min(e_1.rad,e_2.rad)}}$ $\displaystyle \leq$ d_rel
Koszt dopasowania krawędzi

d_r = $\displaystyle {\frac{\vert e_1.rad-e_2.rad\vert}{d_{rel}\min(e_1.rad,e_2.rad)}}$
Koszt dopasowania wierzchołków

C_{m, n} = $\displaystyle {\frac{\sum d_r + \sum d_\phi}{N_{(m,n)}^2}}$
Gdzie d = ${\frac{\vert\theta_1-\theta_2\vert}{D_\phi}}$ .
Zbiór TOP
Zbiór TOP zawiera T_m (odpowiednio dobrana stała) par wierzchołków o najmniejszym koszcie dopasowania.
Koszt strict matching phase

C_strict = $\displaystyle {\frac{\sum_{(u_i,v_i)\in TOP} C_{u_i,v_i}}{T_m}}$

Niech S₁ i S₂ będą gwiazdami wokół odpowiednio m i n. Wybieramy krawędzie e₁ $\in$ S₁ i e₂ $\in$ S₂ o najmniejszym koszcie dopasowania. Następnie krawędzie (e₁, e₂) dopasowywane są do (f₁, f₂) na zasadzie minimalizacji różnicy kątów $\theta_{1}^{}$ = $\overline{e_1,m,e_2}$ i $\theta_{2}^{}$ = $\overline{f_1,m,f_2}$ . Po obliczeniu kosztu dopasowania dla wszystkich par wierzchołków, tworzony jest zbiór TOP zawierający T_m najlepszych dopasowań.

Consistency check phase

Sprawdzamy zgodność sparowanych wierzchołków w zbiorze TOP.

Para (u_i, v_i) $\in$ TOP jest zgodna, jeśli przynajmniej N_m elementów z {(u_iu_j, v_iv_j) : j = 1, 2,..., T_m} jest zgodnych krawędziowo i wierzchołkowo. Zbiór TOP jest zgodny, jeśli zawiera przynajmniej N_m zgodnych par.

DEFINICJA Koszt consistency check phase

C_consistency = $\displaystyle {\frac{\sum c_{cons\_pair}(u_i,v_i)}{N}}$

Gdzie c_{cons_pair} jest średnią kosztów dopasowania krawędzi.

Parametry i podejmowanie decyzji

Parametry zostaly dobrane eksperymentalnie.

Dla 80 < d_max < 100 w otoczeniu było średnio 10 - 13 wierzcho2ków. Pozostałe parametry: T_m = 8; d_rel = 0.15; c_diff = 3; D = 0.1; f_min = 0.7.

Miara podobieństwa jest obliczana według wzoru:

100 - CONST*C_strict*C_consisteny

gdzie stała CONST jest dobrana tak, aby normował miarę między 0 a 100.

5. Wyniki

Przedstawiony powyżej algorytm został zaimplementowany w języku C++ (środowisko: Borland C++ Builder).

Testy

Do testów wykorzystano następujące obrazy odcisków palców:

**Rysunek 8:** Osoba A, 3 skany jednego palca. Oznaczmy je kolejno od lewej przez: A11, A12, A13
$\includegraphics[width=4.5cm]{ania1_1.eps}$ $\includegraphics[width=4.5cm]{ania1_2.eps}$ $\includegraphics[width=4.5cm]{ania1_3.eps}$

**Rysunek 9:** Osoba B, 2 skany jednego palca. Oznaczmy je kolejno od lewej przez: B11, B12
$\includegraphics[width=4.5cm]{krzys1_1.eps}$ $\includegraphics[width=4.5cm]{krzys1_2.eps}$

**Rysunek 10:** Osoba C, skany dwóch różnych palców. Oznaczmy je kolejno od lewej przez: C11, C21
$\includegraphics[width=4.5cm]{krzys2_1.eps}$ $\includegraphics[width=4.5cm]{krzys3_1.eps}$

Tablica 1: Wyniki - współczynniki podobieństwa dla obrazów

	A11	A12	A13	B11	B12	C11	C21
A11	100	98	98	31	23	36	77
A12	98	100	71	1	10	13	99
A13	98	71	100	40	25	16	98
B11	31	1	40	100	88	0	0
B12	23	10	25	88	100	13	0
C11	36	13	16	0	13	100	0
C21	77	99	98	0	0	0	100

Wnioski

Próbka testowa była bardzo mała, jednak już na jej podstawie można ocenić sprawność algorytmu. Można zauważyć, że algorytm miał problemy z obrazem C21 i obrazami odcisków osoby A. Dla pozostałych testów widzimy, że dla obrazów odcisków pochodzących od dwóch różnych palców wartość współczynnika podobieństwa jest poniżej 40, a dla obrazów odcisków pochodzących z tego samego palca jest powyżej 70. Co pozwala dobrze określić rozgraniczenie miedzy akceptacją, a odrzuceniem.

Literatura

1: I.Pitas, Digital image processing algorithms and applications, Willey 2000
2: N.K.Ratha, R.M.Bolle, V.D.Pandit, V.Vaish; Robust Fingerprint Authentification Using Local Structural Similarity
3: J.C.Amengual,A.Juan,J.C.Perez,F.Prat,S.Saez,J.M.Vilar; Real-time minutiae extraction in fingerprint images

About this document ...

This document was generated using the LaTeX2HTML translator Version 99.2beta8 (1.43)