\section{Pir�t� atspaud� atpa�inimas}
\begin{wrapfigure}{r}{0.60\textwidth}
    \includegraphics[width=0.25\textwidth]{figures/1_1.jpg}
%  \caption{}
\end{wrapfigure}
\begin{enumerate}\small{
\item  \hyperlink{Yvadas}{�vadas} 
\item  \hyperlink{Taikymai}{Pir�to atspaud� taikymai} 
\item  \hyperlink{Pirminis}{Pirminis apdorojimas} 
\item  \hyperlink{Pozymiai}{Po�ymi� i�skyrimas} 
\item  \hyperlink{Palyginimas}{Po�ymi� �ablon� palyginimas} 
\item  \hyperlink{Praktinis}{Praktinis darbas} 
\item  \hyperlink{Literatura}{Literat�ra} 
}\end{enumerate}
\hypertarget{Yvadas}{{\bf �vadas}}
\hypertarget{Taikymai}{{\bf Pir�to atspaud� taikymai}}
Pir�to atspaudai yra taikomi:
\begin{itemize}
\item Kriminalistikoje identifikuojant asmenis
\item Pasuose �ra�ant skaitmenine forma asmens pir�to atspaudo duomenis bei juos lyginant pvz. oro uostuose
\item �mon�se organizuojant automatin� darbuotoj� �leidimo � darbo viet� bei lankomumo registracijos sistem�
\item Masinio aptarnavimo sistemose, pvz. Maximos tipo parduotuv�se greitam kortel�s tapatyb�s patvirtinimui
\item Bankin�se sistemose identifikuojant kortel�s asmens tapatyb�.
\item Individualizuojant prieig� prie �rengini�, pvz. asmeninio kompiuterio, mobiliojo telefono.
\item Atomin�se elektrin�se, re�imin�se �staigose ir t.t.
\end{itemize}

\hypertarget{Pirminis}{{\bf Pirminis pir�to atspaudo vaizdo apdorojimas}}
 \href{http://bias.csr.unibo.it/maltoni/handbook/extract_from_4_3.pdf}{http://bias.csr.unibo.it/maltoni/handbook/extract\_from\_4\_3.pdf}

\hypertarget{Pozymiai}{{\bf Po�ymi� i�skyrimas}}
\href{Kocetkov.doc}{Alexej Ko�etkov magistro darbas}

 \begin{figure}
\centering
\includegraphics[scale=1]{figures/finger3} 
\caption{ Pir�to atspaudo po�ymi� angli�ki terminai}
 \label{fig:pirstoAngliski}
\end{figure}

\hypertarget{Palyginimas}{{\bf 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.

 \begin{figure}
\centering
\includegraphics[scale=0.75]{figures/FVC2002_DB1_A_1_1.jpg} 
\includegraphics[scale=0.75]{figures/FVC2002_DB1_A_1_2.jpg} 
\caption{ FVC 2002 DB1 A baz�s 1\_1 (kairiau) ir 1\_2 (de�iniau) pir�t� atspaud� pavyzd�iai}
 \label{fig:duPirstuPvz}
\end{figure}
 
I� \ref{fig:duPirstuPvz} paveiksl�lio matyti, kad tai yra to paties asmens vieno pir�to
dviej� skenavim� rezultatai. Tokius pir�t� por� atvejus vadinsime autenti�komis (angl. {\em genuine}).
Jei paveiksl�li� pora b�t� skirting� asmen� ar vieno asmens bet skirting� pir�t�,
kad turime apsi�auk�li� por� (angl. {\it impostors}).
 
Laikysime, kad abu atspaudai yra apdoroti ir juose i�skirti po�ymiai.
Vienas po�ymis turi tokius atributus: $\{t_i, x_i, y_i, \alpha_i\}$.
�ia 
\begin{itemize}
\item $i$ - $i$-asis po�ymis.
\item  $t_i$ - $i$-ojo po�ymio tipas (0 - neapibr��tas, 1 - linijos galas,
2 - linijos bifurkacijos (i�si�akojimo � dvi dalis) ta�kas.
\item $( x_i, y_i )$ - po�ymio centrinio ta�ko koordinat�s.
$x$ matuojama ta�keliais nuo kair�s � de�in�, $y$ - ta�keliais
nuo vir�aus � apa�i�. Vir�utinio kairiojo paveiksliuko
kampo koordinat�s yra $(0,0)$.
\item $alpha_i$ kampas, kur� sudaro $i$-ojo po�ymio vektorius einantis linijos liestin�s
kryptimi i� po�ymio centrinio ta�ko. Linijos galo atveju vektoriaus 
krytis nukreipta link linijos, i�si�akojimo atveju link i�si�akojimo.
Krypties vektorius pasirinkimas taip tod�l, kad krypties po�ymis
b�t� stabilesnis po�ymio tipo nustatymo klaidoms.
\end{itemize}


 \begin{figure}
\centering
\includegraphics[scale=0.75]{figures/FVC2002_DB1_A_1_1_poz} 
\includegraphics[scale=0.75]{figures/FVC2002_DB1_A_1_2_poz}  
  \caption{ 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 \href{http://www.neurotechnology.com}{verifinger} demonstracin� algoritm� }
  \label{fig:pirstuPozymiai}
\end{figure}
 
\ref{fig:pirstuPozymiai} pav. grafi�kai iliustruoja  i�skirtus 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_{i,j}$ ir du kampus $\alpha1_{i,j}$ ir $\alpha2_{i,j}$,
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.

 \begin{figure}
\centering
\includegraphics[scale=1]{figures/invPoz} 
  \caption{ Du po�ymio ta�kus jungian�i� linij� invariantiniai geometrin�ms transformacijoms po�ymiai }
  \label{fig:invarPozymiai}
\end{figure}
 
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 {\it detales}   (angli�kas po�ymio centro {\it 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 {\it detales}  .

 \begin{figure}
\centering
\includegraphics[scale=1]{figures/pozApl} 
  \caption{ Po�ymi� aplinka }
  \label{fig:pozymiuAplinka}
\end{figure}
\ref{fig:pozymiuAplinka} pav. iliustruoja po�ymio aplinkas i�sirinktas dviem b�dais.
Pirmuoju atveju atkarpomis sujungiami nutol� nedidesniu pasirinktu
atstumu R ta�kai. Kitu atveju pasirinktos $i$-osios {\it detal�s}   at�vilgiu
vaizdas padalinamas � keturis arba a�tuonis sektorius ir apjungiamos
kiekviename sektoriuje esan�ios artimiausios {\it detal�s}  . Sektori� skaidymas
ir numeracija pradedama pasirinktos centrin�s {\it detal�s}   krypties, t.y.
nulinio sektoriaus vienas kra�t� eina detal�s kryptimi.

\hypertarget{Praktinis}{{\bf Praktinis darbas}}
{\em
Realizuokite pir�to atspaud� palyginimo algoritm�.}

 
 Pir�t� atspaud� atpa�inimo u�duotis pasirenkama laisvai, kai atliktos privalomos u�duotys.
Darbas atliekamas auditorijoje pratyb� metu arba savaranki�kai namuose atsiskaitant auditorijoje pratyboms skirtu laiku u� atskirus etapus.

Pir�t� vaizd� pavyzd�ius rasite \href{http://www.mif.vu.lt/atpazinimas/finger/FVC/2002/DB1_A/}{fvc2002db1a.zip} archyve.
Pir�t� atspaud� po�ymis rasite \href{http://www.mif.vu.lt/atpazinimas/finger/FVC2002_DB1_A.info}{FVC2002\_DB1\_A.info} faile.
\begin{enumerate}

\item Nuskaitykite pir�to atspaudo po�ymius.
Vieno pir�to po�ymiai �ra�yti vienoje teksto eilut�je tokiu formatu:

katalogoNr	failoVardas id pir�toPo�ymi�Skai�ius tipas xKoordinat� yKoordinat� kryptis \dots tipas xKoordinat� yKoordinat� kryptis
 
Po�ymi� failo prad�ioje yra antra�t�, kurioje pateikiama bendra visiems pir�t� atspaudams informacija.
Po "String katalogas[1]" eilut�s para�ytas katalogo vardas(ai), kuriame patalpinti pir�t� atspaud� paveiksl�liai. �i� eilut� galite pakeisti, kad atitikt� j�s� kompiuteryje patalpint� raineli� pavyzd�i� katalog�(us).
 
Trumpai apib�dinsime parametrus.
\begin{enumerate}
\item  {\it katalogoNr} numeris katalogo, kuriame patalpintas rainel�s vaizdas. Jei antra�t�s eilut� yra {\it String katalogas[1]}, tai visi paveiksl�liai yra viename kataloge ir tuomet visi katalogo numeriai lyg�s 0.
\item  {\it failoVardas}   yra {\it tif}   formato failas, kuriame yra nuskenuoto pir�to atspaudo vaizdas.
Failai patalpinti \href{http://uosis.mif.vu.lt/atpazinimas/finger/FVC/2002/DB1_A/}{http://uosis.mif.vu.lt/atpazinimas/finger/FVC/2002/DB1\_A/}   kataloge.
\item {\it id} pir�to atspaudo unikalus identifikatorius. Autenti�k� pir�t� pora turi t� pat� {\it id}.
\item  {\it pir�toPo�ymi�Skai�ius}   yra sveikasis skai�ius, kurio reik�m� gali kisti nuo 0 iki 254.
\item  {\it 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).
\item  {\it x koordinat�}   yra sveikasis skai�ius, kurio reik�m� gali kisti nuo 0 iki pir�to atspaudo paveiksl�lio {\it plo�io - 1}. 
Laikoma, kad pir�to atspaudo paveiksl�lio vir�utinio kairiojo ta�ko koordinat�s yra (0,0). 
\item  {\it y koordinat�}   yra sveikasis skai�ius, kurio reik�m� gali kisti nuo 0 iki pir�to atspaudo paveiksl�lio {\it auk��io - 1}.
\item  {\it 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 {\it byte}   tipo kintam�j�, nes atliekant aritmetik�
su byte skai�iais automati�kai gauname periodi�kum�.
\end{enumerate}
 
�emiau pateiktas Java {\em Minutia.java} klas�s pavyzdys, kuris apibr��ia
duomen� strukt�r� nauding� pir�to atspaudo vienai {\it detalei} saugoti.
Pagalbin� klas� {\em Tipas.java}

\lstinputlisting{java/Tipas.java}

\lstinputlisting{java/Minutia.java}
 
Klas�je yra metodas {\it 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.


Nuskai�ius po�ymius, sudarykite ir vizualizuokite pir�to atspaudo detali� �vaig�dines
aplinkas. �vaig�din�s aplinkos vizualizacijos pavyzdys pateiktas \ref{fig:pozymiuAplinka} pav.

Atliekant u�duot� rekomenduojama sukurti "Minutiae" - detali� aib�s,
"Line" - dvi minutes jungian�ios linijos ir "Star" - i� vienos {\it 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 {\em Minutiae.java} klas�s pavyzdys, apibr��iantis
duomen� strukt�r� nauding� pir�to atspaudo visiems po�ymiams (detal�ms, minutiae) saugoti
ir vizualizuoti.

\lstinputlisting{java/Minutiae.java}
 
Klas�je yra metodas {\it 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,info" failo eilut�.

Vertinama iki \textcolor{gold}{1.25 balo}.

\item
Sukurkite pir�t� atspaud� linij� palyginimo metod�,
pritaikykite j� "FVC2002\_DB1\_A.info" duomen� bazei ir �ra�ykite
gautus rezultatus \href{http://www.mif.vu.lt/~bastys/academic/ATE/ROC/ROC.htm}{*.roc} formatu.
  Reikiam� informacij� apie fail� atitikmenis tiems patiems pir�tams
nustatysite pagal po�ymio failo {\it id} parametro reik�mes.
 
Dviej� linij� pana�umas (angl. {\it similarity}  ) �vertinamas neneigiamu
sveikuoju skai�iu, gaunamu lyginant linij� ilgius ({\it d}  ) ir prad�ios
($\alpha_1$  ) bei galo ($\alpha_2$  ) kampus (�i�r. \label{fig:invarPozymiai} pav.).
Dviej� lyginam� linij� metrikos detal�s 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 {\it detal�mis}   visas turimas pir�to atspaudo detales saugomas "Minutiae"
strukt�roje.

Atlikite pir�t� atspaud� palyginimo patobulinim�. 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 atvirk��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�, i� ankstesn�s u�duoties
rastos bendros linij� pana�umo ta�k� sumos atmeskite pana�umo ta�kus t�
linij�, kuri� bent vienas arba 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.


Vertinama iki \textcolor{gold}{1.25 balo}.

\item Pir�t� atspaud� atpa�inimo konkursas.
Paruo�kite pir�t� atspaud� verifikacijos algoritm�, kuris apskai�iuot� duot� pir�t� atspaud� duomen� (pirshtai.info) pirshtai.roc fail�.
Skai�iavimams turite perduoti d�stytojui algoritmus paruo�tus tokiu b�du.

\begin{itemize}
\item J�s� vykdomasis "*.exe" arba java "*.jar" failas (Matlab, Python ir kitos programavimo terp�s neturi b�ti naudojamos) turi b�ti paleid�iamas komandine eilute, kurioje papildomai nurodomas vienas parametras: \href{http://www.mif.vu.lt/atpazinimas/finger/FVC2002_DB1_A.info}{FVC2002\_DB1\_A.info}.

Tarkime, jei j�s� programos vardas ManoPirshtai.jar, naudojimo pavyzdys b�t�

{\em java -Xmx1024m -jar ManoPirshtai.jar \href{http://www.mif.vu.lt/atpazinimas/finger/FVC2002_DB1_A.info}{FVC2002\_DB1\_A.info} }

\item J�s� programa turi kiekvien� fiksuot� pirshtai.info s�ra�o element� palyginti su pirshtai.info s�ra�o elementais �ra�ytais didesnio numerio eilut�se.
Gautus rezultatus �ra�yti � *.roc formato fail�. \href{http://www.mif.vu.lt/atpazinimas/finger/FVC2002_DB1_A.info}{FVC2002\_DB1\_A.info} pavyzdyje yra $800$ �ra��. Vadinasi paskai�iuoto pavyzd�io *.roc faile tur�s b�ti $800*759/2$ palyginim� �ra��.

\item Pilnai paruo�ta programa vykdymui kartu su program� pradiniais kodais
turi b�ti pateikta iki \textcolor{gold}{�. m.  gruod�io 15 d.} (imtinai).
\item Vertinama \textcolor{gold}{1} balo u� atitinkan�ius reikalavimus algoritmo pateikim�.

Papildomai, priklausomai nuo algoritmu gaut� rezultat�, skiriama \textcolor{gold}{iki penki�}
konkursini� egzamino bal�, kurie atskirai prisideda prie j�s� pratyb� ir teorijos bal�.
 \begin{figure}
\centering
\includegraphics[scale=0.75]{figures/fvc2002db1aRokai} 
  \caption{ FVC2002DB1A pir�t� duomen� baz�s palyginimo algoritm� kokyb�s DET kreiv�s.
	Skirtingomis spalvomis pa�ym�ti skirting� algoritm� DET kreiv�s.}
  \label{fig:fvc2002db1Rokai}
\end{figure}

\ref{fig:fvc2002db1Rokai} paveiksl�lis iliustruoja FVC2002DB1A pir�t� duomen� skirting� algoritm� palyginimo kreives.
Kuo kreiv� �emiau, tuo geresn� algoritmo kokyb�.
M�lyna vir�utin� kreiv� iliustruoja palyginimo algoritmo, kuris remiasi tik linij� pana�umais ir j� atiktimis, kokyb�.
Geltona kreiv� iliustruoja t� pat� algoritm�, kuris papildomai naudoja vaizdo registracijos kampo reik�m�.
Raudona kreiv� iliustruoja palyginimo algoritm�, kur atitikmenys ie�komi detali� centr� lygmenyje.
Tamsiai �alia kreiv� iliustruoja raudonos kreiv�s palyginimo algoritm�, kuriam papildomai pritaikyta pilna registracija pagal vaizd� registracijos pos�kio kamp� ir poslink�.
Paskutin� fuksin�s spalvos kreiv� gauta panaudojant profesionali� \href{http://www.neurotechnology.com}{Neurotechnologijos Megamatcher} pir�t� atspaud� po�ymi� i�skyrimo ir palyginimo algoritm�.
�i kreiv� gauta panaudojant programos versij� skirt� produkto �vertinimui (angl. {\em evaluation}).

J�s� pateikto algoritmo kokyb� bus laikoma tinkama, jei gauta DET kreiv� nevir�ys "geltonos" DET kreiv�s.
\end{itemize}
 
\end{enumerate}
