Registration of algebraic varieties using Riemannian optimization

Florentin Goyens, Coralia Cartis, Stéphane ChrétienarXiv 2024 · DOI · arXiv

Introduction

Point cloud registration—the process of aligning two sets of spatial data—is a fundamental task in computer vision, robotics, and medical imaging. While the Iterative Closest Point (ICP) algorithm has long been the standard, its reliance on point-to-point correspondences makes it fragile when faced with noise, varying sampling densities, or partial overlaps. This paper introduces a paradigm shift: treating point clouds not as discrete sets, but as samples from underlying algebraic varieties (sets defined by polynomial equations).

The Correspondence Problem

Traditional registration methods attempt to find an optimal transformation by matching specific points in a source scan to their nearest neighbors in a target scan. This approach breaks down when the scans represent different parts of the same object or contain significant noise.

Conceptual overview of registering two manifolds $M_1$ and $M_2$ via a transformation $\mathcal{T}$.

By moving from "matching points" to "matching geometry," the authors propose aligning the polynomial equations that describe the surfaces. If two scans represent different segments of the same underlying variety, they can be registered even with zero physical overlap between the point sets.

Methods: Riemannian Optimization

The proposed pipeline consists of two primary stages, both leveraging optimization on smooth geometric manifolds.

1. Algebraic Variety Identification (Denoising)

The first step involves approximating the noisy point cloud with a smooth algebraic variety. Points are mapped into a higher-dimensional space of polynomial features. The algorithm then searches the Grassmann manifold—the space of all $q$-dimensional subspaces—to find the set of equations that best "vanish" on the data.

The denoising step approximates noisy data points (black) with a smooth algebraic variety $\hat{M}$ (red).

This process effectively "snaps" noisy points to a smooth underlying surface, providing a denoised representation that is easier to align. To ensure accuracy without ground truth, the paper utilizes Stein’s Unbiased Risk Estimate (SURE) to estimate denoising error.

2. Registration

Once the varieties are identified, the algorithm seeks the rigid transformation (rotation $Q$ and translation $a$) that minimizes the distance between the source points and the target variety. This optimization is performed on the orthogonal group $O(n)$ using second-order Riemannian trust-region methods, which provide fast convergence and theoretical guarantees for finding critical points.

Key Results and Discussion

The method was evaluated on synthetic 2D/3D shapes and real-world dental tomography scans:

  • Robustness to Noise: The algorithm maintained high accuracy in synthetic tests even under significant Gaussian noise ($\sigma = 0.1$).
  • Handling Non-Overlap: Unlike ICP, this method successfully registered point clouds with zero overlap, provided they shared the same underlying algebraic structure.
  • Real-World Application: On complex 3D dental surfaces, the algorithm achieved residual errors of approximately $10^{-1}$, demonstrating its viability for biological data.

Conclusion and Future Work

By utilizing the geometric properties of manifolds and algebraic varieties, this approach offers a robust alternative to correspondence-based registration. However, challenges remain regarding the "curse of dimensionality" as polynomial degrees increase, which can lead to exponential growth in computational cost. Future research will focus on using orthogonal polynomial bases to improve numerical stability and stochastic Riemannian methods to scale the algorithm for massive datasets.

Summary updated

Abstract

We consider the point cloud registration problem, the task of finding a transformation between two point clouds that represent the same object but are expressed in different coordinate systems. Our approach is not based on a point-to-point correspondence, matching every point in the source point cloud to a point in the target point cloud. Instead, we assume and leverage a low-dimensional nonlinear geometric structure of the data. Firstly, we approximate each point cloud by an algebraic variety (a set defined by finitely many polynomial equations). This is done by solving an optimization problem on the Grassmann manifold, using a connection between algebraic varieties and polynomial bases. Secondly, we solve an optimization problem on the orthogonal group to find the transformation (rotation $+$ translation) which makes the two algebraic varieties overlap. We use second-order Riemannian optimization methods for the solution of both steps. Numerical experiments on real and synthetic data are provided, with encouraging results. Our approach is particularly useful when the two point clouds describe different parts of an objects (which may not even be overlapping), on the condition that the surface of the object may be well approximated by a set of polynomial equations. The first procedure -- the approximation -- is of independent interest, as it can be used for denoising data that belongs to an algebraic variety. We provide statistical guarantees for the estimation error of the denoising using Stein's unbiased estimator.
BibTeX
@misc{goyens2024registration,
  author = {Florentin Goyens and Coralia Cartis and Stéphane Chrétien},
  title = {{Registration of algebraic varieties using Riemannian optimization}},
  year = {2024},
  eprint = {2401.08562},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.08562},
}
Figure