 

THESIS

llllllllllHIlllllllllUHllllHllllllIlllllillilllllllllllllll

3 1293 01701 91

This is to certify that the

dissertation entitled

Auromkﬂc 99.50qu meant-1:311»! 0514”;

F M) (IIKP RM! V
presented by

LIN 140le

has been accepted towards fulﬁllment
of the requirements for

pk. D . degree in W546!

 

MW

 

Major professor

Date IN [1,1798

 

MS U is an Afﬁrmative Action/Equal Opportunity Institution 0-12771

 

 

 

 

LIBRARY

, M‘Chlgan State
University

 

 

 

PLACE IN RETURN BOX to remove this checkout from your record.
To AVOID FINE return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE I DATE DUE DATE DUE

 

mum-331$“

 

 

 

 

 

 

 

 

 

 

 

 

 

1M COW.965-p.14

AUTOMATIC PERSONAL IDENTIFICATION USING
FINGERPRINTS

By

Lin Hang

A DISSERTATION

Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Computer Science

June 8, 1998

Ar

than [I
Print id
01” obj
aflil‘fl‘i;
ﬁdinte.
' ﬁndm

IEdi-(lid

ABSTRACT
AUTOMATIC PERSONAL IDENTIFICATION USING FINGERPRINTS
By

Lin Hang

An accurate automatic personal identiﬁcation is critical in a wide range of ap-
plication domains such as national ID card, electronic commerce, and automated
banking. Biometrics, which refers to automatic identiﬁcation of a person based on
her physiological or behavioral characteristics, is inherently more reliable and more
capable in differentiating between an authorized person and a fraudulent imposter
than traditional methods such as passwords and PIN numbers. Automatic ﬁnger-
print identiﬁcation is one of the most reliable biometric technology. In this thesis,
our objective is to design a ﬁngerprint-based biometric system which is capable of
achieving a fully automatic “positive personal identiﬁcation” with a high level of con-
ﬁdence. We have identiﬁed and explored the following issues: (2') feature extraction
- ﬁnding representative features from an input image for the purpose of ﬁngerprint
matching, (Ii) image enhancement - improving the clarity of ridge structures of ﬁnger-
print images to facilitate automatic extraction of features or for visual inspection, (z'z'z')

minutiae matching - determining whether two sets of features (minutiae patterns) are

extrz
the 1
print
into
have
only
idem

mala-

5‘4
em,
(IQ

”YD

mare

perfo;

extracted from the same ﬁnger, (in) integration of multiple biometrics - improving
the performance of a biometric system by combining several biometrics (e.g. ﬁnger-
print, face, speech, etc.), and (v) ﬁngerprint classiﬁcation - assigning a ﬁngerprint
into one of several pre—speciﬁed categories according to its pattern formation. We
have designed two prototype biometric systems: (2') a veriﬁcation system which uses
only ﬁngerprints to authenticate the identity claimed by a user, and (22') an integrated
identiﬁcation system which combines face recognition and ﬁngerprint veriﬁcation to
make a personal identiﬁcation. Our systems have been evaluated extensively on a
large number of ﬁngerprint images captured with the traditional inked method and
more recent inkless optical scanners. Experimental results Show that our systems

perform very well on these data sets.

To Yonghong

iv

I II
years 0
adVléUl
help. A
and CO”

fortunan

IB.\I T

encouragt
always be
learning. l
and lnsigli;
our discussi
Statistics in
Serve on my
fondant of

flank our Pill

ACKNOWLEDGMENTS

I would like to acknowledge all the people who have assisted me during four
years of my graduate study at Michigan State University. I am most grateful to my
advisor, Dr. Anil Jain, for both his professional and personal advice, guidance, and
help. He has provided me with numerous valuable ideas, insights, encouragement,
and comments. He has also been very understanding and supportive. I am very
fortunate to have him as my advisor. I would like to thank Dr. Sharath Pankanti of
IBM T. J. Watson Research Center, NY for his many insightful discussions, steady
encouragement, and numerous professional and personal help. Dr. John Weng has
always been available to me to discuss ideas and concepts in computer vision and
learning. I am very grateful to Dr. Weng for his numerous suggestions, discussions,
and insights. Thanks to Dr. V. Mandrekar for his willingness to make time for
our discussions. He has given me a number of suggestions and ideas on how to use
statistics in ﬁngerprint identiﬁcation. Thanks to Dr. Eric Torng for his willingness to
serve on my committee. He has helped me to appreciate the beauty underlying the
complexity of theory Of computing. Besides the committee members, I would like to

thank our PRIP Lab. Director, Dr. George Stockman, who has been very supportive

mora
and c
Conn
Kalle
Salil l
and Bi
the drz
l in;
london.
.\l}' 5
my Wild:
that I M
[of their
have art-oi
athlerenm
Flﬂall};

Ch

llla. mv f

over the years. I would also like to thank Dr. Ruud Bolle of IBM T. J. Watson
Research Center, NY for his support during the past three years.

My fellow students and colleagues in the MSU PRIP lab have provided help and
moral support throughout my stay here. I would like to thank them for their interest
and concern, especially Paul Albee, Vera Bakic, J inlong Chen, Shaoyun Chen, Scott
Connell, Yuntao Cui, Chitra Dorai, Nico Duta, Mario Figueredo, WeyShuan Hwang,
Kalle Karu, Yatin Kulkarni, Gongjun Li, Jinhui Liu, Karissa Miller, Aniati Murni,
Salil Prabhakar, Nalini Ratha, Arun Ross, Jarle Strand, Dan Swets, Aditya Vailaya,
and Bin Yu. My special thanks go to Salil Prabhakar and Arun Ross for proofreading
the draft of this dissertation.

I would also like to thank Cathy Davison, Mary Gebbia, Lora Mae Higbee, Donna
London, and Linda Moore for their administrative assistance.

My sincere thanks go to all the members of my family. I am most thankful for
my wife’s unfailing support, understanding, and love. Without her, I cannot imagine
that I would have ﬁnished my Ph.D. study. I am also very grateful to my parents
for their never-fading love, care, understanding, and encouragement. I could not
have accomplished anything without their love and support. I owe my life and every
achievement to them.

Finally, I would like to acknowledge Professor Zhisheng You of Sichuan University,

China, my former advisor, for his support and encouragement.

vi

TABLE OF CONTENTS

LIST OF FIGURES x
LIST OF TABLES xv
1 Introduction 1
1.1 Biometrics ................................... 2
1.1.1 Biometric System .............................. 3
1.1.2 Requirements of Biometric Identiﬁers ................... 4
1.1.3 Operational Mode ............................. 5
1.1.4 Performance ................................. 6
1.2 Applications .................................. 8
1.3 Biometric Technologies ............................ 10
1.3.1 Face ..................................... 10
1.3.2 Face Thermogram ............................. 14
1.3.3 Fingerprints ................................. 15
1.3.4 Hand Geometry ............................... 16
1.3.5 Hand Vein .................................. 17
1.3.6 Iris ...................................... 17
1.3.7 Retinal Pattern ............................... 18
1.3.8 Signature .................................. 19
1.3.9 Voice Print ................................. 20
1.3.10 Other Biometric Techniques ........................ 21
1.3.11 Comparison of Biometric Technologies .................. 21
1.4 Problem Deﬁnition .............................. 22
1.5 Overview of the Thesis ............................ 26
1.6 Summary ................................... 28
2 Fingerprint Identiﬁcation 29
2.1 History of Fingerprint Identiﬁcation ..................... 30
2.2 Fingerprint Acquisition ............................ 35
2.3 Fingerprint Classiﬁcation ........................... 40
2.4 Fingerprint Matching ............................. 44
3 System Design 48
3.1 System Level Design ............................. 48
3.2 Algorithm Level Design ........................... 53
3.3 Veriﬁcation System .............................. 55
3.4 Identiﬁcation System ............................. 59

vii

3.5 Difﬁcult Problems .............................. 61

4 Minutiae Extraction 66
4.1 Related Work ................................. 70
4.2 Minutiae Extraction Algorithm ....................... 75
4.2.1 Deﬁnitions ................................. 75
4.2.2 Orientation Field Estimation ....................... 76
4.2.3 Ridge Detection .............................. 80
4.2.4 Minutiae Detection ............................. 81
4.3 Summary ................................... 85
5 Fingerprint Enhancement 87
5.1 Filtering of Fingerprint Image ........................ 93
5.2 Ridge Extraction ............................... 97
5.3 Ridge Voting ................................. 98
5.4 Enhanced Image ............................... 100
5.5 Summary ................................... 104
6 Minutiae Matching 107
6.1 Problem Speciﬁcation ............................ 107
6.2 Literature Review ............................... 112
6.3 Alignment-based Algorithm ......................... 114
6.4 Alignment Hypothesis ............................ 115
6.5 Alignment Hypothesis Evaluation ...................... 118
6.6 Summary ................................... 123
7 Decision Fusion 126
7.1 Multimodal Biometrics ............................ 126
7.1.1 Multimodal Biometrics for Veriﬁcation .................. 129
7.1.2 Multimodal Biometrics for Identiﬁcation ................. 132
7.2 Face Recognition ............................... 133
7.3 Decision Fusion ................................ 137
7.3.1 Impostor Distribution for Fingerprint Veriﬁcation ............ 137
7.3.2 Impostor Distribution for Face Recognition ............... 140
7.3.3 Decision Fusion ............................... 143
7.4 Summary ................................... 145
8 Fingerprint Classiﬁcation 147
8.1 Automatic Fingerprint Classiﬁcation .................... 147
8.2 Feature Extraction .............................. 151
8.2.1 Deﬁnitions ................................. 152
8.3 Ridge Veriﬁcation ............................... 153
8.3.1 Singular Point Detection .......................... 155
8.3.2 Recurring Ridges .............................. 159
8.4 Classiﬁcation ................................. 162

 

LII
8t?
8.5 1

9 E:
91 7
92 l
93 I
94 E
941
9t?
943
95 C
991
952
96 St

IOSun
lOlSu
192Fu

8.4.1 Classiﬁcation Scheme I ........................... 162

8.4.2 Classiﬁcation Scheme II .......................... 165
8.5 Summary ................................... 166
9 Experimental Results 167
9.1 Test Databases ................................ 169
9.2 Feature Extraction Performance ....................... 173
9.3 Fingerprint Enhancement Performance ................... 178
9.4 System Performance ............................. 179
9.4.1 Matching Scores .............................. 180
9.4.2 Authentication Test ............................ 181
9.4.3 Identiﬁcation Test ............................. 188
9.5 Classiﬁcation Performance .......................... 192
9.5.1 Classiﬁcation Scheme I ........................... 192
9.5.2 Classiﬁcation Scheme 11 .......................... 197
9.6 Summary ................................... 201
10 Summary and Iﬁiture Research 202
10.1 Summary ................................... 202
10.2 Future Research ................................ 205

ix

1.4 F

1.5 F
1.6 In
1.7 :1

2.1 E;

2-3 Ila}

LIST OF FIGURES

1.1 A generic biometric system. .........................

1.2 Examples of different biometric characteristics ................

1.3 Multiple Personalities: all the people in this image are the same person
(The New York Times Magazine, September 1, 1996/section 6, pages
48-49). ..................................

1.4 Fingerprint matching: (a) and (b) are two impressions from the same
ﬁnger; (c) and (d) are two impressions from different ﬁngers.

1.5 Fingerprint image enhancement: (a) corrupted image; (b) enhanced image.

1.6 Integration of face recognition and ﬁngerprint veriﬁcation. ........
1.7 A ﬁngerprint image and ﬁve major ﬁngerprint classes ............

2.1 Examples of archaeological ﬁngerprint carvings and historic ﬁngerprint
impressions; although the impressions on the Neolithic carvings and
the Goat Island standing stones might not be used to indicate the
identity, there is sufﬁcient evidence to suggest that the Chinese clay
seal and the impressions on the Palestinian lamp were used to indicate
the identity of the providers. ......................

2.2 Dermatoglyphics drawn by Grew [103]. ...................

2.3 Mayer’s drawings of ﬁngerprints [40]. ....................

2.4 'ITademarks of Thomas Bewick [85] ......................

2.5 The nine patterns illustrated in Purkinje’s thesis [103]. ..........

2.6 Comparison of diﬁerent ﬁngerprint impressions: (a) a rolled ﬁngerprint
(from NIST 4 database); (b) a live-scan ﬁngerprint (captured with a
scanner manufactured by Digital Biometrics); (c) a latent ﬁngerprint.

2.7 FTIR ﬁngerprint scanners: (a) manufactured by Identiar, (b) manufactured
by Digital Biometrics. ..........................

2.8 Solid state ﬁngerprint chips: (a) differential capacitance ﬁngerprint chip
manufactured by Harris [130]; (b) differential capacitance ﬁngerprint
chip manufactured by Veridicom [146]; (c) thermal ﬁngerprint chip
manufactured by Thomson CSF [39]. ..................

2.9 Pattern area and typelines. .........................

2.10 Examples of delta conﬁguration [103]. ...................

2.11 Examples of core conﬁguration [103]. ...................

2.12 Ridge counting [103]. i ............................

2.13 Examples of ﬁngerprints that are difﬁcult to classify; (a) tented arch; (b)
a loop; (c) a whorl; it seems that all the ﬁngerprints shown here should
be in the loop category. .........................

13

24
25
26
27

31
32
32
33

36

2.14 I
2.15 l

3.1 I
3.2 .~‘
3.3
3.4

mm

3.5 F
3.6 .\l

3.7 Pi

~‘l.l E);

2.14 Minutiae; (a) example of minutiae; (b) characterization of minutiae.
2.15 Fingerprint matching result in which 18 identical minute details are iden-

3.1
3.2
3.3
3.4

3.5
3.6

3.7

4.1

4.2

4.3
4.4

4.5
4.6

4.7

4.8

5.1

5.2

5.3

5.4
5.5

tiﬁed [103]. ................................

Different applications have different requirements for the FAR and FRR.
Architecture of the prototype automatic identity veriﬁcation system.
Graphical user interface of the automatic identity veriﬁcation system. . .
System architecture of the prototype integrated biometric identiﬁcation
system. ..................................
Fingerprint images of very poor quality. ..................
Minutiae extraction from a poor quality image; white: correct minutiae;
red: spurious minutiae; green: missing minutiae. ...........
Fingerprint impression deformation. ....................

Examples of good quality live-scan ﬁngerprint images, which were captured
using a ﬁngerprint scanner manufactured by Digital Biometrics.
Examples of poor quality live-scan ﬁngerprint images, which were captured
using a ﬁngerprint scanner manufactured by Digital Biometrics.
Flowchart of the minutiae extraction algorithm ..............
Comparison of orientation ﬁelds estimated by the method proposed in [118]
andourmethod;wxw=16x16andw¢xw¢=5x5 ......
Ridge ﬁlter, ht(i,j; u, v). ..........................
Results of our minutiae extraction algorithm on a live-scan ﬁngerprint im-
age (512 x 512); (a) input image; (b) orientation ﬁeld superimposed on
the input image; (c) ﬁngerprint region; ((1) extracted ridges (e) thinned
ridge map; (f) extracted minutiae and their orientations superimposed
on the input image. ...........................
Results of our minutiae extraction algorithm on a rolled image from N IST
9 database (832 x 768); (a) input image; (b) orientation ﬁeld superim-
posed on the input image; (c) ﬁngerprint region; ((1) extracted ridges
(e) thinned ridge map; (f) extracted minutiae and their orientations
superimposed on the input image. ...................
Examples of postprocessing heuristics. ...................

Results of applying a minutiae extraction algorithm to a ﬁngerprint image
of good quality; (a) input image; (b) extracted ridge map; (c) extracted
minutiae superimposed on the input ﬁngerprint image. ........

Results of applying a minutiae extraction algorithm to a ﬁngerprint image
of poor quality; (a) input image; (b) extracted ridge map; (c) extracted
minutiae superimposed on the input ﬁngerprint image. ........

Fingerprint regions; (a) well-deﬁned region; (b) recoverable corrupted re-
gion; (c) unrecoverable corrupted region. ................

Estimated orientation ﬁelds of ﬁngerprint images of poor quality.

An overview of the ﬁngerprint enhancement algorithm. ..........

xi

45

46

50
56
57

59
62

62
63

68

68
74

78
79

82

88

89
91
92

5.6 .

5.9 In

are

7'1 A gene]
7'2 A 89m
7'3 Integrat
7'4 Integran
1.5 FlrStejg‘

they

Valiie,
7'6 l‘llnuriae
line in

5.6

5.7

5.8

5.9

5.10

5.11

6.1
6.2
6.3
6.4

7.1
7.2
7.3
7.4
7.5

7.6

An even-symmetric Gabor ﬁlter: (a) Gabor ﬁlter tuned to 60 cycles / width
and 0° orientation; (b) corresponding MTF. ..............

Examples of ﬁltered images for a 512 x 512 ﬁngerprint image: (a) input
image; (b—i) ﬁltered images with Gabor ﬁlters tuned to 60 cycles/ width
and orientations of 0°, 22.5°, 45°, 67.5°, 90°, 112.5°, 135°, 157.5°, re-
spectively. ................................

The extracted ridge map of the 0° ﬁltered image: (a) the 0° ﬁltered im-
age; (b) the extracted ridge map from the 0° ﬁltered image; the dark
lines represent the valid ridges; grey lines represent the spurious ridges
removed by the postprocessing step. ..................

Intuitive meaning of the voting algorithm; here for Simplicity, we assume
that the input image is decomposed into two ﬁltered images; (a)-(c)
correspond to rule 1; (d)-(f) correspond to rule 2; (g)-(h) correspond
to rule 3; the left two columns show the inputs to the voting algorithm
while the third column shows the voting results. ...........

An example of ridge voting: (a-h) the ridge maps extracted from ﬁltered
images at 0°, 22.5°, 45°, 67.5°, 90°, 112.5°, 135°, 157.5°, respectively;
(i) the voting result. ...........................

Results of applying the enhancement algorithm to a ﬁngerprint image
of poor quality: (a) input image; (b) coarse-level ridge map; (c)
unrecoverable-region mask which consists of white pixels; ((1) estimated
orientation ﬁeld; (e) enhanced image; (f) minutiae extracted from the
enhanced image superimposed on the input image. ..........

Alignment of the input ridge and the template ridge. ...........
The string matching of a pair of point patterns. ..............
Bounding box and its adjustment. .....................

Results of applying the matching algorithm to an input minutiae set and
a template; (a) input minutiae set; (b) template minutiae set; (c)
alignment result based on the minutiae marked with green circles; ((1)
matching result where template minutiae and their correspondences
are connected by green lines. ......................

A generic multimodal veriﬁcation system. .................
A generic multimodal identiﬁcation system. ................
Integration of multiple snapshots of a Single biometric characteristic.

Integration of diﬁerent biometric characteristics ...............

First eight eigenfaces obtained from 542 training images of size 92 x 112;
they are listed, from left to right and top to bottom, in decreasing
values of the corresponding eigenvalues. ................

Minutiae matching model. A solid line indicates a match and a dashed
line indicates a mismatch. ........................

xii

94

105

116
119
120

124

128
129
130
131

135

L!’

8.1

8.2
8.3
8.4
8.5

9?. F1
9.3 E)

9.6 Era

USiI

11 A‘ pair (
a re.

diffs]
”2171];
minu

8.1 Examples of ﬁngerprints from different categories; (a) tented arch; (b)
loop; (c) whorl; it seems that all the ﬁngerprints shown here should be
in the loop category. ...........................

8.2 The ﬂow-chart of the ﬁngerprint classiﬁcation algorithm. .........

8.3 Singular points .................................

8.4 Ridge veriﬁcation. ..............................

8.5 Ridge veriﬁcation; (a) input image; (b) orientation ﬁeld; (0) thinned ridge
map, ((1) veriﬁed ridge map, where the veriﬁed ridges are marked with
gray shade; (e) interpolated orientation ﬁeld. .............

8.6 Singular point detection: a core is labeled by a rectangle and a delta is
labeled by a triangle. ...........................

8.7 Ridge classiﬁcation; (a) ridges classiﬁed as non-recurring ridges; (b) ridges
classiﬁed as type-1 recurring ridges; and (c) ridges classiﬁed as type-2
recurring ridges. .............................

8.8 Fingerprint class prototypes; (a) arch; (b) tented arch; (c) left loop; ((1)
right loop; and (e) whorl; the dashed lines in (b), (c), and (d) are the
symmetric axes. .............................

9.1 Fingerprint images captured with a scanner manufactured by Digital Bio-
metrics; the size of these images is 640 x 480; images in each row are
from the same ﬁnger. ..........................

9.2 Fingerprint images of ' poor quality. .....................

9.3 Examples of ﬁngerprints in the NIST 9 database; the size of these images
is 832 x 768 .................................

9.4 Examples of ﬁngerprints in the NIST 4 database; the size Of these images
is 512 x 480 .................................

9.5 Examples of ﬁngerprints in the IBM database ................

9.6 Examples of faces in the composite database. ...............

9.7 Receiver Operating Curves; the vertical axis is (l-FRR); the ROC shows
the improvement in veriﬁcation performance of the new minutiae ex-
traction algorithm in contrast to the algorithm in [120]. .......

9.8 Receiver Operating Curves; the ROC shows the improvement in veriﬁca-
tion performance of the enhancement algorithm. ...........

9.9 Fingerprint images from the same ﬁnger. .................

9.10 A mated pair in the MSU database that has a relatively low matching
score: (a) and (b) ﬁngerprint images from the same ﬁnger; (c) and
(d) thinned ridge maps; (e) and (f) extracted minutiae superimposed
on the input images and the corresponding minutiae pairs established
using our matching algorithm. .....................

9.11 A pair of ﬁngerprints from different ﬁngers in the MSU database that have
a relatively high matching score: (a) and (b) ﬁngerprint images from
different ﬁngers; (c) and (d) thinned ridge maps; (e) and (f) extracted
minutiae superimposed on the input images and the corresponding
minutiae pairs established using our matching algorithm. ......

xiii

151
152
154

159

172

174
175
176

177

179
180

9.12

9.13
9.14

916 .'
9.17 I

9.18 .\

919 .11

10.1 Mil

9.12 Distributions of correct and incorrect matching scores; vertical axis repre-

sents distribution of matching scores in percentage; (a) MSU database;

(b) NIST 9 (CD No. 1). ......................... 184
9.13 Receiver Operating Curves; (a) MSU database; (b) NIST 9 (CD No. 1). 187
9.14 Face and ﬁngerprint pairs; the face images (92 x 112) are from the Olivetti

Research Lab.; the ﬁngerprint images (640 x 480) are captured with a

scanner manufactured by Digital Biometrics ............... 189
9.15 Impostor distributions; (a) impostor distribution for ﬁngerprint veriﬁca-

tion; (b) the impostor distribution for face recognition at rank no. 1,

where the stars (*) represent empirical data and the solid curve repre-

sents the ﬁtting result. .......................... 189
9.16 Receiver Operating Curves; the vertical axis is (l-FRR). ......... 190
9.17 Misclassiﬁed ﬁngerprints in NIST 4 ﬁngerprint database; (a) a left loop is

misclassiﬁed as an arch; (b) a tented arch is misclassiﬁed as an arch;

(c) a left loop is misclassiﬁed as a whorl; (d) a whorl is misclassiﬁed as

a right loop. ............................... 194
9.18 Misclassiﬁed ﬁngerprints in NIST 9 database; (a) a tented arch is misclas-

siﬁed as an arch; (b) a whorl is misclassiﬁed as an arch; (c) a whorl is

misclassiﬁed as a left loop; ((1) a whorl is misclassiﬁed as a right loop. 196
9.19 Misclassiﬁed ﬁngerprints in the IBM database; (a) a left loop is misclas-

siﬁed as an arch; (b) a right loop is misclassiﬁed as a tented arch; (c)

a whorl is misclassiﬁed as an arch; (d) a tented arch is misclassiﬁed as

an arch. .................................. 198

10.1 Minutiae with diﬁ'erent degrees of importance; the minutiae labeled by the
circle is more important than the minutiae labeled by the square. . . 206

xiv

II
9.1

93 .-

94 f
9.5 A
9.6 F

.7 F.
9-8 E:
9.9 F]
9.l0 Fc
911 Er
9.12 Fh
9-13 F0:
9.14 Err
9-15 Cor
9-16 lHC(

9'17 Con
9-18 lnco

LIST OF TABLES

1.1 Comparison of Biometric Technologies. ...................

9.1 d’ and mean and standard deviation of the correct and incorrect matching
scores. ...................................
9.2 False acceptance and false reject rates on test sets with different threshold
values. ..................................
9.3 Average CPU time for minutiae extraction and matching on a Sun ULTRA
1 workstation. ..............................
9.4 False reject rates (FRR) on the test set with different values of FAR.
9.5 Average CPU time for one test on a Sun UltraSPARC 1 workstation. . .
9.6 Five-class classiﬁcation results on NIST 4 database .............
9.7 Four-class classiﬁcation results on NIST 4 database .............
9.8 Error-reject tradeoff. .............................
9.9 Five-class classiﬁcation results on NIST 9 database (5,400 images).
9.10 Four-class classiﬁcation results on NIST 9 database .............
9.11 Error rates corresponding to different reject rates on NIST 9 database.
9.12 Five-class classiﬁcation results on the IBM database. ...........
9.13 Four-class classiﬁcation results on the IBM database. ...........
9.14 Error rates corresponding to different reject rates on the IBM database.
9.15 Consistency test results on the NIST 4 database. .............
9.16 Inconsistency rates corresponding to different reject rates on the NIST 4
database. .................................
9.17 Consistency results on the NIST 9 database. ...............
9.18 Inconsistency rates corresponding to different reject rates on the NIST 9
database. .................................

XV

21

C]

In?

Parse.
a criti.
such an
barf/IE I
have 0.
El'ery d,
elf-1.11011
0f lllfun
009119610
ldenliﬁca
Tladi I
lla'rp [100“
ha” 3111)

199111,]

Hal.

Chapter 1

Introduction

Personal identiﬁcation is to associate a particular individual with an identity. It plays
a critical role in our society, in which questions related to the identity of individuals
such as “Is this the person who he or she claims to be?”, “Has this applicant been here
before .9”, “Should this individual be given access to our system?”, “Does this employee
have authorization to perform this transaction?”, etc. are asked millions of times
every day by hundreds of thousands of organizations in ﬁnancial services, health care,
electronic commerce, telecommunication, government, etc. With the rapid evolution
of information technology, people are becoming even more and more electronically
connected. As a result, the ability to achieve highly accurate automatic personal
identiﬁcation is becoming more critical [75, 34, 44, 97, 106, 109, 154].

Traditionally, two major types of automatic personal identiﬁcation approaches
have been widely used: (2') knowledge-based and (ii) token-based [97, 106, 109]. Token-
based approaches use “something that you have” to make a personal identiﬁcation.
Individuals are identiﬁed by demonstrating that they are in possession of certain

I

take
bé‘m
lndi

or k:

easil)

tiona

3 per:
stolen
All of
and a]
{129d l~

r(‘quire

1.1

BEG-flirt;

haligral

2

token, such as passport, driver’s license, ID card, credit card, and keys. Knowledge-
based approaches use “something that you know” to make a personal identiﬁcation.
Individuals are identiﬁed by demonstrating that they are in possession of information
or knowledge which only they themselves are expected to know such as password and
personal identiﬁcation number (PIN). The major advantages of these traditional per-
sonal identiﬁcation approaches are that (i) they are very Simple and (ii) they can be
easily integrated into different systems with a low cost. However, since these tradi-
tional approaches are not based on any inherent attributes of an individual to make
a personal identiﬁcation, they have a number of disadvantages: tokens may be lost,
stolen, forgotten, or misplaced; PIN may be forgotten or guessed by the impostors.
All of these approaches are also unable to diﬁerentiate between an authorized person
and an impostor who fraudulently acquires the “token” or “knowledge” of the autho-
rized person [34, 44, 97, 106, 109]. Therefore, they are unable to satisfy the security

requirements of our electronically inter-connected information society.

1.1 Biometrics

Biometrics, which refers to identifying an individual based on her physiological or be-
havioral characteristics (identiﬁers) [75, 34, 44, 97, 106], relies on “something which
you are or you do” to make a positive personal identiﬁcation. It is inherently more
reliable and more capable than knowledge-based and token-based techniques in dif-
ferentiating between an authorized person and a fraudulent impostor, because the

physiological or behavioral characteristics are unique to every person. Also, the per-

5011
Ehur
C011 11

Inati

1.1.1

A big.
identt
charac
l5 dt’pl
Inenty
for 9an
biompt]
dMPar
lbe raw
generate
theapph
Stream 0
Thejden.
affﬁs [3
Oil”? indi

pr‘i’cfnsvd 1

3

son to be identiﬁed is required to be physically present at the point-of-identiﬁcation.
Biometrics provides a solution for the security requirements of our electronically inter-
connected information society and has the potential to become the dominant auto-

matic personal identiﬁcation in the near future [34, 44, 106, 109, 97, 75].

1.1.1 Biometric System

A biometric system is essentially a pattern recognition system which make a personal
identiﬁcation by determining the authenticity of a speciﬁc physiological or behavioral
characteristic possessed by the user. The block diagram of a generic biometric system
is depicted in Figure 1.1. Logically, it can be divided into two modules: (2) enroll-
ment module and (ii) identiﬁcation module. The enrollment module is responsible
for enrolling individuals into the biometric system. During the enrollment phase, the
biometric characteristic of an individual is ﬁrst scanned by a biometric reader to pro-
duce a raw digital representation of the characteristic. In order to facilitate matching,
the raw digital representation is usually further processed by a feature extractor to
generate a compact but expressive representation, called a template. Depending on
the application, the template may be stored in the central database of the biometric
system or be recorded on a magnetic card or smart card issued to the individual.
The identiﬁcation module is responsible for identifying individuals at the point-of-
access. During the operation phase, the biometric reader captures the characteristic
of the individual to be identiﬁed and converts it to a digital format, which is further

processed by the feature extractor to produce the same representation. The resulting

1“”

 

13%" T“

b;.

vi

2...:

WW”

[0 ESIE

1.1.2

Any hU
characlf
the folla
should he
should hf.
that the c
(2165 that
a biometrir

be feasible l

Template Database

Enrollment Module

Blometrlc Feature Extractor
Reader

o
)

Identification Module
Feature Extractor
Biometric
Reader

 

‘ Feature Matcher 1

Figure 1.1: A generic biometric system.

 

representation is fed to the feature matcher which compares it against the template(s)

to establish the identity.

1.1.2 Requirements of Biometric Identiﬁers

Any human physiological or behavioral characteristic can be used as a biometric
characteristic 0r identiﬁer to make a personal identiﬁcation as long as it satisﬁes
the following requirements [34, 106]: (i) universality, which means that each person
should have the characteristic, (ii) uniqueness, which indicates that no two persons
should be the same in terms of the characteristic, (iii) permanence, which means
that the characteristic should not be changeable, and (iv) collectability, which indi-
cates that the characteristic can be measured quantitatively. However, in practice,
a biometric characteristic that satisﬁes all the above requirements may not always

be feasible for a practical biometric system. In a practical biometric system, there

t0 acre
Which I
blillllf’ll
and 5pc

[E‘CIS an.

Various 1

1.1.3

llllllVllan
Illay be p]-
'l [Silica]
II .

ll CDHdUCI.

Indilldual

dished to l

5

are a number of other issues which should be considered, including [34, 106] (2) per-
formance, which refers to the achievable identiﬁcation accuracy, Speed, robustness,
the resource requirements to achieve the desired identiﬁcation accuracy and Speed,
as well as Operational or environmental factors that affect the identiﬁcation accuracy
and Speed, (22) acceptability, which indicates the extent to which people are willing
to accept a particular biometric identiﬁer in their daily life, and (iii) circumvention,
which reﬂects how easy it is to fool the system by fraudulent methods. A practical
biometric system Should be able to (i) achieve an acceptable identiﬁcation accuracy
and speed with a reasonable resource requirements, (ii) not be harmful to the sub-
jects and be accepted by the intended population, and (iii) be sufﬁciently robust to

various fraudulent methods.

1.1.3 Operational Mode

An important issue in designing a practical biometric system is to determine how an
individual is identiﬁed. Depending on the application context, a biometric system
may be either a veriﬁcation (authentication) system or an identiﬁcation system [106].
A veriﬁcation system authenticates a person’s identity by comparing the captured
biometric characteristic with her own biometric template(s) pre-stored in the system.
It conducts one-to-one comparison to determine whether the identity claimed by the
individual is true or not. In a veriﬁcation (authentication) system, an individual
desired to be identiﬁed submits a claim to an identity to the system usually via a

magnetic stripe card, login name, smart card, etc., and the system either rejects or

it

aI‘CPp‘
systen
It can
an id?
subjec
an ids]
De;
onhnc
cationf
On tht
liOll_.-’rldé

l5 allow.

1.1.4

DUE to i
lahllSlieC
ideallly;
1in 931a]
ithid] Ca,
and lfnpg
than], 0

Comes: i 2')

6

accepts the submitted claim of identity (Am I whom I claim I am .9). An identiﬁcation
system recognizes an individual by searching the entire template database for a match.
It conducts one-to—many comparisons to establish the identity of the individual. In
an identiﬁcation system, the system establishes a subject’s identity (or fails if the
subject is not enrolled in the system database) without the subject having to claim

an identity (Who am 1?).

Depending on the application domain, a biometric system could be either (i) an
online system or (ii) an offline system. An online system requires that a veriﬁ-
cation/identiﬁcation be performed quickly and an immediate response is imposed.
On the other hand, an offline system usually does not. require that a veriﬁca-
tion/identiﬁcation be performed immediately and a relatively long response delay

is allowed.

1 .1.4 Performance

Due to intraclass variations present in any biometric characteristic, the identity es-
tablished by a biometric system is not an absolute “yes” or “no” answer about the
identity; instead it is an answer with a certain conﬁdence level. Generally, the iden-
tity established by a biometric system is either a genuine type or an impostor type,
which can be represented by two statistical distributions, called genuine distribution
and impostor distribution, respectively. For each of type of identity, there are two
possible outcomes, true or false. Therefore, there are a total of four possible out-

comes: (i) a genuine individual is accepted, (22) a genuine individual is rejected, (iii)

an inlllf
torrf?Ct ‘
til." 95m
(ll f0!"E
terlzpd ’
false 3“"
genuinei
indit'lduf’
:l Smallt’l
larger FR
personal 1
n0 imp”SI
An idP
the conﬁtlf
Surfs, 11'th
to be prox‘i
Precision is
by the idea
deﬁned as t
the identiﬁt.‘
database.
in adllitiu

mam pedal

7

an impostor is rejected, and (iv) an impostor is accepted. Outcomes (i) and (iii) are
correct whereas (22) and (iv) are incorrect. The conﬁdence associated with the iden-
tity established by the biometric system may be determined by the two error rates,
(i) false acceptance rate (FAR) and (ii) false reject rate (F RR), which are charac-
terized by the genuine distribution and the impostor distribution, respectively. The
false acceptance rate is deﬁned as the probability that an impostor is accepted as a
genuine individual and the false reject rate is deﬁned as the probability that a genuine
individual is rejected as an impostor. Clearly, FAR and FRR are dual of each other.
A smaller FRR usually leads to a larger FAR while a smaller FAR usually implies a
larger FRR. Generally, the capability of a biometric system in performing automatic
personal identiﬁcation is speciﬁed in terms of FAR [106]. A FAR of zero means that
no impostor is accepted as a genuine individual.

An identiﬁcation system is essentially a database retrieval system. In addition to
the conﬁdence level Of the established identity, two other important accuracy mea-
sures, which characterize the retrieval accuracy of a database retrieval system, need
to be provided to indicate the capability of the system: (i) precision and (ii) recall.
Precision is defined as the ratio of genuine records in the template database retrieved
by the identiﬁcation system and the total number of templates retrieved. Recall is
deﬁned as the ratio of the genuine records in the template database retrieved by
the identiﬁcation system and the total number of genuine records in the template
database.

In addition to accuracy, veriﬁcation / identiﬁcation speed constitutes the next im-

portant performance measure. In a veriﬁcation system, since only one-tO-one compar-

 

150115
time (
com p1

qnirer

nnmbe

and St

8

isons are performed, the Speed performance is mainly characterized by the response
time of the veriﬁcation (and feature extraction) algorithm or more precisely by the
computational complexity of the algorithm. It is usually easy to meet the speed re-
quirement of a veriﬁcation system. However, in an identiﬁcation system, especially
for a system which consists of millions of templates, a large number of comparisons
need to be performed to identify an individual. The speed performance involves a
number of aspects, including response time, throughput, computational complexity,

and scalability.

1 .2 Applications

Biometrics is a rapidly evolving technology which has been widely used in forensics
such as criminal identiﬁcation and prison security, and has a very strong potential to
be widely adopted in a broad range of civilian applications. These applications may
be divided into the following two groups: (2) applications such as banking, electronic
commence, and access control in which biometrics will replace or enforce the current
token-based or knowledge-based techniques and (ii) applications such as welfare and
immigration in which neither the token-based nor the knowledge-based techniques
are currently being used.

Electronic commence and electronic banking are one of the most important and
emerging application areas of biometrics due to the rapid progress in electronic trans-
actions. These applications include electronic fund transfers, ATM security, check

cashing, credit card security, smart cards security, online transactions, etc. Cur-

t: “mm-1*

till

tenth“

relOPm
and AI
demon:
control

that. W

to bion:

anthem

tial app
systems,
of lnten.
program

ings in dt
such as l.
inmigrati
ational eff.
citizens an.
inter r5923
based time ,1

9

rently, there are several large biometric security projects in these areas under de-
velopment including credit card security (MasterCard) and smart card security (IBM
and American Express). A variety of biometric technologies are now competing to
demonstrate their utility in these application areas. The market of physical access
control is currently dominated by token-based technology. However, it is predicted
that, with the progress in biometric technology, market Share will increasingly Shift
to biometric techniques. Information system/computer network security such as user
authentication and access to databases via remote login iS another important poten-
tial application area for biometrics. It is expected that more and more information
systems/ computer networks will be secured with biometrics with the rapid expansion
of Internet. With the introduction of biometrics, government beneﬁts distribution
program such as welfare disbursement programs [98] will experience substantial sav-
ings in deterring multiple claimants. In addition, customs and immigration initiatives
such as INS Passenger Accelerated Service System (INSPASS) which permits faster
immigration procedures based on hand geometry [62] will greatly increase the Oper-
ational efﬁciency. Biometrics-based national ID systems provide a unique ID to the
citizens and integrate different government services [106]. Biometrics-based voter and
driver registration provides registration facilities for voters and drivers. Biometrics-
based time/attendance monitoring systems can be used to prevent any abuses of the

current token-based / manual systems [86].

 

--_.___1

1.3

A bion:
10ml cl
A belia
accurac
reliable
charactt
charactt
Curr
Widely u
geometry
9mm [6.
393mm};
metrics, E
Cllllt‘rem [
DISHES. [0
have been

alﬁlid him

10
1.3 Biometric Technologies

A biometric characteristic could be either (i) a physiological characteristic or a behav-
ioral characteristic. A physiological characteristic is an attribute that is innate to us.
A behavioral characteristic captures something that we do. In terms of identiﬁcation
accuracy, generally, it is believed that a physiological biometric characteristic is more
reliable than a behavioral biometric characteristic, since a physiological biometric
characteristic tends to have smaller intraclass variation than a behavioral biometric
characteristic [106].

Currently, there are mainly nine different biometric techniques that are either
widely used or are under intensive investigation, including face, ﬁngerprint, hand
geometry, hand vein, iris, retinal pattern, signature, voice-print, and facial thermo-
gram [6, 34, 44, 75, 97, 42, 106, 143, 49, 70, 155, 105, 153]. Face, ﬁngerprint, hand
geometry, hand vein, iris, facial thermogram, and retinal pattern are physiological bio—
metrics. Signature and voice-print are behavioral biometrics. Examples of these nine
different biometric characteristics are shown in Figure 1.2. All these biometric tech-
niques, to a certain extent, satisfy the requirements mentioned in section 1.1.2 and
have been used in practical systems [34, 44, 42, 106] or have the potential to become

a valid biometric technique [106]. We will brieﬂy review these biometric technologies.

1.3.1 Face

Facial images are probably the most common biometric characteristic used by hu-

mans to make a personal identiﬁcation. Face recognition is one of the most active

11

 

face

   

hand geometry hand vein

 

 

 

 

 

 

M II II! 0.! II I) II U II

retinal scan signature voice print

Figure 1.2: Examples of different biometric characteristics.

area 0
tion it
the to
static.
facial l
or ran,
olutior:
and fa:
in such
traclass
general]
Theater

12

area of research with applications ranging from static, controlled mug shot veriﬁca-
tion to dynamic, uncontrolled face identiﬁcation in a cluttered background [30]. In
the context of automatic personal identiﬁcation, face recognition usually refers to
static, controlled full frontal portrait recognition [30]. By static we mean that the
facial portraits used by the face recognition system are still facial images (intensity
or range). By controlled we mean that the type of background, illumination, res-
olution of the acquisition devices and the distance between the acquisition devices
and faces, etc. are essentially ﬁxed during the image acquisition process. Clearly,
in such a controlled situation, the segmentation task is relatively simple and the in-
traclass variations are small. Face recognition is a non-intrusive technique. People
generally do not have any problem in accepting face as a biometric characteristic.
Theoretically, it has the potential to become the most friendly and acceptable way
to make personal identiﬁcation [6, 106, 144]. During the past 25 years, a substantial
amount of research effort has been devoted to face recognition [30, 145, 155]. In the
early 1970’s, face recognition was mainly based on measured facial attributes such
as eyes, eyebrows, nose, lips, chin shape, etc. [30]. Due to lack of computational
resources and reliable feature extraction algorithms, only a very limited number of
tests were conducted and the recognition performance of these systems was far from
desirable [30]. After the dormant early 1980’s, there was a resurgence in face recog-
nition research in the late 1980’s and early 1990’s. In addition to continuing efforts
on attribute-based techniques [30], a number of new face recognition techniques were
proposed, including principle component analysis (PCA) [144], linear discriminant

analysis (LDA) [139], singular value decomposition (SVD) [65], local feature analy-

 

 

—m—--

_. m

We
91”
are

the

71-5.
3:“
5
g
. *2
r"
:3

 

Figure 1.3: Multiple Personalities: all the people in this image are the same person
(The New York Times Magazine, September 1, 1996/section 6, pages 48-49).

sis [6], and a variety of neural network-based techniques [145]. The performance of
these approaches is impressive. It was concluded that “face recognition algorithms
were developed and were sufﬁciently mature that they could be ported to real-time
experimental / demonstration system” [114]. A number of face recognition systems are
available on the market, such as TrueFace [99] and Faceit [148]. The performance of
these systems is reasonable.

Although humans depend heavily on facial images and attributes to identify in-
dividuals, it is widely known that humans utilize a large amount of contextual infor-
mation in performing face recognition [34]. Without the contextual information, it is
questionable whether the face itself is sufﬁciently effective to make a personal identi-
ﬁcation with a high level of conﬁdence. For example, without any other information

about the faces in ﬁgure 1.3, it will be very difﬁcult for both humans and machine

vision 5)
.llogazii
posed It
should r.
acquired
Whether
and (222')

the difl‘ic'

1.3.2

The under
When heat
famill Sign;
[3‘9 therrnt
They are lit
ﬂow 0f bloo

0‘ an mum

14

vision systems to conclude that they are all of the same person (The New York Times
Magazine, September 1, 1996/section 6, pp. 48-49). Since face recognition is sup—
posed to be the most user-friendly biometric technology, a face recognition system
should not impose any annoying controlled restrictions on how the facial images are
acquired. This requires that the system should be able to automatically (2) detect
whether there exists a face in the acquired image, (ii) locate the face if there is one,
and (iii) recognize the face from a general viewpoint. These issues highlight some of

the difﬁculties in face recognition [6, 144].

1.3.2 Face Thermogram

The underlying vascular system in the human face produces a unique facial signature
when heat passes through the facial tissue and is emitted from the skin [143]. Such
facial signatures can be captured using an infrared camera, which are usually called
face thermogram. It is believed that a face thermogram is unique to each individual.
They are not vulnerable to disguises. Even plastic surgery, which does not reroute the
ﬂow of blood through the veins, cannot change the formation of the face thermogram
of an individual. Also, face thermograms are independent of ambient light. An
infrared camera can capture the face thermogram in low light or in the absence of any
light, which greatly reduces the restrictions on how face thermograms are acquired.
Clearly, face thermogram is a non-intrusive biometric technique. Identity can be
veriﬁed without contact, without full camera view, and without the cooperation of

subjects. It is claimed that face thermogram-based recognition is superior to face

 

Thin-1|

recogr
are ur
SllfIlClt
such a
face tl

been 5.

1.3.3

A huge
l3 form.
Scales fr
riod [10
Identiﬁu
are “'El]
femuricg
fact. ling.
kWine t.
023-13 its
used {Dr C
[Sing 50%;.
Oil is that

C .
Olllpu [5111.0

15

recognition using CCD cameras [143]. Although it may be true that face thermograms
are unique to each individual, it has not been proven that face thermograms are
sufﬁciently discriminative. Face thermograms depend heavily on a number of factors
such as the emotion of the subjects, the body temperature, etc. Like face recognition,
face thermogram recognition is view-dependent. Finally, face thermogram has not

been shown to be a permanent biometric characteristic.

1.3.3 Fingerprints

A ﬁngerprint is the pattern of ridges and furrows on the surface of a ﬁngertip. It
is formed by the accumulation of dead, corniﬁed cells that constantly Slough as
scales from the exposed surface [103]. It’s formation is determined in the fetal pe-
riod [103]. Extensive studies have been conducted on ﬁngerprints and ﬁngerprint
identiﬁcation [39, 53, 108, 85, 103, 106]. The biological properties of ﬁngerprints
are well understood. Humans have used ﬁngerprints for personal identiﬁcation for
centuries and the validity of ﬁngerprint identiﬁcation has been well-established. In
fact, ﬁngerprint technology is so common in personal identiﬁcation that it has almost
become the synonym of biometrics [44]. A major problem with ﬁngerprint technol-
ogy is its acceptability by a typical user, because ﬁngerprints have traditionally been
used for criminal investigations and police work. People may feel uncomfortable in
using ﬁngerprints in civilian applications. Another problem with ﬁngerprint technol-
ogy is that automatic ﬁngerprint identiﬁcation generally requires a large amount of

computational resources. For more details on ﬁngerprint matching, see section 2.2.

 

1.3.4

A variet
of the ﬁi
metric S.
the C olc
techniqu
ric systei
limited I
problem
is its low
biometric-
PODulatio
TE‘Strict it
metric IPI'
blOmE'll'ic
based him

a HUDIIJEr (
rework. b“

p"T‘SQTIEIl ide

”Ether lUstl

16
1.3.4 Hand Geometry

A variety of hand geometries including the shape of the hand and lengths and widths
of the ﬁngers, etc. can be used as biometric characteristics. Hand geometry-based bio-
metric systems have been installed at over 4,000 locations around the world, including
the Colombian legislature and the San Francisco International Airport [44, 106]. The
technique is very simple and cheap. The accuracy of a hand geometry—based biomet-
ric system is quite reasonable. Operational environmental factors generally have very
limited negative effects on the identiﬁcation accuracy. It does not appear to be a
problem for people to accept this technology. A main disadvantage of this technique
is its low discriminative capability — it is very difficult for a hand geometry-based
biometric system to achieve a very high identiﬁcation accuracy especially for a large
population. The physical size of a hand geometry-based system is large, which may
restrict it from certain applications such as laptop computers. Among the nine bio-
metric techniques illustrated in Figure 1.2, hand geometry is the least circumventive
biometric characteristic. It is usually not very difficult to fool a hand geometry-
based biometric system. In addition, hand geometry is not a permanent biometric

characteristic [106].

A variant of hand geometry technique, ﬁnger geometry technique, which relies on
a number of geometrical invariants of ﬁngers such as the 3D shape of a ﬁnger has
recently been investigated. It is claimed that ﬁnger geometry is more accurate in
personal identiﬁcation than hand geometry. However, such a conclusion needs some

further justiﬁcation.

it? inn" ' -—.-1

1.3.5

Hand \
metric
vein pa
are uni<
is easy I
the ban.
is very 6
system 1
are norrr
51'5tern a
automati
‘3 hand y.
The phyS

permanen

1.3.6 ]

17
1.3.5 Hand Vein

Hand veins provide a very robust and repeatable pattern that can be used as a bio-
metric characteristic to make a personal identiﬁcation [106]. Digitized images of hand
vein patterns can be easily captured with an infra-red camera. Hand vein patterns
are unique to each individual. They are separated from external environment, so it
is easy to segment it from background. It is very difﬁcult to change the formation of
the hand vein pattern of an individual by surgery. Thus, hand vein based technique
is very efﬁcient in circumventing fraudulent attempts. A hand vein-based biometric
system has the potential to achieve a reasonable identiﬁcation accuracy and people
are normally willing to accept it. However, there is no hand vein-based biometric
system available that iS able to demonstrate its superior capability in conducting
automatic personal identiﬁcation. Like hand geometry, it might be very difﬁcult for
a hand vein-based biometric system to achieve a very high identiﬁcation accuracy.
The physical size of a hand vein-based system is large. Again, hand vein is not a

permanent biometric feature, especially for people in developing age group.

1.3.6 Iris

The texture formation of iris in a human eye depends on the initial conditions of the
embryonic mesoderm from which it develOpS [42, 106]. It is unique for each individual
and it never changes during the person’s life time. Iris is inherently isolated from
external environment and can not be modiﬁed surgically [42]. All of these properties

make iris one of the most secure biometric characteristic in deterring impostors [106,

1:33].
identﬁ
future
such a
a very
resourc
as 3 pr
imaging
feel con
usually
certain (
the iris i
ills imag

t0 be use.

1.3.7

The Min,-
retinal pat
can be “'9‘
Patterns 81

l
n dWhine

me ”1011]

18

153]. The technique is simple but very efﬁcient in performing automatic personal
identiﬁcation. It has the potential to become a major biometric technique in the
future. Currently, a few iris scan-based biometric systems are available in the market
such as the IriScan developed by IriScan, Inc. which is claimed to be able to achieve
a very high identiﬁcation accuracy with a very limited amount of computational
resources [42, 106]. The major problem with iris scan is that it is still not accepted
as a proven technology and its validity has not yet been well established [106]. Iris
imaging needs to project a bean of light on the iris. It appears that people may not
feel comfortable in accepting iris scan technique in their daily life, since people are
usually very protective of their eyes. In addition, the sensor needs to be placed at a
certain distance from the eye to capture the visual texture information and to register
the iris images, which is another annoying restriction. Finally, in order to capture an
iris image that is suitable for identiﬁcation, a relatively expensive iris scanner needs

to be used.

1.3.7 Retinal Pattern

The retinal veins in human eyes form very stable and repeatable patterns, called
retinal patterns. They are unique to each person. Digital images of retinal patterns
can be acquired by projecting a low-intensity beam of light on the eyeball. Retinal
patterns are isolated from the external environment which is a very good property
in deterring impostors. In fact, retinal scan is currently believed to be the most

secure biometric technique. A large number of retinal scan-based biometric systems

i —_—.TITI"Z-n ‘ﬂ

have bt
Well 95h
that 0’"
all." full
Swen]
usually
Capt”re
the ‘15”
The ('051

bjomel fl

1.3.8

Each per:
that can
proaches ‘
cation use
uSeS both
110D, YelOf
Sgnature~l
acceptable
hthat it i.

Written sir'
t. 3.3.

19

have been installed in several highly secure environments. Their validity has been
well established by these operational installations. For example, it has been reported
that one type of retinal scan-based biometric system, the EyeDentify, has never let in
any impostor so far [106]. The major problem for a retinal pattern-based biometric
system is that most people do not feel comfortable in using such a system and it
usually needs a high degree of cooperation from the subjects, since retinal image
capture requires peeping into an eye-piece and focusing on a predetermined spot in
the visual ﬁeld so that a predetermined part of the retinal veins could be scanned.
The cost of a retinal scanner is high. Again, retinal pattern is not a permanent

biometric characteristic [106].

1.3.8 Signature

Each person has a unique style of handwriting. Signature is a kind of “ﬁngerprint”
that can be used to make a personal identiﬁcation [105, 106]. There are two ap-
proaches to signature veriﬁcation: (i) static and (ii) dynamic. Static signature veriﬁ-
cation uses only the geometric features of a signature. Dynamic signature veriﬁcation
uses both the static geometric features and the dynamic features such as accelera-
tion, velocity, and trajectory proﬁles of the signature. An inherent advantage of a
signature-based biometric system is that the signature has been established as an
acceptable form of personal identiﬁcation method. Another advantage of signature
is that it is impossible for an impostor to obtain the dynamics information from a

written signature. The identiﬁcation accuracy of signature-based biometric systems

is reas‘
val'l'f“t it

system:

1.3.9

The \'OC

nasal Ca-
The.V 3“
cation CC
A text*d‘
fn'Ed Pr“
speaker l1
ﬁcation. I
there are

including5
ternariona.
l'eritel). l
are willing
voicepriht t
identiﬁcatim

ahumher of

20

is reasonable. For example, a false acceptance rate of 0.58% and false reject rate of
2.1% were claimed by a commercial system [106]. However, due to large intraclass
variations of signature, it is very difﬁcult for both static and dynamic signature-based

systems to reach a very high identiﬁcation accuracy.

1.3.9 Voice Print

The vocal characteristics of humans are totally determined by the vocal tract, mouth,
nasal cavities, and the other speech processing mechanisms of human body [70, 106].
They are unique to each person and are usually called voice-prints. Voice—print veriﬁ-
cation could be either a text—dependent veriﬁcation or a text-independent veriﬁcation.
A text-dependent veriﬁcation authenticates the identity of an individual based on a
ﬁxed predetermined phrase. A text-independent veriﬁcation veriﬁes the identity of a
speaker independent of the phrase, which is more difﬁcult than a text-dependent veri-
ﬁcation. Extensive studies have been conducted on voice print techniques. Currently,
there are a number of voice print-based biometric systems available in the market,
including SpeakEZ (by T-NETIX), Tespar (by Domain Dynamics), VoiceKey (by In-
ternational Electronic, Inc.), BHS-1024 (by Technologia Systems), and Veritel (by
Veritel). They can achieve a reasonable identiﬁcation accuracy. Generally, people
are willing to accept a voice-print based biometric system. The main problem with
voice-print technique is that voice-prints may not be suﬂiciently unique to permit an
identiﬁcation of an individual from a large population. Voice-prints are sensitive to

a number of factors such as background noise as well as the emotional and physical

KT
lau

Fixer;
l Hithd (10!.
._______

llftIi‘i \

l .
lib

. Retznal 1

Striati

I \'.tl(t' l)
' FTQ'iermr.
—

State of t
accuracy

In additlt

1.3.10

Besides ll
been int-(i
dynamm‘
0W1] ade
the nine d
ll] faCt, ll]

be USed W

13.11

Eat-h of ti

Vmasks.

lS Dim-id“;

21

 

Table 1.1: Comparison of Biometric Technologies.

state of the speaker. It is very difficult for a voice-print based system to achieve an
accuracy comparable to ﬁngerprint-based or retinal pattern-based biometric systems.

In addition, some people seem to be extraordinarily skilled in mimicking others voice.

1.3.10 Other Biometric Techniques

Besides the techniques mentioned above, a number of other biometric techniques have
been investigated or are currently under study, including ear shape, gait, keystroke
dynamics, body odor, lip shape, DNA, etc. Although each of these techniques has its
own advantages, so far, none of them can achieve an accuracy that is comparable to
the nine different techniques mentioned above or can be conducted fully automatically.
In fact, they do not have a strong potential to become a valid biometric technique to

be used widely in the near future.

1.3.11 Comparison of Biometric Technologies

Each of the biometric technique reviewed above has its own advantages and disad-
vantages. A brief comparison of these nine biometric techniques along seven factors

is provided in Table 1.1. The applicability of a speciﬁc biometric technique depends

if...

heavily

in all 01

missiblf

lIlS SC'aI]

aCCuraC}

Print 1“.
Idephon.
It is j
the Dim-j.
idem”): I
Iechniqlle
Used and ,
a legally a

IHVOlt-pd “

U;

22

heavily on the application domain. No single technique can outperform all the others
in all operational environments [106]. In this sense, each biometric technique is ad-
missible. For example, it is well known that both the ﬁngerprint technique and the
iris scan technique perform much better than the voice print technique in terms of
accuracy and speed. However, in a telephone account security application, the voice
print technique is preferred, because it can be integrated seamlessly into the current
telephone system.

It is important to point out that most of the biometric techniques reviewed in
the previous section are not acceptable (in a court of law) as indisputable evidence of
identity. In fact, the only legally acceptable, readily automated, and mature biometric
technique so far is the automatic ﬁngerprint identiﬁcation technique which has been
used and accepted in forensics since the early 1970’s [85]. Although, signature is also
a legally acceptable biometrics, it ranks a distant second to ﬁngerprints due to issues

involved with accuracy, forgery, and behavioral variability.

1 .4 Problem Deﬁnition

In this thesis, our objective is to design a biometric system which is capable of
achieving a fully automatic personal identiﬁcation with a high level of conﬁdence
using mainly ﬁngerprints. The research problem may be stated as follows: Design a
ﬁngerprint-based automatic personal identiﬁcation system that can (i) authenticate
whether the identity claimed by an individual is true or not (Am I who I claim I am?)

or (ii) establish the identity of individuals that are enrolled in the system (Who am

 

I'?)- T]
tion is '
long be
techni‘l‘
fuIUre l
th95i5°
(it) ﬁ
of the 5‘
Capabllll
impOrtaI
.se'nfal 10 7}
match (21'
tion is to
is to dete
attracted
ﬁt-ient fin
ﬁngerpriri‘
effective I]
representa
should con
prints. \rhi

r r w
~9ilffrsteritat

lit-l") ﬁng

23

I7). The advantages of using ﬁngerprints are as follows: (i) ﬁngerprint identiﬁca-
tion is one of the most reliable personal identiﬁcation technique, (ii) its validity has
long been established and justiﬁed, and (iii) it is the most commonly used biometric
technique which has the potential to stay as a dominant biometric technique in the
future [106]. We have identiﬁed and investigated the following four issues in this
thesis.

(i) ﬁngerprint matching - determining whether two ﬁngerprints are impressions
of the same ﬁnger (Figure 1.4). Fingerprint matching constitutes the fundamental
capability of a fully automatic ﬁngerprint-based biometric system. The two most
important problems in ﬁngerprint matching are: (i) how to derive an eﬂ‘icient repre-
sentation that is able to capture the individuality of each ﬁngerprint and (ii) how to
match two representations to find the similarity between them. To derive a representa-
tion is to extract a set of features from an input image. To match two representations
is to determine a conﬁdence value with which we can claim that two sets of features
extracted from two ﬁngerprints are from the same ﬁnger. In order to design an ef-
ﬁcient ﬁngerprint matching algorithm, it is necessary that a concise but sufﬁcient
ﬁngerprint representation be derived from the input digital ﬁngerprint images and an
eﬁ'ectiue matching algorithm be designed to determine whether two sets of derived
representations are of the same ﬁnger. By sufﬁcient we mean that a representation
should contain enough class-speciﬁc (individual) information about the digital ﬁnger—
prints, while by effective we mean that the matching performance based on the given
representation should be high enough to make a conﬁdent personal identiﬁcation.

(ii) ﬁngerprint image enhancement - improving the quality of an input ﬁngerprint

L"

‘_

u.

”9‘9
\
‘n‘ "his.“

" \ \
K‘Q‘

l\“' '

\E

(mam c .. ..

x
Y

I I

(l
«h
‘mu

nmmm
,I
I4““

figure
ﬁnger:

unage

perhiri
ﬁngerp
ﬁgurati
postn'at
tude of
iniately
POOr-ql‘
beCorrt
a«‘Smissi
ln OIdE]
IQlJUSt ‘

NEOUth

ll?!)

Indl‘if’tto

24

   

(a) (b) (C)

Figure 1.4: Fingerprint matching: (a) and (b) are two impressions from the same
ﬁnger; (c) and (d) are two impressions from different ﬁngers.

image to make it more suitable for the feature extraction algorithm (Figure 1.4). The
performance of a feature extraction algorithm relies heavily on the quality of input
ﬁngerprint images. In practice, due to variations in impression conditions, ridge con-
ﬁguration, skin conditions (aberrant formations of epidermal ridges of ﬁngerprints,
postnatal marks, occupational marks), acquisition devices, and non-cooperative atti-
tude of subjects, etc., a signiﬁcant percentage of acquired ﬁngerprint images (approx-
imately 10% according to our experience) is of poor quality. The ridge structures in
poor-quality ﬁngerprint images are not always well-deﬁned and hence they can not
be correctly detected. This leads to a signiﬁcant number of spurious features as well
as missing features, which greatly degrades the performance of ﬁngerprint matching.
In order to ensure that the performance of the feature extraction algorithm will be
robust with respect to the quality of input digital ﬁngerprint images, an enhancement

algorithm which can improve the clarity of the ridge structures is necessary.

(iii) Integration of multiple biometric indicators - combining multiple biometric
indicators to improve the performance and applicability of a biometric system. Differ-

ent application domains impose different operational and performance requirements

”(3‘
3‘4“»? .
. i.
Ar
.‘C

, l

v . ' .9
I.“ ’«-t
,l

-_ “15'1"?"

.st ..

Figure
age.

on a bit
on ﬁng'
matchir
matic p
the idet
"realtir.
proving
a DECC‘SN
it. it is I]
is SUitab.
33.39”] v.
Ufa biou.

Prim) to

(ill fl}

25

 

Figure 1.5: Fingerprint image enhancement: (a) corrupted image; (b) enhanced im-
age.

on a biometric system. By and large, the personal identiﬁcation systems based solely
on ﬁngerprints are able to satisfy these requirements. However, since ﬁngerprint
matching is computationally demanding, it is impractical to require that an auto-
matic personal identiﬁcation system based solely on ﬁngerprints is able to establish
the identity of an individual by searching through a huge ﬁngerprint database in
“real-time.” Integration of multiple clues has been shown to be very effective in im-
proving the performance of pattern recognition systems [19]. In addition, although
a necessary requirement for a biometric characteristic is that each individual possess
it, it is not necessary that a particular biometric characteristic of a speciﬁc individual
is suitable for an automatic system. By using multiple biometric characteristics, the
system will be applicable on a larger target population. We have explored the design
of a biometric system which combines multiple biometric indicators (face and ﬁnger-

print) to overcome some of the limitations of a ﬁngerprint-based system (Figure 1.6).

(iu) ﬁngerprint classiﬁcation - assigning ﬁngerprints into a number of categories

 

based on
Sification
ﬁn.‘éerprii
ﬁngerprit
are th f;
Prints int.
pmfldes ;
Print that
greatly ret

databasg

1.5 C

The rest of

lilfflhodglog

26

 
 

    

r/V/ Calvin 94%-
l" ‘
Face Recognition Bob 5% '-
Alice 1%
Calvin 99.9%
é/IV/ Calvin 99%-
|
’ ‘ Fin e rint
5’”, Bob 0.1%—
Verlficatlon
Alice 0.9%—

 

Figure 1.6: Integration of face recognition and ﬁngerprint veriﬁcation.

based on the global ridge and furrow conﬁgurations (Figure 1.4). Fingerprint clas-
siﬁcation provides important information about the global pattern conﬁguration of
ﬁngerprints and, thus, plays an important role in ﬁngerprint matching. In fact, if two
ﬁngerprints are not in the same category, then it is certain that the two ﬁngerprints
are not from the same ﬁnger. Fingerprint classiﬁcation consistently assigns ﬁnger-
prints into categories according to the global pattern conﬁgurations, which essentially
provides an indexing mechanism for a ﬁngerprint database. Since automatic ﬁnger-
print matching is a computationally demanding task, this indexing mechanism can
greatly reduce the computational complexity in searching for a match in a ﬁngerprint

database, especially a large ﬁngerprint database.

1.5 Overview of the Thesis

The rest of the thesis is organized as follows. Chapter 2 introduces the history and

methodology of ﬁngerprint identiﬁcation. Chapter 3 presents the design of our au-

 

'Jigllllf ” ’1' 'l’

    
     
   
 

  

/ "it ‘*

«I

left loop right loop whorl

Figure 1.7: A ﬁngerprint image and ﬁve major ﬁngerprint Classes.
tomatic personal identiﬁcation system and related issues. Chapter 4 discusses ﬁn-
gerprint feature extraction and presents an improved minutiae extraction algorithm.
Chapter 5 emphasizes the need for ﬁngerprint enhancement and proposes a novel
ﬁngerprint image enhancement algorithm. Chapter 6 presents our minutiae matching
algorithm. Chapter 7 addresses the decision fusion scheme which integrates faces
and ﬁngerprints to achieve a better performance. Chapter 8 discusses the problem
of ﬁngerprint image classiﬁcation and presents a novel ﬁngerprint image classiﬁcation
algorithm. Chapter 9 discusses the problem of performance evaluation for biometric
systems. Also, experimental results of our system on several data sets are reported.
Finally, chapter 10 contains a summary of our research, discusses the limitations of

our current algorithms, and gives a list of problems which should be explored by other

researchers

1.6 S'

Accurate 3
domains su:
metrics. Wll
or behavior.
entiating be
methods sur
is one of the
metric tetrlltl
ObijCtiYe 0“
fun." autollla

ﬁngerprints.

28

researchers.

1.6 Summary

Accurate automatic personal identiﬁcation is critical in a wide range of application
domains such as national ID card, electronic commerce, and automated banking. Bio-
metrics, which refers to automatic identiﬁcation of a person based on her physiological
or behavioral characteristics, is inherently more reliable and more capable in differ-
entiating between an authorized person and a fraudulent impostor than traditional
methods such as passwords and PIN numbers. Automatic ﬁngerprint identiﬁcation
is one of the most reliable biometric technology among the nine different major bio-
metric techniques which are either currently available or are under investigation. The
objective of our research is to design a biometric system which is capable of achieving
fully automatic “personal identiﬁcation” with a high level of conﬁdence using mainly

ﬁngerprints.

chz

pin

in the C
erall}. 11;
prints. E
sjorls 0f
the fOllO
print clt;
ﬁngertip
a ﬁnger?
ration. f
ﬁnger. F
tiﬁt’atiorl
Autorrlat
signiﬁcar.

heatiorl s

Chapter 2

Fingerprint Identiﬁcation

In the context of ﬁngerprint identiﬁcation, fingerprints or simply prints are gen-
erally used to refer to the impressions of human ﬁngers. In this thesis, ﬁngerprints,
prints, and ﬁngerprint impressions are used synonymously to indicate the impres-
sions of ﬁngertips. Operationally, ﬁngerprint identiﬁcation can be decomposed into
the following three fundamental tasks [103]: (i) ﬁngerprint acquisition, (ii) ﬁnger-
print classiﬁcation, and (iii) ﬁngerprint matching. Fingerprints are acquired from
ﬁngertips or impressions of the ridges and furrows. Fingerprint classiﬁcation assigns
a ﬁngerprint into a certain category according to its global ridge and furrow conﬁgu-
ration. Fingerprint matching determines whether two ﬁngerprints are from the same
ﬁnger. Fingerprint identiﬁcation is one of the most reliable and valid personal iden-
tiﬁcation method, which has been in use for a long time [39, 53, 108, 85, 103, 106].
Automatic ﬁngerprint identiﬁcation has been studied since the early 1970’s and a
signiﬁcant progress has been made. A large number of automatic ﬁngerprint identi-

ﬁcation systems for both forensic applications and civilian applications are installed

29

worldwide. l

problem [85-

2,1 His

Humans have
37.112124. lt
archaeological
Although these

to Show that l

 

awareness (locs'

lt was not 11
nique was ﬁrst
Nehemiah Gre“
the ridge. furro‘
large number of
is. In 1788. a 1
made by Mayer
tiﬁed and charm
ht ﬁngerprint a:
important mllt'sl
[ﬁle in 1823. prr

2e ' .~
. rpunts into my

30

worldwide. However, fully automatic ﬁngerprint identiﬁcation is still a challenging

problem [85, 106].

2.1 History of Fingerprint Identiﬁcation

Humans have used ﬁngerprints for a very long period of time [39, 53, 108, 85, 103, 26,
37, 112, 124, 109, 135]. Human ﬁngerprints have been discovered on a large number of
archaeological artifacts and historical items (refer to Figure 2.1 for some examples).
Although these archaeological artifacts and historical items provide sufﬁcient evidence
to show that ancient people were aware of the individuality of ﬁngerprints, such
awareness does not appear to have any scientiﬁc basis [85, 103].

It was not until the late 16th century that the modern scientiﬁc ﬁngerprint tech-
nique was ﬁrst initiated [39, 53, 108, 85, 103]. In 1864, English plant morphologist,
Nehemiah Grew, published the ﬁrst scientiﬁc paper reporting his systematic study on
the ridge, furrow, and pore structure in ﬁngerprints (Figure 2.2) [85]. Since then, a
large number of researchers have invested huge amounts of effort on ﬁngerprint stud-
ies. In 1788, a detailed description of the anatomical formations of ﬁngerprints was
made by Mayer [103] in which a number of ﬁngerprint ridge characteristics were iden-
tiﬁed and characterized (Figure 2.3). Starting in 1809, Thomas Bewick began to use
his ﬁngerprint as his trademark (Figure 2.4), which is believed to be one of the most
important milestones of the scientiﬁc study of ﬁngerprint identiﬁcation [103]. Purk-
inje, in 1823, proposed the ﬁrst ﬁngerprint classiﬁcation scheme which classiﬁed ﬁn-

gerprints into nine categories according to the ridge conﬁgurations (Figure 2.5) [103].

 

me. .r m.

Neoll'

{Carl

l

5....uu A1 *'-a.aum.-"wnlv-ll£~mu4nduh“!

Figure
imprei
Stand]
[0 5111-:
were i

31

  

  

hi1 . M. W ,
Neolithic Carvings Standing Stone (Goat Is-
(Gavrinis Island) [103] land, 2,000 BC.) [85]

    

A Chinese clay seal (300 An _ . rm—
B_C_) [85] presswn on a Palestinian
lamp (400 AD.) [103]

Figure 2.1: Examples of archaeological ﬁngerprint carvings and historic ﬁngerprint
impressions; although the impressions on the Neolithic carvings and the Goat Island
standing stones might not be used to indicate the identity, there is sufﬁcient evidence
to suggest that the Chinese clay seal and the impressions on the Palestinian lamp
were used to indicate the identity of the providers.

 

Figure 2.2: Dermatoglyphics drawn by Grew [103].

 

 

Figure 2.4: Trademarks of Thomas Bewick [85].

g - "
.r'. i
I» ‘ I ‘
x” _ _- e

I
f:
g i
,1... l
i! "i
l"? 'I ‘1
K\
Figure

Henry Fauld. i

 

based on his ow
tit-ed ﬁngerprint
the foundation
Francis Gallon t
minutiae featurt
in ﬁngerprint id
twol

ndlan assist

 

 

Figure 2.5: The nine patterns illustrated in Purkinje’s thesis [103].

Henry Fauld, in 1880, ﬁrst scientiﬁcally suggested the individuality of ﬁngerprints
based on his own observation. At the same time, Herschel asserted that he had prac-
ticed ﬁngerprint identiﬁcation for about 20 years [85, 103]. This discovery established
the foundation of modern ﬁngerprint identiﬁcation. In the late 19th century, Sir
Francis Galton conducted an extensive study on ﬁngerprints [53]. He introduced the
minutiae features for single ﬁngerprint classiﬁcation in 1888. An important advance
in ﬁngerprint identiﬁcation was made in 1899 by Edward Henry, who (actually his
two Indian assistants) established the well known “Henry system” of ﬁngerprint clas-
siﬁcation [85, 106]. By the early 20th century, the formations of ﬁngerprints were well
understood. The biological principles of ﬁngerprints are now well established [103]

and are summarized below:

. [1.

u j}

o T”

m t’

The ﬁt“
second P
In th
valid Per:
Fingerl)ri
database:
[Hg latent
were (19)"?
1924 with
With 1
gerprint (l
feasible. I:
now Stand:
titration r
experts we

the early 1!

34

0 Individual epdiermal ridges and furrows have diﬁerent characteristics for differ-

ent ﬁngerprints.

o The conﬁguration types are individually variable, but they vary within limits

which allow for a systematic classiﬁcation.

0 The conﬁgurations and minute details of individual ridges and furrows are per-

manent and unchanging.

The ﬁrst principle constitutes the foundation of ﬁngerprint identiﬁcation and the
second principle constitutes the foundation for ﬁngerprint classiﬁcation.

In the early 20th century, ﬁngerprint identiﬁcation was formally accepted as a
valid personal identiﬁcation method and became a standard routine in forensics [85].
Fingerprint identiﬁcation agencies were setup worldwide and criminal ﬁngerprint
databases were established [85]. Various ﬁngerprint identiﬁcation techniques, includ-
ing latent ﬁngerprint acquisition, ﬁngerprint classiﬁcation, and ﬁngerprint matching
were developed. For example, the FBI ﬁngerprint identiﬁcation division was setup in
1924 with a database of 810,000 ﬁngerprints [108].

With the rapid expansion of ﬁngerprint identiﬁcation in forensics, operational ﬁn-
gerprint databases became so huge that manual ﬁngerprint identiﬁcation became in-
feasible. For example, the total number of ﬁngerprints in the FBI ﬁngerprint database
now stands at 70 million from its original number of 810,000. With thousands of iden-
tiﬁcation requests being received daily, even a team of more than 1,300 ﬁngerprint
experts were not able to provide timely responses to these requests [85]. Starting in

the early 1960’s, FBI, Home Ofﬁce in the UK, and Paris Police Department began to

In

35

invest a large amount of effort to develop automatic ﬁngerprint identiﬁcation systems
(AFIS) [85, 108]. Based on the observations of how human ﬁngerprint experts perform
ﬁngerprint identiﬁcation, three major problems in designing AFISs were identiﬁed and
investigated: (i) digital ﬁngerprint acquisition, (ii) local ridge characteristic extrac-
tion, and (iii) ridge characteristic pattern matching. Their efforts were so successful
that a large number of commercial AFIS are currently installed and in operation in
law enforcement agencies worldwide. These systems have greatly improved the op-
erational productivity of these agencies and reduced the cost of hiring and training
human ﬁngerprint experts.

Recently, due to the rising demand in our increasing electronically inter-connected
society for automatic personal identiﬁcation and the success of various AFIS instal-
lations in forensics, automatic ﬁngerprint identiﬁcation technology has rapidly grown
beyond forensic applications into civilian applications [106]. In fact, ﬁngerprint based
biometric systems are so popular that they have almost become the synonym of bio-

metric systems [44].

2.2 Fingerprint Acquisition

Depending on whether the acquisition process is online or ofﬂine, a ﬁngerprint may
be either (i) an inked ﬁngerprint or (ii) a live-scan ﬁngerprint.

Inked ﬁngerprint is a term which is used to indicate that the ﬁngerprint image
is obtained from an impression of the ﬁnger on an intermediate media such as pa-

per. Generally, inked ﬁngerprint is obtained using the rolled method, called rolled

36

   

(b) 7' h (c)

Figure 2.6: Comparison of different ﬁngerprint impressions: (a) a rolled ﬁngerprint
(from NIST 4 database); (b) a live-scan ﬁngerprint (captured with a scanner manu-
factured by Digital Biometrics); (c) a latent ﬁngerprint.

inked ﬁngerprint. An example of a rolled inked ﬁngerprint is shown in Figure 2.6 (a).
Typically, the ﬁrst step in capturing a rolled impression of a ﬁngerprint is to place
a few dabs of ink on a slab and rolling it out smoothly with a roller until the slab
is covered with a thin, even layer of ink. Then the ﬁnger is rolled from one side of
the nail to the other side over the inked slab which inks the ridge patterns on top
of the ﬁnger completely. After that, the ﬁnger is rolled on a piece of white paper
so that the inked impression of the ridge pattern of the ﬁnger appears on the white
paper. Rolled inked ﬁngerprints impressed on paper can be electronically scanned
into digital rolled ﬁngerprints using optical scanners or video cameras. So far, rolled
acquisition method remains the most popular acquisition technique. In fact, it has
been essentially a standard technique for ﬁngerprint acquisition for more than a bun-
dred years [108, 103]. Rolled inked ﬁngerprints tend to have a larger area of valid
ridges and furrows, but have large deformations due to the inherent nature of the
rolled acquisition process. Direct feedback is not available to the subject to control

the acquisition process which, in turn, may result in difﬁculties in quality control.

37

Acquisition of rolled ﬁngerprints is cumbersome and slow. In the context of an auto-
matic personal identiﬁcation system, it is both infeasible and socially unacceptable to
use the rolled inked method to acquires ﬁngerprints in the Operational phase although
it may be feasible to use the rolled inked method in the enrollment phasel.

In forensics, a special kind of inked ﬁngerprints, called latent ﬁngerprints, is of
great interest. Constant perspiration exudation of sweat pores on ﬁngerprint ridges
and intermittent contact of ﬁnger with other parts of human body and various objects
leave a ﬁlm of moisture and/or grease on the surface of ﬁngers. In touching an
object, the ﬁlm of moisture and/or grease may be transferred to the object and
leave an impression of the ridges thereon. This type of ﬁngerprints is called latent
ﬁngerprint. Latent ﬁngerprints are very important in forensics. Actually, a major
task in forensic ﬁngerprinting application is searching and reliably recording latent
ﬁngerprints [85, 103], which is beyond the scope of this thesis. An example of a latent
ﬁngerprint is shown in Figure 2.6 (c).

The live-scan ﬁngerprint is a collective term for a ﬁngerprint image directly ob-
tained from the ﬁnger without the intermediate step of getting an impression on a
paper. A number of sensing mechanisms can be used to sense the ridge and fur-
rows of the ﬁnger impressions, including (i) optical frustrated total internal reﬂection
(FTIR) [3, 59, 137, 60, 77], (ii) ultrasonic total internal reﬂection [126], (iii) optical
total internal reﬂection of edge-lit holograms [2, 52, 129], (iv) thermal sensing of the
temperature differential (across the ridges and valleys) [83, 38], (v) sensing of differ-

ential capacitance [93, 130, 146], and non-contact 3D scanning [88]. Scanners based

 

1For example, Master Card relies on inked impressions for enrollment.

38

   

(b)

Figure 2.7: FTIR ﬁngerprint scanners: (a) manufactured by Identiar, (b) manufac—
tured by Digital Biometrics.

on these physical processes can be used to acquire the impressions, called live-scan
ﬁngerprints, of human ﬁngers directly. These acquisition methods eliminate the in-
termediate digitization process of inked impressions and makes it possible to build
on-line systems. Depending on the clarity of ridge structures of scanned ﬁngers and
acquisition conditions, acquired live-scan ﬁngerprints vary in quality. However, since
there exists a direct feedback on such type of devices, it is relatively easier to control
the quality of acquired ﬁngerprints.

A live—scan ﬁngerprint is usually obtained using the dab method, in which a ﬁnger
is impressed on the acquisition surface of a device without rollingz. A dab live-
scan ﬁngerprint only captures the ridges and furrows that are in contact with the
acquisition surface. Therefore, it tends to have a smaller area of valid ridges and

furrows and smaller deformations than a rolled ﬁngerprint.

The most popular technology to obtain a live-scan ﬁngerprint image is based on

 

2R is also possible to capture a rolled live—scan ﬁngerprint. Some vendors are trying to develop
such ﬁngerprint scanners.

39

      

() i I

Figure 2.8: Solid state ﬁngerprint chips: (a) differential capacitance ﬁngerprint chip
manufactured by Harris [130]; (b) differential capacitance ﬁngerprint chip manufac-
tured by Veridicom [146]; (c) thermal ﬁngerprint chip manufactured by Thomson
CSF [38].

optical frustrated total internal reﬂection (F TIR) concept [59, 125]. When a ﬁnger is
placed on one side of a glass platen (prism), ridges of the ﬁnger are in contact with
the platen, while the valleys of the ﬁnger are not in contact with the platen. The rest
of the imaging system essentially consists of an assembly of an LED light source and
a CCD placed on the other side of the glass platen. The laser light source illuminates
the glass at a certain angle and the camera is placed such that it can capture the
laser light reﬂected from the glass. The light which is incident on the plate at the
glass surface touched by the ridges is randomly scattered while the light incident at
the glass surface corresponding to valleys suffers total internal reﬂection, resulting
in a corresponding ﬁngerprint image on the imaging plane of the CCD. An example
of live-scan ﬁngerprint is shown in Figure 2.6 (b). Figure 2.7 shows the two FTIR
ﬁngerprint scanners used in our prototype systems.

Optical scanners are too large to be readily integrated in a number of applications
such as laptop security, cellular phone security, and notebook security. Recently, a

number of different types of compact solid state ﬁngerprint chips have become avail-

40

able. The quality of the images acquired using these solid state chips is comparable
to the quality of images acquired using optical scanners. These solid state chips can
be manufactured with a very low cost if manufactured in a large quantity. Figure 2.8
shows the three different types of solid state ﬁngerprint chips which are commercially

available.

2.3 Fingerprint Classiﬁcation

Global patterns of ridges and furrows in the central region of ﬁngerprints form special
conﬁgurations, which have a certain amount of intraclass variability. But these varia-

tions are sufﬁciently small which allows for a systematic classiﬁcation of ﬁngerprints.

T ypelines

 

 

Figure 2.9: Pattern area and typelines.

41

In regard to ﬁngerprint classiﬁcation, only a portion of a ﬁngerprint, called pat-
tern area is of interest [108]. The pattern area of a ﬁngerprint consists of those ridges
encircled by typelines which is deﬁned as the two innermost ridges that form a diver-
gence tending to encircle or encompass the central portion of a ﬁngerprint (Figure 2.9
shows an example of pattern area and typelines) [108]. The pattern areas of loop
or whorl types of ﬁngerprints contain two types of singular points, (i) delta and (ii)
core. The delta, sometimes called the outer terminus, is deﬁned as the point of ridge
at or in front of and nearest to the center of the divergence of the typelines. It may
be a ridge dot, a short ridge, the forking point of a bifurcated ridge, ending ridge,
or the point on the ridge running in front of the divergence nearest to the center
between the innermost diverging ridges. Examples of delta conﬁgurations are shown
in Figure 2.10. The core, sometimes called the inner terminus, is deﬁned as the spe-
ciﬁc point located on or within the innermost suﬂ‘iciently curved ridges. Due to large
variations in the formations of curved ridges, the rules for the selection of the core are
very complicated. Figure 2.11 shows several examples of core conﬁgurations. Another
important concept in both ﬁngerprint classiﬁcation and ﬁngerprint matching is ridge
count, which may be roughly deﬁned as the number of ridges that touch or cross an
imaginary line drawn between the core and delta. Due to the high complexity of
ridge conﬁgurations, a precise deﬁnition of ridge count is difﬁcult. Three simple ridge
counting examples are shown in Figure 2.12. In this thesis, we extend the deﬁnition
of ridge count to be the number of ridges that touch or cross an imaginary line drawn
between a given pair of minutiae.

With the above deﬁnitions, ﬁngerprint categories can be described as follows. A

42

 

Figure 2.10: Examples of delta conﬁguration [103].

 

Figure 2.11: Examples of core conﬁguration [103].

 

Figure 2.12: Ridge counting [103].

43

loop is the type of ﬁngerprint in which “one or more of the ridges enter on either
side, recurve, touch or pass an imaginary line drawn from the delta to the core, and
terminate or tend to terminate on or toward the same side from which such ridge or
ridges entered” [108]. There are three essential ingredients for classifying a ﬁngerprint
into a loop: (i) at least one sufﬁciently recurve ridge, (ii) a delta, and (iii) nonzero
ridge count. L00ps may be further divided into lunar loop and radial loop depending
on the orientation tendency and ﬁngers. About 60-65% of human ﬁngerprints belong
to this category [108, 103].

A whorl is that type of ﬁngerprint in which “at least two deltas are present with
a recurve in front of each” [108]. This deﬁnition, though very general, captures the
essence of the category. Whorls may be further divided into four sub-categories: (i)
plain whorl, (ii) central pocket loop, (iii) double loop, and (iv) accidental. About
30-35% of human ﬁngerprints belong to this category [108, 103].

Arch is a special type of ﬁngerprint conﬁguration. Less than 5% of all ﬁngerprints
are arches [108, 103]. Arch may be divided into two sub-categories: (i) plain arch
and (ii) tented arch. A plain arch is that type of ﬁngerprint in which ridges enter one
side and ﬂow or tend to ﬂow out the other with a rise of wave in the center [108]. In
a tented arch, most of the ridges enter one side and ﬂow or tend to ﬂow out the other
with a rise of wave in the center and the rest of the ridges form a deﬁnite angle, or
up—thrush [108].

Fingerprint classiﬁcation still remains a very difﬁcult problem for both human
experts and automatic systems [108, 103]. On the one hand, only a limited number of

major ﬁngerprint categories have been identiﬁed and the distribution of ﬁngerprints

       
 

fa?” \ \

. «7'

r-‘f‘ﬁ ‘
’ My:
4; / ”:53-‘: "Sn.
1' . \
/ .

" ._.'»y;
I
// \\§\\

. / If” _;\ \\\.,
' ’ \‘ \
u

  

   

        
 

  

    

(C)

Figure 2.13: Examples of ﬁngerprints that are difﬁcult to classify; (a) tented arch;
(b) a loop; (c) a whorl; it seems that all the ﬁngerprints shown here should be in the
loop category.

into these categories is not uniform. On the other hand, as we mentioned above,
there exists a large variation in ﬁngerprint conﬁgurations. The deﬁnition of each
ﬁngerprint category is both complex and vague. A human inspector needs a long
period of experience to reach a satisfactory performance in performing ﬁngerprint
classiﬁcation. In fact, ﬁngerprint classiﬁcation is more like an art than a science,
since the long period of experience can only be gained by practice [103]. Figure 2.13

shows examples of ﬁngerprints that are difficult to classify.

2.4 Fingerprint Matching

Although ﬁngerprint category information and other global pattern conﬁgurations
such as the number and positions of core and delta and ridge count may indicate,
to a certain extent, the individuality of ﬁngerprints, the uniqueness of a ﬁngerprint
is exclusively determined by the local ridge characteristics and their relationships.

Fingerprint matching depends on the comparison of local ridge characteristics and

45

their relationships to determine the individuality of ﬁngerprints. A total of one hun-
dred and ﬁfty different local ridge characteristics, called minute details, have been
identiﬁed [103]. These local ridge characteristics are not evenly distributed. Most of
them depend heavily on the impression conditions and quality of ﬁngerprints and are
rarely observed in ﬁngerprints. The two most prominent ridge characteristics, called
minutiae, are (i) ridge ending and (ii) ridge bifurcation. A ridge ending is deﬁned as
the ridge point where a ridge ends abruptly. A ridge bifurcation is deﬁned as the ridge
point where a ridge forks or diverges into branch ridges. Minutiae in ﬁngerprints are
generally stable and robust to the ﬁngerprint impression conditions. Normally, they
can be easily identiﬁed. Examples of minutiae are shown in Figure 2.14. For a given
ﬁngerprint, a minutia can be characterized by its type, its x and y coordinates, and

its direction whose deﬁnition is also shown in Figure 2.14.

 

-- -- —"/ --9_---

#
Ridge Ending Ridge Bifurcation

(a) Ridge Ending Ridge Bifurcation

 

 

(b)

Figure 2.14: Minutiae; (a) example of minutiae; (b) characterization of minutiae.

If two ﬁngerprints belong to the same category and have a sufﬁcient number of
minute details that are identical, then it can be concluded conﬁdently that they are
from the same ﬁnger. Generally, in order to determine that two ﬁngerprints are from

the same ﬁnger, four factors must be evaluated: (i) general pattern conﬁguration

46

 

Figure 2.15: Fingerprint matching result in which 18 identical minute details are
identiﬁed [103].

agreement which means that two ﬁngerprints must be of the same pattern conﬁg-
uration, (ii) qualitative concordance which requires that the corresponding minute
details must be identical, (iii) quantitative factor which speciﬁes that at least a
certain number (a minimum of 12 according to the forensic guidelines in the United
States) of corresponding minute details must be found, and (iv) relationship of minute
details which speciﬁes that the corresponding minute details must be identically inter-
related. In practice, complex identiﬁcation protocols have been deﬁned for ﬁngerprint
matching. These protocols are carefully designed based on the knowledge of ﬁnger-
print experts. A detailed ﬂow chart is available to guide ﬁngerprint examiners in
performing ﬁngerprint matching.

Although various protocols for ﬁngerprint matching may be different in the con-
cept deﬁnition and decision making process, the major steps in the associated ﬂow
charts are essentially the same. Typically, a ﬁngerprint matching process is executed

with an iterative three-stage process. First of all, two ﬁngerprints to be matched

47

are compared to determine whether they are similar to each other in global pattern
conﬁguration. If the two ﬁngerprints are totally different in terms of global pattern
conﬁguration, it is impossible that these two ﬁngerprint are from the same ﬁnger.
Next, a pattern alignment process is conducted in which several salient feature points
are ﬁrst located from the ﬁngerprints and, then, an approximate alignment of the
ﬁngerprints is performed. Finally, a matching process is conducted in which corre-
sponding minute details are evaluated in the valid ﬁngerprint pattern areas and a
decision is made based on the identiﬁed corresponding pairs and pattern conﬁgu-
ration. Due to variations in ﬁngerprint quality, impression deformation, ﬁngerprint
ridge conﬁguration, and skin conditions, several steps in ﬁngerprint matching pro-
tocols can not be clearly and precisely deﬁned. Fingerprint examiners must depend
heavily on their experience to make decisions. For example, even the most prominent
minute details, minutiae, can not be identiﬁed easily. Some ridge bifurcations may be
inevitably identiﬁed as ridge endings if the fingerprint impression pressure is too low.
Therefore, although ﬁngerprint matching is practiced daily by thousands of opera-
tional ﬁngerprint experts around the world, ﬁngerprint matching is still an art instead
of a science. Experience plays a key role in manual ﬁngerprint matching. Figure 2.15
shows an example of ﬁngerprint matching result in which 18 corresponding minute

details have been identiﬁed.

Chapter 3

System Design

The design of a biometric system can be characterized at two different levels: (i)

system level and (ii) algorithm level.

3.1 System Level Design

The major issues at the system level design include which biometric characteristics
should be used, which operational mode should be used, how to acquire a raw digital
representation of the biometric characteristic, the system architecture, and other
issues such as ergonomics, physical size, power supply, weight, cost, administrative
and maintenance costs, and environmental inﬂuence.

The selection of a biometric characteristic is mainly determined by the practical
requirements, especially performance requirements. The practical performance re-
quirement is very much application related. On the one extreme, from the view point
of system accuracy, a low false reject rate may be the primary objective. For example,

48

49

in some forensic applications such as criminal identiﬁcation, it is the false reject rate
that is a major concern and not the false acceptance rate: i.e., we do not want to
miss a criminal even at the risk of examining a large number of potential matches
identiﬁed by the biometric system. In forensic applications, it is the human expert
that will make the ﬁnal decision anyway. On the other extreme, the false reject rate
may be the most important factor in a highly secure access control application, where
the primary objective is deterring impostors although we are concerned with the pos-
sible inconvenience to the legitimate users due to a high false reject rate. In between
these two extremes are several civilian applications, where both false acceptance rate
and false reject rate need to be considered. For example, in applications like ATM
card veriﬁcation, false reject rate is more important than the false acceptance rate
- a false acceptance means a loss of several hundred dollars while a high false reject
rate may irritate the customers. Obviously, even in civilian applications, a high false
acceptance rate is not desirable since the main advantage of automation is defeated
if human experts are involved in examining a long list of false positives. Ideally, we
would like to have a reliable binary output - Is the subject in the system database
or not? On the other hand, a high false reject rate is also not desirable since that
would let in an impostor easily. But the risks involved in civilian applications are
not as severe as in a criminal or security system. Figure 3.1 graphically depicts the
situation discussed above.

Different biometric characteristics possess different discrimination capability in
terms of system accuracy. At the one extreme, we have biometric characteristics such

as face and dynamic signature that are inherently better at accepting genuine indi-

50

High Security Access Control

   
   

Civilian Applications

False Reject Rate

Criminal Identification

 

 

>
False Acceptance Rate

Figure 3.1: Different applications have different requirements for the FAR and FRR.

viduals, but do not perform well in deterring impostors. For example, an individual
may be easily mistaken due to changes in makeup, hair style, lighting conditions,
background, etc. At the other extreme, we have the biometric characteristics such as
retinal scans, ﬁngerprints, and iris that are better at preventing impostors but are less
efficient in identifying genuine individuals. Somewhere in between these two extremes
are those biometric characteristics such as hand geometry and hand vein which per-
form about the same in deterring impostors and accepting genuine individuals [106].
Generally, there is no rule of thumb to indicate which biometric technique should be
used for a given application. A realistic design strategy is to examine what are the
system requirements, assess which technique is suitable for the given application, and

then tune the biometric system to satisfy the practical performance requirements.

As mentioned in Chapter 1, a biometric system may operate either in (i) veriﬁca-

tion mode or (ii) identiﬁcation mode. It is more difficult to design an identiﬁcation

51

system than to design a veriﬁcation system [106]. For a veriﬁcation system, the
major challenge is the system accuracy. It is usually not very difﬁcult to meet the
response time requirement in a veriﬁcation system, because only one-to-one compar-
ison is conducted. However, for an identiﬁcation system, both accuracy and speed
are critical. An identiﬁcation system needs to explore the entire template database
to establish an identity. Thus, more requirements are imposed on the feature extrac-
tor and, especially, the feature matcher. Inherently, some biometric approaches are
more feasible for operating in the identiﬁcation mode than the others. For exam-
ple, the individuality of ﬁngerprints is mainly determined by the local minute details
and their relationship. To automatically match a pair of unregistered ﬁngerprints
is computationally expensive. A linear search of the entire template database even
for a small size database is not acceptable. Fingerprint classiﬁcation may provide
a partial solution to index a ﬁngerprint database. However, it is doubtful that an
one-ﬁnger-indexing mechanism based solely on the global ﬁngerprint conﬁguration,
which is difﬁcult to be registered in a fully automatic personal identiﬁcation applica-
tion, can reach the desirable accuracyl. Therefore, although a signiﬁcant progress has
been made in ﬁngerprint identiﬁcation, it is still not practical to conduct a real-time
search even on a relatively small size ﬁngerprint database of several thousand images
without dedicated hardware matchers and an efficient indexing mechanism. On the
other hand, it is feasible to design a face recognition system Operating in the iden-

tiﬁcation mode, because (i) face comparison is a relatively less expensive operation,

 

lAn indexing mechanism based on multiple ﬁngers such as the Henry System which is based on
ten-ﬁnger classiﬁcation is widely used in AFIS [85]. However, using all ten ﬁngers to make a personal
identiﬁcation may not always be acceptable in a civilian application.

52

and (ii) efﬁcient indexing techniques are available and the recognition performance
is admissible [139].

Choosing the operational mode for a biometric system depends mainly on practical
requirements. Generally, an identiﬁcation system is more desirable than a veriﬁcation
system. However, an identiﬁcation system usually requires more resources and, thus,
costs more. In addition, an identiﬁcation system may not always be technically
practical. For example, an ATM card identiﬁcation system needs to connect all the
ATM machines around the world, establish a template database of millions of records,
and it should be able to search through millions of template records in real time for
each access authentication.

Data acquisition is one of the critical processes in a biometric system. The quality
of the acquired data determines the performance of the entire system. However,
the selection of a data acquisition device depends on practical requirements such as
availability, cost, and size. There is no rule of thumb to determine which device
should be used. In this thesis, we concentrate on online applications. Thus, we want
a device which is able to acquire the ﬁngerprint images directly from human ﬁngers.

The biometric system architecture depends on the application. Logically, as men-
tioned in Chapter 1, a biometric system mainly consists of two modules: enrollment
module and identiﬁcation module. Each module consists of a number of sequential
feed-forward submodules, which accept inputs from the previous submodule(s) and
produce intermediate results which are, in turn, treated as inputs to the next sub-
module(s). The design of these submodules depends on the biometrics being used. It

is tightly related to the algorithm level design.

53
3.2 Algorithm Level Design

Given the system level speciﬁcations and the practical requirements, the major tasks
in algorithm level design are: (i) feature extraction and (ii) matching. Feature ex-
traction is responsible for extraction of representative features from the raw input
data. Matching is responsible for determining whether two sets of representative fea—
tures are extracted from the same source. The algorithm level design also consists of
other modules such as database management, quality control, encryption, and user

interface, which are beyond the scope of this thesis.

The ﬁngerprint representation (features) constitutes the essence of algorithm level
design and determines almost all aspects of the recognition mechanism. A representa-
tion should have the following two properties: (i) saliency and (ii) suitability. Saliency
means that a representation should contain enough class-speciﬁc (individual) infor-
mation about the input data. Suitability means that the representation can be easily
extracted, stored in a compact fashion, and is useful for matching. Saliency and suit-
ability properties are not highly correlated. A salient representation is not necessarily
a suitable representation. There is no general representation scheme that is suitable

for all biometrics.

A matching algorithm is generally based on a similarity function to determine
whether two sets of features are from the same source. For a given representation,
deriving a similarity function is a very difﬁcult problem because of intraclass and
interclass variations. Typically, there is no systematic way to derive a similarity

function.

54

For automatic ﬁngerprint identiﬁcation, it is well known that the acquired im-
age has redundancy and tends to have large intraclass variations. Therefore, the
ﬁngerprint image itself is not a desirable representation. Currently, the two major
representation schemes for automatic ﬁngerprint identiﬁcation are: (i) image-based
representation and (ii) feature—based representation. The image-based representation
assumes that the individuality of ﬁngerprints may be exclusively determined in the
spatial or the frequency domain. For example, a ﬁngerprint can be represented by
its Fourier spectrum. Due to orientation-speciﬁc ﬂow pattern of ridges in the ﬁnger-
prints, a concise representation may be obtained using the Fourier spectrum. The
image-based representations usually require that the input image be registered. In
practice, registering an input image is as difﬁcult as matching itself. Therefore, al-
though several image-based ﬁngerprint representations have been pr0posed in the
literature [51, 50, 9, 1, 7, 73, 74], the validity of these representations is still far from
established.

The feature-based representation originates from the fact that if a pair of ﬁn-
gerprints belong to the same category (e.g., arch, loop, whorl, etc.) and share a
sufﬁciently large number of signiﬁcant local ridge characteristics then it can be con-
cluded conﬁdently that they are from the same ﬁnger. Each ﬁngerprint has a small
number of signiﬁcant local ridge characteristics. So, a compact and efﬁcient ﬁnger-
print representation can be obtained. In addition, feature-based representation is
widely accepted by the automatic ﬁngerprint identiﬁcation community. Its validity
has been proven by the large number of automatic ﬁngerprint identiﬁcation systems

in practical operation, which use this representation.

55

There are a large number of feature-based methods which utilize different types
of minute details, including minutiae, singular points, orientation ﬁeld, ridge counts,
ridge pores, and ridges [87, 5, 12, 13, 15, 29, 46, 48, 56, 58, 69, 116, 123, 134, 71,
85, 142, 152, 121, 147, 61, 66, 24, 151]. In this thesis, we focus on a minutiae-based
method, in which each ﬁngerprint is represented by a minutiae pattern and matching
is accomplished by determining the number of corresponding minutiae between the
two patterns. There are two major tasks in minutiae-based matching: (i) minutiae
extraction and (ii) minutiae matching. The objective of minutiae extraction is to
extract the minutiae from input ﬁngerprint images. Minutiae matching determines
whether an extracted minutiae pattern and a stored template pattern are from the

same ﬁnger or not.

3.3 Veriﬁcation System

We have designed a prototype veriﬁcation system which uses only ﬁngerprints in iden-
tity authentication - conducts only one-to—one comparison to authenticate whether
the identity claimed by an individual is true or not. It is designed for applications
such as ATM card security, smart card security, information system security, and
access control. The architecture of the prototype veriﬁcation system is shown in Fig-
ure 3.2. Logically, the system consists of four major components: (i) user interface,
(ii) system database, (iii) enrollment module, and (iv) veriﬁcation module. The user
interface provides a mechanism for a user to indicate her identity and present her

ﬁngerprints to the system. Depending on the application, the user interface can be

56

    
    
     
  

Enrollment Module

Minutia Quality

   

    
 
 

User Interface Extractor Checker

 

    
    
   

User Name

Minutia Minutia

  

 

Matcher

   

 

Extractor

Authentication Module

 

Figure 3.2: Architecture of the prototype automatic identity veriﬁcation system.

designed to ﬁt the practical requirements. In the prototype veriﬁcation system, FTIR
ﬁngerprint scanners are used to acquire the live-scan ﬁngerprint images. Figure 3.3

shows the graphical user interface (GUI) of our prototype veriﬁcation system.

The system database consists of a collection of records, each of which corresponds
to an authorized individual that has access to the system. Each record contains the
following ﬁelds which are used for authentication purpose: (i) the proﬁle of the indi-
vidual and (ii) ﬁngerprint templates of the individual. Depending on the application,
the system database may be either a physical database that resides in the system or
a virtual database with the record of each individual being carried on the magnetic
card issued to the individual. For example, in information system security, a database
that resides in the system may be used to store the record of each individual. At the

point-of-access, the individual indicates her identity by entering her user name and

 

Figure 3.3: Graphical user interface of the automatic identity veriﬁcation system.

the system retrieves the corresponding record from the database for authentication.
In ATM card authentication, it may not be practical to have a database which stores
all the records, since a large template database may become the point of failure.
Generally, it is more efficient to store records on magnetic cards and let each individ-
ual keep her own magnetic card. At the point-of-access, the individual presents her
magnetic card to indicate her identity and to provide the system her biometric tem-
plate(s). In this case, the template database is only a virtual database and there is
no physical database in the system. Both the number of templates and the quality of
the templates for each individual are important design parameters of the veriﬁcation
system. On the one hand, the larger the number of templates and better the quality
of the templates, the better the expected accuracy of the veriﬁcation system. On the

other hand, the larger the number of templates stored for each individual, the more

58

resources are required. There is obviously a trade-off.

The task of enrollment module is to enroll the proﬁle of each individual and
her ﬁngerprint(s) into the system database. In our system, a compact but expressive
biometric template which is generated by a feature extractor is used instead of the raw
digital representation of the biometric characteristic. When the ﬁngerprint images
and the proﬁle of an individual to be enrolled are fed to the enrollment module,
a minutiae extraction algorithm is ﬁrst applied to the ﬁngerprint images and the
minutiae patterns which are the valid representation of ﬁngerprints are extracted. A
quality checking algorithm is used to ensure that the records in the system database
only consist of ﬁngerprints of good quality, in which a signiﬁcant number (default
value is 25) of genuine minutiae may be detected. This is important, because there
is no point in using a ﬁngerprint with only a very small number of genuine minutiae
as a template to make an authentication. If a ﬁngerprint image is of poor quality,
it is enhanced to improve the clarity of ridge/ valley structures and mask out all the
regions where minutiae cannot be reliably recovered. The enhanced ﬁngerprint image
is fed to the minutiae extractor again.

The task of veriﬁcation module is to authenticate the identity of the individual who
intends to access the system. The individual to be authenticated indicates her identity
and places her ﬁnger on the ﬁngerprint scanner; a digital image of her ﬁngerprint is
captured; minutiae pattern is extracted from the captured ﬁngerprint image and fed
to a minutiae matching algorithm which matches it against the individual’s minutiae
templates stored in the system database to authenticate whether the identity claimed

by the individual is correct or not.

59

Enrollment lVIodule System Database

Face Eigenface l T:
Detection Projection Code ‘

Fingerprin " .1
Minutiae Quality Template .
Extractor Checker _. - : _-

 

 

User Interface Face Eigenface Database
Detection Projection Retrieval
‘ Minutiae Nlinutiae Decision
Extractor Matcher 1 Fusion

Identiﬁcation l\lodule

 

Figure 3.4: System architecture of the prototype integrated biometric identiﬁcation
system.

3.4 Identiﬁcation System

The identiﬁcation system we propose is mainly intended for the information system
security and access control. The goal is to design an identiﬁcation system that works
in a limited environment such as an intranet environment in medium or small enter-
prises. In our identiﬁcation system, we integrate multiple biometric characteristics

(ﬁngerprint and face) to improve the performance.

An important aspect that needs to be speciﬁed about an identiﬁcation system
is whether it is intended for conducting a fully automatic personal identiﬁcation or
not. An automatic ﬁngerprint identiﬁcation system (AF IS) is generally not deemed
as a fully automatic system, since the candidates retrieved by the system usually

need to be further examined by human experts to reach a ﬁnal decision. However,

60

for certain applications such as information system security, it is not feasible to let
human experts make the ﬁnal decision. Instead, the system has to be fully automatic
- the answer to a query needs to be either “yes” or “no”. In this thesis, we focus on
a fully automatic personal identiﬁcation.

We have deveIOped a prototype integrated biometric system that uses both facial
and ﬁngerprint information in conducting personal identiﬁcation. The architecture of
the system is shown in Figure 3.4. The system, in fact, consists of two subsystems, a
face recognition subsystem and a ﬁngerprint veriﬁcation subsystem, which are inte—
grated by a decision fusion module. The face recognition subsystem is responsible for
retrieving the top it possible matches of a query from the template database, where
n is usually a small number (n = 5 in our design). The ﬁngerprint veriﬁcation sub-
system is responsible for matching the ﬁngerprints of the top it possible matches of
the query and providing the corresponding ﬁngerprint matching scores. The decision
fusion module integrates the results from the face recognition and the results from
the ﬁngerprint veriﬁcation to establish the ﬁnal decision.

Like the prototype veriﬁcation system, logically, the prototype identiﬁcation sys-
tem also consists of four components: (i) user interface, (ii) system database, (iii)
enrollment module, and (iv) identiﬁcation module. The user interface is responsi-
ble for acquiring facial and ﬁngerprint images of the users who intend to access the
system. The system database stores the template records of all the individuals that
have access to the system. Unlike the veriﬁcation system, the system database in the
identiﬁcation system is always a physical database containing all the template records

of the individuals who are enrolled in the system.

61
3.5 Difﬁcult Problems

While a signiﬁcant progress has been made in automatic ﬁngerprint identiﬁcation,
there are still a number of research issues which need to be addressed to improve

system performance. Some of these problems are listed below:

0 Robust live-scan ﬁngerprint scanner
The quality of acquired ﬁngerprint images is critical to the performance of
an automatic ﬁngerprint identiﬁcation system. It is desirable to have a more
advanced live-scan ﬁngerprint scanner that is able to tolerate different types of

skins, cuts and bruises on the ﬁnger, and dryness of the impressed ﬁnger.

0 Fingerprint feature extraction
In practice, a signiﬁcant percentage of acquired ﬁngerprint images is of poor
quality. The performance of the feature extraction algorithms reported in the
literature on different types of poor quality ﬁngerprint images is still far from
desirable. To design a feature extraction algorithm that is robust to different
types of image degradations is a challenge. Examples of ﬁngerprint images that
are of very poor quality are shown in Figure 3.5. Figure 3.6 shows the extracted
minutiae obtained by our algorithm on a ﬁngerprint image of poor quality due

to high humidity of the impressed ﬁnger.

0 Fingerprint enhancement
Fingerprint enhancement can be used to recover the genuine ridge structures

from the corrupted images. However, to design a ﬁngerprint enhancement al-

62

(.M
Kim.

..
kilnm‘u-s.

 

Figure 3.5: Fingerprint images of very poor quality.

'.\1..\. J. ...
a b: t, ‘

 

,

image; white: correct minutiae-

Minutiae extraction from a poor quality

F i gure 3.6:

green: missing minutiae.

7

red; spurious minutiae'

 

Figure 3.7: Fingerprint impression deformation.

gorithm that is able to handle all types of noise sources is very difﬁcult.

Minutiae matching

The performance of minutiae matching algorithms depends heavily on the reli-
ability of minutiae and external alignment. To design a minutiae matching that
is able to handle different situations such as a large percentage of spurious and
missing minutiae and impression deformations is still a very difficult problem.

Figure 3.7 shows an example of an impression deformation.

Fingerprint classiﬁcation

Although a number of automatic ﬁngerprint classiﬁcation methods have been
proposed and some of them are used in operational AFISs, ﬁngerprint clas-
siﬁcation still remains one of the most difﬁcult problem for both humans and

machines. Currently, the ﬁngerprint classiﬁcation framework is mainly intended

64

for human experts which may not be optimal for an automatic system.

Fingerprint compression

Without a good ﬁngerprint compression scheme, storing hundreds of millions of
ﬁngerprints is too expensive. A wavelet-based method which has been proposed
as the standard for ﬁngerprint compression can compress a ﬁngerprint image by
a factor of 10 to 25 [31]. An algorithm that can reach even higher compression

ratio is an important research topic.

Computational complexity of matching

Computational complexity is a very important issue in automatic ﬁngerprint
identiﬁcation. It is a practical requirement that all veriﬁcations should be per-
formed in “real time” for all online applications. However, to achieve both high

accuracy and high speed poses another difﬁculty.

Integration of multiple biometric characteristics
An integration scheme that fuses multiple cues can be used to reach a desired

performance that can not be reached using only a single biometric technique.

Performance evaluation

In designing a biometric system, an important issue is the performance assess-
ment of the system: how to evaluate the performance of a given biometric
system or how to verify that a deployed biometric system satisﬁes certain per-
formance speciﬁcations? Unfortunately, the performance evaluation problem is

far from well established.

65

The above difﬁculties are not isolated, instead they are highly correlated with one
another. For example, if a perfect ﬁngerprint scanner is available, which can acquire
a very clear ﬁngerprint image even though the impressed ﬁnger does not have clear
ridge structuresz, then even a very simple minutiae extraction algorithm can locate
all the minutiae without any errors. In turn, the minutiae matching can be simpliﬁed

greatly.

 

2This is possible in theory by scanning the internal layers of friction skin.

Chapter 4

Minutiae Extraction

Minutiae extraction is to extract representative features, called minutiae, from the
input ﬁngerprint images. For automatic ﬁngerprint matching, a salient and suitable
representation of the input ﬁngerprint images is critical. Generally, this representa-
tion should have the following properties [120]: (i) retain the discriminating power
of raw digital ﬁngerprint images, (ii) compactness, (iii) amenable to matching al-
gorithms, (iv) robust to noise and distortions, and (v) easy to compute. The ﬁrst
property requires that a representation should be able to retain the individuality of
ﬁngerprints such that the identity can be reliablely established based solely on the rep-
resentation. The second property insists that the representation should not contain
information besides the individuality of the ﬁngerprints. The third property postu-
lates that the representation should be suitable for a matching algorithm. Clearly,
the representation should be sufﬁciently robust to the quality of ﬁngerprint images,
which is speciﬁed in the fourth property. Finally, the representation should not be
computationally demanding.

66

67

The pattern of the minute details of a ﬁngerprint forms a valid representation
of the ﬁngerprint. It is compact, amenable to matching algorithms, robust to noise
and distortions, and easy to compute. However, as indicated in chapter 2, most of
the 150 types of minute details in ﬁngerprint images are not stable and can not be
reliably identiﬁed. In an automatic ﬁngerprint matching, only the two most promi-
nent types of minute details are used for their stability and robustness: (i) ridge
ending and (ii) ridge bifurcation. In addition, since various data acquisition condi-
tions such as impression pressure can easily change one type of minutiae into the
other, we do not make any distinction between these two types of minutiae in our
system. So, each minutiae is completely characterized by the following parameters:
(i) :c-coordinate, (ii) y-coordinate, and (iii) orientation (refer to Figure 2.14 for their
deﬁnition). Typically, in a live-scan ﬁngerprint image of good quality, there are about
50-100 minutiae.

A good minutiae extraction algorithm should be both reliable and efﬁcient. Reli-
ability means that the minutiae extraction algorithm should (i) not create spurious
minutiae, (ii) not miss genuine minutiae, and (iii) be precise in minutiae position
localization and minutiae orientation computation. Reliable extraction of minutiae
from ﬁngerprint images is a difﬁcult task. When the quality of ﬁngerprint images is
good, the ridges and furrows in a ﬁngerprint, which alternate and ﬂow in a locally
constant direction, are well-deﬁned and are clearly differentiated from one another. In
such situations, ridge endings and ridge bifurcations which are essentially anomalies of
ridges can be easily identiﬁed and be precisely located from the binary ridges. Exam-

ples of good quality live-scan ﬁngerprint images are shown in Figure 4.1. However, in

68

 

Figure 4.1: Examples of good quality live—scan ﬁngerprint images, which were cap-
tured using a ﬁngerprint scanner manufactured by Digital Biometrics.

 

Figure 4.2: Examples of poor quality live-scan ﬁngerprint images, which were cap-
tured using a ﬁngerprint scanner manufactured by Digital Biometrics.

69

practice, a signiﬁcant percentage of acquired ﬁngerprint images (approximately 10%)
is of poor quality. The ridge structures in such kind of ﬁngerprint images are not al-
ways well-deﬁned and hence they can not be correctly extracted. Thus, a signiﬁcant
number of spurious minutiae may be created, a large percent of genuine minutiae may
be ignored, and large errors in their localization (position and orientation) may be
introduced. Examples of ﬁngerprint images of very poor quality, in which ridge struc-
tures are completely corrupted, are shown in Figure 3.5. Figure 4.2 shows examples
of poor quality live-scan images. The minutiae extraction result on a poor quality
ﬁngerprint image is shown in Figure 3.6. Depending on the quality, a poor ﬁnger-
print image can be either rejected or enhanced prior to the minutiae extraction. A
very poor ﬁngerprint image in which ridge structures are corrupted completely should
be rejected, while a poor ﬁngerprint image in which ridge structures are still visible
should be enhanced before minutiae extraction. A good minutiae extraction algo-
rithm should be able to tolerate, to a limited extent, the corrupted ridge structures
and degrade gracefully with the image quality.

It is critical that a minutiae extraction algorithm is able to Operate in “real-time”
in an online application such as ATM card security, smart card security, and access
control. However, there is a trade-off between speed and reliability. In order for a
minutiae extraction algorithm to be fast in speed, only simple operations which may
not be robust to image quality can be allowed. On the other hand, in order for the
minutiae extraction algorithm to be robust, complex operations which are usually
computationally demanding are needed. A practical design strategy is to select a set

of Operations that are efﬁcient in both speed and reliability.

70
4.1 Related Work

Extensive studies have been conducted on minutiae extraction [25, 12, 85, 100, 27,
28, 95, 94, 17, 120, 91, 115, 67, 140, 84, 47, 111, 107, 35, 122]. In the following, we

will brieﬂy review the well-known techniques used for minutiae extraction.

As indicated in the previous section, a critical task in minutiae extraction is ridge
extraction. Ridge extraction is essentially a segmentation operation which separates
ridges from the background (furrows). A global thresholding method is not able to
correctly separate the ridges from the background [85]. An adaptive thresholding
technique is necessary. One of the earliest attempts at minutiae extraction is the FBI
minutiae reader which is a typical two-stage algorithm [12, 122, 85]. The algorithm
adaptively binarizes the input ﬁngerprint images using a “composite” approach and
extracts the minutiae from the binarized ridges. The “composite” approach is essen-
tially a local thresholding method based on the local ridge direction estimated by a
“slit comparison” formula. This algorithm has been used as a standard algorithm for
minutiae extraction in AFISs [85]. The performance of this algorithm is reasonable if
the quality of the input ﬁngerprint images is good. Moayer and Fu’s algorithm [100]
applies the Laplacian Operator and dynamic thresholding iteratively to the gray-level
input ﬁngerprint images to extract ridges. Chatterjee et al. [27, 28] proposed a fuzzy
approach which ﬁrst enhances the input ﬁngerprint images and then utilizes an adap-
tive thresholding method which preserves the same number of 1 and 0 pixels in each
neighborhood to extract the ridges from the enhanced images. Although the above

algorithms use the adaptive thresholding technique in ridge extraction, the perfor-

71

mance of these algorithms is good only when the quality of the input ﬁngerprint
images is reasonable. The adaptive thresholding techniques they employ do not fully
exploit the important information residing in the local ridge orientation.
Fingerprints are ﬂow-like patterns. Therefore the local ridge orientation pro-
vides very important information about the ridge structures. By incorporating local
ridge orientation efficiently, the performance of minutiae extraction algorithm can be
greatly improved. Mehtre [95, 94] proposed an algorithm using the directional im-
age. The directional image, which represents the local ridge direction in a 16 x 16
neighborhood, is ﬁrst computed and a set of eight 7 x 7 convolution masks is applied
to the gray-level input ﬁngerprint images to improve the quality of ridge structures.
Then, the ridges are extracted by applying a locally adaptive thresholding method
and a thinning operation is applied to the ridges. Finally, the minutiae are obtained
based on the computation of the connection number. A post-processing stage based
on a set of heuristics is used to eliminate the spurious minutiae. Although this algo-
rithm established the basic principle of incorporating local ridge orientation in ridge
extraction, its performance is not very impressive due to the inefﬁcient utilization
of the local ridge orientation. Botha and Coetzee [17] extract edges from the gray-
level input ﬁngerprint images using the Marr-Hildreth edge operator and compute the
ridge orientation in a local neighborhood. Then, they binarize the gray-level input
ﬁngerprint images using a segmentation algorithm which conducts local thresholding
based on the estimated local ridge orientation and extracted edges. Finally, they
apply a thinning algorithm to the smoothed binary image and extract the minutiae

from the thinned ridges. Again, due to the inefﬁcient way that they utilize the local

72

ridge orientation, the performance of their algorithm is not impressive.

Ratha et al. [120] proposed a minutiae extraction algorithm in which the ﬂow
direction of the ridges is computed by viewing the ﬁngerprint image as a directional
textured image. A waveform projection-based algorithm is used for ridge extraction,
the thinned skeleton of the extracted ridges is smoothed using morphological ﬁlters,
minutiae are extracted from the skeleton ridges, and a postprocessing step is applied
to delete spurious minutiae. Since the waveform projection and directional smooth-
ing operation used in the algorithm are very effective in suppressing small amounts
of noise, this algorithm performs very well. Maio and Maltoni [91] extract minutiae
directly from gray-level ﬁngerprint images. The algorithm is essentially a gray-level
ridge tracer which extracts ridges by sequentially following each gray~level ridge until
it reaches a ridge ending or a ridge bifurcation. Although they claim that the al-
gorithm does not binarize the gray-level ﬁngerprint image directly when conducting
minutiae extraction, binarization is still conducted implicitly by the gray-level ridge
tracer. The robustness Of this algorithm with respect to image quality is questionable,
due to the fact that the gray-level ridge tracer may behave unpredictably when ridges
and furrows are not well deﬁned.

In practice, the occurrences of minutiae in a ﬁngerprint image follow certain rules.
Therefore, a number of heuristics can be used to correct the minutiae errors. Xiao
and Raafat [115] describe a method to identify and eliminate spurious minutiae using
the structural information of minutiae. For each minutiae, statistics Of ridge width
and ridge attributes such as ridge length, ridge direction and minutiae direction are

used to decide the spurious minutiae. Szekely and Szekely [140] proposed a minutiae

73

extraction algorithm based on the computation of the directional image divergence.
Hung [67] enhanced binary ﬁngerprint images by equalizing the ridge widths. Direc-
tional enhancement of ridges is done after estimating the local direction in a small
window. The enhancement process has two steps: (i) direction-oriented ridge shrink-
ing, followed by (ii) direction-oriented ridge expanding. In addition, methods for

detecting bridges and breaks were also implemented.

Besides the attempts mentioned above, a number of alternative approaches have
also been investigated [84, 47, 111, 25]. For example, Engeler et al. [47] introduced
a neural network-based minutiae extraction algorithm, in which a multilayer per-
ceptron is used to extract ridges from gray-level ﬁngerprint images. The input to
the multilayer perceptron is a set of Gabor ﬁlter responses in a local neighborhood.

Unfortunately, the performances of these approaches have not been established.

In summary, a good minutiae extraction algorithm should efﬁciently incorporate
local ridge orientation in ridge extraction. Directional ridge enhancement should be
employed before the ridge extraction Operation. However, it should also be kept in
mind that directional smoothing is usually a computationally expensive Operation.
Postprocessing is a very important step for minutiae extraction, which can eliminate

a signiﬁcant number of errors.

74

 

 

     

Minutia
R I Extraction 7

Figure 4.3: Flowchart of the minutiae extraction algorithm

75
4.2 Minutiae Extraction Algorithm

We have developed a minutiae extraction algorithm which is an improved version
of the technique described in [120]. Our algorithm employs a more reliable and
more efﬁcient way to conduct adaptive ridge extraction than the original algorithm.
Experimental results demonstrate that this algorithm not only performs very well,
but it is also fast. The overall ﬂowchart of this algorithm is depicted in Figure 4.3. It
mainly consists of three stages: (i) orientation ﬁeld estimation, (ii) ridge extraction,
and (iii) minutiae extraction and postprocessing. First, for an input image, the local
ridge orientation is estimated and the region of interest is located. Then, ridges are
extracted from the input image, reﬁned to get rid of the small speckles and holes,
and thinned to obtain 8-connected single pixel wide ridges. Finally, minutiae are
extracted from the thinned ridges and reﬁned using some heuristics. In the following
subsections, we will describe in detail our minutiae extraction algorithm. In our
description, we assume that the resolution of input ﬁngerprint images is 500 dpi,

which is the recommended resolution for automatic ﬁngerprint identiﬁcation by the

FBI [85].

4.2.1 Deﬁnitions

In order to introduce our minutiae extraction algorithm, a list of notations and some
basic deﬁnitions are given below.
A gray-level ﬁngerprint image, I, is deﬁned as a N x N matrix, where I(i, j)

represents the intensity of the pixel at the ith row and jth column.

76

An orientation ﬁeld/image, (9, is deﬁned as an N x N image, where 0(i, j) rep-
resents the local ridge orientation at pixel (i, j). Local ridge orientation is usually
speciﬁed for a region (block) rather than at every pixel; an image is divided into a
set of w x w non-overlapping blocks and a single local ridge orientation is deﬁned for
each block. Note that in a ﬁngerprint image, the ridges oriented at 0° and the ridges
oriented at 180° in a local neighborhood can not be differentiated from each other.

A ridge map, R, is an N x N binary image, where R(i, j) = 1 indicates that pixel
(i, j) is a ridge pixel and R(i, j) = 0 indicates that pixel (i, j) is not a ridge pixel. A
ridge in a ridge map is an 8—connected component. A thinned ridge has a width of 1

pixel and a thinned ridge map, TR, consists of thinned ridges.

4.2.2 Orientation Field Estimation

The orientation ﬁeld of a ﬁngerprint image represents an intrinsic nature of the ﬁn-
gerprint image and deﬁnes invariant coordinates for ridges and furrows around each
local neighborhood, which plays a very important role in ﬁngerprint image analysis.
By viewing a ﬁngerprint image as an oriented texture, a number of methods have
been proposed to estimate the orientation ﬁeld of ﬁngerprint images [80, 118, 79, 25].
We have developed an iterated least mean square orientation estimation algorithm.

The main steps of the algorithm are as follows:

1. Divide the input ﬁngerprint image into blocks of size to x w. For 500 dpi images,
the initial value of w is 16.

2. Compute the gradients (91(i, j) and 0,,(i, j) at each pixel, (i, j). Depending on
the computational requirement, the gradient operator may vary from the simple
Sobel operator to the more complex Marr-Hildreth operator [92].

77

3. Estimate the local orientation of each block centered at pixel (i, j) using the
following equations [118]:

14% j+%

Vx(i,j) = Z 20x(u,v)8y(u,v), (4.1)
u=i—%v=j-E2’-
1+% 34%

vim) = Z _Z (a:<u,v)—a:(u,v)), (4.2)

 

1 .
9033') = -tan"l( . ), (43)
where 0(i, j) is the least square estimate of the local ridge orientation at the
block centered at pixel (i, j). Mathematically, it represents the direction that
is orthogonal to the dominant direction of the Fourier spectrum of the w x w
window.

 

4. Due to the presence of noise, corrupted ridge and valley structures, minutiae,
etc. in the input image, the estimated local ridge orientation, 0(i, j), may not
always be correct. Since local ridge orientation varies slowly in a local neighbor-
hood where no singular points appear, a low-pass ﬁlter can be used to modify the
incorrect local ridge orientation. In order to perform the low-pass ﬁltering, the

orientation image needs to be converted into a continuous vector ﬁeld, which is
deﬁned as follows:

(bx(i,j) = cos(20(i,j)), and (4.4)
(pt/(inf) = sin(20(i,j)), (45)

where 6,, and 6y, are the x and y components of the vector ﬁeld, respectively.
With the resulting vector ﬁeld, the low-pass ﬁltering can then be performed as
follows:

W¢/2 was/2

<I>;(z',j) = Z Z h(u,v)<I>x(i—uw,j—vw) and (4.6)

u=—w¢/2 v=—w¢/2
twp/2 imp/2

(Pg/(id) = Z Z h(u, v)<I>y(i — uw,j - vw), (4.7)

u=-w¢/2 v=—w¢/2

where h is a 2-dimensional low-pass ﬁlter with unit integral and wq, st speciﬁes
the size of the ﬁlter. Note that the smoothing operation is performed at the block
level. The default size of the ﬁlter is 5 x 5.

5. Compute the local ridge orientation at (i,j) using

. . 1 <P’(i,j)
0%,] :—tan”1 y,,
( ) (9920.3)

 

2 ). (4.8)

78

6. Compute the consistency level of the orientation ﬁeld in the local neighborhood
of a block (i, j) with the following formula:

 

can = 210(23): (4.9)
(1'; jc91)6D
., ., . . _ d ifd<180,
lam—own — [ d_,80 aha-mm (4.10)

d _ (0(1’, j’) —O(i, j)+360) mod 360, (4.11)

where D represents a local neighborhood around the block (i, j) (the default size
of D is 5 x 5); n is the number of blocks within D; O(i’,j’) and 0(i,j) are local
ridge orientations for blocks (i’, j’) and (i, j), respectively.

\2

. If C (i, j ) is above a certain threshold Tc, then the local orientations in this block
are re~estimated at a lower resolution level until C (i, j) is below a certain level.

With this algorithm, a fairly smooth orientation ﬁeld estimate can be obtained.
Figure 4.4 shows the orientation ﬁeld of a ﬁngerprint image estimated with our algo-

rithm.

\\
\\
xx
\\
\\
\I
ll
ll
//
1/
l/
//
//

[ ////——\.\\ \ \

\
\
l
I
I
/
/

/
/
I
/
/

.,

l

/(747/5/// 1
: ”/rf ' "

////—l~r-<f’
:/<//KI%///7//’.
1“ ///..--///--*-\ )
‘/////(//’*/
i//////<"4///
rum/7//**///”’F

t

/ ///.///////

/
I
l
|
l
l
i
\
i
K
\

///—/——-——_\\

 

”ﬁt
/
l
l
l
i
|
l
[
W\
’l
h

///
II/
III
III
lll
III
III
II\
II\
\\\
\\\
\\\
\\\

(b) Iterated method

 

Figure 4.4: Comparison of orientation ﬁelds estimated by the method proposed
in [118] and our method; to x w = 16 x 16 and wq, x 1114; = 5 x 5.

After the orientation ﬁeld of an input ﬁngerprint image is estimated, a region

of interest localization algorithm which is based on the local certainty level of the

 

Figure 4.5: Ridge ﬁlter, ht(i,j; u, v).

orientation ﬁeld is used to locate the region of interest within the input image. The

certainty level of the orientation ﬁeld in block (i, j) is deﬁned as follows:

 

7

. . _ e 1 (vz(i.j)2+vy(i,j)2)
5(2).” — waw Ve(7;ij)
i+% 14%

Ve(i,j) = Z Z (33(uiv)+3§(u,v))-

—'__u_’. — 1.2

(4.12)

(4.13)

For each block, if its certainty level of the orientation ﬁeld is below a threshold T1,

then all the pixels in this block are marked as a background pixel. The main reason

that we use 8 (i, j) to locate the region of interest within the input image is that

(i) E (i, j) is actually a by-product of the estimated local ridge orientation, so it is

efficient to compute 8 (i, j); (ii) 8 (i, j) performs reasonably well in detecting the region

Of interest. In our region of interest localization algorithm, we assume that only one

ﬁngerprint is present in the image.

80
4.2.3 Ridge Detection

An important prOperty of the ridges is that the gray-level values on ridges attain their
local maxima along a direction that is orthogonal to the local ridge orientation and
the gray-level values of furrows attain their local minima along the same direction.
Locally, ridges and furrows run parallel to one another forming a two-dimensional sine
wave. Therefore, pixels can be identiﬁed to be ridge pixels in a local neighborhood
based on this property. In our minutiae detection algorithm, a ﬁngerprint image
is ﬁrst convolved with two masks, ht(i,j;u,v) and hb(i,j;u,v), of size L x H (on
an average 11 x 7), respectively. The two masks, ht(i, j;u, v) and hb(i, j;u,v), are

essentially the same except that one is rotated by 180" with respect to the other (see

 

 

Figure 4.5):
—‘/2l7;68—%7, 1fu = (U COt(O(’l,j)) - mfg—(ﬁx?) E Q
ht(z‘,j; um) = $65137, if u = (vcot(0(i,j))),v e a (4-14)
] 0, otherwise,
“'2 u u o
——\/21=ﬂge737, 1fu = (v cot((9(i,j)) + 533%)” 6 Q
. . “2
hb(Z,J; “’71) = $667, ifu = (v cot(0(i,j))),v E 0 (4-15)
0, otherwise,
Lsin(0(i,j))

 

 

(4.16)

I

2

Lsin(0(i,j)) H
2 ,

 

9:]—

Where C(i, j) represents the local ridge direction at pixel (i, j). These two masks

 

 

are capable of accentuating the local maximum gray-level values along a direction

that is orthogonal to the local ridge orientation. They can also adaptively smooth

81

the ﬁngerprint images along the local ridge orientation and thus enhance the ridges.
The smoothing effect depends on the value of 6. The larger the value Of 6, the more
robust are the ﬁlters to noise but more sensitive they are to highly curved ridges. In
order to speedup the algorithm, the value of 6 is set to a very large number such that
each Of the ﬁlter is actually degenerated into a ﬁlter with all the coefﬁcients being
equal. Pixel (i, j) is labeled as a ridge pixel (R(i, j) = 1) if both the gray level values
at pixel (i, j) of the convolved images are larger than a certain threshold Tridge. By
adapting the mask width to the width of the local ridge, this algorithm can efﬁciently
locate the ridges. However, due to the presence of noise, breaks, smudges, etc. in
the input ﬁngerprint image, the resulting binary ridge map often contains holes and
speckles. Therefore, a hole and speckle removal algorithm needs to be applied before
ridge thinning. Our implementation of the hole and speckle removal algorithm uses
a connected component algorithm to compute the number of pixels within each ridge
and each hole and removes those connected components with number of pixels being
less than a threshold, Twmponem (the default value is 50). After the small speckles
and holes are removed, a thinning algorithm generates the thinned ridges with each

ridge being 8-connected and single pixel in width.

4.2.4 Minutiae Detection

Minutiae detection is a trivial task when an ideal thinned ridge map is available. If

(TR(i,j) = 1) (a ridge pixel) and ( 1 _121:_17"R(i + u,j + v) = 2), then pixel

u:

(i,j) is a ridge ending. If (T72(i,j) = 1) and (( 3,24 21:_17'7Z(i + U,j + v) > 3),

82

 

(c) ﬁngerprint region ((1) ridge map

      

r

(e) thinned ridge map (f) extracted minutiae

Figure 4.6: Results of our minutiae extraction algorithm on a live-scan ﬁngerprint
image (512 x 512); (a) input image; (b) orientation ﬁeld superimposed on the input
image; (c) ﬁngerprint region; ((1) extracted ridges (e) thinned ridge map; (f) extracted
minutiae and their orientations superimposed on the input image.

83

 

 

 

 

‘

 

(e) thinned ridge map (f) extracted minutiae

Figure 4.7: Results of our minutiae extraction algorithm on a rolled image from NIST
9 database (832 x 768); (a) input image; (b) orientation ﬁeld superimposed on the
input image; (0) ﬁngerprint region; (d) extracted ridges (e) thinned ridge map; (f)
extracted minutiae and their orientations superimposed on the input image.

84

then pixel (i, j) is a ridge bifurcation. However, the presence of undesired spikes and
breaks in a thinned ridge map may lead to many spurious minutiae being detected.
Therefore, before the minutiae detection, a smoothing procedure is applied to remove
spikes and to join broken ridges. Our ridge smoothing algorithm uses the following

heuristics (Figure 4.8):

o If the angle formed by a branch and the trunk ridge is larger than Time, (= 70°)
and less than Tapper (2 110°) and the length of the branch is less than Tbmnch

(2 20 pixels), then the branch is removed.

0 If a break in a ridge is shorter than Tbreak (= 15 pixels) and no other ridges pass

through it, then the break is connected.

The parameters controlling the behavior of ridge smoothing heuristic are presently
set to large values to ensure that all the genuine minutiae are detected. Although, it
is possible that the ridge smoothing algorithm may occasionally annihilate genuine
minutiae, by and large, it deletes the spurious minutiae generated due to poor quality
of images, artifacts introduced during image processing, and ﬁngerprint creases.

For each detected minutiae, the following parameters are recorded: (i) x-
coordinate, (ii) y-coordinate, (iii) orientation which is deﬁned as the local ridge ori-
entation of the associated ridge, and (iv) the associated ridge segment. The recorded
ridges are represented as one-dimensional discrete signals which are normalized by
a preset length parameter which is approximately equal to the average inter-ridge
distance (presently computed manually once for the given imaging setup). About 10

locations on each ridge are sampled per minutiae. The entire representation for a ﬁn-

85

E X \a

I x Remove spikes
ﬁn n' “x—“”

 

 

 

 

 

 

 

 

 

 

Figure 4.8: Examples of postprocessing heuristics.

ger when stored in a compressed format takes, on an average, about 800 bytes. These
recorded ridges are used for alignment in the minutiae matching stage. Figure 4.6
shows the results of our minutiae extraction algorithm on a live-scan ﬁngerprint image
captured with an FTIR optical ﬁngerprint scanner and Figure 4.7 shows the results
of our minutiae extraction algorithm on a rolled ﬁngerprint image from the NIST 9

ﬁngerprint database.

4.3 Summary

Minutiae extraction ﬁnds representative features, called minutiae, from the input

ﬁngerprint images. A minutiae extraction algorithm should be reliable as well as

86

computationally efﬁcient. A poor ﬁngerprint image can be either rejected or enhanced
prior to the minutiae extraction. A good minutiae extraction algorithm should be
able to tolerate, to a limited extent, the corrupted ridge structures and degrade
gracefully with the image quality. We have developed a minutiae extraction algorithm
which is both fast and reliable in minutiae extraction. The new orientation ﬁeld
estimation algorithm results in a smoother orientation ﬁeld which greatly improves
the performance of the minutiae extraction. The adaptive ridge ﬁnder is capable
of tolerating, to a certain extent, low ridge contrast and various sources of noise in
ﬁngerprint images such as short breaks and small smudges. The postprocessing step

further reﬁnes the extracted minutiae.

Chapter 5

Fingerprint Enhancement

The performance of currently available minutiae extraction algorithms depends heav-
ily on the quality of input images. In an ideal ﬁngerprint image, ridges can be easily
detected and minutiae can be precisely located from the thinned ridges. However,
in practice, due to the factors mentioned early, a signiﬁcant percentage of acquired
ﬁngerprint images (approximately 10%) is of poor quality. The ridge structures in
poor-quality ﬁngerprint images are not always well-deﬁned and hence they can not
be correctly detected. This leads to the following problems: (i) a signiﬁcant number
of spurious minutiae may be created, (ii) a large percentage of genuine minutiae may
be ignored, and (iii) large errors in their localization (position and orientation) may
be introduced. Figures 5.1 and 5.2 show typical examples of applying our minutiae
extraction algorithm to live-scan ﬁngerprint images of both good and poor quality.
We can see that the performance of the minutiae extraction algorithm on the poor
quality image is far from desirable; a signiﬁcant number of Spurious minutiae are
created and a large percentage of genuine minutiae are ignored by the algorithm.

87

88

(a)
Figure 5.1: Results of applying a minutiae extraction algorithm to a ﬁngerprint image
of good quality; (3.) input image; (b) extracted ridge map; (c) extracted minutiae
superimposed on the input ﬁngerprint image.

 

 

Figure 5.2: Results of applying a minutiae extraction algorithm to a ﬁngerprint image
of poor quality; (a) input image; (b) extracted ridge map; (c) extracted minutiae
superimposed on the input ﬁngerprint image.

In order to ensure that the performance of the minutiae extraction algorithm will
be robust with respect to the quality of input ﬁngerprint images, an enhancement
algorithm which can improve the clarity of the ridge structures of input ﬁngerprint

images is, thus, necessary.

Ideally, the ridge structures in a ﬁngerprint image are well—deﬁned. Each ridge is
separated by two parallel narrow furrows, each furrow is separated by two parallel
narrow ridges; and minutiae are anomalies of ridges, i.e., ridge endings and ridge
bifurcations. When a ﬁngerprint image is corrupted, such well-deﬁned ridge structures

are no longer visible. However, despite the existence of such noise, a ﬁngerprint expert

89

 

Figure 5.3: Fingerprint regions; (a) well-deﬁned region; (b) recoverable corrupted
region; (c) unrecoverable corrupted region.

is often able to correctly identify the minutiae by using various visual clues such as
local ridge orientation, ridge continuity, and ridge tendency. It is possible to develop
an enhancement algorithm that can exploit these visual clues to improve the clarity
of ridge structure in ﬁngerprint images, which, in turn, will improve the performance
of the minutiae extraction algorithm.

Generally, for a given ﬁngerprint image, the region of interest can be divided into

the following three categories (Figure 5.3):

o Well-deﬁned region, where ridges and valleys are clearly differentiated from one

another such that a minutiae extraction algorithm is able to operate reasonably.

o Recoverable corrupted region, where ridges and valleys are corrupted by a small
amount of creases, smudges, etc. But, they are still visible and the neighboring

regions provide suﬂicient information about the true ridge and valley structures.

0 Unrecoverable corrupted region, where ridges and valleys are corrupted by such
a severe amount of noise and distortion that no ridges and valleys are visible

and the neighboring regions do not provide sufﬁcient information about the true

90

ridge and valley structures either.

We refer to the ﬁrst two categories Of ﬁngerprint regions as recoverable and the last
category as unrecoverable. It is impossible to recover the original ridge structures in
the unrecoverable regions, since no ridges and furrows are present at all within these
regions. Any effort to improve the quality of the ﬁngerprint image in these regions
is futile. Therefore, the goal of a reasonable enhancement algorithm is to improve
the clarity of ridge structures of ﬁngerprint images in recoverable regions and to
mask out the unrecoverable regions. In addition, since the objective of a ﬁngerprint
enhancement algorithm is to improve the clarity of ridge structures of input ﬁngerprint
images to facilitate the extraction of ridges and minutiae, a ﬁngerprint enhancement
algorithm should not result in any spurious ridge structures. This is very important,

because spurious ridge structure may change the individuality of input ﬁngerprints.

Fingerprint enhancement can be conducted on either (i) binary images or (ii) gray-
level images. The parallel property of ridges provides a number of simple heuristics
to differentiate the spurious ridge conﬁgurations from the true ridge conﬁgurations
in binary images [67]. However, after applying a ridge extraction algorithm on the
original gray-level images, information about the true ridge structures is often lost
depending on the performance of the ridge extraction algorithm. Enhancement based

on binary images has its inherent limitations.

A number Of algorithms have been proposed to enhance grey level ﬁngerprint im-
ages [14, 40, 67, 110, 76, 35, 96, 131, 132, 81]. Most of these techniques take advantage

of the information about the local ridge structures and are capable of adaptively im-

91

proving the quality of input ﬁngerprint images [40, 110, 76, 35, 96, 131, 81]. They
usually assume that the local ridge orientation can be reliably estimated from input
ﬁngerprint images. In practice, this assumption is mainly valid for ﬁngerprint images
of good quality. For ﬁngerprint image of poor quality, such an assumption is really
not true, due to the existence of noise, creases, smudges, and holes; ﬁgure 5.4 shows
some examples of estimated orientation ﬁeld of ﬁngerprint images of poor quality.
Therefore, a good ﬁngerprint enhancement algorithm should not assume that local
ridge orientation can be easily obtained. Instead, it should focus a signiﬁcant amount

of effort on reliable computation of orientation ﬁeld.

. z ;.....\\\\\\.....s.~~

 

Figure 5.4: Estimated orientation ﬁelds of ﬁngerprint images of poor quality.

We have developed a ﬁngerprint enhancement algorithm, which improves the clar-
ity of ridge structures in recoverable regions and make them suitable for minutiae ex-
traction algorithms. Our algorithm also identiﬁes all the corrupted regions in which
it does not have the capability of recovering the true ridge structures and labels them

as unrecoverable regions. The overview of the algorithm is shown in Figure 5.5. It

92

Input Image

 

Bank of Gabor Filters

_1_[// l
—_‘l —“l i

f

Ridge Extraction

f i ll f

. . . . Ridge Maps

\ \ /\ /

Voting Algorithm

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Coarse-level Map Unrecoverable-Mask

 

 

Estimate Local Orientation

FEL

Composition

vii/v

Orientation Field

 

 

 

 

 

 

 

 

Enhanced Image

 

 

 

Figure 5.5: An overview of the ﬁngerprint enhancement algorithm.

93

consists of two main stages: (i) orientation ﬁeld estimation, and (ii) enhancement.
Instead of estimating the orientation ﬁeld directly from the input ﬁngerprint image,
we estimate it from the ﬁltered images in which noise that is orthogonal to the dom-
inant ridge orientation is greatly attenuated. Because our algorithm can obtain a
reliable estimate of the orientation ﬁeld, a better performance can thus be achieved

in the enhancement stage. Its main steps are described as follows:

N

. A bank of even-symmetric Gabor ﬁlters is applied to an input ﬁngerprint image
and a set of ﬁltered images is produced.

2. A ridge extraction algorithm is applied to each of the ﬁltered images and the
corresponding ridge map is obtained.

3. From the extracted ridge maps of ﬁltered images, a voting algorithm is used to
generate a coarse-level ridge map and unrecoverable-region mask. The generated

coarse-level ridge map is used for orientation ﬁeld estimation.

4. An orientation estimation algorithm is applied to the generated coarse-level ridge
map, and the local orientation at each pixel is obtained.

5. From the computed orientation ﬁeld and ﬁltered images, an enhanced image is
obtained.

5.1 Filtering Of Fingerprint Image

In a small local neighborhood, the ridges and furrows in a ﬁngerprint image approx-
imately form a two-dimensional sine wave along the local ridge orientation. Thus,
the ridges and valleys in a small local neighborhood have well-deﬁned local frequency
and local orientation properties. A set of bandpass ﬁlters can remove the undesired

noise and preserve the true ridge structures [76, 110, 35, 131]. Gabor ﬁlters have both

94

frequency-selective and orientation-selective properties and have optimal joint resolu-
tion in both spatial and frequency domains [41, 72]. Therefore, it is beneﬁcial to use

Gabor ﬁlters as bandpass ﬁlters to remove the noise and preserve true ridge/ furrow

structures.

 

 

 

Figure 5.6: An even-symmetric Gabor ﬁlter: (a) Gabor ﬁlter tuned to 60 cycles/ width
and 0° orientation; (b) corresponding MTF.

The even-symmetric Gabor ﬁlter has the following general form [72]:

h(x _ — 1 $2 y2
,y) — exp -2- 5 + 32- cos(27ruox), (5.1)
x y

where no is the frequency of a sinusoidal plane wave along the x-axis, and 6,, and 6,,
are the space constants of the Gaussian envelope along x and y axes, respectively.
Gabor ﬁlters with arbitrary orientation can be obtained via a rotation of the x — y
coordinate system. The modulation transfer function (MTF) of a Gabor ﬁlter can be
represented as

H(u,v) = 27rdxr5y (exp{—-1- M + f }+ exp —% M22- + 3: }) (5.2)

2 53 52

U

95

where 6,, = 1/2rr61, and 6,, = 1/2rr6y. Figure 5.6 shows an even-symmetric Gabor
ﬁlter and its MTF.

An important issue in applying Gabor ﬁlters is the selection of ﬁlter parameters.
We have observed that in a 500 dpi ﬁngerprint image, the ridge frequency is generally
around 60 cycles per image width (height). Therefore, in our ﬁngerprint enhancement
algorithm, the central frequency, uo, is selected as 60 cycles/width (height). The
radial bandwidth is selected as 2.5 octaves. Eight values of central orientation 60 are
used: 0°, 22.5°, 45°, 67.5°, 90°, 112,5°, 135°, 157.5°. The orientation bandwidth is
selected as 35°. For a given input ﬁngerprint image, these 8 Gabor ﬁlters are applied
to Obtain 8 ﬁltered images. To obtain a ﬁltered image, a FFT is ﬁrst performed on
the input ﬁngerprint image. Then the corresponding Gabor ﬁlters with tuned radial
and orientation frequencies are applied to the frequency image and an inverse FFT
is performed to Obtain the ﬁltered image. Figures 5.7(b)—(i) show the eight ﬁltered
images for the ﬁngerprint image shown in Figure 5.7 (a).

The ﬁltered image corresponding to a given Gabor ﬁlter mainly preserves the
ridges and valleys that are of the same direction as the ﬁlter direction. A channel
selection algorithm is needed to combine the ﬁltered images to generate an enhanced
image. Ideally, a Bayesian evidence integration scheme which is based on the differ-
ence of the orthogonal channel contribution can be used to select channel(s) corre-
sponding to each block. However, in order to ensure that such an evidence integration
scheme is robust to noise, evidence should be collected from a relatively large local
neighborhood. Computationally, this approach is very expensive. Therefore, in our

algorithm, a simplifying scheme, which is based on the binary ridge maps of the ﬁl-

 

(g) (h) 0)

Figure 5.7: Examples of ﬁltered images for a 512 x 512 ﬁngerprint image: (a) input im-
age; (b—i) ﬁltered images with Gabor ﬁlters tuned to 60 cycles/width and orientations
of 0°, 22.5", 45". 67.5”, 90°. 112.5°, 135°, 157.5°, respectively.

97

tered images, is used. Although the simplifying scheme is not as efficient as a Bayesian
evidence integration scheme, it is adequate in selecting the correct channels and is

computationally inexpensive.

5.2 Ridge Extraction

For each ﬁltered image, the ridge extraction algorithm which is described in chapter
4 is applied and the corresponding ridge maps are extracted from the ﬁltered images.
These ridge maps are not used for minutiae extraction. Instead, they are used to
generate a coarse-level ridge map of the input ﬁngerprint image.

Due to the presence of noise, creases, smudges, etc. in the input ﬁngerprint image,
the resulting ridge maps of the ﬁltered images often contain a large number of non-
ridge pixels being labeled as ridge pixels. A postprocessing step is needed to remove
these non-ridge pixels. In our ﬁngerprint enhancement algorithm, we use the following

heuristics:

0 Compute the area of each connected component appearing in the ridge map. If
the area is less than a threshold Tm," (the default value is 200), then label this
connected component as background; otherwise break the connected component

into a set of short line segments and go to the next step.

0 For each short line segment, if it is between a pair of narrow parallel ridges,

then label it as a true ridge; otherwise label it as background.

The motivation behind these two heuristics is based on the fact that a genuine ridge

98

should (i) be sufﬁciently long and (ii) is located between a pair of ridges. The
algorithm based on these two heuristics can remove the spurious ridges as well as the
short genuine ridges and boundary ridges. Figure 5.8 shows an example of how the

above algorithm performs on a ridge map extracted from a ﬁltered image.

 

(a) (b)

Figure 5.8: The extracted ridge map of the 0° ﬁltered image: (a) the 0° ﬁltered image;
(b) the extracted ridge map from the 0° ﬁltered image; the dark lines represent the
valid ridges; grey lines represent the spurious ridges removed by the postprocessing
step.

5.3 Ridge Voting

After the ridge map of each ﬁltered image is obtained, the next step in our ﬁngerprint
enhancement algorithm is to generate a coarse-level ridge map and a mask of unre-
coverable regions of the input ﬁngerprint image. The coarse-level ridge map consists
of the ridges extracted from each ﬁltered images that are consistent with one another.

It is used to estimate a reliable orientation ﬁeld. The only requirement for the gen—

99

erated coarse-level ridge map is that it should roughly reﬂect the orientation of the
local ridge structures of the input ﬁngerprint image. It is not necessary to impose a
requirement that this coarse-level ridge map should be very precise in terms of local
ridge structures, since the minutiae will not be extracted from the coarse-level ridge
map.

Neighboring ridges in a ﬁngerprint image are usually oriented in the same direc-
tion. A ﬁltered image obtained by applying a Gabor ﬁlter tuned to a certain direction
retains the ridges that are oriented approximately in the same direction as the tuned
direction Of the Gabor ﬁlter. Generally, a ridge is a genuine ridge only if it is in
a continuous region of signiﬁcant size and tends to run parallel to its neighboring
ridges. We can use this property as a heuristic to differentiate the genuine ridges
from the spurious ridges. In our enhancement algorithm, the coarse-level ridge map
and unrecoverable region mask are generated from the ridge maps Of ﬁltered images
by using the following ridge voting algorithm.

0 Divide each ridge map of ﬁltered images into blocks of size W x W (8 x 8 in
our algorithm).

0 Label each block as foreground (with a value 1) if there are enough ridge pixels
appearing around the block; otherwise label it as background (with a value 0).
After this process, a binary block map in which a pixel value of 1 represents the
existence of ridges and 0 as non-ridges is obtained for each ridge map of ﬁltered
images.

0 Delete all the connected components (8-connected) in the binary block maps
which have an area less than a threshold (16 in our algorithm).

0 For each block, examine all the eight ﬁltered images and compute the coarse-
level ridge map according to the following rules (an intuitive meaning of these
rules is shown in Figure 5. .9):

Rule 1. If only one of the eight binary block map at pixel (x,y) has the value 1
and this pixel belongs to a connected component of size K, K > Tblock;

100

then the pixel values of the corresponding block in the coarse-level ridge
map are duplicated from the associated ridge map. The pixel value of the
corresponding recoverable region mask is set to the value 0 to indicate that
this block is recoverable.

Rule 2. If more than one binary block map at pixel (x, g) has the value 1 and the
associated local ridge orientations are not orthogonal to one another, the
pixel values of the corresponding block in the coarse-level ridge map are
taken as the average values of the associated ridge maps. The pixel values
of the corresponding recoverable region mask is set to the value 0 to indicate
that this block is recoverable.

Rule 3. If more than one binary block map at pixel (x, y) has the value 1, the asso-
ciated local ridge orientations may be orthogonal to one another, and only
one pixel with the value 1 resides in a connected component of size larger
than a certain threshold Tblock; then the pixel values of the corresponding
block in the coarse-level ridge map are duplicated from the ridge map as-
sociated with the largest connected component and the pixel value of the
corresponding recoverable region mask is set to the value 0 to indicate that
this block is recoverable.

Rule 4. If the above conditions are not satisﬁed, then the block is assigned a label
1 to indicate that it is unrecoverable.

By applying this algorithm to the set of ridge maps of ﬁltered images, a coarse-
level ridge map and an unrecoverable region mask are generated. An example of ridge

voting is shown in Figure 5.10.

5.4 Enhanced Image

The coarse-level ridge map generated from the ridge maps of the ﬁltered images pre-
serves the local orientation information of the ridge structures of the input ﬁngerprint
image. The orientation ﬁeld of the input ﬁngerprint image can now be estimated from
the coarse-level ridge map by ignoring the unrecoverable regions. The orientation ﬁeld
estimated from the coarse-level ridge map is more reliable than the orientation ﬁeld

estimated directly from the original image, because the steps introduced in the previ—

(a)

\n.“

”/

l

[y/;

l/

U
)1

M.

l//
n

(s)

101

\‘

x \
.\\\‘*~

0))

(11)

W

\
\x\

if
u

0)

Figure 5.9: Intuitive meaning of the voting algorithm; here for simplicity, we assume
that the input image is decomposed into two ﬁltered images; (a)-(c) correspond to
rule 1; (d)-(f) correspond to rule 2; (g)-(h) correspond to rule 3; the left two columns
show the inputs to the voting algorithm while the third column shows the voting

results.

102

Illll \‘ \‘ ‘0‘ \ 3\\ \\§~\

l t'r H \\\ l N ‘ \:\\\\\\\\ \ ‘ \_ \ \“~\\\\ \\
. in][\[[\]((\(;b‘\ﬁ \ \.\\\\\\\\\\\\\\\\\\\— 5% \\§\\\\\\:\\}\\\\x\

l \ \:\_“\\\\§ ‘\ \\‘\

—_ a
~‘\\\ -5 ’ / k
. t“ , r, w, /,
‘_=~:\ \\ [I] I 4’ f,
‘ —\ — \\‘\\\%\\\ ‘f'd' '-’-=
._ s\\ “a A” - :- }
v f
\ w‘ ‘L ‘ 9‘ - f—u’ '- a}; .
:\\ 3‘ 3. rs." -r- — a’
‘M‘ F \ v“... f. g - /- - ,.
\ \\\\ s‘ x a" .f’ "”‘
1 -: \“ F \ ’- J / ’ a ,
‘ - \ \\ \\\ ._ ‘- 4:74 " ’1 ‘
: \F : :\~\\ ; _’_’:3/ 1-"/
: \ —‘-
s \‘ \‘ \\ /---/’ 7?
a ‘\ ‘ ..\. \ v -
$:~ “‘ #V "/

 

I /
7:

I" ’f ,

I 1%
//I / /
/ ,. C / / s; \ \
7; 94,7 I, 2 _:\ \ \
I /,
a 1” /’ 7’ ’ J//’ ' —-— _ I \ \
.x,-\ ,
; /

il’y'
.11, W ,
(h)

Figure 5.10: An example of ridge voting: (a-h) the ridge maps extracted from ﬁltered
images at 0°, 225°, 45°, 67.5°, 90°, 112.5°, 135°, 157.5°, respectively; (i) the voting

 

result.

103

ous sections are able to suppress the harmful effect of noise, speckles, creases, holes,
etc. The orientation estimation algorithm described in chapter 4 is used to compute

the orientation ﬁeld.

After the orientation ﬁeld is obtained, the ﬁngerprint image can then be adaptively
enhanced by using the local orientation information. Let f,(x, y) (i=0, 1, 2, 3, 4, 5,
6, 7) denote the grey level value at pixel (x, y) Of the ﬁltered image corresponding to
the orientation 0,, 6, = i =1: 225°. The grey level value at pixel (x, y) Of the enhanced

image can be interpolated according to the following formula:

 

 

fenh($i y) = “(317, ylfpfriyﬂxr y) + (1 — 0(1), y))fQ($,y)(xa :9), (53)
where
1903,31) = 16:35“) J, (5.4)
(103.31) = [£33312] mod 8, (5-5)
deny) 0(x,y)2;513(x,y), (56)
(5.7)

and 0(x,y) represents the value of the local orientation ﬁeld at pixel (x, y). The
main reason for interpolating the enhanced image directly from the limited number
of ﬁltered images is that the ﬁltered images are already available and the above in-
terpolation is computationally efﬁcient. Obviously, the quality of the image obtained

from such an interpolation scheme is not as good as the quality of the image ob—

104

tained by adaptively ﬁltering the original image using the Gabor ﬁlters. However, it
is sufﬁcient for our minutiae extraction algorithm, which, in fact, has the capability

of tolerating the unsmoothed effect of the enhanced images.

5.5 Summary

We have introduced our ﬁngerprint enhancement algorithm. This algorithm, unlike
other algorithms, concentrates a large amount of effort on a reliable estimation of the
orientation ﬁeld, which plays a critical role in the minutiae extraction algorithm. Our
algorithm is capable of obtaining a relatively good estimate of orientation ﬁeld even
if the quality of the input ﬁngerprint image is poor. Our algorithm also identiﬁes
the unrecoverable corrupted regions in the ﬁngerprint and masks them out. This is a
very important property because such unrecoverable regions do appear in some of the
corrupted ﬁngerprint images and they are extremely harmful to minutiae extraction.
We note that our algorithm does not perform very well around singular regions where
ridges and valleys have relatively high curvature values. It tends to mask these
regions as unrecoverable regions. However, because minutiae around singular regions
are usually assigned lower weights during matching, such a deﬁciency is not serious.

The major disadvantage of the current algorithm is that it is relatively slow.
It takes approximately 13.8 seconds for our enhancement algorithm to process one
512 x 512 ﬁngerprint image on a UltraSPARC 1 workstation. Obviously, this is
too slow for an online application. Therefore, this algorithm is only used in the

enrollment module. We have also proposed a fast enhancement algorithm which is able

105

 

(e)

(T)
Figure 5.11: Results of applying the enhancement algorithm to a ﬁngerprint image
of poor quality: (a) input image; (b) coarse-level ridge map; (c) unrecoverable-region
mask which consists of white pixels; (d) estimated orientation ﬁeld; (e) enhanced
image; (f) minutiae extracted from the enhanced image superimposed on the input
image.

106

to adaptively enhance the ridge and valley structures using Gabor ﬁlters controlled by
the local ridge orientation and local frequency information [64]. Experimental results
have demonstrated that the fast algorithm can improve the performance of minutiae
matching. It takes 2.3 seconds for the fast algorithm to enhance a 512 x 512 image

on a UltraSPARC 1 workstation.

Chapter 6

Minutiae Matching

Given two (an input and a template) minutiae patterns, the minutiae matching algo-

rithm determines whether they are from the impressions of the same ﬁnger.

6.1 Problem Speciﬁcation

A minutiae matching problem is essentially a point pattern matching problem. The
similarity of two minutiae patterns is determined by the total number (or normalized
total number) of corresponding minutiae and the decision is made by comparing the
value of the similarity with a pre-speciﬁed threshold. Formally, it can be stated as fol-
lows: Let P = (of. if. 6f), (art, it, at» and Q = «$9,219. 9?), (act. that»
denote the M minutiae in the template and the N minutiae in the input image, re-
spectively. Find the number, MW", of corresponding pairs between P and Q and

compare it against a threshold value Tminutiae-

In the ideal case, if (i) the correspondence between the template and input is

107

108

known, (ii) there are no deformations such as translation, rotation and deformations
between them, and (iii) each minutiae present in a ﬁngerprint image is exactly local-
ized, then minutiae matching is only a trivial task of counting the number of spatially
matching pairs between the two ﬁngerprints and comparing it against a pre-speciﬁed
threshold value.

In practice, determining whether two minutiae patterns extracted from two ﬁn-
gerprint impressions, possibly separated by a long duration of time, are indeed from
the same ﬁnger, is an extremely difﬁcult problem. The difﬁculty can be attributed
to two primary reasons. First, even though the test and template minutiae patterns
are indeed mated pairs, the correspondence between the test and template minutiae
patterns is generally not known. Secondly, the imaging system presents a number of
peculiar and challenging situations some Of which are unique to ﬁngerprint image cap-
ture scenario: (i) Inconsistent contact: The act of sensing distorts the ﬁnger. Based
on the pressure and contact of the ﬁnger on the glass platen, the three-dimensional
shape of the ﬁnger gets mapped onto the two-dimensional surface Of the glass platen.
Typically, this mapping function is uncontrolled and results in different ﬁngerprint
images across the impressions. (ii) Non—uniform contact: The ridge structure of a
ﬁnger would be completely captured if ridges of the part of the ﬁnger being imaged
are in complete Optical contact with the glass platen. However, dryness of the skin,
skin disease, sweat, dirt, humidity in the air all confound the situation, resulting in
a non-ideal contact situation; some parts of the ridges may not come in complete
contact with the platen and regions representing some furrows may come in contact

with the glass platen. This results in “noisy” low contrast images, leading to either

109

spurious minutiae or missing minutiae. (iii) Irreproducible contact: Manual work,
accidents, etc. inﬂict injuries to the ﬁnger, thereby, changing the ridge structure of
the ﬁnger either permanently or semi-permanently. This may introduce additional
spurious minutiae. (iv) Feature extraction artifacts: The feature extraction algorithm
is imperfect and introduces measurement errors. Various image processing Operations
might introduce inconsistent biases to perturb the location and orientation estimates
of the reported minutiae from their gray scale counterparts. (v) The act of sensing
itself adds noise to the image. For example, residues are leftover from the previous
ﬁngerprint capture. A typical imaging system distorts the image of the Object being
sensed due to imperfect imaging conditions. In the FTIR sensing scheme, for exam-
ple, there is a geometric distortion because the image plane is not parallel to the glass
platen.

In the light Of the Operational environments mentioned above, the design of the
minutiae matching algorithms needs to establish and characterize a realistic model of
the variations among the representations of mated pairs. This model should include

the properties of interest listed below:

1. The ﬁnger may be placed at different locations on the glass platen resulting in
a (global) translation of the minutiae of the test representation from those in

the template representation.

2. The ﬁnger may be placed in different orientations on the glass platen resulting
in a (global) rotation of the minutiae Of the test representation from those of

the template representation.

110

3. The ﬁnger may exert a diﬁerent (average) downward normal pressure on the
glass platen resulting in a (global) spatial scaling Of the minutiae of the test

representation from those in the template representation.

4. The ﬁnger may exert a different (average) shear force on the glass platen re-
sulting in a (global) shear transformation (characterized by a shear direction
and magnitude) Of the minutiae of the test representation from those in the

template representation.

5. Spurious minutiae may be present in both the template as well as the test

representations.

6. Genuine minutiae may be absent in the template or test representations.

7. Minutiae may be locally perturbed from their “true” location and the pertur-
bation may be different for each individual minutiae. (The magnitude of such
perturbations, however, is assumed to be small and within a ﬁxed number of

pixels.)

8. The individual perturbations among the corresponding minutiae could be rela-
tively large (with respect to ridge spacings) but the perturbations among pairs

of the minutiae are spatially linear.

9. The individual perturbations among the corresponding minutiae could be rela-
tively large (with respect to ridge spacings) but the perturbations among pairs

of the minutiae are spatially non-linear.

111

10. Only a (ridge) connectivity preserving transformation could characterize the

relationship between the test and template representations.

A minutiae matcher may rely on one or more of these assumptions, resulting in a
wide spectrum of behavior. At the one end of the spectrum, we have the “Euclidean”
matchers which allow only rigid transformations among the test and template rep-
resentations. At the other extreme, we have a “tOpological” matcher which may
allow the most general transformations including, say, order reversalsl. The choice
of assumptions often represents matching performance trade-offs. Only a highly con-
strained system with not too demanding accuracies could get away with restrictive
assumptions.

Figure 3.7 illustrates a typical situation of aligned ridge structures of mated pairs.
Note that the best alignment in one part of the image may result in a large amount of
displacements between the corresponding minutiae in the other regions. In addition,
observe that the distortion is non-linear: given distortions at two arbitrary locations
on the ﬁnger, it is not possible to predict the distortion at all the intervening points
on the line joining the two points. In our opinion, a good minutiae matcher needs to
accommodate not only global similarity transformations, but also shear transforma-
tions, linear and non-linear differential distortions. In our experience, assumption 10
is too general a model to characterize the impressions of a ﬁnger and its inclusion
into the matcher design may compromise efﬁciency and discriminatory power of the

matcher. In addition, the minutiae matchers based on such an assumption need to use

 

1Order reversal means that the minutiae in the test representation are in totally different spatial
order with respect to their correspondences in the template representation.

112

connectivity information which is notoriously difﬁcult to extract from the ﬁngerprint

images of poor quality.

6.2 Literature Review

A large number of minutiae matchers (point pattern matchers) which are essentially
“Euclidean” matchers have been proposed [46, 56, 4, 8, 11, 54, 24, 117, 128, 127, 138,
136, 141, 121, 147]. These matchers assume similarity transformation (assumptions
1, 2, and 3) and can tolerate, to a limited extent, both spurious minutiae as well as
missing genuine minutiae (assumptions 5 and 6). Also, some of them can be modiﬁed
to tolerate assumption 7, i.e. to be “elastic” in accommodating a small bounded local
perturbation of minutiae. But they are not able to handle large displacements of the
minutiae from their true locations. The relaxation approach [117] iteratively adjusts
the conﬁdence level of each corresponding pair based on its consistency with other
pairs until a certain criterion is satisﬁed. Although a number of modiﬁed versions
of this algorithm have been proposed to reduce the matching complexity [141], these
algorithms are inherently slow because Of their iterative nature and are unable to han-
dle large distortions. The generalized Hough transform-based approach [11, 138, 24]
converts point pattern matching to a problem of detecting peaks in the Hough space
of transformation parameters. It discretizes the parameter space and accumulates
evidence in the discretized space by deriving transformation parameters that relate
two point patterns using a substructure or feature matching technique. A hierarchical

Hough transform-based algorithm may be used to reduce the size of the accumulator

113

array by using a multi-resolution approach [24]. However, if there are only a few
minutiae points available, it is very difﬁcult to accumulate enough evidence in the
Hough transform space for a reliable match. Again, it is difﬁcult for this approach
to handle large distortions. Tree-pruning approaches attempt to ﬁnd the correspon-
dence between a pair of point sets by searching over a tree Of possible matches while
employing different tree pruning methods such as branch-and-bound to reduce the
search space [8]. To efﬁciently prune the tree of possible matches, this approach tends
to impose a number of requirements on the input point sets such as an equal number
Of points and no outliers. These requirements are difﬁcult to satisfy in practice, es-
pecially in a ﬁngerprint identiﬁcation/ veriﬁcation system. The energy minimization
approach to point pattern matching establishes the correspondence between a pair of
point sets by deﬁning an energy function based on an initial set of possible correspon-
dences and uses an appropriate Optimization technique such as genetic algorithm,
neural network, simulated annealing, etc. [4, 136, 147, 128, 127, 54] to ﬁnd a possi-
ble subOptimal match. These methods tend to be very slow and are unsuitable for
a real-time identiﬁcation/ veriﬁcation system. They can tolerate only a very limited
percentage of spurious and missing minutiae.

There also exist a number of graph-based matchers [134, 116, 69, 66, 61], which
are essentially a “topological” type of matchers. They allow general transformations,
positional errors, missing minutiae, and spurious minutiae. Since a general graph
matching is a NP-complete problem, ridge features such as the position of the core
points, ridge counts, inter-minutiae ridge counts and/ or external alignment informa-

tion are widely used to reduce the exponential search problem to a tractable problem.

114

The performance of these algorithms depends heavily on the availability of the ridge
features and external alignment information. In a semi-automatic ﬁngerprint identiﬁ-
cation system, these algorithms usually perform well, since the minutiae patterns can
be aligned and the errors in minutiae and ridge features can be corrected interactively.
However, a fully automatic ﬁngerprint matching may not always be able to guarantee

the availability of the correct ridge features and external alignment information.

6.3 Alignment-based Algorithm

We have developed an alignment-based matching algorithm, which is simple in the-
ory, efﬁcient in discrimination, and fast in speed. The alignment-based matching
algorithm decomposes the minutiae matching into two stages: (i) alignment stage
and (ii) matching stage. In the alignment stage, an alignment hypothesis, including
translation and rotation between the input and the template is ﬁrst generated and the
input minutiae are aligned with the template minutiae according to the hypothesis.
In the matching stage, the input minutiae and the template minutiae are ﬁrst con-
verted to a string representation in the polar coordinate system and an elastic string
matching algorithm is used to evaluate the similarity between the two strings. The
hypothesis that results in the largest similarity value is determined as the optimal
alignment. The corresponding minutiae pairs are determined based on the optimal

alignment. The main steps of our algorithm are as follows:

1. For each pair of minutiae in P and Q, ﬁnd the translation and rotation param-
eters between the ridge associated with input minutiae and the ridge associated
with template minutiae and align the two minutiae patterns according to the
estimated parameters.

115

2. Convert the template pattern and input pattern into the polar coordinate rep-
resentations with respect to the corresponding minutiae on which alignment is
achieved and represent them as two symbolic strings by concatenating each minu-
tiae in an increasing order of radial angles:

PP: ((7.1 ’61P,6P)m (7.11:1! eff/Ii OF M))

Q1): ((Tl ,CIQ,01Q)...(7‘N,8N,6Q))

where r..., e.., and 0... represent the corresponding radius, radial angle, and nor-
malized minutiae orientation with respect to the reference minutiae, respectively.

3. Match the resulting strings PI) and Qp with a modiﬁed dynamic-programming
algorithm described below to ﬁnd the ‘edit distance’ between Pp and Qp.

4. Find the minimum edit distance between Pp and Qp. Use the minimum edit
distance to establish the correspondence of the minutiae between Pp and Q, and
compute the total number of corresponding minutiae, M pq. The matching score,
5', is then computed according to

100MPQMPQ

5: MN

 

(6.3)

6.4 Alignment Hypothesis

Ideally, two sets of planar point patterns can be aligned completely by only two
corresponding point pairs. A true alignment between two point patterns can be
obtained by testing all possible corresponding point pairs and selecting the optimal
one. However, due to the presence of noise and deformations, the input minutiae
cannot always be aligned exactly with respect to those of the templates. In order to
accurately recover pose transformations between two point patterns, a relatively large
number of corresponding point pairs need to be used. This leads to a prohibitively
large number of possible correspondences to be tested. Therefore, an alignment by

corresponding point pairs is not practical even though it is feasible.

116

 
 

Y t
Template Minutia

      
   
 

 

 

 

Rotate
. (A9) Template Ridge
l\ N
Translate}
(Ax,Ay) / V\
Input Minutia Input Ridge

 

 

>
X

Figure 6.1: Alignment Of the input ridge and the template ridge.

It is well known that corresponding curve segments are capable of aligning two
point patterns with a high accuracy in the presence of noise and deformations [68].
Each minutiae in a ﬁngerprint is associated with a ridge. Therefore, it is clear that
a true alignment can be achieved by aligning corresponding ridges (see Figure 6.1).
During the minutiae detection stage, when a minutiae is extracted and recorded,
the ridge on which it resides is also recorded. This ridge is represented as a planar
curve with its origin coincident with the minutiae and its x-coordinate being in the
same direction as the direction of the minutiae. Also, this planar curve is normalized
with the average inter-ridge distance. By matching these ridges, the relative pose
transformation between the input ﬁngerprint and the template can be accurately

estimated. To be speciﬁc, let Rd and RD denote the sets of ridges associated with

117

the minutiae in the input and the template, respectively. Our alignment algorithm is

described as follows:

1. For each ridge d 6 Rd, represent it as an one-dimensional discrete signal and
match it against each ridge, D 6 RD according to the following formula:

251:0 diDi
V iL=O (1?th

where L is the minimal length of the two ridges and d,- and D, represent the
distances from point i on the ridges d and D to the x-axis, respectively. The
sampling interval on a ridge is set to the average inter-ridge distance. If the
matching score S (0 S S S 1) is larger than a certain threshold T, (0.8), then
go to step 2, otherwise continue to match the next pair of ridges.

 

s = (6.4)

2. Estimate the transformation between the two ridges (Figure 6.1). Generally, a
least-square method can be used to estimate the pose transformation. However,
in our system, we observe that the following method is capable of achieving
the same accuracy with fewer computations. The translation vector (Ax, Ay)T
between the two corresponding ridges is computed as

Ax x“ x0
(Ail—(ydl—(Wl’ (6'5)
where (xd,yd)T and (xD,yD)T are the x and y coordinates of the two minu-

tiae, which are called reference minutiae, associated with the ridges d and D,
respectively. The rotation angle A6 between the two ridges is computed as

= £37.- — n), (6.6)

i=0

A0

where L is the minimal length of the two ridges d and D; 7,- and F,- are radial
angles of the ith point on the ridge with respect to the reference minutiae asso-
ciated with the two ridges d and D, respectively. The scaling factor between the
input and template images is assumed to be 1.

3. Denote the minutiae (xd,yd,6d)T, based on which the transformation parame-
ters are estimated, as the reference minutiae. Translate and rotate all the N
input minutiae with respect to this reference minutiae, according to the following
formula:

Ax cos A0 sin A9 0 x,- — xd
2 Ag + sin A0 — cos A0 0 y,- — yd , (6.7)
014 A9 0 0 1 9,- - 0d

118

where (x,,y,~,6,)T, (i = 1,2,...,N), represents an input minutiae and

(xf‘,y{4,6{‘)T represents the corresponding aligned minutiae.
Note that, because the aspect ratio of the pixels in our acquisition devices is not

one (non-square pixels), a rectiﬁcation is performed before the alignment.

6.5 Alignment Hypothesis Evaluation

If two identical point patterns are exactly aligned with each other, then each pair
of corresponding points are completely coincident. In such a case, a point pattern
matching can be simply achieved by counting the number of overlapping pairs. How-
ever, in practice, such a situation is rarely encountered. On the one hand, the error in
determining and localizing minutiae hinders the alignment algorithm to recover the
relative pose transformation exactly, while on the other hand, our alignment scheme
does not model the nonlinear deformation of ﬁngerprints which is an inherent prop-
erty of ﬁngerprint impressions. With the existence of such a nonlinear deformation, it
is impossible to exactly recover the position Of each input minutiae with respect to its
corresponding minutiae in the template. Therefore, the aligned point pattern match-
ing algorithm needs to be elastic which means that it should be capable of tolerating,
to some extent, the deformations due to inexact extraction of minutiae positions and
nonlinear deformations. Usually, such an elastic matching can be achieved by placing
a bounding box around each template minutiae, which speciﬁes all the possible posi-
tions Of the corresponding input minutiae with respect to the template minutiae, and
restricting the corresponding minutiae in the input image to be within this box [121].

This method does not provide a satisfactory performance in practice, because local

 

deform
large,

COmpe;

119

(r5.C5,05) (r'hc'hejx) (13,63,131)
((4.0411‘) (1.3963963)
(r- L.- 0) ”494-94. (T290592)
-/\ (rt-01991)
\\\ \ -~ /
(rﬁ'eﬁveh) I \ / (rl ,el ’6‘)
-— - " '*\ .4. ---------------- ->
Reference Minutiae ‘ '— e r
"‘ r7,°7,97)
fl}, .C(,.O,,_)
(1‘7,C7,87)
__l _ ____ll ________ l, J _l___l __ _I»
Template 6 Input c

Figure 6.2: The string matching of a pair of point patterns.

deformations may be small while the accumulated global deformations can be quite
large. We have proposed an adaptive elastic matching algorithm with the ability to

compensate the minutiae localization errors and nonlinear deformations.

Our adaptive elastic matching algorithm consists of two main steps: (i) represent-
ing minutiae patterns as a string in the polar coordinate system and (ii) matching
the strings with a dynamic programming algorithm to establish the correspondence.
Minutiae matching in the polar coordinate system has several advantages. Although
the deformation of ﬁngerprints depends on a number of factors such as impression
pressure and impression direction, the deformation in a local region is usually con-
sistent and it may become less consistent as one moves further away from the region
where the ﬁngerprint patterns are consistent (see Figure 3.7). Consequently, it is eas-

ier to represent and manipulate the representations in polar coordinate space (with

 

pa

HIE

Ce]

120

81(m,n)\

Template minutia
81(m.n) ,. ’

   

u <—— Reference minutia

Figure 6.3: Bounding box and its adjustment.

origin at a point of maximal consistency between the reference and aligned test tem-
plate). At the same time, it is easier to formulate rotation, which constitutes the main
part of the alignment error between an input image and a template, in the polar space
than in the Cartesian space. The symbolic string generated by concatenating points
in an increasing order of radial angle in polar coordinates uniquely represents a point
pattern. This reveals that point pattern matching can be achieved with a string

matching algorithm.

A number of string matching algorithms have been reported in the literature [37].
Generally, string matching can be thought of as the maximization/minimization Of
a certain cost function such as the edit distance. Including an elastic term in the
cost function of a string matching algorithm can achieve a certain amount of error

tolerance. Given two strings Pp and Q1, of lengths M and N, respectively, we deﬁne

the “edit 1

C(m. n)

where

u.'(m. n)

Ac

.10

121

the “edit distance”, C (M, N) recursively as follows:

 

 

 

 

 

0 if m = 0 and n = 0
C(m — 1, n) + it
C(m,n) = l (6.8)
minl C(m,n_1)+Q )0<m§Mand0<n§N,
L \ C(m—1,n—1)+w(m,n)]
where
alri—rf,’ +ﬁAe+7A0 if]r,’,’,—rf,3<6,Ae<candA0<g
w(m, n) = (6.9)
Q otherwise,
a if (a 2 (e5, -— e? + 360) mod 360) < 180
Ae = (6.10)
a — 180 otherwise,
a if (a = (of; — 0,? + 360) mod 360) < 180
A0 = (6.11)

a — 180 otherwise,

a, 0, and 'y are the weights associated with radius, radial angle, and minutiae direc-
tion, respectively; 6, e and 9 specify the bounding box; and fl is a pre-speciﬁed penalty
for a mismatch. Such an edit distance, to some extent, captures the elastic property
of string matching. It represents the cost of changing one polygon to the other. The
intuitive meaning of the string matching is depicted in Figure 6.2. However, this
scheme can only tolerate, but not compensate for, the adverse effect on matching
produced by the inexact localization of minutiae and nonlinear deformations. There-

fore, an adaptive mechanism is needed. This adaptive mechanism should be able

 

SC.

b(

w}

122

to track the local nonlinear deformation and inexact alignment and try to alleviate
them during the minimization process. However, we do not expect that this adaptive
mechanism can handle the “order ﬂip” of minutiae, which, to some extent, can be

solved by an exhaustive re-ordering and matching within a local angular window.

In our matching algorithm, the adaptation is achieved by adjusting the bounding

box (Figure 6.3) when an inexact match is found. It can be represented as follows:

 

 

 

61(m, n) < (r5, — r3) < 6h(m,n)
a Inf. — r? + we + 7A0 if mm, is < Ae < than, n)
wl(m, n) = < (6.12)
A0 < p
L (2 otherwise,
where
51(mm) < (7‘5. - 7‘3) < Mm”)
r5, — r3
Ara if 61(m, n) < Ae < ch(m,n)
Aea A0 < p
0 otherwise,
61(m +1,n +1) 2 61(m, n) + nAra, (6.14)
6,,(m + 1, n +1) 2 6,,(m, n) + nAra, (6.15)
61(m+1,n+1) = q(m,n) +r1Aea, (6.16)
ch(m +1,n +1) 2 6,,(m, n) + nAea, (6.17)

w'(m,n) represents the penalty for matching a pair of minutiae (r;,e,’,’,,0,’,3,)T and

 

 

 

box
This
to it

follo

and
resul

pair.

6.6

Giver:
frOm

treme
the m
impre,
numbe
precise
mod-at,
(from,

h: ‘
d\e D1

123

(r3, e3, 0,?)T, 6,(m, n), 6,,(m, n), 51(771, n), and ch(m, n) specify the adaptive bounding
box in the polar coordinate system (radius and radial angle), and r} is the learning rate.
This elastic string matching algorithm has a number of parameters which are critical
to its performance. We have empirically determined the values of these parameters as
follows: 61(0, 0) = —8; 6,,(0, 0) = +8; 6;“), 0) = —7.5; ch(0, 0) = +7.5; 9 = 30; a = 1.0;
0 = 2.0; 7 = 0.1; Q = 200(a +,B+'y); r) = 0.5. The values of 6)(0,0), 6h(0,0), ((0,0),
and ch(0,0) depend on the resolution Of ﬁngerprint images. Figure 6.4 shows the
results of applying the matching algorithm to an input and a template minutiae set

pair.

6.6 Summary

Given two minutiae sets, minutiae matching determines whether they are extracted
from the ﬁngerprint impressions of the same ﬁnger. Minutiae matching is an ex-
tremely diﬂicult problem for the following reasons: (i) the correspondence between
the minutiae sets is not known, (ii) presence of relative translation, rotation, and
impression deformations between the two minutiae sets, (iii) presence of a signiﬁcant
number of spurious minutiae and missing minutiae, and (iv) minutiae may not be
precisely located. A good minutiae matching algorithm should be able to accom-
modate these transformations, missing minutiae, spurious minutiae, small position
errors, shear transformation, and linear and non-linear differential distortions. We

have proposed an alignment-based elastic matching algorithm. This algorithm is

124

v

 

(c) (d)

Figure 6.4: Results of applying the matching algorithm to an input minutiae set and
a template; (a) input minutiae set; (b) template minutiae set; (c) alignment result
based on the minutiae marked with green circles; (d) matching result where template
minutiae and their correspondences are connected by green lines.

 

capab
hausti
its ca}

transﬁ

125

capable of ﬁnding the correspondences between minutiae without resorting to an ex-
haustive search. It achieves a good performance in minutiae matching because of
its capability to adaptively compensate for the nonlinear deformations and inexact

transformations between mated ﬁngerprints.

 

C]

Dr

A bio

charm
biome
System
System

multi-n;

A “Him
metric s
of ill Un
tion. A I

lions. F1“,

Chapter 7

Decision Fusion

A biometric system can be based on either a (or one snapshot of a) single biometric
characteristic or multiple biometric characteristics (or multiple snapshots of a single
biometric characteristic) to make a personal identiﬁcation. We deﬁne a biometric
system which uses only a single biometric characteristic as a unimodal biometric
system and a biometric system which uses multiple biometric characteristics as a

multimodal biometric system.

7 .1 Multimodal Biometrics

A unimodal biometric system is usually more cost-effective than a multimodal bio-
metric system. However, it may not always be applicable in a given domain because
of (i) unacceptable performance and (ii) inability to Operate on a large user popula-
tion. A multimodal biometric system can overcome, to a certain extent, these limita-
tions. First of all, identiﬁcation using multiple biometrics is essentially a sensor fusion

126

 

probi
capal
of in«
ofthl
requi
neces
ﬁu'ai
beap
gener
Inuhi
In
ered;
Opera
biOmg
DEnd

dE‘SlgI

127

problem, which utilizes information from multiple sensors to increase fault-tolerance
capability, to reduce uncertainty, to reduce noise, and to overcome incompleteness
of individual sensors [33, 133]. A multimodal approach can increase the reliability
of the decisions made by a biometric system [20, 45, 82, 16]. Although a necessary
requirement for a biometric characteristic is that each individual possess it, it is not
necessary that a particular biometric characteristic of a speciﬁc individual is suitable
for an automatic system. By using multiple biometric characteristics, the system will
be applicable on a larger target population. Finally, a multimodal biometric system is
generally more robust to fraudulent technologies, because it is more difﬁcult to forge
multiple biometric characteristics than to forge a single biometric characteristic.

In designing a multimodal biometric system, a number of issues need to be consid-
ered: (i) what is the main purpose of utilizing multiple biometrics? (ii) what is the
Operational mode? (iii) which biometrics should be integrated? and (iv) how many
biometrics are sufﬁcient? Since the applicable population and system robustness de-
pend mainly on the characteristics of the selected biometrics, the main problem in
designing a multimodal biometric system is the integration of individual biometrics
to improve the performance of personal identiﬁcation. Typically, performance refers
to (i) accuracy and (ii) speed. System accuracy indicates how reliable and conﬁdent a
biometric system is in differentiating between a genuine individual and an impostor.
System speed refers to the time taken by a biometric system in making a personal
identiﬁcation. By properly incorporating those biometrics that are relatively fast, the
overall Speed of a biometric system can be improved.

A biometric system can operate in either a veriﬁcation mode or an identiﬁcation

128

 

 

l Biometric
Subsystem 1

 

 

 

 

 

 

 

' l
. I
Claimed : Decision Fusion —-—>
3 Claimed Identify Veriﬁed
Biometric
Subsystem N

 

 

 

4

Template Database

 

 

 

 

Figure 7.1: A generic multimodal veriﬁcation system.

mode. The integration schemes for these two modes are very different. Since only a
one-to—one comparison is performed in a veriﬁcation system, multimodal biometrics
cannot really improve the veriﬁcation speed. Therefore, integration of multiple bio-
metrics in a veriﬁcation system is mainly intended to improve the accuracy of the
system. The block diagram of a generic multimodal veriﬁcation system is shown in
Figure 7.1. In a typical identiﬁcation system, a large number of matchings need to
be performed to identify an individual. A biometrics that has a large discriminating
power can improve the identiﬁcation accuracy, while a biometrics that is computa-
tionally efﬁcient can improve the identiﬁcation speed. The block diagram of a generic

multimodal identiﬁcation system is shown in Figure 7.2.

Which biometrics and how many of them should be integrated depend very much
on the application domain. It is difﬁcult to establish a systematic procedure to deter-
mine which biometrics should be used. Intuitively, the larger the number of integrated
biometrics, the higher the system accuracy, but more expensive the system. In this

thesis, we mainly concentrate on improving the system performance by integrating

 

 

 

tWO

7.1.

Integ
follo-
exam

ure'

129

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Retrieval _ 9 Veriﬁcation ‘
Subsystem 1 Subsystem 1
_> ,
: _> Database 1
Retrieval , Veriﬁcation
Subsystem N

 

Subsystem N

 

 

 

 

 

 

 

 

lit I

Decision Fusion —>
Established Identity

 

 

 

 

Figure 7.2: A generic multimodal identiﬁcation system.

two speciﬁc biometrics, namely face and ﬁngerprint.

7 .1.1 Multimodal Biometrics for Veriﬁcation

Integration of multiple biometrics for a veriﬁcation system may be performed in the
following scenario: (i) integration of multiple snapshots of a single biometrics, for
example, several ﬁngerprint images of the same ﬁnger in ﬁngerprint veriﬁcation (Fig-
ure 7.3) and (ii) integration of a number of diﬂ'erent biometrics (Figure 7 .4). In this
sense, multimodal biometrics is a conventional decision fusion problem - to combine
evidence provided by each biometrics to improve the overall decision accuracy. Gen-
erally, multiple evidences may be integrated at one of the following three different
levels [19]: (i) Abstract level; the output from each module is only a set of possible
labels without any conﬁdence value associated with the labels; in this case, the sim-
ple majority rule may be employed to reach a more reliable decision [156], (ii) Rank

level; the output from each module is a set of possible labels ranked by decreasing

130

   
 

Decision Fusion

 

Figure 7 .3: Integration of multiple snapshots of a single biometric characteristic.

conﬁdence values, but the conﬁdence values themselves are not speciﬁed; (iii) Mea-
surement level; the output from each module is a set of possible labels with associated
conﬁdence values; in this case, more accurate decisions can be made by integrating

different conﬁdence values.

Dieckmann et al. [45] have proposed an abstract level fusion scheme: “2—from-3
approach” which integrates face, lip motion, and voice based on the principle that a
human uses multiple clues to identify a person. This approach uses a simple voting
algorithm to ﬁnd whether the decision made by each individual classiﬁer is consistent
with the other two classiﬁers. Brunelli and Falavian [20] have proposed two schemes
to combine evidence from speaker veriﬁcation and face recognition. The ﬁrst scheme
is a measurement level scheme in which the outputs of two different speech classiﬁers
and the outputs of three different face classiﬁers are normalized and combined using

geometric average. The second scheme is a hybrid rank/ measurement level scheme

     

Decision Fucion

uouguBooag 3312:]

 
    

Figure 7.4: Integration of different biometric characteristics.

which uses HyperBF network to combine the outputs of these ﬁve classiﬁers. The
authors have demonstrated that the system accuracy can be improved by using these
fusion schemes. Kittler et al. [82] have demonstrated the efﬁciency of an integra-
tion strategy which fuses multiple snapshots of a single biometrics using a Bayesian
framework. In this scheme, the a posteriori class probabilities for each individual are
estimated and the decision is made based on the average or maximum or median of
the a posteriori class probabilities for a given set of snapshots. Bigun et al. [16] have
proposed a Bayesian integration scheme to combine different evidences based on the
assumption that the evidences are independent of one another. Their scheme results
in an improved recognition accuracy by combining voice and face as well as voice and

lip motion. Maes et al. [89] have proposed to combine biometric data (e.g., voice)

132

with non-biometric data (e. g., password).

7 .1.2 Multimodal Biometrics for Identiﬁcation

All the decision fusion schemes mentioned above can be used to improve the identiﬁca-
tion accuracy in a multimodal identiﬁcation system. However, since an identiﬁcation
system needs to perform one-to—many comparisons to ﬁnd a match, the average com-
putational complexity for each comparison should be as low as possible to enable a
reasonable response time, especially for a large database. However, the integration
schemes mentioned above increase the computational complexity for each compari-
son. Therefore, it is not practical to directly apply these schemes to an identiﬁcation
system; an integration scheme that is able to improve both the speed and the accu-
racy should be used. We introduce a multimodal biometrics scheme which integrates
two biometrics (in particular, face and ﬁngerprint) which complement each other in
terms of identiﬁcation speed and identiﬁcation accuracy: a biometric approach (e. g.,
face recognition) that is suitable for database retrieval is used to index the template
database and a biometric approach (e.g., ﬁngerprint veriﬁcation) that is reliable in
deterring impostors is used to ensure the overall system accuracy. In addition, since
each biometric approach provides a certain conﬁdence about the identity being es-
tablished, a decision fusion scheme which exploits all the information at the output
of each module can be used to make a more reliable decision. We have designed a
integrated biometric system which uses this decision fusion scheme to integrate face

recognition and ﬁngerprint veriﬁcation in making a personal identiﬁcation [63]. The

 

ff)
' ’1
U1

tior
stag
fror
n p«
ﬁna

and

7.2

In th
front
the f;
we H
devic
ﬁxed

the se

133

system essentially consists Of a face recognition subsystem and a ﬁngerprint veriﬁca-
tion subsystem, which are integrated by a decision fusion module. It operates in three
stages: (i) the face recognition subsystem retrieves the top n matches of a query face
from the template database, (ii) the ﬁngerprint veriﬁcation subsystem veriﬁes the top
n possible matches and provides the corresponding ﬁngerprint matching scores, and
ﬁnally (iii) the decision fusion module integrates the results from the face recognition

and the results from the ﬁngerprint veriﬁcation to establish the ﬁnal decision.

7 .2 Face Recognition

In the context of personal identiﬁcation, face recognition refers to static, controlled full
frontal portrait recognition [30]. By static we mean that the facial portraits used by
the face recognition system are still facial images (intensity or range). By controlled
we mean that the type Of background, illumination, resolution of the acquisition
devices and the distance between the acquisition devices and faces, etc. are essentially
ﬁxed during the image acquisition process. Obviously, in such a controlled situation,
the segmentation task is relatively simple and the intra—class variations are small.
Generally, there are two major tasks in face recognition: (i) locating faces in input
images and (ii) recognizing the located faces. Face location itself continues to be a
challenging problem for uncontrolled and cluttered images [30]. Fortunately, in the
context of personal identiﬁcation, the background is controlled or almost controlled,
so face location is generally not considered to be a difﬁcult problem for a face-based

biometric system. Face recognition from a general view point remains an open prob—

 

lem

illuu
cont
striC

perfc

contt
can I
imag
feasil
nique
9pm

more

(2) tr:
COFIeE
face If

134

lem because transformations such as position, orientation, and scale and changes in
illumination produce substantially large intra-class variations [114]. Again, in the
context of personal identiﬁcation, the variations in acquired face images can be re—
stricted to a certain limit, which enables the current techniques to achieve a desirable
performance [30, 114].

In our system, the eigenface approach is used for the following reasons: (i) in the
context of personal identiﬁcation, the background, transformations, and illumination
can be controlled, (ii) eigenface approach has a compact representation - a facial
image can be concisely represented by a feature vector with a few elements, (iii) it is
feasible to index an eigenface-based template database using diﬂ'erent indexing tech-
niques such that the retrieval can be conducted efﬁciently [139], and (iv) the eigenface
approach is a generalized template matching approach which was demonstrated to be
more accurate than the attribute-based approach [20].

The eigenface-based face recognition consists of the following two stages [144]:
(i) training stage in which a set of training face images are collected; eigenfaces that
correspond to the M highest eigenvalues are computed from the training set; and each
face is represented as a point in the M-dimensional eigenspace, and (ii) Operational
stage in which each test image is ﬁrst projected onto the M -dimensional eigenspace;
the M -dimensional face representation is then deemed as a feature vector and fed to
a classiﬁer to establish the identity of the individual.

A W x H face image I (x, y) can be represented as a W x H -dimensional feature
vector by concatenating the rows of I (x, y) together. Thus, each W x H face image

becomes a point in the W x H -dimensional Space. The value of W x H is typically

 

km

31

 

la rg
sucl
and

Don

 

Figure 7.5: First eight eigenfaces obtained from 542 training images of size 92 x 112;
they are listed, from left to right and top to bottom, in decreasing values of the
corresponding eigenvalues.

large, on the order of several thousands for even small image sizes. Face images in
such a high dimensional space are not randomly distributed. Therefore, it is efﬁcient
and beneﬁcial to project them to a lower dimensional subspace using principle com-
ponent analysis [144]. Let \Ill,\I12,\IIN denote the N W x H—dimensional training
vectors with zero-mean. Let the M basis vectors, u1,u2, ..., uM be a set of orthonor-
mal vectors that best describe the distribution of face images in the M -dimensional
subspace (eigenspace), M < N. The kth vector, uk,k = 1,2,...,M, is computed

such that [144]

N
/\k = 2(UE‘I’1V (7.1)

 

isr

The

esti

The

her

“he:

the :

136

is maximum, subject to

1, ifi =j
iruj = (7-2)
0, otherwise.

The value /\,c is the kth largest eigenvalue of the covariance matrix 2 which can be

estimated using the training samples by
. 1 N
2 = — Z waif. (7.3)
N i=1

The vector uk is the kth eigenvector of the covariance matrix 2 corresponding to M.

With the M-dimensional eigenspace deﬁned, training vectors, \1'1, \112, ~ - - , \IIN, can
be represented as a set of M -dimensional feature vectors, (1)1, <I>2, - ' - , (EN:
4),, = uT\IIi, i: 1,2, . --,N, (7.4)

where u = (111, 112, ..., uM). Figure 7.5 shows the ﬁrst 8 eigenfaces corresponding to

the 8 largest eigenvalues.

In the operational phase, a detected face image, I‘, which is normalized to zero
mean, is vectorized and projected onto the eigenvectors according to H = uTI‘.
With both training samples and test samples being projected onto M-dimensional
eigenspace, face recognition can be accomplished by a classiﬁer operating in the
eigenspace. In the context of personal identiﬁcation, only a very limited number

of training samples is available for each individual [106]. Thus, a k-nearest neighbor

classiﬁe
Space I

l: 41

ll

7.3

Thede.
lusioris
ckﬂons

dechdol
bmnmt
tics ma
PTObabj
mate [3‘

bE’tWee l

7.3.1

A mOde
ing alg(
donﬂl’:
may be

31mm 18

137

classiﬁer is typically used, in which the distance, (1, called Distance From Feature
Space (DFFS) [144] between a template, <I>, and a test pattern, II, is deﬁned as

||<I> -— II“, where H 0 || means L2 norm.

7 .3 Decision Fusion

The decision made by each biometrics has an associated conﬁdence value. A decision
fusion scheme should utilize all these conﬁdence values associated with individual de-
cisions to reach a more reliable decision. As we mentioned early, in order to derive a
decision fusion scheme, we need to deﬁne (t) a conﬁdence measure for each individual
biometrics and (it) a decision fusion criterion. The conﬁdence of a given biomet-
rics may be characterized by its false acceptance rate (FAR), which is deﬁned as the
probability of an impostor being accepted as a genuine individual. In order to esti-
mate FAR, the impostor distribution which is deﬁned as the distribution of similarity

between biometric characteristic(s) of different individuals needs to be computed.

7 .3.1 Impostor Distribution for Fingerprint Veriﬁcation

A model that can precisely characterize the impostor distribution of a minutiae match-
ing algorithm is not easy, since (2) the minutiae in a ﬁngerprint are distributed ran-
domly in the region of interest, (it) the region of interest for each input ﬁngerprint
may be different, (zz'z') each input ﬁngerprint tends to have a different number of
minutiae, (iv) there may be a signiﬁcant number of spurious minutiae and missing

minutiae, (v) sensing, sampling, and feature extraction may result in errors in minu-

tiae p
it is p

some

Le
registc
of the
tessell
large (
are wi‘
cells i1
DUmhe
and 981

Of the

138

tiae positions, and (v2) sensed ﬁngerprints may have different distortions. However,
it is possible to obtain a general model of the overall impostor distribution by making

some simplifying assumptions.

Let us assume that the input ﬁngerprint and the template have already been
registered and the region of interest of both the input ﬁngerprint and the template is
of the same size, a W x W (for example, 500 X 500) region. The W x W region is
tessellated into small cells of size 21) x 22). These cells are assumed to be sufficiently
large (for example, 40 x 40) such that possible deformation and transformation errors
are within the speciﬁed bound. Therefore, there are a total of g x 113—(:2 NC) different
cells in the region of interest. Further, assume that each ﬁngerprint has the same
number of minutiae, Nm (3 NC), which are distributed randomly in different cells
and each cell contains at most one minutiae. Each minutiae is directed towards one
of the D (for example, 8) possible orientations with equal probability. Thus, for a
given cell, the probability, Pempty, that the cell is empty with no minutiae present is
%‘:l and the probability, P, that the cell has a minutiae that is directed towards a
speciﬁc orientation is 5532M. A pair of corresponding minutiae between a template
and an input is considered to be identical if and only if they are in the cells at the
same position and directed in the same direction (see Figure 7.6). With the above

simplifying assumptions, the number of corresponding minutiae pairs between any two

randomly selected minutiae patterns is a random variable, Y, which has a binomial

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Template Minutiae Set Input Minutiae Set

Figure 7.6: Minutiae matching model. A solid line indicates a match and a dashed
line indicates a mismatch.

distribution with parameters Nm and P [113]:

Nm!

90’) = Y!(Nm — Y)

 

'PY(1 — P)(N""Y). (7.5)

The probability that the number of corresponding minutiae pairs between any two

minutiae patterns is less than a given threshold value, y, is

0(2) = W < y) = ”S: gas). (7.6)
k=0

The decision made by the proposed minutiae matching algorithm for an input

ﬁngerprint and a template is based on the comparison of the “normalized” number

of cc
ﬁon

ranth

7JL.

The (
Due 1
needs
identi
Le
match
Which
(in Org
in the
The Sn
relativg
DFFSs
bHRY a
Probabi
that the
lends to

ThUSatl

140

of corresponding minutiae pairs against a threshold. Therefore, under the assump-
tion that minutiae in the region of interest of ﬁngerprints of different individuals are

randomly distributed, the probability that an impostor is accepted is (1 — G (311)).

7 .3.2 Impostor Distribution for Face Recognition

The characterization of impostor distribution for face recognition is more difﬁcult.
Due to the relatively low discrimination capability of face recognition, this module
needs to keep the top n matches to guarantee that the genuine individual will be

identiﬁed if he or she is in the database.

Let (P1,<I>2, ...,CDN be the N face templates stored in the database. The top n
matches, (DE, g,...,<1>;, are obtained by searching through the entire database, in
which N comparisons are conducted explicitly (in the linear search case) or implicitly
(in organized search cases such as the tree search). The top 72 matches are arranged
in the increasing order of DFF S (Distance From Feature Space, Section 2) values.
The smaller the DFFS value, the more likely it is that the match is correct. Since the
relative distances between consecutive DFFSs are invariant to the mean shift of the
DFFSs, it is beneﬁcial to use relative instead of absolute DFFS values. The proba-
bility that a retrieved top n match is incorrect is different for different ranks. The
probability that the ﬁrst match is incorrect tends to be smaller than the probability
that the second match is incorrect, the probability that the second match is incorrect
tends to be smaller than the probability that the third match is incorrect, and so on.

Thus, the impostor distribution should be a decreasing function of rank order and

141
it is a function of both the relative DFF S values, A, and the rank order, 2', which
has the following form: F,(A)Porde,(2'), where FAA) represents the probability that
the consecutive DFF S between impostors and their claimed individuals at rank 2' are
larger than a value A and Porderu) represents the probability that the retrieved match
at rank 2' is an impostor. In practice, 17,-(A) and Porder(2') need to be estimated from

empirical data.

In order to simplify the analysis, we assume that each individual has only one face
template in the database. Thus, there are a total of N individuals enrolled in the
database and 11, 12, ..., I N are used as identity indicators. Let X 0' denote the DFFS
between an individual and her own template which is a random variable with density
function fa(X°) and let X15, X53, ..., Xf,_1 denote the DFFSs between an individual
and the templates of the other individuals in the database, which are random variables
with density functions, ff (X f3 ), ff(X2ﬁ), ..., f £_1(X 164), respectively. Assume that
X“ and X€,X€,...,X£-_l are statistically independent and f16(Xf3) = f2ﬂ(X25) =
...fg_1(X,HV_1) = f5(X3). For an individual, II, who has a template stored in the
database, {(191,<I>2, ...<I>N}, the rank, R, of X“ among X?,X2B,...,X£,_l is a random

variable with probability

 

where

142

When p < 1 and N is sufﬁciently large, P(R) may be approximated by a Poisson

distribution [113],

 

P(R = 2) e , (7.9)

where a i np. Obviously, P(R = 2) is exactly the probability that matches at rank i

are genuine individuals. Therefore,
Porde,(2') = 1 — P(R = 2'). (7.10)

Although the assumption that X15, Xg, ..., X {Ll are 2'.2..d may not be true in practice,
it is still reasonable to use the above parametric form to estimate the probability that
retrieved matches at rank i are impostors. Our experimental results support this
claim.

Without any loss of generality, we assume that, for a given individual, H,
X 13 , X5 , ..., X 54 are arranged in increasing order of values. Deﬁne the non-negative

distance between the (2 + 1)th and 2th DFFS values as the ith DFFS distance,
A,- =Xf’+, -Xf’, 13 2' < N— 1. (7.11)

The distribution, f,(A,-), of the 2th relative distance, A,, is obtained from the joint

distribution 212,-(X5, 13,-) of the 2th value, X '6 , and the ith relative distance, 13,-,

m.) = /_°° Mata-MW, (7.12)

where
dmtan

than 2

7.3.:

The '1
print
bY'th
One C
indlv

Eithe

143
more, A.) = CF"(X3)“1[1 — F300” + A2)]N"'f"(xﬁ)fﬁ(xe + 21,-), (7.13)

N—l !
C = (2—1()!(N—)2—2')!’ (7'14)

 

where F5(X*3) = If: f5(X5)dX5 [57]. With the distribution, f,(A,-), of the 2th
distance deﬁned, the probability that the DFFS of the impostor at rank 2' is larger

than a threshold value, A, is
FAA) = /: f.(A.)dA.-. (7.15)

The above equations do not make any assumptions about the distributions of
X15,X23,...,Xf(,_1 as long as they are 2'.in The equations also hold even if the
mean values of X {3 ,Xg , ...,X £4 shift. Therefore, it can tolerate, to a certain ex-
tent, DFFS variations which is a desirable property. In our system, we assume that
X15,X2B,...,X1€_1 are distributed with a Gaussian distribution with unknown mean

and variance.

7 .3.3 Decision Fusion

The impostor distribution for face recognition and the impostor distribution for ﬁnger-
print veriﬁcation provide conﬁdence measures for each of the top n matches retrieved
by the face recognition module. Without a loss of generality, we assume that at most
one of the 72 possible identities established by the face recognition module for a given
individual is the genuine identity of the individual. The ﬁnal decision by integration

either rejects all the 72 possibilities or accepts only one of them as the genuine identity.

0

144

In practice, it is usually speciﬁed that the FAR of the system should be less than a
given value [106]. Therefore, the goal of decision fusion, in essence, is to derive a

decision criterion which satisﬁes the FAR speciﬁcation.

It is reasonable to assume that the DFFS between two different individuals is
statistically independent of the ﬁngerprint matching score between them; facial sim-
ilarity between two individuals does not imply that they have similar ﬁngerprints,
and vice versa. This assumption should not be confused with the situation where an
impostor tries to fool the system by counterfeiting the face and/or ﬁngerprints of the
genuine individual. Let F,(A)Pm-der('i) and C(Y) denote the impostor distribution
at rank 2' for face recognition and ﬁngerprint veriﬁcation modules, respectively. The

composite impostor distribution at rank 2' may be deﬁned as

am, Y) = mmemexacm. (7.16)

Let {11,12, ..., In} denote the 72 possible identities established by face recognition,
{X1, X2, ..., Xn} denote the corresponding 72 DFFSs, {1"1,Y2, ..., Yn} denote the corre-
sponding n ﬁngerprint matching scores, and F ARO denote the speciﬁed value of FAR.
The ﬁnal decision, I D(II), for a given individual II is determined by the following
criterion:

Hk(Ak, Yk) < FARO, and
1k, if

1W1) = Hum, Y2) = min{H1(A1, Y1), Hummus} (7-17)

impostor, otherwise,

when
accep
l'.th

x.
Aheni
the d
in th«
IV arc
satisf
full a
UpdaI
indivi

inforr

7.4

‘4 luc
”C ch
"lulu;
idem i
501117.
aCQUr;

a df‘cj

145

where A,- = X,“ — Xi. Since H,(A, Y) deﬁnes the probability that an impostor is
accepted at rank 2' with consecutive relative DFFS, A, and ﬁngerprint matching score,

Y, the above decision criterion satisﬁes the FAR speciﬁcation.

Note that the decision criteria in Eq. (7.17) depends on the number of individuals,
N, enrolled in the database, since F,- depends on N. However, it does not mean that
the distributions of Rs have to be recomputed whenever a new individual is enrolled
in the database. In fact, if N >> 1, the distributions of F,s for different values of
N are quite similar to one another. On the other hand, the decision criterion still
satisﬁes the FAR speciﬁcation when N increases, though it may not be able to take
full advantage of the information contained in the N comparisons. In practice, an
update schema which recomputes the decision criteria whenever the number of added
individuals is larger than a pre-speciﬁed value can be used to exploit all the available

information.

7 .4 Summary

A biometric system which is based only on a (or one snapshot of a) single biomet-
ric characteristic may not always be able to achieve the desired performance. A
multimodal biometrics technique, which combines multiple biometrics in making an
identiﬁcation, can be used to overcome the limitations. Integration of multimodal
biometrics for an identiﬁcation system has two goals: (2') improve the identiﬁcation
accuracy and (22') improve the identiﬁcation speed (throughput). We have developed

a decision fusion scheme which integrates two different biometrics (face and ﬁnger-

146

print) that complement each other. In this scheme, a biometrics that is suitable for
database retrieval is used to index the template database and a biometrics that is
reliable in deterring impostors is used to ensure the overall system accuracy. In ad-
dition, a decision fusion scheme which exploits all the information in the decisions
made by each individual biometrics is used to make a more reliable decision.

The decision fusion schema may be applied to similar scenarios in other domains
to provide a better discrimination performance. For example, in image database
retrieval, a less reliable but computationally attractive algorithm may be used to
retrieve the top 72 matches; then a more reliable, but computationally more expensive
algorithm may be used to verify the t0p 72 matches; and ﬁnally a decision fusion

scheme can be used to reach a more reliable decision.

The]
tofa(
aretl
Then
Print:
ﬁnger
Catiol

the d;

AIlau
of Dre

Geller

Chapter 8

Fingerprint Classiﬁcation

The main advantage of ﬁngerprint classiﬁcation is that it provides an indexing scheme
to facilitate efficient matching in large ﬁngerprint databases; if two ﬁngerprint images
are the impressions of the same ﬁnger, then they must belong to the same category.
Therefore, a query ﬁngerprint needs to be compared only with the database ﬁnger-
prints of the same category in the ﬁngerprint matching process. Without an effective
ﬁngerprint classiﬁcation scheme or some other indexing scheme, ﬁngerprint identiﬁ-
cation involves an exhaustive matching of query ﬁngerprint to all the ﬁngerprints in

the database, which is computationally demanding [85].

8.1 Automatic Fingerprint Classiﬁcation

An automatic ﬁngerprint classiﬁcation algorithm classiﬁes a ﬁngerprint into a number
of pre—speciﬁed categories according to the features extracted from the ﬁngerprint.
Generally, the pre-speciﬁed categories could be either the categories deﬁned in Chap-

147

 

ter2

inay

teres
tlie (
and
speci
suﬁk
depe
Gﬁki
shou
each

thej

148

ter 2 or a “new” set of categories which have not been used by forensic experts, but
may be easily recognized automatically.

For automatic ﬁngerprint classiﬁcation, the following ﬁve issues are of great in-
terest: (2') number of ﬁngerprint categories, (22') distribution of ﬁngerprints among
the categories, (222') consistency of classiﬁcation scheme, (2'22) classiﬁcation accuracy,
and (v) computational requirements of the classiﬁcation algorithm. Property (2')
speciﬁes that a classiﬁcation algorithm should be able to classify ﬁngerprints into a
sufﬁciently large number of categories. The effectiveness of the indexing mechanism
depends on the number of categories; the larger the number of categories, the more
efﬁcient the resulting indexing mechanism. Property (22') emphasizes that ﬁngerprints
should be distributed uniformly among the categories of interest; it is desirable that
each category should contain the same number of ﬁngerprints. The more uniformly
the ﬁngerprints are distributed among the categories of interest, the more effective
the resulting indexing mechanism. Property (222') suggests that the ﬁngerprints in
each category of interest should be similar in terms of global pattern conﬁguration.
Property (2'21) stipulates that classiﬁcation scheme should be able to reach a desirable
classiﬁcation accuracy. If the classiﬁcation scheme can not reach a desirable accuracy,
then the classiﬁcation scheme will be useless for the purpose of indexing. Property (2))
says that the classiﬁcation should be performed quickly. If the classiﬁcation is more
expensive than conducting a linear search of a ﬁngerprint database, then it is mean-
ingless to use the classiﬁcation scheme to index the ﬁngerprint database. Ideally, an
automatic ﬁngerprint classiﬁcation algorithm should be able to quickly classify ﬁnger-

prints into a signiﬁcant number of categories consistently with a desirable accuracy.

II] [)I

iris;

gﬂobz
expel

good

. ‘u “|
N
‘

-. \ \ '\"~."\ ‘~...‘

.\‘
\,‘\

ﬁ
.3
.

\ ..
_. . \ ‘ \
. ‘ 5

N93

as

emusxx
.‘u ‘11.“:
‘5‘:
\x -

I

(xxx-~37

ih

1'.”
. 'f’ f

.5".

.'

.I'
t
1

1..
1

an in.

Don I]

149

In practice, due to the complex and noisy nature of ﬁngerprint ridge conﬁgurations,
it is a major challenge to design such a ﬁngerprint classiﬁcation algorithm.

Due to large variations in the ridge pattern conﬁguration, the deﬁnition of the
global pattern features used to specify the classiﬁcation criteria used by ﬁngerprint
experts is very complex and vague. When the quality of input images is not very
good, it is extremely difﬁcult for an automatic algorithm to reliably extract these
“high level” features from the images. Therefore, the performance of the ﬁngerprint
classiﬁcation algorithms based on these global features is far from desirable. On the
other hand, the classiﬁcation criteria used by ﬁngerprint experts is sufﬁciently vague
that it may classify ﬁngerprints with similar pattern conﬁgurations into different
categories. Figure 8.1 shows examples of ﬁngerprints that appear similar but are

classiﬁed into different categories according to ﬁngerprint experts.

5‘33,“ ,
re \\\

   
 
 

 

1’ / ‘ fr 1": l ' \\;:

/ ”figs“: ‘
.' 1‘ ‘- \ ‘1 \

. , : I‘l/l/ \\ \
22:1

)‘

rl'f 7 .‘ I

f I \\ ‘3“ to
1 //

\Xi.‘\

 
  

11w"
’- l

i)
ll
,3.

 

Figure 8.1: Examples of ﬁngerprints from different categories; (a) tented arch; (b)
loop; (c) whorl; it seems that all the ﬁngerprints shown here should be in the loop
category.

As mentioned early, the ﬁngerprint classiﬁcation is intended for quickly providing

an indexing mechanism and to give an indication of general pattern agreement. It is

not necessarily required that ﬁngerprints should be classiﬁed according to the tradi-

tionz
is at

distr

a ﬁn
and '
Orien

mod¢

We” .

rapid

150

tional classiﬁcation scheme. Essentially, what is needed is a classiﬁcation scheme that
is able to consistently and correctly classify ﬁngerprints into a number of uniformly
distributed categories with large intra-class similarity and small inter-class similarity.
A central problem in designing such a classiﬁcation scheme is to decide what features
should be used to classify ﬁngerprints and how categories are deﬁned based on these
features. These ﬁngerprint features should be invariant to the translation and rota-
tion of the input ﬁngerprint images and be able to capture the inherent nature of
the global ﬁngerprint pattern conﬁguration. Global ﬁngerprint features are mainly
derived from the orientation ﬁeld and global ridge shape. The orientation ﬁeld of
a ﬁngerprint consists of the local ridge orientation tendency in local neighborhoods
and forms an abstraction of the local ridge structures. It has been shown that the
orientation ﬁeld is highly structured and can be roughly approximated by a core-delta
model [104]. Therefore, singular points and their relationship can be used to derive
ﬁngerprint categories.

Previous approaches to ﬁngerprint classiﬁcation can be roughly divided into two
categories: (2') statistical approach [22, 21, 23, 10, 17, 55] and (22') structural ap-
proach [32, 78, 80, 119, 101, 90, 102]. A statistical approach classiﬁes a ﬁngerprint
using feature vectors derived directly from the orientation ﬁeld of the input images.
A structural approach extracts and represents ﬁngerprints using a number of salient
ﬁngerprint properties and their relationships. These algorithms perform reasonably
well when the input ﬁngerprint images are of good quality. When the quality of
the input ﬁngerprint images is poor, the performance of these algorithms degrades

rapidly. The major reason for the brittleness of these algorithms is that they do not

151

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ridge Ridge Ridge '1

' Extraction Veriﬁcation Classiﬁcation
Orientation Orientation Singularff
. , Point? .1
Estimation Interpclﬁnon' Detection.

 

 

Figure 8.2: The ﬂow-chart of the ﬁngerprint classiﬁcation algorithm.

utilize robust features.

We have designed two ﬁngerprint classiﬁcation schemes based on the features
mentioned above. One follows the approach to classify ﬁngerprints into ﬁve categories
(arch, tented arch, left loop, right loop, and whorl) according to the extracted cores,
deltas, and ridge shape. The other scheme classiﬁes ﬁngerprints into four categories
which depends on pattern similarity based on cores and deltas. The main stages of
the classiﬁcation algorithms are depicted in Figure 8.2, which can be divided into two
parts: (2') feature extraction and (22') classiﬁcation scheme. The feature extraction

module extracts two types of features: (2') singular points, and (22') ﬁngerprint ridges.

8.2 Feature Extraction

For local orientation estimation and ridge extraction, we use the same procedure as
used for minutiae extraction algorithm. Our algorithm spends a signiﬁcant amount
of effort to improve the quality of extracted orientation ﬁeld and ridges, which results

in a more robust feature extraction and classiﬁcation. In order to understand the

152

 

 

 

 

 

 

 

 

 

 

 

 

core delta

Figure 8.3: Singular points.

algorithm, some additional deﬁnitions are given.

8.2.1 Deﬁnitions

A Recurring ridge is deﬁned as a chain of pixels, r1, r2, ..., rn, in a thinned ridge map,
where r1 is the ﬁrst ridge pixel, r" is the last ridge pixel, and each pair of consecutive
pixels, (r,_1,r,-) is eight connected, which cumulatively turns more than a certain
degree when traveling from r, to r,, where 1 S i < j S n.

A singular point is either a core point or a delta point which is characterized by
its position and type (see Figure 8.3). A core is deﬁned as a point in the orientation
ﬁeld where the orientation in a small local neighborhood around the point presents
semi-circular tendency. A delta is deﬁned as a point in the orientation ﬁeld where a
small local neighborhood around the point forms three sectors and the orientation in

each sector presents hyperbolic tendency.

153
8.3 Ridge Veriﬁcation

Since ridge structures in poor-quality ﬁngerprint images are not always well-deﬁned, it
may lead to: (i) incorrect local ridge orientation estimates and (ii) incorrect extracted
ridges. It is very difﬁcult to correctly classify a ﬁngerprint based on the incorrect
orientation ﬁeld and incorrect ridge structure. Therefore, a noise removal algorithm

should be applied to obtain more precise orientation estimates and ridges.

A direct way to ensure that orientation ﬁeld estimation and ridge extraction are
robust with respect to the quality of input ﬁngerprint images is to enhance the in-
put images before orientation estimation and ridge extraction. As long as the ridge
structures are not corrupted completely, it is possible to develop an enhancement
algorithm to improve the clarity of ridge structures in corrupted ﬁngerprint images.
However, the extraction of local orientation and ridge structure are intertwined; a

correct estimate of either one will result in a correct estimate of the other.

Fingerprint ridges are highly structured both locally and globally. Locally, each
ridge runs parallel to the neighboring ridges. Globally, ridges form families of similar
types of smooth curves. In an extracted ridge map, ridges in the well-deﬁned regions
satisfy the above properties, while in the corrupted regions, they do not have such
properties. Therefore, we can use these properties to differentiate the corrupted
ridges from the true ridges. The orientation ﬁeld in the regions where the true ridges
appear can be correctly estimated as the tangent direction of the ridges. If the
true regions occupy most of the ﬁngerprint image, we can correctly interpolate the

local orientation in those regions where true ridges are not identiﬁed using these true

154

 

   
 
 
      

lql

)’

(x(i+1)£9y(i+l)£)

)
(HM

I
(“7 V) /

Figure 8.4: Ridge veriﬁcation.

 

 

 

local orientations. Obviously, if the corrupted regions occupy a signiﬁcant portion
of the ﬁngerprint image, the true local orientation may not be recovered using the
interpolation method.

We have developed a ridge veriﬁcation algorithm which receives as input a thinned
ridge map and outputs a reﬁned thinned ridge map, a reﬁned orientation ﬁeld, and
a quality index which indicates the goodness of the input ridge map. Let ’R, 0’, and
72’ be the input ridge map, the interpolated orientation ﬁeld, and the veriﬁed ridge

map, respectively. The major steps in our ridge veriﬁcation algorithm are as follows:

I. Initialize (9’, ’R’, and A which is a map used to indicate the true regions.

2. Delete all ridge pixels in ’R. which have more than two 8—connected neighboring
pixels to ensure that each ridge is a single 8-connected chain.

3. Trace and label all the ridges in R.

155

4. For each traced ridge, r = {(x1,y1), (x2, yg)..., (xn, yn)}, represented in terms of
the coordinates of points on it, do the following:

o smooth r.

0 let (3322,3116) and ($(i+1)ea y(i+1)e) denote the starting point and ending
point of a segment in r, where e is the length of the segment and i =
0,6,26, ..., [n—z-Eje. Find the 2 nearest neighboring ridge points which are
on the line that crosses (x16, y“) and perpendicular to the ridge segment on
both sided of the segment: (22, u) and (u’, u’) and the 2 nearest neighboring
ridge points which are on the line that crosses (x(,-+1)E, y(,-+1)¢) and perpen-
dicular to the ridge segment on both sided of the segment: (p, q) and (p’, q’).
Note that (magic), (x(,-+1)(,y(,-+1)6), (p, q), and (u,u) form a quadrilateral
at one side of the segment and (3316,3116), (113011)“ y(,-+1)¢), (p’, q’), and (u’, '0')
form a quadrilateral at the other side of the segment.

0 for each quadrilateral, ﬁnd the minimum rectangle that contains the quadri-
lateral. Compute the ratio, 77, between the area of the quadrilateral and the
area of the minimum rectangle. If r) is larger than a threshold (770 = 0.75),
then label all the pixels inside the quadrilateral as foreground pixels. 0th-
erwise, label them as background pixels.

5. Remove in A all the foreground connected components whose area is less than
a threshold (we 2 15 )

6. Fill in A all the background connected components whose area is less than a
threshold (r0 = 15).

7. Compute local orientation at all the pixels in 0’ where the corresponding pixels
in A are foreground pixels as the orientation of the nearest ridge segment.

8. Interpolate the local orientation at all pixels in 0’, where the corresponding
pixels in A are background pixels.

9. Return the percentage of the area of the foreground regions in A with respect to
total area of A as the quality index.

An example of ridge veriﬁcation is depicted in Figure 8.5, which demonstrates that

a better orientation ﬁeld can be obtained by using our ridge veriﬁcation algorithm.

8.3.1 Singular Point Detection

A singular point is deﬁned as the point where the vector ﬁeld is not continuous, which

can be characterized using Poincare index. The Poincare index at a given point, (x, y),

156

   
 

/////—'~\\\\\\\\\

 
   

////////////’e—~~\\\\\\\\\
////////
//ﬂ’/////—’—’ad—F~'—-—ov——~——‘——-—-————

 

/..-”~__-M\\\

   

 
  

\\\\\\\\\\\\\\\\\\\\\\

   

/// /////////--,-\\\\\\\\\\
/// /////////wi—~\\\\\\\\\
//////////4a~~~~—~~\\\~\\\\
//////////-——-—\—-—————\\\\\\\
//’///////-o~~~~——————r~‘\\\\\

(d) (6)

Figure 8.5: Ridge veriﬁcation; (a) input image; (b) orientation ﬁeld; (c) thinned ridge
map, ((1) veriﬁed ridge map, where the veriﬁed ridges are marked with gray shade;
(e) interpolated orientation ﬁeld.

 
  

/
/

 
 
       
   

157

in a vector ﬁeld, V, is deﬁned as follows:

27r
Poincare(x, y) = 517—; 113(1) {/0 glitz: + 5 cos 6, y + 5 sin 6)d0}. (8.1)

If the Poincare index at a given point (x, y) is not equal to zero, then the point (x, y)
is called a singular point. The Poincare index of a core-shaped singular point in a
vector ﬁeld has a value of 1 and the Poincare index for a delta-shaped singular point

has a value of -1.

It has been shown that the orientation ﬁeld of a ﬁngerprint image can not be
unambiguously represented as a vector ﬁeld [104]. The deﬁnition of Poincare index
needs to be extended to the orientation ﬁeld. Let 0’ be the orientation ﬁeld. The

Poincare index at a given point (i, j) is deﬁned as follows:

 

. . . 1 . 2" 3 , . . .
P02ncare(2,]) — 57? 113(1) {/0 50 (2 + ecos 0,] + esm 0MB} , (8.2)
where
d6, if |d6| < 7r/2,
8
50’(i + ecos 0,j + esin 0) = 7r + d6, if d6 S _W/g, (8.3)
7r — d6, otherwise,
d6 = lim 0 (2 +ecos(0 + 11),] +esm(6+ V)) — 0 (2 +ecosl9,] +es1n6’). (8.4)

u—>0 V

In an orientation ﬁeld, the Poincare index of a core-shaped singular point has a value

of 1 / 2 and the Poincare index of a delta-shaped singular point has a value of -1 / 2. In

158
a digital image, the computation of the Poincare index is implemented by replacing
the integration in Eq. (8.2) by a summation of all orientation differences along a
closed digital curve. Let \III(-) and \Ily(-) represent the x and y coordinates of a closed
digital curve with ‘1! pixels. The Poincare index at pixel (i, j) which is enclosed by

the digital curve can be computed as follows:

17
Poincare(i,j) = 21; Z A(k), (8.5)
1:20
where
d6(k), if |d6(k)| < 7r/2,
A(k) = 71 + 216(k), if 215(1) 3 41/2, (8-6)

77—d6(k), otherwise,
d6(k) = o'(\11.((z'+1)Moo\11),\p,((z'+1)Mooxr))—o'(\p,(2),\11,(2)).(s.7)

The size of the closed digital curve is crucial for the performance of a singular point
detection algorithm using the Poincare index. If it is too small, then a small per-
turbation of orientations may result in spurious singular points being detected. On
the other hand, if it is too large, then a true pair of core and delta which are close
to one another may be ignored because the Poincare index of a digital curve that
includes an equal number of cores and deltas is 0. We have developed a singular
point detection algorithm which uses a closed square curve with a length of 25 pixels.
We have empirically determined that a curve of 25 pixels is a good trade-off between

detections and misses of singular points. Let (9’ be the interpolated orientation ﬁeld.

 

Figure 8.6: Singular point detection: a core is labeled by a rectangle and a delta is
labeled by a triangle.

The main steps in our singular point detection algorithm are as follows:
1. Initialize A, which is a label image used to indicate the singular points.

2. For each pixel (i, j) in (9’, compute the Poincare index and assign the corre-
sponding pixel in A a value 1 if the Poincare index is (1/2} and a value 2 if the
Poincare index is {-1/2).

3. Find each connected component in A with pixel values 1. If the area of the
connected component is larger than 7, a core is detected at the centroid of the
connected component. If the area of the connected component is larger than 20,
then two cores are detected at the centroid of the connected component.

4. Find each connected component in A with pixel values 2. If the area of the
connected component is larger than 7, a delta is detected at the centroid of the
connected component.

5. If more than two cores or more than two deltas are detected, smooth the orien-
tation ﬁeld 0’ and go back to step 1.

Although the heuristic that at most two cores and two deltas exist in a ﬁngerprint
is not always true, it is rarely observed that a ﬁngerprint has more than two cores
and two deltas. Results of applying our singular point detection algorithm on two

ﬁngerprint images are shown Figure 8.6.

8.3.2 Recurring Ridges

The global shape of ridges determines the global conﬁguration of ﬁngerprints. Ridges

in ﬁngerprints are highly structured. Generally, in the upper region (which can be

160

roughly deﬁned as the region above the highest core points in loops, tented arches,
and whorls and the region above the most curved ridges in arches) of a ﬁngerprint,
ridges are a family of uni-modal smooth curve segments. In the bottom region,
ridges form a family of relatively ﬂat curves. In the middle region, depending on
the ﬁngerprint class, ridges may be of the following types: uni-modal curve segment,
recurring segment, circular segments, multi-recurring segments, spiral segments, etc.
The presence of a particular type of ridges deﬁnes the class of a ﬁngerprint. If the ridge

type can be accurately determined, then the ﬁngerprint can be correctly classiﬁed.

We classify ridges into three categories: (i) non-recurring ridge, (ii) type-1 re-
curring ridge, and (iii) type-2 recurring ridge. Let r = {r1,r2, ...,rn} be a ridge of
length n, where r1 is the ﬁrst ridge pixel, rn is the last ridge pixel, and each pair of
consecutive pixels is eight connected. Then r’ = {r1, r2,, ..., rm}, where m = [Hz—9],
is obtained by sampling r at intervals of length 6. Deﬁne the cumulative orientation

of r as:

A01) = 15:: WW
pa), if 111/«)1 < 1.
w(k) = 2n + p(k), if p(k) 3 —7r,

2n — p(k), otherwise,
WC) = 190$) - :90: -1),

where 29(k) represents the angle from r’ (k) to r’ (k + 1). Deﬁne any sequence of ridge

pixels in r, {r,-,r2,...,rj}, where 1 S i < j _<_ n, a sub-ridge of r. A non-recurring

161

ridge, r, is a ridge such that the cumulative orientation of any sub-ridge of r is less
than a threshold, Tnon 2 150°. A type-1 recurring ridge, r, is a ridge such that
the cumulative orientation of any sub-ridge of r is between the two thresholds, Tnon
and Tree = 270°. A type-2 recurring ridge, r, is a ridge such that the cumulative
orientation of any sub-ridge of r is larger than a threshold, Tm or a ridge such
that there exist multiple disjoint sub-ridges of r, which are type-1 recurring ridges.
Obviously, uni-modal ridge segments and ﬂat ridge segments are non-recurring ridges.
Circular ridge segments, multi-recurring ridge segments and spiral ridge segments are
type-2 recurring ridges.

It is very difﬁcult to correctly extract all the true ridges from an input ﬁngerprint
image, especially when the quality of the input ﬁngerprint image is poor. It is essen-
tial that a ridge classiﬁcation algorithm be able to handle the following undesirable
situations: (2) spurious ridges, (22') broken ridges, and (iii) missing ridges. Ridge ver-
iﬁcation (see Figure 8.5) can be used to remove all the spurious ridges from a ridge
map. Broken ridges can be connected based on the information present near the end
of broken ridges. However, it is very difficult to recover missing ridges. This needs
both high-level structural analysis and local structural analysis of the ridge pattern,
which is very difﬁcult to formulate and implement. We have developed a ridge clas-
siﬁcation algorithm which traces each ridge in the veriﬁed ridge map and classiﬁes
each ridge into one of the three categories mentioned above (Figure 8.7). The main

steps of the algorithm are depicted as follows:

1. Trace and label all the ridges in 72’.

2. For each traced ridge, r : {r1,r2, ...,rn}, expand r at both ends to generate a
new ridge and repeat the expansion operation until the new generated ridge can

162

ll
11

1

ll

 

l)

(a) (b) (C)

Figure 8.7: Ridge classiﬁcation; (a) ridges classiﬁed as non-recurring ridges; (b) ridges
classiﬁed as type-1 recurring ridges; and (c) ridges classiﬁed as type-2 recurring ridges.

not be expanded anymore. Ridge expansion is to connect r with a ridge in ’R.’
at the end points to generate a new ridge with the condition that the expanded
ridge is consistent with the original ridge at the expansion points.

3. Compute the A0 of the expanded ridge and classify it according to the criteria
mentioned above.

Examples of ridge classiﬁcation are shown Figure 8.7.

8.4 Classiﬁcation

Fingerprints can be classiﬁed into a number of pre—speciﬁed categories based on the

features extracted from the orientation ﬁeld and ridge map.

8.4.1 Classiﬁcation Scheme I

This classiﬁcation scheme classiﬁes input ﬁngerprints into ﬁve categories according
to the number of singular points detected, their relative position and presence of
type-1 and type-2 recurring ridges. These categories are: (i) arch, (ii) tented arch,
(222) left loop, (iii) right loop, and (v) whorl. A prototype of each class is shown in

Figure 8.8. Let 0’ be the interpolated orientation ﬁeld; NC and Nd be the number of

163

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(8)

Figure 8.8: Fingerprint class prototypes; (a) arch; (b) tented arch; (c) left loop; ((1)
right loop; and (e) whorl; the dashed lines in (b), (c), and (d) are the symmetric axes.

164

cores and deltas detected from 0’, respectively; N1 and N2 be the number of type-1

recurring ridges and type-2 recurring ridges in 72’. The classiﬁcation criteria used in

our algorithm is depicted as follows:

1.
2.

9.
1 0.

If (N2 > 0) and (NC = 2) and (Nd : 2), then a whorl is identiﬁed.
If(N1 = 0) and (N2 = 0) and (Nc = 0) and (Nd = 0), then an arch is identiﬁed.

If (N1 > 0) and (N2 = 0) and (Nc = 1) and (Nd = 1), then classify the input
using the core and delta assessment algorithm given below.

If (N2 > T2) and (NC > 0), then a whorl is identiﬁed.

If (N1 > T1) and (N2 = 0) and (Nc = 1) then classify the input using the core
and delta assessment algorithm.

If (NC = 2), then a whorl is identiﬁed.

If (Nc = 1) and (N; = 1), then classify the input using the core and delta
assessment algorithm.

If (N1 > 0) and (NC = 1), then classify the input using the core and delta
assessment algorithm.

If (NC = 0) and (Nd = 0), then an arch is identiﬁed.

If none of the above conditions is satisﬁed, then reject the ﬁngerprint.

The core and delta assessment algorithm is used to classify an one-core and one-

delta ﬁngerprint into one of the following categories: (i) left loop, (ii) right loop, and

(iii) tented arch. It is depicted as follows:

1.
2.

Estimate the symmetric axis which crosses the core in its local neighborhood.

Compute the angle, oz, between the line segment from the core to the delta and
the symmetric axis.

Compute the average angle difference, 5, between the local ridge orientation
on the line segment from the core to the delta and the orientation of the line
segment.

Count the number of ridges, 7, that cross the line segment from the core to the
delta.

If (a < 10°) or (,6 < 15°) and (7 = 0), then classify the input as a tented arch.

165
6. If the delta is on the right side of the axis, then classify the input as a left loop.

7. If the delta is on the left side of the axis, then classify the input as a right loop.

8.4.2 Classiﬁcation Scheme 11

This classiﬁcation scheme classiﬁes ﬁngerprints into four categories according to the
number of singular points detected and their relative positions. Let Nc and Nd be the
number of core and delta points detected from 0’, respectively; (C¢1,Cy1), (C12, Cyg),
be the x and y coordinates of the cores, respectively; If (Nc = 1), then (C32, Cyg) =
(—1,—1); if (Nc = 0), then (Cx1,Cy1) = (C22,Cy2) = (—1,—1); Let (Dthyl),
(D22, Dyg), be the x and y coordinates of the deltas, respectively; if (Nd = 1), then
(ng,Dy2) = (—1,—1); If (Nd = 0), then (D31,Dy1) = (D32,Dy2) = (—1,—1). The
deﬁnition of the four categories is as follows:
1. If (NC = 2 ), then the ﬁngerprint is a class-1 ﬁngerprint.
2. If (Nc = 1) and (Nd = 1) and (d((C31,Cy1), (D11,Dy1)) > S) and the
delta is at the right side of the symmetric axis, where S is a threshold and

d((Cxl,Cy1), (Du, Dy1)) is the distance between (Cxl,Cy1) and (D31, Dyl), then
the ﬁngerprint is a class-2 ﬁngerprint.

3. If (N, = 1) and (N, = 1) and (d((C11,Cy1),(Dx1,Dy1)) > S) and the
delta is at the left side of the symmetric axis, where S’ is a threshold and
d((Cxl,Cy1), (D11, Dy1)) is the distance between (C31,Cy1) and (D31, Dyl), then
the ﬁngerprint is a class-3 ﬁngerprint.

4. If none of the above conditions is satisﬁed, then the ﬁngerprint is a class-4
ﬁngerprint.

In this classiﬁcation scheme, a class-1 ﬁngerprint corresponds to a whorl in the
traditional classiﬁcation scheme. Class-2 ﬁngerprints and class-3 ﬁngerprints are ﬁn-

gerprints of loop, and tented arch with the distance between core and delta being

166

rather large. Class-4 ﬁngerprints consist arches and loops and tented arches with a

small distance between core and delta.

8.5 Summary

Fingerprint classiﬁcation provides an important indexing mechanism for automatic
ﬁngerprint identiﬁcation. At a ﬁrst glance, the ﬁngerprint classiﬁcation problem
appears to be rather simple. But, because of large intraclass and small interclass
variations in global pattern conﬁguration and due to poor quality of input images,
the desired accuracy of 1% error rate at 20% reject rate is very difficult to achieve.
We have designed two ﬁngerprint classiﬁcation algorithms. One classiﬁes input ﬁn-
gerprints into ﬁve categories according to the number of singular points detected,
their relative positions, and presence of type-1 and type-2 recurring ridges. The other
scheme classiﬁes ﬁngerprints into four categories. Since we invest a signiﬁcant amount
of effort in feature extraction so that the features are robust to interclass variations as
well as poor quality of input images, the resulting classiﬁcation algorithms are more

robust to image quality.

Chapter 9

Experimental Results

The biometrics community is slow in establishing benchmarks for biometric sys-
tems [44]. Although, benchmark results on standard databases in themselves are
useful only to a limited extent and may result in excessive tuning of the system pa-
rameters to “improve” the system performancel, they constitute a good starting point
for comparing the gross performance characteristics of the systems.

No metric is sufﬁciently adequate to give a reliable and convincing indication
of the identiﬁcation accuracy of a biometric system. In principle, we can use the
false (impostor) acceptance rate (FAR), the false (genuine individual) reject rate
(FRR) and the equal error rate (EER)2 to indicate the identiﬁcation accuracy of
a biometric system [106, 42, 43]. In practice, these performance metrics can only
be estimated from empirical data and the estimates of the performance are very

data dependent. Therefore, they are meaningful only for a speciﬁc database in a

 

1Several additional techniques like data-sequestering [114] and third party benchmarking [18]
may also help in obtaining fairer performance results.
2Equal error rate is deﬁned as the value where FAR and FRR are equal.

167

168

speciﬁc test environment. For example, the manufacturer of a particular biometric
system claimed that the system had an FRR of 0.3% and an FAR of 0.1%. An
independent test by the Sandia National Lab. found that the same system had
an FRR of 25% with an unknown FAR [75]! In order to provide a more reliable
assessment of a biometric system, some more descriptive performance measures are
necessary. A receiver operating curve provides an empirical assessment of the system
performance at different operating points which is more informative than FAR and
FRR. The statistical metric (1’ gives an indication of the separation between the
genuine distribution and impostor distribution [43]. It is deﬁned as the difference
between the means of the genuine distribution and impostor distribution divided by

a conjoint measure of their standard deviations [43]:

 

(1,: ”MW“... — 2119......“ , (9.1)
Jon-2mm... + SD3....-...)/2
where Mgenume, SDgenume, Mimposm, and SDimposto, are the means and standard
deviations of the genuine distribution and impostor distribution, respectively. Like
FAR, FRR, and EER, both ROC and d’ also depend heavily on test data and test
environments. For such performance metrics to be able to precisely generalize to the
entire population of interest, the test data should (i) be large enough to represent the
population and (ii) contain enough samples from each category of the population [43].
To obtain fair test results, enough samples should be available, the samples should
be representative of the population, and adequately represent all the categories (im-

postors and genuine). Further, irrespective of the performance measure, error bounds

169

that indicate the conﬁdence of the estimates are valuable for understanding the sig-

niﬁcance of the test results.

9.1 Test Databases

The MSU ﬁngerprint database contains 10 images (640 x 480) per ﬁnger from 150
individuals for a total of 1,500 ﬁngerprint images, which were captured with a scanner
manufactured by Digital Biometrics. When these ﬁngerprint images were captured,
no restrictions on the position and orientation of ﬁngers were imposed. The captured
ﬁngerprint images vary in quality. Figure 9.1 shows some of the ﬁngerprint images
in our database. Approximately 90% of the ﬁngerprint images in our database are
of reasonable quality similar to those shown in Figure 9.1, while about 10% of the
ﬁngerprint images in our database are not of good quality (Figure 9.2), which are
mainly due to large creases and smudges in ridges and dryness of the impressed
ﬁnger.

A portion of the N IST 9 ﬁngerprint database is also used in our experiments. N IST
9 ﬁngerprint database contains 1,350 mated ﬁngerprint card pairs (image size is 832 x
768) that approximate a natural distribution of the National Crime and Information
Center (NCIC) ﬁngerprint classes (examples of ﬁngerprints in the NIST 9 database
are shown in Figure 9.3) [149]. It is divided into multiple volumes. Each volume has
3 CD’S. Each CD contains 900 images of card type 1 and 900 images of card type
2. Fingerprints on card type 1 were scanned using a rolled method and ﬁngerprints

on card type 2 were scanned using a live-scan method. The ﬁngerprint images in

Figure 9.1:
Biometrics;
same ﬁnger.

170

 

Fingerprint images captured with a scanner manufactured by Digital
the size of these images is 640 x 480; images in each row are from the

171

     

Figure 9.2: Fingerprint images of poor quality.

NIST 9 database are more challenging compared to the live-scan ﬁngerprint images
for a number of reasons, including: (i) the NIST 9 ﬁngerprints are a combination of
dabs and rolled impressions; large discrepancy between the number of minutiae in
test and reference template inherently skews the matching score normalization; (ii)
a large number of NIST 9 images are of much poorer image quality than a. typical
live-scan ﬁngerprint image; (iii) NIST 9 images often contain extraneous objects like
handwritten characters and other artifacts common to inked ﬁngerprints. Although
only one-half of the ﬁngerprint images in NIST 9 ﬁngerprint database are live-scan
images and there exists a large distortion between 3 rolled ﬁngerprint and a live-scan
ﬁngerprint, we can still use this database to generate some statistics and comparative

performance numbers for our matching algorithm.

NIST 4 ﬁngerprint database contains 4,000 images (image size is 512 x 480) taken
from 2,000 different ﬁngers, two images per ﬁnger. Five ﬁngerprint classes are de-

ﬁned: (2) Arch, (ii) Tented arch, (iii) Left Loop, (iv) Right Loop, and (v) Whorl.

172

 

 

      

  

lH‘llE "

 

 

SI

 

 

a ... Y -.

 

 

 

 

 

 

 

 

 

 

 

 

Figure 9.3: Examples of ﬁngerprints in the N IST 9 database; the size of these images
is 832 x 768.

173

Fingerprints are uniformly distributed among these ﬁve classes. NIST 4 database
is compiled for evaluating the performance of a ﬁngerprint classiﬁcation algorithm.

Examples of ﬁngerprints in the NIST 4 database are shown in Figure 9.4 [150].

A database from IBM which contains 1,044 live-scan ﬁngerprint images (varying
image size) was also used to test the performance of our classiﬁcation algorithm.
Fingerprints in the IBM database are classiﬁed manually by ﬁngerprint experts into:
(2) Arch, (ii) Tented arch, (222) Left loop, (iv) Right loop, (v) Whorl, (vi) Twin,
and (vii) Composite. Examples of ﬁngerprints in the IBM database are shown in
Figure 9.5.

A composite public domain face database was used in the performance evaluation
of the identiﬁcation system. The face database contains a total of 1,132 images of 86
individuals (examples of images in this database are shown in Figure 9.6); 400 images
of 40 individuals with 10 images per individual are from the Olivetti Research Lab.,
300 images of 30 individuals with 10 images per individual are from the University
of Bern, and 432 images of 16 individuals with 27 images per individual are from
MIT Media Lab. The images were re-sampled from the original sizes to a ﬁxed size

of 92 X 112 and normalized to zero mean.

9.2 Feature Extraction Performance

It is very difficult to independently assess the performance of feature extraction algo-
rithms. Accuracy of the extracted minutiae was subjectively conﬁrmed in two ways.

Visual inspection of a large number of typical minutiae extraction results showed that

174

 

Figure 9.4: Examples of ﬁngerprints in the NIST 4 database; the size of these images
is 512 x 480.

 

Figure 9.5: Examples of ﬁngerprints in the IBM database.

176

 

Figure 9.6: Examples of faces in the composite database.

177

 

 

 

 

 

 

 

100 f I T I I I r I T
90— —
801- j
A 70- / 4
12’ new
2
E soL a
g 50- old / ‘
<
E 40— f
30- -4
20- -
1o 4
o 1 J. l i L l 4 l
o 1 2 3 4 5 6 7 a 9 10

False Acoeptanco Rate (‘71.)

Figure 9.7: Receiver Operating Curves; the vertical axis is (1-FRR); the ROC shows
the improvement in veriﬁcation performance of the new minutiae extraction algorithm
in contrast to the algorithm in [120].

our algorithm rarely missed minutiae in reasonable quality ﬁngerprint images.

We have compared the performance of our feature extraction algorithm with that
of the feature extraction algorithm in [120]. The premise underlying this experiment
is that given an identical matcher, the accuracy of the system indicates the perfor-
mance of the feature extraction algorithm. We extracted ﬁngerprint representations
from a sample set of ﬁngerprint images using our feature extraction algorithm. The
veriﬁcation accuracy was estimated using a Hough-transform based matcher [121] by
performing an “all against all” veriﬁcation test to obtain distributions of match and
mismatch scores. The same test was also performed on the features extracted from
our previous feature extraction algorithm [120]. The ROCs resulting from these two
experiments are shown in Figure 9.7. The CPU time required by our new feature

extraction algorithm to process a 640 x 480 ﬁngerprint image is, on an average, 1.1

 

178

seconds on a UltraSPARC workstation whereas the CPU time for the old algorithm is
16.1 seconds. Thus, we can see that the new minutiae extraction algorithm results in
a signiﬁcant improvement in the overall accuracy as well as the speed of the system.
Note that the above accuracy improvement is context dependent, i.e., it reveals the
accuracy improvement when the Hough-transform based matcher is used. However,
since the accuracies of both the matchers depend solely on the correctness of the ex-
tracted minutiae, the performance of our matcher should also improve with the new

minutiae extraction algorithm.

9.3 Fingerprint Enhancement Performance

The purpose of a ﬁngerprint enhancement algorithm is to improve the quality of
input ﬁngerprint images and make them more suitable for the minutiae extraction
module. Therefore, the ultimate criterion for evaluating such an enhancement algo-
rithm is the amount of performance improvement when the algorithm is applied to
the noisy ﬁngerprint images. In order to evaluate the performance of our ﬁngerprint
enhancement algorithm, we have conducted two experiments using the veriﬁcation
system on a subset of the MSU ﬁngerprint database which consists of 700 images of
70 individuals.

In the ﬁrst experiment, the ﬁngerprint enhancement algorithm was not applied.
Each ﬁngerprint image in the database was directly matched against the other ﬁnger-
print images in the database. In the second experiment, our ﬁngerprint enhancement

algorithm was ﬁrst applied to each ﬁngerprint image in the database. Then, the ver-

 

100 1 Y V ' V "YI

I V V Y W r f1 I V 1 Y YYYYY I T t ' U v v
w/ enhancement M

    

90

80

7o~ ~

60- x

40" -(

Authentic Acceptance Rate (%)
0|
0
l
l

 

 

 

20- 4
1o- —
O 1 L L 1 J#.l . 1 L L 1 A 111 L 1 i A . i ..l . i i A 1 141
1 o‘2 10‘1 10° 10‘ 102

False Acceptance Rate (%)

Figure 9.8: Receiver Operating Curves; the ROC shows the improvement in veriﬁca-
tion performance of the enhancement algorithm.

iﬁcation is conducted on the enhanced ﬁngerprint images. The ROCs resulting from
these two experiments are shown in Figure 9.8. From these experimental results, we
can observe that the performance of the online ﬁngerprint veriﬁcation system is signif-
icantly improved when our ﬁngerprint enhancement algorithm is applied to the input
ﬁngerprint images. In particular, using the enhancement algorithm has substantially

reduced the reject rate while maintaining essentially the same recognition rate.

9.4 System Performance

We ﬁrst evaluated the matching scores of correct and incorrect matches and then eval-

uated the performance of the veriﬁcation system in conducting identity authentication

180

and the performance of the identiﬁcation system in conducting personal identiﬁcation.

9.4.1 Matching Scores

   

(a) (b) '1

Figure 9.9: Fingerprint images from the same ﬁnger.

In test 1, each of the ﬁrst 1,500 ﬁngerprints in the MSU ﬁngerprint database was
matched with all the other ﬁngerprints in the database. A matching was labeled
correct if the matched ﬁngerprint was from the same ﬁnger, and incorrect otherwise.
A total of 2,248,500 (1, 500 x 1, 499) matchings were performed. The distributions
of correct and incorrect matching scores are shown in Figure 9.12(a). In test 2, each
of the 900 ﬁngerprints of card type 1 in the NIST 9 (CD No. 1) was matched with
all the 900 ﬁngerprints of card type 2. A matching was labeled correct if a matched
ﬁngerprint was from the same ﬁnger. A total of 810,000 (900 X 900) matchings were
performed on this database (to our knowledge, no comparative results are available
on NIST 9 database). The distributions of correct and incorrect matching scores
are shown in Figure 9.12(b). Table 9.1 lists the d’ values in addition to the mean
and standard deviation of correct and incorrect matching scores. The large variance

of correct matching scores is mainly due to different number of detected minutiae,

 

181

 

 

 

 

Database d’ Mean Standard Deviation Mean Standard Deviation
(correct) (correct) (incorrect) (incorrect)
MSU 2.26 23.46 13.59 1.56 0.71
NIST-9 2.01 18.76 11.22 2.39 0.83

 

 

 

 

 

 

 

 

Table 9.1: d’ and mean and standard deviation of the correct and incorrect matching
scores.

quality of acquired ﬁngerprint images, and ﬁngerprint distortion. For example, the
ﬁngerprint images shown in Figures 9.9(a) and (b) are captured from the same ﬁnger.
However, only a small region of interest is common to these two ﬁngerprint images
(approximately 30%). Obviously, it is very difﬁcult to make a highly conﬁdent decision
based only on the limited number of minutiae appearing in the region of interest which
are common to both the ﬁngerprints. In practice, such a problem can be solved
by requiring that each input ﬁngerprint image should have a sufficient amount of
overlapping region of interest with its stored template(s). Figure 9.10 shows a mated
pair in the MSU database that has a relatively low matching score (8). Figure 9.11
shows a pair of ﬁngerprints from different ﬁngers in the MSU database that has a

relatively high matching score (9).

9.4.2 Authentication Test

In test 1, for each individual, we randomly selected 3 ﬁngerprint images which passed
the quality checking as the template minutiae patterns for the individual and inserted

them into the system database. The major reason why we use 3 ﬁngerprint templates

 

182

 

Figure 9.10: A mated pair in the MSU database that has a relatively low matching
score: (a) and (b) ﬁngerprint images from the same ﬁnger; (c) and (d) thinned ridge
maps; (e) and (f) extracted minutiae superimposed on the input images and the
corresponding minutiae pairs established using our matching algorithm.

 

183

 

Figure 9.11: A pair of ﬁngerprints from different ﬁngers in the MSU database that
have a relatively high matching score: (a) and (b) ﬁngerprint images from different
ﬁngers; (c) and (d) thinned ridge maps; (e) and (f) extracted minutiae superim-
posed on the input images and the corresponding minutiae pairs established using
our matching algorithm.

184

 

7O 1 r r 1 1 T T r T
60 -] -

incorrect

401 a

Precentage
8

 

201- -l

(:07de

 

 

 

4 L l l l l 1

O 1 O 20 30 4O 50 60 7O 80 90 1 00
Normalized matching score

(a)

 

 

70 I T I I

601- 1

50*- _

40 l' incorrect 4

Preoeniage
8

 

 

 

 

 

20 ' —
1 0 ” correct ‘
O A A A
O 1 O 20 3O 4O 50 60 7O 80 90 1 00

Normalized matching score
(b)

Figure 9.12: Distributions of correct and incorrect matching scores; vertical axis
represents distribution of matching scores in percentage; (a) MSU database; (b) N IST
9 (CD No. 1).

185

is that a signiﬁcant number of acquired ﬁngerprint images from the same ﬁnger in the
MSU database do not have a sufficient amount of common region of interest due to
the unrestricted acquisition process. Even if two images are of good quality, if they
share a small common region of interest, it is unlikely that the matching algorithm
can establish a sufﬁcient number of corresponding minutiae pairs to reach a correct
decision. Using more than one template is a simple solution although it may result in
a higher FAR. The remaining 1,050 (150 x 7) ﬁngerprint images were used as input
ﬁngerprints to test the performance of the system. An identity is established if at least
one of the 3 matching scores is above a certain threshold value. Otherwise, the input
ﬁngerprint is rejected as an impostor. In test 2, we used 798 out of the 900 ﬁngerprints
of card type 1 in NIST 9 database (CD. No. 1) as templates, which pass the quality
checking. The 900 ﬁngerprints of card type 2 were used as input ﬁngerprints. An
identity is established if the matching score is above a certain threshold value. The
false acceptance rates and false reject rates with different threshold values on the
matching score are shown in Table 9.2, which are obtained based on 157,500 (150
x 1,050) matches for test 1 and 718,200 (798 X 900) matches on test 2. Since the
matching scores are discretized with a large sampling interval, only an approximate
EER can be obtained by averaging the most similar FAR and FRR. The EER was
approximated to be 3.07% in test 1 and 2.69% in test 2. The ROCs of the two tests
are shown in Figure 9.13. In each ROC, authentic acceptance rate (the percentage of
a genuine individual being accepted) is plotted against the FAR. Each point on the
curve corresponds to a decision criterion. In the ideal case, if the genuine distribution

and the impostor distribution are disjoint, i.e. each genuine individual is accepted

 

186

 

 

 

 

 

 

Threshold False Acceptance False Reject False Acceptance False Reject
Value Rate Rate Rate Rate
(MSU) (MSU) (NIST 9) (NIST 9)
7 0.07% 7.1% 0.073% 12.4%
8 0.02% 9.4% 0.023% 14.6%
9 0.01% 12.5% 0.012% 16.9%
10 0 14.3% 0.003% 19.5%

 

 

 

 

 

 

 

Table 9.2: False acceptance and false reject rates on test sets with different threshold
values.

and each impostor is rejected correctly, then the ROC is a horizontal line segment
hovering at the authentic acceptance rate of 100%. On the other hand, if the genuine
distribution and the impostor distribution are exactly the same, then the ROC is a
45° line segment with one end point at the origin. In this case, decisions can only be
made by a random choice. In practice, a ROC is a curve between these two extremes.
The closer the ROC is to the upper boundary, the better the system performance.
The numbers shown in Table 9.2 are the performance measures of our veriﬁcation
algorithm. They should not be treated as the ultimate performance numbers of the
system. In practice, a number of techniques can be employed to ensure a sufﬁcient
amount of common region of interest in ﬁngerprint images and good image quality
and to restrict the distortion of input images, which can substantially decrease both

the FAR and FRR.

In order for an automatic identity authentication system to be acceptable in prac-
tice, the reSponse time of the system needs to be within a few seconds. Table 9.3 shows

that our implemented system does meet the practical response time requirement.

 

187

 

 

 

 

 

100 . . ......, . . ...... A - .r-..-, . . .4-.T., ﬁff...”
90A _
80- —

E 70~ —

Q)

5:5 60L- _

g 50- -

g 40~ _
ao— _
20- -
10- -
o_____1..._ 1__4__QL#1L_ _.a__ L___L_L_J_A_JIAL 4 A A A -AAAl A A A A AAAAl A A llllll
1 o‘° 1 0" 1 0“ 1 0° 1 0‘ 1 02

False Acceptance Rate (%)

(a)

 

 

 

 

 

 

100 . ﬁ......, . .-.”... . ﬁ.--.r¢ .ﬁ ......, a
ace _
80+- _

E 70» _

2

g 60- _

En 50L .1

g 40[ 1
30— A
20»- A
10~ A
o—A‘L___j__l_d_(wwi__‘1_‘,ﬂ__l_hl441i 4 A A A AAAAl A A A A ..AAl ...
10" 10‘2 10‘1 10° 10‘ 10’

False Acceptance Rate (%)
(b)
Figure 9.13: Receiver Operating Curves; (a) MSU database; (b) NIST 9 (CD No. 1).

 

188

 

Minutiae Extraction Minutiae Matching Total
(seconds) (seconds) (seconds)
1.1 _ 0.3 1.4

 

 

 

 

 

 

Table 9.3: Average CPU time for minutiae extraction and matching on a Sun ULTRA
1 workstation.

9.4.3 Identiﬁcation Test

We randomly assigned each of the remaining 86 individuals in the MSU ﬁngerprint

database to an individual in the face database (see Figure 9.14 for some examples).

 

Since the DFFS between two different individuals is statistically independent of the
ﬁngerprint matching scores between the two individuals, such a random assignment
of a face to a ﬁngerprint is admissible. One ﬁngerprint for each individual is randomly
selected as the template for the individual. To simulate the practical identiﬁcation
scenario, each of the remaining 590 faces was paired with a ﬁngerprint to produce a
test pair. In the test, with a pre-speciﬁed conﬁdence value (FAR), for each of the 590
ﬁngerprint and face pairs, the top 5 matches are retrieved using face recognition. Then
ﬁngerprint veriﬁcation is applied to each of the top 5 matches and a ﬁnal decision is

made by decision fusion.

We randomly selected 640 ﬁngerprints of 64 individuals as the training set and the
remaining as the test set. The mean and variance of the impostor distribution (Fig-

ure 9.15 (a)) were estimated to be 0.70 and 0.64 from the 403,200 (640 x 630) impostor

189

 

(h)

Figure 9.14: Face and ﬁngerprint pairs; the face images (92 x 112) are from the
Olivetti Research Lab.; the ﬁngerprint images (640 x 480) are captured with a scanner
manufactured by Digital Biometrics.

 

 

 

 

 

 

 

 

 

0.0- 0.0» 1
03 m 1
0.0 1
0.1-
0.7
0.0
0.0
05 l
0.5
0.4
0.4
0.5
02 °‘3
02
1
° mm.
o 0.1
"'" 10 20 30 40 so so 70 00 00 no " 0.1 02 0:: 0.4 0.5 0.0 0.1 0.0 0.0
Wig-con mmsm
(a) (b)

Figure 9.15: Impostor distributions; (a) impostor distribution for ﬁngerprint veriﬁca-
tion; (b) the impostor distribution for face recognition at rank no. 1, where the stars
(*) represent empirical data and the solid curve represents the ﬁtting result.

190

 

 

 

 

 

 

False Reject Rate (FRR)
FAR . . .
Face Fingerprint Integration
1% 15.8% 3.9% 1.8%
0.1% 42.2% 6.9% 4.4%
0.01% 61.2% 10.6% 6.6%
0.001% 64.1% 14.9% 9.8%

 

 

 

 

 

 

Table 9.4: False reject rates (FRR) on the test set with different values of FAR.

 

100

 
 
 

Fusion

 

  

Fingerprint

 

 

40- -

.NManAa»an0Rm000
8

20— A

10" -]

 

 

A A A l A A A A A l A A A A A4 A1 A
10“ 10° 10
False Acceptance Rate (%)

L

 

1 0"

Figure 9.16: Receiver Operating Curves; the vertical axis is (1-FRR).

matching scores of “all against all” veriﬁcation test by ﬁtting the probability model
described in Section 4.1. A total of 542 face images were used as training sam-
ples. Since variations in position, orientation, scale, and illumination exist in the face
database, the 542 training samples were selected such that the training set contained
several representative views. Eigenfaces were estimated from the 542 training sam-
ples and the ﬁrst 64 eigenfaces were used. The top 5 impostor distributions were

approximated. Figure 9.15 (b) shows the impostor distribution at rank no. 1.

The pre-speciﬁed FAR for a biometric system is usually very small (< 0.0001). In

order to demonstrate that the biometric system does meet such a speciﬁcation, a large

191

 

Face Recognition Fingerprint Veriﬁcation Total
(seconds) (seconds) (seconds)
0.9 2.1 3.0

 

 

 

 

 

 

Table 9.5: Average CPU time for one test on a Sun UltraSPARC 1 workstation.

set of representative samples is needed. Unfortunately, obtaining such a large number
of test samples is both expensive and time consuming. In our test, we re-use faces by
different assignment practices. In order to diminish the possible gain in performance
due to such a re—use schema, we multiplied the estimated impostor distribution for
face recognition by a constant of 1.25, which is sufﬁciently conservative. On the
other hand, ﬁngerprint veriﬁcation operates in the one-to-one veriﬁcation mode, so
different assignments may be deemed as different impostor forgeries. Therefore, the
test results using such a random assignment schema are able to reasonably estimate
the underlying performance numbers. In our test, 1000 different assignments were
tried. A total of 590,000 (590 x 1000) face and ﬁngerprint test pairs were generated
and tested. The FRRs of our system with respect to different pre—speciﬁed FARs, as
well as the FRRs using only ﬁngerprints or faces are listed in Table 9.4. Note that the
FRRs in integration column include the error rate (1.8%) of genuine individuals not
present in the top 5 matches. The receiver operating curves are plotted in Figure 9.16,
in which the authentic acceptance rate (the percentage of genuine individuals being
accepted, i.e., 1 — F RR) is plotted against FAR. We can conclude from these test
results that integration of ﬁngerprints and faces does result in a signiﬁcantly better
recognition performance. Table 9.5 shows that our implemented system does meet

the response time requirement.

.J-i‘ V'tn

 

‘F’n a...

192
9.5 Classiﬁcation Performance

We have tested our ﬁngerprint classiﬁcation algorithms on (i) NIST 4 ﬁngerprint
database, (ii) NIST 9 ﬁngerprint database, and (iii) a set of live-scan ﬁngerprint

images from IBM.

9.5.1 Classiﬁcation Scheme I

We ﬁrst present the performance of our classiﬁcation algorithm on the NIST 4
database. The ﬁve-class error rate in classifying these 4,000 ﬁngerprints is 12.5%.
The confusion matrix is given in Table 9.6; numbers shown in bold font are correct
classiﬁcations. Since a number of ﬁngerprints in NIST 4 database are labeled as be-
longing to two different classes, each row of the confusion matrix in Table 9.6 does not
sum up to 800. For the ﬁve-class problem, most of the classiﬁcation errors are due to
misclassifying a tented arch as an arch. By combining these two arch categories into
a single class, the error rate drops to 7.7%. Besides the tented arch-arch errors, the
other errors mainly come from misclassiﬁcations between arch/ tented arch and loops
and due to poor image quality. Four examples of misclassiﬁed ﬁngerprints are shown
in Figure 9.17. A lower error rate can be achieved by adding the reject option, which
is based on the quality index of the input image. The error rates corresponding to
different reject rates are listed in Table 9.8.

When testing on the NIST 9 database, if a ﬁngerprint is not an arch or tented
arch or loop then classify it as a whorl, since our classiﬁcation scheme only classiﬁes

ﬁngerprints into ﬁve classes. The ﬁve-class error rate in classifying the 5,400 ﬁnger-

 

193

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

True Class Assigned Class
Arch ] Tented Arch LLeft Loop ] Right Loop [Whorl

Arch 885 13 10 11 0
Tented Arch 179 384 54 14 5
Left Loop 31 27 755 3 20
Right Loop 30 47 3 717 16
Whorl 6 1 15 15 759

Table 9.6: Five—class classiﬁcation results on NIST 4 database.

 

 

 

 

 

 

 

 

 

 

 

 

Assigned Class
Tm Class Arch 1 Left Loop 1 Right Loop 1 Whorl
Arch 1461 64 25 5
Left Loop 58 755 3 20
Right Loop 77 3 717 16
Whorl 7 15 15 759

 

 

 

Table 9.7: Four-class classiﬁcation results on NIST 4 database.

 

 

 

 

 

 

 

 

Reject rate 0% 5% 10% 20%
5-class Error 12.5% 11.6% 10.1% 7.5%
4-class Error 7.7% 6.6% 5.1% 2.4%

 

 

 

Table 9.8: Error-reject tradeoff.

194

   

(C) ((0

Figure 9.17: Misclassiﬁed ﬁngerprints in N IST 4 ﬁngerprint database; (a) a left loop
is misclassiﬁed as an arch; (b) a tented arch is misclassiﬁed as an arch; (c) a left loop
is misclassiﬁed as a whorl; (d) a whorl is misclassiﬁed as a right loop.

195

 

 

 

 

 

 

 

 

 

True Class Assigned Class
Arch Tented Arch Left Loop Right Loop Whorl
Arch 357 10 6 3 3
Tented Arch 38 121 8 5 2
Left Loop 32 32 1506 15 65
Right Loop 21 82 23 1481 72
Whorl 5 8 93 58 1293

 

 

 

 

 

 

 

Table 9.9: Five-class classiﬁcation results on NIST 9 database (5,400 images).

 

 

 

 

 

 

 

 

True Class Assigned Class
Arch Left Loop Right Loop Whorl
Arch 526 14 8 5
Left Loop 64 1506 15 65
Right Loop 103 23 1481 72
Whorl 13 93 58 1293

 

 

 

 

 

 

 

 

Table 9.10: Four-class classiﬁcation results on NIST 9 database.

prints in NIST 9 database is 10.9%. The confusion matrix is shown in Table 9.9.
The classiﬁcation errors are due to misclassiﬁcations between arch/tented arch and
100ps and poor image quality. Examples of misclassiﬁed ﬁngerprints are shown in
Figure 9.18. A lower error rate can be achieved by adding the reject option, which
is based on the quality index of the input image. Table 9.11 shows the error rates
corresponding to different reject rates.

In classifying the ﬁngerprints in the IBM database, we assume that twins and
composites are whorls. The classiﬁcation error rate on the IBM database is 10.1%
with a 2.6% reject rate. The confusion matrix is listed in Table 9.12. Examples of

misclassiﬁed ﬁngerprints are shown in Figure 9.19. The error rates corresponding to

 

 

 

 

 

 

Reject rate 0 5% 10% 15% 20%
5-class Error rate 10.9% 9.6% 8.2% 7.4% 6.4%
4-class Error rate 10.0% 8.6% 7.7 % 6.9% 6.2%

 

 

 

 

 

 

Table 9.11: Error rates corresponding to different reject rates on NIST 9 database.

196

 

Figure 9.18: Misclassiﬁed ﬁngerprints in NIST 9 database; (a) a tented arch is mis-
classiﬁed as an arch; (b) a whorl is misclassiﬁed as an arch; (c) a whorl is misclassiﬁed
as a left loop; ((1) a whorl is misclassiﬁed as a right loop.

 

197

 

 

 

 

 

 

 

 

 

True Class Assigned Class
Arch Tented Arch Left Loop Right Loop Whorl
Arch 62 0 1 1
Tented Arch 25 65 2 3
Left Loop 10 4 266 3 6
Right Loop 9 7 345 4
Whorl 3 0 10 17 3

 

 

 

 

 

 

Table 9.12: Five-class classiﬁcation results on the IBM database.

 

 

 

 

 

 

 

 

 

Assi ed Class
True Class Arch [Left Loopgl]1 Right Loop ] Whorl
Arch 152 5 3 4
Left Loop 14 266 3 6
Right Loop 16 3 345 4
Whorl 3 7 10 17 3

 

 

 

 

 

 

 

 

Table 9.13: Four-class classiﬁcation results on the IBM database.

different reject rates are listed in Table 9.14.

9.5.2 Classiﬁcation Scheme II

It is difﬁculty to evaluate the performance of classiﬁcation scheme 11, because the
ground truth is not available. However, since the essence of ﬁngerprint classiﬁcation
is to classify ﬁngerprints from the same ﬁnger to the same category, we can use
individuality property to verify the validity of the classiﬁcation accuracy implicitly.
If two ﬁngerprints from the same ﬁnger are classiﬁed into the same category, then
we claim that the classiﬁcation is correct, otherwise incorrect. Let N be the number

of mated pairs in a database (a total of 2N ﬁngerprints), and Nc be the number of

 

 

 

 

 

Reject rate 2.6% 5% 10% 15% 20%
5-class Error rate 10.1% 9.3% 7.5% 6.9% 5.8%
4-class Error rate 7.7% 7.0% 5.2% 4.9% 4.1%

 

 

 

 

 

 

 

Table 9.14: Error rates corresponding to different reject rates on the IBM database.

198

 

Figure 9.19: Misclassiﬁed ﬁngerprints in the IBM database; (a) a left loop is mis-
classiﬁed as an arch; (b) a right loop is misclassiﬁed as a tented arch; (c) a whorl is
misclassiﬁed as an arch; (d) a tented arch is misclassiﬁed as an arch.

199

ﬁngerprint pairs that are consistently classiﬁed. Then, the inconsistency rate, e,-, is

deﬁned as

100Nc
61‘ = . (9.2)

 

Let c be the misclassiﬁcation rate, and deﬁne c = 1 — e. For a given mated pair,
there are four outcomes: (2) both images are correctly classiﬁed, (ii) the ﬁrst image is
correctly classiﬁed and the second image is incorrectly classiﬁed, (iii) the ﬁrst image
is incorrectly classiﬁed and the second image is correctly classiﬁed, and (iv) both im-
ages are incorrectly classiﬁed. Outcome (2) corresponds to a consistent classiﬁcation.
Outcomes (ii) and (iii) correspond to an inconsistent classiﬁcation. For outcome (iv),
the mated images may be misclassiﬁed into (a) the same category and (b) different
categories. Outcome (a) corresponds to a consistent classiﬁcation and outcome (b)

corresponds to an inconsistent classiﬁcation. Therefore,

e,- = ce + ce + be2, (9.3)
= e+e+ (1 —b)e2, (9.4)
> 6, (9.5)

where b < 1 denote the probability of outcome (b).

We have tested classiﬁcation scheme II on both NIST 4 database and NIST 9
database. The inconsistency rate in classifying all the 2,000 mated pairs is 7.0% with

a 1.4% reject rate. The confusion matrix is given in Table 9.15; numbers shown in

 

200

 

 

 

 

 

 

 

 

First Class Second Class
Class-1 ] Class-2 ] Class-3 Class-4
Class-1 774 28 15 3
Class-2 19 355 6 9
Class-3 30 7 360 8
Class-4 3 9 5 339

 

 

 

 

 

 

 

Table 9.15: Consistency test results on the NIST 4 database.

 

 

Reject rate 1.4% 5.0% 10.0% 15.0% 20.0%
Inconsistency rate 7.0% 4.3% 4.3% 3.1% 2.7%

 

 

 

 

 

 

 

 

 

Table 9.16: Inconsistency rates corresponding to different reject rates on the NIST 4
database.

bold font are the number of times when the mated pairs are classiﬁed in the same
category. A lower inconsistency rate can be achieved by incorporating the reject
option, which is based on the quality index of the input image. The inconsistency

rates corresponding to different reject rates are listed in Table 9.16.

The inconsistency rate in classifying all the 5,400 NIST 9 ﬁngerprints is 7.6% with
a reject rate of 4.2%. The confusion matrix is given in Table 9.17; numbers shown
in bold font are the number of consistent classiﬁcations. A lower inconsistency rate
can be achieved by adding the reject option, which is based on the quality index of

the input image. The error rates corresponding to different reject rates are listed in

 

 

 

 

 

 

 

 

Table 9.18.
. Second Class
FlrSt Class Class-1iClass-2 I Class-3] Class-4
Class-1 349 18 17 5
Class-2 21 714 14 22
Class-3 27 8 718 21
Class-4 2 21 30 599

 

 

 

 

 

 

 

Table 9.17: Consistency results on the NIST 9 database.

 

201

 

 

Reject rate 4.2% 5.0% 1.0% 15.0% 20.0%
Inconsistency rate 7.6% 7.3% 5.4% 4.8% 3.3%

 

 

 

 

 

 

 

 

 

Table 9.18: Inconsistency rates corresponding to different reject rates on the NIST 9
database.

9.6 Summary

In summary, the number of tests conducted on an automatic ﬁngerprint identiﬁ-
cation/veriﬁcation system is never enough. Performance measures are as much a
function of the algorithm as they are a function of the database used for testing. The
biometrics community is slow at establishing benchmarks and the ultimate perfor—
mance numbers of a ﬁngerprint identiﬁcation / veriﬁcation system are those which you
ﬁnd in a deployed system. Therefore, one can carry out only a limited amount of
testing in a laboratory environment to show the anticipated system performance. In
ﬁeld testing, in addition to the real performance of the system, the system designer
has to pay attention to the perceived performance of the system, especially in the

context of the authentication applications which are sensitive to false negatives.

 

Chapter 10

Summary and Future Research

In this chapter, we will summarize the work we have done, discuss the limitations of

our current approaches and some possible solutions.

10.1 Summary

The goal of our research is to design a ﬁngerprint-based biometric system which is
capable of achieving a fully automatic positive personal identiﬁcation with a high level
of conﬁdence. We have develOped a prototype veriﬁcation system and a prototype
identiﬁcation system. The veriﬁcation depends solely on ﬁngerprints to authenticate
the identity claimed by an individual. The identiﬁcation system which is designed for
a limited environment, uses multiple biometric characteristics (ﬁngerprint and face)
to make a personal identiﬁcation. In the design of these two prototype systems, we
have identiﬁed and investigated the following problems:

202

 

203

o Minutiae extraction

We have developed a new minutiae extraction algorithm which is faster and
more reliable than the earlier algorithms reported in the literature, e.g., [120].
The new orientation ﬁeld estimation algorithm results in a smoother orientation
ﬁeld which greatly improves the performance of ridge extraction. The adaptive
ridge ﬁnder is capable of tolerating, to a certain extent, low ridge contrast and
various sources of noise in ﬁngerprint images such as short breaks and small

amount of smudges.

Fingerprint enhancement

We have developed a new ﬁngerprint image enhancement algorithm. Unlike
other enhancement algorithms, we expend a large amount of effort on the es-
timation of orientation ﬁeld, which plays a critical role in ﬁngerprint enhance-
ment. We can obtain a relatively good estimate of orientation ﬁeld even if the
quality of input ﬁngerprint image is poor. The algorithm also identiﬁes the
unrecoverable corrupted regions in the ﬁngerprint and removes them. Experi-
mental results reveal that the pr0posed ﬁngerprint enhancement algorithm can
signiﬁcantly improve the quality of input images, resulting in better matching

performance.

Minutiae matching
An alignment-based elastic matching algorithm has been developed to imple-
ment minutiae matching. This algorithm is capable of ﬁnding the correspon-

dences between minutiae without resorting to an exhaustive search. It can

 

204

achieve a good performance in minutiae matching because of its capability to
adaptively compensate for the nonlinear deformations and inexact transforma-

tions between mated ﬁngerprints.

Decision fusion

We have developed an integration scheme which can be used to fuse multiple
biometrics that complement each other in terms of speed and accuracy. We have
tested our scheme by integrating ﬁngerprint veriﬁcation and face recognition.
Experimental results demonstrate that our scheme is able to improve both the
accuracy and speed of identiﬁcation. The multimodal biometric system over-

comes some of the limitations of face recognition and ﬁngerprint veriﬁcation.

Fingerprint classiﬁcation

We have designed two ﬁngerprint classiﬁcation algorithms. The ﬁrst algorithm
classiﬁes input ﬁngerprints into ﬁve categories according to the number of sin-
gular points detected, their relative positions, and presence of type-1 and type-2
recurring ridges. The second algorithm classiﬁes ﬁngerprints into four categories
according to the number of singular points detected and their relative positions.
Our algorithm invests a signiﬁcant amount of effort in feature extraction to
make the system robust to intraclass variations as well as poor quality of input
images. Experiment results demonstrate that our algorithm has better classi-

ﬁcation performance than previously reported in the literature on the NIST 9

and NIST 4 databases.

 

205

0 Performance evaluation
The performance of the entire veriﬁcation system and the identiﬁcation system
as well as the performance of various system components (e. g., minutiae extrac-
tion and the ﬁngerprint enhancement) were evaluated extensively on a number
of real ﬁngerprint databases. The experimental results reveal that both the ver-

iﬁcation system and the identiﬁcation system can achieve a good performance.

10.2 Future Research

Despite the fact that both the veriﬁcation system and the identiﬁcation system can
achieve a good performance in making a personal identiﬁcation, we believe that a
number of problems still need to be solved to make these systems more effective in
practice. The following is a list of limitations of our current approaches and the direc-

tions which are signiﬁcant for the performance improvement of our implementation.

0 In order to determine whether a pair of ﬁngerprints are from the same ﬁnger, two
conditions must be assessed: (2) the two ﬁngerprints must be of the same pattern
conﬁguration, e.g., whorl, arch, etc. and (ii) they must share a substantial
number of identical minute details. Currently, our minutiae matching algorithm
depends only on the assessment of the second condition to make a decision.
Obviously, this is not sufﬁcient. A ﬁngerprint classiﬁcation scheme assigns a
ﬁngerprint into one of the prespeciﬁed categories based on its global pattern
conﬁguration. If two ﬁngerprints are from the same ﬁnger, they must belong

to the same category. Although ﬁngerprint classiﬁcation is still a challenging

 

206

 

 

Figure 10.1: Minutiae with different degrees of importance; the minutiae labeled by
the circle is more important than the minutiae labeled by the square.

problem and it is very difficult to achieve a very high classiﬁcation rate, it is
nonetheless beneﬁcial to incorporate the category information into a minutiae

matching algorithm to improve its performance.

0 All the minutiae extracted by our algorithm are weighted equally in minutiae
matching. In fact, different minutiae have varying degrees of importance in
matching (see Figure 10.1). Therefore, it will be beneﬁcial to systematically
assign a weight to each minutiae to indicate its importance and to incorporate

this information in minutiae matching.

0 Currently, the minutiae extraction algorithm does not assume any model of the

 

207

input ﬁngerprints. In fact, in a veriﬁcation system, as soon as the individual
indicates his/her identity, the template of the individual is available. Such a
template provides a model of the input ﬁngerprint. The minutiae extraction

algorithm should use this model to facilitate the minutiae extraction.

Since the minutiae matching does not make any assumptions about the relative
translation and rotation between the input minutiae pattern and the template,
it needs to evaluate the edit distance corresponding to each pair of aligning
ridges to ﬁnd the best match. Computing the edit distance is computationally
expensive. The speed of the minutiae matching can be greatly accelerated if
the unreasonable alignments achieved by the ridge matching can be quickly

rejected.

A number of factors are detrimental to the correct localization of minutiae.
Among them, poor image quality is the most serious one. By integrating an en-
hancement mechanism into the minutiae extraction module, this problem can,
to a limited extent, be solved. However, currently, our ﬁngerprint enhancement
algorithm is computationally expensive, which is not suitable for incorpora-
tion into the minutiae extraction algorithm. A fast enhancement algorithm is

needed.

In order to show that a deployed biometric system is capable of achieving certain
benchmarks, a systematic and objective performance assessment of the system
is necessary, which, unfortunately, is far from established. The expected error

rate of a deployed biometric system is usually a very small number (<< 1%). A

 

208

maximum likelihood estimate of the error rate is usually not reliable. In order to
estimate such a small number reliably and accurately, large representative data
sets are needed and the corresponding conﬁdence intervals should be provided
to characterize the reliability of the estimate. Two major issues need to be
addressed: (2) how should the samples be selected from the population? and
(ii) how many samples are needed to estimate the error rate with the expected

conﬁdence?

 

Bibliography

 

[1] Access Control Applications using Optical Computing.

http://www.mytec.com/, 1997.

 

[2] Edge Lit Hologram for Live-scan Fingerprinting. http://eastview.org/ImEdge/,

1997.

[3] Scanner Speciﬁcations. ftp: / / ard.fbi.gov / pub/ IQS / spec/ , 1997.

[4] N. Ansari, M. H. Chen, and E. S. H. Hou. A genetic algorithm for point pattern
matching. In B. Souéek and the IRIS Group, editors, Dynamic, Genetic, and

Chaotic Programming. John Wiley & Sons, 1992.

[5] K. Asai, Y. Hoshino, Y. Kato, and K. Kiji. Automatic reading and matching
for single-ﬁngerprint identiﬁcation._ In Proc. 65th Int. Ass. for Identiﬁcation

Conf., pages 1—7, Ottawa, Canada, 1991.

[6] J. Atick, P. Grifﬁn, and A. Redlich. Statistical approach to shape from shading:
Reconstruction of 3D face surfaces from single 2D images. Neural Computation,
1998. to appear.

209

210

 

[7], R. Bahuguna. Fingerprint veriﬁcation using hologram matched ﬁlterings. In

Proc. Biometric Consortium Eighth Meeting, San Jose, California, June 1996.

[8] H. Baird. Model Based Image Matching Using Location. MIT Press, Cambridge,

MA, 1984.

[9] K. Balck and K. Rao. A hybrid optical computer processing technique for

 

ﬁngerprint identiﬁcation. IEEE Trans. Computer, 24:358—369, 1975.

 

[10] P. Baldi and Y. Chauvin. Neural networks for ﬁngerprint recognition. Neural J

Computation, 5(3):402—418, 1993.

[11] D. H. Ballard. Generalized hough transform to detect arbitrary patterns. IEEE

Trans. Pattern Anal. and Machine Intell., 3(2):111—122, 1981.

[12] C. Banner and R. Stock. The FBI’s approach to automatic ﬁngerprint identiﬁca-
tion (part I). FBI Law Enforcement Bulletin, U.S.A. Government Publication,

44(1),1975.

[13] C. Banner and R. Stock. The FBI’s approach to automatic ﬁngerprint identiﬁca-
tion (part II). FBI Law Enforcement Bulletin, U. S.A. Government Publication,

44(2),1975.

[14] L. Berdan and R. Chiralo. Adaptive digital enhancement of latent ﬁngerprints.
In Proc. Int. Carnahan Conf. on Electronic Crime Countermeasures, pages

131—135, University of Kentucky, Lexington, Kentucky, 1978.

211

[15] Z. Bian and Q. Xiao. An approach to ﬁngerprint identiﬁcation by using the
attributes of feature lines of ﬁngerprint. In Proc. 8th ICPR, pages 27—31, Paris,

France,1986.

[16] E. S. Bigun, J. Bigun, B. Duo, and S. Fischer. Expert conciliation for multi
modal person authentication systems by Bayesian statistics. In Proc. Ist Int.
Conf. on Audio Video-Based Personal Authentication, pages 327—334, Crans—

Montana, Switzerland, March 1997.

[17] Biometrics Consortium Homepage. INS Passenger Accelerated Service System

(INSPA SS). http: //www.accentdesign.com/bc/publications.html, 1998.

[18] E. Botha and L. Coetzee. Fingerprint recognition with a neural-net classiﬁer. In
Proc. First South African Workshop on Pattern Recognition, volume 1, pages

33—40, 1990.

[19] F. Bouchier, J. S. Ahrens, and G. Wells. Laboratory Evaluation of the IriScan
Prototype Biometric Identi-
ﬁer. http: / / infoserve.library.sandia. gov / sand_doc / 1996 / 961033.pdf, SAND96—

1033, 1996.

[20] R. Brunelli and D. Falavigna. Personal identiﬁcation using multiple cues. IEEE

Trans. Pattern Analysis and Machine Intelligence, 17(10):955—966, 1995.

[21] R. Brunelli and T. Poggio. Face recognition: Features versus templates. IEEE

Trans. Pattern Analysis and Machine Intelligence, 15(10):1042-1052, 1993.

 

212

[22] G. Candela and R. Chellappa. Comparative Performance of Classiﬁcation Meth-

ods for Fingerprints. Tech. Report: NIST TR 5163, 1993.

[23] G. Candela, P. Grother, C. Watson, R. Wikinson, and C. Wilson. Evaluation of
Pattern Classiﬁers for Fingerprint and OCR Applications. Tech. Report: NIST

TR 3162, 1993.

[24] G. T. Candela, P. J. Grother, C. I. Watson, R. A. Wilkinson, and C. L. Wilson.
PCASYS: A Pattern-Level Classiﬁcation Automation System for Fingerprints.

NIST Tech. Report NISTIR 5647, August 1995.

 

"i.e.-A.-.

[25] S. H. Chang, F. H. Cheng, W. H. Hsu, and G. Z. Wu. Fast algorithm for
point pattern matching: Invariant to translations, rotations, and scale changes.

Pattern Recognition, 30(2):321—339, 1997.

[26] T. Chang. Texture analysis of digitized ﬁngerprints for singularity detection.

In Proc. 5th ICPR, pages 478—480, 1980.

[27] C. Chapel. Fingerprinting - A Manual of Identiﬁcation. Coward McCann, New

York, 1971.

[28] B. Chatterjee, S. Kapoor, B. Mehtre, and N. Murthy. Segmentation of ﬁn-
gerprint images using the directional image. Pattern Recognition, 20:429—435,

1987.

[29] B. Chatterjee, A. Majumdar, and M. Verma. Edge detection in ﬁngerprints.

Pattern Recognition, 20:513—523, 1987.

213

[30] B. Chatterjee and B. Mehtre. Automatic ﬁngerprint identiﬁcation. Journal of

the Institution of Electronics and Telecom., 37(5/6):493, 1991.

[31] R. Chellappa, C. Wilson, and A. Sirohey. Human and machine recognition of

faces: A survey. Proceedings IEEE, 83(5):705—740, 1995.

[32] M. Chong, R. Gay, J. Liu, and H. Tan. Automatic representation of ﬁngerprints
for data compression by B-spline functions. Pattern Recognition, 25(10):1199—

1210, 1992.

[33] M. Chong, T. Ngee, L. Jun, and R. Gay. Geometric framework for ﬁngerprint

image classiﬁcation. Pattern Recognition, 30(9):1475—1488, 1997.

[34] J. Clark and A. Yuille. Data Fusion for Sensory Information Processing Sys-

tems. Kluwer Academic Publishers, Boston, 1990.

[35] R. Clarke. Human identiﬁcation in information systems: Management chal-
lenges and public policy issues. Information Technology 63 People, 7(4):6—37,

1994.

[36] Louis Coetzee and Elizabeth Botha. Fingerprint recognition in low quality

images. Pattern Recognition, 26(10):1441—1460, 1993.

[37] T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms.

McGraw—Hill, New York, 1990.

[38] J. Cowger. Friction Ridge Skin: Comparison and Identiﬁcation of Fingerprints.

Elsevier, New York, 1983.

 

214

[39] Thomson CSF. Thomson CSF Homepage. http://www.tcs.thomson-

csf.com / Us / standard / ﬁnger.htm, 1998.

[40] H. Cummins and C. Mildo. Finger Prints, Palms and Soles. Dover Publication

[41]

[42]

[43]

[44]

[45]

[46]

Inc., New York, 1961.

P. E. Danielsson and Q. Z. Ye. Rotation-invariant operators applied to enhance-

ment of ﬁngerprints. In Proc. 9th ICPR, pages 329—333, Rome, 1988.

J. G. Daugman. Uncertainty relation for resolution in space, spatial-frequency,
and orientation optimized by two-dimensional visual cortical ﬁlters. J. Opt.

Soc. Am., 221160—1169, 1985.

J. G. Daugman. High conﬁdence visual recognition of persons by a test of
statistical independence. IEEE Trans. Pattern Anal. and Machine Intell.,

15(11):1148—1161, 1993.

J. G. Daugman and G. 0. Williams. A proposed standard for biometric de-
cidability. In Proc. CardTech/SecureTech Conference, pages 223—234, Atlanta,

GA, 1996.

S. G. Davies. Touching big brother: How biometric technology will fuse ﬂesh

and machine. Information Technology 5 People, 7(4):60-69, 1994.

U. Dieckmann, P. Plankensteiner, and T. Wagner. Sesam: A biometric per-

son identiﬁcation system using sensor fusion. Pattern Recognition Letters,

18(9):827—833, 1997.

 

 

215

[47] M. Eleccion. Automatic ﬁngerprint identiﬁcation. IEEE Spectrum, 10(9):36—45,

[48]

[49]

[50]

[51]

[52]

1973.

W. Engeler, P. Frank, and M. Leung. Fingerprint image processing using neural
network. In Proc. IEEE Region 10 Conf. on Computer and Comm. Systems,

Hong Kong, 1990.

P. Engler, Y. Shi, and F. You. Fingerprint pattern recognition for medical
uses— a frequency domain approach. In Proc. Annual Northeast Bioengineering

Conference, volume 19, page 176, 1993.

J. Ferrante, J. Maier, J. Nelson, and J. Woodard. Automated entry control:
Radc technology develOpment results and future plans. In Proc. Int. Carna-
han Conf. on Electronic Crime Countermeasures, pages 77—82, University of

Kentucky, Lexington, Kentucky, 1981.

K. Fielding, J. Homer, and C. Makekau. Optical ﬁngerprint identiﬁcation by

binary joint transform correlation. Optical Engineering, 30:1958, 1991.

L. Frye, F. Gamble, and D. Grieser. Real-time ﬁngerprint veriﬁcation system.

Applied Optics, 31(5):652, 1992.

[53] Y. Fumio, I. Seigo, and E. Shin. Real-time ﬁngerprint sensor using a hologram.

[54]

Applied Optics, 31(11):1794, 1992.

F. Galton. Finger Prints. Da Capo Press, New York, 1961.

 

EL.

216

[55] S. Gold and A. Rangarajan. A graduated assignment algorithm for graph match-

ing. IEEE Trans. Pattern Anal. and Machine Intell., 18(4):377—388, 1996.

[56] K. Goto, T. Minami, and O. N akamura. Fingerprint classiﬁcation by directional

distribution patterns. System Computer Controls, 13:81—89, 1982.

[57] Q. Guisheng, C. Minde, Q. Shi, and N. Xue. A new automated ﬁngerprint

identiﬁcation system. Computer Science Technology, 4(4):289—294, 1989.

[58] E. J. Gumbel. Statistics of Extremes. Columbia University Press, New York,

1958.

[59] L. Gyergyek, S. Kovacic, and F. Pernus. Minutiae based ﬁngerprint recognition.

In Proc. 5th ICPR, pages 1380—1382, 1980.

[60] M. Hartman. Compact ﬁngerprint scanner techniques. In Proc. Biometric

Consortium Eighth Meeting, San Jose, California, June 1996.

[61] M. Hase and A. Shimisu. Entry method of ﬁngerprint image using a prism.

Trans. Inst. Electron. Commum. Eng. Japan, J67—Dz627—628, 1984.

[62] I. Hideki, K. Ryuj, and H. Yu. A fast automatic ﬁngerprint identiﬁcation
method based on a weighted-mean of binary image. IEICE Transactions on

Fundamentals of Electronic, 76:1469, 1993.

[63] L. Hong and A. Jain. Integrating faces and ﬁngerprints for personal identiﬁca-
tion. In Proc. 3rd Asian Conference on Computer Vision, pages 16—23, Hong

Kong, China, 1998.

 

 

217

[64] L. Hong, Y. Wan, and A. Jain. Fingerprint image enhancement: Algorithms

and performance evaluation. to appear in IEEE Trans. on PAM], 1998.

[65] Z. Hong. Algebraic feature extraction of image for recognition. Pattern Recog-

nition, 24(2):211—219, 1991.

 

[66] A. Hrechak and J. McHugh. Automated ﬁngerprint recognition using structural 1

matching. Pattern Recognition, 23(8):893—904, 1990. ,L

 

[67] D. C. Huang. Enhancement and feature puriﬁcation of ﬁngerprint images. Pat- Ej

tern Recognition, 26(11):1661—1671, 1993.

[68] D. P. Huttenlocher and S. Ullman. Object recognition using alignment. In Proc.

First Intern. Conf. Comput. Vision, pages 102—111, London, 1987.

 

[69] D. Isenor and S. Zaky. Fingerprint identiﬁcation using graph matching. Pattern

Recognition, 19: 1 13—122, 1986.

[70] Jr. J. Campbell. Speaker recognition: A tutorial. Proceedings of IEEE,

85(9):1437—1462, 1997.

[71] A. Jain, L. Hong, and R. Bolle. On—line ﬁngerprint veriﬁcation. IEEE Trans.

Pattern Anal. and Machine Intell., 19(4):302~314, 1997.

[72] A. K. Jain and F. Farrokhnia. Unsupervised texture segmentation using Gabor

ﬁlters. Pattern Recognition, 24(12):1167—1186, 1991.

218
[73] G. Johnson, D. McMahon, S. Teeter, and G. Whitney. A hybrid optical com-

puter processing technique for ﬁngerprint identiﬁcation. IEEE Trans. Comput-

ers, 24:358—369, 1975.

[74] P. Jones, B. Santer, and T. Wigley. Correlation methods in ﬁngerprint detection

studies. Climate Dynamics, 8(6):265, 1993.

[75] J. Campbell Jr., L. Alyea, and J. Dunn. Biometric security: Government appli-

cations and operations. http:/www.m'tro.bloomington.in.us:8080/~BC/, 1996.

[76] T. Kamei and M. Mizoguchi. Image ﬁlter design for ﬁngerprint enhancement.

In Proc. ISCV’ 95, pages 109—114, Coral Gables, FL, 1995.

[77] F. Karen. Encryption, smart cards, and ﬁngerprint readers. IEEE Spectrum,

26(8):22, 1989.

[78] K. Karu and A. K. Jain. Fingerprint classiﬁcation. Pattern Recognition,

29(3) :389—404, 1996.

[79] M. Kass and A. Witkin. Analyzing oriented patterns. Comput. Vision Graphics

Image Process, 37(4):362—385, 1987.

[80] M. Kawagoe and A. Tojo. Fingerprint pattern classiﬁcation. Pattern Recogni-

tion, 17(3):295—303, 1984.

[81] E. Kaymaz and S. Mitra. A novel approach to Fourier spectral enhancement of
laser-luminescent ﬁngerprint images. Journal of Forensic Sciences, 38(3):530,

1993.

 

219
[82] J. Kittler, Y. Li, J. Matas, and M. U. Sanchez. Combining evidence in multi-

modal personal identity recognition systems. In Proc. Ist Int. Conf. on Audio

Video-Based Personal Authentication, pages 327—334, Crans—Montana, Switzer-

land, March 1997.

[83] J. Klett. Thermal imaging ﬁngerprint technology. In Proc. Biometric Consor-

tium Ninth Meeting, Crystal City, Virginia, April 1997.

[84] W. Lau, S. Leung, W. Leung, and A. Luk. Fingerprint recognition using neural

network. In Proc. IEEE Workshop Neural Network for Signal Processing, 1991.

[85] H. C. Lee and R. E. Gaensslen. Advances in Fingerprint Technology. Elsevier,

New York, 1991.

[86] Lexington Technology, Inc. Lexington Technology, Inc. Homepage.

http: / / www.1exingtontech.com / index.html, 1998.

[87] J. Li, Y. Shan, and P. Shi. Fingerprint preclassiﬁcation using key-points. In
Proc. IEEE International Symposium on Speech, Image Proc. and Neural Net-

work, Hong Kong, 1994.

[88] F. R. Livingstone, L. King, J. Beraldin, and M. Rjoux. Development of a real-
time laser scanning system for object recognition, inspection, and robot control.
In Proc. SPIE on Telemanipulator Technology and Space Telerobotics, volume

2057, pages 454—461, Boston, Massachusetts, September 1993.

 

[90]

220

[89] S. Maes and H. Beigi. Open sesame! speech, password or key to secure your
door? In Proc. 3rd Asian Conference on Computer Vision, pages 531—541,

Hong Kong, China, 1998.

[90] D. Maio and D. Maltoni. A structural approach to ﬁngerprint classiﬁcation. In

Proc. 13th ICPR, pages 578—585, Vienna, 1996.

[91] D. Maio and D. Maltoni. Direct gray-scale minutiae detection in ﬁngerprints.

IEEE Trans. Pattern Anal. and Machine Intell., 19(1):27—40, 1997.

[92] D. Marr. Vision. W. H. Freeman, San Francisco, 1982.

[93] K. McCalley, D. Setlak, S. Wilson, and J. Schmitt. A direct ﬁngerprint reader.
In Proc. CardTech/SecurTech, Volume 1: Technology, pages 271-279, Atlanta,

Georgia, May 1996.

[94] B. Mehtre. Fingerprint image analysis for automatic identiﬁcation. Machine

Vision and Applications, 6(2-3):124—139, 1993.

[95] B. M. Mehtre, N. N. Murthy, and Kapoor. Segmentation of ﬁngerprint images

using the directional image. Pattern Recognition, 20(4):429—435, 1987.

[96] K. Millard, D. Monro, and B. Sherlock. Algorithm for enhancing ﬁngerprint

images. Electronics Letters, 28(18):1720, 1992.

[97] B. Miller. Vital signs of identity. IEEE Spectrum, 31(2):22—30, 1994.

 

 

[98]

[99]

[100]

[101}

{102]

[1031

[104]

{106]

[107]

221

[98] D. Mintie. Welfare id at the point of transaction using ﬁngerprint and 2D bar
codes. In Proc. CardTech/SecurTech, Volume II: Applications, pages 469—476,

Atlanta, Georgia, May 1996.

[99] Miros. Miros Homepage. http://www.miros.com, 1998.

[100] B. Moayer and K. Fu. A syntactic approach to ﬁngerprint pattern recognition.

Pattern Recognition, 6, 1974.

[101] B. Moayer and K. Fu. An application of stochastic languages to ﬁngerprint

pattern recognition. Pattern Recognition, 8:173—179, 1976.

[102] B. Moayer and K. Fu. A tree system approach for ﬁngerprint pattern recogni-

tion. IEEE Trans. Pattern Anal. and Machine Intell., 8(3):376—388, 1986.

[103] A. Moenssens. Fingerprint Techniques. Chilton Book Company, London, 1971.

[104] D. Monro and B. Sherlock. A model for interpreting ﬁngerprint topology. Pat-

tern Recognition, 26(7):1047—1055, 1993.

[105] V. Nalwa. Automatic on-line signature veriﬁcation. Proceedings of IEEE,

85(2):213—239, 1997.

[106] E. Newham. The Biometric Report. SJB Services, New York, 1995.

[107] J. Nickerson and L. O’Gorman. Matched ﬁlter design for ﬁngerprint image en-
hancement. In Proc. IEEE Int. Conf. on Acoustic, Speech and Signal Processing,

pages 916—919, New York, 1988.

 

[110] r

[111] 1

[113]

[1141

[108]

[109]

[110]

[111]

[112]

[113]

[114]

[115]

222

Federal Bureau of Investigation. The Science of Fingerprints: Classiﬁcation

and Uses. US. Government Printing Ofﬁce, Washington, D. C., 1984.

National Institute of Standards and Technology. Guideline for The Use of Ad-
vanced Authentication Technology Alternatives. Federal Information Processing

Standards Publication 190, 1994.

L. O’Gorman and J. V. Nickerson. An approach to ﬁngerprint ﬁlter design.

Pattern Recognition, 22(1):29—38, 1989.

H. Okada and B. Sheu. An analog VLSI edge detector chip and digital mul-
tiprocessor chip for neural-based vision processing. In Proc. IEEE Int. Conf.

System Engineering, 1992.

J. Osterberg, T. Parthasarathy, T. Raghavan, and S. Sclove. Development of a
mathematical formula for the calculation of ﬁngerprint probabilities based on
individual characteristic. Journal American Statistic Association, 72:772—778,

1977.

A. Papoulis. Probability, Random Variables, and Stochastic Processes. McGraw-

Hill, New York, 1965.

P. J. Phillips, P. J. Rauss, and S. Z. Der. FERET (Face Recognition Technol-
ogy) Recognition Algorithm Development and Test Results. US. Government

Publication, ALR—TR-995, Army Research Laboratory, Adelphi, MD, 1996.

H. Raafat and Q. Xiao. Fingerprint image postprocessing: A combined statis-

tical and structural approach. Pattern Recognition, 24(10):985—992, 1991.

 

[116] J

[118] .

[119]

[123]

[124]

223
[116] J. Rafferty and J. Wegstein. The LX39 latent Fingerprint Matcher. U.S.A.

Government Publication. National Bureau of Standards, Institute for Computer

Sciences and Technology, 1978.

[117] A. Ranade and A. Rosenfeld. Point pattern matching by relaxation. Pattern

Recognition, 12(2):269—275, 1983.

[118] A. Rao. A Taxonomy for Texture Description and Identiﬁcation. Springer-

Verlag, New York, 1990.

[119] K. Rao and K. Balck. Type classiﬁcation of ﬁngerprints: A syntactic approach.

IEEE Trans. Pattern Anal. and Machine Intell., 2(3):223—231, 1980.

[120] N. Ratha, S. Chen, and A. K. Jain. Adaptive ﬂow orientation based feature

extraction in ﬁngerprint images. Pattern Recognition, 28(11):1657—1672, 1995.

[121] N. Ratha, K. Karu, S. Chen, and A. K. Jain. A real-time matching system for

large ﬁngerprint database. IEEE Trans. on PAMI, 18(8):799—813, 1996.

[122] J. Riganati. An overview of algorithms employed in automated ﬁngerprint pro-
cessing. In Proc. Int. Carnahan Conf. on Electronic Crime Countermeasures,

pages 125—131, University of Kentucky, Lexington, Kentucky, 1977 .

[123] A. Roddy and J. Stosz. Fingerprint features - statistical analysis and system

performance estimates. Proceedings of IEEE, 85(9):1390—1421, 1997.

[124] K. Saviers. Friction skin characteristics: A study and comparison of proposed

standards. In Garden Grove. California Police Department, 1987.

 

!‘~J

I")

224

[125] J. Schneider. Improved image quality of live scan ﬁngerprint scanners using
acoustic backscatter measurements. In Proc. Biometric Consortium Eighth

Meeting, San Jose, California, June 1996.

[126] J. Schneider and D. Wobschall. Live scan ﬁngerprint imagery using high reso-
lution c-scan ultrasonography. In Proc. 25th Int. Carnahan Conf. on Security

Technology, pages 88—95, 1991.

[127] S. Sclaroff and A. P. Pentland. Modal matching for correspondence and recog-

nition. IEEE Trans. Pattern Anal. and Machine Intell., 17(6):545-561, 1995.

[128] G. Scott and C. Longuet-Higgins. An algorithm for associating the features of

two images. Proc. Royal Society of London, 244:21—26, 1991.

[129] I. Seigo, E. Shin, and S. Takashi. Holographic ﬁngerprint sensor. Fujitsu Sci-

entiﬁc 59’ Technical Journal, 25(4):287, 1989.

[130] Harris Semiconductor. Harris Semiconductor Homepage.

http: //www.semi.harris.com/fngrloc/index.htm, 1998.

[131] D. Sherlock, D. M. Monro, and K. Millard. Fingerprint enhancement by direc-
tional Fourier ﬁltering. IEE Proc. Vis. Image Signal Processing, 141(2):87—94,

1994.

[132] A. Sherstinsky and R. W. Picard. Restoration and enhancement of ﬁngerprint
images using m-lattice: A novel non-linear dynamical system. In Proc. 12th

[CPR-B, pages 195—200, 1994.

 

{13:

[13

[13

225
[133] A. Solberg, T. Taxt, and A. Jain. A Markov random ﬁeld model for classiﬁcation

of multisource satellite imagery. IEEE Trans. Geoscience and Remote Sensing,

34(1):100—113, 1996.

[134] M. Sparrow and P. Sparrow. A Topological Approach to The Matching of Sin-
gle Fingerprints: Development of Algorithms for Use on Latent Fingermarks.
U.S.A. Government Publication. Gaithersburg, MD: US. Dept. of Commerce,

National Bureau of Standards, Washington, DC, 1985.

[135] C. Stanley. Are ﬁngerprints a genetic marker for handedness? Behavior Genet-

ics, 24(2):141, 1994.

[136] J. P. P. Starink and E. Backer. Finding point correspondence using simulated

annealing. Pattern Recognition, 28(2):231—240, 1995.

[137] R. Stock. Automatic ﬁngerprint reading. In Proc. Int. Carnahan Conf. on
Electronic Crime Countermeasures, pages 16—28, University of Kentucky, Lex-

ington, Kentucky, 1977.

[138] G. Stockman, S. Kopstein, and S. Benett. Matching images to models for
registration and object detection via clustering. IEEE Trans. Pattern Anal.

and Machine Intell., 4(3):229—241, 1982.

[139] D. L. Swets and J. Weng. Using discriminant eigenfeatures for image retrieval.

IEEE Trans. PAMI, 18(8):831—836, 1996.

[140] E. Szekly and V Szekly. Image recognition problems of ﬁngerprint identiﬁcation.

Microprocessors and Microsystems, 17(4):215—218, 1993.

 

 

{141:

[142

{14;

[11.3

[141

226

[141] J. Ton and A. K. Jain. Registering Landsat images by point matching. IEEE

Transactions on Geoscience and Remote Sensing, 27(5):642—651, 1989.

[142] M. Trauring. Automatic comparison of ﬁngerprint-ridge patterns. Nature,

197(4871):938—940, 1963.

[143] TRS. Technology Recognition Systems Homepage. http://www.betac.com/trs/,

1998.

[144] M. Turk and A. Pentland. Eigenfaces for recognition. Journal of Cognitive

Neuroscience, 3(1):71—86, 1991.

[145] D. Valentin, H. Abdi, A. J. O’Toole, and G. Cottrell. Connectionist models of

face processing: A survey. Pattern Recognition, 27(9):1209—1230, 1994.
[146] Veridicom. Veridicom Homepage. http://www.veridicom.com/, 1998.

[147] V. V. Vinod and S. Ghose. Point matching using asymmetric neural networks.

Pattern Recognition, 26(8):1207—1214, 1993.
[148] Visionics. Visionics Homepage. http://www.visionics.com, 1998.

[149] C. 1. Watson. NIS T Special Database 9, Mated Fingerprint Card Pairs. National

Institute of Standards and Technology, 1993;

[150] C. 1. Watson. NIS T Special Database 4, Mated Fingerprint Card Pairs. National

Institute of Standards and Technology, 1994.

227
[151] J. Wegstein. The M40 Fingerprint Matcher. U.S.A. Government Publication.

Washington DC: National Bureau of Standards, Technical Note 878, US Gov-

ernment Printing Ofﬁce, 1972.

[152] J. H. Wegstein. An Automated Fingerprint Identiﬁcation System. USA. Gov-

ernment Publication, Washington, 1982.

[153] R. Wildes. Iris recognition: An emerging biometric technology. Proceedings of

IEEE, 85(9):1348—1363, 1997.

[154] J. Woodward. Biometrics: Privacy’s foe or privacy’s friend? Proceedings of

IEEE, 85(9):1480—1492, 1997.

[155] J. Zhang, Y. Yan, and M. Lades. Face recognition: Eigenface, elastic matching,

and neural nets. Proceedings of IEEE, 85(9):1423—1436, 1997.

[156] Y. A. Zuev and S. K. Ivanov. The voting as a way to increase the decision reli-
ability. In Proc. Foundations of Information/Decision Fusion with Applications

to Engineering Problems, pages 206—210, Washington, DC, August 1996.