´ UJJLENYOMAT-AZONOS´ ITAS ´ ˝ ´ DERMATOLOGIAI JELLEMZOK ALAPJAN
´s Fazekas Ga ´bor Fazekas Attila e Bevezet´ es Az emberek k¨ oz¨ otti kapcsolat egy igen r´egi probl´em´ aja a szem´elyi identifik´ aci´ o, vagyis a szem´elyazonoss´ ag meg´ allap´ıt´ asa. Az id˝ ok sor´ an sz´ amos m´ odszert alkalmaztak ennek megold´ as´ ara, a pecs´etgy˝ ur˝ ut˝ ol az al´ a´ır´ ason a ´t eg´eszen a f´enyk´epig. Az ujjlenyomat, mint az azonos´ıt´ as eszk¨ oze, m´ ar az o ´kori k´ınaiakn´ al ismeretes volt. u ¨zleti ´es kereskedelmi szerz˝ od´esek szign´ al´ asakor gyakran alkalmazt´ ak. A m´ ult sz´ azadt´ ol b¨ untet˝ o elj´ ar´ asokn´ al is alkalmazz´ ak. A hatvanas ´evekt˝ ol kezdve, amikor is terjedni kezdtek a sz´ am´ıt´ og´epek, felvet˝ od¨ ott az ujjlenyomat-azonos´ıt´ as sz´ am´ıt´ og´epes´ıt´es´enek lehet˝ os´ege. Az automatikus ujjlenyomat-azonos´ıt´ assal kapcsolatban — f˝ oleg a modern letapogat´ o berendez´esek elterjed´es´evel, amelyek nemcsak a lenyomatot veszik le, de k¨ ozben az ujj h˝ om´ers´eklet´et ´es v´erkering´es´et is ellen˝ orzik — a jelenlegi technol´ ogiai szinten nem mer¨ ul fel a hamis´ıt´ as lehet˝ os´ege. ´erdemes tal´ an felh´ıvni a figyelmet, hogy a kriminol´ ogiai azonos´ıt´ as ´es a bel´eptet˝ orendszerekn´el sz¨ uks´eges azonos´ıt´ as elvileg elt´er˝ o feladatot takarnak. A kriminol´ ogi´ aban az a feladat, hogy egy tal´ alt (ujj)lenyomatot az arch´ıvumban l´ev˝ oo ¨sszes mint´ aval o ¨ssze kell vetni, ´es azok k¨ oz¨ ul kell kiv´ alasztani azt az egyet (ha van ilyen), amellyel megegyezik. A bel´eptet˝ orendszerekn´el viszont valamilyen m´ odon — jelsz´ oval, bel´eptet˝ ok´ arty´ aval — az azonos´ıtand´ o szem´ely kijel¨ oli, hogy mely etalonnal kell a t˝ ole vett mint´ at o ¨sszehasonl´ıtani. Ebben a cikkben egy bel´eptet˝ orendszerekben haszn´ alhat´ o ujjlenyomat azonos´ıt´ o rendszer ker¨ ul ismertet´esre. Az azonos´ıt´ as dermatol´ ogiai jellemz˝ ok alapj´ an t¨ ort´enik. ´ giai alapfogalmak Dermatolo Az ujjlenyomat alapj´ an t¨ ort´en˝ o azonos´ıt´ as (daktiloszk´ opia) biol´ ogiai alapj´ at az ujjak b˝ orred˝ oinek mint´ azata szolg´ altatja. Ezek a b˝ orred˝ ok vagy b˝ orl´ecek (tori dactyles) az ujjbegyek b˝ or´enek irhar´eteg´eben lev˝ o k¨ ot˝ osz¨ oveti szem¨ olcs¨ ok a ´ltal okozott h´ amkiemelked´esek (l´ asd 1.´ abra).
Typeset by AMS-TEX
1
2
´ FAZEKAS GABOR ´ FAZEKAS ATTILA ES
1. a ´bra. A b˝ orl´ ecek fel´ ep´ıt´ ese
A daktiloszk´ opi´ aban a b˝ orl´ecek pozit´ıv lenyomataira a fodorvonal vagy fodorsz´ al elnevez´es terjedt el. A b˝ orred˝ ok k¨ ozti m´elyed´eseket a ´ltal´ aban csak v¨ olgynek nevezik. A h´ amfel¨ uleti mint´ aknak k´et szintj´et is meg szokt´ ak k¨ ul¨ onb¨ oztetni, a glob´ alis vagy makromint´ akat ´es a lok´ alis vagy mikromint´ akat. A n´eh´ any (max. 3–5) fodorvonal m´eretig terjed˝ o mint´ akat szok´ as lok´ alis mint´ aknak nevezni, az enn´el nagyobbakat glob´ alisnak. Mivel a dermatol´ ogiai mint´ ak a fodorvonalakb´ ol a ´llnak, ez´ert a kialakult mint´ azatok is vonalas szerkezet˝ uek. Ebb˝ ol ad´ od´ oan a mint´ azatok egyik legfontosabb jellemz˝ oje az ir´ anyults´ ag, vagyis a fodorvonalak ir´ any´ anak alakul´ asa a mintafel¨ uleten. Mivel — lok´ alisan szeml´elve — a fel¨ ulet nagy r´esz´en a fodorvonalak p´ arhuzamosan futnak, ez´ert ´ertelmes a fel¨ ulet egyes pontjainak ir´ any´ ar´ ol besz´elni. A glob´ alis mint´ ak m´ asik fontos jellemz˝ oje a fodorvonalak kapcsol´ od´ as´ ab´ ol, ela ´gaz´ as´ ab´ ol ´es megsz¨ un´es´eb˝ ol kialakul´ o fodorvonal-rendszerek jellegzetess´egei. A manu´ alis dermatol´ ogia a glob´ alis jellemz˝ ok keres´es´eben els˝ osorban a kialakult fodorvonal mint´ azatok felismer´es´ere, le´ır´ as´ ara helyezte a hangs´ ulyt, az ir´ anyults´ agot csak mint ezek m´ asodlagos jellemz˝ oj´et vett´ek figyelembe. Ez alapj´ an a manu´ alis dermatol´ ogia egy ujjlenyomat le´ır´ asa sor´ an olyan fogalmakat haszn´ al, mint ´ıvek, hurkok, o ¨rv´enyek, boltozat stb. Ezeknek az alakzatoknak sz´ amos tov´ abbfinom´ıt´ asa l´etezik, s az ezek a ´ltal gener´ alt oszt´ alyoz´ ast haszn´ alj´ ak a mint´ azatok le´ır´ as´ an´ al. Egy m´ asfajta terminol´ ogia ezeknek a mint´ aknak a k¨ ozponti r´esz´et — amelyek azzal jellemezhet˝ ok, hogy k¨ ornyezet¨ ukben a fodorvonalak ir´ anyults´ aga jellemz˝ o m´ odon elt´er a minta m´ as r´eszeit˝ ol — minoroknak szokta nevezni.
´ DERMATOLOGIAI ´ ˝ ALAPJAN ´ UJJLENYOMAT-AZONOS´ITAS JELLEMZOK
3
2. a ´bra. A glob´ alis mint´ ak alapt´ıpusai
Ezeknek az oszt´ alyoz´ asoknak a haszn´ alata a sz´ am´ıt´ og´epes azonos´ıt´ as sor´ an igen neh´ezkesnek bizonyult. Egyr´eszt els˝ osorban olyan jellemz˝ okkel ´ırhat´ ok le, amelyek a sz´ am´ıt´ og´epes k´epfeldolgoz´ as eszk¨ ozeivel nehezen nyerhet˝ ok ki az input k´epb˝ ol — p´eld´ aul topol´ ogiailag ekvivalensek —, m´ asr´eszt az ezen alapul´ o m´ odszerek rendk´ıv¨ ul hiba´erz´ekenyek, ak´ ar egyetlen fodorvonal megszakad´ asa felismerhetetlenn´e teszi a sz´ am´ıt´ og´ep sz´ am´ ara az adott mint´ at. Enn´el k¨ onnyebbnek t˝ unik a lok´ alis mint´ ak alkalmaz´ asa, ezeket a daktiloszk´ opia o ¨sszefoglal´ oan minutiae-nek nevezi. Itt a legfontosabb a trir´ adiuszok ´es a vill´ ak megeml´ıt´ese, de ide sorolj´ ak a t¨ or´eseket ´es v´egz˝ od´eseket is. ´erdemes megeml´ıteni, mint ahogy erre Hung [5] cikke is felh´ıvja a figyelmet, hogy a minutiae-k k¨ oz¨ ott l´etezik egyfajta dualit´ as. P´eld´ aul ahol az el˝ ot´eren el´ agaz´ as van, ott a h´ att´ervonalak k¨ oz¨ ott egy v´egz˝ od´es van, ´es viszont, az el˝ ot´erben egy fodorvonal megszakad´ asa a h´ att´ermint´ azaton villaszer˝ u alakzatot k´epez. A trir´ adiuszok olyan t¨ obb fodorvonalb´ ol a ´ll´ o mint´ ak, ahol h´ arom k¨ ul¨ onb¨ oz˝ o ir´ anyb´ ol ´erkez˝ o fodorvonalak futnak o ¨ssze egy pontba, vagy kanyarodnak el a k¨ oz´eppont k¨ or¨ ul. Ennek sz´ amos v´ altozata lehets´eges aszerint, hogy k¨ oz´epen tal´ alkoznak-e a vonalak, illetve hogy milyen az egyes ir´ anyok egym´ ashoz k´epesti elhelyezked´ese. A legkisebb, az azonos´ıt´ asban hasznosnak bizonyult mint´ ak a vill´ ak, m´ asik hasz-
4
´ FAZEKAS GABOR ´ FAZEKAS ATTILA ES
n´ alt nev¨ uk¨ on bifurk´ aci´ ok. Ezek olyan pontok, ahol egy fodorvonal kett´ev´ alik ´es k´et p´ arhuzamos vonalban folytat´ odik. Defini´ alhat´ o a villa ir´ anya is, ami a ´ltal´ aban a villa ,,sz´ ar´ anak” (,,nyel´enek”) kifut´ asi ir´ any´ at jelenti. A vill´ akkal t¨ ort´en˝ o azonos´ıt´ ashoz kapcsol´ odik a villacsoportok fogalma is. Szint´en gyakorlati tapasztalat, hogy ha egy viszonylag kis ter¨ uleten t¨ obb egyforma a ´ll´ as´ u villa, u ´n. villacsoport is tal´ alhat´ o, akkor ezek az azonos´ıt´ as szempontj´ ab´ ol fontosabb inform´ aci´ ot jelentenek, mint az egyes vill´ ak magukban. Egy villacsoport a benne tal´ alhat´ o vill´ ak sz´ am´ aval ´es k¨ oz¨ os ir´ anyukkal jellemezhet˝ o. A gyakorlati daktiloszk´ opia tapasztalatai alapj´ an a ´ll´ıthat´ o, hogy a glob´ alis alakzatok mellett a vill´ ak hordozz´ ak a legt¨ obb azonos´ıt´ asra alkalmas inform´ aci´ ot az ujjlenyomatr´ ol. Ez magyar´ azza, hogy az a ´ltalunk kifejlesztett rendszer ezeket kit¨ untetett figyelemmel kezeli. Egy harmadik, azonos´ıt´ asra haszn´ alt kieg´esz´ıt˝ o m´ odszer az u ´n. fodorsz´ al-sz´ aml´ al´ as. Ennek sor´ an az ujjlenyomat k´et kijel¨ olt pontja — p´eld´ aul k´et minutiae k¨ oz´eppontja — k¨ oz¨ ott megh´ uzott egyenes szakasz a ´ltal metszett fodorvonalakat sz´ amolj´ ak meg, ´es ezt tekintik a fodorvonal-rendszer egyik azonos´ıt´ asi jegy´enek. ´m´ıto ´ g´ ´si elja ´ ra ´s a ´ltala ´nos va ´zlata A sza epes ujjlenyomat azonos´ıta Az a ´ltalunk kifejlesztett ´es implement´ alt azonos´ıt´ asi elj´ ar´ ast a 3. a ´br´ an v´ azolt rendszers´ema szeml´elteti.
3. a ´bra. Az azonos´ıt´ as a ´ltal´ anos rendszers´ em´ aja
Az els˝ o l´ep´es a minta tulajdonk´eppeni lev´etele. Jelenleg alapj´ aban v´eve h´ arom alapvet˝ o m´ odszeren alapul´ o le´erz˝ o berendez´est haszn´ alnak az ujjlenyomat lev´etel´ere: optikai, l´ezeres, elektromechanikus. A le´erz˝ o berendez´esek tipikus fel´ep´ıt´es´er˝ ol p´eld´ aul a [7,8]-ban olvashatunk. A fizikai letapogat´ as ´es a kapott k´ep digitaliz´ al´ asa tulajdonk´eppen az azonos´ıt´ asi folyamat inputjak´ent tekinthet˝ o. Az alkalmazott elj´ ar´ as olyan szempontb´ ol fontos, hogy ennek sor´ an milyen torzul´ asok, zajok keletkezhetnek az eredeti forr´ ashoz k´epest. A legtipikusabb hib´ ak az elmos´ od´ as, t´ ul- vagy alultel´ıtetts´eg, nem line´ aris geometriai torzul´ as, eltol´ od´ as, elfordul´ as. A fentiek, a t´ ul- vagy alultel´ıtetts´eg ´es a nem line´ aris geometriai torzul´ as kiv´etel´evel a ´ltal´ aban a letapogat´ o hardver fejleszt´ese sor´ an kik¨ usz¨ ob¨ olhet˝ ok. A t´ ul- vagy alultel´ıtetts´eg korrig´ al´ asa megtehet˝ o pl. [5]-ben tal´ alhat´ o algoritmus haszn´ alat´ aval. Az els˝ o l´ep´es eredm´enyek´ent a ´ltal´ aban egy sz¨ urkesk´ al´ as k´ep keletkezik. Ezt a k´epet a saj´ atoss´ agok kinyer´es´ehez kedvez˝ obb alakra kell hoznunk. Ennek ´erdek´eben a k´epet el˝ osz¨ or k´etszintre v´ agjuk egy adapt´ıv algoritmus seg´ıts´eg´evel, amely a v´ ag´ asi k¨ usz¨ ob¨ oket olyan r´eszk´epeken, u ´n. cell´ akon hat´ arozza meg, ahol a fodorvonaltel´ıtetts´eg azonosnak tekinthet˝ o. ´erdemes az ´ıgy kapott bin´ aris k´epen egy sz˝ ur´est alkalmazni a s´ o-bors zaj elt¨ untet´es´ere. A lok´ alis jellemz˝ ok keres´es´eben nagy seg´ıts´eget jelent a v´ azkijel¨ ol´es, ugyanis a v´ azon a ´ltal´ aban k¨ onnyebb megtal´ alni a lok´ alis mint´ akat. A rendszer¨ unkben mi a [2]-ben tal´ alhat´ o v´ekony´ıt´ o algoritmust haszn´ altuk.
´ DERMATOLOGIAI ´ ˝ ALAPJAN ´ UJJLENYOMAT-AZONOS´ITAS JELLEMZOK
5
A harmadik l´ep´es bizonyos szempontb´ ol a leg´erdekesebb r´esze a folyamatnak, itt t¨ ort´enik meg az azonos´ıt´ ashoz sz¨ uks´eges dermatol´ ogiai jellemz˝ ok kinyer´ese. Err˝ ol r´eszletesebben olvashatunk a cikk 3. ´es 4. fejezet´eben. A jellemz˝ ok kinyer´ese a gyakorlatban k´et c´elt szolg´ al. Haszn´ alhat´ ok a kinyert jellemz˝ ok az etalon elk´esz´ıt´es´ehez, teh´ at annak a jellemz˝ o-egy¨ uttesnek a meghat´ aroz´ as´ ahoz, amelyhez a k´es˝ obbiekben hasonl´ıtjuk az u ´jabb mint´ akat. Ez az etalon egyszer k´esz¨ ul el ´es ker¨ ul t´ arol´ asra. Err˝ ol r´eszletesebben a cikk 5. fejezet´eben olvashatunk. A rendszer tov´ abbi haszn´ alata sor´ an a jellemz˝ ok kinyer´ese az u ´j mint´ anak a r´egivel t¨ ort´en˝ oo ¨sszevet´es´ere szolg´ al. A tulajdonk´eppeni azonos´ıt´ asi folyamat utols´ o l´ep´es´et jelenti a d¨ ont´es, amikor az etalonb´ ol nyert jellemz˝ oket o ¨sszevetj¨ uk az u ´jabb minta jellemz˝ oivel, ´es ez alapj´ an hozzuk meg a pozit´ıv vagy negat´ıv identifik´ aci´ os d¨ ont´est. A d¨ ont´esi modellr˝ ol a 6. fejezetben olvashatunk. ´lis ira ´nyjellemzo ˝ k kinyer´ Globa ese A glob´ alis mint´ ak elemz´es´ehez sz¨ uks´eg van a minta egyes ter¨ uleteihez rendelhet˝ o ir´ anyults´ ag meghat´ aroz´ as´ ara. A [4-6]-ban is felbukkan az az o ¨tlet, hogy minden egyes pixelhez rendelj¨ unk egy ir´ anyt, ´es ezzel a vektormez˝ ovel ´ırjuk le a k´epet. Ez a fajta jellemz´es azonban meglehet˝ osen redund´ ans. A ponthoz rendelt ir´ anyt mindig egy k¨ ornyezet´enek vizsg´ alat´ aval hat´ arozzuk meg. Ez pedig azt jelenten´e, hogy az egyes k´eppontokhoz rendelt ir´ anyadatok o ¨sszes inform´ aci´ otartalma j´ oval kevesebb lenne, mint a t´ arolt adatmennyis´eg. Ennek kik¨ usz¨ ob¨ ol´es´ere az ir´ anyults´ agra vonatkoz´ o inform´ aci´ okat s˝ ur´ıtve, u ´n. ir´ anym´ atrixban t´ aroljuk a rendszer¨ unkben. Az ir´ anym´ atrix olyan m´ atrix, amelynek egy-egy eleme az eredeti ujjlenyomat egy ter¨ ulet´enek — tipikusan egy cell´ anak — a jellemz˝ o ir´ anyults´ ag´ at t´ arolja. Ha az eredeti m´ atrix n × m-es, a cell´ ak m´erete pedig k × l-es, akkor az ir´ anym´ atrix m´erete bn/kc × bm/lc. Az ujjlenyomat glob´ alis jellemz´es´ere szolg´ al´ o ir´ anym´ atrixt rendszer¨ unkben l´ anck´ odol´ assal hat´ arozzuk meg. Ennek m´ odszer´et ismertetj¨ uk az al´ abbiakban.
6
´ FAZEKAS GABOR ´ FAZEKAS ATTILA ES
L´ anck´ odol´ as. A l´ anck´ odol´ asi elj´ ar´ as a v´ekony´ıtott k´epb˝ ol, a fodorvonalak v´ az´ ab´ ol indul ki. Az algoritmus a klasszikus irodalmi algorimusokhoz k´epest elt´er´est mutat abban, hogy a v´ azpontokhoz hozz´ arendelt k´ odok nemcsak ir´ any, hanem m´ as speci´ alis k´ odok (pl. el´ agaz´ as vagy v´egpont) is lehetnek. A l´ anck´ odol´ as az ir´ anym´ atrix meghat´ aroz´ as´ an t´ ul is hasznos inform´ aci´ okat ny´ ujt. Egyik haszna, hogy lehet˝ os´eget ad a v´ azkijel¨ ol´es olyan hib´ ainak korrig´ al´ as´ ara, mint a szakad´ asok vagy a hamis el´ agaz´ asok. M´ asr´eszt arra is lehet˝ os´eg ny´ılik, hogy a lok´ alis alakzatok, a minutiae-k hely´enek ´es jelleg´enek meghat´ aroz´ as´ ahoz felhaszn´ aljuk az ´ıgy kapott jellemz˝ oket. A k´ odol´ as ut´ an a v´ azat k´et alapvet˝ o korrekci´ onak vetj¨ uk al´ a: a szakad´ asok ´es az u ´n. hamis a ´gak elt´ avol´ıt´ as´ anak. A szakad´ asok korrekci´ oja azokat a hib´ akat pr´ ob´ alja meg korrig´ alni, amelyek vagy m´ ar a mintav´etelez´es sor´ an, vagy a feldolgoz´ as sor´ an valamely fodorsz´ al megszakad´ as´ ahoz vezettek. Az a ´ltalunk adott krit´erium ezen hib´ ak felismer´es´ere igen egyszer˝ u: k´et azonos ir´ anyba es˝ o v´egz˝ od´espont nem lehet a minta a ´tlagos fodorsz´ alvastags´ ag´ at´ ol f¨ ugg˝ o megadott k¨ usz¨ obn´el k¨ ozelebb. A tapasztalatok szerint, ha ez bek¨ ovetkezik, akkor ott val´ oj´ aban szakad´ as t¨ ort´ent, ´es a k´et pont o ¨sszek¨ ot´es´evel (´es megfelel˝ oa ´tk´ odol´ as´ aval) korrig´ aland´ o. A m´ asik korrekci´ o, amit a l´ anck´ odolt v´ az alapj´ an el lehet v´egezni, a hamis a ´gak elt´ avol´ıt´ asa, vagyis azoknak a hamis v´ az´ agaknak a t¨ orl´ese, amelyek a kor´ abbi zajokb´ ol/hib´ akb´ ol fakad´ oan a v´ azkijel¨ ol´es sor´ an keletkeztek. Abb´ ol kiindulva, hogy a fodorsz´ alak hossza adott felbont´ as mellett nagy, a hamis a ´gak elt´ avol´ıt´ asa egy egyszer˝ u krit´eriumra t´ amaszkodhat: Ha az el´ agaz´ asi pontb´ ol kiindul´ o sz´ alak valamelyike egy adott pixelsz´ am-k¨ usz¨ obn´el hamarabb fejez˝ odik be, akkor az ,,hamisnak” min˝ os¨ ul, ´es t¨ orlend˝ o. Ir´ anym´ atrix-meghat´ aroz´ as l´ anck´ odolt v´ az alapj´ an. A l´ anck´ odolt v´ az elk´esz´ıt´es´evel ´es korrekci´ oival rendelkez´esre a ´ll az az inform´ aci´ o, amely alapj´ an az ir´ anym´ atrix meghat´ arozhat´ o. Az ir´ anym´ atrix egy elem´enek meghat´ aroz´ as´ ahoz o ¨ssze kell sz´ amolni a megfelel˝ o cell´ aba es˝ o k¨ ul¨ onb¨ oz˝ o k´ od´ u v´ azpontokat, majd ezekb˝ ol a gyakoris´ agokb´ ol sz´ am´ıthat´ o ki a f˝ o ir´ anyjellemz˝ o. A m´ ashol alkalmazott ir´ anym´ atrix-meghat´ aroz´ asokhoz k´epest u ´j, hogy a minta megfelel˝ o cell´ aj´ ahoz nem felt´etlen¨ ul rendel¨ unk ir´ anyt, s ´ıgy lehet˝ os´eg van a k´es˝ obbi elj´ ar´ asok sz´ am´ ara explicite jelezni, hogy az adott ter¨ ulet valamilyen okb´ ol nem jellemezhet˝ o egy´ertelm˝ uen ir´ anyults´ aggal, azt a d¨ ont´esi folyamatban k´es˝ obb figyelembe venni nem c´elszer˝ u. Jel¨ olje n0 , n1 , n2 , n3 rendre a 0◦ , 45◦, 90◦, 135◦ k´ oddal rendelkez˝ o v´ azpontok, n pedig az o ¨sszes v´ azpont sz´ am´ at az adott cell´ aban. Ha az n egy adott k¨ usz¨ obn´el kisebb, vagy egy m´ asik k¨ usz¨ obn´el nagyobb, akkor nem rendel¨ unk ir´ anyt az adott cell´ ahoz. Az ir´ anym´ atrixba t´ aroland´ o elemet a k¨ ovetkez˝ ok´eppen hat´ arozzuk meg: (1) Ha n0 = 0 ´es n1 = n3 , akkor a cella ir´ anya 90◦. (2) Sz´ amoljuk ki a Γ ir´ anysz´ amot a k¨ ovetkez˝ ok´eppen: n1 + n 2 + n 3 , n0 + n 1 − n 3 Γ= − n1 + n 2 + n 3 , n0 − n 1 + n 3
ha n1 ≥ n3 egy´ebk´ent.
(3) Ha |Γ| < 0.2, akkor a cell´ ahoz tartoz´ o ir´ any 0◦.
´ DERMATOLOGIAI ´ ˝ ALAPJAN ´ UJJLENYOMAT-AZONOS´ITAS JELLEMZOK
7
(4) Ha |Γ| ≥ 2.5, akkor a cell´ ahoz tartoz´ o ir´ any 90◦. (5) Ha Γ > 0, akkor az ir´ any 45◦, egy´ebk´ent pedig 135◦ Ha valamelyik felt´etel teljes¨ ul, akkor az hat´ arozza meg az ir´ anyt, egy´ebk´ent pedig a megadott sorrendben kell a krit´eriumokat vizsg´ alni.
sz¨ urkesk´ al´ as k´ ep
k´ etszintre v´ agott k´ ep
v´ ekony´ıtott k´ ep
sz˝ urt k´ ep
ir´ anym´ atrix
4. a ´bra. Az el˝ ofeldolgoz´ as l´ ep´ eseinek eredm´ enyei
´lis minutiae-k felismer´ A loka ese Ahhoz k´epest, hogy a daktiloszk´ opusok szerint nagy szerepe van a vill´ aknak az azonos´ıt´ asban, a szakirodalom viszonylag keveset foglalkozik ezek detekt´ al´ as´ aval. A villa olyan lok´ alis k´epz˝ odm´eny, amelynek k¨ oz´eppontj´ ab´ ol egyik ir´ anyba egy, az ezzel ellent´etes ir´ anyba k´et vonal indul ki, amelyek r¨ ovid eltart´ o szakasz ut´ an viszonylag hosszan p´ arhuzamosan futnak. A villa egyik f˝ o azonos´ıt´ oja a helye, a m´ asik az az ir´ any lehet, amerre a sz´ ara (a mag´ anyos sz´ al) fut ki. A tapasztalatok alapj´ an a villa ir´ anya mindig p´ arhuzamos a lok´ alisan jellemz˝ o fodorsz´ al-ir´ annyal. A vill´ ak kiv´ alaszt´ as´ ara az els˝ o, term´eszetesen felmer¨ ul˝ oo ¨tlet a l´ anck´ odolt v´ az felhaszn´ al´ asa. Ahol az eredeti mint´ an villa tal´ alhat´ o, ott a l´ anck´ odolt v´ aznak el´ agaz´ as k´ od´ u pontja kellene hogy legyen, ´es abb´ ol kiindulva kell a villa a ´gainak ´es sz´ ar´ anak a megfelel˝ o ir´ anyba futnia. Azonban a l´ anck´ odolt v´ azon hib´ ak is akadhatnak, ez´ert a k´et szintre v´ agott, sz˝ urt k´epet is haszn´ aljuk a villakeres´es sor´ an a k¨ ovetkez˝ o m´ odon.
8
´ FAZEKAS GABOR ´ FAZEKAS ATTILA ES
• Jel¨ olj¨ uk ki (p´eld´ aul a l´ anck´ odolt v´ az alapj´ an) a felt´etelezett villa k¨ oz´eppontj´ at. • Illessz¨ unk k´epzeletben egy akkora t´eglalapot a k¨ oz´eppont k¨ or´e, amely biztosan tartalmazza a vill´ at, elforgatva a villa felt´etelezett ir´ any´ anak megfelel˝ oen (´ ugy, hogy a t´eglalap ,,teteje” a villa felt´etelezett sz´ ara ir´ any´ aban legyen). • Sz˝ uk´ıts¨ uk minden ir´ anyb´ ol a t´eglalapot u ´gy, hogy k¨ ozben teljes¨ ulj¨ on az al´ abbi k´et felt´etel: • a t´eglalap teteje legal´ abb egy fodorsz´ alat ´erintsen; • a t´eglalap alja legal´ abb k´et fodorsz´ alat ´erintsen. • Ha a fenti felt´etelek mellett egy megadott k¨ usz¨ obn´el kisebbre o ¨ssze tudjuk h´ uzni a t´eglalapot, akkor az tartalmazza egy megfelel˝ o ir´ any´ u villa k¨ ozep´et. Mint azt m´ ar kor´ abban is megjegyezt¨ uk, a villacsoportoknak daktiloszk´ opiai szempontb´ ol k¨ ul¨ onleges jelent˝ os´ege van. A tapasztalat szerint az egym´ ashoz k¨ ozel es˝ o, t¨ obb azonos ir´ any´ u vill´ ab´ ol a ´ll´ o csoport az egyedi vill´ an´ al j´ oval nagyobb azonos´ıt´ o jelleggel b´ır. Ez´ert k´esz´ıtett¨ uk fel a rendszer¨ unket a villacsoportok felismer´es´ere is. Az etalonk´ esz´ıt´ es folyamata A k´esz´ıt´es folyamat´ at egyr´eszt maga a jellemz˝ ok kijel¨ ol´ese alkotja, m´ asr´eszt a defini´ al´ as folyamat´ aba ´ep´ıtett ellen˝ orz´esek. B´ ar u ´gy tervezt¨ uk meg a rendszert, hogy az etalon defini´ al´ asa manu´ alis munka, az´ert a biztons´ ag ´erdek´eben ahol lehetett, ellen˝ orz´esi pontokat ´ep´ıtett¨ unk be. Az el˝ ofeldolgozott k´ep l´etrehoz´ as´ aval kezd˝ odhet el tulajdonk´eppen az etalondefini´ al´ as. Az etalon els˝ o elemei a minorok. Ezek az ir´ anym´ atrix cell´ ainak t´eglalap alak´ u tartom´ anyai. Jellemz˝ o m´ odon a glob´ alis mint´ anak egy-egy, ir´ anyults´ ag alapj´ an k¨ onnyen azonos´ıthat´ o r´eszlet´et tartalmazz´ ak. Jelen rendszer¨ unkben pontosan h´ arom minort kell kijel¨ olni az etalonk´esz´ıt´eshez. Ez egyr´eszt az´ert alakult ´ıgy, mert ennyi jellemz˝ o r´eszletnek mindenk´eppen kell lenni az ujjlenyomaton, u ´gyhogy ennyi elv´ arhat´ o. M´ asr´eszt az azonos´ıt´ as sor´ an a minorok fognak seg´ıteni a geometriai torzul´ as meghat´ aroz´ as´ aban. A minorokhoz kapcsol´ od´ oan, azzal a manu´ alis m´ odszerrel o ¨sszhangban, hogy a minorok k¨ oz¨ otti fodorsz´ al-sz´ amok is j´ o jellemz˝ oi az ujjlenyomat glob´ alis strukt´ ur´ aj´ anak, az etalonban minden k´epezhet˝ o minor-p´ arhoz kijel¨ olhet˝ o egy szakasz. A szakaszok helyzete, illetve a szakaszok a ´ltal metszett fodorsz´ alak sz´ ama szint´en beker¨ ul az etalonba. A szakaszok v´egpontjainak koordin´ at´ ait a megfelel˝ o minorhoz viszony´ıtva relat´ıv m´ odon sz´ am´ıtjuk. Ez biztos´ıtja a mintav´etel sor´ an bek¨ ovetkezett geometriai torzul´ asok vagy elcs´ usz´ as hat´ as´ anak kik¨ usz¨ ob¨ olhet˝ os´eg´et. A vill´ ak helyzet¨ ukkel ´es ir´ anyukkal jellemezhet˝ oek. Ez t¨ ok´eletesen elegend˝ o t´ arol´ asukhoz is. A villak¨ oz´eppontok koordin´ at´ ait is a legk¨ ozelebbi minorhoz relat´ıve ´erdemes t´ arolni, ´ıgy detekt´ al´ asukkor kiker¨ ulhetj¨ uk a torzul´ as/elcs´ usz´ as probl´em´ aj´ at. Optim´ alis h´ arom villa megad´ asa etalononk´ent. A villacsoportok eset´en a vill´ ak egyedi t´ arol´ asa mellett az o ˝ket befoglal´ o t´eglalap adatait sz¨ uks´eges m´eg t´ arolni.
´ DERMATOLOGIAI ´ ˝ ALAPJAN ´ UJJLENYOMAT-AZONOS´ITAS JELLEMZOK
9
¨ nt´ ´sa A do esi modell le´ıra A d¨ ont´esi modell gyakorlatilag egy t¨ obbdimenzi´ os intervallum megad´ as´ aval jellemezhet˝ o. A d¨ ont´esi folyamat t¨ obbl´epcs˝ os, ez annyit jelent, hogy az egyes d¨ ont´esi dimenzi´ okat nem p´ arhuzamosan vizsg´ aljuk, hanem egyes dimenzi´ okban hamarabb megvizsg´ aljuk az intervallum vet¨ ulet´ebe es´est, ´es ha ez nem k¨ ovetkezik be, akkor a teljes ki´ert´ekel´es el˝ ott elvetj¨ uk a minta-azonoss´ ag nullhipot´ezis´et. Ezeknek a komponenseknek a felsorol´ as´ ahoz legegyszer˝ ubb sorban v´egigtekinteni az a ´ltalunk alkalmazott azonos´ıt´ asi folyamat l´ep´eseit, ez meghat´ arozza azokat a mennyis´egeket, amelyek le´ırj´ ak az illeszt´es j´ os´ ag´ at, s ily m´ odon a d¨ ont´es meghoz´ as´ ara alapot ny´ ujthatnak. Minor-illeszt´ es. Az els˝ o l´ep´es az etalonban t´ arolt minorok megkeres´ese a mint´ an. Ezt az´ert fontos els˝ o l´ep´esk´ent v´egezni, mivel a minorok hely´enek megkeres´es´evel fogjuk a felismer´es folyam´ an az elcs´ usz´ as jelleg˝ u hib´ akat korrig´ alni. A minor-illeszt´eshez el˝ osz¨ or is meghat´ arozunk egy ablakot, amelyen bel¨ ul keress¨ uk a minort. Ez az ablak a minor etalonbeli hely´enek adott nagys´ ag´ u kiterjeszt´ese lesz. Ez a gyakorlatban azt jelenti, hogy b´ ar megenged¨ unk valamekkora elcs´ usz´ ast a mintav´etel sor´ an, ennek nagys´ ag´ at az adott param´eterrel korl´ atozzuk. A minor hely´enek meghat´ aroz´ asa annyib´ ol a ´ll, hogy az adott ablakon bel¨ ul a minta ir´ anym´ atrix´ ara illesztve az etalonb´ ol sz´ armaz´ o minort, megkeress¨ uk, hogy az egym´ ast fed˝ o minoroknak hol minim´ alis a t´ avols´ aga a keres´esi ablakra n´ezve. Ezt a poz´ıci´ ot tekintj¨ uk a minor mintabeli hely´enek. Ezt az etalon mindh´ arom minorj´ ara elv´egezz¨ uk. K´et minor k¨ ul¨ onb¨ oz˝ os´eg´enek a m´er´es´ehez egy metrik´ at alkalmazunk, ami a cell´ ak k¨ oz¨ otti t´ avols´ agon alapszik. K´et cella t´ avols´ aga z´erus, ha ir´ anyuk megegyezik, 1, ha ir´ anyuk 45◦-ban t´er el, ´es 2, ha az elt´er´es der´eksz¨ ognyi. Ha valamelyik cella nem rendelkezik ir´ annyal, akkor a t´ avols´ ag nincs ´ertelmezve. Az els˝ o m´ert´ek az etalon ´es a minta t´ avols´ ag´ anak m´er´es´ere ezeknek a minimumt´ avols´ agoknak az ´ert´eke. A sz´ am, amelyet bevezett¨ unk az illeszt´esi sikertelens´egnek a m´er´es´ere a maxim´ alis minort´ avols´ ag, ami a h´ arom minor minimaliz´ alt t´ avols´ aga k¨ oz¨ ul a legnagyobbat tartalmazza. A k¨ ovetkez˝ o l´ep´es a minorok relat´ıv helyzet´enek megvizsg´ al´ asa, ´es o ¨sszehasonl´ıt´ asa az etalonbeli relat´ıv helyzet¨ ukkel. Ebb˝ ol kifoly´ olag a k¨ ovetkez˝ o m´ert´ek, amelyet az etalon ´es a minta k¨ ul¨ onb¨ oz˝ os´eg´enek m´er´es´ere sz´ armaztatunk, a minorok relat´ıv helyzet´enek k¨ ul¨ onbs´ege az etalonon ´es a mint´ an. Ezt a k¨ ovetkez˝ ok´eppen defini´ aljuk: Jel¨ olje a minorok bal fels˝ o sark´ at az etalonbeli ir´ anym´ atrixban (x 1 , y1 ), (x2 , y2 ), 0 0 0 0 0 0 ol megalkotjuk (x3 , y3 ). Ugyanez a mint´ aban (x1 , y1 ), (x2 , y2 ), (x3 , y3 ). Ha ezekb˝ az (x2 − x1 , y2 − y1 , x3 − x1 , y3 − y1 , x3 − x2 , y3 − y2 ) ´es az (x02 − x01 , y20 − y10 , x03 − x01 , y30 − y10 , x03 − x02 , y30 − y20 ) vektorokat, akkor geometriai torzul´ as n´elk¨ ul ezeknek meg kell egyezni. Ennek hi´ any´ aban a torzul´ ast a k´et vektor k¨ ul¨ onb¨ oz˝ os´eg´evel lehet jellemezni. Az a ´ltalunk bevezetett k´et m´er˝ osz´ am a maxim´ alis minork¨ ul¨ onbs´eg, amely a k´et vektor koordin´ at´ ainak elt´er´ese k¨ oz¨ ul a legnagyobbat mutatja, ´es a tot´ alis minork¨ ul¨ onbs´eg, ami az o ¨sszes elt´er´esek abszol´ ut ´ert´ekeinek o ¨sszeg´et jelenti.
10
´ FAZEKAS GABOR ´ FAZEKAS ATTILA ES
Fodorsz´ al-sz´ aml´ al´ as. A k¨ ovetkez˝ o l´ep´es a fodorsz´ al-alappontok k¨ oz¨ otti szakaszok a ´ltal metszett fodorvonalak sz´ am´ anak meghat´ aroz´ asa. Ezek meghat´ aroz´ as´ an´ al az alappontokat a mint´ an a minorok m´ ar megtal´ alt helyzet´ehez relat´ıve hat´ arozzuk meg. Mivel h´ arom fodorsz´ al-alappont p´ art jel¨ olt¨ unk ki, ez´ert h´ arom ´ert´eket fogunk kapni. Ezeket o ¨sszehasonl´ıtva az etalonbeli ´ert´ekekkel u ´jabb k´et m´ert´eket defini´ alhatunk: az egyik a maxim´ alis fodorsz´ am-k¨ ul¨ onbs´eg a legnagyobb elt´er´esre, a m´ asik a tot´ alis fodorsz´ am-k¨ ul¨ onbs´eg az elt´er´esek abszol´ ut ´ert´ek´enek o ¨sszeg´ere. Ezekkel a most defini´ alt m´ert´ekekkel ´es a minorilleszt´esn´el meghat´ arozottakkal tulajdonk´eppen a vizsg´ alt ujjlenyomat glob´ alis mint´ ainak hasonl´ os´ ag´ at/k¨ ul¨ onb¨ oz˝ os´eg´et ´ırtuk le az etalonhoz viszony´ıtva. A d¨ ont´esi param´eterek m´ asik csoportj´ at a lok´ alis jellemz˝ ok adj´ ak. Villa- ´ es villacsoport keres´ es. A vill´ ak keres´es´ehez a m´ ar kor´ abban bemutatott villadetekt´ al´ o algoritmust haszn´ aljuk. A keres´es hely´ehez ism´et a minor mintabeli val´ osz´ın˝ us´ıtett helye szolg´ al referenciapontk´ent. Egy adott villa detekt´ al´ as´ anak eredm´enye dichot´ om: vagy megtal´ aljuk, vagy nem. A d¨ ont´es szempontj´ ab´ ol csak egyetlen sz´ amot tal´ altunk l´enyegesnek: a megtal´ alt vill´ ak ar´ any´ at, azaz hogy az etalonban defini´ alt vill´ ak h´ any sz´ azal´ek´ at tal´ altuk meg. A villacsoportok detekt´ al´ as´ anak sikeress´eg´ere k´et m´er˝ osz´ amot alkalmaztunk. Az els˝ o a megtal´ alt teljes villacsoportok ar´ anya, amely azt fejezi ki, hogy a villacsoportok k¨ oz¨ ul h´ any olyan van, amelynek minden vill´ aj´ at megtal´ altuk. Eml´ıtett¨ uk, hogy a villacsoportok igen fontos szerepet j´ atszanak az azonos´ıt´ asban, ez´ert fontosnak tal´ altuk, hogy a d¨ ont´esbe bevonjuk a ,,majdnem teljes” villacsoportokat is. Ugyanis a mintav´etel sor´ an valamely okb´ ol jelentkez˝ o fodorsz´ alszakad´ as k¨ onnyen eredm´enyezi egy villa elt˝ un´es´et az azonos´ıtand´ o mint´ ar´ ol. Ezek alapj´ an az azonos´ıt´ asi algoritmus nemcsak a teljes, de az u ´n. csonka villacsoportok sz´ am´ at is felhaszn´ alja a d¨ ont´eshez, amelyekn´el csak egyetlen villa hi´ anyzik az etalonban r¨ ogz´ıtett sz´ amhoz k´epest. Irodalomjegyz´ ek 1. H. Cummins and C. Midlo, Finger Prints, Palms and Soles; An Introduction to Dermatoglyphics, The Blackiston Company, USA, 1943. 2. E. S. Deutsch, Thinning algorithms on rectangular, hexagonal and triangular arrays, 9, Communications of the ACM 15 (1972), 827–836. 3. P. Baldi and Y. Chauris, Neural networks for fingerprint recognition, Neural Computation 5 (1993), 402–418. 4. B. G. Sherlock and D. M. Monro, A model for interpreting fingerprint topology, 7, Pattern Recognition 26 (1993), 1047–1055. 5. D. C. D. Hung, Enhancement and feature purification of fingerprint images, 11, Pattern Recognition 26 (1993), 1661–1671. 6. M. Kawagoe and A. Toio, Fingerprint pattern classification, 3, Pattern Recognition 17 (1984), 295–303. 7. K. Y. Yang, European Patent Application 0 459 712 A2 (1991), European Patent Office. 8. K. Y. Yang, United States Patent US 5 109 427 A (1992), United States Patent Office. 4010 Debrecen Pf:12 E-mail address:
[email protected],
[email protected]
