\section{Rainel�s atpa�inimas}
\begin{enumerate}\small{
\item \hyperlink{ivadas}{�vadas}
\item \hyperlink{privalumai}{Privalumai}
\item \hyperlink{trukumai}{Tr�kumai}
\item \hyperlink{praktiniaiTaikymai}{Praktiniai taikymai}
\item \hyperlink{rainelesAS}{Rainel�s atpa�inimo schema}
\item \hyperlink{akiesPirminisApdorojimas}{Rainel�s vaizdo pirminis apdorojimas}
\item \hyperlink{akiesSkenavimas}{Akies rainel�s duomen� skenavimas}
\item \hyperlink{vyzdzioLokalizavimas}{Vyzd�io lokalizavimas}
\item \hyperlink{duApskritimai}{Vyzd�io ir rainel�s kra�t� aproksimavimas dviems apskritimais}
\item \hyperlink{rbpi}{Binarini� po�ymi� i�skyrimas}
\item \hyperlink{rainSabl}{Rainel�s �ablonas}
\item \hyperlink{sablPalyg}{�ablon� palyginimas}
\item \hyperlink{praktRain}{Praktin� u�duotis}}
\end{enumerate}

\hypertarget{ivadas}{{\bf �vadas}}

Rainel� yra �iedo formos matoma akies dalis tarp vyzd�io ir
stiklak�nio ( �i�r. \ref{fig:akiesRainele} pav). Rainel�s vaizdai pasi�ymi turtinga tekst�ra.
Oftalmologas ( aki� lig� specialistas ) Frank Burch 1936 m.
suformulavo mint� apie aki� raineli� panaudojim�
asmens identifikavimui. Pereito am�iaus 8-ajame de�imtmetyje akies rainel�s
panaudojimo identifikacijai id�ja pasirod� James Bond seriale, ta�iau
prakti�kai ji dar nebuvo realizuota.1987 m. du oftalmologai Aran Safir ir Leonard
Flom u�patentavo� �i� id�j� ir 1989 m. jie papra�� John Daugman ( Harvardo
universiteto lektoriaus ) sukurti tinkant� kompiuteriui aki� raineli�
atpa�inimo algoritm�. Daugmano pradinis algoritmas apra�ytas \cite{bib:Daugman1993}
straipsnyje. �iuolaikin�s komercin�s raineli� atpa�inimo sistemos naudoja
�vairias originalaus Daugman algoritmo modifikacijas, ta�iau principin�
atpa�inimo schema nesikei�ia. Teises � patentus i�pirko Iridian Technologies \cite{bib:IridianTechnologies} kompanija ir s�kmingai vysto asmen� identifikavimo pagal akies
rainel� bizn�. 

\begin{figure}
\centering
\includegraphics[scale=0.67]{figures/image001} 
\caption{ �mogaus akies rainel�s spalvota nuotrauka}
 \label{fig:akiesRainele}
\end{figure}

\hypertarget{privalumai}{{\bf Privalumai}}

Akies rainel�s panaudojimas biometrikoje turi daug ger� savyvi�.
\begin{itemize}
 \item Rainel� gerai apsaugota nuo i�orinio
     poveikio labai skaidria membrana. Palyginimui pir�t� atspaudai nuolat
     kinta nuo ranka laikomos cigaret�s sukelt� mikro-nudeginim�, �sipjovim�
     peiliu, mechaninio poveikio dirbant rankomis.
 \item Rainel� i� esm�s yra plok��ia ir jos geometrija
     kei�iama tik dviem nepriklausomais raumenimis reguliuojan�iais vyzd�io
     skersmen�. Tai s�lygoja rainel�s pastovum� lyginant pavyzd�iui su trima�io
     veido projekcijomis.
 \item Rainel�s turi turting� unikali� tekst�r�,
     kuri, pana�iai kaip ir pir�t� atspaudai,� atsitiktinai suformuojama
     embriono vystymosi stadijoje. Net geneti�kai identi�ki dvyniai turi
     nepriklausomas raineli� tekst�ras. Palyginimui pasaulyje yra apie 10
     milijon� geneti�kai identi�k� dvyni�, kuri� DNR negali b�ti panaudota j�
     identifikacijai.
 \item Rainel�s skenavimo proced�ra analogi�ka
     paprastam fotografavimui atliekamam nuo 10 cm. iki keli� metr� atstumu. Tai
     �ymiai maloniau, nei pavyzd�iui liesti pir�t� atspaud� skenavimo
     mechanizm�, kur�, gal b�t, k� tik liet� kitas jums ne�inomos higienos
     kult�ros asmuo.
 \item Yra publikacij� teigian�i�, kad apie 200
     ta�keli� akies rainel�s skersmens vaizdas yra �ymiai informatyvesnis nei
     pir�t� atspaud� vaizdas.
 \item �iuo metu komercinis John Daugman IrisCode
     algoritmas pasi�ymi unikaliu FAR ( {\it angl. False Acceptance Rate}  )
     rodikliu geresniu nei $10^{-11}$. Atlikus daugiau kaip 200 milijard�
     palyginim� naudojant realius Jungtini� Arab� Emirat� imigracijos kontrol�s
     sistemoje sukauptus duomenis \cite{bib:Daugmantechreport635} nebuvo nei vieno �false
     acceptance� atvejo.
 \item Nors ir egzistuoja medicinin�s ir technin�s
     proced�ros dalinai kei�ian�ios rain�s spalvas ir geometrij�, tekst�ra i�
     esm�s lieka stabili de�imtme�iais. Yra pavyzd�i� s�kmingos raineli�
     identifikacijos 30 met� laikotarpiu.
\end{itemize}

\hypertarget{trukumai}{{\bf Tr�kumai}}

\begin{itemize}
 \item Raineli� skenavimas yra santykinai jauna
     technologija ir negali lygintis su analogi�komis pir�t� atspaud� duomen�
     saugyklomis.
 \item Identifikuoti rainel� labai keblu didesniu
     nei keli metrai atstumu ir tuo atveju, kai identifikuojamas asmuo
     nekooperuoja su sistema nukreipdamas galv� nuo kameros.
 \item Kaip ir kitos biometrin�s sistemos raineli� biometrin�
     identifikacijos sistema jautri blogos kokyb�s vaizdams.
 \item Kaip ir kit� biometrini� identifikavimo sistem�
     atveju, prie� raineli� duomen� bazi� kaupim� pasisako kovos u� asmen�
     teises organizacijos.
 \item Skirtingai nuo pir�t� atspaud�, kol kas
     nemokama i�gauti raineli� vaizd� kopijas paliktas nusikaltim� vietose.
\end{itemize}

\hypertarget{praktiniaiTaikymai}{{\bf Praktiniai taikymai}}

Tarptautin� civili� skryd�i� organizacija
\cite{bib:ICAO} akies raineles, kartu su pir�t� atspaudais ir veidais, pripa�ino ir
standartizavo ateities pas� panaudojime. Olandijos Schiphol aerouoste naudojama
imigracijos tarnyboje nuo 2001 met� \cite{bib:Schiphol}. Jungtini� Arab� Emirat� visuose
17 oro, sausumos ir j�ros pasienio kontrol�s punktuose naudojama akies rainel�s
atpa�inimo proced�ra taip pat nuo 2001 met� \cite{bib:UAE}. \cite{bib:UKIRIS} Anglijoje
funkcionuoja IRIS � �Iris Recognition Immigration System�. Keletas Kanados
aerouost� taip pat naudoja rainel�s atpa�inim� skryd�i� saugumo kontrol�s
tikslais. 

\hypertarget{rainelesAS}{{\bf Rainel�s atpa�inimo schema}}

 
Bendra rainel�s atpa�inimo schema nesiskiria
nuo �prastin�s vaizd� atpa�inimo schemos. \ref{fig:akiesRainelesAS}
paveiksl�lis iliustruoja tipinius akies rainel�s atpa�inimo etapus.

\begin{figure}
\centering
\includegraphics{figures/image003} 
\caption{ �mogaus akies rainel�s atpa�inimo etapai}
 \label{fig:akiesRainelesAS}
\end{figure}

Trumpai aptarsime kiekvien� rainel�s atpa�inimo etap� atskirai. 

\hypertarget{akiesSkenavimas}{{\bf Akies rainel�s duomen� skenavimas}}

Akies rainel�s duomen� skenavimas �skaitmenina
rainel�s analogin� ( real� ) vaizd�. Duomen� atpa�inimui pateikim� skaitmenine
forma s�lygoja �iuolaikini� kompiuteri� architekt�ra.� Kadangi spalvin�
raineli� informacija ma�iau atspari laikui ir medicinin�ms 

Priemon�ms, spalvin� raineli� informacija �iuo
metu komercin�se atpa�inimo sistemose nenaudojama. \ref{fig:akiesRainele} pav. pateiktas vienas
nespalvotos rainel�s nuotraukos pavyzdys. Atkreipkite d�mes� � ry�ki� balt�
d�m� vyzd�io srityje ( 23 val. kryptimi ). Tokios d�m�s kaip taisykl� matomos
skaitmenin�se raineli� nuotraukose ir gaunasi d�l specifinio ap�vietimo
�altinio i�ry�kinan�io infraraudon�sias elektromagnetines vaizdo bangas. Kitas skenavimo
b�do s�lygotas defektas yra taip vadinamas �interlacing� \cite{bib:Interlacing}, kuris
pasirei�kia lygini� ir nelygini� vaizdo eilu�i� pasislinkimu, kuris atsiranda
d�l skenavimo pirma lygini�, o po to nelygini� vaizdo eilu�i�. 

 \begin{figure}
\centering
\includegraphics{figures/image004} 
\caption{ NIST ICE 2005
raineli� duomen� baz�s 242116.tiff failo rainel�s vaizdas. }
 \label{fig:akiesRainele}
\end{figure}

\hypertarget{akiesPirminisApdorojimas}{{\bf Rainel�s vaizdo pirminis apdorojimas}}

Pirminis rainel�s vaizdo apdorojimas, kaip ir kitais vaizd� atpa�inimo
atvejais, yra ma�iausiai standartizuotas. Mes naudodami pirmin� vaizdo
apdorojim� spr�sime tris problemas. 
\begin{enumerate}
  \item Eliminuosime vaizdo
      kokyb�s pablog�jim� s�lygot� lygini�/nelygini� eilu�i� skenavimo ypatumu (vadinamu �interlacing� efektu).
  \item Pa�alinsime ap�vietimo �altinio s�lygotus ry�kius at�vaitus.
  \item Apskai�iuosime kaupiam�j� vaizd� (angl. {\it Integral image}), 
	kuris bus naudingas lokalizuojant vyzd� vaizde.
\end{enumerate}

 
Egzistuoja daug ir gana sud�ting� �interlacing�
efekto sukelt� vaizdo i�kraipymo problemos sprendim�. 
�ie vaizdo i�kraipymai atsiranda d�l to, kad dalis skeneri� pirma skenuoja lygines ($0,2, \dots$),
o po to nelygines ($1,3, \dots$) eilutes. D�l to atsiranda skenavimo laik� skirtumai ir akis
gana da�nai sp�ja kiek pakeisti gretim� eilu�i� skenavimo pozicijas. 
Vienas b�d� suma�inti �io efekto s�lygotus vaizd� i�kraipymus yra
 eliminuoti kas antr� (pavyzd�iui nelygin�) vaizdo eilut�. Kadangi mums
svarbu i�saugoti apskritimin� rainel�s simetrij� mes eliminuosime ne tik
nelygines vaizdo eilutes bet ir nelyginius vaizdo stulpelius. Kadangi rainel�s
nuotraukos kokyb�s b�na auk�tos rezoliucijos, suma�intas du kartus im�i�
skai�ius horizontalia ir vertikalia kryptimis i�saugos gana detali� informacij�
apie rainel�s tekst�r� ir tuo pa�iu apie $4$ kartus paspartins v�lesnius
skai�iavimus atliekamus su vaizdo ta�keli� matrica. Atlikus �i� parast� �deinterlacing�
proced�r� gausime \ref{fig:rainelesDeinterlacing} paveiksl�lyje pavaizduot� rainel�s vaizd�.

 \begin{figure}
\centering
\includegraphics{figures/image005} 
\caption{ 242116
vaizdas, kuriame eliminuotas lygini�/nelygini� eilu�i� triuk�mas}
 \label{fig:rainelesDeinterlacing}
\end{figure} 

Pradiniame vaizdelyje �interlacing� i�kraipymai
lengvai pastebimi balto at�vaito bei atskir� blakstien� srityje. \ref{fig:rainelesDeinterlacing} pav. vaizdo
kokyb� �ia prasme yra geresn�. Suma�intos rezoliucijos vaizde rainel�s tekst�ra
i�lieka pakankamai ai�ki, kad remiantis ja b�t� galima identifikuoti skirtingas
raineles. 
 

Baltus ap�vietimo at�vaitus pa�alinsime tokiu
b�du. Pirma pasirinksime �viesumo slenkst� {\it trshld}  (pvz. {\it trshld}  =
220 ). Tuomet surandame jungi� ta�k� $(x,y)$ srit� vaizde, kurioms vaizdo
reik�m�s $img(x,y) > trshld$ . Fiksuojame koki� nors toki� ta�k� srit�
ir u�pildome jos reik�mes srities kra�to vaizdo reik�mi� vidurkiu. Atlik� �ias
proced�ras gauname \ref{fig:rainelesDeinterlacing} pav.� rainel�s vaizd�. 

 \begin{figure}
\centering
\includegraphics{figures/image006} 
\caption{ Rainel�s vaizdas pa�alinus didelio intensyvumo sritis (ap�vietimo at�vaitus). }
 \label{fig:rainelesBeAtsvaitu}
\end{figure} 

 
Kaupiamasis vaizdas $IImg(x,y)$ (angl. {\em Integral Image} )
gaunamas susumuojant visas $img(i,j)$ reik�mes, kur $(i,j)$ koordinat�s tenkina
s�lygas $i \le x$ ir $j \le y$. �io vaizdo nevizualizuosime, nes kaupiamasis
vaizdas skirtas ne vizualizacijai, o yra pagalbin� priemon� greit� vaizdo
vidurki� bet kokiame sta�iakampyje apskai�iavimui kuo mes v�liau ir
pasinaudosime. Pla�iau apie kaupiam�j� vaizd� galite paskaityti \cite{bib:integralImage}
�altinyje. 

\hypertarget{vyzdzioLokalizavimas}{{\bf Vyzd�io lokalizavimas}}

Objekto lokalizacija yra sudedamoji daugelio
vaizd� atpa�inimo algoritm� dalis. Lokalizuojant kok� nors objekt� reikia
surasti srit� ar sritis vaizde kuriose yra mus dominantis objektas nekreipiant
d�mesio � individualias objekto detales pagal kurias v�liau yra
identifikuojamas konkretus objektas. Java programavimo terminais lokalizuojant
reikia atpa�inti Java klas�s tip�, o atpa�inimas ekvivalentus kokio nors klas�s
konkretaus egzemplioriaus identifikavimui. Rainel�s atveju patogiau prad�ioje
lokalizuoti ne vis� rainel�, o tik srit� vaizde, kuri atitinka vyzd�.
U�pild�ius baltus at�vaitus, vyzdys pasi�ymi ma�o intensyvumo $img(x,y)$
reik�m�mis. Ta�iau blakstienos, ypa� mergin�, kurios specialiai ry�kina jas
juodu tu�u, taip pat pasi�ymi ma�omis intensyvumo reik�m�mis. Kadangi
blakstienos yra nedidelio storio vidurkintame vaizde blakstienas atitinkan�ios
reik�m�s vidurkinsis su gretimomis didesn�mis veido spalvos reik�m�mis, o
vyzd�io vidurio ta�kai i�liks tokie pat tams�s. Kad greitai atlikti vidurkinimo
operacij� patogu naudoti kaupiam�j� vaizd�. Sta�iakampyje, kurio vir��n�s
ta�kuose $(a-1,b-1)$ ir $(c,d)$, $( a<c, b<d)$ esan�i� vaizdo reik�mi� $img(x,y)$
suma yra lygi 
$$ 
IImg(c,d) - IImg(a,d) - IImg(c,b) + IImg(a,b).
$$
Vadinasi �io sta�iakampio vidutin� vaizdo
reik�m� bus randama keletu sud�ties/atimties bei daugybos/dalybos veiksmais: 
$$
\overline{img}_{(c,d)\times(a-1,b-1)} = \frac{IImg(c,d)
- IImg(a,d) - �IImg(c,b) + IImg(a,b)}{(c-a)(d-b)}.
$$
Kad vidurkintas vaizdas b�t� labiau
lokalizuotas mes vidurkiname du vidurkintus vaizdus, kuri� sta�iakampiai
lokalizuoti arba horizontalia arba vertikalia kryptimi. Galutin� vidurkinto
vaizdo reik�m� ta�ke $(x,y)$ apskai�iuojama formule 
$$ 
\overline{img}(x,y) = 0.5 *(\overline{img}_{(x+1,y+h)\times(x-1-1, y-h-1)}
 + \overline{img}_{(x+h, y+1)\times(x-h-1, y-1-1)}). 
$$
�ia $h$  yra vidurkinimo sta�iakampio did�iosios kra�tin�s pus�. 

\ref{fig:raineleVidurkintaKvadratais} pav. iliustruoja gaunam� vidurkinimo rezultat� ( $h = 10$ ).
Alternatyvus b�das gauti vidurkint� rainel�s vaizd� yra pritaikyti simetrin� eksponentin� filtr� apra�yt� vaizd� vidurkinimo skyriuje.

 \begin{figure}
\centering
\includegraphics{figures/image007} 
\caption{ 20x20 kvadratuose vidurkintas rainel�s vaizdas}
 \label{fig:raineleVidurkintaKvadratais}
\end{figure} 

Detektuojant vyzd� vaizde yra ie�komas globalus vidurkinto vaizdo minimumas 
$$ 
\mbox{argMin}( \overline{img}(x,y) ) = (x_{min}, y_{min}) 
$$
ir surandama jungi ta�k� sritis, kurios elementai $(x,y)$ tenkina s�lyg� 
$$\overline{img}(x,y) \ge� \overline{img}(x_{min},y_{min}) + \delta. $$
Slenks�io reik�m� $\delta$ parenkama
eksperimentiniu b�du ir $256$ pilkumo lygi� vaizde tipin� reik�m�s yra $\delta = 8$,
$16$ arba $32$. 

\ref{fig:lokalizuotasVyzdys} pav. iliustruoja gaunamo vyzd�io
lokalizacijos rezultat�. Rausvais ta�kais pa�ym�tas i�skirtos jungios vyzd�io
srities kra�tas. �iuo atveju delta reik�m� buvo $32$. 

 \begin{figure}
\centering
\includegraphics{figures/image008} 
\caption{ Lokalizuoto vyzd�io vaizdas. Rausvi ta�kai �ymi vyzd�io srities kra�tinius ta�kus, raudonas
- vyzd�io srities ta�k� koordina�i� aritmetin� vidurk�}
 \label{fig:lokalizuotasVyzdys}
\end{figure} 

  
Suradus akies vyzd�io srit� randamas �ios
srities ta�k� koordina�i� aritmetinis vidurkis. \ref{fig:lokalizuotasVyzdys} pav. ta�kas su aritmetinio vidurkio
koordinat�mis pa�ym�tas ma�u raudonu kry�iuku. Taip pat apytiksliai �vertinamas
vyzd�io spindulys, kurio reik�m� randama apskai�iuojant atstum� vidurk� tarp i�orinio
vyzd�io kont�ro ta�k� ir rasto vyzd�io centro. \ref{fig:lokalizuotasVyzdys} pav. pavaizduotos akies atveju
gaunama vyzd�io spindulio reik�m� yra apytiksliai lygi $28$ ta�keliams. 

\hypertarget{duApskritimai}{{\bf Vyzd�io ir rainel�s kra�t� aproksimavimas dviems apskritimais}}

 
Seka�iame etape yra patikslinamas vyzd�io
centras bei jo kra�t� aproksimuojantis apskritimas ir surandamas analogi�kas
apskritimas rainel�s i�oriniam kra�tui. Kad i�ry�kinti kra�tus da�nai
naudojamas diferencijavimas. Vieno kintamojo funkcijos pirmosios eil�s
i�vestin� greito reik�mi� kilimo srityje tur�s lokal� maksimum�, o greito
kritimo srityje � minimum�. Antrosios eil�s i�vestin� ir maksimumo ir minimumo
ta�k� aplinkose kirs nulin� reik�m�. Da�niausiai tokie ta�kai ir yra naudojami detektuoti
kra�tams. M�s� atveju patogu naudoti jau detektuot� vyzd�io centr� nustatyti
kryp�iai kuria yra skai�iuojama antrosios eil�s i�vestin�. Tiksliau antrosios
eil�s i�vestin� yra aproksimuojama antrosios eil�s skirtumais spindulio i�vesto
i� vyzd�io centro kryptimi. Tokiu b�du vaizdo $img(x,y)$ antrosios eil�s
diferencialas spindulio kryptimi randamas pagal formul� 
$$ 
\frac{d^2 img(x,y)}{dr^2} = \frac{img( x + dr \cos(\phi),
y+ dr \sin(\phi) ) - 2 img( x,y ) + img( x - dr \cos(\phi), y - dr \sin(\phi) )}{(dr)^2}. 
$$
�ia $(r, \phi )$ yra ta�ko $(x,y)$ polin�s
koordinat�s randamos i� lyg�i� 
\begin{eqnarray*}
x &=& x_o + r \cos(\phi),\\
y &=& y_o + r \sin(\phi), 
\end{eqnarray*}
$(x_o,y_o)$ detektuoto vyzd�io centro
koordinat�s, $dr$ � diferencialo �ingsnis, kurio praktin� reik�m� gali b�ti
apie $5$ ta�kelius. �sta�ius konkre�ias reik�mes daugeliu atvej� gausime nesveikaskaites
vaizdo koordinates. Tod�l tenka vaizdo reik�mes bitiesi�kai interpoliuoti
panaudojant $4$-ias vaizdo reik�mes artimiausiose sveikaskait�se koordinat�se
(pla�iau �i�r. \cite{bib:BilinearInterpolation}). Kad neskai�iuoti be reikalo stipriai
nutolusiuose nuo vyzd�io centro vaizdo ta�kuose diferencial� galima apsiriboti
maksimalaus rainel�s spindulio skrituliu. Kadangi da�nai � rainel�s srit�
patenka apatinis ir vir�utinis akies vokas taip pat tikslingas apsiriboti tik
$45$ laipsni� sektoriais i�einan�iais i� vyzd�io centro, kuri� simetrijos a�is
yra lygiagreti horizonto linijai. \ref{fig:antriDif} pav. iliustruoja apskai�iuotas nurodytoje
srityje antrosios eil�s diferencialo reik�mes. Kuo spalva raudonesn� tuo
didesn� diferencialo teigiama reik�m� pa�ym�tame ta�ke, kuo spalva m�lynesn�
tuo reik�m� didesn� neigiama, reik�m�s artimos nuliui arba kurios neskai�iuotos
nuspalvintos juodai. Balta spalva �ymi per�jimo i� m�lynos spalvos � raudon�
ta�kus ( t.y. antrosios eil�s diferencialo spindulio kryptimi nulio kirtimo
ta�kus, o geltona � analogi�kus ta�kus kai spalva �i�rint i� kair�s � de�in� i�
raudonos pereina � m�lyn�. Kad greitai ir tiksliai �vertinti apskritim�
ribojan�i� vyzd�io ir rainel�s kra�tus sudaroma nulio kirtimo ta�k� nuotoli�
iki vyzd�io centro histograma. Histograma skai�iuojama atskirai kiekvienam
jungiam nulio kirtim� kont�rui. Gautas histogramas taip pat galima kiek
pavidurkinti, kad j� grafikai b�t� tolydesni. 

 \begin{figure}
\centering
\includegraphics{figures/image009} 
  \caption{ 
Antrosios eil�s diferencialai apskai�iuoti riboto apskritimo ilgio 45 laipsni� sektori�,
i�einan�i� i� vyzd�io centro, srityse}
 \label{fig:antriDif}
\end{figure} 


\ref{fig:jkHistogr} pav. iliustruoja gaunamas histogramas. Dvi
beveik susiliejan�ios histogramos turi maksimumus atitinkan�ius argumento
reik�mes $55$ ir $56$. �ios histogramos atitinka kair�j� ir de�in�j� vyzd�io
kont�r�, o maksimumai atitinka vyzd� aproksimuojan�io apskritimo spindul�.
Prisiminkime, kad pradin� �vertinta apskritimo reik�m� buvo lygi $28$. Beveik
dvigubas spindulio padid�jimas gavosi tod�l, kad pereidami prie polini�
koordina�i� mes pasmulkinome du kartus skai�iuojam� ta�k� mastel� kad gauti
tikslesnes vyzd�io ir rainel�s kra�tus ribojan�i� apskritim� reik�mes. Kit�
dviej� reik�ming� histogram� grafik� maksimumai yra de�iniau ir j� reik�m�s yra
$130$ ir $136$. �ios dvi histogramos atitinka rainel�s de�inio ir kairiojo i�orinio
kra�to kont�rus, o j� maksimumai � rainel�s kra�tus aproksimuojan�i� apskritim�
spindulius. �iuo atveju gaut� spinduli� reik�m�s skiriasi gana daug, tiksliau
$136 � 130 = 6$ ta�keliais. To prie�astis yra ta, kad vyzd�io centras netiksliai
sutampa su rainel� ribojan�io apskritimo centru. Tod�l papildomai apjungiame
atskirai ta�kus sudaran�ius du kont�rus ( kair�j� ir de�in�j� ), kurie riboja vyzd�,
bei ta�kai analogi�ka rainel�s kra�t� kont�r� ta�k� aib�. �ioms dvejoms ta�k�
aib�ms surandami du apskritimai minimizuojantys atstumus kont�r� ta�k� iki
apskritim�. � �i� apskritim� apskai�iavimo detales nesigilinsime, pa�ym�sime
tik kad gaunam� apskritim� centrai ir spinduliai ir yra galutinis segmentacijos/lokalizacijos
rezultatas. 


  \begin{figure}
\centering
\includegraphics{figures/image010} 
  \caption{ 
 Jungi� kont�r� ta�k� atstum� iki vyzd�io centro histogramos
}
 \label{fig:jkHistogr}
\end{figure} 


\ref{fig:gautiRainApskrit} pav. iliustruoja galutin� rainel�s
lokalizacijos algoritmo darbo rezultat�. �aliasis apskritimas ir jo centro
ta�kas aproksimuoja akies vyzd� ribojant� kont�r�, kuris sutampa su rainel�s
vidiniu kont�ru, o geltonai nuspalvintas apskritimas ir centro ta�kas �ymi
rainel�s i�orinio kra�to kont�r� aproksimuojant� apskritim�. Originalus Daugman
ir kiti algoritmai papildomai dar detektuoja apatin� ir vir�utin� vok� aproksimuojan�ius
apskritimus. Kadangi �iems apskritimams i�skirti netinka histograma sudaryta i�
kont�ro ta�k� atstum� iki vyzd�io centro, �iuo atveju reik�t� taikyti
apskritimin� Hough transformacij� \cite{bib:CircularHoughTransform}. Hough
transformacijos sud�tingumas yra �ymiai sud�tingesnis, nes ie�komas ne vienas
parametras � apskritimo spindulys, bet dar papildomi du � centro ta�ko
koordinat�s, tod�l mes savo algoritme jo nenaudojame. B�siu d�kingas, jei kas
pasi�lysite greitus ir patikimus algoritmus aki� vok� kra�tams surasti. �ia
apra�ytas algoritmas yra realizuotas Java kalba ir vienam 3 pav. pateiktos
rezoliucijos vaizde lokalizuoja rainel� vidutini�kai per $0.25$ sek. ( $2.8$ GHZ PC). 


  \begin{figure}
\centering
\includegraphics{figures/image011} 
  \caption{ 
Vyzd� ir akies rainel�s i�orin� kont�r� aproksimuojantys apskritimai
}
 \label{fig:gautiRainApskrit}
\end{figure} 

\hypertarget{rbpi}{{\bf Binarini� po�ymi� i�skyrimas}}

 
Atlikus segmentacij� atsiranda galimyb�
i�skirti po�ymius. Apskai�iuodami po�ymius remsim�s Daugman tradicija, t.y.
rainel�s po�ymiai bus binarini� skai�i�, t.y. $0/1$, matrica. Tokia binarini�
po�ymi� patogi palyginimui nes galima apjungti $0/1$ grup�mis, pvz. po $16$
pozicij� ir lyginimo metu operuoti su tomis grup�mis, kas �ymiai pagreitina
skai�iavimus. Originaliame Daugmas darbe yra naudojami Gaboro filtrai \cite{bib:GaborFilter}.
Mes naudosime paprastesnius filtrus, kuri� esm� i�lieka tapati � filtr� svoriai
parenkami taip, kad jie trivialius signalus, pvz. konstant� atvaizduot� � nul�
ir konkreti po�ymio reik�m� parenkama pagal filtravimo rezultato �enkl�. 

Prad�ioje reikia nuspr�sti kok� signal�
filtruosime. Atlik� rainel�s segmentacij� gauname du apskritimus, kuri� ma�asis
aproksimuoja kont�r� ribojant� vyzd� ir vidin� rainel�s kra�t�, o didysis aproksimuoja
i�orin� rainel�s kont�r�. Prad�ioje tarkime paprastumo d�lei, kad �i� dviej�
apskritim� centrai sutampa. Tuomet i�skirta rainel� sudaro �ied�, ribojam� $R_{pupil}$
ir $R_{iris}$  spinduliais. Daugman schemoje po�ymiams i�skirti yra pereinama
prie vaizdo polini� koordina�i� sistemos, kurios centras sutampa su i�skirt�
apskritim� centru, o reik�m�s sudaro sta�iakamp� ta�keli� matric�, gaunam�
kei�iant polinio kampo ir spindulio reik�mes. Jei (ox,oy) pa�ym�ti rasto
rainel�s centro koordinates, tai gausime tokias formules: 
\begin{eqnarray*} 
img_{n,m} &=& img( x_o + r_n\cos(\phi_m), y_o + r_n\sin(\phi_m))\\
\phi_m &=& \frac{2\pi m }{ M }, \ \ m = 0, 1, \dots, M-1,\\
r_n &=& R_{pupil} + \frac{( R_{iris}-R_{pupil})*(n+0.5)}{N}, \ \ n = 0, 1, \dots, N-1.
\end{eqnarray*}  
Prakti�kai taikant �ias formules tenka spr�sti
vaizdo reik�m�s $ img(x,y)$  apskai�iavimo problem�, nes nuskaitytas
pilkumo lygmen� rainel�s vaizdas yra �inomas tik sveikaskait�se koordinat�se, t.y.
ta�kuose $(x,y)=(i,j)$, kur $i$  ir $j$  yra sveikieji skai�iai. M�su
atveju $x = x_o+r_n \cos(\phi_m)$ ir $y = y_o + r_n \sin(\phi_m)$ yra real�s skai�iai
kurie tik retais atvejais bus sveikieji. �i problema sprend�iama naudojant bitiesin�
interpoliacij�, kurios esm� yra tokia. 
\begin{enumerate}
 \item Ta�kui $(x,y)$ surandami artimiausi 4-i ta�kai
     su sveikaskait�mis koordinat�mis ( �i�r. \ref{fig:artimBit} pav.). Naudojant Java
     programavimo operatorius $(i,j)$ ta�ko koordinat�s bus randamos taip:
\begin{eqnarray*} 
\mbox{int } i &=& \mbox{(int) } \ x;\\
\mbox{int } j &=& \mbox{(int) } \ y;	
\end{eqnarray*} 
 \item Vaizdo reik�m� ta�ke $(x,y)$ apskai�iuojama formule
\begin{eqnarray}
img(x,y)� &=&� img[i,j]*(1-dx)*(1-dy) + img[i+1,j]*dx*(1-dy) + \label{bitinterp}\\
 & & img[i,j+1]*(1-dx)*dy + img[i+1,j+1]*dx*dy. \nonumber
\end{eqnarray}
�ia $dx = x - i$, $dy = y - j$. Nesunku pasteb�ti, kad fiksuotam $x$ arba $y$ i�rai�ka $img(x,y)$ yra
tiesin� likusio ( $y$ arba $x$ ) kintamojo at�vilgiu. Jei $x$ ir $y$ yra sveikaskait�s,
t.y. $x = i$ ir $y = j$, tai formule apskai�iuota reik�m� $img(x,y)$ sutampa su
vaizdo reik�me $img[i,j]$. D�l �i� dviej� savybi� formul� ir yra vadinama {\it bitiesine
interpoliacija} . 
\end{enumerate}
  \begin{figure}
\centering
\includegraphics{figures/image013} 
  \caption{ 
Ta�ko $(x,y)$ artimiausios sveikaskait�s koordinat�s naudojamos bitiesinei interpoliacijai
}
 \label{fig:artimBit}
\end{figure} 
Modifikuosime rainel�s reik�mi� apskai�iavimo
i�rai�kas, kad jos tikt� bendru atveju kai ma�ojo ir didesniojo apskritimo
centrai yra skirtingi. Formuli� modifikacijos id�ja yra gana paprasta � formul�se
reikia pakeisti fiksuot� centr� $(x_o,y_o)$ �kintamu� centru $(x_o(r),y_o(r))$ taip,
kad kintant spinduliui r nuo minimalios reik�m�s $r = R_{pupil}$ iki maksimalios $R_{iris}$
�centro� koordina�i� i�rai�ka $(x_o(r),y_o(r))$ kist� tiesi�kai nuo $({x_o}_{pupil},{y_o}_{pupil})$
(vyzd�io centro ta�kas) iki $({x_o}_{iris},{y_o}_{iris})$ (rainel�s centro koordinat�s). Atlikus
�i� modifikacij� gauname tokias formules: 
\begin{eqnarray*}
iris_{n,m} &=& img( x_o(r_n) + r_n \cos(\phi_m), y_o(r_n) + r_n \sin(\phi_m)), \\
\phi_m &=& 2\pi n/M, \ \ m=0,1,\dots, M-1,\\
r_n &=& R_{pupil} + (R_{iris}-R_{pupil})(n+0.5)/N, \ \ n=0,1, \dots, N-1, \\
x_o(r) &=& {x_o}_{pupil} + (r-R_{pupil})/(R_{iris}-R_{pupil})({x_o}_{iris}-{x_o}_{pupil}),\\
y_o(r) &=& {y_o}_{pupil} + (r-R_{pupil})/(R_{iris}-R_{pupil})({y_o}_{iris}-{y_o}_{pupil}).
\end{eqnarray*}

\ref{fig:rainGardTask} pav. m�lynais ta�keliais pavaizduoti ta�kai
$( x_{n,m}, y_{n,m} )$, kuriuose taikant bitiesin� interpoliacij� apskai�iuojamos
$iris_{n,m}$ reik�m�s

   \begin{figure}
\centering
\includegraphics{figures/image015} 
  \caption{ 
Rainel�s $iris_(n,m)$ gardel�s ta�kai,
kuriuose, taikant bitiesin� interpoliacij�, apskai�iuojamos rainel�s pilkumo
lygmen� reik�m�s
}
 \label{fig:rainGardTask}
\end{figure} 

Sekantis \ref{fig:rainPilkLygVaizd} paveiksl�lis iliustruoja gaut� bitiesine
interpoliacija pilkumo lygmen� ta�keli� matric�. Kaip ir anks�iau, iliustracijai
gauti naudojamas NIST ICE 2005 \cite{bib:NISTICE2005} raineli� duomen� baz�s 242116.tiff
failo rainel�s vaizdas, \ref{fig:rainGardTask} pav. atveju $N = 8$, $M = 64$, \ref{fig:rainPilkLygVaizd} pav. � $N = 64$, $M =
512$, juoda \ref{fig:rainGardTask} pav. linija �ymi atkarp� ties kuria buvo �perkirptas� rainel�s
�iedas pavaizduojant j� \ref{fig:rainPilkLygVaizd} pav. pilkumo lygmen� ta�keliais, apatiniai \ref{fig:rainPilkLygVaizd} pav.
ta�kai atitinka rainel�s vidinio apskritimo ta�kus. 

 \begin{figure}
\centering
\includegraphics{figures/image016} 
  \caption{ 
 Rainel�s pilkumo lygmen� $64 x 512$ ta�keli� vaizdas
}
 \label{fig:rainPilkLygVaizd}
\end{figure} 
 

Turint sta�iakamp� rainel�s pilkumo lygmen�
matric� galima prad�ti i�skyrin�ti binarinius po�ymius. Po�ymiams skai�iuoti
pasirenkamas koks nors filtras, juo filtruojamas rainel�s vaizdas ir pagal
filtravimo rezultato �enklo reik�m� priskiriama galutin� binarinio po�ymio
reik�m�. Daugmanas filtravimui naudojo dvimat� Gaboro filtr� \cite{bib:GaborFilter}.
Dvima�iai Gaboro filtrai horizontalia ir vertikalia kryptimi turi po du laisvus
parametrus, kuri� konkre�ios reik�m�s literat�roje nenurodomos, tod�l
prakti�kai ne�manoma atkartoti autori� gaunam� raineli� atpa�inimo rezultat�
gaunam� taikant �� filtravim�. Tod�l mes naudosime paprastesnius vienma�ius
filtrus ir nurodysime konkre�ias filtr� koeficient� reik�mes. Kadangi binariniai
po�ymiai gaunami remiantis filtravimo rezultato �enklu, ai�ku, kad filtro
koeficient� suma turi b�ti lygi nuliui. Jei pavyzd�iui vidutin� filtro
koeficient� reik�m� b�t� teigiama, tai filtruojant rainel�s vaizdo reik�mes gautume
dominuojan�i� teigiam� filtravimo rezultato reik�m�, nes visos rainel�s
reik�m�s yra neneigiamos ir kinta intervale $[0,255]$. Papras�iausias vienmatis netrivialus
filtras, kurio koeficient� suma lygi nuliui, yra 
$$ 
f_m = \left\{ \begin{array}{ll}
-1, & m=0,\\
1, & m=1,\\
0, & m\neq0,1.
\end{array}\right.
$$
Pritaikius �it� filtr� vienma�iam signalui $ u_n $
gausime tok� filtravimo rezultat�:
$$(u * f )_m = u_m - u_{m-1}, $$
kuris yra signalo $u$  i�vestin�s aproksimacija.
Atlikus po�ymio binarizacij�, pozicijoje $m$  ra�ytume $1$, jei $u_m$ didesnis
u� $u_{m-1}$,  ir $0$ prie�ingu atveju, kai� $u_m$ ma�esnis arba lygus $u_{m-1}$.
Prakti�kai �sitikinta, kad daugeliu atvej� geriau analizuoti ne funkcij� arba
jos i�vestin�, bet jos antrosios eil�s i�vestin�. Antrosios eil�s i�vestin�s skirtuminis
analogas apibr��iamas filtru 
$$ 
f_m = \left\{ \begin{array}{ll}
1, & m=1,\\
-2, & m=0,\\
1, & m=-1,\\
0, & m\neq-1,0,1.
\end{array}\right.
$$
Pritaikius �� filtr� vienma�iam signalui
gauname tok� rezultat�: 
$$
(u * f )_m = u_{m+1}-2u_m + u_{m-1}.
$$
�iuo atveju binarinis po�ymis ta�ke $m$
b�t� apibr��iamas i�rai�ka 
$$ 
bin_{m} = \left\{ \begin{array}{ll}
1, & \mbox{kai } \; \Delta u_m = u_{m+1}-2u_m+u_{m-1} \ge 0,\\
0, & \mbox{kai } \; \Delta u_m < 0.
\end{array}\right.
$$
Rainel�s atveju turime dvimat� signal� $iris(n,m)$.
Skai�iuoti signalo poky�ius spindulio kryptimi gana rizikinga, nes rainel�s
vidinis ir ypa� i�orinis kont�ras neturi ai�kiai apibr��tos ribos. Tod�l
spindulio (indekso $n$ ) reik�m� $r_n$ yra fiksuojama ir skai�iuojami
poky�iai kampo ( indekso $m$ ) kitimo at�vilgiu. Tokiu b�du gauname binarini�
po�ymi� matric� 
$$ 
bin_{n,m} = \left\{ \begin{array}{ll}
1, & \mbox{kai } \; \mbox{iris}_{n,m+1}-2\mbox{iris}_{n,m}+\mbox{iris}_{n,m-1} \ge 0,\\
-1, & \mbox{kai } \; \mbox{iris}_{n,m+1}-2\mbox{iris}_{n,m}+\mbox{iris}_{n,m-1} < 0,\\
& n = 0, 1, \dots, N-1, \; m = 0, 1, \dots, M-1.
\end{array}\right.
$$
Taip skai�iuojami po�ymiai yra gana nestabil�s
atsitiktiniam triuk�mui. \ref{fig:rainPozDif2} pav. pavaizduota $32 x 256$ binarini� po�ymi� matrica 
$bin_{n,m}$ apskai�iuota 242116.tiff paveiksliukui imant $32$ fiksuotas $r_n$ $( N
= 32 )$ ir $256 \;\;  \phi_m $ ( $M = 256$ ) reik�mes. �ali ta�keliai �ymi reik�mes $bin_{n,m} 
= 0$, o raudoni ta�kus $bin_{n,m}  = 1$. I� paveiksl�lio matyti, kad dviej�
autenti�k� raineli� binarini� po�ymi� matricos gali stipriai skirtis d�l
smulkaus mastelio. 

    \begin{figure}
\centering
\includegraphics{figures/image023} 
  \caption{ 
 242116.tiff failo rainel�s binariniai
po�ymiai skai�iuojami pagal rainel�s antrosios eil�s i�vestin�s skirtuminio
analogo skai�iuojamo kampo kryptimi
}
 \label{fig:rainPozDif2}
\end{figure} 

Kad spr�sti �i� problem� atliksime
skai�iuojam� po�ymi� vidurkinim� spindulio ir kampo kryptimi. Papras�iausiu
atveju gaunamas vidurkinimo rezultatas bus ekvivalentus filtravimui su tokiu
dvima�iu filtru: 
\begin{eqnarray*} 
f_{n,m} &=& \left[ \begin{array}{cccccc}
0.5&0.5&-1&-1&0.5&0.5\\
1&1&-2&-2_{0,0}&1&1\\
0.5&0.5&-1&-1&0.5&0.5
\end{array}\right],\\
(u*f)_{n,m} &=&\sum_{j=-1}^1\sum_{i=-3}^2 \ u_{n-j,m-i} f_{j,i}. 
\end{eqnarray*} 
�ia $2_{0,0}$ �ymi filtro $f_{n,m}$ centrin�
koeficient� atitinkant� indeks� reik�mes $n = 0$ ir $m = 0$. Taikant �ias formules
laikoma, kad $u_{n-j,m-i}$, kai $m>i$ arba $m \ge M + i$, yra gaunamos periodu $M$
prat�siant reik�mes, t.y. $u_{n-j,m-i} = u_{n-j, (M+m-i)\%M}$. Toks periodinis
prat�simas yra nat�ralus, nes pradinis rainel�s signalas yra periodinis kampo
kryptimi. Kadangi spindulio kryptimi signalas n�ra periodinis, tai pateiktose
dvima�io filtravimo formul�se laikoma, kad $u_{n-j,m-i} = 0$, kai $n<j$ arba $n \ge
 N + j$. Atlikus minimal� vidurkinim� spindulio ir kampo kryptimis gausime
\ref{fig:rainPozDif2k} pav. pavaizduot� binarini� po�ymi� matric�. �i po�ymi� matrica kiek pana�i �
\ref{fig:rainPozDif2} pav. po�ymi� matric� tik apskai�iuot� kitu dvigubai smulkesniu masteliu. 


 \begin{figure}
\centering
\includegraphics{figures/image025} 
  \caption{ 
 Binarini� po�ymi� matrica gaunama
filtruojant antrosios eil�s i�vestin� atitinkan�iu skirtuminiu filtru
vidurkintu 2 ta�keliais kampo ir minimaliu trikampiu vidurkinimu spindulio
kryptimi
}
 \label{fig:rainPozDif2k}
\end{figure} 

Daugman darbe taip pat nurodyta, kad galutin�
po�ymi� matrica formuojama naudojant keli� masteli� Gaboro filtrus. Tod�l mes
apibendrinsime vidurkinimo formules tuo atveju, kai imama KF vienodais svoriais
vidurkinim� kampo ir $(2*KR+1)$ trikampio lango svoriais spindulio kryptimi. Tok�
vidurkinim� atitiks filtras 

\begin{eqnarray*} 
f_{n,m} &=& \left\{ \begin{array}{ll}
1-\frac{|n|}{KR+1}, & |n|\le KR, \ m=-KF,\dots,-1, \mbox{ arba } KF,\dots,2KF-1,\\
-2(1-\frac{|n|}{KR+1}), & |n|\le KR, \ m=0,\dots,KF-1,\\
0, & \mbox{ likusiais atvejais.}
\end{array}\right.
\end{eqnarray*} 
\ref{fig:rainPozDif2k} pav. atitinka vidurkinimo parametr� reik�m�s $KF = 2$ ir $KR = 1$.

 
\hypertarget{rainSabl}{{\bf Rainel�s �ablonas}}

 
�ablonas ( angl. {\it template}  ) yra
formuojamas i� po�ymi�. �ablono prad�ioje gali b�ti antra�t� ( angl. {\it header} ),
 kurioje �ra�oma specifin� informacija, pavyzd�iui pradinio paveiksliuko
katalogas ir vardas, objekto unikalus identifikatorius. �ablono antra�t�je
patalpinama informacija nenaudojama skai�iuojant dviej� �ablon� pana�um�.
Likusi rainel�s �ablono dalis sudaroma i� binarini� po�ymi�. Tarkime fiksuoto
mastelio po�ymi� matricai sudaryti naudosime $32 \; r_n $ ( $N = 32$ ) ir $256 \; \phi_m$ ( $M
= 256$ ) reik�mes, bei keturis skirtingus mastelius/vidurkinimus atitinka�ius
parametrus $KF = 2$, $KR = 1$; $KF = 3$, $KR = 2$; $KF = 4$, $KR = 2$ ir $KF = 6$, $KR = 3$. 16 pav.
iliustruoja 242116.tiff failo rainel�s gaunam� �ablon�. Vaizdumo d�lei 4-i�
skirting� masteli� binarini� po�ymi� matricos atskirtos keli� ta�keli� baltais
tarpais. Sudarant viening� $4x32x256$ bit� matric� neb�tina i�d�styti paveiksl�lyje
nurodyta tvarka. Pavyzd�iui gali b�ti patogu vien� bait� sudaryti i� dviej� ketvertuk�,
gaunam� sudedant greta keturi� skirting� masteli� binarini� po�ymi� bitus.
Objektus atspindintys �ablonai kaip taisykl� u�ima �ymiai ma�iau vietos nei
pradin� informacija. Pavyzd�iui m�s� pradinis rainel�s paveiksl�lis pateikiamas
$640 x 480$ $256$ pilkumo lygmen� ta�keliais, kas atitnka $640 x 480 x 8 = 2457600$
bitus informacijos, o tos pa�ios rainel�s �ablonas u�ima tik 32 x 256 x 4 =
$32768$ bitus, t.y. pradin� informacija suspaud�iama lygiai $75$ kartus. Daugmano
algoritmas naudoja dar glaudesnius �ablonus, kuri� dydis yra $2048$ bitai binarini�
po�ymi� plius tokio paties dyd�io kauk�s ( angl. {\it mask}  ), t.y. vieno
rainel�s �ablono dydis yra tik $4096$ bitai. 


  \begin{figure}
\centering
\includegraphics{figures/image027} 
\includegraphics{figures/image028}\\
\includegraphics{figures/image029} 
\includegraphics{figures/image030}

  \caption{ 
 Rainel�s �ablonas sudarytas i� $4$ - i� masteli� $32x256$ binarini� po�ymi� matric�. 
}
 \label{fig:rainPoz4sabl}
\end{figure} 

\hypertarget{sablPalyg}{{\bf �ablon� palyginimas}}
 

Beliko i�siai�kinti paskutin� raineli�
atpa�inimo/verifikacijos etap�, t.y. �ablon� palyginim�. Verifikacijos atveju
atpa�inimui pateikiami du raineli� �ablonai ir reikia priimti sprendim� ar tie
�ablonai atitinka vien� ir t� pa�i� rainel� ar tai yra �ablonai gauti i�
skirting� raineli�. Kaip taisykl� pirmasis �ablonas yra i�sirenkamas i� i�
anksto �ra�ytos raineli� duomen� baz�s pagal asmens prisistatym�, pvz.
klaviat�roje surinkt� vard�/pavard� ar kok� nors asmen� identifikuojant� kod�,
-o antrasis �ablonas sudaromas operatyviai nuskenavus asmens rainel� ir atlikus
piln� rainel�s lokalizavimo bei po�ymi� i�skyrimo proced�r�. Taigi verifikacijos
metu reikia �vertinti dviej� �ablon� pana�um�. �ablon� pana�umas �vertinamas
lyginant atskirus �ablon� bitus. Jei dviej� �ablon� atitinkamose pozicijose
bitai sutampa (t.y. $0 = 0$ arba $1 = 1$ ), tai pana�umo metrika padidinama
vienetu. Paprastumo d�lei laikysime, kad �ablone yra �ra�yta $K x N x M = L$ bit� $bin_l$ ,
$l = 0, 1, ..., L-1$, kur $K$ yra masteli� skai�ius, $N$ � skirting� spinduli�
skai�ius, $M$ � kamp� skai�ius\footnote{
Terminijos paprastumo d�lei laikome, kad rainel�s i�orinio ir vidinio
apskritim� centrai yra vienodi ir tuomet $N$ atitinka naudojam� fiksuot�
spinduli� skai�i�, o $M$ - pilno kampo $2\pi$ padalinim� skai�i�}.
Tuomet dviej� �ablon� pana�umas ( angl. {\it similarity}  ) gali b�ti
�vertintas taip  
$$
 \sim(bin^1,bin^2) = \frac{\sum_{l=0}^{L-1}\sim[bin_l^1,bin_l^2]}{L},
$$ 
kur $\sim[a,b] = 1$, kai $a = b$ ir $\sim[a,b] = 0$,
kai $a != b$. Kitaip tariant pana�umas yra dviejuose �ablonuose sutapusi� bit�
dalis. Deja tokia paprasta pana�umo samprata duoda nelabai auk�t� raineli� verifikacijos
kokyb�. Taip atsitinka d�l to, kad dvi skirtingos tos pa�ios rainel�s
nuotraukos gali b�ti kiek pasisukusios kampu $\phi_0$ ir prielaida, kad abiej�
raineli� kamp� reik�m�s vieningoje koordina�i� sistemoje sutampa, t.y. $phi^1_m
= \phi^2_m$, yra neteisinga ir tur�t� b�ti patikslinta pvz. $phi^1_m = \phi^2_m +
\phi_0 $ formule. Ta�iau prakti�kai pos�kio $\phi_0$ reik�m� b�na ne�inoma, tuo labiau,
kad bendru atveju d�l raineli� nestand�i� deformacij� ir lokalizacijos paklaid�
kiekvienam $m$  gali b�ti kiek kita pos�kio $\phi_0$ reik�m�. Tod�l prakti�kai
yra fiksuojamas ie�komo pos�kio $\phi_0$ tikslumas $\delta(Rot)$, pasirenkamas galim�
pos�ki� skai�ius $NRot$ ( pvz. Daugman naudoja $NRot = 3$ ) ir ie�komas maksimalus
pana�umas 
$$
 \Sim(bin^1,bin^2) = \max_{\mbox{rot } \in \{-\mbox{NRot}, \dots, \mbox{NRot} \} }
 \sim(bin^1, Rot(bin^2,rot)) = \frac{\sum_{l=0}^{L-1} \sim[bin^1_l,Rot(bin^2_l,rot^*)]}{L}.
$$ 

Kaip taisykl� $Rot(bin_l,rot) = bin_{l+rot}$,
ta�iau jei $(l+rot\ge L)$ arba $l$ ir $l+rot$ yra skirting� spinduli� eilut�se,
indeksas $l+rot$ paslenkamas kartotiniu eilut�s periodu $M$ taip, kad� $l$ ir $l+rot+mM$
b�t� vienoje eilut�je. Pavyzd�iui, jei $M = 256$ ir formuojant �ablon� naudojama
\ref{fig:rainPoz4sabl} pav. iliustruojama skirting� masteli� i�d�tymo tvarka, tai 
$$ Rot(bin^2_{254},7) = bin^2_5. $$

Kad palyginti skirting� pana�umo metrik�
kokyb� ir parinkti optimalius po�ymi� i�skyrimo ir palyginimo algoritm�
parametrus naudosime JAV nacionalinio standartizacijos instituto ICE 2005
raineli� duomen� baz� \cite{bib:NISTICE2005}. Rainel�s lokalizavimo mes
neoptimizuosime, taip pat fiksuosime 4 po�ymi� mastelius, spinduli� skai�i� $N =
32$ ir kamp� $M = 256$. \ref{fig:nistIce2005DET} pav. iliustruoja dviej� skirting� raineli� palyginimo
algoritm� kokyb�. M�lyna spalva pa�ym�ta verifikacijos kokyb�s kreiv� DET \cite{bib:ROC}
gaunama tiesiogiai lyginant du �ablonus, t.y. atveju $NRot = 0$, o kita, �aliai nuspalvinta
kreiv�, gauta atveju $NRot = 4$, kas atitinka $1 + 2 * 4 = 9$ skirtingus rainel�s
poslinkius (post�mius �ablon� atveju). Kadangi �alia DET kreiv� visuose
ta�kuose �emiau m�lynos DET kreiv�s, tai vienareik�miai galime teigti, kad �i�
duomen� bazei antrasis �ablon� palyginimo� variantas tinka geriau. Atkreipkite
d�mes�, kad skai�iuojant DET kreiv� pana�umo �ver�iai buvo skai�iuojami ne
visose galimose apsi�auk�li� porose. Taip daroma gana da�nai, nes dideli�
duomen� bazi� atveju galima sudaryti labai daug apsi�auk�li� por� ir taupant
skai�iavimo laik� galima skai�iuoti pana�umo �ver�ius ne visoms, o pavyzd�iui
tik kas $16$ ar $64$ apsi�auk�li� porai. Autenti�k� por� palyginus b�na ma�iau,
tod�l nesunku joms visoms apskai�iuoti pana�umo �ver�ius. 

  \begin{figure}
\centering
\includegraphics{figures/image033} 
  \caption{ 
 NIST ICE 2005 Right Iris duomen� DET
kreiv�s gaunamos naudojant nesukiojamus �ablonus (m�lyna kreiv� ) ir sukiojamus
9 pozicijose ( �alia kreiv� )
}
 \label{fig:nistIce2005DET}
\end{figure} 


Pasi�lysime dar kelet� �ablon� palyginimo
modifikacij�, kurios gerina verifikacijos kokyb�. Lyginam� �ablon� poslinkius
galima atlikti ne tik kampo kryptimi bet ir spindulio kryptimi. Idealaus
raineli� lokalizacijos atveju tokie poslinkiai neturi prasm�s, ta�iau nedideles
vyzd� ir rainel� ribojan�i� apskritim� spinduli� suradimo paklaidas galima
i�taisyti �ablon� palyginimo metu slenkant �ablonus keliais ta�keliais
spindulio kryptimi. Turint $K$ masteli� ir $M$ vieno mastelio skirting� kamp�
atliekant vieno ta�kelio poslink� spindulio kryptimi reikia $bin_l$ reik�m�
pakeisti $bin_{l + K*M}$ reik�me. Gana kebli problema yra lyginti nestand�iai
deformuotas raineles. Nedaug pak�lus/nuleidus, pasukus/pakreipus galv� tos
pa�ios akies skenuotas rainel�s vaizdas �i�sitampo� ir dviej� apskritim�
modelis nepilnai sugeba kompensuoti atsiradusius i�kraipymus. �iai problemai
spr�sti si�lome suskaidyti rainel�s gardel�s ta�kus atskirais sektoriais. \ref{fig:rainSektoriai} pav.
pavaizduotas gardel�s ta�k� grupavimas $8$ sektoriais. Laikysime, kad vieno
sektoriaus ribose deformacijos yra pakankamai ma�os ir lygindami dviej�
raineli� po�ymius ie�kosime �ablon� optimali� poslinki� kampo ir spindulio
kryptimis. 


  \begin{figure}
\centering
\includegraphics{figures/rainSektoriai} 
  \caption{  Rainel�s gardel�s ta�k� suskaidymas � 8 sektorius. }
 \label{fig:rainSektoriai}
\end{figure} 

Tarkime $KRot$ yra teigiam� poslinki� skai�ius
kampo kryptimi, o $KShift$ � teigiam� poslinki� skai�ius spindulio kryptimi. Atliekant
poslink� spindulio kryptimi susiduriame su kra�to problema, nes �iuo atveju
periodinis reik�mi� prat�simas b�t� nelogi�kas. Sprend�iant �i� problem� galima
apsiriboti ma�esniu lyginam� ta�keli� skai�iumi, pavyzd�iui $KMx(N-2KShift)$
parenkant juos taip, kad visi teigiami ir neigiami poslinkiai tilpt� $KMxN$ binarini�
po�ymi� matricoje. Kitas sprendimas � ta�keliams, kuri� indeksai i�eina i� $KMxN$
matricos rib� priskirti su tikimybe $0.5$ reik�m� $0$ arba $1$ ir lyginti pilnas $KMxN$
ta�keli� matricas. Kadangi pagal filtravimo �enkl� parenkam� binarini� po�ymi�
reik�m�s gana tiksliai su vienoda tikimybe $0.5$ yra lygios $0$ arba $1$, tai toks
santykinai nedidelio i� rib� i�einan�i� ta�keli� pakeitimas atsitiktiniais $0$
arba $1$ ne�ymiai kei�ia palyginimo rezultat� ir sprend�ia gana sud�ting�
problem� kok� atlikti normavim� lyginant skirting� dyd�i� binarini� po�ymi�
matricas. 

����������� 
Tarkime suskaid�me gardel� � $S$ sektori�. Tokiu
atveju maksimizuodami at�vilgiu $KShift$ ir $KRot$ poslinki� kiekvieno lyginamo
sektoriaus binarini� po�ymi� sutapimo procent� tur�sime 
$$((2KShift+1)(2KRot+1))^S$$
laisv�s laipsni�. Did�jant $S$  �is
skai�ius greitai auga ir tod�l apsi�auk�li� poros gali atsitiktinai �gyti
dideles pana�umo reik�mes. �iai problemai spr�sti si�lome toki� dinaminiu
programavimu paremt� proced�r�: 

\begin{program} 

|int|[][] score = |new| \; |int|[-|KShift|:|KShift|][-|KRot|:|KRot|]
\FOR sector := 0 \TO |S|-1 \STEP 1 \DO
\FOR k := -|KShift| \TO |KShift| \STEP 1 \DO
\FOR r := -|KRot| \TO |KRot| \STEP 1 \DO
	score[k][r] += \sim(|shift|(|bin|^1,k),|rot|(bin^2,r))_{sector} + 
		\max( score[k][r], score[k-1][r], score[k+1][r], score[k][r-1], score[k][r+1])
 \OD
 \OD
 \OD
\end{program}

Realizuojant $\max(score \dots )$ skai�iavim� reikia
pasir�pinti, kad indeks� ribos nei�eit� i� r��i�.�Dviej� �ablon� pana�umo
reik�m� �vertinama dvima�io score masyvo maksimumu. Taip skai�iuojamas
pana�umas ma�� autenti�k� raineli� deformacij� atveju surinks didel� pana�umo
ta�k� skai�i�, o apsi�auk�li� atveju pana�umo reik�m� turi ma�iau �ans�
surinkti daug pana�umo ta�k�, nes dabar laisv�s laipsni� skai�ius ma�esnis nei 
$$(2\mbox{KShift}+1)(2\mbox{KRot}+1)5^{S-1}.$$
\ref{fig:nistIce2005DETpapild} pav. iliustruoja verifikacijos DET kreiv�s
pager�jim� gaut� apra�ytu algoritmu, kurio parametrai yra $S = 16$, $N = 32$, $M =
256$, $KShift = 2$, $KRot = 4$. 

   \begin{figure}
\centering
\includegraphics{figures/image041} 
  \caption{ 
\ref{fig:nistIce2005DET} pav. DET kreiv�s papildytos juoda verifikacijos
DET kreive, kuri gauta palyginimo algoritmu naudojan�iu $16$ sektori�, $9$
poslinkius kampo kryptimi, $5$ poslinkius sindulio kryptimi ir dinaminio
programavimo pana�umo ta�k� skai�iavimo algoritm�. 
}
 \label{fig:nistIce2005DETpapild}
\end{figure} 

\hypertarget{praktRain}{{\bf Praktin� u�duotis}}

{\em 
Realizuokite apra�yt� raineli� po�ymi� apskai�iavimo, �ablon� suk�rimo ir j� palyginimo algoritm�.}

Raineli� 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.

Raineli� vaizd� pavyzd�ius rasite
\href{http://www.mif.vu.lt/atpazinimas/iris/ice2005/Spring2004iris/}{http://ww.mif.vu.lt/atpazinimas/iris/ice2005/Spring2004iris/}
kataloge. Raineli� segmentacijos informacija patalpinta \href{http://www.mif.vu.lt/atpazinimas/iris/ice2005/Ice2005_right.info}{Ice2005\_right.info}
ir \href{http://www.mif.vu.lt/atpazinimas/iris/ice2005/Ice2005_left.info}{Ice2005\_left.info} failuose.

\begin{enumerate}
\item Apskai�iuokite ir pavaizduokite i�tiesintos rainel�s pilkumo lygmenis analogi�kai \ref{fig:rainPilkLygVaizd} paveiksl�liui.

Raskite ir pavaizduokite rainel�s binarini� po�ymi� �ablon� analogi�kai \ref{fig:rainPoz4sabl} paveiksl�liui.

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


\item Realizuokite raineli� �ablon� palyginimo variant�,
kuris naudoja raineli� pos�kius. Palyginimo rezultatus �ra�ykite "*.roc" formato faile (�i�r. \cite{bib:ROC}).
NIST ICE 2005 right raineli� �ablon� baz�s verifikacijos lygios klaidos tikimyb� (EER) turi b�ti ma�esn� u� 5 \%.

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

\item Raineli� verifikacijos konkursas.
Paruo�kite raineli� verifikacijos algoritm�, kuris apskai�iuot� duot� raineli� ir j� segmentacijos duomen� (raineles.info) raineles.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/iris/ice2005/Ice2005_right.info}{raineles.list}.

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

{\em java -Xmx1024m -jar ManoRainele.jar \href{http://www.mif.vu.lt/atpazinimas/iris/ice2005/Ice2005_right.info}{raineles.info}}

\item J�s� programa turi kiekvien� fiksuot� raineles.info s�ra�o element� palyginti su raineles.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/iris/ice2005/Ice2005_right.info}{raineles.info} pavyzdyje yra $1425$ �ra��. Vadinasi paskai�iuoto pavyzd�io *.roc faile tur�s b�ti $1425*1424/2$ palyginim� �ra��.

\item Kad j�s� programa sugeb�t� palyginti pakankamai daug por�, jai keliami raineli� poros  palyginimo spartos reikalavimai.

Skai�iavimai bus atliekami su Intel Core 2 Duo, 2.1 GHz, 3 Gb Ram PC.
Programa turi palyginti bent 100 raineli� por� per sekund�.

\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 atsikirai prisideda prie j�s� pratyb� ir teorijos bal�.
\end{itemize}
 
\end{enumerate}