Gray_Hausdorff_Distance_Measure_for_Comparing_Face_Images.pdf
(
805 KB
)
Pobierz
591030005 UNPDF
342
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006
Gray Hausdorff Distance Measure
for Comparing Face Images
E. P. Vivek and N. Sudha
Abstract—
Human face recognition is considered to be one of the
toughest problems in the domain of pattern recognition. The varia-
tions in face images due to differing expression, pose and illumina-
tion are some of the key issues to be addressed in developing a face
recognition system. In this paper, a new measure called gray Haus-
dorff distance (denoted by ) is proposed to compare the gray
images of faces directly. An efficient algorithm for computation of
the new measure is presented. The computation time is linear in the
size of the image. The performance of this measure is evaluated on
benchmark face databases. The face recognition system based on
the new measure is found to be robust to pose and expression vari-
ations, as well as to slight variation in illumination. Comparison
studies show that the proposed measure performs better than the
existing ones in most cases.
Index Terms—
Euclidean distance transform, face image, face
recognition, gray Hausdorff distance.
was intended to get a partial match between images. Subse-
quent work on image comparison using this distance includes
fast searching of face libraries [5], object tracking in video [6],
video sequence matching [7], etc.
A measure that is insensitive to local nonrigid distortions in
objects is required for comparing faces with such distortions
due to variations in pose and expression. Hausdorff distance
measure has this property. For face recognition, a number of
variants of the actual distance were proposed. One of these
variants introduce the notion of penalties associated with
a neighborhood function [8]. It works with the assumption
that the corresponding points in the compared images must
fall within a given neighborhood. Another variant, namely,
spatially weighted Hausdorff distance gives more importance
to the edge points located at crucial facial features like eyes
and mouth [9]. To capture these dominant features, a weight
function that computes weights according to the importance
of different facial features is used. The weight function uses
rectangular windows of different weights for this purpose. An
attempt for improving this method has been made by using
eigenfaces for weight function instead of rectangular windows
[10]. The components of eigenfaces corresponding to the re-
gions where the training images have large variations will have
large magnitudes. For distinguishing faces, the regions where
the face images have larger variations are more important than
those regions which have less variations.
An entirely different approach was put forward by Gao and
Leung [11]. In this, they used line segments approximated from
face edge map. Three distance measures were defined between
these line segments. Later Gao also proposed a distance based
on a facial feature called “dominant points.” Dominant points
[12] are the points extracted from portions of the edge map
having high curvature. All these approaches require Hausdorff
distance to be computed between edge map or equivalent binary
images of faces. Apart from transforming gray face images to bi-
nary maps, these existing approaches extract additional features
like eigenfaces and dominant points, which are computationally
intensive operations.
Edge images are normally shape descriptors, and they are
quite useful for object detection. In the case of faces, humans
discriminate faces by appearance [that carries three-dimen-
sional (3-D) shape information], and this is embedded in pixel
intensities of face images. Studies [13] have shown that fea-
tures such as cheeks, jaw, etc., are equally important in face
recognition along with features like nose, mouth, etc. Appear-
ance information includes all these features. In this paper, a
new Hausdorff distance based measure called
gray Hausdorff
distance
is proposed to compare gray images directly. It is
applicable for automatic recognition of faces by appearance.
I. I
NTRODUCTION
physiological characteristics is gaining importance. One
method of identification is using images of human faces. Face-
based identification is a nonintrusive method and hence it is
useful for security applications. One important such application
is automatic video surveillance. The faces in the images cap-
tured by a surveillance camera may vary in pose, expression and
illumination. The design of a face recognition system robust to
these variations is a challenging task.
A measure that has been used for comparing images is Haus-
dorff distance [1], [2]. Hausdorff distance has been used in ob-
ject detection [3] and recognition [4]. Recently, it has been in
use for face recognition. Hausdorff distance was originally de-
fined on point sets as a measure of dissimilarity between two
point sets. The dissimilarity measure is given by a scalar quan-
tity . The definition of Hausdorff distance is, for any point
in a set there is atleast one point in the other set within a dis-
tance of . One of the earliest work on using this distance in
computer vision was by Huttenlocher
et al.
[4]. They proposed
this distance as a measure of similarity between edge images.
Their work contains a modification to the actual distance, called
partial Hausdorff distance, for comparing partial objects. This
Manuscript received August 8, 2005; revised April 18, 2006. This work was
supported by the Department of Science and Technology, Government of India
under Project SR/FTP/ETA-23/03. The associate editor coordinating the review
of this manuscript and approving it for publication was Prof. Davide Maltoni.
E. P. Vivek is with Synopsys India, Bangalore 560 016, India (e-mail:
vivekep@synopsys.com).
N. Sudha is with the School of Computer Engineering, Nanyang Technolog-
ical University, Singapore 639798 (e-mail: sudha@ntu.edu.sg).
Digital Object Identifier 10.1109/TIFS.2006.879294
1556-6013/$20.00 © 2006 IEEE
A
UTOMATIC identification of a person based on his/her
VIVEK AND SUDHA: GRAY HAUSDORFF DISTANCE MEASURE FOR COMPARING FACE IMAGES
343
Further, the new measure is computationally efficient and it
gives better performance than the existing methods based on
Hausdorff distance.
The paper is organized as follows. The Section II defines
the Hausdorff distance. Section III describes the proposed gray
Hausdorff distance and its computation. The application of the
new measure to face recognition is explained in Sections IV and
V and concludes the paper.
III. P
ROPOSED
G
RAY
H
AUSDORFF
D
ISTANCE
M
EASURE
First, we put forth the notations used for computation of the
new measure.
and
model and test images;
and
quantized images corresponding to
and
;
number of most significant bits retained for
quantization of
and ;
set of pixels in
with quantized
II. C
ONVENTIONAL
H
AUSDORFF
D
ISTANCE
AND
R
ELATED
M
EASURES
The Hausdorff distance was originally proposed to measure
the dissimilarity between point sets. Consider point sets
and
gray value ;
distance transform corresponding to
. The Hausdorff dis-
distance measure between two quantities;
directed gray Hausdorff distance;
gray Hausdorff distance;
partial gray Hausdorff distance;
directed partial gray Hausdorff distance;
partialness fraction;
rank corresponding to ;
tance between and is given by
(1)
where
is the directed Hausdorff distance from to
(2)
and
number of rows and columns of an image.
where is the norm of a vector. In the case of images, point
sets are pixel sets containing the coordinates of feature pixels
(for example, edges).
The directed Hausdorff distance will find the point
which is farthest from any point in , and gives the
distance between and its nearest point in . In other words,
will find the most mismatching point in , and finds
the distance between that particular and its closest matching
point in . Thus if , for any point in there
will be at least one matching point in within a distance of
, and there should be at least a single point in that is exactly
at a distance of from its nearest neighbor in . The Hausdorff
distance, tries to estimate the dissimilarity between
the point sets and by finding the maximum of the directed
Hausdorff distances between and ( and ).
By considering and as sets of feature points of two
objects, Hausdorff distance can be used as a measure of mis-
match between the objects. In the case of images, edges can be
the features. The Hausdorff distance differs from many of the
shape comparison methods in the sense that there is no explicit
pairing between the points of and . The disadvantage of
using conventional Hausdorff distance is that the degree of mis-
match will be large when even a part of an object is missing
due to occlusion, or when there are outliers. This is undesirable
in object matching applications. In order to have a match be-
tween closely resembling portions of objects, partial Hausdorff
distance has been proposed in [4] which is a mod-
ification of the conventional Hausdorff distance. This is done
by taking the th-ranked maximum value instead of taking the
overall maximum in the directed Hausdorff distance
A. Definition of the Measure
The existing Hausdorff distance based face recognition sys-
tems work on edge maps of face images which contain primarily
the structure but not the appearance of the faces. Here, we de-
fine a variant of conventional Hausdorff distance that is applicable
for gray images of faces. Consider face as a distribution of gray
values of pixels over a two-dimensional (2-D) plane. The distri-
bution forms a 3-D discrete surface in which the height of a point
on the surface equals the gray value of corresponding pixel. We
propose a similarity measure to compare the distribution of gray
values and hence comparing the appearance of the faces. The new
measure considers separate pixel sets corresponding to each of the
gray values. As 8 bits are used for representing gray values, there
will be 256 different pixel sets. A pixel with gray value belong
to the th pixel set. Instead of exact gray value, if pixels are rep-
resented by the most significant bits of their gray values, where
, the total number of pixel sets will be reduced. The image
obtained in this way is a quantized version of the actual image. By
choosing a small , the perceptual appearance of the image can be
retained, and the appearance based comparison is still preserved.
Fig. 1 shows an image and its quantized versions for various values
of . The advantage of retaining only the most significant bits of
a gray value is that it can tolerate slight changes in lighting con-
ditions. The quantized image leads to different pixel sets. For
comparing two images, corresponding sets in both the images are
compared first. Let and be the
pixel sets obtained from quantized images and of images
and , respectively. The and consist of the coordinates of
pixels with the quantized value . Any two pixel sets
(or ) and
(3)
(or ) are disjoint. The
gray Hausdorff distance
between and is defined as the maximum of the Hausdorff
distances between the corresponding pixel sets of images
where
is called the partial directed Hausdorff distance
(4)
(5)
344
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006
Fig. 1. (a) Original image. (b)–g) are the quantized images with
n=2
,3–7, respectively.
In order to define partial gray Hausdorff distance , which is
actually applied for comparing faces, (5) is redefined as
Proof
: Equation (8) leads to the assignment of a distance
value to every pixel
in
. This distance is the min-
imum of distances from
to pixels in
with the same
(6)
gray value of . As given by (7),
is the max-
imum
of these distances assigned to the pixels in
.
where
is the directed gray Hausdorff distance. It is given by
Hence, every pixel in
is at a distance less than or equal
to from some pixel in
with the same gray value of .
(7)
2) If with a partialness of fraction , then
between every subset of of size and the
entire is greater than or equal to . corresponds
to the subset whose is minimum. In other words,
automatically selects the best matching portion of with
size that minimizes the directed gray Hausdorff
distance with .
Proof
: As given by (9), is the th ranked dis-
tance from the ascending order of distances assigned to
pixels in where . The pixels in whose
distance values are less than or equal to form the best
matching portion of of size that minimizes the di-
rected gray Hausdorff distance with . Any other subset
of of size includes pixels with distance greater than
or equal to in place of pixels with distance less than or
equal to . The between these subsets and the
entire is hence greater than or equal to .
3) When the quantized values of
where
if is non-empty
otherwise
(8)
where gives the distance between and its
nearest point in . The norm taken is Euclidean. If is
empty, then the distance is . is a large value which can be
.
The effects of outliers, occlusion and local variations result
in poor performance of the proposed gray Hausdorff distance in
face recognition. To reduce these effects and to perform partial
match between images, the directed gray Hausdorff distance as
defined in (7) can be modified by taking the th-ranked distance
from the ascending order of distances
,
and
varies from 0 to
, instead of taking the maximum. That is
(9)
pixels of
and
are same, both
and
and hence
Instead of giving the value of directly, it can be specified as a
fraction of the total number of pixels in the image sets or
depending on the direction of the distance. That is,
and for and , respectively.
denotes the number of pixels in . The partial gray
Hausdorff distance is given by
are zero. if .
Proof:
In the computation of , the pixels
of whose quantized values are same as those pixels
of are assigned the distance value zero. When the dis-
tance values of pixels in are ascending ordered, atleast
zeros occur at the beginning and hence the
given by the th ranked distance is zero. Sim-
ilar argument holds for
and, hence,
(10)
as well as
are zero. However,
is zero only
when the quantized value of every pixel in
is the same
For each pixel in a quantized image, the nearest pixel with the
same value in the other quantized image is found by scanning
this image once. It takes checks. This is repeated for all
the pixels in both the images. Thus, for images of size , the
distance assignment to pixels takes computations. The
time complexity for sorting distance values using the simple
sorting procedure “insertion sort” is
as that of
.
4)
, , , and are all positive.
Proof:
, , , and are based on the Euclidean
distance between pixels represented by their coordinates
and this distance value is either zero or a positive number.
. Hence, the direct
computation of
takes
computations.
C. Efficient Computation of
In order to find the gray Hausdorff distance between two im-
ages, we need to determine for each pixel in an image, the dis-
tance to the nearest pixel with the same gray value in the other
image. This can be done efficiently by constructing distance
transform [14]. The distance transform is a 2-D array of distance
B. Properties of ,
,
, and
1) If
, then every pixel in
is at a distance
less than or equal to from some pixel in
with the same
gray value of .
VIVEK AND SUDHA: GRAY HAUSDORFF DISTANCE MEASURE FOR COMPARING FACE IMAGES
345
values defined on a binary image consisting of foreground and
background pixels. Here, the pixel set or is represented
as a binary image with foreground pixels being the pixels in the
set. All other pixels are considered to be the background pixels
of the image. For each pixel in the binary image, the distance
transform results in the distance to its nearest foreground pixel.
Euclidean norm has been chosen for distance computation.
Let and be Euclidean distance transforms of binary
images corresponding to and . Using these distance trans-
forms, the is computed as follows. For each pixel in
the pixel set , the distance to the nearest pixel in can be
given by the distance value at . This leads to the assign-
ment of a distance value for every pixel in . The th-ranked
value when these distances are in ascending order gives the par-
tial directed gray Hausdorff distance from to . Simi-
larly, the is obtained from to . The maximum of these
two distances gives the partial gray Hausdorff distance. The al-
gorithm to find partial gray Hausdorff distance is given below.
Fig. 2. Average computation time of
H
for different image sizes.
Algorithm
Compute
end for
Inputs
: face images
and .
end for
Output
: partial gray Hausdorff distance
between
and .
Find th ranked values and of arrays and
Steps
:
1) Obtain quantized images
and
from
and .
2) Construct pixel sets
and
from
and
, respectively.
3) Find distance transforms
and
1) Complexity Analysis of the Algorithm:
Let and be of
size . Then the quantization in Step 1 is done by scanning
the images once. The construction of the pixel sets in Step 2 from
the quantized images also requires a single scan on these images.
Both these steps therefore takes computations. The Eu-
clidean distance transform of a binary image can also be computed
in time [14]. There are distance transforms computed
in Step 3 and, hence, this step takes computations. In
the computation of , the construction of and arrays take
time. There are algorithms [15] to find th ranked value
from an unsorted array of size in time . Step 3 is the time
consuming part of the algorithm and, hence, the time complexity
of the algorithm is . However, the maximum value of
is only 8. Therefore, the time complexity will be .
The actual computation time has been taken for face images
of different sizes. For images of each size, more than thousand
computations of between images were done. The average
time taken for all such computations was found out. and have
been chosen as 5 and 0.85 which are obtained as optimal values
from the studies presented later in Section IV-A. The algorithm
has been implemented in C programming language and the exper-
iments were done on a uniprocessor system (Intel Pentium(R)-4,
1.7 GHz, 1-GB RAM) running Linux operating system. The av-
erage times taken for the computation of for different image
sizes are plotted in Fig. 2. The curve is almost linear.
While space complexity is concerned, two arrays of size
are required to store face images and . As the actual pixel
values are not required in the algorithm later, the same arrays
can store quantized images. The pixel sets
corresponding to
and
, respectively, and obtain
from the distance
transforms:
;
for
do
.
Compute
and
for
do
for
do
Assigning distance values to pixels in
if
then
end if
Assigning distance values to pixels in
if
then
end if
end for
and need not
346
IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, VOL. 1, NO. 3, SEPTEMBER 2006
Fig. 3. Sample face images from various databases. (a) and (b) Yale images; (c) and (d) AR images; (e) and (f) Bern images; and (g) and (h) ORL images.
be explicitly stored, as they can be identified from the quan-
tized images. For the computation of , only a pair of dis-
tance transforms are required at a time. Hence, the memory re-
quirement for the distance transform is . The arrays and
defined in the algorithm take memory elements. The en-
tire algorithm therefore requires, at the most,
memory elements. Hence, the space complexity is also
.
A. Performance Evaluation
The partial gray Hausdorff distance is robust to pose and
expression variations, as well as minor illumination and scale
changes and mis-alignment. The -based method for face
recognition is evaluated on benchmark databases consisting of
face images varying in expressions, pose and illumination. Four
different databases are considered for performance and compar-
ison studies. 1) The Yale face database [16] consists of 15 sub-
jects each with 11 images. The images have significant expres-
sion changes as well as differing illumination conditions due
to positional changes of light source such as left side illumi-
nation and right side illumination. 2) The Bern university face
database [17] has 30 subjects, each with ten images varying in
pose such as looking upward, downward and to the sides. 3) The
AR face database [18] from Purdue University has 126 subjects
with images taken in two sessions. Each session has 13 images
per subject with variations in expression, illumination and oc-
clusion caused by covering the face with scarf. The images of
the first session with expression variations were considered for
comparison studies. 4) The ORL face database [19] consists of
40 subjects with ten images per subject. The faces have mild ex-
pression and considerable pose variations as well as small scale
changes caused by head movement. The sample images of dif-
ferent databases are shown in Fig. 3.
The performance of the method is measured in terms of
recognition rate, which is the ratio of the number of test images
correctly classified to the total number of images in the test
set. Figs. 4–6 show the plots of recognition rates for different
databases and for different values of and . From the plots, it
can be observed that for low values of , the similar portions
in the quantized images of different faces are considered for
matching which causes considerable misclassifications. Hence,
the recognition rate decreases for low values of as seen in
some curves. When is too high, the recognition is affected
by the background and variations due to pose, expression and
directional lighting. The recognition rate is therefore decreasing
for very high values of . The rate remains high for in the
range for all . In the case of , the recognition
rate increases as increases. This is because the appearance of
the face is better for higher . However, there is no significant
improvement in performance for greater than 5. From these
studies on benchmark databases, the optimal values for and
to achieve good recognition performance can be determined.
can be set to 0.85 and to 5.
The recognition method can be applied to person authenti-
cation apart from identification. Authentication requires setting
a threshold distance value. Given a new face and the claimed
identity of the face, is computed between the new face
and the model corresponding to the claimed identity. If it is
IV. A
PPLICATION OF
TO
F
ACE
R
ECOGNITION
Face recognition involves classifying a given face image as
one of the subjects whose model face (normal frontal) images
are available. While the existing Hausdorff distance-based mea-
sures for face recognition are defined between the binary edge
images of faces which contain primarily the structural informa-
tion, the proposed measure gives the dissimilarity between the
appearance of faces. Face recognition is done by finding be-
tween the given face and each of the model faces, and assigning
the identity of the model face that gives the smallest .As
partial gray Hausdorff distance measures the dissimilarity
between face images of different subjects in terms of appear-
ance, but still tolerates the variability in face images of same
subject, it is a useful tool for face recognition.
Consider the frontal faces of a subject with only expression
changes. Though the changes in expression vary the distribution
of the gray values of a subject’s normal face, the variation is
limited and local. As partial gray Hausdorff distance tolerate
some amount of variability in the distributions of gray values of
the images, it is expected to be robust to changes in expression.
The slight pose variations although lead to disturbance in the
distribution of gray values and a shift in facial parts from their
locations in the model frontal face, it still retains the appearance
of facial parts. The ability of to perform partial match can
solve recognition invariant to pose to some extent. As directed
gray Hausdorff distance by definition identifies for each pixel in
an image, the nearest matching pixel in the other image, can
tolerate some amount of shift in facial parts. In order to handle
wide pose variations, templates of faces in different poses can
be stored during registration.
As depends on the pixels’ intensities, it is sensitive to
lighting conditions. However, if there is directional lighting,
only a part of face image is affected. Since partial matching can
be performed using , the effect of directional lighting can
be reduced. Further in our method, as the images are quantized,
a range of gray values correspond to a quantized level. Small
changes in illumination lead to changes in almost all pixel in-
tensities, but do not significantly affect the quantization values.
As is computed from quantized images, it is invariant to
small changes in illumination.
Plik z chomika:
Kuya
Inne pliki z tego folderu:
Behavior_Forensics_for_Scalable_Multiuser_Collusion_Fairness_Versus_Effectivenes.pdf
(964 KB)
Block_QIM_Watermarking_Games.pdf
(869 KB)
Correspondence.pdf
(176 KB)
Dual_Protection_of_JPEG_Images_Based_on_Informed_Embedding_and_Two-Stage_Waterma.pdf
(1549 KB)
Estimation_of_Message_Source_and_Destination_From_Network_Intercepts.pdf
(613 KB)
Inne foldery tego chomika:
2006-1
2006-2
2006-4
2007-1
2007-2
Zgłoś jeśli
naruszono regulamin