Page 190 - Autonomous Mobile Robots

174 Autonomous Mobile Robots

second room where they adopt positions B and C. Now R1 can continue to D
using R2 and R3 as artificial landmarks and map the second room.
Once the relative positionsofthe companion robotsare known, map building
is possible. The main difficulty is achieving fast and reliable detection of circles
of known radius from noisy range data. The detection of shapes in images is
a large area of research within the computer vision community and contains
several relevant techniques such as the Hough Transform and least squares
fitting approaches.

4.5.1 Circular Hough Transform

The Hough Transform [25] has been highly successful in the vision community,
thanks to its tolerance of image noise and excellent straight-line detection. The
Hough Transform may be generalized to any geometric primitive. However, the
introduction of each new parameter adds another dimension to the Hough space.
The geometric increase in storage and processing required for the accumulator
grids have repercussions on performance. A typical high-resolution laser scan is
given in Figure 4.13a which shows a relatively cluttered environment with two
circular landmarks that are indicated with dashed lines. The standard Hough
Transform is particularly ineffective for circle extraction from laser range data
becauseoftheunevendistributionofpointsinCartesianspace. Thelaserscanner
samples at regular intervals of θ resulting in an increased density of read-
ings from nearer objects. A nearby straight edge obstacle may be detected in
preference to the circles.
This is rectified by a Range Weighted Hough Transform (RWHT) as dis-
cussed in Reference 26. The weight function applied is a simple linear increase
from the origin of the scan. This linear increase negates the effect of the 1/r
fall in point density. The improvement is immediately apparent in Figure 4.13b
where the peaks of the circle centers can be distinguished from nearby walls.
As can be seen, the two highest peaks correspond to the circular landmarks.
Only a 2D Hough parameter space is required for the circle search because
the radii of the circles are known. The two parameters are the coordinates of the
candidate circle center. The confusion of straight lines with circles is a serious
problem that refuses to be resolved. A possible solution would be to first remove
all points corresponding to straight lines and then perform the circular Hough
Transform on the remaining points, however this is very time consuming. The
process for Hough Transform circle detection is summarized in Figure 4.14.
There are a number of reasons why the circular Hough Transform is not
particularly suited to this application. Range data are different from image data
for which the Hough Transform was first devised. Another problem is that it
always returns an answer even if the geometric primitive is not present in the
data. The determination of peak significance by comparison with others and
the kind of data expected requires a relatively complicated statistical analysis.

© 2006 by Taylor & Francis Group, LLC

FRANKL: “dk6033_c004” — 2006/3/31 — 16:42 — page 174 — #26