Minutiae Matching Algorithm: following “On-line Fingerprint Verification” by Jain at al.
Notation and Settings:
Following notation from , 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  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.
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:
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 .
 D. Maltoni, D. Maio, A. K. Jain, and
 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.