Robust Nonrigid Registration by Convex Optimization

Qifeng Chen, Vladlen Koltun

Abstract

Nonrigid surface registration is a critical task in computer vision, yet real-world 3D scans often present challenges such as noise and topological violations. This paper introduces a robust registration framework that casts the problem as a discrete Markov Random Field (MRF) optimization. By employing a robust truncated penalty and global optimization through Tree-Reweighted Message Passing (TRW-S), the proposed method achieves a 3x improvement in precision over existing state-of-the-art techniques on the FAUST dataset.

Introduction

The goal of nonrigid registration is to establish a mathematical mapping between corresponding points on two deformable 3D shapes, such as a person in different poses. While theoretical solutions like Generalized Multidimensional Scaling (GMDS) exist, they struggle with "messy" real-world data. Scans often contain sensor noise, holes, and topological errors—for instance, a hand touching a hip creates a "bridge" that alters the perceived geometry. Most current algorithms are either sensitive to initial guesses or rely on local descriptors that fail under significant deformation.

Methodology

The authors propose a direct, global optimization approach centered on three pillars:

  1. MRF Formulation: Registration is treated as a labeling task where each point on a source surface seeks its corresponding label on a target surface within a discrete MRF framework.
  2. Robust Objective Function: To handle topological errors, the method utilizes a robust truncated penalty rather than standard linear or quadratic distance metrics. This allows the algorithm to effectively ignore massive outliers caused by "geodesic shortcuts" (e.g., surfaces touching) that would otherwise derail the registration.
  3. Global Optimization via TRW-S: The resulting NP-hard problem is solved using a linear programming relaxation via Tree-Reweighted Message Passing (TRW-S). This approach avoids the need for precise initialization and is robust against local minima.

A final refinement stage uses "fusion moves" and upsampling to transition from a sparse global correspondence to a dense, high-resolution mapping.

Experimental Results

The method was rigorously evaluated using the FAUST dataset, which features high-resolution scans of real human subjects in diverse poses, including challenging self-contact scenarios.

Comparison of registration error across different methods on the FAUST dataset. (a) Blended intrinsic maps, (b) Random forests, and (c) the proposed approach. Darker colors indicate higher error in centimeters.

The quantitative results demonstrate a substantial leap in performance:

  • Precision: The proposed method reduced average error by a factor of 3 compared to baselines like Blended Intrinsic Maps and Random Forests.
  • Intra-subject Accuracy: Achieved an average error of 4.49 cm, significantly lower than the 13.60 cm recorded by the next best method.
  • Inter-subject Accuracy: Achieved an average error of 5.95 cm, compared to 17.36 cm for the runner-up.
  • Reliability: Worst-case error was reduced by over 4x, indicating a high degree of stability even in difficult poses.

Conclusion

This research highlights that combining robust statistical modeling with modern global optimization machinery can outperform complex, hand-engineered pipelines. By prioritizing global isometric consistency over local descriptors, the framework provides a more resilient solution for real-world 3D registration tasks. Future work may address computational complexity and extend the model to handle significant non-isometric deformations.

Summary updated

Abstract

We present an approach to nonrigid registration of 3D surfaces. We cast isometric embedding as MRF optimization and apply efficient global optimization algorithms based on linear programming relaxations. The Markov random field perspective suggests a natural connection with robust statistics and motivates robust forms of the intrinsic distortion functional. Our approach outperforms a large body of prior work by a significant margin, increasing registration precision on real data by a factor of 3.
BibTeX
@inproceedings{chen2015robust,
  author = {Qifeng Chen and Vladlen Koltun},
  title = {{Robust Nonrigid Registration by Convex Optimization}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2015},
  doi = {10.1109/iccv.2015.236},
}
Figure