Enhanced Continuous Tabu Search for Parameter Estimation in Multiview Geometry

Guoqing Zhou, Qing WangICCV 2013 · DOI

Abstract

Parameter estimation is a fundamental challenge in multiview geometry, particularly for tasks like triangulation and resection. While $L_\infty$ norm optimization offers robustness due to its quasi-convex nature, it is often computationally prohibitive for large-scale datasets. This paper presents Enhanced Continuous Tabu Search (ECTS), a meta-heuristic approach that combines memory-based search strategies with the pseudo-convex properties of reprojection errors. ECTS achieves global optima up to 280x faster than traditional bisection methods, demonstrating superior scalability and accuracy on both synthetic and real-world benchmarks.

Introduction

In computer vision, tasks such as 3D reconstruction (triangulation) and camera pose estimation (resection) rely heavily on accurate parameter estimation. Traditionally, these problems are framed as $L_2$ norm optimization, which minimizes the sum of squared errors. However, the resulting objective functions are non-convex and prone to local minima. $L_\infty$ norm optimization, which minimizes the maximum error, is quasi-convex and thus more robust, but standard global optimization techniques like bisection scale poorly with increasing data points and views.

The authors address this efficiency gap by introducing ECTS, adapting Tabu Search—a meta-heuristic originally designed for discrete combinatorial optimization—to the continuous domain of geometric problems. By leveraging the specific mathematical properties of reprojection errors, ECTS provides a fast, reliable path to global optimality.

Methodology

The ECTS framework optimizes the search process through three distinct phases:

  1. Diversification: To avoid searching the entire solution space, a fast linear algebraic method provides an initial estimate. A "bounding convex hull" is then constructed around this point using linear programming, effectively isolating the region containing the global optimum.
  2. Intensification: Within the identified region, the algorithm performs a local search. A "Tabu List" (a memory structure) stores recently visited areas to prevent the search from becoming trapped in cycles or local minima, allowing the algorithm to "escape" sub-optimal regions.
  3. Guided Search: Leveraging the pseudo-convex nature of reprojection errors, ECTS uses the gradient as a descent direction to generate candidate solutions. This makes the search significantly more efficient than stochastic or "blind" global optimizers.

Crucially, the authors provide a theoretical proof that ECTS converges to the global optimum with probability one.

Experimental Evaluation

The algorithm was evaluated on both synthetic and well-known real-world benchmarks:

  • Synthetic Data: Simulated 3D scenes with up to 1,000 views and varying levels of Gaussian noise.
  • VGG Datasets: Classic computer vision benchmarks including the Model House, Wadham College, Dinosaur, and Oxford datasets.
  • Large-Scale Data: The Notre Dame Cathedral sequence, involving 212 images and 27,000 tracks.

Results and Discussion

ECTS demonstrates significant improvements in both speed and accuracy compared to state-of-the-art bisection methods.

Comparison of RMS error between the proposed ECTS method and the standard bisection approach across varying numbers of views.

Performance and Scalability

On synthetic triangulation tasks, ECTS was 280.5x faster than the standard Bisect-I algorithm for 10-view problems. Its efficiency remains high even as the problem size grows; at 1,000 views, it remained nearly 10x faster than the baseline. Notably, in the "Full Dinosaur" dataset—comprising nearly 5,000 points and 15,000 unknowns—ECTS successfully converged in approximately 17 minutes, whereas other solvers like Bisect-II and Gugat failed due to memory constraints.

3D reconstruction of the Dinosaur dataset, a large-scale benchmark where ECTS demonstrated superior scalability.

Accuracy

Across almost all real-world datasets, ECTS achieved lower Root Mean Square (RMS) errors than the bisection baseline. This indicates that the massive speed gains do not come at the expense of precision. The integration of AI-driven memory strategies with traditional geometric optimization allows the algorithm to navigate complex error surfaces more effectively than traditional calculus-based methods.

Conclusion

Enhanced Continuous Tabu Search represents a significant advancement in global optimization for multiview geometry. By utilizing pseudo-convexity and memory-based search, it overcomes the computational bottlenecks of traditional $L_\infty$ methods. While the algorithm's performance can be sensitive to the quality of the initial linear estimate, its convergence to the global optimum is guaranteed. Future work may extend this framework to full Structure-from-Motion (SfM) pipelines and complex camera calibration tasks.

Summary updated

BibTeX
@inproceedings{zhou2013enhanced,
  author = {Guoqing Zhou and Qing Wang},
  title = {{Enhanced Continuous Tabu Search for Parameter Estimation in Multiview Geometry}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2013},
  doi = {10.1109/iccv.2013.402},
}
Figure