Fingerprint Identification System Rendszerterv Készítette: Venczel Viktor BMF-NIK 2007. december
Venczel Viktor
FIS
2007
Bevezetés A célom egy olyan ujjlenyomat azonosító rendszer megvalósítása, mely a beolvasott képet feldolgozza, és összeveti az adatbázisban tárolt mintával. Az ujjlenyomat mellett egyéb azonosításra is szükség van, ez határozza meg, hogy az adatbázisból melyik mintával történjen az összehasonlítás. Ez a verifikáció folyamata.
Szoftver és hardver eszközök A rendszer létrehozásához szükség van valamilyen ujjlenyomat leolvasó készülékre, mely célszerűen a számítógéphez csatlakoztatható soros, párhuzamos vagy USB porton keresztül. Ezen a csatlakozáson keresztül jutnak el a képi információk a leolvasóról a számítógépbe, ahol a feldolgozást végző szoftver beolvassa azokat. A program mely a képfeldolgozást és az összehasonlítást végzi, nem igényel kirívóan nagy hardvert. Az adatok tárolására elég egy kisebb kapacitású winchester még komolyabb elemszámú adatbázis esetében is. Memóriából ugyancsak elegendő egy olyan minimális mennyiség, ami ma már jelentéktelennek számít, ezért nem érdemes foglalkozni külön vele. Ami lényeges az a CPU sebessége, ez fogja jelentősen meghatározni a rendszer sebességét a sok számításigényes algoritmus végett. Hogy mi a jó az attól függ természetesen, hogy mire szeretnénk használni a rendszert. Ha fontos a sebesség, a minél gyorsabb feldolgozás, akkor elkelhet egy 2.4Ghz-es processzorral felszerelt gép is, de ha nem számít néhány másodperc, akkor egy kisebb teljesítmény is elegendő.
2
Venczel Viktor
FIS
Modulok Meg kell különböztetnünk itt két állapotot.
Beviteli állapot: amikor a rendszerbe új felhasználót viszünk be.
Összehasonlító állapot: amikor egy már meglévő adattal hasonlítjuk össze a beolvasottat
Beviteli állapotkor 3 modulra bontható a rendszer (1. Modulábra): 1. Beolvasó modul 2. Előfeldolgozó modul 3. Elemző modul
1. Modulábra Beviteli állapot
Az input oldalon az ujjlenyomat leolvasó, a hardver van, de ez lehet akár már tárolt látens minta is, amit képfileban adunk át a programnak. További input adat még a felhasználó adatai, melyeket tárolni szeretnénk a rendszerben. Ezek közt feltétlenül szerepelni kell annak az azonosítónak, ami alapján később a verifikáció végezhető. Ez most a felhasználó neve lesz. Kimeneti rész az, hogy az adatbázist kibővítjük egy új rekorddal, ami tartalmazza a felhasználó adatait, és a hozzá eltárolt, feldolgozott ujjlenyomat mintát. Összehasonlítás esetén négy fő részre bontható a rendszer (2. Modulábra): 1. 2. 3. 4.
Beolvasó modul Előfeldolgozó modul Elemző modul Összehasonlító modul
3
2007
Venczel Viktor
FIS
2007
2. Modulábra Összehasonlító állapot
A bemenet itt is az ujjlenyomat leolvasó vagy képfileként tárolt minta, és egy egyéb módon bevitt azonosító, a felhasználói név, mely alapján a rendszer az verifikációt elvégzi. Output oldalon jelzést küld a képernyőre a vizsgálat eredményéről, és hangjelzést is az eredmény függvényében. Ha nem feltétlenül fontos a gyorsaság, azonban a biztonság annál inkább, akkor készíthetjük úgy a rendszert, hogy kétszer vegyen mintát az ujjról, majd azokat különkülön feldolgozva az eredményeket összeveti. Ha mindkét esetben ugyanazt az eredményt kapjuk, akkor elfogadjuk helyesnek. Ha nem, akkor megtagadjuk a hozzáférést, és újabb vizsgálatot kérünk. Még jobb lehet, ha a két mintát nem ugyanarról az ujjról vesszük, hanem két különbözőről, ez viszont feltételezi legalább két minta tárolását már a rendszerben.
4
Venczel Viktor
FIS
2007
Beolvasó modul Ez a módul végzi kép előállítását az input adatokból. Bemeneti részen található a hardver, ami maga a leolvasó készülék, ami valamilyen porton keresztül csatlakoztatva van a számítógéphez, és ezen át kommunikál az alkalmazással. Bemenetként érkezik még az egyéb azonosító, mely a verifikációhoz szükséges. Ez esetünkben lehet például a név megadása, de igény szerint ez lehet akár valamilyen chip vagy kártya is. A leolvasó készülékeknek többféle változatuk van. Az egyik elterjedt változat az optikai szenzor. Ez tulajdonképpen nagyon hasonlít egy általánosan is ismert kamerához. Az üvegre helyezett ujjat alulról egy LED világítja meg, majd a visszaverődő fényt egy CCD segítségével érzékeli. Előnye a technológiának, hogy nem érzékeny az elektrosztatikus kisülésekre, hátránya azonban, hogy az eredményt jelentősen befolyásolja az ujj tisztasága és állapota. Ezenkívül a másik hátrányos tulajdonsága, hogy ez önmagában nem tudja megkülönböztetni az élő ujjat valamilyen utánzattól. Az érzékelést nyomásérzékelős felület is biztosíthatja, mely esetben az ruganyos piezoelektromos anyagból készül. A barázdák közti nyomáskülönbséget elektromos árammá konvertálja, így alakítva ki a képet az ujjról. Léteznek még hőmérséklet érzékeny szenzorok is, amelyek a fodor szálak, redők élei és a barázdák, mélyedések közötti hőmérséklet különbséget képesek mérni. Egy másik típus, ami szintén nem érzékeny az ujj tisztaságára és sérülésmentességére az ultrahangos szenzor. Ugyanazon az elven működnek, ahogy az orvosi használatban lévő ultrahangos berendezések is. Piezoelektromos mágneses erősítők által kibocsájtott hanghullámokat, és a visszavert hullámokat egyaránt mérik piezoelektromos anyagokkal. Ezek segítségével áthatolva a felhám rétegen, az alatta lévő bőrrétegről visszaverődve képet kaphatunk az ujjlenyomatról. Mivel az alsó réteg tükrözi a felső réteg karakterisztikáját, ezért ugyanazt az ujjnyomatot fogjuk kapni eredményül. A rendszer a bemenetet kaphatja azonban képfájlként is, ha egy már korábban eltárolt, látens mintát akarunk bevinni a rendszerbe inputként. Output részen továbbküldi a kép memóriába betöltött címét, szélességét és magasságát az előfeldolgozó modulnak. (1)
5
Venczel Viktor
FIS
2007
Előfeldolgozó modul Ennek a modulnak a szerepe az inputként kapott képet a későbbi feldolgozáshoz megfelelő formára hozni. A kapott képet először célszerű elmosni valamilyen szűrő segítségével. Erre alkalmas egy egyszerű átlagoló szűrő (1. ábra), mely az adott képpontban vett lokális környezet értékeit átlagolja. 1
1
1
1
1
1
1
1
1
/9
１. ábra Átlagoló szűrő maszk
Némely esetekben hasznos lehet egy mediánszűrő alkalmazása is, ami sorba rendezi a lokális környezet pixelintenzitásait, majd azok mediánjával helyettesíti a célpixelt. Ezzel kiszűrhetők a pont típusú, ill. az egy pixel vastagságú zajok. Így könnyebben elemezhető válik a mintánk. Az eredmény képen utána meghatározzuk a gradienseket például a Sobel operátorral (2. ábra), vagy Roberts keresztoperátorral, esetleg Kirsch operátorral. Ennek segítségével szegmentálhatjuk a képet, és így kiszűrhetjük a feldolgozás szempontjából lényegtelen képi részleteket, mint pl. háttér. -1
-2
-1
-1
0
1
0
0
0
-2
0
2
1
2
1
-1
0
1
２. ábra Sobel operátor
Az irodalomkutatásban már ismertetett módszert alkalmazva felosztjuk a képet WxW méretű blokkokra, majd ezeken végighaladva lokális gradiens értékeket számítunk. Ahol a bizonyossági értéknél kisebb a kiszámolt érték vagy nem határozható meg irány a felosztott képrészen, akkor azt megjelöljük háttérként, és továbbmegyünk a következő blokkra. Az ablakméret megválasztása jelentősen befolyásolja az eredményünket. Az így kapott képet binarizáljuk. Ennél a lépésnél a kritikus pont a küszöb meghatározása. Szerencsés esetben szép kontrasztos képet kapunk, ilyenkor a hisztogram tipikusan fordított W-re hasonlít, és a két kimagasló domb közötti völgy lesz a küszöb. Azonban, ha például a felhasználó az ujja egyik részét jobban rányomja, mint a másikat, abban az esetben az a fele jóval sötétebb lesz, olyan mint amikor egy képnek a két oldalát nem egyforma megvilágítás éri. Ez esetben már nem alkalmazható az előbb említett
6
Venczel Viktor
FIS
2007
módszer. Ilyenkor célszerű lokálisan változó küszöbölést alkalmazni. Erre használható a Niblack algoritmus, ami változó küszöbértékekkel dolgozik. Egy pixel adott környezetében vett középértékét és szórását veszi alapul a küszöb meghatározásához. Egyik paramétere, amit meg kell adnunk, az a környezet mérete, ami általában 15x15, 30x30 vagy 60x60-as szokott lenni. Rendelkezik továbbá egy k paraméterrel, ami azt szabályozza, hogy a szórást milyen mértékben vegye figyelemben a számítások során. Ez az érték sötét objektumok esetében nullánál kisebb, világos objektumok esetében 0-nál nagyobb érték, tipikusan 0.20.5 szokott lenni. Ha elkészült a binarizált kép, akkor még hátra van a vékonyítás fázisa. Az irodalomkutatásban ismertettet módon a binarizált képen összesen nyolcszor megyünk végig a vékonyító maszkokkal egy ciklusban. A nyolc maszk a 3. ábrán látható két maszk 90°-kal elforgatott változataiból áll össze. 0
0
0
1 1
1
1 1
0
0
1
0
1
３. ábra Vékonyító maszkok
Ezt addig ismételjük, amíg már egyetlen változás se következik be a ciklus során. Mivel ez egy rendkívül számításigényes művelet a sok ciklus miatt, fontos, hogy nagyon jól optimalizált kódot írjunk itt. Ha ez megvan, akkor a képet tovább kell küldeni az elemző modulnak. (2)
7
Venczel Viktor
FIS
2007
Elemző modul Az elemző modul feladata a vékonyított képen a minuciák megkeresése, illetve a hibák kiszűrése, a feldolgozás során keletkezett hamis minuciák eltüntetése. Ide tartozik az, hogy két egymáshoz közeli, hasonló irányultságú végződést összekössünk, mert az feltételezhetően szakadás során keletkezett, nem valódi végződések. Továbbá a túl rövid szálakat el kell tüntetni. A folyamat lényege, hogy veszünk egy 3x3-as maszkot és végigmegyünk vele a kép pixeljein. Mivel a szálak 1 pixel vastagságúak, összesen 3 fodor szál pixelt fog lefedni a maszk alapesetben. Ha csak kettőt találunk, akkor végződéshez értünk, ha 3-nál többet, akkor elágazáshoz. A probléma az, hogy a vékonyítás során keletkezhettek hamis minuciák is, ill. az ujjon található sérülések is hasonlóan hibás eredményhez vezethetnek. Ezek kiszűrése már komplikált. Szerencsére a fodor szálak követnek bizonyos szabályosságokat. Léteznek empirikus úton meghatározható értékek, például egy fodor szál minimális hosszára. Ha tehát találunk két végződést ugyanazon izolált fodor szálon, akkor azok feltehetőleg hamis minuciák. Ha a fodor szálak áramlásának irányával párhuzamosan találunk két azonos irányultságú végződést, akkor azok valószínűleg egy szakadás során keletkeztek, így ezeket összeköthetjük, ill. törölhetjük a listánkról. A kép szélén lévő végződéseket is figyelmen kívül hagyhatjuk. Ha egy elágazás egyik vége rövidebb, mint a tapasztalati úton meghatározott minimális érték, akkor biztos, hogy az valamilyen hiba folytán került oda, így ezt is kiszűrhetjük az azonosított minuciák közül. A feldolgozást csinálhatjuk úgy is, hogy előbb megkeressük az összes minuciát, a hamisakkal együtt, és utólag egy ellenőrzéssel kitöröljük azokat melyek nem tartoznak a listára, vagy már eleve a megkereséskor ellenőrizhetjük, hogy jó-e amit találtunk. Normál esetben 40-100 közötti minuciát találunk egy átlagos ujjlenyomat képen. Ezeket tárolnunk is kell. Tárolhatjuk polár koordinátás rendszerben az adatokat, aminek a lényege az, hogy minden pontot egy irány és egy távolság határoz meg. Ehhez viszont meg kell határoznunk egy középpontot, amihez viszonyítunk, és ügyelni kell arra, hogy az ujjlenyomat nincs-e elforgatva a képen. Másik megoldás, hogy a minuciák egymáshoz viszonyított helyzetét tároljuk, ami kiküszöböli az elforgatásból adódó hibákat. Ilyenkor a minuciákat egy súlyozott, irányítatlan gráf csúcspontjaiként kezeljük, melyek egy sík gráfot alkotnak. A gráf élein a súlyok a két csúcs közötti távolság, azaz a két minucia közti távolság lesz. Ez nem érzékeny így az elforgatásra, viszont egy kicsit lassabb feldolgozást eredményezhet. Az eltárolt adatokat tovább kell küldeni az Összehasonlító modulnak ha összehasonlító állapotban vagyunk, ha beviteli állapotban, akkor az eredményeket az adatbázisba kell beszúrni az új felhasználóhoz.
8
Venczel Viktor
FIS
2007
Összehasonlító modul Ez a modul input adatként megkapja a minucia adatokat, amiket össze kell hasonlítania az adatbázisban tároltakkal és megkapja a beolvasó modultól a felhasználó nevet, ami alapján keresünk az adatbázisban. Itt a felhasználó nevet, mint azonosítót használva meg kell keresni az adatbázisban a hozzá tartozó tárolt ujjlenyomat információkat. Ide bármilyen keresési algoritmus megfelel, egy lineáris keresés elegendő, de ha gyorsítani szeretnénk az eljárást, akkor felhasználói név esetében rendezett adatbázist célszerű tárolni, és alkalmazhatunk bináris keresést a hatékonyabb megtalálás érdekében. Mivel törölni ritkán vagy egyáltalán nem szoktunk ilyen adatbázisból, ezért törlési részről nem igényel komolyabb műveleteket az adatbázis rendezettségének megőrzése. Beszúrás is akkor jellemző csak, amikor először feltöltik a rendszert, utána már csak ritkán kell beszúrni új elemeket az adatbázisba, így itt se gond, ha nem olyan hatékony sebesség szempontjából az algoritmusunk. Ha azt szeretnénk, hogy valaki többet ne férjen hozzá a rendszer által őrzött tartalomhoz, akkor a felhasználó rekordjában az erre megfelelő logikai típusú változót elegendő beállítani, nem szükséges törölni az egész rekordot. Ez különösen hasznos lehet, ha csak ideiglenesen szeretnénk megvonni az engedélyét a felhasználónak, így később az engedélyezésnél nem szükséges újra bevinni az adatait. Ha kiválasztottuk a kívánt rekordot, és megkaptuk a bemeneti minucia adatokat is, akkor elkezdődhet az összehasonlítás folyamata. A beolvasott adatokból képzett gráfot össze kell hasonlítani a tárolt változattal, majd ha nem egyeznek, akkor el kell forgatni ill. el kell tolni és újra próbálkozni. Sokat gyorsíthat az eljáráson, ha nem az egész gráfon hajtjuk végre ezeket a műveleteket, hanem csak egy kisebb darabját tologatjuk és forgatjuk,
４. ábra Határoló terület (2)
9
Venczel Viktor
FIS
2007
és azzal keresünk egyezést a tárolt változaton. Ha sikerült egyezést találni, akkor még meg kell róla győződni, hogy valóban egyezésről beszélhetünk-e. Ezt úgy dönthetjük el, hogy megvizsgáljuk a minuciák lokális környezetét, és ha a rávetített másik minucia ezen a határoló területen belülre esik, akkor azt egyezésnek tekintjük. Ilyen eltérések keletkezhetnek például az ujjon a bőr nyúlásának esetén, ezért szinte lehetetlen két pontosan egyforma ujjlenyomatot venni. Az összehasonlítás eredményét a program kijelzi képernyőn megjelenő üzenet formájában, és hanggal is.
Összefoglalás Ez a leírás nem feltétlenül a leghatékonyabb módszereket írja le. Igyekeztem olyan célt kitűzni, ami meg is valósítható. A továbbfejlesztés lehetősége természetesen mindig fent áll, és majd a konkrét tesztek tudják csak igazolni, hogy bizonyos esetekben gyakorlati alkalmazásnál melyik módszer a hatékonyabb, majd ezeket figyelembe véve végül optimalizáltabbá tenni a rendszert. Későbbiek során terveim szerint belekerülne még valamiféle kódolás is, ami az adatbázist hivatott védeni, ám ez ismét csak lassítaná a rendszert, mert minden alkalommal, ha hozzá szeretnénk férni az adatbázishoz, akkor valamilyen dekódolást kellene végrehajtani, viszont a biztonság szempontjából ez elengedhetetlen. Szintén ez miatt programozás technikailag ügyelni arra, hogy a memóriából gondosan kitöröljük használat után az adatokat, ill. sehol máshol ne tároljuk őket, hogy ne lehessen azokhoz kívülről hozzáférni. A rendszerben természetesen valamilyen loggolási megoldást is szeretnék alkalmazni, mely a mindenkori eseményeket tárolja valamilyen erre a célra előre meghatározott állományban a későbbi nyomon követés céljából.
10
Venczel Viktor
FIS
2007
Tartalomjegyzék Bevezetés .................................................................................................................................... 2 Szoftver és hardver eszközök ..................................................................................................... 2 Modulok ..................................................................................................................................... 3 Beolvasó modul ...................................................................................................................... 5 Előfeldolgozó modul .............................................................................................................. 6 Elemző modul ........................................................................................................................ 8 Összehasonlító modul ............................................................................................................ 9 Összefoglalás ............................................................................................................................ 10 Tartalomjegyzék ....................................................................................................................... 11
Irodalomjegyzék Idézett forrásmunkák 1. Anil K. Jain, Salil Prabhakar, and Arun Ross. Fingerprint Matching: Data Acquisition and Performance Evaluation. Michigan State University : ismeretlen szerző, 1999. MSUCPS-99-14. 2. Henrik, Bordás. AFIS. [Online] 2003. [Hivatkozva: 2007. 12 7.] http://roberta.obuda.kando.hu/iar/2001_2002/afis/index.html.
11
