26-07-2012, 12:05 PM
Fingerprint Identification : A brief literary review
[attachment=29019]
INTRODUCTION
Biometric identification is one of the most amazing technological innovation of the recent
history and fingerprint identification being the most promising form of it and most widely used.
Out of a number of possible ways to match fingerprints, minutiae based matching is perhaps
the most widely studied and have yielded better results in the past as compared to the other
methods.
This paper is organized as follows : The reader is assumed to be already familiar with the
basic fingerprint identification technical terms. The section on literature gives a brief
introduction to different forms of fingerprint identification systems and lists the different
publications considered in this review. The section on findings deals with the themes
considered in the review and draws together results from different papers on the theme. The
next section draws a conclusion out of all the discussion followed by a list of references.
LITERATURE
Fingerprint identification is based upon unique and invariant features of fingerprints.
Fingerprints are graphical flow like ridges present in human fingers which are formed during
embryonic development, caused by ridges underneath the skin. According to FBI, the odds of
two people sharing the same fingerprints are one in 64,000,000,000. Fingerprints differ even
for ten fingers of the same person.[1]
Some of the advantages of fingerprint identification are : high distinctiveness , high
permanence, low potential for fraud and high performance with medium collectivity and
acceptability.
It also has certain drawbacks like need for training,finger and hand impairment,worn ridges
etc acting as a barrier to universality.
The method of identification is suitable for workstation access control , physical access
control, Information system control etc.
TYPES OF FINGERPRINTS
EXEMPLAR
PRINTS
LATENT
PRINTS
PATENT
PRINTS
PLASTIC
PRINTS
ELECTRONIC
RECORDING
Plain Arch
Tented Arch
Plain Loop Central
Pocket loop
Twinned Loop
Lateral Pocket
loop
Whorl
Accidental
FINGERPRINT PATTERNS
IDENTIFICATION CHARACTERSTICS
Ridge Ending Bifurcation DOT (or Island)
The accuracy of a fingerprint matching algorithm is measured by :
· FAR : It stands for false acceptance rate. It is defined as the ratio of the number of
impostor images considered as authentic by the algorithm to the total number of
impostor images.
· FRR : It stands for false rejection rate. It is defined as the ratio of the number of
authentic images not considered qualified by the algorithm to the total number of
authentic images.
When FAR and FRR are equal, we call it equal error rate (ERR). The performance of an
algorithm is generally measured in terms of ERR.
The uniqueness of fingerprint is determined by global features like valleys and ridges , and by
local features like ridge endings and ridge bifurcations , which are called minutiae.
The earlier work in the field was done by Moayer [2][3]. He considered fingerprint as a 1-D
character string and another method considering fingerprint as 2-D tree and verifying two
fingerprints by grammar matching. These methods worked for a rough classification but failed
on low quality images and thus, were not suitable for an identification system.
Among the various current fingerprint matching algorithms such as minutiae based matching
correlation filters based matching , transform feature based matching, graph based
matching ,genetic algorithms based and hybrid feature based matching and other global and
local methods, minutiae based fingerprint matching is dominant. A detailed reference for the
various techniques can be found in [4].
The above mentioned local features are the ones considered by the FBI for the identification
purposes [1]. The minutiae are obtained from the scanned image by fingerprint preprocessing
Usually the similarity of two fingerprints is determined by number of computing the total
number of matching minutiae and the process is called minutiae matching [5]. However,
general minutiae matching algorithms in automated Identity authentication systems use
minutiae orientation and alignment [6].
Extraction of minutiae features before matching needs a series of processes, including
orientation computation [7-9], image segmentation [8,9], image enhancement [10,11], ridge
extraction and shinning [12], minutiae extraction and filtering [13], etc. before the matching
can be done.
An earlier popular minutiae based technique was introduced by Bebis et al. [14] using the
delay triangulation method. Jain et. Al [15]. used ridge patterns in fingerprint matching. They
used ridge information to help with alignment. For a pair of template and query minutiae, the
template minutiae was rotated and translate taking the coordinates of this pair as origin and
axes along and perpendicular to its direction. However the computational cost involved with
method was still high. Minor modifications to reduce the computational cost and establish
better minutiae correspondence have been introduced [16][17][18] over the time.
He. et.al [17] proposed an improvement which was a good trade-off between performance
and computational cost. They first built a minutia-simplex that contains a pair of minutiae as
well as their associated textures, with its transformation-variant and invariant relative features
employed for the comprehensive similarity measurement and parameter estimation,
respectively. By the second step, they used the ridge-based nearest neighborhood among
minutiae to represent the ridge-based relative features among minutiae. Finally, they
modeled the relationship between transformation and the comprehensive similarity between
two fingerprints in terms of histogram for initial parameter estimation.
Wang [19] proposed a new feature called polyline to extract ridge information. For each ridge
sampling point, three transformation invariant feature were calculated and matching was
based on these features. However, it did not perform very well when the distortions were
present.
Graph based fingerprint matching algorithm was presented by Isener et. Al [20] . This method
however, is time consuming and complicated as complex algorithms like graph isomorphism
has to be adopted in the system. An improvement was presented by Hrechak et.al[21]
Another approach is the application of correlation filters to the fingerprint identification.
Correlation filters have added features like built in shift invariance, closed form expressions
and trade off discrimination for distortion tolerance [22].The one-to-one correlation of
fingerprints on a large set of data yields poor results for fingerprint matching because of the
elastic distortions between two fingerprints of the same finger [23]. The distortions can be
significant enough that the correlation cannot recognize elastic-distorted versions of the same
fingerprint and cannot discriminate between a matching fingerprint and a non-matching
fingerprint of the same class. C.I. Watson et.al proposed a distortion-tolerant filter for elasticdistorted
fingerprint matching . K.Venkataramani showed that MACE and OTSDF filters
demonstrate good performance in fingerprint verification without requiring any perprocessing.
Earlier work in the field of combining optical features with neural networks was done by
Gamble [24]. Sujan et. al[25] classified binary fingerprints using HAVNET. The number of
output nodes of HAVNET was equal to number of enrolled fingerprints. So whenever a new
fingerprint was enrolled, an output node has to be added to HAVENET. The method was not
able to distinguish fingerprints of similar shapes. Work in the same area was also carried on
by Wilson[26].
During the last few years, some genetic algorithm based approaches have been suggested.
Tan et. al. [27] proposed a straightforward Genetic Algorithm(GA) for fingerprint matching.
These methods try to identify the optimal global alignment between two fingerprints. However,
the convergence may take a lot of time mainly because these methods employ either the
simple evolutionary algorithm or its variants, which are not well suited to fine-tuning the
search in complex search spaces. Sheng et. al. [28] develops a memetic fingerprint matching
algorithm.Then, Sheng et. al. [29] propose an improved integrated method which works by
suggesting a consensus matching function in genetic algorithm (GA), which combines
different matching criteria based on heterogeneous features.Feng et. al. [30] assigned each
minutia two descriptors: texture-based and minutiae-based descriptors and proposed a novel
fingerprint matching based on these descriptors. This method produced good results with
true/false minutiae classification but unsatisfactory with the case distorted minutiae set. Thai
and hong Combined global features and local minutiae descriptors in Genetic Algorithms for
Fingerprint Matching.
The following section discusses some of the challenges encountered in fingerprint
identification systems and different strategies to resolve them.
Challenges with fingerprint identification
Some of the common challenges related with fingerprint technology are low quality or
degraded input images , noise reduction , data security related issues with fingerprint
systems etc.
The low quality or distorted fingerprint images is perhaps the most common problem. The
degradation can be of types like natural effects like cuts,bruises etc or it may be appearance
of gaps on ridges or parallel ridge intercepts. The fingerprint enhancement techniques not
only have to enhance the quality of image but at the same time, also have to reduce noise.
Much work has been done in this field and most commonly used method for this is application
filters.
O’Gonnan and Nickerson [31] proposed the first method which employed contextual
filtering for fingerprint enhancement. Hong et al. [32], reported fingerprint enhancement based
on the estimated local ridge orientation and frequency clarification of ridge and valley
structures of input . Khmanee and Nguyen [33] proposed a method to develop 2D gabor
filters for this purpose. Wang [34] proposed another method using log-Gabor filters. Çavuso
glu [35] suggested a fast filtering method based on referenced mask of ̆ parabolic coefficients.
Cheng and Titan [36] proposed scale space theory in which enhancement was done by first
decomposing a series of images and then reorganizing them to a finer scheme using a cursor.
Also recently, M.S.khalil et. Al [37] proposed a method for to verify an enhanced fingerprint
image using four statistical descriptors which characterize a co-occurrence matrix.
To address the concerns of security related to biometrics, a more secure biometric technique
called canceled biometrics is introduced. [38] It is a privacy protection technology. Instead of
storing data on the system database during enrollment, the data is stored in encrypted form.
During recognition, the system would transform the data using the same non-invertible
transformation and the matching would be carried out in the transformed space. A detailed
introduction to this branch of biometrics can be found in [39][40]. These papers empirically
compare results of some of the transformations like polar, Cartesian, surface folding etc. and
demonstrate that surface folding transformation achieves better results than other two. Polar
transformation performs better than Cartesian in terms of EER, but the encryption is less
strong. Chen et.al [41] used circular rings of minutiae and improved both security and
accuracy.
Fuzzy techniques show some similarity to the method of technology of canceled biometrics. A
type of encryption based on cryptographic construction called fuzzy vaults was proposed by
Sudan and Juels [42][43].Clancy proposed a fingerprint vault using sets of multiple minutiae
locations.[44] . Uldag et.al [45] proposed a system which used minutiae lines to store the
information.
Conclusion
The fingerprint identification is one of the oldest and most common form of biometric
identification. As a result, its a common misconception that fingerprint recognition is a
completely solved problem. The truth is, the research on fingerprint recognition never stops
due to its complexity and Intractability. Some of the directions for the future research work in
the field can be listed as follows :
Improved feature extraction and matching :
We still need to improve algorithms for better feature extraction and matching in a
robust manner, especially for low quality and degraded images obtained from cheap image
acquisition devices.
Secure fingerprint-based identification systems :
Like any other identification technique, fingerprint identification is not completely
immune to fraud. R. Capelli et. Al [46] described a technique to reverse engineer minutiae
based fingerprint templates. Several potential threats to the identification systems are attacks
on communication channels, presenting fake fingerprints, replacing software modules with
trojans, attacks on databases etc. A considerable amount of research on fake-detection
approaches and template-protection techniques (some of which were described in the
previous section ) is definitely needed to address the most critical security threats.
[attachment=29019]
INTRODUCTION
Biometric identification is one of the most amazing technological innovation of the recent
history and fingerprint identification being the most promising form of it and most widely used.
Out of a number of possible ways to match fingerprints, minutiae based matching is perhaps
the most widely studied and have yielded better results in the past as compared to the other
methods.
This paper is organized as follows : The reader is assumed to be already familiar with the
basic fingerprint identification technical terms. The section on literature gives a brief
introduction to different forms of fingerprint identification systems and lists the different
publications considered in this review. The section on findings deals with the themes
considered in the review and draws together results from different papers on the theme. The
next section draws a conclusion out of all the discussion followed by a list of references.
LITERATURE
Fingerprint identification is based upon unique and invariant features of fingerprints.
Fingerprints are graphical flow like ridges present in human fingers which are formed during
embryonic development, caused by ridges underneath the skin. According to FBI, the odds of
two people sharing the same fingerprints are one in 64,000,000,000. Fingerprints differ even
for ten fingers of the same person.[1]
Some of the advantages of fingerprint identification are : high distinctiveness , high
permanence, low potential for fraud and high performance with medium collectivity and
acceptability.
It also has certain drawbacks like need for training,finger and hand impairment,worn ridges
etc acting as a barrier to universality.
The method of identification is suitable for workstation access control , physical access
control, Information system control etc.
TYPES OF FINGERPRINTS
EXEMPLAR
PRINTS
LATENT
PRINTS
PATENT
PRINTS
PLASTIC
PRINTS
ELECTRONIC
RECORDING
Plain Arch
Tented Arch
Plain Loop Central
Pocket loop
Twinned Loop
Lateral Pocket
loop
Whorl
Accidental
FINGERPRINT PATTERNS
IDENTIFICATION CHARACTERSTICS
Ridge Ending Bifurcation DOT (or Island)
The accuracy of a fingerprint matching algorithm is measured by :
· FAR : It stands for false acceptance rate. It is defined as the ratio of the number of
impostor images considered as authentic by the algorithm to the total number of
impostor images.
· FRR : It stands for false rejection rate. It is defined as the ratio of the number of
authentic images not considered qualified by the algorithm to the total number of
authentic images.
When FAR and FRR are equal, we call it equal error rate (ERR). The performance of an
algorithm is generally measured in terms of ERR.
The uniqueness of fingerprint is determined by global features like valleys and ridges , and by
local features like ridge endings and ridge bifurcations , which are called minutiae.
The earlier work in the field was done by Moayer [2][3]. He considered fingerprint as a 1-D
character string and another method considering fingerprint as 2-D tree and verifying two
fingerprints by grammar matching. These methods worked for a rough classification but failed
on low quality images and thus, were not suitable for an identification system.
Among the various current fingerprint matching algorithms such as minutiae based matching
correlation filters based matching , transform feature based matching, graph based
matching ,genetic algorithms based and hybrid feature based matching and other global and
local methods, minutiae based fingerprint matching is dominant. A detailed reference for the
various techniques can be found in [4].
The above mentioned local features are the ones considered by the FBI for the identification
purposes [1]. The minutiae are obtained from the scanned image by fingerprint preprocessing
Usually the similarity of two fingerprints is determined by number of computing the total
number of matching minutiae and the process is called minutiae matching [5]. However,
general minutiae matching algorithms in automated Identity authentication systems use
minutiae orientation and alignment [6].
Extraction of minutiae features before matching needs a series of processes, including
orientation computation [7-9], image segmentation [8,9], image enhancement [10,11], ridge
extraction and shinning [12], minutiae extraction and filtering [13], etc. before the matching
can be done.
An earlier popular minutiae based technique was introduced by Bebis et al. [14] using the
delay triangulation method. Jain et. Al [15]. used ridge patterns in fingerprint matching. They
used ridge information to help with alignment. For a pair of template and query minutiae, the
template minutiae was rotated and translate taking the coordinates of this pair as origin and
axes along and perpendicular to its direction. However the computational cost involved with
method was still high. Minor modifications to reduce the computational cost and establish
better minutiae correspondence have been introduced [16][17][18] over the time.
He. et.al [17] proposed an improvement which was a good trade-off between performance
and computational cost. They first built a minutia-simplex that contains a pair of minutiae as
well as their associated textures, with its transformation-variant and invariant relative features
employed for the comprehensive similarity measurement and parameter estimation,
respectively. By the second step, they used the ridge-based nearest neighborhood among
minutiae to represent the ridge-based relative features among minutiae. Finally, they
modeled the relationship between transformation and the comprehensive similarity between
two fingerprints in terms of histogram for initial parameter estimation.
Wang [19] proposed a new feature called polyline to extract ridge information. For each ridge
sampling point, three transformation invariant feature were calculated and matching was
based on these features. However, it did not perform very well when the distortions were
present.
Graph based fingerprint matching algorithm was presented by Isener et. Al [20] . This method
however, is time consuming and complicated as complex algorithms like graph isomorphism
has to be adopted in the system. An improvement was presented by Hrechak et.al[21]
Another approach is the application of correlation filters to the fingerprint identification.
Correlation filters have added features like built in shift invariance, closed form expressions
and trade off discrimination for distortion tolerance [22].The one-to-one correlation of
fingerprints on a large set of data yields poor results for fingerprint matching because of the
elastic distortions between two fingerprints of the same finger [23]. The distortions can be
significant enough that the correlation cannot recognize elastic-distorted versions of the same
fingerprint and cannot discriminate between a matching fingerprint and a non-matching
fingerprint of the same class. C.I. Watson et.al proposed a distortion-tolerant filter for elasticdistorted
fingerprint matching . K.Venkataramani showed that MACE and OTSDF filters
demonstrate good performance in fingerprint verification without requiring any perprocessing.
Earlier work in the field of combining optical features with neural networks was done by
Gamble [24]. Sujan et. al[25] classified binary fingerprints using HAVNET. The number of
output nodes of HAVNET was equal to number of enrolled fingerprints. So whenever a new
fingerprint was enrolled, an output node has to be added to HAVENET. The method was not
able to distinguish fingerprints of similar shapes. Work in the same area was also carried on
by Wilson[26].
During the last few years, some genetic algorithm based approaches have been suggested.
Tan et. al. [27] proposed a straightforward Genetic Algorithm(GA) for fingerprint matching.
These methods try to identify the optimal global alignment between two fingerprints. However,
the convergence may take a lot of time mainly because these methods employ either the
simple evolutionary algorithm or its variants, which are not well suited to fine-tuning the
search in complex search spaces. Sheng et. al. [28] develops a memetic fingerprint matching
algorithm.Then, Sheng et. al. [29] propose an improved integrated method which works by
suggesting a consensus matching function in genetic algorithm (GA), which combines
different matching criteria based on heterogeneous features.Feng et. al. [30] assigned each
minutia two descriptors: texture-based and minutiae-based descriptors and proposed a novel
fingerprint matching based on these descriptors. This method produced good results with
true/false minutiae classification but unsatisfactory with the case distorted minutiae set. Thai
and hong Combined global features and local minutiae descriptors in Genetic Algorithms for
Fingerprint Matching.
The following section discusses some of the challenges encountered in fingerprint
identification systems and different strategies to resolve them.
Challenges with fingerprint identification
Some of the common challenges related with fingerprint technology are low quality or
degraded input images , noise reduction , data security related issues with fingerprint
systems etc.
The low quality or distorted fingerprint images is perhaps the most common problem. The
degradation can be of types like natural effects like cuts,bruises etc or it may be appearance
of gaps on ridges or parallel ridge intercepts. The fingerprint enhancement techniques not
only have to enhance the quality of image but at the same time, also have to reduce noise.
Much work has been done in this field and most commonly used method for this is application
filters.
O’Gonnan and Nickerson [31] proposed the first method which employed contextual
filtering for fingerprint enhancement. Hong et al. [32], reported fingerprint enhancement based
on the estimated local ridge orientation and frequency clarification of ridge and valley
structures of input . Khmanee and Nguyen [33] proposed a method to develop 2D gabor
filters for this purpose. Wang [34] proposed another method using log-Gabor filters. Çavuso
glu [35] suggested a fast filtering method based on referenced mask of ̆ parabolic coefficients.
Cheng and Titan [36] proposed scale space theory in which enhancement was done by first
decomposing a series of images and then reorganizing them to a finer scheme using a cursor.
Also recently, M.S.khalil et. Al [37] proposed a method for to verify an enhanced fingerprint
image using four statistical descriptors which characterize a co-occurrence matrix.
To address the concerns of security related to biometrics, a more secure biometric technique
called canceled biometrics is introduced. [38] It is a privacy protection technology. Instead of
storing data on the system database during enrollment, the data is stored in encrypted form.
During recognition, the system would transform the data using the same non-invertible
transformation and the matching would be carried out in the transformed space. A detailed
introduction to this branch of biometrics can be found in [39][40]. These papers empirically
compare results of some of the transformations like polar, Cartesian, surface folding etc. and
demonstrate that surface folding transformation achieves better results than other two. Polar
transformation performs better than Cartesian in terms of EER, but the encryption is less
strong. Chen et.al [41] used circular rings of minutiae and improved both security and
accuracy.
Fuzzy techniques show some similarity to the method of technology of canceled biometrics. A
type of encryption based on cryptographic construction called fuzzy vaults was proposed by
Sudan and Juels [42][43].Clancy proposed a fingerprint vault using sets of multiple minutiae
locations.[44] . Uldag et.al [45] proposed a system which used minutiae lines to store the
information.
Conclusion
The fingerprint identification is one of the oldest and most common form of biometric
identification. As a result, its a common misconception that fingerprint recognition is a
completely solved problem. The truth is, the research on fingerprint recognition never stops
due to its complexity and Intractability. Some of the directions for the future research work in
the field can be listed as follows :
Improved feature extraction and matching :
We still need to improve algorithms for better feature extraction and matching in a
robust manner, especially for low quality and degraded images obtained from cheap image
acquisition devices.
Secure fingerprint-based identification systems :
Like any other identification technique, fingerprint identification is not completely
immune to fraud. R. Capelli et. Al [46] described a technique to reverse engineer minutiae
based fingerprint templates. Several potential threats to the identification systems are attacks
on communication channels, presenting fake fingerprints, replacing software modules with
trojans, attacks on databases etc. A considerable amount of research on fake-detection
approaches and template-protection techniques (some of which were described in the
previous section ) is definitely needed to address the most critical security threats.