PaperlayerView exact revision on arXiv

Source-linked AI summary

STD: Stable Triangle Descriptor for 3D place recognition

Chongjian Yuan, Jiarong Lin, Zuhao Zou, Xiaoping Hong, Fu Zhang

arXiv:2209.12435v2cs.CVcs.RO

TL;DR

LiDAR place recognition must accommodate viewpoint changes and point-cloud sparsity that varies across distances, scenes, and sensor types. The paper extracts keypoints to form and match stable triangle descriptors, then reports better public-dataset performance and broader adaptability than other global descriptors.

  • Problem

    LiDAR place recognition calls for rotation- and translation-invariant matching, while point-cloud sparsity varies with distance, scene, and LiDAR type.

    Source: §I · p. 1

  • Method

    STD projects point clouds onto plane boundaries to extract keypoints, forms triangle descriptors, matches them, and uses plane-based geometric verification.

    Source: §I · p. 1, C. Loop Detection · p. 4

  • Results

    STD performs better than other global descriptors on public datasets and shows greater adaptability across environments and LiDAR types.

    Source: §V · p. 6

  • Takeaways & Limitations

    A hash-table database for historical descriptors avoids building a k-D tree during loop searching.

    Source: §V · p. 6

    On KITTI08, lowering the plane-coincidence threshold admits smaller-overlap loops and possible false positives; 0.5–0.6 is reported as a good trade-off.

    Source: 3) Plane Coincidence Threshold Selection · p. 5

Abstract

from arXiv · show

In this work, we present a novel global descriptor termed stable triangle descriptor (STD) for 3D place recognition. For a triangle, its shape is uniquely determined by the length of the sides or included angles. Moreover, the shape of triangles is completely invariant to rigid transformations. Based on this property, we first design an algorithm to efficiently extract local key points from the 3D point cloud and encode these key points into triangular descriptors. Then, place recognition is achieved by matching the side lengths (and some other information) of the descriptors between point clouds. The point correspondence obtained from the descriptor matching pair can be further used in geometric verification, which greatly improves the accuracy of place recognition. In our experiments, we extensively compare our proposed system against other state-of-the-art systems (i.e., M2DP, Scan Context) on public datasets (i.e., KITTI, NCLT, and Complex-Urban) and our self-collected dataset (with a non-repetitive scanning solid-state LiDAR). All the quantitative results show that STD has stronger adaptability and a great improvement in precision over its counterparts. To share our findings and make contributions to the community, we open source our code on our GitHub: https://github.com/hku-mars/STD.

I. INTRODUCTION

LiDAR place recognition must handle viewpoint changes and varying point-cloud density while providing rotation- and translation-invariant matching. The paper introduces STD, a triangle-based descriptor with a boundary-projection keypoint method, and evaluates it across varied environments and LiDAR types.

I. INTRODUCTION

  • LiDAR provides environmental structure without illumination or appearance variation, while vision-based loop detection methods can struggle with illumination, appearance, and viewpoint changes.The introduction identifies rotation and translation invariance and robustness to varying point-cloud density as desired properties of LiDAR place recognition.Source: §I · p. 1
  • STD encodes three scene keypoints as a triangle whose side lengths and adjacent-plane normal angles form a rotation- and translation-invariant descriptor.The six-dimensional descriptor is described as retaining a high degree of distinguishability.Source: §I · pp. 1–2
  • The keypoint method projects point clouds onto plane boundaries, extracts boundary keypoints, and forms triangles with adjacent keypoints.The paper describes the extraction method as fast and based on keyframes.Source: §I · p. 2
  • The authors evaluate STD across urban, indoor, and unstructured scenarios and conventional spinning and solid-state LiDAR data.They report that the experimental results verify the method’s effectiveness.Source: §I · p. 2
  • The authors make their code publicly available on GitHub to support reproduction and follow-up research.The repository is github.com/hku-mars/STD.Source: §I · p. 2

II. RELATED WORKS

Prior 3D place-recognition work includes local point-feature descriptors, appearance-based global descriptors, and learning-based methods. The paper positions STD as a global descriptor intended to improve viewpoint invariance while providing full-degree-of-freedom pose estimates.

II. RELATED WORKS

  • Local point-feature descriptors can be sensitive to LiDAR point-cloud density and noise and may lack rotation or translation invariance.Examples include range-image features, Gestalt descriptors, PFH, SURFs, and SHOT.Source: §II · p. 2
  • Appearance-based global descriptors represent point-cloud structure through properties such as surface shape, projected distributions, or surrounding height.The cited approaches include NDT histograms, M2DP, Scan Context, and polygon or triangle descriptors.Source: §II · p. 2
  • Learning-based approaches such as SegMap and OverlapNet address 3D place recognition, but require training and GPU acceleration.The related-work discussion presents them as another response to viewpoint changes that challenge global descriptors.Source: §II · p. 2
  • STD is a three-keypoint global descriptor that represents their relative distribution within a keyframe and provides full-degree-of-freedom pose estimates.The paper contrasts its rotation and translation invariance with other global descriptors and its direct 3D triangle extraction with 2D polygon descriptors.Source: §II · p. 2

III. METHODOLOGY

The method extracts key points from keyframes, encodes them in stable triangle descriptors, and uses descriptor matching followed by geometric verification to detect loops. Plane segmentation and projection provide the key points and their associated plane normals.

III. METHODOLOGY

  • The pipeline computes descriptors from keyframes, selects loop candidates, and applies geometric verification; it also retains keyframe planes for that verification.The workflow depicts a hash-table database, selection of the top 10 matching-score frames, and estimation of the relative transformation when a loop is accepted.Source: §III · p. 2, Figure 2 · p. 3, A. Stable Triangle Descriptor · p. 3

A. Stable Triangle Descriptor

  • Keyframes are segmented into planes by growing from plane voxels to neighboring voxels with matching normals and sufficiently small distance.Nonmatching neighboring voxels become boundary voxels; expansion continues until the added neighbors are exhausted or boundary voxels are reached.Source: A. Stable Triangle Descriptor · pp. 2–3
  • Key points are selected from boundary-voxel points projected onto each plane, choosing the point with the largest value in its 5×5 image neighborhood.Each selected point corresponds to a 3D point and can be associated with the plane’s normal.Source: A. Stable Triangle Descriptor · p. 3, Figure 5 · p. 3
  • A triangle descriptor uses three vertices associated with adjacent planes, ordered by ascending side length, and stores the triangle centroid and plane-normal information.The standard descriptor illustration identifies the three vertices and corresponding normals; the listed descriptor contents include the vertices, normals, and centroid.Source: A. Stable Triangle Descriptor · p. 3, Figure 3 · p. 3

B. Search of Loop Candidates

A hash table indexes descriptors by six invariant attributes and accumulates votes for matching keyframes. The ordered triangle sides also make correspondence checks unambiguous.

B. Search of Loop Candidates

  • The hash key uses three side lengths and three pairwise normal-vector dot products; matching descriptors vote for keyframes, with the top 10 vote-getters selected as candidates.Matched descriptors are saved for the loop-detection step.Source: B. Search of Loop Candidates · p. 3
  • The six descriptor attributes are invariant to rigid transformations, and plane-based keypoint projection is invariant to view-angle change.The passage contrasts plane projection with projection from a range image.Source: B. Search of Loop Candidates · p. 3
  • Ordered side lengths identify equivalent triangles without enumerating side correspondences.The passage states that two triangles are assured to be the same if and only if their ordered side lengths are equal.Source: B. Search of Loop Candidates · p. 3

C. Loop Detection

Matched triangle vertices provide point correspondences for estimating the relative transform, while RANSAC and plane-based geometric verification help reject incorrect descriptor matches and validate loop candidates.

C. Loop Detection

  • Matched triangle vertices provide point correspondences for SVD to estimate the relative transformation, and RANSAC selects the transformation maximizing correctly matched descriptors.Source: C. Loop Detection · p. 4
  • The method transforms current-frame plane centers and searches candidate-frame centers in a 3D k-D tree, testing plane coincidence by normal-vector and point-to-plane differences.Source: C. Loop Detection · p. 4
  • A candidate is accepted when plane coincidence exceeds a threshold; this verification is more efficient than ICP because it compares fewer planes than points.Source: C. Loop Detection · p. 4
  • The plane-normal and point-to-plane constraints can also be optimized to obtain a more accurate transformation for loop correction.Source: C. Loop Detection · p. 4

IV. EXPERIMENTS

The experiments evaluate STD across varied environments and LiDAR types, comparing it with state-of-the-art counterparts on a common computing system.

IV. EXPERIMENTS

  • STD is evaluated in urban, indoor, and unstructured environments using mechanical spinning and solid-state LiDARs.Source: §IV · p. 4
  • Each experiment compares STD with state-of-the-art counterparts to assess effectiveness, robustness, and adaptability.Source: §IV · p. 4
  • All experiments run on an Intel i7-11700k at 3.6 GHz with 16 GB memory.Source: §IV · p. 4

A. Benchmark Evaluation

The benchmark evaluation compares STD with Scan Context and M2DP on three urban datasets collected using mechanical spinning LiDARs.

A. Benchmark Evaluation

  • The evaluation uses KITTI, NCLT, and Complex Urban, with data collected in urban environments using mechanical spinning LiDARs with different scanning lines.Source: A. Benchmark Evaluation · p. 4
  • STD is compared with Scan Context and M2DP using keyframes accumulated from every 10 frames; a detection is true when ground-truth pose distance is under 20 m.Source: A. Benchmark Evaluation · p. 4
  • STD uses the same parameters across datasets, while Scan Context and M2DP results come from their original paper.Source: A. Benchmark Evaluation · p. 4

1) Precision-Recall Evaluation:

STD outperforms Scan Context and M2DP in almost all datasets, while sparse scene structure can limit its keypoint supply and performance.

1) Precision-Recall Evaluation:

2) Run Time Evaluation:

STD’s computation time is similar to M2DP’s despite processing more points, and it avoids the library-size linear growth reported for Scan Context and M2DP. The plane coincidence threshold σpc trades loop selection against false positives.

2) Run Time Evaluation:

  • Scan Context and M2DP time per frame grows linearly with library size, whereas STD has no such linear growth, mainly because it stores descriptors in a hash table.The hash table avoids building a k-D tree for historical descriptors.Source: 2) Run Time Evaluation · pp. 4–5
  • STD’s computation time is similar to M2DP’s while processing 10 times more points.Scan Context’s augmented descriptors increase time in both descriptor construction and search.Source: 2) Run Time Evaluation · p. 5

3) Plane Coincidence Threshold Selection:

4) Localization Evaluation:

STD provides a six-degree-of-freedom relative transformation for localization, and STD-ICP approaches GICP accuracy with less variance and much lower computation time. The authors also evaluate STD with Livox LiDAR in urban, park, and indoor settings.

4) Localization Evaluation:

  • STD provides the relative transformation across all six degrees of freedom between loop and candidate frames without extra calculation.STD’s plane count is hundreds, compared with more than 100K points in the point cloud.Source: 4) Localization Evaluation · p. 5

B. Applicability to Other Types of LiDARs

4) Localization Evaluation:

  • STD-ICP achieves accuracy similar to GICP with less rotation and translation variance, while STD and STD-ICP take less than 1% of GICP’s computation time.The experiment perturbs the initial transform within ±5° per rotation axis and ±5 m per translation axis.Source: 4) Localization Evaluation · p. 5, Figure 10 · p. 6

1) Result Analysis:

On Livox data, STD performs similarly to its earlier evaluation except indoors, where similar floor corridors lower precision and recall; M2DP performs poorly. The conclusion emphasizes STD’s triangle-based descriptor, keypoint extraction, and adaptability across environments and LiDAR types.

V. CONCLUSION

  • STD uses plane detection and boundary projection to extract geometrically featured keypoints, which form triangle descriptors with neighboring keypoints.The conclusion attributes rotation and translation invariance to this combination.Source: §V · p. 6

1) Result Analysis:

  • STD performs similarly to its earlier evaluation on Livox data except indoors, where similar floor corridors lower precision and recall; M2DP performs poorly.The authors report that STD still provides valid loop nodes for indoor loop correction.Source: Figure 12 · p. 6, 1) Result Analysis · p. 6

V. CONCLUSION

  • The conclusion reports that STD performs better than other global descriptors on public datasets and is more adaptable to different environments and LiDAR types.The authors also describe using a hash table to store historical descriptors and avoid building a k-D tree during loop searching.Source: §V · p. 6
Loading 2209.12435v2…