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
108 Synthesis and Analysis in Biometrics
It is important to note that the process in non-linear. In the case
of insufficient quality of an image, multiple conflicting feature points or
erroneous matching, data can be re-sampled, preprocessed again or another
matching technique could be used.
Data source
Sensors
Data source
Sensors
Feature
extraction
Data pre
-
processing
Data source
Sensors
Pattern
matching
Reporting
Data Collection Decision
Transmission
Storage
Compression module
Data
Base
Processing
CG
methods
Fig. 4.1. Computation Geometry Methods (identified by yellow cubes) in Generic
Biometric System.
The above process is not necessary error-proof. Various factors might
influence false identification, or in contrast not finding any matches.
Therefore, a long-term goal in biometric testing is to establish acceptable
error rates for biometric devices in as many different application categories
as possible, and to continue to improve methodology in order to decrease a
possibility of an error and make implementation more robust.
4.5. Computational Geometry Methods in Biometrics
As can be seen from Fig. 4.1, the most important steps in the processing
and identification of biometric data are pattern matching, extraction of
important features and pre-processing. The techniques for optimization of
these steps are crucial for successful design and functioning of the biometric
system. These steps can be made more efficient and implemented using
advanced research in the area of computational geometry (see Fig. 4.1),
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 109
based specifically on concepts of proximity of geometric sets and extracting
and utilizing topological information on the data studies. The methods
include:
• Utilization of the Voronoi diagram and Delaunay triangulation
computational geometry data structures for data processing and
matching
• Development of distance distribution methods using weighted metric
functions and distance transform for studying image properties and
pattern matching
• Constructing medial-axis transform for boundary and skeleton extraction
and topological properties identification
• Introducing topology-based approach for generation and synthesis of new
biometric data
These methods and numerous applications are described below according
to their classification.
4.5.1. Voronoi Diagram Techniques in Biometrics
On the perpetual human quest for perfection, techniques for increasing
the efficiency and reliability of biometric identification and matching are
continuosly being developed; computational geometry and image processing
inspiring many of those techniques.
As one of the most fundamental data structures of computational
geometry, Voronoi diagram and it’s dual Delaunay triangulation
[
32
]
is
being perhaps one of the most popular data structures being utilized
in various areas of applied sciences and recently making its way into
the area of biometrics. Applications of Voronoi diagrams for proximity
studies and material structure analysis has gained considerable momentum
in the past few decades; traditional application areas being Molecular
Biology, Physics, Chemistry, Astronomy, Mechanical Engineering, Material
Sciences, and more recently Visualization, Geographical Information
Systems and Bioinformatics.
In the area of biometrics, Biometric Technologies Laboratory at the
University of Calgary has pioneered some of the important applications of
Voronoi diagrams in fingerprint matching, iris synthesis, hand geometry
identification and face modeling
[
36,37,35,34
]
. For instance, in 3D facial
expression modeling, mesh is used as a medium to convey facial expression
transformation through a set of control areas. Delaunay triangulation
technique is often utilized to represent and control mesh deformations,
which is useful for facial structure analysis, face synthesis and identification
[
27,36,28
]
. Among other studies on the subject, Voronoi diagrams were
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
110 Synthesis and Analysis in Biometrics
utilized for face partitioning onto segments and facial feature extraction in
[
24
]
. In fingerprint identification area, Bebis et. al.
[
14
]
used the Delaunay
triangle as the comparing index in fingerprint matching in 1999. Recently,
a new method for binary fingerprint image denoising based on Distance
Transform realized through Voronoi method was introduced in
[
18
]
.In
related areas of geographical information systems and navigation planning,
Voronoi diagrams have been applied for 3D object reconstruction from point
clouds and in clustering analysis. Examples can be found in recent works
by
[
12,13,26
]
. The above is just a small fraction of the research undertaken
in this area. There are other application areas of biometrics where Voronoi
diagram methodologies are being utilized and developed. The concentration
of the following sections is on the example of Voronoi technique application
in fingerprint matching.
4.5.1.1. Voronoi Diagram Preliminaries
Let us start with the brief introduction of Voronoi Diagram and Delaunay
Triangulation to the reader. Typically,
The Euclidean Voronoi diagram is used to store the topological
information about the system of objects (points, spheres, polygons) in
the plane or in the higher dimension, as well as to assist in performing
various nearest-neighbors and point-location queries.
We start with the most general definition of the Voronoi Diagram.
Definition 1. The Voronoi diagram for a set of objects S in d-dimensional
space is a partitioning of the space into regions, such that each region is
the locus of points from S closer to the object P ∈ S than to any other
object Q ∈ S, Q = P .
The above general definition can be specialized to the set of spheres in
the Euclidean metric
[
32
]
:
Definition 2. A generalized Euclidean Voronoi diagram for a set of
spheres S in R
d
is the set of Voronoi regions {x ∈ R
d
|d(x,P) ≤ d(x,Q),
∀Q ∈ S −{P }},whered (x,P) is the Euclideandistance function between
apointx and a sphere P ∈ S.
The above definition is often used in material sciences for representation
of circular objects (balls, particles, molecules) as well as in dynamic
behavior modeling (of growing plants, in game design, etc). In the simplest
case, the set of spheres can be replaced by the set of points and the distance
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 111
between the sphere and the point will reduce to the simple distance between
two points in Euclidean space. Following the classification of Voronoi
diagrams based on the way of how to compute such distance, presented
in
[
32
]
, the Euclidean weighted Voronoi diagram is an instance of the class
of additively weighted Voronoi diagrams. Thus, the distance between a
point x and a sphere P with center at p and radius r
p
is defined as
d(x,P)=d(x, p) −r
p
) (see Fig. 4.2). The distance d(x, p) between points
x(x
1
,x
2
, ..., x
d
)andp(p
1
,p
2
, ..., p
d
) in the Euclidean metric is computed as
d(x, p)=
d
i=1
(x
i
− p
i
)
2
. According to the definition:
The generalized Voronoi region of an additively weighted Voronoi
diagram of n spheres is obtained as the intersection of n − 1 quasi-
halfspaces with hyperbolic boundaries.
P
Q
B(P,Q)
(b)
x
d(x,P)
(a)
P
Fig. 4.2. The Euclidean distance and the Euclidean bisector in the plane.
The boundary of the generalized Voronoi region consists of up to n −1
curvilinear facets, where each facet is a d − 1 curvilinear dimensional face.
The boundary of the (d−1)-dimensional face consists of (d−2)-dimensional
faces and so on. An 1-dimensional face is called a generalized Voronoi edge
(a straight-line segment or a hyperbolic arc), and a 0 dimensional face is
called a generalized Voronoi vertex.Itwasshownin
[
32
]
that the weighted
Euclidean Voronoi diagram for a set of spheres is the set of singly-connected
Voronoi regions with the hyperbolic boundaries, and each Voronoi region
is star-shaped relative to sphere P .
The example of the Euclidean Voronoi diagram in R
3
is given in Fig. 4.3.
The straight-line dual to the Voronoi diagram, called a Delaunay
tessellation, is often used instead of the Voronoi diagram to store
topological information for a set of spheres.
Definition 3. A generalized Delaunay tessellation corresponding to a
generalized Voronoi diagram for a set of spheres S in d-dimensional space
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
112 Synthesis and Analysis in Biometrics
Fig. 4.3. The Euclidean Voronoi diagram in R
3
.
is a collection of d-dimensional simplices such that for each generalized
Voronoi vertex v = EV or (P
1
) ∩EV or (P
2
) ∩... ∩EV or (P
d+1
)thereexists
asimplex(p
1
,p
2
,,p
d+1
) in the generalized Delaunay tessellation.
The example of the Delaunay triangulation in the plane is given in the
figure below (see Fig. 4.4).
Fig. 4.4. Neighbors identified by the edges of the Delaunay triangulation.
The concept is illustrated further by Fig. 4.5: left image displays the
Voronoi diagram in supremum metric, right image — its dual, the Delaunay
triangulation. A number of useful properties of the above data structure,
such as “empty circle” and “nearest-neighbor property, as well as regularity
of corresponding Delaunay triangulation, make this data structure highly
popular in a variety of applications
[
7,6,8,32,9,3
]
. The methodology is
making its way to the core methods of biometrics, such as fingerprint
identification, iris and retina matching, face analysis, ear geometry and
others
[
24,17,18,2,14,1,11
]
. The methods are using Voronoi diagram to
partition the area of a studied image and compute some important features
(such as areas of Voronoi region, boundary representation, etc.) and
compare with similarly obtained characteristics of other biometric data.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 113
Fig. 4.5. Voronoi diagram and corresponding Delaunay triangulation of 1,000 weighted
sites in supremum (L
inf
) metric (left to right).
The Delaunay triangulation in the plane possesses important properties
that make its application in biometric and computer graphics, among other
areas, very appealing. These properties are described on the example of
fingerprint matching in the section below.
4.5.1.2. Voronoi Diagrams in Fingerprint Matching
Let us now discuss how Delaunay triangulation can be utilized in fingerprint
matching problem. The large number of approaches to fingerprint matching
can be coarsely classified into three classes: correlation-based matching,
minutiae-based matching and ridge-based matching.
In correlation-based matching, two fingerprint images are superimposed
and the correlation between corresponding pixels is computed for different
alignments. During minutiae-based matching, the sets of minutiae are
extracted from the two fingerprints and stored as sets of points in the two
dimensional plane
[
15,1
]
. Ridge-based matching is based on such features
as orientation map, ridge lines and ridge geometry
[
15
]
.Amongtheabove
techniques, minutiae-matching is most widely used approach that yields
best matching results. Traditional algorithms (such as
[
14
]
) work under the
restricting assumption that at least one corresponding triangle pair can be
found between the input and template fingerprint images. Unfortunately,
this assumption might not hold due to low quality of fingerprint images,
unsatisfactory performance of the feature extraction algorithm or distorted
images. Another problem in fingerprint matching is noticeable when the
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
114 Synthesis and Analysis in Biometrics
distance between two points in template image increases. It becomes
more challenging to match point pairs in the corresponding images. For
instance, Kovacs-Vajna
[
17
]
have shown that local deformation of less than
10% can cause global deformation reaching 45% in edge length. In the
following, we discuss how to deal with shortcoming of the above methods
using Delaunay triangulation technique and applying radial functions for
deformation modeling.
Some of the outlined above problems can be alleviated by the use of
a special data structure for data representation and processing, such as
Delaunay triangulation. We propose to use this data structure for minutiae
matching and singular-point comparison in the fingerprints. The method
was implemented as part of the global fingerprint recognition system
[
20
]
and is sustainable under presence of elastic deformations
[
21
]
.The
minutiae-matching algorithm, in which context the Delaunay triangulation
approach is utilized, is based on classic fingerprint matching technique
[
22
]
.
Using Delaunay triangulation brings unique challenges and advantages:
(1) Delaunay edges rather than minutiae or whole minutiae triangles are
selected as matching index which provides an easier way to compare
two fingerprints.
(2) The method is combined with deformation model, which helps
to preserve consistency of the results under elastic finger surface
deformations.
(3) To improve matching performance, we introduce feature based on
spatial relationship and geometric attribute of ridges, and combine it
with information from both singular point sets and minutiae sets to
increase matching precision.
4.5.1.3. Delaunay Triangulation for Fingerprint Matching and
Deformation Modeling
The purpose of fingerprint identification is to determine whether two
fingerprints are from the same finger or not. In order to complete this
task, the input fingerprint needs to be aligned with the template fingerprint
represented by its minutia pattern. We divide our algorithm into three
stages. During the first stage, identification of feature patterns utilizing
Delaunay triangulation takes place. During the second step, Radial Basis
Function (RBF) is applied to model the finger deformation and align
images. Finally, the global matching algorithm is employed to compute
the combined matching score, using additional topological information
extracted from ridge geometry (see Fig. 4.6).
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 115
Input minutae set
DT of input minutae
Template minutae set
DT of template minutae
Compare triangle edges from
input and template images
Model finger deformation
Global matching
Matched / Not matched
Fig. 4.6. Flow chart of generic fingerprint identification system.
Using triangle edge as comparing index has many advantages. For
local matching, we first compute the Delaunay triangulation of minutiae
sets Q and P . Second, we use triangle edge as our comparing index. To
compare two edges, parameters such as Length, Type1, Type2, Ridgecount
are used. Note that these parameters are invariant of the translation and
rotation. Conditions for determining whether two edges match identified
as the set of linear inequalities depending on the above parameters and the
specified thresholds (usually derived empirically depending on image size
and quality). A sample set of such conditions can be found in
[
21,37
]
.Ifthe
threshold is selected successfully, then the transformation to align the input
and template images is obtained. Matching using Delaunay triangulation
edge is realized as follows. If one edge from an input image matches two
edges from the template image, we need to consider the triangulation
to which this triangle edge belongs to and compare the triangle pair.
For a certain range of translation and rotation dispersion, we detect the
peak in the transformation space, and record transformations that are
neighbors of the peak in the transformation space. Note that those recorded
transformations are close to each other, but not identical. Also note that
elastic deformations should be dealt with separately as such deformations
can not be ignored. Figure 4.7 shows the successfully matched Delaunay
triangle edge pairs. Detailed description of the matching algorithm can be
found in
[
21,37
]
.
The deformation problems arise due to the inherent flexibility of the
finger. In
[
21
]
, we proposed a framework aimed at quantifying and modeling
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
116 Synthesis and Analysis in Biometrics
Fig. 4.7. Matched Delaunay triangle edges are shown in red. On contrary, no single
triangle is matched.
the local, regional and global deformation of the fingerprint. The method is
based on the use of RBFs, that represent a practical solution to the problem
of modeling of a deformable behavior. The application of RBF has been
explored in medical image matching as well as in image morphing. For
our fingerprint matching algorithm, deformation problem can be described
as knowing the consistent transformations of specific control points from
the minutiae set, and knowing how to interpolate the transformation of
other minutiae which are not control points. We do not consider all the
transformations obtained by the local matching. We rank them in the
transformation space and pick those consistent transformations which form
large clusters.
We then consider the transformation of input image as a rigid
transformation. Experimentally, we established that the maximum number
of matching minutiae pairs between input image and template image is 6
(labeled by the big dashed circle in Fig. 4.8, left). Circles denote minutiae
of the input image after transformation, while squares denote minutiae of
the template image. Knowing transformation of the five minutiae (control
points) of the input image, we apply the RBF to model the non-rigid
deformation, visualized by the deformed grid in Fig. 4.8 (right). In the
example below, the number of matching minutiae pairs is 10, which greatly
increased the matching scores of these two corresponding images.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 117
Fig. 4.8. Comparison of rigid transformation and non-rigid transformation.
4.5.1.4. System Implementation and Experiments
The described above fingerprint identification system (including both local
and global matching) was implemented in C++ and tested on a Pentium
4 2.8 GHZ CPU, 512 RAM PC. Experiments have been performed on two
fingerprint databases: from Biometric System Laboratory at University of
Bologna, that consists of 21 ×8 fingerprint images of 256 ×256 size; and on
the publicly available database used in Fingerprint Verification Competition
FVC2000. The captured fingerprint images vary in quality. The interface
of the implemented system is presented below (Fig. 4.9).
Extensive experimentations were performed with the system, that
confirmed its high efficiency, low FRR (False Refused Rate), low FAR
(False Acceptance Rate) and good overall comparison with many other
algorithms. We further conducted experiments to show resistance of the
proposed matching algorithm to fingerprint deformations, which impact
negatively most of the other fingerprint matching algorithms. For detailed
experimental results, consult
[
21,37
]
.
Note, that an additional improvement in matching rate was achieved
by combining the Delaunay Triangulation approach with the distance
transform method for ridge geometry computation in addition to minutiae
matching, that will be described in the next section.