Recent Researches in Communications, Automation, Signal Processing, Nanotechnology, Astronomy and Nuclear Physics
Euclidean Distance Based Fingerprint Matching
JADHAV S.D. BARBADEKAR A.B. Prof.(Dr.) PATIL S.P.
Dept of Computer Engg. Dept of Electronics Engg. Dept.of Electronics,
Vishwakarma Institute of Vishwakarma Institute of A.D. COE, Ashta,
Technology, Pune, INDIA. Technology, Pune, INDIA. Sangli, INDIA.
shivajijadhavcse@gmail.com bvbarbadekar@gmail.com vitmeit6@gmail.com
Abstract— Forensic Science is an art and science of a print made by an impression of ridges in the skin of a
finger, often used for biometric identification in criminal investigation. The law enforcement agencies uses system
like AFIS (Automatic Fingerprint Identification System) where reference fingerprints are stored in database
which are further used to match with latent fingerprints recovered from actual crime scene. There is high rate of
rejection of latent fingerprints since they are found in damaged condition due to blood spills, oil spills, wet
surface, snow, dust, etc that damages their quality and hence individuality of fingerprint is lost. Verification of
such mutilated fingerprints against stored reference fingerprint can be done using Laplacian, Gaussian, minutia-
based, etc methods. Each such method has there own advantages and disadvantages. The paper emphasis on the
use of Gabor filters for fingerprint identification. The fingerprint matching is done by extracting the Finger code
from both reference and latent fingerprints and then finding the Euclidean distance between the two
corresponding finger codes. After proper training the system, the result obtained provides 99 % rate of
recognition.
Keywords- Biometrics, Gabor filters, Finger code,Euclidean distance,latent fingerprint.
1.Introduction fingerprints. But such fingerprints are found in
fractured/damaged conditions at the crime scene due to blood
Biometrics is the science of establishing the identity of the spills, oil spills, wet surface, snow, dust, etc. Here degree of
individual based on the physical, chemical and behavioral accuracy is low but probability of availability at crime scene
characteristics of the person. There are nine biometric is high.
identification technologies such as: Face, Finger print, Hand As the condition in which latent fingerprints were
Geometry, Hand Vein, Iris, Retinal Scan, Signature, Voice recovered, it is highly impossible for a fingerprint expert to
Print, Thermo gram [1]. Fingerprint is the most commonly match it with stored reference fingerprint since police uses
and widely accepted biometric identification technique traditional method of matching minutia for fingerprint
among all other biometric identification techniques since it detection. Therefore the recovered latent fingerprint is needed
has highest probability to get recovered from actual crime to be first normalized and enhanced before matching.
scene. For other biometric evidences , it is prior condition that
there must be a properly installed biometric identification
device (like Iris recognizer, CCTV, Voice recorder, etc and a 2. System Design
power supply unit) at the crime scene which is not possible in
all the cases .But for the fingerprint evidence collection there The performance of Automated Fingerprint Identification
is no such prior condition as criminal leaves his/her System highly depends on the quality of input fingerprint
fingerprint accidently at the crime scene and thus availability images (both reference and latent one)[2,3,4,5].The
of such fingerprint at crime scene is highest than any other fingerprint images those are of very poor quality are rejected
biometric evidence. where as the fingerprint images that are of poor quality but
Reference fingerprint: Fingerprints that were enrolled can be recovered , as shown in figure2, are first normalized
under ideal conditions where suspect and criminals were and enhanced before matching. A good quality fingerprint
called upon at agency office and their fingerprints were image contains about 40 to 100 minutia and a poor quality
recorded with due cares are called as reference fingerprints. fingerprint image contains about 60 to 120 minutia. Such
Here, degree of accuracy and availability of such fingerprints large number of spurious minutia creates errors in the
is very high. localization and orientation of image and individuality of
Latent fingerprints: Fingerprints that were first detected fingerprint is lost.Therefore following steps are incorporated
(using available chemical techniques) from actual crime
in proposed system design as shown in below flowchart :
scene and later enrolled are called latent or chance
ISBN: 978-960-474-276-9 148
Recent Researches in Communications, Automation, Signal Processing, Nanotechnology, Astronomy and Nuclear Physics
2.1 Flowchart of proposed system
Input image
Fingerprint Enhancement & Normalization
Rotate image by 20 degree
Figure 2. Fingerprint image quality : (a ) Very poor (b) Poor .
Find out Centre Point of Image
2.2 Fingerprint enhancement & normalization
Fingerprint enhancement is done by using both the local
ridge orientation and local frequency information as stated by
Define Tessellation of Image Space
Lin Hong., et.all [6]. Let I be defined as gray level fingerprint
image of N×N matrix where I (i, j) represents intensity of the
th th
Apply Gabor filter pixel at i row and j column. The mean and variance of
gray level fingerprint image, I, is defined as:
Find the Finger code N −1 N −1
1
M (I ) =
N
2 ∑∑
i= 0 j=0
I (i, j ) -- (1)
N −1 N −1
1
Is
VAR ( I ) = 2 ∑ ∑ ( I (i, j ) − M ( I )) 2 -- (2)
Match
N i=0 j=0
Found
? It is a short time Fourier transform analysis of given input
fingerprint image. Normalization is done in order to remove
the unwanted noise which get added in the input fingerprint
Match found Match found image due to sensors [2].Normalization is done on each sector
Euclidean Euclidean separately by considering its estimated mean and variance.
The input fingerprint image I (x, y) can be normalized by
Distance Distance =0
using equation:
=abc.xyz
(V0 * I ( x , y ) − M i ) 2
N (x, y ) = M
i 0 +
Vi
; ifI ( x , y ) ≥ M
-- (3)
(V0 * I (x , y ) − M i ) 2
Store the feature in the feature library N (x, y ) = M
i 0 −
Vi
; otherwise
-- (4)
Where, M 0V0 are estimated mean and variance. M iVi are
Figure 1. Flowchart of proposed system
desired mean and variance respectively. The effect of
enhancement and normalization is shown in figure 3.
ISBN: 978-960-474-276-9 149
Recent Researches in Communications, Automation, Signal Processing, Nanotechnology, Astronomy and Nuclear Physics
2.3 Image Orientation
Image orientation can be done by both local ridge
orientation and local ridge frequency. Non-overlapping
blocks are created first. An oriented image O is treated as an
matrix of M×N where O (i, j) represents local ridge
orientation at pixel (i, j) for orientation based technique and in
case of frequency based technique O (i, j) represents local
ridge frequency at pixel (i, j) which is defined as the
frequency of the ridge, valley in local neighborhood along a
directional normal to the local ridge orientation [6].
Figure 4. Centre point determination of input fingerprint image of
resolution [400 ×400].Centre C[200,200] is indicated by plus sign.
2.6 Filtering
The sinusoidal-shaped waves of ridges and valleys vary
slowly in a local constant orientation which provides useful
information. As Gabor filter have both frequency selective
and orientation selective properties and provides optimal joint
resolution in both spatial and frequency domains therefore we
can use Gabor filter as band-pass filter that can be tuned to
the corresponding frequency and orientation and thus can
effectively remove the unwanted noise and helps to restore
the lost minutia points, ridge and valley structure. The even-
symmetric Gabor filter has the general form [6, 7] as:
1 X 2 Y 2
h ( x , y : Φ , f ) = exp − 2Φ + Φ2 cos (2πfx Φ ) -- (5)
2 δ x δ y
Figure 3. Fingerprint images : ( c ), ( e ) Before enhancement ( d ), ( f ) X Φ = x cos Φ + y sin Φ -- (6)
After enhancement.
YΦ = − x sin Φ + y cos Φ -- (7)
2.4 Centre point determination
We proposed a very simple and novel method of finding
the centre point of a given fingerprint image .Here length and Where,
breadth of fingerprint image is divided by numeric value 2
which gives its centre point. Suppose, an image has the
dimension of 400 × 400 resolution then point C [200,200]
Φ -- is the orientation of Gabor filter
f -- is the frequency of sinusoidal plane wave
will be its center point .This is shown in figure 4.Centre point
helps to achieve faster fingerprint verification. δ x, δ y – are the space constants of the Gaussian
envelope along X, Y- axes respectively
2.5 Registration point determination One should note that frequency characteristics of the filter
Matching is done on the basis of registration point which are completely determined by the local ridge frequency and
can be consistently detected in the fingerprint image by the orientation is determined by the local ridge orientation.
rotating it with an angle of 10° up to 45° . We found 20° The values of δ x, δ y was set to 4.0 and 4.0 respectively. It
as an approximate angle of rotation in all cases of fingerprint
images. Further divide the input fingerprint image into blocks is generally expected that values of δ x, δ y should be larger
and use least mean square orientation estimation algorithm to as it helps to be more robust against noise.
determine registration point [6, 7].
ISBN: 978-960-474-276-9 150
Recent Researches in Communications, Automation, Signal Processing, Nanotechnology, Astronomy and Nuclear Physics
2.7 Finger code generation nearest match which will display Euclidian distance (say,
The Mean, Standard deviation, Co-occurance, i.e Contrast 996.9907, 1450.9073, etc.). Now the mean of all such
in each sector will represent the feature vector and are defined Euclidean distance of 8 fingerprint images are taken (e.g. for
as: 101_1.tif series fingerprint images: mean of Euclidean
distance is 813.2008).This is shown in Table 1. Note that, if
we resubmit any fingerprint from available template, say
1 k 101_4.tif, then the system will calculate the finger code of
Mean ( Mi θ ) = ∑ Si
k i =1
-- (7) fingerprint image 101_4.tif and will match it with all the
available finger codes and will come with output of Euclidean
distance equal to zero and with corresponding Image ID.This
indicates that the recognition rate achieved is 99 %.This is
Std .deviation ( Fi θ ) = (∑ k
)
Riθ ( x , y ) − Mi θ -- (8) shown in figure 5.
Suppose, if a new template of fingerprint image other than
above (say 101_9.tif), is provided as input then it is expected
that the value of Euclidean distance must be zero or lie in
n
between zero and less than or equal to the respective mean of
Contrast = ∑ (i −
i, j =0
j ) 2 C 2 (i, j ) -- (9)
Euclidean distance (say 0 ≤ (ED of 101_9) ≤ 813.2008).If
this is not the case, then it is clear that the provided input
fingerprint image does not match with the stored template.
The experimental results tabulated at serial no.2 up to serial
Where,
no.10 for different sets of fingerprint images shows that if the
calculated Euclidean distance of any image is found to be
I= 0, 1, 2, 3 …47.
greater than the respective mean of Euclidean distance then it
θ = 0°,45°,90°,135°,270°. is clear that it is not the perfect match but if it is less than the
K=Total number of pixels in the sector Si respective mean of Euclidean distance then it shows a perfect
Riθ = is the sector of filtered image match. In all such cases, it is highly expected from the user of
the system to add the finger code of every fingerprint image,
C= Co-occurrence matrix
irrespective of its match found or not found since this helps to
increase the stored template database and in turn matching
Here, the gray level value in each sector of the filtered
probability of the system.
image will give the finger code.
2.8 Fingerprint Verification
Verification of input latent fingerprint image against
stored reference fingerprint images is done by finding the
Euclidean distance between the two corresponding finger
codes[6,7,8].It is highly expected that the value of Euclidean
distance should be zero or as minimum as possible. Smaller
value of Euclidean distance indicates closest match found and
larger value indicates very low probability of finding
corresponding match.
3. Experimentation and results
Fingerprint Verification Competition database 2004 (FVC
2004DB1, FVC 2004DB2, FVC 2004DB3, FVC 2004DB4)
were used for experimentation which contains set of single
reference fingerprint and respective seven damaged
fingerprints. Each such subset contains 80 fingerprint images.
We developed a Fingerprint identification system using Mat
lab 7.0. Initially, for fingerprint image, say 101_1.tif, the
database is empty thus no check is possible. First step is to
enhance the fingerprint image then finding out its orientation
and center point .Further finger code is extracted and added to
database. Now the Euclidean distance for each such
corresponding fingerprint image, say 101_2.tif, 101_3.tif,
101_4.tif, up to 101_8.tif is extracted and added, which helps Figure 5. Snapshot of developed Software : showning Higest rate of
to increase the database and simultaneously finding the recognition .
ISBN: 978-960-474-276-9 151
Recent Researches in Communications, Automation, Signal Processing, Nanotechnology, Astronomy and Nuclear Physics
TABLE I. CALCULATION OF EUCLIDEAN DISTANCE AND ITS
AVERAGE VALUE
Serial Image Euclidian Mean of Euclidean
Serial Image Euclidian Mean of Euclidean
No ID Distance Distance
No ID Distance Distance
6 106_1 2510.2676 1577.171
1 101_1 # 813.2008
106_2 395.3441
101_2 996.9907
106_3 1840.208
101_3 1450.9073
106_4 1100.7412
101_4 867.8048
106_5 1535.6802
101_5 679.3049
106_6 1705.5185
101_6 553.0061
101_7 1144.3372 106_7 1814.3931
101_8 813.256 106_8 1715.2153
2 102_1 1747.4794 1085.2734 7 107_1 1798.7755 934.9689
102_2 844.4314 107_2 1091.999
102_3 1365.2735 107_3 918.7048
102_4 928.8577 107_4 844.4832
102_5 873.0664 107_5 694.7853
102_6 1221.4432 107_6 781.2197
102_7 1059.6964 107_7 794.2974
102_8 641.9399 107_8 555.4863
3 103_1 922.9361 842.3499 8 108_1 1713.2818 1362.1609
103_2 1131.5571 108_2 1317.0248
103_3 1060.2302 108_3 1213.865
103_4 555.9761 108_4 1493.9085
103_5 756.9171 108_5 1405.6696
103_6 708.9675 108_6 1211.6913
103_7 902.6493 108_7 1290.6956
103_8 699.5665 108_8 1251.1511
4 104_1 1038.7306 743.0992 9 109_1 1693.4306 1282.6695
104_2 994.5667 109_2 1395.5213
104_3 844.6542 109_3 1178.8754
104_4 576.5214 109_4 1339.5763
104_5 675.6324 109_5 1342.9715
104_6 667.7179 109_6 987.5946
104_7 584.4963 109_7 1188.4600
104_8 562.4298 109_8 1134.9269
5 105_1 1366.4255 992.1052 10 110_1 933.7688 763.6706
105_2 830.2027 110_2 1103.2859
105_3 1112.2749 110_3 933.7778
105_4 745.1571 110_4 647.8003
105_5 1291.0413 110_5 487.8475
105_6 725.8707 110_6 687.02
105_7 1041.6371 110_7 664.137
105_8 824.2325 110_8 651.7278
(# Represents database is empty. No check is possible.)
ISBN: 978-960-474-276-9 152
Recent Researches in Communications, Automation, Signal Processing, Nanotechnology, Astronomy and Nuclear Physics
4. Conclusion [6] Lin Hong,Yifei Wan, Anil Jain “Fingerprint Image
enhancement : Algorithm and performance
It is highly expected to achieve the Euclidean distance to Evaluation “ IEEE Transaction on pattern analysis
be equal to zero for a perfect match else value of Euclidean and machine Intelligence ,Vol.20,No.8,August
distance should be less than or equal to the respective mean of 1998.
Euclidean distance. If it is greater than respective mean of
Euclidean distance then provided input fingerprint image [7] Anil k.Jain ,Salil Prabhakar,Lin Hong,Sharat
does not match with any stored template. The Crime Pankanti “Filterbank-Based Fingerprint
investigating agency always receives damaged latent Matching” , IEEE Transaction on Image
fingerprints from crime scene and when such fingerprints are Processing ,Vol.9,No.5,May 2000.
tested for matching then our system provides effective
[8] T. Chang, “Texture Analysis of Digitized
solution for such matching problem since system is trained
for matching single reference fingerprint against seven Fingerprints for SingularityDetection,” Proc. Fifth
damaged latent fingerprints. Experimental results show that ICPR, pp. 478-480, 1980.
developed system achieved highest rate of recognition i.e., 99 [9] P.E. Danielsson and Q. Z. Ye, “Rotation-Invariant
%. In future, need to develop a full fledged Mobile AFIS Operators Appliedto Enhancement of
system containing Gabor filter method for the Crime
Fingerprints,” Proc. Ninth ICPR, pp. 329333,
Investigation Agency which will assist them for finding the
perfect match in real time. Such mobile AFIS needs Rome, 1988.
additional hardware like MODEM, Wireless Connectivity, [10] J.G. Daugman, “Uncertainty Relation for
etc. Resolution in Space, Spatial-Frequency, and
ACKNOWLEDEGEMENT Orientation Optimized by Two-Dimensional Visual
Cortical Filters,” J. Optical Soc. Am., vol. 2, pp.
We are thankful for the co-operation given by Additional
DGP Shri S.P.S. Yadav, Special IGP, Dr.D.S Chavan
1,160-1,169, 1985.
(Superintendent of Police), Mr. Dilip Bhujbal (Superintendent
of Police-Law and Research), Mr. Dhore K.V (PI –FP
Expert), Mr. Koshti J.S (API- FP Expert), Mr. Prasad P. Joshi
(FP- Expert)), Mr.Shinde (Police Photographer), all from
Criminal Investigation Department (C.I.D), Maharashtra
State- Pune, India.
REFERENCES
[1] Arun Ross and Anil Jain “Biometric sensor
interoperability” : A case study in
Fingerprints“pp.134-145.
[2] Shivaji Jadhav ,Barbadekar Ashwini,et.all
“Performance analysis of finegerprint sensors “
ICMEE conference ,Koyoto,Japan 1-3 Aug-
2010,Vol.1,pp.75-80.
[3] R. Hashido" et al," A capacitive fingerprint
sensor chip using low temperature poly-si TFTs on
a glass substrate and a nove l and unique sensing
method" IEEE Journal of Solid-State Circuits,
2003, Vol.38 pp.274-280.
[4] H. Han, Y.Koshimoto " Characteristics of thermal
type fingerprint sensor" Biometric Technology for
Human Identification, Proc. Of SPIE, 2008, pp
.1-12.
[5] F.Alonso-Fernandez, F.Roli, J.Fierrez
"Performance of fingerprint quality measures
depending on sensor technology", Journal of
Electronic Imaging, 2008, Vol. 17, pp.1-lI.
ISBN: 978-960-474-276-9 153
