Page 254 - Innovations in Intelligent Machines

Toward Robot Perception through Omnidirectional Vision 247
scattered throughout a high dimensional space but – due to their similarity –
lie in a lower dimensional subspace.
We implement dimensionality reduction using the classical procedure of
8
Principal Component Analysis (PCA) , as described by Murase and Nayar in
[62], and detailed by Winters in [88] or Gaspar, Winters and Santos-Victor in
[35]. Simply put, Principal Component Analysis reduces the dimension-
ality of a set of linearly independent input variables, while still accurately
representing most of the original data. The reconstruction of this original
data is optimal in the sense that the mean square error between it and the
original data is minimized.
L
Imagine that we represent images as L-dimensional vectors in R .Dueto
the similarity between images (data redundancy) these vectors will not span
L
the entire space of R but rather, they will be confined (or close, to be more
precise) to a lower-dimensional subspace, R M where M<< L. Hence, to save
on computation, we can represent our images by their co-ordinates in such
a lower-dimensional subspace, rather than using all of the pixel information.
Each time a new image is acquired, its capture position can easily be deter-
mined by projecting it into the lower-dimensional subspace and finding its
closest match from the a priori set of points (images).
A basis for such a linear subspace can be found through PCA, where
the basis vectors are denominated Principal Components. They can be
computed as the eigenvectors of the covariance matrix of the normalised
set of images acquired by the robot. The number of eigenvectors that can be
computed in such a way is the same as the number of images in the input
data, and the eigenvectors are the same size as the images.
Each reference image is associated with a qualitative robot position (e.g.
half way along the corridor). To find the robot position in the topological
map, we have to determine the reference image that best matches the current
view. The distance between the current view and the reference images can be
computed directly using their projections (vectors) on the lower dimensional
eigenspace. The distance is computed between M-dimensional coefficient vec-
tors (typically 10 to 12), as opposed to image size vectors (128 × 128). The
position of the robot is that associated with the reference image having the
lowest distance.
When using intensity images, comparison of images is essentially a sum
of squared differences of brightness (radiance) values and because of this the
robot is prone to miscalculating its location where large non-uniform devi-
ations in illumination occur. This can be overcome by using edge images,
although these are not robust to edge-point position errors. The solution
therefore, is to compare shapes instead of edge-points, or more specifically
the distance between shapes present in both images. There are several possible

8
It is sometimes known as the application of the Karhunen-Lo`eve transform
[67, 86].