Recovering Perspective Pose with a Dual Step EM Algorithm

Andrew D. J. Cross, Edwin R. HancockNeurIPS 1997

Introduction

In computer vision and robotics, recovering the transformation between a 2D image and a 3D world coordinate system presents a classic "chicken-and-egg" dilemma. To accurately estimate the transformation matrix—known as the pose—one needs a reliable set of matching points (correspondences) between the two coordinate systems. Conversely, finding these reliable correspondences typically requires a rough initial estimate of the transformation geometry.

Traditional methods often attempt to bootstrap this process by using constraints, such as epipolar geometry, to prune potential matches. However, this approach is fragile: even a small number of residual outliers (incorrect matches) can lead to singular or ill-conditioned matrices, causing the entire pose estimation process to fail. To overcome this, researchers have proposed a unified framework that tackles matching and pose estimation simultaneously.

The Dual-Step EM Algorithm

To robustly solve this joint problem, the authors introduce a Dual-Step Expectation-Maximization (EM) Algorithm. This approach treats point correspondence as a hidden variable within a probabilistic mixture model.

Relational Constraints and Structural Gating

Instead of treating every potential match as an independent probability, the algorithm leverages the spatial structure of the image. The authors represent this image structure using Delaunay triangulations, creating a bipartite graph where nodes are feature points and edges represent spatial relationships.

Delaunay triangulation overlaid on a floppy disk image.

Using this graph, the algorithm employs Structural Gating. It evaluates the local graph structure to "gate" or weight contributions to the likelihood function. If a point's neighbors in the image do not match the expected neighbors in the model (measured via Hamming distance), that specific match is penalized and weighted less heavily.

The EM Optimization Framework

The core of the approach alternates between two steps:

  1. Expectation (E) Step: The algorithm calculates the a posteriori probabilities of matches based on the current pose parameters and the structural consistency of the Delaunay graph.
  2. Maximization (M) Step: This is a "dual" step. First, it updates the correspondence matches to maximize the posterior probability. Second, it updates the perspective transformation parameters by minimizing the structurally gated squared residuals.

Because perspective geometry involves non-linear foreshortening, the authors utilize the Levenberg-Marquardt optimization technique to solve the maximization equations, ensuring a stable path to the optimum. Furthermore, to avoid getting trapped in local optima—a common pitfall with discrete matching—the authors use a mean-field approximation. By replacing discrete "yes/no" match indicators with continuous probabilities, they smooth the optimization landscape.

Experimental Evaluation

The algorithm was evaluated using both real-world and synthetic datasets:

  • Real-World Data: The primary test subject was a 3.5-inch floppy disk placed on a desktop, captured using a low-quality SGI IndyCam. This camera's optics deviated from a perfect theoretical pin-hole model, providing a challenging, realistic test of the algorithm's robustness.
  • Synthetic Sensitivity Analysis: A controlled point-set of 20 nodes was used to benchmark the EM algorithm against standard least-squares estimation under varying levels of initial matching errors.

Key Results and Insights

By interleaving the estimation of geometry and the identification of matches, the two processes inform and refine each other. Good pose estimates improve matching, and consistent matches refine the pose.

  • Robustness to Initialization: A striking insight from the study is the algorithm's ability to converge to a correct solution even when the initial pose parameters are selected entirely at random.
  • Outperforming Least-Squares: In the 20-node synthetic test, the EM method consistently outperformed standard least-squares estimation once more than 40% (8 out of 20) of the initial matches were correct.
  • Handling Severe Foreshortening: The algorithm successfully registered images of the floppy disk under severe perspective foreshortening and significant rotation, proving its real-world applicability.
Algorithm successfully handling severe perspective foreshortening.
  • Effective Outlier Rejection: The structural gating mechanism successfully rejected outliers that would have otherwise skewed the transformation matrix, validating the use of Delaunay triangulations for spatial regularization.

Limitations and Future Directions

While highly effective, the current evaluation focuses primarily on planar objects like the floppy disk. The underlying mathematics are extensible, but the paper does not empirically demonstrate the algorithm on complex, 3D non-planar structures. Additionally, EM algorithms involving graph matching and non-linear Levenberg-Marquardt optimization can be computationally intensive compared to simpler linear closed-form solutions.

Future work suggests that this framework is readily extensible to recognizing more complex, non-planar objects. It also holds potential for application to other types of feature sets beyond simple points, such as line segments, broadening its utility in computer vision tasks.

Summary updated

BibTeX
@inproceedings{cross1997recovering,
  author = {Andrew D. J. Cross and Edwin R. Hancock},
  title = {{Recovering Perspective Pose with a Dual Step EM Algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1997},
}
Figure