Abstract
A technique is presented for computing 3D scene structure from point and line features in monocular image sequences. Unlike previous methods, the technique guarantees the completeness of the recovered scene, ensuring that every scene feature that is detected in each image is reconstructed. The approach relies on the presence of four or more reference features whose correspondences are known in all the images. Under an orthographic or affine camera model, the parallax of the reference features provides constraints that simplify the recovery of the rest of the visible scene. An efficient recursive algorithm is described that uses a unified framework for point and line features. The algorithm integrates the tasks of feature correspondence and structure recovery, ensuring that all reconstructible features are tracked. In addition, the algorithm is immune to outliers and feature drift, two weaknesses of existing structure from motion techniques. Experimental results are presented for real images.
Introduction
In the mid-1990s, Structure-from-Motion (SfM) algorithms were notoriously "leaky." Most relied on tracking features from frame to frame. If a tracker lost a point due to noise or a sudden movement, that part of the 3D structure was gone forever. Consequently, these methods usually produced sparse, incomplete reconstructions. Seitz and Dyer identified three major gaps in the existing literature: incompleteness of reconstructed features, sensitivity to outliers where bad matches ruined the model, and feature drift where small errors accumulated into warped geometry. This paper introduces a system designed to reconstruct every physically reconstructible feature in a scene.
Methodology
The core of the approach is the Affine Camera Model. While perspective cameras are more realistic, the affine model (which assumes the scene is far from the camera) simplifies the mathematical formulation significantly. The "secret sauce" is the use of four non-coplanar reference points. Once these four points are identified in every image, a global coordinate system can be defined. The movement of any other point in the image—relative to these four anchors—is defined as parallax.
Key technical components include:
- Epipolar Constraints: Using the four reference points to calculate epipolar lines. For any point in one image, its match in a subsequent image must lie on a specific line, reducing a 2D search to a 1D search.
- Recursive Voting Scheme: Instead of immediate "hard" matching, the algorithm uses a recursive voting process. Each image contributes to a probability space for a 3D feature's location. Over time, the true 3D location emerges as the peak.
- Image Rectification: Images are warped so that all epipolar lines are horizontal, allowing for extremely efficient table-lookup matching.
Experimental Evaluation
The paper evaluates the algorithm on two primary real-world sequences. The first is a Rotating Cube Sequence, featuring a Rubik’s Cube on a turntable captured over 83 images. This tested the algorithm's ability to handle long sequences and many features (83 points).
The second is an Outdoor Building Scene, consisting of eight images of a university building from varying viewpoints. This tested the robustness of the affine assumption on a large-scale, static object with fewer frames.
Results and Discussion
The algorithm demonstrated remarkable robustness. In the cube sequence, it successfully filtered out "outlier" lines—features on the background that did not move with the cube. Efficiency was also a highlight; on a 1995-era Sun SPARC 10 workstation, the algorithm processed roughly 12 frames per second.
Despite the successes, the authors noted several limitations. The method is heavily dependent on the accurate tracking of the initial four "anchor" points. Additionally, the basic version assumes features are visible in every frame, leaving temporal occlusions for future work. Finally, while the affine model is efficient, it can introduce geometric distortion in scenes with significant depth, suggesting a need for extension to full projective camera models.
Conclusion
Seitz and Dyer's work provides a robust framework for complete scene reconstruction. By shifting from local frame-to-frame tracking to a global parallax-based voting scheme anchored by four reference points, they achieved a level of completeness and outlier immunity that was previously unattainable in SfM tasks.
Summary updated