Fingerprint Matching using Gabor Filters

Muhammad Umer Munir and Dr. Muhammad Younas Javed

College of Electrical and Mechanical Engineering, National University of Sciences and Technology
Rawalpindi, Pakistan.

Abstract: We present a fingerprint matching scheme that come to an end which is called termination or it can divide
utilizes a ridge feature map to match fingerprint images. into two ridges which is called bifurcations (Figure 1).
The technique described here obviates the need for
extracting minutiae points to match fingerprint images.
The proposed scheme uses a set of 16 Gabor filters, whose
spatial frequencies correspond to the average inter-ridge
spacing in fingerprints, is used to capture the ridge
strength at equally spaced orientations. A circular
tessellation of filtered image is then used to construct the
ridge feature map. This ridge feature map contains both
global and local details in a fingerprint as a compact fixed
length feature vector. The fingerprint matching is based
on the Euclidean distance between two corresponding
feature vectors. The genuine accept rate of the Gabor
filter based matcher is observed to be ~ 10% to 15%
higher than that of minutiae-based matcher at low false
accept rates. Fingerprint feature extraction and matching
takes ~ 7.1 seconds on a Pentium IV, 2.4 GHz processor.

Keywords: Biometrics, Gabor filters, fingerprints,

matching, verification, core point
Figure 1: Ridge ending, core point and ridge bifurcation is
1. INTRODUCTION shown.

Fingerprint-based identification is one of the most 2. FINGERPRINT MATCHING

important biometric technologies which has drawn a
substantial amount of attention recently. Humans have Fingerprint matching techniques can be broadly classified
used fingerprints for personal identification for centuries as minutiae based and correlation based [1]. Minutiae-
and the validity of fingerprint identification has been well based technique first locates the minutiae points in a given
established. In fact, fingerprint technology is so common fingerprint image and matches their relative placements in
in personal identification that it has almost become the a stored template fingerprint. A good quality fingerprint
synonym of biometrics. Fingerprints are believed to be contains between 60 and 80 minutiae, but different
unique across individuals and across fingers of same fingerprints have different number of minutiae. The
individual. Even identical twins having similar DNA, are performance of minutiae-based techniques rely on the
believed to have different fingerprints. These observations accurate detection of minutiae points and the use of
have led to the increased use of automatic fingerprint- sophisticated matching techniques to compare two
based identification in both civilian and law-enforcement minutiae fields which undergo non-rigid transformations.
applications. Correlation based techniques compare the global pattern of
ridges and valleys to see if the ridges in the two
A fingerprint is the pattern of ridges and furrows on the fingerprints align. The global approach to fingerprint
surface of a fingertip. Ridges and valleys are often run in representation is typically used for indexing [2] and does
parallel and sometimes they bifurcate and sometimes they not offer reliable fingerprint discrimination.
terminate. When fingerprint image is analyzed at global
level, the fingerprint pattern exhibits one or more regions The ridge structure in a fingerprint can be viewed as an
where ridge lines assume distinctive shapes. These shapes oriented texture patterns having a dominant spatial
are characterized by high curvature, terminations, frequency and orientation in a local neighborhood. The
bifurcations, cross-over etc. These regions are called frequency is due to inter ridge-spacing present in a
singular regions or singularities. These singularities may fingerprint and the orientation is due to the flow pattern
be classified into three topologies; loop, delta and whorl. exhibited by ridges. Most textured images contain a
At local level, there are other important features known as narrow range of spatial frequencies. For a typical
minutiae can be found in the fingerprint patterns. Minutiae fingerprint images scanned at 500 dpi, there is a little
means small details and this refers to the various ways that variation in the spatial frequencies among different
the ridges can be discontinuous. A ridge can suddenly fingerprints. This implies that there is an optimal scale

National Conference on Emerging Technologies 2004 147

(spatial frequency) for analyzing the fingerprint texture. 3. CORE POINT DETECTION
By capturing the frequency and orientation of ridges in
local regions in the fingerprint, a distinct representation of Two different methods are used to detect core point in a
the fingerprint is possible [3]. fingerprint image (Figure 2). The core point location is
more accurately detected by using multiple techniques.
The proposed scheme first detects the core point in a
fingerprint image using two different techniques. Core 3.1 Core point detection using Poincare index
point is defined as the north most point of inner-most ridge
line. In practices, the core point corresponds to center of 1) Estimate the orientation field O using the least square
north most loop type singularity. Some fingerprints do not orientation estimation algorithm [5]. Orientation field
contain loop or whorl singularities, therefore it is difficult O is defined as an M x N image, where O(i,j)
to define core. In that kind of images, core is normally represents the local ridge orientation at pixel (i,j). An
associated with the maximum ridge line curvature. image is divided into a set of w x w non-overlapping
Detecting a core point is not a trivial task; therefore two blocks and a single orientation is defined for each
different techniques have been used to detect optimal core block.
point location. A circular region around the core point is
located and tessellated into 128 sectors. The pixel 2) Initialize A, a label image used to indicate the core
intensities in each sector are normalized to a constant point.
mean and variance. The circular region is filtered using a
bank of sixteen Gabor filters to produce a set of sixteen 3) For each pixel (i,j) in O, compute Poincare index [2]
filtered images. Gabor filter-banks are a well known and assign the corresponding pixels in A the value of
technique to capture useful information in specific band one if Poincare index is between 0.45 and 0.51.The
pass channels. Two such techniques have been discussed Poincare index at pixel (i,j) enclosed by a digital
in [3] and [4]. The average absolute deviation with in a curve, which consists of sequence of pixels that are on
sector quantifies the underlying ridge structure and is used or within a distance of one pixel apart from the
as a feature. The feature vector (2048 values in length) is corresponding curve, is computed as follows:
the collection of all the features, computed from all the
128 sectors, in every filtered image. The feature vector Np-1
captures the local information and the ordered Poincare (i ,j) = 1/(2π) ∑ ∆(k) (1)
enumeration of the tessellation captures the invariant k=0
global relationships among the local patterns. The
matching stage computes the Euclidean distance between δ(k) if |δ(k)| < π/2
the two corresponding feature vectors. ∆(k) = π + δ(k) if δ(k) ≤ −π/2 (2)
π − δ(k) otherwise
It is desirable to obtain representations for fingerprints
which are translation and rotation invariant. In the δ(k) = θ(x (k+1) mod Np ,y (k+1) mod Np) − θ(xk , yk )
proposed scheme, translation is taken care of by a (3)
reference point which is core point during the feature
extraction stage and the image rotation is handled by a For our method, Np is selected as 8.
cyclic rotation of the feature values in the feature vector.
The features are cyclically rotated to generate feature 4) The center of block with the value of one is
vectors corresponding to different orientations to perform considered to be the center of fingerprint. If more than
the matching. one block has value of one, then calculate the average
of coordinates of these blocks.

3.2 Core point detection using slope

1) Estimate the orientation field O using the least square

orientation estimation algorithm [5].

2) Smooth the orientation field in local neighborhood.

Let the smoothed orientation field be represented as
O’.

3) Initialize A, a label image used to indicate the core

point.

4) In O’(i , j) , start from first row (0, 0), find the block
Figure 2: Optimal core point location whose angle is between 0 and π /2 and then trace
down vertically until a block with a slope not with in

National Conference on Emerging Technologies 2004 148

 Figure 3: Filtered images and their corresponding feature vectors for orientations 0ο , 22.5ο , and 45 ο are shown.

that range (0 and π /2) is encountered. That block is pressure differences. For all the pixels in sector Si, where i
then marked [6] in A. This procedure is performed on ∈ (0,1,2….127), the normalized image is defined as:
all the rows of orientation field O’(i,j). Vo × ( I ( x , y ) − M i ) 2 if I(x,y) > Mi
M0 +
Vi
5) The center of block with the highest number of marks Ni(x, y) = (4)
is considered to be the center of fingerprint.
V × ( I ( x, y ) − M i ) 2 otherwise
M0 − o
Vi

3.3 Optimal Core Point Mi and Vi are estimated mean and variance of grey levels
in sector Si respectively. Mo and Vo are the desired mean
Now we have two core point locations obtained from and variance values, respectively. For our experiments,
above two techniques. Optimal core point is then both Mo and Vo are set to a value of 50.
calculated by taking average of x-coordinate values and
taking the maximum of two y-coordinate values as 6. FILTERING
maximum y-coordinate is more precise location of core
point. Gabor filters optimally capture both local orientation
and frequency information from a fingerprint image. By
tuning a Gabor filter to specific frequency and direction,
4. TESSELLATION the local frequency and orientation information can be
obtained [2][3] as shown in Figure 3. Thus, they are suited
The spatial tessellation of fingerprint image which consists for extracting texture information from images [4].
of the region of interest is defined by a collection of Daugman has successfully used these filters to extract
sectors. We use four concentric bands around the core discriminatory features from human iris [7].
point. Each band is 20 pixels wide and segmented into
thirty two sectors. Thus we have a total of 32 x 4 = 128 An even symmetric Gabor filter has the following
sectors and the region of interest is a circle of radius 100 general form in the spatial domain:
pixels, centered at the core point.
−1  x'2 y'2 
G(x, y ; f, θ ) = exp  2 + 2  cos(2πfx' ) (5)
5. NORMALIZATION  2 δ x' δ y' 
Normalization is performed to remove the effects of x’ = x sin θ + y cos θ (6)
sensor noise and gray level background due to finger
y’ = x cos θ - y sin θ (7)

National Conference on Emerging Technologies 2004 149

 Gabor filter based matching Minutiae based matching

100
G enunie Accept Rate (% )

90

G enunie Accept Rare (% )

85
95
80
90 75
70
85
65
80 60
0.1 0.9 3.5 5.3 8 16 0.1 1 2 3 4 5 6 10
False Accept Rate (%) False Accept Rate (%)

Figure 4: The ROC curve comparing the performance of the Gabor filter based approach with the minutiae based approach

where f is the frequency of the sinusoidal plane wave sixteen filtered images defines the components of our
along the direction θ from the x-axis, and δ x and δ y feature vector.
are the space constants of the Gaussian envelope along x The rotation invariance is achieved by cyclically rotating
and y axes, respectively. the features in a feature vector itself. A single step cyclic
rotation of the features corresponds to a feature vector
The filtering is performed in the spatial domain with a which would be obtained if the image was rotated by
mask size of 17x17. The frequency f is the average ridge 11.25 degrees.
frequency (1/K), where K is the average inter ridge
distance. The average inter ridge distance is approximately Fingerprint matching is based on finding the Euclidean
10 pixels in a 500 dpi fingerprint image. Hence, f = 1/10. distance between the corresponding feature vectors. This
Sixteen different orientations are examined. These minimum score corresponds to the best alignment of the
correspond to θ values of 0, 11.25, 22.5, 33.75, 45, two fingerprints being matched. If the Euclidean distance
56.25, 67.5, 78.75, 90, 101.25, 112.5, 123.75, 135, 146.25, between two feature vectors is less than a threshold, then
157.5 and 168.75 degrees. The values for δ x ' and δ y ' the decision that “the two images come from the same
finger” is made, otherwise a decision that “the two images
were empirically determined and each is set to 4 (about
come from different fingers” is made. Since the template
half the average inter ridge distance).
generation for storage in the database is an off-line
process, the verification time still depends on the time
7. FEATURE VECTOR
taken to generate a single template.
Let Fiθ ( x, y ) be the θ -direction filtered image for sector
Si. Now, ∀ i ∈ (0,1,2….127) and θ ∈ (0, 11.25, 8. EXPERIMENTAL RESULTS
22.5, 33.75, 45, 56.25, 67.5, 78.75, 90, 101.25, 112.5,
123.75, 135, 146.25, 157.5, 168.75 degrees) the feature The database of fingerprint images contains 180 images.
value, Viθ , is the average absolute deviation from the There are eight different impressions per finger. The
performance of biometric system can be shown as a
mean defined as: Receiver Operating Characteristic (ROC) curve that plots
the Genuine Accept Rate (GAR) against the False Accept
1   Rate (FAR) at different thresholds on the matching score.
Viθ = ∑ Fiθ ( x, y ) − Piθ  (8) We compare this performance with a minutiae-based
ni  ni  approach [4][8]. As can be seen in Figure 4, our approach
where ni is the number of pixels in Si and Piθ is the mean outperforms the minutiae based approach over wider range
of FAR values. For example, at 1% FAR, the Gabor filter
of pixel values of Fiθ ( x, y ) in sector Si. The average based fingerprint matcher gives a GAR of 91% while the
absolute deviation of each sector in each of the sixteen minutiae based matcher gives a GAR of 73%.
filtered images defines the components of our 2048-
dimensional feature vector [4]. The average absolute The Gabor filter based fingerprint technique takes ~ 7.1
deviation from the mean of each sector in each of the seconds on Pentium – IV, 2.4 GHz processor, for feature
extraction and matching. About 95% of the total time i.e. ~

National Conference on Emerging Technologies 2004 150

6.7 seconds, is taken by the convolution of the input image [2] A. K. Jain, S. Prabhakar and L. Hong, "A
with 16 Gabor filters. The convolution operation can be Multichannel Approach to Fingerprint
made significantly faster by dedicated DSP processors. If Classification", IEEE Transactions on PAMI,
the core point is correctly located, the features are Vol.21, No.4, pp. 348-359, April 1999.
translation invariant and the rotation handled in the [3] A. Ross, A. K. Jain, and J. Reisman, "A Hybrid
matching stage is very fast. As a result, the matching Fingerprint Matcher", Pattern Recognition, Vol.
process is extremely fast. 36, No. 7, pp. 1661-1673, 2003.
[4] A. K. Jain, A. Ross, and S. Prabhakar, "Fingerprint
9. SUMMARY AND FUTURE WORK Matching Using Minutiae and Texture Features",
Proc International Conference on Image
We have presented a fingerprint matching scheme that Processing (ICIP), pp. 282-285, Greece, October
utilizes both the frequency and orientation information 7-10, 2001.
available in a fingerprint. Sixteen Gabor filters are used to [5] L. Hong, Y. Wan and A.K. Jain, "Fingerprint
extract features from the template and input images. The Image Enhancement: Algorithms and Performance
primary advantage of our approach is improved translation Evaluation", IEEE Transactions on PAMI, Vol. 20,
and rotation invariance. The following areas of No. 8, pp.777-789, August 1998.
improvement are also being studied: [6] A. R. Rao, A Taxonomy for Texture Description
and Identification, New York: Springer-Verlag,
(1) New matching methods for comparing the ridge 1990.
feature maps of two images [7] J. Daugman, Recognizing persons by their iris
patterns, in: A. K. Jain, R. Bolle, S. Pankanti
(2) Constructing the ridge feature maps using adaptive (Eds.), Biometrics: Personal Identification in a
methods for optimal selection of Gabor filters Networked Society, Kluwer Academic Publishers,
1999, pp. 103-121.
REFERENCES [8] Anil K. Jain, Lin Hong, Sharat Pankanti, and Ruud
Bolle, “An identity authentication system using
[1] D. Maltoni, D. Maio, A. K. Jain, and S. Prabhakar, fingerprints,” Proceedings of the IEEE, vol. 85,
Handbook of Fingerprint Recognition, Springer- no. 9, pp. 1365–1388, 1997
Verlag, June 2003.

National Conference on Emerging Technologies 2004 151