Fast loop-closure detection using visual-word-vectors from image sequences

Abstract

In this paper, a novel pipeline for loop-closure detection is proposed. We base our work on a bag of binary feature words and we produce a description vector capable of characterizing a physical scene as a whole. Instead of relying on single camera measurements, the robot’s trajectory is dynamically segmented into image sequences according to its content. The visual word occurrences from each sequence are then combined to create sequence-visual-word-vectors and provide additional information to the matching functionality. In this way, scenes with considerable visual differences are firstly discarded, while the respective image-to-image associations are provided subsequently. With the purpose of further enhancing the system’s performance, a novel temporal consistency filter (trained offline) is also introduced to advance matches that persist over time. Evaluation results prove that the presented method compares favorably with other state-of-the-art techniques, while our algorithm is tested on a tablet device, verifying the computational efficiency of the approach.

Keywords

Loop-closure detection image sequences visual SLAM mobile robotics low-power embedded systems

1. Introduction

The problem of visual place recognition (vPR) refers to the ability of a system to recognize a scene based on visual sensing; it has been used during the last decade to address many challenges in mobile robotics. As part of a simultaneous localization and mapping (SLAM) system, vPR has been applied in a variety of forms and alterations, such as the loop-closure detection (LCD) and the relocalization procedures. An LCD engine is responsible for detecting revisited trajectory regions and creating additional edge constraints between the current and earlier pose nodes on graph-based SLAM systems (Folkesson and Christensen, 2004; Grisetti et al., 2010; Thrun and Montemerlo, 2006). Those additional edge constraints provide supplementary information regarding the measurements’ arrangement in the 3D space, and they can be used to further improve the SLAM output in an online or post-processing manner (Latif et al., 2013; Mei et al., 2009; Mur-Artal et al., 2015; Strasdat et al., 2010). Moreover, a relocalization system utilizes the visual information to recover the robot’s position in an already known environment (the problem of a kidnapped robot) or in localization-failure scenarios (Konolige et al., 2010; Mur-Artal and Tards, 2014; Wolf et al., 2005). Even though these challenges refer to different applications, they share the same basic functionality of identifying a previously visited scene and thus can be addressed by common solutions.

During the past decade, a plethora of vPR techniques has been presented in the literature. Williams et al. (2009) distinguishes the approaches into three main categories with respect to the type of data they associate. In the first category, referred to as “map-to-map”, correspondences are found between features, taking into account both their appearance and their relative location inside the world. Furthermore, “image-to-map” methods aim to recognize places by associating features between the latest acquired frame and a retained spatial representation of the already-seen world. Finally, “image-to-image” matching approaches (or appearance-based techniques) detect correspondences between the images themselves and present better scaling capabilities in long-trajectory cases.

The most common approach for addressing appearance-based LCD tasks refers to the characterization of each individual frame by an aggregation of local image descriptors. As the robot moves, revisited places are detected by measuring content similarities between the current input frame (query) and all the previous ones (database). To provide efficiency in the implementation, the bag of visual words (BoVW) model can be utilized as a means of quantizing the extracted descriptors’ space. In the general case, every input frame is assigned with one image-visual-word-vector (I-VWV). The entries of this vector correspond to a weighted frequency of occurrence for every visual word in the given image (histogram). The created I-VWVs are treated as image descriptors, thus loop-closing pairs of camera poses are recognized by calculating similarity metrics between them. The aforementioned approach was initially inspired by image-retrieval techniques (Sivic and Zisserman, 2003), yet in some vPR algorithms, measurements obtained from close-in-time instances are summed to enhance the results. Finally, it has been proven that the representation of the created BoVW with a tree structure (vocabulary tree) significantly improves the computational efficiency (Nister and Stewenius, 2006).

In this work, we present an improved pipeline for appearance-based LCD, which combines the visual information from multiple frames to describe a physical scene as a total. As the robot moves, the input camera stream is dynamically segmented into intervals (image sequences), based on the scene’s content variations. For each image sequence, the extracted feature descriptors are converted into visual words and combined to produce one global sequence-visual-word-vector (S-VWV) as well as the individual I-VWVs. Thus, the revisited trajectory regions are detected on a first level by measuring the similarities between all S-VWVs in the database, while the loop-closing frames are determined using the individual I-VWVs only for the associated sequences’ image-members. A typical example of the aforementioned procedure is illustrated in Figure 1. Note that, henceforth, the term “sequence” will refer to “sequence of images,” for brevity.

The main contributions of the paper in hand can be summarized as follows:

Using a description vector capable of characterizing an image sequence as a whole, our method provides more information to the matching functionality advancing the LCD performance. Additionally, since our pipeline relies on such a descriptor, rather than accumulating the similarities between multiple I-VWVs, the system’s performance is not restricted by a per-frame perception of the environment.

With the view of further enhancing the produced sequence similarity measurements, our algorithm introduces a temporal consistency filter over the similarity matrix entries. The corresponding kernel’s coefficients are calculated using a cost-function minimization scheme on a set of training samples.

The proposed methodology entails a reduced computational complexity, as compared with other vPR techniques, since our first level of sequence-to-sequence matching excludes the trajectory regions that are absolutely different in the general view. In addition, the nature of our pipeline provides an efficient way to further reduce the visual word votes by considering only the entries that persist during the sequence formulation. An implementation of the proposed algorithm is tested on a mobile device utilizing the parallel execution capabilities of the ARM-NEON coprocessor and proving its ability to run in real time (in the sense of processing the input faster or in equal time with the execution frequency of a modern key-frame SLAM system), even for a less powerful machine.

A preliminary version of the presented work was presented in Bampis et al. (2016). In this paper, we advance the system’s performance by adopting a rotation- and scale-invariant local feature descriptor and a dynamic sequence identification technique, while, additionally, we address the temporal consistency filtering as a classification problem operating on the sequence similarity scores. Furthermore, we provide a complete justification of the benefits offered by a unified visual-word-vector and extend our experiments to fully evaluate the performance of our algorithm. Finally, extensive comparative results are presented against other state-of-the-art sequence-based vPR techniques, proving the capabilities of the S-VWV based description.

The following section contains a discussion of related work on the field of vPR and subsequently introduces the advantageous matching properties of the introduced S-VWVs. Section 3 describes in detail our online pipeline, together with the preprocessing steps for the vocabulary tree formulation and filter training. In Section 4, our experimental evaluation and comparative results against other state-of-the-art approaches are presented. The computational benefits of the proposed approach, together with the employed parallelization techniques and implementation details of the tested mobile device application, are summarized and assessed in Section 5. Finally, Section 6 draws our final conclusions by describing our algorithm’s potentials and contributions.

2. From image to sequence description

In this section, we discuss some of the most representative techniques in the field of appearance-based vPR with the aim of leading our reader to the comprehension of the proposed sequence description method. For an extended survey of vPR, the reader can refer to the work of Lowry et al. (2016).

2.1. Single-image-based visual place recognition

Probably the most acknowledged method in the field of vPR is FAB-MAP (Cummins and Newman, 2008). According to that method, co-currency probabilities between observed visual words are used to perform appearance-based vPR. Although FAB-MAP constitutes the foundation of a plethora of later methodologies, it suffers in terms of performance, when repetitive patterns are accounted (Piniés et al., 2010), and execution time, owing to the expensive extraction and matching of SURF features (Bay et al., 2006). In a later work, the same authors introduced an improved sparse approximation of their original technique, called FAB-MAP 2.0 (Cummins and Newman, 2011), allowing their system to scale by more than two orders of magnitude. Another representative approach was proposed by Angeli et al. (2008), where the description relied on two visual vocabularies (one from SIFT descriptors (Lowe, 2004) and another from local color histograms). Using a Bayesian filter, the detection was enhanced, taking into account the matching probability of previously obtained measurements. Schindler et al. (2007) provided a more sophisticated representation of the visual vocabulary, with a tree structure addressing city-scale vPR challenges. In their work, the Greedy N-Best Paths algorithm was used so as to cluster the feature descriptors incrementally.

More recent techniques have deviated from the aforementioned probabilistic approach of detecting loop-closures with floating-point descriptors, like SIFT or SURF, offering faster but still competitive results (Gálvez-Lpez and Tards, 2012; Khan and Wollherr, 2015; Mur-Artal and Tards, 2014). More specifically, visual words from binary features, found in every camera measurement, are used to create I-VWVs. Thus, the detection of revisited places is achieved by obtaining similarity metrics, based on the L1/L2 norm, between the individual I-VWVs. Gálvez-Lpez and Tards (2012) proposed a typical technique for this approach with the DBoW2 algorithm. Since in their case the Bayesian filtering was not included, the matching candidates were forced to follow a temporal consistency constraint. Mur-Artal and Tards (2014) enforced DBoW2 by exploring the usage of a more sophisticated binary descriptor (“Oriented FAST and Rotated BRIEF”, or “ORB” (Rublee et al., 2011)) and provided a real-time vPR, relocalization, and LCD system.

Additionally, since the offline formulation of a visual vocabulary is not suitable for every application, some researchers have suggested the online development of a BoVW by estimating an average representation of repetitive descriptors. For instance, Labbé and Michaud (2013) proposed the formulation of an online vocabulary based on a randomized forest of k-d-trees, achieving exquisite performance for large-scale environments. Although their technique is capable of recognizing revisited places in constant time, independently of the traversed trajectory’s length, the computationally expensive SURF feature extraction and the constant updates of their vocabulary render the approach less appealing for normal scale scenarios (such as 20k–30k input frames). Aiming for an immediate reduction of the execution time, Khan and Wollherr (2015) proposed the online creation of a binary vocabulary based on the insertion of new visual words whenever an unfamiliar descriptor is obtained. Since their method (“Incremental Bag of Binary Words for Appearance-Based Loop-Closure Detection” or “IBuILD”) utilizes efficient binary operations, it constitutes a more attractive solution in terms of computational complexity.

Recently, the concept of sequence-to-sequence matching has also been introduced in the literature. Newman et al. (2006), in their work for outdoor SLAM applications, pointed out the advantages of matching sequences instead of individual frames using an accumulative version of similarity matrices. The same notion appears (even on some abstract level) in other techniques as well (e.g. Gálvez-Lpez and Tards, 2012; Mur-Artal and Tards, 2014) proving that LCD performance can be strengthened when visual information from more than one camera measurements is considered. Even though these techniques aim to take advantage of the additional information from the entire scene, they treat each sequence as an aggregation of image description vectors rather than visual words, subjecting their matching procedure to a per-frame view of the environment (visual words are redundantly clustered by camera measurements). On the contrary, our method reformulates the process of creating visual-word-vectors and considers the whole sequence as a single “super-frame”. This approach offers invariance to the visual words’ distribution over the camera measurements, and will be further analyzed in the following subsection.

Finally, sequence-based techniques have been reported, addressing the vPR task under extreme environmental changes originated from different lighting conditions (day and night) or year seasons (Arroyo et al., 2015; Milford and Wyeth, 2012). Even though the choice of more traditional local feature descriptors is avoided (owing to the inability of matching under such intense environmental changes (Valgren and Lilienthal, 2010)), the use of global sequence descriptors is proven to be crucial for the achieved performance. Most recently, condition-invariant vPR techniques have been presented based on the classification characteristics of convolution neural networks (CNNs). Methods like those presented by Sünderhauf et al. (2015a,b) and Arroyo et al. (2016) treat the output of particular CNN layers, initially trained for object detection tasks, as image descriptors and address the vPR problem by measuring the distances between them. Even though CNN-based techniques offer superior retrieval performances, they are still decoupled from the LCD and SLAM functionalities. Sizikova et al. (2016) and Fei et al. (2016), in their respective works, accurately pointed out the CNN’s dependence on viewpoint-invariant surface appearances and the lack of topological information at the higher network levels, which characterize them as suboptimal for LCD tasks. On the contrary, local feature-based techniques are widely used in visual SLAM applications (Cieslewski and Scaramuzza, 2017; Davison et al., 2007; Klein and Murray, Lim et al., 2014; 2007; Mur-Artal et al., 2015) and can be efficiently combined with an illumination invariant image representation technique (e.g. Maddern et al., 2014; Shakeri and Zhang, 2016) to further improve their robustness over potential environmental changes. However, such an application is beyond the scope of this paper and thus it is not further discussed.

2.2. Establishing the necessity ofsequence-visual-word-vectors

Given an actual pair of loop-closing images, there is no guarantee that a sufficient subset of common visual words will be detected in every case, since a single image can be subject to aliasing, contain noise or moving objects, etc. Thus, it is expected that an absolute thresholding, over the similarity scores between single instances, would fail in detecting some of the trajectory’s loops, or would also result in many false-positive detections (when a tolerant thresholding is applied). Many existing techniques (e.g. Gálvez-Lpez and Tards, 2012; Newman et al., 2006; Milford and Wyeth, 2012; Mur-Artal and Tards, 2014) choose to support their detection by accumulating similarity metrics ( $F_{I} (I_{1}, I_{2})$ ) from many images acquired close together in time. In the general case, succeeding frames are treated as sequences of multiple I-VWVs. These groups of I-VWVs (for instance S₁ and S₂) are then compared with the database and assigned an additive score of $F_{S} (S_{1}, S_{2}) = \sum_{i, j}^{i \in S_{1}, j \in S_{2}} F_{I} (I_{i}, I_{j})$ . Although this approach produces effective results, it is limited to a per-frame representation of the environment rather than offering a description of the whole sequence. Considering a simple example, such as the one presented in Figure 2(a), each visual word of a given scene might not constantly be inside the camera’s frustum or, for any reason, might not found by the feature detector (Figure 2(b)). This inconsistency entails I-VWVs with considerably uneven values even though they refer to the same scene. As a result, the $F_{S} (S_{1}, S_{2})$ scores often lead to a false interpretation of the actual sequences’ similarity in a variety of operational scenarios.

With this notion in mind, the aforementioned approaches can be characterized as sequence-matching techniques rather than sequence-descriptive ones. As opposed to treating a sequence as the summation of individual matching scores, our method achieves a description vector that contains every visual word found in the scene. Using a computationally efficient approach, for a given sequence of images, the visual words found in every camera measurement are gathered and vote on the respective bin of a common description vector (S-VWV). Note that multiple instances corresponding to the same visual word (i.e. a visual word observed by multiple frames) are treated as one, since they refer to the same feature in the world. A realization worth noticing here is that the proposed S-VWV-to-S-VWV matching would present the same results as the earlier approaches only under the false assumption that the used similarity metrics preserved the additive property of linear mapping. As can be seen in Figure 2(c), our method produces description vectors with better matching properties, as confirmed by our experimental evaluation (see Section 4).

A similar evaluation of such a unified description has been reported by MacTavish and Barfoot (2014). In their work, sequence-based descriptors were assessed for a variety of different but fixed-sized image groups, while the matching was achieved using a FAB-MAP-based probabilistic scheme. Parallel to this notion, our previous work (Bampis et al., 2016) deviated from the probabilistic matching solution and introduced a temporal consistency filtering to further improve the results. As mentioned before, the method in hand incorporates a dynamic sequence distinction technique, allowing for sequences of varying size to be formulated, while additionally, addressing the filtering as a classification procedure. Finally, a unified description was also achieved by the work of Lynen et al. (2014). Although their system allowed for the detected features to be matched against the whole database (regardless of the image they belonged to), their method was restricted to operate offline, after the conclusion of the full trajectory, while the sequence formulation was performed at query time. On the contrary, here the sequence distinction and matching is achieved online, as the trajectory escalates, quantizing the searching space through the means of the BoVW model.

3. Proposed methodology

Our online LCD algorithm is divided into two main steps, while the vocabulary and the filter’s kernel coefficients are learned offline through a training scheme. In the first step of the proposed online pipeline, sequence matches are detected, while the individual image associations are extracted in the second step.

3.1. Vocabulary training

To quantize the feature descriptors’ space, a visual vocabulary needs to be created. Aiming to offer a real-time implementation, we choose to utilize the binary description of ORB. In an offline step, a generic set of training descriptors is provided as input to a k-median hierarchical clustering, with k-means++ seeding (Arthur and Vassilvitskii, 2007) and Hamming as the distance metric. In accordance with the conclusions drawn by Nister and Stewenius (2006) and Gálvez-Lpez and Tards (2012), we formulate a vocabulary tree with L=6 levels and K=10 branches per level, leading to a total set of $W = K^{L}$ discrete visual words $w_{i}$ ( $i \in [1, W]$ ). Two different kinds of multiset need to be defined here, namely $ℕ_{i}^{D}$ and $ℕ^{D}$ , corresponding to the i th word’s occurrences and the occurrences of the total visual words in the training dataset, respectively.

3.2. Creating sequence and image descriptors

The main objective of our sequence distinction functionality does not refer to the actual semantics of the observed environment, but rather to the identification of groups of frames that share common features. To achieve a dynamic partition of the image stream, we utilize the variance of the obtained visual words. At a time instant t, during the sequence’s $S_{t}$ escalation, an occupancy vector $V_{S_{t}}^{O}$ is retained to keep track of the already-seen visual words. This binary vector, represented as $V_{S_{t}}^{O} = [w_{1}^{o}, \dots, w_{i}^{o}, \dots, w_{W}^{o}]$ , shares the same length as the vocabulary, while each value $w_{i}^{o}$ declares the existence ( $w_{i}^{o} = 1$ ) or absence ( $w_{i}^{o} = 0$ ) of the corresponding word $w_{i}$ in the current sequence. As the robot moves, the $N_{f}$ most prominent ORB features are extracted using the oFAST algorithm (the orientation invariant alteration of FAST (Rosten and Drummond, 2006), proposed by Rublee et al. (2011)) from every input image. The descriptors are then mapped onto visual words through the created vocabulary and marked NEW (seen for the first time during $S_{t}$ ) or OLD (already seen during $S_{t}$ ) by checking their indexes with vector $V_{S_{t}}^{O}$ . Thus, using a “visual word variance” metric, defined as $σ_{v} = N_{NEW} ∕ (N_{NEW} + N_{OLD})$ , we signal the completion of the current $S_{t}$ and the beginning of a new $S_{t + 1}$ each time $σ_{v} > r_{v}$ , with $r_{v}$ being a visual word variance, above which the input frame does not share enough visual words with the rest of the sequence. $N_{NEW}$ and $N_{OLD}$ denote the number of visual words marked NEW or OLD, respectively. Using this metric, a new sequence is instigated when the percentage of NEW visual words dominates the entire set of the input image’s features. Then the new vector $V_{S_{t + 1}}^{O}$ is initialized to zero, and the same procedure is repeated for the next sequence. In the case of $σ_{v} \leq r_{v}$ , the $V_{S_{t}}^{O}$ vector is updated with the visual words marked NEW and the following input image is characterized as a member of the current $S_{t}$ . We additionally force a maximum and minimum visual words’ capacity for the sequences, preventing their uncontrolled growth and allowing the $V_{S_{t}}^{O}$ vectors to initialize at least some elements. Finally, images that do not contain a minimum number of visual words are rejected as less informative.

Having a completed sequence S with M image-members $I_{m}$ ( $m \in [1, M]$ ), we now proceed to its description. The following multisets of visual words need to be defined. Multisets $ℕ_{i}^{S}$ and $ℕ_{i}^{I_{m}}$ are defined as the i th visual word’s occurrences in sequence S and image $I_{m}$ , respectively. Additionally, $ℕ^{S}$ and $ℕ^{I_{m}}$ are defined as the total visual word’s occurrences in S and $I_{m}$ , respectively. The aforementioned multisets are governed by

\begin{matrix} ℕ_{i}^{S} & = ⋃_{m = 1}^{M} ℕ_{i}^{I_{m}} \end{matrix}

(1)

\begin{matrix} ℕ^{S} & = ⋃_{m = 1}^{M} ℕ^{I_{m}} \end{matrix}

(2)

The widely used “term frequency–inverse document frequency” (tf–idf) (Sivic and Zisserman, 2003) was selected as a means of defining each visual word’s participation and creating the following visual-word-vectors: (i) one S-VWV ( ${\bar{v}}^{(S)}$ ) describing the whole observed visual content of the sequence’s respective area and (ii) M I-VWVs ( ${\bar{v}}^{(I_{m})}$ ) for the individual image-members. These descriptors

{\bar{v}}^{(S)} = [v_{1}^{(S)}, \dots, v_{i}^{(S)}, \dots, v_{W}^{(S)}]

and

{\bar{v}}^{(I_{m})} = [v_{1}^{(I_{m})}, \dots, v_{i}^{(I_{m})}, \dots, v_{W}^{(I_{m})}]

are calculated via

\begin{matrix} v_{i}^{(S)} & = \frac{N_{i}^{S}}{N^{S}} log \frac{N^{D}}{N_{i}^{D}} \end{matrix}

(3)

\begin{matrix} v_{i}^{(I_{m})} & = \frac{N_{i}^{I_{m}}}{N^{I_{m}}} log \frac{N^{D}}{N_{i}^{D}} \end{matrix}

(4)

where $N_{i}^{S} = | ℕ_{i}^{S} |$ , $N_{i}^{I_{m}} = | ℕ_{i}^{I_{m}} |$ , $N^{S} = | ℕ^{S} |$ , $N^{I_{m}} = | ℕ^{I_{m}} |$ , $N_{i}^{D} = | ℕ_{i}^{D} |$ , and $N^{D} = | ℕ^{D} |$ , with the notation $|X|$ representing the cardinality of multiset $X$ . Equation (4) refers to the description of the individual frames, while using equation (3) we are able to create a global description with better sequence-matching capabilities, as described in Section 2.2. Note that the additional computational burden for producing two versions of visual-word-vectors is negligible, since the most time-consuming part of the process (the tree traversal) is executed only once per visual word.

Finally, to restrict the matching search only between S-VWVs that include mutual visual information, inverted indexing is applied (Jegou et al., 2008). A set of W lists (one for every visual word $w_{i}$ ) is retained, keeping track of sequence indexes whose S-VWVs contain common visual words. Thus, sequence similarity scores are calculated through the inverted indexing list, achieving a reduction in the computational complexity.

3.3. Sequences-to-sequence matching

To match the individual sequences, we make use of a similarity metric based on the $L 2$ -norm. More specifically, using an $L 2$ -score similarity between a query ( $S_{q}$ ) and a database ( $S_{d}$ ) sequence that the inverse indexes indicate

L 2 ({\bar{v}}_{q}^{(S)}, {\bar{v}}_{d}^{(S)}) = 1 - 0.5 |\frac{{\bar{v}}_{q}^{(S)}}{|{\bar{v}}_{q}^{(S)}|} - \frac{{\bar{v}}_{d}^{(S)}}{|{\bar{v}}_{d}^{(S)}|}|

(5)

we obtain a metric that produces higher values as the vectors become more similar. As the trajectory escalates, the calculated $L 2$ -scores can be arranged to incrementally formulate a similarity matrix $M_{S}$ , like the one presented in Figure 3(a). This matrix is symmetric, with each element containing a corresponding normalized (Gálvez-Lpez and Tards, 2012) $L 2 ({\bar{v}}_{i}^{(S)}, {\bar{v}}_{j}^{(S)})$ measurement.

A naive approach to the detection of loop-closing sequences would be to apply an absolute thresholding over the values of matrix $M_{S}$ . With a view to further enhancing the cases of sequence matches with indexes that advance concurrently along time ( $S_{i \pm k}$ -to- $S_{j \pm k}$ , $k = 0, 1, 2, \dots$ ), we propose a novel temporal consistency filtering, the coefficients of which are trained in an offline step. Quantitatively interpreting the temporal constrain, we expect this filter to advance a sequence similarity score $L 2 ({\bar{v}}_{i}^{(S)}, {\bar{v}}_{j}^{(S)})$ proportionally with the values of $L 2 ({\bar{v}}_{i \pm k}^{(S)}, {\bar{v}}_{j \pm k}^{(S)})$ . In the same fashion, the filter should penalize $L 2 ({\bar{v}}_{i}^{(S)}, {\bar{v}}_{j}^{(S)})$ proportionally with the scores of $L 2 ({\bar{v}}_{i \pm k_{1}}^{(S)}, {\bar{v}}_{j \pm k_{2}}^{(S)})$ , with $(k_{1} \neq k_{2})$ . In other words, the resulting similarity measurement between sequences $S_{i}$ and $S_{j}$ will tend to become higher as the respective submatrix ( $m_{S}$ ) of $M_{S}$ —centered around the ( $i, j$ ) entry—comes closer to a diagonal view (e.g. Figure 3(b)) and by analogy lower in cases of temporal inconsistency (e.g. Figure 3(c)). Considering an example of window size $w_{F} = 3$ (corresponding to k=1), those two notions can be efficiently combined into a filter kernel with the structure

F = [\begin{matrix} α_{0} & - α_{1} & - α_{2} \\ - α_{3} & α_{4} & - α_{5} \\ - α_{6} & - α_{7} & α_{8} \end{matrix}]

(6)

with $α_{i} \geq 0$ . The correlation operation of F with the $M_{S}$ matrix results in a more intelligible interpretation ( $M_{S}^{F}$ ), as shown in Figure 3(d). To avoid the manual selection of the F coefficients and its size, an offline supervised training scheme based on cost-function minimization is formulated. Another way to consider our consistency filter is as a classifier that separates the loop-closing (class LC) similarity measurements from the non-closing ones (class N-LC). For each tested sequence pair $< S_{i}, S_{j} >$ , this classifier uses the corresponding $m_{S}$ neighborhood (i.e. a window around $M_{S} (i, j)$ of size $w_{F} \times w_{F}$ ), as a descriptor and decides whether it should fall into category LC or N-LC. Thus, we adopt a logistic-regression approach and we search for a first-order multivariate polynomial, with coefficients $\bar{θ} = {[θ_{0}, θ_{1}, \dots, θ_{n}]}^{T}$ , for which $\bar{x} \cdot \bar{θ} \geq 0$ indicates the detection of a sequence loop-closure event. Note that $\bar{x} = [1, {\hat{x}}_{1}, \dots, {\hat{x}}_{n}]$ denotes the rearrangement of a $m_{S}$ submatrix’s entries into a normalized feature vector format and $n = w_{F}^{2}$ . The normalization ${\hat{x}}_{i} = x_{i} ∕ max (x_{i})$ , $x_{i} \in m_{S}$ provides the required invariance over any similarity scale. Consequently, the values of $θ_{1}$ to $θ_{n}$ correspond to the filter’s coefficients (equation (6)), while $r_{s} = - θ_{0}$ can be characterized as a threshold that should be applied over the $M_{S}^{F}$ entries to identify the loop-closing sequences. The final cost-function minimization scheme is governed by

\begin{matrix} \bar{θ} & = \underset{\bar{θ}}{argmin} J (\bar{θ}) \end{matrix}

(7)

\begin{matrix} J (\bar{θ}) = - \frac{1}{l_{tr}} \sum_{i = 1}^{l_{tr}} [y_{tr}^{(i)} log h_{θ} ({\bar{x}}_{tr}^{(i)}, \bar{θ}) \\ + (1 - y_{tr}^{(i)}) log (1 - h_{θ} ({\bar{x}}_{tr}^{(i)}, \bar{θ}))] \end{matrix}

(8)

\begin{matrix} h_{θ} (\bar{x}, \bar{θ}) & = \frac{1}{1 + e^{\bar{x} \cdot \bar{θ}}} \end{matrix}

(9)

In equation (8), $l_{tr}$ denotes the size of the learning set, while ${\bar{x}}_{tr}^{(i)}$ and $y_{tr}^{(i)}$ denote the individual training feature vectors and their corresponding loop-closure ground-truth, respectively. Since two classes are used, we assign $y_{tr}^{(i)} = 1$ to the training LC elements and $y_{tr}^{(i)} = 0$ to the N-LC ones. This set of equations corresponds to a standard binary logistic-regression formulation. Looking for a hypothesis vector $\bar{θ}$ with the characteristics explained before, the sigmoid function of equation (9) maps the range $ℝ$ of $\bar{x} \cdot \bar{θ}$ output into the interval $(0, 1)$ . Then, the first summation term of equation (8) quantifies the cost of $\bar{x} \cdot \bar{θ} < 0$ for the ground-truth LC training sample, while the second one quantifies the cost of $\bar{x} \cdot \bar{θ} \geq 0$ for the N-LC ground-truth cases. Finally, the hypothesis vector $\bar{θ}$ can be achieved by minimizing the total cost (equation (7)) through gradient-descent, with the training samples being already normalized into the interval $[0, 1]$ . The selection of logistic regression as a classification technique is justified owing to its high tolerance over unbalanced training samples. As King and Zeng (2001) and Crone and Finlay (2012) pointed out, this effect can be accounted for when the training and testing data contain approximately the same amount of LC and N-LC events; this will be further considered in Section 4.1.3.

Moreover, to select the window size $w_{F}$ , we formulate a cross-validation step using another stand-alone set of feature vectors, ${\bar{x}}_{cv}^{(i)}$ . We assess multiple filter size scenarios ( $w_{F} = 2, 3, 4, 5, 6, 7$ ) corresponding to multiple feature vector’s lengths $n = w_{F}^{2}$ and we create a ${\bar{θ}}_{h}$ hypothesis for each one of them ( $h \in [0, 5]$ ). Next, the cross-validation error for every ${\bar{θ}}_{h}$ is evaluated using

J_{cv} ({\bar{θ}}_{h}) = \frac{1}{2 l_{cv}} \sum_{i = 1}^{l_{cv}} {(h_{θ} ({\bar{x}}_{cv}^{(i)}, {\bar{θ}}_{h}) - y_{cv}^{(i)})}^{2}

(10)

while the hypothesis producing the lowest $J_{cv}$ ( ${\bar{θ}}_{h}$ ) is to be adopted for the final filter’s kernel. Similar attempts to influence the values of $M_{S}$ matrix can be found in other techniques as well (Milford and Wyeth, 2012; Newman et al., 2006), yet in our case, the filtering is interpreted as a classification approach. It should also be noted that, during the online execution of our algorithm, the only $m_{S}$ sub-matrices that we need to formulate and filter are those indicated by the inverse indexing lists. Thus, the $M_{S}$ and $M_{S}^{F}$ matrices retain a sparse structure.

Filtered matching scores overpassing $r_{s} = - θ_{0}$ (or equivalently, matching scores with $\bar{x} \cdot {\bar{θ}}_{h} \geq 0$ ) are considered to contain loop-closure frame candidates and the next step of our method refers to their individual image-member associations. The sequence distinction technique described in Section 3.2 does not ensure that the produced trajectory intervals will be aligned between multiple traversals of the same area. Thus, some image-members of the query $S_{q}$ may actually need to be matched with the members of different neighboring database sequences. For this reason, we allow each $S_{q}$ to be associated with multiple $S_{d}$ , as long as they are subsequent.

3.4. Image-to-image matching

To provide a typical LCD technique, our method should provide image-to-image pairs as a final output. Although we find our sequence matches sufficient, so as to detect revisited regions of the trajectory, it is possible for some camera poses to be associated without necessarily observing the same content. One can consider the example of two trajectory tracks for which, even though they remain parallel and spatially close to each other for the majority of their length, their respective courses slowly deviate until they observe significantly different views. The corresponding two sequences assigned to those tracks ( $S_{m_{1}}$ and $S_{m_{2}}$ ), are naturally going to be matched despite the fact that their last camera measurements might not correspond to loop-closure events. In such a scenario, during the slow deviation of the trajectories, the visual content from both sequences does not drastically change, preventing the activation of our visual word variance constraint and the further segmentation of the sequences. In those cases, a simple “one-to-one” pairing would fail, since the last image-members of $S_{m_{1}}$ and $S_{m_{2}}$ should not be considered as loop-closures. To address these cases, individual I-VWVs need to be considered. For a highly accurate SLAM system, it would be sufficient to detect a single pair of loop-closing camera poses per sequence match using the highest $L 2$ -scoring I-VWV pair. Yet, as a general rule (assuming an odometry with low accuracy), we need to seek for as many detections as possible. More specifically, for every image-member of $S_{m_{1}}$ we seek in its paired sequence $S_{m_{2}}$ (or paired sequences, if more than one association was produced by the previous step) for the image that produces the maximum I-VWV $L 2$ -score. Subsequently, in order to reject image pairs that cannot be visually associated, a loop-closure event is identified if the measured similarity is greater than a threshold $r_{i}$ . A common practice for many LCD systems (e.g. Bampis et al., 2016; Gálvez-Lpez and Tards, 2012; Lynen et al., 2014; Mur-Artal et al., 2015) is to apply a final geometrical-verification test to accept a loop-closing pair of images. Since such tests are based on the computationally expensive estimation of a valid camera transformation matrix, the $r_{i}$ threshold must be decided so as to reduce the geometrical-verification steps to the minimum required by the SLAM and the pose-graph optimization technique (Latif et al., 2013).

4. Results

In this section, we evaluate the individual components of our system and compare the achieved overall performance against other state-of-the-art methods. To measure the accuracy of an implementation we utilize precision–recall metrics. As a reminder, “precision” is defined as the ratio between accurately detected loop-closing frames (true-positive) and the total number of detections returned by the method (true-positive plus false-positive). Additionally, “recall” is defined as the number of true-positive detections found, over the total number of loop-closing frames that exist in the used dataset (true-positive plus false-negative). For our experiments, we consider a sequence match as true-positive if at least one loop-closing camera pose is contained. Nine different datasets (indoors and outdoors) were used for our experiments, namely Bovisa 2008-09-01 (BV) (Rawseeds, 2007), Bicocca 2009-02-25b (BC) (Rawseeds, 2007), New College (NC)¹ (Smith et al., 2009), Lip6 Indoor (L6I) (Angeli et al., 2008), Lip6 Outdoor (L6O) (Angeli et al., 2008), Malaga 2009 Parking 6L (MG6L) (Blanco et al., 2009), City Center (CC) (Cummins and Newman, 2008), KITTIsequence 00 (KITTI00) (Geiger et al., 2013), and KITTI sequence 05 (KITTI05) (Geiger et al., 2013). Regarding the KITTI dataset, we considered only sequences 00 and 05, since, among the rest, they provide the most meaningful loop-closure events in urban and long-term operational conditions. Table 1 contains a brief description of every case. Datasets BC through L60 were used as training and cross-validation sets for our method’s parameters, while the remaining datasets (MG6L through KITTI05) were treated as testing cases, measuring the performance of our final system. In such a way, the achieved detection accuracy is not directly influenced by the algorithm’s optimization, thus offering a fair evaluation. Note that the loop-closure ground-truth information for the cases of BC, NC, MG6L, and CC was manually created within the work of Gálvez-Lpez and Tards (2012). The L6I and L6O datasets contain their own ground-truth information, as provided by Angeli et al. (2008), while for the KITTI sequences, this information was obtained through the corresponding odometry data.

Table 1.

Properties of the datasets used.

	Dataset	Environment	Conditions	Camera position	Image size
Training/cross-validation	Bovisa 2008-09-01	Indoors & outdoors	Static	Frontal	$320 \times 240$
	Bicocca 2009-02-25b	Indoors	Static	Frontal	$640 \times 480$
	New College	Outdoors	Dynamic	Frontal	$512 \times 384$
	Lip6 Indoor	Indoors	Static	Frontal	$240 \times 192$
	Lip6 Outdoor	Outdoors, urban	Highly dynamic	Frontal	$240 \times 192$
Testing	Malaga 2009 Parking 6L	Outdoors	Slightly dynamic	Frontal	$1024 \times 768$
	City Center	Outdoors, urban	Dynamic	Lateral	$640 \times 480$
	KITTI Sequence 00	Outdoors, urban	Dynamic	Frontal	$1241 \times 376$
	KITTI Sequence 05	Outdoors, urban	Dynamic	Frontal	$1241 \times 376$

4.1. Offline training and performance evaluation

4.1.1. Vocabulary training

Using a vocabulary training set corresponding to a specific environment with limited visual variations inevitably biases the system’s performance to the respective operational conditions. Within the scope of this work, we aim to create a vocabulary that is able to perform in a variety of indoor and outdoor conditions. In accordance with these terms, the BV dataset was selected as a stand-alone training sample in order to offer an objective evaluation. Using 10k frames, a set of 9M ORB descriptors was extracted and used as an input to our hierarchical clustering. Thus, a binary vocabulary tree was produced retaining a total of $1 0^{6}$ discrete visual words as leaf nodes.

4.1.2. Trajectory segmentation

As described in Section 3.2, our algorithm dynamically separates the input image stream into sequences based on the observed visual words’ variance. Considering the system’s overall performance as a final objective, a validation test based on precision–recall metrics was formulated to measure the effect of different $r_{v}$ . Multiple values were selected and assessed on the four training datasets. In this step, the production of precision–recall measurements is not straightforward, since our system does not create any loop-closure output during the sequences’ partition. To this end, we temporarily fixed the kernel of our consistency filter to have all its $α_{i}$ elements equal to zero except for $α_{4} = 1$ , canceling its effect during the detection and promoting $r_{s}$ as a means of alternating the precision–recall measurements. Figure 4(a) to 4(d) shows the most informative curves we obtained by considering sequence matches for every training dataset, respectively. The curves shown in Figure 4(e) were created accordingly by treating all the datasets as a unified environment(as if the same robot traveled through each dataset, one after another). Note that, for a range of $r_{v}$ values between 0.6 and 0.8, the achieved performance remains relatively stable. Considering the BC dataset, it appears that the best performance is achieved using a visual word variance threshold of $r_{v} = 0.6$ while, for the case of NC, the most beneficial case was $r_{v} = 0.75$ . This is because the BC dataset corresponds to an indoor environment; therefore, visual changes tend to be more severe than NC. Given a specified application scenario (indoors or outdoors, dynamic or non-dynamic, frontal or lateral camera view, etc.), the most appropriate $r_{v}$ value can be selected accordingly. However, in this paper we aim for a generic setup and thus the value of $r_{v} = 0.75$ was adopted. The resulting sequences for the most representative regions of BC and NC (containing turning points and sight changes) are shown in Figure 5. Note that, for the L6I and L6O datasets, no odometry ground-truth is provided by Angeli et al. (2008).

The proposed visual word variance metric is not the only kind of measurement considered for our methodology. Other approaches, capable of running in real time and online (while the robot is moving) without the requirement of accessing the whole database beforehand, were also examined. Table 2 presents some of the evaluated techniques together with their respective best-case recall rates (for $100 %$ precision) and average execution time, tested on the aforementioned unified training dataset. The “progressive $L 2$ -score” method marks the completion of a sequence whenever the $L 2$ -score between the current and the previously acquired input frame becomes smaller than a certain level, while the “visual word variance” method refers to the proposed approach that we previously evaluated. The “windowed progressive $L 2$ -score” and “windowed visual word variance” methods apply an additional averaging sliding window over the two aforementioned metrics. In these methods, the mean values of $L 2$ -score and $σ_{v}$ were calculated, respectively, between the current and the last p input frames. Thus, the most recent sequence is finalized whenever the average $L 2$ -score becomes less than a certain level (“windowed progressive $L 2$ -score”), or when the average $σ_{v}$ becomes greater than one (“windowed visual word variance”). These approaches were selected with the aim of preventing unnecessary partition of the input stream when an instantaneous change of the view occurs (e.g. instantaneously looking sideways) while the robot is still located in the same scene. Interestingly, the two methods did not provide any considerable advantage to the system’s performance. This is because the proposed sequence matching scheme, in which, even if a continuous trajectory region is segmented without a semantic meaning, the produced additional sequences can all still be matched to a potentially loop-closing non-segmented database entry. The only disadvantage of such a division is the additional processing steps induced by the unnecessary segmentation of the searching space. Yet, as can be seen in Table 2, the continuous calculations of the extra $L 2$ -score or $σ_{v}$ measurements render the window-based approaches unfavorable, compared with their corresponding straightforward ones. Finally, the “image islands” method is inspired by the techniques described by Gálvez-Lpez and Tards (2012) and Milford and Wyeth (2012). The procedure starts with a calculation of the $L 2$ -scores between the I-VWVs. Then, close-in-time sets of images that present considerable similarity scores with the database are grouped to create the required sequences. The remaining frames are not employed. The rest of the proposed steps (S-VWV formulations, comparisons, etc.) remain the same. As seen, although this approach presents higher recall rates for $100 %$ precision accuracy, it is still the most costly in terms of execution time. Considering a case of a powerful processing architecture, the “image islands” technique would be the most beneficial approach for distinguishing the required sequences. Yet, within the scope of this paper, time efficiency is crucial and thus the proposed visual word variance is adopted since it achieves a nice trade-off between performance and operational frequency.

Table 2.

Tested sequence distinction approaches.

Method	Recall ( $%$ )	Average execution time (ms)
Progressive $L 2$ -score	68.12	0.14
Visual word variance	67.54	0.01
Windowed progressive $L 2$ -score	69.85	0.77
Windowed visual word variance	68.01	0.12
Image islands	74.36	8.84

4.1.3. Temporal consistency filter

The next set of parameters that we need to assess is the coefficients of the proposed temporal consistency filter. Once more, the same four training datasets were selected and the corresponding $M_{S}$ matrices were formulated using the procedure described in Section 3.3. Concatenation of all four $M_{S}$ resulted in a training sample that contained a representative ratio between LC (Figure 3(b)) and N-LC (Figure 3(c)) events, allowing the classifier to address analogous cases during its online execution. Yet, given a specified operational environment, the estimated hypothesis vector can be accordingly adjusted to fit each particular sample distribution without the need to retrain the whole system, as described by King and Zeng (2001). The sample was further separated into two subsets, namely training ( ${\bar{x}}_{tr}^{(i)}$ ) and cross-validation ( ${\bar{x}}_{cv}^{(i)}$ ), containing $70 %$ and $30 %$ of the total loop-closing and non-loop-closing entries, respectively. Using equations (7) to (9) for every filter size scenario, we obtained six different hypothesis vectors ${\bar{θ}}_{h}$ . The rates of convergence for each one are shown in Figure 6(a), while Figure 6(b) contains their respective cross-validation errors. The winning hypothesis ${\bar{θ}}_{1}^{w} = {[θ_{0}^{w}, θ_{1}^{w}, \dots, θ_{9}^{w}]}^{T}$ (h=1) corresponds to a filter size of $w_{F} = 3$ . Thus, the filter’s kernel was found using the values of $θ_{1}^{w}, \dots, θ_{9}^{w}$ as

F = [\begin{matrix} 2.3088 & - 0.5663 & - 1.8762 \\ - 0.4084 & 2.1938 & - 0.7538 \\ - 1.8333 & - 0.3420 & 2.1512 \end{matrix}]

(11)

Additionally, considering that $θ_{0}^{w}$ converged to the value of $- 3.5$ , we found $r_{s}$ from $r_{s} = - θ_{0}^{w} = 3.5$ . The filtered similarity matrix $M_{S}^{F}$ shown in Figure 3(d) was produced by applying the kernel of equation (11) over the $M_{S}$ entries of the BC dataset. Here, we need to point out that the feature vector converged into a kernel with the same structure as that of equation (6), proving that our temporal consistency objective is admissible and achieved.

4.1.4. Overall performance

Using the aforementioned trained filtering, the overall performance of our pipeline was evaluated for each training dataset. By varying threshold $r_{i}$ and considering image-to-image matches, we acquired the precision–recall curves presented in Figure 7. To test our whole methodology on some stand-alone cases, we used the MG6L, CC, KITTI00, and KITTI05 datasets. Figure 8 shows the recall rates corresponding to $100 %$ precision for each proposed matching step. The used parameter setup is summarized in Table 3. The presented results reveal that our algorithm provides nice scaling capabilities over the selected testing sets. Note that the sequence-matching recall rates correspond to the testing evaluation of the trained logistic-regression classifier. As expected, the highest recall improvement, obtained through the image-matching step, occurred in the MG6L dataset, since, in that case, sequence tracks with small loop-closing overlap are more profound (Figure 1). Finally, operational examples for each of the used datasets are presented in Figures 9 to 16. At this point, we need to state once again that L6I and L6O do not offer any odometry ground-truth and that BV does not contain considerable loop-closure events.

Table 3.

Parameter setup.

Tree branches (K)	10
Tree levels (L)	6
ORBs/frame ( $N_{f}$ )	300
Visual variation ( $r_{v}$ )	0.75
Filter kernel (F)	$[\begin{matrix} 2.31 & - 0.57 & - 1.88 \\ - 0.41 & 2.19 & - 0.75 \\ - 1.83 & - 0.34 & 2.15 \end{matrix}]$
Seq. matching ( $r_{s}$ )	3.5
Image matching ( $r_{i}$ )	0.25

4.2. Comparative results

In this subsection, the overall performance of our system is compared against other state-of-the-art techniques. Within the scope of this work, we aim for a solution capable of achieving high-quality LCD results while still retaining a real-time performance for key-frame SLAM applications (≈100–200 ms per frame (Davison et al., 2007; Mei et al., 2009; Strasdat et al., 2010)). For this reason, the methods described by Angeli et al. (2008); Cummins and Newman (2011); Gálvez-Lpez and Tards (2012); Milford and Wyeth (2012); Mur-Artal and Tards (2014), and Khan and Wollherr (2015), as well as our previous preliminary version (Bampis et al., 2016), were selected for assessment. As can be seen in Table 4, our approach achieves higher recall rates than any other tested algorithm tangibly proving the capabilities of the proposed S-VWV to S-VWV matching. Table entries marked “–” correspond to evaluations not available in the literature, while all the included performance metrics were obtained using a common loop-closure ground-truth. Once again, the BV dataset was not tested, as it does not present sufficient loop-closure events. Among the selected approaches, FAB-MAP 2.0 (Cummins and Newman, 2011) and SIFT+COLOR (Angeli et al., 2008) are both considered golden standards for LCD tasks. Additionally, since for the case of FAB-MAP 2.0 no actual precision–recall measurements are provided by Cummins and Newman (2011) regarding the used datasets, the presented performance is obtained from the setup described in the work of Gálvez-Lpez and Tards (2012). To evaluate the performance of SeqSLAM algorithm (Milford and Wyeth, 2012), one of the most representative sequence-based LCD techniques that groups camera measurements based on their matching similarities, we made use of the OpenSeqSLAM² implementation. Since the original version was optimized for addressing the vPR task under changing illumination conditions, rather than identifying revisited places under different viewpoints (MacTavish and Barfoot, 2014), it is reasonable that the SeqSLAM performance is not competitive in many of the tested datasets. To confirm the arguments presented in Section 2.2 and to offer fair comparisons, we additionally implemented a BoVW-based version of SeqSLAM using the same visual vocabulary as in our method and computing I-VWV to I-VWV $L 2$ -norms. This version utilizes the same elements as the proposed algorithm, but differs in its key characteristic by adopting a sequence-matching, rather than a sequence-description approach. The best-performing parameters for each assessed case were identified according to the literature. As can be seen, the proposed S-VWV description outperforms the BoVW-based SeqSLAM for almost every case, with the L6I being the only dataset slightly failing. This is because the presented algorithm exploits its highest potentials, as compared with other sequence-based techniques, in dynamic environments where the visual words might not be constantly detected by each camera measurement, as illustrated in Figure 2. The case of L6I dataset, though, corresponds to a static environment, with a camera facing forward and traveling through well-lit corridors. Therefore, the proposed unified description is unavailing and thus performs analogously to the BoVW-based SeqSLAM. Methods DBoW2 (Gálvez-Lpez and Tards, 2012) and DBoW2-ORB (Mur-Artal and Tards, 2014) also accumulate similarity metrics between single frames to form a sequence-matching score, though in those cases, image groups are formulated based on their time intervals. Finally, the IBuILD method (Khan and Wollherr, 2015) corresponds to a dynamic vocabulary creation approach, capable of running in real time, while the S-VWV baseline method (Bampis et al., 2016) also incorporates the presented S-VWV description, yet lacks an adoptive parametrization since every sequence was distinguished based on a fixed traversed distance.

Table 4.

Comparative results showing achieved recall rates ( $%$ ) for $100 %$ precision accuracy. Entries in bold indicate the best-performing approach for each dataset.

	BC	NC	L6I	L6O	MG6L	CC	KITTI00	KITTI05
Cummins and Newman (2011)	–	–	–	–	68.52	38.77	–	–
FAB-MAP 2.0
Angeli et al. (2008)	–	–	36.86	23.59	–	–	–	–
SIFT+COLOR
Gálvez-Lpez and Tards (2012)	81.20	55.92	–	–	74.75	31.61	–	–
DBoW2
Mur-Artal and Tards (2014)	76.60	70.29	–	–	81.51	43.03	–	–
DBoW2-ORB
Khan and Wollherr (2015)	–	–	41.74	25.58	78.13	38.92	–	–
IBuILD
Milford and Wyeth (2012)	13.90	55.12	20.91	5.63	15.09	42.80	83.54	87.95
SeqSLAM
Based on Milford and Wyeth (2012)	73.15	85.97	54.43	39.95	80.48	60.27	89.29	91.65
SeqSLAM-BoVW
Bampis et al. (2016)	78.10	77.55	45.69	51.92	76.78	68.49	81.54	84.80
S-VWV baseline
Proposed	91.90	92.74	52.22	58.32	87.56	71.14	96.53	97.28

5. Algorithm efficiency and mobile deviceimplementation

In addition to effective similarity properties, our first level of sequence-to-sequence matching allows for a more efficient implementation in terms of computational complexity. More specifically, one can consider the proposed S-VWV comparisons as a means of rejecting large trajectory regions that are different in the general view, followed by a supplementary examination of the individual image-members. Taking into account an example of a long traversed route with $n_{c}$ camera poses, we can evaluate the number of comparisons that a generic image-to-image based method and the proposed one need to perform. In the first case, each individually generated I-VWV has to be compared with the whole database to find the most similar match, leading to a total of up to ${n_{c}}^{2} ∕ 2$ similarity measurements. On the contrary, our method is capable of detecting revisited trajectory regions using only ${(n_{c} ∕ \bar{M})}^{2} ∕ 2$ comparisons, where $\bar{M}$ denotes the average size of the produced sequences. Subsequently, only for the identified revisited scenes, the individual image associations corresponding to loop closures are produced. Even for the extreme case in which a match has been found for all the sequences, the additional computational steps for producing image pairs are of the order of $n_{c} * \bar{M}$ , which, accumulated to ${(n_{c} ∕ \bar{M})}^{2} ∕ 2$ , is still less than the ${n_{c}}^{2} ∕ 2$ required by the brute-force image-to-image matching for prolonged datasets. Naturally, the inverse indexes will reduce the execution time of both approaches in the same manner. Thus, their effect is omitted from this example.

The nature of the presented sequence description algorithm provides an additional means for further reducing the computational complexity of the S-VWV matching functionality. During the formulation of each sequence, it is natural to expect a set of visual words to be observed by multiple image-members. Such visual words typically correspond to better-localized ORB descriptors in the vocabulary clustering space and they are originated from more representative sequence landmarks. Thus, a significant speedup can be achieved, during the sequence-matching procedure, by only considering visual words observed from more than one image-member. As can be seen in Figure 17, the exclusion of visual words occurring in only one image has a minor effect on the achieved recall rates, while at the same time increasing the computational frequency of the sequence-matching functionality by more than $100 %$ .

Since our system is capable of detecting loop-closure events using only a monocular camera while retaining a low computational complexity, an application for mobile devices was developed to provide a complete and fully functional system. Using the Android development kit provided by Google’s Project Tango (Google, 2017), we implemented a C++ based algorithm³ utilizing the parallelization capabilities of the ARM-NEON coprocessor. The application was specifically designed so as to respect the limitations of a mobile device in terms of available RAM and processing power. In particular, we used a sparse representation for each of the description vectors (S-VWVs and I-VWVs) while the ARM-NEON coprocessor, built on the SIMD architecture, undertook the parallelizable procedures, e.g. detection or description of ORB features and the Hamming distance calculation for the vocabulary tree traversal. In addition, we assigned the sequence-matching procedure on a dedicated thread running concurrently with the rest of our algorithm (but not on a different core). Since the sequence matching is triggered whenever a new sequence is completed and not for every input frame, it is natural to burden the execution time unevenly. During the formulation of a new sequence, no similarity score calculations are performed, allowing the implementation to run in less than 25 ms. Whenever a new sequence is completed, an instantaneous overhead appears, preventing our application from running in constant time. Thus, using two individual threads in a pipeline manner, the most recently created sequence is compared with the database and the loop-closures—if any—are detected while the formulation of a new S-VWV occurs. In this way, even though we do not achieve any speedup over the total execution time, the necessary calculations are evenly spread along the acquisition of every input image. Extension 1 shows an instance of our application running on the Tango device in a real-world scenario.

Using this implementation, we formulated a time-profiling experiment on the biggest tested dataset. Table 5 presents the execution time obtained by each of the processing stages for 15k images of the NC dataset (padding the available RAM of the device). As one can observe, the most demanding procedure of our algorithm is the feature extraction, which can be considered as pre-computed for many SLAM architectures. Although the matching procedure may require a maximum of 12.56 ms, only its average cost is perceptible by the whole application, owing to the used pipelining. In addition, by forcing a serialized execution of the two pipelining threads, we obtained the timing measurements presented in Figure 18 for each of the main algorithm’s procedures.

Table 5.

Time profiling for 15k images of New College dataset.

		Time (ms∕frame)
		Mean	Standard deviation	Minimum	Maximum
Feature	oFAST detection	11.38	5.05	4.59	30.08
extraction	ORB description	7.21	2.45	3.63	21.21
	Total	18.58	4.84	8.29	52.53
Visual-word-vector	Tree traversal	3.84	0.76	1.43	17.49
calculation	Form I-VWV	0.05	0.02	0.03	0.61
	Form S-VWV	0.07	0.05	0.001	0.78
	Total	3.96	0.77	1.43	17.49
Matching	Inverse indexing	0.09	0.34	0.83	3.55
	Sequence matching	4.87	7.72	0.66	12.47
	Image matching	0.02	0.26	0.20	8.54
	Total	4.99	8.04	2.81	12.56
Whole application		27.44	8.74	13.66	58.01

6. Discussion

In this paper, a novel sequence description technique is proposed, which allows us, for the first time, to combine the entire visual information of a place into a single descriptor, while still retaining a feature-based approach. The newly introduced S-VWV module allows for a two-layered LCD system that firstly recognizes revisited scenes and later associates the individual loop-closing camera poses. Instead of adopting a spatiotemporal approach so as to distinguish the individual sequences, an efficient visual word variance metric is selected, separating the input stream with respect to the visual content’s alterations. In addition, taking into account the temporal consistency constraint that successively recognized camera measurements need to obey, a novel similarity filtering is proposed. By considering the filter’s kernel as a binary classifier, its coefficients are learned using a cost-function minimization scheme. Finally, an implementation of the presented algorithm is developed and tested on a mobile device, utilizing the parallelization properties of the SIMD architecture and proving the computational efficiency of our method.

By successfully describing an image sequence, rather than matching single instances and accumulating their similarity scores, our method provides a unified solution. Yet, its true potentials are fully exploited when the executed trajectory includes long loop-closing tracks. In contrast with the rest of the evaluated datasets, BC contains many sharp and rapid turning movements (especially during the end of the traversed route, as shown in Figure 5(a)), causing the used sequence distinction function to over-segment the trajectory into scenes that actually correspond to the same place. An analogous example can be considered with a camera rotating around its yaw axis and causing the formulation of multiple sequences, while still remaining in the same physical place. In these cases, the presented method descends into a simple BoVW-based approach, with the formulated S-VWVs retaining a similar structure to the corresponding I-VWVs. Even though this aimless segmentation does not affect the system’s performance (see Section 4.1.2), it may unnecessarily increase the computational complexity of the sequence-matching procedure by expanding the searching database space. Possible ways to avoid such extreme cases are the tested “windowed progressive $L 2$ -score” and “windowed visual word variance” approaches. A scale-space filtering (Witkin, 1984) over these measurements can also be useful to achieve a dynamic window size. Having as principal objective the identification of image groups that share a sufficient number of common visual words, further co-visibility and graph-connectivity measurements can be applied and evaluated (Chandrasekharet al., 2014b; Erkent and Bozma, 2015), especially in cases of offline map optimization or relocalization scenarios, where the traversed map is fully formulated beforehand (Chandrasekhar et al., 2014a; Johns and Yang, 2011; Moon et al., 2016).

Given our choice of ORB local features, a scale- and rotation-invariant description is achieved. Such a mechanism, though, does not promote a direction invariant LCD system, especially when the respective robot is equipped with a monocular frontal camera. This is because the detected patches’ appearance, although originating from the same place, changes significantly when observed from two opposite directions, leading many vPR systems to exclude these revisited paths, or fail to identify them (Fraundorfer et al., 2007; Lynen et al., 2014). Even though such cases are not commonly encountered, thus not handled by the proposed and other sequence-based vPR techniques (Newman et al., 2006), possible solutions include the utilization of lateral-oriented or panoramic cameras (Agarwal et al., 2015; Lynen et al., 2014), or the estimation of the detected patches’ orientation (Davison et al., 2007) in order to predict their appearance changes. Using the proposed system for such events would additional imply an appropriate temporal consistency filter structure. Thus, our filter needs to be retrained accordingly (probably converging to a higher window size) or applied twice, once with the structure of equation (11) and once with the same kernel flipped on both axes, to additionally promote $m_{S}$ sub-matrices with high antidiagonal similarity metrics.

An important characteristic of the introduced S-VWV-based LCD approach is its fundamental generality. In contrast with the sequence-matching approaches (that accumulate similarity metrics between multiple images), the proposed descriptor can efficiently adapt to a distributed architecture, such as that described in the recent work of Cieslewski and Scaramuzza (2017), and allow for a decentralized vPR system of multiple agents. Additionally, since such a description vector can be combined with any kind of vocabulary, an extension of our work would be to utilize visual words that present invariance over illumination or other environmental changes (Lee et al., 2013; Linegar et al., 2016; McManus et al., 2015; Ng et al., 2015). As a final thought, the notion of a sequence description could serve as a basis for introducing new variables in the LCD procedure. Approaches capable of quantizing time-depended measurements in the S-VWVs, such as the optical flow or the robot’s ego-motion, can be investigated with the aim of further assisting the matching functionality.

Footnotes

Appendix A: Index to multimedia extension

Archives of IJRR multimedia extensions published prior to 2014 can be found at http://www.ijrr.org, after 2014 all videos are available on the IJRR YouTube channel at http://www.youtube.com/user/ijrrmultimedia

SAGE-Journals-Accessible-Video-Player 10.1177/0278364917740639.M1 sj-vid-1-ijr-10.1177_0278364917740639 Extension 1

Operational example on a mobile device

Acknowledgements

The ORB feature extraction ARM-NEON implementation was developed at MARS Lab UMN. The authors would also like to thank Dorian Gálvez-López for providing their manually created loop-closure ground-truth regarding many of the used datasets.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: The ARM-NEON implementation of ORB was funded by Google’s Project Tango.

Notes

References

Agarwal

Burgard

Spinello

(2015) Metric localization using Google Street View. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Hamburg, Germany, 28 September–2 October 2015, pp. 3111–3118. Piscataway, NJ: IEEE.

Angeli

Filliat

Doncieux

et al . (2008) Fast and incremental method for loop-closure detection using bags of visual words. IEEE Transactions on Robotics 24(5): 1027–1037.

Arroyo

Alcantarilla

Bergasa

et al . (2015) Towards life-long visual localization using an efficient matching of binary sequences from images. In: Proceedings of the IEEE international conference on robotics and automation, Seattle, WA, 26–30 May 2015, pp. 6328–6335. Piscataway, NJ: IEEE.

Arroyo

Alcantarilla

Bergasa

et al . (2016) Fusion and binarization of CNN features for robust topological localization across seasons. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Daejeon, South Korea, 9–14 October 2016, pp. 4656–4663. Piscataway, NJ: IEEE.

Arthur

Vassilvitskii

(2007) k-means++: The advantages of careful seeding. In: Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, New Orleans, LA, 7–9 January 2007, pp. 1027–1035. Philadelphia, PA: Society for Industrial and Applied Mathematics.

Bampis

Amanatiadis

Gasteratos

(2016) Encoding the description of image sequences: A two-layered pipeline for loop closure detection. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Daejeon, South Korea, 9–14 October 2016, pp. 4530–4536. Piscataway, NJ: IEEE.

Bay

Tuytelaars

Van Gool

(2006) SURF: Speeded up robust features. In: Leonardis

Bischof

Pinz

(eds.) Computer Vision—ECCV 2006 (Lecture Notes in Computer Science, vol. 3951). Berlin: Springer, pp. 404–417.

Blanco

Moreno

Gonzalez

(2009) A collection of outdoor robotic datasets with centimeter-accuracy ground truth. Autonomous Robots 27(4): 327–351.

Chandrasekhar

Min

et al . (2014a) Efficient retrieval from large-scale egocentric visual data using a sparse graph representation. In: Proceedings of the IEEE conference on computer vision and pattern recognition workshops, Columbus, OH, 23–28 June 2014, pp. 527–534. Piscataway, NJ: IEEE.

10.

Chandrasekhar

Tan

Min

et al . (2014b) Incremental graph clustering for efficient retrieval from streaming egocentric video data. In: Proceedings of the IEEE international conference on pattern recognition, Stockholm, Sweden, 24–28 August 2014, pp. 2631–2636. Piscataway, NJ: IEEE.

11.

Cieslewski

Scaramuzza

(2017) Efficient decentralized visual place recognition using a distributed inverted index. IEEE Robotics and Automation Letters 2(2): 640–647.

12.

Crone

Finlay

(2012) Instance sampling in credit scoring: An empirical study of sample size and balancing. International Journal of Forecasting 28(1): 224–238.

13.

Cummins

Newman

(2008) FAB-MAP: Probabilistic localization and mapping in the space of appearance. The International Journal of Robotics Research 27(6): 647–665.

14.

Cummins

Newman

(2011) Appearance-only SLAM at large scale with FAB-MAP 2.0. The International Journal of Robotics Research 30(9): 1100–1123.

15.

Davison

Reid

Molton

et al . (2007) MonoSLAM: Real-time single camera SLAM. IEEE Transactions on Pattern Analysis and Machine Intelligence 29(6): 1052–1067.

16.

Erkent

Bozma

(2015) Long-term topological place learning. In: Proceedings of the IEEE international conference on robotics and automation, Seattle, WA, 26–30 May 2015, pp. 5462–5467. Piscataway, NJ: IEEE.

17.

Fei

Tsotsos

Soatto

(2016) A simple hierarchical pooling data structure for loop closure. In: Leibe

Matas

Sebe

al.

(eds.) Computer Vision—ECCV 2016 (Lecture Notes in Computer Science, vol. 9907). Cham: Springer, pp. 321–337.

18.

Folkesson

Christensen

(2004) Graphical SLAM—a self-correcting map. In: Proceedings of the IEEE international conference on robotics and automation, New Orleans, LA, 26 April–1 May 2004, vol. 1, pp. 383–390. Piscataway, NJ: IEEE.

19.

Fraundorfer

Engels

Nistér

(2007) Topological mapping, localization and navigation using image collections. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, San Diego, CA, 29 October–2 November 2007, pp. 3872–3877. Piscataway, NJ: IEEE.

20.

Gálvez-Lpez

Tards

(2012) Bags of binary words for fast place recognition in image sequences. IEEE Transactions on Robotics 28(5): 1188–1197.

21.

Geiger

Lenz

Stiller

et al . (2013) Vision meets robotics: The KITTI dataset. The International Journal of Robotics Research 32(11): 1231–1237.

22.

Google (2017) Project Tango. Available at: https://developers.google.com/tango/hardware/tablet (accessed 10 October 2017).

23.

Grisetti

Kümmerle

Stachniss

et al . (2010) A tutorial on graph-based SLAM. Intelligent Transportation Systems Magazine 2(4): 31–43.

24.

Jegou

Douze

Schmid

(2008) Hamming embedding and weak geometric consistency for large scale image search. In: Forsyth

Torr

Zisserman

(eds.) Computer Vision – ECCV 2008 (Lecture Notes in Computer Science, vol. 5302). Berlin: Springer, pp. 304–317.

25.

Johns

Yang

(2011) From images to scenes: Compressing an image cluster into a single scene model for place recognition. In: Proceedings of the IEEE international conference on computer vision, Barcelona, Spain, 6–13 November 2011, pp. 874–881. Piscataway, NJ: IEEE.

26.

Khan

Wollherr

(2015) IBuILD: Incremental bag of binary words for appearance based loop closure detection. In: Proceedings of the IEEE international conference on robotics and automation, Seattle, WA, 26–30 May 2015, pp. 5441–5447. Piscataway, NJ: IEEE.

27.

King

Zeng

(2001) Logistic regression in rare events data. Political Analysis 9(2): 137–163.

28.

Klein

Murray

(2007) Parallel tracking and mapping for small AR workspaces. In: IEEE and ACM international symposium on mixed and augmented reality, Nara, Japan, 13–16 November 2007, pp. 225–234. Piscataway, NJ: IEEE.

29.

Konolige

Bowman

Chen

et al . (2010) View-based maps. The International Journal of Robotics Research 29(8): 941–957.

30.

Labbé

Michaud

(2013) Appearance-based loop closure detection for online large-scale and long-term operation. IEEE Transactions on Robotics 29(3): 734–745.

31.

Latif

Cadena

Neira

(2013) Robust loop closing over time for pose graph SLAM. The International Journal of Robotics Research 32(14): 1611–1626.

32.

Lee

Zhang

Lim

et al . (2013) Place recognition using straight lines for vision-based SLAM. In: Proceedings of the IEEE international conference on robotics and automation, Karlsruhe, Germany, 6–10 May 2013, pp. 3799–3806. Piscataway, NJ: IEEE.

33.

Lim

Kim

(2014) Real-time 6-DOF monocular visual SLAM in a large-scale environment. In: Proceedings of the IEEE international conference on robotics and automation, Hong Kong, China, 31 May–7 June 2014, pp. 1532–1539. Piscataway, NJ: IEEE.

34.

Linegar

Churchill

Newman

(2016) Made to measure: Bespoke landmarks for 24-hour, all-weather localisation with a camera. In: Proceedings of the IEEE international conference on robotics and automation, Stockholm, Sweden, 16–21 May 2016, pp. 787–794. Piscataway, NJ: IEEE.

35.

Lowe

(2004) Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision 60(2): 91–110.

36.

Lowry

Sünderhauf

Newman

et al . (2016) Visual place recognition: A survey. IEEE Transactions on Robotics 32(1): 1–19.

37.

Lynen

Bosse

Furgale

et al . (2014) Placeless place-recognition. In: Proceedings of the IEEE international conference on 3D vision, Tokyo, Japan, 8–11 December 2014, vol. 1, pp. 303–310. Piscataway, NJ: IEEE.

38.

McManus

Upcroft

Newman

(2015) Learning place-dependant features for long-term vision-based localisation. Autonomous Robots 39(3): 363–387.

39.

MacTavish

Barfoot

(2014) Towards hierarchical place recognition for long-term autonomy. In: Proceedings of the IEEE international conference on robotics and automation, visual place recognition in changing environments workshop, Hong Kong, China, 31 May–7 June 2014, Piscataway, NJ: IEEE.

40.

Maddern

Stewart

McManus

et al . (2014) Illumination invariant imaging: Applications in robust vision-based localisation, mapping and classification for autonomous vehicles. In: Proceedings of the IEEE international conference on robotics and automation, visual place recognition changing environments workshop, Hong Kong, China, 31 May–7 June 2014, Piscataway, NJ: IEEE.

41.

Mei

Sibley

Cummins

et al . (2009) A constant-time efficient stereo SLAM system. In: Proceedings of the British machine vision conference (eds. Cavallaro

Prince

Alexander

), 7–10 September 2009, London, UK, pp. 54.1–54.11. Durham, UK: BMVA Press.

42.

Milford

Wyeth

(2012) SeqSLAM: Visual route-based navigation for sunny summer days and stormy winter nights. In: Proceedings of the IEEE international conference on robotics and automation, Saint Paul, MN, 14–18 May 2012, pp. 1643–1649. Piscataway, NJ: IEEE.

43.

Moon

Lee

et al . (2016) Effective place scene clustering using straight lines. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Daejeon, South Korea, 9–14 October 2016, pp. 487–494. Piscataway, NJ: IEEE.

44.

Mur-Artal

Tards

(2014) Fast relocalisation and loop closing in keyframe-based SLAM. In: Proceedings of the IEEE international conference on robotics and automation, Hong Kong, China, 31 May–7 June 2014, pp. 846–853. Piscataway, NJ: IEEE.

45.

Mur-Artal

Montiel

JMM

Tardos

(2015) ORB-SLAM: A versatile and accurate monocular SLAM system. IEEE Transactions on Robotics 31(5): 1147–1163.

46.

Newman

Cole

(2006) Outdoor SLAM using visual appearance and laser ranging. In: Proceedings of the IEEE international conference on robotics and automation, Orlando, FL, 15–19 May 2006, pp. 1180–1187. Piscataway, NJ: IEEE.

47.

JYH

Yang

Davis

(2015) Exploiting local features from deep networks for image retrieval. In: Proceedings of the IEEE conference on computer vision and pattern recognition workshops, Boston, MA, 7–12 June 2015, pp. 53–61. Piscataway, NJ: IEEE.

48.

Nister

Stewenius

(2006) Scalable recognition with a vocabulary tree. In: Proceedings of the IEEE conference on computer vision and pattern recognition, New York, NY, 17–22 June 2006, vol. 2, pp. 2161–2168. Piscataway, NJ: IEEE.

49.

Piniés

Paz

Gálvez-Lpez

et al . (2010) CI-Graph simultaneous localization and mapping for three-dimensional reconstruction of large and complex environments using a multicamera system. Journal of Field Robotics 27(5): 561–586.

50.

Rawseeds (2007) The Rawseeds Project. Available at: http://www.rawseeds.org/rs/datasets (accessed 10 October 2017).

51.

Rosten

Drummond

(2006) Machine learning for high-speed corner detection. In: Leonardis

Bischof

Pinz

(eds.) Computer Vision—ECCV 2006 (Lecture Notes in Computer Science, vol. 3951). Berlin: Springer, pp. 430–443.

52.

Rublee

Rabaud

Konolige

et al . (2011) ORB: An efficient alternative to SIFT or SURF. In: Proceedings of the IEEE international conference on computer vision, Barcelona, Spain, 6–13 November 2011, pp. 2564–2571. Piscataway, NJ: IEEE.

53.

Schindler

Brown

Szeliski

(2007) City-scale location recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition, Minneapolis, MN, 17–22 June 2007. Piscataway, NJ: IEEE.

54.

Shakeri

Zhang

(2016) Illumination invariant representation of natural images for visual place recognition. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Daejeon, South Korea, 9–14 October 2016, pp. 466–472. Piscataway, NJ: IEEE.

55.

Sivic

Zisserman

(2003) Video Google: A text retrieval approach to object matching in videos. In: Proceedings of the IEEE international conference on computer vision, Nice, France, 13–16 October 2003, pp. 1470–1477. Piscataway, NJ: IEEE.

56.

Sizikova

Singh

Georgescu

et al . (2016) Enhancing place recognition using joint intensity—depth analysis and synthetic data. In: Hua

Jégou

(eds.) Computer Vision—ECCV 2016 Workshops (Lecture Notes in Computer Science, vol. 9915). Cham: Springer, pp. 901–908.

57.

Smith

Baldwin

Churchill

et al . (2009) The New College vision and laser data set. The International Journal of Robotics Research 28(5): 595–599.

58.

Strasdat

Montiel

Davison

(2010) Scale drift-aware large scale monocular SLAM (eds. Matsuoka

Durrant-Whyte

Neira

). In: Robotics: Science and systems VI, Zaragoza, Spain, 27–30 June 2010. Cambridge, MA: MIT Press.

59.

Sünderhauf

Shirazi

Dayoub

et al . (2015a) On the performance of ConvNet features for place recognition. In: Proceedings of the IEEE/RSJ international conference on intelligent robots and systems, Hamburg, Germany, 28 September–2 October 2015, pp. 4297–4304. Piscataway, NJ: IEEE.

60.

Sünderhauf

Shirazi

Jacobson

et al . (2015b) Place recognition with ConvNet landmarks: Viewpoint-robust, condition-robust, training-free. Robotics: Science and systems XII (eds. Kavraki

Hsu

Buchli

), Rome, Italy, 13–17 July 2015, accessed 10 October 2017.

61.

Thrun

Montemerlo

(2006) The graph SLAM algorithm with applications to large-scale mapping of urban structures. The International Journal of Robotics Research 25(5–6): 403–429.

62.

Valgren

Lilienthal

(2010) SIFT, SURF & seasons: Appearance-based long-term localization in outdoor environments. Robotics and Autonomous Systems 58(2): 149–156.

63.

Williams

Cummins

Neira

et al . (2009) A comparison of loop closing techniques in monocular SLAM. Robotics and Autonomous Systems 57(12): 1188–1197.

64.

Witkin

(1984) Scale-space filtering: A new approach to multi-scale description. In: Proceedings of the IEEE international conference on acoustics, speech, and signal processing, San Diego, CA, 19–21 March 1984, vol. 9, pp. 150–153. Piscataway, NJ: IEEE.

65.

Wolf

Burgard

Burkhardt

(2005) Robust vision-based localization by combining an image-retrieval system with Monte Carlo localization. IEEE Transactions on Robotics 21(2): 208–216.