K-Best Transformation Synchronization

Yifan Sun, Jiacheng Zhuo, Arnav Mohan, Qixing HuangICCV 2019 · OpenReview

Abstract

In this paper, we introduce the problem of K-best transformation synchronization for the purpose of multiple scan matching. Given noisy pair-wise transformations computed between a subset of depth scan pairs, K-best transformation synchronization seeks to output multiple consistent relative transformations. This problem naturally arises in many geometry reconstruction applications, where the underlying object possesses self-symmetry. For approximately symmetric or even non-symmetric objects, K-best solutions offer an intermediate presentation for recovering the underlying single-best solution. We introduce a simple yet robust iterative algorithm for K-best transformation synchronization, which alternates between transformation propagation and transformation clustering. We present theoretical guarantees on the robust and exact recoveries of our algorithm. Experimental results demonstrate the advantage of our approach against state-of-the-art transformation synchronization techniques on both synthetic and real datasets.

Introduction

In computer vision tasks such as 3D reconstruction and Structure-from-Motion (SfM), the goal of transformation synchronization is to find globally consistent absolute poses from noisy, pairwise relative poses. A major challenge for existing methods is symmetry. When an object possesses self-symmetry (e.g., a square table with four valid rotations), traditional algorithms often attempt to find a single "best" solution by averaging different modes. This typically results in blurred or entirely incorrect alignments. This paper introduces K-best transformation synchronization, a framework designed to identify all $K$ plausible solutions simultaneously, providing a robust solution for symmetric objects and a powerful initialization for non-symmetric ones.

Methodology

The proposed approach utilizes a discrete, iterative algorithm that avoids the averaging pitfalls of standard spectral or convex optimization methods.

  1. Transformation Sampling: The space of rigid transformations ($SE(3)$) is discretized. Translations are sampled on a regular grid, and rotations are sampled using the HEALPix grid. This discretization transforms a complex continuous problem into a manageable discrete search space.
  2. Propagation and Clustering: The core algorithm alternates between two steps. First, Propagation spreads transformation signals from a root object through the observation graph. Second, Clustering identifies the $K$ most frequent (dominant) modes among incoming signals, preserving the multi-modal nature of symmetric data.
  3. Automatic Estimation of $K$: The algorithm estimates the optimal $K$ by evaluating a "description efficiency" score across different values, identifying the "elbow" point where increasing $K$ no longer yields significant consistency gains.
  4. Post-processing: For objects that are only approximately symmetric, a spectral relaxation technique can be applied to select the single most consistent pose for each object from the $K$ candidates.

Experimental Results

The K-best approach was evaluated on synthetic datasets (ShapeNetCore), real-world indoor scans (ScanNet), and large-scale SfM benchmarks (Notre-Dame, Cornell ArtQuad, San Francisco).

Qualitative comparison on symmetric objects from ShapeNetCoreSym. Baselines like MRF-SFM and RobustAlign suffer from averaging artifacts, while the proposed method recovers clean structures.

Quantitative Performance

On the ShapeNetCoreSym dataset, the method reduced mean angular rotation error from 12.1° to 6.7°. On real-world ScanNetSym data, error dropped from 31.6° to 19.6°. Even on general non-symmetric scenes in the full ScanNet dataset, the method improved mean error from 36.3° to 21.3°, demonstrating high robustness to outliers.

Cumulative distribution of angular distortion on SfM benchmarks. The proposed method (red) consistently outperforms the input and the state-of-the-art baseline by Chatterjee et al.

Discussion and Conclusion

A key insight of this work is the "death of the spectral gap." Modern synchronization methods rely on a clear signal-to-noise gap that vanishes in the presence of symmetry. By explicitly searching for multiple modes, the K-best framework bypasses this limitation. Furthermore, the discrete voting mechanism prevents the "averaging trap" common in Iteratively Reweighted Least Squares (IRLS) techniques. While the method is currently limited by discretization precision, it provides a highly robust intermediate representation for complex 3D reconstruction tasks.

Summary updated

Abstract

In this paper, we introduce the problem of K-best transformation synchronization for the purpose of multiple scan matching. Given noisy pair-wise transformations computed between a subset of depth scan pairs, K-best transformation synchronization seeks to output multiple consistent relative transformations. This problem naturally arises in many geometry reconstruction applications, where the underlying object possesses self-symmetry. For approximately symmetric or even non-symmetric objects, K-best solutions offer an intermediate presentation for recovering the underlying single-best solution. We introduce a simple yet robust iterative algorithm for K-best transformation synchronization, which alternates between transformation propagation and transformation clustering. We present theoretical guarantees on the robust and exact recoveries of our algorithm. Experimental results demonstrate the advantage of our approach against state-of-the-art transformation synchronization techniques on both synthetic and real datasets.
BibTeX
@inproceedings{sun2019k,
  author = {Yifan Sun and Jiacheng Zhuo and Arnav Mohan and Qixing Huang},
  title = {{K-Best Transformation Synchronization}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2019},
  url = {https://openreview.net/forum?id=2ljL5In8lga},
}
Figure