Cviˇcen´ı z pˇredmˇetu Biometrie ´ Uloha 2: Identifikace osoby pomoc´ı otisku prstu Pavel Vostatek, Jakub Schneider kontaktn´ı email:
[email protected] 7. ˇr´ıjna 2014
1
´ Uvod
Rozpozn´av´an´ı otisk˚ u prst˚ u lze rozdˇelit na dvˇe hlavn´ı ˇca´sti: pˇredzpracov´an´ı otisku a rozpozn´av´an´ı otisku. Pˇredzpracov´an´ı zahrnuje segmentaci otisku od pozad´ı, u ´pravu kontrastu, v´ ypoˇcet natoˇcen´ı papil´arn´ıch lini´ı v ploˇse otisku, v´ ypoˇcet hustoty papil´arn´ıch lini´ı, filtrace Gaborovou maskou pro vyhlazen´ı drobn´ ych chyb, vytvoˇren´ı kostry otisku a v´ yslednˇe nalezen´ı markant˚ u. Pro kaˇzdou ˇca´st existuje bezpoˇcet zp˚ usob˚ u jej´ıho zpracov´an´ı. My se budeme zab´ yvat pouze vybran´ ymi state of the art metodami. Vyˇcerp´avaj´ıc´ı pˇrehled metod lze nal´ezt v [1]. Z problematiky rozpozn´av´an´ı otisku se budeme ve cviˇcen´ı zab´ yvat pouze identifikac´ı totoˇznosti ˇclovˇeka. V t´eto ˇca´sti srovn´ame dvˇe metody, kter´e identifikace vyuˇz´ıv´a. Prvn´ı z nich, markatov´ e srovn´ av´ an´ı, vych´az´ı z klasick´eho porovn´av´an´ı otisk˚ u v daktyloskopii a srovn´av´a rozloˇzen´ı markant˚ u na otisc´ıch. Druh´a metoda, Finger Code, kvantuje po ploch´ach mezikruˇz´ı dan´e velikosti okolo otisku a z kaˇzd´e plochy vypoˇc´ıt´a jednu hodnotu do pˇr´ıznakov´eho vektoru. Vektory jsou pot´e srovn´any mezi otisky. ´ Ukolem bude v prvn´ı ˇca´sti prakticky otestovat siln´e a slab´e str´anky pˇredzpracov´an´ı na pˇeti r˚ uzn´ ych otisc´ıch. Nˇekter´e metody budete muset vymyslet a implementovat. V druh´e ˇca´sti budete muset implementovat obˇe metody pro porovn´an´ı otisk˚ u, jejichˇz podrobn´ y popis je souˇca´st´ı zad´an´ı, a n´aslednˇe zhodnotit s´ılu obou metod statisticky na datab´azi. K dispozici je Fingerprint Toolbox pro Matlab, kter´ y byl pro cviˇcen´ı vytvoˇren. Obsahuje funkce pro naˇc´ıt´an´ı i zpracov´an´ı otisku. Funkce potˇrebn´e pro kaˇzdou operaci jsou uvedeny v pˇr´ısluˇsn´ ych kapitol´ach.
2 2.1
Pˇ redzpracov´ an´ı otisku Orientace papil´ arn´ıch lini´ı
Prvn´ı technikou pˇredzpracov´an´ı otisku je v´ ypoˇcet n´aklonu teˇcny papil´arn´ıch lin´ı v bodˇe [x, y]. Tyto hodnoty nejsou tradiˇcnˇe poˇc´ıt´any pro kaˇzd´ y pixel obrazu, ale vzorkov´any s dan´ ym krokem, pˇriˇcemˇz v pˇr´ıpadˇe potˇreby pro libovoln´e m´ısto v prostoru je hodnota ´ z´ısk´ana interpolac´ı. Uhel pro bod [x, y] znaˇc´ıme Θxy a je poˇc´ıt´an v otisku po bloc´ıch 1
(pr˚ umˇern´a hodnota v bloku dan´e velikosti), ˇc´ımˇz je d´ano vzorkov´an´ı Θxy v obraze. klasickou metodou pro v´ ypoˇcet Θxy je pouˇzit´ım gradientu. Oznaˇcme ∇(x, y) dvouprvkov´ y vektor, kter´ y tvoˇr´ı parci´aln´ı derivace obrazu ∇x , ∇y podle souˇradnic x a y. Ten je z´ısk´an pomoc´ı Prewittovy nebo Sobellovy masky filtrac´ı (v Matlabu pˇr´ıkaz gradient). Vektor ∇(x, y) z definice m´ıˇr´ı ve smˇeru nejvyˇsˇs´ıho r˚ ustu jasov´e intenzity — tedy ve smˇeru nejvyˇsˇs´ıho kontrastu. Smˇer papil´arn´ıch lini´ı je pot´e br´an jako kolm´ y smˇer na gradient. Uk´azka v´ ysledku v´ ypoˇctu je na Obr. 1. orientacni pole
orientace pixelu v sede skale
Obr´azek 1: Orientaˇcn´ı pole, computeorientationarray(im, imSegmented, 10)
2.2
V´ ypoˇ cet frekvenˇ cn´ıho pole
Frekvenˇcn´ı pole papil´arn´ıch lin´ı m˚ uˇzeme popsat jako v prostoru vzorkovanou funkci f (x, y), kter´a urˇcuje poˇcet pap. lini´ı na jednotku d´elky ve smˇeru kolm´em na smˇer lini´ı. Opˇet exituje nˇekolik zaj´ımav´ ych algoritm˚ u. Ve Fingerprint Toolboxu je implementovan´ y algoritmus vyuˇz´ıvaj´ıc´ı orientovan´e okno. Okno definovan´e velikosti je um´ıstˇeno do polohy (x, y) a natoˇceno podle smˇeru papil´arn´ıch lin´ı (pokud jde o asymetrick´e okno, je natoˇceno ˇsirˇs´ım rozmˇerem kolmo na smˇer lini´ı). Jasov´e hodnoty v kaˇzd´em sloupci jsou zpr˚ umˇerov´any, takˇze v´ ysledkem je jednorozmˇern´ y vektor honot periodick´eho pr˚ ubˇehu odpov´ıdaj´ıc´ı reli´efu prohlubn´ı a v´ ystupk˚ u lini´ı. V tomto vektoru je pot´e spoˇc´ıt´an poˇcet vrchol˚ u a d´elka mezer mezi pocet mezer P nimi, frekvence je pot´e spoˇc´ıt´ana: f = (delka mezer) . Uk´azka je na Obr. 2. puvodni otisk
Obr´azek 2: Frekvenˇcn´ı orientationArray)
pole,
frekvence papilarnich linii
computelocalfrequency(im, imSegmented,
2
2.3
Segmentace otisku
Segmentace otisku se prov´ad´ı s c´ılem porovn´avat pouze relevantn´ı ˇca´sti obrazu. Segmentaci m˚ uˇze pˇredch´azet nejprve upraven´ı kontrastu, coˇz ale nen´ı nezbytnˇe nutn´e. Z bezpoˇctu algoritm˚ u slouˇz´ıc´ıch k oddˇelen´ı otisku od pozad´ı si zde nˇekolik zevrubnˇe pˇredstav´ıme. J´adrem vˇsech segmentaˇcn´ıch algoritm˚ u je zpracov´an´ı otisku adaptivnˇe — po bloc´ıch. Kaˇzd´ y blok je samostatnˇe zpracov´an a klasifikov´an na otisk nebo pozad´ı, pˇr´ıpadnˇe je moˇzn´e vytvoˇrit v´ıce hodnocen´ı podle kvality pozad´ı a rozpozn´avat tak´e nekvalitn´ı nebo rozmazan´e ˇc´asti otisku. Prvn´ı nasnadˇe pro segmentaci by se nab´ızelo jednoduch´e prahov´an´ı podle hodnoty jasov´e intenzity. Tento pˇr´ıstup ale nen´ı nejvhodnˇejˇs´ı, protoˇze to co charakterizuje plochu otisku je hlavnˇe vzor papil´arn´ıch lini´ı, kter´ y je doplnˇen ˇsumem zp˚ usoben´ ym nahr´avac´ım ˇcipem ˇci neˇcistotami. Pouˇz´ıvan´e metody pro segmentaci otisku lze shrnout do n´asleduj´ıc´ıch skupin: Pouˇzit´ım orientaˇ cn´ıho pole, kdy je pro kaˇzd´ y blok vypoˇc´ıt´an histogram orientac´ı papil´arn´ıch lini´ı. Pokud je v tomto histogramu patrn´a ˇspiˇcka, znamen´a to jednotn´ y smˇer lini´ı v obraze a blok je klasifikov´an jako otisk. Pouˇzit´ım variance jasov´ e intenzity ve smˇ eru kolm´ em na smˇ er papil´ arn´ıch lini´ı. Tento pˇr´ıstup vych´az´ı z toho, ˇze mimo oblast otisku je variance jasu nez´avisl´a na detekovan´em smˇeru papil´arn´ıch lini´ı. Pouˇzit´ım gradientu jasov´ e intenzity poˇc´ıtan´em pr˚ umˇernˇe v kaˇzd´em bloku, n´aslednˇe klasifikovan´em podle velikosti gradientu. Tento zp˚ usob vych´az´ı z toho, ˇze velikost gradientu je v´ yraznˇe vyˇsˇs´ı pro oblasti s papil´arn´ımi liniemi neˇz oblasti mimo otisk. Pouˇzit´ım Gaborov´ ych filtr˚ u. Kaˇzd´ y blok je filtrov´an sadou 8 Gaborov´ ych filtr˚ u s r˚ uzn´ ym natoˇcen´ım a v´ ystup t´eto filtrace je pouˇzit jak pro klasifikaci na otisk a pozad´ı a z´aroveˇ n m˚ uˇze slouˇzit k posouzen´ı kvality dan´eho bloku. Tento krok m˚ uˇze b´ yt spojen s n´asledn´ ym vyhlazov´an´ım otisku pomoc´ı G. filtrace. otisk
segmentace otisku od pozadi
Obr´azek 3: Uk´azka moˇzn´e segmentace. Zde poˇc´ıt´ano prahov´an´ım velikosti gradientu jasov´e intenzity.
2.4
Vylepˇ sen´ı pouˇ zit´ım Gaborov´ ych filtr˚ u
Filtrov´an´ı pouˇzit´ım Gaborov´ ych filtr˚ u neboli tzv. kontextu´aln´ı filtrac´ı je smˇerovou filtrac´ı obrazu. Bˇeˇznˇe se pouˇz´ıv´a jako hranov´ y detektor, n´am se tyto vlastnosti hod´ı na zahlazen´ı 3
nespojitost´ı papil´arn´ıch lini´ı zp˚ usoben´ ych nekvalitou obrazu. Na Obr. 4 je vidˇet filtraˇcn´ı maska G. filtru v prostorov´e oblasti. Jej´ı vlnov´ y tvar j´ı d´av´a smˇerov´e vlastnosti. Vlna, kter´a je vidˇet na obr´azku je postupnˇe nat´aˇcena do r˚ uzn´ ych smˇer˚ u. Natoˇcen´ım do smˇeru papil. lini´ı zp˚ usob´ı jejich zv´ yraznˇen´ı a zahlazen´ı chyb.
1
0.5
0
−0.5
−1 40 30
40 30
20 20 10
10 0
0
Obr´azek 4: Maska G. filtrace, kter´a je konvolvov´ana s filtrovan´ ym obrazem. Maska je z izometrick´eho pohledu. Obraz je opˇet zpracov´av´an po bloc´ıch implementace Gaborovy masky bude v u ´loze za u ´kol. Je to jednoduch´e, jej´ı definice je n´asleduj´ıc´ıch: x =< −16, 16 >, y =< −16, 16 > xp = sin(angle) · x + cos(angle) · y yp = sin(angle) · y − cos(angle) · x x2 y2 gab(x, y) = exp{− 12 · [( t2p ) + ( t2p )]} · cos(2πf · xp ) x
y
obraz vylepseni pouzitim Gaborovych filtru
kostra otisku pred cistenim
Obr´azek 5: Gaborova filtrace, orientationArray, frequencyArray, 0)
enhance2ridgevalley(im, imSegmented,
4
2.5
Kostra otisku, markanty
Po filtraci Gaborov´ ymi filtry jsou papil´arn´ı linie ztenˇceny na nejmenˇs´ı ˇs´ıˇrku - vznikne kostra otisku. V kostˇre otisku jsou pot´e hled´any markanty napˇr. pomoc´ı jednoduch´ ych pravidel. Zhodnot’te kvalitu nalezen´ ych markant˚ u ve dvou zvolen´ ych otisc´ıch.
kostra otisku po vycisteni
v otisku vyznacene markanty
End of Ridge Bifurcation
Obr´azek 6: Finaln´ı detekce markant˚ u, defaultn´ı nastaven´ı. Pˇri spr´avn´e implementaci masky Gaborova filtru by mˇela funkce uk´azka vr´atit obr´azky podobn´e, jako jsou zde.
3
Identifikace identity ˇ clovˇ eka pomoc´ı otisku prstu
Identifikace - neboli urˇcen´ı totoˇznosti ˇclovˇeka podle otisku prstu je zn´am´a metoda pouˇz´ıvan´a v kriminalistice. Potˇrebujeme k n´ı dostateˇcnˇe velikou datab´azi otisk˚ u. Pot´e dostaneme otisk a naˇs´ım u ´kolem je nal´ezt v datab´azi odpov´ıdaj´ıc´ı otisk prstu, kter´ y nejpravdˇepodobnˇeji odpov´ıd´a pˇredloze. Pˇr´ıpadnˇe urˇcit, ˇze nejsme schopni podobn´ y otisk nal´ezt pro nekvalitu vstupn´ıho obrazu nebo nem´ame hledan´ y otisk v datab´azi. K identifikaci otisku potˇrebujeme hlavnˇe metody na srovn´an´ı vstupn´ıho otisku s tˇemi v datab´azi. V pˇredchoz´ıch kapitol´ach jsme si uk´azali, jak otisk pˇredzpracovat a pˇripravit na extrakci moˇzn´ ych pˇr´ıznak˚ u. N´aslednˇe si uk´aˇzeme dvˇe metody pro porovn´an´ı otisk˚ u. Prvn´ı vych´az´ı z klasick´eho porovn´an´ı pomoc´ı v´ yznamn´ ych bod˚ u, tzv. markant˚ u. Jejichˇz topologie jednoznaˇcnˇe urˇcuje lidsk´ y otisk. A druh´a je zaloˇzena na textuˇre otisku a extrakci pˇr´ıznakov´eho vektoru z n´ı pouˇzit´ım Gaborovy filtrace.
3.1
Markantov´ e rozpozn´ an´ı
Pro markantov´e porovn´av´an´ı otisk˚ u je pˇripravena funkce match.m, kterou je tˇreba implementovat.
5
Algoritmus: Vstupem jsou dvˇe sady markant˚ u (bod˚ u) v rovinˇe: mAi1 a mAi2 a pr´ah pro vzd´alenost d. Vstupn´ı poˇcty markant˚ u jsou: |mAi1|, resp. |mAi2|, poˇcet p´ar˚ u markant˚ u iniciovan´ y nbmatch = 0 a celkov´a vzd´alenost dist = 0. • Pro kaˇzd´ y bod z mAi2 naleznˇete nejbliˇzˇs´ı bod v mAi1. Pokud jsou markanty vzd´aleny m´enˇe, neˇz d, potom je oznaˇcte za p´ar a vyjmˇete z mAi1 i mAi2. Za kaˇzd´ y nalezen´ y p´ar nbmatch + 1 • Po vyˇcerp´an´ı vˇsech markant˚ u z mAi2 moˇzn´ ych sp´arovat vypoˇctˇete matchingScore = coˇz je v´ ysledn´e ohodnocen´ı pˇriˇrazen´ı otisk˚ u. Plat´ı, ˇze ˇcim vyˇsˇs´ı matchingScore, t´ım sp´ıˇs patˇr´ı patˇr´ı otisky stejn´emu p˚ uvodci (interval je < 0, 1 >). 2·nbmatch , |mAi1|+|mAi2|
Syntaxe funkce match je n´asleduj´ıc´ı: [matchingScore, nbmatch, inputmatch, dbmatch] = match(mAi1, mAi2); Vstupem jsou pole s vyznaˇcen´ ymi markanty pro vzor (mAi1 ) a porovn´avan´ y otisk (mAi2 ). Tato pole jsou pˇr´ımo v´ ystupem funkce findminutia, pˇriˇcemˇz mAi2 mus´ı b´ yt zarovn´ano s mAi1. V´ ystupy jsou: matchingScore - ohodnocen´ı podobnost dvou otisk˚ u. V´ ypoˇcet je v´ yˇse. nbmatch - poˇcet dvojic markant˚ u. inputmatch - pole stejn´e velikost jako mAi2, kde jsou vyznaˇceny markanty stejn´ ym zp˚ usobem jako v mAi2, ale pouze ty, kter´e byly zp´arov´any. dbmatch - stejnˇe jako inputmatch, ale pro otisk 1.
3.2
Rozpozn´ av´ an´ı pomoc´ı Finger Codu
Pomoc´ı sady Gaborov´ ych filtr˚ u s r˚ uzn´ ym natoˇcen´ım filtrujte otisk prstu. Vznikne k filtrovan´ ych obraz˚ u. Kaˇzd´ y filtrovan´ y obr´azek zpracujte po bloc´ıch N velikosti n x n bez pˇrekryvu. Hodnotu pro kaˇzd´ y blok spoˇc´ıtejte jako f (N ) = |mean(N ) − std(N )|, kde std znaˇc´ı smˇerodatnou odchylku, mean stˇredn´ı hodnotu. Z kaˇzd´eho bloku vznikne n´aslednˇe jeden pixel. Blokov´ y obraz pot´e vyˇr´ıznˇete maskou pouze okolo j´adra otisku, jak ukazuje Figure 1. filtrovany otisk
otisk po blokach zpracovany
vymaskovany stred
Obr´azek 7: Postup pˇri vytv´aˇren´ı FingerCodu
6
N´asledn´ y pˇr´ıznakov´ y vektor f1 (odpov´ıdaj´ıc´ı vzoru, resp. f2 odpov´ıdaj´ıc´ı vstupn´ımu obrazu) vznikne seˇrazen´ım hodnot leˇz´ıc´ıch v mezikruˇz´ı (nevynulovan´e hodnoty Figure 1 vpravo) z kaˇzd´eho z k obraz˚ u a jejich seˇrazen´ım za sebe. Porovn´an´ı 2 otisk˚ u pot´e proved’te jako ˇ ım niˇzˇs´ı je v´ matchingScoreGabor = mean(abs(f1 − f2 ))[1]. C´ ysledn´a hodnota, t´ım l´epe si otisky odpov´ıdaj´ı, tedy jako score pouˇzijeme z´apornou hodnotu vzd´alenosti. Pro Finger Code je pˇripravena funkce fingercode creation.m. [fingercode Fmasked] = fingercode creation(imOriginal, Gfilt, core, maskSize, dia), imOriginal je vstupn´ı obr´azek pro v´ ypoˇcet, Gfilt je sada k Gaborov´ ych filtr˚ u vytvoˇren´a pomoc´ı GaborFilter creation, core jsou souˇradnice j´adra otisku, maskSize je velikost bloku pro filtraci obrazu a dia jsou velikosti vnˇejˇs´ıho a vnitˇrn´ıho polomˇeru oˇrezu okolo j´adra. V´ ystupy: fingercode - vektor velikosti [1 x N], kde N z´aleˇz´ı na velikosti mezikruˇz´ı (viz d´ale). Fmasked - blokov´ y obraz s vyˇr´ıznut´ ym mezikruˇz´ım (Figure 1, vpravo) pro kaˇzd´ y Gabor˚ uv filtr. Velikost [M x N x O]. M x N je velikost blokov´eho obrazu a O je poˇcet Gaborov´ ych filtr˚ u. V´ ystup Fmasked nen´ı nutn´ e implementovat.
4
Vypracov´ an´ı u ´ lohy
Kaˇzd´ y student si zvol´ı 10 otisk˚ u r˚ uzn´e kvality (od r˚ uzn´ ych osob). Tyto otisky si vyjme z ´ datab´aze (je nutn´e uˇz´ıt aspoˇ n dvˇe z poskytnut´ ych tˇr´ı). Ukolem bude pomoc´ı pˇripraven´eho toolboxu vytvoˇrit syst´em, kter´ y nalezne v dan´e datab´azi nejpravdˇepodobnˇejˇs´ıho odpov´ıdaj´ıc´ıho adepta pro kaˇzd´ y z otisk˚ u, pˇr´ıpadnˇe rozhodne o nemoˇznosti nal´ezt vhodn´eho adepta v datab´azi. ´ Ukoly: Na poskytnut´ ych otisc´ıch nejprve vyzkouˇsejte v´ ypoˇcet frekvenˇcn´ıho a orientaˇcn´ıho ’ pole. Vizu´alnˇe zhodnot te, jak´ y m´a kvalita otisku vliv na v´ ysledek v´ ypoˇctu. [2 b] Implementujte vlastn´ı algoritmus segmentace otisku. M˚ uˇzete si zvolit z algoritm˚ u jmenovan´ ych v Kapitole 2.3 nebo si vybrat jin´ y z literatury ([1]). M˚ uˇzete vymyslet vlastn´ı algoritmus, kter´ y automaticky segmentuje otisky, kter´e jste dostali v zad´an´ı. [4 b] Pro umoˇznˇen´ı Gaborovy filtrace je potˇreba implementovat v´ ypoˇcet G. masky do funkce enhance2ridgevalley.m (v teto funkci je podfunkce filtergabor) podle kapitoly 2.4. [2 b] Nahrajte vlastn´ı sadu otisk˚ u na naˇsich sn´ımaˇc´ıch a srovnejte jak si porad´ı funkce na pˇredzpracov´an´ı otisku s v´ ystupy jednotliv´ ych sn´ımaˇc˚ u. Budou vˇzdy nalezen´e markanty stejn´e nebo r˚ uzn´e. Segmentuje spr´avnˇe V´aˇs algoritmus pro segmentaci otisku nahran´e otisky? [2 b]
7
Implementujte funkci match pro v´ ypoˇcet shody mezi zarovnan´ ym vstupn´ım obr´azkem a vzorem (v datab´azi) pomoc´ı markant˚ u. [4 b] Implementujte funkci fingercode creation po v´ ypoˇcet shody mezi obrazy pomoc´ı Finger Codu. [4 b] Pro pˇriˇrazen´ y otisk vyzkouˇsejte naj´ıt identitu (ID) z poskytnut´e datab´aze ”DataBase”. Udejte nejlepˇs´ı a nejhorˇs´ı v´ ysledn´e sk´ore pro zvolen´e ID (r˚ uzn´e senzory). (datab´aze obsahuje r˚ uzn´e typy senzor˚ u, pro dohled´an´ı ID nen´ı nutn´e pouˇz´ıvat vˇsechny) [2 b]
A
Pˇ r´ıloha: Struktura Sigature Toolboxu.
Toolbox je rozdˇelen na 2 ˇca´sti: predzpracovani a porovnani, kaˇzd´a obsahuje funkce pro jednotliv´e ˇc´asti u ´lohy. Funkce potˇrebn´e pro kaˇzd´ y popisovan´ y algoritmus jsou pops´any v textu.
B
Reference
[1] Anil K. Jain and David Maltoni. Handbook of Fingerprint Recognition. Springer-Verlag New York, Imc., Secaucus, NJ, USA, 2003
8
