A Method for Localization by Integrationof Imprecise Vision and a Field Model
K. Terada, K. Mochizuki, A. Ueno,
H. Takeda and T. Nishida
T. Nakamura A. Ebina H. Fujiwara
Graduate School of Information Science
Nara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara 630-0101, Japan
E-mail : kazuno-t@is.aist-nara.ac.jp

Abstracttheeld of mobile robots. In this paper we propose

a method of localization by integration of impre-In recent years, many researchers in AI and Robotics cise vision and a 3D environmental model. We will
pay attention to RoboCup, because robotic soccer show that this method is also e ective to identify
games needs various techniques in AI and Robotics,
such as navigation, behavior generation, localization

opponent robots.
Dead reckoning and rangender are often uti-and environment recognition. Localization is one of

lized to the localization problem [7] [5] [3].

the important issues for RoboCup.

reckoning uses odometry (i.e.

In this paper,

we propose a method of robot's localization by in-Deadcounting wheel ro-tations) to determine the robot's position.

Since,

tegrating vision and modeling of the environment.

errors from slip of wheels accumulate over time, es-

The environment model that realizes the robotic soc-

timation of its position becomes increasingly inac-cercurate.

led in the computer can produce an image ofrobot's view at any location.

In the environment

model, the system can search and appropriate lo-

The rangenders such as sonar and IR

sensors are not useful in the environment in which
there are no walls which re ect the ultrasonic wave

cation of which view image is similar to the viewand infrared rays. In order to overcome this prob-

image by the real robot. Our robot can estimate lo-

lem we need to use the method of localization there

cation form goal's height and aspect ratio on theare less dependent on its environment.

camera image. We search the most suitable position

In this paper we propose the system which useswith hill-climbing algorithm form the estimated lo-

both visual sensor and soccer thecation. We programmed this method, and tested va-

making comparison between images from the visual

50cm by sensor and provided by the eld model, the robot
20cm by this method. can estimate its position.

lidity. The error range is reduced form 1m
robot's estimation from 40cm

eld model. By

This method is superior to the other methods using

In the domain of vision-guided mobile robot re-dead reckoning or range sensor with map because it

search, there are a lot of techniques of localization

does not depend on theusing visual sensors. There is a method which uses

eld size on precision, anddoes not need walls as landmark.

1 Introduction
In the domain of the robotic soccer, there are various classes of problems; navigation, behavior generation, recognition of the environment, and localization. In these problems, localization is especiallyindispensable technique for robotic soccer. In orderto generate cooperative behavior, an agent needs toknow its position within the environment. Therefore, the problem of estimating the position of amobile robot is one of the fundamental problems in

3D model of environments to estimate the robot's
position and orientation. In this approach, 3D model
is employed to generate an expected image and it iscompared with an image captured by the robot [2][9] [6] [4] [1].
If the 3D model of environment is already known
and we can measure several feature points of an object in a captured 2D image, the distance to object
may be derived by geometrical model.

However,

it is hard to measure such feature points becauseof the following two reasons.

One reason is that

if there is an unknown object in the captured image and it obstructs the view, these feature points
would not be observed. The other is that the image

objectcolor

3 localization
The procedure of our method of localization con-groundgreen

one goal

yellowsists of the following two steps; 1) Estimate theanother goal

blue

current position by calculating distance to a land-wall

whitemark from an image which is sent from camera on

ball

red

outside ofeldrobotthe robot, 2) Revise the position by comparing thecamera image and vision images that are generated

blackby thegray

eld model.

We select a goal as a landmark to estimate theposition. The reasons of selecting the goal as a land-

Table 1:mark are as follows. 1) The robot can always see
either goal everywhere in the soccer
processing system is often confronted with changeof lighting, therefore accurate measurement is impossible.

In order to overcome this problem, we

add a method of matching two images to distanceestimation from several feature points.

eld. 2) The

robot can always see a complete view of either goal
since it can rotate its camera.

3.1 Estimation of the position
We use distance and angle from the goal estimate
position of the robot in the2 System Architecture

eld. Distance and an-gle are calculated from width and height of the goalthat are identi ed in an image captured by the camera on the robot. The relations between distance,
angle and width, height of the goal are as follows; The height of a goal in the image is inversely

SONY EVI D30NIKKOBLACK BEAST
Touch sensors

proportional to the real distance to the goal.

 The angle to the goal concerns to the ratio ofMotor Driver
Board
serial port

keyboard
port

parallel port

Linux onLibretto 60 /32M

IBM Smart
Capture Card II

the width to the height of goal.

WaveLAN/PCMCIA(a)The former relation can be easily formulated;

ahd=(b)(1)

Where the h is height of the goal in the image. We

select the constant a by calculating the mean value

Figure 1: Our soccer robot.

from the real data. The latter is derived from theOur robot consists of four major hardware components; a portable PC (Libretto 50 or 60, 100,Toshiba), a vision system including a camera and ageometrical model of the relation between a goal
and a robot(See Figure 2).
According to this model, angle to the goal is;video capture card, a tactile sensor system, and achassis including motors and a motor drive board.
The detail of our system is described in [8].

 = 90 0 arcsin(An image captured by the vision system is processed by the vision module.

The vision module

provides information about objects in theeld andmmdsin(arctan())) 0 arctan()
gdd(2)We de ne the origin of the coordinate axes ascenter of center circle in the soccer

the image is segmented into 7 colors (See Table1)

tion of robot is;regions in the vision module which runs on PC onxythe robot.
Every pixel in an image is classi ed to 6 col-=eld. The posi-

0 d cos()d sin( )4110=

ors except gray by means of a discrimination rule

The position calculated this method has about

which uses the Mahalanobis distance, and this rule

60cm error in average. This error is caused by limit

is learned by sample color data. A pixel which doesof image precision (64not classi ed to any colors labeled to gray.

segmentation.

2 48 pixels) and error of color

Image precision is limited because

all kinds of processing including image processing
are done in a single computer in our robot and it
requires real-time response.
In order to reduce this error, we revise the position with theeld model.

1. The size of every part ofgoal
ω geld such as wall andgoal can be changed.

θ

2. This model can generate any image of viewmf

that the robot ought to see from coordinates(x; y ) and angle  .

d

3. We can place multiple robots in theeld.

4. The shape of every robot can be changed.

3.4 Method of Position Revisionψ

We use two types of images for position revision.
One type of images that is captured by the camera
on a robot.

The image is segmented to 7 colors

region by the vision module on the robot and sent

robot

to the server through ethernet. The other type ofimages is an ideal image of theFigure 2:

The geometrical model of the relation

between a goal and a robot

eld. This image isgenerated by the server and is calculated from valueof position; (x; y;  ) that is sent from a client to theserver. The strategy of position revision is to3.2 Position Revisionoptimal point in thend an

eld model. In this point theeld model generates the most similar image to theThe position revision system consists of a serverwhich revises the position, and clients each of which
is on a robot and send estimated positions to thecaptured image. The method ofnding this point is

to search the neighborhood point of starting point
which is estimated from geometrical model. We use

server. The server communicates with multiple clients the hill-climbing algorithm as a search algorithm.
The evaluation function is;and holds the position of each robot. Figure 3 shows
the client-server system applied in our work.

robot name,position info.,
image info.

Server2c(3)a+ba is the number of pixels of the goal area in animage which generated by the 3D eld model. b isrobot

the number of pixels of the goal area in an image

Clientwhich is captured by camera on the robot.

c is anumber of intersection pixels of both areas when

position(x,y, θ )positionf unc(a; b; c) =position(x,y, θ )image

position info.
image info.

Shared memory

Environment model

two images are overlapped in order tot center ofgravity of both areas.
By means of hill-climbing algorithm search of
optimal point is carried out by the following steps.

Figure 3: Server Client System

1. Step1: Evaluation of beginning of search.
(a) Calculate the value of beginning point

The role of the server and the client is describedas follows. Server receives both data of the position
which is estimated in the computer on the robot,
and images captured by the camera on the robot
through wireless ethernet. The server then revises
the position by comparing the two images; one iscaptured by the robot, another is generated in theserver by means of a 3D

eld model.

3.3 Field Model
The server has a 3D
this model are;eld model. The features ofpt (i; j ) by evaluation function.

2. Step2: Calculate the value of the next candidate points(a) Select the neighbor 8 points of pt (i; j )(See Figure 4).
(b) Generate the image of each point andcalculate a value by the evaluation function.
(c) Select the point pt+1 (i; j ) in which theevaluation value is the greatest of 8 points.
3. Step3: Comparison.

error after revision becomes also smaller when thex2robot is closer to the goal. The reason for this is8

1that we use the number of pixel in an image as aparameter of evaluation function. Since error rate
does not depend on the amount of these pixels, thelarger amount of these pixels contributes to makey3

a7

5

4

6position more accurate.

5 Identi cation of Opponent
RobotsIn this section we explain a method of identi cation

Figure 4: Neighbor point of (i; j )of opponent robots. This method is realized by ourproposed localization method andeld model. To

distinguish team mate robot from opponent robot
is important ability for soccer robot. An innocent
robot may pass the ball to an opponent robot. With-position

estimatedrevised(2000.0)

659mm

206mm

(1850,0)

639mm

308mm

(1300,0)1113mm

320mm(1150,0)1111mm

381mm(1000,0)

927mm

335mm

(1000,1000)

279mm

260mm

(0,1000)

486mm

172mm

(-1000,1000)

606mm

243mm

(1000,-1000)

341mm

141mm

(0,-1000)

258mm

215mm

by the server, and another is sent from one of

295mm

the robot in the(-1000,-1000)

404mm

Table 2: Comparison of errors

out explicit mark, to do that is considerably hard.
Our basic idea is that there are only team materobots in theeld model constructed in the server.

The server know all positions of each team materobot by communicating with each robot, and cangenerate an image in which there are only teammate robots.

The procedure of distinguishing ateam mate from opponent robots is follows.
1. Preparation of two images; one is generated
eld.

2. Counting the pixels which are colored gray.
Each image is segmented to 7 colors and therobot is colored gray in each image.

(a) If the value in pt (i; j ) is greater than thatin pt

+1(i; j ),nish searching.

(b) If the value in
0.99,pt (i; j ) is greater thannish searching.

(c) If the value in pt
that in pt

01 (i; j ),(d) If the value in pt+1 (i; j ) is the same asnish searching.

3. Calculation of remainder of each number ofpixels; r .

4. If r is greater than a threshold, we de ne that
there is at least an opponent robot in the image which is captured by robot. We select thethreshold as 100 pixels.

+1 (i; j ) is greater thanthat in pt (i; j ), return Step2.

4 Experimental result
We had experiments on the proposed method. We
put the robot on the point of theeld that is ran-

domly selected, and executed the program. Experimental results are shown in Table 2.
The mean value of the error before revision is(a)(b)

about 600mm and it is reduced to 260mm after revision. While the error before revision becomes larger

Figure 5: There are no robots.

with the robot goes away from the goal, the error
after revision becomes less sensitive to the distance.
This fact suggests that our proposed method is tolerant of the changing position in theeld. But, the4 experimental result are shown in Figure 5
Figure 8. In eachgure, (a) is captured by a camera

(a)

(b)

(a)

Figure 6: There is only opponent robot.

(b)

Figure 8: There are both a team mate and an opponent robot.

the accuracy of the localization. On the other hand,in the method of comparing an image captured byrobot and an image generated by theeld model,

starting point of search is important to reduce thecomputational cost. Combining these two methods,
we reduced the cost of search and improved the ac(a)curacy of localization.

(b)

There are two advantages of our localization method
against the other method such as a method utilized

Figure 7: There is only a team mate robot.

sonar or IR sensor and a method of dead reckoning.
One is that our method does not depend on the sizeon a robot and (b) is generated by server. In

gureof theeld. We utilize the view of goal in order to(b) a team mate robot is expressed by a gray cone.

estimate and revise the position of the robot, there-In Figure 5(a), the number of gray pixels is 66

fore if only the goal is visible, localization is possi-

and in Figure 5(b) 0. Therefore, the server decides

ble. If the size of thethat there are no robots. In Figure 6(a), the number

from dead reckoning are proportionally increased.

of gray pixel is 184 and in Figure 6(b) 0. Therefore,

The other is that our method does not depend on

the server decides that there is a team mate robot.

the structure of theIn Figure 7(a), there is a robot in the left side ofsonar or IR sensor, if there are no walls, the robot

the goal and the number of gray pixel is 155.

could not know its position.

InFigure 5(b) there is a corn as a team mate robot.

eld become greater, errors

eld.

In the method utilized

In the method of identi cation of the opponent

The server know each position of each team materobot, we compare an image of arobot, and can generate an image in which there

which there are only a team mate robot to an image

is a team mate robot.

captured by the robot in order to distinguishing a

The number of gray pixel

eld model inis 104. Therefore the server decides that there is ateam mate robot from opponent robots.

team mate robot. While in Figure 8(a), there are

perimental result shows that we can identify thetwo robots, in Figure 8(b), there is one robot, theopponent robot without explicit marking.

server decides that there are both a team mate andReferences

an opponent robot.

6 Conclusions[1] H. Christensen, N. Kirkeby, and et al. Modeldriven vison for in-door navigation.

In this paper, we propose a method of robot's localization by integrating vision and modeling of theenvironment. We also propose a method of identication of opponent robots by using vision and theeld model. By means of our method, accuracy ofthe localization of the robot in the soccer

Our ex-

eld isimproved.

Robotics

and Autonomous Systems, 12:199{207, 1994.
[2] C. Fennema, A. Hansen, E. Riseman, J.R. Beveridge, and R. Kumar. Model-directed mobile
robot navigation.

IEEE Trans. on Systems,

Man, and Cybernetics, 20:1352{1369, 1990.
[3] J.-S.

Gutmann,W.

Hatzack,I.

Herrmann,

In the method of using geometrical model andB. Nebel, F. Rittinger, A. Topor, T. Weigel, andimage's feature points, a noise of image prevents

B. Welsch. The cs freiburg robotic soccer team:sampling of the feature value and directly e ects

Reliable self-localization, multirobot sensor in-tegration, and basic soccer skills. In RoboCup-98:

Robot Soccer World Cup II. Springer-Verlag, Berlin, Heidelberg, 1998.

Hier-[4] A. C. Kak, K. M. Andress, and et al.

archical evidence accumulation in the PSEIKE
system and experiment in model-driven mobilerobot navigation. M. Henrion and R. Shachterand et al., Elsevier, 1990.
[5] L. Kleeman. Optimal estimation of position andheading for mobile robots using ultrasonic beacons and dead-reckoning. In Proceedings 1992,

IEEE International Conference on Robotics andAutomation, pages 2582{2587, 1992.
[6] A. Kosaka and A. C. Kak. Fast vision-guided
mobile robot navigation using model-based reasoning and prediction of uncertainties.

Com-puter Vision, Graphics and Image Processing IU, 56:271{329, 1992.
[7] E. Krotkov,G. Heredia.

L. Chrisman,F. Cozman,andDead reckoning and visual land-marks for a prototype lunar rover. In Proc. ofIEEE/RSJ International Conference on Intelligent Robots and Systems 1995 (IROS95), 1995.
[8] T. Nakamura, K. Terada, and et al.
robocup-naist:

AcheapThe

multisensor-based

moblie robot with on-line visual learning capibility.

In Proceedings of the second RoboCupWorkshop., pages 291{303, 1998.
[9] T. Tsubouchi and S. Yuta. Map-assisted visionsystem of mobile robots for rechoning in a building invironment. In Proceedings of 1987 IEEE

International Conference on Robotics and Automation, pages 1978{1984, 1987.