Correlation Based Indexing


We attempt to index the similarity between two fingerprints by finding the correlation of their grayscale component values. The overall scheme is illustrated in the flowchart below.

 

Because the grayscale color scheme gives an unjustified weighting to lighter pixels for a correlation calculation, we must normalize both input images before computing the correlation. This normalization will also ensure that the L2 inner product of the two images will have a value between 0 and 1, which is a convenient artifact for this type of matching. Several factors influence our computation of the correlation. First, we want to account for different translations, or shifts, of the fingerprint image. For example, if a print from one individual is in the upper left corner of the print area and a print from the same individual is located in the lower right corner, our system should identify the two prints as being highly correlated. Second, we need to consider computational complexity and the time it takes to perform this calculation. Because of these issues, we chose to implement a convolution based method of the convolution calculation.

Convolution is an inner product calculation with various shifts. Thus, it works nicely to solve our issue of translation of a fingerprint in the print area. However, we must "preflip" one and only one of the images to account for the flip inherent in the convolution algorithm. Now, because convolution computes the inner product of the two images for all possible shifts, we can simply extract the maximum value from the convolution result matrix and call this our correlation for the two images. In this manner, we implement a method for comparing the two grayscale images.

The other issue we are faced with is computational expense. In order to reduce the number of multiplies and adds we need to perform, we can optimize our convolution method using the Fast Fourier Transform (FFT). Performing multiplication in the Fourier domain is equivalent to a circular convolution in the sample domain. So, instead of computing the convolution directly, we compute the FFT of the 2 input signals, multiply the results, and then compute the Inverse Fast Fourier Transform to find the convolution result. Because this computation is equivalent to a circular convolution, we must first zero pad the images and then extract the center of the computation result. Also, we perform the calculations using square images which have dimensions that are powers of two, thus allowing us to use the Fast Fourier Transform in MATLAB. The use of the FFT allows us to compute the result in fewer instructions than by implementing the convolution directly.

The correlation-based method provides us with an index to the similarity of two input fingerprints. The results follow ...

 


[Home] [Abstract][Background][Classification] [Correlation] [Results] [Conclusions][Code][References]