Yanushkevich S.N., Wang P.S.P., Gavrilova M.L., Srihari S.N. (eds.) Image Pattern Recognition. Synthesis and Analysis in Biometrics
Подождите немного. Документ загружается.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
98 Synthesis and Analysis in Biometrics
Appendix B
The resulting filters for Q are
Q
s
=
000000···
100000···
−
2033
3000
−
49
152
0000···
2137
12000
−
289
608
−
23
208
000···
139
500
1 −
23
52
000···
139
2000
−
347
912
−
63
208
−
23
208
00···
0 −
115
228
1 −
23
52
00···
0 −
115
912
−
63
208
−
63
208
−
23
208
0 ···
Q
e
=
··· 0 −
23
208
−
63
208
−
63
208
−
115
912
0
··· 00−
23
52
1 −
115
228
0
··· 00−
23
208
−
63
208
−
347
912
139
2000
··· 00 0−
23
52
1
139
500
··· 00 0−
23
208
−
289
608
2137
12000
··· 00 0 0−
49
152
−
2033
3000
··· 00 0 0 0 1
··· 00 0 0 0 0
Q
r
=
00−
23
52
1 −
23
52
00···
00−
23
208
−
63
208
−
63
208
−
23
208
0 ···
.
.
.
Appendix C: The Filters for the Narrow Cubic B-Spline
In this case, A becomes
A
s
=
1000000 ···
−1200000 ···
A
r
=
00−
1
2
2 −
1
2
00 000 ···
00 0 0−
1
2
2 −
1
2
000 ···
.
.
.
A
e
=
··· 0002−1
··· 00001
.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Local B-Spline Multiresolution 99
The corresponding B matrix is B
s
=
3
4
−
3
2
9
8
−
1
2
1
8
0 ···
,
B
r
=
00
1
4
−1
3
2
−1
1
4
00000···
00 0 0
1
4
−1
3
2
−1
1
4
000 ···
.
.
.
,
B
e
=
··· 0000
1
8
−
1
2
9
8
−
3
2
3
4
.
And finally, the Q matrix is Q
s
=
00000 ···
00000 ···
,
Q
r
=
10000···
1
4
1
4
000···
01000···
0
1
4
1
4
00 ···
.
.
.
Q
e
=
00000 ···
00000 ···
.
Appendix D
P
s
=
1 0 000 ···
1
2
1
2
000 ···
, P
r
=
0
3
4
1
4
00···
0
1
4
3
4
00···
00
3
4
1
4
0 ···
00
1
4
3
4
0 ···
.
.
.
,
P
e
=
··· 000
1
2
1
2
··· 000 0 1
.
Similarly, the A matrix becomes
A
s
=
100 000···
−
1
2
1
3
4
−
1
4
00 ···
,
A
r
=
00−
1
4
3
4
3
4
−
1
4
00···
000 0−
1
4
3
4
3
4
−
1
4
···
.
.
.
,
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
100 Synthesis and Analysis in Biometrics
A
e
=
··· 00−
1
4
3
4
1 −
1
2
··· 00 0 0 0 1
.
And B is
B
s
=
−
1
2
1 −
3
4
1
4
000···
00−
1
4
3
4
−
3
4
1
4
0 ···
,
B
r
=
0000
1
4
−
3
4
3
4
−
1
4
00···
0000 00
1
4
−
3
4
3
4
−
1
4
···
.
.
.
,
B
e
=
··· 00
1
4
−
3
4
1 −
1
2
. Finally, for Q we have
Q
s
=
0000···
1
2
000···
−
3
4
1
4
00···
−
1
4
3
4
00···
0 −
3
4
−
1
4
0 ···
0 −
1
4
−
3
4
0 ···
Q
r
=
00
3
4
−
1
4
00···
00
1
4
−
3
4
00···
000
3
4
−
1
4
0 ···
000
1
4
−
3
4
0 ···
.
.
.
Q
e
=
··· 000
1
2
··· 000 0
Appendix E
A
s
=
100000000···
−
41
141
82
141
45
47
−
5
141
−
15
47
5
47
00 0···
41
425
−
82
425
−
41
425
287
425
297
425
−
11
425
−
99
425
33
425
0 ···
,
A
r
=
00
3
40
−
9
40
−
1
40
27
40
27
40
−
1
40
−
9
40
3
40
00 0···
00 0 0
3
40
−
9
40
−
1
40
27
40
27
40
−
1
40
−
9
40
3
40
0 ···
.
.
.
,
A
e
=
··· 0
33
425
−
99
425
−
11
425
297
425
287
425
−
41
425
−
82
425
41
425
··· 00 0
5
47
−
15
47
−
5
141
45
47
82
141
−
41
141
··· 000000001
.
The second decomposition matrix, B,is
B
s
=
−
27
80
27
40
−
81
160
27
160
00 ···
,
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Local B-Spline Multiresolution 101
B
r
=
00−
27
160
81
160
−
81
160
27
160
0000···
00 0 0−
27
160
81
160
−
81
160
27
160
00 ···
.
.
.
,
B
e
=
··· 00
27
160
−
81
160
27
40
−
27
80
. And Q is
Q
s
=
00000···
4000
3807
−
400
1269
000···
−
2296
3995
−
1928
21573
−
88
765
00···
−
328
323595
21416
21573
−
88
255
00···
164
765
−
49
51
58
2295
−
1
9
0 ···
164
2295
−
11
459
254
255
−
1
3
0 ···
,
Q
r
=
0
1
3
−1
1
27
−
1
9
00···
0
1
9
−
1
27
1 −
1
3
00···
00
1
3
−1
1
27
−
1
9
0 ···
00
1
9
−
1
27
1 −
1
3
0 ···
.
.
.
,
Q
e
=
··· 0
1
3
254
255
−
11
459
164
2295
··· 0
1
9
58
2295
−
49
51
164
765
··· 00−
88
255
21416
21573
−
328
323595
··· 00−
88
765
−
1928
21573
−
2296
3995
··· 00 0−
400
1269
4000
3807
··· 00 0 0 0
.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
This page intentionally left blankThis page intentionally left blank
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Chapter 4
Computational Geometry and Image Processing in
Biometrics: On the Path to Convergence
Marina L. Gavrilova
Biometric Technology Laboratory: Modeling and Simulation,
SPARCS Laboratory, Department of Computer Science,
University of Calgary, Calgary, AB, Canada
marina@cpsc.ucalgary.ca
The rapid development of biometric technologies is one of the modern
world’s phenomena, which can be justified by the strong need for the
increased security by the society and the spur in the new technological
developments driven by the industries. This chapter examines a unique
aspect of the problem — the development of new approaches and
methodologies for biometric identification, verification and synthesis
utilizing the notion of proximity and topological properties of biometric
identifiers. The use of recently developed advanced techniques in
computational geometry and image processing is examined with the
purpose of finding the common denominator between the different
biometric problems, and identifying the most promising methodologies.
The material of the chapter is enhanced with recently obtained
experimental results for fingerprint identification, facial expression
modeling, iris synthesis, and hand boundary tracing.
Contents
4.1. Introduction ................................... 104
4.2. BiometricMethods ............................... 106
4.3. ChapterOverview................................ 106
4.4. BiometricSystemArchitecture......................... 107
4.5. Computational Geometry Methods in Biometrics . . . . . . . . . . . . . . 108
4.5.1. Voronoi Diagram Techniques in Biometrics . . . . . . . . . . . . . 109
4.5.2. Distance Distribution Computation in Biometrics . . . . . . . . . 118
4.5.3. Medial Axis Transform for Boundary and Skeleton Extraction and
TopologicalPropertiesIdentification ................ 126
4.5.4. Topology-Based Approach for Generation and Synthesis of New
BiometricInformation ........................ 128
103
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
104 Synthesis and Analysis in Biometrics
4.6. Conclusions ................................... 130
Bibliography ....................................... 130
Glossary
FA R — False Acceptance Rate
FRR — False Refused Rate
RBF — Radial Basis Function
NPR — Non-Photorealistic Rendering
VD — Voronoi Diagram
DT — Delaunay Triangulation
4.1. Introduction
The term “biometric authentication” refers to the automatic identification,
or identity verification using physiological and behavioural characteristics.
AccordingtoJ.L.Wayman
[
1
]
, there are two distinct functions for
biometric devices: to prove that you are who you say you are or to prove
that you are not who you say you are not.
A negative claim to identity can only be accomplished through
biometrics. For positive identification, however, there are multiple
alternative technologies, such as passwords, PINs (Personal Identification
Numbers), cryptographic keys, and various tokes, including identification
cards. However, the use of passwords, PINs, keys and tokens carries the
security problem of verifying that the presenter is the authorized user,
and not an unauthorized holder. Consequently, passwords and tokens
can be used in conjunction with biometric identification to mitigate their
vulnerability to unauthorized use. Most importantly, properly designed
biometric systems can be faster and more convenient for the user, and
cheaper for the administrator, than the alternatives.
Security systems traditionally use biometrics for two basic purposes: to
verify and to identify users
[
2
]
. Identification tends to be the more difficult
task as the system must perform the search on a database of enrolled users
to find a match (a one-to-many search). The biometric that the security
system employs depends in part on what the system is protecting and what
it is trying to protect against.
For decades, many highly secure environments have used biometric
technology for monitoring the entry access. Today, the primary application
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 105
of biometrics is shifting from the physical security, where the access
to the specific locations is usually monitored using standard security
identification mechanisms such as signature, access cards, passwords,
fingerprint scanning, palm prints and others, to remote security.By
this we mean the advanced methods of crowd monitoring at banks, car
registries or in the mall using video cameras, infrared and ultrared scanners,
temperature measuring devices, gait and behavioural pattern recording
made at the distance from the studied subject. The popularity of such
approaches has increased dramatically as the new technological devices are
coming on the market every week, capability to process massive amount of
data is doubling every few month, and the algorithm development by the
leading IT companies and the University research centers is tripled in the
last year.
Biometric modeling or synthesis of the biometrics is the new area of
the research at the frontier of biometric science. It is driven by two
major stimulating factors: the need to verify the effectiveness and
correctness of the newly developed methodologies on the extensive
biometric data sets and the desire to study dynamically evolving
situations from the different perspectives.
In order to satisfy the first demand, the data sets containing fingerprint,
facial and other biometric data are generated using specifically developed
methods. For the second need, dynamical modeling of processes, situations,
and subject behavior is utilized. Such computations are usually complex
and require either distributed environment, parallel algorithms or complex
3D visualization system.
Finally, as the demand for fast remote access and distributed processing
of biometric data had been increasingly growing, and the need to develop
more precise and reliable ways of person identification is ever pressing, the
combination of biometrics and data processing methods are gaining high
popularity as it undoubtedly increases the quality of the results and the
level of security protection.
Driven by the above motivations, the rest of this Chapter is devoted to
displaying the variety of computational geometry techniques in biometric
synthesis and identification, as well as the use of multiple algorithms to
enhance the solution to a specific problem. Our goal is not to provide
a comprehensive analysis of all the methods used in modern biometrics
(even this book with all its chapters would not be enough for this purpose),
but rather to concentrate on unique aspects of geometric computing and
exploring the topological relationship among objects in the biometric
world with the purpose of showcasing the strength and robustness of
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
106 Synthesis and Analysis in Biometrics
such approaches. All algorithms presented in the Chapter have been
implemented by students of Biometric Technologies Laboratory under
supervision of Prof. Marina Gavrilova.
4.2. Biometric Methods
There seems to be virtually no limit to personal characteristics and methods
that have been suggested and used for biometric identification: fingers,
hands, feet, faces, eyes, ears, teeth, voices, signatures, typing patterns, gaits
etc. Among the recently emerging biometric characteristics are temperature
maps, obtained by analyzing the amount of heat emitted by different body
parts, infrared scanning and bio-magnetic fields.
Typically, biometrics can be separated into two distinctive classes:
physiological characteristics and behavioural characteristics. Common
physiological biometric identifiers include fingerprints, hand geometry, eye
patterns (iris and retina), facial features and other physical characteristics.
Typical behavioural identifiers are the voice, signature and typing patterns.
Analyzers, which are based on behavioural identifiers, are often less
conclusive because they are subject to limitations and can exhibit complex
patterns.
However, there has been no agreement on which biometric measure is
the best, since they vary greatly in their availability, ease of accessing,
storing and transmitting, and even in their ability to identify a person
uniquely (fingerprint seems to be a unique measure, while hand geometry
is not). Some are also much easier to digitize and classify than others —
thus making their use dependent on a variety of factors, such as availability
of technological base and specifics of the goals of the applications.
4.3. Chapter Overview
The interest of general public as well as research community to the
area of biometric can be illustrated by many examples, perhaps one of
the most appealing is the number of manuscripts being written in the
recent years and devoted exclusively to biometric. After a very successful
book on fingerprint identification
[
10
]
, a book on face recognition as
well as the book devoted to various biometrics recently saw the light of
publishing
[
33,22,23
]
. While these books concentrate on the fundamental
techniques developed for addressing biometric identification, classification
and recognition problems (and doing an exceptional job at it), the new area
of biometrics devoted to continuously emerging new techniques as well as
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 107
new applications (such as biometric synthesis), remain outside the scope of
these fine publications.
Within two years since the manuscript “Computational Geometry
and Biometrics: on the Path to Convergence” has found the audience
as the part of International Workshop on Biometrics Technologies 2004
[
19
]
, the number of attempts to extract geometric information and
apply topology to solve biometric problems has increased significantly.
There has been research on application of topological methods, including
Voronoi diagram, Delaunay triangulation and distance transform, for hand
geometry detection, iris synthesis, signature recognition, face modeling and
fingerprint matching
[
14,18,24
]
. As the methodology is new, many questions
on what is the best way to utilize the complex geometric data structures,
which topological information to use and in which context, how to make
implementation decisions and whether the performance is superior to other
techniques remain largely unanswered. This chapter attempts to fill this
gap and introduces a number of methodologies and techniques, illustrated
by concrete examples from different biometric areas.
4.4. Biometric System Architecture
We start with the basics of introducing the generic biometric system
components and then identifying the appropriate placement of the
topological methods in the above content.
Although biometric devices rely on a scope of different technologies,
much can be said about them in general. In Fig. 4.1, we depict a
generic biometric authentication system, divided into five sub-systems:
data collection, transmission, processing, decision and data storage. Data
Collection subsystem constitute the set of electronic devices and collection
methods, intended to measure accurately some biometric characteristics.
This information is then either sent directly to Processing module or
compressed and stored in a Biometric Database (located locally or at
a remote location). Processing module includes preprocessing of the
biometric data (a scanned fingerprint image, for instance), with the purpose
of enhancing its quality, accommodating for variations in the conditions
under which the data was obtained. Then the extracting important features
(such as minutiae of a fingerprint) are extracted. The decision making
module uses obtained information in order to search in the database and
compare new biometric data with the existing one with the purpose of
identification or verification. It then reports the results after which the
new query can be originated.