Introduction
This research extends the classic Tomasi-Kanade factorization method—originally designed for point features—to work with line correspondences. By leveraging an affine camera model and a novel four-step linear pipeline, the authors demonstrate how to robustly recover 3D structure and motion using as few as seven lines across three views.
Problem Statement
In the mid-1990s, Structure from Motion (SfM) was a primary focus in computer vision. While factorization techniques using Singular Value Decomposition (SVD) had successfully split image data into shape and motion for point features, applying this to line segments proved difficult.
Lines are often more desirable than points because they are easier to detect reliably in noisy images and provide more structural information. However, the mathematics governing lines are traditionally non-linear and unstable. Previous attempts to solve this required complex optimizations or over-parameterization that led to brittle solutions. This paper seeks a stable, linear, and computationally efficient way to reconstruct 3D scenes using only line segments.
Methodology
The authors utilize the affine camera model, which simplifies the math of 3D-to-2D projection (covering orthographic, weak perspective, and para-perspective models). Instead of solving for all parameters in a single step, the problem is decomposed into a four-step factorization pipeline:
- Rescaling (Step 0): Line directions in the image are treated as points in a 1D projective space, allowing the data to be rescaled to account for camera depth changes.
- Direction Factorization (Step 1): Rescaled line directions are stacked into a measurement matrix and decomposed via SVD into camera rotations and 3D line directions.
- Translation Factorization (Step 2): With rotations known, the camera's translation is solved by factorizing constraints from the "interpretation planes" of the lines.
- Shape Factorization (Step 3): Finally, the actual 3D positions of the lines in space are recovered.
By using SVD at each stage, the algorithm remains numerically stable even when the data is slightly singular, such as during minimal camera movement.
Experimental Setup
The paper primarily uses simulated data for evaluation to establish a theoretical proof-of-concept.
- Synthetic Cube: The authors generated a 3D cube with visible line segments and projected them into 2D images using various camera parameters.
- Noise Testing: Varying levels of Gaussian noise (up to 2 pixels) were added to the 2D line endpoints to test the algorithm's robustness.
Key Insights
- The 1D Projective Link: A major contribution is the realization that line projection in an affine camera is mathematically equivalent to a 1D projective reconstruction of points. This allows the use of projective geometry techniques to simplify the affine problem.
- Linearity and Stability: By choosing the affine model over the full perspective model, the authors convert a heavy non-linear problem into a series of linear ones, avoiding the local minima traps of non-linear optimization.
- Minimal Data Requirements: The paper establishes a new theoretical bound: a minimum of seven lines over three views is required for a linear solution. This is a significant reduction from the thirteen lines required for perspective cameras.
Results and Limitations
In simulations, the method produced high-quality reconstructions with up to 2 pixels of image noise. The SVD-based approach ensured the system remained stable even as noise increased. Because the method relies on linear algebra rather than iterative optimization, it is computationally efficient and well-conditioned.
However, the reliance on the affine approximation is a limitation; it becomes less accurate if the object is very close to the camera or has significant depth relative to its distance. Furthermore, the paper assumes the correspondence problem (matching lines across images) is already solved. Future work suggests integrating this into a unified framework that handles both points and lines interchangeably to maximize the utility of all available image features.
Summary updated