Fingerprint algorithm recognition

Introduction

A fingerprint-based biometric system is essentially a pattern recognition system that recognizes a person by determining the authenticity of her fingerprint. Depending on the application context, a fingerprint-based biometric system may be called either a verification system or an identification system:

• a verification system authenticates a person’s identity by comparing the captured fingerprints with her own biometric template(s) pre-stored in the system. It conducts a one-to-one comparison to determine whether the identity claimed by the individual is true;

• an identification system recognizes an individual by searching the entire template database for a match. It conducts one-to-many comparisons to establish the identity of the individual.

The performance of minutiae extraction algorithms and other fingerprint recognition techniques relies heavily on the quality of the input fingerprint images. In an ideal fingerprint image, ridges and valleys alternate and flow in a locally constant direction. However, the fingerprint images obtained are usually poor due to elements that corrode the clarity of the ridge elements. This leads to problems in minutiae extraction.

The goal of this article is to review a fingerprint recognition algorithm based on genetic algorithms and tools for filtering images. The results are retrieved and validated using Python.

Source code https://github.com/cuevas1208/fingerprint_recognition/blob/master/utils/normalization.py

Segmentation

To define the ROI a mask is created using blockwise coherence to segment the ridges from the background. There are more robust methods for segmentation[1] however the method I used is based on the calculation of the variance of gray levels. Image is divided into sub-blocks of (W × W) size’s and for each block, the variance is calculated.

V = 1n mi=0n-1j=0m-1(I(i,j)-M)2

Then, the root of the variance of each block is compared with a threshold T based on the global variance of the image, if the value obtained is lower than the threshold, then the corresponding block is considered as the background of the image and will be excluded by the subsequent processing. Otherwise, the block will be considered as a useful part of the image. The selected threshold value for this repository is T = 0.2*std(image) and the selected block size is W = 16 [7]. This step makes it possible to reduce the size of the useful part of the image and subsequently to optimize the extraction phase of the biometric data.

After the mask is created, the mask is smooth with an open/close morphological filter, to eliminate possible mask outliers. Two Morphological operations called ‘OPEN’ and ‘CLOSE’ are adopted. The ‘OPEN’ operation can expand images and remove peaks introduced by background noise. The ‘CLOSE’ operation can shrink images and eliminate small cavities.

Image normalization is calculated based on the segmented image.

Source code: https://github.com/cuevas1208/fingerprint_recognition/blob/master/utils/segmentation.py

Orientation field

Sobel filters were used to obtain the direction of the field. The 3 by 3 operators Gx and Gy are used to obtain the gradients in horizontal and vertical directions.

Thus, the local direction in the vicinity V, in the direction of the lines (Vx (i, j)) and in the direction of the columns (Vy (i, j)) is estimated by the following calculation:

The estimation of the local orientation in the neighborhood V is Ѳ (i, j) such that:

For fingerprint images, the average width of the ridge or valley is five to eight pixels, so W1 = 16 gives a good orientation estimate and saves computational time.

There are two reasons for the failure of the orientation measure [11]. The neighborhood may contain a constant gray value area or an isotropic gray value structure without a preferred orientation. To distinguish these two cases we need to compare the magnitude of the orientation vector with the mean square magnitude of the gradient.

The directional map defines the local orientation of the striates contained in the impression. The estimation of orientation is a fundamental step in the process of image enhancement based on Gabor’s filtering. (figure 3)

Source code: https://github.com/cuevas1208/fingerprint_recognition/blob/master/utils/orientation.py

Frequency map

Calculation of a frequency block In addition to the directional map we must have the local estimation of the frequency map to be able to construct the Gabor filter. The frequency map of the image consists of estimating the local frequency of the streaks in each pixel. The steps in the frequency estimation stage are:

1. Divide the image into blocks of size W×W.
2. Project the pixels located inside each block along a direction orthogonal to the local ridge orientation. It forms an almost sinusoidal-shape wave with the local minimum points corresponding to the ridges in the fingerprint.
3. Calculate the ridge spacing by counting the number of pixels between consecutive minima points in the projected waveform. If the block contains at less than two maxima the period is set to zero and it is considered noise. The maxima are the centers of the streaks and the minima are the centers of the valleys. The set of successive maxima and minima represents what is called extrema.
4. Determine the wavelength(T) by dividing the distance from the first peak to the last peak, if the wavelength is outside the allowed bounds, the frequency image is set to zero
5. Calculate the frequency by the ratio (1 / T) where T represents the period calculated between two successive extrema.

Source code: https://github.com/cuevas1208/fingerprint_recognition/blob/master/utils/frequency.py

Gabor Filter

Hong, Wan, and Jain [10] proposed an effective method based on Gabor filters. Gabor filters have both frequency-selective and orientation-selective properties and have an optimal joint resolution in both spatial and frequency domains. A graphical representation of a bank of 24 filters and an example of their applications is shown below. Further information on the huge number of existing fingerprint enhancement and binarization techniques can be found in [2].

The principle of filtering is to modify the value of the pixels of an image, generally in order to improve its appearance. In practice, it is a matter of creating a new image using the pixel values of the original image, in order to select in the Fourier domain the set of frequencies that make up the region to be detected. The filter used is the Gabor filter with even symmetry and oriented at 0 degrees (formula 15):

To obtain other orientations, it is sufficient to carry out a rotation of the coordinate axes according to the formula:

According to the different blocks of the image, the filter can have several favored directions. In this case, the final filter is a sum of basic filters placed in each direction. The resulting image will be the spatial convolution of the original (normalized) image and one of the base filters in the direction and local frequency from the two-directional and frequency maps:

with: — E(i,j) is the new value of the pixel (i, j) — O(i,j) and F(i,j) Are the values of the pixels (i, j) of the directional and frequency maps. — and Are respectively the length and the width of the block used for the convolution.

Source code: https://github.com/cuevas1208/fingerprint_recognition/blob/master/utils/gabor_filter.py

Thinning

To facilitate extraction of minutiae the image must be skeletonized: a sequence of morphological

erosion operations are used to eliminate the redundant pixels of ridges until the ridges are just one pixel wide. While some papers use Rosenfeld algorithm for its simplicity[3]. I used skimage Zha84 A fast parallel algorithm for thinning digital patterns[4]

Source code: https://github.com/cuevas1208/fingerprint_recognition/blob/master/utils/skeletonize.py

Minutiae extraction

Crossing number method is a really simple way to detect ridge endings and ridge bifurcations. The crossing number algorithm will look at 3x3 pixel blocks. The value of the CN is calculated according to formula 18: [5][6]

if the middle pixel is black (represents ridge):

if the pixel on boundary crossed the ridge once, then we’ve found ridge ending

if the pixel on boundary crossed the ridge three times, then we’ve found ridge bifurcation

There are other minutiae extraction approaches that work directly on the gray-scale images without binarization and thinning. This choice is motivated by these considerations:

• information may be lost during the binarization process
• binarization and thinning are time-consuming

Maio and Maltoni [8] proposed a direct gray-scale minutiae extraction technique that may be worth looking at it.

Source code: https://github.com/cuevas1208/fingerprint_recognition/blob/master/utils/crossing_number.py

Singularities

Uses the Poincaré index method proposed by Kawagoe and Tojo (1984).

Let G be the field associated with a fingerprint orientation and let [i,j] be the position of the element. Computed as follows.

• The curve C is a closed path defined as an ordered sequence of some elements of D, such that [i,j] is an internal point;

• PG, C(i,j) is computed by algebraically summing the orientation differences between adjacent elements of C.

It is well known and can be easily shown that, on closed curves, the Poincaré index assumes only one of the discrete values: 0°, ±180°, and ±360°. In the case of fingerprint singularities:

0° does not belong to any singular region.

360° belongs to a whorl type singular region

180° belongs to a loop type singular region

-180° belongs to a delta type singular region

Source code: https://github.com/cuevas1208/fingerprint_recognition/blob/master/utils/poincare.py

References:

[1] Bazen, A.M., Gerez, S.H.: Segmentation of Fingerprint Images. Proc. Workshop on Circuits Systems and Signal Processing (ProRISC 2001) (2001) 276−280.

[2] Maltoni, D., Maio, D., Jain, A.K., Prabhakar, S.: Handbook of Fingerprint Recognition, Springer, New York (2003).

[3] Farah Dhib Tatar, “Finger Recognition Algorithm”

[4] T. Y. Zhang and C. Y. Suen, Communications of the ACM, March 1984, Volume 27, Number 3.

[5] Jin Bo, Tang Hua Ping, Xu Ming Lan, “Fingerprint Singular Point Detection Algorithm by Poincaré Index”

[6] A.K. Jain, S. Prabhakar and S. Pankanti, “Twin Test: On Discriminability of Fingerprints”, Proc. 3rd International Conference on Audio- and Video-Based Person Authentication, pp. 211–216, Sweden, June 6–8, 2007.

[7] A.K. Jain, S. Prabhakar and S. Pankanti, “Twin Test: On Discriminability of Fingerprints”, Proc. 3rd International Conference on Audio- and Video-Based Person Authentication,, pp. 211–216, Sweden, June 6–8, 2007.

[8] Maio, D., Maltoni, D.: Ridge-Line Density Estimation in Digital Images. Proc. Int. Conf. on Pattern Recognition (14th) (1998) 534−538.