PaperlayerView exact revision on arXiv

Source-linked AI summary

FlashReg: GPU-Accelerated 3-Clique Point Cloud Registration for Real-Time Correspondence-to-Pose Estimation

Ziyang Yu, Xiang Li, Qiong Chang, Jun Miyazaki

arXiv:2608.21804v1cs.CVcs.DC

TL;DR

Robust graph-based point cloud registration is costly because second-order compatibility graphs and clique searches consume substantial computation and memory. FlashReg uses capacity-bounded sparse FFSOG construction and dataflow-integrated 3-clique search, reducing latency by 2–3× relative to TurboReg at comparable recall while using about 50% of its peak tensor memory on an embedded GPU.

  • Problem

    Graph-based registration provides robust geometrically consistent correspondence sets, but dense second-order graph construction and clique enumeration are compute- and memory-intensive.

  • Method

    FlashReg constructs a capacity-bounded sparse second-order graph directly from the first-order graph and searches 3-cliques using compact candidate pools and sparse-neighborhood intersections.

  • Results

    FlashReg reduces estimator latency by 2–3× relative to TurboReg at comparable registration recall across indoor and outdoor benchmarks.

  • Takeaways & Limitations

    FlashReg provides a compact, memory-efficient correspondence-to-pose backend for resource-constrained robot platforms.

  • Takeaways & Limitations

    FlashReg is a capacity-bounded approximation unless row-size, candidate-pool coverage, and tie-resolution conditions match the dense search.

Abstract

from arXiv · show

Graph-based point cloud registration achieves high robustness by identifying geometrically consistent correspondence sets, but constructing second-order compatibility graphs and enumerating candidate cliques remain compute- and memory-intensive. This work presents FlashReg, a GPU-oriented correspondence-to-pose estimator that avoids materializing the dense scored second-order graph. Its Fast First- and Second-Order Graph (FFSOG) construction builds a capacity-bounded sparse second-order graph directly from the binary first-order graph. A dataflow-optimized three-node clique (3-clique) search then selects pivots from compact per-row candidate pools and enumerates triples through sorted sparse-neighborhood intersections. Across indoor and outdoor benchmarks, FlashReg reduces correspondence-to-pose latency by 2--3x relative to TurboReg at comparable registration recall, while using about 50% of its peak allocated tensor memory on an embedded GPU. These results make FlashReg suitable as a high-throughput registration backend within onboard perception pipelines.

1 Introduction

FlashReg addresses the computational and memory costs of robust graph-based registration with sparse GPU-native construction and dataflow-integrated 3-clique search. It maintains competitive recall while substantially improving estimator speed and memory efficiency.

  • Motivation: Point cloud registration must combine real-time response with high registration quality on resource-limited platforms.Point clouds provide fewer distinctive features and lower cross-scan similarity than images, increasing computational and memory demands.
  • Motivation: Graph-based registration improves robustness through geometrically consistent correspondence cliques and second-order compatibility, but graph construction and clique search are expensive.Dense graph construction scales quadratically with correspondence count, while maximal-clique search can enumerate millions of overlapping candidates.
  • FlashReg Design: FlashReg avoids dense second-order materialization by constructing capacity-bounded sparse graphs and passing intermediate results directly into search.Its design co-optimizes graph construction and inter-stage data movement rather than rebuilding intermediate results.
  • FlashReg Design: FFSOG compacts scored second-order rows, while dataflow-optimized search selects row-local pivots and enumerates cliques through sorted sparse-neighborhood intersections.The design avoids dense SOG write-back, redundant computation, and host synchronization.
  • Results: More than 2× lower estimator latency is reported across indoor, outdoor, and low-overlap benchmarks, with about 50% of TurboReg’s peak allocated tensor memory on Jetson AGX Xavier.The reported comparison also includes lower measured GPU-rail energy and competitive registration recall.

2 Related Work

Prior registration methods trade initialization requirements, robustness, accuracy, and computational cost in different ways. TurboReg brings pivot-based 3-clique search to GPUs, but FlashReg targets its remaining dense-memory and data-movement costs.

  • Descriptor-based Registration: ICP requires a good initial pose, whereas Go-ICP remains far from real time despite global optimality.Descriptor-based methods avoid initialization through handcrafted or learned local features.
  • Descriptor-based Registration: Low-overlap and noisy scans produce many outliers, motivating robust filtering in descriptor-based registration.Predator and GeoTransformer add overlap-aware matching to descriptor-based pipelines.
  • Graph-based Registration: Graph-based methods search geometric compatibility directly, with second-order compatibility and clique strategies improving robustness under outliers.Learning-based filters such as PointDSC, DGR, and 3DRegNet instead require labeled training.
  • GPU Acceleration: TurboReg replaces maximal-clique enumeration with GPU pivot-based 3-clique search and achieves over 100× speedup versus CPU-based MAC.However, recursive clique search remains difficult to parallelize and TurboReg still materializes dense intermediate structures.

3 Method

FlashReg estimates rigid poses by searching geometrically consistent 3-cliques among putative correspondences. Its pipeline combines fused first- and second-order graph construction with sparse, dataflow-oriented clique processing.

  • Problem Formulation: Descriptor matching produces N putative source–target correspondences, and registration seeks a rigid transformation aligning their inlier subset.The transformation is represented by rotation R and translation t.
  • Pipeline: FlashReg searches geometrically consistent 3-cliques to generate pose hypotheses, then verifies and refines those hypotheses against all correspondences.Three-node clique selection is the correspondence-to-pose stage of the pipeline.
  • FFSOG: FastFOG and FastSOG form FFSOG, producing a first-order graph and column-sorted sparse second-order rows with per-row top-scoring candidate pools.FastSOG computes scores by common-neighbor voting and emits positive entries directly as ELL-SOG.
  • Search: The dataflow-optimized search consumes compact graph outputs for pivot selection and clique enumeration without materializing the dense SOG score matrix.This organization passes graph-construction products directly to subsequent search stages.

3.1 FFSOG: Fast First- and Second-Order Graph Construction

FlashReg’s FFSOG constructs first- and second-order compatibility representations with fused GPU kernels, compact sparse storage, and row-local candidate pools. This avoids dense SOG materialization while preserving the access patterns needed by downstream search.

  • FastFOG Construction: FastFOG builds the binary first-order adjacency matrix with a fused tiled kernel that reuses coordinates in shared memory.It evaluates one triangle and writes symmetric off-diagonal results to produce the complete adjacency matrix.
  • FastFOG Construction: 0.19 ms is the reported FastFOG construction time, down from 1.64 ms in the stage-by-stage implementation.FastFOG retains O(N^2) computation and storage while reducing constant-factor work and global-memory traffic.
  • FastSOG Construction: FastSOG computes common-neighbor scores only for existing upper-triangular FOG edges and compacts positive entries directly into ELL-SOG.The masked product assigns scores to existing FOG edges rather than introducing new edges; each row has at most d_i nonzero entries.
  • FastSOG Construction: ELL-SOG stores valid neighbor indices and scores in column order, while each row’s top-scoring pool A_i supports score-ordered pivot selection.Downstream kernels inspect only each row’s valid prefix and ignore padding.
  • FastSOG Construction: FastSOG avoids dense SOG storage and dense-row scans, reducing scored-graph storage to O(NL) while retaining the dense binary FOG matrix for first-order lookups.The compact representations are generated in the access orders required by clique enumeration and pivot selection.

3.2 Dataflow-Optimized 3-Clique Search

FlashReg’s search integrates pivot selection with sparse 3-clique enumeration. It uses bounded per-row candidate pools, sorted sparse-neighborhood intersections, and local top-T retention instead of dense matrix scans.

  • 3-Clique Enumeration: Phase 2 intersects each pivot’s endpoint neighborhoods and retains at most T highest-scoring 3-cliques per pivot.The search emits at most KT scored triples; experiments use T=2.
  • Search Objective and Pivot Selection: Phase 1 selects K highest-scoring positive upper-triangular SOG edges as pivots from the union of per-row candidate pools.FFSOG extracts each row’s m highest-scoring retained edges before the row leaves shared memory.
  • Sparse Data Access: ELL-SOG lets the search inspect valid sparse prefixes directly, avoiding dense row scans and adjacency reconstruction.Its column-sorted neighborhoods support binary-search intersections for candidate third vertices.
  • 3-Clique Enumeration: Each thread keeps its κ highest-scoring candidates in registers, then threads merge their lists through shared memory without atomics or global scratch space.Because κ ≥ T, lower-ranked discarded candidates cannot enter the block-level top-T set.
  • Approximation and Bounded Cost: FlashReg is a capacity-bounded approximation unless row, candidate-pool, and tie-resolution conditions make its pivots and cliques match the dense search.Avoiding truncation by L alone does not ensure that the top-m pools contain every dense global top-K pivot.
  • Approximation and Bounded Cost: FlashReg examines at most Nm edges in Phase 1 and performs O(KL log L) Phase 2 work, with O(NL + Nm) search storage.These bounds apply to SOG storage and clique search; the full graph pipeline still includes FastFOG’s quadratic pairwise evaluation.

3.3 Pose Estimation, Verification, and Refinement

Each retained 3-clique produces a pose hypothesis through a batched weighted-SVD solver, followed by correspondence verification and iterative reweighted-SVD refinement.

  • Pose Estimation: Each retained 3-clique generates a pose hypothesis with a batched weighted-SVD (Kabsch) solver.The downstream pose-estimation stages follow TurboReg and are not a contribution of FlashReg.
  • Verification and Refinement: The hypotheses are verified against the input correspondences and the best pose is refined by iteratively reweighted SVD.Verification and refinement operate after clique-based hypothesis generation.

4 Experiments

FlashReg is evaluated across indoor, outdoor, and embedded settings, where it preserves competitive registration recall while substantially reducing correspondence-to-pose latency and tensor-memory use.

  • 4.2 Benchmark Evaluation: FlashReg reaches 84.01% RR with FPFH and 93.41% with FCGF on 3DMatch, essentially matching TurboReg.
  • 4.2 Benchmark Evaluation: 4–5 ms latency on 3DMatch is over two orders of magnitude faster than CPU clique solvers and below TurboReg’s 10 ms.
  • 4.2 Benchmark Evaluation: On 3DLoMatch, FlashReg obtains 39.25% RR with FPFH and 59.12% with FCGF, exceeding TurboReg by 0.06 and 0.67 percentage points.
  • 4.2 Benchmark Evaluation: On KITTI, FlashReg matches TurboReg’s recall exactly at 97.83% with FPFH and 97.66% with FCGF while reducing latency to 4–5 ms.
  • 4.3 Embedded Platform Evaluation: On Jetson AGX Xavier, FlashReg tracks TurboReg’s recall while using about half its peak allocated tensor memory and consistently less measured energy.
  • 4.4 Ablation Study: The fused pipeline achieves a 2.23× end-to-end speedup, reducing latency by 55.2% while maintaining 84.01% RR.

5 Conclusion

FlashReg is a GPU-native 3-clique correspondence-to-pose estimator that avoids dense second-order graph materialization and redundant data movement. It preserves recall comparable to TurboReg while reducing latency by 2–3×, lowering embedded-GPU memory and energy use, and supporting onboard registration pipelines.

  • 5 Conclusion: FlashReg avoids materializing the dense SOG score matrix and eliminates redundant data movement between graph construction and search.Its consumer-oriented ELL-SOG and candidate pools support the GPU-native 3-clique estimator design.
  • 5 Conclusion: 2–3× latency reduction preserves recall comparable to TurboReg across the evaluated registration benchmarks.The conclusion identifies latency reduction and recall preservation as the main performance outcome.
  • 5 Conclusion: Lower peak allocated tensor memory and measured GPU-rail energy support FlashReg as a practical backend for onboard registration pipelines.The paper frames this consequence within onboard registration rather than complete perception-system deployment.
  • 5 Conclusion: Future work will extend the dataflow design to higher-order geometric reasoning and integrate it with complete perception systems.These are stated future directions rather than evaluated capabilities of the present system.
Loading 2608.21804v1…