Open access peer-reviewed chapter

Minutiae-based Fingerprint Extraction and Recognition

By Naser Zaeri

Submitted: October 21st 2010Reviewed: May 9th 2011Published: June 20th 2011

DOI: 10.5772/17527

Downloaded: 7382

1. Introduction

In our electronically inter-connected society, reliable and user-friendly recognition and verification system is essential in many sectors of our life. The person’s physiological or behavioral characteristics, known as biometrics, are important and vital methods that can be used for identification and verification. Fingerprint recognition is one of the most popular biometric techniques used in automatic personal identification and verification.

Many researchers have addressed the fingerprint classification problem and many approaches to automatic fingerprint classification have been presented in the literature; nevertheless, the research on this topic is still very active. Although significant progress has been made in designing automatic fingerprint identification systems over the past two decades, a number of design factors (lack of reliable minutia extraction algorithms, difficulty in quantitatively defining a reliable match between fingerprint images, poor image acquisition, low contrast images, the difficulty of reading the fingerprint for manual workers, etc.) create bottlenecks in achieving the desired performance. Nowadays, investigating the influence of the fingerprint quality on recognition performances also gains more and more attention.

A fingerprint is the pattern of ridges and valleys on the surface of a fingertip. Each individual has unique fingerprints. Most fingerprint matching systems are based on four types of fingerprint representation schemes (Fig. 1): grayscale image (Bazen et al., 2000), phase image (Thebaud, 1999), skeleton image (Feng, 2006, Hara & Toyama, 2007), and minutiae (Ratha et al., 2000, Bazen & Gerez, 2003). Due to its distinctiveness, compactness, and compatibility with features used by human fingerprint experts, minutiae-based representation has become the most widely adopted fingerprint representation scheme.

The uniqueness of a fingerprint is exclusively determined by the local ridge characteristics and their relationships. The ridges and valleys in a fingerprint alternate, flowing in a local constant direction. The two most prominent local ridge characteristics are: 1) ridge ending and, 2) ridge bifurcation. A ridge ending is defined as the point where a ridge ends abruptly. A ridge bifurcation is defined as the point where a ridge forks or diverges into branch ridges. Collectively, these features are called minutiae. Detailed description of fingerprint minutiae will be given in the next section.

The widespread deployment of fingerprint recognition systems in various applications has caused concerns that compromised fingerprint templates may be used to make fake fingers, which could then be used to deceive all fingerprint systems the same person is enrolled in. Once compromised, the grayscale image is the most at risk. Leakage of a phase image or skeleton image is also dangerous since it is a trivial problem to reconstruct a grayscale fingerprint image from the phase image or the skeleton image. In contrast to the above three representations, leakage of minutiae templates has been considered to be less serious as it is not trivial to reconstruct a grayscale image from the minutiae (Feng & Jain, 2011).

Figure 1.

Fingerprint representation schemes. (a) Grayscale image (FVC2002 DB1, 19_1), (b) phase image, (c) skeleton image, and (d) minutiae (Feng & Jain, 2011)

In this chapter, we study the recent advancements in the field of minutia-based fingerprint extraction and recognition, where we give a comprehensive idea about some of the well-known methods that were presented by researchers during the last two decades. Further, we provide a special focus on the recent techniques presented in the last few years. A close analysis of the fingerprint image will be discussed and the various minutiae features shall be described, as well.

2. Fingerprint minutiae description

The first scientific studies on fingerprint classification were made by (Galton, 1892), who divided the fingerprints into three major classes. Later, (Henry, 1900) refined Galton’s classification by increasing the number of the classes. All the classification schemes currently used by police agencies are variants of the so-called Henry’s classification scheme.

As mentioned in the previous section, the uniqueness of a fingerprint is exclusively determined by the local ridge characteristics and their relationships (Kamijo, 1993; Kawagoe & Tojo, 1984). The ridges and valleys in a fingerprint alternate, flowing in a local constant direction (Fig. 2). Eighteen different types of fingerprint features have been enumerated by (Federal Bureau of Investigation, 1984). Further, a total of 150 different local ridge characteristics (islands, short ridges, enclosure, etc.) have been identified by (Kawagoe & Tojo, 1984). These local ridge characteristics are not evenly distributed. Most of them depend heavily on the impression conditions and quality of fingerprints and are rarely observed in fingerprints. The two most prominent local ridge characteristics are: 1) ridge ending and, 2) ridge bifurcation.

A ridge ending is defined as the point where a ridge ends abruptly. A ridge bifurcation is defined as the point where a ridge forks or diverges into branch ridges. Collectively, these features are called minutiae. Most of the fingerprint extraction and matching techniques restrict the set of features to two types of minutiae: ridge endings and ridge bifurcations, as shown in Fig. 3. A good quality fingerprint typically contains about 40–100 minutiae.

In a latent or partial fingerprint, the number of minutiae is much less (approximately 20 to 30). More complex fingerprint features can be expressed as a combination of these two basic features. For example, an enclosure can be considered a collection of two bifurcations and a short ridge can be considered a pair of ridge endings as shown in Fig. 4.

Each of the ridge endings and ridge bifurcations types of minutiae has three attributes, namely, the x-coordinate, the y-coordinate, and the local ridge direction (θ) as shown in Fig. 5. Many other features have been derived from this basic three- dimensional feature vector. Given the minutiae representation of fingerprints, matching a fingerprint against a database reduces to the problem of point matching.

Figure 2.

Gray level fingerprint images of different types of patterns with core (□) and delta (Δ) points: (a) arch; (b) tented arch; (c) right loop; (d) left loop; (e) whorl; (f) twin loop (Ratha et al., 1996)

Figure 3.

Two commonly used fingerprint features: (a) ridge bifurcation; (b) ridge ending (Ratha et al., 1996)

Figure 4.

Complex features as a combination of simple features: (a) short ridge; (b) enclosure (Ratha et al., 1996)

The matching problem can be defined as finding a degree of match between a query and reference fingerprint feature set. The minutiae sets can be matched using many techniques, where some of them will be addressed in following sections. The large computational requirement of matching is primarily due to the following three factors: 1) a query fingerprint is usually of poor quality, 2) the fingerprint database is very large, and 3) structural distortion of the fingerprint images requires powerful matching algorithms.

Figure 5.

Components of a minutiae feature (Hong et al., 1998)

In addition to minutiae features described above, there are other high-level features that can be used in reducing the search space during a match. A very important feature for this purpose is the pattern class of a fingerprint. Fingerprints are classified into five main categories:

  • arch,

  • tented arch,

  • left loop,

  • right loop, and

  • whorl.

The pattern class may be ambiguous in partial fingerprints and indeterminate for noisy fingerprints. Yet another high-level feature is the ridge density in a fingerprint. Ridge density can be defined as the number of ridges per unit distance. In order to make it invariant to position, the ridge density between two singular points in a fingerprint is computed. Some singular points of interest are defined as the core and delta points (Ratha et al., 1996). The core point is the top most point on the inner most ridge and a delta point is the tri-radial point with three ridges radiating from it (Fig. 2 and Fig. 6).

Figure 6.

Three levels of fingerprint features (Zhang et al., 2011)

Figure 7.

Features at three levels in a fingerprint. (a) Grayscale image (NIST SD30, A067_11), (b) Level 1 feature (orientation field), (c) Level 2 feature (ridge skeleton), and (d) Level 3 features (ridge contour, pore, and dot) (Feng & Jain, 2011)

Recently, fingerprint features have been classified at three distinctive levels of detail (Feng & Jain, 2011; Zhang et al., 2011), as shown in Figs. 6 and 7. Although their definitions for level-1 and level-2 are different, they agree on the definition of level-3. In (Zhang et al., 2011), level-1 features are the macro details of fingerprints, such as singular points and global ridge patterns, e.g., deltas and cores (indicated by red triangles in Fig. 6). They are not very distinctive and are thus mainly used for fingerprint classification rather than recognition. The level-2 features (red rectangles) primarily refer to the minutiae, namely, ridge endings and bifurcations. Level-2 features are the most distinctive and stable features, which are used in almost all automated fingerprint recognition systems and can reliably be extracted from low-resolution fingerprint images (~500 dpi). A resolution of 500 dpi is also the standard fingerprint resolution of the Federal Bureau of Investigation for automatic fingerprint recognition systems using minutiae (Jain et al., 2007). Level-3 features (red circles) are often defined as the dimensional attributes of the ridges and include sweat pores, ridge contours, and ridge edge features, all of which provide quantitative data supporting more accurate and robust fingerprint recognition. Among these features, recent researches are focusing on pores (International Biometric Group, 2008, Jain et al., 2006, Jain et al., 2007, Parsons et al., 2008, Zhao et al., 2008, Zhao et al., 2009), where they are considered to be reliably available only at a resolution higher than 500 dpi.

3. Structural approach

One of the early attempts to automate fingerprint recognition was proposed by (Liu & Shelton, 1970). The fundamental concept underlying the proposed system is to use an operator to recognize the ridge characteristics and to impart to a computer the ability to manipulate and compare the digitized locations and directions of these characteristics for single-fingerprint classification. In (Moayer & Fu, 1975) and (Rao & Balck, 1980), patterns were described by means of terminal symbols and production rules. Terminal symbols are associated to small groups of directional elements within the fingerprint directional image. A grammar is defined for each class and a parsing process is responsible for classifying each new pattern. (Moayer & Fu, 1976) demonstrated how a tree system may be used to represent and classify fingerprint patterns. The fingerprint impressions are subdivided into sampling squares which are preprocessed and postprocessed for feature extraction. A set of regular tree languages is used to describe the fingerprint patterns. In order to infer the structural configuration of the encoded fingerprints, a grammatical inference system is developed.

In (Maio & Maltoni, 1996), a well-defined structural approach for fingerprint classification was presented. The basic idea is to perform a directional image partitioning into several homogeneous regular-shaped regions, which are used to build a relational graph summarizing the fingerprint macro-features. The whole approach can be divided into four main steps: computation of the directional image, segmentation of the directional image, construction of the relational graph, and inexact graph matching. The directional image is computed over a discrete grid by means of a robust technique proposed by (Donahue & Rokhlin, 1993). A dynamic clustering algorithm (Maio et al., 1996) is adopted to segment the directional image according to well-suited optimality criteria. In particular, with the aim of creating regions as homogeneous as possible, the algorithm works by minimizing the variance of the element directions within the regions and, simultaneously, by maintaining the regularity of the region shape. Starting from the segmentation of the directional image, a relational graph is built by creating a node for each region and an arc for each pair of adjacent regions. By appropriately labeling the nodes and arcs of the graph, the authors obtained a structure which summarizes the topological features of the fingerprint and is invariant with respect to displacement and rotation.

The PCASYS approach (Pattern-level Classification Automation SYStem) proposed by (Candela & Chellappa, 1993) and (Candela et al., 1995) assigns fingerprints to six non-overlapping classes. Before computing the directional images, the ridge-line area is separated from the background and an enhancement is performed in the frequency domain. The computation of the directions is carried out by the method reported in (Stock & Swonger, 1969). The directional image is then registered with respect to the core position which corresponds to the fingerprint center. The dimensionality of the directional image, considered as a vector of 1,680 elements, is reduced to 64 elements by using the principal component analysis (Jolliffe, 1986). At this stage, a PNN (Probabilistic Neural Network) (Specht, 1990) is used for assigning each 64-element vector to one class of the classification scheme. In order to improve the classification reliability, especially for whorl fingerprints, the authors also implemented an auxiliary module (called pseudoridge tracer), which works by analyzing the ridge-line concavity under the core position.

(Wahab et al., 1998) described an enhanced fingerprint recognition system consisting of image preprocessing, feature extraction and matching that runs accurately on a personal computer platform. The image preprocessing includes histogram equalization, modification of directional codes, dynamic thresholding and ridgeline thinning. Only the extracted features are stored in a file for fingerprint matching. The matching algorithm presented is a modification and improvement of the structural approach. In their approach, they first divided the original image (320 x 240) into 40 x 30 small areas. Next, each area is assigned a directional code to represent the direction of the ridgeline in that area. To reduce computational time, a total of eight directional codes are used. The eight directional windows w d (d = 0, 1, 2,..., 7), each having a length of 16 pixels are shown in Fig. 8. To find the ridge direction of a given area, each of the directional windows, w d is moved in the direction tangential to the direction of the window. Each of the directional windows will have to move eight times to cover the entire area. At each location when the window moves, the mean value M( Wd) of the grey level of the pixels in the window is calculated. The fluctuation of M(Wd) is expected to be the largest when the movement of the directional window is orthogonal to the direction of the ridges. Therefore this area will be assigned to have ridges in the direction d such that the fluctuation of M( Wd) is the largest.

Figure 8.

Eight directional windows Wd for extraction of ridge direction (Wahab et al., 1998)

4. Ridge orientation approach

Since the performance of a minutiae extraction algorithm relies heavily on the quality of the input fingerprint images, it is essential to incorporate a fingerprint enhancement algorithm in the minutiae extraction module to ensure that the performance of the system is robust with respect to the quality of input fingerprint images. In practice, due to variations in impression conditions, ridge configuration, skin conditions (aberrant formations of epidermal ridges of fingerprints, postnatal marks, and occupational marks), acquisition devices, and non-cooperative attitude of subjects, etc., a significant percentage of acquired fingerprint images is of poor quality. The ridge structures in poor-quality fingerprint images are not always well-defined and, hence, they cannot be correctly detected. This leads to following problems:

  1. a significant number of spurious minutiae may be created,

  2. a large percent of genuine minutiae may be ignored, and

  3. large errors in their localization (position and orientation) may be introduced.

In order to ensure that the performance of the minutiae extraction algorithm is robust with respect to the quality of the input fingerprint images, an enhancement algorithm that improves the clarity of the ridge structures is necessary. Fingerprint enhancement can be conducted on either: 1) binary ridge images or, 2) gray-level images.

A binary ridge image is an image where all the ridge pixels are assigned a value one and nonridge pixels are assigned a value zero. The binary image can be obtained by applying a ridge extraction algorithm on a gray-level fingerprint image. Since ridges and valleys in a fingerprint image alternate and run parallel to each other in a local neighborhood, a number of simple heuristics can be used to differentiate the spurious ridge configurations from the true ridge configurations in a binary ridge image. However, after applying a ridge extraction algorithm on the original gray-level images, information about the true ridge structures is often lost depending on the performance of the ridge extraction algorithm. Therefore, enhancement of binary ridge images has its inherent limitations. In a gray-level fingerprint image, ridges and valleys in a local neighborhood form a sinusoidal-shaped plane wave which has a well-defined frequency and orientation.

Figure 9.

Fingerprint images of very poor quality (Hong et al., 1998)

(Hong et al., 1998) presented a fast fingerprint enhancement algorithm, which can adaptively improve the clarity of ridge and valley structures of input fingerprint images based on the estimated local ridge orientation and frequency using both the local ridge orientation and local frequency information. (Vaikol et al., 2009) presented a reliable method of computation for minutiae feature extraction from fingerprint images. The scheme relies on describing the orientation field of the fingerprint pattern with respect to each minutia detail. A fingerprint image is treated as a textured image, where an orientation flow field of the ridges is computed. To accurately locate ridges, a ridge orientation based computation method is used. After ridge segmentation, smoothing is done using morphological operators.

(Choi et al., 2010) introduced a novel fingerprint matching algorithm using both ridge features and the conventional minutiae features to increase the recognition performance against nonlinear deformation in fingerprints. The proposed ridge features are composed of four elements: ridge count, ridge length, ridge curvature direction, and ridge type. These ridge features have some advantages in that they can represent the topology information in entire ridge patterns that exist between two minutiae and are not changed by non-linear deformation of the finger. For extracting ridge features, they have also defined the ridge-based coordinate system in a skeletonized image. With the proposed ridge features and conventional minutiae features (minutiae type, orientation, and position), they have proposed a novel matching scheme using a breadth first search to detect the matched minutiae pairs incrementally (Fig. 10).

Figure 10.

Example of matched minutiae using the proposed ridge feature vectors (solid circles represent matched minutiae and dotted lines represent the vertical axis of each minutia) (Choi et al., 2010)

5. Pixel-level approach

(Abutaleb & Kamel, 1999) used the fact that a fingerprint is made of white followed by black lines of bounded number of pixels. This enabled the problem formulation to be cast as a parametric optimization problem. The parameters are the widths of the black and white lines in the scanned line in the fingerprint. The proposed adaptive genetic algorithm proved to be effective in determining the ridges or edges in the fingerprint. Further, (Ceguema & Koprinska, 2002) presented an approach for combining local and global recognition schemes for automatic fingerprint verification by using matched local features as the reference axis for generating global features. In their implementation, minutia-based and shape-based techniques were combined. The first one matches local features (minutiae) by a point-pattern matching algorithm. The second one generates global features (shape signatures) by using the matched minutiae as its frame of reference. Shape signatures are then digitized to form a feature vector describing the fingerprint. Finally, a Learning Vector Quantization neural network was trained to match the fingerprints using the difference between a pair of feature vectors.

In (Zhang et al., 2010), investigation has been conducted on analyzing the mechanisms of fingerprint image rotation processing and its potential effects on the major features, mainly minutiae and singular point, of the rotation transformed fingerprint. It was observed that the information integrity of the original fingerprint image can be significantly compromised by the image rotation transformation process, which can cause noticeable singular point change and produce non-negligible number of fake minutiae. It is found that the quantization and interpolation process can change the fingerprint features significantly though they may not change the image visually. Their experimental results have shown that up to 7% of the minutiae can be mis-matched. For the matched ones, their positions deviate up to 16 pixels. The position of singular point can change up to 55 pixels while the orientation angle change can be up to 90 degrees. (Kaur et al., 2010) proposed an approach for feature extraction based on dividing the image into equal sized blocks. Each block is processed independently. The gray level projection along a line perpendicular to the local orientation field provides the maximum variance. Then the ridges are located using the peaks and the variance in this projection. The ridges are thinned and the resulting image is enhanced using an adaptive morphological filter.

Square-based method was presented in (Gamassi et al., 2005) and (Alibeigi et al., 2009). The Square-based method is composed of the following steps, repeated for each pixel of the binary image:

1. Create a 3x3 square mask around the (x, y) pixel and compute the average of the pixels. If the average is less than 0.25 the pixel is preliminary identified as a ridge termination minutiae, otherwise if the average is greater than 0.75 the pixel is treated like a bifurcation minutiae.

2. Create a square perimeter P around the (x, y) pixel of size W×W.

3. Compute the number of the logic commutations present in the perimeter P without considering isolated pixels as shows in Fig. 11.

Figure 11.

Processing the commutations (Gamassi et al., 2005)

4. The algorithm continues if there are two logic commutations, otherwise it jumps to step 1 processing another pixel.

5. Compute the average of the pixels in the perimeter P. If the pixel has been defined as a termination minutiae in step 1, it checks if the average is greater than the threshold K. (in bifurcation minutiae, the average must be less than 1-K) otherwise it jumps to step 1 processing another pixel.

6. Estimate the orientation angle α in the minutiae point.

7. False detection removal (Fig. 12).

Figure 12.

Estimating the orientation angle (left) and removing the false terminations detections (right) (Gamassi et al., 2005)

6. Filtering and wavelet approach

(Lee & Wang, 1999) have developed a one-step method using Gabor filters for directly extracting fingerprint features for a small-scale fingerprint recognition system. From the experimental results, the use of magnitude Gabor features with eight orientations as fingerprint features led to good shift-invariant properties and an accuracy of 97.2% with 3-NN classifiers, on a database of 192 inked fingerprint images from 16 persons. In (Watson et al., 1994) and (Willis & Myers, 2001), the fingerprint’s blockwise Fourier transform is multiplied by its power spectrum raised to a power, thus magnifying the dominant orientation.

Also, a Laplacian-like image pyramid is used to decompose the original fingerprint into sub-bands corresponding to different spatial scales for fingerprint enhancement. The Laplacian pyramid (Adelson et al., 1984), (Simoncelli & Freeman, 1995) is equivalent to bandpass filtering in the spatial domain. In a further step, contextual smoothing is performed on these pyramid levels, where the corresponding filtering directions stem from the frequency-adapted structure tensor. For minutiae extraction, parabolic symmetry is added to the local fingerprint model which allows to accurately detecting the position and direction of a minutia simultaneously.

Also, (Cappelli et al., 1999) have implemented the directional approach. The directional image is partitioned into “homogeneous” connected regions according to the fingerprint topology, thus giving a synthetic representation which can be exploited as a basis for the classification. A set of dynamic masks, together with an optimization criterion, was used to guide the partitioning. The adaptation of the masks produces a numerical vector representing each fingerprint as a multidimensional point, which can be conceived as a continuous classification. Different search strategies were discussed to efficiently retrieve fingerprints both with continuous and exclusive classification. A directional image is a discrete matrix whose elements represent the local average directions of the fingerprint ridge lines.

(Hong et al., 1998) proposed an algorithm using Gabor bandpass filters tuned to the corresponding ridge frequency and orientation to remove undesired noise while preserving the true ridge-valley structures. All operations are performed in the spatial domain, whereas the contextual filtering in (Sherlock et al., 1994) and (Chikkerur & Govindaraju, 2005) is done in the Fourier domain. From (Tico et al., 2001), the discrete wavelet transform (DWT) coefficients have been used as the ridge pattern. The authors discussed that the middle frequency has an oscillated pattern corresponding to the ridge pattern. Then, to extract wavelet features from a gray-scale fingerprint image, the image was first cropped to the size of 64×64 pixels, where the center point in the image is referred to as a reference point. The cropped image was then quartered, centered at the reference point, to obtain four non-overlapping images of size 32×32 pixels. After applying the DWT to each non-overlapping image four times, twelve sub-images in the wavelet domain at each decomposition level are created as shown in Fig. 13. Next, the standard deviation of the DWT coefficients from each sub-image is computed to create a feature vector of length 48 (12 DWT sub-images from 4 non-overlapping images). The resulted feature vector is then used as a representation of that fingerprint image.

Figure 13.

Arrangements of twelve sub-images in the wavelet domain (Tico et al., 2001)

On the other hand, it was shown in (Tachaphetpiboon & Amornraksa, 2005, 2007) that the discrete cosine transform (DCT) is better suited in extracting informative features than the DWT. The results have shown that the fingerprint matching system based on the DCT obtained a high recognition rate and a lower complexity. (Tachaphetpiboon & Amornraksa, 2005) proposed to divide all the DCT coefficients containing the oscillate pattern in a zigzag-scanned fashion, extract DCT features from the divided DCT coefficients, and then use them for fingerprint matching. Accordingly, all the DCT coefficients in each non-overlapping image were divided into 12 areas, where one feature was extracted from each one of these areas, generating 12 features for each non-overlapping image.

(Fronthaler et al., 2008) proposed the use of an image-scale pyramid and directional filtering in the spatial domain for fingerprint image enhancement to improve the matching performance as well as the computational efficiency. Image pyramids or multiresolution processing is especially known from image compression and medical image processing. (Fronthaler et al., 2008) expected that all the relevant information to be concentrated within a few frequency bands. Furthermore, they have proposed Gaussian directional filtering to enhance the ridge-valley pattern of a fingerprint image using computationally cheap 1-D filtering on higher pyramid levels (lower resolution) only. The filtering directions are recovered from the orientations of the structure tensor (Bigun, 2006) at the corresponding pyramid level. Linear symmetry features are thereby used to extract the local ridge-valley orientation (angle and reliability).

(On et al., 2006) presented a filtering strategy that can solve the problem of rotated scanned input images. The fingerprint image is scanned with an optical fingerprint scanner. The scanned fingerprint image is saved in bitmap format with black and white colour. The scanned fingerprint image is then enhanced for quality improvement. Further, the enhanced fingerprint image is applied for binarization. The conversion is needed to reduce the computation and analysis time for filtering and thinning process. The noise produced from the binarized fingerprint image is then removed using median filtering and the filtered fingerprint image is further thinned. After that, the bifurcation minutiae extraction method is applied for the thinned fingerprint image. The extracted feature data are then used for neural network training.

The concept of spectral minutiae representation was used by (Xu & Veldhuis, 2009). The spectral minutiae representation is based on the shift, scale and rotation properties of the two-dimensional continuous Fourier transform. Assume a fingerprint with Z minutiae. In location-based spectral minutiae representation (SML), with every minutia, a function m i (x, y) = δ(x − x i , y − y i ), i = 1,..., Z is associated where (x i , y i ) represents the location of the i-th minutia in the fingerprint image. Thus, in the spatial domain, every minutia is represented by a Dirac pulse. The Fourier transform of m i (x, y) is given by:

{mi(x,y)}=exp(j(wxxi)+wyyi)E1

and the location-based spectral minutiae representation is defined as

ML(wx,wy)=i=1Zexp(j(wxxi+wyyi))E2

In order to reduce the sensitivity to small variations in minutiae locations in the spatial domain, a Gaussian low-pass filter is used to attenuate the higher frequencies. This multiplication in the frequency domain corresponds to a convolution in the spatial domain where every minutia is now represented by a Gaussian pulse. Following the shift property of the Fourier transform, the magnitude of M is taken in order to make the spectrum invariant to translation of the input, and we obtain

|ML(wx,wy;σL2)||exp(wx2+wy22σL2)i=1Zexp(j(wxxi+wyyi))|E3

Then, the orientation information in the spectral representation is included. The orientation θ of a minutia can be incorporated by using the spatial derivative of m(x, y) in the direction of the minutia orientation. Thus, to every minutia in a fingerprint, a function m i (x, y, θ) is assigned being the derivative of m i (x, y) in the direction θ i , such that

{mi(x,y,θ)}=j(wxcosθi+wysinθi)exp(j(wxxi+wyyi))E4

As with the SML algorithm, using a Gaussian filter and taking the magnitude of the spectrum yields

|MO(wx,wy;σO2)|=|exp(wx2+wy22σO2)j(wxcosθi+wysinθi)exp(j(wxxi+wyyi))|E5

Recently, (Xu & Veldhuis, 2010) have further discussed the objective of the spectral minutiae representation in representing a minutiae set as a fixed-length feature vector that is invariant to translation, rotation and scaling. Fig. 14 illustrates a general procedure of the spectral minutiae representation discussed by (Xu & Veldhuis, 2010).

Figure 14.

Illustration of the general spectral minutiae representation procedure. (a) a fingerprint and its minutiae; (b) representation of minutiae points as real (or complex) valued continuous functions; (c) the 2D Fourier spectrum of ‘b’ in a Cartesian coordinate and a polar-logarithmic sampling grid; (d) the Fourier spectrum sampled on a polar-logarithmic grid (Xu & Veldhuis, 2010)

Moreover, based on the spectral minutiae feature, (Xu et al., 2009a, 2009b) introduced two feature reduction methods: the Column-Principal Component Analysis (PCA) and the Line-Discrete Fourier Transform feature reduction algorithms. The experiments demonstrated that these methods decrease the minutiae feature dimensionality with a reduction rate of 94%, while at the same time, the recognition performance of the fingerprint system is not degraded. On the other hand, (Dadgostar et al., 2009) presented a novel feature extraction method based on Gabor filter and Recursive Fisher Linear Discriminate (RFLD) algorithm, for fingerprint identification. The proposed method was assessed on images from the biolab database (Biometric System Lab). Experimental results have shown that applying RFLD to a Gabor filter in four orientations, in comparison with Gabor filter and PCA transform, increases the identification accuracy from 85.2% to 95.2% by nearest cluster center point classifier with Leave-One-Out method. Also, it has been shown that applying RFLD to a Gabor filter in four orientations, in comparison with Gabor filter and PCA transform, increases the identification accuracy from 81.9% to 100% by 3NN classifier.

7. Geometric approach

(Chen et al., 2009) proposed an algorithm to use minutiae for fingerprint recognition, in which the fingerprint’s orientation field is reconstructed from minutiae and further utilized in the matching stage to enhance the system’s performance. First, they have produced “virtual” minutiae by using interpolation in the sparse area, and then used an orientation model to reconstruct the orientation field from all “real” and “virtual” minutiae (Fig. 15). A decision fusion scheme is used to combine the reconstructed orientation field matching with the conventional minutiae-based matching. (Min & Thein, 2009) have presented a recognition system which combines both the statistical and geometry approaches. The core point (CP) of the input fingerprint is detected and located in the centre. Then, the fingerprint image is cropped around the based point. Fingerprint features such as minutiae points' determination, their coordinates location, and radius of arcs for each ridge are stored in different databases. For a testing fingerprint image, the features are compared with these pre-defined databases and the decision is made by a voting system.

In (Wei-bo et al., 2008), each minutia was defined by the type and the relative topological relationship among the minutia and its 5 nearest neighbors. (Qi et al., 2008) proposed a fingerprint matching algorithm using the elaborate combination of minutiae and curvature maps from fingerprint images. First, they computed the curvature in a simple way based on orientation field, and then performed the sampling operation on the curvature map around each minutia to get the fixed length minutiae specifiers. Second, a similarity measurement was defined between two specifiers. Third, they found the reference points pair based on computing the least squared error of Euclidean distance between these two specifiers. Finally, they completed the matching task by aligning the two fingerprint minutiae sets and accounting the number of overlapping minutiae.

Figure 15.

Interpolation step: (a) the minutiae image; (b) the triangulated image; (c) virtual minutiae by interpolation (the bigger red minutiae are “real,” while the smaller purple ones are “virtual”) (Chen et al., 2009)

8. Singularity approach

The global features of a fingerprint are singularity points, namely core and delta. Generally, singularity points are used to classify fingerprint images to reduce the search space. (Kryszczuk & Drygajlo, 2006) presented a method in which the singular point detection is performed by analyzing the local quadrant change of the ridge gradient vectors. Singular points (SP) are defined as discontinuities in the directional field (Liu et al., 2005). In formally, this can be stated as the area where ridges oriented rightwards change to leftwards and those that were oriented upwards turn downwards, and opposite. Their algorithm performs a robust estimation of the local ridge gradient. They employed a modified version of the “squared average gradients” to estimate the direction of the smoothed gradient vectors. Also, they allowed cancelling out the opposite local gradients, achieving a more robust average local ridge gradient estimation. Moreover, (Militello et al., 2008) proposed a fingerprint recognition approach based on core and delta singularity points detection. The singularity points extraction is performed using three sequential steps: directional image extraction, Poincarè indexes computation and core and delta extraction. The approach has shown a good accuracy level in the singularity points detection and extraction and a low computational cost.

(Conti et al., 2010) proposed another fingerprint recognition that is based on singularity points detection and singularity regions analysis. Despite to the classical minutiae-based fingerprint recognition system, the proposed system is based on core and delta position, their relative distance and orientation to perform both classification and matching tasks. The proposed approach enhances the performance of singularity points based methods by introducing pseudo-singularity points when the standard singularity points (core and delta) cannot be extracted. As a result, singularity points and/or pseudosingularity-points are detected and extracted to make possible successful fingerprint classification and recognition. After singularity points extraction, a roto-translation operation is applied for fingerprint image registration. Finally, a matching algorithm based on morphological operation, such as dilation and erosion, on two considered regions of interests (singularity regions or pseudo singularity regions) around core and delta is performed. The obtained similarity degree considering the regions of interest gives the matching result. The experimental results have shown good accuracy levels, reaching a FAR=1.22% and a FRR=9.23% using FVC2002 DB2-A database, and in the best of case, a FAR=0.26% and a FRR=7.36% using FVC2000 DB1-B database.

9. Pore approach

Recently, researchers have focused on pores as a distinctive fingerprint features (International Biometric Group, 2008; Jain et al., 2006, 2007; Parsons et al., 2008; Zhang et al., 2011; Zhao et al., 2008; Zhao et al., 2009). Focusing on this kind of features depends heavily on the quality of the digital fingerprint image. Resolution is one of the main parameters affecting the quality of a digital fingerprint image, and so, it has an important role in the design and deployment of fingerprint recognition systems and impacts both their cost and recognition performance. Despite this, the field of fingerprint recognition does not currently have a well-proven reference resolution or standard resolution that can be used interoperably between different systems. For example, (Jain et al., 2007) chose a resolution of 1,000 dpi based on the 2005 ANSI/NIST fingerprint standard update workshop. (Zhao et al., 2008, 2009) proposed some pore extraction and matching methods at a resolution of 902 dpi x 1200 dpi. Finally, the International Biometric Group analyzed level-3 features at a resolution of 2000 dpi.

(Zhao & Jain, 2010) have studied the utility of pores on rolled ink fingerprint images which are widely used in forensic applications. Fingerprint images of three different qualities at two different resolutions (500ppi and 1000ppi) were considered in their experiments. By using NIST SD30 database, and a commercial minutiae matcher, they have investigated the impact of fingerprint image quality on the accuracy of automatic pore extraction, and the effectiveness of pores in improving fingerprint recognition accuracy. The experimental results have shown that the (i) pores do not provide any significant improvement to the fingerprint recognition accuracy on 500ppi fingerprint images, and (ii) fusion of pore and minutiae matchers is effective only for high resolution (1000ppi) fingerprint images of good quality.

(Zhang et al., 2011) have taken further steps toward establishing a reference resolution, assuming a fixed image size and making use of the two most representative fingerprint features, i.e., minutiae and pores, and providing a minimum resolution for pore extraction that is based on anatomical evidence. They conducted experiments on a set of fingerprint images of different resolutions (from 500 to 2000 dpi). By evaluating these resolutions in terms of the number of minutiae and pores, their results have shown that 800 dpi would be a good choice for a reference resolution. (Malathi & Meena, 2010) presented a suitable technique for partial fingerprint matching based on pores and its corresponding Local Binary Pattern (LBP) features. The first step involves extracting the pores from the partial image. These pores act as anchor points where a sub window (32x32) is formed to surround them. Then rotation invariant LBP histograms are obtained from this surrounding window. Finally, a chi-square formula is used to calculate the minimum distance between two histograms to find the best matching score.

10. Other approaches

In this section we present an overview of some other general techniques proposed for fingerprint recognition. Neural network approaches are mostly based on multilayer perceptrons or Kohonen self-organizing networks (Bowen, 1992, Hughes & Green, 1991, Kamijo, 1993, Moscinska & Tyma, 1993). In particular, (Kamijo, 1993) presented an interesting pyramidal architecture constituted by several multilayer perceptrons, each of which was trained to recognize fingerprints belonging to different classes. (Wang et al., 2008) proposed the cellular neural/nonlinear network (CNN) as a powerful tool for fingerprint feature extraction. They presented two theorems for designing two kinds of CNN templates. These two theorems provided the template parameter inequalities to determine parameter intervals for implementing the corresponding functions. (Senior, 1997) proposed a hidden Markov model classifier whose input features are the measurements (ridge angle, separation, curvature, etc.) taken at the intersection points between some horizontal- vertical fiducial lines and the fingerprint ridge lines. (Yang et al., 2008) proposed a fingerprint matching algorithm based on invariant moments. (Montesanto et al., 2007) have studied the fingerprint verification based on the fuzzy logic, where they combined the results obtained using three different methods of minutiae extraction: the sequential method, the reactive agent and the neural classification system.

(Puertas et al., 2010) studied the performance of a fingerprint recognition technology, in several practical scenarios of interest in forensic casework. First, the differences in performance between manual and automatic minutiae extraction for latent fingerprints were presented. Then, automatic minutiae extraction was analyzed using three different types of fingerprints: latent, rolled and plain. The experiments were carried out using a database of latent fingermarks and fingerprint impressions from real forensic cases.

11. Quality assessment methods

Fingerprint quality is usually defined as a measure of the clarity of ridges and valleys and the extractability of the features used for identification such as minutiae, core and delta points, etc. Therefore, it is important to estimate the quality and validity of the fingerprint images in order to improve recognition performance. A number of factors can affect the quality of fingerprint images (Joun et al., 2003): occupation, motivation/collaboration of users, age, temporal or permanent cuts, dryness/wetness conditions, temperature, dirt, residual prints on the sensor surface, etc. Unfortunately, many of these factors cannot be controlled and/or avoided. For this reason, assessing the quality of captured fingerprints is important for a fingerprint recognition system.

(Qi et al., 2005) proposed a hybrid scheme to measure quality by considering local and global features. They used seven quality indices and analyzed the correlation between the quality value and each quality index. (Chen et al., 2005) suggested quality estimation methods based on the power spectrum analysis in the 2-D Fourier domain and coherence in the spatial domain.

ISO/INCITS-M1 (International Standards Organization/International Committee for Information Technology Standards) has established a biometric sample-quality draft standard (Int. Com. Inf. Technol. Standards, 2005), in which a biometric sample quality is considered from three different points of view: 1) character, which refers to the quality attributable to inherent physical features of the subject; 2) fidelity, which is the degree of similarity between a biometric sample and its source, attributable to each step through which the sample is processed; and 3) utility, which refers to the impact of the individual biometric sample on the overall performance of a biometric system, where the concept of sample quality is a scalar quantity that is related monotonically to the performance of the system. The character of the sample source and the fidelity of the processed samples contribute to, or similarly detract from, the utility of the sample. It is generally accepted that the utility is most importantly mirrored by a quality metric (Grother & Tabassi, 2007), so that images assigned higher quality shall necessarily lead to better identification of individuals (i.e., better separation of genuine and impostor match score distributions).

A theoretical framework for a biometric sample quality has been developed by (Youmaran & Adler, 2006), where they relate biometric sample quality with the identifiable information contained. They defined “Biometric information” (BI) as the decrease in uncertainty about the identity of a person due to a set of biometric measurements. BI is calculated by the relative entropy between the population feature distribution and the person’s feature distribution. The results reported by (Youmaran & Adler, 2006) show that degraded biometric samples result in a decrease in BI. In (Van derWeken et al., 2007), a number of quality metrics can be found aimed at objectively assessing the quality of an image in terms of the similarity between a reference image and a degraded version of it.

Finally, (Lee et al., 2008) proposed a fingerprint-quality measurement method based on the shapes of several probability density functions (PDFs). The 2-D gradients of the fingerprint images are first separated into two sets of 1-D gradients. Then, the shapes of the PDFs of these gradients are measured in order to determine the fingerprint quality.

12. Conclusion

In this chapter, we have presented a study covering different automatic fingerprint recognition techniques, presented by the experts in this field. Although many academic and commercial systems for fingerprint recognition exist, there is a necessity for further research in this topic in order to improve the reliability and performances of the current systems. Many unresolved problems still need to be explored and investigated. For example, for a large automated fingerprint identification system, the recognition accuracy, matching speed and its robustness to poor image quality are normally regarded as the most critical elements of system performance. Also, fast comparison algorithm is necessary since most minutiae-based matching algorithms will fail to meet the high speed requirement. Further, matching partial fingerprints still needs lots of improvement. The major challenges faced in partial fingerprint matching are the absence of sufficient level 2 features (minutiae) and other structures such as core and delta. Thus, common matching methods based on alignment of singular structures would fail in case of partial prints. Pores (level 3 features) on fingerprints have proven to be discriminative features and have recently been successfully employed in automatic fingerprint recognition systems. Finally, there is still a lot of research to be done when dealing with latent fingermarks. Low quality, incompletion and distortion are typical problems that forensic fingerprint recognition systems have to face when extracting features from latent fingermarks.

Acknowledgments

The author would like to acknowledge and thank Kuwait Foundation for the Advancement of Sciences (KFAS) for financially supporting this work.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Naser Zaeri (June 20th 2011). Minutiae-based Fingerprint Extraction and Recognition, Biometrics, Jucheng Yang, IntechOpen, DOI: 10.5772/17527. Available from:

Embed this chapter on your site Copy to clipboard

<iframe src="http://www.intechopen.com/embed/biometrics/minutiae-based-fingerprint-extraction-and-recognition" />

Embed this code snippet in the HTML of your website to show this chapter

chapter statistics

7382total chapter downloads

8Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Non-minutiae based fingerprint descriptor

By Jucheng Yang

Related Book

First chapter

Biometrics on mobile phone

By Shuo Wang and Jing Liu

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More about us