INTRODUCTION TO

FINGERPRINT RECOGNITION
인하대학교 정보통신공학부

김 학 일

2001. 2. 23

한국정보과학회 컴퓨터비젼 및 패턴인식 연구회

생 체 인 식 기 술 워 크 샵
 목차
Definitions
Biometric System Description
Fingerprint Recognition
n Minutiae extraction
n Matching
Applications
Prospective
Conclusion
Reference
2001/2/23 Introduction to Fingerprint Recognition 2
 Modern History of Fingerprint
1880년대 이후
n Bertillon system (1880): 프랑스 범죄학자 A. Bertillon의 범죄자 식
별법
n F. Galton의 “Personal ID and Description (1880)”, “Finger Prints
(1892)” : Minutiae 소개, 지문의 불변성(Immutability), 유일성
(Individuality) 주장
n Vucetich (1891 아르헨티나) : 지문의 Uniqueness 주장
n E. R. Henry (1900) : global structure of fingerprints
“Henry System” – Whorl, Right loop, Left loop, Arch, Tented arch
1950년대 이후
n FBI, NBS(미국), 파리 경찰청 중심으로 범죄 수사에 활용
n FBI, NBS에 의해 최초의 AFIS 실용화 (1972)
n NEC, Sagem Morpho, Printrack, Cogent : AFIS 개발

2001/2/23 Introduction to Fingerprint Recognition 3

 Definition of Biometrics
Automatic identification or identity verification of
living, human individuals based on behavioral
and/or physiological characteristics

Verification v. Identification
n One-to-one v. One-to-many
ü Verification can be “one-to-many”, usually “few-to-few”
ü Identification can be “one-to-one”, usually “few-to-
some”
ü Fail to account for the reversal in meaning of “false
accept/reject”

2001/2/23 Introduction to Fingerprint Recognition 4

 Verification (AFAS)
ID

Image Acquisition
Database
Digitized
Fingerprint
Feature Extraction Features of
Template
Features of
Sample
Matching
Measure of
Similarity
Decision YES/NO

2001/2/23 Introduction to Fingerprint Recognition 5

 Identification (AFIS)

Features of Sample
for Classification
Classification
Image Acquisition
Fingerprint
Digitized Class
Fingerprint
Feature Extraction Database
Features of Features of
Sample Templates
Matching
Measure of List of
Similarity Fingerprints and
ID in the order of
similarity
2001/2/23 Introduction to Fingerprint Recognition 6
 Positive Identification

To prove I am who I say I am

Prevent multiple users of a single identity
Matching sample to single stored template
False match allows fraud
False non -match causes inconvenience
Multiple alternatives (PIN, ID, etc)
Can be voluntary

2001/2/23 Introduction to Fingerprint Recognition 7

 Negative Identification

To prove I am not who I say I am not

Prevent multiple identities of a single user
Matching sample to all stored templates
False match causes inconvenience
False non -match allows fraud
No alternatives
Mandatory for all users

2001/2/23 Introduction to Fingerprint Recognition 8

 “Type I” and “Type II” Errors
Type I : rejecting a true hypothesis
Type II : accepting a false hypothesis

ü What is the hypothesis?

ü Always refer to claim of user

2001/2/23 Introduction to Fingerprint Recognition 9

 “False Match” v.
“False Non-Match”
Error rates of the matching algorithm from
a single attempt-template comparison
n Impostor : false match
n Genuine : false non-match

2001/2/23 Introduction to Fingerprint Recognition 10

 “False Acceptance” v.
“False Rejection”
False Rejection
n Positive ID: “failure to acquire” or “false non-
match” after several trials
n Negative ID: “failure to acquire” or “false match”
against enrolled template(s)
False Acceptance
n Negative ID: “failure to acquire” or “false non-
match” after several trials
n Positive ID: “false match” against claimed template
2001/2/23 Introduction to Fingerprint Recognition 11
 Generic Biometric System
DATA SIGNAL
DECISION
COLLECTION PROCESSING

PATTERN
BIOMETRIC DECISION
MATCHING

QUALITY
PRESENTATION
CONTROL

FEATURE
SENSOR
EXTRACTION

TRANSMISSION
STORAGE

COMPRESSION EXPANSION IMAGE STORAGE

TRANSMISSION DATABASE

2001/2/23 Introduction to Fingerprint Recognition 12

 System Description
Data Collection
n Biometric Characteristic
n Presentation
w Acceptability : intrusive or non-intrusive ?
n Sensor
w Accessibility : easy to capture by sensor ?
Transmission
n Compression/Decompression
w Noise and loss

2001/2/23 Introduction to Fingerprint Recognition 13

 System Description
Signal Processing
n Feature extraction
w Robustness : stable, repeatable, time-invariant ?
w Distinctiveness : variation across the population
n Quality control
w Availability : independent measures for each user
n Pattern matching
w Matching and Scoring
w Separability : easy to make a decision ?
w Possibly multiple matcher

2001/2/23 Introduction to Fingerprint Recognition 14

 System Description
Storage Template Sizes (Bytes)

n Image storage Fingerprint 200+

Hand Geometry 9
w Raw data / Sample data (rarely)
Finger Geometry 14
n Database
Iris 512
w Templates / Transaction log
Face 64+
Voice 3k~6k
Decision
n Decision Rules
w Translates scores to decision (reject/accept)
w Thresholding
w “Three strike out”
w Multiple measures
2001/2/23 Introduction to Fingerprint Recognition 15
 Score Distribution
ü Inter-template curve와 Imposter curve는 일치
하지 않는다.

Genuine
mode 1
Imposter
mode 3
Probability Distribution

Genuine
GENUINE Inter-template curve mode 3
Imposter
mode 1
IMPOSTER
Imposter Genuine
mode 2 mode 2

NEAR τ Distance FAR

2001/2/23 Introduction to Fingerprint Recognition 16

 Advantages v. Disadvantages
of Fingerprint
Advantages
n Extremely low false match error rates
n Small and inexpensive sensor size
n Data partitioning through classification
n Some standards
n Forensic acceptability of image
Disadvantages
n Non-intuitive operation
n Fragility of friction ridges
n No interoperability of standards
n Required sensor cleaning
n Forensic acceptability of image

2001/2/23 Introduction to Fingerprint Recognition 17

 Information Level in Fingerprint
Level 1
n Global ridge flow pattern
n Pattern classification
Level 2 Duality of
Minutia
n Local ridge-valley structures
n Minutiae : Ending / Bifurcation
n Singular points : Core / Delta
Level 3
n Pore structures (1000 dpi)

2001/2/23 Introduction to Fingerprint Recognition 18

 Presentation
n Inconsistent without user feedback
n Core presentation preferred
n Rotation
n Plastic skin deformation
n Inconsistent contact
w Dryness / Moisture
n Irreproducible contact
w Skin damage

2001/2/23 Introduction to Fingerprint Recognition 19

 Sensors
n Optical
n Capacitive
n Thermal
n Electrostatic
n Acoustic
Optical

Electrostatic

Hologram
2001/2/23 Introduction to Fingerprint Recognition 20
 No Standard on
Fingerprint Images
Optics
300x300
500dpi

Optics
288x352 Ink-rolled
660dpi 512x480
500dpi

Generated Semiconduct
Optics or
240x320
512x480 128x128
500dpi
480dpi 250dpi
2001/2/23 Introduction to Fingerprint Recognition 21
 Transmission
Compression
n “Wavelet Scalar Quantization(WSQ) Gray-scale
Fingerprint Image Compression Specification”, Criminal
Justice Information Services, FBI, IAFIS-IC-0110v2, Feb
16, 1993.
Transmission Format
n “Data Format for the Interchange of Fingerprint
Information”, ANSI/NIST-CSL-1-1993.
n Include scar, mark, tattoo in 2000 version.
n “Common Biometrics Exchange File Format”, v1.0, Feb
2001.

2001/2/23 Introduction to Fingerprint Recognition 22

 Signal Processing

Optical Correlator
Fourier Transform
Correlation
Minutia extraction & Matching

2001/2/23 Introduction to Fingerprint Recognition 23

 Minutia Extraction

Direction Calculation Singularity Detection Minutiae Detection

Gray level
Binarization Minutiae Healing
Enhancement
Minutiae
List
Segmentation Thinning
Matching Module

Typical process of minutia extraction

2001/2/23 Introduction to Fingerprint Recognition 24

 Modified 2D Gabor Filter
Orientation selective bandpass filter
Product of a Gaussian and a sinusoidal wave
n Sinusoidal wave has a direction and a frequency.
n Gaussian is circular symmetric with a rate of decay.
1  x2 + y2  x cos θ k + y sin θ k
−   j 2π
2  σ 2  λ
G ( x, y ) = e ⋅e
σ 2 : variance of Gaussian

where λ : wavelength of ridge
θ k : orientatio n perpendicu lar to ridge flow

2001/2/23 Introduction to Fingerprint Recognition 25

 Modified 2D Gabor Filter
Requires local ridge spacing and local ridge orientation.
n Ridge spacing determines both λ and σ.
n Ridge orientation θk= tan-1(-kx/ky)
ü Still difficult for low-quality or high-curvature region

2001/2/23 Introduction to Fingerprint Recognition 26

 Direction Calculation
Direction Field v. Direction image

Gabor filter with multiple filter orientations

n Max magnitude of filter output indicates perpendicular to ridge
direction

Least Square Estimation using Gradient

 W W 
 ∑∑ x 2G (i , j )G y (i , j ) 
1  i =1 j =1 
θ o = tan−1  
2 W W
{
 ∑ ∑ G x2 (i , j ) − G 2y (i , j ) 
 i =1 j =1
}


2001/2/23 Introduction to Fingerprint Recognition 27

 Direction Smoothing
ü Direction flow is smooth and continuous except singular points.

2001/2/23 Introduction to Fingerprint Recognition 28

 Gray-level Enhancement

Histogram equalization is not enough.

Simple LP filtering reduces noise as well as blurs ridge
pattern.
Orientation selective filtering
n Non-ridge frequencies are filtered out.

ü Gray-level normalization for quality control

2001/2/23 Introduction to Fingerprint Recognition 29

 Segmentation

Discriminating the fingerprint area from the background

n Background : uniform gray-level without dominant direction
n Fingerprint : large variance in gray-level with direction

Measures
n Variance
n Certainty associated with the direction
n Directional histogram in the block

2001/2/23 Introduction to Fingerprint Recognition 30

 Singularity Detection

Definition of singular points

n Core : topmost point on the innermost upward recurving ridge
n Delta : point of flow-bifurcation
Poincare Index : integral of the rate of change of
orientation on a close contour
n Ordinary points = 0
n Core = ½
n Delta = - ½

ü Arch type do not have any singularity in terms of Poincare

index

2001/2/23 Introduction to Fingerprint Recognition 31

 Binarization (Thresholding) &
Thinning (Skeletonizing)
Global v. Local thresholding
n Histogram of fingerprint image is not bimodal.
n Local thresholding is more adaptive.
w Slit mask perpendicular to ridge direction
w Projection perpendicular to ridge direction
w Zero-crossing of Laplacian operation
Also requires post-processing to remove holes and islands
in the binary image.

Thinning
n Make ridge pixels black, valleys white.
n Reduce ridge width to one pixel.

2001/2/23 Introduction to Fingerprint Recognition 32

 Minutiae Detection
1 1 1
F (i , j ) = 1 0 1
1 1 1
1 at Ending
∑ I (i , j ) ⋅ F (i , j ) = 2 at Ridge
3 at Bifurcation

Possible attributes of minutiae for matching

n Orientation
n Location w.r.t singular points
n Ridge counting along the line from a singular point
n Slope of the line from a singular point
n Minutiae type

2001/2/23 Introduction to Fingerprint Recognition 33

 Minutiae Healing
Heuristic rules for case-by-case
Possible false minutiae

Merge Loop Bridge Cross Triangle

Break Spur Ladder Double Break & Island

Break merge
n minutiae too close to each other
n minutiae too close to background
2001/2/23 Introduction to Fingerprint Recognition 34
 Example of Minutia Extraction
Smoothing

Binarization Thinning

Original Result

2001/2/23 Introduction to Fingerprint Recognition 35

 Matching
What makes it difficult :
n Rotation and translation
n Deformation of ridge
n Size of common area
n Repeatability of minutia extraction
Matching process
n Alignment
n Matching
n Scoring

2001/2/23 Introduction to Fingerprint Recognition 36

 Decision Policies
“Three strikes out”
n System’s FNM = FNM∩FNM ∩FNM
n If errors are independent,

FNM sys = FNMR 3

( )
1 − FRR = 1 − FNM sys ⋅ (1 − F 2 A)

FRR = FNMR 3 + F 2 A − FNMR 3 × F 2 A

ü FNMR are NOT independent : A single comparison FNM slightly
increases the probability that a subsequent comparison is FNM.
ü Above FRR gives the lower bound of FRR.

2001/2/23 Introduction to Fingerprint Recognition 37

 Decision Policies
n No system’s FM = (No FM) ∩ (No FM) ∩ (No FM)
n False Accept = No failure to acquire AND system FM

1 − FM sys = (1 − FMR )3

[ ]
FAR = 1 − (1 − FMR )3 ⋅ (1 − F 2 A)
≈ 3FMR (1 − F 2 A)

2001/2/23 Introduction to Fingerprint Recognition 38

 007 Never Die

2001/2/23 Introduction to Fingerprint Recognition 39

 Applications
National ID Card Program
n Korea, Spain, Taiwan, Philippine, Singapore
Crime Investigation
n KNPA, FBI's IAFIS and NCIC 2000 Programs
Access Control
n Office, Computer boot-up & logon , Vehicle, Mobile phone, etc.
Network Security, e-Commerce
ATM & Tele-Banking (NCR)
U.S. Prisons & Border Control (DoJ)
Passenger Accelerated Service System - INSPASS
n J.F. Kennedy Airport, SF Airport, worldwide.
Welfare Benefits

2001/2/23 Introduction to Fingerprint Recognition 40

 Taxonomy of Applications
Cooperative / Non-cooperative
n Wolf becomes cooperative in positive ID, but non-cooperative in
negative ID.
Public / Private
n Open to public or limited to employees ?
Open / Closed
n Biometric templates exchangeable to other systems ?
Attended / Unattended
n Supervised or unsupervised ?
Habituated / Non-habituated
n Depending on the frequency of uses

2001/2/23 Introduction to Fingerprint Recognition 41

 Taxonomy of Applications
Overt / Covert
n User’s awareness of biometric identifiers being measured
Standard / Non-standard environment
n Operating in controlled indoor or hostile outdoor ?

Examples
n INSPASS : cooperative, overt, non-attended, non-habituated, public,
closed, standard environment
n Driver’s licensing : non-cooperative, overt, attended, non-habituated,
public, open, standard environment

ü Performance for one environment cannot guarantee the same

performance for other environment

2001/2/23 Introduction to Fingerprint Recognition 42

 Privacy Concerns

생체인식 시스템은 사용자의 신분을 필요로 하지

않음 (범죄수사 제외)
생체인식 특징파일은 법적 구속이 없음
생체인식은 익명의 트랜잭션을 가능케 함
신분 확인 없이 개인인증 가능
신분 확인을 위하여 외부자료와 연계 요구

2001/2/23 Introduction to Fingerprint Recognition 43

 Factors to consider

There are alternatives for positive ID.

Security costs time, money, and effort.
Exception handling is always required.
Testing and evaluation is another technique.
User acceptance is greater than 90%.
System integrator makes or breaks the system.
Beware of orphaned systems.
Integrate with current business process.

2001/2/23 Introduction to Fingerprint Recognition 44

 Prospective

Slow but steady growth

Limits on improving error rates
Great improvement in “human factor”
Multi-modal biometrics
Networked biometrics (wired/wireless)
Biometrics + SC + PKI
Encrypted biometrics
Unlimited applications for identification and
authentication

2001/2/23 Introduction to Fingerprint Recognition 45

 Conclusions

Biometrics has a 120 year history.

Automation of ID process
Positive ID applications are motivated by convenience.
Negative ID applications are motivated by necessity.
Every application requires customization.
One size does not fit all.
This is not “plug-and-play”.
Successful applications abound
Integration !

2001/2/23 Introduction to Fingerprint Recognition 46

 References
J. Wayman, “National Biometric Test Center Collected Works”, Ver. 1.3,
http://www.engr.sjsu.edu/biometrics/nbtccw.pdf, Aug. 2000.
UK Biometrics Working Group, “Best practices in testing and reporting
performance of biometric devices”, http://www.afb.uk/bwgbestprac10.pdf,
Ver. 1.0, Jan. 2000.
A. Jain, et.al., Eds. Biometrics: Information Security in a Networked
Society, Kluwer, 1999.
“Special Issue on Biometrics”, IEEE Computer Magazine, Feb. 2000.
L. Jain, et.al., Eds. Intelligent Biometric Techniques in Fingerprint and
Face Recognition, CRC Press, 1999.
A. Jain, et.al., “Fingerprint Image Enhancement: Algorithm and
Performance Evaluation,” IEEE Trans. On PAMI, Vol.20, No.9, pp.777-
789, Aug. 1998.
D. Gabor, “Theory of Communication”, J. IEE(London), Vol. 93, Part III,
No. 26, pp. 429-457, Nov. 1946.

2001/2/23 Introduction to Fingerprint Recognition 47