Fingerprint Enhancement by Directional Filtering
Abstract: The important step in fingerprint matching is the reliable fingerprint recognition. Automatic Fingerprint Recognition System relies on the input fingerprint for feature extraction. Hence, the effectiveness of feature extraction relies heavily on the quality of input fingerprint images. In this paper adaptive filtering in frequency domain in order to enhance fingerprint image is proposed.
Several stages of processing take place when an Automated Fingerprint Identification System (AFIS) is used to match an unknown fingerprint [2].
1) The fingerprint is first enhanced to remove noisy and any irrelevant information.
2) The enhanced image is then encoded into a form suitable for comparison with the records held in the database. The encoded data consists of various key information of the fingerprint image like its minutiae.
3) Matching is then performed by comparing the encoded record against those held in the database.
4) Verification stage is performed wherein a fingerprint expert visually compares the unknown print with the candidates’ fingerprints.
Enhancement stage yields the information required for the later stages. Hence the performance of the entire AFIS system depends on the enhancement stage.
Need for Directional Filtering:
Fingerprint is a pattern of ridges and valleys
Two most prominent local ridge characteristics, called minutiae, are:
(a) Ridge ending
(b) Ridge bifurcation
These minutiae can be used for manual or automatic fingerprint identification. These characteristics of fingerprint images are shown in Figure 1 [1].
By applying a bank of Gabor filters on input fingerprint images, orientation field from a set of filtered images can be estimated. Automatic fingerprint matching depends on the comparison of these local ridge characteristics and their relationships leading to personal identification.
Properties of directional filters:
1) It must be frequency and orientation
selective.
2) It has to pass spectral component
corresponding to ridges, while attenuating
noise components.
3) DC and low frequency coefficients are to be
eliminated since they have no impact on the
ridge frequency and orientation.
4) Band pass has to be properly selected.
Filter is described in the frequency domain through combination of two components:
1) Radial component depends on local ridge spacing (LRS).
2) Angular component depends on local ridge orientation (LRO).
The ridge structures in poor quality fingerprint images are not always well defined and hence, they cannot be detected properly. This leads to the following problems:
3) a significant number of spurious minutiae may be created.
4) a large percent of genuine minutiae may be ignored
5) large errors in their localization (position and orientation) may be introduced.
Flowchart
Fig 1: A fingerprint image with marked singularities, minutiae and the frequency spectra corresponding to the local regions.[1]
Steps for fingerprint enhancement:
The flowchart of the fingerprint enhancement algorithm is shown in Figure 2 [3]
1) The image is first normalized to have desired mean and variance
2) It is then divided into non-overlapping blocks
3) Dominant ridge orientation is determined for each block
4) They are then smoothed and subsequently the block direction image is formed
5) Average ridge distance for the whole input image is determined
6) Directional filtering is used to enhance the image.(figure 2)
Normalization: The main purpose of normalization is (figure 3)
1) To have images with similar characteristics
2) To remove the effect of the
sensor noise.
Fig 2: A flowchart of the proposed fingerprint enhancement algorithm [3]
3) To reduce the variation in gray level values along ridges and valleys.
Fig 3: Normalized image [7]
LRO (Local Ridge Orientation) Figure 4:
Algorithm for estimating LRO at a point
A window of size 32 by 32 pixels is centered at the point where the LRO is to be found. This window is rotated to 16 different orientations, θi = iΠ/16, for i = 0, 1, 2… 15. At each orientation a projection along the y-axis of the window is formed:
Pix= 132y=031Wi(x,y) x= 0, 1, 2… 31
where W i(x,y) is the data inside the window at angle θi.
When the window is aligned with its x-axis perpendicular to the ridges, one expects maximum variation of the projection, since ridges are crossed as x varies. Alignment of the x- axis along the ridges should lead to minimum variation.
A second order Butterworth band pass filter removes the noise from the projections. The total variation Vi of each filtered projection is evaluated as:
Vi= x=031fpi(x+1)-fpi(x)
where
fpi=FFT (Pi(x))
The LRO estimate is given by imaxΠ/l6, where Vimax is the maximum of the 16 variations. This algorithm produces the correct value except in the noisiest regions. A simple model has been developed describing the behavior of LRO, and incorrect estimates can be dealt with by reference to this model.
LRF (Local Ridge Frequency)[1]
1) Project gray values of all the pixels located in each block along a direction orthogonal to the local orientation computed above. The projection forms 1D wave with the local extrema corresponding to the ridges and valleys.
2) L(i,j) is the average number of pixels between two consecutive peaks in 1D wave. The frequency f(i,j) is calculated as:
f(i,j)=1/L(i,j)
Algorithm for fingerprint enhancement :[1],[3]
In figure 5
1) The fast Fourier transform (FFT) F [9] of the fingerprint image is computed. Fast fourier transform is a discrete fourier transform algorithm which reduces the number of computations needed for N points from 2N2 to 2Nlog2N.
2) Fourier transform of the filter components Pi
Fig 4: Orientation field image [7]
depends upon the orientation values. Each directional filter Pi is point by point multiplied by F, obtaining n filtered image transforms PFi, i=1,2…..,n.
3) Inverse FFT is calculated for each PFi resulting in n filtered images Ii, i=1,2,…..,n (spatial domain).Inverse FFT is calculated which is exactly the reverse the process of FFT
4) The filtered image is then formed by selecting, for each pixel position, the pixel value from the prefiltered image whose direction of filtering corresponds most closely to the actual ridge orientation at that position.
The sinusoidal shaped waves of ridges and valleys vary slowly in a local constant orientation. Therefore a bandpass filter tuned to the corresponding frequency and orientation can effectively remove the noise and preserve the true ridge and valley structures.
For directional filtering, Gabor filter is proposed: [1],[4]
Gabor filter: It is a type of directional filter useful in frequency and spatial domains.
1) It has frequency selective and orientation selective properties.
2) Its impulse response is a Gaussian modulated sinusoidal bandpass filter.
Fig. 5: Algorithm for fingerprint enhancement [1]
3) By simple adjustment of mutually independent parameters, it can be configured for different shapes, orientations, different widths of bandpass and different central frequencies.
4) Ridge ending-provides a lowpass averaging effect along the ridge direction with the aim of linking small gaps and filling impurities due to pores and noise.
5) Ridge bifurcation performs a bandpass (differentiating) effect in a direction orthogonal to the ridges and valleys and to separate parallel linked ridges.
The original output of the Gabor filter and the enhanced images are shown in figure 7 and 8.
Even symmetric Gabor filters general form in the spatial domain:
hx,y,ф,f=
cos[2Πf(xcosф+ysinф) ]*exp[-0.5xρx2+yρy2]
where ф is the orientation of the Gabor filter, f is the frequency of the sinusoidal plane wave along the x axis, x and y are the standard deviations of the Gaussian envelope along the x and y axes.
If x and y are too large, the filter is more robust to noise but more likely to create spurious ridges and valleys.
If they are too small, the filter is not effective in removing the noise.
f, x and y depend on inter-ridge distance in the fingerprint image.
Gabor filter in Fourier domain:
Hx,y=12Πρxρycos2Πwxx+2Πwyy*exp[-0.5(xρx2+yρy2)]
Here 8 different values for ф are used : ф=i*Π/8 (i=1,2,……,8) with respect to x-axis are used.
A two-dimensional Gabor filter is a complex field sinusoidal grating that is modulated by a two dimensional Gaussian function in the spatial domain.
Set of 8 filtered images are obtained where in each of them direction normal to orientation of applied filter is enhanced as shown in figure 6 for two different orientations.
The encoding stage of AFIS consists of two phases:
1) Minutiae detection: There are a large number of false minutiae (i.e. points which have been incorrectly identified as minutiae) detected. Some are ‘soft’ and some are ‘hard’ minutiae. Soft false minutiae are caused by noisy imperfections in the enhanced images. Hard false minutiae are those which are present in the enhanced images but not present in the original image.
2) Minutiae detection: if the image is further processed then the false minutiae gets removed but it yields the ‘missed minutiae’, i.e. removal of the true minutiae from the list.
(a)Original image
Fig 7: Original figure(a) and its output after Gabor filtering(b) [7]
(b)Image after Gabor filtering
(a)22.50
(b)900
Fig 6: Filtered images for directions [1]
Fig. 8: Enhanced Image[7]
Experimental results:
(a) Original image, (b)Enhanced image by Gabor filtering, (c)Binarized image
Table 1: Original image and enhanced images are compared based on various minutiae[1]
A / P / M / F / EOriginal fingerprint Image / 187 / 70 / 30 / 117 / 100
Gabor filtered image / 131 / 80 / 20 / 51 / 100
A:The number of automatically extracted minutiae;
P: Number of matched minutiae
M:The number of missing minutiae
F: The number of false minutiae
E: The number of minutiae determined
Results of fingerprint image are shown in Table 1 [1]
Software implementation:
Software implementation of enhancement scheme is based on Gabor filtering and understanding the process and complexity involved with it. If it is determined that a more cost-efficient solution is possible for any function, the related aspects will be examined, depending on the time available.
Conclusions: As mentioned above, it is proposed to implement adaptive filtering for fingerprint enhancement. Due to the above mentioned characteristics of the fingerprint in the frequency domain directional filtering is used for the enhancement. This technique helps to increase the contrast between the ridges and valleys thereby removing noise from the image.
Acknowledgement: I heartily acknowledge my mentor. The ideas here are taken from the various IEEE papers and is supported by the various research papers on Fingerprint Enhancement methods.
References:
[1] A.M.Raicevic and B.M. Popovic, “An Effective and Robust Enhancement by Adaptive Filtering Domain”,SER.:ELEC.ENERG. vol.22, no. 1, pp.91-104 April 2009.
[2] B.G. Sherlock, D.M. Monro, and K. Millard, “Fingerprint Enhancement by Directional Fourier Filtering,” IEE Proc. Vision Image Signal Process., vol.141, no. 2, pp. 87-94, April 1994.
[3] L. Hong, Y.Wan, and A.K. Jain, “Fingerprint Image Enhancement: Algorithm and Performance Evolution,”IEEE Trans. Pattern Anal. Machine Intell., vol. 20, no. 8, pp. 777-789, Aug. 1998.
[4] J.Yang, L. Lin, T. Jiang, and Y.Fan, “A Modified Gabor Filter Design Method for Fingerprint Image Enhancement,” Pattern Recognition Letters, vol. 24, pp. 1805-1817,Jan. 2003.
[5] A.K. Jain and F. Farrokhnia,”Unsupervised Texture Segmentation Using Gabor Filters,” Pattern Recognition, vol. 24, no. 12, pp. 1,167-1,186, May 1991.
[6] K. Karu and A.K. Jain, “Fingerprint Classification,” Pattern Recognition, vol.29, no. 3, pp. 389-404, 1996.
[7] Database [online]. Availabe http://www.nist.gov/itl/iad/ig/sd27a.cfm.
[8] A.L Bovik, Handbook of Image and Video Processing. Elsevier, 2005.
[9]K.R.Rao, D.N.Kim and J.J.Hwang, “Fast Fourier Transform:Algorithms and Applications”, Heidelberg, Germany: Springer 2010.