Tree-based indexing for real-time ConvNet landmark-based visual place recognition

Abstract

Recent impressive studies on using ConvNet landmarks for visual place recognition take an approach that involves three steps: (a) detection of landmarks, (b) description of the landmarks by ConvNet features using a convolutional neural network, and (c) matching of the landmarks in the current view with those in the database views. Such an approach has been shown to achieve the state-of-the-art accuracy even under significant viewpoint and environmental changes. However, the computational burden in step (c) significantly prevents this approach from being applied in practice, due to the complexity of linear search in high-dimensional space of the ConvNet features. In this article, we propose two simple and efficient search methods to tackle this issue. Both methods are built upon tree-based indexing. Given a set of ConvNet features of a query image, the first method directly searches the features’ approximate nearest neighbors in a tree structure that is constructed from ConvNet features of database images. The database images are voted on by features in the query image, according to a lookup table which maps each ConvNet feature to its corresponding database image. The database image with the highest vote is considered the solution. Our second method uses a coarse-to-fine procedure: the coarse step uses the first method to coarsely find the top-N database images, and the fine step performs a linear search in Hamming space of the hash codes of the ConvNet features to determine the best match. Experimental results demonstrate that our methods achieve real-time search performance on five data sets with different sizes and various conditions. Most notably, by achieving an average search time of 0.035 seconds/query, our second method improves the matching efficiency by the three orders of magnitude over a linear search baseline on a database with 20,688 images, with negligible loss in place recognition accuracy.

Keywords

Visual place recognition ConvNet landmark tree-based indexing k-means tree nearest neighbor search

Introduction

Visual place recognition is a fundamental problem in computer vision as well as in mobile robotics. Nowadays, it is attracting more and more attention in autonomous vehicles and robots such as self-driving cars and service robots, as it allows these systems to navigate without any human intervention. The goal of visual place recognition is to determine whether the current view of the camera corresponds to a location that has been already visited or seen.¹ To achieve this goal, a visual place recognition system matches the image acquired at the current location with those obtained at previously visited locations. That is, the problem of visual place recognition is essentially one of image matching, which directly relies on the descriptors used for the different locations. Although great strides have been made, visual place recognition is still challenging because a range of environmental and conditional changes usually result in significant variations in image appearances. These changes are due to variations in weather, the time of day, season, camera viewpoint, and so on. As a result, appearance variations make it difficult to develop descriptors that are able to recognize places reliably.

Until recently, there were two popular categories of visual place recognition approaches^1,2: local descriptor based^3

–6 and global descriptor based.^7

–14 Local descriptor-based approaches use a set of local keypoint descriptors, such as scale-invariant feature transform (SIFT)¹⁵ and speeded up robust features (SURF),¹⁶ to represent an image. These local keypoint descriptors are usually extracted in two phases: (a) the detection phase in which a set of keypoints are first detected and (b) the description phase in which neighbor regions around the detected keypoints are used to create local keypoint descriptors. In contrast, global descriptor-based approaches simply use one global vector, such as GIST¹⁷ and histogram of oriented gradients,¹⁸ to represent an image. A global descriptor is usually computed using an entire image as input. Although these two descriptor categories have achieved tremendous success, each has its own disadvantages, as have been identified in the literature.^1,2 Thanks to the invariance properties of local descriptors, local descriptor-based approaches are usually more robust to occlusions and viewpoint change. However, they are sensitive to illumination change, which generates perceptual aliasing and reduces the discriminative power of local descriptors. In contrast, global descriptor-based approaches have better illumination invariance but offer less robustness to occlusion and viewpoint change. Consequently, neither of these categories are satisfactory in environments that experience a combination of illumination, occlusions, viewpoint, and other changes.

Recent work has shown that convolutional neural networks (CNNs) have the remarkable ability to a variety of visual tasks of mobile robot,^19
–21 including visual place recognition. More specifically, in order to overcome the weakness of existing scene description approaches, the literature^19,20 proposed to directly extract the whole-image descriptors using a pretrained CNN²² and achieved great success. Most recently, a novel solution has been proposed by Süenderhauf et al.²³ This solution has demonstrated impressive recognition accuracy in a range of challenging environments with significant appearance and viewpoint variations. It makes full use of the power of ConvNet features to match landmarks between images for visual place recognition. Similar to the method by Süenderhauf et al.,²³ we refer to this category of approaches as ConvNet landmark-based approaches. Figure 1 shows the examples of ConvNet landmark-based place recognition. Generally, an approach in this category proceeds in three major steps: (a) a number of landmarks are first detected in an image and expressed as bounding boxes (as shown in Figure 1), (b) detected landmarks are then described by ConvNet features, and (c) descriptors based on ConvNet features are matched. One can argue that ConvNet landmark-based approaches lead to good adaptability for place recognition in complex environments. On one hand, by working in a compromised way, ConvNet landmark-based approaches achieve their superiority by enjoying the benefits of both global descriptor-based and local descriptor-based approaches.^1,23
–25 Specifically, since the typical size of the bounding box of a detected landmark is larger than a region used for describing a keypoint, condition invariance of global descriptor-based approaches can be obtained within the bounding box. Conversely, the size of a bounding box is smaller than a full image, so that the viewpoint invariance of local descriptor-based approaches can be retained. On the other hand, compared to handcrafted features used in traditional approaches, ConvNet features have shown a better discrimination capacity, which leads to higher matching rates and fewer recognition errors in visual place recognition.^19,20 For these reasons, ConvNet landmark-based approaches are more likely to overcome the weaknesses of the two categories of approaches mentioned above and achieve robust performance in challenging environments, especially when multiple environmental conditions and viewpoint vary, as illustrated in Figure 1.

Figure 1.

Sample examples of matched image pairs produced by a ConvNet landmark-based approach, which is accelerated using our proposed two-stage method. These images come from the testing data sets used in our experiments (see detail in Datasets section). For each example, the bounding boxes with the same color in the two matched images show the landmarks that have been correctly matched via our proposed two-stage method. Best viewed in color. (a) UACampus (06:20 vs. 22:15), its main change includes large illumination. (b) CMU (spring vs. winter), its main changes include large seasonal and moderate illumination. (c) St Lucia (08:45 vs. 15:45), its main changes include moderate illumination and large shadows. (d) Mapillary (mploop1 vs. mploop2), its main changes include large viewpoint and moderate illumination. CMU: Carnegie Mellon University.

However, for satisfactory performance in place recognition, we usually need to detect a sufficient number of landmarks and use ConvNet features of sufficient dimensions (even after dimensionality reduction). For example, in the method by Süenderhauf et al.,²³ 100 landmarks within each image were detected, and the dimensions of original ConvNet features were reduced to 1024. Consequently, the image matching step using exhaustive comparison is very time-consuming, preventing ConvNet landmark-based approaches from being able to perform place recognition in an environment of even moderate size in real time. So far, no effective solution to improve the computational efficiency of ConvNet landmarks-based approaches has been reported. Therefore, how to perform place recognition with high-dimensional ConvNet features in real time, without losing recognition accuracy, represents a challenge, and it is the focus of this article.

Specifically, we propose two methods in this article to speed up the ConvNet landmark-based place recognition. Our methods achieve their efficiency through tree-based indexing, which is an effective and popular approach for approximate the nearest neighbor (NN) search. Its basic idea is to directly index the K-NN matches of a set of visual features in a tree, a particular data structure for efficient feature matching. Thanks to its efficiency, tree-based indexing has been widely applied in many large-scale vision applications, such as image retrieval^26,27 and object recognition.²⁸ In addition, two inspirations for our methods are as follows:

The effectiveness and applicability of tree-based indexing to visual place recognition have been verified in the work.²⁹ In that work, randomized k-d tree-based indexing was used for real-time loop closure detection, which is a particular application of visual place recognition in appearance-based robot simultaneous localization and mapping. Although the work²⁹ relies on local descriptors, that is, directly matching SIFT features using tree-based indexing, its superior performance to bag of words in accuracy and efficiency demonstrates the possibility of tree-based indexing to solve our problem.

The landmarks used in ConvNet landmark-based approaches are essentially image patches. With high-dimensional features, tree-based indexing is usually considered to be ineffective. In the extreme case, to achieve good search accuracy, the computational complexity may degrade to that of a linear search. However, it has been shown that this problem does not happen when matching similar image patches with high-dimensional features.^30,31 Specifically, an exciting finding has been observed: In the case of similar image patches, the search efficiency of tree-based indexing does not decrease with dimensionality; on the contrary, the search accuracy may increase to some degree. Because landmarks detected in ConvNet landmark-based approaches are image patches of high dimensions, we believe this finding is also applicable to our case.

Motivated by the above observations, in this article, we explore the possibility of leveraging tree-based indexing to speed up ConvNet landmark-based approaches, while retaining their recognition accuracy. Among various existing tree structures, the multiple randomized k-d trees and the priority search hierarchical k-means tree have been demonstrated the best performance.^30,31 What’s more, the latter has been shown to be more effective than the former when a high search accuracy is required.^30,31 Therefore, we use the priority search hierarchical k-means tree in our methods, although other types of tree structures may also work well. For simplicity, we use the term HKMeansTree for the priority search hierarchical k-means tree in this article.

In terms of the number of candidate image matches, we present a one-stage method and a two-stage method. The one-stage method applies tree-based indexing to find the top match as follows. First, we directly retrieve the approximate NN matches of ConvNet features of a query image in an HKMeansTree structure, which is constructed over ConvNet features of database images in an off-line process. Then the retrieved matching features vote for the corresponding database images, according to a prepared lookup table which stores the mapping from each ConvNet feature to its corresponding database image. Finally, we consider the image with the highest vote as the final match. By extending the one-stage method, our two-stage method uses a coarse-to-fine search scheme. In the coarse step of the method, we use the one-stage method as above to find the top-N candidate database images, where N > 1. In the fine step, we perform a fast-linear search in Hamming space, based on hash codes of these candidates, to determine the final match of the query image.

To verify the effectiveness of our methods, we perform a thorough empirical evaluation using five data sets of different sizes involving changes in various environmental conditions. Experimental results show that our methods can significantly reduce the recognition time with negligible decrease in search accuracy. Specifically, compared to the linear search baseline, our two-stage method achieves 1360× speedup, with nearly no performance loss in recognition accuracy. On average, the search time is 0.035 seconds/query on a database with 20,688 images. To the best of our knowledge, this is the first time that tree-based indexing has been successfully used for ConvNet landmark-based visual place recognition. Furthermore, this is also the first reported work of real-time search performance in visual place recognition using ConvNet landmarks. Our work demonstrates the practicality of ConvNet landmark-based approaches in visual place recognition.

The remainder of this article is organized as follows. Background section briefly reviews the main components of a ConvNet landmark-based place recognition system and tree-based indexing. Proposed methods section presents our proposed methods in detail. Experiments and results section presents the experimental results on five data sets to demonstrate the effectiveness of our methods, and the last section provides the conclusion.

Background

In this section, we briefly review the background research, including ConvNet landmark-based place recognition and HKMeansTree-based indexing. For more detailed description and discussion of relevant techniques, one can refer to the literature.^23,31

ConvNet landmark-based visual place recognition

Assume we are given a query image, I_q, and a set of M database images, $I_{d} = {I_{d_{m}}, m = 1, 2, ..., M}$ . The goal of a visual place recognition system is to find the database image, $I_{d}^{q}$ in I_d, which corresponds to the place where I_q was captured. To solve this problem, a ConvNet landmark-based system makes full use of the power of ConvNet features to match landmarks between images to find $I_{d}^{q}$ . Specifically, such a system consists of the following three major steps:

Step 1: Landmark proposal detection. For each query or database image, N landmarks are first detected. The bounding boxes of detected landmarks of I_q and I_d are denoted as $B_{q} = {B_{q}^{i}} and B_{d} = {B_{d_{m}}^{i}}$ , respectively. Note that $i = 1, 2, ..., N, and m = 1, 2, ..., M$ in this article.

Step 2: ConvNet feature extraction. For each landmark detected in Step 1, one ConvNet feature is then extracted using a CNN. Next, the dimensionality of each extracted ConvNet feature is reduced using an appropriate method. Similar to Step 1, the dimension-reduced ConvNet features of I_q and I_d are denoted as $F_{q} = {F_{q}^{i}} and F_{d} = {F_{d_{m}}^{i}}$ , respectively.

Step 3: Image matching. Finally, based on $(B_{q}, F_{q}) and (B_{d}, F_{d})$ , the database image $I_{d}^{q}$ corresponding to the same place of I_q is searched from I_d. To penalize false positive matches between landmarks that have a similar feature but different bounding box shape, a simple shape filtering strategy is performed during this step. The shape filtering strategy will discard two matched landmarks with significant difference in the weight and height of their bounding boxes.

As already discussed in the introduction, Step 3 is the most time-consuming step. Hence, it is important to develop efficient methods to reduce the search time for a query and make ConvNet landmark-based place recognition practical.

It is worth noting that the search scheme proposed by Süenderhauf et al.²³ is theoretically unable to achieve real-time performance with today’s computing technology. The reason is that it uses bidirectional matching based on a linear NN search to match landmarks. In particular, by using a linear NN search based on the cosine distance, matched landmark pairs are identified with a bidirectional matching scheme. This scheme works as follows: if $F_{d_{m}}^{j}$ is the NN of $F_{q}^{i}, and F_{q}^{i}$ is also the NN of $F_{d_{m}}^{j}$ , then two landmarks corresponding to $F_{q}^{i} and F_{d_{m}}^{j}$ are accepted as a matched landmark pair. Obviously, this bidirectional matching severely limits the search efficiency, though its purpose is to obtain a good matching accuracy. However, our experimental results in Baseline section show that our methods, which directly search with feature indexing instead of bidirectional matching, can achieve comparable recognition accuracy. This finding is important because it demonstrates that existing fast NN search algorithms, such as tree-based indexing as described in this article, can be used to speed up the process while having no performance degradation in recognition accuracy.

HKMeansTree-based indexing

Tree-based indexing for the approximate NN search can be defined as follows. Given a set of n features $D = {X_{1},..., X_{n}} with X_{i} \in ℝ^{d}$ being a d-dimensional feature, we build a tree structure to store these features so that the approximate K-NNs of a query feature X_q can be found in D quickly. In this article, we employ HKMeansTree to implement this tree-based indexing.

HKMeansTree, proposed by the literature,^30,31 is a special case of partitioning trees based on hierarchical k-means clustering. It has been widely used to approximate the NN search, demonstrating better performance than hashing-based methods.^30,31 The HKMeansTree is constructed by recursively partitioning the feature space at each level of a tree into k distinct subspaces (i.e. cluster centers) using k-means clustering. In particular, features are first partitioned into k distinct subspaces to generate the nodes of the first level of the tree. Then the same process is recursively applied to the associated features in each subspace, in order to partition the feature space at the current level into k distinct subspaces. These distinct subspaces form the nodes of the next level of the tree. This recursion continues until the number of features in a subspace is no more than k. To find the NN of a query in HKMeansTree, a depth-first searching procedure is commonly used. In addition, to further improve the search efficiency, priority search based on a priority queue is used. The priority queue, which is dynamically built while the tree is being searched, stores the distances of the unvisited branches of the nodes along the path from the query. Thus, after checking which branch is with the closest cluster center to the query feature at each inner node, only unvisited branches are searched in the order of their distances. In this way, both search speed and accuracy can be improved. Note that the term “branching factor” is used to describe the number of distinct subspaces to use when partitioning the feature space at each level and that a search algorithm often limits the maximum number of leaves to examine, L, in order to constrain the search time.

Proposed methods

In this section, we present our methods to speed up the image matching step in ConvNet landmark-based visual place recognition. We first describe how to construct the HKMeansTree-based index used in our methods and then detail our one-stage and two-stage methods.

Construction of an HKMeansTree-based index

In our methods, HKMeansTree is utilized to construct the search index. Specifically, an HKMeansTree-based index is constructed in an off-line preprocessing phase. First, all dimension-reduced ConvNet features $F_{d_{m}}^{i}$ in F_d are grouped into a set. At the same time, a lookup table is created. The table stores a mapping from each ConvNet feature with its bounding box $B_{d_{m}}^{i}$ and feature vector $F_{d_{m}}^{i}$ to its corresponding database image I_dm. Then the set of all database features is used to build an HKMeansTree. To ensure brevity, we denote the generated lookup table and the constructed HKMeansTree as LUT and HKMT, respectively. In this way, a fast NN search index based on HKMeansTree for the given feature data set F_d can be constructed. In other words, for any given feature $F_{q}^{i}$ from a query image I_q, using LUT, it is easy and fast to find the NN feature $F_{d_{m}}^{i}$ in HKMT and then find the corresponding bounding box $B_{d_{m}}^{i}$ and the image I_dm from which $F_{d_{m}}^{i}$ is extracted.

One-stage method

Our one-stage method performs the NN search only. Note that it uses HKMeansTree to carefully check a relatively large number of leaves in the tree, in order to obtain a satisfactory recognition accuracy. The detailed steps of this method are presented in the following section and in algorithm 1.

Step 1: Searching the K-NNs of the query features using HKMeansTree-based indexing. For each feature $F_{q}^{i}$ of the query image, we search its K-NNs in the database features F_b using the constructed HKMT. The indices and distances to the K-NNs found can be obtained after searching. We denote them as $(idxs, dists) = {(i d x_{i}^{k}, d i s t_{i}^{k}), i = 1, ..., N; k = 1, ..., K}$ . It is worth noting that in our experiments, the best performance in both of the recognition accuracy and the search efficiency was achieved when using K = 1. So we use K = 1for the one-stage method in this article.

Step 2: Voting for the corresponding database images. The following processing is applied recursively to each feature in F_q: (a) for feature $F_{q}^{i}$ , we now have found the index $i d x_{i}^{k}$ of its NN feature $F_{d_{m}}^{i}$ and the distance $d i s t_{i}^{k} between F_{q}^{i} and F_{d_{m}}^{i}$ . According to $i d x_{i}^{k}$ and LUT, we find the corresponding bounding box $B_{d_{m}}^{i} of F_{d_{m}}^{i}$ and its associated image I_dm, (b) we check the difference with respect to the width and height of the bounding boxes of $B_{q}^{i} and B_{d_{m}}^{i}$ . It is only when their widths and heights are both similar that we continue the (c), and (c) the matched landmarks vote for the database image I_dm by $imIDX (m) = imIDX (m) + 1$ . Then we compute the corresponding similarity between the query image and I_dm by $imDIST (m) = imDIST (m) - {dist}_{i}^{k}$ . Note that the threshold to check the difference in the weight and height of two matched bounding boxes, r, is empirically set to 1.3 in our experiments.

Step 3: Finally, we choose the database image with the highest number of votes of matched landmarks as the final match of the query image. In the case of that multiple database images have the highest number of votes of matched landmarks, we select the database image with the maximum similarity as the final match.

Algorithm 1

One-stage method.

Input: B_q, F_q, B_d, HKMT, LUT, L, r, and number of neighbors to search K

Output: $I_{d}^{q}$

Procedure OneStageSearch (B_q, F_q, B_d, HKMT, LUT, L, K, r)

▹ Searching the K-NNs of the query features F_q in HKMT, return the indices and distances to the K-NNs found. Note that they are N × K matrices: $(i d x s, d i s t s) = {(i d x_{i}^{k}, d i s t_{i}^{k}), i = 1, ..., N; k = 1, ..., K}$

1: $(idxs, dists) \leftarrow c a l l$ SearchKNNInHKMeansTree (F_q, HKMT, L, K)

▹ Voting for the corresponding database images

2: imIDX: a 1 × M matrix of zeros used to vote for the indices of database images

3: imDIST: a 1 × M matrix of zeros used to vote for the similarity of database images

4: for i = 1 to N do

5: $w_{q}, h_{q} \leftarrow$ compute the weight and height of $B_{q}^{i}$

6: for k = 1 to K do

7: $idx, dist \leftarrow ({idx}_{i}^{k}, {dist}_{i}^{k})$

8: m ← use idx to find the index of the corresponding database image in LUT

9: n ← use idx to find the index of the corresponding bounding box in LUT

10: $w_{d}, h_{d} \leftarrow$ compute the weight and height of $B_{d_{m}}^{n}$

11: $(w_{min}, w_{max}) \leftarrow$ the minimum and maximum of $(w_{q}, w_{d})$

12: $(h_{min}, h_{max}) \leftarrow$ the minimum and maximum of $(h_{q}, h_{d})$

13: if $w_{max} \leq r \times w_{min}$ and $h_{max} \leq r \times h_{min}$ then

14: $imIDX (m) = imIDX (m) + 1$

15: $imDIST (m) = imDIST (m) - d i s t$

▹ Finding the best match

16: ${imIDX}_{max} \leftarrow f i n d (imIDX = = max (imIDX))$

17: ${imDIST}_{min} \leftarrow max (imDIST ({imIDX}_{max}))$

18: $I_{d}^{q} \leftarrow f i n d (imDIST = = {imDIST}_{min})$

19: return $I_{d}^{q}$

Two-stage method

So far, we have presented the one-stage method. However, as we will show later in the experiments, a relatively large number of leaves, L, in HKMeansTree needs to be checked for recognition accuracy to be satisfactory. This comes at the expense of long search time. To overcome this weakness and further improve the search speed, we extend the one-stage method into a coarse-to-fine, two-stage search method. Specifically, it consists of the following steps, some of which are shared with the one-stage method. To avoid redundancy, we will not repeat the shared steps and describe only the difference.

In the coarse stage of this method, we apply the one-stage method in a coarse step to find the top-N candidate database images, which have a high probability of containing at least one ground truth database image. By coarse, we mean that only a small number of leaves in the HKMeansTree are checked to optimize for efficiency.

Step 1: Searching K-NNs of the query features using HKMeansTree-based indexing. This step is the same as step 1 in the one-stage method but with two different parameters: (a) we use K = 5 and (b) we set L to a lower value so that we examine only a small number of leaves.

Step 2: Voting for the corresponding database images. This step is exactly the same as step 2 of the one-stage method. After finishing this step, we can obtain the voting result imIDX, which stores the number of matched landmarks between the query image and the database images.

Step 3: Selecting the top-N candidate database images. We first sort imIDX in descending order and then take its top-N as the candidate database images. Similar to the step 3 of the one-stage method, we select the database image with the larger similarity when multiple database images have the same number of votes of matched landmarks.

In the fine stage of this method, we perform an exact search to determine the final match of the query image among the top-N candidate images obtained in the coarse stage. In this article, we implement the fast exact search in Hamming space. Specifically, the query feature is first encoded into a binary code using the same hash function that encodes the database features to codes. Then we find the NN of the query feature by computing the Hamming distance between the query code to all the database codes. Finally, with the computed Hamming distance, we use a linear search to find the NN of the query. Using hash code, the linear search can be performed efficiently. The fine stage is detailed as follows.

Step 4: Searching the 1 − NN of the query features using a fast exact search in Hamming space. The purpose of this step is the same as that of step 1 of the one-stage method. However, we find the 1 − NN of the features using the fast exact search in Hamming space, instead of using HKMeansTree-based indexing. For each feature of the query image, we search its 1 − NN in the database features, which come from the top-N candidate database images obtained in the coarse stage.

Step 5: Voting for the corresponding database images. This step is exactly the same as step 2 of the one-stage method.

Step 6: Finding the best match. This step is also exactly the same as step 3 of the one-stage method.

As we will show in the following section, compared to the one-stage method, the two-stage method can not only further speed up recognition but also improve search accuracy.

Experiments and results

Experimental setup

Data sets

In order to evaluate the effectiveness of our proposed methods under different conditions, we ran experiments on five data sets that exhibit typical changes present in real-world place recognition applications. From the summary of their main characteristics listed in Table 1, we can divide these data sets into three categories of changes. The first three data sets present different kinds of significant appearance change but without viewpoint variation, the fourth data set mainly exhibits large viewpoint change, and the fifth data set covers both aforementioned categories of changes. Figure 1 shows the sample images of each data set.

The UACampus³² data set was collected with a Husky A200 mobile robot on the campus of the University of Alberta, Canada. The robot was equipped with a forward-facing camera (ASUS Xtion PRO LIVE), which was configured to acquire the images of 640 × 480 pixels at 30 Hz. In order to create illumination variation, the robot was driven through the same route (about 650 m) at five different times of the day (between 06:20 and 22:15). In our experiments, we used two subsets that exhibit the greatest relative illumination change, that is, two subsets at 06:20 and 22:15. Their images are manually matched to generate the ground truth.

The Carnegie Mellon University (CMU)³³ data set was collected with a vehicle made by CMU in Pittsburgh, PA, USA. The vehicle, which had a pair of Point Grey Flea 2 cameras mounted on the left and right sides, was driven along an 8.8-km route. The cameras were set to collect the images of 256 × 192 pixels at 15 Hz. In our experiments, all images were resized to 640 × 480 pixels. The same route was traversed 16 times under varying environmental and climatological conditions over the course of a year. To evaluate the performance in the case of seasonal change, we used two subsets in our experiments. Those subsets were collected in the spring and the winter. The spring subset was obtained on April 4, 2011, which was a cloudy day. The winter subset was obtained on February 2, 2011, when there was light snow fall and some snow was on ground. We used only the images captured by the left camera when the vehicle was moving. The ground truth was created with Global Positioning System (GPS). Two images within 10 m are considered to be the same place.

The St Lucia³⁴ data set was collected using a car in the Brisbane suburb of St Lucia, Australia. A forward-facing web camera (Logitech QuickCam Pro 9000) was mounted on the car, with 640 × 480 pixel resolution at 15 Hz. In order to capture the difference in appearance between early morning and late afternoon, the route was traversed at five different times during 2 days over 3 weeks, for a total of 10 subsets. We used two subsets that exhibit the greatest relative appearance changes caused by illumination and shadow, that is, two subsets at 08:45 and 15:45 on September 9, 2010. In our experiments, we use 10,000 images uniformly sampled from the subsets. The ground truth was created with GPS. Two images within 20 m are considered to be the same place.

The Mapillary data set was downloaded from Mapillary,³⁵ which is a service similar to Google Street View. A number of driver users share their geotagged photos captured when driving along a road. Usually, many roads would be traversed by more than one user under different environmental conditions. More importantly, these revisits do not drive accurately along the same wheel ruts. For example, they may drive in different lanes. We specifically downloaded 2028 image pairs with different viewpoints across several countries in Europe. Therefore, this data set exhibits a significant viewpoint change as well as some appearance changes due to variations in the weather. All images were resized to 640 × 480 pixels in our experiments. A GPS reading is attached in each image, but each reading is quite inaccurate. Therefore, we first use the coarse GPS readings to create the initial ground truth and then refine the initial ground truth manually to make it accurate.

The FullSet is a combination of the above four data sets. Its main purpose is to evaluate the search efficiency on a bigger data set containing tens of thousands of images.

Table 1.

Summary of the main characteristics of five data sets used in our experiments.^a

Data set	Subset	No.	Main changes
UACampus³²	06:20 and 22:15	649 and 647	Large illumination
CMU³³	Spring and Winter	9955 and 8013	Large seasonal + moderate illumination
St Lucia³⁴	08:45 and 15:45	10,000 and 10,000	Moderate illumination + large shadows
Mapillary	mploop1 and mploop2	2028 and 2028	Large viewpoint + moderate illumination
FullSet	fsloop1 and fsloop2	22,632 and 20,688	Combination of the above all

^a“No.” indicates the number of images in a subset. For each data set, two subsets with extreme changes are listed below and will be matched in our experiments. CMU: Carnegie Mellon University.

Implementation details

In all experiments, we followed the method used by Süenderhauf et al.²³ to perform the first two steps (as described in ConvNet landmark-based visual place recognition section) of ConvNet landmark-based place recognition. In the first step, we detected 100 landmarks per image using EdgeBoxes,³⁶ which is a popular object proposal method in object detection application. EdgeBoxes has demonstrated the outstanding repeatability under different imaging conditions (e.g. illumination, rotation, scaling, and so on).³⁷ Thanks to its good repeatability, impressive recognition accuracy in the presence of severe environmental changes has been achieved in the work by Süenderhauf et al.²³

In the second step, we extracted one ConvNet feature for each landmark from a pretrained CNN known as AlexNet.²² Note that, unlike the method by Süenderhauf et al.,²³ we extracted features from the pool5 layer instead of the conv3 layer. As we know, the pool5 layer has more pooling operations than the conv3 layer, and the pooling operation is commonly used to achieve better invariance to image transformations. Therefore, it is reasonable to believe that the features from the pool5 layer are better at handling the localization errors of detected landmarks than those features from the conv3 layer, and that this superiority of the pool5 layer will bring better recognition accuracy in ConvNet landmark-based place recognition. Actually, this point has been confirmed by our experimental evaluation, though we will not show the results of this evaluation in this article because it is beyond the scope of this article. The dimensionality of extracted ConvNet features was then reduced. Except that in the second stage of the two-stage method, the ConvNet features were encoded as 1024-bit hash binary codes using locality-sensitive hashing (LSH).³⁸ In all other cases, the ConvNet features were reduced to 1024 using Gaussian random projection (GRP).^39,40 Note that the LSH employed in this article is very naive because it is simply based on random unit-norm projections followed by signed binarization. Better hash codes, which may bring higher recognition accuracy and/or faster search, could be obtained by applying more sophisticated hashing methods.

For HKMeansTree, we used the publicly available implementation in the FLANN library (http://www.cs.ubc.ca/research/flann/). To compute the Hamming distance of hash binary codes, we used the open-source code of Yael (http://yael.gforge.inria.fr/). All experiments in this article were conducted on a desktop PC with eight cores of CPU@4.00 GHz, 32 GB random-access memory (RAM) memory. We used the maximum number (16) of physical threads for parallelization. Streaming SIMD Extensions 4 (SSE4) instructions were used to accelerate the computation of the Hamming distance.

Evaluation protocols

For each data set in Table 1, we consider the first subset as the query set and use the second subset as the database set. For example, in the UACampus data set, the subset collected at 06:20 is the query set and the subset collected at 22:15 is the database set. Each image in the query set is required to find its similar image that is likely to correspond to the same place in the database set. The ground truth is used to determine the correctness. We use two metrics to evaluate the performance in terms of recognition accuracy and search efficiency: (a) the Precision–Recall curve is commonly used as a standard criterion for assessing recognition accuracy in the visual place recognition community¹; and (b) search time for per query is used to measure search efficiency. Note that the search time reported in this article is an average time for searching all query images of a data set.

Baseline

As described previously, our aim is to speed up the image matching step in ConvNet landmark-based visual place recognition, ideally without losing original recognition accuracy. Consequently, we need to establish the baseline of recognition accuracy in the first place. The method proposed by Süenderhauf et al.²³ is the latest representative of ConvNet landmark-based approaches. It has shown state-of-the-art recognition accuracy, so we have implemented it and run it on our data sets to produce the precision–recall curves. We consider those precision–recall curves produced by the method of Süenderhauf et al.²³ as the baseline of recognition accuracy. For the sake of convenience, we denote these curves as Baseline-Accuracy. It is expected that our proposed methods could achieve real-time search performance under an important condition, that is, keeping almost the same recognition accuracy as Baseline-Accuracy.

To validate whether this condition could be satisfied, we compare the recognition accuracy of Linear-GRP with Baseline-Accuracy. Note that the results of Linear-GRP are actually produced by our one-stage method with a linear NN search, instead of HKMeansTree-based indexing. Theoretically, Linear-GRP shows the best recognition accuracy that could be achieved by our proposed methods when using HKMeansTree-based indexing. Results on four data sets are shown in Figure 2. Compared to Baseline-Accuracy, Linear-GRP shows almost the same recognition accuracy in environments without viewpoint change (as shown in Figure 2(a) to (c)) and better accuracy in environments with large viewpoint change (as shown in Figure 2(d)). This confirms that it is possible to satisfy the important condition on performance.

Figure 2.

Comparison in terms of place recognition accuracy between the state-of-the-art method by Süenderhauf et al.²³ (denoted as “Baseline-Accuracy”) and our one-stage method with a linear NN search (denoted as “Linear-GRP”). (a) UACampus. (b) CMU. (c) St Lucia. (d) Mapillary. CMU: Carnegie Mellon University.

It is worth noting that we use Linear-GRP instead of Baseline-Accuracy as the baseline in terms of recognition accuracy and search efficiency in the following experiments. Two reasons for this are (a) the place recognition accuracy of Linear-GRP is almost the same as that of Baseline-Accuracy and (b) more importantly, Linear-GRP is more fair than Baseline-Accuracy when comparing search efficiency with our proposed methods. Because we implement the method by Süenderhauf et al.²³ in MATLAB without optimization, however, we produce the results of Linear-GRP using the fast-linear search implementation in the FLANN library.

Results and summaries

The results with respect to place recognition accuracy are shown in Figure 4, and the corresponding search times are listed in Table 2. It is known that HKMeansTree has a set of adjustable parameters that have a significant influence on search performance. Naturally, there is a trade-off between place recognition accuracy and search efficiency in our proposed methods. Therefore, we first give the parameter selection in the experiments before discussing the results.

Table 2.

Comparison of search times (seconds/query).^a

Data set	UACampus	Mapillary	CMU	St Lucia	FullSet
Number of images	647	2028	8013	10,000	20,688
Linear GRP	0.885	3.017	15.079	21.046	47.593
HKMeansTree-L64	0.006 148×	0.009 335×	0.012 1257×	0.012 1754×	0.012 3966×
HKMeansTree-L1000	0.041 22×	0.070 43×	0.124 122×	0.086 245×	0.075 635×
HKMeansTree-L64-Linear-LSH
HKMeansTree-L64	0.014	0.014	0.021	0.020	0.021
Linear-LSH	0.014	0.013	0.014	0.014	0.014
Total	0.028 32×	0.027 112×	0.035 431×	0.034 619×	0.035 1360×

^a“Number of images” means the number of database images in a data set. “×” denotes the speedup of a method over the linear search baseline of Linear GRP. CMU: Carnegie Mellon University.

Tuning parameters

Since our aim is to achieve real-time search performance while keeping the original recognition accuracy, we carefully tuned the parameters following a rule: increasing parameters that contribute to improving search accuracy until the recognition accuracy is close to that of the baseline linear GRP. The final parameters that were used to produce the results in Figure 4 are summarized below. We ran all experiments using the same parameters across all data sets.

When constructing an HKMeansTree, the branching factor was 64 and the maximum number of iterations for the k-means clustering was 30.

When searching a constructed HKMeansTree, the search performance in accuracy and efficiency mainly depends on the maximum number of leaves to examine L. A higher L would bring better search accuracy but also take more time. For our one-stage method, L was gradually increased from 64 to 1000. When L = 1000, the recognition accuracy was close to the baseline. In Figure 4, we show the precision–recall curves of using L = 64 and L = 1000, which are, respectively, named HKMeansTree-L64 and HKMeansTree-L1000. For the first stage of our two-stage method, we used L = 64. The precision–recall curves produced by our two-stage method, shown in Figure 4, are named HKMeansTree-L64-Linear-LSH.

In the first stage of our two-stage method, we need to determine the number of ranked database images used in finding the final match in the second stage. To find an appropriate N, we calculated the recall curve at various values of N, which is a common measure for evaluating the performance of an image retrieval system. In our case, recall is defined as the proportion of query images for which its ground truth database image is ranked in the top N positions of ranked database images. This measure is commonly denoted as Recall@Top-N. We plotted this Recall@Top-N curve of HKMeansTree-L64 on each data set in Figure 3. It clearly shows that the recalls on all data sets are stable at the highest level when N = 200. Therefore, we used N = 200 of ranked database images as the candidates of the experiments.

Figure 3.

Recall@Top-N of HKMeansTree-L64 in the first stage of our two-stage method. (a) UACampus. (b) CMU. (c) St Lucia. (d) Mapillary. (e) FullSet. CMU: Carnegie Mellon University.

Comparison and summaries

From Figure 4 and Table 2, we can arrive at some conclusions, as summarized below.

Comparison of HKMeansTree-L64/L1000 in the one-stage method clearly shows the effect of increasing the number of leaves to examine L on the search performance. That is, a higher L gives better search accuracy but takes more search time. In particular, the search speed of L = 64 is extremely fast, but its recognition accuracy is much worse than that of L = 1000. In contrast, HKMeansTree-L1000 achieves expected recognition accuracy that is quite close to that of the baseline Linear-GRP. Its search time on the FullSet data set is as little as 0.075 seconds/query.

Compared to the one-stage method, our two-stage method, HKMeansTree-L64-Linear-LSH, achieves better recognition accuracy that is nearly the same as that of the baseline. Furthermore, the two-stage method is faster than the one-stage method of HKMeansTree-L1000, with an average search time of 0.035 seconds/query on the FullSet data set. Note that this average search time is 1360× speedup over a linear search baseline. The total search time per query of the two-stage method consists of two parts: to search the HKMeansTree and to perform the fast-linear search in Hamming space. The second part is a constant, which in our experiments is only about 0.014 s when using top-200. Note that the Hamming distance was computed by the code of Yael using a single thread. Theoretically, the second part of the time can be further optimized by applying a multithread processing. The first part of the time is a fraction of the one-stage method of HKMeansTree-L1000. For example, compared to HKMeansTree-L1000, the first part of two-stage has 3.6× speed improvement on the FullSet data set. While the 3.6× improvement might seem a small improvement, for real-time applications it will still be significant.

In summary, both of our proposed methods have achieved real-time search performance on all data sets used in our experiments. From the above comparison, our two-stage method is not only more accurate but also faster than our one-stage method.

Figure 4.

Comparison in terms of place recognition accuracy. Best viewed in color. (a) UACampus. (b) CMU. (c) St Lucia. (d) Mapillary. (e) FullSet. CMU: Carnegie Mellon University.

Discussion

We discuss the limitations of our methods in this section. As we have shown, compared to the one-stage method, our two-stage method is superior in both place recognition accuracy and search efficiency. However, the two-stage method also has its deficiencies. First, it needs more storage space for saving the hash codes of the ConvNet features, although these hash codes are binary and very compact. Second, for reducing Input/Output access time, the hash codes are usually loaded into the memory (RAM). As a result, the two-stage method consumes more memory than the one-stage method. Therefore, one should choose one method or the other depending on the specific application scenario. Generally, we suggest that the one-stage method may be preferable in an environment of moderate size, while the two-stage method may be better when the size of an environment becomes large.

Another limitation of our proposed methods is due to the need to perform hierarchical k-means clustering to construct the search tree. While this is not an issue in applications such as place recognition or robot localization in a fixed environment, for other applications that involve an environment that grows over time, the time complexity of hierarchical k-means clustering prevents our methods from being real time.

Conclusion

In this article, we have proposed two methods, that is, the one-stage method and the two-stage method, to speed up the visual place recognition using ConvNet landmarks. We exploit the efficiency of tree-based indexing to achieve the speedup. The one-stage method applies tree-based indexing and uses the top-ranked image as the result of the recognition system. The two-stage method performs a coarse-to-fine search scheme. Specifically, the top N candidate images are first retrieved using the one-stage method in a coarse step and then the final winning match of the query image is found with a fast-linear search in Hamming space. Extensive experiments were conducted on five data sets with various environmental changes, and our methods achieved real-time search speed, with only negligible loss in the place recognition accuracy. Compared to the one-stage method, we found the two-stage method to be not only more accurate but also faster. For the largest data set with 20,688 database images, our two-stage method achieved 1360× speedup over a linear search baseline, with an average search time of 0.035 seconds/query. We believe this work has made ConvNet landmarks-based approaches to be more practical in visual place recognition.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship and/or publication of this article: The authors gratefully acknowledge the support from the Hunan Provincial Innovation Foundation for Postgraduate (CX2014B021), the Hunan Provincial Natural Science Foundation of China (2015JJ3018), and the Fund of Innovation of NUDT Graduate School (B140406). This research is also supported in part by the Program of Foshan Innovation Team (grant no. 2015IT100072) and by NSFC (grant no. 61673125).

References

Lowry

Süenderhauf

Newman

. Visual place recognition: a survey. IEEE Trans Robot 2016; 32(1): 1–19.

Garcia-Fidalgo

Ortiz

. Vision-based topological mapping and localization methods: a survey. Robot Auton Syst 2015; 64: 1–20.

Kosecka

. Vision based topological markov localization. In: IEEE international conference on robotics and automation (ICRA), Vol. 2, New Orleans, LA, USA, 26 April–1 May 2004, pp. 1481–1486. IEEE.

Kosecka

. Probabilistic location recognition using reduced feature set. In: IEEE international conference on robotics and automation (ICRA), Orlando, Florida, USA, 15–19 May 2006, pp. 3405–3410. IEEE.

Cummins

Newman

. FAB-MAP: probabilistic localization and mapping in the space of appearance. Int J Robot Res 2008; 27(6): 647–665.

Zhang

. BoRF: loop-closure detection with scale invariant visual features. In: IEEE international conference on robotics and automation (ICRA), Shanghai, China, 9–13 May 2011, pp. 3125–3130. IEEE.

Singh

Kosecka

. Visual loop closing using gist descriptors in manhattan world. In: IEEE international conference on robotics and automation (ICRA) omnidirectional robot vision workshop, Anchorage, Alaska, USA, 3–7 May 2010. IEEE.

Süenderhauf

Protzel

. BRIEF-Gist – closing the loop by simple means. In: IEEE/RSJ international conference on intelligent robots and systems (IROS), San Francisco, CA, USA, 25–30 September 2011, pp. 1234–1241. IEEE.

Liu

Zhang

. Visual loop closure detection with a compact image descriptor. In: IEEE/RSJ international conference on intelligent robots and systems (IROS), Vilamoura, Portugal, 7 October 2012, pp. 1051–1056. IEEE.

10.

Milford

Wyeth

. SeqSLAM: visual routebased navigation for sunny summer days and stormywinter nights. In: 2012 IEEE international conference on robotics and automation (ICRA), St Paul, MN, USA, 14–18 May 2012, pp. 1643–1649. IEEE.

11.

Liu

Zhang

. Towards improving the efficiency of sequence-based SLAM. In: IEEE international conference on mechatronics and automation (ICMA), Takamatsu, Kagawa, Japan, 4–7 August 2013, pp. 1261–1266. IEEE.

12.

Milford

. Vision-based place recognition: how low can you go? Int J Robot Res 2013; 32(7): 766–789.

13.

Pepperell

Corke

Milford

. All-environment visual place recognition with SMART. In: IEEE international conference on robotics and automation (ICRA), Hong Kong, China, 31 May –7 Jun 2014, pp. 1612–1618. IEEE.

14.

Naseer

Spinello

Burgard

. Robust visual robot localization across seasons using network flows. In: The AAAI conference on artificial intelligence, Québec, Canada, 27 July 2014, AAAI Press.

15.

Lowe

. Distinctive image features from scale-invariant keypoints. Int J Comput Vis 2004; 60: 91–110.

16.

Bay

Tuytelaars

Van Gool

. SURF: speeded up robust features. In: Computer vision-ECCV, Vol. 3951, Graz, Austria, 7–13 May 2006, pp. 404–417. Springer.

17.

Oliva

Torralba

. Modeling the shape of the scene: a holistic representation of the spatial envelope. Int J Comput Vis 2001; 42(3): 145–175.

18.

Dalal

Triggs

. Histograms of oriented gradients for human detection. In: International conference on computer vision and pattern recognition (CVPR), San Diego, CA, USA, 17–21 October 2005, pp. 886–893. IEEE.

19.

Hou

Zhang

Zhou

. Convolutional neural network-based image representation for visual loop closure detection. In: IEEE international conference on information and automation (ICIA), Lijiang, Yunnan, China, 8–10 August 2015, pp. 2238–2245. IEEE.

20.

Süenderhauf

Dayoub

Shirazi

. On the performance of convnet features for place recognition, In: IEEE/RSJ international conference on intelligent robots and systems (IROS), Hamburg, Germany, 28 September – 02 October 2015. IEEE.

21.

Tai

Liu

. A deep-network solution towards model-less obstacle avoidance: IEEE/RSJ international conference on intelligent robots and systems (IROS), Daejeon, Korea, 9–14 October 2016, pp. 2759–2764. IEEE.

22.

Krizhevsky

Sutskever

Hinton

. ImageNet classification with deep convolutional neural networks. In: Advances in neural information processing systems (NIPS), Lake Tahoe, Nevada, USA, 3–8 December 2012, pp. 1097–1105. NIPS.

23.

Süenderhauf

Shirazi

Jacobson

. Place recognition with convnet landmarks: viewpoint-robust, condition-robust, training-free. In: Robotics: science and systems (RSS), Rome, Italy, 17 July 2015.

24.

McManus

Upcroft

Newman

. Scene signatures: localised and point-less features for localisation. In: Robotics science and systems (RSS), Berkeley, CA, USA, 12–16 July 2014.

25.

Yanagihara

Ando

Chokushi

. An experimental study of the effects of landmark discovery and retrieval on visual place recognition across seasons. In: Workshop on visual place recognition in changing environments at the IEEE international conference on robotics and automation, Seattle, Washington, USA, 26–30 May 2015. IEEE.

26.

Silpa-Anan

Hartley

. Optimised KD-trees for fast image descriptor matching. In: IEEE conference on computer vision and pattern recognition, (CVPR), Anchorage, Alaska, USA, 23–28 June 2008, pp. 1–8. IEEE.

27.

Jia

Wang

Zeng

. Optimizing KD-trees for scalable visual descriptor indexing. In: IEEE conference on computer vision and pattern recognition (CVPR), San Francisco, California, USA, 13–18 June 2010, pp. 3392–3399. IEEE.

28.

Obdrzalek

Jiri

. Sub-linear indexing for large scale object recognition. In: BMVC, Oxford, UK, 5–8 September 2005, pp. 1–10. BMVA Press.

29.

Liu

Zhang

. Indexing visual features: realtime loop closure detection using a tree structure. In: IEEE international conference on robotics and automation (ICRA), St Paul, MN, USA, 14–18 May 2012, pp. 3613–3618. IEEE.

30.

Muja

Lowe

. Fast approximate nearest neighbors with automatic algorithm configuration. In: International conference on computer vision theory and application, Lisbon, Portugal, 5–8 February 2009, pp. 331–340. Springer.

31.

Muja

Lowe

. Scalable nearest neighbor algorithms for high dimensional data. IEEE Trans Pattern Anal Mach Intell 2014; 36(11): 2227–2240.

32.

Liu

Feng

Zhang

. Keypoint matching by outlier pruning with consensus constraint. In: IEEE international conference on robotics and automation (ICRA), Seattle, Washington, USA, 26–30 May 2015, pp. 5481–5486. IEEE.

33.

Hernan

Daniel

Takeo

. The CMU visual localization data set. http://3dvis.ri.cmu.edu/datasets/localization (2011, accessed 15 May 2016).

34.

Glover

Maddern

Milford

. FAB-MAP + RatSLAM: appearance-based SLAM for multiple times of day. In: IEEE international conference on robotics and automation (ICRA), Anchorage, Alaska, USA, 3–7 May 2010, pp. 3507–3512. IEEE.

35.

Mapillary. https://www.mapillary.com (accessed 15 May 2016).

36.

Zitnick

Dollár

. Edge boxes: locating object proposals from edges. In: Computer vision-ECCV, Zurich, Switzerland, 6–12 September 2014, pp. 391–405, Springer.

37.

Hosang

Benenson

Dollár

. What makes for effective detection proposals? IEEE Trans Pattern Anal Mach Intell 2015, p. 1.

38.

Gionis

Indyk

Motwani

. Similarity search in high dimensions via hashing: International conference on very large data bases, San Francisco, CA, USA, 07–10 September 1999, pp. 518–529. Morgan Kaufmann Publishers Inc.

39.

Dasgupta

. Experiments with random projection. In: Conference on uncertainty in artificial intelligence, San Francisco, CA, USA, 30 June – 03 July 2000, pp. 143–151. Morgan Kaufmann Publishers Inc.

40.

Bingham

Mannila

. Random projection in dimensionality reduction: applications to image and text data. In: ACM SIGKDD international conference on knowledge discovery and data mining, San Francisco, California, 26–29 August 2001, pp. 245–250. New York, NY: ACM.