IEEE Robotics & Automation Magazine - March 2013 - 69

everything that does not fall into this region as an obstacle; we
follow an approach similar to that proposed in [13], albeit
with monocular vision, rather than using a stereo head.
The first step is to segment the image into constituent
regions. For this, we use the watershed algorithm, since it is
fast enough to work in real time [15]. We take the original
image [Figure 4(a)] and begin by applying the well-known
Canny edge-detection, as shown in Figure 4(b). A distance
transform is then applied such that each pixel is given a value
that represents the minimum Euclidean distance to the nearest edge. This results in the relief map as shown in Figure
4(c), with a set of peaks (the farthest points from the edges)
and troughs (the edges themselves). The watershed segmentation algorithm itself is applied to this relief map, using the
peaks as markers, which results in an image with a (large)
number of segments [see Figure 4(d)]. To reduce the number
of segments, the adjacent regions with similar average colors
are merged. Finally, the average color of the region that has
the largest number of pixels along the base of the image is
considered to be the floor. All the remaining regions in the
image are classified either as obstacles or as navigable floor,
depending on how closely they match the newly defined
floor color. The result is shown in Figure 4(e), where the
detected obstacles are highlighted in red.
Since we know the relative position of the camera and its
lens distortion parameters, we are able to build a local occupancy grid that can be used by the shared controller, as is
described in the following section.
Updating the Occupancy Grid
At each time-step, the occupancy grid is updated to include
the latest sample of sensory data from each sonar and the output of the computer vision obstacle-detection algorithm. We
extend the histogram grid construction method described in
[16] by fusing information from multiple sensor types into
the same occupancy grid. For the sonars, we consider a ray to
be emitted from each device along its sensing axis. The likelihood value of each occupancy grid cell that the ray passes
through is decremented, while the final grid cell (at the distance value returned by the sonar) is incremented. A similar
process is applied for each column of pixels from the computer vision algorithm, as shown in Figure 5. The weight of
each increment and decrement is determined by the confidence we have for each sensor at that specific distance. For
example, the confidence of the sonar readings being correct in
the range 3-50 cm is high, whereas outside this range it is
zero (note that the sonars are capable of sensing up to 6 m,
but given that they are mounted low on the wheelchair, the
reflections from the ground yield a practical limit of 0.5 m).
Similarly, the computer vision algorithm only returns valid
readings for distances between 0.5 and 3 m. Using this
method, multiple sensors and sensor modalities can be integrated into the planning grid.
As the wheelchair moves around the environment, the
information from the wheel-encoder-based dead-reckoning
system is used to translate and rotate the occupancy grid cells

(x, y)

d = f(x, y)

Figure 5. Each column of pixels is scanned from bottom to top in
order to detect the nearest obstacle (assuming it intersects with
the ground). The estimated distance from the wheelchair to this
obstacle is a function of the (x, y) pixel coordinates and the camera
distortion parameters.

such that the wheelchair
Many BCI implementations
remains at the center of
the map. In this way, the
rely on the subject
cells accumulate evidence
over time from multiple
attending to visual stimuli
sensors and sensor modalities. As new cells enter the
presented on a screen.
map at the boundaries,
they are set to "unknown,"
or "50% probability of
being occupied," until new occupancy evidence (from sensor
readings) becomes available.
Motion Planning
All the motion planning is done at the level of the occupancy
grid, which integrates the data from multiple sensors. We base

Detection Zones

LF2

LF1

RF2

RF1

F1
y

LC1

RC1

x
RB1

LB1
Wheelchair

Figure 6. Diagram of the wheelchair centered in an 8 # 8-m
occupancy grid (to scale). The wheelchair obstacle-detection zones
are labeled, and the origin of the coordinate system is on the center
of the wheelchair's driving axle.

March 2013

IEEE ROBOTICS & AUTOMATION MAGAZINE

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - March 2013