SUGISAKAMASANORI

Journal of Advances in Artificial Life Robotics
Vol. 1(2); September (2020), pp. 101–105
ON LINE ISSN 2435-8061; ISSN-L 2435-8061
https://alife-robotics.org/jallr.html

Research Article

Development of an Autonomous Mobile Robot Doing SelfPosition Estimation and Road Region Search
Naokazu Iwata1, Joo Kooi Tan2

Graduate School of Engineering, Kyushu Institute of Technology, Kitakyushu, 804-8550, Fukuoka, Japan
Faculty of Engineering, Kyushu Institute of Technology, Kitakyushu, 804-8550, Fukuoka, Japan

1
2

ARTICLE INFO
Article History
Received 13 November 2019
Accepted 21 July 2020
Keywords
Autonomous mobile robot
ORB
BoF

ABSTRACTThis paper proposes an autonomous mobile robot expected to realize an intelligent robot that
supports a human life. The proposed mobile robot has three main functions; self-position
estimation, road region estimation, and route planning. Self-position estimation is performed bycomparing local features obtained from the frontal images captured by the robot to a knowledge
base. In road region estimation, the frontal image is separated into several regions to find theregion where the robot can move. Furthermore, the route to the destination is planned by graphsearch. Experimental results show satisfactory performance of the proposed mobile robot.

© 2022 The Author. Published by Sugisaka Masanori at ALife Robotics Corporation Ltd.
This is an open access article distributed under the CC BY-NC 4.0 license(http://creativecommons.org/licenses/by-nc/4.0/).

GBS
K-means++

and travel routes. To realize this, we propose a selfposition estimation method using local features based on acamera. In the method, the ORB [5] (Oriented FAST and
Rotated BRIEF [6]) technique is employed for detecting
local features on an image. The ORB realizes high speed
processing without affected by scaling, rotation andillumination. Since the calculation cost is high if the local
features are used in their original form, BoF (Bag of
Features [7]) is employed that converts the image features
into feature vectors to reduce the calculation cost.
An autonomous mobile robot needs to find an area whereit travels. For this purpose, the frontal image the robot
acquires is separated into several regions employing GBS(Graph Based Segmentation [8]) and the regions are foundthat are similar to the initial robot travel region. For
travelling autonomously to a destination, the robot mustplan a route from the current location to the destination. In

1. Introduction
Robot technology has been widely used in industries. But,in recent years, it is largely expected in a welfare field andvarious kinds of service areas for supporting a human life.
In particular, much attention has been focused on service
robots [1] to help our daily life. These robots need toautonomously judge their actions in response to various
usage situations, scenes, and environmental changes.
Therefore, in recent years, researches on recognition andjudgment on a drivable area for a mobile robot insurroundings have greatly advanced. GPS, LiDAR [2],[3]and cameras [4] are commonly used sensors for thispurpose. GPS and LiDAR are, however, not able to acquire
sensor signals in a specific environment. The former
provides no information in a tunnel or indoors, whereas thelatter is helpless without reflective objects such asbuildings around it.
This paper proposes an autonomous mobile robot systemthat employs a camera and adapts to various environments
Corresponding author’s E-mail: etheltan@cntl.kyutech.ac.jp

101

the method, numbers are given as labels to forks, corners
and destinations, and route planning is performed based on
backward search of a graph. The developed mobile robot
travels to the destination employing the information on its
self-position, the estimated road region and the plannedroute.
2. Self-Position Estimation of a Robot
Obviously, self-position estimation is of great importancefor a mobile robot to travel to its destination. The proposed
method uses local features on an image to know its present
position. Here, local feature points are called local featuresin the method. Since many local features are extracted
from a single image, comparing each local feature to a
database increases calculation cost. Therefore, in the
proposed method, extracted local features are converted toa histogram showing the frequency of occurrence ofspecific local features on the image by use of BoF. The
robot's self-position is estimated by comparing thehistogram to those prepared for each check point.

Fig. 1 Example of local features extracted by ORB.

the maximum value of the score. Then a vote is given tobin i* corresponding to Vi*. A histogramis made by performing the vote with all Fj (j=1,2,…,m).
This histogram provides an n-dimensional feature vector
that represents the image.
The procedure for finding i* is formulated by thefollowing equations;𝑖𝑖 ∗ = arg max 𝑠𝑠𝑖𝑖𝑖𝑖
1

Bag of Features (BoF) represents an image by a single
feature vector. The process of BoF is shown as follows;(i) Extracting local features from an image.
(ii) Creating Visual Words (VWs) by clustering the local
features.
(iii) Creating a histogram of the image based on the VisualWords.

𝒊𝒊

(1)

𝒋𝒋

In order to estimate the robot’s self-position, the input
images and keyframe images at branch points (junctions)are converted into histograms using BoF. The similarity of
the histogram is then calculated and the robot’s selfposition corresponding to the input image is estimated.
The procedure of the robot’s self-position estimation isshown below.
(i) Histograms 𝐻𝐻𝑖𝑖𝑖𝑖 and 𝐻𝐻𝑘𝑘𝑘𝑘𝑘𝑘 of local features are createdby BoF from the input image and the key frame image,respectively.
The similarity measure, 𝑆𝑆𝑆𝑆𝑆𝑆𝐷𝐷 (> 0), defined by

Local features are extracted using ORB in the proposed
method. Fig. 1 shows an example of local features
extracted by ORB. They are indicated by red circles in Fig.
1.

𝑛𝑛−1
𝑆𝑆SAD = ∑𝑖𝑖=0
�𝐻𝐻𝑖𝑖𝑖𝑖 − 𝐻𝐻𝑘𝑘𝑘𝑘𝑘𝑘 �𝑖𝑖(ii) Clustering the local features

After having clustered the local features, the center of eachcluster 𝑖𝑖(𝑖𝑖 = 1, … , 𝑛𝑛) is defined as VWs 𝑽𝑽𝑖𝑖 (𝑖𝑖 = 1,2, … , 𝑛𝑛).
A histogram representing a given image is created asfollows. Given a local feature Fj, a score sij showing thesimilarity between Vi and Fj is calculated to find Vi* giving

𝑭𝑭𝒋𝒋

2.2. Self-position Estimation of the Robot(i) Extracting local features(iii) Creating a histogram𝑽𝑽

𝑠𝑠𝑖𝑖𝑖𝑖 = 1 − 2 �‖𝑽𝑽𝒊𝒊 ‖ − �𝑭𝑭 ��

2.1. Bag of Features

Let us suppose that 𝑭𝑭𝑗𝑗 (𝑗𝑗 = 1,2, … , 𝑚𝑚) local features are
extracted from an image. They are clustered by K- means++ [9]in a feature space. K-means++ is a clustering algorithm
that improves the initial cluster problem of K-means [10].

𝑖𝑖

,

(2)

is calculated between 𝐻𝐻𝑖𝑖𝑖𝑖 and 𝐻𝐻𝑘𝑘𝑘𝑘𝑘𝑘 . Here |a|i is theabsolute value of the ith component of vector a, and 𝑛𝑛
is the number of classes of the VWs. Note that SAD
means Sum of Absolute Difference.
(ii) To make the self-position estimation more accurate, thesum of the similarities of the past 𝑀𝑀 input images is used.
Let the similarity of frame f be denoted by S f SAD. Then, if
𝑓𝑓∑𝑓𝑓−𝑀𝑀+1
𝑆𝑆SAD < 𝑇𝑇𝑠𝑠
𝑓𝑓=𝑓𝑓

(3)

holds, it is judged that the robot is at the position where thekey frame indicates. Here 𝑇𝑇𝑠𝑠 is a predefined threshold.
102

3. Road Region Estimation(i) Divide the input image into regions using the GBS.
(ii) Set the robot’s foot region as shown by a blue box in
Fig. 2.
(iii) The maximum area including the foot region is a roadregion.
(iv) If the estimated road region 𝐴𝐴𝑅𝑅 in (iii) is less than athreshold 𝐴𝐴𝑡𝑡ℎ , the road region of the past frame is used.
Fig. 3 shows an example of road region estimation. The grayarea is the estimated road region.

A road region is estimated from an image using an image
segmentation technique. In the proposed method, GBS [8] isemployed. It is a well-known image segmentation technique.
3.1. Graph Based Segmentation
Graph Based Segmentation (GBS) is one of the renowned
image segmentation methods, which combines pixels withsimilar characteristic pixel values into multiple regions.
The algorithm of GBS is shown below.
(i) Smoothing the input image 𝐼𝐼(𝑥𝑥, 𝑦𝑦) using thefollowing equation.

The proposed method assumes the knowledge on a road
map. Numbers are given as labels to junctions, corners anddestinations on the map, all referred to as check points inthe method, in advance. The relations on their connection
are represented by a graph using the labels: A vertex
corresponds to a label (or a check point), whereas an edge
shows connection of two vertices: A weight is(4)

𝐿𝐿(𝑥𝑥, 𝑦𝑦, 𝜎𝜎) = 𝐺𝐺(𝑥𝑥, 𝑦𝑦, 𝜎𝜎) ∙ 𝐼𝐼(𝑥𝑥, 𝑦𝑦)

𝐺𝐺(𝑥𝑥, 𝑦𝑦, 𝜎𝜎) =4. Route Planning1
𝑥𝑥 2 +𝑦𝑦 2
exp �− 2 �
2𝜋𝜋𝜋𝜋

(5)

Here 𝜎𝜎 is the standard deviation, 𝐺𝐺(𝑥𝑥, 𝑦𝑦, 𝜎𝜎) is theGaussian function, and 𝐿𝐿(𝑥𝑥, 𝑦𝑦, 𝜎𝜎) is a smoothed image.
(ii) Creating a graph with the node 𝑣𝑣𝑖𝑖 representing eachpixel of the smoothed image and the edge 𝑒𝑒𝑞𝑞
connecting adjacent pixels in the image. Using theilluminance difference between the pixels connectedby an edge, the weight of the edge 𝑤𝑤�𝑒𝑒𝑞𝑞 � is calculatedby the following equation.
222𝜔𝜔�𝑒𝑒𝑞𝑞 � = ��𝑅𝑅𝑖𝑖 − 𝑅𝑅𝑗𝑗 � + �𝐺𝐺𝑖𝑖 − 𝐺𝐺𝑗𝑗 � + �𝐵𝐵𝑖𝑖 − 𝐵𝐵𝑗𝑗 �(6)where, 𝑅𝑅# , 𝐺𝐺# , and 𝐵𝐵# are the red, green and blue
values of the node.
(iii) Assignment of a separate region 𝑆𝑆𝑞𝑞 (𝑞𝑞 = 1, … , 𝑚𝑚) toeach node where 𝑚𝑚 is the total number of pixels in theimage.
(iv) When nodes 𝑣𝑣𝑖𝑖 and 𝑣𝑣𝑗𝑗 connected by edge 𝑒𝑒𝑞𝑞 (𝑞𝑞 =1, … 𝑚𝑚) satisfy the following equation, the region 𝑆𝑆𝑖𝑖and 𝑆𝑆𝑗𝑗 are combined.
𝑐𝑐𝜔𝜔�𝑒𝑒𝑞𝑞 � ≤ min �max{𝜔𝜔(𝑒𝑒)} + |𝑆𝑆 | , max{𝜔𝜔(𝑒𝑒)} +𝑒𝑒∈𝐸𝐸𝑖𝑖

𝑖𝑖

𝑒𝑒∈𝐸𝐸𝑗𝑗

𝑐𝑐�𝑆𝑆𝑗𝑗 �Fig. 2 Example of the robot’s foot region

given to an edge according to the distance between two� (7)Here, 𝑐𝑐 is a predetermined fixed value, |𝑆𝑆# | is the numberof nodes constituting the region 𝑆𝑆# , and 𝐸𝐸# is a set of edges
connecting nodes in the region 𝑆𝑆# .
For all edges, the node is divided into several regions bydetermining the region connection by Eq. (7). If, with acertain region, the number of nodes is less than or equal toa threshold 𝑆𝑆𝑡𝑡ℎ , the region is merged with an adjacentregion with which an edge connecting the two regions has
the smallest weight among adjacent regions.

Fig. 3 Example of estimation of a road region

connected vertices.
Given an initial position and a destination, the route having
the minimum weight is searched on the graph backwards
from the destination to the initial position. Then a route is
finally produced which the robot tracks.

3.2. Road Region Estimation
In the proposed method, the road region is estimated by thefollowing procedure;103

5. Algorithm on Autonomous Movement

thought to be due to the high accuracy of self-position
estimation and road region estimation.
However, in the second and the third experiment on route
A and the first experiment on route B, the destination could
not be reached. Failure with the first experiment on route
A results from misdetection of a check point whensuccessive check points exist. It is necessary to raise theability of self-position estimation further by designing astronger classifier.
Failure with the second experiment is incomplete
estimation of the road region caused by a shadow. When ashadow is on the road region, the part that is originally thesame region with a neighbor region is separated from theneighbor like the one in the white circle as shown in Fig. 4.
Moreover, in the method, the road region to move next isdetermined by selecting the region having the maximum
area among the three separated sub-regions. Hence theexistence of a shadow on the road may mislead the selection.
More robust road region estimation not influenced by ashadow needs to be developed.

An autonomous movement algorithm of the robot is shown in
the following;(i) Find the road region from the input image using GBS
and the foot region.
(ii) Separate the road region into three sub-regions andcalculate the areas of the three sub-regions. If the areas
are all less than a threshold, pause. Otherwise, face thesub-region having the largest area.
(iii) Move forward.
(iv) Obtain local features from the input image and estimate
the robot's self-position.
(v) If the estimated self-position matches one of the key
frames, judge if it is the destination. If yes, stop. If not,turn to the direction specified in the route plan. Go to(i).
(vi) If the estimated self-position does not match any of the
key frames, go to (i).
6. Experiment

Table. 1 Parameters used in the experiment6.1. Experimental Environment

No. dimensions of ORB
No. features
No. clusters
No. learning images

In the experiment, the proposed robot system is evaluatedby whether or not the robot reaches the destination
autonomously in an outdoor environment. Two different
routes, A and B, with different destinations are set. Route
A contains more number of junctions (referred to as checkpoints) than route B and higher precision in self-position
estimation is required. On the other hand, route B has arotary on the way and a robot needs travel along a curved
line at the spot. The robot travels these routes five times
each. If an emergency stop is required due to the passage
of a vehicle or the like while travelling, the trial isinterrupted and restarted after the passage. Table 1 shows
the parameters related to the experiment. The travel speedof the robot is 0.2 [m/s] and the rotation speed is 0.2 [rad/s].

32
1000
500
12 places×5 frames

Table. 2 Experimental results

1
2obtained3from a RGB-D
4
5
Use of depth information
camera
route
A
〇
×
×
〇
〇
may be useful for solving the difficulty.
route B×〇〇〇〇

6.2. Experimental Results
Table 2 shows the results of the experiment. In Table 2, ‘〇’
indicates that the robot reached the destination successfully,
whereas ‘×’ indicates failure. The processing time was 65.4
[ms/frame]. The travel of the robot was successful 3 times outof 5 with route A, whereas it was successful 4 times out of 5with route B. As for the weather, 2 times out of 4 weresuccessful when it was fine, whereas 5 times out of 6 weresuccessful when cloudy.

Fig. 4 Example of a shadow region on a roadUse of depth information obtained from a RGB-D camera
may be useful for solving the difficulty.
Failure with the first experiment on route B results fromthe inclination of the road surface near the roadside. The
inclination of the road surface becomes larger toward theend of the roadside. This has a negative effect on driving
close to the roadside. Actually, the travel closes to theroadside didn’t go well only by coping with fineadjustment of the traveling direction. It is necessary to
calculate the inclination of the road surface from, e.g.,

7. Discussion
In the performed experiment, as shown in Table 2, thedestination could be reached in many cases (70%)
regardless of the travel route and the weather. This is104images and to adjust traveling direction of the robot early.
The depth information which a RGB-D camera provides
might be of some help.
Detection of a road region where fewer pedestrians or
obstacles exist is also within the scope of the present study.
This function may help the robot choose an easier way
when there is an alternative route such as a rotary.

9. D. Arthur, S. Vassilivitskii, “k-means++: The Advantage of
Careful Seeding”, Proceedings of the 18 Annual ACM-SIAM
Symposium on Discrete Algorithm, pp.1027-1035, 2007.
10. P. Agarwak, N. Mustafa, “k-Means Projective Clustering”,
PODS ’04 Proceedings of the twenty-third ACM DIGMODSIGACT-SIGART Symposium on Principles of the Database
Systems, pp.155-165, 2004.

8. Conclusion

Authors introduction

This paper proposed an autonomous mobile robot system
which does self-position estimation by scene recognition
at a check point on the road using local features on a fed
image, and travels forward by detecting a road region
connected to its present position by performing region
segmentation on the image. The route to the destination
was decided in advance by graph, representing a road map,
search. In the experiment, satisfactory performance wasachieved with the robot travel on two routes and two kindsof weather. Further studies to equip higher functionality
with the proposed robot system include use of depth
information for more accurate detection of a road region
not influenced by shadows or for detecting the inclinationof a road surface, and design of a stronger classifier to finda check point regardless of the weather.

Mr. Naokazu Iwata
He received B.E. in Control Engineeringfrom Kyushu Institute of Technology. He ispresently in the Master’s course of
Graduate School of Engineering, in thesame University. His current researchinterests include autonomous mobile robot
and computer vision.
Prof. Dr. Joo Kooi Tan

She is currently with Department of
MechanicalandControlEngineering, Kyushu Institute ofTechnology, as Professor. Her
current research interests include
three-dimensional
shape/motion
recovery, human detection and its
motion analysis from video. She wasawarded SICE Kyushu Branch Young Author’s Award in
1999, the AROB Young Author’s Award in 2004, Young
Author’s Award from IPSJ of Kyushu Branch in 2004 and
BMFSA Best Paper Award in 2008, 2010, 2013 and 2015. She isa member of IEEE, The Information Processing Society, The
Institute of Electronics, Information and Communication
Engineers, and The Biomedical Fuzzy Systems Association ofJapan.

References
1. J. K., Tan, A. Sato, “Human-robot Cooperation Based on
Visual Communication”, International Journal of
Innovative Computing, Information and Control, Vol,16,
No.2, pp543-554, 2020.
2. M. Shinohara, S. A. Rahok, K. Inoue, K. Ozaki,“Development of Localization Method Using Magnetic
Sensor and LIDAR”, Transactions of the Society of
Instrument and Control Engineers, Vol.49, No.8, 795-801,
2013.
3. H. Date, S. Ohkawa, Y. Takita, J. Kikuchi, “High Precision
Localization of Mobile Robot Using LIDAR Intensity ofSurface”, The Japan Society of Mechanical Engineers,
Vol.79, No.806, pp.100-109, 2013.
4. K. Demura, Y. Nakagawa, “A Monte Carlo Localization
based on Template Matching using an Omni-directional
Camera”, Journal of the Robotics Society of Japan, Vol.27,
No.2, pp.249-257, 2009.
5. E. Rublee, V. Rabaud, K. Konolige, G. R. Bradski, “ORB:
An Efficient Alternative to SIFT or SURF”, Proceedings ofIEEE International Conference on Computer Vision,
pp.2564-2571, 2011.
6. M. Calonder, V. Lepetit, C. Strecha, P. Fua, “BRIEF: Binary
Robust Independent Elementary Features”, 11th European
Conference on Computer Vision, pp.1-14, 2010.
7. G. Csurka, “Visual Categorization with Bags of Keypoints”,
Proceedings of ECCV Learning in Computer Vision, pp.122, 2004.
8. P. Felzenswalb, D. Huttenlocher, “Efficient Graph-based
Image Segmentation”, International Journal of Computer
Vision, Vol.59, pp.167-181, 2004.

105