A Factorization Based Algorithm for Multi-Image Projective Structure and Motion

Peter F. Sturm, Bill TriggsECCV 1996 · DOI

TL;DR

This paper introduces a novel algorithm for reconstructing the 3D structure and motion of a scene from multiple uncalibrated images. It achieves this by factorizing a matrix of image points, a technique previously limited to affine projections, and extends it to projective geometry by introducing a method to recover crucial "projective depths" using fundamental matrices and epipoles.

What Problem Does This Paper Address?

Reconstructing the 3D structure and camera motion from a sequence of images is a fundamental problem in computer vision. Traditionally, this required calibrated cameras or significant prior knowledge about the scene. While methods for uncalibrated reconstruction existed, they primarily focused on pairs of images and struggled to scale efficiently to multiple views while maintaining a unified approach. The challenge was to extend existing factorization-based methods, which worked well for affine projections, to the more general and realistic projective case, where camera intrinsics are unknown and points are projected onto the image plane in a perspective manner. This requires handling unknown scaling factors for image points, which represent "projective depths."

Methods

The core of the paper's contribution lies in extending factorization-based methods to projective geometry. Here's a breakdown:

  • Projective Reconstruction Framework: The authors frame the problem as factorizing a "measurement matrix" $W$, which is formed by stacking scaled image coordinates of 3D points across all views. This matrix, when correctly scaled, should have a low rank (specifically, rank 4 for projective geometry).
  • Recovering Projective Depths: The key innovation is a method to recover the unknown scaling factors (projective depths, $\lambda_{ip}$) for each image point. This is achieved by leveraging the relationship between fundamental matrices ($F_{ij}$) and epipoles ($e_{ij}$) estimated from pairs of images. Equation (2) provides a crucial link: $(F_{ij}q_{jp})\lambda_{jp} = (e_{ij}q_{ip})\lambda_{ip}$. By solving a system of such equations derived from multiple image pairs, the projective depths can be determined up to an overall scale.
  • Factorization: Once the projective depths are recovered, the measurement matrix $W$ can be formed. A Singular Value Decomposition (SVD) of $W$ is then performed. The first four singular vectors provide the decomposed matrices representing projective motion (camera projection matrices $P_i$) and projective shape (3D point coordinates $Q_p$).
  • Normalization and Balancing: To improve numerical stability, the authors employ two preprocessing steps:
  • Image Normalization: Image coordinates are transformed using a similarity transformation to center them at the origin and normalize their scale. This is crucial for robust factorization.
  • Matrix Balancing: The rescaled measurement matrix $W$ is further balanced by applying column-wise and row-triplet-wise scaling to ensure that all entries have a similar magnitude, which helps mitigate the effects of noise and improves the SVD's performance.

Datasets

The paper evaluates its algorithm using both simulated and real image data.

  • Simulated Data: Experiments were conducted using synthetic scenes with points distributed in a sphere. Three camera motion configurations were simulated: lateral movement, translation towards the scene, and circular movement. Noise was added to image coordinates to test robustness.
  • Real Image Data: Two real image sequences were used:
  • House Sequence: A sequence of 6 images of a wooden house with 38 tracked points.
  • Castle Sequence: A sequence of 11 images of a castle with 28 tracked points, for which 3D ground truth was available.

Key Insights and Ideas

  • Projective Depths as the Missing Link: The paper elegantly demonstrates that the "projective depths" are the crucial missing piece to bridge the gap between uncalibrated image measurements and projective structure/motion recovery using factorization.
  • Fundamental Matrices and Epipoles as Depth Estimators: It's surprising and powerful that standard tools for pairwise epipolar geometry (fundamental matrices and epipoles) can be repurposed to estimate the necessary scaling factors for a multi-view factorization approach.
  • The Importance of Normalization: The results strongly highlight that working with normalized image coordinates is not just a minor optimization but a critical step for achieving accurate and stable projective reconstruction, especially in the presence of noise.
  • Factorization Extends to Projective Geometry: The work successfully extends the elegant factorization framework, previously confined to affine projections, to the more general projective case, significantly broadening its applicability.

Key Results

  • Accurate Reconstruction: The algorithm demonstrates accurate projective reconstruction for both simulated and real images. For the castle sequence, the RMS error was 4.45 mm for an object size of approximately 220mm, and the reprojection error was less than 0.02 pixels.
  • Robustness to Noise: The algorithm shows good robustness to noise, with 2D errors being comparable to the noise level for configurations 1 and 3. However, configuration 2 (translation towards the scene) proved more sensitive, with 3D errors increasing rapidly with noise.
  • Benefit of More Views: Increasing the number of views generally leads to more accurate reconstructions, with 20 views reducing the 3D error by 50% compared to 2 views.
  • Impact of Normalization and Balancing: Experiments show that normalization significantly improves results, preventing errors from becoming "off scale" even with minimal noise. Balancing further improves 3D errors by up to 20%.

Limitations and Future Work

  • Configuration Sensitivity: The algorithm struggles with configurations where camera motion is directly towards the scene (configuration 2), as points lying on the line connecting projection centers cannot be recovered, and reconstruction of nearby points is highly inaccurate.
  • Chaining Strategy: The current method recovers depths by chaining equations sequentially (e.g., $F_{12}, F_{23}, \dots$). The authors suggest investigating more stable chaining strategies and considering uncertainty estimates of fundamental matrices for more robust equation selection.
  • Handling Missing Points: The current implementation assumes points are visible in all images. A future direction is to extend the method to handle points that are not visible in all views.
  • Higher-Order Tensors: The paper primarily uses fundamental matrices (bilinear constraints). Future work could explore extending the method to use trilinear and quadrilinear matching tensors for potentially richer reconstruction.
  • Numerical Conditioning: While normalization and balancing help, unbalanced scaling of fundamental matrices and epipoles could still lead to numerically ill-conditioned factorization. The authors mention re-balancing the recovered depth matrix, but further investigation into robust scaling policies is suggested.

Summary updated

BibTeX
@inproceedings{sturm1996factorization,
  author = {Peter F. Sturm and Bill Triggs},
  title = {{A Factorization Based Algorithm for Multi-Image Projective Structure and Motion}},
  booktitle = {European Conference on Computer Vision},
  year = {1996},
  doi = {10.1007/3-540-61123-1\_183},
}
Figure