IIT Kanpur
Fingerprint Recognition
CS676: Image Processing and Computer Vision
Written ByVinay Gupta Y6534, &
Rohit Singh Y6400
Fingerprint recognition
Introduction
Fingerprint recognition or fingerprint authentication refers to the automated method of
verifying a match between two human fingerprints. Fingerprints are one of many forms of
biometrics used to identify an individual and verify their identity. Because of their uniqueness
and consistency over time, fingerprints have been used for over a century, more recently
becoming automated (i.e. a biometric) due to advancement in computing capabilities.
Fingerprint identification is popular because of the inherent ease in acquisition, the numerous
sources (ten fingers) available for collection, and their established use and collections by law
enforcement and immigration.
Background
What is fingerprint?
A fingerprint is an impression of the friction ridges on all parts of the finger. A friction ridge is a
raised portion of the epidermis on the palmar (palm) or digits (fingers and toes) or plantar
(sole) skin, consisting of one or more connected ridge units of friction ridge skin. These are
sometimes known as "epidermal ridges" which are caused by the underlying interface between
the dermal papillae of the dermis and the interpapillary (rete) pegs of the epidermis. These
epidermal ridges serve to amplify vibrations triggered when fingertips brush across an uneven
surface, better transmitting the signals to sensory nerves involved in fine texture perception.
The ridges do not assist in gripping objects, sometimes in fact reducing grip to as much as 30%
compared to completely smooth finger pads.
Fingerprints may be deposited in natural secretions from the eccrine glands present in friction
ridge skin (secretions consisting primarily of water) or they may be made by ink or other
contaminants transferred from the peaks of friction skin ridges to a relatively smooth surface
such as a fingerprint card. The term fingerprint normally refers to impressions transferred from
the pad on the last joint of fingers and thumbs, though fingerprint cards also typically record
portions of lower joint areas of the fingers (which are also used to make identifications)
Fingerprint Recognition
Fingerprint recognition (sometimes referred to as dactyloscopy) or palm print identification is
the process of comparing questioned and known friction skin ridge impressions from fingers or
palms or even toes to determine if the impressions are from the same finger or palm. The
flexibility of friction ridge skin means that no two finger or palm prints are ever exactly alike
(never identical in every detail), even two impressions recorded immediately after each other.
Fingerprint identification (also referred to as individualization) occurs when an expert (or an
expert computer system operating under threshold scoring rules) determines that two friction
ridge impressions originated from the same finger or palm (or toe, sole) to the exclusion of all
others.
A known print is the intentional recording of the friction ridges, usually with black printers ink
rolled across a contrasting white background, typically a white card. Friction ridges can also be
recorded digitally using a technique called Live-Scan. A latent print is the chance reproduction
of the friction ridges deposited on the surface of an item. Latent prints are often fragmentary
and may require chemical methods, powder, or alternative light sources in order to be
visualized.
When friction ridges come in contact with a surface that is receptive to a print, material on the
ridges, such as perspiration, oil, grease, ink, etc. can be transferred to the item. The factors
which affect friction ridge impressions are numerous, thereby requiring examiners to undergo
extensive and objective study in order to be trained to competency. Pliability of the skin,
deposition pressure, slippage, the matrix, the surface, and the development medium are just
some of the various factors which can cause a latent print to appear differently from the known
recording of the same friction ridges. Indeed, the conditions of friction ridge deposition are
unique and never duplicated. This is another reason why extensive and objective study is
necessary for examiners to achieve competency.
Fingerprint Patterns
The analysis of fingerprints for matching purposes generally requires the comparison of several
features of the print pattern. These include patterns, which are aggregate characteristics of
ridges, and minutia points, which are unique features found within the patterns. It is also
necessary to know the structure and properties of human skin in order to successfully employ
some of the imaging technologies.
Patterns
The three basic patterns of fingerprint ridges are the arch, loop, and whorl.
An arch is a pattern where the ridges enter from one side of the finger, rise in the center
forming an arc, and then exit the other side of the finger.
The loop is a pattern where the ridges enter from one side of a finger, form a curve, and
tend to exit from the same side they enter.
In the whorl pattern, ridges form circularly around a central point on the finger.
Scientists have found that family members often share the same general fingerprint
patterns, leading to the belief that these patterns are inherited
Arch
Loop (Right Loop)
Whorl
Minutia features
Minutiae are major features of a fingerprint, using which comparisons of one print with another
can be made. Minutiae include:
Ridge ending - the abrupt end of a ridge
Ridge bifurcation - a single ridge that divides into two ridges
Short ridge, or independent ridge - a ridge that commences, travels a short distance and
then ends
Island - a single small ridge inside a short ridge or ridge ending that is not connected to
all other ridges
Ridge enclosure - a single ridge that bifurcates and reunites shortly afterward to
continue as a single ridge
Spur - a bifurcation with a short ridge branching off a longer ridge
Crossover or bridge - a short ridge that runs between two parallel ridges
Delta - a Y-shaped ridge meeting
Core - a U-turn in the ridge pattern
Techniques for Fingerprint matching
The large number of approaches to fingerprint matching can be coarsely classified into
three families.
Correlation-based matching: Two fingerprint images are superimposed and the
correlation between corresponding pixels is computed for different alignments (e.g.,
various displacements and rotations).
Minutiae-based matching: This is the most popular and widely used technique, being
the basis of the fingerprint comparison made by fingerprint examiners. Minutiae are
extracted from the two fingerprints and stored as sets of points in the two- dimensional
plane. Minutiae-based matching essentially consists of finding the alignment between
the template and the input minutiae sets that results in the maximum number of
minutiae pairings
Ridge feature-based matching: Minutiae extraction is difficult in very low-quality
fingerprint images. However, whereas other features of the fingerprint ridge pattern
(e.g., local orientation and frequency, ridge shape, texture information) may be
extracted more reliably than minutiae, their distinctiveness is generally lower. The
approaches belonging to this family compare fingerprints in term of features extracted
from the ridge pattern. In principle, correlation- and minutiae-based matching could be
conceived of as subfamilies of ridge feature-based matching, in as much as the pixel
intensity and the minutiae positions are themselves features of the finger ridge pattern.
1. Correlation-based Techniques :
Let T and I be the two fingerprint images corresponding to the template and the input fingerFingerprint, respectively. Then an intuitive measure of their diversity is the sum of squared
differences (SSD) between the intensities of the corresponding pixels:
where the superscript "T" denotes the transpose of a vector. If the terms ||T||2 and ||l||2 are
constant, the diversity between the two images is minimized when the cross-correlation (CC)
between T and I is maximized:
Note that the quantity 2, CC(T,I) appears as the third term in Equation 1. The cross- correlation
(or simply correlation) is then a measure of image similarity. Due to the displacement and
rotation that unavoidably characterize two impressions of a given finger, their similarity cannot
be simply computed by superimposing T and I and applying Equation 2.
Let I(x, y,) represent a rotation of the input image I by an angle around the origin (usually
the image center) and shifted by x, y pixels in directions x and y, respectively; then the
similarity between the two fingerprint images T and I can be measured as
However equation 3 rarely leads to acceptable results because of the following problems.
1. Non-linear distortion makes impressions of the same finger significantly different in terms of
global structure; in particular, the elastic distortion does not significantly alter the fingerprint
pattern locally, but since the effects of distortion get integrated in image space, two global
fingerprint patterns cannot be reliably correlated.
2. Skin condition and finger pressure cause image brightness, contrast, and ridge thickness to
vary significantly across different impressions.
3. A direct application of Equation 3 is computationally very expensive. For example, consider
two 400 x 400 pixel images; then the computation of the cross-correlation (Equation 2) for a
single value of the (x, y, ) triplet would require 16,000 multiplications and 16,000
summations.
2. Minutiae-based Methods:
Minutiae matching is certainly the most authentic and widely used method for fingerprint
matching.
Let T and I be the representation of the template and input fingerprint, respectively. Most
common minutiae matching algorithms consider each minutia as a triplet m = {x, y, } that
indicates the x, y minutia location coordinates and the minutia angle :
where m and n denote the number of minutiae in T and I, respectively.
A minutia mj in I and a minutia mi in T are considered "matching," if the spatial distance (sd)
between them is smaller than a given tolerance r0 and the direction difference (dd) between
them is smaller than an angular tolerance 0.
R0 and 0 are necessary to compensate for errors in feature extraction process and to account
for small plastic deformations.
Aligning the two fingerprints is a mandatory step in order to maximize the number of matching
minutiae. Correctly aligning two fingerprints certainly requires displacement (in x and y) and
rotation () to be recovered and likely involves other geometrical transformations like scale
resolution and other kinds of distortion.
Let map(.) be the function that maps a minutia m'j (from I) into m"j according to a given
geometrical transformation; for example, by considering a displacement of [x, y] and a
counterclockwise rotation around the origin.
Let mm(.) be an indicator function that returns 1 in the case where the minutiae m" j and mi ,
match according to Equations 5 and 6.
Then, the matching problem can be formulated as
where P(i) is an unknown function that determines the pairing between I and T minutiae;
in particular, each minutia has either exactly one mate in the other fingerprint or has no mate
at all:
1. P(i) = j indicates that the mate of the mi in T is the minutia m'j in I;
2. P(i) = null indicates that minutia mi in T has no mate in I;
3. a minutia m'j in I, such that for all i = 1..m, P(i) j has no mate in T;
4. for all i = 1..m, k = l..m, i k => P(i) P(k) or P(i) = P(k) = null (this requires that each minutia
in I is associated with a maximum of one minutia in T).
Expression 7 requires that the number of minutiae mates be maximized, independently of how
strict these mates are; in other words, if two minutiae comply with Equations 5 and 6, then
their contribution to expression 7 is made independently of their spatial distance and of their
direction difference.
Also, to comply with constraint 4 above, each minutia m"j already mated has to be marked, to
avoid mating it twice or more.
To achieve the optimum pairing (according to Equation 7), a slightly more complicated scheme
should be adopted i.e. in the case when a minutia of I falls within the tolerance hyper-sphere of
more than one minutia of T, the optimum assignment is that which maximizes the number of
mates.
Solving the minutiae matching problem (expression7) is trivial when the correct alignment
(x,y, ) is known; in fact, the pairing (i.e., the function P) can be determined by setting for
each i = 1..m:
Also, the maximization in 7 can be easily solved if the function P (minutiae correspondence) is
known; in this case, the unknown alignment (x, y, ) can be determined in the least square
sense.
However in practice both the function P and correct alignment (x, y, ) is not known which
makes the matching problem hard because of its exponential nature. Hence the minutiae
matching problem has been generally addressed as a point pattern matching problem which
can be solved using numerous approaches like relaxation methods, algebraic and operational
research solutions, tree-pruning approaches, energy-minimization methods, Hough transform,
and so on.
An approach to point pattern matching, as proposed by Chang et al. (1997) consists of the main
steps:
1. Detect the minutiae pair (called the principal pair) that receives the maximum Matching
Pair Support (MPS) and the alignment parameters (, s) that can match most minutiae
between T and I. The principal pair that has maximum MPS is determined through a
Hough transform-based voting process;
2. The remaining minutiae mates (i.e., the function P) are then determined once the two
fingerprints have been registered to superimpose the minutiae constituting the principal
pair;
3. The exact alignment is computed in the least square sense once the correspondence
function is known.
To accomplish Step 1, which is at the core of this approach, the algorithm considers segments
defined by pairs of minutiae mi2mi1 in T and mj2mj1 in I and derives, from each pair of
segments, the parameters ands simply as
A transformation (x, y, , s), which aligns the two segments, must necessarily involve a scale
change by an amount given by the ratio of the two segment lengths, and a rotation by an angle
equal to the difference between the two segment angles
Using the above algorithm we get the principal pair and the corresponding parameters (*, s*).
Thereafter we perform step 2 and 3 to find the rest matching pairs and their alignments. Thus
at the end of step 3 we get the max number of matching pairs of minutiae which helps in
matching the 2 fingerprints.
This is basically the crux of fingerprint matching algorithm. Various other techniques are
additionally used to efficiently solve and improve results of the matching problem like Minutiae
matching with pre-alignment, Global and local Minutiae matching, distortion corrections etc.
3. Ridge Feature-based Matching Techniques:
Techniques followed under this category resulted from the disadvantages Minutiae-based
methods suffered with. Some of them are:
Reliably extracting minutiae from poor quality fingerprints is very difficult. Although
minutiae may carry most of the fingerprint discriminatory information, they do not
always constitute the best tradeoff between accuracy and robustness;
Minutiae extraction is computationally expensive and time consuming.
Need for additional features to be used in conjunction with minutiae (and not as an
alternative) to increase system accuracy and robustness.
The commonly used alternative features under this category are:
spatial relationship and geometrical attributes of the ridge lines: In 1986 Moayer and Fu
and Isenor and Zaky introduced tree grammars to classify ridge line patterns and graph
structures to perform incremental graph matching which was carried out to compare a
set of ridges.
global and local texture information: Textures are defined by spatial repetition of basic
elements, and are characterized by properties such as scale, orientation, frequency,
symmetry, isotropy, and so on. Fingerprint ridge lines are mainly described by smooth
ridge orientation and frequency, except at singular regions. These singular regions are
discontinuities in a basically regular pattern and include the loop(s) and the delta(s) at a
coarse resolution and the minutiae points at a high resolution. Various techniques using
filters are applied to extract both global and local textures.
shape features : Ceguerra and Koprinska in 2002 proposed shape-based features, where
a compact one- dimensional shape signature that encodes the general shape of the
fingerprint is generated from the two-dimensional fingerprint image using a reference
axis.
Summary
This was a brief discussion about the different techniques use for fingerprint matching and recognition.
We included only a brief description of the techniques being used and did not include the procedure of
finger print sensing, feature extraction, fingerprint classification and indexing etc. since it is beyond the
scope of the report.
References
Handbook of Fingerprint Recognition
by Davide Maltoni, Dario Maio, Anil K. Jain, Salil Prabhakar
Fingerprint Classication and Matching
by Anil Jain (Dept. of Computer Science & Engg, Michigan State University) & Sharath Pankanti
(Exploratory Computer Vision Grp. IBM T. J. Watson Research Centre)
Wikipedia - http://en.wikipedia.org/wiki/Fingerprint_recognition
http://www.biometrics.gov/Documents/FingerprintRec.pdf
(Document By : National Science and Technology Council (NSTC), Committee on Technology,
Committee on Homeland and National Security Subcommittee on Biometrics )
