Introduction Fingerprint verification algorithms could potentially to have wide spread uses in civilian and governmental spheres. [1,2,3,4,5]. The purpose of a verification program is to confirm that a person is who s/he says s/he is, by matching her/his fingerprint with the one in a database that corresponds to the username entered. Thus, the fingerprint is used instead of a password or a pin number [1, 5, 6]. This use however, cannot be actualized without software that can be trusted to accurately match fingerprints and only allow access to the correct people [5]. Fingerprint recognition and other forms of biometric identification and verification have many advantages over traditional identity verification methods. Currently, there are many different methods are used to verify people?s identity and allow certain people access to specific places, computer systems, and information. Some of these methods include passwords, cards, keys etc. The major disadvantage of using these methods is that the security that cards, passwords and keys provide can be compromised as they can be given to someone else or stolen allowing an unauthorized person access to a system or area. They can also be lost, keeping an authorized person from gaining access. Because fingerprints are a part of ones physical being, they cannot be lost like identification card, passwords or keys. They also cannot be forgotten or handed out [1]. Theft is also difficult. Despite the many advantages of using a biometric approach to verification, it use is not common. These systems are difficult to prefect [6] and the algorithms used to create them are often closely guarded [7,8]. In this project I attempt to implement some of the algorithms needed in a fingerprint verification system in order to illuminate some of the methods and difficulties involved in using fingerprints to automatically verify one's identity. Background Fingerprints are not the only features that can be used to build biometric verification systems. There has also been work done to build systems that verify ones identity based on their iris, palmprints, and faces [1, 9]. Fingerprints, however, are one of the better features on which to build a biometric system. Among the various biometrics that can be used, fingerprints make a good choice because everyone has unique fingerprints [1, 2, 5]. One's fingerprints also do not vary with age making it a biometric whose features do not have to be constantly updated by the verification system [1, 2]. There is a long history of using fingerprints to identify people and verify identity [1, 2, 6]. Thus, the methods used to compare fingerprints are widely known and accepted [1, 2]. The uniqueness of each fingerprint is found in the pattern of ridges and valleys formed in the skin of the finger. There are both global patterns and minutiae [1]. The global patterns are the general orientation of the ridges on the finger. Several types of global patterns have been officially named including the arch, tented arch, whorl, left loop, and right loop [1, 7 ]. The global patterns cannot be used to determine if two fingerprints match, as many people have the same global patterns. These global patterns can be identified by merely looking at the finger and are mainly used to classify the fingerprints so that the matching algorithm need only try to look for a match if the two fingerprints are of the same type [2, 4]. The smaller minutiae are particulars of a person's ridges and valleys. Features like bifurcation ridge ends, islands, lakes, and dots are formed by the placement of the ridges and valley along the finger (See Figure 1) [4,10]. There are about 60 to 80 [5] minutiae can be found in a good print. The minutiae can be used to match fingerprints as everyone has a unique arrangement of these features [10]. Usually only bifurcation and ends are used in automated fingerprint matching systems [1,3, 4, 7,11]. Figure 1, Different types of minutia. From left to right, images of a bifurcation, ridge end, island, lake and dot. [10] [Image of differnt features] In a fingerprint verification system, often only the unique attributes of one's fingerprint are stored in a database, not the entire image [4, 5]. When setting up the system, one collects the prints of those who should have access. This initial process is called registration or enrollment [1, 5]. Later, when one wants to gain access using the system the program try to match the features of the new print with the one stored in the database. In many cases, it is the minutiae that are used to determine if two prints are from the same finger. Fingerprint matching using the minutiae is really a simple problem of determining whether the minutiae on two prints match. However, there are several issues that add to the problem's complexity. First of all, there is the unknown rotation, scale and translation of the prints that may cause the minutiae not to line up [1]. Because people are not likely to place their finger onto the scanner in exactly the same position every time, the prints and thus the minutiae will never line up exactly [1,6]. There is also the problem of plastic distortion that arises because of the pressure that is put on the finger when it is pressed against a surface. The distortion is not equal every time a fingerprint is taken, therefore this too can cause differences between the two prints from the same finger [1, 4]. Because of these problems, preprocessing must be done on the prints in order to eliminate some of the differences between the two fingerprints [7]. The quality of the prints can also affect the matching algorithm's performance. When using a scanner, poor quality prints can be produced if a person?s hands are wet, dirty or too dry. These conditions can cause a scanner to pick up false minutiae (ones that are not actually there) and not pick up some true minutiae [12]. Either case would adversely affect the matching algorithm. Scars or cuts across a finger can lead to a host of ridge endings that were not in both the print that was stored and the one being matched against [1]. Even under good conditions, different scans of the same fingerprint will not have the same minutiae on them [3]. When using ink and paper to initially capture the prints, the problems mentioned above still apply. There are also the additional problems of over inking and smudges in the ink. Poor quality prints are also a possible when one is working with latent prints from a crime scene or from prints used at police department, where the people submitting the prints are less then willing [4]. Because getting identically matching images of the same fingerprint is impossible [4], a matching algorithm cannot just match each minutia and declare that there is a match only when all of them can be lined up. Instead matching algorithms decide how similar two prints are. The programmer has to decide what is similar enough to declare two prints a match and what is not. To do this one has to decide how strict the algorithm is going to be. This strictness is embodied in the balance between the false rejection rate and false acceptance rate. The false acceptance rate is the rate in which the program declares two prints as a match when they are not. Meanwhile, false rejection rate is the number of time the system will reject a print that actually matches [1, 3]. Usually, when the false acceptance rate decreases the false rejection does as well and visa versa. There is no agreed upon standard that defines matching [6]. In the Netherlands 12 minutiae must match for fingerprints to legally be declared as matching. Seven are needed in South Africa and the United States leaves it up to experts in individual cases [13]. The fingerprint matching program's strictness is determined by the program's application. In government security systems the program is likely to be stricter than those used for access to one's home desktop. The problems noted above mainly apply to minutiae matching algorithms. While several fingerprint matching programs rely on the minutiae, that is only one of the methods that has been researched. Filterbank based matching, an experimental method published in IEEE in May uses a radically different approach. The algorithm uses Gabor filters, harmonic functions modulated by Gaussian distribution, that do an excellent job in image or information compaction. The results obtained from the filters are put into a "FingerCode" that was used to match the prints. If the Euclidean distance between codes is acceptable it is considered to be a match [5]. This method was tried to determine if fingerprint matching could be done more efficiently without the computation needed to first find the minutiae. The method is also supposed to cut down on the time needed to make the prints scale, rotation and translation invariant, as one would just need to manipulate the code, not individual points. In testing it was just a little worse than minutiae based methods of matching [5]. The methods based on minutiae matching are far from uniform. Some extract the minutiae directly from a grayscale image [11]. Others however, rely on vast amounts of preprocessing like the binarization and thinning of the image before the minutiae can be located [1,3,5]. Once the minutiae are found there are several means of matching the prints. Most include looking at the x and y coordinates of the minutiae and the relative distance between points on the print [3]. Some also look at the number of ridges between minutiae points [4] and the orientation of the ridges [3,4] to match the minutiae in different prints. Procedures and Materials: The fingerprint verification algorithms I have used involve matching the minutiae in two prints. 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,7]. I have covered most of these steps in the algorithms attempted for this project. In order to complete this project, I have borrowed some code and equipment from previous fingerprint recognition projects done here at Earlham. Last year, the Earlham Computer Science Department acquired a FingerTIP scanner produced by Siemens. This scanner produces 8 bit grayscale, jpeg images. These images are 224x288 pixels, 513dpi with 30 or 70 grays depending on the resolution chosen [12]. The FingerTIP scanner obtains the fingerprint image by using capacitors. The plate on which one places his/her finger is pre-charged with a reference voltage. There are two dynamics one with lower base voltage that gives lower contrast and one with higher voltage that produces image with higher contrast between the ridges and valleys. When a finger is placed on the scanner the skin acts as a counter electrode changing the amount of electricity that flows there. The differences between the skin touching the sensor and air where the valleys is used to produce an image. This image is then enhanced [12]. I have attempted to use a driver written by Cameron Murrel for this device to get the scanner to function. This would be a helpful source of images for the project. I have also studied the fingerprint matching code produced by Alex Reeder [8] in order to find inspiration for my own project. 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 [9] 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 scanner and the sample images from the NIST databases [14]. One of the first modules used in a fingerprint verification system is the binarization function [1, 3, 7]. These functions transform grayscale images of the type that the FingerTIP Scanner produces, to binary images. 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 [15]. 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 [12]. The binarization step is only useful with jpeg images. The bitmaps produced by the generator are already binary. After the binary version of the image has been acquired the ridges are thinned. Thinning involves reducing each ridge in the image so that each one is one pixel wide [1,3,7]. The thinning algorithm I will use an algorithm described on the Image Processing Learning Resources website [15]. The algorithm works through the pixels of the 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 neighbors matches one of the structuring elements shown in Figure 2, the point is removed. The center pixel in the structuring elements shown is the pixel currently being examined. The structuring elements are rotated 90 degrees for each successive pass. The passes with the structuring elements continue until they no longer produce a change. Figure 2. - The two structuring elements [15]. 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 is done. Pruning is accomplished much like thinning, except with a different set of 'structuring elements'. These elements are shown in Figure 3. They are only used for a few passes, as they would erode away the entire image if used to many times [15]. Figure 3. Two structural elements used for pruning [15]. 0 0 0 0 1 0 0 0 0 0 0 1 0 0 Binarization and thinning are not used by all fingerprint verification systems [11, 5]. However, the arguments against using thinning and binarization mainly apply to systems where there are large numbers of poor quality prints. Both processes involve the loss of data, which could be highly detrimental if one is working with prints of poor quality where there is not a lot of information to make comparisons with in the first place [11,5]. Yet, this system was developed for use with a fingerprint scanner by people who want to have access to a given service or place in mind. Thus, I am less concerned about the loss of information caused by binarization as the people using this system will probably be somewhat careful as to produce high quality prints. Plus, using the grayscale directly and the full ridges add a level of complexity to the project that would be prohibitive given the time constraints. 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 bifurcation. It stores the x and y coordinates 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 a pixel has three black neighbors that point is a bifurcation and its position is saved [3]. Because the matching program depends on a thinned image, one cannot over emphasis the importance of the thinning and binarization algorithms to this system. If they are faulty it could destroy some minutiae and introduce a host of false minutiae. Thus, special care has been taken in the production and testing of the algorithms for this project. Fortunately, using the fingerprint generators, one knows exactly how many minutiae there 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. 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 of the points from each point and dividing by the standard deviation [7]. 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 the center of the global pattern 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 is aligned [7]. When the prints are scale, translation and rotationally invariant it is much easier to tell if the prints match. As noted above, 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 minutiae matching 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 [7]. If the sum is small then it is likely that the prints match. If the sum is large the prints probably do not match. Results: I will be looking at several factors once the program has been built. First I will have to do some testing to figure out what an optimal sum is for the fingerprint matching segment of the code. To do this I would like to analyze compare the sums created by matching prints and by prints that do not match. I will also be considering the false acceptance rates and false rejection rates at various sums to determine which one is optimal. These rates would allow comparisons with other more sophisticated algorithms that have been developed. I would also like to analyze how well the different components work together. I would also detail what was actually accomplished In this section. Conclusions: Are there unforeseen consequences of using this particular set of algorithms? If I can think of anything, I might also add a section detailing what could be improved in the system and things that I would change. By building and analyzing of some of the components of a fingerprint verification system, I feel that I 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 have enjoyed seeing 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. Appendix A Code created for the project 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] N. Ratha, K. Karu, S. Chen, and A. Jain, A Real-Time Matching System For Large fingerprint Databases, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 18, No. 8, August 1996. [5] A. Jain, S. Prbhakar, L. Hong and s. Pankanti, Filterbank-Based Fingerprint Matching, IEEE Transactions On Image Processing, Vol. 9, No. 5, May 2000. [6] R. Hopkins, An Introduction to Biometrics and Large Scale Civilian Identification, International Review of Law, Computers and Technology, Vol.13, Issue 3, December 1999. [7] Eammon Keogh (personal communications October 19 - November 1, 2000) [ 8] A. Reeder, Fingerprint verification and Recognition, Retrieved September 2000, http://www.cs.earlham.edu/~odo/biometrics/, February 3, 2000. [9] Biolab, Department of Computer Science University of Bologna, Retrieved October 2000, http://www.csr.unibo.it/research/biolab/research.html [10] J.M. Villiot, Fingerprint Identification, Retrieved September 2000, http:/ /c3iwww.epfl.ch/projects_activities/jmv/fingerprint_identification.html. [11] D. Maio and D. Maltoni, Direct Grey-Scale Minutiae Detection in Fingerprints, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, No. 1. January 1997. [12] Microsystems for Biometrics FingerTIP CMOS Chip and System Databook 3.1, Infineon Technologies AG, CC Applications Group, Munchen, 1999. [13] M. Hanson, Fingerprint-Based forensics Identify Argentina?s Desaperecidos, Retrieved October 2000, http://www.computer.org/cga/articles/fingerprints.htm, 2000. [14] NIST, Imaging Databases, retrieved October 2000, http://www.nist.gov/srd/ special.htm, August 3, 2000. [15] 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.