{'fraction_non_alphanumeric': 0.03423853211009174, 'fraction_numerical': 0.011596330275229359, 'mean_word_length': 4.746731336988613, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Locus: LiDAR-based Place Recognition using Spatiotemporal Higher-Order Pooling

Place Recognition enables the estimation of a globally consistent map and trajectory by providing non-local constraints in Simultaneous Localisation and Mapping (SLAM). This paper presents Locus, a novel place recognition method using 3D LiDAR point clouds in large-scale environments. We propose a method for extracting and encoding topological and temporal information related to components in a scene and demonstrate how the inclusion of this auxiliary information in place description leads to more robust and discriminative scene representations. Second-order pooling along with a non-linear transform is used to aggregate these multi-level features to generate a fixed-length global descriptor, which is invariant to the permutation of input features. The proposed method outperforms state-of-the-art methods on the KITTI dataset. Furthermore, Locus is demonstrated to be robust across several challenging situations such as occlusions and viewpoint changes in 3D LiDAR point clouds. The open-source implementation is available at: https://github.com/csiro-robotics/locus .


I. INTRODUCTION
Place Recognition (PR) is an essential capability required by autonomous robots and driverless cars, which enables the recognition of previously visited places under changing viewpoints and environmental conditions. Place recognition is crucial for various applications such as loop closure detection for large-scale, global data association in Simultaneous Localization and Mapping (SLAM) or metric localization within known maps [1], [2].
In this paper, we consider the problem of place recognition based on 3D LiDAR point clouds. The majority of the current state-of-the-art LiDAR-based place recognition methods extract representations of 3D point clouds based on either local or global descriptors. Local descriptors such as keypoint features [3] often suffer from low repeatability under noise and minor changes in the environment. The demand for extracting discriminative and generalizable global descriptors from point clouds has led to the development of several different techniques [4]- [6]. However, the majority of global descriptors are not robust to viewpoint variations, occlusions and dynamic scenes [7]. A potential reason for this fragility is that these methods are inherently not capable of capturing topological and temporal interactions between different components in the scene. Such auxiliary information is vital for the construction of robust and discriminative representations since a higher-level understanding is needed to distinguish between different scenes of similar structure.
To this end, we propose a novel place recognition method (named Locus) which effectively exploits multi-level features for global place description using 3D LiDAR data. We define multiple levels of feature representations for each point cloud frame. A point cloud frame is defined as the points accumulated from a sweep of the LiDAR [8]. First, segment features are extracted to encode structural information of each point cloud frame. The segment-based representation leverages from the advantages of both local and global representations while not suffering from their individual drawbacks. Compared to local keypoint based representations, they are more descriptive and more robust to noise and changing environments. Next, spatial feature pooling encodes topological relationships between segments within a point cloud frame. Capturing topological relationships between components of a scene enables discrimination between scenes of similar composition but different arrangement.
Finally, temporal feature pooling encodes co-occurrences of segments in the past k t point cloud frames providing robustness to sensor motion and dynamic objects. Once multilevel features are extracted, second-order pooling aggregates information of local features over a point cloud frame to form a holistic representation for place recognition. Second-order pooling captures the multiplicative interactions between the multi-level features and outputs a fixed-length descriptor which is invariant to the number and permutation of the input features. Furthermore, the fixed dimension of the global descriptor enables maintaining the computational complexity.
Our main contributions are summarised as follows: • We introduce multi-level features which encode structural appearance, topological relationships and temporal correspondences related to components in a scene. • We formulate the generation of a global descriptor which encodes these multi-level features into a single viewpoint invariant representation using second-order pooling and demonstrate how these multi-level features contribute to place recognition performance. • Our proposed method (Locus) outperforms the state-ofthe-art place recognition methods on the KITTI dataset. • We quantitatively evaluate the robustness of our Locus method on a variety of challenging scenarios such as viewpoint changes and occlusion. Fig. 1: The overall framework of the proposed Locus method. Segments extracted from a LiDAR point cloud frame are described using two complementary sets of features. One feature describes the structural appearance of a segment while the other encodes topological and temporal information related to a segment. The two sets of features are aggregated using second-order pooling (O2P) followed by a Power-Euclidean transform (PE) to obtain a global descriptor of the point cloud.

A. Point cloud representation and descriptor generation
To address the challenge of place recognition, the scenelevel point cloud is often encoded in three different ways; a set of local descriptors, a single global descriptor or a set of object/segment descriptors. Local descriptor based methods first detect a set of keypoints in the point cloud and then form local descriptors by encoding information in each keypoint neighbourhood [3], [9]. Local descriptors and keypoint detection suffer from low repeatability in noisy point clouds and changing environments.
Global descriptors aim to describe the entire point cloud by a single vector representation. M2DP [4] generates a global descriptor by projecting the points into multiple 2D planes and calculating density signatures. PointNetVLAD [5] extracts a global descriptor using an end-to-end process based on PointNet and NetVLAD [10]. PointNetVLAD ignores the spatial distribution of features and hence lacks descriptive power. LPD-Net [11] addresses the limitation of PointNetVLAD by using adaptive local feature extraction along with a graph-based neighborhood aggregation module. Recently, DH3D [12] proposed a network which learns both the keypoint detection and local description and generates a global descriptor using NetVLAD. The aforementioned global descriptors do not demonstrate rotational-invariance and often fail upon reverse revisits.
The current state-of-the-art consists of several rotationinvariant global descriptors. ScanContext [6] records the maximum height of points in a 2D grid-map of the scene and computes pairwise descriptor distances by comparing distances to all column shifted variants of the query descriptor to achieve rotational-invariance. Intensity ScanContext [13] extends ScanContext by including the intensity return of the LiDAR sensor. The ScanContext and its variants are not capable of capturing scene composition or topological relationships and rely on expensive distance calculation to ensure rotational-invariance.
Recently, Kong et al. [14] represented point clouds as a semantic graph and recognize places using a graph similarity network. Their network is capable of capturing topological and semantic information from the point cloud and also achieves rotational-invariance along with state-of-the-art performance. However, due to the use of semantic segmentation, their method suffers from the following two bottlenecks. First, it is dependant on the existence of pre-defined semantic classes in the test dataset (i.e., domain gap problem). Second, since each segment is only represented by its class label, the method is not capable of differentiating between two segments of the same class and thus loses valuable information related to intra-class variations.
Euclidean segment based representations [7] are less affected by the aforementioned drawbacks while still being able to capture topological and semantic information of the components in a scene. SegMatch [7] and SegMap [15] address the challenges of local and global descriptors by constructing a global map along the trajectory and performs recognition via segment-wise kNN retrieval on this map followed by a geometric consistency check. In this paper, we also leverage from segment descriptors for point cloud encoding but we avoid the construction of a global map and instead treat place recognition as a retrieval problem similar to recent LiDAR-based place recognition research [5], [6], [13], [14]. In this sense, we avoid segment-wise kNN search and construct a global descriptor through the aggregation of multi-level segment features.

B. Feature aggregation
Bag-of-Words (BoW) [16] and its higher-order variants (Vector of Locally Aggregated Descriptors (VLAD) [17], NetVLAD [10], Fisher Vector (FV) [18]) are popular methods in many retrieval tasks which construct global descriptors by aggregating local descriptors using zeroth, first or second order statistics respectively. These codebook-based aggregation methods require a preprocessing step to learn the codebook (a standard BoW, cluster centers in VLAD and Gaussian Mixture Models (GMM) in FV) and do not transfer well to unseen environments.
Other higher-order aggregation methods such as Second Order Pooling (O2P) [19] do not require such pre-processing steps and and hence enables to be used for online place recognition in unseen environments. They also tend to be more efficient in run-time since the description stage does not require finding the nearest codebook word for each feature. Additionally, O2P methods allow the aggregation of complementary features [20] while maintaining a fixedlength descriptor without violating permutation invariance. In this paper, we propose to use second-order pooling to aggregate multiple levels of feature representations (structural, topological and temporal) into a fixed-length global descriptor for place recognition.

C. Incorporating temporal information
In place recognition, temporal information has been used almost exclusively in the retrieval stage. In visual place recognition (VPR), SeqSLAM [21] incorporated sequential information by comparing feature similarity over time and demonstrated dramatic performance improvement when dealing with changing appearance. Lynen et al. [22] modeled sequential retrieval as a probability density estimation in votes versus travel distance space. More recently, SeqLPD [23] extended LPD-Net with SeqSLAM for LiDAR-based place recognition. Our method differs from these sequential retrieval methods by incorporating temporal information in the place description stage instead. Recently, in VPR, Delta descriptors [24] outlined how visual sequentialrepresentation provides inherent robustness to variations in camera motion and environmental changes.

III. METHOD
This section describes our proposed method (named Locus) for LiDAR-based place description including the segment based representation of the point cloud, the generation of the multi-level features and their second-order aggregation (see Fig. 1).

A. Segment-based representation
Segments are defined as Euclidean clusters of points in the point cloud representation. Our segment extraction is performed similar to the SegMatch implementation [7] by first removing the ground plane and then extracting Euclidean clusters of points. The maximum Euclidean distance between two neighbouring points in the same segment is set to 0.2m and the segments contain a minimum of 100 and a maximum of 15000 points. Thus, each input point cloud P ∈ R N ×3 is represented by a set of segments S = {s 1 , .., s m }, where s i ∈ R Ni×3 , and the number of segments m varies depending on the environment and range of the point cloud.
For each segment, a compact deep feature which encodes the structural appearance of the segment is obtained using the SegMap-CNN network proposed in [15]. The network represents each segment in a voxel grid of 32x32x16 of which the voxel sizes (0.1m by default) are scaled in order to fit larger segments. The description network consists of three 3D convolutional layers plus max-pool layers followed by two fully connected layers. For a given set of m segments S, it outputs a set of compact features F a = {f a1 , .., f am } (where f ai = f a (s i ) ∈ R d , d = 64) which discriminates segments based on structural appearance.

B. Spatiotemporal Pooling
Incorporating topological and temporal information in place description has many advantages when dealing with changing environments and varying sensor motion. With the aim of encoding this information, we compute a complimentary set of features F b ∈ R m×d for each point cloud frame P n , in addition to the structural appearance features F a ∈ R m×d described in section III-A. This is achieved via two stages of feature pooling: spatial and temporal.
Feature pooling computes a new feature for a segment by taking the weighted average of features of all related segments. Encoding topological information is achieved via feature pooling based on spatial relationships within a point cloud frame. Temporal information is encoded via pooling features based on temporal correspondences across multiple point cloud frames. For a query segment s Pn i from the current point cloud frame P n , we find topological relationships and temporal correspondences with all other segments s P l j ∈ S n,kt from the current frame and k t frames into the immediate past, S n,kt = {S Pn , .., S P n−k t }, S P l = {s P l 1 , .., s P l m l }, (1) If a segment s P l j is spatially or temporally related to the query segment s Pn i , its structural appearance feature f a (s P l j ) is included in the feature pooling of the query segment.
1) Spatial Feature Pooling: We define spatial relationships between segments through a directed graph G = (V, E). Vertices V = {1, .., m} represent the segments S = {s 1 , .., s m } in the current point cloud frame and edges E ⊆ V × V represent which segments relate to which other segments. G is constructed as a kNN graph where each segment is connected to its k s nearest neighbours (k s = 5) and the distance between segments is calculated using the minimum translational distance (MTD) [25] between the convex hulls of the segments. We use the QuickHull algorithm [26] to compute convex hulls. Since the segment extraction process in Section III-A guarantees that segments do not overlap, the MTD (D) can be computed as follows, where p ix − p jy represents Euclidean distance between points p ix , p jy ∈ R 3 andŝ = QuickHull(s). The spatial feature pooling for segment s i is then carried out as, Algorithm 1: Estimate temporal segment correspondences from frame P l to P l−1 Result: Corresponding segment indices S c ∈ R m S P l , S P l−1 ∈ R m ×n ×3 // segments; F P l a , F P l−1 a ∈ R m ×d // features; C P l , C P l−1 ∈ R m ×4 // segment centroids; T l−1 l ∈ SE(3) // relative pose from P l−1 to P l ; for s i ∈ S P l do f ai , c l i // feature, centroid of segment s i in P l ; where β = 0.1 is a smoothing factor. The spatiallypooled feature Φ(s i ) is essentially a weighted average of the structural-appearance features (f a ) of the 5 closest segments to segment s i . This captures information on the immediate neighbourhood of s i and thus contributes towards encoding topological information in the scene.
2) Temporal Feature Pooling: Temporal relationships are defined by segment correspondences between frames. The segment s Pn i in the current point cloud frame P n will only relate to its corresponding segment in each of the k t previous frames (k t = 3). Segment correspondence indices S c are calculated as in Algorithm 1 iteratively k t times.
First kN N finds the indices of the k nearest neighbours of f ai from the set of features F P l−1 a of the previous frame. Next, rN N finds the indices of nearest neighbor centroids from the previous frame within a radius r = 1m. To increase accuracy, the rN N search takes into account the the sensor's relative pose across frames represented by the homogeneous transformation T l−1 l . Finally, common elements in both nearest neighbour sets are found using the intersection function and the function arg min finds the index of the segment which minimises both feature-space and Euclideanspace distance.
For the selected segment s Pn i in the current frame, the set of corresponding segments can be obtained from S c as {s Pn−1 i , .., s P n−kc i } = {S n,kt (j) : j ∈ S c }. We note that k c ≤ k t since correspondences can be lost between frames (when a segment which minimises both feature space and Euclidean-space distance is not available in the previous frame). The temporal pooling for s Pn i is then carried out as, Ψ(s i ) = j∈Sc ψ(i, j)f a (s j ),s j = S n,kt (j), where ψ(i, j) is calculated similar to φ(i, j) in Eq. 4 with D(s i , s j ) replaced by f a (s i ) − f a (s j ) and k is sampled from S c . The aggregation of features across multiple sequential frames essentially magnifies the weight of features corresponding to highly repeatable segments (segments which are extracted at every frame in the sequence and mapped to a similar point in the f a feature space each time) and thus, inherently down-weights non-repeatable segments.
The final sptiotemporal feature f b is obtained as the average of a spatially-pooled feature Φ(s i ) and a temporallypooled feature Ψ(s i ), C. Second-order pooling Given a set of segments S = {s 1 , .., s m } and two complementary sets of features F a ∈ R m×d and F b ∈ R m×d the second-order pooling F O2 of the features is defined as, where F O2 is a matrix with elements F O2 xy (1 ≤ x, y ≤ d) and f o2 (s) = f a (s)f b (s) T ∈ R d×d is the outer product of the two complementary features of segment s (f a (s), f b (s) ∈ R d ). This accounts to taking the element-wise maximum of the second-order features of all segments in the scene.
In order to make the scene descriptor matrix F O2 more discriminative, it is decomposed in to singular values as F O2 = U λV and transformed non-linearly using the Power-Euclidean (PE) transform [27] [28] into F O2 α by raising each of its Eigen values by a power of α as follows, where α = 0.5. The matrix F O2 α is flattened and normalized to obtain the final global descriptor vector g ∈ R d 2 . The aggregation of multi-level features using higher-order pooling has multiple advantages for segment-based place description. First, it allows the encoding of complementary features for each segment thus enabling the incorporation of structural-appearance information along with topological and temporal information. Second, even though different point clouds will consist of varying number of segments m of varying sizes N i , the output dimension of the aggregated feature is fixed and therefore computational time can be greatly reduced. Finally, the aggregated feature is invariant to the permutation of its inputs, which results in a viewpoint invariant global descriptor for place recognition.

A. Evaluation criteria
We evaluate performance using the Precision-Recall curve and its scalar metric: the maximum F 1 score (F 1 max ). Additionally, we use the Extended Precision (EP ) metric proposed in [29] as it highlights the maximum recall at 100% precision which is vital for robustness in place recognition. For Precision (P) and Recall (R), the F 1 max and EP scores are defined as,  where τ is the threshold for positive prediction, P R0 is the Precision at minimum Recall, and R P 100 is the maximum Recall at 100% Precision. Retrieval is performed based on the comparison of the cosine distance of the query descriptor with a database of descriptors of previously visited places. Inline with the evaluation criteria of [14], previous entries adjacent to the query by less than 30s time difference are excluded from search to avoid matching to the same instance. The top-1 retrieval is considered a positive if the associated distance to query is less than the test threshold (τ ). A positive retrieval is considered a true-positive if it is less than 3m from the ground truth pose of the query and a false-positive if it is greater than 20m away to maintain consistency with the evaluation in [14].

B. Dataset
Evaluation is performed on the KITTI odometry dataset [8] which consists of Velodyne HDL-64E LiDAR scans collected from a moving vehicle in multiple dynamic urban environments in Karlsruhe, Germany. In line with the most recent evaluation on this dataset [14], we evaluate on sequences 00, 02, 05, 06, 07, and 08.

V. RESULTS
In this section, we demonstrate the contribution of each component in our proposed method. We also provide quantitative and qualitative results to validate our method in comparison to state-of-the-art methods and we quantitatively evaluate the robustness our proposed method against viewpoint changes and sensor occlusion.

A. Contribution of individual components
We investigate the contributions of each component (ablation study) of our proposed method using F 1 max and EP on KITTI sequence 08. First, we demonstrate the importance of the Power Euclidean (PE) non-linear transform in our second-order pooling. For the generation of feature f a , we use the model trained on extracted segments from the sequences 05 and 06 [15]. The most basic second-order pooling method (O2P) is the aggregation of second-order statistics of the same feature (Eq. 7 with f b = f a ). This can be extended with the Power Euclidean (PE) non-linear transform to get O2P+PE (Eq. 8 with f b = f a ). The O2P+PE shows a dramatic increase of 44.7% F 1 max (from 0.550 to 0.796) and and improvement of 32.4% EP (from 0.564 to 0.739) when including the non-linear transform. This demonstrates the importance of PE for obtaining discriminative descriptors. The rest of the evaluation uses the O2P+PE feature pooling and compares the contribution of each input feature type. The input f a is the structural appearance feature and the input feature f b is varied across all multi-level feature types. Table I shows the respective performance for each of the following cases: Table I demonstrates that pooling information from complementary features improves the place recognition performance. Furthermore, incorporating topological or temporal information individually makes the final descriptor more discriminative and improves F 1 max by 12.4% and 13.1% respectively. The best performance of our proposed method is achieved when incorporating both topological and temporal information along with the structural appearance (+ 17% F 1 max ).

B. Comparison to State-of-the-Art
In this section, we compare the results of our method against other state-of-the-art results. Table II shows summary comparison of F 1 max scores. Locus outperforms all other methods with the highest mean F 1 max score (0.942). Our method sets a new state-of-the-art place recognition performance on KITTI dataset. Locus achieves a significant improvement on the challenging sequence 08 which consists of number of reverse or orthogonal revisits thereby demonstrating the robustness to viewpoint variations.
The Precision-Recall curves of Locus across all sequences are presented in Fig. 2. The curves highlight that the performance of Locus on sequence 02 is significantly poor compared to other sequences. As depicted in Fig. 3, sequence 02 has a long stretch of road with many false negatives. This road consists of non-descriptive point clouds where the segment extraction process fails to obtain a high number of descriptive segments.
The qualitative visualization of our method at R P 100 (i.e., maximum Recall at 100% Precision) is shown in Fig.  3. The figure shows the locations of true positive (red) and false negative (black) retrievals along the trajectory. This demonstrates that our method is capable of obtaining accurate retrievals in a wide range of environment and revisit types. We observe that most failure cases (black dots) occur   [14] with the same evaluation criteria. PointNetVLAD* is the PointNetVLAD method retrained on KITTI [14]. near intersections.

C. Robustness tests
We evaluate the robustness of our method against the state-of-the-art on a variety of challenging scenarios which simulate real-word adverse conditions. We simulate these adverse conditions by introducing a set of distortions to the input point cloud. Performance is compared based on the F 1 max metric on the same KITTI sequences.
1) Viewpoint changes: We simulate viewpoint changes by rotating point clouds about the z-axis with a random angle. The change in mean F 1 max over all sequences on this test compared to the normal results was -0.007 for our method. The respective change for ScanContext was +0.002 and for SemGraph-RN it was -0.003 as presented in [14]. Locus, ScanContext and SemGraph-RN show less than 1% difference implying that random rotation of the input point cloud does not effect the final performance of these methods. Other methods such as M2DP, PointNetVLAD have been shown not to be rotation invariant as mentioned in [14].
2) Occlusion: This test aims to simulate occlusion of the LiDAR where the field-of-view of the sensor can be greatly reduced due to nearby dynamic objects or self-occlusion. We extend the occlusion test in [14] which only considered occlusions of 30°by evaluating performance of various occlusion angles θ occ from 0°up to 180°. The occlusion test consists of removing all points which lie within a sector of a randomly selected azimuth. We compare our method with ScanContext (SC) [6], which achieved the second best overall performance in the Table II. ScanContext (SC) mean F 1 max performance drops by more than 20% at 45°occlusion and around 50% at 90°occlusion. Our method shows small performance degradation of 3.2% at 45°occlusion and 9.98% at 90°occlusion. Our method outperforms ScanContext (SC) with a large margin of 45.2% mean F 1 max at 90°occlusion. Also note that in our method, the F 1 max of sequences 00

VI. CONCLUSION
In this paper, we presented Locus, a novel LiDAR-based place recognition method for large-scale environments. We presented the advantages of scene representation via the aggregation of multi-level features related to components in a scene. We quantitatively showed how the inclusion of topological and temporal information in the description stage leads to an improvement in final place recognition performance. We formulated the generation of a global descriptor which incorporates all multi-level features without violating rotational-invariance. We validated our method through evaluation on the KITTI dataset where it surpassed the stateof-the art. Furthermore, we demonstrated the robustness of Locus against viewpoint changes and occlusion.