Fingerprint Recognition. Fingerprint Matching

Depending on an application two kinds of fingerprint recognition systems exist: verification systems and identification system.. A verification system generally stores the fingerprint images or feature sets of users in a database. At a future time, it compares the fingerprint of a person with her/his own fingerprint image or feature set to verify that this person is, indeed, who she/he claims to be. This problem is a one-to-one matching problem.

The system can accept or reject this person, according to the verification result. An identification system is more complex where, for a query fingerprint, the system searches the entire database to find out if any fingerprint images or feature sets saved in the database can match it. It conducts one-to-many matching. Two kinds of identification systems exists: the closed- set identification system and the open-set identification system.

The closed-set identification system is the identification system for which all potential users are enrolled in the system. Usually, the closed-set identification is used for research purposes. The open-set identification system is the identification system for which some potential users are not enrolled in the system. The open-set identification is performed in real operational systems. The verification and the closed-set identification are special cases of the open-set identification.

Three kinds of approaches (see Fig. 7) exist to solve the fingerprint identification problem (10): (1) Repeat the verification procedure for each fingerprint in the database and select the best match; (2) use fingerprint classification followed by verification; and (3) use fingerprint indexing followed by verification. Fingerprint matching, classification, and indexing are three basic problems in fingerprint identification.

Figure 7. Block diagram of three kinds of approaches to solve the identification problem

Fingerprint Matching. A fingerprint matching algorithm aligns the two given fingerprints, finds the correspondences between them, and returns a measure of the degree of similarity. Usually, the similarity score is used to represent the degree of similarity between the two given fingerprints. Fingerprint matching is a challenging problem because different impressions of the same finger could be very different because of distortion, displacement, rotation, noise, skin condition, pressure, noise, and so forth.

Furthermore the impressions from different fingers could be quite similar. Figure 8 shows two impressions of one fingerprint from the NIST-4 database (10). The fingerprint matching algorithms can be classified into three different types: (1) the correlation-based approach, (2) the minutiae-based approach, and (3) the ridge feature-based approach.

Figure 8. Two impressions of one fingerprint

1. Correlation-based matching: The correlation-based approach uses the gray-level information of fingerprints. For a template fingerprint (in the database) and a query fingerprint, it computes the sum of the squared differences in gray values of all the pixels to evaluate the diversity of the template fingerprint and the query fingerprint. To deal with the distortion problem, it computes the correlation in local regions instead of the global correlation on the entire image. In Bazen et al., the correlation-based evaluation is used to find the distinctive regions of the template fingerprint.

These local regions fit very well at the original locations and much worse at other locations. During the matching, they compute the gray-level distance between the distinctive regions of a template and the corresponding areas in the query fingerprints. Then, they sum up the squared gray-level difference for each local region. The position of a region of the template with the minimal distance is considered as the corresponding region in the query fingerprint.

Compared with the other matching algorithms described below, correlation-based matching approaches use gray-level information of the fingerprint. When the quality of the fingerprint image is not good, especially when a large number of minutiae are missing, the correlation-based matching algorithm may be considered. However, it is expensive computationally.

2. Minutiae-based matching: Minutiae-based matching is the most commonly used method for fingerprint recognition systems. In this approach, a fingerprint is represented by a set of minutiae features. Thus, the fingerprint recognition problem is reduced to a point-matching problem. Therefore, any point matching approach, such as the relaxation algorithms, can be used to recognize the fingerprints.

Feature extraction: The first step of the minutiae- matching algorithm is the minutiae extraction. Figure 9 is the block diagram of the minutiae-based feature extraction procedure, which is used widely in most fingerprint recognition systems. As an example, Bhanu and Tan present a learned template-based algorithm for feature extraction.

Figure 9. Block diagram for minutiae-based feature extraction

Templates are learned from examples by optimizing a criterion function using the Lagrange method. To detect the presence of minutiae in fingerprints, templates for endpoints and bifurcations are applied with appropriate orientation to the binary fingerprints at selected potential minutiae locations.

Matching: Tan and Bhanu present a fingerprintmatching approach, based on genetic algorithms (GA). This method can achieve a globally optimized solution for the transformation between two sets of minutiae extracted from two different fingerprints. In their approach, the fitness function is based on the local properties of triplets of minutiae, such as minimum angle, maximum angle, triangle handedness, triangle direction, maximum side, minutiae density, and ridge counts. These features are described in the “Fingerprint Indexing” section below.

Jiang and Yau use both the local and global structures of minutiae in their minutiae-matching approach. The local structure of a minutia describes the features independent of the rotation and translation in its l-nearest neighborhood. The global structure is variant with the rotation and translation. Using the local structure, the best matched minutiae pair is found and used to align the template and query fingerprint. Then, the elastic bounding box of the global features is used for the fingerprint matching.

Kovacs-Vajna used triangular matching to deal with deformations of fingerprints. In this approach, the minutiae regions of the template fingerprint are moved around the query fingerprint to find the possible correspondence. The triangular matching algorithm is used to obtain the matching minutiae set. Then, the dynamic time-warping algorithm is applied to validate the final matching results.

3. Ridge feature-based matching: For a good quality fingerprint with size 480 x 512 [500 pixels per inch (ppi)], about 80 minutiae features could exist. Thus, for the triangular minutiae matching, hundreds of thousands of triangles could exist. So, the minutiae matching approach needs high computational power. However, when the image quality is not good, the minutiae extraction would be difficult. Because fingerprints consist of natural valley and ridges, researchers have used them for fingerprint matching.

Maltoni et al. (8) present a filter-based algorithm for fingerprint recognition. It is based on the grayscale image. First, they determine a reference point with the maximum curvature of the concave ridges and an interest region in the fingerprint. After tessellating the interest region around the reference point, they use a bank of Gabor filters to capture both local and global details in a fingerprint.

Then, they compute the average absolute deviation from the mean to define the compact fixed-length FingerCode as the feature vector. Finally, they match the fingerprint by computing the Euclidean distance between the corresponding FingerCode between the template and query fingerprints.

With the improvement of the fingerprint sensor technology, now it is possible to extract features at a high resolution. In Jain et al., authors use pores and ridge contours combined with minutiae features to improve fingerprint recognition performance. In their approach, they use Gabor filter and wavelet transform to extract pores and ridge contours. During the matching process, they extract orientation field and minutiae features and establish alignment between the template and query fingerprint.

If the orientation fields match, then the system uses a minutiae-based matching algorithm to verify the query fingerprint or to reject the query fingerprint. If the number of the corresponding minutiae between the template fingerprint and query fingerprint is greater than a threshold, then these two fingerprints match; if not, then the system extracts pores and ridge contours and they use the Iterative Closest Point (ICP) algorithm to match these features. This hierarchical matching system requires 1000 ppi resolution for the sensor.

Representative Fingerprint Classification Approaches

Most fingerprint classification systems use the Henry system for fingerprint classification, which has five classes as shown in Fig. 3. The most widely-used approaches for fingerprint classification are based on the number and relations of the singular points, including the core and the delta.

Karu and Jain present a classification approach based on the structural information around the singular points. Three steps are in this algorithm: (1) Compute the ridge direction in a fingerprint image; (2) find the singular points based on the changes in the directional angle around the curve; and (3) classify the fingerprints according to the number and locations of the core and delta.

Other researchers use a similar method: first, find the singular point; then use a classification algorithm to find the difference in areas, which are around the singular points for different classes. Several representations based on principal component analysis (PCA) (3), a self-organizing map (18), and Gabor filters (8) are used.

The problems with these approaches are:
- It is not easy to detect singular points, and some fingerprints do not have singular points.
- Uncertainty in the location of the singular points is large, which has a great effect on the classification performance because the features around the singular points are used.

Cappelli et al. present a structural analysis of the orientation field of a fingerprint. In their approach, the directional image is calculated and enhanced. A set of dynamic masks is used in the segmentation step, and each dynamic mask is adapted independently to best fit the directional image according to a cost function. The resulting cost constitutes a basis for the final classification (3).

Based on the orientation field, Cappelli et al. also present a fingerprint classification system based on the multispace KL transform. It uses a different number of principal components for different classes. Jain and Minut propose a classification algorithm based on finding the kernel that best fits the flow field of a given fingerprint. For each class, a kernel is used to define the shape of the fingerprint in that class. In these approaches, it is not necessary to find the singular points.

Researchers also have tried different methods to combine different classifiers to improve the classification performance. Senior combines the hidden Markov model (HMM), decision trees, and PCASYS. Yao et al. present new fingerprint classification algorithms based on two machine learning approaches: support vector machines (SVMs) and recursive neural networks (RNNs).

In their approach, the fingerprints are represented by the relational graphs. Then, RNNs are used to train these graphs and extract distributed features for the fingerprints. SVMs integrated with distributed features are used for classification. To solve the ambiguity problem in fingerprint classification, an error-correcting code scheme is combined with SVMs.

Tan et al. present a fingerprint classification approach based on genetic programming (GP) to learn composite operators that help to find useful features. During the training, they use GP to generate composite operators. Then, the composite operators are used to generate the feature vectors for fingerprint classification.

Table 1. Representative fingerprint classification approaches

A Bayesian classifier is used for classification. Fitness values are computed for the composite operators based on the classification results. During the testing, the learned composite operator is applied directly to generate feature vectors. In their approach, they do not need to find the reference points. Table 1 summarizes representative fingerprint classification approaches.