Comparison between Minutiae Based and Pattern Based Algorithm of Fingerprint Image

Published Online March 2016 in MECS

Biometric is a technique to recognize a person identity. It is mostly used in criminal investigation, Security and educational areas. Mostly used biometric techniques are Iris, palm-print, voice and fingerprint recognition [11]. Among these techniques, fingerprint recognition is the well known and accurate method. To recognize a person identity it is necessary to match his fingerprint with the templates stored in the database. Matching is based on the information included in the fingerprint image.

The fingerprint image contains minutiae points, core points, ridges and valleys, background area, foreground areas, local features and global features. Minutiae points are the small lines in fingerprint image. Core point is the central area of fingerprint image. It is the most upper point of innermost area. Ridges are the black lines of fingerprint image and valleys are the white lines of fingerprint image.

Fig.1. Fingerprint Structure

Background area

Background area contains the noise and Foreground area is the main informational part. Global feature contain whole structure of fingerprint image and local features are the singular points in the fingerprint image.

There are mainly eight types of minutiae points in a fingerprint image are ridge ending, crossover, bridge, hook, bifurcation, dot, enclosure and delta. From these eight minutiae’s ridge ending and bifurcation are the points on which the fingerprint matching algorithm depends. Bifurcation is the point which further divides into two ridges like Y shape. Ridge ending is the termination point which end abruptly.

There are two methods for fingerprint matching i.e. Minutiae-based and pattern based. Minutiae based methods are the singular points exist in fingerprint image. They can also be called the local features of fingerprint image. Bifurcation, termination, bridge, hook, trifurcation etc. are all the singular points exist in fingerprint image. It is impossible to find more than seven common minutiae points in two different fingerprint images. Pattern based method includes Global as well as local features which covers the whole area of fingerprint image. Delta and core are the global features of fingerprint image. This is the fast technique than minutiae based method because it includes every macro and micro part of the fingerprint.

A fingerprint image has four type patterns i.e. whorl, right loop, left loop and arch. One or more ridges entering and exiting from same side in a curvy form of fingerprint is called loop. Loop is of two types i.e. left loop and right loop. Whorl can be plain, central pocket, double loop, and accidental. Plain whorls have atleast one ridge that makes

Fig.3. Fingerprint Classification a complete circuit, and an imaginary line from one delta to the other must touch a whorl ridge. Central pocket whorls must have at least one ridge that makes a complete circuit, and an imaginary line from one delta to the other cannot touch a whorl ridge. Double loop is two loops combined to make one whorl. Any other types not in the three categories are called accidentals. Arch ridges enter from one side leave out from the other side. They are of two types tented arch and plain arch.

This paper introduce algorithm for fingerprint matching using pattern based method. First of all it enhances the image using intensity adjustment method which removes all the ambiguity from the image. Then image segmentation and Binarization is done. Binarization converts a grey level image into a binary image. The segmentation defines which part of fingerprint image belongs to background and foreground area. Principal component analysis method converts the higher dimensional space to lower dimensional space. Gabor filter are applied on lower dimensional space to extract the feature vectors. The feature vectors generate feature maps. And this feature map is matched with the fingerprint image stored in the database. Euclidean distance helps in matching the two fingerprint using threshold value. If the Euclidean distance between two feature maps is less than the threshold value than it is match of stored template and acquired template otherwise they considered the two different images from different fingers.

• II.    Literature Survey

There are so many algorithms used in the field of recognition and matching of fingerprint images. Matching of an algorithm includes various steps like enhancement, segmentation, feature extraction, matching, filtering etc. Following are the related work to the proposed algorithm.

Asif Iqbal Khan et al explained the minutiae based method used for recognition of fingerprint image. Valid minutiae and bifurcation points are extracted using Crossnumbering method. Here cross-numbering method used the example of 4x4 window instead of 3x3 window to remove duplicate minutiae points. Before extraction process image enhancement, Binarization, thinning and minutiae marking is done. Using 3x3 window duplicate bifurcation points are detected which are removed by false minutiae removal technique. After applying the proposed solution the number of valid bifurcation points has increased by approximately 55% and all the bifurcation points which were missed earlier have been included [2].

Muhammad Umer Munir et al described Matching algorithm of two fingerprint images by using Gabor filtering method. It includes three steps, firstly it extract the Core point of fingerprint image using Poincare and slope method. Second, the circular region is divided around core point into 128 sectors and the pixel intensities in each sector are normalized to a constant mean and variance. The circular region is filtered using a bank of sixteen Gabor filters. Feature vectors are generated using Gabor filters. And last the Euclidean distance is calculated between two feature vectors. The performance is measured using Genuine Accept Rate (GAR) against the False Accept Rate (FAR) [1].

Ala Balti et al introduces a new algorithm which includes Euclidean distance for fingerprint identification. Euclidean distance calculates the distance between central point and nearest neighbor bifurcation minutiae’s. This new algorithm reduces the number of feature vector and avoids the problem of geometric rotation and translation over the acquisition phase of fingerprint image. The new algorithm first determines the centre point and then perform enhancement on it. After the feature extraction Euclidean distance is calculated. Normalization is done after short the Euclidean distance vectors [3].

Wang Yongxu et al described PCA (principal component analysis) used to extract statistical feature of ROI to form feature vector. PCA translate an image MXN to a vector form into row and column. Pca normalized the feature vectors by choosing uncommon feature vectors. Here PCA is performed only on ROI rather than whole fingerprint image. After applying PCA the Euclidean distance is calculated between two feature vectors extracted from ROI. This method dependents on the central position of fingerprint image because low quality or non central image cause failure to detect centre position [4].

• M. Horton et al introduced the complex 2-D Gabor filters for fingerprint matching system. Here image is divided into two parts and then 2-D Gabor filters are applied. These filters enhance the ridges that are oriented at the same angle as the filter while suppressing ridges oriented at other angles. Once the images are filtered, statistical information is gathered for each of the regions within the image [5].

• III.    Exsiting Algorithm

The existing algorithm is based on minutiae method. It includes only local features of the fingerprint image. This algorithm recognize fingerprint with the help of valid bifurcation points. The valid bifurcation points are extracted using cross-numbering method and spurious minutiae are removed by applying false minutiae removal technique in [2].

• A.    Image Enhancement

For enhancing a fingerprint image intensity adjustment is done on the basis of threshold value. First obtain the threshold of an image and then based on the threshold decide whether to adjust the intensity or not. If the intensity is to be adjusted, by how much it should be adjusted.

• B.    Binarization

Here Binarization is done with NOT operation which changes the value and color of ridges and furrows. Here ridges represent by white or 1’s and furrows represent by black or 0’s.

В = im2bw(I, Level)             (1)

B=~B;                  (2)

Here I is the grey-scale image and B is binary image.

• C.    Extracting ROI and Ridge Thinning

OPEN and CLOSE operation is done to extract region of interest from binary images. Open operation remove noise in background and close operation shrinks images to remove cavities. Ridge thinning makes the ridges just one pixel wide without changing its basic structure. It helps in removing the redundant pixels.

• D.    Minutiae Extraction

3x3 pixel window is used to extract minutiae point. A 3x3 window contain 0s and 1s values called pixels. If the centre pixel having value 1 corresponds to its three neighbors having value 1 than it is called bifurcation point otherwise it is a ridge ending point. But it is a simple method which also contains false bifurcation points. This method is not accurate one [2].

0	1	0	0
0	1(p1)	0	0
0	1(p2)	1(p3)	1
1	0	0	0

Fig.4. 4x4 Pixel Window of Fingerprint Image using CN Method

If 4x4 pixel window is taken as above then extra neighbors detected with value one which create false minutiae points. After removing of these false minutiae points valid bifurcation got deleted. So to avoid it delete all the neighboring bifurcation points which are just 1 pixel close to each other i.e. if there are n 1-pixel close bifurcation points then delete n-1 points. This is achieved by examining four neighboring pixels one above, one below and one on right and one on left side of a bifurcation point, if any of these points satisfy the bifurcation condition (3 neighboring 1’s) then remove that point and repeat for all bifurcation points. After all the bifurcation points are examined we can apply the false point removal technique [2].

• E.    False Minutiae Removal

False minutiae are the point which occurs because of breaks, noise and gaps etc. Sometimes Enhancement process enables to remove all false minutiae’s, so the false minutiae points are removed in post-processing of image. They are removed by these steps 1) First calculate the average distance D between two neighbor’s ridges. 2) Than calculate the distance between two minutiae points. They can be both bifurcations, can be one bifurcation and one termination and can be both termination points. The distance calculated named as d. 3) If d is less than D than and the two minutiae in same ridge than remove both of them 4) After removing false minutiae points marks valid minutiae points and on the basis of these the image is recognized [2].

• IV.    Problem Definaltion

The Existing algorithm was based on minutiae approach and used only local features of fingerprint image which cause inaccurate results because it include some part of the fingerprint image which missed some minutiae point necessary to match fingerprint images. The proposed algorithm based on pattern approaches which include whole structure of fingerprint image. The algorithm based on global approach. It includes both global and local features of fingerprint image.

Oil and dust cause noise in the fingerprint image during capturing the fingerprint with sensors. Bad quality of sensors also causes distortion in fingerprint image. Image enhancement is used to remove all the noise and bad effects.

Spurious minutiae’s are breaks and gaps in the fingerprint image. They occurred during Binarization and thinning process most of the time. They can be removed by applying false minutiae removal methods.

Finding correlating minutiae points creates problem and make algorithm expensive. Minutiae matching are not affected if two fingerprints are matched, which are twisted to each other, because it has to find correlating minutiae with the same direction anyway [18].

• V.    Proposed Work

• A.    Image Enhancement

Before minutiae extraction image enhancement is required in some low quality fingerprint images. Image enhancement is done using intensity adjustment method based on threshold. This method used to adjust the intensity levels of a fingerprint image. The intensity level ranges from (0, 255) levels. After selecting a specific area, create the intensity level of that specific area and calculate the threshold value of intensity levels. The threshold value decides how much intensity should be adjusted or not. The MATLAB function used is imadjust() for this method.

• B.    Binarization and Segmentation

Binarization converts a grey level image into a binary image to improve the contrast between the ridges and valleys in a fingerprint image which leads in the extraction of minutiae. The Binarization process determine the grey-level value of each pixel in the enhanced image, and, if the value is greater than the global threshold, then the pixel value is set to a binary value one, otherwise it is set to zero. The Matlab function for Binarization is im2bw().

The main motive of segmentation is to define which part of fingerprint image belongs to background and foreground area, which part is the noisy and distorted. Background contains furrows or irrelevant part of fingerprint image and foreground contains ridges and relevant area. Here texture segmentation is done using texture filters. The Matlab function of texture segmentation is

Е = entropy f ilt(I);(3)

Elm = mat2gray(.E);(4)

bw1 = im2bw(Eim, 0.8);

Here in eq. 3 I is the image and entropyfilt() creates texture image. In eq. 4 mat2gray rescale the texture image E. the fifth equation threshold the rescaled image Eim to segment the texture and 0.8 values is selected for threshold.

• C.    Principal component analysis

Pca is used for reducing dimensions of fingerprint image. It is a pattern recognition technique of fingerprint image which covert a higher dimensional space to lower dimensional space. Pca also recognize the false minutiae region and true minutiae region of fingerprint image. PCA helps in determining the rotation and orientation of objects. The Matlab function is used to perform PCA is coeff =pca(X). Following are the main steps of PCA.

Step 1: First convert an image into vector form. An image in vector form has MXN format where M is for column and N for rows.

Step 2: Normalization is done by removing the common features of all images and each image left with unique features.

Step 3: Calculate the average vector of all unique features and name it as 0. Subtract average feature vector from all normal feature vectors.

0_t = [M x N] — 0 (6)

Step 4: then eigenvectors are calculated by co-variance inverse method instead of simple co-variance method because this method reduce the eigenvectors and convert higher dimensional space to low dimensional space.

C = A¹ A where A = [0 1 0 2 .. 0 „ ], A is sze of n² xm (7)

C = m x n². n² x m (8)

Eigenvectors = C = m x m (9)

Step 5: then select best k eigenvectors from lower dimensional space. These K components called principal components. These principal components further used in extracting features of fingerprint image by using Gabor filter.

• D.    Gabor Filter

For successful matching of two fingerprint images at least 70-100 minutiae points are required. This algorithm works on bank of Gabor filters. It is a product of Gaussian envelops and wavelet transforms which also called sinusoid. It enhances the ridges and valleys patterns for identify and extracting feature vector so that Euclidean distance can be calculated between two feature vectors for template match. The algorithm work as follow:

• 1.    Central point detection: First Extracting the centre point of fingerprint image for identifies. It is also called region of interest i.e. ROI. Through ROI all the feature vectors extracted from fingerprint image. The centre point found at same position in every fingerprint image. It is the most upper part of the innermost region. Ridge curvature is also necessary to determine for computing orientation.

• 2.    Regions around centarl point: Next the circular region is drawn around core point. The circular. Region is of five bands and these five bands are divided into 16 regions and each band consist of 20 pixels means total 100 pixels in ROI. There is total 80 regions because 16x5=80. Then each region is normalized to their constant mean and variance.

• 3.    Normalization: Normalize the image. Each sector

• 4.    Bank of Gabor filters: A Gabor filter is a linear filter used for edge detection [6]. Ridges and valleys of ROI transformed into sinusoidal waves. Gabor filters optimally capture both local orientation and Frequency information from a fingerprint image by tuning a Gabor filter to specific frequency and direction, the local frequency and orientation information can be obtained [7].

• 5.    Feature map Generation: Generate the Fingerprint feature maps. The Fingerprint feature map vector is generated by calculating the average absolute deviation (AAD) for each of the 80 sectors in each of the eight filtered images. The AAD for a sector is calculated as follows.

within the image is normalized so that it has a specified initial mean and variance value. Normalization is performed to help remove the effects of sensor noise and gray level intensity variations due to finger pressure differences [5]. The ROI is divided because reduces the extra noise from the region and each region is normalize because to eliminate the common minutiae.

G(x,y:f,0) = exp{-1[^ + ^]}cos(27rfx') (10)x' = x sin0 + y cos 0              (11)

y ' = x cos0—y sin0             (12)

Here f is ridge frequency and 0 is orientation which represent the regions and their directions. 6./ And Sy are standard deviation of Gaussian envelop along the x’ and y’ axes. Filter bank applies eight filters with different orientation, 0 only and produces eight different filtered images. Now the components of feature vectors are extracted by calculating average absolute deviation of each sector in each of the eight filtered images. Eight different orientation of Gabor filter are applied to extract feature vectors. The feature vectors generated using Gabor filters form feature maps. And this feature map is matched with the fingerprint image stored in the database.

AAD_l=^X^₁₁ . \f_l(x.y)-u_l\)         (13)

Where п is the number of pixels in sector I, f i (x.y) is the intensity of the pixel at location (x, y), and г is the mean intensity of sector i. The Feature map vector representing a fingerprint is simply the concatenation of the 640 AAD values from the eight filtered images [5].

• E.    Matching Using Euclidean Distance

The mean threshold value of all feature vectors is calculated and the distance between the two feature maps are calculated. The translation invariance in the Feature map was established by the core. Approximate rotation invariance was achieved by cyclically rotating the features in the Feature map itself. In train database 5 templates were stored. Test fingerprint template was matched with the entire 5 templates and score were noted. The minimum score describe the best match of two fingerprint images. If the Euclidean distance between two feature maps is less than the threshold value than it is match of stored template and acquired template otherwise they considered the two different images from different fingers.

• VI.    Result And Discussion

The pattern based algorithm is slightly better than the minutiae based algorithm as it covers the whole area of fingerprint image. The above algorithm used Pca which automatically remove the false minutiae points no need to apply false minutiae removing technique. After applying the proposed solution the number of valid bifurcation points has increased by approximately 5-10%. The proposed solution also finds out the missing minutiae points which were missed earlier during previous algorithm. Table 1 shows the number of bifurcation and minutiae points obtained on different images before and after applying our solution.

With the solution proposed above all the duplicate bifurcation points are eliminated and the maximum original point is retained which was not possible earlier. The above implementation was an effort to improve the extraction of minutiae points for Fingerprint Recognition and matching thus improve the efficiency and robustness of fingerprint matching algorithms.

Table.1. Bifurcation and Minutiae Points Compared with Previous Work

Images	Previous algorithm		Proposed algorithm
	Minutiae Points	Bifurcation Points	Minutiae Points	Bifurcation Points
1.jpg	73	34	75	36
2.Jpg	78	40	71	41
3.Jpg	63	24	66	27
4.Jpg	80	50	82	51
5.Jpg	77	33	76	32

Results indicate that the proposed strategy filters the false minutiae points reliably. Also a major challenge in Fingerprint matching lies in the pre processing of the bad quality of fingerprint images which also add to the low verification rate.

Running the database of 5 fingerprint images through the first, baseline, and system resulted in matching statistics that were similar to those obtained in the literature. Our results were slightly better, but this was attributed to the fact that our total minutiae points were chosen around 100 to 150 rather than below 100. Set of 5 images in both train and test database. Total minutiae and bifurcation points are calculated in table 1above and the graph is plotted for the better representation of comparison of previous and proposed work of all images in figure 5 and 6.

Fig.5. Minutiae Value Comparison

Fig.6. Bifurcation Value Comparison

• VII.    Conclusion

This algorithm for fingerprint recognition and matching improve overall feature extraction process mainly the extraction of bifurcation and total minutiae points. This algorithm improves the matching speed and accuracy. This algorithm based on pattern matching which is relatively fast and less expensive than minutiae based algorithm.

The proposed algorithm is not limited to the local features of fingerprint images rather they use global features like ridges patterns, location and directions of ridges, their rotations etc. PCA describe the format of principal components which help in choosing the best principal features. The main advantage of PCA is that it used lower dimensionality of fingerprint image which reduced complexity. Gabor filter helps in find out orientation and frequency of ridges. Euclidean is best to use for matching two templates, easy to compute, in less time. The future work can be done on the recognizing rate of PCA for fingerprint images.

In Gabor filter future work can be done on the core position of fingerprint image as recognition can get faulty if core point is not adjusted properly.

Acknowledgement

All Thanks to Mrs. Daljit Kaur who supported me in this research work. She is an assistant Professor in Information technology department in CEC, Landran.