Fingerprint Recognition

Anil K. Jain
Michigan State University jain@[Link] [Link]

Outline
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

Fingerprints

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 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 Fingerprints

Fingerprint on Palestinian lamp (400 A.D.)

Bewicks trademark (1809)

A Chinese deed of sale (1839) signed with a fingerprint

Jain, 2004

History 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 Matching
Find the similarity between two fingerprints

Fingerprints from the same finger

Fingerprints from two different fingers

Jain, 2004

Fingerprint Classification
Assign fingerprints into one of pre-specified types

Plain Arch

Tented Arch

Right Loop

Left Loop

Accidental

Pocket Whorl

Plain Whorl

Double Loop

Jain, 2004

 Jain, 2004

Fingerprint Sensors
Optical, capacitive, ultrasound, pressure, thermal, electric field

Jain, 2004

Types 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

Terminology
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 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 Representation

Jain, 2004

Challenges 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

Fake fingerprint

Non-universality of fingerprint

Jain, 2004

Fingerprint Matching Techniques

Minutiae-based Correlation-based Ridge Feature-based

Jain, 2004

Minutiae-based Fingerprint Verification System

Jain, 2004

Steps in Minutiae Extraction

Orientation field estimation Fingerprint area location Ridge extraction Thinning Minutia extraction

Jain, 2004

Minutiae Extraction Algorithm

Jain, 2004

Minutiae Extraction Algorithm

Input Image

Orientation Estimation

Ridge Filter

Minutiae Extraction

Post-processing

Ridge Thinning Minutiae Detection

Jain, 2004

Orientation 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 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
i +W j +W 2 2G (u, v)G (u, v) 2 1 y (i, j) = tan1 2 x 2 W Gx (u, v) Gy (u, v) W 2 u=i v= j 2 2

Jain, 2004

Orientation 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

x (i, j ) = cos(2 (i, j )), and y (i, j ) = sin( 2 (i, j ))

Jain, 2004

Orientation Field Estimation Algorithm

Apply a 2-D low pass filter as follows

where w w is the size of the filter, default is 5 x 5 blocks

' 1 1 x (i, j ) Local ridge orientation at (i, j) is O(i, j ) = tan ' (i, j ) 2 y

Jain, 2004

Orientation 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 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 Location
Certainty level is defined as
2 2 1 Gx (i, j) + Gy (i, j) , (i, j) = 2 2 Ge (i, j) W

i+

Ge (i, j ) =

(G (u, v ) + G (u, v)).

2 x 2 y W W v= j 2 2

w 2

j+

W 2

u =i

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 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 Filter

Jain, 2004

Ridge 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 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 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 Detection

Jain, 2004

Minutiae 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 Matching

Jain, 2004

Minutiae Matching
Point pattern matching problem
P P P Let P = x1P , y1P ,1P ,..., xM , y M , M

{(

) (

)}

be the set of M minutiae in the template image

Q Q Q Q Q Let Q = x1 , y1 ,1Q ,..., xN , yN , N

{(

) (

)}

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 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 Matching

Template

Generate Alignment Hypothesis

Find Similarity Using String Matching

Matching score

Input

Jain, 2004

Alignment 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

Jain, 2004

Alignment 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 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 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 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 P P Pp = r1P , e1P ,1P ,..., rM , eM ,M

{(

) (

)}

Q Q Q Qp = r1Q , e1Q ,1Q ,..., rN , eN , N

{(

) (

)}
Jain, 2004

String 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 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 Adjustment

Jain, 2004

 Jain, 2004

String 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 Correspondences

Jain, 2004

Matching 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
S= 100 M PQ M PQ MN

Jain, 2004

Minutiae Matching Result

(a)

(c)

(b)

(d)
Jain, 2004

2-D Dynamic Programming based Minutiae Matching

Template Minutiae T = {t1, .., tm} Maximize L Minutiae Pairing S1(R(ti),R(qj)) > 1 For each selected minutiae pair (ti, qj), compute x, y, 1-D elastic string matching based on ti, qj, x, y, Matching Stage S2(O(T),O(Q),x, y, ) > 2

(ti, qj, x, y, )Lmax

Query Minutiae Q = {q1, .., qn} Alignment Stage

2-D dynamic programming based matching using (ti, qj, ,x, y, )Lmax

Find an alignment that maximizes the number of minutiae correspondences

Lmax
Score / (S2,Lmax)

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 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 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 Failure

True Minutiae Matches: A1B3, A18B9, A19B7 A1, B9 and B7 were detected, but the associated ridges were not detected because they are close to the boundary
Jain, 2004

Alignment Failure

True Minutiae Matches: A7B9, A8B8, A4B1 A7B9 and A8B8 pairs have ridge points; however, there exists a false alignment that results in more than three matches
Jain, 2004

Matching Failure

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
Jain, 2004