PaperlayerView exact revision on arXiv

Source-linked AI summary

SegMatch: Segment based loop-closure for 3D point clouds

Renaud Dubé, Daniel Dugas, Elena Stumm, Juan Nieto, Roland Siegwart, Cesar Cadena

arXiv:1609.07720v2cs.RO

TL;DR

SegMatch targets challenging 3D loop-closure detection, where local methods can be ambiguous and global methods can depend on viewpoint. It matches 3D segments through a modular pipeline without assuming perfect segmentation or predefined objects, achieving accurate localization above 1Hz on KITTI’s largest map and demonstrating online loop closure.

  • Problem

    3D loop-closure detection is challenging because local features can be ambiguous and global features can be viewpoint dependent.

  • Method

    SegMatch extracts, describes, and matches 3D segments, then applies geometric verification without assuming perfect segmentation or the presence of objects.

  • Results

    SegMatch accurately localizes at a frequency higher than 1Hz on the largest KITTI map and robustly detects loops online.

  • Takeaways & Limitations

    Segment-level place recognition offers a practical basis for real-time localization and online loop closure in 3D laser data.

Abstract

from arXiv · show

Loop-closure detection on 3D data is a challenging task that has been commonly approached by adapting image-based solutions. Methods based on local features suffer from ambiguity and from robustness to environment changes while methods based on global features are viewpoint dependent. We propose SegMatch, a reliable loop-closure detection algorithm based on the matching of 3D segments. Segments provide a good compromise between local and global descriptions, incorporating their strengths while reducing their individual drawbacks. SegMatch does not rely on assumptions of "perfect segmentation", or on the existence of "objects" in the environment, which allows for reliable execution on large scale, unstructured environments. We quantitatively demonstrate that SegMatch can achieve accurate localization at a frequency of 1Hz on the largest sequence of the KITTI odometry dataset. We furthermore show how this algorithm can reliably detect and close loops in real-time, during online operation. In addition, the source code for the SegMatch algorithm will be made available after publication.

DOI: 10.1109/ICRA.2017.7989618

SegMatch addresses 3D place recognition by matching segments rather than keypoints or objects. Its modular design supports online loop closure and real-time localization without assuming perfect segmentation or predefined objects.

  • 3D place recognition is important for SLAM because drift makes reliable loop-closure detection crucial without global positioning information.
  • SegMatch matches segments that may represent partial objects, full objects, or parts of larger structures such as windows, arcs, and façades.
  • The pipeline extracts and describes segments, matches them to mapped target segments, and applies geometric verification to propose place-recognition candidates.
  • Segment matching compresses point clouds into distinct elements, reducing matching time and the likelihood of false matches.
  • SegMatch provides an open-source implementation for online, real-time loop-closure detection and localization.

II. RELATED WORK

Prior 3D place-recognition methods use local keypoints, global descriptors, or planes and objects. SegMatch instead seeks a general segment-based solution without requiring simplistic primitives or rich object libraries.

  • Existing 3D laser place-recognition strategies primarily extract and match local keypoint features.
  • Global descriptors summarize local point clouds with height histograms or rotation-invariant geometric features, but require descriptor-specific assumptions and matching procedures.
  • Plane- and object-based approaches use geometric structures such as planes, graphs, or detected objects for recognition.
  • SegMatch avoids assuming environments consist of simplistic geometric primitives, planes, or a rich library of objects.

III. SegMatch ALGORITHM

SegMatch is a modular 3D point-cloud place-recognition system. It combines segmentation, feature extraction, segment matching, and geometric verification, with target maps loaded or built online.

  • SegMatch comprises four modules: point-cloud segmentation, feature extraction, segment matching, and geometric verification.
  • The target map can be loaded from disk for localization or computed online for loop closure.

A. Segmentation

SegMatch constructs matchable segments from a local neighborhood of each incoming point cloud. Voxel filtering removes weak occupancy evidence before clustering.

  • For each incoming point cloud, SegMatch extracts a cylindrical local neighborhood of radius R centered on the robot.
  • A voxel grid filters noise from insufficiently occupied voxels, after which the remaining cloud is segmented into point clusters using Cluster-All.

B. Feature extraction

SegMatch compresses each segment into multiple geometric descriptors and uses a learned random-forest classifier to identify candidate matches efficiently.

  • Segment descriptors compress raw point-cloud data into signatures suitable for recognition and classification.
  • The eigenvalue descriptor contains seven measures, including linearity, planarity, scattering, omnivariance, anisotropy, eigenentropy, and change of curvature.
  • The shape-histogram descriptor is a 1x640 feature comprising ten histograms that encode D2, D3, and A3 shape functions.D2 uses point-pair distances, D3 uses point-triplet areas, and A3 uses angles between lines derived from those triplets.
  • Candidate matches are retrieved with a k-d tree in feature space before classification, preserving efficiency when multiple feature types are used.
  • A random forest combines feature comparisons, assigns a match score w, and thresholds that score to produce the final candidate list.The classifier uses absolute differences for eigenvalue features and histogram intersections for the shape features.

D. Geometric verification

Geometric verification filters segment-match candidates with RANSAC, accepting geometrically consistent clusters and returning a 6DOF place-recognition transformation.

  • RANSAC evaluates transformations from candidate matches using segment centroids.
  • A candidate is accepted when its segments form a geometrically consistent cluster meeting a minimum-size requirement.
  • The verification stage outputs a 6DOF transformation and the matching segments representing the place-recognition candidate.

IV. EXPERIMENTS

The experiments evaluate SegMatch on KITTI sequences through classifier analysis, localization and loop-detection comparisons, and online operation.

  • The evaluation uses the KITTI odometry dataset to train and test classifiers, compare localization strategies, and assess online loop detection.
  • Sequence 00 spans 3.7 km and 470 seconds, including a 500-meter loop used for the localization experiment.
  • Real-time point-cloud generation subsamples half of each Velodyne scan and adds scans after every minimum 1-meter vehicle displacement.Ground-plane extraction filters points by minimum height using the known sensor configuration.
  • Source clouds use a 60-meter cylindrical neighborhood, 0.1-meter voxels, and segments containing 100 to 15000 points.Occupied voxels are clustered when their maximum Euclidean separation is 0.2 meters.
  • Training and testing data are generated by matching corresponding and differing segments when the vehicle revisits mapped sections.
  • Sequence 06 produces 2000 true and 800000 false segment matches for classifier training.

C. Segment matching performance

SegMatch compares a distance-threshold baseline with random-forest segment matching, then fixes the false-positive operating point for localization and loop-closure experiments.

  • The experiment compares L2 distance thresholding with random forests using eigenvalue features alone or eigenvalue-plus-shape features.
  • Random-forest classifiers improve performance over the L2 norm counterpart on sequence 00 test data.
  • The classifiers operate at a false positive rate of 0.2 to limit false segment matches and avoid false place recognitions.
  • The localization evaluation compares three segment-based strategies with a keypoint-based place-recognition technique.
  • The ROC curves report segment-matching performance for L2, RF_eigen, and RF_eigen+shapes, with operating points marked at FPR = 0.2.

1) Keypoint baseline:

Localization is evaluated across repeated runs using distance-to-localization, false-localization counts, computational timing, and comparison with a keypoint baseline.

  • Evaluation protocol: 90 runs per strategy quantify the probability of travelling a given distance before successful localization in the target map.The distance travelled between localizations is recorded and averaged across runs because computer load changes localization locations.
  • Localization results: RF_eigen+shapes never required more than 55 meters before successful localization, compared with 67 meters for L2 and 88 meters for RF_eigen.RF_eigen+shapes is the most complex and computationally demanding strategy.
  • Trade-offs: L2 is the quickest strategy but made 14 false localizations, motivating possible reduction of its operating point of 0.2 FPR.
  • Localization results: The two random forest strategies successfully localized within 35 meters 95% of the time.
  • Baseline comparison: All segment matching methods outperformed the keypoint baseline, which averaged 5.23 true-positive and 3.25 false-positive localizations per one-minute run.The keypoint approach required more work to produce positive results without allowing false positives.

E. Loop-closure performance

SegMatch demonstrates segment correspondences, localization behavior, and online loop closure across KITTI experiments, including region-grown segments as discriminative inputs.

  • Loop-closure performance: During online operation on KITTI sequence 05, RF_eigen+shapes detected 12 true-positive and no false-positive loop closures.The online target map is built by accumulating source-cloud segments while avoiding duplicate segments.
  • Loop-closure performance: The detected loops were fed into an online pose-graph optimization system to update target segment positions.
  • Segment correspondences: Fig. 4 shows corresponding segments successfully detected by SegMatch, with target-cloud segments in the top row and source-cloud segments in the bottom row.
  • Localization evaluation: Fig. 5 reports localization-distance probabilities from 90 runs per strategy on KITTI drive 00 and records false localizations for each strategy.
  • Alternative segmentation: Region growing with smoothness constraints produced segments whose features enabled correct loop detection despite appearing less meaningful to humans.

V. CONCLUSION

The conclusion presents SegMatch as a modular segment-matching framework for 3D place recognition, reports KITTI localization and online loop-closure results, and identifies extensibility to other scenarios.

  • V. CONCLUSION: SegMatch extracts and describes source segments, matches them to mapped target segments, and applies geometric verification to generate place-recognition candidates.
  • V. CONCLUSION: On KITTI, SegMatch accurately localized at a frequency higher than 1Hz in the dataset’s largest map.
  • V. CONCLUSION: The framework robustly detected loops online and fed them to a pose-graph trajectory estimator.
  • V. CONCLUSION: Its modular design supports different scenarios by replacing pipeline building blocks, and the source code provides real-time segmentation and loop-closure detection for 3D point-cloud streams.
  • V. CONCLUSION: The authors propose future supervised learning to interpret segment-based maps into structural and object semantic classes.
Loading 1609.07720v2…