Online and Incremental Appearance-based SLAM
in Highly Dynamic Environments

Aram Kawewong, Noppharit Tongprasit, Sirinart Tungruamsub, Osamu Hasegawa
4259-R2-52 Nagatsuta, Midori-ku, Yokohama, 226-8503, JAPANDepartment of Computational Intelligence and Systems Science
Tokyo Institute of Technology{kawewong.a.aa, tongprasit.n.aa, tangruamsub.s.aa, hasegawa.o.aa}@m.titech.ac.jp

Abstract
This paper presents a novel method for online and incremental appearance-based
localization and mapping in a highly dynamic environment. Using position-invariant
robust features (PIRFs), the method can achieve a high rate of recall with 100%
precision. It can handle both strong perceptual aliasing and dynamic changes of places
efficiently. Its performance also extends beyond conventional images; it is applicable toomnidirectional images for which the major portions of scenes are similar for most places.
The proposed PIRF-based Navigation method named PIRF-Nav is evaluated by testing it
on two standard datasets as is in FAB-MAP and on an additional omnidirectional image
dataset that we collected. This extra dataset is collected on two days with different
specific events, i.e., an open-campus event, to present challenges related to illumination
variance and strong dynamic changes, and to test assessment of dynamic scene changes.
Results show that PIRF-Nav outperforms FAB-MAP; PIRF-Nav at precision-1 yields a
recall rate about two times (approximately 80%) higher than that of FAB-MAP. Its
computation time is sufficiently short for real-time applications. The method is fullyincremental, and requires no offline process for dictionary creation. Additional testing
using combined datasets proves that PIRF-Nav can function over a long term and cansolve the kidnapped robot problem.

1. INTRODUCTION
Appearance-based localization and mapping have recently become hot topics of discussion in
robotics because of the difficulty of detecting loop closure in metric SLAM (Filliat and Meyer 2003;
Meyer and Filliat 2003). Advanced computing technologies and the low prices of cameras havehelped to supplement traditional metric SLAM methods with appearance-based visual information.
Consequently, commonly used sensors such as laser scanners, radars, and sonar tend to be
associated with, or replaced by, a mono or stereo camera. With the popularity of this topic,
numerous approaches have been reported for fast and accurate localization and mapping. However,there are still some important problems to overcome. Perceptual aliasing and dynamic changes in thesystems are important concerns for localization and mapping in robotics. At 37%, the recall rate of
localization with 100% precision for localization in City Centre is considerably low (Cummins andNewman 2008a) even with the current Bag-of-Words (BoW) based methods (Newman et al. 2006;
Wang et al. 2006; Filliat 2007; Newman et al. 2006; Ho and Newman 2007; Schindler et al. 2007) that
render real-time and online performance.
The position-invariant robust feature based navigation system (PIRF-Nav) was designed toperform localization and mapping in exactly the same manner as the current state-of-the-art method
FAB-MAP, but with a substantially higher recall rate with 100% precision. This high performance isachieved by making use of the design of our previously proposed PIRF (Kawewong et al. 2009). PIRF
extraction is simple and fast. It is generated by averaging the existing scale-invariant featuretransformation (SIFTs) (Lowe 2004), which appear to be "slow moving" relative to the change incamera positions. These slow-moving features are identified using simple feature matching: a local
feature that appears repeatedly in many sequential images would be regarded as a slow-moving
local feature. Extracting PIRFs in this manner also enables landmark filtering. Unlike BoW-based
approaches that encode an entire image into a set of visual words, PIRFs selectively capture only
objects that are likely to exist in a place permanently. This ability renders PIRFs robust against
dynamic changes in scenes. Representing each image with a set of PIRF features instead of SIFT
features enables a compact representation that is robust against noise, while preserving thedistinctive power of unique local features. Loop-closure is detected using PIRF-Nav by taking into
account similar PIRF-based scores among observations, and then pairwise similarity among all
observations are computed to yield a square similarity matrix, similar to that obtained in someprevious studies (Levin and Szeliski 2004; Silpa-Anan and Hartley 2004; Zivkovic et al. 2005;
Newman et al. 2006). The similarity scoring of PIRF-Nav is modeled on the concept of term
frequency–inverted document frequency (tf-idf) and the discrete Bayes’ filtering scheme. Only a few
PIRFs are necessary for image representation (about 50–100 PIRFs per image; about 50,000–100,000
features for 1000 images). Therefore, PIRF-Nav is sufficiently fast for real time. We demonstrate the
PIRF-Nav performance by testing it on three image datasets. The first dataset, New College(Cummins and Newman 2008a), has localization under a strong perceptual aliasing condition. The
second dataset, City Centre (Cummins and Newman 2008a), has localization under dynamic changesof the scene in the center of the city. The last dataset that consists of 1079 omnidirectional images,
collected by us on different days, presents the task of localization under “highly” dynamic changes.
By the term “highly dynamic,” we mean the unusual dynamic changes that occur occasionallybecause of some special event (e.g., open-campus event). The dataset also includes illumination
variance by collecting data in different weather conditions (i.e., sunny, cloudy, etc.). These conditions
were not addressed in the earlier studies (Cummins and Newman 2008a). Finally, all three datasets
are combined to illustrate long-run performance of PIRF-Nav. We achieve 3000+ image localizationsin an online incremental manner without offline dictionary generation.

2. RELATED WORKS
Appearance-based localization and mapping are popular, and there are several approaches to them.
Initially, many methods represented appearance using global features, where a single descriptor iscomputed for an entire image (Ulrich and Nourbakhsh 2003; Lamon et al. 2001; Torralba et al. 2003;
Krose et al. 2001). Most such approaches using global features require much effort in the supervised
training phase to learn the generative place models. Later, Bowling et al. (2005) described an
unsupervised approach that uses a sophisticated dimensionality reduction technique, but themethod yields localization results in a subjective form that are inconvenient to interpret and still calls
for high computational cost. Furthermore, the use of global features is not robust to some effects suchas varied lighting, perspective change, and dynamic objects that alter portions of a scene between
visits.
Work in computer vision has engendered development of local features such as scale, rotation,and some lighting changes that are robust to transformations. Many recent appearance-based
localization methods therefore use SIFTs (Lowe 2004) or speeded up robust features (SURFs) (Bay et
al. 2006) as the main visual feature for the localization and mapping system. Wolf et al. (2005) used
an image retrieval system based on invariant features as the basis of a Monte Carlo localization
scheme. Kosecka et al. (2005) represented a model of an environment by a set of locations and spatial
relations among the locations. Each location is represented as a set of views and their associated local
SIFTs. Their method has a salient disadvantage in computation time. Localization based on matching
numerous features consumes too much time for use in real-time systems. Consequently, the idea of avisual vocabulary from computer vision community (Sivic and Zisserman 2003; Nister andStewenius 2006) built upon local invariant features was applied widely to address this problem. The
visual vocabulary model treats an image as a bag-of-words (BoW) much like a text document, where a“word” corresponds to a region in the space of invariant descriptors. One of the main advantages ofusing BoW is that it enables rapid visual search through the application of methods developed fortext retrieval. Wang et al. (2006) use geometric information in a post-verification step to confirm
putative matches. Schindler et al. (2007) described how to improve the visual vocabulary generation
to yield more discriminative visual words, and discussed the application of a technique for city-scale
localization with a database of 10 million images.
Nevertheless, most studies till date address only the problem of “localization.” It is the problem
of recognizing an input image to an already mapped location, where the map is known a priori. Thisguarantees that the image has come from somewhere within the map. This limitation renders thesemethods unsuitable for real implementation in SLAM. For using an appearance-based approach todetect loop closure in SLAM, the system must cope with the possibility that the current view comesfrom a previously unvisited place, and therefore has no match within the map. Chen and Wang
(2006) solved this in a topological framework, but their solution to the perceptual aliasing problem is
unsatisfactory (two different places appear to be similar). Goedeme et al. (2007) described an
approach to this issue using Dempster–Shafer theory with sequences of observations to confirm or
reject putative loop closures. Because localization and mapping were done separately, this approach
was unsuitable for online unsupervised mobile robot applications. More recently, Cummins andNewman (2008a) proposed a probabilistic framework for online visual SLAM. The method,
FAB-MAP, considers the correlation among visual words using Chow–Liu trees. This approach,based on the BoW scheme, is also robust against perceptual aliasing: a generative model ofappearance is learned offline by approximating the occurrence probabilities of the words included in
the offline-built dictionary. The main asset of this model is its capability of evaluating thedistinctiveness of each word, thereby accounting for perceptual aliasing at the word level; its
principal disadvantage lies in the offline process needed for model learning and dictionary
computation. These disadvantages become more serious when there is a remarkable change in theenvironment (e.g., when a human wants to use the robot in different countries). A good dictionary of
one environment is not useful in a different environment. Our results would later show that
FAB-MAP performance decreases when the environments differ considerably.
Most recently, Angeli et al. (2008) described the incremental creation of a visual vocabulary. The
method is still based on the popular BoW scheme, as explained in an earlier study (Cummins andNewman 2008a). The system can start with an empty dictionary. The model requires around 40,000
visual words for 500+ images, which is much more than FAB-MAP. The authors trade off theincreased number of words with the ability to generate a dictionary online. The performance interms of accuracy of the recall rate of loop-closure detection, as stated by the authors at the end of
their earlier paper (Angeli et al. 2008), is less than or approximately similar to that of FAB-MAP. In
light of these reasons, we selected FAB-MAP as our baseline for evaluating PIRF-Nav in terms ofaccuracy.

In order to design a method for selecting the most salient visual feature, Li and Kosecka (2006)
reduced a set of SIFTs by first estimating the posterior probability of the feature. Then theycalculated the information entropy of each feature. This information is used to select the most usefulfeature. However, this method requires a set of training images. The selection process must be
performed offline. Moreover, this method is limited to localization, where an input image isguaranteed to be from some previously visited location. Nevertheless, a PIRF can be extracted in an
incremental manner. Its performance is beyond localization and is therefore applicable to theincremental online loop-closure detection. Se et al. (2001) also described a similar underlying concept.
Their system, much like our basic idea, shows that the matched SIFTs between different frames offera good salient feature for tracking. However, there are some significant differences between their
method and ours. First, the PIRF-Nav is proposed for a large-scale outdoor scene where thematching can be done between images taken at about ~10 m. different observer's positions. PIRF-Nav
also takes into account the problem of moving objects; it can localize the place even though the majorpart of scene has been changed (see Fig. 11). Furthermore, using PIRF-Nav, the odometry data are
not required for obtaining the coordinate of each feature.
The proposed PIRF-Nav can achieve a high rate of recall (approximately twice that of FAB-MAP)
with 100% precision under identical conditions as FAB-MAP, while requiring no offline process suchas dictionary generation. Moreover, PIRF-Nav can run in real time similar to other systems (Angeli etal. 2008; Cummins and Newman 2008a) and hence is applicable to real robots. We utilized two
datasets used earlier (Cummins and Newman 2008a)––City Centre and New College––to sufficiently
evaluate the PIRF-Nav performance under strong perceptual aliasing and under dynamic scenechanges. We also test our PIRF-Nav using the omnidirectional image dataset, which was collected on
different days under highly dynamic changes, where different events were held. The result ofcombining all three datasets proves that PIRF-Nav can be used efficiently with omnidirectional
images, can run in the long term, and can accommodate the kidnapped robot problem. The
experiment is also expanded to testing on the New Colleges dataset. We also present a more detailed
evaluation and description of the proposed PIRF-Nav.

3. POSITION-INVARIANT ROBUST FEATURE
A position-invariant robust feature, designated as a PIRF, is a local descriptor generated from SIFTs(or SURFs), which appears repeatedly in an image sequence. To extract a PIRF, we must set thesliding window to extract a PIRF for wsize sequential images. In other words, the number of SIFTs in asingle image can be reduced markedly by considering only the descriptors that can be matched tothose of neighboring images. Fig. 1 portrays a sample of the resulting extracted PIRF from three
sequential images. Standard feature matching is performed for the current image and its neighbor.
The number of image matchings depends on the window size, which is set by the user. For example,
if the window size wsize is 3, then the current image It must be matched to It−2 and It−1. Strictly speaking,the image It would be matched only to It−1. The resulting matched descriptor would then be used toretrieve its matches recursively from image It−2 because the matching result between It−2 and It−1 would
have already been obtained. The corresponding SIFTs, which appear repeatedly in all three images,
are retrieved and averaged to obtain a single representative descriptor. This descriptor is a PIRF ψ,
where ψ = (d t −2 (d t −1 (d i )) + d t −1 (d i ) + d i ) / 3 , in which dx(dy) denotes the descriptor in image Ix andmatches descriptor dy under the distant threshold θ. To match the descriptors, we use the same
standard feature matching as that was used by Lowe (2004). That is, given d as a descriptor in image
I1 and d1 and d2 as the first and second nearest descriptors of d found in I2, d1 would be considered as
the matched descriptor of d, if and only if

𝑐𝑜𝑠 −1 (𝑑∙𝑑1 )𝑐𝑜𝑠 −1 (𝑑∙𝑑2 )< θ. The process is repeated for every descriptor

Fig. 1. Extracted PIRF with threshold θ = 0.5. (Top-row) Three sequential images described using SIFTs.
(Bottom-row) PIRFs extracted from SIFTs. Only "slow-moving" descriptors are selected to generate the mean feature
vectors, PIRFs.

di in the current image It. It is worth clarifying that the matching is performed only once with aneighboring image It−1. Precisely at image It, given that the matching results between It−2 − It−1 wereobtained at time t-1, for every matched descriptor between It−2 − It−1, we can retrieve all corresponding
descriptors recursively from It−2. In doing so, the system must perform only one matching for an
input image It, which makes our system applicable to real-time localization and mapping because thecost for one matching is acceptable for one step of the robot.
The extracted PIRFs are used instead of SIFT to represent an image, and this eliminates numerous
SIFTs that appear to be sensitive to changes of the observer’s position. Typically, we found that only
about 50–100 PIRFs are derived from an image with about 3000 SIFTs. It is very apparent that the
number of PIRFs, for some constant threshold θ, depends directly on the sliding window size wsize.
The number of PIRFs would be equal to the number of matched SIFTs between two images if thewindows were set to their smallest size: wsize = 2. On the other hand, if the window size is too large,
then PIRFs might not be found because local descriptors that exist in many images are unlikely toexist. Therefore, it can be said that the size of the sliding window wsize and the threshold value θ1 are
the two main factors that affect the system’s computational cost. To make it suitable for real-world
applications, at least one of these two parameters should adapt dynamically. This flexibility ofparameters is not easy to achieve because information of the input scenes is not available a priori.
Among these two parameters, we found that adaptively changing the window size wsize is more
tractable. First, the default window size is set to wsize = 3. After PIRF extraction, the resulting numberof obtained PIRFs npirf can be checked to determine whether it is less than npirf_min or greater than
nprif_max. If npirf < npirf_min, then w is decreased by 1 (i.e., reset to 2 if the default size is 3), and the PIRFs
are re-extracted. In contrast, if npirf > nprif_max, then the wsize is increased by 1 and the PIRF is re-extracted.
For the latter case, the re-extraction can be repeated until npirf is in an acceptable range. Sometimes, acase arises in which npirf, even at the smallest size wsize = 2, yields an insufficient number of PIRFs, i.e.,
npirf, w=2 < npirf_min. The system handles this eventuality by simply neglecting the input image andregarding it as a new previously unexplored location; this can prevent the system from yielding a
false positive. In other words, this image is treated as a “bad image” that would be discarded andwould not be included in the appearance-based representation for localization. Insufficient PIRFs
mean insufficient information for localization. However, this case rarely occurs. In all experiments ofthis study, only 3–5 images per dataset become the new location because of the insufficient numberof PIRFs. Despite their simplicity, PIRFs are robust, especially against highly dynamic changes inscenes (Kawewong et al. 2009), while being sufficiently tolerant to perceptual aliasing.

To extract PIRF, an important parameter wsize related to the fps of the camera and the egomotion of
the camera through the scene needs to be considered. However, our PIRF extraction handles thisusing the adaptive value of wsize. For example, consider the case in which the camera runs at 200 fps
vs 0.5 fps. At 200 fps, wsize would be too small and several redundant PIRFs are obtained. For this case,wsize will automatically be incremented until the resulting PIRFs meet the acceptable range. For thecase of 0.5 fps, images would be fairly far from each other and wsize might be reduced to its smallest
value wsize = 2. Note that we have started trying PIRF with the 1000 km dataset of Cummins andNewman (2009), where the images are captured around at an interval of 10 m. The resultant numberof PIRFs is still sufficient for calculation, although the value of wsize would usually be reduced to 2. If
the fps is very low (i.e., each picture taken every 50 m), our system would not be applicable because
the number of PIRFs is insufficient. Nonetheless, our PIRF-Nav is mainly proposed for mobile robots.
Unlike other vehicles, general robots do not have a speed high enough for the fps rate to be outsideof an acceptable range.

4. INCREMENTAL APPEARANCE-BASED SLAM
The environment is modeled as a set of discrete locations, each location being described using a
set of PIRFs. An incoming observation is converted into a PIRF-based representation and then foreach location, we simply calculate the similarity between the PIRFs of the observation and the PIRFs
of that location. The system then decides whether the observation came from a place not in the map
by considering the quality of the similarity score. The proposed system uses the PIRF as the only
visual feature, and takes advantage of it to obtain high performance. This system, called a
PIRF-based navigation system or PIRF-Nav, is outlined in detail in the following subsections。

4.1

Modeling Appearance

In our system, scenes are simply represented as a collection of PIRFs, much like the traditional
representation using raw SIFTs. An important difference is that the required number of PIRFs forrepresenting a location is much lesser than the number of SIFTs required for similar purposes.
Precisely, at time step t, the system must retain wsize images in the buffer for PIRF extraction. For
example, if the window size for PIRF extraction is set to w = 3, then the system must retain three
images { It−2, It−1, It} in memory and two matching results of (It−2 − It−1) and (It-1 − It). Analyzing thesematching results takes less time and is tractable, as mentioned earlier in this study. It provides us thecorresponding descriptors, which are slow-moving. All PIRFs of image It can be generated quickly.
This set of PIRFs is simply used to model the image appearance.

4.2

Localization and Mapping

At time t, our map of the environment is a collection of nt discrete and disjoint locations L ={L1 ,..., Lnt } . Each of these locations Li, which was created from the past image Ii, has an associatedappearance model Mi. This model Mi is a set of PIRFs. Modified from naive Bayes, four main steps
are used to calculate the similarity score for loop-closure detection. Fig. 2 depicts the overall
processing of the PIRF-Nav. First, an obtained image is described by the PIRFs. Simple feature
matching is performed in Step 1 to obtain the basic similarity score s if the number of PIRFs issufficient. The system proceeds to the next step if the maximum score exceeds the threshold and is
not the null hypothesis M0. In Steps 2–3, the score is recalculated considering the score ofneighboring models. The normalized score β is used to decide if the detected loop-closure is acceptedFig. 2. Overall processing diagram of PIRF-Nav (see text for details).

or rejected. If accepted, re-localization (Step 4) is performed by doing a second summation over thesimilarity scores obtained from step 3 to re-assign the most probable location for loop-closure. The
details for each step are described as follows.

Step 1: Simple Feature MatchingFirst, the current observed model Mt is compared to each of the mapped models
𝐌t = {𝑀0 . . . , 𝑀𝑛𝑡 } using standard feature matching with distant threshold theta θ. Each matching
outputs the similarity score between the input model and the query model. M0 is the model of thelocation L0, which is a virtual location for the event “no loop closure occurred at time t.” In fact, thisevent is evaluated as the event “a loop closure is found with the model M0.” M0 is a virtual model ofthe virtual image I0 built/updated at each step by randomly sampling PIRFs from all models Mi:
1 ≤ 𝑖 ≤ 𝑛𝑡 . For example, we can sample two PIRFs from 100 past models, yielding 200 PIRFs formodeling M0 for the current time. This technique has been proven to be effective in Angeli et al.
(2008). By sampling the PIRF, models of locations that have never been visited resemble M0 the most.
In other words, M0 will contain about 3–4 times more PIRFs than other models. In this study, we
sample five PIRFs from every new input model. New PIRFs from current model Mt are accumulated
into M0 without deletion unless the number of PIRFs reach the maximum size (i.e., 3000 for thisstudy). For instance, if we set the maximum number of PIRFs in M0 to 3000, sample PIRFs from first
600 models would be accumulated to M0. After this point, for every new model, M0 randomly selects
five PIRFs to be deleted and stores the five new PIRFs to the model. However, the virtual model
sometimes can be re-created particularly to prevent biased sampling. For this study, we re-create
virtual models at every 300 input images. That is, M0 is reset to null. Three thousand PIRFs are
randomly sampled from a set of currently obtained models. For example, if there are 1000 models

obtained, the system will sample three PIRFs from each model to create the M0.
After the first step, if M0 turns out to be the winner, the system terminates the process anddetermines that Mt belongs to a new previously unseen location. Otherwise, the system performs
feature matching to obtain a similarity score s between Mt and the existing models. This similarity isassessed using the score. Instead of counting matched features, we calculate the score by considering
the term frequency-inverted document frequency (tf-idf) weighting (Sivic and Zisserman 2003):
tf − idf =

𝑛𝑤𝑖
𝑛𝑖

log

𝑁

(1)

𝑛𝑤

In this equation, 𝑛𝑤𝑖 is the number of occurrences of the visual word w in Mi, ni is the total numberof visual words in Mi, nw is the number of models containing word w, and N is the total number of all𝑛existing models. The weighting is a product of the word frequency term 𝑤𝑖 and the inverse document

frequency term log

𝑁

𝑛𝑤

𝑛𝑖

. This scoring increases emphasis to words that are seen frequently in a small

number of images, and penalizes common words (i.e., words that appear everywhere) according to
the most recent statistics. In the classification/retrieval (Sivic and Zisserman 2003), models are ranked
by their normalized scalar product (cosine of angle) between query model and all existing mappedmodels. However, this model-to-model (image-to-image) comparison is too exhaustive for real-timerobotic navigation. Angeli et al. (2008) solves this by taking an advantage of the inverted index
associated with the dictionary. At each current image It, each time a word is found, the list of past
images in which it has previously appeared are retrieved. When a word that has appeared in image Ii
is found, the statistical score in equation (1) is added to the score of each image Ii. That is, at eachobserved current image It, the similarity score between It and previous image Ii is the summation of
tf-idf of all visual words that appear in both It and Ii:
𝛼

𝑛

𝑁

(2)

𝑤𝑖
𝑖
𝑠𝑖 = ∑𝑤=1
log � �𝑛𝑤

𝑛𝑖

where 𝛼𝑖 is the number of visual words that appear in It and Ii.
We consider this scoring as accurate and thus would like to apply this scoring to our method.
Unfortunately, we cannot apply this scoring for use with PIRF straightaway. In PIRF, no common
vocabulary is used to represent the image. The number of PIRFs detected in an input image is quite𝑛small: it is about 50–100 PIRFs. Consider the word frequency term 𝑤𝑖 in equation (2). It gives us the𝑛𝑖weight value of the frequency of the word in the image. However, if 𝑛𝑖 is too small, this term would
become very sensitive to noise. Therefore, in order to apply this scoring to our method, the word𝑛𝑛𝑁frequency term would be ignored. Because 0 ≤ 𝑤𝑖 ≤ 1, we set 𝑤𝑖 to 1 for all cases. The term log
𝑛𝑖

𝑛𝑤

𝑛𝑖

can be obtained by assigning 𝑁 = 𝑛𝑡 and 𝑛𝑤 as the number of models containing PIRF w. In otherwords, with a small number of PIRFs, scoring based on only the inverted document frequency termis sufficient for our method by avoiding the noise that might occur in the word frequency term. By𝑛ignoring the word frequency term 𝑤𝑖 , the scoring function can be written as𝑛𝑖𝑚𝑖𝑠𝑖 = ∑𝑘=1
log �

𝑛𝑡

𝑛𝑤𝑘

� ,

(3)

where 𝑛𝑤𝑘 is the number of models Mj, 0 ≤ 𝑗 ≤ 𝑛𝑡 , 𝑗 ≠ 𝑖 , containing PIRFs that match the kth PIRF
of the input model Mt, mi is the number of all matched PIRFs between input model Mt and querymodel Mi (mi is equivalent to 𝛼𝑖 in (2)). This model closely resembles scoring based on the number ofmatched PIRFs between Mt and Mi. The difference is that we assign more weight to the PIRF that is
likely to be distinctive. Matching between the input and query model will earn a high score whenmost of the matched PIRFs appear only in the query model.

Step 2: Considering Neighbors
Once we obtain the similarity score si between the input model Mt and query model Mi, we
proceed to the next step of scoring. Generally, this score can be used simply to determine that thepotential loop-closure is found for the model 𝑀argmax𝑖 (𝑠𝑖 ) . However, accepting or rejecting
loop-closure detection based on the score from a single image is sensitive to noise. To obtain highprecision, the system must not assert loop-closure detection with high confidence based only on asingle similar image. This avoidance of detection can be achieved by additionally considering thesimilarity score of neighboring image models. Therefore, we create another scoring function as𝛽𝑖 = ∑𝑖+𝜔
𝑘=𝑖−𝜔�𝑠𝑘 ∙ 𝑝𝑇 (𝑖, 𝑘)� ,(4)

where the term 𝑝𝑇 (𝑖, 𝑘) is the transition probability generated from a Gaussian sigma = 2 on the
distance in time between i and k (note that we did not use any motion models in this study). The
Gaussian parameter used here is determined in order to obtain the best result (See appendix C).
However, considering the graph in the Appendix, this parameter does not significantly affect theperformance of PIRF-Nav. In addition, 𝜔 stands for the number of neighbors examined. The use of
the term 𝑝𝑇 is much like the time evolution model of the probability density function in eq. (5) ofAngeli et al. (2008), in the sense that it gives the probability of transition from state k to state i. By thisscoring, a high score 𝛽𝑖 of the query model Mi is obtained if and only if its neighbors
𝑀𝑖−ω . . . , 𝑀𝑖−1 , 𝑀𝑖+1 , … , 𝑀𝑖+ω also earn a high score.

Step 3: Normalizing the Score

Now that the similarity score 𝛽𝑖 of the model 𝑀𝑖 can be obtained properly, it is necessary tonormalize. Practically speaking, the resulting number of matched features between images isdifficult to predict. Matching two images taken from the same place might output only a few
matched features, although some matching between different images might yield many matchedfeatures. That is, a score 𝛽𝑖 of model Mi, even though all of its neighbors obtain a good score, could
be lower than another score 𝛽𝑗 of the single model Mj if the matched features between Mt and Mj are
numerous. For that reason, the score must be normalized.
Based on the score 𝛽𝑖 of model 𝑀𝑖 , we calculate the standard deviation and mean over all thesescores to determine the loop-closure acceptance/rejection. To determine the loop-closure acceptanceor rejection, we need to consider the deviation among scores. If the input image is to be localized tosome previously visited places, the similarity score of this place to the nearest model and neighbors
should be high, while the score of the other model should be low. Otherwise, the loop-closure would
be rejected. However, the standard deviation and mean directly depend on the number of data.
Consider Fig. 3 for example. 𝛽𝑖 obtains the highest score. We calculate the deviation and meansover the set of scores 𝛽𝑖−𝑙𝑛 , … , 𝛽𝑖 , … , 𝛽𝑖+𝑙𝑛 .
The normalization used here is employed from the method done in the incremental BoW method(Angeli et el., 2008). Considering the set of scores 𝛽𝑖−𝑙𝑛 , … , 𝛽𝑖 , … , 𝛽𝑖+𝑙𝑛 , we calculate the standard
deviation (𝜎) and means (𝜇), where 𝑙𝑛 indicates the number of neighbors taken into consideration.
The normalized score 𝐶𝑖 of a score 𝛽𝑖 is obtained as follows:𝐶𝑖 = �
where

1,

𝛽𝑖 −𝜎
𝜇

, if 𝛽𝑖 ≥ 𝑇

Otherwise

𝑇 =𝜎+𝜇(5)(6)

By this normalization, the model with the sufficiently high score would be rewarded, while theFig. 3. Sample normalizing the similarity score of the query model Mi and input model Mt.

low score of the other model would be penalized. The illustration is shown in Fig. 3. There are 𝑙𝑛 = 7
neighbors taken into consideration, resulting in a set of 15 scores. The summation of deviation andmean T is calculated. The normalized score C is shown at the bottom graph.
The obtained similarity score for all possible models determines the most potential loop-closure
location Lj, where𝑗 = argmax𝑖 𝐶𝑖.

(7)

The parameter 𝑙𝑛 is used to limit the number of scores for calculating the T value, because the Tvalue can be very different in the long run as the number of mapped models increase. It should be
noted that the difference of the 𝑙𝑛 value does not greatly affect the overall performance; it is used
only to make sure that the calculated T value for every time step is in the same scale. Considering the
maximum score obtained in Step 1, it is also based on the same scale. Because the number of PIRFs
for each image is limited to a maximum of 150 as described in Section 3, the maximum number ofmatched PIRFs would always be less than 150.

Step 4: Loop Closure Acceptance/Rejection and Re-localization
The obtained location Lj would be accepted as loop-closure if 𝛽𝑗 − 𝑇 > 𝜏2 . We use the T value todetermine the loop-closure acceptance/rejection because it indicates both the deviation and meanvalue of the scores. The difference between the similarity score and T can reflect the quality of
localization. That is, the detected loop-closing location Lj would be accepted if and only if 𝛽𝑗 isgreater than 𝜎 + 𝜇 by at least 𝜏2 . After the localization, unlike other methods, the current model
Mt would be discarded. The number of mapped model nt would not be increased (see Fig. 9). The
system would store the model Mt as the new model in the map and continue acquiring new images
only if the loop-closure is rejected. This enables us to discard redundant models of previously visitedFig. 4. Sample case where normalized beta score is not symmetrical (upper). By performing the second summation,
the graph becomes more symmetrical (bottom).

locations. In this study, we simply discard the input model Mt if the loop-closure is accepted.
However, it might be helpful if the model is used to update the existing model, so that it can be moretolerant to dynamic changes.
For the case of loop-closure acceptance at Lj, the system must perform a few more tasks. Ideally,
the neighboring model scores of location Lj should decrease symmetrically from a model score 𝐶𝑗 .
However, scenes in dynamic environment always contain moving objects that frequently cause theocclusion. Some landmarks might be occluded. Therefore, we compensate for this by performing thesecond summation over the neighboring score model to achieve a more accurate localization. The
sample of this problem is shown by Fig. 4. The upper graph shows the score obtained from step 2.
The value of the maximum score 𝐶𝑗 , j = 87, is sufficiently high to satisfy the acceptance/rejection
condition. However, the graph is not symmetrical. The second summation can refine the graphs to be
more symmetrical, and the location can be re-located. It should also be noted that if the graphobtained from step 2 is already symmetrical, the second summation will just emphasize the score of
the winning location.
Particularly, given a set of beta scores 𝐶𝜔+1 , … , 𝐶𝑛𝑡−(𝜔+1) , the scores are re-calculated using theequation (4), resulting in
𝐶𝑖′ = ∑𝑖+𝜔
𝑘=𝑖−𝜔�𝐶𝑘 ∙ 𝑝𝑇 (𝑖, 𝑘)�

(8)

𝑗 = argmax𝑖 𝐶𝑖′(9)where ω + 1 ≤ 𝑖 ≤ 𝑛𝑡 − (𝜔 + 1). The loop-closure location Lj is finally re-located by these scores:-5. RESULTS AND EXPERIMENTS
We tested the proposed PIRF-Nav using three outdoor image datasets. Each one of them is used to
examine various difficulties, including dynamic changes and perceptual aliasing. The results
obtained from each dataset prove that PIRF-Nav is efficient. Finally, we combine all datasets toevaluate the performance of PIRF-Nav in the long run. The computation time is acceptable forreal-time applications with an impressive rate of recall with 100% precision.

5.1

Datasets

As described, three outdoor image datasets are used to evaluate the performance of PIRF-Nav.
The first dataset (New College), provided by Cummins and Newman (2008a) was chosen to test thesystem’s robustness to perceptual aliasing. It features several large areas of strong visual repetition,
including a medieval cloister with identical repeating archways and a garden area with a long
stretch of uniform stone wall and bushes.
The second dataset (City Centre), which was also provided by Cummins and Newman (2008a),
was collected intentionally to test the matching capability in the presence of scene changes. It wascompiled using the data collected along public roads near City Centre, featuring many dynamic
objects such as traffic and pedestrians. Moreover, it was collected on a windy day with brightsunshine, which renders abundant foliage and shadow features unstable.
For these two datasets provided by Cummins and Newman (2008a), a real mobile robot collected
the images. The robot moved through its environment, collecting images to the left and right of its
trajectory, approximately every 1.5 m. There were a total of 2,474 images collected from City Centre
and 2,146 images from New College. Each has 640 × 480 resolution. For this study, left and rightimages are combined before being processed by our system, that is, one location is associated with
one left image and one right image, and 1,237 images from City Centre and 1,073 images from New
College with a resolution of 1280 × 480 were obtained.
Actually, PIRF-Nav is proposed for highly dynamic environments, as stated in the title. Therefore,
we collected an additional dataset to improve these PIRF advantages. The third
dataset—Suzukakedai Campus (our campus)—was chosen to test the matching ability further, evenin highly dynamic environments: the first and the second visits are different events. For this dataset,
images are grabbed using a single monocular handheld camera (HDC-TM300; Panasonic Inc.) withan omnidirectional lens and with a frame rate of 0.5 frame/s. Images were collected during two days,on which different specific events were held. The first sequence (Seq. 1) was collected on anafternoon during an open-campus event under clear weather. Many people attended the event. Tents
and booths were set up for this event. The second sequence (Seq. 2) was collected on a cloudy
evening of a normal day with fewer people. All tents and booths had been removed. Major portionsof many scenes changed because of this event. We consider this change as highly dynamic because
marked changes occur for some special events. Collecting this dataset yielded a totals of 1,079
omnidirectional images (689 + 390) with 1920 × 1080 resolution. Fig. 5 shows the walking route fordata collection. The short dotted line indicates routes in which no images were collected.

5.2

Baseline

Among recent appearance-based methods, we consider FAB-MAP as the most suitable baseline
for comparison. Based on the popular BoW scheme, FAB-MAP uses the complex probabilistic
framework to handle the problem of perceptual aliasing properly. It considers the problem at theword level (i.e., the input information level). In fact, two recent well-known BoW-based methods forthis task exist: FAB-MAP of Cummins and Newman (2008a) and the incremental BoW method of

Fig. 5. Route of walks for data collection on two different days for the Suzukakedai Campus dataset.

Angeli et al. (2008). However, a true comparison in terms of accuracy between these two methods
has not been done because the latter was mainly proposed as a complementary method; a dictionaryof the latter method can be generated and updated in an online manner, whereas FAB-MAP requires
a preliminarily well-formed dictionary. An earlier study (Angeli et al. 2008) also described thisrequirement. In terms of accuracy, it is more appropriate to compare the result of PIRF-Nav with the
FAB-MAP.
Although FAB-MAP on the Suzukakedai Campus dataset can be implemented straightaway, theimplementation at City Centre and New College requires a slight modification for a fair comparison
with PIRF-Nav. In our study, one location comprises two images (left-hand-side and right-hand-side
images), but the original FAB-MAP represents one location with only a single image. That is,
FAB-MAP performs loop-closure detection on 2,474 images, whereas PIRF-Nav does it on 1237
images. To cope with this unfair condition, we combine the results of left-image and right-image of
FAB-MAP into one. Particularly, for each location, FAB-MAP has two answers, one for the left andanother for the right image. If either one of these answers is correct, the localization would beconsidered as correct. Consequently, with 100% precision, the recall rate on the 2,474 images of City
Centre increased from 37% to recall rate of 43% on the 1,237 images, and the 48% recall rate on the2,146 images of New College increased to 61% recall rate on the 1,073 images. These combined
results facilitate a fair comparison.
For the Suzukakedai campus, where the FAB-MAP can be implemented without any changes, noproper dictionary for FAB-MAP exists. The dictionary used for this dataset is identical to that used in
the City Centre and New College. However, our PIRF-Nav requires no preliminary dictionary
generation process. In fact, PIRF-Nav can start on any dataset without any modifications eventhough the datasets are collected from different countries with different building structures. Failure

of FAB-MAP on the Suzukakedai dataset confirms that “good” vocabularies are indispensable for
FAB-MAP.

5.3

Initialization and Testing Conditions

As described previously, there are a few parameters that play an important role in PIRF-Nav. We
explain the importance of all parameters and their appropriate values used for this study as follows:
−

−

−

−

−

−

θ : This is the distance threshold for PIRF extraction and feature matching. It controls thenumber of extracted PIRFs for appearance representation. If this parameter is too large, thenmore PIRFs would be obtained. Some might be noisy and useless, e.g., PIRFs that will never bematched during localization. In this work, we found that θ = 0.5 offers the highest performancefor all datasets. Actually, PIRF-Nav works best with small θ because a PIRF must be extracted
from slow-moving features. We have also tried θ = 0.5, 0.6, and 0.7, but the results are not muchdifferent, i.e., θ = 0.6 offers about 3% lower recall rate than θ = 0.5.
npirf_min and npirf_max: These are the minimum and maximum number of PIRFs for representing asingle image. These numbers are set manually to 10 and 100, respectively. The values control
the number of extracted PIRFs per image to be around 10–150. We have tried to set theseparameters at 100 and 200, which yields about 100–250 PIRFs per image. Although theperformance is not much different from settings at 10 and 150, the computation increases
greatly. Therefore, we select these values as the most appropriate value for PIRF extraction ofimages for all datasets.
𝜏1 : This is the threshold value for loop-closure detection/non-detection. This parameter canfilter out images with very few matched PIRFs between the input model and the query model
because a mere few PIRFs are insufficient for generating a reliable similarity score. In otherwords, this parameter indicates which image is considered “insufficient information.” In thiswork, we set 𝜏1 =3 as the threshold value for all experiments because it offers the highest recall
rate for all datasets. This parameter can be set to other values such as 4 or 5. The overall
accuracy will not differ much by changing this value. Using this parameter can reduce the
PIRF-Nav computation time. For images with insufficient information (too few PIRFs), thesystem can simply retain the input model as the model for the new location and start fetching
new input images.
𝜏2 : This is the threshold for determining the loop-closure acceptance or rejection. This parameter
indicates the difference between the beta score of the most probable loop-closing location andthe term 𝜎 + 𝜇 . Actually, this parameter is difficult to set in order to obtain 100% precision. As
in other works (Angeli et al., 2008; Cummins & Newman 2008), we select the threshold byconsidering the result to obtain 100% precision for all datasets. The relation between the recall
rate, the precision rate, and this threshold are shown by the graphs in the Appendix. A little
drop in threshold can reasonably increase the recall rate while retaining high precision.
Considering all datasets in this study, 𝜏2 = 3.1 yields the highest accuracy with 100% precision.
(See Appendix B)
ω : This is the parameter indicating how many neighbors are examined for calculating the
updated score in Step 2. If ω is large, the scoring would become slightly more stable, but theaccuracy of the localization would drop. For example, if ω = 20, then there would be 20 models
that cannot be used in localization (first 10 models and last 10 models). However, this parameterhas little effect on the overall accuracy of PIRF-Nav. For this study, ω has been set to 3. Other
values ω = 4, 5, 6 have also been tried, but the accuracy is mostly equivalent while thecomputation time is increased. However, this parameter is expected to depend directly on thecamera velocity. This value is expected to be larger because many neighbors will have highscores if the robot walks slowly while the capturing rate is high.
ln : The parameter indicates the number of model scores to be included for calculating thestandard deviation and means. Actually, this parameter is not very significant for databases lessthan 4000 images; 𝜎 and 𝜇 will not be very different even though they can be calculated forall over scores. However, these two values can gradually change as the number of score models
is increasing. Therefore, we need to set some fixed number of score models for calculating 𝜇
and 𝜎 to make the score of every time step be in the same scale and comparable.

With these parameters, for each dataset, each collected image is processed using the proposed
PIRF-Nav and is used either to initialize a new place, or, if loop-closure is detected and accepted, tolocalize the correct loop-closure location. No additional dataset exists for offline dictionary
generation.
Although there seems to be several parameters that users need to manually set, their values are
not sensitive to overall performance. The results in Fig. 7 show that the recall rate considerablyincreases by sacrificing just a small amount of precision. With the parameters used in this paper,
although it cannot be guaranteed to always yield 100% precision in any environment, its resulting
recall rate should be sufficiently good for loop-closure detection. In any case, a system that canalways offer 100% precision in any environment is difficult to obtain.
Three main experiments and one additional experiment were conducted in this study. The threemain experiments were the testing on each dataset—New College, City Centre, and SuzukakedaiCampus. An additional experiment was performed by combining all three experiments(1,237+1,073+1,079 = 3,389 images). This last experiment tested whether PIRF-Nav can run
incrementally over the long term. It is useful in many places and can accommodate the kidnapped
robot problem (i.e., taking the robot from England to Japan). Despite the increased number ofmapped places, the precision rate for loop-closure detection can remain at exactly 100% with a highrecall rate.

5.4

Results

The results of the experiments conducted for City Centre, New College, and SuzukakedaiCampus are shown in Fig. 6, and as precision-recall curves in Fig. 7. Although the FAB-MAP is run
on the full-scale image, PIRF-Nav has also been tested with three different levels of scale reduction:
0.25, 0.5, and 0.75. Because PIRF-Nav is based on feature matching, it requires one image matchingfor every input image. Additionally, all programs in this study were written in MATLAB and
executed with a 3.2 GHz CPU (Intel Corp.), therefore the computation was slightly slower than thatof FAB-MAP. We resolve this by showing that, even with a reduced image, PIRF-Nav offers a muchhigher recall rate with 100% precision than FAB-MAP. Although it is reasonable to say that
PIRF-Nav’s computation time can be shortened further, it is more appropriate to present what wehave obtained instead of what we expect to obtain.
Figure 6 presents navigation results overlaid on the aerial photographs. These results weregenerated using images with 50% scale reduction. The system correctly identifies a large portion of
possible loop-closures with good scores. No false positives met the score threshold.
Precision-recall curves are depicted in Fig. 7. The curves were generated by varying the thresholdvalue 𝜏2 at which a loop-closure was accepted. Ground truths were obtained from Cummins andNewman (2008a) for City Centre and New College dataset, and labeled by GPS for the Suzukakedai
dataset. The threshold value for 100% precision varied depending on the image size. For parameters,
𝜏2 = 3 has been set for all image scales. These thresholds offer 100% precision for all datasets foreach image scale. The effects of threshold values on precision and recall for each image scale areshown as graphs in the Appendix. The graphs show that changing of threshold values does notaffect the recall rate too much.
Considering 100% precision, PIRF-Nav achieves a high recall rate using an image scale more than
0.5. It is particularly interesting that a 100% image scale does not always offer the highest recall rate(about 70–80% for the City Centre and New College datasets), although the image scales of 0.5 andVehicle Trajectory
Loop Closure(a) New College (Image scale = 0.5)
Vehicle Trajectory
Loop Closure

Vehicle Trajectory
Loop Closure(b) City Centre (Image scale = 0.5)(c) Suzukakedai Campus (Image scale = 0.5)

Fig. 6 (a) Appearance-based matching results for New College dataset overlaid on an aerial photograph. The aerial
photograph and the ground truth data are obtained from Cummins and Newman (2008a). (b) Appearance-basedmatching results for City Centre dataset overlaid on an aerial photograph. The aerial photograph and the ground truth
data are also obtained from Cummins and Newman (2008a). (c) Appearance-based matching results for Suzukakedai
dataset overlaid on an aerial photograph. Ground truth is generated from the GPS data. Any pair of matched images
that was separated by less than 10 m based on GPS was accepted as a correct correspondence. All results are for image
scale = 0.5. Two images that were assigned a similarity score 𝛽 − 𝑇 > 3 (based on appearance alone) are marked in red(darker color) and joined with a line. For all datasets, there are no incorrect matches that meet this threshold. These
results are best viewed as videos (Extension 2, Extension 1, and Extension 3 for (a), (b) and (c) respectively).

0.75 offer better rates of recall. The highest rate is obtainable using an image at scale = 0.75; about
85% for City Centre and New College datasets. Unfortunately, the image size at scale >0.75 consumes
too much time for real-time applications by the current PIRF-Nav. Therefore, PIRF-Nav requires a
reduced size of an image at scale <= 0.5 to run in real time. In other words, compared to the approachof Cummins and Newman (2008a) and Angeli et al. (2008), PIRF-Nav, in its current form, still has
slightly lower performance in terms of computation time. However, PIRF-Nav compensates for thisshortcoming with the ability to run on various image scale sizes. Even at a 50% image scale,
PIRF-Nav offers about two times the rate of recall of the FAB-MAP in real time (78% for New College,

(a) New College(c) Suzukakedai Campus(b) City Centre(d) Combined Datasets

Fig. 7 Precision-recall curves for all experiments at all image scales: (a) New College, (b) City Centre, (c) SuzukakedaiCampus, (d) combined datasets.

and 84% for City Centre).
It is noteworthy that the recall rate of the Suzukakedai campus dataset is apparently markedly
lower than those of City Centre and New College because it contains sequences obtained undermarkedly different conditions (specific events). By considering loop-closure only on the Seq. 1 (firstday), for which all images were collected on the same day, the system achieves a 68% recall rate with
100% precision for the image scale of 0.5. This rate is not very different from those at City Centre and
New College. In fact, FAB-MAP did not perform well with this dataset. We believe that the main
reason is the dictionary. The structures of most buildings in England and Japan differ greatly.
Vocabulary captured from streets in England is not useful to describe the feature in scenes in Japan.
Nevertheless, PIRF-Nav can run in various environments without the need for offline dictionary
generation. The Suzukakedai Campus result also proves that PIRF-Nav is compatible withomnidirectional images.
Computation times of PIRF-Nav for each image scale of all datasets are shown in the graphs of
Fig. 8. For the computation time, we are interested only in the image scale in which the PIRF-Nav canprocess in real time: scale = 0.5 and 0.25. According to the graphs, the computation time is acceptable
for real-time application. The average time is about 2–3 s, including SIFT extraction. Unlike otherapproaches, the computation of PIRF-Nav depends on the number of extracted PIRFs of the current
image, which creates high peaks in the graph. Results show that time is acceptable for real-time
applications. For City Centre and New College, images are captured approximately every 2 s.
Consequently, each combined left and right image is obtained about every 4 s. The average time ofabout 2–3 s for one image is acceptable. The time can be reduced further to yield high speed with animage scale of 0.25 with averaged time per image within 1 s, including SIFT extraction. This
high-speed mode of PIRF-Nav yields a lower rate of recall, but the recall rate is approximately equal
to that of FAB-MAP. The computation time of PIRF-Nav is apparently even faster than the original(a) City Centre(b)(b) New College

Precision-threshold curve (Image(c) Combined Datasets(d) Suzukakedai

Fig. 8. Processing times for images for all datasets at image scales 0.25 and 0.5 including SIFT extraction. All programs
were written in MATLAB 7.6.0.

FAB-MAP. However, the latest FAB-MAP 2.0 (Cummins and Newman 2009) has been improved tobe applicable to cars instead of robots. It processes one image within 0.1 s, which is much faster thanour system. Nevertheless, the PIRF-Nav is currently being proposed for robots by emphasizing therecall rate improvement. Although no clear results for testing FAB-MAP 2.0 exists on City Centre
and New College, its accuracy should be equivalent because the authors specifically examine speeds
instead of accuracy, as was done in FAB-MAP 1.5 (Cummins and Newman 2008b). In any case, itwould also be interesting to consider extending PIRF-Nav for use in automobiles, similarly to
FAB-MAP 2.0. We leave this as a topic for future studies.
The computation time of PIRF-Nav might also be considered as the number of feature matchings
required for each input image (see Fig. 10). For all datasets, at an image scale of 0.5, PIRF-Nav’s
maximum number of required feature matchings is about 4000–5000K, which implies that the
maximum number of feature matchings for every input image is approximately equal to that
required for image-to-image matching (i.e., match 2000–4000 SIFTs to 2000–4000 SIFTs of 4000k –16000k matching). In other words, for every input, PIRF-Nav requires a processing time
approximately equal to that required for image matching twice (one for PIRF extraction and anotherfor loop-closure detection).
It is noteworthy that the number of feature matchings, as shown in Fig. 10, apparently does notcorrespond with the computation time portrayed in Fig. 8; the numbers of feature matchings forimage scales 0.5 and 0.75 are not very different. However, their computation times differ greatly: thePIRF extraction for image scale 0.5 is much greater than scale 0.25, although feature matchings forloop-closure detection are equivalent. Furthermore, it is noteworthy that the number of feature
matchings becomes zero for some images. This process of zeroing the matchings is done by Step 1 of
the algorithm; images with either insufficient amount of PIRFs or a low similarity score are rejected.

(a)

(b)

(c)

(d)

Fig. 9. Accumulated number of PIRFs: (a) New College, (b) City Centre, (c) Suzukakedai Campus. (a)–(c) graphs areplotted for every image scale of 0.25, 0.5, 0.75 and 1.0, with 𝜏2 = 3. The dotted line, plotted by hand, roughly shows
loop-closure images. The number of PIRFs during loop-closure detection becomes more stable. (d) the graphs for
combined datasets. Graphs are plotted only for image scale = 0.25 and 0.5 because they offer real-time performance.

For memory, the average number of PIRFs for each model is approximately 100 (50–150). The
memory required for one image representation is therefore 100 × 128 = 12,800 floats. This necessary
memory size is slightly less than that required by the former incremental method of Angeli et al.
(2008), where the dictionary size is about 40,000, which results in 40,000 integers to represent one
image.
The graphs in Fig. 9 show the number of extracted PIRFs accumulated for representing the map(all visited locations) at each time step. In the current PIRF-Nav, the system simply discards the
input model, which is detected as the loop-closure location, so that the number of accumulated PIRFs
becomes approximately stable for loop-closure detected locations. The dotted line in Fig. 9, shown byhand, roughly indicates images being detected as loop-closure. For all datasets, the maximum
number of PIRFs that must be retained is less than 60,000 PIRFs. This number of PIRFs is acceptablecompared to the method of Angeli et al. (2008); 40,000 visual words for 500+ images are not muchdifferent from 60,000 PIRFs for 1000+ images. By further consideration of the graph, we can also saythat the number of extracted PIRFs can be limited to the range of 50–150 for any datasets at every
image scales, which guarantees that PIRF-Nav will not face the problem of retaining highly
overloaded features.
In addition to testing of three datasets (City Centre, New College, and Suzukakedai), we conduct
the last experiment by combining all datasets. This experiment proves two more advantages of
PIRF-Nav: performance in the long run and kidnapped robot problem. The precision-recall curve of

(a)

(c)

(b)

(d)

Fig. 10 Number of feature matchings necessary for loop-closure detection of every dataset at 𝜏2 = 3: (a) New College(b) City Centre (c) Suzukakedai Campus. (a)–(c) graphs are plotted for image scales of 0.25, 0.5, and 0.75. (d) Graphs for
combined datasets. Graphs are plotted only for image scale = 0.25 and 0.5 because they offer the real-time performance.
For each dataset (a)–(c), the averaged number of matching at image scale < 0.5 is approximately equal to that required
for matching two single images. The number of matchings can be reduced further by using a scale of 0.25, although
the performance is the same as that of FAB-MAP.

this experiment is portrayed in Fig. 7(d). For this experiment, we specifically examine only image
scales of 0.25 and 0.5 because larger scales are unacceptable for real-time applications. The
computation time, the number of accumulated PIRFs, and the number of feature matchings arepresented in Fig. 8(c), Fig. 9(d), and Fig. 10(d), respectively. In terms of accuracy, PIRF-Nav can stillobtain a good recall rate (65%) with 100% precision. In addition, by sacrificing only a small amountof precision (i.e., with 97% precision), the recall rate increases considerably to 72%. In terms of time,even with 3000+ images, the computation time is still acceptable for real-time applications. The
averaged processing time per image increases to around 4–5 s. However, because of the fact that the
combined scene of each location from New College and City Centre is obtained every 4 s, thisprocessing time is not too far from real-time performance. This processing time is also not too
different from that reported by FAB-MAP 1.0 (processing time is about 3–6 s per image for City
Centre).
The increased number of PIRFs does not affect the system accuracy much (the recall rate for eachdataset is still approximately the same) because the PIRFs are sufficiently distinctive for use as goodsignatures for each place in spite of the presence of dynamic changes and perceptual aliasing. The
required feature matching number is still 4000K–16000K. The PIRFs retained in the system for thelast image are approximately 120K. This number is apparently too large for only 3000+ images, as
FAB-MAP 2.0 (Cummins and Newman 2009) requires 100K words for 100K images. However, thisamount of PIRFs might be acceptable for mobile robots in the same sense as FAB-MAP 1.0 (Angeli etal. 2008; Cummins and Newman 2008a), as offline dictionary generation is not needed. In futurestudies, we plan to extend the PIRF-Nav to be sufficiently fast for application to car navigation
systems such as FAB-MAP 2.0, as discussed in the next section.
Some examples of typical image matching results are presented in Fig. 11 and Fig. 12. Fig. 11(bottom) highlights robustness to drastic viewpoint changes in New College. The PIRF-Nav canachieve this by considering the neighboring scores. For this sample, two peaks in the score exist,
which might imply that the robot used to visit this place previously at least two times. The graphs
show in each step how the score has been updated and used to calculate the pdf for re-localization.
Through re-localization, an image which earns a lower score in step 1 might obtain the highest pdf inthe step 4. Fig. 11 (top) shows matching performance in the presence of scene changes in City Centre.
For this matching, PIRF-Nav mostly ignores the truck because it was believed to be an unreliableobject. We emphasize that these results are not outliers; they represent typical system performance.
Fig. 12 shows more matching in the presence of highly dynamic changes in the Suzukakedai campus.
Empty parking lots in the query image become full in the input image, which does not affect
PIRF-Nav because it mostly ignores such nearby unstable objects.

6. DISCUSSION
Actually, PIRF-Nav is a completely incremental and online appearance-based method allowing
loop-closure detection in real time. The results obtained from experiments on three outdoor
datasets––City Centre, New College, and Suzukakedai––confirm that PIRF-Nav outperforms thecurrent BoW method in terms of accuracy. The implementation of multi-steps loop-closure
detection/non-detection and loop-closure acceptance/rejection enable the system to close the loop
without the need to calculate the full posteriori. Using PIRF as the main visual feature is also a
success. As distinct from a BoW scheme, PIRF selects the most distinctive local feature instead ofclustering all of them into the visual word, which enables the PIRF-Nav to cope efficiently withdynamic changes of scene. Furthermore, the use of PIRF can handle the problem of strong perceptual
aliasing efficiently by retaining the most unique feature of the places and use them as the signatureof the place. The scoring method based on tf-idf enables us to calculate the similarity score forloop-closure detection properly. The test of Suzukakedai Campus shows that PIRF-Nav is also
applicable for use with omnidirectional images. In contrast, the BoW-based method encodes anentire scene into a set of unordered visual words. In some cases of dynamic changes, BoW also
includes many noisy words in the appearance model. This inclusion of words would be problematic
if the scene changed markedly. We believe that this might be one reason why FAB-MAP obtains
lower accuracy of the City Centre than at the New College.
Another advantage of PIRF-Nav is the ability of incremental loop-closure detection as in themethod of Angeli et al. (2008). The combined dataset experiment illustrates clearly that PIRF-Nav
can run in many environments without confusion, although FAB-MAP still lays its disadvantage ona preliminarily well-generated dictionary.
Despite its success, our PIRF-Nav leaves great room for improvement. First, its computation timeof PIRF-Nav can be speeded up further, which might be done in one of two ways. The first way isimplementation of the whole system with more appropriate language instead of MATLAB, which is
expected to speed up the time slightly. The second means is to structure the PIRFs. As described inthis paper, PIRFs for each model are simply stores as the sequential data in the memory. Every modeof image retrieval requires O(n2). If the PIRF has been stored in some efficient way, i.e., tree-like BoW,
its retrieval time could be hastened markedly. In addition, application of some other method of rapid
image matching could decrease the time. For each image, PIRF-Nav constantly requires time that isequivalent to that required for double image matching. Reducing the time for image retrieval andimage matching for PIRF-extraction can speed up the time greatly. We plan to implement this in theFig. 11 Some examples of images detected correctly as loop closure locations despite scene changes. Blue arrows show
PIRFs extracted from the input image and query image. The red arrows are matched PIRFs between two images. The
images, taken from City Centre and New College, failed localization by FAB-MAP. Four graphs show the resulting
calculated score from each step. (Top) PIRFs did not capture the truck because it realized that the truck is a nearby
object that is unlikely to be present for a long time. (Bottom) Loop can be closed in spite of a much different viewpoint.

future to make PIRF-Nav applicable to car navigation similarly to FAB-MAP 2.0.
For a slight but simple improvement, PIRF-Nav can be combined with some post-processing

Fig. 12 Sample images from Suzukakedai that were detected correctly as the same place. The input image is collected on
weekdays with full parking lots (right); although the query image (left) was collected on holidays with empty parking
lots (special events were hold on holidays with crowded people but in other different places). The four graphs display
the scores calculated from each step. Major portion of images which belong to road surface have been ignored by
PIRF-Nav because it is a common nearby objects that changes overtime. Discarding these unreliable image's component
can prevent the occurrence of perceptual aliasing.

techniques such as epipolar geometry (Nister 2004) to increase its performance, as done by Angeli etal. (2008) and Cummins and Newman (2009). Using multiple-view geometry algorithm, thethreshold can be decreased. Some wrong matches that gain a probability more than threshold would
be rejected by this algorithm. The PIRF-Nav can drastically increases the recall rate by sacrificing asmall amount of precision (as depicted in Fig. 7). Therefore, a lower threshold can improve the
PIRF-Nav result considerably. In addition, accessing to the motion models is expected to provide thesystem a good location priori for use in re-localization based on Bayes' filtering.
Actually, PIRF can also be investigated more extensively. Instead of simple averaging the SIFTs toobtain PIRF, we can more carefully consider the orientation of each bin in the SIFT, which mightyield a more compacted PIRF with similar or better performance.

7. CONCLUSIONSAs described herein, we have presented an online incremental appearance-based localization andmapping based using Position Invariant Robust Feature named PIRF-Nav. The proposed systemoutperforms the state-of-the-art BoW based method, FAB-MAP, in terms of accuracy; it offers about
a two times higher recall rate at 100% precision. The system requires no offline processing. Testing
using a combined dataset proves that PIRF-Nav can offer such a capability. All performance hasbeen evaluated by testing using two standard datasets provided by Cummins and Newman (2008a)
and our own collected dataset. In fact, PIRF-Nav is based on scoring the feature matching by
combining the tf-idf into the simple feature matching to earn a reliable score and then convert such ascore into a probability that is useful with discrete Bayes filtering. The method can run incrementallyin real time, even for 3000+ images.

ACKNOWLEDGMENT
This study was supported by an Industrial Technology Research Grant Program received in 2004
from the New Energy and Industrial Technology Development Organization (NEDO) of Japan. Also,
the authors gratefully acknowledge Oxford Robotics Research Group for their provided databaseand source codes.

REFERENCES
Angeli, A., Filliat, D., Doncieux, S. & Meyer, J. (2008). Fast and Incremental Method for Loop-Closure
Detection Using Bags of Visual Words. IEEE Trans. Robotics, 24(2): 1027-1037.
Bay, H., Tuytelaars, T. & Gool, L. V. (2006). SURF: Speeded Up Robust Features. Proc. Euro. Conf.
Computer Vision (ECCV).
Bowling, M., Wilkinson, D., Ghodsi, A. & Milstein, A. (2005). Subjective Localization with Action
Respecting Embedding. Proc. Int’l Sym. Robotics Research (ISRR).
Chen, C. & Wang, H. (2006). Appearance-based Topological Bayesian Inference for Loop-closing
Detection in a Cross Country Environment. Int’l Jour. Robotics Research, 25(10): 953-983.
Cummins, M & Newman, P. (2008a). FAB-MAP: Probabilistic Localization and Mapping in the Spaceof Appearance. Int’l Jour. Robotics Research, 27(6): 647-665.
Cummins, M. & Newman, P. (2008b). Accelerated Appearance-Only SLAM,” Proc. IEEE Int’l Conf.
Robotics and Automation (ICRA).
Cummins, M. & Newman, P. (2009). Highly Scalable Appearance-Only SLAM – FAB-MAP 2.0. Proc.
Robotics: Sciences and Systems (RSS).
Filliat, D. & Meyer, J. A. (2003). Map-based Navigation in Mobile Robots—I. A Review of Localisation
Strategies. Cognitive Systems Research, 4(4): 243-282.
Filliat, D. (2007). A Visual Bag of Words Method for Interactive Qualitative Localization and
Mapping. Proc. IEEE Int’l Conf. Robotics and Automation (ICRA).
Goedeme, T., Nuttin, M., Tuytelaars, T. & Gool, L. V. (2007). Omnidirectional Vision Based
Topological Navigation. Int’l Jour. Computer Vision, 74(3): 219-236.
Ho, K. & Newman, P. (2007). Detecting Loop Closure with Scene Sequences. Int’l Jour. Computer
Vision, 74(3): 261-286.

Kawewong, A., Tangruamsub, S. & Hasegawa, O. (2009). Wide-baseline Visible Features for Highly
Dynamic Scene Recognition. Proc. Int’l Conf. Computer Analysis of Images and Patterns (CAIP).
Kosecka, J., Li, F. & Yang, X. (2005). Global Localization and Relative Positioning based on
Scale-invariant Keypoints. Robotics and Autonomous Systems, 52(1): 27-38.
Krose, B. J. A., Vlassis, N. A., Bunschoten, R. & Motomura, Y. (2001). A Probabilistic Model for
Appearance-based Robot Localization. Image and Vision Computing, 19(6): 381-391.
Lamon, P., Nourbakhsh, I., Jensen, B. & Siegwart, R. (2001). Deriving and Matching Image
Fingerprint Sequences for Mobile Robot Localization. Proc. IEEE Int’l Conf. Robotics and Automation(ICRA).
Levin, A. & Szeliski, R. (2004). Visual Odometry and Map Correlation. Proc. IEEE Int'l Conf. Computer
Vision and Pattern Recognition (CVPR).
Li, F. & Kosecka, J. (2006). Probabilistic Location Recognition Using Reduced Feature Set. Proc. Int’l
Conf. Robotics and Automation (ICRA).
Lowe, D. (2004). Distinctive Image Features from Scale-Invariant Keypoints. Int’l Jour. Computer Vision,
60(2): 91-110.
Meyer, J. A. & Filliat, D. (2003). Map-based Navigation in Mobile Robots—III. A Review of
Map-learning and Path-planning Strategies. Cognitive Systems Research, 4(4): 283-317.
Newman, P., Cole, D. & Ho, K. (2006). Outdoor SLAM Using Visual Appearance and Laser Ranging.
Proc. IEEE Int'l Conf. Robotics and Automation (ICRA).
Nister, D. (2004) An Efficient Solution to the Five-Point Relative Pose Problem. IEEE Trans. PatternAnalysis and Machine Intelligence (PAMI), 26(6): 756-777.
Nister, D. & Stewenius, H. (2006) Scalable Recognition with a Vocabulary Tree. Proc. IEEE Int’l Conf.
Computer Vision and Pattern Recognition (CVPR).
Schindler, G., Brown, M., & Szeliski, R. (2007). City-scale Location Recognition. Proc. IEEE Conf.
Computer Vision and Pattern Recognition (CVPR).
Se, S., Lowe, D. & Little, J. (2001). Vision-based Mobile Robot Localization and Mapping Using
Scale-Invariant Features. Proc. IEEE Int'l Conf. Robotics and Automation (ICRA).
Silpa-Anan, C. & Hartley, R. (2004). Localisation Using an Image-map. Proc. Aust. Conf. Robotics andAutomation.
Sivic, J. & Zisserman, A. (2003). Video Google: A Text Retrieval Approach to Object Matching inVideos. Proc. IEEE Int’l Conf. Computer Vision (ICCV).
Torralba, A., Murphy, K. P., Freeman, W. T. & Rubin, M. A. (2003). Context-based Vision System forPlace and Object Recognition. Proc. IEEE Int’l Conf. Computer Vision (ICCV).
Ulrich, I. & Nourbakhsh, I. (2003). Appearance-based Place Recognition for Topological Localization.
Proc. IEEE Int’l Conf. Robotics and Automation (ICRA).
Wang, J, Zha, H., & Cipolla, R. (2006). Coarse-to-fine Vision-based Localization by Indexing
Scale-Invariant Features. IEEE Trans. System, Man and Cybernetics, 36(2): 413-422.

Wolf, J., Burgard, W. & Burkhardt, H. (2005). Robust Vision-based Localization by Combining an
Image-retrieval System with Monte Carlo Localization. IEEE Trans. Robotics, 21(2): 208-216.
Zivkovic, Z., Bakker, B. & Krose, B. (2005). Hierarchical Map Building Using Visual Landmarks andGeometric Constraints. Proc. IEEE/RSJ Int'l Conf. Intelligent Robots and Systems (IROS).

APPENDIX A: APPENDIX OF MULTIMEDIA EXTENSIONS
Table of multimedia extension
Extension
1
2
3

Type
Video
Video
Video

Description
Results for the City Centre Dataset
Results for the New College Dataset
Results for the Suzukakedai Dataset

APPENDIX B: RELATIONSHIP BETWEEN THRESHOLD AND ACCURACY
The appendix presents the graphs showing the relationship between threshold values andprecision-recall rate for all dataset at every image scale.

APPENDIX C: RELATIONSHIP BETWEEN SIGMA AND PRECISION
The appendix presents the graphs showing the relationship between threshold values (𝜏2 ), sigma
value used for Gaussian distribution in (4) and (8), and precision rate for each dataset. From theobtained graphs, we can simply use high sigma value in order to obtain precision-1. However, highsigma reduces the recall rate. In this study, sigma value around 2 - 3.5 seems to yield a reasonable
good result both for precision and recall. Also, it is noteworthy that sigma value does not much affectthe precision; all precisions are greater than 80% at any thresholds for any datasets.

City Centre

New College

Suzukakedai