1 Introduction

The use of one’s fingerprints as a means of identification has existed long before its common usage today in the field of criminal investigation.  Prior to the nineteenth century, fingerprints were primarily used only as a signature for indicating authorship or ownership.  Other applications were not acknowledged until about 1860 when William Hershel was regularly imprinting the handprints of those engaged in his contracts.  It was not until 1881 when Henry Faulds recognized that fingerprints found at crime scenes may be used to identify the perpetrator.  Further exploration into fingerprints followed when Sir Francis Galton began his research in the field and authored the first textbook on fingerprinting in 1892.  As a result of the work of these individuals, fingerprinting was soon accepted by Scotland Yard and finally by the United States in 1910¹.

Today, fingerprints are perhaps the primary means of personal identification although there are many other unique characteristics of an individual that can be used.  They include voiceprints, dental impressions, DNA, retinal patterns, and even the shape of the ear lobes¹.  Although these other characteristics are as much unique to the individual as are fingerprints, they lack many advantages which fingerprints have especially for the criminal investigator and forensic scientist.  Common to the other distinctive attributes, fingerprints are universal and unique.  In other words, everyone has them and no two have ever been found to be identical.  Fingerprints are also unchangeable.  They are formed before birth and remain until decomposition of the skin occurs some time after death.  Although some deformities may result from aging, manual labor, or scarring, the overall pattern always remains distinguishable.  What make fingerprints preferable are that they can be easily attained, quickly classified, and are very likely to be found at crime scenes.  Not only can they identify criminals but also casualties of disasters such as plane crashes.  Another common application is in maintaining access control.

Since 1924, the FBI has accumulated about 30 million sets of fingerprints² making the matching of a single fingerprint with such a collection very difficult.  With the advent of advanced computer technology in the past few decades, automated fingerprint identification systems (AFIS) can effectively perform what would otherwise be a laborious and time consuming task.  This study presents a method to fingerprint recognition by way of a spatial re-sampling of the pattern through concentric circles.  With this approach, the concentric circular samples have rotation invariant features while a translation is dependent only on the location of the circles' center.  The resulting circles are then correlated with those from a known set to obtain a collection of the most probable matches.

2 Background

2.1 Fingerprint Uniqueness

What actually makes a fingerprint unique depends on one main factor.  Fingerprints basically consist of ridges (raised skin) and furrows (lowered skin) that twist to form a distinct pattern.  When an inked imprint of a finger is made, the impression created is of the ridges while the furrows are the uninked areas between the ridges.  Although the manner in which the ridges flow is distinctive, other characteristics of the fingerprint called ‘minutiae’ are what is most unique to the individual (See figure 1 for several minutiae representations).  These features are particular patterns consisting of terminations or bifurcations of the ridges.  It is these features that AFIS extract and compare for determining a match³. 

Moreover, all fingerprints can be classified into three categories based on their major central pattern⁴.  These patterns are the arch, loop, and whorl, which are shown in figure 2.  The importance of these three patterns will be described in more detail in the methods section. 

Figure 2. Three major fingerprint classifiers 

Arch

Loop

Whorl

Several obstacles exist that make the matching of fingerprints a difficult task.  The major obstacles are rotation, displacement, missing areas, and image defects.  Rotation and displacement effects as well as image defects are problematic as variations occur each time fingerprints are taken and digitized.  Aligning the finger for impression in the same registration and orientation every time would be impossible while improper inking along with the noise of the scanning system commonly attribute to image defects.  THese factors are even more difficult to control considering that the fingerprints under question are typically latent prints found at a crime scene.  These are prints left unintentionally on some surface that is not necessarily paper and impressioned in something that is not likely to be ink.  It is expected that these prints are poor in quality and often have many missing or indisernible areas.  The fingerprint identification system must account for each of these factors.  Other factors exist as well but will not be investigated in this research.  For instance, the scaling of the fingerprint is often considered as someone may be identified even though their fingerprints were recorded at a very young age.

2.3 AFIS Recognition Process

Digitized fingerprint images are obtained either through a dedicated fingerprint scanner or the standard scanning of inked fingerprint impressions.  The prints are scanned at a resolution of 500 dpi with 8 bits per pixel with digital images having dimensions of 512 x 512 pixels (approximately 1" x 1") and 256 gray levels.  This is the criterion as recommended by the FBI⁵ and is employed in this research.  Once the images have been acquired, they are put through an image enhancement procedure to remove unwanted image defects and modify properties for certain purposes.  Specifically, all the minutiae in the fingerprint must be extracted and mapped.  The fingerprint is also categorized so that it only has to be matched with its class.

3 Theory

3.1 Sampling and Concentric Circular Sampling

An image, such as that of a fingerprint, may be considered as a two-dimensional continuous signal.  By this, it can have an infinite number of brightness intensities in an infinitesimal area.  In order for an image to be handled by a computer, it must first be digitized.

Digitizing removes the continuous condition of the image through sampling and quantization thereby making the signal discrete.  By sampling, the image is spatially approximated by repeatedly recording the averaged intensity within a region at regular intervals throughout the entire area.  With quantization, the intensities are approximated to finite levels.  These values, often termed gray levels, are then stored into a two-dimensional array where each cell in the array maps to a corresponding sample point.  These cells are commonly called picture elements or pixels.  Because the information between the sampling intervals in the image is lost, it is often desired that the interval size be controlled.  This is achieved by managing the number of sampling points to be used over a certain distance.  This is referred to as resolution.  Likewise, the number of gray levels may also be regulated.

For this study, the image had to be sampled in a different manner.  Instead of sampling in the general Cartesian space, the image is sampled through a pattern consisting of concentric circles.  It may be considered that this technique is sampling in a polar coordinate space.  Under this approach, the sampling resolutions are the distance between the concentric circles and the sampling interval within the circumference of the circles.
 

 Figure 3. Sampling procedures

Image

Sampled Signal

3.2 Correlation

The correlation operator, given by Equation 1, is especially useful for finding occurences of one signal in another.  When correlation is performed, the signal that results indicates a magnitude that is dependent on a varying shift between the two signals it operates on.  A high magnitude indicates that at the corresponding shift, the two source signals were more alike than at a shift for a low magnitude.  This can be assured since the magnitude is the total area of the product of the two signals.

                        (1)

Equation 1 however, is expressed for continuous signals when it must be applied to discrete signals for this study.  In addition, the correlation operation is performed in a circular fashion so that the shifted signal must wrap around the other.  This procedure is shown in Figure 4 with its equation given by Equation 2.
 

                        (2)

Figure 4. Circular correlation process

4 Methods

The following procedures were performed through routines provided in the appendix.

4.1 Test Images

Prior to testing the present matching process on fingerprint images, a series of test images were created to observe for any perculiarities in the algorithms.  These images consisted of fragments of lines varying in frequency, orientation, and thickness.

4.2 Synthetic Fingerprint Images
 
Another set of test images were of synthetic fingerprint images created through a demo software called Fingerprint Creator by Optel http://www.OPTEL.com.pl/index_en.htm.  With the various minutiae types randomly placed in each generated image, these images are useful in showing well how the present matching algorithm performs.  However, these artificial images are not realistic enough that it can be assumed the same results will occur for actual fingerprints.

All test images were 512 x 512 pixels in size with one bit per pixel.

4.3 Match Metrics

Three different metrics are defined for indicating the liklihood of a match between the concentric circular samplings of two fingerprint images being compared.  The three metrics are the area ratio, correlation fraction, and angular density.  The metrics are actually performed on each individual circle pair and and averaged over all the circles.  A value of one indicates a perfect match while a zero would indicate a very poor match.

4.3.1 Area Ratio

One way of considering two signals as being similar is through their areas.  This metric, given by Equation 3, only measures the ratio the smaller area to the higher area between the two circular signals being compared.  A perfect match occurs if the two signals have equal areas. 

                        (3)

Where A_pn is the area of the n^th circle signal in image p as given by equation 4. 

                        (4)

 Where f_pn(i) is the n^th circle signal of image p having I number of samples.

4.3.2 Correlation Fraction

As mentioned in section 3.2, the location of the highest magnitude in the correlation of two signals indicates where the two signals were most similar.  Since in this research the signals are binary, meaning they can only have values of zero or one, the product of the two signals being compared may be considered as a signal containing their common area.  With this in mind, it can be stated that the correlation between two binary signals can not have a magnitude greater than the smaller area of those signals.  Based on this knowledge is the correlation fraction metric, which is given by Equation 5. 

                         (5)

Where V is the notation for the maximum operation.

4.3.3 Angular Density

The angular density metric measures the match likelihood by determining how closely the locations of the highest match in each circle corresponds to that in the other circles of the correlation signal.  This is achieved by the following steps.
 
Location(s) corresponding to highest magnitude in correlation signal g(i) are recorded as i_max for each circle.  Then the set of the high correlation locations are converted to a set of angles through equation 6 where k is one angle of K total angles in the set. 

                        (6)

The set of angles are then converted to a set of unit vectors whose coordinates are given by equation 7. 

                        (7)

The vector components are averaged as given by equation 8. 

                            (8)

The mean square error (MSE) is then calculated for the x and y vectors through equation 9. 

                            (9)

The angular based MSE is then calculated from the vector based MSE through equation 10. 

                            (10)

Finally the angular density metric is defined by equation 11. 

                        (11)

4.4. Matching Process

A set of 48 synthetic fingerprint test images were generated with the major identifier located at the center of the images.  This allowed them to be circularly sampled without having a user select that location.  Each sample in this 48 fingerprint set is then matched against every fingerprint in the set to form a 48x48 matrix.  Three matrices are then created so that there is one matrix for each match metric.  The effects of the several matching obstacles are also investigated as the fingerprints across the columns of the matrix are altered. 

5 Results

The following surface plots are the 48x48 match matrices.  Along the x-axis (lower horizontal axis) are the fingerprint images dependent on some variation matched against the original unvaried images along the y-axis (side axis) while the value of the match metric in question is plotted along the z-axis (vertical axis).  Also given for each matrice are the self match maximim and other match minimum values.  The self match minimum is the smallest metric value determined along the diagonal where the varied image is match against itself.  The other match maximum is the largest metric value determined at all locations not including the diagonal where the varied image is match against other images in the set (does not include itself).  Ideally, the self match minimum should have a value of 1.0 while the other match maximum a value of 0.0.  This however would not occur so it can only be desired that the self match minimum value be close to 1.0 and be greater than the other match maximum.  If this holds true, a threshold may then be set between these values so that unknown images may be tested against this database.
 
5.1 Observation of Peculiarities Without Variations
 

Figure 6. No variations effect

Area Ratio Self match minimum: 1.00000  Other match maximum: 0.942616

Correlation Fraction Self match minimum: 1.00000  Other match maximum: 0.719253

Angular Density Self match minimum: 1.00000  Other match maximum: 0.604292

 

5.2 Observation of Missing Area Effect
 

Figure 7. Missing area effect

Area Ratio Self match minimum: 0.739651  Other match maximum: 0.773329

Correlation Fraction Self match minimum: 1.00000  Other match maximum: 0.726498

Angular Density Self match minimum: 0.620960  Other match maximum: 0.489653

 
5.3 Observation of Rotational Effect
 

Figure 8. Rotation effect (Rotated 45 degrees)

Area Ratio Self match minimum: 0.944036  Other match maximum: 0.938593

Correlation Fraction Self match minimum: 0.652650  Other match maximum: 0.724185

Angular Density Self match minimum: 0.463935  Other match maximum: 0.550657

 
5.4 Observation of Displacement Effect
 
Figure 9 shows the magnitude for each the three metrics at every displacement location as described in the methods setion.  The red areas indicate the highest liklihood of a match while the dark violet and black regions indicate the lowest liklihood.
 

 Figure 9. Displacement effect

6 Discussion

6.1 Peculiarities Without Variations

With this procedure, it was determined that all the metrics were able to successfully determine the correct match.  However, the angular density metric proved to show the best match given that its other match maximum of 0.604292 was lower than 0.942616 and 0.719253 found in the area ratio and correlation fraction metric respectively.

6.2 Missing Area Effect
 
With this experiment, we can expect that the area ratio metric fails since it is dependent only on the area of the signals.  With the Correlation fraction metric, there was actually improvement with the signal having been manipulated in this manner.  However, this occurrence can be explained by the behavior of the correlation operator.  If one of the two signals has more locations with no magnitude, there is a greater chance for that signal with the lesser magnitude to be matched against the other.  Since this metric does not consider the locations of highest correlation, it is not as reliable as the angular density metric though it shows better results.  This is not to say that the angular density metric fails, which it does not.  It still shows a self match minimum of 0.620960 that is fortunately a good amount greater than the other match maximum of 0.489653.
 
6.3 Rotational Effect

The area ratio and correlation metric had much difficulty in finding the correct match when the fingerprint images were rotated 45 degrees counterclockwise.  Both metrics still found the most probable match to be the correct fingerprint however a greater difference in the metric value between the correct print and the incorrect prints is desired.

6.4 Displacement Effect

As can be seen from Figure 9, a shift no more than a single pixel in any direction is permissible in the case of the area ratio and correlation fraction metric.  The angular density metric however, allows for a little greater flexibility as it would still indicate a match if the center is displaced beyond the specific location by up to three pixels in any direction.  This is particularly true in the case of a whorl type fingerprint but less so in the other two.

7 Conclusions

Given the results as discussed earlier, it is evident that the fingerprint images can be successfully matched through the proposed concentric circular sampling technique by way of the angular density metric.  This metric performs very well for recognizing fingerprints that have missing areas.  The results from the effects of rotation are acceptable while displacement effects are least problematic for this metric when compared to the other metrics.  Overall, this technique shows exceptional results for matching the synthetic binary fingerprint images and similar results are expected if tested on enhanced actual fingerprint images.  Of course the enhancement of the actual fingerprints must include binarization since that is a requirement of this technique.
In consideration of matching speed, the approach of this study cannot accurately determine a match without comparing the fingerprint under question to the entire known set.  This is necessary if the desired result of this matching process is a collection of the most probable fingerprints.  For small fingerprint databases, this would not be a major dilemma but in consideration of the FBI's massive set, this would be unacceptable given the amount of time required.  However, there are those that have a need for fingerprint identification given a small database.  Such an example would be businesses having to maintain access control.

7.1 Future Work

The current research is somewhat of a preliminary study into the possibility of performing fingerprint recognition through the proposed alternative approach that is circular sampling.  Some suggestions for further research into this approach are presented.
A more efficient approach would require a means of classification prior to matching.  This would greatly reduce the number of matches that need to be performed thus improving the overall matching speed.  Also beneficial to the matching speed would be optimized code since the number of computations could be reduced.  Since this technique is directed at binary images, further study may include an application towards images other than fingerprints such as text characters.