Internati o nal  Journal of Ele c trical   and Computer  Engineering  (IJE CE)  Vol .   4 ,  No . 5, Oct o ber   2 0 1 4 ,  pp . 81 7~ 83 0   I S SN : 208 8-8 7 0 8           8 17     Jo urn a l  h o me pa ge : h ttp ://iaesjo u r na l.com/ o n lin e/ind e x.ph p / IJECE  Fingerprint Direct-Access Stra t e gyUsing L o cal-St ar-Stru c t u re- based Discriminator Feat ures: A Comparison Study       G Indr awan*,  S  Akb a r * , B  Sitoh a n g*  * Data & Software Engine ering Research   Division,  School  of El ectr i cal   Engin eer ing and  Inform ati c s, Institut Tekno lo gi  Bandung       Article Info    A B STRAC T Article histo r y:  Received Aug 18, 2014  Rev i sed  Sep  20 , 20 14  Accepte d Oct 1, 2014      This paper descr i bes a comparison stud y  of the  proposed finger p rint direct- access strateg y  using local-star-topol og y - b a sed discriminator  featur es,  including  internal comparison  among diffe r e nt  co ncerned  conf igur ations, and   extern al compar ison to the other  stra tegies. Thro ugh careful min u tiae-based  featur e ex traction, hashing-b a sed inde x i ng-re tr ieva l m echan ism ,  variab le- threshold-on-sco r e-ratio-ba sed candidate-list red u c tion techniqu e, and hill- climbing learning process, th isstrate g y  was  considered pr omising, as  confirm e d b y  t h e exp e rim e nt  res u lts . F o r par ticul ar  as pect  o f  exte rna l   accur a c y  com p aris on, this s  tr ateg y outp e rfor m ed the others  over three   publicd a ta sets,  i.e. up to Pene tration  Rate (PR) 5%, it consistently  gav e   lower Error Rate (ER). B y   taking sample  at P R  5%, this strateg y  p r oduced   ER 4%, 10% , an d 1% on FVC2000 DB2A, FVC 2000 DB3A, and FVC2002  DB1A, res p ec tiv el y.  Another  per s pectiv e if  a ccur a c y  p e rform anc e  was  bas e d   on area und er cu rve of graph ER  and PR, this str a teg y  n e ith er is the best nor   the worst strateg y  on FVC200 0 DB2A and FVC2000 DB3A, while on   FVC2002  DB1 A  it outperfomed the others and even it gav e  impressive  results for index created b y  thr e e im pressions per  finger (with or without  N T )  b y  id eal s t ep do wn curve where  P R  equal to 1 %  can a l wa y s  b e  m a inta ined   for smaller  ER. Keyword:  Direct-access   ErrorRate   Fi nge r p ri nt   Local-star  Pen e tration  Rate   Copyright ©  201 4 Institut e  o f   Ad vanced  Engin eer ing and S c i e nce.  All rights re se rve d .  Co rresp ond i ng  Autho r :  G .  I ndr aw an ,   Dat a  &  So ft wa re E ngi neeri n g  R e searc h   Di vi si on ,   Scho o l   of Electrical Eng i n eerin g  and   In formatics, Institu t Tek n o l og i Ban d u n g ,   Jl.  G a n e sh a 1 0 ,  Band ung  4 0243 , In don esia.  Em a il: g i n d r awan@liv e.co m       1.   INTRODUCTION  Recent performance com p arison i n  ar ea  of finge r print direct-access st rategy [1], leaving  furthe r  que stion  on  how far its accuracy , efficiency , and scala b ility perform a nce  can be im proved. In ge ne ral, direct- access strategy  itself  m eans any searc h ing st rategy to  out puta candidate l i st (CL) without pe rform i ng  1-t o -1   match i n g   b e tween  a  qu ery and  can d i d a tes in th e  d a tab a se.  ACLfro m  a query will h a v ea  list o f  certain   Error  Rate (ER) atcertain  Pen e t r atio n  Rate (PR ) .  Th e ER is th e avera g e pe rce n tage of sea r che d  queries that  are not  fo u n d ,  an dt he  PR  i s t h e p o rt i on  o f  t h e  dat a base t o   be sea r che d   on t h e a v era g e.  The ac curacy  performance   isth en  m easu r ed  b y th egraph   of th e trad e-o f f  b e tween   ER and PR that s h ows atcertain E R how low PR  can be   achieve d. The  efficiency perform an ce is consid ering  as strateg y ’s  sea r ch s p eed and m e mory  usa g e.  Based on above question and m o tiva tion to answe r  it through ne w fi ngerprint direct-acces s strategy ,  in itial wo rk   h a s b e en  cond u c t e d  b y  au tho r s  [2 ].  As  fa r  as au tho r s’ k nowled g e ,  th e propo sed   strateg y  by  th is  work  fill in non-e xisting e x ploration area i n   direct-acces s strategy base d  on 1-to-1  m a tching  using local -star- stru cture th at  was in trod u c ed  first b y  Ratha et al. [3 ].  This p r opo sed  strateg y  will th en b e  co m p ared   to  th e  othe r state-of-the -a rt strate giesin this  pa per. Seve ral  proposed  fingerpri n t  direct-acce ss strategies have be e n   ro u ghl y  cl assi fi ed by  [4] ,  i . e.  1)  usi n g gl o b al  feat ures  s u ch  as global ridge - line fre qu ency  [5]; 2) local fe atures   Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S SN :  2 088 -87 08  I J ECE Vo l. 4 ,  N o . 5 ,  O c tob e r  20 14   :   817  –  8 30  81 8 suc h  aslocal ri dge -line frequency, lo cal  ri d g e-l i n e  ori e nt at i ons, a ndl ocal   features  from   the orie ntation im age  ([ 5] , [6] ,  [ 7 ] ,  [ 8 ] ,  [9] ,  [ 1 0] );  3) m i nut i ae feat uress u c h  asg e om et ri c feat ures fr om  t r i p l e t s  of m i nut i ae poi nt s   an d   p e rf or m  se ar ch i n g  thr ough  h a sh ing  str a teg y  ( [ 1 1 ] , [12 ] , [ 1 3 ] , [ 1 4 ] ) ; 4) o t h e r  f eat u r es su ch  asFi n g e rCo d e ,  ri d g e c u r v at u r e , an d S I FT  feat ures  ( [ 1 4 ] ,   [1 5] , [ 1 6] ), a n d m a t c hi ng  sc ores  ( [ 1 7 ] ,   [1 8] ).   The p r o p o se d  st rat e gy  cl oses t o   m i nut i ae-base d a ppro a ch  abo v e bu t in stead  of u s i n g  tri p letsof  min u tiae, it u s es lo cal-star-stru ct u r e  o f  m i n u tiae. Th is p a per reports exp e rim e n t s o n  th ree p u b licly av ailab l e  benc hm arks a n d i t s  res u l t s   pr ove  t h at  t h e  p r op ose d  st r a t e g y  was c o n s i d e r edas  a  pr om i s i ng st rat e gy  si nce i t   com p ares fa vorably  with the   othe r state- of -the-a rt strate gies.  Based  on pre v ious m e ntione d  perfom ace indicator, th e  rest of this  pa per is  orga nized as  follows .  Sectio n  2  illu st rativ ely d e scri b e s th e propo sed  strateg y  th at  was in itiated  b y  In drawan  et al. [2 ] (its scalab ilit y   per f o r m a nce was al ready  g i ven o n  i t ) . S ect i on 3 desc r i bes exp e ri m e nt s on  pu bl i c  dat a  set s , i n t e rnal l y   com p are i t a m o ng  di ffe re nt  co ncer ne d co nfi g urat i o ns, a n dex t ernal l y  com p are i t  wi t h  ni ne  pu bl i s he d st rat e gi es.   It desc ribes   data sets that  was  use d  (Section  3.1), internal accuracy c o m p arison am ong  diffe re nt   configurations and e x ternal accuracy  com p aris on to the other strate gi es (Section 3.2), interna l  speed  com p ari s on  a m ong di f f ere n t  con f i g urat i o n s  (Sect i o n  3. 3 ) , a n d  i n t e r n al  m e m o ry  usage com p ari s o n   am ong   di ffe re nt  co nfi g u r at i o ns ( S ec t i on  3. 4)  rel a t e d t o  t h e  has h i n g sy st em  used  by  t h e  pr op ose d  i n de xi ng  an d   ret r i e val   pr oce ss. Sect i o n  3. 3  an d  3. 4 ca nn o t  do  ext e r n al  c o m p ari s on  bec a use  of  di f f ere n t  ha rd wa re  pl at form   with  th e  o t h e r strateg i es.  Fin a lly, Sectio n 4   draws  th e con c lu si o n  an d Section   5 sugg ests immed i ate   im pro v em ent for  the  pr o p o s e d  strate gy  th ro ug h t h e  fut u re  wo rk .       2.   R E SEARC H M ETHOD  The  pr op ose d   st rat e gy  was c onst r uct e d by   m i nut i ae-base d  feat ur e ext r a c t i on  pr ocess ,  ha shi n g- bas e d   inde xing-retrie v al m echanism ,  vari ab le- t hr esho ld-o n- scor e-r a tio -b ased   can d i d a te-list redu ction  techn i qu e,  an d   h ill-clim b i n g  learn i n g   pro cess.Its m a th e m atical p e rs pectiv e was elab orated  i n  detail at [2 ]. Figu re  1   ilustrates sim p lified  proce ss  of  th e pr opo sed   str a teg y .  1.   Feat ure e x t r act i on  pr ocess  w a s base d o n    m i nut i ae det ect i on al g o ri t h m  [1 9] , [ 2 0] , w h ere m i nut i a  t y pe  (end ing   o r  b i furcatio n), m i n u t ia cartesian -coo rd in ate,  and   min u tia ab so lute-o rien tatio n (min u tia an g l e to  the horiz ontal  line) are  rec o rded.  Based  on th is feat u r e ex traction r esu lt, th e algo rith m i d e n tifies certai n  num ber  of m i n u tiae edgesthrough id e n tifica tion of  l o cal-st a r  structur e  be long to each minutia-re fe renc e  (sam pl e st ruct urei n Fi gu re  1:  da sh ed -lin e en circled m in u tia-referen ce  m 1  wit h  sev e ral d a sh ed-lines  co nn ecting  to  min u tia- n eighbo ur s). Each  edg e   d e f i n e s a lin e  w h o s e  g e ometr i c f eatu r es ar eex t r acted : i t s   len g t h   f r o m  it s  m i n u tia- r e f e r e n ce t o  its min u tia- n eighbo ur , its m i n u tia- r e f e r e ncer el ativ e- or ien t ation   (angle di ffe rence betwee n m i nutia-refe r e n ce abs o lute-o rien tatio n  to  t h e edg eabso l u te-ori en tatio n), and  its  min u tia- n eighbo ur   r e lativ e-o r i e n t atio n ( a n g l e d i ff er en ce b e t w een m i n u tia- n eigh bou r abso lu te-o r i en tatio n  to  th e edg e  abso lu te-orien tatio n).Hipo t etically, th e si milari ty b e tween  two  fing erprin ts is d e fin e d   b y  th e  num ber of   co rr esp o n d i n g  e d g e s  t h at   ca n be f o u n d  un de r  ret r i e val  pr ocess on   t h e ne xt   st e p .   2.   In stead  of exp licitly co m p aring  th e sim i l a rity b e tween th e qu ery fi n g e rp rin t  an d all th e can d i d a te  fi n g er pri n t s i n  t h e dat a base ( w hi ch w o ul d  be  very  t i m e  consum i ng), t h e a u t h ors  use a g e om et ri chashi n g   t echni q u e [2 1]   fo r  i n d exi ng  pr ocess:  a has h  t a bl e i s  bui l t  by  qua nt i z i n g cert a i n   num ber  of t h e e d g e s  above and for  eachqua n tized edge , a lis t of  poi nters (ID) to the fingerpr i n ts in the database containi ng  that specifice dgeis m a intained.  Wh en   a new fi n g e rp rin t  is in serted  i n  th e  d a tab a se, its edg e s are  extracted, a n d  the ha sh table i s  updated  by a ddi ng th e f i ng er pr in t  I D s an d  th eir  co rr esp ond ing   f i ng erp r i n t   edge s, t o  t h e  has h  val u es a ssoci at ed t o  t h e has h  key s .  A hash  val u e was co nst r u c t e d by  t h e list  to   accomm odate  co llisio n  t h at  c e rt ai nl y  ha ppe ned .   C o llisio n will b e   h a p p e ned   wh en th e same h a sh k e y  was  gene rat e d  f r o m  di fferent   ed ges t h at  co ul d  com e  from  sam e  or  di f f ere n t  fi n g er pri n t  I D .  G o o d   desi g n   o f   has h  f unct i o n  fo r t h e ha sh  k e y  wo ul d m i nim i ze  co llisio n . Fo r  t h e pr oposed  str a teg y , t h e h a shk e y w a s  b a sed  on   3 2 -b it in teg e r  v a lu e co nstructed   by p r ev iou s ly  describ e d  three  d i scrim i n a to r attrib u t es, i.e. th e  ed g e  leng th   (16 - b it Least Sig n i fican t Bit /  LS B), m i nutia-re fere nce re lativ e-orien t ation  (23 th  - 1 6 th  bit),  an d m in u tia-n ei g hbo ur relativ e-orien t a tion  (8-b it Mo st Si g n i fican t Bit / MSB).  3.   At retrieval time, the edges  of the query  finge rpri nt are com puted and, for each  edge , the list  of  fing erp r i n t IDs in  wh ich  th at ed g e is  p r esen t  is retriev e d. Intu itiv ely, if th e sa m e  fin g e rp rin t  ID is h it b y   m o re ed g e s in   th e qu ery, th en it is  m o re lik el y th at  t h e cor r e s po n d i n g fi nge rp ri nt  i s  t h e se arche d   one . B u t   through expe ri ment, an edge  com p arison rel a tively stil l not reduce s  the search s p ace significantly. So the   pr o pose d  st rat e gy  uses  com p ari s on  o f  co n n ect ed -t w o -e dges (sam plein Figure  1: connected edges  wi th  min u tia  m 1 ,  m 2 , and  m 3   by  fi nge r p ri nt   ID  X )  an d c o n n ect e d -t hree -ed g es  ( s am pl ei n Fi gur e 1:  co nnect e d   ed g e s with  m i n u tia  m 1 ,  m 2 ,  m 3 , and  m 4  by  fi nge r p ri nt  I D   X ) . A b ove t h ree  edge s which are connected, the  com putational cost is expone ntially  m o re expensiv e (e xponentially  longe r  tim e  execution). Am ulti-stage   Evaluation Warning : The document was created with Spire.PDF for Python.
I J ECE   I S SN :  208 8-8 7 0 8       Fi nger p ri nt   Di rect -Access St r a t e gy Usi n g Lo cal - St ar -St r uct u re- b ase d  Di scri mi n a t o r  …   ( G . In dr aw a n )   81 9 si m ilarit y  sco r e co m p u t atio n  is app lied  t o   ob tain  afin al  rank ing ,  wh ich is  u s ed   for  v i sitin g  t h e  d a tab a se  in   a con v e n i en t  ord e r.  It co n s ist s  of relativ ely-fast-le ss-accurate si m ilarit y  sco r e co m p u t atio n at pre-filter  stage ( ),  and re latively-slow-m ore-accurate sim ilari ty score com putation  at  m a tcher stage ( ). At pre - filter stag e, an  in itial ran k i n g was  d e sce n d i ng ly ord e red b y   p r e-filter sco r e,  .      ∙   (1 )     whe r e  is th e nu m b er  o f  con n ected - t wo - e dges b e long  to  cer t ain  f i ng er pr i n t I D ,   i s  t h e num ber  of   connected-thre e -edges belong  to   cert a i n  f i nge rp ri nt  ID ,   an d   is th e  weigh tin g v a l u e  wh ich  is  det e rm i n ed t h r o u g h  t h e l ear ni ng  pr ocess  o n  t r ai ni n g   dat a  (S ect i on 3 . 1 ) .  At  m a t c her st age,  a fi nal  ra nki n g   wh ich  is an   upd ate fro m  an  i n itial ran k i ng   was d e scend i ng ly o r d e red   b y   fin a l sco r e,  s .      ∙   (2 )     whe r e  is th e m a x i m u m  v a lu e  o f  th e add itio n of sev e ral  wei g h t ed   p a ram e t e rs  d e ri v e d from   th e lon g e st   con s t r uct e d e d ges  (m ay  be di sco nnect e d )  be l o n g  t o  ce rt ai n  fi n g er pri n t  I D   and  i t s  co unt e r part , t h e l o n g e s t  con s t r uct e d ed ges (m ay  be  di sco n n ect ed)  bel o ng t o   fi n g er pri n t  ID X .  Tho s e par a m e t e rs i n cl udi ng   num ber  of e d gepai r s,  num b er of sam e -type-m inu tiapairs, edge le ngt h di ffe rence  accum u lation  of  edge pairs ,  m i nutia-re fere nce’srela tive-orie ntation differe n c e   accum u la tion  of e dge pairs ,  a nd  m i nutia- n e igh bou r’srel ativ e-orien t ation  d i ffer e n ce a ccum u lation of edgepai r s [2].   is th e weig h ting   v a lu e  w h ich  is d e termin ed  th ro ugh th e lear n i ng  pr o cess on  tr ainin g  d a ta (Sectio n   3 . 1 ) . Figu r e  1  sho w s sim p le  retriev a l p r o c ess  with  = 1 a n d   =  1,  w h i c h a r e n o t  act ual l   va l u es  used  by  t h e p r o p o sed  st ra t e gy .  4.   Can d i d a te-list redu ction  m e c h an ism  was app lied   o n  re t r i e val   p r o cess  a b ove .  It  o u t p ut s cert a i n  num ber   of   fin a l cand i d a tes th ro ugh  co mb in ed  techn i ques o f   v a riab le th resho l d   o n  sco r e  ratio  [2 2 ]  at p r e-filter stage,    an d fi x e d-leng t h  trun catio n of  can d i d a te-list at  m a tch e r stag e.  5.   Fin a lly, h ill-cli m b i n g  learn i ng  p r o cess [23 ]  was u s ed   o n  train i n g  d a ta to  o b t ain  op ti m a l  v a lu es for  param e ter-set  of algorithm .  These  values  for pa ram e te r-set were u s ed   on  sev e ral testing   data (Tab le 1).          Figure  1. Duri ng the i nde xi ng  pha se,  t h e e x tracted feature s  from  each fi nger print in the  database are  use d  to  gene rat e  t h e   hash - keys  (a ,  b, c ) . Eac h   key m aint ai ns t h e l i s t  o f  fi nge r p ri nt   I D s  ( 1 ,  2 ,  3 ) and  th e i r  co rr e s po nd ing   edge s ( e 1 ,  e 2 ,  e 3 ) .   D u r i ng  t h e retr iev a l ph ase,  ed g e s  o f  t h e  q u er y f i ng er pr in t  X  are co m p u t ed  an d th e list  of  fing erp r i n t IDs in   wh ich  th at   ed g e  is  p r esen t  is re triev e d. M u lti stag e sim i l a rity sco r e com p u t atio n  th en  o u t p u t s cand i date list with its fin a l rank ing   wh ich  is an upd ate fro m  th ein iti al rank ing .     Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S SN :  2 088 -87 08  I J ECE Vo l. 4 ,  N o . 5 ,  O c tob e r  20 14   :   817  –  8 30  82 0 3.   R E SU LTS AN D ANA LY SIS  This section  descri bes experim e nts carried out  to eva l uate accuracy  and ot her as pects of the  pr o pose d  fi n g e r p r i n t  di rect -ac cess st rat e gy  a nd t o  com p ar e  it with  th e o t her state-of-t h e -art in  th is field. Th e  al go ri t h m  i s  a C #  i m pl em entat i on,  r u n n i n g  on  an  I n t e l  C o re  2  Qua d  C P U  @  2. 40  G H z . E xpe ri m e nt s usi n g   sam e  p e rform a n ce ev alu a tion   an d p a ram e ters calib ration  in [2 ].      3. 1. D a t a   S e ts   Tabl e 1 s h o w s  pu bl i c  dat a  se t s 1  as testing data for m o st of th e publishe d finge r print direct-access   st rat e gi es  [1] .   It  al so  s h o w s  pu bl i c   dat a  set  use d  a s  t r ai ni ng  d a t a  f o r  t h e p r o p o se d st r a t e gy  [ 2 ] .  M o r e ove r ,   m o re descri pt i on  of t h ei r ac q u i s i t i on speci fi cat i on [ 24] , [ 2 5]  was sh ow n  by  Tabl e 2. Im age sam p l e s of t hose  pu bl i c  dat a  set s  we re s h o w n  by  Fi g u r e  2.       Table  1.  Public data sets c o nsi d ere d   for  e v aluation for direct -access  st rategi es.  No.  Data Set   Data Set   Status  Sensor   Typ e   Pixels  ( w  x h)  I m age Nu m b er   ( w  x d)  Resolution  ( dpi)   Published   Strategies   1 FVC2000  DB1A[24]   T r aining  Data   Lo w-Co st  Capacitive  Sensor   300 x 30 0   800 x 8   500   I ndr awanet al.  ( 2 0 14)  [2]   2 FVC2000  DB2A[24]   T e sting  Data   Lo w-Co st  Capacitive  Sensor   256 x 36 4   800 x 8   500   Capelli (2011) [1]  L i ang et al. ( 2006)  [13]   Jiang et al.   ( 2006)  [5]   De Boer  at al. ( 2001)  [14]   3 FVC2000  DB3A[24]   T e sting  Data   Optical  Sensor   448 x 47 8   800 x 8   500   Capelli (2011) [1]  Jiang et al.   ( 2006)  [5]   4 FVC2002  DB1A[25]   T e sting  Data   Optical  Sensor   388 x 37 4   800 x 8   500   Capelli (2011) [1]  Shuai et al.   ( 2008)  [16]   L i ang et al. ( 2007)  [26]             Fig u r e   2 .  Fro m  lef t  to   r i gh t: sam p le f i n g e rp r i n t s fro m  FV C20 0 0   D B 1A , FVC2 000  D B 2A ,  FV C200 0 D B 3A ,  an d FV C200 2  D B 1 .  Fir s t  im p r ession sw er e used   f o r  i n d e x  cr eatio n ( t op   row ) , an d th e  o t her s   ( b o tto m  r o w )   were  use d   for  que ries.  Noted, im ages are  not  in thei r actual  size but they a r e in thei r scale  diffe re nce.                                                                              1  Beside FVC  (Fi ngerprint Verifica tion Co m p etition) public data sets, several published  strategies have  been also evaluated o n   co mm e r cial  public data sets, i . e.  NIS T   DB4,  NIS T  DB4  (Natura l ),  and NI ST DB14  Evaluation Warning : The document was created with Spire.PDF for Python.
I J ECE   I S SN :  208 8-8 7 0 8       Fi nger p ri nt   Di rect -Access St r a t e gy Usi n g Lo cal - St ar -St r uct u re- b ase d  Di scri mi n a t o r  …   ( G . In dr aw a n )   82 1 Tabl e  2.  Pu bl i c  dat a  set s  ac q u i s i t i on s p eci fi ca t i on.   No.   Aspect  FVC2000 DB1A &  DB2A [24]   FVC2000 DB3A [ 24]   FVC2002 DB1A [ 25]   1  Volunteer   Students ( 20 to 30  y e ar old; about  50% m a le).  19 vol unteer s ( 5  to 73 y ear old;   55%  m a le; 1/3 of  them  wer e  over   55 y ear old; 1/3  of t h em wer e   under  18 y ear old; 1/6 of them   wer e  under  7  y e arold) .   30 stude nts ( 20 y ear  old on the   average).   2  Session   For e  and  m i ddle finger  of  both   the hands  (f our  f i ngers) of  each  volunteer  wer e  acquir e d in two   sessionsby  inte r l eaving the  acquisition o f  the  differ e nt  finger s   ( e . g . ,  fir s t sa m p le   of le ft  for e ,  fir s t   sa m p l e  o f  rig h t  fore, f i rst sa m p l e   of le ft  m i ddle,  fir s t sam p le of   r i ght  m i ddle,  second sam p le of  the left for e ,  and so on) .   T w o im ages  of six finger s   ( t hu m b ,  for e ,  and  m i ddle finger  of   both the  hands) of each volunteer   wer e  acquir e d in four  sessi ons   without inter l eavi ng.  No  m o r e   than two sessio n s  a day .  The ti m e   between the first a nd last sessions   was at least 3 day s  and as l ong  as   3 m onths,   depending  upo n   volunteer .   For eand  m i ddle finger  of both the   hands (f our f i ngers) of  each  volunteer  wer e  acquir e d in thr ee  sessions  by  inter l eaving the   acquisition o f  the differ e nt   f i ngers. The ti m e  between each  session was at le ast two weeks.  At each session,  f o ur i m ages were   acquired of each of the  f o ur  f i ngers of  each volunteer. At the  2 nd   session, they were requested to  exagger a te finger  displacem e nt  ( i m a ge 1 and 2)  a nd r o tation  not   to exceed 35° (i m a ge 3 and 4). At   the 3 rd  session,  finger s  wer e   alternatively dried  (i m a ge 1 and  2)  and  m o istened (im a ge 3 and 4) .  3 Sensor   Platen&  I m age  Quality  T h e sensor  platens wer e  not  cleaned syste m atically. The   im ages wer e  taken fr o m  untr a ined   people and no ef f o r t s wer e   m a de  to control i m age q u ality.   The sensor platen was cleaned  syste m a ticall y  between each  acquisition. At one session, each  volunteer ’ s  finger s  wer e  cleaned  with r ubbing alcoh o l and dr ied.   The sensor platen was not cleaned  syste m a ticall y . Th e i m ages were   taken fr o m  untr a ined people and   no e ffor t s  wer e  m a de to contr o l   i m age quality.   4 Cor e   &  Delta   Finger p r i nt cor e s  and deltas ar e  not guar a nteed exist since no  attention on checking the  correct  finger  center i ng.   Finger p r i nt cor e   was exist but  car e  was taken to  avoid co m p lete  overlap between consecutive  i m ages taken at  a s e ssion.    5 Rotation  &   Non- Null  Over lapping  Area   Maxi m u m   rotation is about 15  and non- n u ll ov er lapping ar ea  between any  two im p r essions of   the sam e  finger .   M a xim u m  r o tatio n is ab out  15°   and non- null o v e r l apping ar ea  between any  two im p r essions of   the sam e  finger .   M a xim u m   r o tation is a bou t   35° and no n- null o v er lapping ar ea  between any  two im p r essions of   the sam e  finger .       3. 2. Accur a c y  Com p ari s on   Figure 3  - 5 s h ow the tra d e - off betwee n PR a nd ER  for seve ral fingerpri n t direct access strategies on  th ree FVC d a ta  sets.  1.   All of th e results, ex cep t  th em  with  an  asterisk  m a rk  (Table  3 ) , were ob tain ed  b y  u s ing  first fing erp r i n t  im pression from each finge r  for inde x c r eation, a n d the re maining seve n for  queries (In this case, the  pr o pose d  st rat e gy  resul t s  we re rep r ese n t e d  by  bl ack  d a sh ed-lin es). The resu lts with   an  asterisk  m a rk  were obtained  by using first  three finge r pri n t im pr essions  from  each finger for inde x  creation a nd t h e   rem a i n i ng fi ve  for  qu eri e s ( I n  t h i s  case, t h e  pr op ose d  st rat e gy  resul t s  we re rep r ese n t e d  by  grey  da she d - l i n es). S huai  et  al . [16]  an d Li ang et  al . [2 6]   aret he exce pt i ons . As s h o w n  by  Tabl e 3, t h ey  used ra nd om   i m pression or random  three i m pr essions from  each finge r for i n dex creation.  This will ha ve a  co nsequ e n ce o n   u n p r ed ictab l e h i gh  qu ality o f  created  in d e x  sin c e first i m p r ession  o r   first th ree  i m p r ession s, as it rep r esen ts  o r  th ey   represen t h i gh er qu ality i m ag e(s)  t h an  o t h e rs  fro m  t h e sam e  fin g e r,  was or were  not selected for  sure .  Because  of that c o nsequence ,  ra ndom  selection not s o  appropriate for  h ead to   h e ad  co m p ariso n .  Howev e r, th ey are still wo rt h y  sho w n  t o  en rich   co m p ariso n  stud y in  t h is  p a p e r.  2.   Al l  of t h e res u l t s , except  t h e m  wi t h  a pl us   m a rk (Ta b l e  3 ) ,  were  obt ai n e d by   usi n g  80 0 fi nge rp ri nt s  o f   t e st i ng set  “A ” [2 4]  [2 5]  fr om  100 fi n g e r s. The re sul t s  wi t h  a pl us  m a rk wer e  o b t ai ned by  usi n g   ad d ition a l 80  fin g e rprin t s of train i ng  set “B” [24 ]  [2 5 ] , resultin g  in  88 0   fing erp r i n ts fro m   1 1 0  fi n g e rs.  In  anot her  wo rd , t h e resul t s  wi t h  a pl us m a rk were  obt ai ne d  by  usi n g ad di t i onal  1 0  im pre ssi ons f o r i n de x  creat i on a n d 7 0  i m pressi ons f o r  que ri es. B o t h  o f  t h e r e sul t s  cann o t  be  u n i t e d f o r  hea d  t o   head c o m p ari s on .   Howev e r, th e resu lts with a  p l u s  m a rk  are still wort h y  sho w n  to enrich com p ariso n  st u d y in  th is  p a p e r.  3.   All o f  th e  results, ex cep t  th em  with  a h a sh m a rk   (Tab le  3 ) , were  ob tain ed withou t selectin g  To p 10%  Scores ( N T  =  N /10), where  N i s  num ber of  im pressi on s u s ed by  i n de x creat i o n .  The  re sul t s  wi t h  a ha s h   m a rk were o b t a i n ed by   sel ect i ng To p 1 0 %  S c ores .   4.   Based on thos e pre v ious points, th e propos e d strategy provides three  kinds of res u lts, each re prese n te d  by  p r evi o u s  m e nt i one d  bl ack - an d  g r ey -  das h ed -l i n es . T h es e three  kinds  of res u lts eac h c o m e s from  thre e  con f i g urat i o ns  t h at  were c o ncer ne d by  t h i s  resear ch  for th e in tern al  co m p arison,  and t h e external  co m p ariso n   with  o t h e r ex istin g  strateg i es.  Th ese thr ee confi g urations are for  sear ch  m o d e : 1)  up topre- filter stag e  (d ash e d - lin es  wit h  sq u a re m a rk); 2)  u p  t o  m a t c h e r  stag e  with   N T  t r u n cat i o n  of C L  ( d as h e d- Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S SN :  2 088 -87 08  I J ECE Vo l. 4 ,  N o . 5 ,  O c tob e r  20 14   :   817  –  8 30  82 2 lin es with  trian g l e m a rk ); and  3) up  to  m a tch e r stag e  with ou t  N T  t r unca t i on o f  C L  ( d a s he d-l i n es  wi t h   ro u nd m a rk) .  F o r t h e  next   di s c ussi o n ,  t h ree   bl ack  das h ed -l i n es  wi t h  s qua r e , t r i a n g l e , a n d  ro u n d  m a rk o n   th e grap h s , each   will b e  re ferred  as  Pre-filter, Match e r,  an d Matc h e r2 . Wh ilst,  t h ree grey  d a sh ed -lines  with square , triangle, a nd round m a rk on the gra phs, each  will be refe rre d  as Pre -filter*, Matcher*, and  M a t c her2 *.  N o t e d,  no  s p eci fi c sq uare , t r i a n g l e , a n d  r o un d  l e gen d s  fo r t h e  p r o p o sed  st rat e gy  f o r  t h e  sak e   of si m p l i c it y   of t h e g r a phs .  As Li ang et  al . [1 3]  [ 26] s t ated that the  finger p r i n t id en tificatio n  can b e   di vi de d i n t o   f i nge rp ri nt  i n d e xi n g  a n d  fi n g er pri n t  ve ri fi cat i on, M a t c h e r, M a t c he r 2 ,  M a t c her * , a n d   M a t c her2 * o f   t h e pr o pose d  st r a t e gy   co ul d be  con s i d ere d   a s   s o rt  of   fi nge rp ri nt   ve ri fi cat i o n.   5.   Th is po in t  refers to  th e i n ternal co m p ariso n   o f  t h e p r o p o se d st rat e gy . G ra ph  res u l t s  co nf i r m e d t h at  Pre- filter/Pre-filter* was less acc urate tha n  Matcher/Ma tche r*, whilst Matcher/Matcher* was less accurate  th an  Match e r2 / M atch er2* . By d e sig n , Pre-fil t er/Pre-filte r*  refer to  th e search  po wered   b y  relativ ely-fast- less-accurate si milarit y  score  com puta tion.  They ga ve the  search  output  in the form  of i n itial CL with it s   in itial can d i d a tes rank . At t h e o t h e r sid e , Match e r/Match e r*o r  Matcher2 /Match er2* refer t o  search   powe red by  relatively-slow-m ore-accu rate  similarity sc ore  com putatio n. They re fi ne initial CL to  becom e  final  CL with its final rank,  whic h  was m o re  accurate on ra ngki ng order. Matcher/Matcher* loss  its accuracy in certain  degree  com p are to M a tcher2/Matcher2*  because  of its final CL t r uncation by t h e  secon d  step  of CL redu ction  [2 ] wh ich  is si m p l y  tru n cating  leng th   o f  C L  to   N T  if leng th   o f  CL long er  th an   N T .  No ted on  Figure  4 ,  Pre-filter resu lt is ou t of  g r aph   v i ew. Fu rth e rm o r e b a sed on   g r aph  resu lts, t h e  pr o pose d  st rat e gy  nee d  t o  i m prove i t s  al go ri t h m   to  g i v e s relativ ely sm a ll d i fferen t  resu lt b e tween  M a tcher a n d   M a tcher2 ,  or  b e tween M a tc h e r* a n d M a tch e r2 *,  specifica lly  for  result  o n  F V C2 0 0 0  D B 2  ( F igu r e 3)  and   FV C200 0 D B 3 ( F i g ur e  4 ) .  6.   Th is po in t refers to  ex tern al co m p ariso n   o f  th e p r o p o s ed  strateg y  (Match erand  Match e r*) to  th e o t her  strateg i es u tilizin g   N T  (st r at egi e s wi t h  has h  m a rk at  Tabl e  3).  On Fi gu re 3 a nd Fi gu re 4 ,  u p  t o  PR  equal  t o   4 % , Match e r gav e  lower ER  rath er th an  Cap e lli [1 ].  Larger th an   PR eq ual to   4 % , Cap e lli [1 ] h a s fast er  rate o f  d e crease o f  its ER to   PR, so  it g a v e  lo wer ER  rather than Matche r. On Figure 5,  at all PR on the  g r aph ,  Match e r g a v e  l o wer ER rath er t h an   Cap e lli [1 ], and  Match e r*   g a v e  lower ER  rath er th an  Cap e lli*   [ 1 ]. M o r e ov er, Match e r*   g a ve step   do wn  cu rv e  wh ic h  is id eal cu rv e  where it can m a in tain  its PR eq ual  t o  1%  f o r  sm al l e r ER . It  m eans  fo r e v ery  q u ery ,   searc h  res u l t  of  t o p  one  o f  C L   ( 1 % o f   num ber  of   fingerpri n t at inde x) alwa ys  give correct  candidate.          Figure  3. Acc u racy of  propos ed direct-acces s  st rategy on  FVC2000 DB 2.       Evaluation Warning : The document was created with Spire.PDF for Python.
I J ECE   I S SN :  208 8-8 7 0 8       Fi nger p ri nt   Di rect -Access St r a t e gy Usi n g Lo cal - St ar -St r uct u re- b ase d  Di scri mi n a t o r  …   ( G . In dr aw a n )   82 3     Figure  4. Acc u racy of  propos ed direct-acces s  st rategy on  FVC2000 DB 3.             Figure  5. Acc u racy of  propos ed direct-acces s  st rategy on  FVC2002 DB 1.                         Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S SN :  2 088 -87 08  I J ECE Vo l. 4 ,  N o . 5 ,  O c tob e r  20 14   :   817  –  8 30  82 4 Table  3. T h e  e x ternal accurac y  com p arisonof direct-access  strategies.  No.  Data set   Proposed approach   Publis hed strategies  Index fro m   each finger  1 FVC2000  DB2A[24]   Match e r2   Match e r2   Match e r2   Match e r #   De Boer  at al. ( 2001) + [14]   Jiang et al.   ( 2006)  [5]   L i ang et al. ( 2006) + [13]   Capelli (2011) # [1]   First i m p r ession  First i m p r ession  First i m p r ession  First i m p r ession  2 FVC2000  DB3A[24]   Match e r2   Match e r #   Jiang et al.   ( 2006)  [5]   Capelli (2011) # [1]   First i m p r ession  First i m p r ession  3 FVC2002  DB1A[25]   Match e r2   Match e r #   Match e r2 *   Match e r2 *   Match e r*   #   Shuai et al.   ( 2008)  [16]   Capelli (2011) # [1]   L i ang et al. ( 2007) *  + [26]   Shuai et al.   ( 2008) *[1 6 ]   Capelli (2011)*  # [1 ]   Rando m  i m pr essio n   First i m p r ession  Rando m  thr e e i m p r essions  Rando m  thr e e i m p r essions  Fir s t thr e e im pressions   +  Results have been obtained  by  usin g additional  80  fin g er pr ints of tr ainin g  set “B”  [2 4]  [25] ,  r e sulting in   880 fi nger p r i nts fr o m  110 finger s .   * Results have bee n  obtaine d by using three f i ngerprint  i m p r essions  f r o m   each f i nger f o r index creation,   instead of one.   #  Results have been obtained by  selecting T op 10% Scor es ( N T  =  N /10) .       7.   Th is po i n t refers to  ex tern al  co m p arison  of th e  pr o pose d  st rat e gy  (M at cher 2 a nd M a t c her 2 * )  t o  t h e  o t h e rstrateg ies n o t  u tilizin g   N T  (strateg ies wi th ou t h a sh  m a rk  at Tab l e 3).  On   Figu re3 ,   up  to  PR eq u a l t o   5 % , Match e r2   g a v e  lower  ER  rath er th an  all  o t h e r strateg i es. Hi g h e r than   PR eq ual to   5 % , De B o er et al.  [1 4]  (C om bi ne d)  gave l o we r  ER  rat h er t h an  M a t c her2 . Hi ghe r t h a n  PR   equal  t o   1 3 %,  Li ang et  al . [ 1 3]    g a v e  lower ER rath er th an   Match e r2.  High er t h an PR  eq u a l t o  22 %,  De Bo er et al. [14 ]  (Direction a l  Field) ga ve lo wer ER rat h er  than M a tche r2 .  Un fo rtu n ately, Matcher2 cannot  be com p ared hea d  to  hea d   to De Boer et al. [14] and Li ang et  al. [13] because of  different num b er of data set used (see Ta ble 3).  Mo reo v e r,  De  Bo er et al. ob tain ed  tho s e  resu lts b y  m a n u a lly co rrectin g th e co re  po int in  1 3 %   o f  t h e  fi n g er pri n t s  an d  by  di sca r di n g   1%  of t h e fi nge r p ri nt s  bec a use  no  co re  p o i n t  c oul d  be f o u n d . M a t c he r 2   have  bee n   pe rf orm e d nei t h e r   suc h  m a nual  a d j u st m e nt s no r  re ject i ons . F u rt herm ore,  M a t c her 2  ca n  onl y   be com p are d   head t o  head t o  Jiang et al.  [5] star t  at  PR  equal  t o  5%  whe r eM at che r 2 ga ve l o we r  ER  r a th er th an  Jian g et al. [5 ].  O n  Figu r e  4,  up  to PR  eq u a l  to  22 %, Matcher2   g a v e  lower ER rath er t h an   Jiang et al. [5] .  Higher tha n   PR  eq u a l to  22%, Jian g  et al. [5 ] g a v e  lower ER rath er th an  Match e r2 . On  Fi gu re 5, at  al l  PR  on t h e gra p h ,  M a t c her 2  and M a t c he r2 *  gave l o we r ER  rat h er t h a n  al l  ot her st rat e gi es,   even though no head t o   hea d  c o m p ari s on exi s t b eca use o f   di ffe rent  nu m b er  of dat a  set   and   di f f ere n t   im pression(s ) s e lection m echanism  for i nde x  creation (see  T a ble 3).  8.   Accuracy perform ance com p arison re su lts  related  to  t h e  u s ed  d a ta  set ch aracteristics. Sev e ral po in t s   about these characteristics that could ex pl ai n t hose re sul t s  (poi nt  5, 6, a n d 7):  1 )    Ji ang et  al . [5]  st at ed   fing erp r i n ts of  FVC200 0 DB 2A h a v e  a h i g h er im ag e q u a lity th an  tho s e  of FVC 2 000  DB 3 A . At a l o wer  PR, s u ccess f ul  retrieval nee d s close r  sim ila rity be twee n t h e  que ry a n d  the candi dates, which is  m o re   sen s itiv e to  t h e im ag e q u a lity. Th erefo r e, FVC 2 000  DB2 A   h a s b e tt er retrieval perfo r m a n ce than   FV C200 0 D B 3 A  at low e r  PR. How e ver ,  FV C 2 000   DB2 A   h a s a  wo r s e r e tr iev a l  p e rf or m a n ce th an  FVC 2 0 0 0  DB 3 A  at   hi g h er  PR  beca use  of  pa r t i a l  fi nge rp rint s whose c o re  point is  near the  im age edge  or  out   of t h e i m age. F V C 2 0 00  DB 2 A  has m o re suc h  pa rt i a l  fi n g er pri n t s  t h an F V C 2 00 0  DB 3 A ,  whi c h  fai l s   to  b e  retriev e d  ev en at h i g h  PR; 2 )  Cap e lli [1 ] h a v e   b e en   man u a lly an al yzed  all qu eries th at co u l d   n o t b e   fo u nd at  PR  e q ual  t o   30% a n d co u n t e d t h e m  per dat a   set  base d o n  the  m o st likely  error ca use  (n o e r ro rs   at th at PR o n  FV C20 00 D B 2 ) : a. co r e  no t  p r esen t  ( F V C 20 00   D B 3A  =  1 ,   FV C200 0  D B 2A  = 3) , b. sm all   o v e r l app i ng  r e g i on  ( F V C 2000  D B 3A  =1, FV C20 0 0  D B 2A  =2 ), c. lar g e r o tatio n  (FV C 2 000  D B 3A  =2 ,  FVC200 0   DB 2 A  =1 ),  d .  low i m ag e q u a lity  (FVC 2 000  DB3 A  =10  , FVC2 000  DB2A  = 0 ) , and  e. skin   d i sto r sion  (FVC2 000   DB3A  = 10  , FVC200 0 DB 2 A  =  0 ) ; 3 )  Abo u t   fing erp r i n t im ag e qu alitystated  b y   Jian g  et al. [5 ],  th is  p a p e r con f irm e d  it b y   measu r em en t u s in g   NIST  Fing erp r i n t Im ag e Qu ality (NFIQ)  al go ri t h m    [20 ] . As sho w n b y  Fi gure 6 ,  N F IQ  out put s t h e im age qual i t y  val u e (w her e  1 i s  t h e hi gh est   q u a lity and  5 is th e lowest quality) fo r  80 0  i m ag es p e r d a ta set. Percen tage o f  im ag es wi th  qu ality 1  and  2  (t wo h i g h e st i m ag e qu ality  v a lu e) are ab ou t 37 %,  88 %,  2 6 %, an d 93 % for FVC 2 000   DB1A  (train i ng  d a ta set u s ed   b y  th e p r op o s ed  str a teg y ), FV C200 0   D B 2 A , FV C 2 000 D B 3 A , and   FV C200 2   D B 1 A ,  resp ectiv ely.  Un lik e Jiang  et al. [5 ] an d  C a p e lli [1 ], the  p r op o s ed  st rateg y  h a s no th i n g  to   do  wit h  co re  p o i n t  and  large ro tatio n   (no t  d e p e nd  on  the m ), so  its retriev a l p e rfo r m a n ce on  testing  d a ta sets is in   accorda n ce to their i m age  quality results by NFIQ , i.e .  best result on FVC 2 002 DB1A,  follow  by  FVC 2 0 00  DB 2A , an d t h e n   FVC 2 0 00  DB 3A . N o t e d ,  t h e  pr op ose d  st rat e gy  ar bi t r ari l y  chos e FVC 2 0 0 0   DB1A as train i n g  d a ta  wh ose  p e rcen tag e  of i m ag es with quality 1  an d  2  is  relativ ely q u ite lo w.      Evaluation Warning : The document was created with Spire.PDF for Python.
IJECE   ISS N :  2088-8708      Fi nger p ri nt   Di rect -Access St r a t e gy Usi n g Lo cal - St ar -St r uct u re- b ase d  Di scri mi n a t o r  …   ( G . In dr aw a n )   82 5     Fig u re  6 .  Histog ram  o f   fing erp r i n t im ag e q u ality b a sed   o n   NFIQ al g o rithm      3. 3. Speed   C o mpari s on   Pre v ious accuracy perform a n ce com e s along  with its  spee d pe rform a nce.  In  ge ne ral, it is not   pos sible t o  m a ke a  system a t ic spee d c o m p arison like   accuracy com p aris on since  s p eed res u lt is  obtai ned  on  diffe re nt ha rd ware  platf o rm s.  1.   M o re ove r,  bas e d o n   [1] ,   un fo rt u n at el y  av erage sea r c h  t i m e s are not   rep o rt e d  f o r  o t her  pu bl i s he d   strateg i es  o n  three  d a ta sets (Tab le 1),  ex cep t  b y Ca p e lli[1 ]  t h at repo rted averag e search  ti me ab ou t 70 m s ,   134m s, and 71m s, each for FVC200 0  DB2, FVC2000  DB 3, and FVC 2002  DB1, runni ng  on a n  Intel  Co r e  2   Q u ad   CPU  @ 2.66   G H z . A ltho ugh  it can no t b e   directly com p a r ed, howe ver,  that result can  be   use d  as a refe r e nce t o  m o t i v at e im provem e nt  of t h e p r op os ed st rat e gy .  As  sho w n by  M a t c her at  Fi g u r e7 ,   avera g e sea r c h  t i m e cond u c t e d by  t h e  p r o p o sed  st rat e gy  i s  ab o u t  2 47m s, 7 56m s, an d  27 8m s for   FV C200 0 D B 2, FV C20 0 0   D B 3 ,  and  FV C 2 002   D B 1 ,  r e sp ect iv ely.  2.   To  co m p lete in tern al co m p arison   p e rsp ecti v e,  Fi gure 7  also s h ows a v erage sea r c h  time com p arison  bet w ee n Pre -fi l t e r and Pre -fi l t e r*;  M a t c her  and M a t c her *  am ongst  t h r ee di ffe rent  d a t a  set s . Sam e   te m p late d a ta (resu lt of  fingerprin t   feature ex trac t i o n  p r ocess )   was  us ed t o  p r ovi de  rel a t i v el y  sa me  in fo rm atio n  as an  inpu t to  t h e  p r o p o s ed  strateg y   w ith   dif f e r e n t  conf igu r ation   ( s ear ch  op tion )  du r i ng  expe ri m e nt . O n  F V C 2 0 0 0   D B 2 a n d  F V C 2 0 0 2  DB 1,  a v era g e sea r c h  t i m e  com p ari s on   ga ve  rel a t i v el y  fl at  resu lt trend .  It mean s th e p r op o s ed  strateg y   relativ ely well  ap p lied  for th ese d a ta sets ch aracteristic sin c e   t r i p l e  gr owt h  n u m b er of i m pressi ons  on sea r ched -i n d e x  di d  not  m a ke average searc h  t i m e  t r i p l e  l onge r,   in  co m p arison  b e tween  Pre-fi lter an d  Pre-filter*   (Pre-filter*  on  FVC20 00 DB2  and  FVC2 002  DB1   g a v e   ad d ition a l av erag e search  time abo u t  1.6 %  an d -2 .7 %,  respectiv ely), or  between Matcher an d Match e r*  ( M atch er*   o n   FV C200 0   D B 2 an d   FV C 2 002 D B 1   g a v e  additio n a l av er ag e sear ch  tim e a b ou t 44 .5 % and   16.9%, re spect ively). On  FVC2 000  D B 3 ,  av e r ag e  s e ar c h   ti me   co m p ariso n   g a v e  relativ ely sub - lin ear  resul t  t r en d, a nd al s o , t r i p l e  gr owt h  n u m b er of i m pressi ons  o n  searc h ed-i nde x di d n o t   m a ke avera g e   search  tim e tri p le lo ng er, in  co m p ariso n   b e t w een   Pr e-filter an d  Pre-filter* (P re-filter*  on  FVC200 0  DB 3   gave a dditiona l average sea r ch tim e  about 32.5% ),  or between Matcher and Matcher* (Matc h er* on  FVC200 0 DB 3 g a v e  ad d ition a l search i n g time abo u t   12 6.7%).      Evaluation Warning : The document was created with Spire.PDF for Python.
                        I S SN :  2 088 -87 08  I JECE Vo l. 4 ,  N o . 5 ,  O c tob e r  20 14   :   817  –  8 30  82 6     Fi gu re  7.  A v er age sea r ch  s p e e d c o m p ari s on   of  t h e  pr o p o s e d  st rat e gy  ba se d  on  n u m b er  of  im pressi o n   fr o m   sam e  fi nger t h at  was  use d   fo r  i nde x c r eat i o n .       3. 4. Mem o r y  Usa g e C o mp a r i s on   As one of  t h e efficiency perform ance  consi d eration  besi d e  spee d,  i t  i s  a l so  not   p o ssi bl e t o  m a ke a  syste m atic  m e m o ry usage c o m p arison like   accuracy c o m p arison because of  differ e n t hardwa re platforms.  1.   Thi s  sect i o n  o n l y  desc ri bes i n t e r n al   com p ari s on , a m ongst  t h ree  di f f ere n t   da t a  set s ,  bet w een  inde xingproces s  (Section 2 Point 2)  usi n g fingerpri n t’s  first im pr ession from  each finge r for inde x  creation (refe r red as the Inde xing),  and usi ng fi ngerpri n t’s first thr ee impressi ons from each finger for  i nde x creat i o n  (re fer r ed as t h e In de xi n g * ) .  Thi s  i n t e r n al  c o m p ari s on  su p pos es t o   gi ve  m o re pers pect i v e  of  t h e  pr o p o s e d  st rat e gy .   2.   C o m p ari s on  u s es t w o di ffe r e nt  co nfi g u r at i ons  ab o v e ( I n dexi ng  an d  In dexi ng * )  bec a u se t h ey  a r e i n   accorda n ce to the pre v ious  expe rim e ts. T h e Inde xing  process prec ede s  the Pr e-filter, Matcher, and  Match e r2,  wh il st th e Ind e x i n g *   p r o cess preced es t h e Pre-filter* , Match e r* , and  Match e r2* .   3.   Thi s  i n de xi n g p r o cess  (I n d ex i ng a n d  I nde x i ng *)  req u i r e d  cert a i n  am ou nt  o f  m e m o ry du ri n g  sy st em   ru n n i n g f o r  ha sh-t a b l e - b ased  searc h ed i n d e x. M e m o ri es  were  occ upi e d  by  ha sh -key s  an d i t s  rel a t e d   retriev e d  ob j e cts (ele m e n t s) t h at co n s t r u c t th at h a sh-tab le.  A h a sh -k ey h o ld s its ele m en ts in  a  lis t  if  th ere  is  co llisio n   (a  hash-key has   m o re than  oneele m ent). A  ha sh -k ey was  allo cated  b y  to tal 3 2 -b it d a t a ,  con s t r uct e d  by  1 6 - b i t  ( L SB )   dat a   of  ed ge l e ngt h,  8  bi t   (bi t   23 th  - 16 th )  dat a  o f  m i nutia-re fere nce  relativ e- ori e nt at i on, a n d 8 - bi t  (M SB )  dat a  of m i nut i a -nei gh b o u r  relativ e-orien t ation .  An  elem en t  was allo cated   b y   to tal 1 04-b it  data, con s tru c ted   b y32 -b it d a t a  o f  can d i d a te  fing erp r i n t ID  in  d a tab a se, 16-b it  d a ta of edg e   len g t h, 8   b it d a ta o f  m i n u tia-referen ce rel a tiv e-orien t ation ,   8 - b it d a ta o f  m i n u tia-n ei g hbo ur relative- ori e nt at i on,  8  bi t  dat a  o f  m i nut i a - n ei g h b o u r t y pe (e ndi ng ,  bi fu rcat i o n,  o r  el se),  16 - b i t  dat a  o f  m i nut ia- r e f e r e n c e nu mb er, an d 16 -b it  d a ta of  m i n u tia- n ei g hbo ur   n u m b er .  4.   Fo r t h e n e x t  d i scu ssion , m e mo ry u s ag e co mp ariso n   will o n ly refers to  th e  n u m b e r of h a sh -k eys and  th eir  related   n u m b e r of elem en ts for an alysis si m p licit y.  5.   Fi gu re 8 s h o w s  i n creasi n g  n u m ber of  has h - k ey  ge ner a t e d  by  t h e  In de xi n g *  t o  t h e b a se  num ber  of  has h - key s  ge ne rat e d  by  t h e  I nde xi ng . T h e  In de xi ng *  ga ve i n c r e a si ng  n u m b er  of  has h - k ey s a b o u t   16% ,  19 %,   an d 12 % fo r FV C20 0 0   D B 2 ,   FV C200 0 D B 3, and   FV C 2 0 02 D B 1,  r e spectiv ely.    6.   R e l a t e d t o  Fi g u re  8, Fi gu re 9  sho w s  hash - k ey s di st ri but i o n base d  on  nu m b er of i t s  el em ent s . Up pe r- r o w   gra p hs (ge n e r a t ed by   t h e I nde xi n g )   an d  l o w e r- ro w gra p hs ( g ene r at ed   by   t h e In de xi n g * )  sho w   di st ri but i o n   perce n t a ge  of  has h - k ey  gr o u p s ba sed  on  n u m ber of i t s  el em ent s . These  h a sh- k ey  g r o u p s  were cl assi fi e d   i n t o  gr o u p   1;  2 - 1 0 ;  21 -3 0;  31 -4 0;  41 -5 0;   a n d 51 - x .  Last   gr ou p c o nt ai ns  x  ( num ber  wi t h   an ast e ri x m a rk )   that diffe rs from each data set and re pre s ent s  the bigg est num b er of elements th at could fill in the list,  rel a t e d t o  cert a i n  has h - k ey . N o t e d, c o nsecut i ve n u m b er of e l em ent s  on l a st  gr ou p ( f r o m  51 t o   x ) wa s n o t  gua ra nt eed e x i s t s  i f  c o m p ared  wi t h  t h e  ot he r  gr o ups .   7.   On t h e I nde xi ng , di st ri but i o ns o f   hash - k ey  gr ou p  1 are a b o u t  1 0 %,  1 6 % , an d 1 0 %  f o r F V C 2 0 0 0  DB 2 ,   FVC 2 0 0 0  DB 3, a n d F V C 2 0 0 2  DB 1,  res p e c t i v el y .  On  t h e  In de xi n g * ,  di st ri but i o ns  o f   has h - k ey  g r ou p  1   rel a t i v el y   n o t  chan ge d  m u ch ,  i . e.   ab o u t  9 % , 15% ,  a n d 8% fo r FVC 2 00 0 DB 2, FV C 2 0 0 0  DB 3,   a n d   Evaluation Warning : The document was created with Spire.PDF for Python.