Studies of Fingerprint Template Selection and Update - Advances in Computational Science and Engineering - page 155

4 Score Based Template Selection

The common template selection strategy is the random selection strategy (Random).
This strategy just randomly chooses several templates each time. Though it may be
poor performance, it is useful to be compared with other strategies. According to
maximized score model mentioned in section 2, we want to choose the K templates
that make s(T K ,I N-K ) maximized. Based on this model, we propose two algorithms. In
the following algorithms Table 1, S N×N delegates the match score matrix. The value of
s m,n is the match score of template t m matched with input sample i n . Choose[K] is used
to record the templates selected.

Table 1. Maximum Match Scores (MMS)

S

1 Initialize N, K, NN , Choose[K],

×

i i

NK

K
N T and

T −

(1

≤≤ iC ) 2 list all

K

i ← 1

C do begin

3 for to

4 begin

using

5

i i

S s ← sTT − (, )

compute (1)

NN × i K N K

6 end

* * K

N

i ( i ∈ , , C )

7 find

K

K
N

i ss

≥ ( , i = , C )

such that

K

8

i

*

*
K

i T with Choose[K]

9

record

To analyze the line (5) of MMS algorithm, we can get the complexity of MMS
as (12):

2 N

2 N

N

/ 2 2

(1 / 4) NC ≥ (1 / 4) N

(12)

When N increases, the complexity will increase exponentially. Then we propose an-
other algorithm Greedy Maximum Match Scores (GMMS) as Table 2.
The idea of algorithm GMMS just can be described as choosing one sample which
has maximum match scores with the left samples each time. The complexity of
GMMS is O(N 2 ). Umut Uludag [3] proposed two methods DEND and MDIST to
select templates. From his work, the MDIST method has a better performance. The
distance in his work is obtained by matching the minutiae point sets of the two finger-
print impressions, and we call MDIST based on match scores sMDIST. The basic idea
of MMS, GMMS and sMDIST is to choose the partition of T N that makes the sum of
match scores maximized.