Yang J., Nanni L. (eds.) State of the Art in Biometrics

Подождите немного. Документ загружается.

Fingerprint Matching using A Hybr id Shape and Orientation Descriptor 15

3.1.2 Similarity score

Once the n iterations are performed, the ﬁnal pairs have now been established. From this, the

shape similarity distance measure can be calculated as

(P, Q)=

∑

p∈P

arg min

q∈Q

C(p, T(q)) +

∑

q∈Q

arg min

p∈P

C(p, T(q)) (47)

where T

(.) denotes the T.P.S transformed representative of the contour point q. In addition, an

appearance term, D

(P, Q), measuring pixel intensity similarity and a bending energy term,

(P, Q)=I

, can be added to the similarity score.

Afterward, the similarity measure was modiﬁed as

∗

= D

+ βD

. (48)

Although this measure does not take into account the strict one-to-one mapping of minutiae;

through experimentation, this method proved to be sound, providing acceptable performance

in ﬁngerprint similarity assessment. However, the resulting minutiae mapping from the

application of the Hungarian algorithm on the contextually based cost histograms produced

some un-natural pairs, as illustrated in Figure 8 (top). This is due to the lack of a minutiae

pair pruning procedure. The existence of un-natural pairs could potentially skew the Thin

Plate Spline (T.P.S) linear transform performed. In addition, such pairs generally increase

the bending energy substantially, thus leading to invalid matching results, particularly for

genuine matches.

3.2 Proposed matching method

Recently, hybrid matching algorithms have been used for ﬁngerprint matching. Although

minutiae detail alone can produce a highly discriminant set of information, the combination

of level 1 feature, such as orientation and frequency, and other level features, can

increase discriminant information, and hence, increase matching accuracy, as illustrated in

Benhammadi et al. (2007), Youssif et al. (2007), Reisman et al. (2002), and Qi et al. (2004).

The detailing of the proposed hybrid matching algorithm based on a modiﬁed version of

the enhanced shape context method in Kwan et al. (2006), along with the integration of

the orientation-based descriptor of Tico & Kuosmanen (2003) is given here, illustrating a

signiﬁcant performance improvement over the enhanced shape context method of Kwan et al.

(2006). The main objective of the integration is two-fold, ﬁrstly to prune outlier minutiae pairs,

and secondly to provide more information to use in similarity assessment.

As brieﬂy described earlier in section 2.3, the orientation-based descriptor in Tico &

Kuosmanen (2003) utilises the orientation image to provided local samples of orientation

around minutiae in a concentric layout. Each orientation sample point is calculated as

c,d

= min(|θ

c,d

−θ

|, π −|θ

c,d

−θ

|) (49)

being the d

sample on the c

concentric circle with distance r

away from the minutiae

point m

, where θ

and θ

c,d

are the minutia and sample point orientation estimations,

respectively. The orientation distance of equation 22 is used to prune outlier pairs resulting

from the Hungarian algorithm which produced the mapping permutation of equation 30.

Although the shape context deﬁnes the similarity measure in equation 47-48 with no strict

one-to-one correspondence, minutiae should have a more strict assessment based on the

optimal mapping, since minutiae are key landmarks as opposed to randomly sampled contour

Fingerprint Matching using A Hybrid Shape and Orientation Descriptor

16 Will-be-set-by-IN-TECH

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

28 correspondences (unwarped X)

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

28 correspondences (warped X)

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

28 correspondences (warped X)

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

18 correspondences (warped X)

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

19 correspondences (warped X)

0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

19 correspondences (warped X)

Fig. 8. top: The Enhanced Shape Context method producing initial minutiae pair

correspondences. The next two images are for the following iterations. One should note that

there are some clear un-natural pairs produced, where plate foldings are evident (i.e. pair

correspondences that cross other pair correspondences). bottom: The proposed hybrid

method initial minutiae pair correspondences along with following iterations of produced

correspondences.

points. Thus, equation 48 can be modiﬁed to only score the pairs with the optimal one-to-one

mapping as

∗∗

(P, Q)=

∑

∈P|D

π(i)

)<δ

C(p

, q

π(i)

)+ΛD

, q

π(i)

)+βD

(50)

with an addition term in the summation to account for orientation distance scaled by the

tunable parameter, Λ with range

[0, 1 ].

In terms of what concentric circle radii and sample conﬁguration should be used, the method

explained in Tico & Kuosmanen (2003) prescribes that the radius for circle K

be r

= 2l × τ,

where τ denotes the average ridge period, and for the sample conﬁguration, the circle K

should have roughly 

πr

. As the average ridge period was recorded to be 0.463 mm in

Stoney (1988), for a ﬁngerprint image with dots per inch (dpi) equal to R, the previous formula

for the conﬁguration can be expressed as K

= 

172.r

. However, this was really only used

as a rough guide for the conﬁguration used in the experimentation of Tico & Kuosmanen

(2003). This was also used as a rough guide for our implementation of the orientation-based

descriptor.

Although the log-polar space adequately provides extra importance toward neighbouring

sample points, additional emphasis on local points may be desirable, since minutiae sets are

largely incomplete and do not entirely overlap. For a given minutia, non-local bin regions may

be partially or largely outside the segmented region of interest for one ﬁngerprint and not the

other. In addition, the non-local bins are spatially larger, and hence, have a higher probability

State of the Art in Biometrics

Fingerprint Matching using A Hybr id Shape and Orientation Descriptor 17

of containing false minutia caused by noises. Such issues can potentially result in incorrect

minutiae pairs. Thus, the enhanced shape context’s log-polar histogram cost in equation 27 is

adjusted to contain a tunable Gaussian weighting of histogram bin totals, depending on their

distances away from the centre (reference minutia), with

∗∗

, q



−γC

ty pe

angl e



⎛

⎜

⎝

∑

k=1



(k) −h

(k)



(k)+h

(k)

exp



−

(

−r

min

)

2σ



⎞

⎟

⎠

(51)

where r

min

is the outer boundary of the closest bin, r

is the current bin outer boundary

distance, and σ

is a tunable parameter (see Figure 9).









Fig. 9. The log-polar sample space convolved with a two dimensional Gaussian kernel,

resulting in each bin to be weighted according to its distance from the origin (minutia). The

histogram cost calculation uses the direction of the reference minutia as the directional offset

for the bin order, making the descriptor invariant to rotation.

3.2.1 Adaptive greedy registration

If we re-examine the registration of the enhanced shape context method of Kwan et al. (2006)

discussed in section 3.1, we can summarise the iterative process as updating minutiae pairs

with the enhanced shape context descriptor, followed by using T.P.S to perform a global

alignment with the linear transform component, and then performing non-linear transform

to model warping caused by skin elasticity. This method does not utilise any singularities

for the registration process, solely relying on the T.P.S framework for registration. Hence,

registration is largely reliant on the accuracy of the spatial distribution of minutiae relative to

a given reference minutia, which is often inadequate.

The proposed method does not use the T.P.S transform to perform the initial afﬁne transform.

Instead, a greedy method similar to Tico & Kuosmanen (2003) (of equations 20-23) is used.

Fingerprint Matching using A Hybrid Shape and Orientation Descriptor

18 Will-be-set-by-IN-TECH

Using the minutiae set representation of equations 3 and 4, each possible pair (m

, m

) of

the afﬁne transform, T, is calculated by using the orientation differences of each minutiae

direction as the rotation component, and the difference in x-y coordinates as the offset

component (as illustrated in equations 7-9). The heuristic that requires maximising is

(A, B)=arg max

∑

S(m

, m

T(i)

)

n(Φ

)

(52)

where S

(.) is previously deﬁned in equation 22 as the similarity function based on the

orientation-based descriptor, ψ is the index pair reference for the transform T (i.e.

(i, j) with

= m

T(j)

), Φ

is the anchor point set (with size n(Φ

)) of minutiae pairs (m

, m

) ∈ Φ

which have each other as closest points from the opposite minutiae sets with distance less

than an empirically set limit, δ

, after applying the given transform. In addition, all anchor

point minutiae pairs must have similar orientation, hence meeting the constraint

min



|θ

−θ

|, π −|θ

−θ



< δ

(53)

(see Figure 5 left). From the given deﬁnition, we can easily verify that

(i, j) ∈ Φ

If the primary core point exists in both the test and template feature sets, provided that the

core point detection is highly accurate with a given test dataset, then we have good reason to

ignore afﬁne transforms that cause the core points to be greater than a ﬁxed distance, δ

, away

from each other. Additional pruning can be achieved by only allowing transforms where the

reference minutiae pair has a orientation-based descriptor similarity score to meet



, q

π(i)



< δ

(54)

where δ

is empirically set. Such restrictions will not only improve performance, but also

make the registration process much more accurate, since we are not just blindly maximising

the heuristic of equation 52.

Many registration algorithms use singularities, texture, and minutiae pair information as

tools for ﬁnding the most likely alignment. However, the overlapped region shape similarity

retrieved from minutiae spatial distribution information provides an additional important

criteria. After ﬁnding the bounding box (overlapping region) of a possible afﬁne transform

meeting all prior restrictions, we can then measure shape dissimilarity via the application of

the shape context to all interior points P

⊆ A and Q ⊆ B with equation 50, giving additional

criteria for afﬁne transforms to meet D

(P, Q) < δ

for an empirically set threshold, δ

For a candidate transform, we have the corresponding anchor point set Φ

. We will now

deﬁne two additional nearest neighbour sets of the interior points in the overlap region (as

depicted in Figure 10) as





− x

)

+(y

−y

)

< δ



(55)

where Φ

contains all interior nearest neighbour indices from ﬁngerprint A, and likewise, Φ

containing interior nearest neighbour indices for ﬁngerprint B . Thus, we have

⊆



(i, j) | i ∈ Φ

and j ∈ Φ



. (56)

with 1

≤ i ≤ p and 1 ≤ j ≤ q. The afﬁne transform method is detailed in algorithm 1.

If a candidate afﬁne transform meets the heuristic of equation 52 with the given constraints,

State of the Art in Biometrics

Fingerprint Matching using A Hybr id Shape and Orientation Descriptor 19

Algorithm 1 Proposed registration algorithm (Afﬁne component)

Require: minutiae set P and Q (representing ﬁngerprints A and B, respectively).

← 0

←NIL

for all possible minutiae pairs



, q





, q



← (1/K)

∑

exp

−



min(|θ

c,d

−θ

c,d

|,π−|θ

c,d

−θ

c,d



πμ

if S



, q



< δ

then

continue

end if

{Perform transform from minutiae pair with offset and orientation parameters from

minutiae x-y and θ differences}



← T(Q)

{Make sure core points are roughly around the same region, provided both cores exist}

if BothCoresE xist

(P, Q



) and CoreDist(P, Q



) > δ

then

continue

end if

{Get T.P.S cost matrix (see algorithm 2)}

∗∗

← TPS

cost

(P, Q



)

←

∑

p∈P

arg min

q∈Q



∗∗

(p, q)+

∑

q∈Q



arg min

p∈P

∗∗

(p, q)

if D

> δ

then

continue

end if

←



(a, b) | arg min

a∈P



− x

)

+(y

−y

)



←



(a, b) | arg min

b∈Q



− x

)

+(y

−y

)





←



(a, b) | (a, b) ∈ Φ

∩Φ

and



− x

)

+(y

−y

)

< δ



test

←

∑

(a,b)∈Φ



S(p

,T(q



))

n(Φ



)

if H

test

> H then

← H

test

ψ ← (i, j)

← Φ



← Q



end if

end for

←





− x

)

+(y

−y

)

< δ



←





− x

)

+(y

−y

)

< δ



return Φ

, Φ

, Q

Fingerprint Matching using A Hybrid Shape and Orientation Descriptor

20 Will-be-set-by-IN-TECH

Algorithm 2 TPS

cost

: Calculate TPS cost matrix

Require: minutiae set P and Q (representing ﬁngerprints A and B, respectively).

for all minutiae q

∈ Q do

for k

= 1toK do

(k) ← #



= q

: (q

−q

) ∈ bin(k)



end for

for all minutiae p

∈ P do

for k

= 1toK do

(k) ← #



= p

: (p

− p

) ∈ bin(k)



end for

for all minutiae p

∈ P and q

∈ Q do

ty pe

←



−1iftype(p

)=type(q

0ifty pe

) = ty pe(q

)

angl e

←−



+ cos((∠

initial−w arped

))



∗∗

, q

) ←



−γC

ty pe

angl e



∑



(k)−h

(k)



(k)+h

(k)

×exp



−

−r

min

)

2σ



end for

return C

∗∗

we can then focus on the non-afﬁne aspect of registration. The T.P.S non-afﬁne component

adequately modeled the warping caused by skin elasticity in the previously proposed method.

With this in mind, it will be desirable to utilise the non-linear component.

The T.P.S has its point correspondence method modiﬁed through having anchor point

correspondences remain static throughout the iterative process, thus attempting to restrict

the afﬁne transform component of T.P.S while ﬁnding new correspondences from Φ

on to

that do not exist in Φ

. The shape context’s log-polar histogram cost is modiﬁed from

equation 51 as

, q

)=γ

∗∗

, q

) (57)

where γ

is deﬁned as



1ifdist

, q

) < δ

max

∞ otherwise

(58)

with δ

max

set as the maximum feasible distance caused by warping after applying the

candidate afﬁne transform, and similarly, γ

, is deﬁned as



1 if min

(|θ

−θ

|, π −|θ

−θ

|) < θ

max

∞ otherwise

(59)

with θ

max

set as the maximum feasible orientation difference caused by orientation estimation

error in the extraction process.

State of the Art in Biometrics

Fingerprint Matching using A Hybr id Shape and Orientation Descriptor 21

Fig. 10. An example afﬁne transform candidate search sequence with ﬁnal state and

corresponding bounding box for the overlapped region.

>From the new cost function, the Hungarian algorithm is then used to ﬁnd additional

one-to-one correspondences to what already existed in the anchor point set. The candidate

afﬁne transform in comparison to the afﬁne component of T.P.S,

⎡

⎣

x,x

x,y

1,x

y,x

y,y

1,y

001

⎤

⎦

, (60)

is used to assess the accuracy of the additional correspondences found. The T.P.S afﬁne

component would not have prominent translation, rotation, and shear parameters since

the candidate transform should have already adequately dealt with the afﬁne registration

task as the Euclidean constraints on the anchor point worked to keep the global transform

rigid. In addition, the inclusion of additional natural minutiae correspondences should not

signiﬁcantly alter the afﬁne registration required. Thus, the lack of prominent translation,

rotation, and shear parameters for the T.P.S afﬁne transform indicates an existing agreement

between both afﬁne transforms. Evaluation of the translation distance is given by

affine



1,x

+ a

1,y

< r

max

. (61)

Using the Singular Value Decomposition (SVD) of the non-translation components of A

SVD



x,x

x,y

y,x

y,y



= UDV

(62)

where U, V

∈ SO(2, R) (i.e. 2x2 dimension rotation matrices with angles θ

and θ

respectively) and D is a 2x2 diagonal matrix representing scaling along the rotated coordinate

Fingerprint Matching using A Hybrid Shape and Orientation Descriptor

22 Will-be-set-by-IN-TECH

Algorithm 3 Proposed registration algorithm (Non-afﬁne component)

Require: minutiae set P and Q

(for ﬁngerprints A and transform B), anchor set Φ

, nearest

neighbourhood sets Φ

and Φ



←

{

| i ∈ Φ

}

, Q

←



| j ∈ Φ



, ω

affine

← 0, D

← 0

for all minutiae q

∈ Q

for k

= 1toK do

(k) ← #



= q

: (q

−q

) ∈ bin(k)



end for

for iter

= 1ton do

for all minutiae p

∈ P do

for k

= 1toK do

(k) ← #



= p

: (p

− p

) ∈ bin(k)



end for

for all minutiae p

∈ Φ

and q

∈ Φ

ty pe

←



−1iftype(p

)=type(q

0ifty pe

) = ty pe(q

)

angl e

←−



+ cos((∠

initial−w arped

))



∗∗

, q

) ←



−γC

ty pe

angl e



∑



(k)−h

(k)



(k)+h

(k)

×exp



−

−r

min

)

2σ



, q

) ← γ

∗∗

, q

)

end for

{calculate and add minutiae pairs additional to the anchor set pairs.}

← Hungarian(C

, Φ

, fixedMap = Φ

)

(x, y) ←T.P .S (P, Q

, Φ

, Regul arized = true )

← D

+ WKW

affine

←



1,x

+ a

1,y

[U, D, V

, θ

] ← SVD



x,x

x,y

y,x

y,y



affine

← ω

affine

+ |θ

+ θ

affine

← log



1,1

2,2



if D

> E

max

or r

affine

≥ δ

max

or ω

affine

≥ θ

max

or τ

affine

≥ τ

max

then

return Φ

end if

for all minutiae p

∈ P do

[x, y] ← [p

(x) , p

(y)]

[

(x) , p

(y)] ← [ f

(x, y), f

(x, y)]

end for

return return Φ

State of the Art in Biometrics

Fingerprint Matching using A Hybr id Shape and Orientation Descriptor 23

axes of V

with nonnegative diagonal elements in decreasing order, the evaluation of rotation

affine

= |θ

+ θ

|< ω

max

, (63)

and shear

affine

= log



1,1

2,2



< τ

max

, (64)

is performed for empirically set values ω

max

and τ

max

. If the above afﬁne transform criteria

of equations 61, 63, and 64 are not met, no extra minutiae pairs are produced. Unlike the

previous method, this helps uphold spatial consistency by not creating un-natural pairs (see

Figure 8 (bottom)). Essentially, the candidate afﬁne transform is used as the ground truth

registration over the T.P.S afﬁne component.

A ﬁnal integrity check of the validity of the additional minutiae pairs produced from the

non-afﬁne transform is the measured bending energy, previously deﬁned in equation 45. If

the non-afﬁne transform produces a bending energy distance D

> E

max

, then all additional

minutiae pairs are also rejected, in order to avoid un-natural warping to occur. The non-afﬁne

transform component is detailed in algorithm 3.

3.2.2 Matching algorithm

Once the minutiae pairs have been established, pruning is performed to remove unnatural

pairings. However, if we closely analyse the orientation-based descriptor used for pruning,

we can see that a fundamental ﬂaw arises with partial ﬁngerprint coverage, speciﬁcally for

minutiae pairs near ﬁngerprint image edges. In such a case, the typical formula for distance

calculation cannot count orientation samples that lie outside the region of interest, and

therefore, unnecessarily reduces the orientation distance measure (see Figure 11). Moreover,

regions that have high noise also cannot have their orientation reliably estimated due to

information to be missing (if regions with high noise are masked), and likewise, reduces the

orientation-based descriptor common region coverage.

A proposed modiﬁcation to the orientation-based descriptor is applied so that the amount of

common region coverage that each descriptor has is reﬂected in the similarity score. This is

achieved by a simple Gaussian weighting of equation 22 with

∗

, m

)=S(m

, m

) ×exp(−max(0, Δ

cuto f f

−Δ

g_count

).μ

) (65)

where Δ

cuto f f

is the cutoff point where all good sample totals below this value are weighed,

g_count

is the total number of good samples (i.e. where a good sample is deﬁned to be in a

coherent ﬁngerprint region), and μ

is a tunable parameter. However, for a more exhaustive

approach, one could empirically review the estimated distribution of orientation-based

similarity scores for true and false cases, with speciﬁc attention towards the effect of coverage

completeness on the accuracy of the similarity measure.

Equation 65 relies on the intersection set of valid samples for each minutiae, deﬁned as

, B



| s ∈{L, K

} and valid(A(s

, s

))



∩



| t ∈{L, K

} and valid(B(t

, t

))



(66)

where L is the sample position set and K

is the concentric circle set. Thus, we can also deﬁne

a variant of the function S

∗

, m

, I) where a predeﬁned sample index set , I, is given to

indicate which samples are only to be used for the similarity calculation, ignoring i /

∈ I even

if corresponding orientation samples are legitimately deﬁned for both ﬁngerprints (note: this

variant is used later for similarity scoring in the matching algorithm).

Fingerprint Matching using A Hybrid Shape and Orientation Descriptor

24 Will-be-set-by-IN-TECH

Fig. 11. An example where the orientation-based descriptor for corresponding minutiae in

two different impressions of the same ﬁngerprint have no coverage in a substantial portion

of the orientation sample.

After the ﬁltered minutiae pair set is produced, we can now assess the similarity of the

pairs. Minutiae δ-neighbourhood structure families, where particular spatial and minutiae

information of the δ closest minutiae to a reference minutiae are extracted as features, have

been used before in minutiae based matching algorithms (such as Chikkerur & Govindaraju

(2006) and Kwon et al. (2006)) for both alignment and similarity measure (see Figure 12). The

δ-neighbourhood structure proposed has the following ﬁelds:

• Distance d

: the distance a neighbourhood minutia is away from the reference minutia.

• Angle

∠

: the angle a neighbourhood minutia is from the reference minutia direction.

• Orientation θ

: the orientation difference between a neighbourhood minutia direction and

the reference minutia direction.

• Texture Γ

: the orientation-based descriptor sample set for a neighbourhood minutia used

to measure the region orientation similarity with the reference minutia for a given sample

index.

giving us the sorted set structure

nδ

)={{d

(1)

, ∠

(1)

, θ

(1)

, {Γ

(1)

}},...,{d

(δ)

, ∠

(δ)

, θ

(δ)

, {Γ

(δ)

}}} (67)

being sorted by the distance ﬁeld in ascending order. The ﬁrst two ﬁelds are considered as the

polar co-ordinates of the neighbourhood minutiae with the referencing minutia as the origin,

and along with the third ﬁeld, they are commonly used in local neighbourhood minutiae

based structures ( Kwon et al. (2006) and Jiang & Yau (2000)). Using the modiﬁed weighted

orientation-based descriptor, the texture ﬁeld provides additional information on how each

local orientation information surrounding the δ-neighbourhood minutiae set vary from that

of the reference minutia, with the measure rated using equation 65. These structures can now

be used to further assess and score the candidate minutiae pairs.

When comparing the δ-neighbourhood elements of a candidate minutiae pair, the ﬁrst three

ﬁelds are straight forward to compute the differences with

State of the Art in Biometrics