TL;DR
This paper introduces a unified approach for merging unconnected feature tracks in video, crucial for robust camera motion estimation and 3D reconstruction. It extends existing methods to novel scenarios like registering multiple independent camera views and recovering from tracking failures due to occlusions, demonstrating practical effectiveness on challenging real-world data.
What Problem Does This Paper Address?
Estimating camera motion and reconstructing 3D scenes from video (Structure-from-Motion or SfM) is a well-established computer vision task. However, a significant challenge arises when tracking feature points across video frames breaks down. This can happen due to occlusions, fast camera movements, or motion blur, leading to "unconnected feature tracks." When these tracks are not properly merged, errors accumulate over time, causing "drift" in the estimated camera poses and 3D scene structure, especially in long sequences. Furthermore, when multiple independent SfM reconstructions of the same scene exist (e.g., from different cameras or after a tracking restart), they need to be registered into a common coordinate system, which also requires merging their feature tracks. Existing methods, often relying on RANSAC, can be computationally expensive and struggle with a high number of outliers.
Methods
The paper proposes a unified framework for merging unconnected feature tracks, building upon existing techniques and introducing novel applications.
- Candidate Selection: The core idea is to identify potential pairs of unconnected feature tracks that likely correspond to the same 3D point. This involves three constraints:
- Proximity Constraint: Feature points should be close in the image plane across different views.
- Similarity Constraint: The appearance (color intensity) around the tracked feature points should be similar. The authors evaluate various similarity measures, finding a combination of SIFT matching and Bhattacharyya distance to be most effective.
- Uniqueness Constraint: To handle repetitive structures, a constraint ensures that a track is not merged with a "wrong" but similar-looking structure.
- Merging Algorithms: Two primary methods are used to merge the selected candidates:
- RANSAC (Random Sample Consensus): A robust statistical method for estimating a transformation (e.g., a 3D similarity transformation) between candidate point pairs. It iteratively samples minimal sets of points to estimate a model and identifies inliers that support it. The paper notes that RANSAC can be computationally expensive with many outliers.
- Spectral Method: An alternative approach adapted from Leordeanu et al. [7]. This method constructs a similarity matrix based on pairwise constraints and then finds the principal eigenvector. The eigenvector's values indicate the confidence of each pair being a valid match, allowing for merging based on confidence scores. The authors suggest this method can be faster than RANSAC.
- Novel Applications: The paper extends these merging techniques to two new scenarios:
- Registration of Multiple Independent Reconstructions: This allows merging SfM results from multiple cameras capturing the same scene simultaneously or registering reconstructions that had to restart due to tracking failures.
- Recovery after Large Occlusions: The framework enables re-establishing a consistent camera motion estimate even when tracking is completely lost for a period.
Datasets
The paper evaluates its methods on three challenging real-world video sequences captured with consumer HDV cameras (1440x1080 resolution, 25 Hz frame rate).
- Example 1 (Drift Removal): A sequence involving two complete loops around an advertising column (2500 frames).
- Example 2 (Multiple Cameras): A scene captured simultaneously by four moving cameras, each with a sequence length of 188 frames.
- Example 3 (Large Occlusions): A market scene sequence (319 frames) where the SfM estimation had to restart twice due to significant occlusions.
The authors also created a ground truth dataset for drift removal by hand-labeling 30 correct matches between two images from the drift sequence.
Key Insights and Ideas
- Unified Framework for Merging: The paper demonstrates that a consistent set of candidate selection criteria (proximity, similarity, uniqueness) and merging algorithms (RANSAC, spectral) can effectively address diverse SfM challenges like drift, multi-camera registration, and recovery from tracking loss.
- Effectiveness of Combined Similarity Measures: The authors found that combining SIFT matching with Bhattacharyya distance for color histograms provides a robust similarity measure, leading to better inlier-outlier ratios, especially in challenging scenarios.
- Spectral Method as a Faster Alternative: The spectral method offers a computationally efficient alternative to RANSAC for merging feature tracks, particularly when dealing with a large number of candidates.
- Practical Applicability to Novel Scenarios: The core contribution lies in showing how these merging techniques can be successfully applied to previously unaddressed problems like registering multiple independent SfM reconstructions and recovering from complete tracking failures.
Key Results
- Drift Removal: The spectral method achieved results comparable to RANSAC but with a 25% speedup in computation time for the drift removal example. In total, 8055 out of 34214 object points were merged in this sequence.
- Multiple Camera Registration: The algorithm successfully registered four independent SfM reconstructions of a scene captured by multiple cameras, even with moving objects and repetitive structures. The resulting merged camera path and 3D point cloud were visually consistent.
- Recovery after Large Occlusions: The framework successfully registered three independent SfM reconstructions that were generated after tracking restarts due to large occlusions. Virtual 3D objects rendered into the scene showed no visual misalignments or jitter, indicating successful alignment.
Limitations and Future Work
- Computational Cost: While the spectral method offers a speedup, RANSAC can still be computationally intensive, especially with a low inlier-outlier ratio. The paper mentions that assuming a similarity transformation (7 parameters instead of 15 for affine) can reduce the RANSAC computational effort.
- Approximation in Covariance: The paper notes that assuming the covariance matrix of 3D object points is not changed by a transformation (H) is an approximation, although it works well in practice.
- Future Work: The authors suggest that this unified technique is an important step towards fully automatic camera motion estimation in difficult situations. Further exploration of more advanced similarity measures and optimization strategies could be beneficial. The paper also hints at the potential for using these techniques in other SfM-related problems.
Summary updated