TELKOM
NIKA Indonesia
n
Journal of
Electrical En
gineering
Vol.12, No.5, May 2014, pp
. 4079 ~ 40
9
0
DOI: http://dx.doi.org/10.11591/telkomni
ka.v12i5.5208
4079
Re
cei
v
ed
No
vem
ber 8, 20
13; Re
vised
De
cem
ber 2
9
,
2013; Accep
t
ed Jan
uary 1
9
, 2014
A Multi-Threaded Fingerprint Direct-Access Strategy
Using Local-Star-Structure-based Discriminator
Features
G. Indra
w
a
n
*
1
, B. Sitohang
2
, S. Akbar
3
, A. S. Nugroho
4
1,2,
3
Data & Softw
a
re En
gin
eer
i
ng Re
s
earch Division, ST
EI –
IT
B,
Jl. Ganesha
10
, Bandun
g, Ind
ones
ia
4
Agenc
y
for T
h
e Assessment
and Ap
plic
atio
n of
T
e
chnol
og
y
(BPPT
),
Jl. MH
T
hamrin
8, Jakarta, Indones
ia
*Corres
p
o
ndi
n
g
author, e-ma
i
l
: gindr
a
w
a
n
@l
ive.com
1
, benh
ard@stei.it
b
.ac
.
id
2
, saiful@informatika.org
3
,
asnu
groh
o@i
e
ee.org
4
A
b
st
r
a
ct
T
a
king
adv
ant
age
of
multi-t
h
rea
d
tec
hno
l
ogy
prov
i
d
e
d
by mu
lti-core
i
n
si
ngl
e proce
ssor,
this
pap
er descr
ib
es multi-thre
a
d
impl
e
m
ent
ation o
n
fing
er
print dir
e
ct-ac
c
ess strategy
using l
o
ca
l-s
t
ar-
topol
ogy-b
ase
d
d
i
scri
m
i
nator
featur
es. M
u
l
t
i-thread
w
a
s
app
lie
d for
da
ta partiti
oni
ng
on
hash
i
n
g
a
d
d
-
look
up pr
ocess
,
and for w
o
rk
partitio
n
in
g o
n
similar
i
ty
score
computati
on.
Efficiency of th
e i
m
pl
e
m
e
n
tati
on
w
a
s achiev
ed,
as confir
med
b
y
the
ex
peri
m
e
n
ts results. Us
i
ng q
u
a
d
-thr
e
a
d
of d
ual-c
ore
singl
e pr
ocess
o
r
o
n
la
st te
sts on
e
x
pe
rim
e
n
t, m
u
l
t
i
-
th
rea
d
im
pl
em
en
tatio
n
can re
duc
e a
v
erag
e searc
h
time
ab
out 1
7
%
compar
e to it
s sing
le-thre
a
d
i
m
p
l
e
m
e
n
tati
on. T
h
is res
u
l
t
w
a
s achiev
e
d
w
i
th relativ
e
ly sa
me
aver
a
ge
accuracy tre
n
d
and
has si
gnifi
cant i
m
pr
ove
m
ent by co
nsid
e
r
ing
mi
llis
eco
n
d
ord
e
r i
m
p
o
rtance
of search
in
g
process o
n
lar
ge scal
e
data.
Ke
y
w
ords
: cor
e
, direct-acces
s
, fingerpri
n
t, local-star-struct
u
re, thread
Copy
right
©
2014 In
stitu
t
e o
f
Ad
van
ced
En
g
i
n
eerin
g and
Scien
ce. All
rig
h
t
s reser
ve
d
.
1. Introduc
tion
This pap
er
is about parallel
pro
c
e
s
s
im
pl
ement
ation
a
s
a
n
imp
r
ove
m
ent of o
u
r rese
arch
on fingerpri
n
t direct
-a
ccess strategy [1]. The im
prove
m
ent accom
m
odate
s
efficiency a
s
pe
ct, i.e.
highe
r se
arching speed
without sacrifying accura
cy, related to taking adva
n
tage of run
n
in
g
algorith
m
on
multi-thre
ad
1
environm
ent of multi-co
re of
singl
e pro
c
e
s
sor.
Our re
se
arch
propo
se
d a
new meth
od i
n
a
r
ea
of
fing
erp
r
int di
re
ct-acce
ss,
wh
ose result
confirmed it
as a p
r
omi
s
ing m
e
thod
beca
u
se it can
comp
a
r
ed favorabl
y with and
even
outperfo
rme
d
other co
mpe
t
ing state-of
-the-a
r
t tech
ni
q
ues ove
r
thre
e publicly ava
ilable data se
ts
[2, 3]. For the accu
ra
cy asp
e
ct [4], up to ce
rtain
small Penet
ration Rate, this metho
d
gave
smalle
r Error
Rate compa
r
ed to other m
e
thod
s.
Relate
d to o
t
her competi
ng state
-
of-t
he-a
r
t tech
ni
que
s, in the
last de
cad
e
,
several
prop
osed fing
erp
r
int dire
ct-acce
ss
strate
gies h
a
s roug
hly classified
by [5].
a)
Global featu
r
es, e.g., average rid
g
e
-
line
frequen
cy. They are u
s
ual
ly collabo
rate
d with othe
r
feature
s
for o
b
taining
small
e
r se
arch
spa
c
e [6].
b)
Local ridg
e-li
ne orie
ntatio
ns, e.g., [6-9], other
features de
rived from
the orient
ation image,
e.g., [10, 11].
c)
Minutiae, e.g
., [12, 15]:
most indexin
g approa
che
s
ba
sed on
minutiae d
e
rive ro
bu
st
geomet
ric fe
ature
s
from triplets of min
u
tiae point
s and u
s
e ha
shing techniqu
es to perfo
rm
the sea
r
ch.
d)
Other features
obtain
ed
from the
fin
gerp
r
in
t
pattern:
s
u
c
h
as Finger Code [15], ridge
curvatu
r
e [16]
, and SIFT feature
s
[17].
e)
Matc
hing sc
ores
to build index k
e
ys
[18,
19].
1
Based on [32], a thread, o
r
thre
ad of execution,
is a softw
ar
e te
r
m
for the basic ordered sequ
ence
of instructions t
h
a
t
can be passed t
h
rough o
r
p
r
ocessed b
y
a single central proc
essing unit (CPU
) c
o
re. At the
other
side, a core is a
hard
w
a
r
e ter
m
th
at describes the number of inde
p
endent
CPUs in
a single computing component (
d
ie or chip).
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 4079 – 40
90
4080
Propo
se
d ne
w method i
s
clo
s
e to the third ap
pr
oa
ch above, but instea
d of usi
ng triplets
of minutiae p
o
ints, it used
local
-
sta
r
-stru
c
ture
asso
cia
t
ed with the
minuti
ae, an
d
then its d
e
riv
ed
feature
s
we
re u
s
ed
by h
a
shi
ng te
ch
n
i
que
s [
20] to
perfo
rm th
e
se
arch. Se
quential
a
c
cess
strategy
(o
ne
-to-o
ne
com
p
arison
) u
s
in
g
this lo
cal
-
sta
r
-structu
re
wa
s int
r
odu
ce
d f
i
rst
by Ratha
et
al. [21] and
wa
s follo
wed
by its vari
a
n
ts a
nd ev
ol
utions [
22]. In the a
r
e
a
o
f
dire
ct-a
cce
s
s
strategy, a
s
far as a
u
tho
r
’s kno
w
led
ge, ther
e i
s
still no
method utilizi
ng Rath
a’s a
ppro
a
ch.
2. Resear
ch
Method
Wo
rkin
g o
n
p
a
rallel
p
r
ocess imp
r
ovem
e
n
t of th
is ne
w meth
od, th
e re
st
of this
pape
r i
s
orga
nized
as
follows. Chap
ter 2.1
introd
uce
s
th
e p
r
o
p
o
se
d di
re
ct
-a
cc
es
s
st
r
a
t
e
g
y
,
comp
ris
e
d
of
the und
erlyin
g features e
x
tracti
on
(Ch
apter
2.2), it
s math
emati
c
al p
e
rsp
e
cti
v
e for in
dexing
pro
c
e
ss
(Ch
apter 2.3
)
, retrieval p
r
o
c
ess (C
ha
pte
r
2.4-2.5), a
nd candi
dat
e-list
red
u
cti
o
n
mech
ani
sm
(Ch
apte
r
2.6
)
. Cha
p
ter 3
explains
de
s
i
gn
fo
r
p
a
r
a
lle
l pr
oc
ess
(
m
u
l
ti-
t
h
r
ea
d
)
impleme
n
tation. Chapte
r
4 de
scri
be
s
experim
ents
on p
ubli
c
d
a
t
a set,
com
p
are
multi-th
re
ad
impleme
n
tation to its
sin
g
le-th
r
ea
d im
plementat
io
n. It describ
es the pe
rform
ance evalu
a
tio
n
(Ch
apte
r
4.1
)
, pa
ram
e
ters
calib
ration
(Cha
pter 4.
2), a
nd
co
m
pari
s
on
resul
t
(Chapte
r
4
.
3).
Finally, Chapt
er 5 draws th
e con
c
lu
sio
n
.
2.1. Direct-Acces
s Stra
te
g
y
Figure 1 sh
o
w
s bl
ock dia
g
r
am of dire
ct
-acce
ss
strate
gy for fingerp
r
int data.
Figure 1. Pro
posed blo
c
k diagram of dire
ct-a
cce
ss
st
rategy for fing
erp
r
int data.
a)
The
con
s
truction was co
mpri
sed
of in
dexing
and
retrieval p
r
o
c
ess. It co
nsi
dere
d
g
ene
ra
l,
whi
c
h me
an
s it can al
so
b
e
appli
ed for other
kin
d
o
f
data that try to accompli
sh
sea
r
ch in
dire
ct-a
cce
s
s fashion.
b)
Indexing p
r
o
c
ess was
ba
se
d on h
a
shing
functi
on
with i
t
s mathem
atical p
e
rspe
cti
v
e (Chapte
r
2.3) co
nst
r
u
c
ted by three di
scrimin
a
tor at
tributes
(Figu
r
e 2).
c)
Retrieval process will output subset
N
T
of
N
can
d
idate
s
from
database, whe
r
e
N
T
are
can
d
idate
s
wi
th top si
milari
ty sco
re
i
n
de
scendi
ng-ord
e
red
fashion,
and id
eally
N
T
<<
N
and
it
inclu
d
e
s
right
search
ed ca
ndidate.
d)
Retrieval p
r
o
c
e
ss
wa
s co
n
s
tru
c
ted by pre-filt
er sta
ge
and matche
r stage. Pre
-
filter stag
e wa
s
based o
n
relative fast-in
a
c
curate
pre-fi
lter-s
core
co
mputation
(Chapter 2.4),
while m
a
tch
e
r
stage
wa
s ba
sed o
n
relativ
e
slo
w
-a
ccu
r
ate
matche
r-score co
mputa
t
ion (Ch
apte
r
2.5).
e)
Retrieval pro
c
e
ss ca
n
be consi
dered
a
s
multi-
sta
ge
score comp
uta
t
ion, whe
r
e p
r
e-filter
stage
is its first sta
ge an
d matcher
stage i
s
i
t
s se
co
nd
sta
ge. First stag
e will out
put
desce
nding
-
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Multi-Thre
a
ded Fing
erpri
n
t Dire
ct-A
ccess Strateg
y
Usi
ng… (G. Indra
w
a
n
)
4081
orde
re
d-score candi
date
-
l
i
st, while se
con
d
stage
will output final update
d
can
d
idate
-
list
,
whi
c
h ha
s ne
w update
d
score (in d
e
sce
nding
-o
rde
r
e
d
fashion too
)
that come from weig
hted
sum
of pre
-
fil
t
er sco
r
e
(Ch
apter 2.
4) a
n
d
ma
tcher score (Chapte
r
2.5).
Weighti
ng
value was
optimally determin
ed thro
ugh lea
r
nin
g
pro
c
e
ss o
n
training d
a
ta (Cha
pter 4.2
)
.
f)
R
e
tr
ie
va
l p
r
oc
es
s us
es
mu
lti-
s
t
a
g
e
c
a
nd
id
a
t
e-li
st red
u
ction
me
cha
n
ism to
finall
y
outputs
N
T
can
d
idate
s
(Cha
pter 2.6
)
.
Figure 2 illustrates
a st
ruct
ure of
a local
-
star (circle
with das
hed-line) associ
ated with a
minutiae of two different fingerpri
n
t imp
r
essi
o
n
s, respectively. So, if a fingerpri
n
t has
n
min
u
tiae,
it will have
n
local
-
sta
r
stru
cture
s
. Zo
o
m
ed recta
ngl
e area
sho
w
s an ed
ge, wh
ich
con
s
tru
c
t
s
a
local
-
sta
r
stru
cture, with its three discri
m
i
nator attribut
es (
sd
( ),
β
i
,
β
j
), used by p
r
opo
se
d dire
ct-
ac
ce
ss st
rat
e
gy
.
sd
( ) is e
dge len
g
th,
β
i
is relative o
r
ientation of
minutia-refe
r
ence, and
β
j
is
relative ori
e
n
t
ation of minutia-nei
ghb
ou
r. Rela
tive orientation is t
he angl
e differen
c
e b
e
tween
minutia’s ab
solute
angl
e
to the e
d
g
e
’s a
b
solute
angle. Ab
solute an
gle i
s
the
angl
e
with
referen
c
e to the hori
z
o
n
tal line.
Figure 2. Left: structure of a local
star (circle
with dashed-li
ne) associated with a minutia, each
belon
gs to lef
t
-pro
be an
d ri
ght-candi
date
(a ma
tchi
ng
pair). Right: minutiae o
r
ie
ntation from
feature
s
extra
c
tion for: endi
ng type
(top);
bifurcatio
n type (bottom
)
Based o
n
Fig
u
re 1 an
d Figure 2, math
ematic
al p
e
rspective of propo
sed di
re
ct-acce
ss
strategy,
wo
uld b
e
ap
pli
ed o
n
: index
ing p
r
o
c
e
s
s
(Ch
apte
r
2.3
)
, pre-filter stage of
retri
e
val
pro
c
e
ss
(Ch
apter 2.4
)
, matche
r
stag
e of re
trieval
pro
c
e
ss (Chapter 2.5), and candi
dat
e-list
redu
ction m
e
cha
n
ism a
ppli
ed on ret
r
ieva
l process (Ch
apter 2.6
)
.
2.2. Featur
e Extrac
tion
Propo
se
d direct-a
cce
ss
strategy wa
s run
u
nde
rl
ying pre
c
e
d
ed feature
extraction
process (block Extractor in Fi
gure 1) based on minutiae detecti
on algorithm [23, 24], utilizing
algorith
m
of smoothi
ng, bi
nari
z
ation, an
d thinning
[2
5], where the
type, the coordin
a
te location
and the
o
r
ien
t
ation of the
ridge at
ea
ch
minutiae
poi
n
t
are
re
co
rde
d
. A minutia
orientatio
n i
s
an
absolute an
gl
e (refer to ho
rizo
ntal line a
nd c
ounte
r
-cl
o
ckwi
se in
cre
a
se
d angl
e).
A ridge
-en
d
in
g
orientatio
n
i
s
comp
uted by measuri
ng
a
n
ab
solute
ang
le of the li
ne
starting
at th
e minutia
poi
nt
to the mi
ddle
of the
ridg
e.
A ridg
e-bifurcation o
r
ie
ntation i
s
com
put
ed by
mea
s
u
r
ing a
n
ab
solu
te
angle
of the li
ne
starting
at
the min
u
tia
point to
the
middle
of the
valley betwe
en the
bifurcating
ridge
s.
The minutiae plotted in previous Figure 2
illustrate the line to
whi
c
h the angle of
orientatio
n i
s
mea
s
u
r
ed.
Each
minutia
point i
s
rep
r
ese
n
ted
by a
circle
o
r
squ
a
re, a
nd th
e
line
from the ci
rcl
e
or squa
re i
s
either the ri
d
ge endi
ng’
s ri
dge, or the
ri
dge bifu
rcatio
n’s valley. In the
illustratio
n
, the ori
entatio
n angle
marked
as
“A
” i
s
the ANSI/
N
IST stan
da
rd. Angle
“B” as
FBI/IAFIS standard angl
e was us
ed for
this proposed di
rect
-access strategy.
2.3. Indexing
Process
Based o
n
Figure
2, local
-
star
stru
cture
c
an be
rep
r
ese
n
ted by u
s
ing g
r
ap
h n
o
tation.
The
st
a
r
a
s
sociate
d
with
the minutia
m
i
for a given maximum
distan
ce
d
max
and maxim
u
m
neigh
bou
r
n
max
is the grap
h S
i
S
i
= (V
i
, E
i
)
(
1
)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 4079 – 40
90
4082
Con
s
i
s
ting of:
a)
The set of vertice
s
V
i
co
ntaining le
ss than or
equ
al to
n
max
minutiae
m
j
whos
e
spatial di
stan
ce
sd
( ) fr
om
m
i
is
les
s
than or equal to
d
max
.
V
i
= {
m
j
|
n
(
m
j
)
≤
n
max
and
sd
(
m
i
,
m
j
)
≤
d
max
}
(
2
)
b)
The set of ed
ges E
i
E
i
= {
e
ij
}
(
3
)
Whe
r
e
e
ij
is t
he edg
e co
nn
ecting min
u
tia
m
i
with minutia
m
j
in V
i
;
e
ij
is labele
d
with a 6-tupl
e
(
id
,
i
,
j
,
sd
(
m
i
,
m
j
),
β
i
,
β
j
), where
id
is a finge
rpri
nt
identifie
r
in databa
se,
β
i
is relative orientatio
n of
m
i
to
e
ij
, and
β
j
is relative o
r
ie
ntation of
m
j
to
e
ji
.
Based
on
Eq
uation
(1
), fo
r h
a
shing
sy
stem
of ind
e
x
ing p
r
ocess (Fig
ure 1
)
, t
here
i
s
a
s
e
t:
H
i
= {
h
ij
}
(
4
)
a)
h
ij
is labele
d
with a 1-tupl
e (
h
), where
h
is a po
sitif numbe
r, whi
c
h is an outp
u
t
of
hashing
func
tion
h
(S
i
) a
n
d
c
o
ns
ide
r
ed
as
a
ke
y
fo
r d
a
ta st
ru
cture
hash-tabl
e.
V
a
lue
asso
ciat
ed
with this
key
, r
e
pr
es
e
n
t
s
S
i
.
b) Ha
shin
g
funct
i
on
h
(S
i
)
d
e
fin
ed by:
S
∙2
∙2
∙2
(
5
)
k
i
s
a
po
sitif numbe
r that
rep
r
e
s
ent
s n
u
mbe
r
of g
e
nerate
d
buckets
(
ke
y
s
)
a
s
so
ciat
ed
with input dat
a that is goin
g
into
hashin
g
function, where the
r
e i
s
a set:
K =
{
k
|
k
ϵ
P
,
k
≤
|A|
+
|B|
+
|C|}
(6)
x
i
is
an inte
ge
r num
ber th
at rep
r
e
s
ent
s
bu
ck
e
t
(
ke
y
)
a
s
soci
ated
with input d
a
ta, i.e. edge
length,
sd
( ), that is
going into
hashing
f
unctio
n
, whe
r
e there is a
set:
A =
{
x
i
|
x
i
ϵ
Z
,
,
∆
/∆
,
∆
/∆
}
(
7
)
y
i
is a
n
integ
e
r num
be
r th
at rep
r
esents
bucket
(
ke
y
) asso
ciated
with input d
a
t
a, i.e.
relative o
r
ie
ntation of
minut
ia-refere
n
ce,
β
i
, that is
goi
ng into
ha
shi
ng
fun
c
tion,
whe
r
e
there i
s
a
s
e
t:
B =
{
y
i
|
y
i
ϵ
Z
,
∆
/∆
∆
/∆
}
(
8
)
z
i
is a
n
integ
e
r num
be
r th
at rep
r
esents
bucket
(
ke
y
) asso
ciated
with input d
a
t
a, i.e.
relative o
r
ient
ation of min
u
tia-nei
ghb
our,
β
j
, that is goi
ng into
h
a
shi
ng
fun
c
tion,
whe
r
e th
ere i
s
a
s
e
t:
C = {
z
i
|
z
i
ϵ
Z
,
∆
/∆
∆
/∆
}
(
9
)
∆
is an intege
r numbe
r, rep
r
ese
n
ts maxi
mum tolera
nce of
sd
(
m
i
,
m
j
)
∆
is an intege
r numbe
r that repre
s
e
n
ts ma
ximum tolera
nce of
β
i
,
β
j
c)
Colli
sion
in
h
a
shi
ng
syste
m
was a
c
com
odated
by
usi
ng d
a
ta
stru
ct
ure
list
co
ntai
ning
input data S
i
with the s
a
me
bucket
(
ke
y
).
2.4. Pre-filter
Stage of
Retrie
v
a
l Process
Based
on Eq
uation (1), Fi
gure
3 sho
w
s a g
r
ap
h-pa
ir (p
rob
e
-
an
d ca
ndid
a
te- grap
h)
whi
c
h wa
s
use
d
to co
mpute simila
rity sco
re
[23, 26, 27]
of matchi
ng
-pair. This
score
comp
utation
algorith
m
wa
s con
s
ide
r
ed
relatively
slo
w
but a
c
cura
te, and was
use
d
by the
next
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Multi-Thre
a
ded Fing
erpri
n
t Dire
ct-A
ccess Strateg
y
Usi
ng… (G. Indra
w
a
n
)
4083
Matche
r Stag
e of Retri
e
va
l Process (Chapter
2.5)
. I
t
need
s to m
ention ea
rlie
r, to sho
w
ho
w
relatively fast but inaccu
rat
e
score
com
p
utation algo
rithm wa
s built on it.
Relatively slow-accu
r
ate
score
comp
u
t
ation
alg
o
rit
h
m will
work o
n
g
r
ap
h-pair, i.e.
prob
e-gra
p
h
and
candi
date-g
r
a
ph,
each h
a
s
its lo
nge
st-ed
ge by
num
ber of
(po
s
sibly
discontin
ued
) edge
s. Th
ro
ugh thi
s
grap
h, the ma
xim
u
m sco
r
e
wa
s comput
ed (Cha
pter 2.5
)
.
The
con
s
tru
c
tion
of the-lon
g
e
s
t-edge
-p
air of
grap
h-p
a
ir
p
a
ssed th
rou
g
h vertex- o
r
minutia-pair, i
.
e
.
one p
r
ob
e m
i
nutia an
d o
ne candi
date
minutia.
Sel
e
cted minuti
a
-pai
r wa
s
b
a
se
d
on ce
rt
ain
simila
rity ran
ge of comp
ari
s
on of its thre
e discrimi
nat
or attribute
s
(Figure 2).
On
the oth
e
r side, rel
a
tively
fast-i
naccu
rate score com
put
ation
alg
o
rit
h
m
ju
st
accumul
a
te its sco
r
e from
numbe
r of
co
rre
sp
ond
en
ce
con
n
e
c
ted-e
dge
s-p
a
ir (p
robe con
n
e
c
te
d
-
edge an
d ca
ndidate conn
ected
-
ed
ge
). Con
n
e
c
ted-
e
dge-pai
r wa
s const
r
u
c
ted
by two or three
prob
e’s e
dge
s for probe
conne
cted
-ed
g
e
, and by tw
o or thre
e ca
ndidate’
s edg
es for candi
d
a
te
con
n
e
c
ted-ed
ge. Counte
d
co
nne
ct
ed
-edge
-pai
r
was
ba
sed
o
n
certain
si
milarity ra
ng
e of
comp
ari
s
o
n
o
f
its three
discrimi
nator attributes (F
i
g
u
r
e
2). E
quation
(10
)
d
e
scribe
s
thi
s
relativel
y
fast-ina
ccu
r
at
e score co
mputation of
a matc
hi
ng
pair (pro
be
and candi
d
a
te), whi
c
h
is
con
s
tru
c
ted
by numbe
r of its conn
ecte
d-ed
ge
-pai
r from two edg
e
s
,
, and by numbe
r of its
con
n
e
c
ted-ed
ge-p
a
ir fro
m
three e
dge
s,
.
∙
(
1
0
)
Whe
r
e:
a)
is e
qual to
|
E
| (ca
r
di
nality of the set of ed
ges
E
), w
h
e
r
e
E
wa
s comp
ute
d
on
the set of edg
es E
i
(Equati
on 3), such th
at:
,
|
AND
AND
AND
,
′
,
′
∆
AN
D
|
′
|∆
AND
|
′
|
∆
AN
D
|
,
′
,
′
|
∆
AN
D
|
′
|
∆
AND |
′
|
∆
(11)
b)
is e
qual to
|
E
| (ca
r
di
nality of the set of ed
ges
E
), w
h
e
r
e
E
wa
s comp
ute
d
on
the set of edg
es E
i
(Equati
on (3
)), such
that:
,
,
|
AND
AND
AND
AND
A
N
D
|
,
′
,
′
|
∆
AN
D
|
′
|∆
AND |
′
|
∆
AND
|
,
′
,
′
|
∆
AN
D
|
′
|
∆
AN
D
|
′
|
∆
AND |
,
′
,
′
|
∆
A
ND
|
′
|
∆
&
|
′
|
∆
OR
|
,
′
,
′
|
∆
AN
D
|
′
|
∆
AN
D
|
′
|
∆
(
1
2
)
c)
For p
o
int 2 a
nd 3,
p
rep
r
e
s
ent
s
p
r
obe,
c
represents
can
d
idate,
∆
d
and
∆
β
r
e
pr
es
e
n
t
s
maximum toleran
c
e fo
r rel
a
ted variabl
e (Ch
apte
r
2.3).
d)
is weightin
g
of
whi
c
h i
s
d
e
termin
ed through th
e lea
r
ning p
r
o
c
e
ss
on traini
ng
data (Chapte
r
4.2).
2.5. Match
e
r Stage o
f
Re
trie
v
a
l Process
Equation (1
3
)
de
scribe
s re
latively slow-acc
urate sco
r
e com
putatio
n, which was
applie
d
on
matchi
ng grap
h-pair (Fi
gure
3
)
.
s
M
= max
(S
M
)
(
1
3
)
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 4079 – 40
90
4084
Figure 3. Ca
se of False
Re
ject (F
R) of a
matc
hin
g
pai
r, i.e. probe (le
ft) and ca
ndid
a
te (rig
h
t),
whe
r
e the alg
o
rithm compu
t
es simila
rity scor
e o
n
wro
ng fingerpri
n
t area
(squa
re
area
with
dash-lin
e). Neverthele
s
s, it shows ho
w the algo
rithm
works to pro
d
u
ce the lo
nge
st-ed
g
e
-
pai
r
(each bel
ongs to probe and cand
idate) that will be used for rel
a
tively slow-accurate score
comp
utation.
Whe
r
e
s
M
is e
qual to maximum value of
s
k
on set S
M.
S
|
ϵ
,
∑
∙
(
1
4
)
k
is po
sitive numbe
r,
N
is n
u
mbe
r
of involved matchin
g
variable
s
,
v
i
is individual
score of
a matchi
ng variabl
e, and
w
i
is weighti
ng of
v
i
,
whi
c
h is d
e
termi
ned by lea
r
n
i
ng pro
c
e
s
s
on
training d
a
ta (see
Cha
p
ter
4.2). As sh
own
by Figure 3,
involved matchin
g
variabl
es,
v
, are:
a)
Numb
er of m
i
nutia-p
air,
o
ne mi
nutia f
r
om
p
r
ob
e-gra
ph a
n
d
one
correspon
ding
minutia
from
can
d
idate
-
g
r
a
ph (seven mi
nutia-p
airs a
s
sho
w
n by Figure 3
)
.
b)
Numb
er of re
petition found
of minutia-p
air t
hat co
nst
r
uct the lo
ng
est-e
dge
of graph
-p
air (not
visible by Fig
u
re 3
)
.
c)
Numb
er of e
dge-pai
r that con
s
tru
c
t the longe
st-e
dge
of graph
-pai
r (six edg
e-p
a
irs as sho
w
n
by Figure 3
)
.
d)
Numb
er of mi
nutia-p
airs th
at have sam
e
type
of minutia (as
sho
w
n
by Figure 3,
minutia-pair
numbe
r
3
was
not
cou
n
ted
sin
c
e it
s
prob
e-mi
nutia
of left g
r
ap
h is type En
ding
and
it
s
corre
s
p
ondin
g
can
d
idate
-
minutia of rig
h
t graph i
s
type Bifurcation
)
.
e)
Accu
mulatio
n
of the differ
ence of e
dge
-length
bet
we
en p
r
ob
e-
e
d
g
e
of probe
-g
raph a
nd it
s
corre
s
p
ondin
g
candid
a
te-edge
of
can
d
idate-gr
aph
asso
ciate
d
with the
lon
gest-edg
e o
f
grap
h-pair
(n
ot visible by Figure 3
)
.
f)
Accu
mulatio
n
of the difference of relati
ve
orie
ntatio
n between
m
i
nutia
-referen
ce of
pro
be-
grap
h an
d its correspon
ding min
u
tia
-refe
ren
c
e
of candi
date
-
g
r
aph
asso
cia
t
e with the
longe
st-e
dge
of graph
-p
air
(not visible by
Figure 3
)
.
g)
Accu
mulatio
n
of the difference of relati
ve
orientatio
n betwe
en m
i
nutia-n
eigh
b
our of p
r
ob
e-
grap
h a
nd it
s
corre
s
p
ond
ing min
u
tia-
neigh
bou
r of
ca
ndid
a
te-g
raph
a
s
soci
a
t
e with th
e
longe
st-e
dge
of graph
-p
air
(ca
nnot sho
w
n by Figure 3
)
.
h)
Fra
c
tion of minutia-p
airs eq
uals to avera
ge va
lue of fraction of prob
e-min
u
tiae an
d fraction o
f
can
d
idate
-
mi
nutiae. F
r
a
c
tion of p
r
o
be-minutiae
equ
als
to ratio of
numb
e
r of
p
r
obe
-min
utia
e
(that co
nstru
c
t the longe
st-ed
ge of p
r
obe
-g
ra
p
h
) t
o
the total numbe
r of p
r
obe
-min
utia.
Fra
c
tion
of
can
d
idate
-
mi
nutiae
equ
al
s to
ratio
o
f
numb
e
r of
ca
ndid
a
te-minutiae
(th
a
t
con
s
tru
c
t the
longe
st-e
dg
e of can
d
ida
t
e-graph
)
to the total nu
mber of
can
d
idate-minuti
a
.
Re
spe
c
tively, numbe
r of probe-minutiae
and nu
mbe
r
of can
d
idate
-
minutiae that
con
s
tru
c
t the
longe
st ed
ge
of gra
ph
pai
r, is e
qual
s t
o
num
ber
of
minutia-pai
r, i.e.
seven, as sho
w
n
by
Figure 3.
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Multi-Thre
a
ded Fing
erpri
n
t Dire
ct-A
ccess Strateg
y
Usi
ng… (G. Indra
w
a
n
)
4085
2.6. Candida
te List
Redu
ction
Casca
de ca
ndidate
-
list (CL)
redu
ctio
n mech
ani
sm through t
w
o ste
p
pro
c
e
ss, was
applie
d for retrieval
pro
c
ess
(Figu
r
e
1). T
he firs
t
step
wa
s ap
plied to
p
r
e-fi
lter
stage
an
d th
e
se
con
d
one f
o
r matcher
st
age.
a)
The first ste
p
,
by applying
variable t
h
re
s
hold o
n
sco
r
e ratio [2
8]. Given a
data
base
of
N
candid
a
te fingerprint
s
and a q
u
e
r
y (probe
) finge
rprint, let CL f
r
om p
o
int 1, i.e. {(id
k
,
)},
k
= 1,
…,
n
, be
the sorted
list
of
n
initial
ca
ndidate
s
with
0
<
n
≤
N
. E
a
ch
CL ele
m
ent con
s
ist
s
of
a
databa
se fing
erp
r
int identifier id
k
and a score
, where
. A redu
ction criterio
n retain
s
the firs
t
n
R
ca
ndidate
s
of CL, whe
r
e the
numbe
r
n
R
(0
≤
n
R
≤
n
) i
s
d
e
termin
ed on
the basi
s
of the
score
s
in CL itself. Variable
thresh
old
on
score
ratio gi
ven by the equation bel
ow:
min
1
,
,
0
(
1
5
)
Whe
r
e:
|
′
,
(
1
6
)
′
m
a
x
1,
.
,
1
,
0
1
b)
The se
con
d
step,
by simp
ly
trunc
ating
CL from
poin
t
2 to b
e
com
e
N
T
if
CL length
longe
r than
N
T
. If CL length
shorte
r o
r
sa
me length tha
n
N
T
, nothing
will be truncat
ed.
3. Multi-Thread Design
To be
abl
e
to de
sign
pa
rallel
(multi-t
hrea
d) proce
s
s [29], we
need
to un
d
e
rsta
nd
memory obj
ects operation in process. Figure
4 illustrated several im
proved m
e
mory obj
ect
s
,
prelimi
nary
st
udied
by [23,
30], that con
s
truct
s
p
r
op
osed di
re
ct-a
ccess p
r
o
c
e
s
s
blocks (Figu
r
e 1)
and imple
m
e
n
t several
su
pportin
g
data
stru
ctures [31
]
.
Figure 4. Memory Obje
cts Con
s
tru
c
tion
in Propo
sed
Dire
ct-acce
ss Strategy
Figure 5 illust
rates m
u
lti-thread de
sig
n
b
a
se
d on tho
s
e memory obj
ects fun
c
tion
ality.
a)
Multi-thre
adin
g
wa
s applie
d both to indexing
and retrieval pro
c
e
s
s that con
s
truct pro
p
o
s
e
d
dire
ct-a
cce
s
s strategy (Fi
g
ure 1
)
.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 4079 – 40
90
4086
b)
There are two types of thr
ead involved,
i.e. thread fo
r data
p
a
rtitio
ning (appli
e
d
to indexing
and ret
r
ieval),
and threa
d
for wo
rk partiti
oning (appli
e
d to retrieval
only).
c)
Step 1, at in
dexing proce
ss a
nd retri
e
val process, use
s
multi-
th
read for const
r
uctio
n
of 2D
data-a
r
ray (Equation (1)), related to co
mputati
on an
d orde
ring of
relatively slow-accu
r
at
e
simila
rity sco
re (Equatio
n (13)) by
Step 4 at retrieval
pro
c
e
ss.
d)
Step 2
usi
n
g
multi-th
read
for p
r
o
c
e
s
s a
t
has
h-ta
ble (Equation (4
))
with data (E
quation
(5
))
addition a
nd l
ookup a
c
tivity related to ind
e
xing
pro
c
e
s
s and retrieva
l process, re
spectively.
e)
Step 3 at retrieval pro
c
e
ss using
multi-t
h
rea
d
rel
a
ted
to comp
utation and
orderi
ng rel
a
tively
fast-ina
ccu
r
at
e simila
rity
score (Eq
uation
(10)).
Figure 5. Multi-thre
adin
g
in Propo
se
d Direct-a
cce
ss St
rategy: indexi
ng (left) an
d retrieval (ri
ght).
Step 1 at both side, con
s
tructs 2
D
data
-
array fo
r com
puting & ord
e
r
ing relatively slow-a
ccurate
score by Step
4 at retrieval side. Step 2 a
t
both side rel
a
ted to can
d
i
dates h
a
sh table add
-
lookup a
c
tivity. Step 3 at r
e
trieval sid
e
relat
ed to com
puting an
d orderin
g rel
a
tively fast-
inac
cu
rate s
c
o
re
4. Results a
nd Analy
s
is
This
ch
apte
r
de
scribe
s
e
x
perime
n
t ca
rrie
d
out to
comp
are mul
t
i-threa
d
to it
s
single-
thread
impl
e
m
entation
of
propo
se
d
dire
ct-a
cc
e
s
s strategy
(Cha
pter 4.3
)
. It is a
C#
impleme
n
tation, runnin
g
o
n
a
2.40
-G
Hz Intel Co
re 2
Quad
CP
U [3
2]. The
experi
m
ent
wa
s b
a
s
ed
on direct-access pe
rform
a
nce eval
uatio
n (Chapte
r
4.
1) u
s
ing o
p
timized
algo
rithm’s p
a
ra
met
e
rs
throug
h lea
r
ni
ng pro
c
e
s
s o
n
sep
a
rate
d trainin
g
data (Cha
pter 4.2
)
.
4.1. Perform
a
nce Ev
aluation
4.1.1. Accur
a
c
y
The a
c
cu
ra
cy perfo
rman
ce
of finge
rprint di
re
ct-a
ccess [4]
ap
proa
ches is
typically
evaluated
by rep
o
rtin
g the
trade
-off b
e
twee
n Er
ro
r Rate (E
R)
and
Penetration
Rate
(PR). T
h
e
Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM
NIKA
ISSN:
2302-4
046
A Multi-Thre
a
ded Fing
erpri
n
t Dire
ct-A
ccess Strateg
y
Usi
ng… (G. Indra
w
a
n
)
4087
ER is d
e
fine
d as th
e pe
rcenta
ge of
searche
d
fi
ng
erp
r
ints th
at are n
o
t foun
d. The PR i
s
the
portion
of th
e datab
ase t
hat the
syste
m
ha
s to
se
arch o
n
the
averag
e (co
r
resp
ondi
ng to
the
averag
e lengt
h of the candi
date lists).
In this
ben
chmark
are
a
, the ER/P
R
trade
-off d
epen
ds on
a pa
ram
e
ter (Max
PR
)
controlling
th
e maximum
portion
of da
tabase to
b
e
con
s
id
ered:
the ER/PR i
s
cal
c
ulate
d
f
o
r
Max
PR
values in the ran
g
e
[1%, …, 100%]. Each value of Max
PR
corre
s
po
nd
s to a maxim
u
m
numbe
r of
candid
a
tes M
a
x
C
= Max
PR
· N
DB
, w
her
e
N
DB
i
s
th
e total numb
e
r of data
b
a
s
e
fingerp
r
int
s
: if a candi
date l
i
st is long
er t
han Max
C
, only the firs
t Max
C
candidate
s
are con
s
ide
r
ed
to calculate the co
rrespon
ding PR an
d ER values.
Figure 6
sh
o
w
s the
pseud
o-code
de
scri
bes the
pro
c
e
dure
in
detail.
Note
that the
length
of the candi
date list
pro
duced by
an
algo
rithm
can be
differe
nt for e
a
ch
query. A
sho
r
ter
candidate list
will
results i
n
lo
wer PR values, but m
a
y produce
more errors,
hen
ce thi
s
aspect
sho
u
ld be
carefully con
s
ide
r
ed [33, 28].
Let
C
i
= {
ID
i
,1
,
ID
i
,2
, …,
ID
i,Ni
} be th
e list
o
f
candi
dates r
e
turne
d
b
y
th
e al
gorithm
fo
r the
i
th
q
uer
y
(contai
nin
g
N
i
c
and
idat
es)
Fo
r
Max
PR
=
1
to 100
// Average PR consi
deri
ng at
most
Max
PR
% cand
idat
es
PR
(
Max
PR
) =
,
// Average ER consi
deri
ng at
most
Max
PR
% cand
idat
es
ER
(
Max
PR
) =
,
,
End F
o
r
w
h
er
e:
// Actual length
of the i
th
candi
date list cons
id
erin
g at most
Max
PR
% cand
i
dates
L
(
i
,
Max
PR
) =
,
,
Err
(
i
,
L
) =
1
0
Figure 6. Pse
udo-co
de of Perform
a
n
c
e
Evaluat
ion G
eneration for
Propo
se
d Direct Acce
ss.
4.1.2. Efficie
n
c
y
Efficiency in
clude
s sp
eed
and scal
abilit
y aspe
cts. B
a
se
d on [4, 5
], speed p
e
rf
orma
nce
of direct
acce
ss st
rategy i
s
ev
aluate
d
by
the flatne
ss
trend
of ave
r
age
que
ry
se
arch time
a
s
a
function of number of
candidat
es in the database. M
eanwhile,
scalability performance of
direct
acce
ss
strate
gy is eval
uat
ed with
an
a
v
erage
ER
g
r
aph
s
on a
certai
n PR a
s
a fu
nctio
n
o
f
numbe
r of ca
ndidate
s
in th
e databa
se.
4.2. Parameters Calibra
ti
on
Our di
rect-access
strategy uses hill climbing optimi
zation [34] to adjust param
e
ter
values that construct overall algorithm. Hill c
limbing is a mathematical optim
ization techni
que
whi
c
h b
e
lon
g
s
t
o
t
he f
a
mil
y
of
local
se
a
r
ch.
Lo
cal
se
arc
h
al
gorit
h
m
s
sea
r
c
h
se
v
e
ral
solut
i
on
s in
the of candi
d
a
te-solution
s
spa
c
e
by
incrementally
ch
angin
g
a
sing
le
facto
r
of th
e sol
u
tion, un
til a
solutio
n
dee
med optimal i
s
found o
r
a time boun
d is
elap
sed.
It attempts
to maximiz
e
(or minimize)
a target function
f
(
X
), wh
ere
X
i
s
a v
e
ctor of
contin
uou
s
a
nd/or di
scret
e
value
s
and
then
X
was
said to be "locally
o
p
timal"
. This p
r
opo
sed
dire
ct-a
c
c
e
s
s
strategy
atte
mpts
to mini
mize a target
function
f
(
X
), whe
r
e
X
is a
vector of di
screte
values.
a)
A separate d
a
ta set has b
een used du
ri
ng som
e
preli
m
inary expe
ri
ments to opti
m
ize vario
u
s
parameters
of the proposed appr
oach.
I
n the followi
ng, this dat
a
set will be referred
to
as
Calib
ration
DB. It is FVC2
000
DB1 A, t
he first FVC2
000
databa
se (2
)
whi
c
h
contain
s
80
0
fingerp
r
int
s
from 100 fin
g
e
rs, ei
ght im
pre
ssi
on
s pe
r finge
r, 300
x300 pixels,
500
DPI, and
captu
r
ed u
s
in
g low-co
st op
tical se
nsor
“Secu
r
e Deskt
op Scan
ne
r”
by KeyTronic.
Evaluation Warning : The document was created with Spire.PDF for Python.
ISSN: 23
02-4
046
TELKOM
NI
KA
Vol. 12, No. 5, May 2014: 4079 – 40
90
4088
b)
Both the pa
rameters of fe
ature
extracti
on
p
r
ocess
(Cha
pter 2.2
)
and the i
nde
xing-retrieval
pro
c
e
s
ses
(Chapter 2.3
- 2.5) have be
en t
uned on t
he Calib
ratio
n
DB and ha
ve been use
d
for all of the experime
n
ts d
e
scrib
ed in th
is Ch
apter 4.
c)
Optimizin
g
variou
s pa
ramet
e
rs b
a
sed on
target fun
c
tion.
∑
∙
(
1
7
)
Whe
r
e
X
is
a
vector of di
screte
pa
rame
ters
(50
p
a
ra
meters for fe
ature
s
extra
c
tion pro
c
e
s
s
and 21 pa
ra
meters for indexing-retri
e
val pro
c
ess).
i
s
t
h
e
l
o
w
e
s
t
P
R
f
o
r
E
R
≤
n
i
, with
2
0
then
m
i
(in %) = 100 / n
i
, and n
i
(in %) = {15, 13, 11, 10, 9, 7,
5, 4, 3, 2, 1, 0.9,
0.8
.
0.7, 0.6, 0.5,
0.
4, 0.3, 0.2,
0.1}. So
we
h
a
ve m
i
=
{7,
8
,
9, 10,
11, 1
4
,
20, 2
5
, 33,
5
0
, 100,
111,
125, 143, 16
7, 200, 250, 333, 500, 10
00}
. Differe
nt weighting a
pplied for
since lo
we
r
for bigge
r
i
is
more impo
rt
ant (4).
(
1
8
)
Figure 7
sho
w
s the
optimi
z
ed
minim
u
m
f
(
X
)
whi
c
h i
s
the tra
d
e
-
off
betwe
en th
e
PR an
d
ER (Chapte
r
4.1) on the Calibratio
n
DB.
Figure 7. The
Optimized Mi
nimum
f
(
X
) o
n
the Calib
rat
i
on DB.
4.3. Result:
Comparis
on
In orde
r to
evaluate
co
mpari
s
o
n
of
multi-
thre
ad i
m
pleme
n
tatio
n
to its
sin
g
l
e
-thread
impleme
n
tation of p
r
op
osed di
re
ct
-a
ccess strategy, a
large
p
ubli
c
fingerprint
d
a
ta set provided
by CASIA (35) wa
s u
s
ed. T
he experi
m
en
ts have bee
n carrie
d out as follows:
a)
20.000
imp
r
ession
s f
r
om
4.000
finge
rs (f
ive
im
pression
s per fi
nger)
were
used. Fi
rst
impre
s
sion fo
r index creati
on, and othe
r four
for se
archin
g (a
s que
ry impre
ssi
on
s).
b)
Four
se
archi
ng test
s hav
e bee
n pe
rf
o
r
med, in
crea
sing th
e data
base si
ze
N
from 10
00 to
4.000 imp
r
e
s
sion
s (a
ddin
g
N
= 100
0 per test).
c)
For ea
ch q
u
e
r
y
,
N
T
=
N
/10
can
d
idate
s
h
a
ve been retri
e
ved.
For ea
ch of the fifteen tests, the followin
g
perfo
rman
ce indicators h
a
ve been me
asu
r
ed:
a)
Average total
search time,
i.e. time of
extracto
r, pre
-
filter,
and matcher (Figu
r
e 1).
b)
Average ER
at an averag
e
PR of 10% (Cha
pter 4.1
)
.
Figure 8
sho
w
s mea
s
u
r
e
d
perf
o
rma
n
ce
indi
cators
ab
ove a
s
fun
c
ti
ons of d
a
tab
a
se
si
ze
N
. Several a
s
pect
s
abo
ut compa
r
ison:
a)
Single-th
rea
d
impleme
n
tation seem
s sl
ight fa
ste
r
o
n
avera
ge
search time t
han its
multi-
thread i
m
ple
m
entation fo
r first and
se
con
d
test.
Th
ere i
s
turning
point where
at third an
d
fourth test, m
u
lti-thre
ad im
plementatio
n
faster
o
n
ave
r
age
se
arch t
i
me than its
single-th
re
ad
impleme
n
tation.
b)
For the fou
r
th
test, multi-thread im
pleme
n
ta
tion ca
n redu
ce averag
e sea
r
ch time
about 17%
comp
ared to its single
-
thre
ad impleme
n
tation. Fo
r further bigg
er d
a
taba
se si
ze,
we pre
d
ict
multi-thre
ad
impleme
n
tatio
n
stil
ca
n
red
u
ce
ave
r
age
sea
r
ch time
at ce
rtain
va
ule m
o
re
tha
n
17% until sat
u
ration
status (maximum
work of thread
s) wa
s re
ache
d.
0
5
10
15
0
5
10
15
2
0
25
30
E
rror
Rat
e
(%
)
Pe
ne
tr
a
t
i
o
n
Ra
t
e
(%
)
Evaluation Warning : The document was created with Spire.PDF for Python.