DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming

DC-Reg: Globally Optimal Point Cloud Registration via Tight Bounding with Difference of Convex Programming

Introduction

Point cloud registration under conditions involving significant noise, outliers, or non-rigid deformation remains a central challenge in geometric computer vision. While local techniques such as ICP and CPD are computationally efficient, their reliance on initialization and their proneness to local minima restricts theoretical guarantees on global optimality. Recent deterministic global solvers, primarily based on Branch-and-Bound (BnB), address some of these limitations but suffer from loose lower bounds, resulting in prohibitive convergence times—particularly in scenarios dominated by heavy outliers. The "DC-Reg" framework, introduced in this work, proposes a holistic Difference of Convex (DC) programming paradigm to derive much tighter lower bounding strategies for globally optimal registration, substantially accelerating BnB search while maintaining determinism and robustness in the presence of extreme geometric disturbances.

Holistic DC Bounding over Transformation-Correspondence Coupling

Traditional BnB-based solvers have typically adopted either variable elimination or term-wise relaxation. Variable elimination approaches, which collapse the problem into concave minimization over correspondences, do not scale for dense or complex assignments. Term-wise relaxations, using convex envelopes or bounding volumes of monomials independently, fail to model the intrinsic interdependence between transformation parameters and assignment matrices, resulting in conservative (loose) bounds and so poor pruning efficiency.

The DC-Reg methodology departs from these approaches by deriving a holistic DC decomposition for the entire coupled objective. Let $$E(\mathbf{P}, \boldsymbol{\theta}) = \sum_{i,j} p_{ij} E_{ij}(\boldsymbol{\theta})$$ with the partial permutation constraint $\mathbf{P}\in\mathcal{P}$. For bounding, each $E_{ij}(\boldsymbol{\theta})$ is written as $$E^{\text{cvx}}_{ij}(\boldsymbol{\theta}) + E^{\text{cav}}_{ij}(\boldsymbol{\theta})$$. The convex term is linearized at the center of the current box, yielding a tight, structure-aware lower bounding function. The overall box lower bound is efficiently computed by solving a Linear Assignment Problem (LAP) at $2^{n_\theta}$ transformation vertices, leveraging the property that the minimum of a pointwise-minimum of concave functions over a polytope occurs at one of its vertices.

The strength of this tight bounding process is validated throughout the experiments, where DC-Reg consistently achieves both lower registration error and dramatically reduced BnB tree sizes compared to solvers using term-wise convex envelopes such as McCormick relaxations.

2D and 3D Registration Scenarios

The DC-Reg framework is applicable to a range of geometric registration problems:

• 2D Similarity Registration: Here, pose is parameterized via scale and rotation angles plus translation, leading to a convex quadratic residual ($E_{ij}(\boldsymbol{\theta})$). The DC decomposition is trivial since the objective is convex. Linearization yields immediate tightness. Empirical sensitivity studies over two data types (prototype biological and character shapes), across increasing non-rigid deformation, noise, and various outlier configurations, show robust performance exceeding that of RPM-HTB, RPM-PA, and RPM-CAV.
• 3D Rigid Registration with Rotation-Invariant Features: For high-dimensional SE(3) registration, direct global minimization is infeasible. DC-Reg adopts a decomposition: optimal translation is solved globally using rotation-invariant norms, then the best rotation is found via existing robust 1-DoF search methods. The DC decomposition for the 1D cost in the translation search inherits structure from the original pairing, enabling highly efficient BnB with only eight LAP calls per box in 3D translation space. Even in cases of moderate non-rigid distortion, DC-Reg maintains stability where rigid-structure-specific solvers (e.g., TEASER++, GO-ICP) fail.

Experimental Results

2D Synthetic and Real-World Registration

The algorithm demonstrates resilience to severe geometric challenges, including extreme non-rigid deformation, additive positional noise, and partial overlap occlusions with mixed and separated outliers. Across all trials, DC-Reg either matches or exceeds baselines in accuracy, with the gap widening as the data becomes more corrupted.

Figure 2: 2D test cases spanning deformation, noise, mixed/separate outliers, and occlusion scenarios; source (red circles) and target (blue crosses) point sets.

Numerical results (registration error and runtime) across these disturbance regimes underscore the principal claims: DC-Reg is robust against underestimated inlier counts (maintaining low error for $n_p$ at $50\%$ of ground truth), while the run time remains controlled except in the maximal outlier regime, where an increase is inevitable due to BnB's exponential complexity in the expanded search space but still outperforms less tight methods.

2D Image Dataset Registration

On real-world image-derived point sets (Caltech-256, VOC2007), DC-Reg accomplishes nearly perfect overlays, even in dense clutter and severe occlusion, whereas term-wise or local solvers converge to visually incorrect alignments.

3D Synthetic Benchmarking

A comprehensive set of disturbance cases on "horse" and "dino" shapes confirms the superiority of DC-Reg’s holistic bounding in mixed-outlier and deformation/noise scenarios. In separated outlier and extreme occlusion tests, while GO-ICP and GORE can occasionally achieve lower error, DC-Reg remains highly competitive and far more stable than RPM-HTB and the family of trilinear-based methods.

Figure 4: 3D test cases covering deformation, noise, various outlier regimes, and occlusion; source (red circles) and target (blue crosses).

Detailed error and timing curves across deformation, noise, and outlier ratios further reinforce the distinct advantage of holistic bounding in terms of convergence speed (runtime) and solution quality (alignment error). Parameter sensitivity analysis illustrates that even inaccurate estimates of inlier cardinality $n_p$ degrade DC-Reg’s performance only mildly, underscoring resilience in underconstrained settings.

Large-Scale Real Data: 3DMatch

Evaluation on 3DMatch (five RGB-D benchmarks) with ground-truth scan pairs demonstrates that DC-Reg outperforms or matches both global BnB solvers and robust, certifiable relaxations like TEASER++ and GORE, especially in low-overlap (challenging) cases. The ability to consistently avoid local optima and provide low, stable error across diverse scenes is a direct consequence of the model’s joint structure-aware bounding.

Implications and Prospective Directions

Theoretically, DC-Reg demonstrates that integrating holistic DC-programming-based tight lower bounds into global registration solvers enables a practical and robust solution to simultaneous pose and correspondence estimation, even when the objective's non-convexity is compounded by correspondence ambiguity, transformation nonlinearity, and massive data corruption.

Practically, the method is suitable for batch and real-time 2D/3D registration tasks where robust, certifiable alignment is required, particularly in automated reverse engineering, medical imaging, autonomous mapping, and dynamic 3D reconstruction with missing and spurious data.

Future extensions will likely target:

• GPU-accelerated BnB to further reduce wall-clock time in high-dimensional search spaces,
• Extension of the holistic DC bounding paradigm to explicit non-rigid transformation groups,
• Integration with learning-based correspondence or feature extraction modules for enhanced applicability in perceptually ambiguous real environments.

Conclusion

DC-Reg establishes a new standard for robust, certifiable global point cloud registration by leveraging holistic, structure-aware difference-of-convex programming for tight bounding within an efficient Branch-and-Bound framework. The demonstrated gains in both accuracy and efficiency, particularly under strong geometric perturbations and outlier regimes, highlight the significance of structural regularization for coupled transformation-assignment objectives. This approach offers tangible advancements for both the practical deployment of registration pipelines in real-world systems and the theoretical understanding of global optimization in high-dimensional unconstrained matching problems.