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
118 Synthesis and Analysis in Biometrics
Fig. 4.9. Fingerprint matching system interface.
4.5.2. Distance Distribution Computation in Biometrics
In this section, we first look at the new ways of establishing thresholds for
biometric matching using weighted distance functions. Next, we describe
how the concept of distance transform (in Euclidean or other Minkowski
metric) can be used for ridge geometry computation and facial expression
morphing. We conclude this chapter with links to the next topic, boundary
and skeleton extraction for biometric image comparison.
4.5.2.1. Weighted Distance Metrics for Establishing the Biometric
Threshold
The most basic technical measures which can be used to determine
the distinctiveness and repeatability of the biometric patterns are the
distance measures output by the processing module. Through testing,
one can establish three application-dependent distributions based on these
measures:
The first distribution, called the genuine distribution, is created from
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 119
distance measures resulting from comparison of samples to similar
templates. It shows the repeatability of measures from the same person.
The second distribution is created from the distance measures resulting
from the comparison of templates obtained from different individuals.
It is called the inter-template distribution.
The third distribution is created from the distance between samples to
non-like templates, called the impostor distribution.Itshowsthe
distinctiveness of measures from different individuals.
One common way to establish a decision policy is by picking a threshold
distance, and declaring distances less than the threshold as a “match” and
those greater to indicate “non-match”. However, under less than perfect
conditions, experiments shown that there is an overlap between the genuine
and impostor distributions. This means that the method is not an error
proof and in some instances no threshold could clearly distinguish the
genuine from the impostor distances.
While the experiments are normally conducted using the traditional
Euclideandistance, one possible way to approach the problem might be
by using other distance functions and weighted metrics. The decision on
which metric to use for studying the proximity of biometric sets can be
based on the type of the biometric data as well as the task. For instance,
the regularity of templates (in a case of fingerprint, or retina), might be
a feature that will allow us to use distance measure more efficiently by
applying a weighted Minkowski metric, such as L
1
(Manhattan)orL
inf
(supremum) metrics.
To illustrate the idea, a number of possible metrics originated by the
group of additively weighted metrics, is suggested. The distance is described
by the general form
d
e
(x, P )=d(x, p) − w
p
(4.1)
where x is a sample point, P is a specific object or feature point and is a
weight function w
p
which represents any individual or cumulative parameter
of the studies phenomena. Under traditional Euclidean metric, the above
expression transforms into:
d(x, P )=
d
i=1
(x
i
− p
i
)
2
− w
p
(4.2)
Using Manhattan and supremum metric (respectively), the formula is
expressed as (Fig. 4.10):
d(x, P )=
d
i=1
|x
i
− pi|−w
p
(4.3)
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
120 Synthesis and Analysis in Biometrics
d(x, P )= max
i=1...d
|x
i
− pi|−w
p
(4.4)
Our proposition is that the regularity of the metric will allow to measure
the distances from some distinct features of the template more precisely,
and ignore minor discrepancies originated from noise and imprecise
measurement while obtaining the data. We presume that the behavioural
identifiers, such as typing pattern, voice and handwriting styles will be
less susceptible to improvement using the proposed weighted distance
methodology than the physiological identifiers.
P
x
P
x
x
P
d(x,P)
d(x,P)
d(x,P)
r
p
r
p
r
p
(a) (b) (c)
Fig. 4.10. Distance computation using additively weighted metrics: (a) Euclidean (b)
Manhattan (c) supremum (left to right).
4.5.2.2. Distance Transform Preliminaries
Let us now take a look at one of the examples of using distance between
pixels of the input image for the purpose of image matching and related
problem of image morphing.
Given an n × n binary image I of white and black pixels, the distance
transform of I is a map that assigns to each pixel the distance to the nearest
black pixel, referred to as feature. The feature transform of I is a map that
assigns to each pixel the feature that is nearest to it. The distance transform
was first introduced by Rosenfeld and Pfaltz
[
31
]
, and it has a wide range of
applications in image processing, robotics, pattern recognition and pattern
matching. The distance metrics used to compute the distance transform
include the L
1
,L
2
and L
∞
metrics, with the L
2
(Euclidean) metric being
the most natural, and rotational invariant.
One approach is to grow clusters or neighborhoods around each
feature p consisting of those pixels whose nearest feature is p.This
approach has been taken in
[
30
]
and
[
29
]
to obtain sequential and parallel
algorithms, respectively. Daniellson
[
30
]
describes a sequential nearest-
neighbor transform algorithm that is nearly error-free. An alternative
approach, pioneered by Rosenford and Pfaltz
[
31
]
, is based on the idea
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 121
of dimension reduction. The transform is first computed using the distance
function in one lower dimension and then the two-dimensional distance
transform is computed.
The approach we utilize in our research is based on simple and optimal
algorithm for computing the Euclidean distance transform and the nearest
feature transform based on image sweeping technique developed in
[
4
]
.The
algorithm processes the rows of the image twice: in a top-down scan and
a bottom-up scan. The polygonal chain C, containing all the necessary
information to compute the nearest feature for each pixel of the currently
processed row, is maintained. A marking characteristic of this algorithm
is updating the polygonal chain dynamically as the image is swept row by
row. The information gathered while processing the previous row is utilized
to compute the nearest features for the next row. The algorithm is one of
the most efficient algorithms of its sort in terms of the implementation
efficiency when compared with other linear time algorithms, and thus it
was selected for facial expression modeling problem. The full description
of this method can be found in
[
4
]
.
4.5.2.3. Face Modeling using Distance Transform
We now illustrate the application of the Distance Transform algorithm to
facial expression modeling problem.
Facial expression modeling and animation, as an identifiable area of
computer graphics and biometrics, has long fascinated computer graphics
researchers. Historically, the earliest attempts to model and animate
realistic human faces date back to the early 1970s
[
38
]
.Sincethen,
numerous research papers have been published on this topic.
NPR animation of faces offer several advantages over attempts to work
with photorealistic images, including compact image storage, inclusion of
selected representable lines for image displaying and manipulation, as well
as additional freedom to transform image according to artist’s desire. In
BT Lab, we developed a new method for automatic animation of NPR faces
from sample images. Our system takes two human facial images as input
and outputs a particular NPR style facial animation. First, a particular
NPR style portrait is created from a frontal facial photograph. While
many NPR techniques have been proposed to generate digital artwork, the
detail information, such as expressive wrinkles and creases, is usually missed
in the generated pictures. As an extension, we propose a segmentation
and tracking method to map those expressive lines, which makes the
portrait more expressive. Then, a metamorphing algorithm using distance
transform is utilized to produce the resulted animation. The system
flowchart is show in the graph below (see Fig. 4.11).
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
122 Synthesis and Analysis in Biometrics
Input photograph
Black-and-while
Illustration Generation
Close-up details
Extraction
Mapping and
Rendering Module
Output Drawing
Fig. 4.11. The distance transform method.
After edge detection for feature lines and feature line tracking, mapping
and rendering steps are performed (for detailed description, see
[
36
]
),
the distance transform based morphing is applied to transform two input
images. The process is outlined below.
Given two input photographs of different facial expressions, two NPR
style portraits are to be produced by Portrait Generator module. The task
is to create a smooth animation between these two NPR portraits. Given
two images A and B, this smooth transition is computed as a sequence of
frames S
0
, S
1
, ... S
k
,whereS
0
= A and S
k
= B. Traditionally, to achieve
a good morphing sequence, a number of equal control points are selected in
both images (often manually), and then a one-to-one mapping is defined. It
can be difficult both to select the control points and compute the mapping.
Thus, we developed a novel approach to computing morphing sequences,
that relies on distance transforms rather than control points.
Let A, B be two bi-level m × n images, we treat the image matrix A
as a set, that is A = {(i, j) | a
ij
=1}. B is defined in the same manner. In
addition, the intermediate slides can be viewed either as bi-level images or
as grey-scale images.
During the morphing sequence, we would like each pixel a ∈ A to move
to its new location in B, so that it travels the shortest distance. We can
achieve this by sending each pixel to its nearest neighbor in B.Inthisway,
the morphing problem between images A and B is reduced to the problem
of animation of the motion of N = |A| + |B| pixels along straight line
segments. To do this, we define two functions, f : A → B,andg : B → A.
Each function maps pixels to a nearest neighbor in the other image. Each
a ∈ A is really an ordered pair and represents the location of a foreground
pixel in A: a =(x
a
,y
a
)andb =(x
b
,y
b
). We define distance between
points a and b in the Euclidean sense d(a, b)=
(x
a
− x
b
)
2
+(y
a
− y
b
)
2
.
Next, we define f and g: f(a)=argmin
b∈B
{d(a, b) | b ∈ B}, g(b)=
arg min
a∈A
{d(a, b) | a ∈ A}. Function f is called a feature transform of B
and similarly g is a feature transform of A. f
(a)=min
b∈B
{d(a, b) | b ∈ B}
is a distance transform.
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 123
In the morphing sequence, each a will travel to its nearest neighbor in
B, i.e. a → f(a). This may cause some visual artifacts, as this mapping
may not be one to one. Although all pixels in A will move, not all pixels in
B may be involved in the transformation. Formally, domain(f)=A, but
range(g) need not be equal to B. Thus, a set of straight line paths in the
reverse direction are created from B to A,usingg as a guide.
Formally, define a set of line segments L as follows
L = {(a, f (a)) | a ∈ A}∪{(g(b),b) | b ∈ B}
= {(u, v)}, for notational simplicity
Thus, L is a set of line segments, each line represented by its endpoints u
and v (u and v are each ordered pairs).
Now we are ready to compute the frames S
0
, S
1
, ...S
k
.WedefineS
i
=
{u +
i
k
(u −v) | (u, v) ∈ L},where L = {(u, v)} = {(a
1
,b
1
), (a
2
,b
2
), (a
2
,b
3
)}.
Then, the maps f and g can be computed in linear time O(mn), where
A is an m × n image, using the algorithm in
[
4
]
using the L
2
norm.
Thus, the distance transform provides out a fast, smooth and visually
continuous morphing process of facial expressions. A morphing sequence
between a happiness and surprise facial expressions using this method is
shown in Fig. 4.12.
Fig. 4.12. Slices morphing from happiness to surprise in line drawing style, 15 frames
as the interval.
4.5.2.4. Distance Transform for Ridge Extraction
Another application of the described above methodology can be found
in ridge extraction problem for fingerprints. It is known that the use of
additional features in conjunction with the minutiae assists in increasing
the system accuracy and robustness. In this respect, we propose to use a
new feature based on the spatial relationship and geometry attributes of
ridge lines. A two-dimensional binary image I of M by M pixels is a matrix
of size M by M whose entries are 0 or 1. The pixel in a row i and column
j is associated with the Cartesian coordinate (i, j). For a given distance
function, the binary image is the thinned fingerprint image that can be
transformed to a distance map to the feature points.
Let m00 represent the minutiae (end or bifurcation). Then it is possible
to construct a vertical line perpendicular to its orientation field. Assume
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
124 Synthesis and Analysis in Biometrics
that the intersection with the binary image is m10, m20, m30 and m40. To
add the curvature information of a associated ith ridge of minutiae m00,
we use m1, m2, m3andm4, the sampled points on the ridge close the
mi0 and equally spaced from near to far, to represent the ridge. The
local comprehensive fingerprint information contains the five associated
ridges, each ridge include the four distance from sampled points to the
intersection. Experiments show that the proposed approach increases the
matching accuracy at the cost of some additional storage space for ridge.
Application of such new feature (orientation field and ridge shape) in
matching algorithm implementation decreases the false refused rate from 8
percent to 5 percent, according to
[
21
]
.
4.5.2.5. Pattern Matching
Aside from a problem of measuring the distance, pattern matching between
the template and the measured biometric characteristic is a very serious
problem on its own. Some preliminary research, mainly in the area of
image processing, should be utilized in order to approach the problem from
the right angle. The advanced research in the area of pattern matching is
being conducted in the recent years for the purpose of image comparison,
database searches in the collection of images or historical texts, performing
handwriting recognition, and integrating the technology into the cellular
phones, notepads and electronic organizers. The most common methods are
based on bit-map comparison techniques, scaling, rotating and modifying
image to fit the template through the use of linear operators, and extracting
template boundaries or skeleton (also called medial axis) for the comparison
purposes.
In addition, template comparison methods also differ, being based on
either pixel to pixel, important features (such as minutiae) positions, or
boundary/skeleton comparison. The illustration of bit-based methods for
image matching is presented in Fig. 4.13. While these methods are well
studies and prove them to produce reliable results, the use of technique
based on the distance transform method can provide necessary improvement
in speed while preserving the methods simplicity and practicality.
4.5.2.6. Distance Transform for Pattern Matching
Definition 4. Given an n ×m binary image I of white and black pixels,
the distance transform of I is a map that assigns to each pixel the distance
to the nearest black pixel (a feature).
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 125
Fig. 4.13. Bit-map representation of an image; template of an image; pixel matching
(from left to right) (images are courtesy of Prof. Jim Parker, University of Calgary).
Fig. 4.14. The distance transform method. Top row from left to right: binary image
of black and white pixels; distance transform of a binary image. Bottom row, left to
right: “temperature map” based on the distance transform; thermogram of an ear (Brent
Griffith, Infrared Thermography Laboratory, Lawrence Berkeley National Laboratory).
The distance transform method introduced in
[
4
]
is based on fast scans
of image in the top-bottom and left-right directions using a fast polygonal
chain maintenance algorithm for optimization. After the distance transform
is build (Fig. 4.14), it can be used to visualize information on closeness in
a form of so-called temperature map. As the distance from the black pixels
(features) increases, the color intensity changes.
It would be interesting and highly beneficial, in our view, to extract
the temperature map (and the original distance transform) from the
thermograms that need to be compared against each other. Our experience
with the method indicates that this process is deterministic and fast,
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
126 Synthesis and Analysis in Biometrics
thus will assure a high reliability and robustness when used for biometric
identification and verification purposes.
4.5.3. Medial Axis Transform for Boundary and Skeleton
Extraction and Topological Properties Identification
Another way to approach the above biometric problems is through
extraction of a boundary or a skeleton of a studied biometric samples.
Definition 5. The medial axis,orskeleton of the set D, denoted M(D), is
defined as the locus of points inside D which lie at the centers of all closed
discs (or spheres) which are maximal in D, together with the limit points
of this locus.
The medial axis transform was first introduced by Blum to describe
biological shapes. It can be viewed as the locus of the center of a maximal
disc as it rolls inside an object. Since its introduction, the concept was used
in numerous applications that involved studying the topology and geometry
of some objects. In the area of image processing and biological modeling,
the algorithms for investigating connectivity problems and background
skeletonization include: peeling, distance-based, Voronoi diagram based
methods
[
32
]
. While the first two techniques has been traditionally used
for skeleton extraction, the Voronoi diagram based method (the concept
is described in detail in the next Section) provides a robust and efficient
alternative, reducing significantly the computation time and also allowing
for computation of additional features of the shape. The illustration of
the skeleton (blue line) constructed for the randomly drawn shape using
software we have developed in presented in Fig. 4.15. The yellow lines
represent dual to Voronoi diagram, the Delaunay triangulation edges.
4.5.3.1. Topology-Based Approximation of Image for Feature
Extraction along the Boundary
In mane biometric problems, such as detecting singular points in fingerprint
images, the quality of the result and false detection rates depend directly
on the quality of the data (image, print, recording etc). To improve the
result, pre-processing can be used. In some cases, however, it is not enough
to simply enhance the image properties (such as valleys and ridges in a
fingerprint image). Many cases of false detection happen at the boundary
of an image or at place where lines are of irregular shape. To remedy the
first situation, we propose a method based on extending the lines of the
image beyond the boundary in the projected direction so that the singular
point can be computed more precisely. For the second case, topology-based
April 2, 2007 14:42 World Scientific Review Volume - 9in x 6in Main˙WorldSc˙IPR˙SAB
Computational Geometry and Image Processing in Biometrics 127
Fig. 4.15. Skeleton extraction using Delaunay triangulation.
Fig. 4.16. Singular point detection (top to bottom): singular point close to boundary
(lower); regular pattern.
methods are traditionally used to smooth the irregularity (including the
interpolation techniques)
[
5,28
]
.
4.5.3.2. Edge Detection for Feature Lines
One example of a particular application of the above methodology is edge
detection for feature lines and feature line thinning. All existing edge