Proposal for the Study of Fingerprint Verification Afua Sanders November 2, 2000 Introduction: Fingerprint verification algorithms could potentially to have wide spread uses in civilian, government spheres. [1,2,3]. The purpose of a verification program is to confirm that a person is who s/he says s/he is, by matching their fingerprint with the one in the database that corresponds to the username entered. Thus, the fingerprint is used instead of a password or a pin number. This use however, cannot be actualized without software that can be trusted to accurately match fingerprints and only allow access to the correct people. In this project I will attempt to implement a few of the algorithms needed in a fingerprint verification system. I hope that I will learn about some of the complexities involved in creating a fingerprint verification system by building one. The fingerprint verification algorithms I plan to use involve matching the minutiae in two prints. The minutiae are the small characteristics of a fingerprint's ridges and valleys like ridge endings and bifurcations. There are several steps involved in creating a program based on minutiae matching. The steps include binarization, thinning, minutiae extraction and finally the actual matching [1,3]. One must also preprocess the prints so that they are scale, rotation and translation invariant [1,3,4]. I plan to cover most of these steps in the algorithms attempted for this project. Algorithms and Procedures: To begin such a project, one must have an ample supply of fingerprint images. I have acquired such a supply using two fingerprint generators, Sfinge created by the Department of Computer Science University of Bologna and Fingerprint Creator designed by Optel. These programs produce bitmaps of fingerprints with varying amounts of distortion, numbers of minutia, types of global features (like whorls, arches, loops etc.). Another potential source of fingerprint images is the FingerTIP fingerprint owned by the Earlham College Computer Science Department. This scanner produces an eight-bit, grayscale, jpeg image of one's fingerprint. At the moment, the fingerprint scanner is not functioning. The correct version of the Linux kernel was needed and now the driver code needs to be installed. Having the scanner working would provide some images of real fingerprints that would be helpful in testing the code. Thus, some time will be spent attempting to make FingerTIP scanner functional. Another source of real fingerprint images could be the sample images from the NIST databases [5]. The fingerprint matching algorithms chosen for this project require the fingerprint images to endure much preprocessing in order to ensure accurate matchings. One of the first modules used in a fingerprint verification system is the binarization functions [1, 3, 4]. These functions transform a grayscale images of the type that scanner the FingerTIP Scanner Owned by Earlham produces, to binary images. While there are some systems that do without this step [8, 10], using the grayscale directly adds a level of complexity to the project that would be prohibitive given the time constraints. Binarization can be achieved using thresholding techniques. Each pixel is compared to a threshold. If the grayscale value is above the threshold the pixel is set to black and if it is below the threshold the pixel is made white [6]. This is possible because the ridges and valleys in good fingerprint images have distinctly different intensities and should separate out nicely. An intensity threshold is chosen so that it is a value between the normal value of the ridges and that of the valleys [7]. The binarization step is only useful with the real fingerprint images. The bitmaps produced by the generator are already binary thus the implementation of this stage will probably be put off until the other pieces have been tested. After the binary version of the image has acquired the ridges must be thinned. Thinning involves reducing each ridge in the image so that each one is one pixel wide [1,3,4]. This is a step not used by all fingerprint verification systems. Many have exclaimed that it reduces the amount of information used to make the comparisons [8]. Despite this argument, thinning will be used in this project because it eases the next step of minutiae extraction significantly. Adding smoothing steps to the thinning process reduces many of the problems [6]. The thinning algorithm I will use an algorithm described on the Image Processing Learning Resources website [6]. The algorithm works through the pixels of an image using a set of 'structuring elements' to decide which of the pixels to remove. The program looks at each dark pixel that has one or more light neighbors. If the pixel and its 8 nieghbors matches one of the structuring elements shown in figure 1, the point is removed unless its removal will disconnect a previously connected line. The structuring elements are rotated 90 degrees for each successive pass. The interations continue until passes with the structuring elements do not produce a change. Figure 1 - shows the two structuring elements. 0 0 0 1 1 1 1 0 0 1 1 0 1 The above method has been shown to produce connected skeletons of the original image. However, thin short spikes are produced using this method. These spikes are not true minutiae, but would be confused with actual minutiae by the minutiae extraction algorithm. To eliminate this problem a little pruning will be done. Pruning is accomplished much like thinning, except with a different set of 'structuring elements'. These elements are shown in figure 2. They are only used for a few interations, as it would erode away the entire image if used to many times [6]. Figure 2. Two structural elements for pruning 0 0 0 0 1 0 0 0 0 0 0 1 0 0 Once binarization and thinning have occurred, the minutiae extraction functions are almost trivial. Minutiae extraction is the process of finding all of the minutiae in a fingerprint image and marking their locations. I will use a minutiae extraction algorithm described by Anil Jain in Online fingerprint Verification [3]. In this algorithm one simply steps through each pixel of the thinned image. The only minutiae this function looks for are the ridge endings and the bifurcations. It stores the positions of these minutiae in an array. The program stops at every black pixel and analyzes the pixel's 8 neighbors. If the pixel only has one black neighbor then it is a ridge ending and the location is stored. If there are two black neighbors it is a regular point on a ridge and the algorithm moves on. When the pixel has three black neighbors that point is a bifurcation and its position is stored [3]. One cannot over emphasis the importance of the thinning algorithm to the minutiae extraction process. If the thinning algorithm is faulty it could destroy some minutiae and introduce a host of false minutiae. Thus, special care will be taken in the production and testing of the thinning algorithm for this project. Fortunately, using the fingerprint generators, one knows exactly how many minutiae are in a given print. This feature will make it easy find out if the thinning and the minutiae extraction algorithms are functioning correctly. Finally, once the minutiae have been extracted the matching process can begin. In a verification system, several prints are registered with in a system along with user information. When that user returns s/he enters her/his username and fingerprint. The program must see if the newly entered print matches the stored print associated with that username. The matching algorithm used for this project was one introduced by Eammon Keogh of the University of California, Irvine. Using this method, one must first preprocess the data to make it scale and translation invariable. This is accomplished by subtracting the mean from each point and dividing by the standard deviation [4]. Then one may make the points rotationally invariant as well. In order to do this one must be able to find two features common to both the new and the stored prints that can be used to align them. The core, a point on a fingerprint where a ridge curves back on itself in a loop or whorl, and the delta, a point where the ridges diverge to form the global pattern are usually the features used. They are used because there are only one or two of each of these types of minutiae in each print that contain these features [2]. Thus, one knows that if the prints do match, that one has the same point on each print. A line is found between the core and the delta of each print. Then the points on each print are rotated until the line between the core and delta are aligned [4]. Because the time available to complete this project is limited this portion might not be attempted. When the prints are scale, translation and rotationally invariant it is much easier to tell if the prints match. Because of difference in plastic distortion and the fact that some of the minutiae found in the new scan may not have been found in the original scan or visa versa, the minutiae will rarely overlap exactly [1]. The function for described here actually calculates the sum of the distance between the two prints. The function developed by Eammon Keogh is called Nearest Neighbor. It first matches each minutia in one print to the nearest minutiae in the other. The Euclidean distance between each point and it nearest neighbor is found and squared. These values are then summed. The square root of this sum is then returned from the function [4]. If the sum is small then it is likely that the prints match. If the sum is large the prints probably do not match. Schedule of implementation: I have actually begun working on the necessary modules out of the order in which they are actually used. I have pretty much finished the matching algorithm (It was coded between October 22nd and October 26th). I will test this code with the minutiae found on the generated fingerprints as soon as that information is available. I will try both matching and non-matching prints and figure out where the sum for a match should be set. I plan to do this testing from November 26th to December 4th. Thus far, I have been making up minutiae locations and feeding them to the program. Getting the minutiae points from actual and generated fingerprints will use thinning and minutiae extraction. I expect that I will spend substantial time on this step. I will work first on the thinning algorithm Starting on November 2nd. I would like to have this portion completed by November 11th. Naturally, the minutiae extraction algorithm will be coded after the thinning program has been completed (November 14th - November 22nd). Because of time constraints, much will be left to the end in the hopes that there is time for some of the extras that would really make a fingerprint verification system sophisticated. For instance, making the prints rotationally invariant will wait until the period between November 29th and December 2nd. While this is a necessary component, I will assume as Alex did [9] that people will be careful when submitting their fingerprints on a small mounted scanner like the one Earlham owns and for the most part the prints will be uniformly rotated. Also, I will mainly be working with the generated prints until I have the algorithms perfected. With these prints, I can control the rotation, making that a non-issue. I will work with the generated prints mainly because they simplify the process of finding fingerprint data to use. I can create as many prints as necessary and at any time. Meanwhile, the fingerTIP scanner is not functional. While I plan to work on the scanner throughout the rest of the semester, it is not the focus of my project and I cannot guarantee that I will get images from it at all. Using the generated images also allows me to put off the binarization process until I am sure that I have the other pieces of the fingerprint verification ready. While writing a binarization algorithm would be a grand learning experience, it is not the main point of the project. Thus I have only set aside a short period from November 24th to November 27th to work on the binarization process. To use the real fingerprint images from the scanner or images from the NIST database samples, I would also have to learn how to manipulate jpeg files which could be another time consuming adventure that I hope to avoid by using other's code. Once all of the pieces are assembled and tested individually, I will test and analyze how they work as a unit (November 26th-December 8th). I will be looking for the number of false acceptances and false rejections made by the system when different sums are used as the cut off for a match. I will determine the sum that minimizes the false acceptance rate and false rejection rate. These figures will help me understand how well the system works and can be used as a means of comparison with other methods. I would also like to know how long it takes to determine if there is a match. By building and analyzing of some of the components of a fingerprint verification system, I feel that I will have a much better grasp of the issues involved in producing accurate fingerprint verification system. These systems have been implemented in numerous ways and tend to be very large and complex. I would like to see how this scaled down approach works. I also think that it will give me a better sense of how pattern recognition and image manipulation is accomplished. References: [1] A. K. Jain and S. Pankanti, Fingerprint Classification and Matching, Retrieved October 2000, http://www.cse.msu.edu/cgi-user/web/tech/document?NUM= 99-5, January 1999. [2] E. Keogh, The Science of Fingerprints, eamonn@ics.uci.edu, October 2000 [3] A. Jain, L. Hong and R. Bolle, On-Line Fingerprint Verification, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, No. 4 April 1997. [4] Eammon Keogh (personal communications October 19 - November 1 2000) [5] NIST, Imaging Databases, retrieved October 2000, http://www.nist.gov/srd/ special.htm, August 3, 2000. [6] R. Fisher, S. Perkins, A. Walker and E. Wolfart, HIPR2: Image Processing Learning Resources, Retrieved November 1, 2000, http://www.dai.ed.ac.uk/HIPR2/ hipr_top.htm, 2000. [7] Microsystems for Biometrics FingerTIP CMOS Chip and System Databook 3.1, Infineon Technologies AG, CC Applications Group, Munchen, 1999. [8] D. Maio and D. Maltoni, Direct Grey-Scale Minutiae Ditection in Fingerprints, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, No. 1, January 1997. [9] A. Reeder, Fingerprint verification and Recognition, Retrieved September 2000, http://www.cs.earlham.edu/~odo/biometrics/, February 3, 2000. [10] A. Jain, S. Prbhakar, L. Hong and s. Pankanti, Filterbank-Based Fingerprint Matching, IEEE Transactions On Inage Processing, Vol. 9, No. 5, May 2000.