Page 256 - Innovations in Intelligent Machines

Toward Robot Perception through Omnidirectional Vision 249

D ij T ij
i,j
d (D, T)= (19)
T ij
i,j
where T is a template edge-image and D is the distance transform of the edges
of the current run-time image. As weaker edges (small gradient magnitudes)
are more susceptible to noise, we set T ij to the gradient magnitudes of the
template images, instead of binary edges. Hence, we give more weight to the
strongest edges.
Equation 19 says that the chamfer distance is an average of the distances
between corresponding points of the shapes. In a strict sense, it is an approx-
imation as the underlying chamfer distance transform is itself an approxima-
tion to the Euclidean distance. In practice this difference is not relevant as
typically the shapes to compare are at similar poses and the distances between
the points are small enough to make negligible the difference of the chamfer
and the Euclidean distances.
In the topological localisation application, we want to find the database
image corresponding to the current run-time image. In order to find the best
matching we search the database using the chamfer distance as the comparison
measure. The comparison of images is done from an edge-image to a distance
transformed edge-image. The distance transformation may be applied either to
the run time or to the database images [36]. We apply the distance transform
to the run time edge-images and leave to the template edge-images the role
of selecting the relevant edge locations.
The distance as defined by Eq. (19) is zero for perfectly matching images.
Therefore we search for the image matching the current image I m in a set
T 1 ...T n by minimizing Eq. (19),
ˆ n =arg min d (D(I m ),T n ) . (20)
n
Notice that, unlike recognition applications such as pedestrian and sign detec-
tion in an image [36], in the localisation application the template and run-time
images have equal sizes. The search parameter is an image index instead of
translation, rotation and scaling. The range of the index is the size of the
database.
Usually there are a large number of database images, and thus under-
taking localisation, as in Eq. (20), is computationally expensive. However it
only needs to be performed once, when the robot is dropped-in-scene. During
normal operation there is a causality constraint along the consecutive loca-
tions. We reduce the search range to a window around the last location, typ-
ically ±5 images.

Eigenspace Approximation to the Hausdorff Fraction

The Hausdorff distance [73] (of which the Hausdorff fraction is a subset) is a
technique whereby one can measure the distance between two sets of points,