FVC 2002 DB1_A 1_1 pirštas

Pirštų atspaudų atpažinimas

Įvadas

Piršto atspaudų taikymai

Piršto atspaudai yra taikomi:

Pirminis piršto atspaudo vaizdo apdorojimas
http://bias.csr.unibo.it/maltoni/handbook/extract_from_4_3.pdf

Požymių išskyrimas
Alexej Kočetkov magistro darbas

1 pav. Piršto atspaudo požymių angliški terminai.

Požymių šablonų palyginimas

Požymių šablonų palyginimą pasiaiškinsime FVC 2002 DB1 A bazės pirmųjų dviejų (1_1 ir 1_2) paveikslėlių pavyzdžiu.

2 pav. FVC 2002 DB1 A bazės 1_1 (kairiau) ir 1_2 (dešiniau) pirštų atspaudų pavyzdžiai.

Iš paveikslėlių matyti, kad tai yra to paties asmens vieno piršto dviejų skenavimų rezultatai. Naudojant anglišką terminą sakysime, kad turime genuinų (autentišką) porą. Jei paveikslėliai būtų skirtingų asmenų ar skirtingų pirštų sakoma, kad turime impostorsų (angl.) arba apsišaukėlių porą.

Laikysime, kad abu atspaudai yra apdoroti ir juose išskirti požymiai. Vienas požymis turi tokius atributus: {t_i, x_i, y_i, alfa_i, c_i, g_i}. Čia

3 pav. FVC 2002 DB1 A bazės 1_1 ir 1_2 pirštų atspaudai ir jų požymiai (detalės).
Detalės išskirtos panaudojant kompanijos "Neurotechnologija" demonstracinį algoritmą.

Paveikslėliai iliustruoja grafiškai išskirtų požymius. Nesunku pastebėti, kad minučių požymių skaitinės reikšmės nėra invariantiškos standartinėms geometrinėms transformacijoms: poslinkiui ir posūkiui. Kad išspręsti šią problemą pirminiais lyginamais atributais laikysime ne požymių taškus, o linijas sudarytas iš dviejų gretimų taškų. Linijai aprašyti naudosime jos ilgį d_ij ir du kampus alfa1_ij ir alfa2_ij, kuriuos sudaro atkarpa su požymių krypčių vektoriais. Abu kampai matuojami nuo atkarpos link požymio taško vektoriaus skaičiuojant prieš laikrodžio rodyklę. Nesunku pastebėti, kad šie atkarpų požymiai bus invariantiniai (nekintantys) geometrinėms transformacijoms, kurios nekeičia atstumo tarp taškų. Todėl dviejų pirštų atkarpų požymius galima tiesiogiai lyginti ir jų artumas bus faktorius didinantis tikimybę, kad atkarpų linijų galai atitinka tuos pačius požymių centrų taškus.

4 pav. Du požymio taškus jungiančių linijų invariantiniai geometrinėms transformacijoms požymiai.

Kyla klausimas kokias požymių taškų poras apjungti atkarpomis. Pasirinkimas sudaryti visas galimas taškų poras nėra geriausias, nes susidarytų labai daug linijų ir būtų sunku sukurti efektyvų (greitą) atkarpų palyginimo algoritmą bei gali kilti triukšmo problema dėl klaidingai išskirtų minučių. Galimi įvairūs sprendimai. Galima fiksuoti i-ojo požymio centrą ir surasti jam visas detales (angliškas požymio centro minutia terminas) nutolusias ne daugiau pasirinkto atstumo R. Kitas variantas rekomenduojamas JAV nacionalinio standartų instituto (NIST) suskaidyti i-ojo požymio atžvilgiu atspaudą į aštuonis sektorius ir kiekviename sektoriuje pasirinkti po vieną ar dvi artimiausias detales.

5 pav. Požymio aplinkos išsirinkimas dvejais būdais Pirmuoju atveju atkarpomis sujungiami nutolę nedidesniu pasirinktu atstumu R taškai. Kitu atveju pasirinkos i-osios detalės atžvilgiu vaizdas padalinamas į keturis arba aštuonis sektorius ir apjungiamos kiekviename sektoriuje esančios artimiausios detalės. Sektorių skaidymas ir numeracija pradedama pasirinktos centrinės detalės krypties, t.y. nulinio sektoriaus vienas kraštų eina detalės kryptimi.

Praktinis darbas

Sukurkite piršto atspaudų vizualizacijos ir atpažinimo sistemą.

Planuojama užduoties vykdymo trukmė 4 savaitės.

1 sav. Nuskaitykite FVC2002_DB1_A_features.txt faile pateiktus pirštų atspaudų požymių duomenis ir juos vizualizuokite, t.y. sukurkite 3 pav. analogą.

Vieno piršto požymiai įrašyti vienoje teksto eilutėje tokiu formatu: 

failo vardas \t piršto požymių skaičius \t tipas \t x koordinatė \t y koordinatė \t kryptis \t kreivumas \t tankis \t tipas \t x koordinatė ... \t tankis \n

Visi pirštų atspaudų failai yra pateikti "*.tif" formatu ir įrašyti http://uosis.mif.vu.lt/atpazinimas/finger/FVC/2002/DB1_A/ kataloge.

Trumpai apibūdinsime parametrus.

  1. failo vardas yra tif formato failas, kuriame yra nuskenuoto piršto atspaudo vaizdas. Failai patalpinti "http://uosis.mif.vu.lt/atpazinimas/finger/FVC/2002/DB1_A/" kataloge.
  2. piršto požymių skaičius yra sveikasis skaičius, kurio reikšmė gali kisti nuo 0 iki 254.
  3. tipas yra sveikasis skaičius, kurio reikšmė gali būti 0, 1 arba 2. 0 reiškia, kad požymio (detalės/minutia) tipas nežinomas, 1 - linijos galas, 2 - bifurkacija (linijos išsišakojimo į dvi dalis vieta).
  4. x koordinatė yra sveikasis skaičius, kurio reikšmė gali kisti nuo 0 iki piršto atspaudo paveikslėlio storio - 1.
    Laikoma, kad piršto atspaudo paveikslėlio viršutinio kairiojo taško koordinatės yra (0,0).
  5. y koordinatė yra sveikasis skaičius, kurio reikšmė gali kisti nuo 0 iki piršto atspaudo paveikslėlio aukščio - 1.
  6. kryptis yra sveikasis skaičius, kurio reikšmė gali kisti nuo 0 iki 255. 0 reiškia horizontalią kryptį nuo kairės į dešinę, 64 = 256/4 yra vertikali kryptis nuo viršaus link apačios ir t.t. Krypčiai saugoti patogu naudoti byte tipo kintamąjį, nes atliekant aritmetiką su byte skaičiais automatiškai gauname periodiškumą.
  7. kreivumas yra sveikasis skaičius, kurio reikšmė gali kisti nuo 0 iki 255. 255 žymi neapibrėžto kreivumo kodą. Kuo požymio aplinkoje piršto atspaudo linijos kreivesnės, tuo šis parametras didesnis. Šiam skaičiui patartina išskirti byte tipo lauką.
  8. tankis yra sveikasis skaičius, kurio reikšmė gali kisti nuo 0 iki 255. 255 žymi neapibrėžto (nežinomo) tankio kodą. Kuo požymio aplinkoje piršto atspaudo linijos tankesnės, tuo šis parametras didesnis. Šiam skaičiui taip pat patartina išskirti byte tipo lauką.

Žemiau pateiktas Java Minutia klasės pavyzdys, kuris apibrėžia duomenų struktūrą naudingą piršto atspaudo vienai detalei saugoti. 



package pirstai;

import java.util.*;
import util.*;

public class Minutia
{
 final public static int NEZINOMAS = 0;
 final public static int GALAS = 1;
 final public static int BIFURKACIJA = 2;
 protected static int markColorNEZINOMAS = my.AB;
 protected static int markColorGALAS = my.AG;
 protected static int markColorBIFURKACIJA = my.Y;
 protected static int markKryptisColor = my.AR;
 protected int tipas;
 protected int x;
 protected int y;
 protected byte kryptis;
 protected byte kreivumas;
 protected byte tankis;
 public Minutia(StringTokenizer st)
 {
	tipas = Integer.parseInt(st.nextToken());
	if (tipasBIFURKACIJA)
	{
		System.err.println("Blogas tipas: "+tipas);
		System.exit(1);
	}	
	x = Integer.parseInt(st.nextToken());	
	y = Integer.parseInt(st.nextToken());	
	kryptis = (byte)Integer.parseInt(st.nextToken());	
	kreivumas = (byte)Integer.parseInt(st.nextToken());	
	tankis = (byte)Integer.parseInt(st.nextToken());
//	my.p(this);
 }
 public void mark(int[] data, int w, int h, int R)
 {
	mark(data, w, h, (tipas==NEZINOMAS)?markColorNEZINOMAS:
		(tipas==GALAS)?markColorGALAS:markColorBIFURKACIJA, R);
 }
 public void mark(int[] data, int w, int h, int color, int R)
 {
	int R1 = R*R-3*R, R2 = R*R+3*R;
	for (int i=-R; i<=R; i++) 	
		for (int j=-R; j<=R; j++)
			if (i*i+j*j>=R1 && i*i+j*j<=R2)
				data[Math.max(0,Math.min(w-1,x+i)) +
					w*Math.max(0,Math.min(h-1,y+j))] = color;
	double	c = Math.cos(kryptis*Math.PI/128),
		s = Math.sin(kryptis*Math.PI/128);
	for (int l=0; l!=2*R; l++)
	{
		for (int ii=-1; ii!=2; ii++)
			for (int jj=-1; jj!=2; jj++) if (ii*ii+jj*jj!=2)
				{
					int i = (int)(0.5 + Math.max(0,Math.min(w-1, x + l*c + ii)));
					int j = (int)(0.5 + Math.max(0,Math.min(h-1, y + l*s + jj)));
					data[i + j*w] = markKryptisColor;
				}
	}
 }
 public String toString()
 {
	return "["+tipas+","+x+","+y+","+kryptis+","+kreivumas+","+tankis+"]";
 } 
}

Klasėje yra metodas mark skirtas grafiškai pažymėti piršto atspaudo požymio parametrus wxh dydžio paveikslėlyje, kurio spalvos pateiktos int[] data masyve. Minutia klasės konstruktorius naudoja StringTokenizer klasės elementą iš kurio pakartotinai naudodamas nextToken() metodą gauna atskirų požymių tekstines reikšmes, kurios statiniu Integer.parseInt() metodu paverčiamos skaitinėmis reikšmėmis.

Už laiku atsiskaitytą aprašytos užduoties dalį skiriama iki 0.5 egzamino balų.

2 sav. Sudarykite ir vizualizuokite piršto atspaudo detalių žvaigždines aplinkas. Žvaigždinės aplinkos vizualizacijos pavyzdys pateiktas 4 pav..

Atliekant užduotį rekomenduojama sukurti "Minutiae" - detalių aibės, "Line" - dvi minutes jungiančios linijos ir "Star" - iš vienos detalės išeinančių linijų aibės, struktūras. "Star" struktūrą sudaro centrinė detalė ir iš jos einančios linijos iki artimiausių kitų detalių pasirinktuose sektoriuose. Rekomenduojamas sektorių skaičius yra 4 arba 8, artimiausiųjų kaimynų sektoriuje - 1 arba 2. Pirmojo ir paskutiniojo sektorių jungimosi linija eina centrinės detalės kryptimi.

Žemiau pateiktas Java Minutiae klasės pavyzdys, apibrėžiantis duomenų struktūrą naudingą piršto atspaudo visiems požymiams (detalėms, minutiae) saugoti ir vizualizuoti. 


package pirstai;

import util.*;
import java.util.*;

public class Minutiae
{
 protected int length;
 protected String presentation;
 protected Minutia[] M;
 public Minutiae(String sData)
 {
	StringTokenizer st = new StringTokenizer(sData);
	presentation = st.nextToken();
	length = Integer.parseInt(st.nextToken());
	M = new Minutia[length];
	for (int l=0; l!=length; l++)
		M[l] = new Minutia(st);
 } 
 public void mark(int[] data, int w, int h)
 {
	mark(data, w, h, 7);
 }
 public void mark(int[] data, int w, int h, int R)
 {
	for (int l=0; l!=length; l++)
		M[l].mark(data, w, h, R);
 }
}

Klasėje yra metodas mark skirtas grafiškai pažymėti piršto atspaudo požymius parametrus "w x h" dydžio paveikslėlyje. Minutiae klasės konstruktorius naudoja String elementą, kurio reikšmė yra viena "FVC2002_DB1_A_features.txt" failo eilutė.

Už laiku atsiskaitytą aprašytos užduoties dalį skiriama iki 0.5 egzamino balų.

3 sav. Sukurkite pirštų atspaudų linijų palyginimo metodą, pritaikykite jį "FVC2002_DB1_A_features.txt" duomenų bazei ir įrašykite gautus rezultatus *.roc formatu.

Reikiamą informaciją apie failų atitikmenis tiems patiems pirštams rasite FVC2002_DB1_A.xml faile. Jame surašyta informacija apie pirštų atspaudų failų pavadinimus (žymė complex-presentation) ir piršto atspaudo ID (žymė complex-biometric-signature).

Čia pateikta java XMLReader klasės pavyzdys, kuri nuskaito xml faile pateiktą informaciją į java Biometric klasę.

Dviejų linijų panašumas (angl. similarity) įvertinamas neneigiamu sveikuoju skaičiu, gaunamu lyginant linijų ilgius (d) ir pradžios (alfa_1) bei galo (alfa_2) kampus (žiūr. 4 pav.). Dviejų lyginamų linijų metrikos detalės ray pasakojamos paskaitos metu. Galutinė dviejų lyginamų pirštų atspaudų panašumo reikšmė yra gaunama susumuojant geriausias linijų panašumo vertes normuojant gautą sumą iš aritmetinio arba geometrinio vieno ir kito piršto atspaudo bendro linijų skaičiaus. Taupant skaičiavimo laiką yra lyginamos tik to paties sektoriaus linijos. Atliekant užduotį rekomenduojama sukurti "Finger" duomenų struktūrą, kuri būtų sudaryta iš "Star" struktūrų imant centrinėmis detalėmis visas turimas piršto atspaudo detales saugomas "Minutiae" struktūroje.

Už laiku atsiskaitytą aprašytos užduoties dalį skiriama iki 0.5 egzamino balų.

4 sav. Realizuokite patobulintą pirštų atspaudų palyginimo algoritmą.

Siūlomi du palyginimo patobulinimai. Pirmu atveju sukaupkite geriausius linijų palyginimo taškus detalėse, kurias jungia linijos. Pavyzdžiui 1-ojo piršto 25-a linija, kurios pradžia yra 7-a, o galas 13-a detalė surinko daugiausiai panašumo taškų lyginant ją su 2-ojo piršto 20 linija, kurios pradžia yra 18-a, o galas 5-a detalė, ir atvikščiai 2-ojo piršto 20 linija surinko daugiausia taškų, kai buvo lyginama su 1-ojo piršto 25-a linija. Tuomet pirmojo piršto 7-os ir antrojo piršto 18-os, bei pirmojo piršto 13-os ir antrojo piršto 5-os detalių porų kaupiamieji panašumo taškų skaitikliai yra padidinami linijų palyginimo taškais. Sukaupus pilnai taškų statistiką sudaromi atitikmenys tarp dviejų pirštų detalių. Atitikmenys sudaromi taikant maksimumo principą, pvz. laikoma, kad pirmojo piršto 7-a detalė atitinka antrojo piršto 18-ą detalę, jei (7,18) poros surinkti kaupiamieji panašumo taškai viršija visų likusių (7,y) ir (x,18) porų kaupiamuosius palyginimo taškus.

Suradus detalių atitikmenis iš geriausių linijų 3 sav. užduoties metu rastos bendros linijų panašumo taškų sumos atmeskite panašumo taškus tų linijų, kurių bent vienas arba tik abu galai turi neatitinkančias detales. Lygindami "*.roc" kreives suraskite koks atmetimo principas geresnis. Gal iš vis geriau neatmetinėti griežtai, o įvesti linijų panašumo taškams daugiklius, pvz. 1, kai abu linijų galai turi "teisingus" detalių atitikmenis, 1/2, kai tik vieno galo atitikmuo geras ir 1/4 likusiu atveju.

Kitas palyginimo patobulinimas remiasi tankio ir kreivumo reikšmėmis. Įveskite linijų palyginimo panašumo taškų korekciją atsižvelgiant į tankio ir kreivumo reikšmių skirtumus. Pavyzdžiui galite įsivesti porą slenksčių ir suteikti visoms lyginamų linijų poroms nulinius panašumus, jei jų atitinkamų detalių galų tankių arba kreivumų skirtumai moduliu viršija jūsų pasirinktą slenkstį. Slenksčių reikšmės nustatomos eksperimentiškai optimizuojant gaunamos "*.roc" kreivės kokybę.

Už laiku atliktą aprašytos užduoties dalį skiriama iki 0.5 egzamino balų.

Greičiausiai atlikę užduotis autoriai gali būti skatinami papildomais balais. Taip pat balais skatinami autoriai nurodę netikslumus pateiktuose konspektuose.

Gale semestro jūsų pateikti algoritmai bus papildomai vertinami pagal pirštų atspaudų atpažinimo kokybę matuojamą ROC (Receiver Operating Characteristic) kreivės EER (Equal Error Rate) ir Zero FAR (Zeor False Aceptance Rate) taškuose.

Jei jūsų ROC kreivė pagal EER arba Zero FAR reikšmę patenka į FVC 2002 DB1 konkurso geriausiųjų rezultatų 20-ą, skiriami 5 papildomi balai. Jei jūsų algoritmu pasiektas rezultatas patenka į geriausiųjų pasaulio algoritmų 10-ą, už egzaminą rašomas 10-as. Kad pasiekti geriausiųjų 10-ą tikrai nepakaks apsiriboti vien šiuose konspektuose nurodytomis pirštų atspaudų palyginimo idėjomis.

 

Literatūra  
 

  1. Handbook of Fingerprint Recognition, D.Maltoni, D.Maio, A.K. Jain, S. Prabhakar
  2. Apžvalga
  3. Jean Francois puslapis
  4. Finger verification competition 2002, http://bias.csr.unibo.it/fvc2002/
  5. Alexej Kočetkov, Pirštų atspaudų atpažinimo problemos, magistro darbas, 2005 m., Vilnius