Study and Implementation of Minutiae Extraction from Automatic Fingerprint Recognition

Study and Implementation of Minutiae Extraction from Automatic Fingerprint Recognition

Arunabha Datta

Department of Electrical & Instrumentation, Sant Longowal Institute of Engineering & Technology Longowal, Sangrur,

Punjab pin-148106, India.

Manmohan Singh

Department of Electrical & Instrumentation, Sant Longowal Institute of Engineering & Technology Longowal, Sangrur,

Punjab pin-148106, India.

Abstract Fingerprint recognition is one of the most popular and successful methods used for person identification. Fingerprint Identification is becoming an essential component of effective person identification solutions because biometric identifiers cannot be shared or misplaced and they intrinsically represent the individuals bodily identity. Fingerprint recognition continues to be one of the most widely used biometric systems. This paper, explores the various steps present in a fingerprint recognition system. The study develops a working algorithm to extract fingerprint minutiae from an input fingerprint image. This stage incorporates a variety of image pre-processing steps necessary for accurate minutiae extraction and includes a methods of ridge thinning. Next, it implements a procedure for matching sets of minutiae data. This process goes through all possible alignments of the datasets and returns the matching score for the best possible alignment. Finally, it conducts a series of matching experiments thinning methods as considered. Results show that thinning by the central line method produces good False Non-match Rates and False Match Rates. Central line thinning methods appear to do an adequate job at locating the minutiae. An error that occurs in the thinning process leads to the minutiae extraction process detecting minutiae that do not correspond with the original ridge structure. Meanwhile, the central line thinning does an excellent job of maintaining the ridge integrity of the original image.

Keywords Biometrics, binarization, central line thinning, fingerprint, Minutiae

1. INTRODUCTION (HEADING 1)

   The use of biometrics continues to evolve in many areas of society. Fingerprint readers can be found on laptop computers, iris scanners are being installed at locations of heightened security, and voice recognition software is being incorporated into automobiles. Biometrics is becoming an essential component of effective person identification solutions because biometric identifiers cannot be shared or misplaced and they intrinsically represent the individuals bodily identity. Whatever the reason for the biometric system, it is evident that their use will continue to develop during the coming years.

   The history of Biometrics (Bio life and metrics- measure) dates back to 14th century when Chinese used to stamp childrens palms and feet on paper with ink to tell them apart [1]. So it can be said that fingerprint was the first biometric to be used and it remains till date one of the most powerful biometrics. In year of 1858 the English first began using fingerprints, on native contracts [2]. In 1880 Dr. Henry Faulds, a Scottish doctor in Tokyo, Japan published an article

   in the scientific journal: Nature; in which he discussed fingerprints as a means of personal identification and the use of printers ink as a method for obtaining such fingerprints. In the year of 1980 first computer data base of fingerprints was developed [1], which came to be known as the Automated Fingerprint Identification System, (AFIS). In the present day, there are nearly 70 million cards, or nearly 700 million individual fingerprints entered in AFIS.

2. FINGERPRINT DETAILS

   A fingerprint is the feature pattern of one finger (Fig.1). It is believed with strong evidences that each fingerprint is unique. Each person has his own fingerprints with the permanent uniqueness.

   Fig.1: A fingerprint image acquired by an Optical Sensor.

   A fingerprint is comprised of a pattern of lines, known as ridges. The spaces between individual ridges are referred to as valleys. As a ridge progresses, it can either come to an end, or it can split into two ridges. A fingerprint is composed of many ridges and Valleys (Fig.2). In a fingerprint, there are two types of characteristic, local and global patterns. Global patterns represent the ridges behaviour. Ridges flow could look like an arch, a loop, or a whorl. Loop is the most common in the society. Local patterns (minutia) were used for this work, and they are discontinuities of ridges. Usually, local patterns are used in fingerprint recognition, especially bifurcations and endings. Fig.2 shows some fingerprint local patterns.

3. FEATURE EXTRACTION TECHNIQUES

   It is first necessary to apply several pre-processing steps to the original fingerprint image to produce consistent results in the classic minutiae extraction procedure. Such steps generally include image binarization, noise removal, and thinning.

   Fig.2: Ridges and valleys in fingerprint image.

   Fingerprint Image

   Fingerprint Image

   Image Binarization

   Image Binarization

   Thinning Method (Central Line Thinning)

   Thinning Method (Central Line Thinning)

   Minutiae Extraction

   Minutiae Extraction

   Matching Score

   Matching Score

   Minutiae Matching

   Minutiae Matching

   Fig.3: Fingerprint Recognition Steps.

   Binarization: Image binarization is the process of turning a grayscale image to a black and white image. In a gray-scale image, a pixel can take on 256 different intensity values while each pixel is assigned to be either black or white in a black and white image. This conversion from gray-scale to black and white is performed by applying a threshold value to the image.

   1. (b)

      Fig.4: (a) Original image, (b) Result of Image Binarization

4. THINNING TECHNIQUES FOR FINGERPRINTS Central line thinning technique reducing the individual

   ridges to a width of one pixel at their central lines. The rule base algorithm was developed by Ahmed et al.[3] Patil et al.[4] have suggested the techniques of rotation invariant thinning algorithm to detect ridge bifurcations for fingerprint identification. They have done the job of modification of the thinning algorithm. The features distinguishing the algorithm signifies its ability to thin any of the symbol and fingerprint to its central line taking care that the shape of the symbol is preserved when the rotation invariant. In this technique the algorithm incorporates a process to thin the zigzag diagonal lines having a width of two pixels. This technique is more iterative and makes use of parallel processing to speed up the parallel processing. This system has 21 rules in its inference engine that are applied simultaneously to every pixel in each iteration. This algorithm is basically used for thinning fingerprints, fonts and symbols to a single pixel width. There have a 24 rule based mask available for the detection of ridge bifurcations which can be helpful for recognition or authentification of the fingerprints. This thinning algorithm preserves the topology of the symbols. The shape accomplished by representing the symbols by their central lines because the central lines of the image form the resultant thinned symbol. There are 21 thinning rules and 4 diagonal rules. These rules are applied in parallel to every pixel in each iteration. The total number of iterations is half the number of pixels in the thickest part of the pattern. This method has a major advantage of being rotation invariant. The results obtained is much more effective, fast and can thin any smbol irrespective of the direction of the rotation, flipping. The 24 rules set here for bifurcation point detection are effective.

   1. (b) (c)

      (d) (e) (f)

      Fig.5: Results for Central line Thinning Process

      (a) black &white image (b) After Iteration 1 (c) After Iteration 2 (d) After Iteration 3 (e) After Iteration 4 (f) After Applying

5. MINUTIAE EXTRACTION

   In minutiae extraction stage minutiae from thinned image derived the minutiae locations and angles. The terminations caused by the outer boundary are not considered as minutiae points. Crossing number is used to identify the minutiae points. Crossing number is defined as half of the sum of differences between intensity values of two adjacent pixels. This value defines the crossing number for the black pixel at the centre of the three-by-three pixel region. The centre pixel corresponds to a termination minutia when the crossing number is equal to one. Similarly, the centre pixel is the location of a bifurcation when the crossing number is greater than or equal to three, and it is an intermediate ridge point when the crossing number is equal to two. Figure 6 illustrates intra-ridge pixels, termination minutia, and bifurcation minutia as detected by the crossing number.

   Fig.7: Fingerprint Image and Minutiae detected by Central line

   Minutiae data from a single fingerprint is stored in a matrix format, where the number of rows represents the number of minutiae points. The number of columns in this matrix is fixed at a value of four. The first column indicates the row index of each minutia, and the second column indicates the column index of the minutiae in the fingerprint image. The third column provides the angle orientation of the minutiae, and the fourth column indicates the type of minutiae, where values of one or two are used to indicate a termination or bifurcation, respectively. Table 1provides a sample of this matrix of data extracted for each fingerprint.

   Table .1 Sample matrix of Minutiae Data.

   Row Index	Column Index	Orientation Angle	Type of Minutiae
   118	55	210.9638	1
   322	59	225	1
   303	61	248.1986	1
   121	214	321.3402	1
   215	35	233.1301	2
   103	44	206.5651	2

   VII. MATCHING SCORE

   The experiment conducted to determine numerical values of the False Non-match Rate (FNMR) and False Match Rate (FMR) for various thresholds. Equation 1 expresses the formula used for calculating the FNMR at different threshold values:

   	Crossing number=2 Normal ridge
   	Crossing number=1 Termination Or ending point
   	Crossing number=3 Bifurcation minutiae

   	Crossing number=2 Normal ridge
   	Crossing number=1 Termination Or ending point
   	Crossing number=3 Bifurcation minutiae

   =

   (1)

   Fig.6: Crossing number and type of minutiae.

   Figure 7 shows the original image and the extracted minutiae points. Square shape shows the position of termination and diamond shape shows the position of bifurcation as in figure.

6. MINUTIAE MATCHING

The minutiae information can be extracted and stored after the image thinning process is to be completed. This information consists of the following for each minutia:

• Location within the image

• Orientation angle

• Type (termination or bifurcation)

The experiment matched the seven images of the same fingerprint to the corresponding template for the same fingerprint. Therefore, each match that took place was considered to be an enrolees attempt to access the system. FNMR and FMR matching processes were performed for methods of thinning. The matching scores were compared against various threshold values to obtain the performance data for central line thinning method. The threshold was adjusted from 0.05 to 0.95 in increments of 0.05.

Results show that the central line thinning scheme leads to very good recognition rates for threshold values below 0.65, and that the FNMR begins to increase to unacceptable values when the threshold is greater than 0.65

Table.2 Central line thinning FNMR/FMR data

VIII. CONCLUSIONS

Results show that using the central line thinning method leads to good recognition rates and allows the recognition system to handle rotated images without performance degradation. The central line thinning methods main strength lies in its ability to thin ridges in the same manner regardless of rotational orientation, making it easier to effectively process all types of input fingerprint images. We plan to develop a fingerprint recognition system based on the method proposed above and obtain some test results.

REFERENCES

1. LLC Crime scene Forensics. History of fingerprints.

2. http://onin.com/fp/fphistory.html

3. Ahmed M., Ward R., A Rotation Invariant Rule-Based Thinning Algorithm for Character Recognition, IEEE transactions on Pattern Analysis and Machine Intelligence, vol. 24, no.12, pp. 1672-1678, 2002

4. Patil P. M., Shekar R. and Suralkar Faiyaz B. Sheikh., Rotation Invariant Thinning Algorithm to Detect Ridge Bifurcations for Fingerprint Identification, 17th IEEE International Conference on Tools with Artificial Intelligence (ICTAI05), Vol.8 pp. 641, 2005.

5. Maltoni D., Maio D., Jain A. and Prabhakar S., Handbook of Fingerprint Recognition, New York: Springer-Verlag, 2009.

6. Hartwing Fronthaler, Klaus kollreider, and Josef Bigun, Local Features for Enhancement andMinutiae Extraction in Fingerprints, IEEE Transactions on Image Processing, vol. 17, no, 3, pp. 354-363, (2008).

7. Jain, A.K., Ross, A., & Prabhakar, S. (2004). Anintroduction to biometric recognition. IEEETransactions on Circuits and Systems for VideoTechnology, 14, 4-20

8. Jain Anil K., Ross Arun and Prabhakar Salil. An Introduction to Biometric Recognition, IEEE transactions on circuits and systems for video technology, vol. 14, no. 1, 2004.

9. Luo, X., Tian, J., & Wu, Y. (2000). A minutia matching algorithm in fingerprint verification. 15th International Conference on Pattern Recognition,833-836.

10. Prabhakar, S, Jain, A.K, Jianguo Wang, Pankanti S, Bolle, Minutia Verification and Classification for Fingerprint Matching, International Conference on Pattern Recognition vol. 1, pp. 25-29, (2002).

11. Wei Honglei, Guo Mingen and Ou Zongying, Fingerprint Verification Based on Multistage Minutiae Matching, 18th International Conference on Pattern Recognition, ICPR 2006. vol. 2, pp. 1058 1061, Hong Kong 2006

12. Zhang David, Feng Liu, Qijun Zhao, Guangming Lu and Nan Luo, Selecting a Reference High Resolution for Fingerprint Recognition Using Minutiae and Pores, IEEE transactions on instrumentation and measurement vol. 60, no. 3, pp. 863 871, 2011.

13. Yang Ju Cheng, Shin Jin Wook, Byoung Jun, Yoon Sook, Fingerprint Matching using Global Minutiae and Invariant Moments, 2008 Congress on Image and Signal Processing, vol. 8, pp. 599 602, Sanya, China 2008