Java程序辅导

1Fingerprint Identification
By: Travis R. Gault
Overview
 Introduction
 Features of interest
 Feature Encoding
 Implementations in Industry
 Conclusions
 Lab Overview
 Steps for Classroom Implementation
 References
Introduction
Fingerprints have been used for centuries for 
identification purposes
Much like irises, each fingerprint is unique to 
individuals
Even identical twins have different 
fingerprints
2Introduction
 There are three fundamental principles of 
fingerprints [3].
1. A fingerprint is an individual characteristic and no 
two fingers have identical ridge characteristics
2. A fingerprint will remain unchanged during an 
individual’s lifetime.
3. Fingerprints have general ridge patterns, making 
it possible to systematically classify them.
Features of Interest
 Global Features - are the characteristics that any 
human can see with the naked eye
 Basic Ridge Patterns
 Pattern Area
 Delta
 Type Lines
 Ridge Count
 Local Features - or “Minutia Points” are the unique 
characteristics of fingerprint ridges that are used for 
positive identification.
 It’s possible to have the same global features, but 
the local features remain unique.
Features of Interest
 Pattern Area - is the part of the fingerprint that 
contains all the global features.  However, some 
local features may be found outside the pattern 
area.  
Images taken from [1].
3Features of Interest
 Core Point - is the approximate center of the 
fingerprint, and is used as the reference point for 
reading/classifying the print.
 More specifically it is defined as the topmost point on 
the innermost upwardly curving ridgeline
 The figure below, taken from [2], shows some 
fingerprints and their core point locations
Features of Interest
Type Lines - are the two innermost ridges 
that start parallel, diverge, and tend to 
surround the pattern area.
Type 
Lines
Features of Interest
Delta - is the point on the first bifurcation, 
abrupt ending ridge, meeting of two 
ridges, dot, fragmentary ridge, or any 
point on a ridge at or nearest the center of 
divergence of two type lines, located at or 
directly in front of their point of 
divergence.
4Features of Interest
Ridge Count - is the number of ridges 
between the delta and the core.  
This is done by drawing an imaginary line 
from the Delta to the Core and each ridge 
that touches this line is counted.
Features of Interest
In the figure below, taken from [4], the circle 
is the core, the triangle is the delta, the 
square is a minutiae-ridge ending and the 
diamond is a minutiae-ridge bifurcation.  The 
orange line is the ridge count line.
Features of Interest
 Local Features
 Ridge Ending - ridge ends
 Ridge Bifurcation - divides into 
branches
 Ridge Divergence - diverging of two 
parallel lines
 Dot or Island - small ridge
 Enclosure - divides and reunites
 Short Ridge - like a dot/island, but 
larger
 Image taken from [5].
5Features of Interest
Basic Ridge Patterns
Loop - is the most common (~65% of all prints)
Arch - more open curve than a loop
Whorl - ridge that makes a complete circle (~30% 
of all prints)
Feature Encoding
 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)
 Taken from [5].
Feature Encoding
 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.
 From a software perspective, the minutia are also used to 
align the images for database comparisons.
6Feature Encoding
 Image Based Matching Using Optical Correlation
 Advantages
 Image itself is used as the template
 Requires only low resolution images
 Fast 
 Disadvantages
 Image itself is used as the template
 Requires accurate alignment of the two prints
 Not robust to changes in scale, orientation and position
 Taken from [5]
Feature Encoding
 Texture Based Matching
 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 
 Disadvantages
 Requires accurate alignment of the two prints
 Varies with translation, orientation and non-
linear distortion
 Less accurate than minutiae based matchers
 Taken from [5]
Feature Encoding
 Minutiae Based Matching
 Advantages
 Invariant to translation, rotation and scale changes
 Very accurate
 Disadvantages
 Error prone in low quality images
 Not robust to non-linear distortion
 Does not use visual and textural cues
 Taken from [5].
7Feature Encoding
In simple terms, we’re 
looking for areas where 
ridges stop or intersect 
another ridge.
This data is stored and used 
for comparisons to other 
templates
Image taken from [5].
Implementations
 Binarization Approach
 Used by:
 MINDTCT fingerprint minutiae detection system
 NIST uses this in a lot of implementations
 NBIS - NIST Biometric Image Software
 Done directionally or with template matching to detect minutiae
 Adaptive Flow Orientation Technique
 Binarization is done by peak detection
 But this leads to false positive in areas of poor contrast
 Direct Gray Scale Ridge Following 
 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
 Modified from [5].
Implementations
Images taken from [5].
Binarization Thinning Minutia DetectionAcquisition
8Implementations
The biometrics lab 
setup uses the 
Binarization approach.
Additionally, a variety 
of software is freely 
available on the web 
for C++, C#, Java, and 
VB implementations.
Implementations
How successful is Fingerprint Matching?
Typical False Rejection Rates range between  
0.03%-1.4% [1,6]
Typical False Acceptance Rates are around 
0.01%-0.001% [1,6].
These rates depend on the manufacturer and 
the algorithm used
Comparatively, iris FRR is about 0.001% and 
FAR is about 1 in billions (basically 0).
Conclusions
 Fingerprinting is still a viable means for biometric 
identification, especially in law enforcement, where 
fingerprints may be left behind.
 Fingerprints also offer a cheaper solution for day-to-
day activities than iris recognition
 Fingerprints are not as good for high-security 
implementation
 More work needs to be done to develop better 
methods to compensate for the variations in 
fingerprint recording when identifying local features
9Lab Overview
 Each classmate will submit their right thumbprint 
twice
 One set of thumbprints will serve as a gallery
 One set of thumbprints will serve as a test gallery, along 
with two additional random prints
 Students will use MATLAB and code examples 
provided to encode fingerprint minutiae
 Students will test each print from the test gallery and 
shall report on the FAR and FRR.
 Students must also include technical documentation 
as well as a small research segment into the field of 
fingerprint analysis.
Lab Overview
This lab will be officially distributed on Tues., 
Nov. 12, and will be due no later than Noon 
in the CVIP Lab on Dec. 8.
Students must submit all code and supporting 
files with the report.
Students must arrange to demo their work.
Steps for Implemetation
6 Steps:
Preprocessing
Binarization
Thinning
Minutiae identification
Minutiae alignment
Database comparisons
10
Preprocessing
 Unless you have a very high quality fingerprint 
reader, you’ll need to enhance the image after 
cropping
 There are two goals:
 Increase the contrast in the image
 Bridge empty spots in ridges
 Techniques
 Histogram equalization  (histeq)
 Gamma correction
 Gabor Filter (gaborfilter)
Download from:  
http://www.mathworks.com/matlabcentral/fileexchange/5237
Histogram Equalization
 The histogram equalization 
technique is used to improve 
global image contrast.
 However, the disadvantage 
is that it may have the 
incorrect effect by increasing 
background noise while 
decreasing the signal of 
interest.
 The implementation of this 
will depend on the images 
rendered by your input 
device.
Gabor Filter
 “The Gabor filter is 
basically a Gaussian (with 
variances Sx and Sy along x 
and y-axes respectively) 
modulated by a complex 
sinusoid (with center 
frequencies U and V along 
x and y-axes respectively).”
[9]
 This will help bridge the 
empty spots along ridges.
11
Binarization
 Next, convert the 8-bit 
grayscale images 
to 1-bit images
 Select a window block 
size (say 32x32)
 Find the average of the 
values in the block
 Set values greater than 
the average equal 1, 
else 0
Thinning
 Next, we must convert the 
binary image to a set of lines.  
 This process is called thinning.
 MATLAB’s morphological toolbox 
facilitates this
 bwmorph( bin_img, ‘thin’, ‘inf’)
Minutiae Detection
 We are primarily interested 
in two types of minutia
 Termination Points – where 
a ridge ends
 Bifurcation Points – where a 
ridge splits
 Now, consider a 3x3 window 
in the thinned image (see 
right).  We are interested in 
figures that look like the top 
row or rotated versions.
 We are not interested in 
images like the bottom row
101
010
010
Bifurcation
000
010
010
Termination
001
001
010
Not Interested
001
000
101
Not Interested
12
Minutiae Detection
 How do you tell the 
difference between 
valid and invalid 
windows?
Windows with the center 
value set equal to 0 are 
of no interest to us.
001
001
010
Not Interested
001
000
101
Not Interested
Minutiae Detection
 How do you distinguish 
between bifurcation and 
termination points?
 Sum the entries and 
subtract 1.
 If the answer is 3, then 
it’s a bifurcation point,
 If the answer is 1, then 
it’s a termination point
101
010
010
Bifurcation
000
010
010
Termination
001
010
010
Not Interested
000
010
000
Not Interested
Minutiae Detection
 This is an example 
of detecting the 
termination points 
from a thinned 
image taken with 
the lab’s finger print 
reader.
 Done using MATLAB
13
Minutiae Detection
 This is an example 
of detecting the 
bifurcation points 
from a thinned 
image taken with 
the lab’s finger print 
reader.
 Done using MATLAB
Minutiae Detection
 This is a composite 
of both the 
bifurcation and 
termination points 
along with the 
original thinned 
image.
Minutiae Detection
 After identifying the minutiae as on the previous 
slides, there are a lot of spurious minutiae that need 
to be removed
 This can be done removing minutiae that occur with 
an arbitrary Euclidian distance from one another.
We need to check the following points’ distances:
 Termination-Termination
 Termination-Bifurcation (and vice versa)
 Bifurcation-Bifurcation
 Coordinates separated by a smaller distance than 
specified shall be removed
14
Minutiae Detection
Next Time
On Tuesday:
ROI selection
Minutiae Orientation/Alignment
Gallery comparison
Fingerprint project distributed
Fingerprint acquisition (CVIP Lab)
ROI Selection
 The ROI selection is determined using MATLAB’s morpho-
logical toolbox by running the thinned image is  through 
imclose(), imerode() and imfill().
 The results are shown below.
15
ROI Selection
 The next step is to mask out coordinates outside the ROI.  
Graphically, the results are shown below.
Termination Orientation
 Consider a 5x5 square 
centered about a 
termination point.
We know the angle of 
each border point w.r.t. 
the center point.
When the termination 
point intersects the 
border, we then know a 
rough estimate of the 
angle.
-135
-150
180
150
135
-45-60-90-120
-30
0X
30
456090120
Termination Orientation
 Example
 Let the red blocks 
represent a termination 
ridge
 From this, we determine 
the angle to be 120 
degrees
-135
-150
180
150
135
-45-60-90-120
-30
0X
30
456090120
16
Termination Orientation
 Example
 Let the red blocks represent 
a termination ridge
 From this, we have two 
possible angles:  120 or 135 
degrees.
 We must choose which to 
use.
 In my code, I use the angle 
representing the smallest 
distance from the center.  
In this case 135.
-135
-150
180
150
135
-45-60-90-120
-30
0X
30
456090120
Termination Orientation
 Example
 Let the red blocks 
represent a termination 
ridge
 From this, we have no 
possible angles, which 
indicates noise.
 In this case, we remove 
the point from the list of 
termination minutia. -135
-150
180
150
135
-45-60-90-120
-30
0X
30
456090120
Bifurcation Orientation
 Example
 Let the red blocks represent 
a bifurcation ridge and an 
unknown ridge.
 We must determine all three 
angles, and exclude the 
angles from the unknown 
ridge.
 To do this, apply bwlabel().  
One region will be labeled 
with 1’s, the other with 2’s.
 Select the correct region 
that by choosing the label 
assigned to X
-135
-150
180
150
135
-45-60-90-120
-30
0X
30
456090120
17
Bifurcation Orientation
 Example
 Remove X and apply 
bwlabel() again.  In the 
second figure, red = 1, 
green = 2, blue = 3
 Perform a similar 
operation to determine 
the three angles by 
analyzing each label 
(1,2,3).
 Handle multiple angles 
for each label as with 
termination points or 
similarly
-135
-150
180
150
135
-45-60-90-120
-30
0X
30
456090120
-135
-150
180
150
135
-45-60-90-120
-30
0X
30
456090120
Orientation Results
 The results of finding 
the termination and 
bifurcation points is on 
the right.
Gallery Comparisons
 General Steps
 1. Select any one minutia from image A and B.  This will 
serve as the origin in each image.
 2. Use the orientation and location information from the 
minutia in image A to transform all minutia in image B, 
about it’s origin.
 3. Perform a similarity comparison between the minutia in A 
to the transformed minutia in B.
There are a large variety of algorithms and types available
You will investigate and select algorithm to use in the project
 4. Repeat for all minutia in B.
 5. Select a new image A to compare against B if the 
similarity score is insufficient.
18
Gallery Comparisons
 Graphically, this is what 
we are doing w.r.t. 
rotating the 
coordinates.
 Image taken from [8]. 
θ
D
E F
D
E
F
X-axis
Y-axis
X'-axis
Y'-axis
y
x
References
1. “DigitalPersonaTM White Paper: Guide to Fingerprint Identification.” Voice 
Recognition Systems.  www.talktoyourcomputer.com
2. “Frequently Asked Questions.” SecuGen Biometrics Solutions.  
http://www.secugen.com/support/faqs.htm
3. “Fingerprint Techniques Manual.” New Mexico Department of Health, Division 
of Health Improvement.
4. Liu, L.; Dai, T.; Hsin-Chu.  “Ridge Orientation Estimation and Verification 
Algorithm for Fingerprint Enhancement.” Journal of Universal Knowledge 
Management.  Vol. 12, Issue 10. Pgs. 1426-1438.
5. Chikkerur, S.  “Online Fingerprint Verification.” Center for Unified Biometrics 
and Sensors.  University at Buffalo.
6. “Security Issues.” Affirmative Technologies. 
http://www.affirmativeusa.com/security_issues.htm
7. “FingerPrint Demo.” MathWorks.  
http://www.mathworks.com/matlabcentral/fx_files/16728/1/content/FingerPri
nt/html/fingerprint.html
References
8. Zhili, W.  “Fingerprint Recognition.” Department of Computer Science.  BS 
Thesis.  Hong Kong Baptist University.  
http://www.comp.hkbu.edu.hk/~vincent/resPaper.htm
9. “2D Gabor Filter (Ver 1,2,3).” MathWorks. 
http://www.mathworks.com/matlabcentral/fileexchange/5237
10. Kenner, F.  “FingerPrint Demo”.  Mathworks.  
http://www.mathworks.com/matlabcentral/fx_files/16728/1/content/FingerPri
nt/html/fingerprint.html