VIDEO IMAGE PROCESSING FOR MOBILE ROBOT INDOOR NAVIGATION C. SULIMAN* Abstract: The paper follows some of the progresses made in the area of vision… [629743]

VIDEO IMAGE PROCESSING FOR MOBILE
ROBOT INDOOR NAVIGATION

C. SULIMAN*

Abstract: The paper follows some of the progresses made in the area of
vision for mobile robot indoor navigation. In this paper we deal only with
indoor navigation whi ch is further subdivided into three major categories:
map-based navigation, map -building -based navigation and map -less
navigation, navigation based on other techniques such as object recognition.

Keywords: image processing, navigation, autonomous mobile robot,
computer vision, indoor navigation
F. MOLDOVEANU*

* Dept. of Automat ics, Transilvania University of Brașov. 1. Introduction

Image processing is becoming a widely
acknowledged technology. Many everyday
processes use automated vision systems,
all of which rely upon image processing
techniques. Image p rocessing, in gen eral
terms, refers to the manipulation, improvement and analysis of pictorial
information . In this case, pictorial
information means a two -dimensional
visual image.

During the last two decades, machines
that can "see" have been developed for a
variety of uses. The progress made in th is
period of time has been on two separate
fronts: vision -based navigation for indoor
robots and vision-based navigation for outdoor robots. We focus our attention on
to indoor navigation. For example, 30
years ago it would hav e been impossible
for an indoor mobile robot to find its way
in the hallway of a building, but now it is
not much of a challenge. In the past,
complex camera images such as the one
shown in the figure (see Fig.1) used to be
formidable to deal with because of an inordinate number of features that would
be output by any feature detector. This
difficulty was compounded by the
subsequent need to determine whether or
not any subset of these features matched
robot expectations. But now, using a
model -based fram ework such as that of
FINALE [7 ], a robot needs only to
examine those portions of the camera
image that contain low-level features in the
“vicinity” of model features, the extent of
the “vicinity” being determined by the
uncertainty in the position of the robot. A
system such as FINALE requires a
geometrical representation of space. One
can now also design a vision-based
navigation system that uses a topological
representation of space and an ensemble of
neural networks to guide a robot through
interior space, the topological
representation helping the robot figure out
which neural networks to use in what part of the space [3].
Equally impressive progress has been
achieved in computer vision for outdoor robotics, as represented by the NAVLAB
system [12], the w ork on vision-guided

2 Video Image Processing for M obile Robot Indoor N avigation

road-following for ”Autobahns” [ 4], and

Fig.1 Image of a hallway in robot vision

the Prometheus system [13]. One of the
first systems developed for NAVLAB could analyze intensity images for
ascertaining the position and the bounda ries of a roadway. A measure of the
success of Navlab -based systems was the
”No hands across America” test drive that consisted of a 2,849 mile trip from
Pittsburgh, Pennsylvania, to San Diego,
California. In this trip, a Navlab 5 vehicle
was able to steer completely autonomously
for more than 98 percent of the distance (a
human driver handled the throttle and
brake).
In the rest of this paper, our goal is to
survey the most important aspects of vision
for mobile robot , indoor and outdoor,
navigation.

2. Indoor Navigation

From the pioneering robotic vehicle
work by Giralt et al. in 1979, it became clear that, implicitly or explicitly, it was
imperative for a vision system meant for
navigation to incorporate within it some
knowledge of what the computer wa s
supposed to see. Some of the first vision
systems developed for mobile robot navigation relied heavily on the geometry of space and other metrical information for
driving the visio n processes and
performing self locali zation. In particular,
interior space was represented by CAD
models of varying complexity. I n some of
the reported work, the CAD models were
replaced by simpler models, such as occupancy maps, topological maps or even
sequences of images [3]. When sequences
of images were used to represent space, the
images taken during navigation were submitted to some kind of appearance –
based matching between the perception (actual image) and expectation (goal image
or goal images stored in the database). We
believe all of these and subsequent efforts
fall into three broad groups:
• Map -Based Navigation . These are
systems that depend on user -created
geometric models or topological maps of
the environment.
• Map -Building -Based Navigation .
These are systems that use sensors to
construct their own geometric or
topological models of the environment and then use these models for navigation.
• Map -less Navigation . These are systems
that use no explicit representation at all about the space in which navigation is to
take place, but rather resort to
recognizing objects found in the
environment or to tracking those objects
by generating motions based on visual
observations.
2.1 Map-Based Approaches
Map-Based Navigation consists of
providing the robot with a model of the
environment. These models may contain
different degrees of detail, varying from a
complete CAD model of the environment
to a simple graph of interconnections or
interrelationships between the elements in
the environment. In some of the very first
vision systems, the knowledge of the
environment consisted of a grid

Bulletin of the Transilvania University of Brașov • Vol. 1 5(50) – 2008 3

representation in which each object in the
environment was represented by a 2D
projection of its volume onto the horizontal
plane. Such a representation is usually
referred to as ”occupancy map”. Later, the
idea of occupancy maps was improved by incorporating ”Virtual Force Fields” (VFF)
[9]. Occupancy -based representations are
still used today in many research
navigation systems. A more elaborate
version of the occupancy map idea is the
S-Map [ 5], [6 ]—for ” Squeezing 3D space
into 2D Map ”. This kind o f map requires a
spatial analysis of the three-dimensional
landmarks and the projection of their
surfaces into a 2D map
.
Since the central idea in any map -based
navigation is to provide to the robot,
directly or indirectly, a sequence of
landmarks expected to be found during
navigation, the task of the vision system is
then to search and identify the landmarks
observed in an image. Once they are
identified, the robot can use the provided
map to estimate the robot’s position (self –
localization) by matching the observation
(image) against the expectation (landmark
description in the database). The
computations involved in vision-based
localization can be divided into the
following:
• Acquire sensory information . This
means acquiring and digitizing images
captured with the help of a video camera
[11].
• Detect ion of landmarks . This means the
use of digital image processing
techniques as extracting edges,
smoothing, filtering, and segmenting
regions on the basis of differences in
gray levels, color, depth, or motion [1].
• Establish matches between
observation and expectation . The
system tries to identify the observed
landmarks by searching in the database
for possible matches according to some
measurement criteria. • Calculate actual position. Once a match
(or a set of matches) is obtained, the
system needs to calculate its position as a
function of the observed landmarks and
their positions in the database.
2.2 Map-Building
The vision -based navigation approaches
discussed so far have all required the robot
to possess a map of the environment in
which it functions . But maps of the
environment are not always easy to
generate, especially if one also has to
provide metrical information. Therefore,
many researchers have proposed
automated or semi -automated robots that
could explore their environment and build
an internal representation of it. A
representation of the steps involved in the
building of a map are shown in Fig.2. One
of the first attempts of robotic map-
building was the Stanford Cart . It used a
single camera to tak e nine images spaced
along a 50 cm slider. Next, an interest
operator (now known as Moravec ’s
interest operator) was applied to extract
distinctive features from the captured
images. The features were tracked at each
iteration of the program and marked in the
grid and in the image plane. Although this
grid indirectly represented the position of
obstacles in the world and was useful for
path planning, it did not provide a
meaningful model of the environment. For
that reason a data structure, known as
occupa ncy grid, is used for accumulating
data from ultrasonic sensors. Each cell in
the occupancy grid has attached with it a
probability value that is a measure of the
belief that the cell is occupied. The data is
projected onto the plane of the floor and
each square of the occupancy grid
represents the probability of occupancy of
the corresponding square in the world by
an object [3]. In today’s robots, occupancy
grids allow measurements from multiple
sensors to be incorporated into a single

2 Video Image Processing for M obile Robot Indoor N avigation

perceived map of th e environment and
even uncertainties can be embedded in the
map. For large -scale and complex
environments , the resulting representations
may not be computationally efficient for
path planning and localization. Such
shortcomings also apply to non occupancy
grid-based approaches to map learning.
The occupancy -grid approach to map
learning is to be contrasted with the
approaches that create topological
representations of space [ 15]. These
representations often have local metrical
information embedded for node recognition and to facilitate navigational
decision making after a map is constructed.

Fig.2 The mapping process

The various proposed approaches differ with respect to what constitutes a node in a
graph-based description of the space, how
a node may b e distinguished from other
neighboring nodes, the effect of sensor
uncertainty, the compactness of the
representations achieved, etc. One of the
major difficulties of topological
approaches is the recognition of nodes
previously visited. In a recent contri bution
[14], Thrun has proposed an integrated
approach that seeks to combine the best of
the occupancy -grid -based and the
topology -based approaches. The system
first learns a grid -based representation
using neural networks and Bayesian
integration. The grid -based representation is then transformed into a topological
representation.
An ex ample for a mobile robo t
navigation system is based on a map, such
as the one in Fig.3, of the fluorescent tubes
located above the robot. A map based on
odometry data is built in advance by the
robot guided by an operator. The self –
localization of the vehicle is done by
detecting the position and orientation of
fluorescent tubes located above (see Fig.3) it’s desired path thanks to a camera
pointing to the ceiling [8].

a) b)
Fig.3 a)Image of the hallway; b) Odometric
map of the hallway .
2.3 Map-less Navigation
In this category, we include all systems
in which navigation is achieved without
any prior description of the environment. It
is, of course, t rue that in the approaches
that build maps automatically, there is no
prior description of the environment either;
but, before any navigation can be carried
out, the system must create a map. In the
systems surveyed in this section, no maps
are ever created. The needed robot motions
are determined by observing and extracting
relevant information about the elements in
the environment [2]. These elements can
be the walls, objects such as desks,
doorways, etc. It is not necessary that

Bulletin of the Transilvania University of Brașov • Vol. 1 5(50) – 2008 3

absolute positions of the se elements of the
environment be known. However,
navigation can only be carried out with
respect to these elements. Of the
techniques that have been tried for this, the
prominent ones are: optical flow-based and
appearance-based. The reader is also
referred to attempts at behavior -based
approaches to vision -based navigation in
map-less spaces [10].
One way of achieving autonomous
navigation in a map-less environment is for
the robot to memorize th e environment.
The main idea of this technique is to store
images of the environment and associate
those images with commands or controls that will lead the robot to its goal .
While in map -based systems it is easy to
establish meaningful navigational goals for
the robot, most robotic systems are limited
to essentially just roaming in map -less
systems. The reason for that is that a
human operator can use the internal map
representation of a structured environment
to conveniently specify different
destination points for the robot. But, for
the map -less case, using the appearance-
based approaches mentioned so far, in
most cases the robot only has access to a
few sequences of images that help it to get
to its destination, or a few predefined
images of target goals that it can use to
track and pursue.

3. Remarks

Compare d to 20 years ago, we have a
much better sense today of the problems
we face as we try to endow mobile robots
with sensory intelligence. We are much
more cognizant of the importance of prior
knowledge and the various forms in which
it can be modeled. This paper has surveyed
these vario us aspects of the progress made
so far in vision for mobile robot indoor
navigation.
References

[1] Cetin, O. L., Erden, A.: Improvement
of an Image Processing System f or
Autonomous Mobile Robot Navigation. In: Proc. 5th Int. C onf. Mechatronic
Design and Modeling, Konya, 2001 , p.
155÷165.
[2] Choi, M., Chung, W., Kwon, Y., Kim,
H.: Safe and high speed navigation of
a patrol robot in occluded dynamic
obstacles. In: Proc . 17th World
Congress, The International Federation
of Automatic Control Seoul, K orea,
2008, p. 1685 ÷1690.
[3] DeSouza, G. N., Kak, A. C.: Vision for
Mobile Robot Navigation: A Survey .
In: Proc. of IEEE Transactions on
Pattern Analysis and Machine
Intelligence, vol. 24, no. 2, 2002, p.
237÷267.
[4] Dickmanns, E.D.: Computer Vision
and Highway Automation. In: Vehicle
System Dynamics, vol. 31, no. 5,
1999 , p. 325÷33.
[5] Kim, D., Nevatia, R.: Representation
and Computation of the Spatial
Environment for Indoor Navigation.
In: Proc. Int. Conf. Computer Vision
and Pattern Recognition, 1994, p.
475÷482.
[6] Kim, D., Nevatia, R.: Symbolic
Navigation with a Generic Map. In:
Proc. IEEE Workshop Vision for Robots, 1995 , p. 69÷88.
[7] Kosaka, A., Kak, A. C.: Fast Vision –
Guided Mobile Robot Navigation Using Model Based Reasoning and
Prediction of Uncertainties . In:
Computer Vision, Graphics, and Image
Processing —Image Understanding,
vol. 56, no. 3, 1992, p. 2177÷2186.
[8] Launay, F., Ohya, A., Yuta, S.: Image
Processing for Visual Navigation of
Mobile Robot using Fluorescent
Tubes . In: Proc. The 2001 Int . Conf .
on Circuits/Systems, Computers and

2 Video Image Processing for M obile Robot Indoor N avigation

Communications, C5-1, 2001, p.
664÷667.
[9] Liu, D.K. Wang, D. Dissanayake,
G.: A Force Field Method Based
Multi-Robot Collaboration. In: Proc.
IEEE Conference on Robotics,
Automation and Mechatronics,
Bangkok, Thailand, 2006, p. 1÷6.
[10] Nakamura, T., Asada, M.: Stereo
Sketch: Stereo Vision -Based Target
Reaching Behavior Acquisition with
Occlusion Detection and Avoidance .
In: Proc. IEEE Int. Conf. Roboti cs and
Automation, vol. 2, 1996, p.
1314÷ 1319.
[11] Park, J. H., Baeg, S. H., Ryu, H. S.,
Baeg, M. H.: An Intelligent Navigation
Method for Service Robots in the
Smart Environment . In: Proc. of the
17th World Congress, The International Federation of Automatic
Control , Seoul, Korea, 2008, p.
1691÷1696. [12] Pomerleau, D.A., Jochem, T.: Rapidly
Adapting Machine Vision for
Automated Vehicle Steering . In: IEEE
Expert, Intelligent Systems and Their Applications, vol. 11, no. 2, 1996, p.
19÷27.
[13] Regensburger, U., Graefe, V.: Visual
Recognition of Obstacles on Roads . In:
Proc. IEEE Int. Conf. Intelligent
Robots and Sys tems, 1994, p.
980÷ 987.
[14] Thrun, S.: Learning Metric-
Topological Maps for Indoor Mobile
Robot Navigation . In: Artificial
Intelligence, vol. 99, no. 1, 1998, p.
21÷71.
[15] Vasudevan, S., Nguyen, V., Siegwart,
R.: Towards a Cognitive P robabilistic
Representation of Space for Mobile
Robots . In: Proc. IEEE Int. Conf . on
Information Acquistion, 2006, p.
353÷ 359.

Procesarea video a imaginii pentru navigația
roboților mobili în medii închise

Rezumat: În această lucrare sunt prezentate câteva din progrese le facute în
domeniul navigat iei în spa ții închise a roboților mobili, roboti dota ți cu
capacitatea de “a vedea”. În lucrare este studiată naviga ția în medii în chise,
categorie care este subdivizată în alte trei mari subcategorii: naviga ția bazată
pe hăr ți predefinite, navigația bazată pe construirea în prealabil a hărților
scenelor de operare, și navigația lipsită de harți, bazată pe alte tehnici cum ar
fi recun oasterea de obiecte.

Cuvinte cheie: procesare de imagini, navigație , robot mobil autonom ,
computer vision , navigatie in spa ții închise .

Recenzent: Prof. Dr. Ing. Radu C âmpeanu

Supervizor traducere în limba engleză : Asist. L aura SASU .