Page 257 - Innovations in Intelligent Machines

250 J. Gaspar et al.
in our case edge images. A number of Hausdorff distance measures are defined
by the following equations:

H(A, B) = max(h(A, B),h(B, A)) (21)
where
h(A, B) = max min a − b (22)
a∈A b∈B
Here A and B represent sets of points. h(A, B) measures the distance from
each point in A to the nearest point in B and the maximum distance is termed
the directed distance from A to B, and is the normal choice for critical time
dependent systems.
The Hausdorff distance is very sensitive to even a single outlying point
in one of the shapes. The Generalised Hausdorff distance, defined by
Huttenlocher et al in [48], is thus proposed as a similar measure but that
is robust to partial occlusions. The generalised Hausdorff distance is an f th
quantile of the distances between all the points of one shape to the corre-
sponding points of the other shape. The quantile is chosen according to the
expected noise and occlusion levels.
In recognition applications, the generalised Hausdorff distance is further
specialised to save computational power. The Hausdorff fraction, the measure
we are interested in, instead of measuring a distance between shapes evaluates
the percentage of superposition when one of the shapes is dilated. Further-
more, for computational efficiency, principal components analysis is included
resulting in an eigenspace approximation to the Hausdorff fraction [49].
The eigenspace approximation is built as follows: Let I m be an observed
edge image and I n d be an edge image from the topological map, arranged
d
as column vectors. The Hausdorff fraction, (I m ,I ), which measures the
n
similarity between these images, can be written as:
T
I I d
d
m n
(I m ,I )= (23)
n 2
I m
An image, I k can be represented in a low dimensional eigenspace [62, 92] by
k
T
k
a coefficient vector, C k =[c , ··· ,c ] , as follows:
M
1
T
k
¯
c = e .(I k − I).
j j
¯
Here, I represents the average of all the intensity images and can be also
used with edge images. Thus, the eigenspace approximation to the Hausdorff
fraction can be efficiently computed as:
T ¯
T
d
C C + I I + I dT ¯ ¯ 2
I − I
n
d
m
m
n
(I m ,I )= . (24)
/
n 2
I m
One important issue, when approximating the Hausdorff fraction, is to
include some tolerance in matching step. Huttenlocher et al. [49] build the