Transcript Automatic Fingerprint Verification

ONLINE FINGERPRINT VERIFICATION
Sharat Chikkerur
Center for Unified Biometrics and Sensors
University at Buffalo
www.cubs.buffalo.edu
Advisor: A. N. Cartwright
Committee: V. Govindaraju, A. H. Titus, L. Kondi
Abstract
 Background
 Traditional password/token based authentication schemes are insecure and
are being replaced by biometric authentication mechanisms
 Fingerprints were one of the first biometrics to be widely used
 Despite 40 years of research, fingerprint recognition is still an open problem.
 Challenges
 Feature extraction is very unreliable in poor quality prints
 Matching fingerprints under non linear distortion is difficult
 Contributions
 New fingerprint image enhancement using STFT analysis.
 New feature extraction algorithm based on chain code contours
 New graph based matching algorithm robust to non linear distortion
Outline
 Introduction
 Biometrics
 Fingerprints 101
 Fingerprint Image Enhancement
 Minutia Feature Extraction
 Matching Algorithm
 Conclusion
 Software Demos
Biometrics
 Definition
 Biometrics is the science of verifying and establishing the identity
of an individual through physiological features or behavioral traits
 Examples
 Physical Biometrics
 Fingerprint, Hand Geometry, Face
 Measurement Biometric
 Dependent on environment/interaction
 Behavioral Biometrics
 Handwriting, Signature, Speech, Gait
 Performance/Temporal biometric
 Dependent on state of mind
 Chemical/Biological Biometrics
 Skin spectroscopy
 DNA, blood-glucose
Fingerprints as a Biometric





High Universality
 A majority of the population (>96%) have legible fingerprints
 More than the number of people who possess passports, license and IDs
High Distinctiveness
 Even identical twins have different fingerprints (most biometrics fail)
 Individuality of fingerprints established through empirical evidence
High Permanence
 Fingerprints are formed in the fetal stage and remain structurally
unchanged through out life.
High Performance
 One of the most accurate forms of biometrics available
 Best trade off between convenience and security
High Acceptability
 Fingerprint acquisition is non intrusive. Requires no training.
Fingerprints 101: Fingerprint Classes
• A fingerprint is made up of system of oriented friction ridges
•A fingerprint can be classified based on type the ridge flow pattern
• Classification helps in narrowing down possible matches
• In reality, the class distribution is skewed (>65% are loops)
• Used only in law enforcement applications
Fingerprints 101: Ridge Characteristics
• Fingerprints can be distinguished based on the ridge characteristics
•Ridge characteristics mark local discontinuities in the ridge flow
• No two individuals have the same pattern of ridge characteristics at the same relative locations
Local Features
Global Features
Prior Related Work: Matching Paradigms

Manual
 Human experts use a combination of visual, textural, minutiae cues and
experience for verification
 Still used in the final stages of law enforcement applications

Image based
 Utilizes only visual appearance.
 Requires the complete image to be stored (large template sizes)

Texture based
 Treats the fingerprint as an oriented texture image
 Less accurate than minutiae based matchers since most regions in the
fingerprints carry low textural content

Minutiae based
 Uses the relative position of the minutiae points
 The most popular and accurate approach for verification
 Resembles manual approach very closely.
Image Based Matching: Optical Correlation


Advantages
 Image itself is used as the template
 Requires only low resolution images
 Optical correlation makes it extremely fast (Choudary and Awwal ’99, Lee et
al. 99, Roberge et al. 99, Baze et al.00)
Disadvantages
 Image itself is used as the template (template size about 30 KB)
 Requires accurate alignment of the two prints (unreliable in poor prints)
 Not robust to changes in scale, orientation and position.
Texture Based Matching: Filterbanks

Advantages
 Uses texture information (lost in
optical and minutiae based schemes)
 Performs well with poor quality prints
 Features are statistically independent
from minutiae and can be combined
with minutiae matchers for higher
accuracy (Jain et al. 00, Jain et al 01)

Disadvantages
 Requires accurate alignment of the two
prints (unreliable in poor prints)
 Not invariant to translation, orientation
and non-linear distortion.
 Less Accurate than minutiae based
matchers
Minutiae Based Matching


Advantages
 Invariant to translation, rotation and scale changes
 Very accurate (Ratha et al 96, Jain et al. 97, Jian Yau 00, Bazen and Garez 03)
Disadvantages
 Minutiae extraction is error prone is low quality images
 Not robust to non-linear distortion.
 Does not use visual and textural cues
General Architecture
Outline
 Introduction
 Fingerprint Image Enhancement
 Need for Enhancement
 Prior Related Work
 Proposed Algorithm: STFT Analysis
 Experimental Evaluation
 Minutia Feature Extraction
 Matching Algorithm
 Software Demos
Need for Enhancement
What you see
What you ‘think’ you see
Reality: What you usually get..
High contrast print
Typical dry print
Faint print
Low contrast print
Typical Wet Print
Creases
Challenges


Challenges
 Fingerprint image is non stationary (has dominant local
orientation and frequency)
 General purpose image processing algorithms are not useful
 Traditional operators and filters assume Gaussian noise model
 ‘Noise’ in fingerprint images consists mostly of ridge breaks
Contextual Filters
 Existing techniques are based on ‘contextual’ filtering
 Filter parameters are adapted to each local neighborhood
 Filter parameters in ‘unrecoverable’ regions can be interpolated
based on its neighbors
Prior Related Work: Spatial Filtering
 (Yang et.al 1996, Greenberg et. Al 1999)
proposed local anisotropic filtering
 Filter kernel adapts at each pixel location
 ( x  x0 )  n 2 ( x  x0 ).n 2 
f ( x, x0 )  S  V ( x  x0 ) exp 


2

(
x
)
  2 ( x0 ) 
0




Hong et al, 96/98 proposed the use of Gabor filters for enhancement
Gabor filter has the best joint space-frequency localization
Does not handle high curvature regions well due to block wise approach.
G ( x, y ) 
e
  x  x0 2  y  x0 2 
 


2
 2  i  0 x  0 y 
 
e
2
Even Symmetric Kernel
Fourier spectrum showing the localization
Prior Related Work: Fourier Domain Filtering



Sherlock et al 94, proposed the use of Fourier domain filtering
The image is convolved with a filter bank of directionally selective filters
Image enhanced by selecting a linear combination of filter responses


Watson et al. 94, proposed the use or ‘root filtering’ for enhancement.(Pseudo matched filter)
Does not require the computation of orientation images

I enh ( x, y )  FFT 1 F (u, v) F (u, v)
F (u, v)  FFT I ( x, y )
Root Filtering
Fourier Domain Filtering
k

Traditional Approaches
Gxy    2Gx (u , v)G y (u , v)
uW vW
Gxx    Gx2 (u , v)  G y2 (u , v)
uW vW
Local Orientation
(x,y)
Gradient Method
1
G 
  tan 1  xy 
2
 Gxx 
[Kaas and Witkins 87]
Enhancement
Frequency/Spatial
Local Ridge Spacing
F(x,y)
Projection Based Method
[Ratha et al 95]
Proposed Approach: Overview
Region
Mask
STFT
Analysis
Frequency
Image
Orientation
Image
Coherence
Image
Fourier domain
Enhancement
STFT Analysis


Fingerprint image is non stationary, so we require both space and frequency
resolution: time frequency analysis
STFT in 1D

X ( ,  ) 

STFT in 2D
X ( 1 , 2 , 1 , 2 ) 

 jt
x
(
t
)
w
(
t


)
e
dt


 

 j (1 x  2 y )

I
(
x
,
y
)
w
(
x


,
y


)
e
dxdy
1
2

  
Surface Wave Model
Fingerprint ridges can be modeled as an oriented wave
i ( x, y )  A cos 2f x cos( )  y sin(  )
( x, y ) 
Local ridge orientation
f ( x, y ) 
Local ridge frequency
Surface wave
Local Neighborhoods
Validity of the model

Parameter Estimation



Paradigm: The Fourier domain response can be viewed as a distribution of
surface waves. Each term F(r, θ) corresponds to a surface wave of frequency
1/r and orientation θ
We seek to find the most likely surface wave and hence estimate the dominant
direction and frequency
We can represent the Fourier spectrum in polar form as F(r,θ) The power
spectrum is reduced to a joint probability density function using
p(r , ) 
F (r , )
  F (r , )
2
2
ddr
r

The angular and frequency densities are given by marginal density functions
p( )   f (r , )dr
r
p(r )   f (r ,  )d

Ridge Orientation Image
 sin( 2 )  p( )d 


1 1  

{ }  tan
2
  cos( 2 )  p( )d 




1 1  sin 2O( x, y )  W ( x, y ) 

O' ( x, y )  tan 
2
 cos2O( x, y )  W ( x, y ) 
Region Mask


2

E  log  F (r , ) drd 




The surface wave approximation does not hold in the background region
The region mask is obtained by simple thresholding of the block energy image
Frequency Image
x 1
{r}   r  p(r )dr
r
F ' ( x, y ) 
y 1
  F (u, v)W (u, v) I (u, v)
u  x 1 v  y 1
y 1
x 1
  W (u, v) I (u, v)
u  x 1 v  y 1
[Jain et al 00]
Coherence Image
•
•
•
•
Block processing is unreliable in regions of high curvature
Sherlock and Monro 94, relax filter parameters near the singular locations
Estimation of singular point is difficult in poor images!
We use an angular coherence measure proposed by Rao and Jain 90
C ( x0 , y0 ) 
 cos(O( x, y))  cos(O( x , y ))
0
( i , j )W
W W
0
Enhancement
H (r ,  )  H r (r )  H  ( )
H r (r ) 
(rrBW ) 2 n
2
(rrBW ) 2 n  (r 2  rc ) 2 n
 2  (  C )
if   c  BW
cos
H  ( )  
2BW

0
otherwise

rBW : radial bandwidth ,  BW : angular bandwidth,
c  E{} : mean orientatio n, rc  E{r} : mean frequency [Sherlock et. al, 1994]
Additional Enhancement Results
Qualitative Comparison
Original Image
Root Filtering
Qualitative Comparison(cont.)
Gabor Filter based Enhancement
Proposed Approach
Objective Evaluation
• We evaluated the effect of enhancement on 800 images from FVC2002 DB3
• The evaluation consists of 2800 genuine test and 4950 impostor tests
• It can be seen that the matcher performance improves with enhancement
Outline
 Introduction
 Fingerprint Image Enhancement
 Minutia Feature Extraction
 Prior Related Work
 Chain code contour
 Experimental Evaluation
 Matching Algorithm
 Conclusion
 Software Demos
Background




Minutiae represent local
discontinuities in ridge flow
Minutiae features are the most
widely used fingerprint
representation
There are several standards such
as CBEFF (file format) and ANSINIST (interchange format)
standards for minutiae based
fingerprint representation
Minutiae extraction approaches may be broadly categorized into
 Binarization based approaches
 Direct gray scale extraction
Prior Related Work

Binarization Approaches
MINDTCT,NIST NFIS, (Garris et. Al, 02)


Directionally adaptive binarization
Template matching is used to detect minutiae


Binarization is performed by peak detection
Peak detection leads to false positives in regions of poor ridge constrast.




Based on ridge pursuit
Has low computational complexity.
Cannot handle poor contrast prints and images with poor ridge structure.
Relies on a good orientation map for ridge pursuit
Adaptive Flow Orientation technique (Ratha et. al., 95)

Direct Gray Scale Ridge Following
Ridge Following (Maio and Maltoni 97, Jiang and Yau 01)
Binarization Method
Acquisition
Binarization
Thinning
Minutia Detection
Proposed Approach: Chain Code Contours




Provides a lossless description of the contour and also gives direction and curvature
information.
Translation and rotation invariant
Used in computer vision for encoding object boundaries
Used for character recognition (Madhavanth et. al 99)
Minutiae Detection using Chain Codes



Minutiae are encountered as points of ‘significant’ turn on the contour


Left turn: Ridge ending
Right turn : sign PIN  POUT  0
Right turn: Bifurcation
Left turn

: sign P
IN

 POUT

 0
Determining Turn Points


P P
cos( )  IN  OUT
PIN POUT
Significan t turn :   Th


  PIN  POUT
P
2
P 
  tan 1  Y 
 PX 
Results
Results (cont.)
Experimental Evaluation


Test Data
 150 prints from FVC2002(DB1)
were randomly selected for
evaluation.
 Ground truth was established using
a semi automated truthing tool.
 Results compared using NIST NFIS
open source software.
Metrics
 Proposed by Sherlock et. Al 94
 Sensitivity: Ability of the algorithm
to detect true minutiae
 Specificity : Ability of the algorithm
to avoid false positives
 Flipped : Minutiae whose type has
been exchanged
FN
FP
E
, Specificit y  1 
, Flipped 
N
N
N
FN : False Negatives, FP : False positives, E : Exchanged, N : Ground Truth
Sensitivity  1 
Quantitative Analysis : Results

Examples
File Name
NIST
Proposed method
Actual
TP
FP
M
F
TP
FP
M
F
10_8.tif
18
16
8
2
1
17
0
1
1
11_6.tif
50
40
4
10
2
41
4
9
4
12_8.tif
29
22
5
7
3
22
3
7
1
13_6.tif
35
28
10
7
4
28
10
7
2
14_6.tif
44
34
12
10
6
37
13
7
5
15_7.tif
38
37
7
1
5
37
3
1
0
16_7.tif
41
35
12
6
5
36
8
5
8
17_6.tif
43
35
16
8
11
36
7
8
11
18_8.tif
34
31
7
3
4
32
6
2
1
19_7.tif
35
26
8
9
3
31
6
4
5
Results
Summary results
 Count TP(NIST) > proposed : 40 of 150
 Count E(NIST) < proposed : 40 of 150
Sensitivity distribution
Metric
NIST
Proposed
Sensitivity(%)
82.8
83.5
Specificity(%)
77.2
76.8
Flipped(%)
12.0
10.9
Overall statistics
Outline
Introduction
Fingerprint Image Enhancement
Minutia Feature Extraction
Matching Algorithm
 Prior Related Work
 New Representation: K-plet
 Local Matching: Dynamic Programming
 Consolidation: Coupled BFS
 Experimental Evaluation
 Conclusion
 Software Demos




Minutiae Based Matching

Challenges
 Minutiae extraction is error prone is low quality images
 Not robust to non-linear distortion.
 Intra-user variation
Challenges: Non-linear Distortion
Challenges: Quality and Intra-user variance
Variation in quality
Intra-user variation
Prior Related Work :Global Matching

Global Matching
 Point correspondences not known : combinatorial problem
Relaxation approach (Ranade and Rosenfield 93)
 Likelihood of each match is either decreased or increased at each
iteration based on compatibility of rest of the points
 Iterative approach makes it too slow to be practical
Generalized Hough Transform (Ratha et al. 96)
 All possible transformation represented as a quantized search space
 Searches for the most optimal transform in the search space
 Very fast
Ridge Alignment (Jain et al. 97)
 Performs explicit alignment before matching
 Each minutiae is associated with its ridge (represented by a curve)
 The alignment is based on ridge correspondence
 Global matching is then performed using string edit distance
Prior Related Work: Local Matching
N0
i 0
ri 0
i
Mi
i1




ri1
N1
(Jiang and Yau 00)
 11 dimensional local features derived from reference minutiae and two closest neighbors
 Best match is used only for explicit alignment
(Jea and Govindaraju 04)
 5 dimesional features Si (ri0, ri1, φi0, φi1, δi) derived from two closest neighbors
 Alignment is still required
(Ratha et al. 00)
 ‘Star’ representation derived from all minutiae within a particular radius
 Consolidation by checking consistency
(Garris et. al 03: BOZORTH3)
 Line features
 Consolidation by linking consisting matches
Proposed Algorithm



Representation
 K-Plet
 Features invariant to rotation and translation
 Local relationship formally represented by a directed graph
Local Matching
 Posed as a string alignment problem and solved by dynamic programming
 Matches all neighbors simultaneously
Consolidation
 Coupled Breadth First Search
 Breadth first search is used to propagate the matches
 Similar to human verification
 No explicit alignment required at any stage
Neighborhood Representation: K-plet
K-plet
Θ
r
Φ
Local Matching
m1I

mT1
mI2
mT2


r


All local neighbors have to be matched
simultaneously. Greedy approach does
not work when conflicts occur
These can solved by finding the
alignment through optimization process
such as by solving a string alignment
problem
Example of alignment:
 S (acbcdb) – (ac__bcdb)
 T (cadbd) - (_cadb_d_)
Trivial solution requires exponential time
Each match is given a cost. Alignment
solved through recurrence relation


MATCH e C ( d ) Cr dr C d  if within bounds
D[i  1, j  1]   ( s[i], t[ j ])  ( s[i ], t[ j ])  

MISMATCH
otherwise

D[i, j ]  max  D[i  1, j ]   ( s[i ],)
 D[i, j  1]   (, t[ j ])
 ( s[i ],)  0,  (, t[ j ])  0

The ‘Graphical’ View
Graphical Matching: Coupled BFS
Coupled BFS
Graphical Matching: Coupled BFS
Graphical Matching: Coupled BFS
Graphical Matching: Coupled BFS
Important Differences
 Traditional Breadth First Search
 Traversal Defined only over a single graph
 All neighbors are considered for expanding the path
 Coupled Breadth First Search
 Traversal proceeds in two directed graphs simultaneously
 Only ‘matched’ neighbors are considered for expanding
the path
 Constant number of neighbors provides a bound for
the traversal complexity
Experimental Evaluation



800 prints from FVC2002(DB1)
2800 genuine tests,4950 impostor tests
Compared with BOZORTH 3
Error Rates
BOZORTH3: 3.6% EER, 5.0% FMR100
Proposed: 1.5% EER, 1.65% FMR100
Software





CUBS Truthing Tool
CUBS Minutiae Truthing Tool
CUBS Fingerprint Verification Demo
Matlab code for Fingerprint Enhancement
Matlab Toolbox for Fingerprint Verification
 http://www.mathworks.com/matlabcentral
 1179 downloads since 01/30
 637 downloads since 03/22
Conclusion
 Contributions
 New Fingerprint Image Enhancement using STFT Analysis.
 Simultaneously estimates all intrinsic images
 Increases recognition rate of existing matchers
 New Feature Extraction Algorithm using Chain code Contour
 Obviates need for thinning
 Performs favorably with NIST feature extractor
 New Graph based matching algorithm
 Robust to non linear distortion
 Formal technique for propagating local matches
 Performs better than NIST BOZORTH3 matcher over FVC DB1 database
Acknowledgements








Tsai Yang Jea (Alan)
Chaohang Wu
Sergey Tulyakov
Faisal Farooq
Amit Mhatre
Karthik Sridharan
Sankalp Nayak
Rest of the research group at CUBS
Thank You
http://www.cubs.buffalo.edu