Pattern Recognition 40 (2007) 431 – 442

www.elsevier.com/locate/patcog

Robust Hausdorff distance measure for face recognition夡

Vivek E. Pa , N. Sudhab,∗
a Synopsys India, Bangalore 560 016, India
b School of Computer Engineering, Nanyang Technological University, Singapore-639798, Singapore

Received 1 July 2005; received in revised form 12 January 2006; accepted 19 April 2006

Abstract
Face is considered to be one of the biometrics in automatic person identification. The non-intrusive nature of face recognition makes it
an attractive choice. For face recognition system to be practical, it should be robust to variations in illumination, pose and expression as
humans recognize faces irrespective of all these variations. In this paper, an attempt to address these issues is made using a new Hausdorff
distance-based measure. The proposed measure represent the gray values of pixels in face images as vectors giving the neighborhood
intensity distribution of the pixels. The transformation is expected to be less sensitive to illumination variations besides preserving the
appearance of face embedded in the original gray image. While the existing Hausdorff distance-based measures are defined between
the binary edge images of faces which contains primarily structural information, the proposed measure gives the dissimilarity between
the appearance of faces. An efficient method to compute the proposed measure is presented. The performance of the method on bench
mark face databases shows that it is robust to considerable variations in pose, expression and illumination. Comparison with some of the
existing Hausdorff distance-based methods shows that the proposed method performs better in many cases.
䉷 2006 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.

Keywords: Hausdorff distance; Face recognition; Face image

1. Introduction matching. In object recognition, as shape information plays

a decisive role, Hausdorff distance between edge images is
Hausdorff distance was originally defined as a dissimi- a suitable measure for comparison.
larity measure on point sets. It later got wide acceptance Many variants of Hausdorff distance have been proposed
in image comparison [1,2]. A more specific application is for face recognition. One of them, namely modified Haus-
proposed by Huttenlocher et al. [3] for object detection and dorff distance [4] uses a neighborhood function and penalty
recognition. Their work contains a modification to the actual value to give preference to points which are located within
Hausdorff distance called partial Hausdorff distance (PHD). a given neighborhood. Guo et al. [5] proposed spatially
This modification is meant to get distance measure between weighted Hausdorff distance (SWHD) as an improvement
the most closely matching portions of the images being com- to conventional Hausdorff distance between edge images.
pared which in turn reduces the effect of occlusion in object As the name suggests, this method gives different weights to
facial regions while finding the Hausdorff distance between
夡 This work was done in part at the Department of Computer Science edge images. This is done under the assumption that the fa-
and Engineering, Indian Institute of Technology Madras, India - 600 cial regions like eyes, mouth, etc. have more importance in
036 with the support of the Department of Science and Technology, recognizing faces compared to other regions. A weight func-
Government of India (Project No. SR/FTP/ETA-23/03). tion with rectangular regions of different sizes and weights
∗ Corresponding author. School of Computer Engineering, Nanyang
which can be overlapped with the face images is used for
Technological University, Singapore - 639798, Tel.: +65 6790 6264;
fax: +65 6792 6559. this purpose. Eigenface was suggested in Ref. [6] as a bet-
E-mail addresses: vivekep@synopsys.com (Vivek E. P), ter choice for weight function than the fixed rectangular
sudha@ntu.edu.sg (N. Sudha). window function. In recognizing faces, the portions of face
0031-3203/$30.00 䉷 2006 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.
doi:10.1016/j.patcog.2006.04.019
432 Vivek E. P, N. Sudha / Pattern Recognition 40 (2007) 431 – 442

images that varies prominently for different subjects have existing methods is given in Sections 7 and 8 concludes the
more importance. The components of eigenfaces obtained paper.
from a set of reference faces of subjects will have large
values in the regions where the images have prominent
changes. 2. Conventional Hausdorff distance
Gao and Leung [7] proposed a different approach for
face recognition. In their work, line segments extracted from The Hausdorff distance is defined as a distance between
face edge curves are used as features. For comparing faces, two point sets. This distance gives a measure of dissimi-
they have defined three distances between line segments. larity between the point sets. Let A = {a1 , a2 , . . . , am } and
Later Gao proposed a distance measure based on features B = {b1 , b2 , . . . , bn } be two point sets. Then the Hausdorff
called ‘dominant points’ [8]. Dominant points are the points distance between A and B is given by
extracted from the portions of edge maps having high cur-
H (A, B) = max(h(A, B), h(B, A)), (1)
vature. While finding the dominant points, a merit factor is
associated with each of them. These factors are incorporated where h is the directed Hausdorff distance which is given by
while determining the Hausdorff distance. As faces are rep-
resented by a small set of dominant points, the storage of h(A, B) = max min a − b (2)
a∈A b∈B
faces takes less space.
All the above mentioned methods for face recognition use  ·  is the norm of a vector and h(A, B) and h(B, A) are
edge images for finding Hausdorff distance or its variants. different. The directed Hausdorff distance h(A, B) finds the
Some of them are computationally intensive as they extract point a ∈ A whose distance from its nearest point in B
additional features like eigenfaces and dominant points. As is maximum among all points in A and gives the distance
edge images contain shape information, they are suitable between a and its nearest point in B. When h(A, B) = d all
features for object detection and recognition. However, when points in A will have at least one point in B within a distance
face recognition is concerned, the appearance is important of d and there will be at least one point in A whose nearest
than the edge maps. It has been established in Ref. [9] that point in B is exactly at a distance of d. Thus as a dissimilarity
when humans recognize faces, the features like cheeks, jaw, measure from A to B, h(A, B) gives the distance between
etc. have equal importance as features like mouth, eyes, the most mismatching point in A and its nearest point in
etc. The overall appearance of the face is determined by all B. Hausdorff distance H (A, B) takes the maximum of the
these features and human recognizes a face based on overall directed distances from A to B and from B to A. When the
appearance. The intensity distribution of pixels captures this Hausdorff distance is taken between images, point sets are
appearance information. However, direct comparison of gray replaced with pixel sets containing the coordinates of feature
images is not advisable as the performance will be affected pixels.
by illumination variations unlike edge maps. One advantage of using Hausdorff distance for shape com-
In this paper, we propose a new PHD-based measure to parison is that it does not require the explicit pairing of
compare the appearance of faces. The measure is applied points in A and B. When Hausdorff distance is used directly
to face recognition based on gray images of faces instead for comparing objects, the mismatch will be large when a
of edge maps. The measure is robust to variations in a face part of an object is missing due to occlusion or when there
due to expression, illumination and slight pose differences. are outliers. This is undesirable in object matching. To over-
The partialness in the measure could tolerate expression and come this, a modification of Hausdorff distance to compare
slight pose changes. Since illumination changes have ad- between the closely matching portions of the objects is avail-
verse effect on the measure when gray images of faces are able [3]. This modified measure is called PHD. It takes the
directly considered for its computation, a transformation of K th ranked maximum value instead of the overall maximum
gray images has been proposed. The transformed face im- in the directed Hausdorff distance.
ages are less sensitive to illumination changes besides pre-
Hp (A, B) = max(hp (A, B), hp (B, A)), (3)
serving the appearance information of faces. The new mea-
sure is defined on these transformed faces. where hp (A, B) is the partial directed Hausdorff distance
The organization of the paper is as follows. The next sec- and is given by
tion defines the Hausdorff distance and its partial version.
Section 3 defines the new Hausdorff distance-based mea- hp (A, B) = K th min a − b. (4)
a∈Ab∈B
sure. It first describes the image transformation and then
defines Hpv and lists the properties of the measure. A time-
space efficient algorithm is proposed for the computation of 3. New partial Hausdorff distance-based measure
Hpv in Section 4. Its theoretical complexity is also analyzed. (Hpv ) for comparing faces
Section 5 studies the values of Hpv for face recognition. In
Section 6, the performance of Hpv for face recognition is Existing Hausdorff distance-based measures for face
evaluated using benchmark face databases. Comparison with recognition are defined between edge images of faces.
 Vivek E. P, N. Sudha / Pattern Recognition 40 (2007) 431 – 442 433

Edge images are less affected by illumination variations. 74 74 76 1 1 1

However, edge images do not carry the overall facial ap-
94 96 96 1 p 0
pearance. When the gray images that have appearance
information are directly considered for comparison, its per- 111 109 105 1 1 1
formance is affected by illumination variations. The effect
of illumination can be reduced to a large extent by rep- 1 1 1 1 0 1 1 1
resenting a pixel based on relative intensities of pixels in
its neighborhood. Thus, a pixel is represented by a vec- Fig. 1. (a) Gray values of pixels in a neighborhood; (b) elements of vector
tor rather than a single gray value. This section defines corresponding to the neighbors; (c) vector representation of p.
a PHD-based measure to compare the transformed face
images. We put forth first the notations used in this section.
Each element of the vector corresponds to the first derivative
3.1. Notations along the direction of a neighbor of the pixel. The element
takes one of the values, viz., 1, 0 and −1. Let g(p) and
M and T Model and test images
g(pn ) be the gray values of pixels p and its neighbor pn .
Mv and Tv Transformed images corresponding to M
Then the element (corresponding to pn ) of vector assigned
and T
to p takes the value 1 if g(p) > g(pn ); 0 if g(p) = g(pn );
g(p) Gray value of pixel p
−1 if g(p) < g(pn ). Fig. 1 shows a 3 × 3 window in an im-
v(p) Vector representation of pixel p
age and the vector corresponding to the pixel p at the center.
d(·, ·) Distance measure between two quantities
The transformed image preserves the intensity distribution
Hv New Hausdorff distance-based measure
and hence the appearance of face besides insensitive to illu-
Hpv New PHD-based measure
mination.
hv Directed version of Hv
For the purpose of plotting the transformed image, each
hpv Directed version of Hpv
vector is uniquely represented by a color in RGB space
f Partialness fraction
and a color image is obtained. A vector in the transformed
K Rank corresponding to f
image have eight components each having value −1, 0 or
r and c Number of rows and columns of an image
1. The green component of the color assigned to the vec-
tor is obtained by setting the components of a vector with
3.2. Image transformation value −1 to 1 and all other vector components to 0. This
results in an 8-bit binary number. For example, the green
A representation of gray images which is tolerable to component’s value of the vector [−1, 0, 0, 1, 1, −1, −1, 0]
illumination variations besides preserving the appearance in- is given by (10000110)2 or (134)10 . Similarly, red com-
formation is necessary for the comparison of faces images ponent is obtained by setting the components of vector
robust to illumination changes. The robustness to expression with value 0–1 and the remaining components to 0, and
and slight pose variations can be achieved by incorporating the blue component is obtained by setting the components
partialness in the measure. In a gray image, the sign of first- of vector with value 1–1 and the remaining components
order derivative operation at each pixel is expected to remain to 0. The green and blue component values of the ex-
same for a wide range of illumination variations. The first- ample vector taken are (01100001)2 and (00011000)2 ,
order derivative at a pixel is approximated to the difference respectively.
between the intensity values of the pixel and its neighbor The robustness of the proposed transformation to illumi-
along a direction. The representation of a pixel in terms of nation variation is illustrated using images from CMU PIE
sign of first derivative, in some arbitrary direction, at that face database. For comparing the perceptual appearance of
pixel point is not much useful in comparing faces in images. the color image, a metric called S-CIELAB [10,11] which is
A more useful representation can be obtained by consider- a spatial extension of CIELAB color metric is used. It gives
ing the 8-neighborhood of the pixel. Consider a pixel and its the error between two color images based on the difference
8-neighborhood which forms a 3 × 3 window. The signs of in the perceptual appearance. The pixel intensities give the
the first derivative taken along the direction of neighbors is amount of perceptual error. The white pixel corresponds to
expected to remain same for uniform illumination changes maximum error and the black corresponds to minimum er-
over the window. The advantage of representing a pixel in ror. Fig. 2(a) and (b) show two images of a person taken
terms of its neighborhood is that it captures the distribution under two different illumination conditions and Fig. 2(c)
of the intensities in the neighborhood. This information acts shows the error image computed between them. The color
as a signature for the pixel in finding the matching pixels images are then converted into gray images (Figure 3(a) and
when face images are compared. (b)) and their transformed images are shown in Fig. 3(c) and
In order to achieve a performance independent of illumi- (d). Fig. 3(e) is the error image between these two trans-
nation and lighting conditions, the gray image is transformed formed images. The error image is almost dark which shows
into an image whose pixels are assigned an 8-element vector. that the transformed images are less affected by illumination
434 Vivek E. P, N. Sudha / Pattern Recognition 40 (2007) 431 – 442

Fig. 2. (a) Face image of a person; (b) Face image of the same person
with illumination variation; (c) S-CILAB error image between (a) and (b).

Fig. 4. (a) and (b) Face images with normal illumination; (c) and (d)
Vector images corresponding to (a) and (b); (e) S-CILAB error image
between (c) and (d).

measure between M and T is defined as

Hv (M, T ) = max(hv (M, T ), hv (T , M)), (5)

where hv is the directed version of Hv and is given by

hv (M, T ) = max min d(m, t), (6)

m∈Mv t∈Tv

Fig. 3. (a) Face image of a person (gray version of Fig. 2(a)); (b) Face where
image of the same person with illumination variation (gray version of


Fig. 2(b)); (c) and (d) Transformed images of (a) and (b) plotted in color; m − t if v(m) = v(t),
(e) S-CILAB error image between (c) and (d). d(m, t) = (7)
L if v(m)  = v(t),

v(m) = v(t) when all the components of v(m) √ and v(t) are
variations. The effectiveness of the transformation for com- equal. L is a large value which can be r 2 + c2 + 1. l2
paring faces in different illumination is hence verified by norm has been chosen for finding distance between m and
computing S-CIELAB error image. Fig. 4(a) and (b) show t. The computation of hv (M, T ) leads to the assignment of
images of two different persons captured under normal il- a distance value to every pixel m ∈ Mv and hv (M, T ) is
lumination. Fig. 4(c) and (d) are the corresponding trans- the maximum of these distance values. The effect of direc-
formed images. The error image between 4(c) and (d) is tional lighting, shadowing, occlusion and local expression
shown in Fig. 4(e). It has larger values over nose, mouth variations results in poor performance of proposed measure
and eye regions and hence discriminate the transformed im- in face recognition.
ages of different faces. It is hence observed that the trans- The proposed measure can be improved for image com-
formed images are suitable for face recognition. The new parison applications by introducing partial matching as given
PHD-based measure Hpv is defined between the transformed in Ref. [3]. Partial matching is obtained by taking K th
images of faces. ranked distance instead of maximum in hv . The equations are
given by
3.3. Definition of Hpv
hpv (M, T ) = K th min d(m, t), (8)
m∈Mv t∈Tv
Let M and T be the face images of size r × c to be
compared. Let Mv and Tv be the transformed images. The Hpv (M, T ) = max(hpv (M, T ), hpv (T , M)), (9)
border pixels of M and T are ignored for the transformed
images as they do not have all eight neighbors. The size of where K = f ∗ size(M) for hpv (M, T ) and K = f ∗ size(T )
Mv or Tv is therefore (r −2)×(c−2). Let v(p) represent the for hpv (T , M). f is a given fraction. Hpv has the following
vector at pixel p. Then the new Hausdorff distance-based properties.
 Vivek E. P, N. Sudha / Pattern Recognition 40 (2007) 431 – 442 435

3.4. Properties of Hpv and related quantities

0 (xa,ya) (xb,yb) ... (xc,yc)

∧
1. If hv (M, T )= d , then every pixel p in Mv is at a distance (xi,yi) (xj,yj) ... (xk,yk)
1
∧
less than or equal to d from some pixel p in Tv with ..
v(p ) = v(p). .
∧
2. If hpv (M, T ) = d with a partialness of fraction f , then 8
3 1 (xp,yp) (xq,yq) ... (xr,yr)
hv between every subset of pixels of Mv of size f
∧
| M | and the entire Tv is greater than or equal to d . hpv
corresponds to the subset whose hv is minimum. In other Fig. 5. Array of linked lists of pixels.
words, hpv automatically selects the best matching por-
tion of Mv (of size f | Mv | pixels) that minimizes the
distance value of the directed version of new measure data structure for Mv and Hpv (T , M) is the maximum of
with Tv . these two distances.
3. hv , Hv , hpv and Hpv are all positive. Hv = 0 if the
transformed images Mv and Tv are same. 4.1. Algorithm
4. hpv (M, T ) = 0 ⇐⇒ hpv (T , M) = 0.
5. hpv (., .) = 0
⇒ Hpv (M, T ) = 0. Inputs: Face images M and T of size r × c
6. If hpv (., .) = 0, then there is a common best matching Output: Hpv
portion in both Mv and Tv with same vector values. Mv = VectorImage(M)
7. If one vector in Mv is different from all vectors in Tv , Tv = VectorImage(T )
then hv (M, T ) as well as Hv (M, T ) take the value L. {Construct data structures as in Fig.5 for Mv and Tv }
The different vector is mainly due to the effect of back- for j = 0 : (r − 3)
ground and noise. Hpv (M, T ) can tolerate these effects. for l = 0 : (c − 3)
hpv (M, T ) = L only if more than (1 − f )rc vectors in i = index(Mv [j ][l])
Mv are different from the vectors in Tv . Add(P [i], j, l)
8. Let SM v and ST v represent the sets of vectors in Mv and i = index(Tv [j ][l])
Tv , respectively. If SM v and ST v are equal, then Hv  = Add(Q[i], j, l);
L. If | SM v − (SM v ∩ ST v ) | or | ST v − (SM v ∩ ST v ) | end for
is greater than (1 − f )rc, then Hpv = L. end for
{Compute distance values for pixels in Mv and Tv }
s=0
for j = 0 : r − 3
4. Computation of Hpv
for l = 0 : c − 3
i = index(Mv [j ][l])
A time and space efficient algorithm is proposed to com-
dist = FindNearest(Q[index], j, l)
pute Hpv . The computation of hpv (M, T ) in Eq. (8) involves
F (s) = dist
finding the nearest pixel t in Tv for each pixel m in Mv
i = index(Tv [j ][l])
with v(m) = v(t). For n × n images, the direct computation
dist = FindNearest(P [index], j, l)
takes O(n4 ) time as each pixel m in Mv requires one scan
R(s) = dist
of image Tv . Instead of scanning the entire image, if linked
s=s+1
list of pixels in Tv is constructed for every possible vector,
end for
then the search for the nearest pixel can be limited. There
end for
are 38 possible vectors and hence an array of 38 linked lists
d = rank(F, K)
are constructed. The elements of array are the pointers to
e = rank(R, K)
the linked lists. The array index i is computed from a vector
Hpv = max(d, e)
[a0 , . . . , a7 ] as i = 7k=0 (ak + 1) ∗ 3k . The pictorial repre-
sentation of the data structure is shown in Fig. 5. In the algorithm to compute Hpv , the function VectorImage()
Once the data structure is created for Tv , the computation converts a gray level image to its vector representation. The
of hpv (M, T ) is done as follows. For each pixel in Mv , function index() computes index value of a vector for ac-
the linked list corresponding to its vector value is searched cessing a linked list in the data structure. Add() will insert
linearly for the nearest pixel and the distance to it is assigned. a pixel to the beginning of a particular linked list. P and
This leads to the assignment of distance value to every pixel Q represent the data structure shown in Fig. 5 correspond-
in Mv . The K th ranked distance is then computed. This gives ing to Mv and Tv . FindNearest() finds the nearest pixel to
hpv (M, T ). Similarly hpv (T , M) is computed by creating a given pixel from a list of pixels. To find hpv (M, T ), for
436 Vivek E. P, N. Sudha / Pattern Recognition 40 (2007) 431 – 442

0.7

0.6

0.5

Average time in Seconds

0.4

0.3

0.2

0.1

0
4096(64x64) 4816(56x86) 5504(64x86) 5888(64x92)

Image size

Fig. 6. Average computation time of Hpv for different image sizes.

each pixel in Mv distance to the nearest matching pixel in Tv average time taken for the computation of Hpv for images
is determined and stored in F . Similarly the distance values of different image sizes are displayed as bar chart in Fig. 6.
for hpv (T , M) is stored in R. The maximum of K th ranked
distances d and e of F and R arrays is the desired distance 4.2.2. Space complexity
measure Hpv . The space required by the images is O(rc). The same
space can be utilized for storing transformed images as orig-
inal images are not used for further computation. The array
4.2. Complexity analysis of pointers to the lists of pixels is of size 2 ∗ 38 . This is con-
stant independent of image size. As all the pixels in both
4.2.1. Time complexity the images will be added once to lists of pixels, the total
The vectorization of the image of size r × c can be memory used in constructing the data structures for images
done in a single scan and hence the time complexity of is 2(38 + rc) units. The arrays F and R used to hold the
VectorImage() is O(rc). index() can be computed in con- distance values occupy a memory of rc units each. Hence
stant time. Insertion of all pixels in the images to correspond- the asymptotic space complexity of the algorithm is O(rc).
ing lists takes O(rc) time. As FindNearest() involves linear As data structures P and Q need not be computed simulta-
search of a list of pixels, the time taken by this operation neously, the actual memory usage can be reduced by using
depends on the length of the list. To find Hpv between two same array for both P and Q. Similarly, a large array of
images, FindNearest() has to be executed 2rc times. Hence, length rc is sufficient for both F and R.
the time required to find distance will be O(drc) where d
is the length of the largest list. There exists algorithms [12]
to find K th ranked value from an unsorted array in linear 5. Suitability of Hpv for face recognition
time and hence rank() has a time complexity of O(rc). The
entire algorithm’s time complexity is therefore O(drc). The Recognition based on the new measure Hpv is expected
value of d can be 1 when rc
38 and will be rc when all to be robust to expression changes, pose differences and
the pixels in an image have the same vector value. illumination variations in face images. A frontal face with
The actual computation time has been taken for face im- only expression variations can be viewed as local variations
ages of different sizes. For images of each size, more than in the image. As Hpv can perform partial matching, face
thousand computations were done and the average time of all recognition invariant to expression can be achieved. Pose
such computations were taken. The algorithm has been im- variation can cause two types of changes in the distribution
plemented in C programming language and the experiments of vectors over the 2-D plane. (1) It shifts the distribution.
were done on a uniprocessor system (Intel Pentium(R)-4, (2) It causes some portions of the distribution in frontal face
1.7GHz, 1GB RAM) running Linux operating system. The to disappear and creates new portions in the pose-variant
 Vivek E. P, N. Sudha / Pattern Recognition 40 (2007) 431 – 442 437

Table 1
Hpv values for expression varying faces shown in Fig. 7

(a) (b) (c) (d) (e)

(f) 5.099 6.403 6.324 8.000 5.830

(g) 6.000 3.606 6.082 7.071 6.082
(h) 6.082 5.830 4.000 7.211 5.656
(i) 6.708 7.000 6.708 3.162 7.000
(j) 6.082 5.830 6.082 7.071 4.123

Table 2
Hpv values for illumination varying faces shown in Fig. 7

(a) (b) (c) (d) (e)

(k) 3.162 5.830 6.082 7.000 6.082

(l) 7.211 5.099 7.211 8.062 7.071
(m) 6.708 6.082 4.472 7.071 6.082
(n) 6.708 7.071 6.324 4.472 6.403
(o) 6.403 6.403 6.403 7.071 5.000
Fig. 7. (a), (b), (c), (d) and (e) Normal faces; (f), (g), (h), (i) and (j)
Expression varying faces; (k), (l), (m), (n) and (o) Illumination varying
faces.
Table 3
Hpv values for pose varying faces shown in Fig. 8

(a) (b) (c) (d) (e)

(f) 3.162 6.403 6.082 6.082 10.049

(g) 6.403 4.472 7.280 5.656 9.486
(h) 5.830 6.708 4.123 6.403 10.000
(i) 5.385 5.830 5.830 4.123 8.062
(j) 9.899 10.049 10.049 8.062 4.472

faces. These distance values support the usefulness of Hpv

for face recognition.
Fig. 8. (a), (b), (c), (d) and (e) Normal faces; (f), (g), (h), (i) and (j) Pose
varying faces.
6. Performance evaluation of Hpv for face recognition

face. As PHD can tolerate the changes in the positions of the The performance of the new measure was evaluated for
feature points to some extent, it is expected to handle some face recognition. Face recognition involves classifying a
amount of pose variations. As the new measure is based given face image as one of the predefined identities spec-
on the relative intensities of neighbors and not on absolute ified by the model face images of subjects. It is done by
intensity values, it is invariant to lighting and illumination finding Hpv between the given face and each of the model
conditions. faces and assigning the identity of the model face that gives
Hpv has been computed between several sample faces the smallest Hpv . The results of the experiments are given
and their values have been studied for application to face as recognition rate which is the ratio of the number of im-
recognition. Ideally, irrespective of variations in a face, the ages correctly classified to the total number of images in the
Hpv values between same faces and between different faces test set. Bench mark face databases consisting of face im-
should be well separated to use it for face recognition. The ages with these types of variations were used to evaluate the
values of Hpv are computed between normal faces and ex- Hpv -based face recognition system.
pression as well as illumination varying faces of five dif-
ferent persons. The face images are shown in Fig. 7. The 6.1. Face databases used for the studies
normal faces and their pose varying ones are shown in
Fig. 8. Tables 1–3 show Hpv values between normal faces For comparing the performance of Hpv with existing
and their expression, illumination and pose variations, re- methods, face databases consisting of images with different
spectively. In all the tables, the distance values between same types of variations are considered. The AR face database
faces are found to be smaller than those between different [13] from Purdue University consists of images of 126
438 Vivek E. P, N. Sudha / Pattern Recognition 40 (2007) 431 – 442

Fig. 9. Sample faces of a person from AR face database.

Fig. 10. Sample faces of a person from Yale face database.

consists of 15 subjects each having 11 images. The images

have expression variations as well as illumination variations
due to a light source positioned at right, left and center with
respect to the face. Some of the images of a person are shown
in Fig. 10. The Bern face database consists of 30 subjects.
Each subject has two images of five different poses. The
Fig. 11. Sample faces of a person from Bern face database. pose variations are due to face looking straight, downward,
upward, left and right. Sample images are shown in Fig. 11.

subjects (70 men and 56 women). The images were taken 6.2. Influence of f on the performance of Hpv
in two sessions. The expression and illumination varying
images were used for the performance studies. Fig. 9 shows The recognition rate of Hpv is expected to be low for
sample images of a subject. The Yale face database [14] both high and low values of f . When the value of f is too

Smiling
100
Angry
Screaming
90

80
Recognition rate in %

70

60

50

40

30

20

10
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Fraction f

Fig. 12. Recognition results for expression varying faces in AR face database.
 Vivek E. P, N. Sudha / Pattern Recognition 40 (2007) 431 – 442 439

expressions as seen in the samples shown in Fig. 9. The

performance of Hpv on smiling and angry expressions is
almost same for large f and it differs for smaller values of
f . This has been analyzed. Some correctly classified smiling
images and misclassified angry faces are shown in Fig. 13.
Though the variation in the smiling face from their normal
face is more when compared to the angry face, the angry
faces displayed in the figure are misclassified due to the tilt
in these faces. It is found that such tilt is less in the case
of smiling faces in the database and hence the performance
is better for small f that considers small similar portions
unaffected by expression.
Fig. 14 shows the recognition rate for different values
of f for faces with illumination variations due to direc-
tional lighting. The fact that recognition rate starts to fall for
moderately high values of f can be explained with the
Fig. 13. (a) and (d) Normal faces; (b) and (e) Faces with smiling expres- transformed images corresponding to a normal face and its
sion; (c) and (f) Faces with angry expression.
illumination varying images shown in Fig. 15. Due to the
effect of point light source focused on to the face, the gray
low, the Hpv is computed between the similar regions in value distribution of a part of a face is disturbed and tend
the faces. The features that discriminate the faces are not to be uniform. This uniformity in the gray values of fa-
considered for the computation. This leads to poor recogni- cial regions results in red patches in the transformed images
tion rate. When the value of f is too high, the background shown in the figure. The images which are illuminated from
and variations in expression, pose and illumination affect both sides, nearly half of the facial regions are affected. For
the performance. such images, recognition rate comes down for values of f
Fig. 12 shows the performance of Hpv for various val- greater than 0.5. In all the three cases, the recognition rate
ues of f on expression varying face images from AR face is found to be quite high for values of f as low as 0.2.
database. The performance for screaming expression is The only variation involved in these images is due to di-
found to be lower than other expressions. This is due to rectional lighting. Hence classification made by considering
the fact that the variations in face due to screaming expres- even small portions of the images is expected to give good
sion is larger than the variations due to smiling and angry results.

100

90

80

70
Recognition rate in %

60

50

40

30

20
light source at left side
10 light source at right side
light sources at both sides
0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Fraction f

Fig. 14. Recognition results for illumination varying faces in AR face database.
440 Vivek E. P, N. Sudha / Pattern Recognition 40 (2007) 431 – 442

Fig. 17. Examples of illumination varying faces from Yale database.

The influence of f on Hpv was also studied on pose

varying faces of Bern face database. When frontal and pose
varying face images are compared, there are portions of
face that appear in one image and are missing in the other
image. When Hpv is computed for a large value of f , such
portions in the images affect the recognition performance.
Fig. 15. Illumination varying faces and their transformed images. This causes the curve in Fig. 18 to fall for large values of
f . When f is small, similar to all other cases recognition
rate falls. From the plots shown in Figs. 12, 14, 16 and 18,
we can observe that good rate is achieved for the values
The performance of Hpv for different values of f on Yale of f around 0.5.
database is shown in Fig. 16. The Yale database has both
expression and illumination varying images. Due to the ef-
fect of shadow, in some of the illumination varying images 7. Comparison studies with existing methods
nearly half of the face is darkened. Examples are shown in
Fig. 17. This causes fall in recognition rate when the value The performance of the new measure is compared with
of f is more than 0.5. For higher values of f the expression PHD on edge maps [3], doubly modified Hausdorff distance
variations also affects the performance. For lower values of (M2HD) on edge maps [4], Hausdorff distance based on
f , recognition rate falls. This is because the closely match- line edge map (LEM) [7], SWHD [5] and spatially eigen-
ing regions of faces are only considered for finding Hpv weighted Hausdorff distances (SEWHD and SEW2HD) [6].
and they do not have the facial parts that discriminate the The results for Hpv are produced for f = 0.5. This choice
faces. of f is based on the overall performance for different

100

90

80

70
Recognition rate in %

60

50

40

30

20

10

0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Fraction f

Fig. 16. Recognition results for expression and illumination varying faces in Yale face database.
 Vivek E. P, N. Sudha / Pattern Recognition 40 (2007) 431 – 442 441

100

90

80

70
Recognition rate in %

60

50

40

30

20

10

0
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
Fraction f

Fig. 18. Recognition results for pose varying faces in Bern face database.

databases. The results for PHD are computed for values of Table 4
f = 0.5, 0.55, 0.6, . . . , 0.9 and the best recognition rate is Comparison study with AR database faces varying in expression
reported. Three different databases viz. AR face database Test faces with expression Recognition rate in %
[13], Bern face database [15] and Yale face database [14]
PHD LEM M2HD Hpv
which were described in the previous section were used for
comparison studies. Smiling 88.88 78.57 52.68 100
Angry 77.77 92.86 81.25 96.82
Screaming 46.82 31.25 20.54 81.74
7.1. Studies with faces varying in expression
Table 5
The performance of Hpv on expression varying face im- Comparison study using Bern database faces varying in pose
ages is compared with some of the existing face recog-
Test faces Recognition rate in %
nition methods using AR face database [13]. One normal
frontal image corresponding to each person is included in PHD LEM M2HD Hpv
the model set. The test set consists of three images per per- Looks right/left 65 74.17 50 86.66
son with smiling, screaming and angry expressions. The per- Looks up 43.33 70 65 85
formance of the new method is compared with PHD, LEM Looks down 61.66 70 67.67 95
Average 58.75 72.09 58.17 88.33
and M2HD. The results for M2HD and LEM are obtained
from Ref. [7]. The results for different methods are given in
Table 4. The performance of Hpv is found to be superior to face is taken as the model image. Eight pose varying face
the existing methods. The recognition rate of Hpv on faces images are used as test images. The performance of the
with screaming expression is found to be less than that of recognition system based on the new measure is compared
other expressions. This is due to the fact that the variation with PHD, LEM and M2HD and the results are shown in
in face caused by screaming expression is larger than that Table 5. The performance of Hpv is found to be better than
caused by smiling and angry expressions. the existing methods in all cases.

7.2. Studies with faces in different poses 7.3. Studies with faces varying in illumination

The comparison study on pose varying faces is carried out The performance of Hpv is compared with the existing
with Bern face database [15]. For each subject, the frontal variants of Hausdorff distance using the face images of Yale
442 Vivek E. P, N. Sudha / Pattern Recognition 40 (2007) 431 – 442

Table 6 face images based on partial Hausdorff distance has been

Comparison study with Yale database faces varying in illumination and defined and its time efficient implementation has been given.
expression
Comparison of the recognition method based on the pro-
Method Recognition rate in % posed measure with some of the existing methods that work
on edge maps of faces using benchmark faces varying in
PHD 84
M2HD 80 expression, illumination and slight pose shows that the pro-
SWHD 82 posed method outperforms the existing ones. This is due
SEWHD 85 to appearance-based comparison of faces performed by the
SEW2HD 89 new measure as human does.
Hpv 95.33

References
Table 7
Comparison study using illumination-varying images from AR database [1] R. Shonkwiler, An image algorithm for computing the Hausdorff
distance efficiently in linear time, Inf. Process. Lett. 30 (2) (1989)
Test faces with Recognition rate in % 87–89.
[2] R. Shonkwiler, Computing the Hausdorff set distance in linear time
PHD LEM M2HD Hpv
for any lp point distance, Inf. Process. Lett. 38 (4) (1991) 201–207.
Left light on 88.88 92.86 82.14 99.2 [3] D.P. Huttenlocher, G.A. Klanderman, W.A. Rucklidge, Comparing
Right light on 84.92 91.07 73.21 97.61 images using the Hausdorff distance, IEEE Trans. Pattern Anal.
Both lights on 64.28 74.11 54.46 84.12 Mach. Intell. 15 (9) (1993) 850–863.
[4] B. Takacs, Comparing face images using the modified Hausdorff
distance, Pattern Recognition 31 (12) (1998) 1873–1881.
[5] B. Guo, K.-M. Lam, K.-H. Lin, W.-C. Siu, Human face recognition
database varying in illumination and expression. The vari- based on spatially weighted Hausdorff distance, Pattern Recognition
ants are PHD, M2HD, SWHD, SEWHD and SEW2HD. The Lett. 24 (1–3) (2003) 499–507.
[6] K.-H. Lin, K.-M. Lam, W.-C. Siu, Spatially eigen-weighted Hausdorff
results are shown in Table 6. The results of the variants
distances for human face recognition, Pattern Recognition 36 (8)
of Hausdorff distance are obtained from Ref. [6]. In an- (2003) 1827–1834.
other study, the illumination varying images from AR face [7] Y. Gao, M.K. Leung, Face recognition using line edge map, IEEE
database were used to compare the new method with PHD, Trans. Pattern Anal. Mach. Intell. 24 (6) (2002) 764–779.
LEM and M2HD. There are three illumination varying im- [8] Y. Gao, Efficiently comparing face images using a modified Hausdorff
distance, in: IEE Proc. Vision, Image Signal Process., vol. 150, 2003,
ages per subject, viz., with a light source on left side of
pp. 346–350.
face, with a light source on right side of face and with light [9] P. Sinha, Recognizing complex patterns, Nature Neurosci. 5 (2002)
sources on both sides. The performance of LEM and M2HD 1093–1097.
are taken from Ref. [7] and the comparison study is reported [10] X. Zhang, B.A. Wandell, A spatial extension of CIELAB for digital
in Table 7. Hpv performs better than the existing methods. color-image reproduction, J. Soc. Inf. Display 5 (1997) 61–63.
[11] X. Zhang, J.E. Farrell, B.A. Wandell, Applications of a spatial
extension to CIELAB, in: Proceedings of SPIE Conference on Very
High Resolution and Quality Imaging II, 1997, pp. 154–157.
8. Conclusion [12] T.H. Cormen, C. Stein, R.L. Rivest, C.E. Leiserson, Introduction to
Algorithms, second ed., McGraw-Hill Higher Education, New York,
A new partial Hausdorff distance-based method for face 2001.
recognition has been proposed in this paper. The recog- [13] A. Martinez, R. Benavente, The AR face database, in: CVC Technical
Report, no. 24, 1998.
nition of faces is done by comparing the appearance of
[14] Yale university face database, http://cvc.yale.edu/projects/yalefaces/
faces embedded in the gray images of them. This involves yalefaces.html .
a transformation of gray face images which are less variant [15] Bern university face database, ftp://ftp.iam.unibe.ch/pub/images/
to illumination changes when compared to the actual gray faceimages/ .
images. A measure namely Hpv to compare the transformed