Minutiae Matching Algorithm: following “On-line
Fingerprint Verification” by Jain at al.
Distributed on
Notation and Settings:
Following notation from [1], let T and I be the representations of the template and input fingerprint, respectively. Denote by 
the i-th minutia from T
and by 
the i-th minutia from
I.
Thus 
is the set of the
template minutiae and 
is the set of the
input minutiae. Note that the total
number of minutiae M and N in the template and in the input
images is distinct.
Similar to all other minutiae matching algorithms the string matching algorithm in [2] is implemented in two stages: (1) alignment stage and (2) matching stage.
This algorithm uses ridge information to align two
fingerprints. Thus the problem of
minutiae alignment is reduced to the problem of ridge alignment. Ridge is considered as a planar curve. During the minutiae detection stage the
ridge associated with every minutia is also recorded. Every ridge is presented as a planar curve
with its origin at the minutia location and its x-coordinate being in the same
direction as the direction of the minutia.
Let 
and 
be two sets of ridges
in the template and input images, respectively.
For each ridge
, sample the ridge with the sampling interval equal to the
average inter-ridge distance and represent the ridge as a one-dimensional
discrete signal (see Fig. 1).
Fig.1: The ridge is uniformly sampled with the interval a. d1, d2, d3, … are
the
distances from the sampled points along the ridge to the X-axis. [d1,d2,…,dK] is the vector representation of the ridge. X-axis
has the direction of the corresponding minutia.
The Alignment Algorithm:
a)
Match each ridge against each ridge 
using the so-called ridge matching
score:
,
where L is the minimal lengths of the two sampled ridges. S can
take the following values 
. The larger is S, the higher is the chance that two
ridges from two different templates match.
How to decide if there is a match? Define a threshold t and use it to make a decision. t is typically set by the designer.
The decision rule then is the following:
If 
then the two ridges
match. Go to the step (b).
If 
then choose a new pair
of ridges.
b) Estimate the pose (translation and orientation) of two ridges.
To proceed with estimation of the pose, define a reference minutia. Choose one of two minutiae corresponding to matched ridges as a reference minutia. The translation and rotation of the second fingerprint will be performed with respect to the reference minutia.
Denote the reference minutia as 
and assume that 
. Then the translation
estimate is obtained as follows:
,
where 
and 
are the locations of
minutiae on two matched ridges.
The rotation angle 
is estimated
using
,
where 
and 
are the radial angles
formed by the line passing through the minutia point and one of the sample
points along the ridge and by the line passing through the minutia along the direction
of minutia (see Fig. 2). Note that the
radial angles are always measured with respect to the orientation of the
reference minutia.
Fig. 2: Radial angles.
c) Then to align two images (input and template) every minutia in the input image
has to be translated and rotated with respect to the reference minutia by the estimated displacement and rotation angle. Mathematically this can be expressed as follows:
,
where the superscript “A” denotes an aligned minutia in the input image and i=1,…,N.
Pattern Matching:
In the ideal case, after the alignment stage each pair of corresponding points is completely coincident. In practice, the error in localizing the minutiae and estimating the parameters and the non-linear deformation of fingerprints hinder to recover the relative pose transformation completely. The aligned point pattern matching algorithm needs to be elastic which means:
- it should tolerate the deformations due to inexact extraction of minutiae positions and
- it should tolerate nonlinear deformations.
Usually such a matching can be achieved by placing a bounding box around each template minutia (it specifies all possible positions of the corresponding input minutia with respect to the template minutia).
The adaptive elastic
matching algorithm can compensate the minutia localization errors and nonlinear
deformations. Let 
be aligned with
respect to the reference minutia input template
.
The steps of the elastic point pattern matching algorithm are:
a)
Convert both the aligned input fingerprint and the template T
into polar
representation. All transformations are performed with respect to the reference minutia
,
where
is the radius, 
is the radial angle
and 
is the orientation
difference of the i-th
minutia from the input image.
Represent the template and the input minutiae in the polar coordinate system as symbolic strings by concatenating each minutia in the increasing order of radial angles
,
.
b)
Match the strings 
and 
with a dynamic programming algorithm to find
the edit distance between and .
c)
Use the edit distance between and to establish the
correspondence of the minutiae between and .
The matching score,
,
where 
is the number of
minutiae which fall in the bounding boxes of the template minutiae. 
takes
the following values 
.
References:
[1] D. Maltoni, D. Maio, A. K. Jain, and
[2] A. Jain and L. Hong, “On-line Fingerprint Verification,”
IEEE Trans. on Pattern Analysis and
Machine Intelligence, vol. 19, no. 4, pp. 302 – 313, 1997.