Proceedings of the 2011 IEEE
International Conference on Robotics and Biomimetics
December 7-11, 2011, Phuket, Thailand

Appearance and map-based global localization using laser reflectivity
DongXiang Zhang, Ryo Kurazume, Yumi Iwashita, Tsutomu Hasegawa

Abstract— Global localization is a fundamental ability torecognize the accurate global position for a mobile robot ina revisited environment. The map-based global localization
gives a precise position by calculating an accurate transformation, but the comparison with large 3D data is quite timeconsuming. The appearance-based global localization which
determines the global position by image retrieval techniqueswith similar structures is real-time. However, this techniqueneeds external illumination constraint and does not work in
the dark extremely. This paper proposes a combination of themap-based global localization and the appearance-based global
localization. Instead of camera images used for the appearancebased global localization, we utilize reflectance images which aretaken as a byproduct of range sensing by a laser range finder.
The proposed method not only detects previously visited scenes
but also estimate relative poses precisely. The effectiveness ofthe proposed technique is demonstrated through experiments
in real environments.

I. INTRODUCTION
In some practical robotic tasks, the perceptual informationfrom external environment is unpredictable, unstructured anduncontrolled. For instance, in an area struck by a strong
earthquake or by a mine disaster, the geometrical structure
differs from the original one because of grounds blocked bya heap of rubble or collapsed walls. To accomplish a searchand rescue task efficiently in such an uncontrolled and unpredictable environment, accurate mapping and localization
are fundamental capabilities.
Global localization, is a definition to accurately localizea robot’s position in a global coordinate system using surrounding features only given a map without any other priorknowledge. Plenty of global localization techniques havebeen proposed so far [11]. Abundant works have carried out
to attack this problem based on camera images captured inconstrained illumination environment, i.e. appearance-based
localization. other works utilizing laser range finder, i.e. mapbased localization mainly focused on 2D range data and can’testimate accurate relative poses.
The map-based global localization[1] is defined to find abest position where the observed geometrical features matchthe ones in the provided geometrical map. Though 3D range
data is preferable for 6D global localization in terms ofaccuracy and reliability, the comparison between 3D range
data captured by a range sensor and pre-constructed 3D map
is quite time-consuming. On the other hand, the appearancebased global localization using camera images[14],[15],[16]Ryo Kurazume, Yumi Iwashita and Tsutomu Hasegawa are with Facultiesof the Graduate School of Information Science and Electrical Engineering,
Kyushu University, Japan
DongXiang Zhang is with Phd candidate of the Graduate School ofInformation Science and Electrical Engineering, Kyushu University, Japan,zhang@irvs.ait.kyushu-u.ac.jp

978-1-4577-2137-3/11/$26.00 © 2011 IEEE1010

is simple and suitable for a real-time processing. However, the appearance-based global positioning can’t work indark or an environment where lighting condition changes
severely since illumination constraints is necessary for robust
appearance-based localization.
This paper proposes a two-steps strategy which combines
the map-based global localization and the appearance-based
global localization. By using reflectance image which aretaken as a byproduct of range sensing by a laser range
finder instead, the proposed technique is useful even in
the dark or an environment under severe lighting condition
thanks to the characteristic of the reflectance image which is
not subject to any severe variants of external illumination
conditions. Furthermore, fast and precise localization canbe done by comparing a few 3D range images which are
selected based on the similarity of the reflectance images.
The proposed two-steps strategy is as follows: i) reflectanceimages retrieval system for rough estimation of a global
position based on Bag-of-feature technique, and ii) precise
global position is determined by Iterative Closest Points
algorithm for 3D range data automatically.
The remainder of this paper is organized as follows: after
brief introduction of related works in section II, section
III simply introduces cooperative positioning system which
the proposed method is based on. The proposed two-steps
strategy is presented in detail in section IV and V, and theexperimental results are shown in section VI.
II. RELATED WORK
Image-based visual SLAM (simultaneous localization andmapping) has been reported in several literatures such as [2]and [3]. The Bag-of-Features (BoF) is a popular techniquefor efficient representation of a raw image captured by acamera. Non-false-positive is achieved in [2] by combining
BoF and the probabilistic calculation. However, [2] requires aconstant illumination condition. Therefore the travel distanceof the robot has to be short enough so that the lighting
condition will not change drastically. In [3], the authors
didn’t evaluate the experimental results explicitly under largechanges of illumination. Extremely, both of them would failin the dark or the environment where the lighting is severely
changed.
A laser range finder which measures the distance fromthe sensor to the surroundings is a popular device forrobot localization, map creation, and 3D modeling. When
we measure range by a laser range finder, the reflectivity,
which indicates the strength of the reflected laser, can beobtained as a byproduct of range data. Note that all of the
pixels in the range image have corresponding reflectancevalues. In other words, the range image and the reflectanceimage are precisely and fundamentally aligned. In addition,
the reflectance image is not subject to any severe variantsof external illumination conditions and thus we can obtainstable reflectance images even at night.
The proposed technique utilizes the reflectance image
instead of a regular camera image. By applying BoF fora reflectance image which corresponds to 3D range data,
the global localization using 3D range data and 2D images
is achieved efficiently. [4] utilizes reflection intensity froma 1D laser range finder for localization in 2D space. On
the other hand, our technique utilizes 2D reflectance images
obtained by a 3D laser range finder for 3D localization. This
proposed technique is deterministic, so it doesn’t rely on
Markov assumption, in which the future state of the robot,
given the present and the past states, depends only on thepresent state[13]. It also doesn’t encounter ”kidnapped robot
problem”[12], because its current state purely depends oncurrent sensor reading.

Figure 1 shows the fifth CPS-SLAM model named CPSV. This system consists of one parent robot and two childrobots. The parent robot is equipped with a highly precise
laser range finder (GPT-9000A, TOPCON LTD), a 2D laser
range finder(SICK LMS151), and a 3-axes attitude sensor.
On the other hand, two child robots are equipped with cornercubes. The GPT-9000A and corner cubes are used for selfpositioning cooperatively as shown in Fig.2. The LMS151(Table I) placed on a rotating table acquires two-dimensionalslit-like range data which are vertical to the ground. Thissensor can capture reflectance data at the same time. Thusby rotating the table around the vertical axis for 360 ◦ while
scanning with the 2D laser range finder, 3D range data anda 2D reflectance image are acquired. The number of pixels
on a reflectance image is exactly same as the number of
3D points in range data, i.e. there is one-to-one mapping
relationship between 2D pixels of the reflectance image and3D points of the local 3D map.

III. 3D MAP CREATION BASED ON COOPERATIVEPOSITIONING SYSTEM
For the map-based global localization, an environmental
map has to be created and provided beforehand. For precise
3D mapping of an environment around a robot, we havebeen proposing an efficient and precise system named CPSSLAM [5], which can construct a quite accurate large-scale
3D map by a laser range finder and multiple robots based on
the technology for geographical surveying. This technique
has been used for the basis of Urban Search and Rescue
robot(USAR)[6].
Fig. 2.

Fig. 1.

Cooperative Positioning System, CPS

The 3D modeling robots, CPS-V
Fig. 3.

Construction of a large-scale 3D map by CPS

TABLE ISICK LMS151

A. 3D global map
Measuring range
Field of View
Precision
Angular resolution

The process of mapping the entire field is displayed in
Fig.3. In each location, the parent robot collects a local
3D map and its measurement position based on the relative
observation between parent and child robots. In the end, all

50[m]270[◦]±30[mm]0.25[◦]

1011

Fig. 4.

Reflectance and range imagesof local 3D maps are aligned into a global 3D map using
measurement position information. More details about CPSbased simultaneous localization and mapping (CPS-SLAM)
can be found in [5].
B. Reflectance images
As mentioned above, reflectance images are captured asa byproduct of range sensing. Two examples of reflectanceimage and its corresponding 3D data acquired by CPS-V
are shown in Fig.4. Note that each reflectance image has its
position information where the image is taken. These images
are used for the appearance-based global localization in the
proposed two-steps strategy.

IV. TWO-STEPS STRATEGY COMBINING
APPEARANCE-BASED AND MAP-BASED GLOBALLOCALIZATIONThis section presents the two-steps strategy for precise
localization using a 3D map. Firstly, we need to create a
global map as a training dataset. As explained in Section
III, the CPS robots move in the environment and construct a
3D global map. At the same time, the parent robot collects
reflectance images at each measurement position. Then allof reflectance images are represented using bag-of-features(BoF) technique and the training dataset is created. Finally,
the dataset of all the BoF representations is stored in Kd-tree
which is efficient for information retrieval.
For global localization, a new robot which is equippedwith a 3D range sensor like CPS-V, is placed and collects
local 3D data and 2D reflectance images (test data). In the
1st step, we retrieve some candidates of initial location bycomparing stored reflectance images (training dataset) andcaptured reflectance images (test data) using BoF and Kdtree. Then we apply 3D geometrical constraint to extract true
feature pairs and run automatic ICP in the 2nd step. Thanks
to the 1st step, fast and precise localization can be done in
the 2nd step by comparing a few 3D range images which are
selected based on the similarity of the reflectance images in
the 1st step.
Hereinafter, we denote variables related with training dataas ”Trm ” or ”Dtr ”, and variables related with test data as”Ten ” or ”Dte ”. D means the 3D distance between two points
in a local 3D map. Train i.re f and Train i.pts represent the
ith reflectance image and local 3D map in training dataset.
Test j.re f and Test j.pts represent the jth reflectance image
and local 3D map in test dataset.
We will explain the proposed two-steps strategy in moredetail below. The entire process is shown in Fig.5

C. Image retrieval using Bag-of-features
When the global 3D map of the target field is constructed,a Kd-tree structure storing Bag-of-features(BoF) representations of reflectance images is also constructed at the sametime. Reflectance images are represented as histograms ofoccurrence of the visual words in an image. Firstly, someregions in feature space are mapped to visual words byclustering all SURF[7] or SIFT[8] features extracted fromrecorded images into representative words using k-meansclustering, the words are stored using Kd-tree structure. With
these words as x-axis, quantize each feature in a reflectanceimage to its approximate nearest word by searching in Kdtree, all of recorded reflectance images are represented asstatistics of words( histograms ). Finally, the histograms of
all recorded images are stored also using Kd-tree structure. A
newly-captured image is also represented as a histogram andthe best M matching images for it are retrieved by quantizing
the histogram to its nearest M histograms.

1012

Fig. 5.
Combination of appearance-based localization and map-based
localization.

A. 1st step: initial localization by Bag-of-features using 2D
reflectance images
All Test j.re f are converted into bag-of-features (BoF)
representations, and searched the best M matches in Kd-tree
previously constructed from the training dataset. Then the M
Train i.re f and Train i.pts are selected as M candidates ofthe position of the robot in the 3D global map.

B. 2nd step: precise localization by Automatic ICP using 3D
dataWith M candidate positions, automatic ICP[9][10] which
consists of two processes is applied for removing incorrect
candidates. But before applying automatic ICP, 3D geometrical constraints are used for removing outliers for using
RANSAC as follows:
1) Rough alignment with RANSACa) Find corresponding features between Test j.re f
and Train i.re f .
b) Get the 3D coordinates of corresponding features
by Test j.pts and Train i.pts which correspondto Test j.re f and Train i.re f respectively.
c) Remove outliers by 3D geometrical constraints.
This process will be explained in Section V.
d) 3D transformation between Test j.pts andTrain i.pts is estimated by RANSAC.
e) Align Test j.pts to Train i.pts.
2) Precise alignment with ICPa) Run ICP[9] using Test j.pts and Train i.pts
which are already aligned roughly.
As a result of ICP, two metrics are defined for evaluating the accuracy of the alignment between Test j.pts
and Train i.pts. One is ”alignment ratio” and another is”average error”. Firstly, we set a threshold of maximum
distance between a pair of 3D points in Test j.pts andTrain i.pts. Suppose Test j.pts has K points in total and
N of them can be found corresponding points in Train i.pts.
The ”alignment ratio” is defined by N/K. In those N pairsof points, the sum of errors between every pair of points
divided by N is defined as ”average error”.

Fig. 6. Corresponding features between Test 17.re f and Train 22.re f .
Left image shows all correspondences, Right image shows the correct
correspondences.

Fig. 7.

3D geometric constraint

V. OUTLIER REMOVAL BY 3D GEOMETRICALCONSTRAINTS
Unlike color and undistorted images used in other works,
gray and distorted reflectance images don’t contain muchinformation. Therefore many false POMFs (Pair Of Matching
Features) between two reflectance images will be extracted.
In some cases, the number of false POMFs is larger thantrue POMFs. As shown in Fig.6, there are only 4 true pairsof matching features between Test 17.re f and Train 22.re f ,their actual locations are shown in Fig.8. Since all thefeatures on the 2D reflectance images have their own 3D
positions in the 3D local map, geometric constraints such as
distance and a normal vector of a surface can be used forextracting true POMFs. We propose a voting algorithm tokeep the true POMFs and remove the false POMFs by using
3D geometrical information. This process corresponds to thestep 1-c) in Section IV-B.
The 1st step of the voting algorithm is the outliers removal
by comparing the 3D distance between two POMFs (seeAlgorithm 1). Dtr is the 3D distance between Trm and Trn ,and Dte is the 3D distance between Tem and Ten . If theerror between Dtr and Dte is below Dthresh , the scores of
two POMFs are increased by 1. In the end if the score of
POMF is below η × f actor1, this POMF is removed as an

1013

outlier. In Fig.7, |AG| ̸= |A′ G′ |, |AH| ̸= |A′ H ′ |, and the redpoints are removed by this step.
The 2nd step is the outliers removal by comparing edges
and normal vectors of triangles in 3D space. This is basedon a self-evident theorem: Given any three points in 3D
space, no matter where the (0, 0, 0)T of a local 3D map
is, the length of three edges are constant. In addition, theangle between a normal vector and a unit vector verticalto the ground (0, 0, 1)T is also constant. In Fig.7, α , β , θ ,and ϕ are the angles between the normal vector of triangles
and the unit vector (0, 0, 1)T . △ADE, △A′ D′ E ′ , △ADF, and△A′ D′ F ′ have common POMFs AA′ , DD′ . |AD| ̸= |A′ D′ |,|DE| ̸= |D′ E ′ | and |θ − ϕ | > ANGthresh ; Another pair oftriangles △ABC ∼= △A′ B′C′ , α = β . In the end, if the scores′of POMFs DD , FF ′ are smaller than ω × f actor2, they
are removed. POMFs AA′ , BB′ ,CC′ , EE ′ are kept. The blue
points are removed by this step. The green points are finallykept as the input of RANSAC.
With the Algorithm 1, the outliers of POMFs between
reflectance images can be removed effectively. Many false
candidate features will be excluded by this voting algorithm.
Since a small number of reliable POMFs are remained, thisAlgorithm 1 Voting algorithm
Suppose η POMFs extracted from Train i.re f and Test j.re f
for 0 ≤ m < η do
Get two 3D points (Trm and Tem ) from m th feature.
for m + 1 ≤ n < η do
Get another two 3D points (Trn and Ten ) from n th featurei f (|Dtr − Dte | < Dthresh )(1){score1[m] + +;score1[n] + +; }Fig. 8.

end forend forfor 0 ≤ m < η doi f (Score1 [m] < η × f actor1) (0 < f actor1 < 1)(2)

Delete the m th pairend forSuppose ω POMFs remained from above vote stepfor 0 ≤ iteration < ω × N do
Randomly select 3 POMFs for ω × N (N is a pre-defined
iteration number) times to form two triangles in 3D space(Tr∆ and Te∆).
()
i f Tr∆edg − Te∆edg < D∆thresh(3)i f (|T rDEG − T eDEG | < ANGthresh )(4){score2[m] + +;score2[n] + +;score2[k] + +; }Experimental fieldthat is, 5 candidates for each Test i.re f are retrieved from thetraining dataset by Kd-tree. All the positions of the robot are
correctly estimated and included in 5 candidate locations. In
25 positions, the positions of the robot are correctly estimatedas the first candidate. In 2 positions, the second candidates
are the actual locations. The remaining 2 positions are also
correctly estimated as third and fifth candidates, respectively.
TABLE IIC ORRECTNESS OF POSITION ESTIMATION AFTER 1 ST STEPNo.
Correct
localization

1st

2nd

3rd

4th

5th

Total

Correctness ratio

25

2

1

0

1

29

100%

TABLE IIIend forfor 0 ≤ m < ω do

C ORRECTNESS OF POSITION ESTIMATION AFTER 2 ND STEPi f {score2 [m] < ω × f actor2} (0 < f actor2 < 1)(5)

Delete the m th pairTotal
Excluded by voting algorithm
Excluded by large ICP error
True positive

29
5
1
23

end forcan save retrieval time. The effectiveness of our method will
be shown in section VI.
VI. EXPERIMENT
An experiment is conducted to verify the proposed twosteps strategy. The experimental field is shown in Fig.8. The
size of every reflectance image is 590 × 569. The CPS-V
robots move and stop at different locations in experimental
fields for 58 times as the red path shown in Fig.8, i.e. 58 data
(Train i.re f and Train i.pts) are stored as training dataset.
On the other hand, test data (Test j.re f and Test j.pts) arecollected in 29 locations as the three colored paths shown in
Fig.8.
A. Results of position estimation after 1st step (coarse estimation)
The results of location estimation after 1st step are listed inTable II. In this experiment, M in Section IV-A is set to be 5,

1014

B. Results of position estimation after 2nd step (precise
estimation)
At first, Dthresh in Algorithm 1-(1) is set to be 3 [m]according to the attribute of LMS151 shown in Table I,f actor1 in (2) is 1/3, N is ω /2, D∆thresh of (4) is 1 [m], andf actor2 of (5) is 1/3. The threshold of the average error for
terminating ICP is set to be 0.02[m] after 40 iterations of ICP.
Table III shows the results of the precise position estimation.
5 positions are not estimated correctly due to the failure in
the voting algorithm, i.e. the number of true 3D POMFs
between Train i.pts and Test j.pts is quite small. One false
localization is excluded by large average error of ICP. True
positive is 23 in total, so 23/29 ≈ 79.3% recall is achieved
and no-false-positive is obtained. Figure 10 shows the alignment results between Test 3.pts and Train 16.pts and results
between Test 21.pts and Train 36.pts after RANSAC andautomatic ICP. Table IV shows the average errors of theirresults. These pairs are correctly selected in Step 1. Theirrelative locations are displayed in Fig.8.

In the proposed method, the most time-consuming part is
ICP. The incorrect candidates can be excluded by the voting
algorithm. Since M is set to be 5 in the experiment, the
ICP should be executed for 29 × 5 = 145 times if the voting
algorithm is not applied. On the other hand, with the voting
algorithm, ICP is executed for only 37 times, that is, 37/29 ≈1.28 times for each test data.
The proposed method is robust for the presence of moving
objects such as pedestrians or cars. Fig.9 shows the correct
POMFs on 2D reflectance images including several pedestrians and a car in the bottom image. It is clear that the
proposed method using BoF and outlier removal hardly be
influenced by these disturbances.

Fig. 9. The rectangles in the training image (lower) show the moving
objects which are not in the test image (upper).

TABLE IVAVERAGE ERROR OF THE TWO EXAMPLES IN F IG .10

ExampleTrain 16.pts and Test 3.pts
Train 36.pts and Test 21.pts

Coarse alignment
60.17[mm]43.34[mm]Precise alignment
30.86[mm]25.03[mm]VII. CONCLUSION
This paper proposes and demonstrates the two-steps
strategy for global localization of a mobile robot. The
appearance-based global localization and the map-based
global localization are combined for improving the performance of correct position estimation. The reflectanceimage which is taken as a byproduct of range sensing andinvariant to the change of illumination condition is utilized
for the appearance-based global localization in the 1st step.
Then the precise map-based global localization by ICP isapplied using 3D local maps which are selected by the
1st step. To improve the performance of the 2nd step, the1015voting algorithm based on the 3D geometrical constraints
and RANSAC-based course position estimation process areproposed. The effectiveness of the proposed technique isdemonstrated through experiments in real environments.
VIII. ACKNOWLEDGMENTS
The present study was supported in part by a Grant-in-Aid
for Scientific Research (B) (23360115).
R EFERENCES[1] D. Filliat, J.-A. Meyer, ”Map-based navigation in mobile robots: I. A
review of localization strategies”, Cognitive Systems Research, vol. 4,
no. 4, pp. 243-282, 2003.
[2] A. Angeli, D. Filliat, S. Doncieux, and J.A. Meyer, ”A Fast andIncremental Method for Loop-Closure Detection Using Bags of VisualWords”, IEEE Transactions on Robotics, vol. 24, no. 5, pp. 1027-1037,
2008.
[3] M. Cummins, P. Newman, ”FAB-MAP: Probabilistic Localizationand Mapping in the Space of Appearance”, International Journal of
Robotics Research, vol. 27, no. 6, pp. 647-665, 2008.
[4] H. Yoshitaka, K. Hirohiko, O. Akihisa, ”Mobile Robot Localizationand Mapping by Scan Matching using Laser Reflection Intensity of
the SOKUIKI Sensor”, IEEE Industrial Electronics, IECON, art. no.
4153430, pp. 3018-3023, 2006
[5] R. Kurazume, S. Hirose, ”An Experimental Study of a Cooperative
Positioning System”, Journal of Autonomous Robots, vol. 8, no. 1,
pp. 43-52, 2000.
[6] M. Guarnieri, R. Kurazume, H. Masuda, ”HELIOS system: A teamof tracked robots for special urban search and rescue operations”,
IEEE/RSJ International Conference on Intelligent Robots and Systems,
IROS, art. no. 5354452, pp. 2795-2800, 2009.
[7] H. Bay, A. Ess, T. Tuytelaars, ”Speeded-Up Robust Features (SURF)”,
Computer Vision and Image Understanding, vol. 110, no. 3, pp. 346359, 2008.
[8] D. Lowe, ”Distinctive image feature from scale-invariant keypoint”,
International Journal of Computer Vision, vol. 60, no. 2, pp. 91-110,
2004.
[9] P. J. Besl, N. D. McKay, ”A method for registration of 3-D shapes”,
IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.
14, no. 2, pp. 239-256, 1992.
[10] C. S. Chen, Y. P. Hung, ”RANSAC-Based DARCES: A new approach
to fast automatic registration of partially overlapping range images” ,IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.
21, no. 11, pp. 1229-1234, 1999.
[11] F. Bonin-Font, A. Ortiz and G. Oliver, ”Visual Navigation for Mobile
Robots: A Survey”, Journal of Intelligent and Robotic Systems: Theory
and Applications, vol. 53, no. 3, pp.263-296, 2008.
[12] S. Thrun, D. Fox, W. Bugard and F. Dellaert, ”Robust Monte Carlo
localization for mobile robots”, Artificial Intelligence, vol. 128, pp.
99-141, 2001.
[13] S. Thrun, ”Probabilistic algorithms in robotics”, AI Magazine, vol. 21,
no. 4, pp. 93-109, 2000.
[14] Y. Matsumoto, M. Inaba, H. Inoue, ”Visual navigation using viewsequenced route representation”, Proceedings - IEEE International
Conference on Robotics and Automation, vol. 1, pp. 83-88, 1996.
[15] S. D. Jones, C. Andresen and J. L. Crowley, ”Appearance based
processes for visual navigation”, IEEE International Conference onIntelligent Robots and Systems, vol. 2, pp. 551-557, 1997.
[16] T. Ohno, A. Ohya, S. Yuta, ”Autonomous navigation for mobile
robots referring pre-recorded image sequence”, IEEE International
Conference on Intelligent Robots and Systems, vol. 2, pp. 672-679,
1996.

(a) Original maps of Train 16.pts and Test 3.pts(c) Precise alignment by ICP between Train 16.pts
and Test 3.pts(b) Coarse alignment by
Train 16.pts and Test 3.pts

RANSACbetween(d) Original maps of Train 36.pts and Test 21.pts(e) Coarse alignment by RANSAC between Train 36.pts (f) Precise alignment by ICP between Train 36.pts andand Test 21.pts
Test 21.pts
Fig. 10.

Alignment Results between the 16th test data and 3th training data, 21th test data and 36th training data1016