Similarity Measures for Fingerprint Matching

Kareem Kamal A.Ghany1, Aboul Ella Hassanien2 and Gerald Schaefer3

1 Faculty of Computers and Information, Beni Suef University, Egypt
2 Faculty of Computers and Information, Cairo University, Egypt
3 Department of Computer Science, Loughborough University, U.K.

Abstract— In this paper, we investigate different distance Motyka distance, cosine similarity, Jaccard coefficient, Dice
metrics for measuring the similarity between fingerprint coefficient, Hellinger distance, Neyman distance, Divergence
templates. In particular, we apply several of them during distance, Clark distance, correlation coefficient, Mahalnobis
the matching phase of a fingerprint system, and evaluate the distance, etc.
obtained results. Our experiments show the Dice coefficient In the following we define the four measure we have used
to give the most convincing results with a matching score of in our experiments.
93%, a false rejection rate of 0.04 and a false acceptance
rate of 0.006.
2.1 Correlation coefficient
Keywords: Fingerprint matching, similarity measure, distance, The correlation coefficient is defined as [2], [7]
Dice coefficient.
P
(a − µa )(b − µb )
Corr(A, B) = pP , (1)
1. Introduction (a − µa )2 (b − µb )2
P

Concepts of similarity and distance are important in many

and is a measure of statistical dependence between two
applications. They are for example necessary to measure the
random variables.
similarity of different objects, and thus form an essential
part in many pattern recognition applications that involve
clustering, classification, recognition, or retrieval. With a 2.2 Dice coefficient
large number of similarity measures having been introduced
in the literature, selecting an appropriate one for a particular The Dice coefficient is defined as [2], [3], [6], [8]
task is crucial, since the success of the related application 2a
may depend critically on this choice. Similarity measures Dice(A, B) = , (2)
2a + b + c
vary depending on the data types used [1].
Fingerprint matching refers to finding the similarity be- where a refers to the features present in both A and B, b
tween two given fingerprint images. While the choice of the features present only in A and c those present only in
matching algorithm depends on which fingerprint repre- B.
sentation is being used, the matching algorithm outputs a
similarity value that indicates its confidence in the decision
2.3 Sokal and Sneath index
that the two images are of the same finger.
In this paper, we compare different similarity measures for The Sokal and Sneath index is defined as [3], [6], [8]
fingerprint matching. In particular, in a set of experiments,
a
we evaluate four distance measures – correlation coefficient, SokalSneath(A, B) = . (3)
Dice coefficient, Sokal and Sneath index, and Simpson index a + 2b + 2c
– in the context of the fingerprint recognition approach
2.4 Simpson index
proposed in [9]. Our results indicate the Dice similarity to
give the best results. The Simpson index is defined as [3], [8]
a
2. Similarity Measures Simpson(A, B) =
min(a + b), (a + c)
. (4)
There are many distance metric families used for matching
and measuring the similarity between any two objects [2], 3. Fingerprint matching system
[3], [4], [5], [7]: Euclidean distance, Manhattan distance,
Chebyshev distance, Minkowski distance, Sorenson distance, Our experiments are based on the fingerprint matching
Sorgel distance, Kulczynksi distance, Canberra distance, system introduced in [9], which we summarise in the fol-
Lorentzian distance, Gower distance, Wave Hedges distance, lowing. An overview of the approach is given in Fig. 1.
 transform can be given as
 
1 1 1 ... 1 1
−N + 1 1 1 ... 1 1
 
 0 −N +2 1 ... 1 1
 
 . . . . . .
Knxn =  ,

 . . . . . .


 . . . . . .

 0 0 0 ... 1 1
0 0 0 ... −N + (N − 1) 1
(5)
with the terms Kxy of the matrix calculated as

 1, x <= y
K(x, y) = −N + (x − 1), x = y + 1 . (6)
0, x > y + 1

Fig. 1: Fingerprint matching architecture.
Applying Kekre’s transform on an N xN image, the
number of required additions is 2N (N − 1), and the number
of required multiplications is (N − 1).
3.1 Minutiae extraction Kekre’s transform is applied to the row mean and column
mean vectors of the image using Algorithm 2 to obtain
Kekre transform row mean and Kekre transform column
Fingerprint matching typically relies on minutiae extrac-
tion. Algorithm 1 details the technical steps of applying the mean feature vectors respectively. The generated transform
principal curves approach for this purpose. coefficients are used as feature vectors of the image. Features
for all images in a database can thus be obtained and
stored in feature tables for fingerprints images retrieval and
Algorithm 1 Fingerprint minutiae extraction from principal matching.
curves.
for i = 1 : n. do Algorithm 2 Application of Kekre’s transform.
Obtain graph G( vs), where V is a set of vertices, V = for xt in X, where x is the sample do
{v1 , v2 , ..., vn } Calculate Rv = [Avg(Row 1), Avg(Row 2), ...,
S = {(vi1 , vj1 ), ..., (vik , vjk )} = {Si1j1 , ..., Sikjk } is a Avg(Row n)], where Rv is the row mean vector.
set of edges. Calculate Cv = [Avg(Col 1), Avg(Col 2), ...,
Minimise a penalised distance function E(G) = Avg(Col n)], where Cv is the column mean vector.
∆(G) + λP (G). Multiply Rv by Kekre’s Transform matrix.
if a single point is found in the extracted edges set then Multiply Cv by Kekre’s Transform matrix.
Consider it as an ending of a simple ridge. Calculate the Euclidean distances from Rv,Cv.
else end for
Consider it as an ending of a ridge bifurcation.
end if
Filter the ridge endings and ridge bifurcations obtained 3.3 Bio-hash function
in the extraction step.
We use a hybrid system that combines a transformation
end for
based approach and a biometric cryptosystem approach
to increase the performance of protecting the biometrics
template process.
3.2 Feature extraction using Kekre’s transform Given n minutia points k1 , k2 , ..., kn , we can construct
the following m symmetric hash functions:

Kekre’s transform matrix [9] can be of any size N xN , h1 (k1 , k2 , ..., kn ) = k1 + k2 + ... + kn (7)
which need not to be an integer power of 2. We find that
h2 (k1 , k2 , ..., kn ) = k12 + k22 + ... + kn2
all diagonal and upper diagonal elements of this matrix
are 1, but that the lower diagonal part except the elements ...
just below diagonal are 0. The general matrix for Kekre’s hm (k1 , k2 , ..., kn ) = k1m + k2m + ... + knm
 We calculate, in Algorithm 3, the three parameters, trans- We applied these to each of ten fingerprints for ten persons
lation t with each fingerprint having five different templates stored
in the databases (for a sample see Fig. 2).
P 2P P P
i xi P i yi − Pxi xi yi
t= 2 2
, i = 1, 2, 3, ..., n, (8)
n i xi − ( i xi )
rotation r
P P P
xi yi
iP − i xi i yi
r= 2
P 2
, i = 1, 2, 3, ..., n, (9)
n i xi − ( i xi )
and error rate E
X
E= (yi − (t + rxi ))2 , i = 1, 2, 3, ..., n. (10)
i

Algorithm 3 Symmetric hash function using linear least

squares
Input: The Euclidean distance between minutiae points
with a selected reference point for both the normal and
transformed minutiae. Fig. 2: Sample of fingerprint templates used in the experi-
Output: The transformation t, rotation r , and error rate ments.
E.
As performance measure we utilised, the false rejection
for i = 1 : n do
rate (FRR)
h′1 = rh1 + t, where (h) is the normal distance, (h′ )
is the transformed distance, and Xi = sum(hi ), Yi = # false rejects
F RR = , (11)
sum(h′i ). # genuine matches
end for and the false acceptance rate (FAR)
for i = 1 : n. do # false accepts
Compute t using Eq. (8). F AR = , (12)
# imposter matches
Compute r using Eq. (9).
Compute E using Eq. (10). as well as the matching score, all calculated for each of the
end for approaches.
As we can see from Table 1, the results can differ quite
significantly depending on which similarity measure was
3.4 Matching phase chosen. Overall we can notice, that using the Dice coefficient
During authentication, the query is used to recover the gave the best performance with a matching score of 93% for
original biometric template from the secure sketch and the the same and of 89% for different fingers respectively. The
exact recovery of the original biometric data is verified to FAR and FRR based on the Dice coefficient were found
authenticate a user. Also, new hash values are produced by to be 0.04 and 0.006 respectively, giving a verification rate
the scanner and are matched to those stored in the database. (defined as 1 − FAR) of 0.96 and system security (defined
Matching can in principle be performed on both client and as 1 − FAR) of 0.994 respectively.
server side, and is conducted using hashed features instead
of the original template. Table 1: Matching score results for all similarity measures.
Authentication is then depending on the matching score similarity measure different finger same finger
and a pre-specified threshold, which decided whether two Correlation coefficient 0.89 0.92
fingerprints are from the same finger. The matching score is Sokal and Sneath index 0.18 0.19
Dice Coefficient 0.89 0.93
obtained based on the choice of similarity measure, while the Simpson index 0.47 0.48
threshold can be set depending on the type of application,
e.g. to a more restrictive value for a criminal identification
application compared to civilian applications. 5. Conclusions
In this paper, we have, in the context of a hybrid biomet-
4. Experimental Results ric approach for matching fingerprint templates, evaluated
We obtained experimental results based on the four chosen different similarity measures for fingerprint matching. The
similarity measures, i.e. correlation coefficient, Dice coeffi- employed fingerprint matching system first uses a principal
cient, Sokal and Sneath index, and Simpson index. curves approach to extract fingerprint features, and then
applies Kekre’s transform for fingerprint template trans- [4] G. Salton and M. McGill, "Introduction to modern information
formation. In addition, a bio-hash function for template retrieval", McGraw-Hill, 1983.
[5] L. Leydesdorff, "Similarity Measures, Author Cocitation Analysis,
protecting is utilised. Four different similarity measures have and Information Theory", Journal of the American Society for Infor-
been tested and the experimental results show the Dice mation Science and Technology, vol. 56, pp. 769-772, 2005.
coefficient to provide the best performance with a matching [6] B. De Baets, S. Janssens and H. De Meyer, "On the transitivity
of a parametric family of cardinality-based similarity measures",
score of 93%. International Journal of Approximate Reasoning, vol. 50, pp. 104-
116, 2009.
References [7] A.A. Goshtasby, "Similarity and Dissimilarity Measures", in "Image
Registration: Principles, Tools and Methods", Springer, 2012.
[1] S. Bandyopadhyay and S. Saha, "Unsupervised Classification: Simi-
[8] D. Sanchez and M. Batet, "Semantic similarity estimation in the
larity Measures, Classical and Metaheuristic Approaches, and Appli- biomedical domain: An ontology-based information-theoretic per-
cations", Springer, 2013. spective", Journal of Biomedical Informatics, vol. 44, pp. 749-759,
[2] S.D. Bharkad and M. Kokare, "Performance evaluation of distance
2011.
metrics: Application to fingerprint recognition", International Journal [9] K.K.A. Ghany, H.A. Hefny, A.E. Hassanien and M.F.Tolba, "Kekre’s
of Pattern Recognition and Artificial Intelligence, vol. 25, no. 6, 2011. Transform for Protecting Fingerprint Template", 13th International
[3] S.S. Choi, S.H. Cha and C.C. Tappert, "A Survey of Binary Similarity Conference on Hybrid Intelligent Systems, pp. 186-191, 2013.
and Distance Measures", Journal on Systemics Cybernetics and
Informatics, vol. 8, no. 1, pp. 43-48, 2010.