1
$3..
.I . w > r .4
at“:
.w

.
i W. l
:mmf. r

a... .2.»

. é-
.mhz. a;
‘
£52....
3.
£3,121.
.

a

_ x
. I! .r. ’11.
26.55.... 1 .3.
3. .34 .2 .c A .x... I. .
a... a. .ﬂ....v..x..... Exam

.63...“

 

3.. J.
c1531....

1: {:1 I a
v:

Danny-Stun.

boaawicnwuw... . ﬂaw; . . x

.V...

 

J

K)"

/
1,:
-p

mam
2

2061-
t'aJS/Q

 

 

LIBRARY

MiChigan State This is to certify that the
University dissertation entitled

 

 

INFORMATION FUSION IN FINGERPRINT
AUTHENTICATION

presented by

ARUN ABRAHAM ROSS

has been accepted towards fulﬁllment
of the requirements for the

PhD. degree in Computer Science

 

 

wwv

 

Major Professor’s Signature

“—16—0}

 

Date

MSU is an Afﬁrmative Action/Equal Opportunity Institution

.n -<-.-.-v-- -.-,-.-,--.-.--

-~- --.<

 

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

 

DATE DUE

DATE DUE f

DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/01 c:/CIRC/DaleDue.p65-p.15

 

INFORMATION FUSION IN FINGERPRINT
AUTHENTICATION

By

Arun Abraham Ross

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 & Engineering

2003

ABSTRACT
INFORMATION FUSION IN FINGERPRINT AUTHENTICATION
By

Amn Abraham Ross

Although the problem of automatic ﬁngerprint matching has been extensively
studied, it is nevertheless, not a fully solved problem. In this thesis, an information
fusion approach is adopted to address some of the limitations of existing ﬁngerprint
matching systems. A hybrid ﬁngerprint system that utilizes both minutiae points
and ridge feature maps to represent and match ﬁngerprint images has been devel-
oped. The hybrid matcher is Shown to perform signiﬁcantly better than a traditional
minutiae-based matcher. The ridge feature maps extracted by this technique have
also been used to align and register ﬁngerprint image pairs via a correlation pro-
cess, thereby obviating the need to rely on minutiae points for image registration.
To address the problem Of partial prints obtained from small-sized sensors, a ﬁnger-
print mosaicking scheme has been developed. The proposed technique constructs a
composite ﬁngerprint template from two partial ﬁngerprint impressions by using the
iterative control point (ICP) algorithm that determines the transformation param-

eters relating the two impressions. TO mitigate the effect of non-linear distortions

in ﬁngerprint images on the matching process, an average deformation model has
been proposed. The model is developed by comparing a ﬁngerprint impression with
several other impressions Of the same ﬁnger and observing the common ridge points
that occur in them. An index of deformation has been suggested in this context to
aid in the selection of an ‘Optimal’ ﬁngerprint impression from a set of impressions.
Finally, techniques to combine ﬁngerprint information with the other biometric traits
Of a subject (viz., face and hand geometry) are presented. To enhance user conve-
nience, a learning methodology has been used to compute user—Speciﬁc parameters in
a multibiometric system. Information fusion systems, as presented in this thesis, are
expected to be more reliable and robust than systems that rely on a single source of

information.

lif— “ -.-———---1q

© Copyright 2003 by Arun Abraham Ross
All Rights Reserved

TO My Family - Love never fails

ACKNOWLEDGMENTS

Trust in the Lord with all your heart, And lean not on your own understanding; In all your ways

acknowledge Him, And He shall direct your paths.

Proverbs 3:5,6

In the last three and a half years I have learnt the importance Of relying on Jesus
completely. Thank you Lord for showing me the way.

I have been privileged to have Dr. Anil Jain as my advisor. His attention to detail,
quest for excellence, and love for perfection has inspired me to give my best time and
again. He has helped deﬁne my research and presentation skills, and I am deeply
indebted to him for making the Ph.D. experience a memorable one. I am grateful to
Dr. George Stockman for his constant encouragement and support during the course
of my program. Special thanks to Dr. James Reisman and Dr. Sarat Dass who have
collaborated with me on various occasions; I thoroughly enjoyed conducting research
work alongside them. I would like to express my gratitude to Dr. J ian-Zhong Qian for
his efforts in ensuring that I spend three productive summers at Siemens Corporate
Research (SCR) in Princeton; portions of my research work were made possible by a

vi

research grant from SCR. Many thanks to Dr. Dennis Gilliland for his guidance and
willingness to serve in my Ph.D. committee.

I am grateful to Dr. Salil Prabhakar and Dr. Sharath Pankanti for the excellent
support rendered over the past several years. The PRIP lab at MSU has proved to
be an excellent working atmosphere, and I will fondly remember the late nights and
weekends Spent in its precincts. I would like to thank Paul Albee, AnOOp Namboodiri,
Umut Uludag, Silviu Minut, Xiaoguang Lu, Martin Law, Miguel Figueroa-Villanue,
Michael Farmer, Shailesh Saini, Dan Gutchess, Friederike Griess, Unsang Park, Hong
Chen, Erin McGarrity, Dr. Vincent Hsu, Dr. Aditya Vailaya, Dr. Nicolae Duta, Dr.
Scott Connell, Dr. Yilu Zhang, Dr. Vera Bakic, Dr. Shaoyun Chen and Dr. Lin
Hong for engaging me in useful discussions many a time.

A special word of appreciation to Linda Moore, Starr Portice, Cathy Davison,
Debbie Kruch, Beverly Wallace and Mary Gebbia for their administrative assistance
and support. Thanks to Jay Kusler, John Lane, Margaret Wilke and the rest of the
team for their role as system administrators.

Finally, I would like to thank my parents, brother and sister for their incredible
love, prayers, enthusiasm, and encouragement; fellow believers for their timely counsel
and prayer; and my beautiful wife Lisa for saying “I do”. It is to them that I dedicate

this thesis to.

vii

TABLE OF CONTENTS

LIST OF TABLES
LIST OF FIGURES

1 Introduction

1.1 Biometrics ...................................
1.2 Fingerprint as a Biometric ..........................
1.2.1 Fingerprint Representation ........................
1.2.2 Fingerprint Matching ............................
1.2.3 Difﬁculties and Challenges in Fingerprint Matching ...........
1.3 Thesis Contributions .............................

2 Fingerprint Representation using Ridge Feature Maps

2. 1 Introduction ..................................
2.2 Fingerprint as Oriented Texture .......................
2.3 Image Filtering using Gabor Filters .....................
2.3.1 Fingerprint Enhancement .........................
2.3.2 Fingerprint Segmentation .........................
2.3.3 Filtering Enhanced Image .........................
2.4 Ridge Feature Maps .............................
2.4.1 Tossellation of Filtered Images ......................
2.4.2 Ridge Feature Map Deﬁnition .......................
2.5 Minutiae Extraction .............................
2.6 Alignment Using Minutiae Information ...................
2.6.1 Aligning Query and Template Images ...................
2.6.2 Matching Scores ..............................
2.6.3 Combining Matching Scores ........................
2.6.4 Fingerprint Identiﬁcation .........................
2.6.5 Experimental Results ............................
2.7 Alignment Using Ridge Feature Maps ....................
2.7.1 Constructing the Ridge Feature Map ...................
2.7.2 Fingerprint Matching Using Ridge Feature Maps ............
2.7.3 Experimental Results ............................
2.8 Summary ...................................

viii

xi

xii

OoI—tl-d

10
10
11
13

17
20
22
25
27
28
29
32
32
32
33
37
37
40
41
41
43
47
48
49
52
54

3 Fingerprint Mosaicking 55

3. 1 Introduction .................................. 57
3.2 Fingerprint Image Registration ....................... 60
3.3 Fingerprint Mosaicking ............................ 63
3.3.1 Preprocessing the Fingerprint Image ................... 64
3.3.2 Fingerprint Segmentation ......................... 64
3.3.3 Fingerprint as a Range Image ....................... 65
3.3.4 Registering Fingerprint Images ...................... 65
3.4 Experimental Results ............................. 71
3.5 Summary ................................... 72
4 A Deformable Model for Fingerprint Matching 74
4. 1 Introduction .................................. 76
4.2 General Warping Methods .......................... 81
4.3 The Fingerprint Warping Model ....................... 85
4.3.1 Establishing Ridge Curve Correspondences ................ 86
4.3.2 Sampling Ridge Curves .......................... 88
4.4 Average Deformation Model ....... , .................. 91
4.4.1 The <I> Index of Deformation ........................ 95
4.4.2 Eliminating Erroneous Correspondences .............. -. . . 96
4.5 Experimental Results ............................. 100
4.6 Summary ................................... 104
5 Multibiometrics 106
5.1 Fusion in Biometrics ............................. 110
5.1.1 Single Biometric Multiple Representation ................ 112
5.1.2 Single Biometric Multiple Matchers .................... 113
5.1.3 Multiple Biometric Fusion ......................... 114
5.2 Multibiometric System ............................ 115
5.2.1 Face Veriﬁcation .............................. 116
5.2.2 Hand Geometry ............................... 117
5.2.3 Combining the three modalities ...................... 118
5.3 Learning User—speciﬁc Parameters ...................... 126
5.3.1 User-speciﬁc matching thresholds ..................... 127
5.3.2 Weighting individual biometric traits ................... 129
5.4 Factors Affecting a User-speciﬁc Approach ................. 134
5.5 Summary ................................... 136
6 Conclusions and Future Work 139
6.1 Research Contributions ............................ 139
6.2 Future Research ................................ 141
APPENDICES 145

A Hand Geometry-based Biometric System 146

A.1 Why Hand Geometry? ............................ 146
A2 Background .................................. 147
A3 Image Acquisition ............................... 148
A31 Enrollment Phase .............................. 150
A32 Veriﬁcation Phase ............................. 150
A.4 Feature Extraction .............................. 151
A5 Experimental Results ............................. 158
BIBLIOGRAPHY 161

3.1

5.1

5.2

5.3

5.4

LIST OF TABLES

Increase in average image size and average number of detected minutiae
as a result of mosaicking ..........................

Error rates associated with ﬁngerprint, face and voice biometric systems.
The accuracy estimates of biometric systems depend on a number of
test conditions. ..............................

Performance of the linear discriminant classiﬁer on three different trials as
indicated by the confusion matrices. In each trial the training and test
sets were partitioned differently. .....................

User-speciﬁc thresholds for the biometric traits of 10 users corresponding
to a FAR of 1% in each ROC curve. .‘ ..................

Weights of different traits for 10 users. ...................

xi

67

108

125

131

LIST OF FIGURES

1.1 Examples of some of the biometric traits used for authenticating an indi-

1.2 The enrollment module and the veriﬁcation module of a biometric system.

vidual. ...................................

1.3 Deployment of Biometric systems in civilian applications. (a) A bor-

1.4

1.5

1.6

1.7

der passage system using iris recognition at London’s Heathrow air-
port (news.bbc.co.uk). (b) The INS Passenger Accelerated Service
System (INSPASS) at JFK international airport (New York) uses
hand geometry to authenticate travellers and Signiﬁcantly reduce
their immigration inspection processing time (wwwpanynjgov). (0)
Ben Gurion airport in Tel Aviv (Israel) uses Express Card entry
kiosks ﬁtted with hand geometry systems for security and immigra-
tion (www.az'rportnet.org). (d) The FacePass system from Viisage
is used in point-of-sale veriﬁcation applications like ATMS, therefore,
obviating the need for PINS (www.m'z'sagecom). (e) Indivos’ “Pay
by Touch” service uses ﬁngerprints to help customers speed up pay-
ments in restaurants and cafeterias. When an enrolled customer places
her ﬁnger on the sensor, the system retrieves her ﬁnancial account
and updates it (wwwkioskbustnesscom). (f) The Identix Touch-
Clock ﬁngerprint system is used in time and attendance applications
(www.cardsolutz’onscom) .........................

A ﬁngerprint image with the core and four minutiae points marked on

it. The ridge pattern along with the core and delta points deﬁne the

global conﬁguration, while the minutiae points deﬁne the local structure.
Fingerprint sensors installed on (a) a keyboard (the Cherry Biometric

Keyboard has a smart card reader and a ﬁngerprint sensor attached
to it); (b) a mouse (the ID Mouse manufactured by Siemens has a
capacitance-based ﬁngerprint sensor placed on a USB mouse).

A variety of ﬁngerprint sensors with different Speciﬁcations (e.g., sensing

technology, image size, image resolution, image quality, etc.) are now
available ...................................

Effect of noisy images on a ﬁngerprint authentication system. (a) Finger-

print obtained from a user during enrollment. (b) Fingerprint obtained
from the same user during veriﬁcation. The development of scars or
cuts can result in erroneous ﬁngerprint matching results. .......

xii

2
5

9

12

1.8 Non universality of ﬁngerprints: Four different impressions of a subject’s
ﬁnger exhibiting poor quality ridges. A ﬁngerprint system might not
be able to enroll this subject since minutiae information cannot be
reliably extracted ..............................

2.1 Fingerprint images acquired using the solid state Veridicom sensor (a)
and the optical Digital Biometrics sensor (b). The detected minutiae
points have been marked in both the ﬁngerprint images. 14 minutiae
have been detected in the ﬁrst case (c), and 39 in the second (d).

2.2 Histogram of the number of minutiae points extracted from images ac—
quired using the Veridicom and Digital Biometric sensors. A total of
2, 500 ﬁngerprint impressions were used to compute these histograms
for each sensor. The histograms suggest that substantially fewer minu-
tiae points are available in images obtained from solid-state sensors. .

2.3 Three impressions of a user’s ﬁngerprint exhibiting partial overlap: the
overlap between (a) and (b), and (a) and (c) is limited. .......

2.4 Fingerprint as an oriented texture pattern. (a) the constant inter-ridge
spacing in a local region of the ﬁngerprint; (b) the dominant direction
of the ridges in (a); (c) the power spectrum of (a) ............

2.5 Tessellating the ﬁngerprint image using a circular and a square grid. The
square tessellation, unlike the circular one, is not affected by the lo-
cation of the core point in the image. (a) Circular tessellation (80
sectors) about a core point. (b) Square tessellation (169 cells) over the
entire image. (0) Circular tessellation about a core detected close to
the boundary of the image. ((1) Square tessellation over image shown
in (c). The images were acquired using the Veridicom sensor. .

2.6 Gabor ﬁlters in spatial domain with eight different orientations used for
feature extraction. f = 0.125, 6, = 6,, = 6 = 4 ..............

2.7 Fingerprint image (a) before and (b) after enhancement. .........

2.8 Segmenting a ﬁngerprint image. (a) The original ﬁngerprint image. (b)
The binarized ﬁngerprint image. (c) The median ﬁltered image. ((1)
The edge image outlining the ridges. (e) The segmented ﬁngerprint
image. ...................................

2.9 Results of the ﬁltering process on the image shown in Figure 2.7(b). The
8 images correspond to the 8 different orientations of the Gabor ﬁlter.

2.10 Tessellating the ﬁltered image. (a) A ﬁngerprint image ﬁltered with a
Gabor ﬁlter oriented at 157.5°. (b) A square tessellation of the ﬁl-
tered image. (c) The ridge feature map (nc x nc) representation of the
ﬁngerprint ..................................

2.11 Feature maps representing the variance in intensity in the ﬁltered images
for each cell. For purposes of visualization, the feature values have
been scaled to the 0 - 255 range ......................

2.12 Flowchart of the minutiae extraction algorithm [1]. ............

2.13 Template feature extraction. A minutiae set and a ridge feature map are
extracted from the input ﬁngerprint image ................

xiii

15

18

19

19

21

24

27
28

30

31

33

34

36

38

2.14 The matching process. The minutiae matching module provides the trans-
formation parameters necessary to align the query image with the tem-
plate .....................................

2.15 Eight 300 x 300 ﬁngerprint impressions acquired using the Veridicom sen-
sor. Images (a) - ((1) correspond to the right index ﬁnger of one subject,
and images (e) - (h) correspond to the right middle ﬁnger of another
subject. The images were resized to 256 x 256 to speed-up Fourier
operations. ................................

2.16 ROC showing the performances of the three matchers. The hybrid matcher‘

is Observed to perform better than the minutiae matcher ........
2.17 Two impressions of the same ﬁnger that have a high minutiae matching
score but a low ridge feature map matching score. The hybrid score
results in a true match ...........................
2.18 Two impressions of the same ﬁnger that have a low minutiae matching
score but a high ridge feature map matching score. The hybrid score
results in a true match ...........................
2.19 The standard deviation map, {59} of the ﬁltered images shown in Figure
2.9. Each image is 240 x 240. ......................
2.20 The ridge feature map, {R9}, of the ﬁltered images shown in Figure 2.9.
Each image is 15 x 15. ..........................
2.21 ROC curves depicting matching performance of the correlation-based tech—
nique. ...................................

3.1 Fingerprint veriﬁcation: Multiple impressions of the same ﬁnger are stored
in the database as templates. The query image is matched against the
components of the template to verify the claimed identity. ......

3.2 Two impressions (300 x 300) Of the same ﬁnger acquired using the Veridi—

39

46

46

47

49

50

56

com sensor. The two impressions are Observed to have very little overlap. 57

3.3 Rolled versus dab prints. (a) - (d): A sequence of 4 rolled ﬁngerprint
impressions obtained using the Digital Biometric sensor. Successive
image frames are known to have spatial proximity. (e) - (h): Four
impressions of a ﬁnger obtained at different time instances using a
Veridicom sensor. The transformation between the impressions is not
known ....................................

3.4 Mapping an intensity image to a range image. (a) The original intensity
image. (b) The intensity image after median ﬁltering and scaling. (c)
The segmented intensity image. ((1) The range image corresponding to
the boxed region (rotated by ~ 90°) in (c) ................

3.5 Composite template construction: (a) First image after segmentation. (b)
Second image after segmentation. (c) Initial alignment. ((1) Final align-
ment. (e) Minutiae extracted from mosaicked images. (f) Composite
minutiae set obtained by augmenting individual minutiae sets. . . . .

3.6 The result of mosaicking six pairs of ﬁngerprint impressions. The spatial
extent of the mosaicked image is observed to be larger than that Of the
component images. ............................

xiv

59

66

68

69

3.7 Examples of poorly mosaicked image pairs. ................

3.8 The ROC curves indicating improvement in matching performance after
mosaicking templates. Utilizing the minutiae points that are extracted
from the composite ﬁngerprint image (M 3,) results in the best match-
ing performance. .............................

4.1 Aligning two impressions of the same ﬁnger using an affine transformation.
Due to non-linear distortions, the alignment is not accurate in some
regions. Only ﬁngerprint ridges are Shown for clarity [2]. .......

4.2 Alignment of two impressions Of the same ﬁnger using afﬁne transforma-
tion. (a) and (b) are the gray scale images; (0) and (d) are the thinned
(skeletonized) images of (a) and (b), respectively; and (e) shows the

alignment based on the thinned images. Ridge lines do not align in (e).

4.3 An example of minutiae correspondences between two impressions of a
ﬁnger. ...................................

4.4 An example of ridge curve correspondences between two impressions Of a
ﬁnger. ...................................

4.5 Non-linear deformations (with rotation and translation parameters re-
. moved) associated with two pairings involving the same template: (a)
Template image; (b) and (0) Query images; (d) and (e) Non-linear
deformation of (a) into (b) and (c), respectively. ............
4.6 Vector representation of ridge bifurcation used to establish correspon-
dences between component ridge curves. 0 marks the bifurcation
points in correspondence, and X marks the points on the ridges at
Euclidean distance d from 0. ......................

4.7 The average deformation model (shown as deformations on a reference
grid) corresponding to 6 templates of a ﬁnger sorted in increasing (I)-
values. (a) is chosen to be the optimal template since it has the least
@-value. ..................................

4.8 The average deformation model (shown as deformations on a reference
grid) of 3 different ﬁngers .........................

4.9 Examples of incorrect minutiae correspondences (a) resulting in erroneous
ridge curve correspondences (b) ......................

4.10 Effect of eliminating unreliable minutiae correspondences on the average
deformation model; (a) template ﬁngerprint, (b) average deformation
model with p = 100, and (c) average deformation model with p = 60.

4.11 Improved alignment of template and query images using ridge curve cor-
respondences (right panel). The alignment using minutiae correspon-
dences are shown in the left panel. Both sets of alignment use the TPS
warping model. ..............................

4.12 Improvement in matching performance when ridge curve correspondences
is used to deveIOp the average deformation model. ...........

78

84

94

97

98

102

4.13 Matching performance when the (1) index of deformation is used to se—
lect optimal templates. Both optimal and suboptimal templates using
ridge curve correspondences result in superior matching performance
compared to minutiae correspondences ..................

5.1 Intra—class variation associated with an individual’s face image. Due to
change in pose, an appearance-based face recognition system will not
be able to match these 3 images successfully, although they belong to
the same individual [3]. .........................

5.2 A bimodal biometric system Showing the three levels of fusion; FU: Fusion
Module, MM: Matching Module, DM: Decision Module. .......

5.3 The problem of face detection is compounded by the effects of complex
lighting and cluttered background. ...................

5.4 A Hand Geometry System. The sensor provides both the top and side
views of the subject’s hand. Features are extracted using the image of
the top-view only ..............................

5.5 Scatter Plot showing the genuine and impostor scores in 3-D space. The
points correspond to 3, 600 genuine scores (+) and 11,025 impostor
scores (0). ............... l ..................

5.6 ROC curves showing the performance of each Of the three individual
modalities ..................................

5.7 ROC curves Showing an improvement in performance when scores are com-
bined using the sum rule ..........................

5.8 ROC curves showing an improvement in performance when scores are com-
bined using the sum rule ..........................

5.9 Construction and Performance of the 05.0 Decision Tree. The perfor-
mance is indicated by confusion matrices .................

5.10 Linear Discriminant Analysis of the score vectors. The score vectors have
been plotted in a 2-dimensional space representing the ﬁrst and the sec-
ond discriminant variables. There are 1, 800 genuine score vectors(+)
and 11, 025 impostor score vectors (0). .................

5.11 Intra-class variability and inter-class similarity of hand geometry features
depicted using Chernoff faces. (a) The feature sets associated with a
user Showing large variability. (b) and (c) The feature sets associated
with two different users exhibiting similarity [4] ............

5.12 The impostor distributions of the face biometric feature vector of 3 users.
(a), (c) and (e) are the histogram of impostor scores associated with the
3 users. (b), (d) and (f) are the corresponding cumulative histograms.
For '7 = 0.3 it is observed that the thresholds for each of the users is
different. .................................

5.13 ROC curves exhibiting performance improvement when user-speciﬁc
thresholds are utilized to verify claimed identity. (a) Fingerprint; (b)
Face .....................................

102

109

111

116

117

119

120

121

122

123

124

128

130

131

5.14 ROC curves when using (a) equal weights for all three traits, and a user-
Speciﬁc matching threshold, (b) user-speciﬁc weights for all three traits
and a common matching threshold. ..................

5.15 (a) and (b) Fingerprint images of user 4 whose ridge details are not very
clear (wl = 0.2); (c),(d) and (e) Varying face poses of user 3 (102 =
0.1); (f) and (g) Incorrect placement of hand and the curved ﬁnger of
user 2 (103 = 0.2.) ............................

A.l Hand geometry sensing device. .......................
A2 The Sixteen axes along which feature values are computed. ........
A3 The gray scale proﬁle of pixels along a measurement axis ..........
A.4 Computation of the feature vector. .....................

132

156

A5 Chernoff Faces representing the average feature vectors of 20 different hands. 157

A6 Incorrect placement of hand ..........................
A.7 The ROC curve depicting the matching performance of the hand geometry
system ....................................

xvii

159

160

Chapter 1

Introduction

1. 1 Biometrics

A wide variety of systems require reliable personal authentication schemes to either
conﬁrm or determine the identity of individuals requesting their services. The purpose
of such schemes is to ensure that the rendered Services are accessed by a legitimate
user, and not anyone else. Examples of these systems include secure access to build-
ings, computer systems, laptops, cellular phones and ATMS. In the absence of robust
authentication schemes, these systems are vulnerable to the wiles of an impostor.
Traditionally, passwords (knowledge-based security) and ID cards (token-based
security) have been used to restrict access to systems. However, security can be eas-
ily breached in these systems when a password is divulged to an unauthorized user
or a card is stolen by an impostor; further, simple passwords are easy to guess (by an
impostor) and difﬁcult passwords may be hard to recall (by a legitimate user). The
emergence of biometrics has addressed the problems that plague traditional veriﬁca-

1

tion methods. Biometrics refers to the automatic identiﬁcation (or veriﬁcation) of an
individual (or a claimed identity) by using certain physiological or behavioral traits
associated with the person. By using biometrics it is possible to establish an identity
based on ‘who you are’, rather than by ‘what you possess’ (e.g., an ID card) or ‘what
you remember’ (e.g., a password). Biometric systems make use of ﬁngerprints, hand
geometry, iris, retina, face, hand vein, facial thermograms, signature, voiceprint, gait,
palmprint, etc. (Figure 1.1) to establish a person’s identity [5, 6]. While biometric
systems have their limitations [7], they have an edge over traditional security methods
in that it is signiﬁcantly difficult to lose, steal or forge biometric traits; further, they

facilitate human recognition at a distance (e.g., face and gait).

 

 

((1) Signature (e) Iris (f) Voice

Figure 1.1: Examples of some of the biometric traits used for authenticating an
individual.

Biometric systems also introduce an aspect of user convenience that may not

be possible using traditional security techniques. For example, users maintaining

different passwords for different applications may ﬁnd it challenging to recollect the
password associated with a speciﬁc application. In some instances, the user might
even forget the password, requiring the system administrator to intervene and reset
the password for that user. A Meta Group study reports that a password-related
help desk call may cost as much as $30 in terms of support staff time and money [8].
Maintaining, recollecting, and remembering passwords can, therefore, be a tedious
and expensive task. Biometrics, on the other hand, addresses this problem effectively,
thereby enhancing user convenience: a user can use different ‘passwords’ (biometric
traits) for different applications, with ‘password’ recollection not being an issue at
all.

A typical biometric system operates by acquiring biometric data from an indi-
vidual, extracting a feature set from the acquired data, and comparing this feature
set against the template feature set in the database. In an identiﬁcation scheme the
comparison is done against templates corresponding to all the enrolled users in order
to recognize the individual (a one—to—many matching); in a veriﬁcation scheme, the
comparison is done against only those templates corresponding to the claimed identity
in order to verify the claim (a one—to—one matching). Thus, identiﬁcation (“Whose
biometric data is this?”) and veriﬁcation (“Does this biometric data belong to Bob?”)
are two different problems with different inherent complexities [9]. The templates are
typically created at the time of enrollment, and depending on the application may or
may not require human personnel intervention. Figure 1.2 illustrates the enrollment
and veriﬁcation modules of a typical biometric system.

The veriﬁcation problem may be formally posed as follows: given an input feature

vector XQ and a claimed identity I , determine if (I, XQ) belongs to col or tag, where
w] indicates that the claim is true (a genuine user) and tag indicates that the claim
is false (an impostor). Typically, XQ is matched against X1, the biometric template

corresponding to user I, to determine its category. Thus,

an if 8(XQ,X1) _>_ 77,
(LXQ) e (1.1)

Log otherwise,
where S is the function that measures the similarity between X Q and X11, and n is a
predeﬁned threshold. Therefore, every claimed identity is classiﬁed as wl or (.02 based

on the variables Xq, I, X; and 17, and the function 8.

The identiﬁcation problem, on the other hand, may be stated as follows: given
an input feature vector XQ, determine the identity [1,, k E {1, 2, . . . N, N + 1}. Here
[1,12, . . .IN are the identities enrolled in the system, and I N+1 indicates the reject

case where no suitable identity can be determined. Hence,

1!: ifmax{S(XQ,X1k)}>n,k=1,2,...N,
XQ E k (1.2)

I NJ, 1 otherwise,

where X 1k is the biometric template corresponding to identity I k, and 17 is a predeﬁned

threshold.

Biometric systems are being increasingly deployed in large scale civilian appli-

cations (Figure 1.3). The Schiphol Privium scheme at the Amsterdam airport, for

 

1The value 8 (X q, X 1) is termed as a similarity score or matching score

Identity, I

 

 

Enrollment Module

% #[Biometrlc SenaoHeature Extractor}— x.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

User
Template
Database
Claimed identity, I
Verification Module
% .—7Lr8iometric Sensor eature Extractor] XI
User
"0
AW Matching Score f
Reject ed‘ WFeature Matcher

 

 

 

 

Figure 1.2: The enrollment module and the veriﬁcation module of a biometric system.

example, employs iris scan cards to speed up the passport and visa control proce-
dures [10]. Passengers enrolled in this scheme insert their card at the gate and look
into a camera; the camera acquires the eye image of the traveller and processes it
to locate the iris, and compute the Iriscode [11]; the computed Iriscode is compared
with the data residing in the card to complete user veriﬁcation. A similar scheme is
also being used to verify the identity of Schiphol airport employees working in high-
security areas. Thus, biometric systems can be used to enhance user convenience
while improving security.

A simple biometric system has four important modules:

1. Sensor Module which captures the biometric data of an individual. An example

is a ﬁngerprint sensor that captures ﬁngerprint impressions of a user.

2. Feature Extraction Module in which the acquired data is processed to extract
feature values. For example, the position and orientation of minutiae points in
a ﬁngerprint image would be computed in the feature extraction module of a

ﬁngerprint system.

3. Matching Module in which the feature values are compared against those in
the template by generating a matching score . For example, in this module,
the number of matching minutiae between the query and the template can be

computed and treated as a matching score.

4. Decision-making Module in which the user’s claimed identity is either accepted

or rejected based on the matching score generated in the matching module

 

Figure 1.3: Biometric systems in civilian applications. (a) A border passage sys—
tem using iris recognition at London’s Heathrow airport (news.bbc.c0.uk). (b) The
INS Passenger Accelerated Service System (INSPASS) at JFK international airport
(New York) uses hand geometry to authenticate travellers and signiﬁcantly reduce
their immigration inspection processing time (Iuww.panynjgov). (c) Ben Gurion
airport in Tel Aviv (Israel) uses Express Card entry kiosks ﬁtted with hand geom-
etry systems for security and immigration (wwwairportnetorg). (d) The FacePass
system from Viisage is used in point—Of-sale veriﬁcation applications like ATMS, there—
fore, obviating the need for PINS (urww.viisage.c0m). (e) Indivos’ “Pay by Touch”
service uses fingerprints to help customers speed up payments in restaurants and
cafeterias. When an enrolled customer places her ﬁnger on the sensor, the system
retrieves her financial account and updates it (wwui.ktioskbusiness.com). (f) The
Identix TouchClock ﬁngerprint system is used in time and attendance applications
(www.cardsolutionscom).

(veriﬁcation). Alternately, the system may identify a user based on the matching

scores (identiﬁcation).

1.2 Fingerprint as a Biometric

Among all biometric traits, ﬁngerprints have one of the highest levels Of reliability [12]
and have been extensively used by forensic experts in criminal investigations [13]. A
ﬁngerprint refers to the ﬂow of ridge patterns in the tip of the ﬁnger. The ridge ﬂow
exhibits anomalies in local regions of the ﬁngertip (Figure 1.4), and it is the position
and orientation of these anomalies that are used to represent and match ﬁngerprints.
Although not scientiﬁcally established, ﬁngerprints are believed to be unique across
individuals, and across ﬁngers of the same individual [14]. Even identical twins having
similar DNA, are believed to have different ﬁngerprints [15]. Traditionally, ﬁngerprint
patterns have been extracted by creating an inked impression of the ﬁngertip on paper.
The electronic era has ushered in a range of compact sensors that provide digital
images of these patterns. These sensors can be easily incorporated into existing
computer peripherals like the mouse or the keyboard (Figure 1.5), thereby making
this mode of identiﬁcation a very attractive proposition. This has led to the increased
use of automatic ﬁngerprint-based authentication systems in both civilian and law-

enforcement applications.

WDGEBFURCAHON

 

CORE

Figure 1.4: A ﬁngerprint image with the core and four minutiae points marked on it.
The ridge pattern along with the core and delta points deﬁne the global conﬁguration,
while the minutiae points deﬁne the local structure.

Sensor

   

(a) (b)

Figure 1.5: Fingerprint sensors installed on (a) a keyboard (the Cherry Biometric
Keyboard has a smart card reader and a ﬁngerprint sensor attached to it); (b) a
mouse (the ID Mouse manufactured by Siemens has a capacitance-based ﬁngerprint
sensor placed on a USB mouse).

1.2.1 Fingerprint Representation

The uniqueness of a fingerprint is determined by the topographic relief of its ridge
structure and the presence of certain ridge anomalies termed as minutiae points.
Typically, the global conﬁguration deﬁned by the ridge structure is used to determine
the class [16, 17] of the ﬁngerprint, while the distribution of minutiae points is used
to match and establish the similarity between two ﬁngerprints [1, 18]. Automatic
ﬁngerprint identiﬁcation systems, that match a query print against a large database
of prints (which can consist of millions of prints), rely on the pattern of ridges in the
query image to narrow their search in the database (ﬁngerprint indexing), and on the
minutiae points to determine an exact match( ﬁngerprint matching). The ridge flow

pattern itself is seldom used for matching ﬁngerprints.

1.2.2 Fingerprint Matching

Fingerprint matching techniques can be broadly classiﬁed as being minutiae-based or
correlation-based. Minutiae-based techniques attempt to align two sets of minutiae
points and determine the total number of matched minutiae [19, 20, 1]. Correlation-
based techniques, on the other hand, compare the global pattern of ridges and furrows
to see if the ridges in the two ﬁngerprints align [21, 22, 23, 24]. The performance
of minutiae-based techniques rely on the accurate detection of minutiae points and
the use of sophisticated matching techniques to compare two minutiae sets which
undergo non-rigid transformations. The performance of correlation-based techniques

is affected by non-linear distortions and noise present in the image. In general, it has

10

been Observed that minutiae-based techniques perform better than correlation—based
ones. Correlation-based techniques suffer from the following problems [25]: (a) A
ﬁngerprint image may have non-linear warping due to the effect of pressing a convex
elastic surface (the ﬁnger) on a ﬂat surface (the sensor). Moreover, various sub-regions
in the sensed image are distorted differently due to the non-uniform pressure applied
by the user. It is difficult to compare two such distorted prints, even if translation
and rotation effects are considered. (b) Based on the moisture content of the skin,
the acquired images may have either thin or thick ridges. Further, the quality Of
the images acquired using the sensor may vary with time, thereby complicating the

correlation process.

1.2.3 Difficulties and Challenges in Fingerprint Matching

Although the problem of automatic ﬁngerprint matching has been extensively
studied2, it is nevertheless, not a fully solved problem. There are a variety of un-
resolved issues that need to be addressed effectively in this rather popular biometric

technique. Some of the challenges are described below:

1. The new generation solid-state sensors are being increasingly used to acquire
ﬁngerprint images. These sensors when embedded in compact systems like lap-
tops, mouse, and cellular phones provide a small contact area (e. g., 0.6” x 0.6” in
a Veridicom sensor) for the ﬁngertip and, therefore, sense only a limited portion

of the ﬁngerprint. This complicates the problem of matching impressions due

 

2The earliest published work on automatic ﬁngerprint matching and classiﬁcation can be traced
back to the 19603 [26, 27, 28].

11

to the lack of sufficient minutiae information. It is, therefore, essential to aug—
ment minutiae information with alternate information available'in ﬁngerprints

in order to deal with the issues introduced by partial ﬁngerprint images.

2. Due to advancements in sensor technology, a variety of ﬁngerprint sensors with
different speciﬁcations are now available (Figure 1.6). However, a ﬁngerprint
matching system developed for a particular sensor is very often not compatible
with images acquired using other sensors. This lack of inter-operability limits

the utility of a matcher.

 

Figure 1.6: A variety of ﬁngerprint sensors with different speciﬁcations (e.g., sensing
technology, image size, image resolution, image quality, etc.) are now available.

3. The ﬁngerprint matching performance is affected by the non—linear distortions
present in the ﬁngerprint image. These distortions are a consequence of the
imaging process which requires the ﬁnger to be pressed against the sensor sur—

face. To facilitate good matching performance, these distortions have to be

12

accounted for prior to the matching stage.

4. While it is acknowledged that the ﬁngerprints of a person do not change over
time, it is possible for minor cuts and bruises to alter the ridge structure of
ﬁngerprints (Figure 1.7). Moreover, the moisture content of the ﬁngertip may
change over time affecting the quality of the ﬁngerprint image being acquired
from a user. The template ﬁngerprint data obtained during enrollment time may
not capture these variations. A protocol to update template data is necessary

to maintain system performance.

5. Some users consistently provide poor quality ﬁngerprints due to the dry nature
of their skin (Figure 1.8). It is difﬁcult to extract features from such poor quality
images. Users providing such noisy ﬁngerprint data might ﬁnd it difﬁcult to
enroll in and interact with a biometric system that uses only ﬁngerprints. To
address this issue, a multibiometric system, that uses other biometric traits in

addition to ﬁngerprints, has to be considered.

1.3 Thesis Contributions

In this thesis, multiple sources Of information are consolidated to enhance the per-
formance of automatic ﬁngerprint authentication systems. A few of the challenges
presented in the earlier section are, consequently, addressed. The four major contri-

butions of this thesis are listed below.

1. A hybrid ﬁngerprint matcher that avails of both the minutiae and texture infor-

13

   

(a)

Figure 1.7: Effect of noisy images on a ﬁngerprint authentication system. (a) Fin-
gerprint Obtained from a. user during enrollment. (b) Fingerprint Obtained from the
same user during veriﬁcation. The development of scars or cuts can result in erroneous
ﬁngerprint matching results.

mation present in ﬁngerprint images has been developed. The texture informa-
tion is extracted by applying a set of 8 Gabor ﬁlters to an enhanced ﬁngerprint

image, and texture features are represented using ridge feature maps.

N)

. To address the problem of partial prints, a ﬁngerprint mosaicking scheme has
been developed. The proposed scheme examines two partial impressions of a
ﬁnger and constructs a composite template image that includes information

from the individual prints.

03

. An average deformation model for ﬁngerprint images has been proposed. This
model accounts for the non-linear distortions present in ﬁngerprint images. The
model is developed by comparing a ﬁngerprint impression with several other

impressions of the same ﬁnger and observing the common ridge points that

14

 

’ (d)

Figure 1.8: Non universality of ﬁngerprints: Four different impressions of a subject’s
ﬁnger exhibiting poor quality ridges. A ﬁngerprint system might not be able to enroll
this subject since minutiae information cannot be reliably extracted.

15

occur in them.

4. TO enhance the performance of a ﬁngerprint system, the face and hand geometry
traits of a subject are also used. By fusing information gleaned from multiple
biometric indicators, the performance of a biometric system can be improved.
The proposed multibiometric system also employs a learning technique to com-

pute user-speciﬁc parameters in order to improve veriﬁcation performance.

In the subsequent chapters, a detailed description of each of these contributions

is provided.

16

Chapter 2

Fingerprint Representation using

Ridge Feature Maps

Most ﬁngerprint matching systems rely on the distribution of minutiae on the ﬁnger-
tip to represent and match ﬁngerprints. The advent of solid-state sensors presents
new opportunities as well as fresh challenges to traditional ﬁngerprint matching algo-
rithms. These sensors provide only a small contact area (0.6” x 0.6”) for the ﬁngertip
and, therefore, sample only a limited portion of the ﬁngerprint pattern (e. g., 300 x 300
pixels at 500 dpi). An optical sensor, on the other hand, may have a contact area
of approximately 1” x 1”, resulting in images of size 480 x 508 pixels at 500 dpi.
Hence, the number of minutiae points that can be extracted from a ﬁngerprint sam-
ple acquired using a solid-state sensor is smaller compared to that acquired using an
optical sensor. Figures 2.1 and 2.2 illustrate this difference. Also, multiple impres-
sions of the same ﬁnger, acquired at different instances using a solid-state sensor, may
Overlap over a small region region due to the rotation and translation of subsequent

17

 

Figure 2.1: Fingerprint images acquired using the solid state Veridicom sensor (a)
and the optical Digital Biometrics sensor (b). The detected minutiae points have
been marked in both the ﬁngerprint images. 14 minutiae have been detected in the
ﬁrst case (c), and 39 in the second ((1).

ﬁngerprints. The minutiae-based matching schemes will not perform well in such
situations due to the lack of a sufficient number of common minutiae points between
the two impressions. Thus, there is a need to explore complimentary representations
of ﬁngerprints.

While the ridge ﬂow pattern is generally used for classifying ﬁngerprints, it is
seldom used in matching. We develop a hybrid ﬁngerprint matching scheme that

uses both minutiae and ridge ﬂow information to represent and match ﬁngerprints.

18

 

DIGITAL BIOIETRICS SENSOR

$

§

Number of Fingerprint Images
a

i

 

 

 

Figure 2.2: Histogram of the number of minutiae points extracted from images ac-
quired using the Veridicom and Digital Biometric sensors. A total of 2, 500 ﬁngerprint
impressions were used to compute these histograms for each sensor. The histograms
suggest that substantially fewer minutiae points are available in images obtained from
solid-state sensors.

 

Figure 2.3: Three impressions of a user’s ﬁngerprint exhibiting partial overlap: the
overlap between (a) and (b), and (a) and (c) is limited.

A set of 8 Gabor ﬁlters, whose spatial frequencies correspond to the average inter-
ridge spacing in ﬁngerprints, is used to capture the ridge strength at equally spaced
orientations. A square tessellation of the ﬁltered images is then used to construct
an eight-dimensional feature map, called the ridge feature map. The ridge feature
map along with the minutiae set of a ﬁngerprint image is used for matching purposes.
The proposed technique has the following features: (i) the entire image is taken into
account while constructing the ridge feature map; (ii) minutiae matching is used
to determine the translation and rotation parameters relating the query and the
template images for ridge feature map extraction; (iii) ﬁltering and ridge feature
map extraction are implemented in the frequency domain thereby Speeding up the
matching process; (iv) ﬁltered query images are cached to greatly increase the one-
tO—many matching speed. The hybrid matcher performs better than a minutiae-based

ﬁngerprint matching system.

2. 1 Introduction

The ridge pattern in a ﬁngerprint may be viewed as an oriented texture pattern
having a ﬁxed dominant spatial frequency and orientation in a local neighborhood.
The frequency is due to the inter-ridge spacing present in the ﬁngerprint (ﬁgure
2.4(a)), and the orientation is due to the ﬂow pattern exhibited by the ridges (ﬁgure
2.4(b)). By capturing the frequency and orientation of ridges in non-overlapping local
regions in the ﬁngerprint, a distinct representation of the ﬁngerprint is possible. One

such representation has been discussed in [29]. However, to match two ﬁngerprints

20

using such a representation, a suitable alignment of the underlying ridge structures

is essential.

|

1

 

Figure 2.4: Fingerprint as an oriented texture pattern. (a) the constant inter-ridge
spacing in a local region of the ﬁngerprint; (b) the dominant direction of the ridges
in (a); (c) the power Spectrum of (a).

We describe a ﬁngerprint representation scheme, that constructs a feature map
by Observing the local ridge orientation in a ﬁngerprint image. The local ridge char-
acteristics are extracted via a set of Gabor ﬁlters that are pre—tuned to a speciﬁc
frequency corresponding to the average inter-ridge spacing in a ﬁngerprint image. An
input ﬁngerprint image is ﬁltered using this set of Gabor ﬁlters; a square tessella-
tion [30] is then applied to each ﬁltered image to examine the local response to the
ﬁlter; a feature vector which measures the energy in the ﬁltered images for each of
the tessellated cells is next obtained. A collection of these feature vectors (over the
tessellation) constitutes the ridge feature map used to represent a ﬁngerprint. Fin-
gerprint matching entails determining the similarity between two such ridge feature
maps. This representation is used along with the minutiae set of the ﬁngerprint im-

age for matching purposes. The proposed representation and matching scheme are

21

motivated by the following observations:

1. Global image information, as deﬁned by the ridge pattern of the ﬁngerprint,
is not being explicitly used during the matching phase in most of the current
matching systems. We believe that the ridge pattern, when observed at various
resolutions and orientations, provides discriminatory information that can be

used for matching ﬁngerprints.

2. Minutiae information may not be very discriminative in the case of solid-state
sensors which typically capture only a small area of the ﬁngertip. For example,
the average number of minutiae points extracted from Digital Biometrics Optical
sensor images (500 x 500 image at 500 dpi) is 45 compared to 25 minutiae
obtained from Veridicom solid-state sensor images (300 x 300 image at 500 dpi).
Alternate representations, to supplement minutiae information, are necessary to
maintain sufﬁcient ﬁngerprint identiﬁcation performance in such cases. Further,
in poor quality images, while it is difﬁcult to accurately locate minutiae points,

the ridge pattern features may be easier to detect.

2.2 Fingerprint as Oriented Texture

Jain et al. [29] have proposed a novel representation scheme that captures global and
local features of a ﬁngerprint in a compact ﬁxed length feature vector termed as Fin-
gerCode. This technique makes use of the texture features available in a ﬁngerprint
to compute the feature vector. Their scheme for generic representation of oriented

texture relies on extracting a core point in the ﬁngerprint. A circular region around

22

the core point is located and tessellated into sectors as shown in Figure 2.5(a). The
pixel intensities in each sector are normalized to a constant mean and variance, and
ﬁltered using a bank Of 8 Gabor ﬁlters to produce a set of 8 ﬁltered images. Gray scale
variance within a sector quantiﬁes the underlying ridge structures and is used as a
feature. The 640-dimensional feature vector is the collection of all the features, com-
puted from all the 80 sectors, in each of the ﬁltered image. The FingerCode captures
the local information, and the ordered enumeration of the tessellation captures the
invariant global relationships among the local patterns. The matching stage simply
computes the Euclidean distance between the two corresponding FingerCodes. This

technique, however, suffers from the following shortcomings:

1. The frame Of reference is based on a global singular point (i.e., the core point).
Detection of the core point is non-trivial; futhermore, the core point may not

even be present in the captured ﬁngerprint images.

2. The alignment is based on a single reference point and is, therefore, not very

robust with respect to errors in the location of the reference point.

3. The tessellation does not cover the entire image. Furthermore, if the core were
to be detected close to the boundary Of the image, the tessellation will include

an extremely small portion of the image (Figure 2.5(c)).
The technique proposed here has the following advantages:

1. Unlike in [29], the ﬁltering is done on the enhanced images rather than the
raw input images. The enhanced images have lower noise content than the raw

images.

23

 

Figure 2.5: Tessellating the ﬁngerprint image using a circular and a square grid. The
square tessellation, unlike the circular one, is not affected by the location of the core
point in the image. (a) Circular tessellation (80 sectors) about a core point. (b)
Square tessellation (169 cells) over the entire image. (c) Circular tessellation about a
core detected close to the boundary of the image. (d) Square tessellation over image
shown in (c). The images were acquired using the Veridicom sensor.

24

2. Instead of using circular tessellation, a square tessellation is used (Figure
2.5(b)). The tessellation covers the entire image, and all the tessellated cells
are of the same size. Moreover, the tessellation is not based on detecting any

landmark points.

3. The ﬁngerprint images are aligned using the overall minutiae information; this

is more robust than using only the core point for aligning image pairs.

4. In the absence of reliable minutiae information, we describe a correlation based

technique that utilizes ridge feature maps alone.

2.3 Image Filtering using Gabor Filters

A 2D Gabor ﬁlter can be thought of as a complex plane wave modulated by a 2D
Gaussian envelope. These ﬁlters optimally capture both local orientation and fre-
quency information1 and their development was motivated by observing the linear
response of the receptive ﬁeld in simple striate cortex cells. By tuning a Gabor ﬁlter
to a speciﬁc frequency and direction, the local frequency and orientation information
can be obtained. Thus, they are suited for extracting texture information from im-
ages. Daugman has successfully used these ﬁlters to extract salient features from the
human iris [11].

An even symmetric Gabor ﬁlter has the following general form in the spatial

 

1They are optimal in the sense that they try to minimize simultaneously the joint space-spatial
frequency uncertainty [31, 32].

25

domain:

G (:1: ) *- e:r :1- E + g cos(27rfx') (21)
orf i y — p 2 63 612’ , .
:r' = :rsind + ycosd,
y’ = xcosd — ysind,

where f is the frequency of the sinusoidal plane wave at an angle 0 with the :r-axis,
and 6, and 6,, are the standard deviations of the Gaussian envelope along the a: and
y axes, respectively.

For extracting the response of the ridge at‘various orientations of the Gabor ﬁlter,
the parameters (f, 63, 6,,, 0) are set to the following values:
(i) The frequency, f, corresponds to the inter-ridge distance in ﬁngerprint images.
For the 300 x 300 (500 dpi) images obtained using the Veridicom sensor and resized
to 240 x 240 (see section 2.6.5), the average inter-ridge spacing is about 8 pixels.
Hence, f = § = 0.125.
(ii) The selection of the standard deviation values, 6x and 6y, involves a trade—off.
Larger values are more robust to noise, but will not capture ridge information at a
ﬁne level. Smaller values, on the other hand, are less robust to noise in the image,
but capture ridge information very well. Based on empirical data [33], both these
values were set to 4, i.e., 6:: = 6,, = 6 == 4.
(iii) Eight different orientations are examined. These correspond to 0 values of 0°,
225°, 45°, 67.5°, 90°, 112.5°, 135°, 157.5° (Figure 2.6).

These parameters are ﬁxed during the matching process, allowing for pre-storing

26

 

 

 

the Gabor ﬁlter representations in a lookup table referred to as the Gabor ﬁlter bank.
This ﬁlter bank precalculates the Fourier representation of the Gabor ﬁlter for all
orientations of interest. This formulation substantially improves the matching time

in a one-to-many matching scheme.

 

(b) 22.50 (c) 45° (d) 67.5°

   

(0 112.50 (g) 135° (h) 157.5°

Figure 2.6: Gabor ﬁlters in spatial domain with eight different orientations used for
feature extraction. f = 0.125, 5,. = 6,, = 6 = 4.

2.3.1 Fingerprint Enhancement

Enhancement is the process by which the clarity of the ridge and furrow structures
in the ﬁngerprint images is improved to facilitate the feature extraction process [33]
[34]. Fingerprint enhancement helps in reducing the noise content in the ﬁngerprint
image. Enhancement, however, can also introduce false ridges, resulting in spurious
or missing minutiae points. Since the ridge feature map representation proposed here

relies on the dominant ridge directions in each tessellated cell, the introduction of

27

false ridges is not a serious problem. The minutiae features are also extracted after
processing the enhanced ﬁngerprint image. The enhancement algorithm is based on
the technique described in [33]. Figure 2.7 shows a ﬁngerprint image before and after

enhancement.

Ml‘w w

‘1]. .[l‘
H .«l

 

Figure 2.7: Fingerprint image (a) before and (b) after enhancement.

2.3.2 Fingerprint Segmentation

The ridge feature map is constructed using the feature values computed at each tes-
sellated cell. Certain cells may predominantly contain background information, and
therefore, the feature values computed at these cells will not be an accurate indication
of ridge strength. Thus, the purpose of segmentation is to separate the foreground
and background regions in a given ﬁngerprint image. The foreground corresponds to
those regions in the image that have relevant ﬁngerprint information (i.e., the ridges
and valleys of the ﬁngerprint), while the background represents those regions that do

not have the relevant information. Cells with predominantly background information

28

are not used during the matching stage. Segmentation is done by observing the local
variation of intensity on the original gray-scale image [1].

The algorithm to segment a ﬁngerprint image is as follows:

1. The intensity of the input ﬁngerprint image is normalized to the range [0,1].
Such a normalization ensures that the effect of any rapid changes in intensity

over the image is minimized.

2. The image is binarized by selecting a threshold that corresponds to one-ha] f of

the mean of the normalized image intensity (Figure 2.8(b)).

3. A 3 x 3 median ﬁlter is applied to the binarized image. This Operation removes
any undesirable “salt-and-pepper” noise that may be present in the binarized

image (Figure 2.8(c)).

4. An edge detection algorithm is applied to the binary image to get the outline

of ridges (Figure 2.8(d)).

5. Graham’s convex hull algorithm [35] is applied on the edge image to generate

a polygon that segments the ﬁngerprint image (Figure 2.8(e)).

2.3.3 Filtering Enhanced Image

Filtering requires convolving the enhanced image, H, with each of the 8 Gabor ﬁlters
in the spatial domain. However, convolution in the spatial domain would be extremely
slow. For example, a 256 x 256 image convolved with a 16 x 16 ﬁlter would need ~ 107

multiplications (assuming that the convolution Operation has not been optimized). In

29

 

The original ﬁngerprint image. (b)

)

a

(

The binarized ﬁngerprint image. (c) The median ﬁltered image. (d) The edge image

outlining the ridges. (e) The segmented ﬁngerprint image.

Figure 2.8: Segmenting a ﬁngerprint image.

30

order to speed—up this operation, we perform the convolution in the frequency domain.
Let f (H ) denote the discrete Fourier transform of H, and let f(Gg) indicate the
discrete Fourier transform of the Gabor ﬁlter having the spatial orientation 0 as
described by Equation (2.2). Thus, the Gabor ﬁltered image, V9, may be obtained

as:

Va = 7"1[7(H)T(Ga)li (2-2)

where .7“ is the inverse Fourier transform. Eight ﬁltered images are obtained as a

result of this ﬁltering (Figure 2.9).

 

Figure 2.9: Results of the ﬁltering process on the image shown in Figure 2.7(b). The
8 images correspond to the 8 different orientations of the Gabor ﬁlter.

31

2.4 Ridge Feature Maps

2.4.1 Tessellation Of Filtered Images

While a ﬁltered image in its entirety can be used as a representation scheme, the
presence of local distortions would adversely affect the matching process. Moreover, it
is the local variations in ridge structure (combined with the global ridge conﬁguration)
that provide a better representation of the ﬁngerprint. To examine local variations,
the image is tessellated into square cells, and features from each of the cells are
computed (Figure 2.10). The size of a cell is chosen to correspond to approximately
the width of two ridges (16 x 16). A 8 pixel wide border of the image is not included
in the tessellation. This results in no = 15 cells in each row and column Of the square
grid. The total number of tessellated cells over the image is, therefore, NC = 225.
The variance of the pixel intensities in each cell across all ﬁltered images is used as
a feature vector. The variance corresponds to the energy of the ﬁlter response, and
is, therefore, a useful measure of ridge orientation in a local neighborhood. Those
tessellated cells that contain a certain proportion of background pixels are labeled as

background cells and the corresponding feature value is set to 0.

2.4.2 Ridge Feature Map Deﬁnition

Let Cg(i, j) refer to the (i, j)th cell in the square grid that is placed on the ﬁltered
image V9. The variance, 03(i, j), represents the feature value corresponding to the

cell. Thus, for each V9, a feature map of variance values can be Obtained. Let R9

32

 

Figure 2.10: Tessellating the ﬁltered image. (a) A ﬁngerprint image ﬁltered with a
Gabor ﬁlter oriented at 157.5°. (b) A square tessellation of the ﬁltered image. (c)
The ridge feature map (nC x nc) representation of the ﬁngerprint.

denote the feature map associated with the ﬁltered image V9. Then,

Re = {CHAD}, (2-3)

where 0 E {0°,22.5°,45°,67.5°,90°,112.5°,135°,157.5°}, i = 1...nc,j = 1...nc.
An eight-dimensional feature map corresponding to the 8 ﬁltered images is Ob-
tained in this way (Figure 2.11). These ridge feature maps are used to represent and

match a query image with a template.

2.5 Minutiae Extraction

Minutiae extraction refers to the process by which the minutiae points are detected in
a ﬁngerprint image. Each minutiae is characterized by its (2:, y) location in the image,
and the orientation 0 of the ridge on which it is detected. The ridge information in
a 64 x 64 region around the (2,31) point is associated with every minutiae which is

useful when two minutiae sets are being matched. The minutiae extraction scheme

33

 

Figure 2.11: Feature maps representing the variance in intensity in the ﬁltered images
for each cell. For purposes of visualization, the feature values have been scaled to the
0 - 255 range.

34

(Figure 2.12) can be broadly classiﬁed into the following stages:

(i) Orientation Field Estimation: The orientation of the ﬁngerprint image is computed
in non-overlapping blocks by examining the gradients of pixel intensities in the a: and
y directions within the block.

(ii) Ridge Detection: The ridges present in the ﬁngerprint image are identiﬁed by
applying masks that are capable of accentuating the local maximum gray level values
along the normal direction of the local ridge direction.

(iii) Ridge Thinning: The ridge map constructed in the earlier stage is used to obtain
a thinned ridge image.

(iv) Minutiae Detection: A set of rules is applied to the thinned ridges to label
minutiae points (ridge endings and ridge bifurcations). As a postprocessing step, a

reﬁnement algorithm is applied to remove spurious minutiae points.

Minutiae matching involves a point matching Operation on the two minutiae sets.
Jain et a1. apply a elastic string matching technique to compare the two minutiae
sets [1]. The output of the matching process is a matching score that indicates the
similarity of the two minutiae sets being compared, and a correspondence map that
indicates pairing Of minutiae points from the two sets. The correspondence map is
used to compute the transformation parameters necessary to align the two ﬁngerprint

images.

35

 

Extracted Ridges

 

 

 

 

Minutiae Polnte Thinned Ridges

 

   

 

 

 

 

 

Figure 2.12: Flowchart of the minutiae extraction algorithm [1].

 

 

 

 

36

2.6 Alignment Using Minutiae Information

The process of ﬁngerprint matching involves comparing a query print with a set Of one
or more template prints. Prior to the matching process, features are extracted from
all the template images (Figure 2.13). The hybrid ﬁngerprint matcher proposed here
utilizes two distinct sets of ﬁngerprint information for matching ﬁngerprints: minutiae
features, and ridge feature maps. When a query image is presented, the matching
proceeds as follows: (i) the query and template minutiae features are matched to
generate a minutiae matching score and a transformation parameter (translation and
rotation) that relates the query and template ﬁngerprints; (ii) the rotation parameter
is used to rotate the 8 Gabor ﬁlters and the modiﬁed ﬁlters are applied to the query
image; (iii) the ﬁltered query images are then translated and rotated according to
the parameters; (iv) the ridge feature map is extracted from these ﬁltered images;
(v) the query and template ridge feature maps are matched; (vi) the minutiae and
ridge feature map matching results are combined to generate a single matching score

(Figure 2.14).

2.6.1 Aligning Query and Template Images

For comparing the ridge feature maps of two images, it is necessary that the images
themselves are aligned appropriately to ensure an overlap of common region in the
two ﬁngerprint images. This is done by determining the transformation parameters,
(t3, ty, t¢), that would align the query image with the template. As indicated in section

2.5, the correspondence map provided by the minutiae matcher is used to compute

37

Enhancement {I

 

F ilren'ng in frequency domain
( 8 Gaborﬁllerx)

 

\¥\

..' t. ( . ‘
— (like
\‘k 3.\

 

 

 

 

 

 

‘7
. I I - Fem” amnion

 

(N
F .
Tesselarr'on
‘

 

 

8 Filtered Images Ridge Feature Map

Figure 2.13: Template feature extraction. A minutiae set and a ridge feature map

are extracted from the input ﬁngerprint image.

38

"' " ' :‘nm-In’nﬁ In n”;- gun-y with Itmplale
before extracting ridge feature map of query

 

 

 

 

—> Minutiae <—
Mo‘lchlng

Score

ll

Marching
Sum Rule
Scare

ll

 

Score

Feature Mm
Matching

 

 

 

Ridge feature map

 

 

 

 

 

 

 

Query

Figure 2.14: The matching process. The minutiae matching module provides the
transformation parameters necessary to align the query image with the template.

39

(tr,ty,t¢). The estimated rotation parameter (t¢) is the average of the difference
in individual rotation values of all corresponding minutiae pairs. The translation
parameters (t1, ty) are computed using the spatial coordinates of the minutiae pair
that resulted in the best alignment.

Once the transformation parameters, (t3, ty, t¢), are Obtained, the query image can
be aligned with the template. But rotating the query image will result in artifacts that
may affect the subsequent ﬁltering operation. In order to avoid this, appropriately
rotated Gabor ﬁlters are applied to the query image. The resulting ﬁltered images
are then rotated and feature values extracted. Let H represent the enhanced query
image, and (t1, ty, t4,) be the translation and, rotation parameters obtained using the

minutiae matching information. Then the ﬁltered image, V9”, is Obtained as,

Vim, = Rott¢f"l[f(H).7-'(Gg_t¢)], (2.4)

where Rota, indicates that the ﬁltered image is rotated by an angle t¢. The notation
V9,“ is used to indicate that the ﬁltered image corresponding to ﬁlter orientation 6—t4,
was rotated through an angle t¢. The ﬁltered image is then translated by (tr, ty), in
order to ensure that the tessellation of the query image would overlap with that of

the template.

2.6.2 Matching Scores

The minutiae matching score is a measure of the similarity of the minutiae sets of

the query and template images; the higher the matching score the better the match.

40

The similarity score is normalized in the [0, 100] range. The ridge feature maps Of the
query and the template images are compared by computing the sum of the Euclidean
distances of the 8-dimensional feature vectors in the corresponding tessellated cells.
Cells that are marked as background, are not used in the matching process. This
results in a distance score measure; a higher distance score indicates a poor match.
The distance score is normalized in the [0,100] range, and converted to a similarity

score by simply subtracting it from 100.

2.6.3 Combining Matching Scores

The matching scores generated by comparing the minutiae sets and the ridge feature
maps, are combined in order to generate a Single matching score. While a variety Of
strategies [36] may be used to fuse these scores, we adopt the simple sum rule. Let
S M and 83 indicate the similarity scores obtained using minutiae matching and ridge
feature map matching, respectively. Then, the ﬁnal matching score, S, is computed
as,

S = (15M + (1 “ (1)512, (2-5)

where a 6 [0,1]. For the experimental results reported in this paper, a was set to

0.5. It is possible to vary a to assign different weights to the individual matchers.

2.6.4 Fingerprint Identiﬁcation

Fingerprint identiﬁcation involves matching a query image against multiple templates

(corresponding to different users) in order to determine the best matching score and,

41

therefore, the template that best resembles it. It is Obvious that the processing time
required to perform identiﬁcation (one-to-many matching) is substantially more than
that required for veriﬁcation (one-to—one matching). In order to reduce the number
Of matching operations, most ﬁngerprint identiﬁcation systems use some indexing
mechanism, to narrow the number of templates against which the query image has
to be matched. A variety of ﬁngerprint indexing mechanisms have been proposed in
the literature [16] [37] [38] [39]. However, in the identiﬁcation process described in this
paper, we do not use an indexing mechanism to limit the number of matchings. The
identiﬁcation process requires ﬁltering and rotating the query image for every match
that is performed (Eq. (2.4)). Computing View is an expensive operation because
of the Fourier operations performed. To decrease the computational complexity in-
volved, a combination of frequency domain ﬁltering, and ﬁltered image-caching, is
done. Caching Vim, avoids recomputing this ﬁltered image. Each time a query image,
Q, is presented, the following sequence Of operations is performed:

Step 1: Let the image-cache be represented by K. Set K = (I) (the empty set).

Step 2: Extract the minutiae set of Q, N! Q

For all the templates {T,-} in the database, represented by their minutiae set {MT‘}
and ridge feature map {Rn}, do steps 3 to 7.

Step 3: Compute the transformation parameters, (15..., ty, t¢), relating Q and Ti, using
the minutiae sets M Q and M T‘ as described earlier.

Step 4: If V9,“ 6 K, do step 6.

Step 5: Compute V9,“ according to Eq. (2.4).. K = K U Von-

Step 6: Offset Vim, using (t1, ty) and perform tessellation and ridge feature map ex-

42

traction. Let RQ be the ridge feature map of the query image.
Step 7: Use MQ, MT‘, RQ and RT‘ to generate the matching scores SM and SR.
Combine scores using Eq. (2.5).

Step 5 is performed only when V9,“ has not been computed at an earlier stage,

thus improving the speed Of the one-tO-many matching process.

2.6.5 Experimental Results

The ﬁngerprint database used in our experiments consists Of ﬁngerprint impressions
Obtained from 160 non-habituated, cooperative subjects using the Veridicom sensor
(300 x 300 images at 500 dpi). The data was collected over two sessions. The subjects
mainly consisted of students, faculty and staff at Michigan State University, and their
relatives and friends. Approximately 35% of the subjects were women. In the ﬁrst
session, each subject was asked to provide 2 impressions of each of 4 different ﬁngers -
the left index ﬁnger, the left middle ﬁnger, the right index ﬁnger and the right middle
ﬁnger. A set Of 1, 280 (160 x 4 x 2) images were collected in this way. The subjects
were requested to provide their ﬁngerprint images again, after a period of 6 weeks.
During the second session, the same procedure was adopted, and an additional 1, 280
images were obtained. Thus, a total of 2,560 images were acquired over two time
sessions (Figure 2.15). We refer to this database as the MSU_VERIDICOM database.
The 300 x 300 images were resized to 256 x 2562 in order to speed-up the Fourier

transformations.

 

2The images were ﬁrst resized to 240 x 240 using a bicubic interpolation; they were then padded
with zeros to increase the Size to 256 x 256. The padding was necessary to avoid the wrap-around
distortions at the border when the image is convolved with the Gabor ﬁlters.

43

 

Figure 2.15: Eight 300 x 300 ﬁngerprint impressions acquired using the Veridicom
sensor. Images (a) - (d) correspond to the right index ﬁnger of one subject, and
images (e) - (h) correspond to the right middle ﬁnger of another subject. The images
were resized to 256 x 256 to speed-up Fourier operations.

The performance of a biometric system can be measured by reporting its False
Accept Rate (FAR) and False Reject Rate (FRR) at various thresholds. These two
error rates are brought together in a Receiver Operating Characteristic (ROC) curve
that plots the FRR against the FAR at different thresholds. (Alternately, the genuine
accept rate (GAR), which equals l—FRR, may be plotted against the FAR). The FAR
and FRR are computed by generating all possible genuine and impostor matching
scores and then setting a threshold for deciding whether to accept or reject a match.
A genuine matching score is obtained when two feature vectors corresponding to the
same individual are compared, and an impostor matching score is obtained when

feature vectors from two different individuals are compared.

The ROC curves depicting the performances of the minutiae, ridge feature map

44

and hybrid matchers are shown in Figure 2.16. The hybrid technique outperforms
the minutiae-based scheme over a wide range of FAR values. For example, at a
FAR of 0.1%, the GAR of the minutiae matcher is ~ 67%, while that of the hybrid
matcher is ~ 84%. The equal error rate of the hybrid technique is observed to be
~ 4%. The experiments also show that the minutiae information and ridge ﬂow
information complement each other. Consider Figure 2.17 that shows two different
impressions of a ﬁnger. For this pair, matching the minutiae sets results in a high
matching score, but matching the ridge feature map results in a low score (due to the
limited amount of foreground overlap between the two impressions). The hybrid score,
however, results in a positive match (at a certain matching threshold) between the two
impressions. Now consider the ﬁngerprint impressions (of another ﬁnger) in Figure
2.18. The minutiae matching score is rather low in this case (due to spurious minutiae
being detected in both images), while the ridge feature map matching score is high
(enhancing the image provides sharp dominant ridge directions). The hybrid score
results in a positive match of the two impressions (at a certain matching threshold),
thereby underlining the importance of the proposed technique.

The experiments reported here were conducted on a Pentium III, 800 Mhz pro-
cessor, running Windows 2000. Minutiae extraction took ~ 1 second, while ridge
feature map computation took ~ 0.3 seconds. The time taken to match two minutiae
sets and generate the transformation parameters was ~ 0.02 seconds. Matching two
ridge feature maps took ~ 0.01 seconds. The total time for ﬁngerprint veriﬁcation
(one-to—one matching) was ~ 1.4 seconds. However, ﬁngerprint identiﬁcation (one-

to-many matching), involving 1, 000 templates, took only ~ 0.2 seconds, because of

45

8

 

888

Genuine Map! Rate ($6)
8

 

 

 

 

Figure 2.16: ROC showing the performances of the three matchers. The hybrid
matcher is observed to perform better than the minutiae matcher.

 

Figure 2.17: Two impressions of the same ﬁnger that have a high minutiae matching
score but a low ridge feature map matching score. The hybrid score results in a true
match.

46

 

Figure 2.18: Two impressions of the same ﬁnger that have a low minutiae matching
score but a high ridge feature map matching score. The hybrid score results in a true
match.

the ﬁltered image-cache.

2.7 Alignment Using Ridge Feature Maps

To circumvent the problem of unreliable landmark points (i.e., core and minutiae
points), we propose a technique that uses the extracted feature sets themselves to align
and match ﬁngerprint images. The feature set, in this case, is the ridge feature map
described in the earlier sections. A template ﬁngerprint image is ﬁltered using a set of
Gabor ﬁlters; a standard deviation map is next computed using each ﬁltered image;
the standard deviation map is then sampled at regular intervals to generate the ridge
feature map. Fingerprint veriﬁcation entails correlating the standard deviation map
of the query image with the ridge feature map of the template. A two-dimensional
correlation is performed thereby taking the spatial relationship between feature values

into account. A matching score is generated using the Euclidean distance metric

47

between corresponding elements in the ridge feature map of the template and the
standard deviation map of the query image. Based on the matching score, and a
pre—speciﬁed threshold, the query image is declared to match successfully (genuine)
or unsuccessfully (impostor) with the template. In the following sections we describe

the feature extraction and correlation process in more detail.

2.7.1 Constructing the Ridge Feature Map

The 240 x 240 input ﬁngerprint image, I, is convolved with the 8 Gabor ﬁlters, {Ga}.
Since the input image may be noisy, it is ﬁrst enhanced before applying the ﬁlters. A
segmentation algorithm is also applied on the input image to identify the foreground
and background regions. The foreground corresponds to those regions in the image
that have ridges and furrows, while the background represents those regions that do
not have this information (Figure 2.7(c)). Segmentation is useful during the matching
phase, when the distance between two feature maps is computed.

Let H indicate the 240 x 240 enhanced image. Let f (H ) denote the discrete
Fourier transform of H, and let f(Gg) indicate the discrete Fourier transform of the
Gabor ﬁlter having the spatial orientation 6 as described by Equation (2.2). Then

the Gabor ﬁltered image, V9, may be obtained as,

V0 = .7: ‘1 [7’ (H )7: (09)], (2-6)

where T” is the inverse Fourier transform. 8 ﬁltered images are obtained in this

way (Figure 2.9). Each V9 is used to construct a standard deviation image, So,

48

 

Figure 2.19: The standard deviation map, {39} of the ﬁltered images shown in Figure
2.9. Each image is 240 x 240.

where So(:r, y) represents the standard deviation of the pixel intensities in a 16 x 16
neighborhood of (:r, y) in V9. The standard deviation map, S = {So}, comprises of
8 images corresponding to the 8 ﬁltered images. Thus, the standard deviation map,
5', captures the variation in the ridge strength at various orientations (Figure 2.19).
Each standard deviation image, So, is then sampled at regular intervals (every 16‘”
pixel) in both the horizontal and vertical directions to obtain the ridge feature image,
R9 (Figure 2.20). The ridge feature map, R = {R9}, is composed of these 8 images.
The size of R9 (15 x 15) is lesser than that of $9 (240 x 240). We, therefore, have a

compact ﬁxed-length (15 X 15 x 8 = 1, SOD-valued) representation for the ﬁngerprint.

2.7.2 Fingerprint Matching Using Ridge Feature Maps

The process of ﬁngerprint matching involves comparing a query print with a set of

one or more template prints. Prior to the matching process, ridge feature maps are

49

 

(6)

Figure 2.20: The ridge feature map, {R9}, of the ﬁltered images shown in Figure 2.9.
Each image is 15 x 15.

extracted from all template images present in the database. When a query print, Q,
is presented to the system, it is matched against a template ridge map, RT = {R3}

as follows:

1. The query image is enhanced and the set of 8 Gabor ﬁlters is applied to the

enhanced image, resulting in 8 ﬁltered images.

2. The standard deviation map, SQ = {3?}, for the query image is constructed

using these ﬁltered images.

3. Each of the 8 template ridge feature images, R3, is ‘expanded’ to the size
of S? by interpolating with 0’s. Let the ridge feature map consisting of the

interpolated images be indicated by ST = {5?}.

4. To determine the alignment between SQ and ST, a 2D correlation of the two

maps is performed. Correlation involves multiplying corresponding entries in

50

the two maps at all possible translation offsets, and determining the sum. The
offset that results in the maximum sum is chosen to be the optimal alignment
between the two maps. Correlation is done in the frequency domain, and every
offset is appropriately weighted. The weighting is necessary to account for the
amount of overlap between the two maps. Let UTQ represent the unweighted
correlation matrix, and CTQ represent the weighted correlation matrix. Let

N x N be the size of a standard deviation image (N = 240). Then,

Um [{F‘msﬂhsz‘n} (2.7)

_ UTQ(CL‘,y)*N*N
CTQ(x3y) — (N-h1)(N—’wy),x

 

=1...N,y=1...N (2.8)

where,

N N N N
h: =I [(x + 3)m0dN] — —2—| and my =| [(y + —2—)m0dN] — 3|

The optimal offset (t1, ty) required to align SQ with ST is then determined as,

(t;,t;) = argrnaIx{CTQ(x,y)},x =1...N,y =1...N

51

t; if t; <

”I?

tg—N iftgz

t~3|2

t; if t; <
t, = (2.10)

t;—N ift;_>_

w|2

t~3|2

Equations (2.9) and (2.10) are used to decide if the offsets are negative or

positive.

5. At this optimal offset, the Euclidean distance between corresponding non-zero
foreground elements in {Sf} and {53} is computed. This distance is treated
as the matching score between the query print, Q and the template, T. Based
on the matching score, and the pre—speciﬁed threshold, the query image is said

to have matched successfully or unsuccessfully with the template.

The above procedure does not account for the rotational offset between the query
and the template feature maps. To account for rotational offsets, various rotated
versions of the template ridge feature map may be correlated with the query fea-
ture map, and the optimal alignment computed. Alternately, FFT-based registration

techniques (like the Fourier-Mellin transform) may be employed.

2.7 .3 Experimental Results

Our experiments on the MSU.VERIDICOM database decribed earlier indicate that

the proposed technique provides a fairly good alignment of ﬁngerprint image pairs.

52

 

 

Genuine Accept Rate (%)

 

 

 

 

 

 

 

60~ /
/ - - Minutiae+Ridge Feature Map
+ Ridge Feature Map
50.. —9— Minutiae
—— Equal Error Line
/
/
4o . m1.....-
10“ 10° 10‘
False Accept Rate (%)

Figure 2.21: ROC curves depicting matching performance of the correlation-based
technique.

We compare the proposed technique with a minutiae—based matcher by plotting the
Genuine Accept Rate against the False Accept Rate at various thresholds of the
matching score. As expected, the minutiaebased matcher demonstrates better per-
formance than the correlation-based matcher. However, fusing the two matchers (by
normalizing and adding the matching scores) results in an improved performance of
the ﬁngerprint veriﬁcation system. The ROC curves exhibiting these behaviors is
shown in Figure 2.21.

It must be mentioned that the transformation parameters computed using minu-
tiae points is more accurate than those computed using the ridge feature maps. How-
ever, in images where minutiae points cannot be reliably derived, the ridge feature
maps will prove to be a suitable alternative. This will be especially true in ﬁngerprint

images exhibiting cuts and bruises.

53

2.8 Summary

In this chapter a novel ﬁngerprint representation technique that uses ridge feature
maps has been presented. A hybrid ﬁngerprint matching technique that combines
minutiae information with the ridge feature map has also been described. Ex-
periments indicate that the hybrid technique performs much better than a purely
minutiae—based matching scheme. Further, the ridge feature maps have been used
to register (align) two ﬁngerprint images via a correlation process. The matching
performance of the hybrid system is tightly coupled with the accuracy of aligning the
ﬁngerprint images using minutiae points. The following areas of improvement can

also be studied:
1. New matching methods for comparing the ridge feature maps of two images.

2. Development of fusion architectures to improve performance of the hybrid

matcher.

3. Constructing the ridge feature maps using adaptive methods for optimal selec-

tion of the Gabor ﬁlters.

54

Chapter 3

Fingerprint Mosaicking

A ﬁngerprint-based veriﬁcation system has two distinct phases of operation: (i) the
enrollment phase, during which multiple impressions of a ﬁngerprint are acquired
and stored in the database as templates, and (ii) the authentication phase, where
the query image of a user is matched against the stored templates pertaining to
that user (Figure 3.1). The solid-state sensors that are being increasingly deployed
in commercial applications, however, sense only a limited portion of the ﬁngerprint
pattern present in the tip of the ﬁnger. The amount of information (e.g., number of
minutiae points) that can be extracted from such partial prints is substantially lower
compared to that which can be extracted from more elaborate prints sensed using an
optical sensor or even inked prints. As observed in Chapter 2, the average number
of minutiae points extracted from a Digital Biometrics optical sensor (500 x 500
image at 500 dpi) is 45 compared to 25 minutiae obtained from a Veridicom sensor
image (300 x 300 image at 500 dpi). This loss of information affects the matching
performance of the veriﬁcation system - the relatively small overlap between the

55

 

Template Images

a“.:"-".:.“ 5': .'~‘. ' "Q \\._ .
’»-.‘, '. s .. ‘__ -1 _ r.

.\
. .\ t3}
v.13“,

 

 

 

 

 

 

 

 

Figure 3.1: Fingerprint veriﬁcation: Multiple impressions of the same ﬁnger are stored
in the database as templates. The query image is matched against the components
of the template to verify the claimed identity.

template and query impressions results in fewer corresponding points and therefore,
results in higher false rejects and/ or higher false accepts (Figure 3.2).

To deal with this problem, we have developed a ﬁngerprint mosaicking scheme
that constructs a composite ﬁngerprint template using evidence accumulated from
multiple impressions. A composite template reduces storage, decreases matching
time and alleviates the quandary of selecting the “optimal” ﬁngerprint template from
a given set of impressions. In the proposed algorithm, two impressions (templates) of
a ﬁnger are initially aligned using the corresponding minutiae points. This alignment
is used by a modiﬁed version of the well-known iterative closest point algorithm (ICP)
to compute a transformation matrix that deﬁnes the spatial relationship between the
two impressions. The resulting transformation matrix is used in two ways: (a) the

two template images are stitched together to generate a composite image. Minutiae

56

     

(a) Template Image (b) Query Image

Figure 3.2: Two impressions (300 x 300) of the same ﬁnger acquired using the Veridi-
com sensor. The two impressions are observed to have very little overlap.

points are then detected in this composite image; (b) the minutia sets obtained from
each of the individual impressions are integrated to create a composite minutia set.
Our experiments show that a composite template improves the performance of the

ﬁngerprint matching system by ~ 4%.

3.1 Introduction

Typically, two types of representations are used to assess the similarity between a
pair of ﬁngerprints: (a) the global representation that examines the structure and
ﬂow of ridges over the entire print, and (b) the local representation, that exploits the
position and orientation of certain singular points, called minutiae, that are present in
the print (e.g., ridge endings and ridge bifurcations). By building a composite image,
the amount of information available for these two types of representation increases.
For example, the number of minutiae points used to represent a ﬁngerprint may
increase when minutiae information from two impressions of a. ﬁnger are integrated.

Similarly, the amount of ridge information available for global representation may

57

increase as well. The challenge lies in accurately registering multiple impressions of
the ﬁnger in order to extract more information. An accurate registration would aid
in efficient mosaicking of the impressions.

Registering ﬁngerprint images, however, is a difficult problem for the following
two reasons: (a) The ridges in a ﬁngerprint image may have non-linear distortions
due to the effect of pressing a convex elastic surface (the ﬁnger) on a ﬂat surface
(the sensor). Moreover, these distortions may be present only in certain regions of
the sensed image due to the non—uniform pressure applied by the subject. (b) The
presence of dirt deposits on the sensor or the ﬁnger can result in noisy or occluded
images. It is rather difﬁcult to register pairs of ﬁngerprint images that are distorted
differently or affected by noise.

Ratha et al. [42] have deveIOped a mosaicking scheme to integrate multiple snap-
shots of a ﬁngerprint. The multiple snapshots are acquired as the user rolls the ﬁnger
on the surface of the sensor and, therefore, a speciﬁc temporal order is imposed on
the image frames when constructing the composite image. The authors examine 5
composition schemes that stack the grayscale images together and construct a com-
posite mosaicked image, by associating a conﬁdence value with every pixel. They
evaluate the efficacy of these schemes by observing the area and quality (in terms
of the number of valid minutiae points detected) of the composite image. Their
experiments indicate that the mosaicked image has a substantially larger area and,
consequently, more number of minutiae points are detected. It has to be noted that in
their technique, successive impressions will have spatial proximity. But,‘in the case

of dab ﬁngerprint impressions obtained at different time instances, the parametric

58

 

Figure 3.3: Rolled versus dab prints. (a) — (d): A sequence of 4 rolled ﬁngerprint
impressions obtained using the Digital Biometric sensor. Successive image frames are
known to have spatial proximity. (e) - (h): Four impressions of a ﬁnger obtained at
different time instances using a Veridicom sensor. The transformation between the
impressions is not known.

transformation between impressions is not known. This complicates the problem of
mosaicking ﬁngerprint images captured at different time instances.

We approach the problem of ﬁngerprint mosaicking by treating the acquired ﬁn-
gerprint images as 3D surfaces. The rationale behind this is the observation that the
imaging process involves pressing the 3D surface of the ﬁngertip on a 2D ﬂat surface.
We assume that the resulting 2D intensity image indicates the pressure with which a
user holds the ﬁnger against the surface of the sensor. Therefore, the intensity images
may be treated as 3D range (surface) images.

In order to generate the transformation matrix deﬁning the spatial relationship
between two impressions, we employ the iterative closest point ( I C'P) algorithm that
registers two 3D surface images when sufﬁcient number of corresponding points are

available between the two surfaces. The correspondences are used to compute an

59

initial approximate alignment between the two surfaces; the ICP algorithm then at-
tempts to ﬁnd an optimal alignment such that the sum of distances between control
points in one surface and the corresponding tangential planes in the other is mini-

mized. Details of the algorithm is provided in the following section.

3.2 Fingerprint Image Registration

The problem of registering multiple 3D surfaces has received much attention in the
literature (see [43, 44] and the references therein). A typical application of registration
is 3D object model construction where multiple views of an object are integrated [45].
However, a variety of other applications exist for surface registration [46], including
medical image analysis [47], terrain matching [48], etc.

A 3D surface registration algorithm seeks to ﬁnd the best transformation 7 that
relates two entities P and Q whose range images1 are given by Rp and Rq, respec-
tively. Thus the goal of a registration algorithm is to ﬁnd T such that the following

objective function, D(Rp, RQ), is minimized:

D<=RP.RQ> Z IITp— f(p (3.1)

PER?

where

fzpaQIVPERPyﬂpleij-

The transformation, T, that is used to Optimally align entities P and Q, usually

 

1The terms range image and 3D surface are used interchangeably in this chapter. Typically, a
3D surface is constructed from a range image

60

depends upon the distortions present in the range images. Thus, T may be rigid,
afﬁne, polynomial, or elastic. For our application we assume T to be a rigid trans-

formation. T can, therefore, be expressed as follows in homogeneous coordinates:

" "l
cosacosﬁ cosasinﬁsin7—sinac037 cosasinﬁcos7+sinasin7 t,c

sin 0 cos 6 sin a sin 6 sin 7 + cos 0 cos 7 sin a sin ,8 cos 7 — cos a sin 7 ty
— sin 6 cos 6 sin 7 cos 6 cos 7 tz

0 0 0

 

 

(3.2)
Here a, ﬂ and 7 are the rotation angles about the :17, y and z axes, respectively, and
t,, t,, and t, are the translation components along the three axes. Thus the matrix

T has 6 independent parameters.

In reality, the function f is not known and, therefore, the objective function in
equation (3.1) has to be replaced by an evaluation function that assumes knowledge
of a set of corresponding points in Rp and RQ. Therefore, given a set of N pairs
of corresponding points, (p,,q,-), p, E Rp, q,-'6 RQ and z' = 1...N, one can try to

minimize the evaluation function e(Rp, RQ):

N
am». HQ) = 2 “7p.- — (1.112. (3.3)
i=1

If the correspondences are not known, then it is not possible to register the images.
Corresponding points are typically selected by extracting higher level features (e.g.,

edges, corners, texture, points of locally maximum curvature, etc.) from the two

61

surfaces, and looking for similarities between the two sets of extracted features.

If the corresponding points are known, then the evaluation function shown in
Equation (3.3) can be minimized by simply searching for the global minimum in
the 6—dimensional parametric space using an iterative procedure. Such a procedure,
however, does not guarantee convergence to a global minimum. To circumvent this
problem, Chen and Medioni [49] assume that an initial approximate transformation,
’13, is known. A good starting approximation assures that the global minimum is

reached quickly and surely.

Equation (3.3) imposes a strict correspondence between points p,- and q,-. If the
pair of points selected are incompatible (i.e., they are located on different surfaces in
the two images), then an iterative procedure may converge very slowly. In order to
deal with this issue, the ICP algorithm is used. This algorithm tries to minimize the
distances between points in one image to geometric entities (as opposed to points)
in the other. Chen and Medioni [49] attempt to minimize the distance of a point on
one surface, to the tangential plane of the corresponding point in the other surface.

Thus, they minimize

N
ekuzp, HQ) = Zara. Sf). (34)

where, d, is the distance from the point to the plane, and Sj is the tangential
plane corresponding to q,- in surface RQ. Once an initial alignment is provided, the
control points are automatically chosen by examining homogeneous regions in the two

images.

62

An iterative procedure is adepted to converge to the global minimum (and hence
the superscript k in the above equation). Since an approximate initial transformation
matrix is known, convergence to the global minimum is assured, and since there is a
relaxation in the condition of strict correspondence between points (equation (3.4)),

convergence is faster.

3.3 Fingerprint Mosaicking

We pose the ﬁngerprint mosaicking problem as a 3D surface registration problem that
can be solved using a modiﬁed ICP algorithm. The initial alignment of ﬁngerprint im-
ages I p and IQ is obtained by extracting minutiae points from each individual image,
and then comparing the two sets of minutiae points using an elastic point matching
algorithm [50]. The comparison proceeds by ﬁrst selecting a reference minutiae pair
(one from each image), and then determining the number of corresponding minutiae
pairs using the remaining sets of points in both the images. The reference pair that
results in the maximum number of corresponding pairs is chosen. Let (p0, go) be
the reference minutiae pair and let (p1,q1),. . . (pN,qN) be the other corresponding
minutiae pairs. Here, p.- = (pmupynpzimgi) and q.- = (qx,,qy,,Qz.-,<19,), where (55,31)
are the spatial coordinates of the minutiae points, z is the intensity of the image at
(x, y) and 0 is the minutiae orientation. The initial transformation, T 0, is computed
using Horn’s method of unit quaternions [51] that operates on the (3:, y, .2) values. In
this technique, the translation parameters in Equation (3.2) are computed using the

centroid of the point sets (pxwpyi, pa.) and (q1,,qy,,qz,), and the rotation components

63

are computed using the cross-covariance matrix between the centroid-adjusted pairs

of points.

3.3.1 Preprocessing the Fingerprint Image

Since the ICP algorithm uses distances from points to planes, it is very sensitive to
rapid and abrupt changes in surface direction. Therefore, the ﬁngerprint images are
ﬁrst median ﬁltered using a 3 x 3 mask. This operation removes any undesirable “salt-
and-pepper” noise that may be present in the valleys (furrows) of the ﬁngerprint image
(which may contribute to abrupt changes in the range image). The intensity values
of the median ﬁltered image are then scaled to a narrow range of values ([10,20]) to
ensure a fairly smooth change in surface direction in the corresponding range image

of the ﬁngerprints (Figure 3.4(b)).

3.3.2 Fingerprint Segmentation

The purpose of segmentation is to separate the foreground and background regions in
the given intensity image. The foreground corresponds to those regions in the image
that have valid ﬁngerprint information (i.e., the ridges and valleys of the ﬁngerprint),
while the background represents those regions that do not have this information. It is
useful to mask out the background of the images before registering the images using
the ICP algorithm. This prevents the ICP algorithm from choosing control points in
the background region (which is possible due to the homogeneity in intensity in these

regions) and then attempting to align the images using these points.

64

The algorithm to segment an image is as follows: (a) The preprocessed grayscale
ﬁngerprint image is converted to a binary image by examining the histogram of in-
tensities and choosing a threshold. (b) An edge detection algorithm is applied to the
binary image to get the outline of ridges. (c) Graham’s convex hull algorithm [35] is

used to generate a polygon that segments the ﬁngerprint image (Figure 3.4(c)).

3.3.3 Fingerprint as a Range Image

The intensity values are directly used as range values. Therefore, the intensity value
of the image at the planar coordinate (:r,y) is treated as the range value at that
location. We now have two range images Rp and RQ, that are obtained from the
corresponding intensity images I p and 149, respectively. Figure 3.4(d) illustrates this

mapping for a portion of the image in 3.4(c).

3.3.4 Registering Fingerprint Images

The two range images, Rp and Rq, are now subject to the iterations of the ICP
algorithm. At each iteration k, the transformation T k that minimizes EC in Equation
(3.4) is chosen. The process is said to have converged when,

lEk—Ek~ll<€
N 1

 

where c is some threshold, 6 z 0.

The ﬁnal transformation matrix, Tsduti‘m, is used in the following two ways.
1. It is used to integrate the two individual images and create a composite image

65

  
 

    

file. ' .
A

  

Figure 3.4: Mapping an intensity image to a range image. (a) The original intensity
image. (b) The intensity image after median ﬁltering and scaling. (c) The segmented
intensity image. (d) The range image corresponding to the boxed region (rotated by
~ 90°) in (c).

66

 

Average Size Average Number of Minutiae
Input Image 300 x 300 22
Mosaicked Image 336 x 332 30

 

 

 

 

 

 

Table 3.1: Increase in average image size and average number of detected minutiae
as a result of mosaicking.

whose spatial extent is generally larger than the individual images. Minutiae

points are then extracted from this larger image.

2. The minutiae sets from the individual images are augmented using T’Oluti‘m.

Mosaicked Images

The given intensity images I p and IQ are integrated into a new image I R. Since
T ”mm" transforms I p into Iq, we compute the new spatial coordinates of every pixel
I p in I R. We extract a new minutiae set (M 3,) from this image using the algorithm
described in [50] (see ﬁgure 3.5(e)). Note that the spatial extent of the composite
image is generally larger than the individual images. Figure 3.6 shows the result of
mosaicking on six different ﬁngerprint pairs. Table 3.1 lists the increase in image size
and the number of detected minutiae in the composite image.

The mosaicking procedure may sometimes result in poorly aligned images. This
can happen when: (i) the segmentation of either of the images is erroneous, (ii) the
images are noisy, or (iii) there are very few (< 5) corresponding points available to

provide a valid initial alignment (Figure 3.7.

67

 

Figure 3.5: Composite template construction: (a) First image after segmentation.
(b) Second image after segmentation. (c) Initial alignment. ((1) Final alignment. (e)
Minutiae extracted from mosaicked images. (f) Composite minutiae set obtained by
augmenting individual minutiae sets.

68

 

(e) (0

Figure 3.6: The result of mosaicking six pairs of ﬁngerprint impressions. The spatial
extent of the mosaicked image is observed to be larger than that of the component
images.

69

 

(a) (b)

Figure 3.7: Examples of poorly mosaicked image pairs.
Integrating Images

The intensity images I p and [Q are integrated into a new image I 3. Since Zena-0,,
transforms I p into Iq, we compute the new spatial coordinate of every pixel I p in I R.
We extract a new minutiae set (M R, from this composite image using the algorithm

described in [50] (see ﬁgure 3.5).

Augmented Minutiae Sets

Let Mp refer to the minutiae set extracted from I p and MQ refer to the minutiae set
extracted from IQ. The composed minutiae set M3, is obtained by computing the
(1:, y, 0) parameter of each minutia in the composite image. The new (:c, y) coordinates
(i.e., the spatial coordinates) of the minutiae points (of the ﬁrst image) is determined
by simply multiplying the old coordinates with the transformation matrix (Figure

3.5f). 2 The minutiae orientation, 0, is not recomputed.

 

2Since the ﬁrst image is transformed to align with the second, this computation has to be done
for the ﬁrst image only.

70

3.4 Experimental Results

We have conducted the following experiments to validate the effectiveness of the
transformation and integration described in section 3.3.4. We have two different
techniques to obtain a composite minutiae set. The two minutiae sets are indicated
by M R, (obtained by extracting minutiae from the composite image), and M 3,
(obtained by integrating individual minutiae sets). We treat these sets as template

minutiae sets against which a query minutiae set can be matched.

Fingerprint images of 640 different ﬁngers, corresponding to 160 different subjects,
were acquired using the Veridicom sensor‘as described in the previous chapter. 4
different impressions of each of these ﬁngers were obtained over two different sessions
separated by a period of six weeks (2 impressions in each session). The two impressions
acquired at the same session were used to construct the template minutiae set of a
ﬁnger, while the other two impressions were used as query images during the test phase
of the experiment. Thus, 640 pairs of images were used to construct the minutiae

templates M R, and M 32, and the rest (1280) were used as query images.

Given a minutiae set Mu (of the query image Ia), and the template minutiae sets
Mp, MQ, M R, and M 32, we perform the following comparisons: (i) My with Mp,
(ii)Mu with Mq, (iii) Mu with M3,, and (iv) My with M 3,. Thus we get a set of
four scores corresponding to these comparisons. The ROC curves depicting the per-
formance of these 4 different matchings are shown in ﬁgure 3.8. It is clear from these
graphs that a composite template image results in improved matching performance.

We further observe that a better matching performance is obtained by using MR,

71

 

100 s e s

 

 

 

95 *- 1
Augmented Minutiae Set (Ma )
.3 9°" ’ i
E
a .
Com rte lma M .
r; 85 _ DOS ge( a!) -_‘ ,
m 80 -
.E are '
g I ewe—~01 ‘ ‘
<9 75 1,___,__,,_ ‘°‘*"“
Impression 2 (Mo)
70 . Impression 1 (MP) 4
65 . - . . ._ A . 4
10° 10'
False Awept Rate(%)

Figure 3.8: The ROC curves indicating improvement in matching performance after
mosaicking templates. Utilizing the minutiae points that are extracted from the
composite ﬁngerprint image (M R1) results in the best matching performance.

rather than M 132' This may be due to incorrect minutiae orientation in M32. Note
that when augmenting the two minutiae sets, M p and Mg, no systematic technique
is used to adjust the minutiae orientation in the composite minutiae template, M 122-

' While the use of M 3, results in better matching performance, generating M 3,
introduces several spurious minutiae that have to be carefully discarded. The spurious
minutiae are a consequence of misalignment of the ridges present in the two individual

impressions that are being integrated.

3.5 Summary

We have described a ﬁngerprint template construction technique that integrates infor-

mation available in two different impressions of the same ﬁnger. The method makes

72

use of corresponding minutiae points to establish an initial approximate alignment,
and a modiﬁed ICP algorithm to register the two impressions. The transformation
matrix generated by the ICP algorithm is used to construct composite information
from the individual impressions. Our experiments indicate that mosaicking the im-
ages together and then extracting the (template) minutiae set results in a better
matching performance.

The mosaicking scheme suggested here has been used to register two impressions
of a ﬁnger. By repeated application of this procedure several impressions of a ﬁnger
(> 2) may be integrated. Fingerprint mosaicking elegantly addresses the problem of
partial ﬁngerprint images and is, therefore, an essential component of a ﬁngerprint

recognition system.

73

Chapter 4

A Deformable Model for

Fingerprint Matching

Fingerprint images are typically acquired using a contact—based sensor wherein a user
places1 her ﬁnger on the surface of the sensor. The elastic nature of the human
skin, coupled with the non-uniform pressure applied by the ﬁnger on the sensor,
result in ﬁngerprint images whose ridges exhibit non-linear distortions. For reliable
matching, these non-linear distortion effects must be accounted for prior to comparing
two ﬁngerprint images. Models based on afﬁne transformations have been used to
offset the effects of distortion, but they invariably lead to unsatisfactory matching
results since the distortions are basically elastic in nature (Figure 4.1).

Given several template impressions of a ﬁnger, we estimate the “average” defor-

mation for each template image corresponding to that ﬁnger based on the thin plate

 

1A live-scan ﬁngerprint is usually acquired using the dab method, in which the ﬁnger is placed
on the surface of the sensor without rolling. (It is possible to capture a rolled live-scan ﬁngerprint,
although an elaborate scanner arrangement may be necessary in this case).

74

 

Figure 4.1: Aligning two impressions of the same ﬁnger using an affine transformation.
Due to non—linear distortions, the alignment is not accurate in some regions. Only
ﬁngerprint ridges are shown for clarity [2].

spline (TPS) model. The estimated average deformation is then utilized to align the
minutiae points between the template and query images during the matching stage.
It is shown that the use of an average deformation model leads to a better alignment
between the two sets of points as opposed to a rigid transformation. The average
deformation is computed using two types of landmark points: minutiae points and
ridge points. Further, an index of deformation is proposed for choosing the best de-
formation model arising from a set of template impressions corresponding to a ﬁnger.
Experimental data consists of 1600 ﬁngerprints corresponding to 50 different ﬁngers
collected over a period of 2 weeks. It is shown that the average deformation model
leads to an improvement in the alignment between impressions originating from the

same ﬁnger.

75

4. 1 Introduction

As indicated earlier, the problem of automatic ﬁngerprint matching involves determin-
ing a measure of similarity between two ﬁngerprint impressions by comparing their
ridge structure and/ or the spatial distribution of the minutiae points [24, 23, 18, 53].
The image acquisition process, however, introduces non-linear distortions in the ridge
structure and, consequently, in the spatial location of minutiae points, thereby con-
founding the matching process. This distortion is a function of several parameters
including the orientation of the sensor with respect to the ﬁnger, the amount of pres-
sure applied by the subject, the disposition of the subject (sitting or standing), the
motion of the ﬁnger prior to its placement on the sensor, the moisture content of
the skin (dry, oily or wet), the elasticity of the skin, etc. Therefore, the distortions
observed in a ﬁngerprint vary from one acquisition to the next. For reliable matching,
these non-linear distortions must be accounted for prior to comparing two ﬁngerprint
images. Deformation models based on affine transformations invariably lead to unsat-
isfactory matching results since the distortions are basically elastic in nature (Figure

4.1).

To deal with the problem of non-linear distortion in ﬁngerprint images, four types
of approaches have been discussed in the literature. The ﬁrst approach accounts for
distortion in the image acquisition stage by capturing the least distorted print from the
user. Ratha et a1. [54] describe a system which does not accept an input image if the
user applies excessive force on the sensor, thereby minimizing the effect of distortions

on the acquired image. The system operates by measuring the forces and torques

76

applied on the sensor. Dorai et a1. [55] observe a video sequence of the ﬁngertip as it
interacts with the sensor and measure the distortion in successive frames. When
excessive distortion is observed, the system requests the user to provide another
ﬁngerprint. These systems require specialized hardware and the ability to perform
extensive computations in real-time. As a result, they do not offer a practical solution
to ﬁngerprint deformation for real-time and embedded ﬁngerprint applications.

In the second approach, the distortion is estimated during the matching stage.
Thebaud [56] uses a gradient descent technique to compute local warps when com-
paring two ﬁngerprints. The ﬁngerprint correlation score is used as the objective
function. Besides being time consuming, this technique potentially results in a higher
False Accept Rate (FAR) since it performs local warping to force a match between the
two images. Kovacs-Vajna [18] uses minutiae triplets to compare two minutiae sets.
By not using the entire minutiae pattern at once, the cumulative effect of distortion
is avoided. Bazen and Gerez [57] use a thin-plate spline (TPS) model to account for
non-linear distortions while comparing two minutiae sets.

In the third approach, the distortion is removed before the matching stage. Senior
and Bolle [58] have developed a model which assumes that ridges in a ﬁngerprint
are constantly spaced, and that deviations from this model indicate the presence of
elastic distortions. They apply local warps in regions exhibiting such deviations to
make the local ridge distances nearly equal the average inter-ridge spacing. Their
experimental results show a signiﬁcant improvement in genuine matching scores (i.e.,
the matching score when comparing two impressions of the same ﬁnger), as indicated

by the t-statistic. However, their assumption that inter-ridge spacing in a ﬁngerprint

77

 

Figure 4.2: Alignment of two impressions of the same ﬁnger using afﬁne transforma-
tion. (a) and (b) are the gray scale images; (c) and (d) are the thinned (skeletonized)
images of (a) and (b), respectively; and (e) shows the alignment based on the thinned
images. Ridge lines do not align in (e).

78

is constantly spaced is not always valid. Watson et a1. [59] construct distortion
tolerant ﬁlters for each (template) ﬁngerprint before performing a correlation type of
matching. Their experiments show that applying the ﬁlter before matching improves
the performance.

The fourth approach is more suited for introducing distortions in synthetic ﬁn-
gerprints. Cappelli et a1. [60] have attempted to model the distortions that could
occur in a ﬁngerprint image by considering three concentric regions in a ﬁngerprint;
the inner and outer regions are assumed to have no distortions although ridges in the
outer region can be translated and rotated with respect to the ridges in the inner
region; the region in between is assumed to undergo non-linear distortions in order to
accommodate the transition of ridges from the inner to the outer region. The authors,
however, do not use this model to perform ﬁngerprint matching. Rather, they use it
to synthesize multiple impressions of the same ﬁnger [61].

Several difﬁculties arise when we try to ascertain the extent of non-linear distor-
tion in ﬁngerprint impressions. The distortion present in impressions of a ﬁnger is not
known in advance, thereby making normalization to a true template as in [58] impos-
sible. A reference template ﬁngerprint having no distortion effects is never available
given multiple impressions of a ﬁnger; in other words, distortion effects should ap-
propriately be measured in relative, rather than in absolute, terms between pairs of
impressions. Bazen and Gerez [57] report the estimation of relative distortions be-
tween pairs of impressions based on the minutiae point pattern correspondence (see
Figure 4.3). In this paper, we present an approach of estimating relative distortions

based on ridge curve correspondence (see Figure 4.4). Modelling distortion effects

79

based on ridge curve correspondence offers several advantages over minutiae point pat-
tern matching, consequently leading to improved authentication performance. Unlike
minutiae points, which can be sparsely distributed in regions of a ﬁngerprint image,
ridge curves are spread all over the image domain resulting in a more reliable estimate
of the distortion. The spatial continuity of ridge curves enables sampling of a large
number of points on the ridges for establishing correspondences, including points in
the vicinity of undetected minutiae points. Obtaining correspondences for undetected
minutiae points is not possible when correspondences are based solely on (detected)
minutiae point patterns. Also, in some poor quality images, minutiae information
cannot be reliably extracted and thus, should not be used to construct a ﬁngerprint
distortion model. For the above reasons, ridge curve-based warping techniques result
in a more robust and reliable estimate of the distortion in ﬁngerprint impressions, and
consequently, incorporating this distortion model in the authentication stage yields
superior matching performance.

Most of the earlier techniques deal with the problem of non-linear distortion on
a case by case basis, i.e., for every pair of ﬁngerprint impressions (or for every ﬁn-
gerprint impression), the distortion removal technique, via a deformation model, is
applied and a matching score generated. No attempt has been made to develop a
ﬁnger-speciﬁc deformation model that can be computed offline and later used for
matching. The main advantage of such a scheme is that once a ﬁnger-speciﬁc model
has been computed and stored along with the template, re—computation of the model
is not necessary during the matching stage. When multiple impressions of a user’s

ﬁngerprint are available, a technique is proposed for computing the average defor-

80

mation model in the training stage using the thin plate spline (TPS) warping model
based on ridge curve correspondence. The average deformation model corresponding
to each ﬁngerprint impression is an overall description of the relative distortions of
the remaining impressions with that impression (called the baseline impression). In
other words, we describe distortion effects by (i) a baseline impression and (ii) the
average deformation model with respect to the baseline impression. An optimal base-
line impression with the most consistent distortions (that is, distortions that deviate
the least from the average) is selected by means of an index of deformation. The
optimal baseline impression is not an impression with no distortion effects; it is the
impression relative to which other impressions of the same ﬁnger have the most con-
sistent (least variable) distortions. We show that by removing distortion effects using
the optimal baseline impressions (and their average deformation models), superior

matching performance is obtained in the authentication stage.

4.2 General Warping Methods

Warping methods can be used to obtain global deformation models for image registra-
tion. Applications of warping techniques abound in the statistical, medical imaging
and computer vision literature. There have been a variety of image registration tech-
niques motivated from different principles; examples include warping by elastic de-
formations [62, 63], optical or ﬂuid flow [64, 65, 66], diffusion processes [67], Bayesian
prior distributions [68, 69], and thin-plate splines (TPS) [70, 71, 72]. Only recently

have warping techniques based on deformation models been used to model distortions

81

 

 

 

 

 

 

 

 

ﬁnger.

fall,

Figure 4.4: An example of rid e cu e corres ondences between two i

 

in ﬁngerprint images for the purpose of matching [73, 57]. Warping enables the distor-
tions to be estimated and subsequently removed prior to matching. It is shown in [57]
that this procedure results in superior matching performance compared to algorithms
which either do not model distortions or model them using rigid transformations.
Distortion models based on TPS were used in [73] and [57].

Earlier work in modelling the non-linear distortion in ﬁngerprint images used only
the spatial distribution of the minutiae points [73, 57]. One disadvantage of using
the minutiae point pattern for estimating the non-linear deformation is that minutiae
points may be sparse in some areas of the ﬁngerprint. As a result, the estimated
deformation model exhibits high variability in such regions leading to sub-optimal
deformation models. A more fundamental and rich feature of ﬁngerprint images
is their ridge structure. A skeletonized version of a ﬁngerprint image, known as
the thinned image, can be used to extract ridge curve information (see Figure 4.2).
Obtaining the deformation model based on aligning the ridge curves offers several
advantages. Firstly, ridge lines are distributed over the entire ﬁngerprint image and
thus, almore reliable deformation model can be obtained. Secondly, the likelihood
of incorrectly corresponding two ridge curves is much less than corresponding two
minutiae points, due to the richer intrinsic information available in curves compared
to points. Consequently, the deformation model based on ridge curves yields better
matching performance compared to minutiae points as is shown in this paper.

When multiple impressions of a ﬁnger are available, it is observed that the non-
linear distortion present in them vary signiﬁcantly. Further, these distortions are

different for different pairings of the impressions (Figure 4.5). Thus, we address the

83

 

(d) (6)

Figure 4.5: Non-linear deformations (with rotation and translation parameters re
moved) associated with two pairings involving the same template: (a) Template im-
age; (b) and (0) Query images; ((1) and (e) Non—linear deformation of (a) into (b) and
(c), respectively.

84

following two problems: (i) obtain a deformation model based on ridge curve corre-
spondence that can be incorporated in the matching stage, and (ii) given multiple
deformation models for a ﬁnger (each model corresponds to one impression of the
ﬁnger), select the optimal model that gives the most consistent distortion effects
measured from a baseline impression. In this paper, we develop an average defor-
mation model given multiple impressions of a single ﬁnger together with an estimate
of its variability based on ridge curve correspondences. An index of deformation
is suggested as a means of selecting a baseline impression with an associated aver-
age deformation model with the least variability. The average deformation model is
incorporated in the matching stage when [a query ﬁngerprint is compared against a
template ﬁngerprint. Experimental results indicate that better matching performance
is achieved by incorporating deformation models (and average deformation models)

based on ridge curves as opposed to using only minutiae points.

4.3 The Fingerprint Warping Model

Let Io(:r,y) and Il(:r,y) denote two ﬁngerprint imprmsions, where (1:,y) E S for a
domain S C R2. Our convention is to refer to Io and I 1 as the template and query
images, respectively. A warping of 10 to 11 is deﬁned as the function F : S —-> S such

that

Io(F($, 31)) = Many) (4-1)

for (3:, y) E S. The function F is called the warping function which takes Io to I 1. In

our application we register the two impressions Io and [1 by matching corresponding

85

ridge curves. Thus, in equation (4.1), the warping function, F : S —> S, registers two
sets of ridge curves derived from 10 and I]. Let uk E uk(t) = (uk1(t), uk2(t))T, t E Ck,
denote a parameterized ridge curve in 10 for k = 1,2, . . . ,n, and let 1);, E vk(t) =
(vk1(t), 'Uk2(t))T, t 6 D, and k = 1, 2, . . . ,n, denote the corresponding parameterized
ridge curves in I 1; here, n is the total number of corresponding curves. The two sets of
ridge curves, one set in Io and the other in I 1, with known correspondences is denoted
by the pair (U, V) where U = (711,712, . . . ,u,,)T and V = (v1,v2, . . . ,vn)T. We assume
that each correspondence pair is aligned as close as possible using rigid transformation
prior to non-linear warping. This can be achieved using the Procrustes analysis (see
[74]) after pairs of corresponding points are obtained using the methodology outlined
below. For n pairs of ridge curve correspondences, a warping function, F, that warps

U to V, subject to perfect alignment, is given by the conditions

F(uk) = 'Uk (4.2)

fork=1,2,...,n.

4.3.1 Establishing Ridge Curve Correspondences

Given a pair of grayscale ﬁngerprint images, 10 and I], we obtain their thinned ver-
sions, R0 and R1, using the algorithm described in [1]. A thinned image is a binary
image (see Figures 4.2 (c) and (d)) with grayscale values of 0 (indicating ridges) and
255 (indicating valleys). Each thinned image can be thought of as a collection of ridge

curves. In order to develop ridge curve correspondences, we proceed as follows:

86

1. Minutiae points are extracted from 10 and 11 using the algorithm described in [1].
Let M0 = (mo,1,m0,2,...,mo,Ko) and M1 = (m1,1,m1,2,...,m1,K,) denote the
two minutiae sets of cardinalities K o and K1, respectively. Here, each minutiae
point mm- is characterized by its location in the image, the orientation of the

associated ridge, and the grayscale intensity of pixels in its vicinity.

2. Minutiae correspondences between M0 and N11 is obtained using the elastic
string matching technique described in [1]. The output of the matcher is a
similarity score in the range [0,1000] and a set of correspondences of the form
C = {(mo,aj,m1,bj) : j = 1,2,...,K} where K S min{Ko,K1}, and the (as
(bjs) are all distinct. Figure 4.3 shows an example of the minutiae point pattern

correspondence for two impressions of a ﬁnger.

3. Once the correspondence between Mo and M1 is established, the ridge curves
associated with these minutiae points are extracted from R0 and R1 using a
simple ridge tracing technique. A minutiae point that is a ridge ending has
one ridge curve associated with it while a ridge bifurcation has three associated
ridges. In the case of a ridge ending, the ridge curve correspondence between
the two images can be easily established since each minutiae point has only one
associated ridge curve. However, in the case of a ridge bifurcation, the problem
of establishing ridge curve correspondences is non-trivial due to the presence
of multiple ridge curves for each minutiae point; each of the three component
ridge curves of one minutiae point can potentially match with any component

of the other impression.

87

 

Figure 4.6: Vector representation of ridge bifurcation used to establish correspon-
dences between component ridge curves. 0 marks the bifurcation points in corre-
spondence, and X marks the points on the ridges at Euclidean distance d from 0.

To resolve this ambiguity, each ridge curve corresponding to the minutiae point
in 10 (11) is represented as a directional vector rJ- (31-), j = 1,2,3, based on two
points on the ridge curve: the minutiae point and the d—th point (d = 20) on
the ridge from the minutiae (see Figure 4.6). We deﬁne 0,3,, (’ij) to be the
angle that rJ- (5,) makes with rk (sh), for k 75 3'. We ﬁnd the vector r,- (3,) for
which the angles {OJ-jg, k 76 j} ({7j,k, k 7é j}) are both obtuse. This establishes
the ﬁrst ridge curve correspondence, say, r1 ~ 31, without loss of generality.
We then compute the cross products or = r2 x r3 and c, = 32 x 33. We assign
the correspondence r2 ~ 82 and r3 ~ .93 if c, and c, are of the same sign, and
r2 ~ 33 and r3 ~ 32, otherwise. Figure 4.4 shows an example of ridge curve

correspondence for a pair of impressions of a ﬁnger.

4.3.2 Sampling Ridge Curves

Having determined the corresponding ridge curves, we next establish a correspondence
between points on these curves by sampling every q—th point (q = 20) on each of the
ridge curves. For the correspondence pair (U, V), we have me E uk(t) and 1);, E vk(t)

for k = 1,2, . . . ,n. The sampling of the k-th corresponding ridge curves, say at

88

points t1, t2, . . . ,tgk, yields 9;, pairings of the form (Uk(tj),vk(tj)) forj = 1,2, . . . ,gk.
Thus, we have a total of N = 22:, 9;, points in establishing the correspondence.
We denote this set of corresponding points by U = (ngo,r1;,...,r1;,,)7 and V =
(1;;0,§;, . . . , £307). We use TPS to estimate the non-linear deformation F based
on these points. TPS represents a natural parametric generalization from rigid to
mild non-rigid deformations. The deformation model for TPS is given in terms of the

warping function F(u), with
F(u) = c + A - u + WTs(u), (4.3)

where u E S, c is a 2 x 1 translation vector, A is a 2 X 2 affine matrix, WT is a N x 2
coefﬁcient matrix, 3(a) = (0(11 -— u’i), 0(u -— 11;), . . . , 0(u — ujv))T where

IIUI|210 (Hall), HUI >0
0(a) = g I (4.4)

0. Hall = 0-
In equation (4.3), there are 6 and 2N parameters corresponding to the rigid and
non-rigid parts of the deformation model, respectively, resulting in a total of 2N + 6

parameters to be estimated. The restrictions

F(u;) = v}, (4.5)
j = 1, 2, . . . , N provide 2N constraints. For the parameters to be uniquely estimated,

we further assume that W satisﬁes the two conditions (i) IEW = 0 and (ii) U I W = 0,

89

where IN is the vector of ones of length N. Thus, the parameters of the TPS model

can be obtained from the matrix equation

 

 

 

 

 

 

- . - - r .
H 11,, u W v
1% o 0 cT = 0 . (4-6)
W 0 0 AT [0

where H is the N X N matrix with entries hij = 0(u: — 11;).

The matrix equation in (4.6) gives rise to a TPS model that minimizes the bending
energy subject to the perfect alignment constraints in (4.5). A more robust TPS model
can be obtained by relaxing the constraints in equation (4.5), and instead determining

the function F which minimizes the expression

2(1); — 113))T(;v —F(u; ))+AJ(F ), (4.7)

where

:1. {re—:2”) <—>

(ng’yl) ] dandy (4.8)

represents the bending energy associated with F = (F1, F2)T, F,- is the 3"" component
of F, and A > 0. The case )1 = 0 gives rise to the TPS model described by equation
(4.6). For general /\ > 0, the parameters of the resulting TPS model can be obtained

using equation (4.6) with H replaced by H + AIN, where I N is the N x N Identity

90

matrix.

4.4 Average Deformation Model

Suppose we have L impressions of a ﬁnger, T1,T2, . . . ,TL. Each impression, T,, can
be paired with the remaining impressions, T], j 75 i, to create L — 1 pairs of the
form (T,,T,). For the pair (511,73), we obtain a non-linear transformation Fij by
employing the technique described in section 4.3. Note that Fij transforms every
pixel in the template ﬁngerprint, T,, to a new location. Thus, we can compute the

average deformation of each pixel u in T} as

not) = L—iT 3}; FM). (4.9)

There will be L average deformation models corresponding to the L impressions

of the ﬁnger. The average deformation is the typical deformation that arises when we
compare one ﬁngerprint impression of a ﬁnger (the baseline impression) with other
impressions of the same ﬁnger. Figure 4.7 shows that changing the baseline impression
for the ﬁnger will result in a different average deformation model for that ﬁnger (the
<I> values are as discussed in section 4.4.1). Figure 4.8 shows the average deformation
for 3 different ﬁngers; it can be clearly seen that the average warping functions are

different for the 3 ﬁngers indicating that the ﬁngerprint deformation is ﬁnger-speciﬁc.

91

 

 

 

 

 

 

 

 

 

 

 

 

 

 

= 15.54

(a) (I)

 

 

(b) <I> = 17.97

 

 

 

 

 

Inn-aka}: n; llW'iv. PlﬂﬁlE
I IIDHIEHIE

 

 

 

 

 

 

 

 

= 48.79

(c) (I)

92

 

(d) <I> = 83.12

 

 

 

 

 

 

E
e
H
:8
ii

 

 

..
.-
..
l—
>-
._
r.
._

F"
1—

 

 

 

 

 

 

(f) e = 232.53

Figure 4.7: The average deformation model (shown as deformations on a reference
grid) corresponding to 6 templates of a ﬁnger sorted in increasing <I>-values. (a) is
chosen to be the optimal template since it has the least <I>-value.

93

 

(a) <1> = 46.68

 

IIIIIIIIILIIIIIFIIIIITITf

 

 

 

 

 

 

 

 

 

 

 

IllfllllllfllllflllIll—[IllI

(c) (I) = 85.18

Figure 4.8: The average deformation model (shown as deformations on a reference
grid) of 3 different ﬁngers .

94

4.4.1 The (1) Index of Deformation

We consider the following two questions in this section:

1. Which of the L average deformation models can be considered to be the optimal

model for this ﬁnger?

2. Will the optimal model, when incorporated in the matching stage, result in

improved performance compared to the suboptimal models?

In order to address these questions, we ﬁrst deﬁne the pixel-wise covariance matrix

associated with the i-th average deformation, F}, as follows:

Dun): ——Z(F..-(u) u)-) (F..(u)- F.(u))T. (4.10)

#i

where E, is the deformation function that warps T; to Tj. The covariance matrix
deﬁned at each pixel u, is a measure of the variability associated with the estimated
deformation functions. Two choices of pixel-wise measures of variability are given by
(i) the determinant, ¢(Dp,(u)) = IDp‘.(u )], and (ii) the trace, ¢(D -.u( ))- — tr(Dp (11)).
Pixels with large (small) values of d indicate high (low) variability in the deformations
Fij. We propose to use the values of 45 to determine the optimal model for a given

ﬁnger. We deﬁne the it" index of deformation, (1),, as

Isl

(Pi: lS—lr 1:; ¢( Dp.( (),u) (4.11)

95

where, ¢(D) = tr(D), and [S] is the number of pixels in the domain S. Subsequently,
we choose ”1",. as the template with the smallest variability in deformation if i‘ =
arg min,<I>,«. In effect, we choose that template T,- that minimizes the average variation
across pixels measured in terms of (1),. Low (high) values of the index of deformation

indicate that the warping functions are similar (dissimilar) to each other.

4.4.2 Eliminating Erroneous Correspondences

For each baseline ﬁngerprint impression, it is important to determine the set of minu-
tiae points that are correctly paired to form a correspondence. The reason for this
is that the average deformation model is sensitive to the accuracy of the ridge curve
correspondence, which in turn depend on the minutiae correspondence. It is, there-
fore, necessary to check the correctness of the minutiae correspondences prior to
obtaining the ridge curve correspondences. Figure 4.9(a) gives an example of two
incorrect minutiae correspondences which result in incorrect ridge curve correspon-
dences (Figure 4.9(b)). These erroneous correspondences have to be eliminated prior
to computing the average deformation model; failure to exclude such minutiae points
results in a warping model that exhibits spurious distortions. This is done using the

technique described below.

For the given baseline ﬁngerprint impression, minutiae points that have a corre
spondence with at least (3 (8 = 5) of the remaining L — 1 impressions are extracted.
We denote the set of all extracted minutiae points by M = {m,-, i = 1,2, . . .,K},

where K is the total number of such minutiae points. Each m,- has a correspond-

96

 

(b)

Figure 4.9: Examples of incorrect minutiae correspondences (a) resulting in erroneous
ridge curve correspondences (b).

97

 

 

 

 

lllllllliLLlllTlfll

lllllllllllllllllll

 

 

 

 

 

 

(b) <1> = 102.16 (c) <1> = 67.78

Figure 4.10: Effect of eliminating unreliable minutiae correspondences on the average
deformation model; (a) template ﬁngerprint, (b) average deformation model with
p = 100, and (c) average deformation model with p = 60.

98

ing minutiae point in at least 3 of the L — 1 impressions. We denote these pairings
by (m,, 191), (m,, p2), . . . , (m,, p5,), where f,- is the total number of pairings. We now

develop a measure of reliability for minutiae point 771, as follows:

1. Sampled ridge point correspondences are obtained for each (m,,pj), j =
1,2,...,n,- based on which a TPS deformation model, F(m,,pj) is computed.

The average deformation model for the minutiae point m,- is given by

l
i; F(mi PJ'l(u

Q<'§“[p_..|

Here, the average deformation model is obtained in a 10 x 10 square region, say

Sm“ centered at m,.

2. Let

"1(1' : m%;( (F(m,-) PJ')( —Fmi(u)) ' (F(m.-,pj)(u) - Fmi(u))T (4.12)

denote the site—wise variability measure of the deformations F (m, .le around Fm...

The average variability is measured by

Sm.
1 l .l

Rnizm;

trace(mei (11))

with small values of Rm, indicating better reliability. Correspondences pertain-
ing to those minutiae points with R,,,, values lower than the p—th percentile (e. g.,

p = 60) are used to develop the average deformation model for the template

99

ﬁngerprint.

For the incorrect minutiae correspondences in Figure 4.9, the value of R for the top
minutiae point was 93.2 (the 60-th percentile value of R was 55.5 for this template)
while the lower minutiae point occurred in less than 5 corresponding pairs and hence
was eliminated. Figure 4.10(a) shows the average deformation model that results for
this template when all correspondences are used (i.e.,p = 100); Figure 4.10(b) gives

the deformation model for p = 60.

4.5 Experimental Results

In order to apply the TPS model to reliably estimate ﬁngerprint deformation, we need
to have several impressions of the same ﬁnger. Large number of impressions of a ﬁnger
are not available in standard ﬁngerprint databases (e.g., FVC 2002 [75]). Therefore,
ﬁngerprint images of 50 ﬁngers were acquired using the Identix sensor (256 x 255, 380
dpi) over a period of two weeks in our lab. There were 32 impressions corresponding
to every ﬁnger, resulting in a total of 1600 impressions. One half of the impressions
(L = 16 for each ﬁnger, resulting in 800 impressions) were used as templates to
compute the average deformation model for each ﬁnger, while the remaining 800
impressions were used as query images for testing. For each template image, T,
the minutiae set, MT, and the thinned image, RT, were extracted. The average
deformation model of T, FT, was obtained based on pairings with the remaining
15 impressions of the same ﬁnger (equation (4.7) with A = 0.1). The minutiae set

MT was transformed to the deformed set, M DT E FT(MT) using FT. A total of

100

 

Figure 4.11: Improved alignment of template and query images using ridge curve
correspondences (right panel). The alignment using minutiae correspondences are
shown in the left panel. Both sets of alignment use the TPS warping model.

101

 

ca
01

92

8

m
_L

 

Genuine Accept Rate (%)
on
N

I
\
1

 

 

 

 

 

 

79 ‘ - - Without Average Deformation *
— Average Deformation Using Minutiae Correspondences
78 —- Average Deformation Using Ridﬂ Curve Correspondences -
-1 0
10 10
False Accept Rate (%)

Figure 4.12: Improvement in matching performance when ridge curve correspondences
is used to develop the average deformation model.

 

m
0'!

2

8

 

Genuine Accept Rate(%)
8

 

 

 

 

 

 

 

81
80 ~ — Minutiae Correspondences ‘
— - Sub-optimal Templates Using Ridge Correspondences
79 _ .- , - Q-optimal Templates Using Ridge Correspondences ‘
78 ‘ ‘ A ‘ ‘ ‘ ‘ ‘
1 0‘1 100

False Mept Rate(°/o)

Figure 4.13: Matching performance when the Q index of deformation is used to se-
lect optimal templates. Both optimal and suboptimal templates using ridge curve

correspondences result in superior matching performance compared to minutiae cor-
respondences.

102

 

800 sets (50 x 16) of deformed minutiae points were thus obtained. In order to
test the matching performance of the deformed minutiae sets, and the utility of the
index of deformation, Q, the following two experiments were conducted. In both
these experiments, the minutiae matcher described in [1] was used to generate the
matching (similarity) score.

In the ﬁrst experiment, the matching performance using the average deformation
model was evaluated. Every template image, T, was compared with every query
image, Q, and two types of matching scores were generated for each comparison:
the matching score obtained by matching (i) MT with Mq, and (ii) M DT with Mq.
The Receiver Operating Characteristic (ROC) curve plotting the genuine accept rate
(GAR) against the false accept rate (FAR) at various matching thresholds is pre-
sented in Figure 4.12. An overall improvement of 2% is observed when the average
deformation model is used to distort MT prior to matching.

In the second experiment, the advantage of using the index of deformation is
demonstrated. The Q-index of deformation (with ¢(D) = tr(D)) of every template
image is used to rank the templates according to their variability in the distortion.
The template images can now be split into two sets: (i) impressions with the least Q
values for every ﬁnger (the Q-optimal templates) and (ii) the remaining impressions
for every ﬁnger (the Q-subOptimal templates). We repeated the matching procedure
outlined above using these two template sets. The resulting ROC curve is shown
in Figure 4.13. From the ﬁgure, it is clear that using Q-optimal templates results
in better performance compared to using Q-suboptimal templates. Further, the Q-

suboptimal templates still yield better performance compared to the non-distorted

103

 

templates thus demonstrating the importance of the average deformable model.

4.6 Summary

In this chapter, a deformation model for estimating the distortion effects in ﬁnger-
print impressions has been prOposed. The distortion is computed based on ridge
curve correspondence. It has been shown that the deformation model based on ridge
curve correspondence gives superior authentication performance compared to minu-
tiae point pattern matching. The warping model samples the ridge curve and uses
thin-plate splines for estimating the non-linear deformation. An index of deforma-
tion has also been proposed for selecting the “optimal” template from a given set of
ﬁngerprint impressions.

The work presented here can be expanded in several ways. An interesting exer-
cise would be to design an incremental approach to updating the average deformation
model, i.e., updating the current average deformation model of a ﬁnger by using infor-
mation presented by newly acquired ﬁngerprint impressions. The technique proposed
here uses a simple pixel-wise averaging measure to compute the average deformation
model. This measure is sensitive to extreme deformations borne out by outliers; thus,
more robust measures of describing the ﬁnger speciﬁc average deformation model are
needed. The effect of the number of training samples (used to develop the average

deformation model ) on the matching performance has to be systematically studied.

N on-linear deformation in ﬁngerprints is a consequence of utilizing contact—based

sensors for imaging the ﬁngertip. Using an acoustic (ultrasound) camera to procure

104

ﬁngerprint images may help avoid this problem [76]. However, an ultrasound camera
introduces other challenges that may affect the quality of the image (e.g., a high
quality reconstruction procedure is required to “assemble” an image). Further, the

cost of the camera and its size may limit its deployment in real-world applications.

105

 

Chapter 5

Multibiometrics

In the previous chapters information integration involved looking for complementary
information present in a single biometric trait, namely, ﬁngerprint. However, bio-
metric systems using a single biometric trait for authentication purposes have the

following limitations:

1. Noise in sensed data: The sensed data might be noisy or distorted. A ﬁngerprint
with a scar, or a voice altered by cold are examples of noisy data. Noisy data
could also be the result of defective or improperly maintained sensors (e.g.,
accumulation of dirt on a ﬁngerprint sensor) or unfavorable ambient conditions
(e.g., poor illumination of a user’s face in a face recognition system). Noisy
biometric data may be incorrectly matched with templates in the database

(Figure 1.7), resulting in a user being incorrectly rejected.

2. Intra-class variations: The biometric data acquired from an individual during
authentication may be very different from the data that was used to generate

106

the template during enrollment, thereby affecting the matching process. This
variation is typically caused by a user who is incorrectly interacting with the
sensor (Figure 5.1), or when the sensing operation is modiﬁed during the veri-
ﬁcation phase (e.g., by changing sensors - the sensor interoperability problem).
As another example, the varying psychological makeup of an individual, might

result in vastly different behavioral traits at various time instances.

. Restricted degrees of freedom: While a biometric trait is expected to vary sig-
niﬁcantly across individuals, there may be similarities in the feature sets used to
represent these traits. This limitation restricts the degrees of freedom provided
by the biometric trait. For example, Gorman [7] states that the discrimina-
tion capability of ﬁngerprints (i.e., keyspace) is about 10‘ - 105, whereas an 8-
character password of randomly chosen characters has a keyspace of 6.6 x 1015.
Every biometric trait has some upper bound in terms of its discrimination ca-

pability.

. Non-universality: While every user is expected to possess the biometric trait
being acquired, in reality it is possible for a subset of the users to not possess
a particular biometric. A ﬁngerprint biometric system, for example, may be
unable to extract features from the ﬁngerprints of certain individuals, due to
the poor quality of the ridges (Figure 1.8). Thus, there is a failure to enroll
(FTE) rate associated with using a single biometric trait. It has been empirically
estimated that around 4% of ﬁngerprint images have poor quality ridges. den

Os et al. [77] report the FTE problem in a speaker recognition system.

107

 

5. Spoof attacks: An impostor may attempt to spoof the biometric trait of a

legitimate enrolled user in order to circumvent the system. This type of attack

is especially relevant when behavioral traits such as signature [78, 79] and voice

[80] are used. However, physical traits are also susceptible to spoof attacks. For

example, it has been convincingly demonstrated that it is possible to construct

artiﬁcial ﬁngers/ ﬁngerprints in a reasonable amount of time to circumvent a

ﬁngerprint authentication system [81].

 

Test

Test
Parameter

False
Rate

Reject

False
Rate

Accept

 

Fingerprint

Face

Voice

 

 

FVC 2002 [75]

FRVT 2002 [82]

NIST 2000 [83]

 

Users ,mostly
in age group
20—39
Enrolment
and test im-
ages were col-
lected in in-
door environ-
ment and
could be on
different days
Text
dependent

 

0.2%

10%

10-20%

 

0.2%

1%

2-5 %

 

Table 5.1: Error rates associated with ﬁngerprint, face and voice biometric systems.
The accuracy estimates of biometric systems depend on a number of test conditions.

Some of the limitations imposed by single biometric systems can be overcome

by installing multiple sensors that capture different biometric traits. Such systems,

known as multibiometric systems [84], are expected to be more reliable due to the

presence of multiple, independent pieces of evidence [85]. These systems are also

able to meet the stringent performance requirements imposed by various applications

108

 

 

 

(a) (b) (c)

Figure 5.1: Intra-class variation associated with an individual’s face image. Due to
change in pose, an appearance-based face recognition system will not be able to match
these 3 images successfully, although they belong to the same individual [3].

[86]. Multibiometric systems address the problem of non-universality, since multiple
traits ensure sufficient population coverage. Further, multibiometric systems provide
anti-spooﬁng measures by making it difficult for an intruder to spoof the multiple
biometric traits of a genuine user simultaneously. By asking the user to present a
random subset of biometric traits, the system ensures that a ‘live’ user is indeed
present at the point of data acquisition.

Multibiometric biometric systems have received much attention in recent litera-
ture. Brunelli et al. [87] describe a multibiometric system that uses the face and
voice traits of an individual for identiﬁcation. Their system combines the scores of
ﬁve different classiﬁers operating on the voice and face feature sets, to generate a
single matching score that is used for identiﬁcation. Bigun et al. develop a statis-
tical framework based on Bayesian statistics to integrate information presented by
the speech (text-dependent) and face data of a user [88]. Hong et al. use face and

ﬁngerprints for person identiﬁcation [86]. Their system consolidates multiple cues

109

by associating different conﬁdence measures with the individual biometric matchers.
A commercial product called BioID [89] uses voice, lip motion and face features of
a user to verify identity. General strategies for combining multiple classiﬁers have
been suggested in [90] and [36]. All the approaches presented in [90] (the highest
rank method, the Borda count method and logistic regression) attempt to reduce or
rerank a given set of classes. These techniques are thus relevant to the identiﬁcation
problem in which a large number of classes (identities) are present. Prabhakar and
Jain show in [91] that selecting classiﬁers based on some “goodness” statistic may be
necessary to avoid performance degradation when using classiﬁer combination tech-
niques. There is also a large amount of literature dealing with combination strategies

for matching scores (see for example [92], [93], [94]).

5.1 Fusion in Biometrics

Multibiometric systems integrate information presented by single or multiple biomet-
ric indicators. The information can be consolidated at various levels. Figure 5.2
illustrates the various levels of fusion possible when combining two (or more) biomet-
ric systems. The three possible levels of fusion are: (a) fusion at the feature extraction

level, (b) fusion at the matching score level, (c) fusion at the decision level.

1. Fusion at the feature extraction level: The data obtained from each sensor is
used to compute a feature vector. As the features extracted from one biometric
indicator are independent of those extracted from the other, it is reasonable to

concatenate the two vectors into a single new vector. The new feature vector

110

 

 

->Accepl/Rej¢cl

Accepl/Rejecr

 

Figure 5.2: A bimodal biometric system showing the three levels of fusion; FU: Fusion
Module, MM: Matching Module, DM: Decision Module.

111

now has a higher dimensionality and represents a person’s identity in a different
(and, hopefully, more discriminating) hyperspace. Feature reduction techniques

may be employed to extract useful features from the larger set of features.

2. Fusion at the matching score level: Each system provides a similarity score
indicating the proximity of the input feature vector with the template vector.
These scores can be combined to assert the veracity of the claimed identity.
Techniques such as logistic regression may be used to combine the scores re-
ported by the two sensors. These techniques attempt to minimize the FRR for

a given FAR [95].

3. Fusion at the decision level: Each sensor captures a biometric attribute and the
resulting feature vectors are individually classiﬁed into the two classes - accept
or reject. A majority vote scheme, such as that employed in [96] can be used

to make the ﬁnal decision.
Fusion in the context of biometrics can take the following forms:
1. Single biometric multiple representation.
2. Single biometric multiple matchers.

3. Multiple biometric fusion.

5.1.1 Single Biometric Multiple Representation

This type of fusion involves using multiple representations of a single biometric indi-

cator. Typically, each representation has its own associated matcher/classiﬁer. The

112

similarity scores reported by these classiﬁers are then consolidated. Cappelli et al.
[97] describe a ﬁngerprint classiﬁcation system 1 that combines a structural classiﬁer
with a KL transform-based classiﬁer by integrating the scores generated by the two
classiﬁers. This is done by ﬁrst mapping the scores (which are distance measures)
into a common domain via a double sigmoid function and then taking a weighted
average in the new domain. Jain et al. [98] also use multiple classiﬁers for ﬁngerprint
indexing. Their technique uses a K nearest neighbor classiﬁer and a set of 10 neural
network classiﬁers to classify ﬁngerprints. General strategies for combining multiple
classiﬁers have been suggested in [90]. All the approaches presented there (the highest
rank method, the Borda count method and logistic regression) attempt to reduce or
rerank a given set of classes. These techniques are thus relevant to the identiﬁcation
problem in which a large number of classes (identities) are present.

The fusion in this approach takes place at the matching stage, after the classiﬁers
report a similarity score for each class. Prabhakar and Jain [91] observe that the
classiﬁers used for fusion have to be carefully selected in order to avoid performance

degradation.

5.1.2 Single Biometric Multiple Matchers

It is also possible to incorporate multiple matching strategies in the matching module
of a biometric system and combine the scores generated by these strategies. Jain

~et al. [95] use the logistic function to map the matching scores obtained from two

 

1The system classiﬁes a ﬁngerprint into one of ﬁve classes - Arch, Left loop, Right loop, Whorl and
Tented arch. Thus it is not a biometric system by itself, as it does not perform person identification
or veriﬁcation.

113

different ﬁngerprint matching algorithms into a single score. The authors demonstrate
that such an integration strategy improves the overall performance of a ﬁngerprint

veriﬁcation system.

This type of fusion also takes place at the matching stage of a biometric system.
Although there are multiple matchers in this case, all matchers Operate on the same

representation of the biometric data.

5.1.3 Multiple Biometric Fusion

Multimodal fusion refers to the fusion of multiple biometric indicators. Such systems
seek to improve the speed and reliability (accuracy) of a biometric system [86] by
integrating matching scores obtained from multiple biometric sources. A variety
of fusion schemes have been described in the literature to combine these various
scores. These include majority voting, sum and product rules, k-N N classiﬁers, SVMs,

decision trees, Bayesian methods, etc. (see for example [92, 36, 88, 99, 93, 94]).

An important aspect that has to be addressed in fusion at the matching score level
is the normalization of the scores obtained from the different domain experts [87].
Normalization typically involves mapping the scores obtained from multiple domains
into a common domain before combining them. This could be viewed as a two-step
process in which the distributions of scores for each domain is ﬁrst estimated using
robust statistical techniques [100] and these distributions are then scaled or translated

into a common domain.

Besides the techniques described above, other types of fusion are also possible in

114

 

biometrics. (i) A ﬁngerprint biometric system may store multiple templates of a user’s
ﬁngerprint (same ﬁnger) in its database. When a ﬁngerprint impression is presented
to the system for veriﬁcation, it is compared against each of the templates, and the
matching score generated by these multiple matchings are integrated. (ii) A system
may store a single template of a user’s ﬁnger, but acquire multiple impressions of
the ﬁnger during veriﬁcation. (iii) Another possibility would be to acquire and use
impressions of multiple ﬁngers for every user. These possibilities have been discussed

in [101].

5.2 Multibiometric System

The choice and number of biometric traits used in designing a multibiometric system
are variables that have to be decided before deploying the system. Fingerprint systems
exhibit very good performance and are very popular since the sensors used to acquire
them can be easily embedded in a system. Most of the working population have hands
and, therefore, hand geometry would be a good choice also. Face images can be easily
acquired and even non-experts can compare face images in the case of repudiation
claims where an individual uses a facility and then denies having used it. We use face,
hand geometry and ﬁngerprints to design and evaluate our multibiometric system. A
brief description of the face and hand geometry indicators used in our experiments is

given below.

115

 

5.2.1 Face Veriﬁcation

Face veriﬁcation involves extracting a feature set from a two—dimensional image of
the user’s face and matching it with the template stored in the database. The fea-
ture extraction process is often preceded by a face detection process during which
the location and spatial extent of the face is determined within the given image.
This is a difﬁcult process given the high degree of variability associated with human
faces (color, texture, expression, pose, etc.). The problem is further compounded by
the presence of complex backgrounds and variable lighting conditions (Figure 5.3).
A variety of techniques have been described in the literature to locate the spatial
coordinates of a face within an image [102, 103, 104]. Once the boundary of the
face is established, we use the eigenface approach to extract features from the face
[105, 106]. In this approach a set of orthonormal vectors (or images) that span a
lower dimensional subspace is ﬁrst computed using the principal component analysis
(PCA) technique. The feature vector of a face image is the projection of the (original
face) image on the (reduced) eigenspace. Matching involves computing the Euclidean

distance between the eigenface coefﬁcients of the template and the detected face.

 

Figure 5.3: The problem of face detection is compounded by the effects of complex
lighting and cluttered background.

116

5.2.2 Hand Geometry

Hand geometry, as the name suggests, refers to the geometric structure of the hand.
This structure includes width of the ﬁngers at various locations, width of the palm,
thickness of the palm, length of the ﬁngers, etc. Although these metrics do not vary
signiﬁcantly across the population, they can nevertheless be used to verify the identity
of an individual. Hand geometry measurement is non-intrusive and the veriﬁcation
involves a simple processing of the resulting features. Figure 5.4 shows the hand
geometry system that was used in our experiments. The system computes 14 feature
values comprising of the lengths of the ﬁngers, widths of the ﬁngers and widths of

the palm at various locations (Appendix A).

 

(a) GUI for capturing hand (b) 14 hand features corre-
geometry. The ﬁve pegs aid sponding to various length
in proper placement of the and width measurements.
hand on the platen.

Figure 5.4: A Hand Geometry System. The sensor provides both the top and side
views of the subject’s hand. Features are extracted using the image of the top-view
only.

117

5.2.3 Combining the three modalities

The database for our experiments consisted of matching scores obtained from three
different modalities - face, ﬁngerprint and hand geometry. However, data pertaining
to all three modalities were not available for a single set of users. The mutual non-
dependence of the biometric indicators allows us to assign the biometric data of one

user to another.

The database itself was constructed as follows: The ﬁngerprint and face data were
obtained from user set I consisting of 50 users. Each user was asked to provide nine
face images and nine ﬁngerprint impressions (of the same ﬁnger). This data was used
to generate 3,600 (50 x 9 x 8) genuine scores and 22,050 (50 x 49 x 9) impostor
scores for each modality. The hand geometry data was collected separately from user
set 11 also consisting of 50 users 2. This resulted in 3, 600 genuine scores and 22, 050
impostor scores for this modality also. Each user in set I was randomly paired with a
user in set II. Thus corresponding genuine and impostor scores for all three modalities
were available for testing. All scores were mapped to the range [0,100]. Since the
face and hand scores were not similarity scores (they were distance scores), they were
converted to similarity scores by simply subtracting them from 100. A similarity
score :1: represents the proximity of two feature sets as computed by a classiﬁer. A
score vector represents the scores of multiple classiﬁers. Thus, the vector (2:1, 2:2, 3:3)
is a score vector, where :31, 2:2 and 3:3 correspond to the (similarity) scores obtained

from the classifers corresponding to the face, ﬁngerprint and hand geometry systems,

 

2Some users from set I were present in set II.

118

respectively.

The scatter plot of the genuine and impostor scores (3, 600 genuine scores, and
11, 025 impostor scores) is shown in Figure 5.5. The plot indicates that the two classes
are reasonably separated in 3-dimensional space; therefore, a relatively simple classi-
ﬁer should perform well on this dataset. The ROC curves depicting the performance

of the individual modalities are shown in Figure 5.6.

    
 

_A
l J

l

HandGeometryScores
s .3 s s

 

Figure 5.5: Scatter Plot showing the genuine and impostor scores in 3-D space. The
points correspond to 3, 600 genuine scores (+) and 11, 025 impostor scores (0).

Sum Rule

The simplest form of combination would be to take the weighted average of the scores
from the multiple modalities. This strategy was applied to all possible combinations
of the three modalities. Equal weights were assigned to each modality as the bias of

each classiﬁer was not computed. Figure 5.7 and Figure 5.8 show the performance of

119

100 “We,

 

  
 

Fingerprint

Genuine Accept Rate(%)
8

 

 

 

50 .- -«
40 * 1
Hand Geometry
30 ~ -
20 A A A AAAAAl A A A -ALAAJ A A AAAA‘AI A A AA AAAl A A A LALAA
10’3 10'2 10'1 10° 10’ 102
False W Rate(%)

Figure 5.6: ROC curves showing the performance of each of the three individual
modalities.

the sum rule on the three modalities.

Decision Trees

A decision tree derives a sequence of if-then-else rules using the training set in order to
assign a class label to the input data. It does this by ﬁnding out an attribute (feature)
that maximizes information gain at a particular node. The 05.0 program [107] was
used to generate a tree from the training set of genuine and impostor score vectors.
The training set consisted of 11, 025 impostor score vectors and 1,800 genuine score
vectors. The test set consisted of the same number of impostor and genuine score
vectors. Figure 5.9 shows the construction and performance of the 05.0 decision tree

on the training and test sets.

120

 

 

 

 

I

70 _ Fingerprint , / ,

l
I

Face
55 -

 

A A .1

 

 

 

I
/ Hand Geometry

 

 

 

w A A
10” 104 10"

Fuse Accept W96)

10" 10

(21) Combining face and ﬁngerprint scores

10"
False mot Rete(%)

 

10 10

O 1

(b) Combining face and hand geometry scores

 

 

 

 

 

 

 

 

 

 

 

 

Threshold Genuine False Threshold Genuine False
Accept Rate(%) Accept Rate(%) Accept Rate(%) Accept Rete(%)
38 100.00 11.75 72 100.00 37.31
41 99.77 4.54 79 99.33 12.28
42 99.33 2.83 82 98.00 5.83
43 98.66 1.75 83 97.55 4.13
44 97.55 0.80 86 95.33 0.97
45 95.77 0.31 87 92.66 0.52
46 94.66 0.12 88 90.88 0.23
47 93.11 0.01 90 81.77 0.02
49 87.55 0.00 91 76.22 0.00

 

 

 

10'

 

 

Figure 5.7: ROC curves showing an improvement in performance when scores are

combined using the sum rule.

121

4.7

 

 

 
 

 

  
 

 

 

 

 

 

 

 

 

 

 

100 P
’00 . W 7 f7 ’ F Fingerprint
F a + ,1 ace + 4
90' $736M d)" ‘ 90» HandGeometry ,
/ ,9“ ﬂ"
“ /
..’ eo- ,.-
°°" J ..~‘ ‘ :2: {A = 2”
’ ’1’ E, I, w,
70 ’ F'mqujnt / 3'- 4 g 70 Fingerprint r 7 {/f
60 / T § w I, //I
. ’ Face
50" /’ﬂ’ '1 g 50* l//
31’ ail/I
40 ,I 40 / +
/// I / Hand Geometry
30’ .2/ Hand Geometry ‘ 30’ 0” 1
‘0‘, ‘04 ‘04 ‘°° ‘°’ ‘02 2100" 10" 10" 10° 10‘ 10’
False Accept Rete(%) False Accept Rate(%)
(a) Combining ﬁngerprint and hand geometry (b) Combining face, ﬁngerprint and hand ge—
scores ometry scores
Threshold Genuine False Threshold Genuine False
Accept Rate(%) Accept Rate(%) Accept Rate(%) Accept Rate(%)
41 100.00 49.19 57 100.00 1.59
46 99.55 6.77 58 99.77 0.65
47 98.66 2.20 59 99.33 0.19
48 97.55 0.32 60 98.22 0.03
51 84.00 0.00 62 95.55 0.00

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 5.8: ROC curves showing an improvement in performance when scores are
combined using the sum rule.

122

 

 

INPUT SCORES

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(x1. x2, x3)
ii
YES x2 <= 8.07 ”0
ii ,
YES x1 <= 93.06 NO YES x1<= 72.12 NO
IMPOSTOR GENUINE GENUINE
x2 <= 35.50‘
YES NO
[~190st GENUINE

Evaluation on training data (11, 250 score vectors):

 

Genuine Class

Impostor Class

 

Genuine Class

1,720

80

 

 

Impostor Class

 

2

 

11,023

 

Evaluation on test data (11,250 score vectors):

 

Genuine Class

Impostor Class

 

Genuine Class

1,624

176

 

Impostor Class

 

4

 

 

11,021

 

123

Figure 5.9: Construction and Performance of the 05.0 Decision Tree. The perfor-
mance is indicated by confusion matrices.

 

 

Linear Discriminant Function

Linear discriminant analysis of the training set helps in transforming the 3-
dimensional score vectors into a new subspace that maximizes the between-class sep-
aration. Figure 5.10 shows the plot of the score vectors using the ﬁrst and the second

discriminant variables.

 

0

-2

-4

Second Discriminant Variable

 

 

 

 

First Discrim'nant VOW

Figure 5.10: Linear Discriminant Analysis of the score vectors. The score vectors
have been plotted in a 2-dimensional space representing the ﬁrst and the second
discriminant variables. There are 1, 800 genuine score vectors(+) and 11,025 impostor
score vectors (0).

The test set vectors are classiﬁed by using the minimum Mahalanobis distance
rule (after ﬁrst calculating the centroids of the two classes in the new feature space,
and then measuring the Mahalanobis distance). We assume that the two classes have
unequal covariance matrices. Table 5.2 shows the confusion matrices resulting from

using this rule on different partitioning of the data into training and test sets.

124

 

 

Genuine Class Impostor Class

 

 

 

 

 

 

Trial 1: Genuine Class 1, 800 0
Impostor Class 54 10, 971
Genuine Class Impostor Class
Trial 2: Genuine Class 1, 800 0
Impostor Class 50 10, 975

 

 

Genuine Class Impostor Class
Tiial 3: Genuine Class 1, 800 0
Impostor Class 72 10,953

 

 

 

 

 

 

 

Table 5.2: Performance of the linear discriminant classiﬁer on three different trials
as indicated by the confusion matrices. In each trial the training and test sets were
partitioned differently.

 

Discussion

The experiments described above suggest that the sum rule performs better than
the decision tree and linear discriminant classiﬁers. The FAR of the tree classiﬁer is
0.036% (:l:0.03%) and the FRR is 9.63% (i0.03%). The FAR of the linear discrimi-
nant classiﬁer is 0.47% (i0.3%) and it’s FRR is 0.00%. The FRR value in this case is
a consequence of overﬁtting the genuine class as it has fewer samples in both the test
and training sets. The sum rule that combines all three scores has a corresponding
FAR of 0.03% and a FRR of 1.78% suggesting better performance than the other two
classiﬁers. It has to be noted that it is not possible to ﬁx the FRR (and then compute

the FAR) in the case of the decision tree and linear discriminant classiﬁers.

125

5.3 Learning User-speciﬁc Parameters

We develop techniques to further improve system performance in a multibiometric
system by learning user—speciﬁc matching thresholds and weighting, for individual
traits. Matching thresholds are used to decide if a matching score corresponds to a
genuine user or an impostor. Scores greater than the matching threshold indicate a
genuine user; scores lower than the threshold indicate an impostor. Biometric systems
typically use a common threshold across users. We show that by setting user-speciﬁc
thresholds, it is possible to improve system performance. Weighting is used to vary
the importance of matching scores of each biometric trait. By learning user-speciﬁc

weights, the performance of the system is shown to improve.

The automatic learning and update of system parameters help reduce the error
rates associated with an individual, thereby improving the performance accuracy of
the system. In a multibiometric system, it is essential that different biometric traits
be given various degrees of importance for different users. This is important especially
when the biometric trait of some users cannot be reliably acquired. For example, users
with persistently dry ﬁngers may not be able to provide good quality ﬁngerprints.
Such users might experience higher false rejects when interacting with a ﬁngerprint
system. By reducing the weight of the ﬁngerprint trait of such users, and increasing
the weights associated with the other traits the false reject error rate of these users
can be reduced. Further, the intra—class and inter-class variability associated with a
single biometric trait varies between users. Consequently, different users are prone to

different types of errors. The false reject mte (FRR) of users with large inter-class

126

variations may be high. Similarly, the false accept rate (FAR) associated with users
having small inter-class variations may be high. Thus, the system invokes a speciﬁc
set of parameters based on the claimed identity, I. The biometric system learns user-
speciﬁc parameters by observing system performance over a period of time. This
will appeal to that segment of the population averse to interacting with a system
that constantly requests a user to provide multiple readings of the same biometric.
The emphasis is on tuning the system variables automatically, yet appropriately, to
attain performance gain. Therefore, adaptation in a multibiometric system entails the
following: (a) developing user-speciﬁc matching thresholds, and (b) assigning weights

to individual biometric traits.

5.3.1 User-speciﬁc matching thresholds

The matching thresholds for each user is computed using the cumulative histogram
of impostor scores corresponding to that user. Since genuine scores (matching scores
generated when comparing feature sets from the same user) would not be available
when the user begins to use the system, the impostor scores are used for this purpose.
The impostor scores are generated by comparing the feature sets of the user with fea-
ture sets of other users or with feature sets available in a predetermined impostor
database. The cumulative histogram at a value x, :2: = 1, 2, . . . 100, is the sum of all
those impostor scores lesser than or equal to :r. The user-speciﬁc matching thresholds

are computed as follows:

127

"‘4

 

ii
a
i

 

(C)

Figure 5.11: Intra-class variability and inter-class similarity of hand geometry features
depicted using Chernoff faces. (a) The feature sets associated with a user showing
large variability. (b) and (c) The feature sets associated with two different users
exhibiting similarity [4]

128

1. For the 2'“ user in the database, let t,(*y) correspond to the threshold in the cumu-
lative histogram that retains 7 fraction of scores, 0 g 'y S 1.

2. Using {t,-('y)} as the matching threshold, compute {F AIL-(7), GAR,- (7)}, where GAR is
the genuine accept rate.

3. Compute the total FAR and GAR as, F AR(7) = 2,- F AR,- (7), GAR(7) = Z,- GAIL-('7).

4. Use {FAR(7),GAR(7)} to generate the ROC curve.

We observe that the choice of threshold relies on the distribution of impostor
scores for each user (Figure 5.12). This is in contrast to traditional methods where
the threshold is established by pooling together the impostor scores associated with
all users. When the multibiometric system is deployed, the 7 corresponding to a
speciﬁed FAR is used to invoke the set of user-speciﬁc thresholds, {t,-('7)}. Table 5.3
shows the user-speciﬁc thresholds (corresponding to a FAR of 1%) associated with
the 10 users whose data was collected over a period of two months. The ROC curves

indicating the improved performance is shown in Figure 5.13.

5.3.2 Weighting individual biometric traits

Each biometric trait provides a matching score based on the input feature set provided
and the template against which the input is compared with. These scores are weighted
according to the biometric trait used (ml for ﬁnger, 1112 for face and 103 for hand

geometry), in order to reduce the impostance of less reliable biometric traits (and

129

é'.‘

 

“ﬂ ‘1

Frequency

Frequency

Frequency
0
9 'o .0
3 8 8

 

0025*

p
i?

 

0 i . 1 i, . ,1,L

40 60
Similarity Score

(a)

 

 

0035*

o
o .0
8 8

.O
0
re

0.015

 

 

 

 

 

O
O O
O -‘
- Ur

§

OT

 

w li/

Similarity Score

(9)

<.
K

 

 

,0

6'

O
01
r

.0
a

Cumulative Frequency

 

 

30 40
Similarity Score

(1))

 

o p o o p o
‘5 U’1 01 \1 ca (0
, . y r r r

Cumulative Frequency
9
(J

 

 

 

30 40 60 70
Similarity Score

(d)

 

Cumulative Frequency
0 o o o o o
N 0 5 U‘ 0') \l

.0

 

i

 

30 4o
Similarity Score

(0

Figure 5.12: The impostor distributions of the face, biometric feature vector of 3 users.
(a) (c) and (e) are the histogram of impostor scores associated with the 3 users. (b),
(d) and (f) are the corresponding cumulative histograms. For 7 = 0.3 it is observed
that the thresholds for each of the users is different.

130

 

 

 

 

 

 

 

 

 

 

ﬁe ,, 90
.’/ . ,-
84' / %
,”/
A82 ’I/ -‘ AwL
i; USER-SPECIFIC THRESHOLD X, , §7s~ 1
£30 ”’,// £70. 4
1” ’II a
mi " / 365‘ ‘
8 ’,/// 260
2’ // B
76 / 55-
6 l ,,// COMMON THRESHOLD 650
74» ,/
?/ 45>
72 ----.---. AA eeeee 40’ A -. A A
to” 10F 10‘ 10" 10? 10'
Falee Accept Rate(%) False Accept 831306)
(a) (b)

Figure 5.13: ROC curves exhibiting performance improvement when user-speciﬁc
thresholds are utilized to verify claimed identity. (a) Fingerprint; (b) Face.

 

 

User # Fingerprint Face Hand Geometry
1 14 91 94
2 17 91 95
3 15 92 95
4 12 94 95
5 11 91 90
6 11 90 92
7 16 95 94
8 19 92 97
9 11 90 96

10 19 94 93

 

 

 

 

 

 

Table 5.3: User-speciﬁc thresholds for the biometric traits of 10 users corresponding
to a FAR of 1% in each ROC curve.

131

increase the inﬂuence of more reliable traits). Weighting the matching scores can be

done in the following ways.

Weighting all traits equally and using a user-speciﬁc threshold

Equal weights are assigned to the face, hand and ﬁngerprint matching scores, and a

new score is obtained as,

3

1
Sf“, = Z ‘35]: (5.1)

k=1

 

The user speciﬁc threshold is computed using the impostor distribution of S f“,
(for each user) using the procedure outlined in section 5.3.1. The performance im-

provement can be seen in Figure 5.14(a).

 

 

       

 

 

 

 

 

 

100 e we
99. 99. USER-SPEClFIC WEIGHTS.
EQUALWEIGHTS.
eel useaseecreic THRESHOLD 98*
ES 97» 3‘ 97+
2 I
E 96- g ser’
g %~ g 95r
94 g 94—
93 3 eai
/
92» 4 92+
91 - 91»
90 A 1 A A‘ A 90 A
10" 10° 10' 10" 10° 10‘
FalaaAcceptRate(%) FabeAcceptRateM)

(a) (b)

Figure 5.14: ROC curves when using (a) equal weights for all three traits, and a
user-speciﬁc matching threshold, (b) user-speciﬁc weights for all three traits and a
common matching threshold.

132

 

 

User # Fingerprint Face Hand Geometry
(wi) (W2) (W3)
1 0.5 0.3 0.2
2 0.6 0.2 0.2
3 0.4 0.1 0.5
4 0.2 0.4 0.4
5 0.5 0.2 0.3
6 0.6 0.1 0.3
7 0.6 0.1 0.3
8 0.4 0.2 0.4
9 0.5 0.1 0.4
10 0.6 0.2 0.2

 

 

 

 

 

 

Table 5.4: Weights of different traits for 10 users.

Estimating user-speciﬁc weights by ‘exhaustive’ search and using a com-

mon matching threshold

Here, the optimal weight for each trait is found by searching the space of weights
((w1,w2,w3)) for each user with the constraint, wl + 7.02 + 1123 = 1, such that the
total error rate is minimized. The total error rate is the sum of the false accept and

false genuine rates.

1. For the 2"“ user in the database, vary weights w1,,-, w2,.- and 1123,,- over the range [0,1],
with the constraint w1,.-+w2,,-+w3,.- = 1. Compute S f“, = w1,iSI +w2,,-Sg+w3,.-Sg.
2. Choose that set of weights that minimizes the total error rate associated with the scores.

The total error rate is the sum of the false accept and false reject rates.

Table 5.4 lists the weights computed for the 10 users listed in table 5.3. Since the

weight estimation procedure utilizes the histograms of both the genuine and impostor

133

 

scores, computing user-speciﬁc thresholds using impostor scores does not further im-
prove performance. We, therefore, use a common matching threshold. The resulting
performance is indicated by the ROC curve in Figure 5.14(b). From table 5.4, we
observe that for user 4, ml = 0.2, a very low value. To understand this, we examined
the ﬁngerprints corresponding to this user (Figures 5.15(a) and 5.15(b)). We note
that the ridge details are not very clear, and therefore the minutiae matching algo-
rithm did not provide correct matching scores. This demonstrates the importance of
assigning user-speciﬁc weights to the individual biometric trait. Similarly, user 3 has
a very small weight attached to the face biometric, possibly due to varying face poses
and lighting during data acquisition (Figure 5.15( c), 5.15(d) and 5.15(e)). User 2
has a small weight attached to hand geometry due to incorrect placement of the hand

and a curved little ﬁnger (Figures 5.15(f) and 5.15(g)).

5.4 Factors Affecting a User-speciﬁc Approach

The following issues will have to be considered while deploying biometric systems

with user-speciﬁc thresholds and weights:

1. A ‘smart’ user may deliberately provide poor quality biometric data constantly
(e.g., by touching the ﬁngerprint sensor lightly), thereby forcing the system to
reduce the weights associated with a speciﬁc biometric. The user may then
claim that the biometric data belongs to someone else. Thus, the user accesses
a privilege, and later denies using it. To address such repudiation claims, one

could use the face images acquired during the veriﬁcation phase to invalidate

134

 

 

Figure 5.15: (a) and (b) Fingerprint images of user 4 whose ridge details are not very
clear (wl = 0.2); (c),(d) and (e) Varying face poses of user 3 (1.02 = 0.1); (f) and (g)
Incorrect placement of hand and the curved ﬁnger of user 2 (103 = 0.2.)

135

the user’s claim. However, this is a post-incidental solution in that it is invoked
after the weights have been lowered. A more effective solution would be to ﬂag

unnatural alterations observed in the weight vector for every user.

2. An intruder attempting to violate a biometric system might target users with
known problems with their biometric data (e.g., users with calloused ﬁngers or
arthritis of the hand). Such users will have low weights attached with certain
biometric traits and, therefore, the intruder has to spoof only these traits having

higher weights.

 

3. While acquiring biometric data from a user, certain extraneous (non-biometric)
information could also be used to verify the claimed identity. For example, if
a certain user typically enters a high-security room only during the day, then
the system could raise a flag when the user attempts to access the facility at
night. At this time, additional more—expensive biometric measurements may be

obtained to facilitate access.

4. The techniques mentioned in the chapter could also be used for a uni-biometric
system. For example, a minutiae-based ﬁngerprint matcher could learn to
weight various regions of a user’s ﬁngerprint differently by merely observing

matching minutiae pairs.

5.5 Summary

In this chapter we have demonstrated the following:

136

1. The performance of a biometric system can be enhanced by computing user-
speciﬁc thresholds. These thresholds may be computed for individual biometric
traits, or may be computed after consolidating the scores provided by individual

traits. This improves user convenience by reducing the false reject rate.

2. The performance can be further improved by assigning user—speciﬁc weights to
the various traits when combining the matching scores. This weighting can be

computed from the training data of every user.

Multibiometrics eliminates the failure to enroll problem. By assigning smaller
weights to those traits for which a user’s sample are consistently noisy, one can ac-
commodate more people in the system. These parameters can be estimated from the
training data provided by the user. Future work could involve looking at ways to
perform template selection and template update. The choice of templates to repre-
sent feature sets, and the methodology initiated to update them would help improve
system performance (and user convenience) over a period of time. However, auto-
matic template selection (and update) has to be done in a reliable manner to prevent
unauthorized users from progressively replacing the biometric template of a legitimate
user with their traits.

The evidence presented by multiple traits can be used in different ways depending
on whether the authentication scheme requires identifying the individual or verifying
the claimed identity. As observed earlier, identiﬁcation potentially requires matching
the extracted feature set against all templates (identities) in the database in order to

ﬁnd out the best match. This could be prohibitive in terms of the number of compar-

137

......-_ -- ._ my

'1. 9-

 

 

 

isons to be performed (especially when feature sets of multiple traits are involved),
resulting in a slow response time which is ill—suited in a real-time identiﬁcation sys-
tem. To circumvent this, an indexing scheme, wherein the extracted feature set is
compared against a small subset of the database, is used to reduce the number of
comparisons to be performed and improve processing time. Hong and Jain [86] use a
face matching system to retrieve the top 5 matches for a user’s identity; a ﬁngerprint
matcher is then applied to these 5 matches, and a ﬁnal decision made by combining
the scores provided by these two matchers. Thus, the face and ﬁngerprint systems
Operate in the cascade mode, where one system is used to narrow down the number
of possible identities, before the other is used. In a veriﬁcation scheme, on the other
hand, indexing is not required since the extracted feature set has to be compared
with only those templates corresponding to the claimed identity. In such systems the
feature sets extracted from multiple traits may be simultaneously used to produce
matching scores which are then consolidated to arrive at a decision. The individ-
ual biometric systems, in this case, Operate in the parallel mode. The techniques

presented in this chapter are more suited for a veriﬁcation system.

138

 

Chapter 6

Conclusions and Future Work

6.1 Research Contributions

Researchers have invested a substantial amount of effort in studying ﬁngerprints in
the context of forensics, computer vision, image processing, pattern recognition, and
biometrics. This seemingly simple pattern of ridges and valleys on the tip of a ﬁnger
has, therefore, received considerable attention. In spite of this attention, the problem
of automatic ﬁngerprint matching continues to harbor plenty of challenges.

In this thesis we have approached the challenges in ﬁngerprint matching from an
information fusion perspective. We ﬁrst developed a hybrid matcher that combined
the minutiae and texture information present in a ﬁngerprint. In the prOposed tech-
nique, the texture information was represented using ridge feature maps which could
also be utilized to align and register pairs of ﬁngerprint images. The hybrid system
presented here was shown to enhance the matching performance of a ﬁngerprint sys-
tem. One of the advantages of using a hybrid approach is the complementary nature

139

 

of the information being combined. This aids in decreasing the false accept rate (i.e.,
the false match rate) as follows: by examining the underlying ridge information via
ridge feature maps after aligning the images using minutiae points, the integrity of
the matcher is improved.

We then described a mosaicking scheme that integrated the information present in
two impressions of a ﬁnger. In this technique, ﬁngerprint images were viewed as range
images, and the iterative control point (ICP) algorithm was used to register them. The
technique presented here utilized minutiae points to determine an initial alignment
between image pairs. The mosaicking process resulted in a composite template which
was more elaborate than the individual images. Mosaicking is an essential component
of a ﬁngerprint system since it elegantly consolidates the information available in
several partial prints.

To account for non—linear distortions in ﬁngerprints, an “average” deformation
model was proposed. In this approach, a ﬁngerprint impression (baseline) was com-
pared with several other impressions of the same ﬁnger in order to determine the
“relative” non-linear deformation present in it. The average deformation model was
developed using thin-plate splines (TPS) and ridge curves were used to establish cor-
respondences between image pairs. The estimated average deformation was utilized
to pre—distort the minutiae points in the template image before matching it with the
minutiae points in the query image. The use of an average deformation model re-
sulted in a better alignment between the template and query minutiae points. An
index of deformation was also deﬁned for choosing the deformation model with the

least variability from a set of template impressions corresponding to a ﬁnger.

140

.'. O

 

 

Finally, the ﬁngerprint evidence of a user was combined with the face and hand
geometry traits to design a multibiometric system. A multibiometric system not
only improves matching performance as was demonstrated in this thesis, but it also
addresses the problem of non-universality and spooﬁng that are prevalent in unimodal
systems. Evidence consolidation was done at the matching score level in which the
matching scores generated by the various matchers were combined. The matching
performance was further improved by employing user-speciﬁc weights and user-speciﬁc

thresholds in the matching stage.

6.2 Future Research

Signiﬁcant efforts are currently being undertaken to integrate biometrics into the
fabric of society (e.g., National ID card, US-VISIT program, etc). It is, therefore,
imperative that researchers and practitioners systematically study the engineering
aspects of biometric systems that would ensure their successful installation in real-
world applications. The social and legal implications of biometric systems will also
have to be separately studied and understood, before deploying these systems on a
large scale.

We conclude this thesis by suggesting possible ways in which the research pre-

sented here may be expanded in order to build robust ﬁngerprint (biometric) systems.

1. The hybrid matcher utilizes square tessellations to compare the texture (i.e.,
ridge ﬂow) information across images. In view of the non-linear deformations

present in ﬁngerprint images, it would be instructive to ‘distort’ the square

141

 

cells in a non-linear fashion prior to the matching process. In fact, the average
deformation model suggested in this thesis may be used to pre—distort the square

tessellations in the template image.

. The performance of the hybrid matcher is closely related to the accuracy of the
image registration (alignment) process. In the procedure presented in this the-
sis, it is the minutiae points that are used to accomplish registration. However,
for the sake of robustness, multiple alignment hypothesis may be used to de-
termine the transformation parameters that best relate two ﬁngerprint images.
For example, the minutiae points, ridge curves, orientation ﬁeld, ridge feature
maps and singular points could all be used to generate an alignment hypoth-
esis. These various hypothesis may then be consolidated to recover the true
transformation parameters. The availability of multiple alignment hypothesis

is especially useful when poor quality ﬁngerprint images are involved.

. The ﬁngerprint mosaicking technique utilizes partial impressions of a ﬁngerprint
to construct a more elaborate one. Given several partial impressions of a ﬁnger,
there is no systematic technique for determining which of these should be used
for generating the composite template. Thus, a method to automatically select
candidate impressions for mosaicking would improve the integrity of the com-
posite template. The candidate selection process could also be used to perform

automatic template selection and update in a biometric system.

. The average deformation model for a ﬁngerprint may be used to detect the

presence of a fake ﬁnger on the sensor. The minutiae points on a fake ﬁngertip

142

 

may not be distorted in the same way as those present on a live ﬁngertip. (This
is true, for example, when the material used to synthesize the fake ﬁngerprint
does not exhibit “skin-like” properties). Therefore, the system may request a
user to present multiple impressions of a ﬁnger during veriﬁcation and derive the
relative non-linear distortion between the acquired impressions. These distor-
tions can then be compared with the average deformation model for the ﬁnger
in order to observe if they are similar. A lack of similarity might indicate the

presence of a fake ﬁnger.

. The effect of score normalization on the matching performance of a multibio-
metric system has to be studied. In this thesis, a simple min-max normalization
technique is utilized to transform the matching scores of multiple modalities into
a common domain (i.e., all matching scores are mapped in a linear fashion to
the [0,100] range). However, other robust normalization techniques have to be

examined in order to offset the effect of outliers on the matching performance.

. Fusion at the matching score level is the most popular approach to multibio-
metrics due to the ease in accessing and consolidating the scores generated by
multiple matchers. However, fusion at the feature extraction (representation)
level is expected to be more effective due to the richer source of information
available at this level. Therefore, it is important to study the possibility of
fusing information at this level. Concatenating compatible feature sets would
be one way to integrate information at this level. Integration at this level is

not without its challenges. For example, it would be difﬁcult to concatenate

143

 

@71me '
- ‘ L - ‘
h. .
‘ 'U '1‘,

 

two incompatible feature sets like the eigen-coefﬁcients (for face) and minutiae

points (for ﬁngerprint).

7. While multibiometric systems typically integrate “typical” physiological (e.g.,
ﬁngerprint, iris, hand) and behavioral (e.g., gait, signature, voice) traits for
recognition , one could consider the use of atypical traits like the color of hair,
color of eyes, height of individual, and gender of individual in conjunction with

typical biometric traits to enhance recognition performance.

144

 

APPENDICES

145

 

Appendix A

Hand Geometry-based Biometric

System

In this appendix a biometric system that uses the geometry of a person’s hand for
recognition is described. A technique for computing the various features (invariant
to the lighting conditions of the device, presence of noise and the color of the skin)
is summarized. A prototype image acquisition system was developed to capture the

proﬁle of the hand. Experiments on a database containing 50 users is presented.

A.1 Why Hand Geometry?

The suitability of a particular biometric to a speciﬁc application depends upon sev-
eral factors [50]; among these factors, the user acceptability seems to be the most
signiﬁcant. For many access control applications, like immigration, border control
and dormitory meal plan access, very distinctive biometrics, e.g., ﬁngerprint and iris,

146

 

 

may not be acceptable for the sake of protecting an individual’s privacy. In such sit-
uations, it is desirable that the given biometric indicator be only distinctive enough
for veriﬁcation but not for identiﬁcation. As hand geometry information is not very
distinctive, it is one of the biometrics of choice in applications like those mentioned
above.

Hand geometry-based authentication is also very effective for various other rea-
sons. Almost all of the working population have hands and exception processing
for peOple with disabilities could be easily engineered [111]. Hand geometry mea-
surements are easily collectible due to both the dexterity of the hand and due to a
relatively simple method of sensing which does not impose undue requirements on
the imaging Optics. Note that good frictional Skin is required by ﬁngerprint imaging
systems, and a special illumination setup is needed by iris or retina-based identiﬁ-
cation systems. Further, hand geometry is ideally suited for integration with other
biometrics, in particular, ﬁngerprints. For instance, an identiﬁcation/ veriﬁcation sys-
tem may use ﬁngerprints for (infrequent) identiﬁcation and use hand geometry for
(frequent) veriﬁcation. It is easy to conceptualize a sensing system which can simul-

taneously capture both ﬁngerprints and hand geometry.

A.2 Background

Hand Geometry, as the name suggests, refers to the geometric structure of the hand.
This structure includes width of the ﬁngers at various locations, width of the palm,

thickness of the palm, length of the ﬁngers, etc. Although these metrics do not vary

147

 

W. .un—

signiﬁcantly across the population, they can however be used to verify the identity
of an individual. Hand geometry measurement is non-intrusive and the veriﬁcation
involves a Simple processing of the resulting features. Unlike palmprint veriﬁcation
methods [112, 113], this method does not involve extraction of detailed features of
the hand (for example, wrinkles on the skin).

Hand geometry-based veriﬁcation systems are not new and have been available
Since the early 19703. However, there is not much open literature addressing the
research issues underlying hand geometry-based identity authentication; much of the
literature is in the form of patents [114, 115, 116] or application-oriented description.
Sidlauskas [117] discusses a 3D hand proﬁle identiﬁcation apparatus that has been
used for hand geometry recognition.

Authentication of identity of an individual based on a set of hand features is
an important research problem. It is well known that the individual hand features
themselves are not very descriptive; devising methods to combine these non-salient
individual features to attain robust positive identiﬁcation is a challenging pattern

recognition problem in its own right.

A.3 Image Acquisition

The image acquisition system which we have used comprises of a light source, a
camera, a single mirror and a ﬂat surface (with ﬁve pegs on it). The user places his
right hand - palm facing downwards - on the ﬂat surface of the device. The ﬁve pegs

serve as control points for appropriate placement of the right hand of the user. The

148

device also has knobs to change the intensity of the light source and the focal length
of the camera. The lone mirror projects the side-view of the user’s hand onto the
camera. The device is hooked to a PC with a GUI application which provides a live
visual feedback of the top-view and the side-view of the hand (Figure A1) and has
the following functionality: (i) assists the user in correct, positioning of the hand on
the surface of the device; (ii) acquires images of the user’s hand; (iii) displays images
that were captured previously; (iv) extracts features from a given image; (v) registers
the user in a database along with the extracted feature vector; (vi) checks whether
a given image of the hand matches any of the entries in the database; (vii) updates
a particular user’s entry in the database by recomputing the feature vector. In the
current prototype implementation, a 640 x 480 8—bit grayscale image of the hand is

captured.

 

Figure A.1: Hand geometry sensing device.

149

A.3. 1 Enrollment Phase

This process involves one of the following two tasks: (i) add a new user to the
database; (ii) update a current user’s feature vector. During the enrollment phase,
ﬁve images of the same hand are taken in succession; the user removes his hand com-
pletely from the device before every acquisition. These ﬁve images are then used to
compute the feature vector of the given hand. Recomputing a feature vector simply

involves averaging the individual feature values.

A.3.2 Veriﬁcation Phase

This process involves matching a given hand to a person previously enrolled in the
system. Two snapshots of the hand are taken and the “average” feature vector is
computed. The given feature vector is then compared with the feature vector stored
in the database associated with the claimed identity. Let F = (f1, f2, ..., fd) represent
the d-dimensional feature vector in the database associated with the claimed identity
and Y = (y1,y2, ..., yd) be the feature vector of the hand whose identity has to be
veriﬁed. The veriﬁcation is positive if the distance between F and Y is less than a

threshold value. Four distance metrics, absolute, weighted absolute, Euclidean, and

150

 

weighted Euclidean, corresponding to the following four equations were explored:

 

 

d

Zl yj _ fjl < Ear (Al)
j=1

d
32:; l ij-jfj I < 6mm (A.2)
2(yj—fjl2 < emand (A.3)
j=1

d a — n2

\ Z J 02 J < (we: (A.4)

i=1 ,

 

where a]? is the feature variance of the j th feature and ea, em, 68, and 6m are threshold

values for each respective distance metric. .

A.4 Feature Extraction

The hand geometry-based authentication system relies on geometric invariants of a
human hand. Typical features include length and width of the ﬁngers, aspect ratio of
the palm or ﬁngers, thickness of the hand, etc. [118]. To our knowledge, the existing
commercial systems do not take advantage of any non-geometric attributes of the
hand, e.g., color of the skin.

Figure A.2 shows the 16 axes along which the various features mentioned above
have been measured. The ﬁve pegs on the image serve as control points and assist
in choosing these axes. The hand is represented as a vector of the measurements
selected above. Since the positions of the ﬁve pegs are ﬁxed in the image, no attempt

is made to remove these pegs in the acquired images.

151

 

 

 

Figure A2: The sixteen axes along which feature values are computed.

In order to offset the effects of background lighting, color of the skin, and noise,
the following approach was devised to compute the various feature values. A sequence
of pixels along a measurement axis will have an ideal gray scale proﬁle as shown in
Figure A.3(a). Here Len refers to the total number of pixels considered, P, and Pa
refer to the end points within which the object (viz., ﬁnger) to be measured is located,

and A1, A2 and B are the gray scale values.

The actual gray scale proﬁle tends to be spiky as shown in Figure A.3(b). Our
ﬁrst step is to model the above proﬁle. Let the pixels along a measurement axis be
numbered from 1 to Len. Let X = (£131,152, ...,:cLen) be the gray values of the pixels

along that axis. We make the following assumptions about the proﬁle:

1. The observed proﬁle (Figure A.3(b)) is obtained from the ideal proﬁle (Figure
A.3(a)) by the addition of Gaussian noise to each of the pixels in the latter.

Thus, for example, the gray level of a pixel lying between P, and R. is assumed

152

 

 

 

 

 

 

 

 

 

ll
A2 -----------------------------

u:

:>

2'

> A1

g

V)

>..

<

a:

o

a ..............
P8 P0 PIXEL NUMBER
(a) The ideal proﬁle
ll

m

D

2‘

>

El

<

L)

U)

>-

<

M

o

 

 

V

PIXEL NUMBER

(b) An observed proﬁle

 

Figure A3: The gray scale proﬁle of pixels along a measurement axis.

153

to be drawn from the distribution

(lbs/8,023) = —2\/__1_—_2_exp {ﬁts — B)2} (A.5)
W08 0

where 0% is the variance of a: in the interval R, P, < R 3 P8.

2. The gray level of an arbitrary pixel along a particular axis is independent of the
gray level of other pixels in the line. This assumption holds good because of

the absence of pronounced Shadows in the acquired image.

Operating under these assumptions, we can write the joint distribution of all the pixel
values along a particular axis as

Per/e): 1:1— 7277...” xp-{ —’—(.—A1>2}]

ﬁll-flamﬂp xp—U —g%(18)2}1 (A'G)

' Len

Hv— {Price-AWN,

 

 

where 9 = (P3, Pe,A1, A2, B, 031,032,0f3) and of“, 0342 and of; are the variances of
x in the three intervals [1, P3], [P3 + 1, P6] and [PC + 1, Len], respectively.
The goal now is to estimate P, and P8 using the observed pixel values along the

chosen axis. We use the Maximum Likelihood Estimate (MLE) method to estimate

6. By taking logarithm on both sides of Eq. (A6) and simplifying, we obtain the

154

likelihood function:

P3 PC

1 1
14(9) =—2' 203:“ — All2 + '7 2017:“ — B)2
0A1 1 03 Pa‘l'l
Len
+ -1— : (...,. _ .492 + 10.10903, (A.7)
0A2 P +1

+ (P. - P.) log 0%, + (Len —- P.) log 03,,

The parameters can now be estimated iteratively; the parameter estimates at the

(k + 1)" stage, given the observation X = ($1,232, ..., :cLen), are given below.

Ak A k A 1:
AU...” P,,P.( ’,A1‘ ),A2( ’
s = argminL
P. ’7“) 706) $06)

k
B()!OA1 10.42 308

 

 

 

 

k+l Ak
AM, P( ),Pe,A1k) ,A2(),
P" = arg ”PinL (k) Ark) (k)
30010311 0A2 ’08
Ark“)
PC
A Ark“) 331'
B(k+l) _ Pa +1
_ 3(k+l)_wﬁ-(k+l)
e for“) 8
(7%“) = E(k+l)+1$j _{§(k+1))}2
B 3a“) '50:“)
e _ s
A(k+l)
230:“) _ f‘ 3:,-
— Ak+l
P: )
Z:A(Ic+1)x
’T(k+l) /\1(k+1)
0A1 : Z:’\(k‘_—+__l)xJ 2_{Al }2
@(k-l-l) = Zéﬁ+ll+1$j
A(k+1)
Len—P
Arm) ZE‘“+”+1$ ' A(k+1) 2
0312 = Le Efk‘l'l) —{A2 } (A.8)
en—

155

\-

 

 

The initial estimates of A1, of“, A2, 03,2, B and 0% are obtained as follows: (i)
A1 and 03“ are estimated using the gray values of the ﬁrst N M pixels along the axis;
(ii) A2 and 0312 are estimated using the gray values of the pixels from (Len — N A2)
to Len; (iii) B and 0% are estimated using the gray values of the pixels between
(Len/2 — N3) and (Len/2 + NB). The values of NM, Mg and N3 are ﬁxed for the
system; N,“ = 5, NA; = 4 and N3 = 5. The initial values of P, and P. are set to

Len/2 — 10 and Len/2 + 10, respectively.

Figure A.4 shows a hand image along with the positions of detected points (P,

and Fe) along each of the 16 axes and the corresponding feature vector.

 

(8.) Estimates of P, and PC along the 16 axes

(ahsapuv 65 53 59 52 62 47 47 45 255 333 253 287 243 149 34 35)

(b) The corresponding database entry

Figure A.4: Computation of the feature vector.

156

 

10

Figure A.5: Chernoff Faces representing the average feature vectors of 20 different

hands.

157

_t .5 ...L
(A) N -"

14

0

15

_s ..s _s
O N a)

.3
CO

”0
O

 

 

A.5 Experimental Results

The hand geometry authentication system was trained and tested using a database
of 50 users. Ten images of each user’s hand were captured over two sessions; in
each session the background lighting of the acquisition device was changed. Thus
a total of 500 images were made available. Out of 500 images, only 360 were used
for testing our hand geometry system. The remaining 140 images were discarded
due to incorrect placement of the hand by the user (see for example, Figure A.6).
Thus, user adaptation of this biometric is necessary. Two images of each user’s hand
were randomly selected to compute the feature vector which is stored in the database
along with the user’s name. Figure A.5 shOws the Chernoff faces [4] representing the
average feature vector of 20 of the users. 15 hand features have been mapped to the
attributes of the cartoon face as follows: 1-area of face; 2-shape of face; 3-length of
nose; 4-location of mouth; 5—curve of smile; 6-width of mouth; 7, 8, 9, 10 and 11-
location, separation, angle, shape and width of eyes; 12-location and width of pupil;
13, 14 and 15 -location, angle and width of eyebrow. The difference between any two

hand geometries as reﬂected in these cartoon faces appears to be signiﬁcant.

EqS. (A.1)— (4) are used for verifying whether the feature vector of a hand matches
with the feature vector stored in the database. In order to study the effectiveness
of various distance metrics, the genuine and impostor distributions are plotted for
matching scores obtained using each distance metric and an ROC curve generated
from each pair of distributions. A genuine matching score is obtained by comparing

two feature vectors from the same hand while an impostor matching score is obtained

158

 

 

 

Figure A.6: Incorrect placement of hand.

by comparing the feature vectors of two different hands. Let us deﬁne the hit rate
to be the percentage of time the system matches a hand to the right entry in the
database, and the false acceptance rate to be the percentage of time the system
matches a hand to an incorrect entry in the database for a given threshold. The
ROC curve that plots the hit rate against the false acceptance rate is then computed
using the leave-one-out method. A feature vector in the database is matched against
those feature vectors representing a different user. The minimum of these distances
is taken as an impostor matching score. If the matching score falls below the chosen
threshold, it is considered to be a false acceptance by the system. This process is
repeated for all the users in the database. A genuine matching score is obtained
by matching a feature vector against those feature vectors that belong to the same
user and then taking the minimum of all such distances. If the matching score falls

below the chosen threshold then it is considered to be a hit. The ROC curve shown in

159

Figure A.7 depicts the performance of the system for the weighted Euclidean distance
(Eq. A.4) which gave the best result. The system performance could be signiﬁcantly
improved by (i) having habituated users; (ii) better registration of hand geometry
measurements; and (iii) using higher level features (like color of the skin, wrinkles
and folds on the skin etc.). Among these factors, registration appears to be the most
critical. Even though the pegs are used for registration in our system, the registration

accomplished by the pegs is not sufficiently accurate.

 

 

 

 

 

90»-

mi-
:5 70»
E
(‘1‘ so] .
g 50- ]
é 40F
o 30*

20>

10L

c0 20 4O 60 80 100

Falsemmnatem)

Figure A.7: The ROC curve depicting the matching performance of the hand geom-
etry system.

160

 

 

BIBLIOGRAPHY

161

Bibliography

[1] A. K. Jain, L. Hong, and R. Bolle, “On-line ﬁngerprint veriﬁcation,” IEEE
Transactions on PAMI, vol. 19, pp. 302—314, April 1997.

[2] L. Hong, “Automatic personal identiﬁcation using ﬁngerprints,” PhD Thesis,
Michigan State University, 1998.

[3] R.-—L. Hsu, “Face detection and modeling for recognition,” PhD Thesis, Michi-
gan State University, 2002.

[4] H. Chernoff, “The use of faces to represent points in k-dimensional space graph-
ically,” Journal of the American Statistical Association, vol. 68, pp. 361—368,
1973. '

[5] A. K. Jain, R. Bolle, and S. Pankanti, eds, Biometrics: Personal Identiﬁcation
in Networked Society. Kluwer Academic Publishers, 1999.

[6] J. L. Wayman, “Fundamentals of biometric authentication technologies,” In-
ternational Journal of Image and Graphics, vol. 1, no. 1, pp. 93-113, 2001.

[7] L. O’Gorman, “Seven issues with human authentication technologies,” in Proc.
of Workshop on Automatic Identiﬁcation Advanced Technologies (AutoID),
(Tarrytown, New York), pp. 185—186, Mar 2002.

[8] R. Yasin, “Password pain relief,” Information Security Magazine, April 2002.
Available at http: //www.infosecurityrnag.com/2002/apr/cover.shtml.

[9] J. Daugman, “Statistical demands of identiﬁcation versus veriﬁcation.” Avail-
able at http://www.cl.cam.ac.uk/userS/jgd1000/veri/veri.html.

[10] “Schiphol backs eye scan security.” CNN World News, March 27 2002. Available
at http: / / www.cnn.com / 2002 / WORLD / europe/ 03 / 27 / schiphol.security/ .

[11] J. Daugman, “Recognizing persons by their iris patterns,” in Biometrics:
Personal Identiﬁcation in a Networked Society (A. K. Jain, R. Bolle, and
S. Pankanti, eds), pp. 103—121, Kluwer Academic Publishers, 1999.

[12] J. Berry and D. A. Stoney, “The history and development of ﬁngerprinting,”
in Advances in Fingerprint Technology (H. C. Lee and R. Gaensslen, eds),
pp. 1—40, Florida: CRC Press, 2nd ed., 2001.

162

 

[13] Federal Bureau of Investigation, The Science of Fingerprints: Classiﬁcation and
Uses. Washington, DC, 1984. US. Government Printing Ofﬁce.

14 S. Pankanti, S. Prabhakar, and A. K. Jain, “On the individuality of ﬁnger-
[
prints,” IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 24, no. 8, pp. 1010—1025, 2002.

[15] A. K. Jain, S. Prabhakar, and S. Pankanti, “On the similarity of identical twin
ﬁngerprints,” Pattern Recognition, vol. 35, no. 8, pp. 2653-2663, 2002.

[16] K. Karu and A. K. Jain, “Fingerprint classiﬁcation,” Pattern Recognition,
vol. 29, no. 3, pp. 389—404, 1996.

[17] A. Senior, “A combination ﬁngerprint classiﬁer,” IEEE Transactions on PAMI,
vol. 23, pp. 1165—1174, Oct 2001.

[18] Z. M. Kovacs-Vajna, “A ﬁngerprint veriﬁcation system based on triangular
matching and dynamic time warping,” IEEE Transactions on PAMI, vol. 22,
pp. 1266—1276, Nov 2000.

[19] F. Pernus, S. Kovacic, and L. Gyergyek, “Minutiae-based ﬁngerprint recogni-
tion,” in Proceedings of the Fifth International Conference on Pattern Recogni-
tion, pp. 1380—1382, 1980. '

[20] B. Mehtre and M. Murthy, “A minutiae based ﬁngerprint identiﬁcation system,”
in Proceedings of the Second International Conference on Advances in Pattern
Recognition and Digital Techniques, (Calcutta, India), January 1986.

[21] A. Sibbald, “Method and apparatus for ﬁngerprint characterization and recog-
nition using auto-correlation pattern,” US Patent 5633947, 1994.

[22] A. Stoianaov, C. Soutar, and A. Graham, “High-speed ﬁngerprint veriﬁcation
using an optical correlator,” in Proceedings SPIE, vol. 3386, pp. 242—252, 1998.

[23] D. Roberge, C. Soutar, and B. Vijaya Kumar, “High-speed ﬁngerprint veriﬁca-
tion using an optical correlator,” in Proceedings SPIE, vol. 3386, pp. 123—133,
1998.

[24] A. M. Bazen, G. T. B. Verwaaijen, S. H. Gerez, L. P. J. Veelenturf, and B. J. van
der Zwaag, “A correlation-based ﬁngerprint veriﬁcation system,” in Proceedings
of the ProR1502000 Workshop on Circuits, Systems and Signal Processing,
(Veldhoven, Netherlands), Nov 2000.

[25] L. O’Gorman, “Fingerprint veriﬁcation,” in Biometrics: Personal Identiﬁcation
in a Networked Society (A. K. Jain, R. Bolle, and S. Pankanti, eds), pp. 43—64,
Kluwer Academic Publishers, 1999.

[26] M. Trauring, “Automatic comparison of ﬁnger-ridge patterns,” Nature, pp. 938—
940, 1963.

163

[27] C. Shelman, “Machine classiﬁcation of ﬁngerprints,” in Proceedings of the First
National Symposium on Law Enforcement Science and Technology, pp. 467—477,
1967.

[28] A. Grasselli, “On the automatic classiﬁcation of ﬁngerprints - some considera-
tions on the linguistic interpretation of pictures,” in Methodologies of Pattern
Recognition (S. Watanabe, ed.), pp. 253—273, Academic Press, 1969.

[29] A. K. Jain, S. Prabhakar, L. Hong, and S. Pankanti, “Filterbank-based ﬁnger-
print matching,” IEEE Transactions on Image Processing, vol. 9, pp. 846—859,
May 2000.

[30] A. K. Jain, A. Ross, and S. Prabhakar, “Fingerprint matching using minutiae
and texture features,” in Proc. International Conference on Image Processing
(ICIP), (Thessaloniki, Greece), pp. 282—285, Oct 2001.

[31] J. Daugman, “Uncertainty relation for resolution in space, spatial frequency,
and orientation Optimized by two-dimensional visual cortical ﬁlters,” Journal
of the Optical Society of America, vol. 2, pp. 1160—1169, 1985.

[32] S. Klein and B. Beutter, “Minimizing and maximizing the joint space-spatial
frequency uncertainty of gabor—like functions: Comment,” Journal of the Opti-
cal Society of America, vol. 9, no. 2, pp. 337—340, 1992.

[33] L. Hong, Y. Wan, and A. K. Jain, “Fingerprint image enhancement: Algorithms
and performance evaluation,” IEEE Transactions on PAMI, vol. 20, pp. 777-
789, Aug 1998.

[34] D. Sherlock, D. M. Monro, and K. Millard, “Fingerprint enhancement by di-
rectional fourier ﬁltering,” IEE Proceedings on Vision, Image and Signal Pro-
cessing, vol. 141, no. 2, pp. 87—94, 1994.

[35] R. L. Graham, “An efﬁcient algorithm for determining the convex hull of a ﬁnite
planar set,” Information Processing Letters, vol. 1, no. 4, pp. 132—133, 1972.

[36] J. Kittler, M. Hatef, R. P. Duin, and J. G. Matas, “On combining classiﬁers,”
IEEE Transactions on PAMI, vol. 20, pp. 226—239, Mar 1998.

[37] R. Germain, A. Califano, and S. Colville, “Fingerprint matching using trans-
formation parameters,” IEEE Computational Science and Engineering, vol. 4,
no. 4, pp. 42-49, 1997.

[38] B. Bhanu and X. Tan, “A triplet based approach for indexing of ﬁngerprint
database for identiﬁcation,” in Proc. Third International Conference on Au-
dio and Video-based Biometric Person Authentication (AVBPA), (Halmstad,
Sweden), pp. 205—210, Jun 2001.

164

[39] R. Cappelli, D. Maio, and D. Maltoni, “Fingerprint classiﬁcation by directional
image partitioning,” IEEE Transactions on PAMI, vol. 21, no. 5, pp. 402—421,
1999.

[40] A. Ross, A. K. Jain, and J. Reisman, “A hybrid ﬁngerprint matcher,” in Proc.
of the International Conference on Pattern Recognition (I CPR), (Quebec City,
Canada), Aug 2002.

[41] A. Ross, A. K. Jain, and J. Reisman, “A hybrid ﬁngerprint matcher,” Pattern
Recognition, vol. 36, pp. 1661—1673, Jul 2003.

[42] N. K. Ratha, J. H. Connell, and R. M. Bolle, “Image mosaicing for rolled
ﬁngerprint construction,” in Proc. of 14th International Conference on Pattern
Recognition, vol. 2, pp. 1651—1653, 1998.

[43] P. J. Besl and N. D. Mckay, “A method for registration of 3-D shapes,” IEEE
Transactions on PAMI, vol. 14, pp. 239-256, February 1992.

[44] L. G. Brown, “A survey of image registration techniques,” ACM Computing
Surveys, vol. 24, no. 4, pp. 325—376, 1992.

[45] B. Vemuri and J. Aggarwal, “3—D model construction from multiple views using
range and intensity data,” in Proc. of IEEE Conference on Computer Vision
and Pattern Recognition, pp. 435-437, 1986.

[46] P. J. Besl, “The freeform surface matching problem,” in Machine Vision for
Three-Dimensional Scenes (H. Freeman, ed.), pp. 25—71, New York: Academic
Press, 1990.

[47] J. B. A. Maintz and M. A. Viergever, “A survey of medical image registration,”
Medical Image Analysis, vol. 4, no. 1, pp. 1-36, 1998.

[48] T. S. Huang, D. B. Goldgof, and H. Lee, “Feature extraction and terrain match-

ing,” in Proc. of the IEEE conference on Computer Vision and Pattern Recog-
nition, pp. 899—904, June 1988.

[49] Y. Chen and G. Medioni, “Object modelling by registration of multiple range
images,” Image and Vision Computing, vol. 10, pp. 145—155, April 1992.

[50] A. K. Jain, L. Hong, S. Pankanti, and R. Bolle, “An identity authentication
system using ﬁngerprints,” Proceedings of the IEEE, vol. 85, no. 9, pp. 1365—
1388, 1997.

[51] B. K. P. Horn, “Closed-form solution of absolute orientation using unit quater-
nions,” Journal of the Optical Society of America, vol. 4, pp. 629—642, April
1987.

[52] A. K. Jain and A. Ross, “Fingerprint mosaicking,” in Proc. of IEEE Inter-
national Conference on Acoustics, Speech, and Signal Processing (ICASSP),
(Orlando, Florida), May 2002.

165

[53] D. Maio and D. Maltoni, “Direct gray-scale minutiae detection in ﬁngerprints,”
IEEE Transactions on PAMI, vol. 19, pp. 27—40, Jan 1997.

[54] N. K. Ratha and R. M. Bolle, “Effect of controlled acquisition on ﬁngerprint
matching,” in Proceedings of the International Conference on Pattern Recogni-
tion, vol. 2, (Brisbane, Australia), pp. 1659—1661, 1998.

[55] C. Dorai, N. Ratha, and R. Bolle, “Detecting dynamic behavior in compressed
ﬁngerprint videos: Distortion,” in Proceedings of Computer Vision and Pattern
Recognition, pp. 320—326, Jun 2000.

[56] L. R. Thebaud, “Systems and methods with identity veriﬁcation by comparison
and interpretation of skin patterns such as ﬁngerprints,” US Patent 5,909,501,
1999.

[57] A. M. Bazen and S. Gerez, “Fingerprint matching by thin-plate spline modelling
of elastic deformations,” Pattern Recognition, vol. 36, pp. 1859—1867, August
2003.

[58] A. Senior and R. Bolle, “Improved ﬁngerprint matching by distortion removal,”
IEICE Transactions on Information and Systems, vol. E84—D, pp. 825—831, Jul
2001.

[59] C. Watson, P. Grother, and D. Cassasent, “Distortion-tolerant ﬁlter for elastic-
distorted ﬁngerprint matching,” in Proceedings of SPIE Optical Pattern Recog-
nition, pp. 166—174, 2000.

[60] R. Cappelli, D. Maio, and D. Maltoni, “Modelling plastic distortion in ﬁnger-
print images,” in Proceedings of the Second International Conference an Ad-
vances in Pattern Recognition (ICAPR), (Rio de Janeiro), Mar 2001.

[61] R. Cappelli, R. Erol, D. Maio, and D. Maltoni, “Synthetic ﬁngerprint-image
generation,” in Proceedings of the 15th International Conference on Pattern
Recognition (ICPR), vol. 3, (Barcelona, Spain), Sep 2000.

[62] D. J. Burr, “A dynamic model for image registration,” Computer Graphics and
Image Processing, vol. 15, pp. 102—112, 1981.

[63] L. Younes, “Optimal matching between shapes via elastic deformations,” Image
and Vision Computing, vol. 17, pp. 381—389, 1999.

[64] J. L. Barron, D. J. Fleet, and S. S. Beauchemin, “Performance of optical ﬂow
techniques,” International Journal Computer Vision, vol. 12, pp. 43—77, 1994.

[65] G. E. Christensen, R. D. Babbitt, and M. I. Miller, “Deformable templates using
large deformation kinetics,” IEEE Transactions on Image Processing, vol. 5,
pp. 1435-1447, 1996.

166

 

[66] S. C. Joshi and M. 1. Miller, “Landmark matching via large deformation diffeo—
morphisms,” IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 9, pp. 1357—1370, 2000.

[67] Y. Amit, U. Grenander, and M. Piccioni, “Structural image restoration through
deformable templates,” Journal of American Statistical Association, vol. 86,
pp. 376-387, 1991.

[68] J. M. Cartensen, “An active lattice model in a Bayesian framework,” Computer
Vision and Image Understandng, vol. 63, no. 2,.pp. 380—387, 1996.

[69] C. A. Glasbey and K. V. Mardia, “A penalized likelihood approach to image
warping,” Journal of the Royal Statistical Society. Series B. Statistical Method-
ology, vol. 63, no. 3, pp. 465-514, 2001.

[70] F. L. Bookstein, “Principal warps: thin-plate splines and the decomposition of
deformations,” IEEE Transactions on Pattern Analysis and Machine Intelli-
gence, vol. 11, pp. 567—585, 1989.

[71] K. V. Mardia and T. J. Hainsworth, “Image warping and Bayesian reconstruc-
tion with gray-level templates,” in Statistics and Images: Volume 1 (K. V.
Mardia and G. K, Kanji, eds.), pp. 257—280, Carfax, Oxford, 1993.

[72] K. V. Mardia, T. J. Hainsworth, and J. F. Haddon, “Deformable templates
in image sequences,” Proceedings of the International Conference on Pattern
Recognition (ICPR), pp. 132—135, 1992.

[73] A. Almansa and L. Cohen, “Fingerprint image matching by minimization of a
thin-plate energy using a two-step algorithm with auxiliary variables,” IEEE
Workshop on Appl. of Comp. Vision (WACV ’00), pp. 35—40, December 2000.

[74] I. L. Dryden and K. V. Mardia, Statistical Shape Analysis. John Wiley and
Sons,1998.

[75] D. Maio, D. Maltoni, R. Cappelli, J. L. Wayman, and A. K. Jain, “FVC2002:
Fingerprint veriﬁcation competition,” in Proceedings of the International Con-
ference on Pattern Recognition (ICPR), (Quebec City, Canada), pp. 744—747,
August 2002.

[76] W. Bicz, Z. Gumienny, D. Kosz, and M. Pluta, “Ultrasonic setup for ﬁngerprint
patterns detection and evaluation,” Acoustical Imaging, vol. 22, 1996.

[77] E. den Os, H. Jongebloed, A. Stijsiger, and L. Boves, “Speaker veriﬁcation as a
user-friendly access for the visually impaired,” in Proceedings of the European
Conference on Speech Technology, (Budapest), pp. 1263—1266, 1999.

[78] D. A. Black, “Forgery above a genuine signature,” Journal of Criminal Law,
Criminology, and Police Science, vol. 50, pp. 585-590, 1962.

167

 

[79] W. Harrison, Suspect Documents, Their Scientiﬁc Examination. Nelson-Hall
Publishers, 1981.

[80] A. Eriksson and P. Wretling, “How ﬂexible is the human voice? A case study

of mimicry,” in Proceedings of the European Conference on Speech Technology,
(Rhodes), pp. 1043-1046, 1997.

[81] T. Matsumoto, H. Matsumoto, K. Yamada, and S. Hoshino, “Impact of artiﬁcial

gummy ﬁngers on ﬁngerprint systems,” in Proceedings SPIE, vol. 4677, (San
Jose, USA), pp. 275—289, Feb 2002.

[82] P. J. Philips, P. Grother, R. J. Micheals, D. M. Blackburn, E. Tabassi, and
M. Bone, “Frvt 2002: Overview and summary,” Technical Report available at
http: //www.frvt.org/frvt2002/documents.htm, 2003.

[83] A. Martin and M. Przybocki, “The NIST 1999 speaker recognition evaluation
- an overview,” Digital Signal Processing, vol. 10, pp. 1—18, 2000.

[84] L. Hong, A. K. Jain, and S. Pankanti, “Can multibiometrics improve perfor-
mance?,” in Proceedings AutoID ’99, (Summit(NJ), USA), pp. 59-64, Oct 1999.

[85] L. I. Kuncheva, C. J. Whitaker, C. A. Shipp, and R. P. W. Duin, “Is indepen-
dence good for combining c1assiﬁers?,” in Proc. of the International Conference
on Pattern Recognition (ICPR), vol. 2, (Barcelona, Spain), pp. 168—171, 2001.

[86] L. Hong and A. K. Jain, “Integrating faces and ﬁngerprints for personal iden-
tiﬁcation,” IEEE Transactions on PAMI, vol. 20, pp. 1295—1307, Dec 1998.

' [87] R. Brunelli and D. Falavigna, “Person identiﬁcation using multiple cues,” IEEE
Transactions on PAMI, vol. 12, pp. 955—966, Oct 1995.

[88] E. Bigun, J. Bigun, B. Duc, and S. Fischer, “Expert conciliation for multimodal
person authentication systems using Bayesian Statistics,” in First International
Conference on AVBPA, (Grams-Montana, Switzerland), pp. 291—300, March
1997.

[89] R. W. Frischholz and U. Dieckmann, “Bioid: A multimodal biometric identiﬁ-
cation system,” IEEE Computer, vol. 33, no. 2, pp. 64-68, 2000.

[90] T. K. Ho, J. J. Hull, and S. N. Srihari, “Decision combination in multiple
classiﬁer systems,” IEEE Transactions on PAMI, vol. 16, pp. 66—75, January
1994.

[91] S. Prabhakar and A. K. Jain, “Decision-level fusion in ﬁngerprint veriﬁcation,”
Pattern Recognition, vol. 35, no. 4, pp. 861—874, 2002.

[92] U. Dieckmann, P. Plankensteiner, and T. Wagner, “Sesam: A biometric person
identiﬁcation system using sensor fusion,” Pattern Recognition Letters, vol. 18,
no. 9, pp. 827—833, 1997.

168

 

[93] P. Verlinde and G. Cholet, “Comparing decision fusion paradigms using k-NN
based classiﬁers, decision trees and logistic regression in a multi-modal iden-
tity veriﬁcation application,” in Second International Conference on AVBPA,

(Washington DC, USA), pp. 188—193, March 1999.

[94] S. Ben-Yacoub, Y. Abdeljaoued, and E. Mayoraz, “Fusion of face and speech
data for person identity veriﬁcation,” Research Paper IDIAP-RR 99—03, IDIAP,
CP 592, 1920 Martigny, Switzerland, Jan 1999.

[95] A. K. Jain, S. Prabhakar, and S. Chen, “Combining multiple matchers for a high
security ﬁngerprint veriﬁcation system,” Pattern Recognition Letters, vol. 20,
pp. 1371—1379, 1999.

[96] Y. Zuev and S. Ivanon, “The voting as a way to increase the decision reli-
ability,” in Foundations of Information/Decision Fusion with Applications to
Engineering Problems, (Washington DC, USA), pp. 206—210, August 1996.

[97] R. Cappelli, D. Maio, and D. Maltoni, “Combining ﬁngerprint classiﬁers,” in
First International Workshop on Multiple Classiﬁer Systems, pp. 351—361, June
2000.

[98] A. K. Jain, S. Prabhakar, and L. Hong, “A multichannel approach to ﬁngerprint
classiﬁcation,” IEEE Transactions on PAMI, vol. 21, no. 4, pp. 348—359, 1999.

[99] A. K. Jain, L. Hong, and Y. Kulkarni, “A multimodal biometric system using
ﬁngerprint, face and speech,” in Second International Conference on AVBPA,
(Washington DC, USA), pp. 182—187, March 1999.

[100] F. Hampel, P. Rousseeuw, E. Ronchetti, and W. Stahel, Robust Statistics: The
Approach Based on Inﬂuence Functions. John Wiley & Sons, 1986.

[101] A. K. Jain, S. Prabhakar, and A. Ross, “Fingerprint matching: Data acquisition
and performance evaluation,” Technical Report MSU-TRz99-l4, Michigan State
University, 1999.

[102] H. Rowley, S. Baluja, and T. Kanade, “Neural network-based face detection,”
IEEE Transactions on PAMI, vol. 20, pp. 23-38, Jan 1998.

[103] G. Burel and C. Carel, “Detection and localization of faces on digital images,”
Pattern Recognition Letters, vol. 15, pp. 963—967, Oct 1994.

[104] C. Yang and T. Huang, “Human face detection in a complex background,”
Pattern Recognition, vol. 27, no. 1, pp. 53—63, 1994.

[105] M. Kirby and L. Sirovich, “Application of the Karhunen-Loeve procedure for
the characterization of human faces,” IEEE Transactions on PAMI, vol. 12,
no. 1, pp. 103—108, 1990.

169

 

[106] M. Turk and A. Pentland, “Eigenfaces for recognition,” Journal of Cognitive
Neuroscience, vol. 3, no. 1, pp. 71—86, 1991.

[107] R. J. Quinlan, C45: Programs for Machine Learning. The Morgan Kaufmann
Series in Machine Learning, Morgan Kaufmann Publishers, Oct 1992.

[108] A. Ross, A. K. Jain, and J. Qian, “Information fusion in biometrics,” in Proceed-
ings of the Third International Conference on Audio- and Video-based Person
Authentication (AVBPA), (Halmstad, Sweden), pp. 354—359, Jun 2001.

[109] A. K. Jain and A. Ross, “Learning user-speciﬁc parameters in a multibiometric
system,” in Proc. of the International Conference on Image Processing (I CIP),
(Rochester, USA), pp. 57—60, Sep 2002.

[110] A. Ross and A. K. Jain, “Information fusion in biometrics,” Pattern Recognition
Letters, vol. 24, pp. 2115—2125, Sep 2003.

[111] R. Zunkel, “Hand geometry based authentication,” in Biometrics: Personal
Identiﬁcation in Networked Society (A. K. Jain, R. Bolle, and S. Pankanti,
eds), ch. 4, pp. 87—-102, Kluwer Academic Publishers, 1998.

[112] J. Young and H. Hammon, “Automatic palmprint veriﬁcation study,” Final
Technical Report RADC-TR-81-l61, Rome Air Development Center, 1981.

[113] H. Yoshikawa and S. Ikebata, “A microcomputer-based personal identiﬁcation
system,” in International Conference on Industrial Electronics, Control, and
Instrumentation, 1984.

[114] R. Miller, “Finger dimension comparison identiﬁcation system,” US Patent
3576538, 1971.

[115] R. Ernst, “Hand id system,” US Patent 3576537, 1971.

[116] I. Jacoby, A. Giordano, and W. Fioretti, “Personnel identiﬁcation apparatus,”
US Patent 3648240, 1972.

[117] D. Sidlauskas, “3d hand proﬁle identiﬁcation apparatus,” US Patent 4736203,
1988.

[1 18] “Hasis - a hand shape identiﬁcation system.”
http: / / bias.csr.unibo.it / research / biolab / handhtml.

[119] A. K. Jain, A. Boss, and S. Pankanti, “A prototype hand geometry-based
veriﬁcation system,” in Second International Conference on Audio and Video-
based Biometric Person Authentication (AVBPA), (Washington, DC, USA),
pp. 166—171, March 1999.

170

 

-~‘...‘......,, ,. , ,

 

    

 

|"‘I]"I'|“|"‘ I ”H

3 1293 0250