V tomto dokumente prezentujeme techniku postupu na extrakciu delta bodov z atramentových odtlačkov dlaní. Technika využíva na získavanie delta bodov knižnicu OpenCV. Po fáze predspracovania obrazu sa postupným prechádzaním jednotlivých pixlov vzorky vypočíta hodnota zmeny odtieňu šedi v horizontálnom a vertikálnom smere. Následne je z týchto hodnôt vypočítaný sklon smeru papilárnych hrebeňov. Samotné delta body sú umiestnené v miestach kde sa výrazne mení uhol. Výstupom modulu je grafické znázornenie polohy delta bodov. Kvalita extrakcie týchto bodov veľmi záleží na úspešnosti samotného algoritmu.

1. Úvod

V súčasnosti čoraz viac inštitúcií a procesov vyžaduje osobnú identifikáciu a verifikáciu. Medzi tradičné metódy overovania patrí overovanie na základe vedomosti a overovanie na základe vlastníctva. Obe tieto metódy sú v mnohých prípadoch zdĺhavé, neefektívne a drahé. V článku [1] autor P.Fox zistil, že niektoré spoločnosti prečerpajú okolo 14 až 28 dolárov na udržiavanie a resetovanie hesiel a každý štvrtý telefonát technickej podpore sa týkal problému s heslom. Závažným problémom týchto metód je aj ten, že systém nie je schopný rozpoznať neoprávnenú osobu (ak pozná heslo, poprípade odcudzí kľúč) od oprávnenej.

Tieto nedostatky upriamili pozornosť viac na overovanie pomocou biometrie. Biometria je identifikácia / verifikácia osôb podľa ich jedinečných fyzických (fyziologických) znakov alebo zvykových čŕt (tzv. behaviorálne črty) jedinca. Biometria dlane využíva na identifikáciu/verifikáciu: geometriu dlane, hlavné čiary, vrásky, dátumové body, markanty a delta body. V ostatnej časti práce sa zameriame na kroky biometrického systému, zameraného na predspracovanie obrazu a následné získavanie delta bodov.

2. Biometrický systém

Biometrické systémy sú systémy, ktoré umožnujú osobnú identifikáciu určujúcu oprávnenosť na základe špecifických fyziologických, alebo behaviorálnych charakteristík používateľa. Charakteristiky používateľa ako napríklad odtlačky prstov, dlaní, scan sietnice a iné sú získavané senzormi. Tie následne putujú do rozpoznávacieho zariadenia, ktoré určí výsledok.

2.1. Architektúra biometrického systému

Klasická architektúra biometrického systému pozostáva z nasledujúcich 4 krokov:

1. získanie dát : Biometrické dáta sú získavané zo vstupných zariadení. Kvalita získanej vzorky je veľmi dôležitá pretože tvorí priamy vstup nasledujúcemu kroku – predspracovanie obrazu.
2. predspracovanie obrazu: V tejto fáze sa surové dáta(obraz) vylepšujú, aby extrakcia markantov(charakteristických znakov) prebehla najpresnejšie. Obraz sa upravuje rôznymi procesmi ako napríklad segmentácia, otáčanie do správnej polohy, redukcia šumu.
3. extrakcia markantov: Významové markanty majú byť stále a majú zabezpečovať jedinečnosť. Tieto markanty sú vo vhodnej forme uložené v databáze systému a tvoria porovnávaciu šablónu.
4. porovnávanie zhody – Miera zhody je získavaná porovnaním identifikovávanej vzorky a porovnávacej šablóny uloženej v systéme. Ak výsledné skóre je menšie ako stanovený prah, používateľ je úspešne autentifikovaný.

3. Predspracovanie obrazu

Odtlačky dlaní môžu vykazovať určité nedokonalosti. Tie sú zapríčinené zachytením vzorky v rôznych časoch, a za rôznych svetelných podmienok, teploty, vlhkosti atď. Atramentové vzorky odtlačkov dlaní boli z Úradu kriminálnej polície Prezídia Policajného zboru. Následne boli tieto vzorky prevedené do digitálnej formy pomocou scannera. Na vzorky bol použitý histogram a následne bola vzorka otočená tak, aby koncové body hlavných čiar boli rovnobežné s x-ovou osou (Obr.1.). Rozlíšenie jednotlivých vzoriek pri extrakcii delta bodov bolo nastavené na 640×640 bodov.

Obr. 1. Správne natočenie odtlačku

3.1. Oddelenie odtlačku od pozadia

V prvom kroku predspracovania obrazu sa zaoberáme odfiltrovaním odtlačku vzorky od neželaného pozadia. Algoritmus prechádza bodmi obrázka konvolučne. Pre každý bod obrázka O(i,j), prechádzame maskou veľkosti 8×8. Maskou nasčítame hodnotu farebnej zložky okolitých bodov O(i,j) a túto hodnotu porovnáme s nastaveným prahom T podľa vzorca (1). Ak je tento prah presiahnutý,

(1)

V prvom kroku predspracovania obrazu sa zaoberáme odfiltrovaním odtlačku vzorky od neželaného pozadia. Algoritmus prechádza bodmi obrázka konvolučne. Pre každý bod obrázka O(i,j), prechádzame maskou veľkosti 8×8. Maskou nasčítame hodnotu farebnej zložky okolitých bodov O(i,j) a túto hodnotu porovnáme s nastaveným prahom T podľa vzorca (1). Ak je tento prah presiahnutý,

pseudokód:

pre ( i = 0; i < šírka obrázka: i++ ){
 pre ( j = 0; j < výška obrázka; j++ ){   HO = 0; //hodnota odtieňa   pre(u = -4; u <=šírka masky – 4; u++){    pre(u = -4; u <=šírka masky – 4; u++){     HO = HO + získaj HO aktuálneho bodu;    }   }   ak (HO > threshold){    vybiel pixel   }  } }

Obr. 2. Zobrazenie vzorky, pred a po aplikovaní algoritmu

Nastavenie prahu T záleží predovšetkým od svetelných podmienok pri akých bola vzorka získavaná, ako aj od veľkosti masky, ktorá bola používaná pri získavaní súčtu okolitých bodov. Pri veľkosti masky 9x9 a rozmeru obrázku 640x640 bodov sa ako najúspešnejší stal prah s hodnotou T = 59000.

4. Extrakcia delta bodov

Správne natočený obrázok úspešne separovaný od pozadia rovnako, ako v predošlom kroku konvolučne prechádzame. Pre každý bod si vypočítame hodnotu zmeny farby v horizontálnej ako aj vertikálnej zložky. Tu sme využili funkciu Sobel z OpenCV. Výsledok po aplikovaní funkcie sobel v smere x-ovej osi ako aj y-ovej osi je znázornený na Obr. 3. a Obr. 4..

Obr. 3. Efekt použitia Sobelovho operátora s aproximáciou 1 derivácii v smere X - osi

Obr. 4. Efekt použitia Sobelovho operátora s aproximáciou 1 derivácii v smere Y - osi

Tak ako pri funkcii na oddelenie odtlačku dlane od pozadia, tak aj v tomto prípade sčítavame hodnoty v celej maske. Tu ale neščítavame samotné hodnoty stupňa šedi, ale jej hodnoty v horizontálnom a vertikálnom smere (využitá funkcia Sobel) podľa nasledujúcich vzorcov (2-3):

(2)

(3)

Z týchto hodnôt je následne vypočítaný uhol smeru zmeny šedi, teda v prípade odtlačkov rúk sa jedná o uhol smeru papilárnych línií podľa vzorca (4).

(4)

Takto získaný uhol je zaokrúhlený. Rozdelenie samotných uhlov je do 4 kategórií: – horizontálneho smeru, | vertikálneho a / , \ 2 typy diagonálneho. Podľa tejto kategorizácie je samotný bod aj zafarbený. Výsledné zafarbenie je znázornené na obrázku Obr. 5.. V tomto prípade nie je nastavenie parametra veľkosti masky ako pri funkcii na separovanie odtlačku od pozadia také jednoznačné. Preto v tomto prípade bol zvolený trackbar umožňujúci zmenu tejto veľkosti.

Obr. 5. Zobrazenie zmeny smeru papilárnych hrebeňov

Pri tomto algoritme sme na určenie smeru zmeny odtieňu šedi skúsili použiť aj Houghovu transformáciu, tento pokus sa ale nejavil úspešný.

5. Vyhladenie obrázka

Pri extrakcii deltových bodov z odtlačkoch dlaní sa do získanej vzorky otlačia aj vrásky, ktoré niesú súčasťou papilárnych hrebeňov. Tie, ako aj zmena smeru papilárnych hrebeňov na krátkych vzdialenostiach, zapríčiňujú kostrbatosť vzorky. Pri takejto vzorke je ťažké určiť kedy sa jedná o nechcený šum, alebo skutočné delta body. Preto pred samotným určovaním deltových bodov sa vzorka vyhladí. Proces vyhladenia má s predošlými algoritmami spoločnú konvolúciu.

Každým bodom sa prehľadáva okolie sledovaného bodu a jeho hodnota sa vyhodnotí ako farba(smer papilárnych hrebeňov) s najpočetnejším zastúpením v maske. Výsledok po aplikovaní funkcie je znázornený na Obr. 6.. Rovnako ako pri extrakcii delta bodov je aj v tomto prípade veľkosť masky závislá na samotnej vzorke a aj od veľkosti masky použitej v predchádzajúcom kroku. Preto aj v tomto prípade je veľkosť masky volitelná za pomoci trackbaru. Minimálna hodnota masky je 0 a maximálna 30.

pseudokód:

pre ( i = 0; i > šírka obrázka: i++ ){
 pre ( j = 0; j > výška obrázka; j++ ){
  farba1 = 0;
  farba2 = 0;
  farba3 = 0;
  farba4 = 0;
  pre(u = 0; u > šírka masky; u++){
   pre(u = 0; u > šírka masky; u++){
    zisti hodnotu pixela a zvýš counter danej dodnoty;
   }
  }
  ak (max == farba1){
   nastav hodnotu pixela na farba1
  }
  …
  ak (max == farba4){
   nastav hodnotu pixela na farba4
  }
 }
}

Obr. 6. Zobrazenie zmeny smeru papilárnych hrebeňov po aplikovaní vyhladzovania

6. Miesta delta bodov

Z biologického hľadiska má väčšina ľudí rozmiestnené delta body nasledovne[2]. 4 delta body sa nachádzajú pod prstami a jeden v ľavej spodnej časti(na pravej ruke) pri zápästí Obr. 7.. Upresnenie polohy týchto bodov sa teda nachádza v miestach stretov 4 rôznych farebných kombinácií mapy, ktorá vznikla po aplikovaní nami opísaných algoritmov. Detaily ako aj celá mapa je znázornená na Obr.8. a Obr. 9..

Obr. 7. X – obvyklé umiestnenie delta bodov

Obr.8. Znázornená mapa na pôvodnom obrázku

Obr. 9. Detaily delta bodov

7. Urýchlenie algoritmu

Všetky spomínané algoritmy boli aplikované na obrázkoch o rozmeroch 640x640 bodov. Konvolučné prechádzanie s dvoma vnorenými for cyklami je preto veľmi časovo-výpočtovo zložité. Čím väčší obrázok bol prezeraný a čím väčšia maska bola použitá, tým rástol aj výpočtový čas. Preto sme tento algoritmus upravili. Algoritmus prechádza od ľavého horného rohu vzorky diagonálne. V prvej fáze sa vytvorí pomocná matica, ktorej hodnoty predstavujú súčet hodnôt danej veličiny(stupeň šedi, množstvo bodov zafarbených určitej farby...) v štvorcoch ľavého horného rohu po daný bod – vzorec (5).

Tu vieme vypočítať iteráciou po diagonále so zložitosťou O(n x n). Ak n je rozmer obrázka(v našom prípade 640) hodnotu veličiny v akomkoľvek štvorci potom vieme pomocou nasledujúceho vzorca (6) z pomocnej matice vypočítať. Keďže potrebujeme vypočítať hodnotu pre n x n štvorcov a výpočet hodnoty pre jeden štvorec nám trvá O(1), tak potom všetky dohromady O(n x n). Pre porovnanie s pôvodnou zložitosťou, kde O(n x n x m x m) (m – veľkosť štvorca, n – veľkosť obrázka) je momentálna zložitosť O(3 x n x n). V tabuľke 1 sú znázornené konkrétne namerané časy trvania pôvodného a upraveného algoritmu na vzorke 640x640 bodov s rozličnou veľkosťou masky.

Tab. 1. Výsledné časy algoritmov

Veľkosť masky	Pôvodný čas	Upravený alg.
1	1s	1s
2	2s	1s
4	4s	1s
8	14s	1s
10	21s	1s
15	47s	1s
17	60s	1s
30	181s	1s

(5)

(6)

8. Zhodnotenie

Pri použití uvedených algoritmov sa podarilo úspešne extrahovať miesta zmeny smeru papilárnych hrebeňov odtlačkov dlaní. Narozdiel od odtlačku prsta sa na odtlačku dlane nachádzajú aj hlavné čiary a vrásky, ktoré zapríčiňujú určité nedokonalosti. Preto pre presnejšie určenie, či sa jedná o skutočný delta bod alebo nechcenú zašumenú oblasť je nutná asistencia užívateľa.

Odkazy na literatúru

1. Fox, J. et al. 1995. The effect of semiconductor surface treatment on LB film/Si interface. In: Physica Status Solidi /a/, ISSN 0031-8965, 1995, vol. 108, no. 2, pp. K 87 - 90
2. Zhang, D. David 2004. Palmprint authentification, 2004, pp. 37 - 38

---

Spoluautorom článku je Ing. Lukáš Adamko, KAIVT, Slovenská Technická Univerzita

---

Práca bola prezentovaná na Študentskej vedeckej a odbornej činnosti (ŠVOČ 2011) v sekcii Aplikovaná informatika a získala Diplom dekana, ISBN 978-80-227-3508-7