PaperlayerView exact revision on arXiv

Source-linked AI summary

Scan Context++: Structural Place Recognition Robust to Rotation and Lateral Variations in Urban Environments

Giseop Kim, Sunwook Choi, Ayoung Kim

arXiv:2109.13494v1cs.RO

TL;DR

Range-sensor place recognition lacks a solid solution for global localization compared with visual methods. This paper proposes Scan Context++, a descriptor robust to rotational and lateral changes, supporting topological retrieval, 1-DOF localization initialization, and real-time CPU operation.

  • Problem

    Range-sensor place recognition still lacks a solid solution for global localization, despite extensive progress in visual place recognition.

  • Method

    Scan Context++ augments two complementary scan-context sub-descriptors to provide rotational and lateral robustness, then estimates a 1-DOF alignment for metric refinement.

  • Results

    The method achieves real-time CPU performance up to 100 Hz, averaging 7.4 ms on KITTI 00, while providing discriminable place recognition without prior knowledge.

  • Takeaways & Limitations

    The proposed module combines global place retrieval with semi-metric localization and can serve as a kidnapped-robot wake-up global localizer.

Abstract

from arXiv · show

Place recognition is a key module in robotic navigation. The existing line of studies mostly focuses on visual place recognition to recognize previously visited places solely based on their appearance. In this paper, we address structural place recognition by recognizing a place based on structural appearance, namely from range sensors. Extending our previous work on a rotation invariant spatial descriptor, the proposed descriptor completes a generic descriptor robust to both rotation (heading) and translation when roll-pitch motions are not severe. We introduce two sub-descriptors and enable topological place retrieval followed by the 1-DOF semi-metric localization thereby bridging the gap between topological place retrieval and metric localization. The proposed method has been evaluated thoroughly in terms of environmental complexity and scale. The source code is available and can easily be integrated into existing LiDAR simultaneous localization and mapping (SLAM).

I. INTRODUCTION

The paper targets structural place recognition from range sensors, addressing missing rotational and lateral invariance while connecting place retrieval with metric localization.

  • Motivation: Range-sensor place recognition remains less mature than visual recognition, despite structural information being effective in outdoor environments.Unstructured, unordered, sparse measurements make range-sensor data harder to consume, and existing methods rarely achieve structural invariance.
  • Contributions: The method extends Scan Context to provide simultaneous robustness to rotational and lateral changes in urban environments.The extension uses Scan Context augmentation based on an urban road assumption, addressing inevitable lane-level changes.
  • Contributions: It combines topological place retrieval with semi-metric localization by providing a retrieved map index and a 1-DOF initial guess for metric refinement.The initial guess can support refinement methods such as Iterated Closest Point (ICP).
  • Contributions: The proposed system uses compact sub-descriptors and tree search to reduce retrieval cost and operate in real time on CPU.It supports up to 100 Hz, with an average runtime of 7.4 ms on KITTI 00, without requiring a GPU.
  • Evaluation: The work evaluates structural place recognition across diverse test scenarios, including in-session and multi-session settings, using distribution-recall curves alongside precision-recall analysis.Distribution-recall curves measure recall together with the diversity of loop-closure matches.

2) Radar:

The paper frames structural place recognition around variations caused by sensors, environments, and robot motion, then describes a Scan Context pipeline for compact range-sensor representation and retrieval.

  • External Factors: LiDAR place recognition must address structural diversity, although prior evaluations often used less complex environments with few dynamic objects or viewpoint changes.The paper distinguishes increasing descriptor discriminability from defining and overcoming structural diversity.
  • External Factors: Robot-induced rotation, translation, and scale changes alter sensor-coordinate measurements, while dynamic objects and construction can change observed structures over time.Scale variation arises from changes in point-cloud density with sensing distance.
  • External Factors: LiDAR data is unstructured and its sensing characteristics vary with range, ray count, resolution, and field of view, motivating invariance to sensor specifications.These characteristics differ from the highly structured data obtained by cameras.
  • Pipeline: The recognition system comprises place description and place recognition, with retrieval, semi-metric localization, and verification inside the recognition module.The overall pipeline is illustrated in Fig. 2.
  • Descriptor: The Scan Context Descriptor projects a downsampled 3D LiDAR scan into discretized 2D BEV bins using polar or Cartesian coordinates and scalar bin encoding.The descriptor shape depends on the region of interest and partitioning resolution; invariance arises from bin encoding and distance functions.

A. Motivation

The method is motivated by urban revisit motion, where rotation and lateral translation challenge structural place recognition. It constructs compact range-measurement descriptors from partitioned 3D LiDAR data using polar and Cartesian coordinate frames.

  • Urban vehicle motion is locally two-dimensional and typically follows at most two disjoint directions, motivating polar and Cartesian coordinate frames.
  • The descriptor partitions a downsampled 3D LiDAR point cloud within a region of interest, projects points into 2D polar or Cartesian space, and assigns scalar values to bins.The input is assumed to be a single 3D LiDAR scan.
  • The aligning axis supports column-wise pre-alignment for rough relative-pose estimation, while the retrieval axis organizes the descriptor; their choice yields Polar Context or Cart Context.
  • Polar Context uses azimuth as its aligning axis for rotational robustness, whereas Cart Context uses lateral position as its aligning axis for lateral-translation invariance.
  • The descriptor is generic across range-measurement distributions and data types, including point clouds and radar, through an appropriate bin encoding function.
  • Each bin stores a representative scalar, with maximum point height selected to summarize urban structure and reduce sparsity variation from sensing conditions.The encoding function is intended to be invariant to internal factors and independent of sensor specifications.
  • Heterogeneous LiDAR place recognition with different mapper and localizer mounting heights remains outside the paper’s scope because it violates the encoding requirement.

D. Scan Context Descriptor

The Scan Context Descriptor represents surrounding structure as a matrix whose axes determine the invariance and alignment behavior. Combining polar and Cartesian descriptors with column-shift matching addresses simultaneous rotational and lateral variation.

  • Each Scan Context Descriptor accumulates bin features into a matrix whose rows follow the retrieval axis and columns follow the aligning axis, representing the surrounding structural skyline.
  • Polar Context supports rotation-invariant recognition because rotational changes appear as column-wise shifts.
  • Cart Context handles lateral variation, including lane changes, because lateral translation also appears as column-wise shifts.
  • Because each descriptor has only one aligning-axis dimension, Polar Context and Cart Context can be limited under simultaneous rotation and translation; hallucinating the retrieval axis provides robustness in both directions.
  • Descriptor proximity is computed from column-wise cosine similarities, whose sum is normalized by the number of columns.
  • The final distance minimizes this similarity-based distance over all column shifts of the query descriptor, aligning rotational variance in Polar Context and lateral displacement in Cart Context.

F. Sub-descriptors

The method introduces retrieval and aligning sub-descriptors to reduce global-search cost, support semi-metric localization, and refine matches with full-descriptor comparison.

  • F. Sub-descriptors: Two sub-descriptors summarize the full SCD along rows and columns for place recognition and semi-metric localization.The retrieval key supports place retrieval, while the aligning key supports pre-alignment.
  • F. Sub-descriptors: The retrieval key is a row-dimension vector formed by applying a column-to-scalar function to each SCD row.The function must be permutation invariant, making the key unaffected by column order from rotation or lane changes.
  • F. Sub-descriptors: The aligning key is a column-dimension vector that summarizes each column, using the L1 norm in the experiments.It is used to estimate the best column shift before full SCD comparison.
  • F. Sub-descriptors: The pipeline retrieves places with a retrieval key, pre-aligns them using an aligning key, then compares full SCDs for refinement and quality assessment.A k-d tree enables fast search, and the reported implementation uses the best candidate, k = 1.
  • F. Sub-descriptors: The reduced search can be insecure when column variation is poor or the upper vertical FOV is low, although a tight neighbor choice performed well empirically.The authors identify diversified bin encoding as one possible way to improve discernibility.

D. Augmentation of the Scan Context Descriptor

The descriptor is augmented to address combined rotational and lateral revisit changes, including lane shifts and reversed headings, while retaining a lightweight retrieval pipeline.

  • D. Augmentation of the Scan Context Descriptor: Polar and Cartesian descriptors lose different motion components, making combined rotational and translational revisits challenging.Polar Context loses translation, whereas Cart Context lacks rotation.
  • D. Augmentation of the Scan Context Descriptor: Polar Context augmentation creates virtual lateral viewpoints and recomputes descriptors for laterally displaced point clouds.The experiments consider two virtual vehicle positions separated by 2 m, producing two additional augmented Polar Context descriptors.
  • D. Augmentation of the Scan Context Descriptor: Cart Context augmentation applies sequential flips on both descriptor axes to incorporate rotational robustness.The resulting descriptor is called Augmented Cart Context.
  • D. Augmentation of the Scan Context Descriptor: A single k-d tree containing original and augmented keys outperforms using multiple k-d trees in the reported matching setup.Augmented descriptors retain the same place index as their originals.
  • D. Augmentation of the Scan Context Descriptor: The augmentation and periodic tree-maintenance costs are reported as negligible, while retrieval remains lightweight.Neighbor search is identified as the most computationally demanding module.
  • D. Augmentation of the Scan Context Descriptor: Pre-alignment reduces comparison cost from O(N^3) to O(N^2) when the descriptor dimensions are approximately equal.The general reduction is from O(NA · NR · NA) to O(NA · NR · 1).

F. Implementation Details

The evaluation uses eight sequences from four public datasets spanning varied urban settings, revisit geometries, scales, and temporal conditions.

  • F. Implementation Details: Eight sequences from four public datasets are used to evaluate place recognition across diverse environments.The datasets are KITTI Odometry, MulRan, Oxford Radar RobotCar, and NAVER LABS.
  • F. Implementation Details: The selected datasets include campus, riverside, planned-city, radar-robot-car, and highly urbanized road environments.The trajectories illustrate differences in scale, shape, and surrounding structures.
  • F. Implementation Details: MulRan Riverside 02 contains repeated roadside structures and multiple revisit-phase lane changes for testing lateral robustness.The sequence is used to quantitatively assess performance under lateral changes.
  • F. Implementation Details: Sejong evaluates multi-session loop closure and temporal robustness across recordings from June and August 2019.Its planned-city environment exhibits slowly varying structural changes over a relatively short period.
  • F. Implementation Details: Pangyo is a 31 km urban trajectory with tall buildings, wide roads, and multiple revisits per place.More than half of same-direction revisits occur in different lanes with rotation changes, supporting comprehensive and scalability evaluation.
  • F. Implementation Details: A detected place is counted as correct when the query and candidate are less than 8 m apart.Measurements are sampled every 1–1.5 m to reduce redundant stopped frames and equalize place contributions.

C. Evaluation Metrics

Evaluation combines precision-recall and maximum F1 with distribution-recall analysis so loop-closure quality reflects both detection performance and revisit diversity.

  • C. Evaluation Metrics: Precision-recall and maximum F1 are used as the main detection metrics.Maximum F1 is the harmonic mean of precision and recall.
  • C. Evaluation Metrics: Distribution-recall curves measure whether detected loop closures are distributed similarly to ground-truth revisits across translational and rotational variation.The ground-truth distribution is represented as a histogram of loop-closure events.
  • C. Evaluation Metrics: Lower KL-D indicates better distributional performance, while higher precision and F1 indicate better detection performance.The method uses the ground-truth loop-closure distribution as the reference for relative divergence.
  • C. Evaluation Metrics: A distributionally better loop-closure detector can provide more spatially unbiased localization even with fewer detected revisits.The authors motivate distributional evaluation because not all recalls are equally valuable for SLAM loop closure.
  • C. Evaluation Metrics: The evaluation compares the proposed descriptors with M2DP and SegMatch using sensor-agnostic CPU implementations.The proposed evaluation includes PC, CC, A-PC, and A-CC, with one retrieved candidate and thresholded SCD distance curves.

3) SegMatch:

The evaluation compares SegMatch with Scan Context variants across sequences characterized by rotational, lateral, composite, and small structural variance. SegMatch can recognize selected composite loops, but its odometry dependence constrains broader comparisons.

  • 3) SegMatch:: SegMatch uses eigenvalue-based segment features, excludes its learning-based version, and requires odometry information during place recognition.The comparison uses the KITTI-oriented eigenvalue configuration and varies the segment-feature distance threshold.
  • 3) SegMatch:: Across the evaluation, routes are color-coded by revisit type to assess recognition under multiple structural variations.The analysis emphasizes that coping with multiple place variations is important for loop detection and global localization.
  • 3) SegMatch:: On KITTI 00, M2DP achieved the highest precision and recall, while SegMatch recognized a composite-change loop that the other methods missed.SegMatch had lower recall, but its recognition distribution was sufficient to construct a globally consistent map.
  • 3) SegMatch:: On MulRan KAIST 03, all methods successfully recognized loops because the campus sequence had few lane changes and dynamic objects.PC and CC also performed similarly on KITTI 00 because that sequence had little rotational or lane-change variance.
  • 3) SegMatch:: KITTI 08 primarily tests rotational variance, while Riverside 02 tests lateral variance and Pangyo combines several variance types.The corresponding figure summaries identify PC as strongest for KITTI 08, CC for Riverside 02, and quadrant-based analysis for Pangyo.

1) KITTI 08:

The experiments examine rotational, lateral, and composite revisit changes, including single-session and multi-session settings. Augmentation improves recognition under composite variance, while the method also estimates a one-dimensional relative pose for metric refinement.

  • 1) KITTI 08:: KITTI 08 contains reverse revisits with frequent simultaneous lane changes, causing severe rotational variance that favors PC precision over M2DP and CC.SegMatch provides enough precision but limited recall, and A-CC is examined for augmentation-related improvement.
  • 1) KITTI 08:: CC outperformed competing methods by a large margin on Riverside 02, where same-direction revisits included multiple lane changes.CC also produced few false positives in challenging regions, while A-PC improved PC under lateral variance.
  • 1) KITTI 08:: Augmentation improved precision at higher recalls under concurrent rotational and lateral variance, with A-CC generally exceeding A-PC.Without augmentation, PC and CC were sharply limited at a recall corresponding to non-same-direction revisits.
  • 1) KITTI 08:: CC exceeded PC in precision and maximum F1 score, but PC detected difficult loops; A-CC alleviated CC’s restricted distribution performance.The distribution-recall view distinguishes concentrated easy-region matches from broader loop coverage.
  • 1) KITTI 08:: On Pangyo, A-PC performed best for rotational change, M2DP was meaningful for lateral variance, and A-CC was strongest under concurrent variance.The sequence includes sporadic lane changes accompanied by rotational changes, representing composite urban revisits.
  • 1) KITTI 08:: In multi-session tests, CC performed best overall on the challenging Sejong pair with multiple lane changes, while augmentation was excluded from that evaluation.The Oxford pair was successfully handled by all methods, whereas M2DP on Sejong included wrong loop closures.
  • 1) KITTI 08:: The method estimates one-dimensional relative rotation or lateral displacement, averaging 1.03° for A-PC and 0.84 m for A-CC on Pangyo.The estimate is intended to initialize subsequent metric refinement after topological retrieval.

F. External Module Dependence and SLAM Integration

The system is designed as a lightweight, stand-alone global localizer that does not require prior odometry and can integrate with keyframe-based LiDAR SLAM. Its CPU execution is fast, with periodic map-dependent tree rebuilding as the main cost.

  • F. External Module Dependence and SLAM Integration: The proposed global localizer avoids external prior information such as odometry, unlike methods whose recognition performance depends on odometry quality.SegMatch particularly struggles in harsh environments when reliable frame-to-frame odometry is unavailable.
  • F. External Module Dependence and SLAM Integration: The implementation is provided as a lightweight C++ and header-file pair that can be combined with keyframe-based pose-graph SLAM.The accompanying SC-LeGO-LOAM system integrates Scan Context loop detection with iSAM2 pose-graph optimization.
  • F. External Module Dependence and SLAM Integration: The mean computational time is less than 10 ms, with periodic k-d tree reconstruction identified as the most time-consuming task.The reported timing uses real-time LiDAR SLAM on an Intel i9-9900 CPU with 64G RAM and conservatively rebuilds the tree every 10 seconds.
  • F. External Module Dependence and SLAM Integration: Overall computation is O(1), while periodic batch tree rebuilding scales linearly with map size O(N).Pangyo executes faster than KITTI 00 because its 32-ray LiDAR produces fewer points.
  • F. External Module Dependence and SLAM Integration: The reported KITTI 00 mean execution time is 7.36 ms, and module costs include downsampling, descriptor generation, tree reconstruction, and nearest-neighbor distance calculation.The figure reports computational costs for the individual processing modules.
  • F. External Module Dependence and SLAM Integration: A-PC adds description cost during augmentation without extra retrieval-key management, while PointNetVLAD is more expensive despite using a GPU.Timing comparisons use Matlab for the proposed method and M2DP, while SegMatch timing comes from prior work.

A. Descriptor Resolution

Ablations examine descriptor resolution, candidate count, retrieval strategy, similarity verification, correctness thresholds, perturbations, and learned-method comparisons. The results support compact retrieval with full-descriptor verification, while robustness declines under stronger roll-pitch perturbations.

  • A. Descriptor Resolution: Lower descriptor resolution yielded better performance on Oxford, so the baseline resolution was used thereafter.The comparison evaluates performance as descriptor resolution changes.
  • A. Descriptor Resolution: Using k = 1 retrieval candidate was selected because increasing candidates reduced spatial discernibility rather than improving performance.Only one candidate is retained after full-descriptor false-positive rejection in the main pipeline.
  • A. Descriptor Resolution: Retrieval-key search had negligible performance difference from full-descriptor brute force, while brute force required O(n) computation and nearly 1 second for 4500 KITTI 00 frames.The comparison uses area under the precision-recall curve as its measure.
  • A. Descriptor Resolution: Full-descriptor similarity verification improved precision for augmented Scan Context and supported its semi-metric localization capability.The additional similarity score removes less accurate matches after retrieval.
  • A. Descriptor Resolution: An 8 m correctness threshold was used in the main evaluations because tighter criteria can count difficult lateral queries as correct rejections and complicate reversed-revisit localization.The threshold ablation reports performance as an AUC comparison.
  • A. Descriptor Resolution: Roll-pitch perturbation simulations caused performance losses for all methods, with clearer degradation as perturbation increased on Riverside 02.The tested pre-rotation ranges were [−5°, 5°], [−10°, 10°], and [−15°, 15°].
  • A. Descriptor Resolution: On hand-held LiDAR data, the proposed method outperformed M2DP by a large margin, while mild walking-induced roll-pitch and height perturbations were acceptable.The experiment used the KA Urban Campus 1 sequence with approximately 70° front horizontal field of view.
  • A. Descriptor Resolution: PointNetVLAD was comparable under little variance but failed as rotational and translational variation increased, while SegMap showed weaker generalization than SegMatch.The comparison uses pretrained weights released by the authors.

F. Failure Cases

The method handles lateral and rotational discrepancies in many urban scans, but localization can fail under severe proximal occlusion or perceptual aliasing. Its scope and use depend on environment, invariance axes, and sensor conditions.

  • The proposed method overcomes lateral and rotational discrepancies between map and query scans, including scenes with many dynamic objects such as cars.
  • Localization may fail when a tall, large object nearby causes severe occlusions in both query and map scans, removing roughly one quarter of scan overlap.
  • Corridor-like places can produce perceptual aliasing and constitute another reported failure case.
  • A-CC generally performs best under combined rotational and lateral variance in urban-road environments, while PC or A-PC are recommended for more general settings or when semi-metric localization is critical.
  • The method is natively invariant along one direction and selects rotation and lateral directions as its invariance axes, using robust search and augmentation.
  • The descriptor is most powerful in urban environments, but additional channels such as intensity, point distribution, or semantic labels may extend it to indoor and natural environments.
Loading 2109.13494v1…