Fingerprint RecognitionFingerprint Recognition
Anil K. Jain
Michigan State University
jain@cse.msu.edu
http://biometrics.cse.msu.edu
© Jain, 2004
OutlineOutline
• Brief History
• Fingerprint Representation
• Minutiae-based Fingerprint Recognition
• Fingerprint Enhancement
• Other methods of Fingerprint Recognition
• Ridge Feature Maps
• Correlation
• Fingerprint Classification
• Fingerprint Individuality
• Estimating non-linear deformation
© Jain, 2004
FingerprintsFingerprints
• Description: graphical flow like ridges present in human fingers
• Formation: during embryonic development
• Permanence: minute details do not change over time
• Uniqueness: believed to be unique to each finger
• History: used in forensics and has been extensively studied
© Jain, 2004
Biological Principles of FingerprintsBiological Principles of Fingerprints
• Individual epidermal ridges and valleys have
different characteristics for different fingerprints
• Configurations and minute details of individual ridges
and valleys are permanent and unchanging (except
for enlargement in the course of bodily growth)
• Configuration types are individually variable, but
they vary within limits which allow for systematic
classification
© Jain, 2004
© Jain, 2004
History of FingerprintsHistory of Fingerprints
Fingerprint on Palestinian lamp (400 A.D.) Bewick’s trademark (1809)
A Chinese deed of sale (1839) signed with a fingerprint
© Jain, 2004
History of FingerprintsHistory of Fingerprints
• Many impressions of fingers have been found on ancient pottery
• Grew (1684): first scientific paper on ridges, valleys & pore structures
• Mayer (1788): detailed description of anatomical formation of
fingerprints
• Bewick (1809): used his fingerprint as his trademark
• Purkinje (1823): classified fingerprints into 9 categories based on ridges
• Herschel (1858): used fingerprints on legal contracts in Bengal
• Fauld (1880): suggested "scientific identification of criminals" using
fingerprints
• Vucetich (1888): first known user of dactylograms (inked fingerprints)
• Scotland Yard (1900): adopted Henry/Galton system of classification
• FBI (1924) set up a fingerprint identification division with a database of
810,000 fingerprints
• FBI (1965): installed AFIS with a database of 810,000 fingerprints
• FBI (2000): installed IAFIS with a database of 47 million 10 prints;
conducts an average of 50,000 searches/ day; ~15% of searches are in
lights out mode. Response time: 2 hours for criminal search and 24
hours for civilian search
© Jain, 2004
Fingerprint MatchingFingerprint Matching
• Find the similarity between two fingerprints
Fingerprints from the same finger
Fingerprints from two different fingers
© Jain, 2004
Fingerprint ClassificationFingerprint Classification
• Assign fingerprints into one of pre-specified types
Plain Arch Tented Arch Right Loop Left Loop
Plain WhorlAccidental Pocket Whorl Double Loop
© Jain, 2004
© Jain, 2004
Fingerprint SensorsFingerprint Sensors
• Optical, capacitive, ultrasound, pressure, thermal, electric field
© Jain, 2004
Types of Fingerprint ImagesTypes of Fingerprint Images
Flat Fingerprint
(One-touch print from a
single-finger livescan device)
Unsegmented Slap Fingerprint
(4-finger simultaneous impression from livescan
devices or scanned from paper FP cards)
Rolled Fingerprint
(Image collected by rolling the
finger across the livescan platen
or paper from nail to nail)
© Jain, 2004
TerminologyTerminology
• Fingerprint – Impression of a finger
• Minutiae – Ridge bifurcations,endings and many
other features (52 types listed, 7 are usually used
by human experts and two by automated systems)
• Core – uppermost point on the innermost ridge
• Delta – separating point between pattern area and
non-pattern area
• Pattern class – determined by ridge flow
characteristics
© Jain, 2004
Fingerprint RepresentationFingerprint Representation
• Local ridge characteristics (minutiae): ridge
ending and ridge bifurcation
• Singular points: Discontinuity in ridge orientation
Core
Delta
Ridge Bifurcation Ridge Ending
© Jain, 2004
Minutiae-based RepresentationMinutiae-based Representation
© Jain, 2004
Challenges in Fingerprint IdentificationChallenges in Fingerprint Identification
• Cuts and bruises on finger; dry or oily fingers; ~3% of
fingerprints are not of “good” quality
• Wear and tear of sensor; no proven contactless fingerprint
sensor technology is currently available
• New compact solid-state sensors capture only a small portion
of the fingerprint
• Fingerprint impression is often left on the sensor
• Non-universality of fingerprint
• Changes in sensor technology; sensor interoperability
Non-universality of fingerprint
Fake fingerprint
© Jain, 2004
Fingerprint Matching TechniquesFingerprint Matching Techniques
• Minutiae-based
• Correlation-based
• Ridge Feature-based
© Jain, 2004
Minutiae-based Fingerprint
Verification System
Minutiae-based Fingerprint
Verification System
© Jain, 2004
Steps in Minutiae ExtractionSteps in Minutiae Extraction
• Orientation field estimation
• Fingerprint area location
• Ridge extraction
• Thinning
• Minutia extraction
© Jain, 2004
Minutiae Extraction AlgorithmMinutiae Extraction Algorithm
© Jain, 2004
Minutiae Extraction AlgorithmMinutiae Extraction Algorithm
Ridge FilterOrientation EstimationInput Image
Minutiae Extraction Post-processing Ridge Thinning
Minutiae Detection
© Jain, 2004
Orientation FieldOrientation Field
• Angle formed by the ridges with horizontal axis
• Usually computed at the block level and not at the
pixel level (more resistant to noise)
• The gradient direction is perpendicular to the
ridge direction
• An arithmetic average of gradient angles is not
well defined
• Doubling the angles allows local gradient
estimates to be averaged
© Jain, 2004
Orientation Field Estimation AlgorithmOrientation Field Estimation Algorithm
• Divide the input fingerprint image into nonoverlapping
blocks of size W x W
• Compute the gradients Gx (i, j) and Gy (i, j) at
each pixel (i, j) using Sobel or Marr-Hildreth
operator
• Least squares estimate of the local orientation of
the block centered at (i, j) is
⎟
⎟
⎟
⎠
⎞
⎜
⎜
⎜
⎝
⎛
−
⎟
⎠
⎞
⎜
⎝
⎛
= ∑ ∑
+
−=
+
−=
−
2
2
2
2
22
1
),(),(
),(),(2
tan
2
1
),(
W
i
W
iu
W
j
W
jv yx
yx
vuGvuG
vuGvuG
jiθ
© Jain, 2004
Orientation Field Estimation AlgorithmOrientation Field Estimation Algorithm
• Local ridge orientation varies slowly in a
neighborhood where no singular points appear
• A low-pass filter can be applied to modify the
local ridge orientation
• To apply low pass filter the orientation image is
converted into a continuous vector field
)),(2sin(),(
)),,(2cos(),(
jiji
andjiji
y
x
θ
θ
=Φ
=Φ
© Jain, 2004
Orientation Field Estimation AlgorithmOrientation Field Estimation Algorithm
• Apply a 2-D low pass filter as follows
where is the size of the filter, default is 5 x 5 blocksΦΦ × ww
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
Φ
Φ
⎟
⎠
⎞
⎜
⎝
⎛
= −
),(
),(
tan
2
1
),( '
'
1
ji
ji
jiO
y
x
Local ridge orientation at (i, j) is
© Jain, 2004
Orientation Field ConsistencyOrientation Field Consistency
• Consistency (actually inconsistency) level of the
orientation field in the local neighborhood is
If C (i, j) is greater than Tc, re-estimate the local orientations
in this block at a lower resolution level, until C (i, j) is less
than Tc
© Jain, 2004
Fingerprint Region LocalizationFingerprint Region Localization
• Separation of the fingerprint area from the
background
• In the fingerprint area, the variance is very high
in a direction orthogonal to the ridge orientation
• In the background regions, the variance has no
directional dependence
• Local variance of gray level can be used to locate
the fingerprint area
• Assumption: Only one fingerprint is present in
the image
© Jain, 2004
Fingerprint LocationFingerprint Location
Certainty level is defined as
,
),(
),(),(1
),( 2
22
2 ⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛ +
⎟
⎠
⎞
⎜
⎝
⎛
=
jiG
jiGjiG
W
ji
e
yx
ε
( ).),(),(),(
2
2
2
2
22
∑ ∑
+
−=
+
−=
+=
w
i
W
iu
W
j
W
jv
yxe vuGvuGjiG
For a block, if the certainty level is below a threshold Tk,
then all pixels in that block are marked as background
© Jain, 2004
Ridge ExtractionRidge Extraction
• Ridges and furrows run parallel to one another
forming 2-D sine wave
• Gray-level values on the ridges attain their local
maxima along a direction that is orthogonal to
the local orientation
• The fingerprint image is convolved with two
masks ht (i, j; u, v) and hb (i, j ; u, v) that are
180º out of phase
© Jain, 2004
Ridge Extraction FilterRidge Extraction Filter
© Jain, 2004
Ridge ExtractionRidge Extraction
• On average, L x H is 11 x 7. Ideally the mask width
must be equal to the width of the local ridge
• Pixel (i, j) is labeled as ridge pixel if both the graylevel
values of the pixel (i, j) of the convolved
images are greater than Tridge
• The masks also do some smoothing, determined
the parameter δ
• For computational efficiency, δ is made large
enough to make the filter coefficient degenerate to
a single value
© Jain, 2004
Removing Holes and SpecklesRemoving Holes and Speckles
• The binary ridge map has many holes and
speckles due to noise, smudges, breaks, etc.
• Connected component algorithm is used to
remove holes and speckles
• Remove the connected components having
less than 50 pixels
• Thinning is applied to obtain 8-connected
thinned ridges of one pixel width
© Jain, 2004
Minutiae DetectionMinutiae Detection
• Spikes and breaks in the thinned ridge map
leads to detection of spurious minutiae
• Heuristics are applied to post-process the
thinned ridge map
• If the angle between the branch and the trunk is
greater than 70º and less than 110º, then the
branch is removed
• If the break in the ridges is less than 15 pixels
and no other pixel passes through it, then the
break is connected
© Jain, 2004
Minutiae DetectionMinutiae Detection
© Jain, 2004
Minutiae Type DetectionMinutiae Type Detection
• A ridge pixel is a ridge ending, if the number of
ridge pixels in the 8-neighborhood is 1
• A ridge pixel is a ridge bifurcation, if the number
of ridge pixels in the 8-neighborhood is greater
than or equal to 3
• A ridge pixel is a intermediate ridge pixel, if the
number of ridge pixels in the 8-neighborhood is 2
• [x, y, θ, associated ridge] are stored for each
minutia
© Jain, 2004
Minutiae Point Pattern MatchingMinutiae Point Pattern Matching
© Jain, 2004
Minutiae MatchingMinutiae Matching
• Point pattern matching problem
• Let ( ) ( ){ }P
M
P
M
P
M
PPP
yxyxP θθ ,,,...,,, 111=
be the set of M minutiae in the template image
• Let ( ) ( ){ }Q
N
Q
N
Q
N
QQQ
yxyxQ θθ ,,,...,,, 111=
be the set of N minutiae in the input image
• Find the number of corresponding minutia pairs
between P and Q and compare it against a
threshold
© Jain, 2004
Stages in Minutiae MatchingStages in Minutiae Matching
• Alignment
– Estimate rotation, translation, and distortion
– Input fingerprint is aligned with the template
• Matching
– Compute the similarity between the pre-aligned
input and the template using the number of
matching minutiae
© Jain, 2004
Minutiae MatchingMinutiae Matching
Generate Alignment
Hypothesis
Find Similarity Using
String Matching
Template Matching score
Input
© Jain, 2004
Alignment of point patternsAlignment of point patterns
• Corresponding point pairs are not known
• Due to noise and deformations, the input
minutiae cannot be aligned exactly with
respect to the template minutiae
• Ridges corresponding to the minutia are
aligned
© Jain, 2004
Alignment of Input and Template
Ridges
Alignment of Input and Template
Ridges
© Jain, 2004
Alignment AlgorithmAlignment Algorithm
• Ridges are represented as 1-D discrete signals,
normalized wrt the inter-ridge distance
• Let Rd and RD be the set of ridges in the input
and template images
• Each ridge d є Rd is matched with D є RD as
L is the minimal length of the two ridges, di and Di
represent the distances from point i to the x-axis
© Jain, 2004
Alignment AlgorithmAlignment Algorithm
• If S is greater than a threshold (0.8), go to the
next step. Otherwise continue to match the next
pair of ridges
• Compute the translation vector and rotation
angle as follows:
γi, and Γi are the radial angles of the ith point
with respect to the reference minutia
© Jain, 2004
Alignment AlgorithmAlignment Algorithm
• Let (xd, yd, θd)T be the reference minutia (based
on which the transformation parameters are
estimated). The N input minutiae are
transformed as follows:
© Jain, 2004
Matching AlgorithmMatching Algorithm
• Estimate the rotation and translation parameters
and align the two minutiae patterns
• Convert the template and input patterns into the
polar coordinate system with respect to the
reference minutiae and represent them as strings
by concatenating each minutia in an increasing
order of radial angles
( ) ( ){ }P
M
P
M
P
M
PPP
p ererP θθ ,,,...,,, 111=
( ) ( ){ }Q
N
Q
N
Q
N
QQQ
p ererQ θθ ,,,...,,, 111=
© Jain, 2004
String FormationString Formation
© Jain, 2004
String Matching
• Match the strings Pp and Qp with a modified
dynamic programming algorithm to find the edit
distance
• Edit distance must have the elastic property of
string matching
• Edit distance is defined recursively as follows:
© Jain, 2004
© Jain, 2004
String MatchingString Matching
• α, β, and γ are the weights associated with radius,
radial angle, and orientation components
• δ, ε, and ρ specify the bounding box
• Ω is the pre-specified penalty for mismatch
• This scheme can tolerate non-linear deformations
and inexact transformations to some extent, but
cannot compensate for it
• An adaptive bounding box can be used
© Jain, 2004
Bounding Box AdjustmentBounding Box Adjustment
© Jain, 2004
© Jain, 2004
String MatchingString Matching
• δl(m,n), δh(m,n), εl(m,n), and εh(m,n)
specify the adaptive bounding box; initial
values depend on the resolution of the
fingerprint image
• η is the learning rate
• Parameter values are determined
empirically
© Jain, 2004
Minutiae CorrespondencesMinutiae Correspondences
© Jain, 2004
Matching ScoreMatching Score
• The edit distance is used to establish the
correspondence of the minutiae between Pp
and Qp
• Total number of corresponding minutiae is
computed as MPQ
• The matching score is
MN
MM
S
PQPQ100
=
© Jain, 2004
Minutiae Matching ResultMinutiae Matching Result
(a) (c)
(b) (d)
© Jain, 2004
2-D Dynamic Programming based
Minutiae Matching
2-D Dynamic Programming based
Minutiae Matching
Matching Stage
Alignment Stage
Maximize L
Template Minutiae
T = {t1, .., tm}
Query Minutiae
Q = {q1, .., qn}
For each selected
minutiae pair (ti, qj),
compute ∆x, ∆y, ∆θ
1-D elastic
string matching
based on ti, qj,
∆x, ∆y, ∆θ
2-D dynamic
programming based
matching using
(ti, qj, ,∆x, ∆y, ∆θ )Lmax
(ti, qj, ∆x, ∆y, ∆θ)Lmax
maxL′
Minutiae Pairing
S1(R(ti),R(qj)) > 1δ
S2(O(T),O(Q),∆x,
∆y, ∆θ ) > 2δ
Score / (S2,L’max)
Find an alignment that maximizes the
number of minutiae correspondences
S1 → Ridge similarity measure, S2 → Orientation similarity measure,
R(t) → 1-D representation of ridge points of minutia t, O(T) → Orientation field
Matching time ~0.1 sec.
© Jain, 2004
Matching Score DistributionsMatching Score Distributions
• Performance depends on the database. FVC2002 Database
1 (100 users, 8 impressions/user)
• For FAR = 0.1% (1 in 1000), GAR = 97.1%
• EER = 1.65%; at 0% False Accept, FRR = 4%
Matching Score Distribution ROC Curve
© Jain, 2004
Analysis of ErrorsAnalysis of Errors
• Minutiae Extraction
– Extraction stage does not extract all minutiae and their ridges
– There may be no corresponding minutiae having ridge points
for finding the correct alignment
• Alignment
– Corresponding minutiae with ridge points exist
– Alignment step fails due to small number of correspondences
• Matching
– Estimated alignment is correct
– But, the matching score is low because the number of
correspondences is low compared to the number of minutiae
– Reasons: deformation, spurious and missing minutiae
© Jain, 2004
Minutiae Extraction FailureMinutiae Extraction Failure
A
B
True Minutiae Matches: A1→B3, A18→B9, A19→B7
A1, B9 and B7 were detected, but the associated ridges
were not detected because they are close to the boundary
© Jain, 2004
Alignment FailureAlignment Failure
BA
True Minutiae Matches: A7→B9, A8→B8, A4→B1
A7→B9 and A8→B8 pairs have ridge points; however, there
exists a false alignment that results in more than three matches
© Jain, 2004
Matching FailureMatching Failure
BA
No. of matching minutiae identified by the matcher = 10
No. of minutiae in A = 38; No. of minutiae in B = 34
Spurious minutiae and large deformation leads to small score