Minutiae Matching Algorithm: following “On-line Fingerprint Verification” by Jain at al.

Distributed on February 11, 2004

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.

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 S. Prabhakar, Handbook of Fingerprint Recognition, Springer, New York, 2003.

[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.