A Fast Optimal Algorithm for L 2 Triangulation
A Fast Optimal Algorithm for L 2 Triangulation
- New search for: Lu, Fangfang
- New search for: Hartley, Richard
- New search for: Lu, Fangfang
- New search for: Hartley, Richard
Abstract This paper presents a practical method for obtaining the global minimum to the least-squares (L 2) triangulation problem. Although optimal algorithms for the triangulation problem under L ∞ -norm have been given, finding an optimal solution to the L 2 triangulation problem is difficult. This is because the cost function under L 2-norm is not convex. Since there are no ideal techniques for initialization, traditional iterative methods that are sensitive to initialization may be trapped in local minima. A branch-and-bound algorithm was introduced in [1] for finding the optimal solution and it theoretically guarantees the global optimality within a chosen tolerance. However, this algorithm is complicated and too slow for large-scale use. In this paper, we propose a simpler branch-and-bound algorithm to approach the global estimate. Linear programming algorithms plus iterative techniques are all we need in implementing our method. Experiments on a large data set of 277,887 points show that it only takes on average 0.02s for each triangulation problem.
Document information
A Fast Optimal Algorithm for L 2 Triangulation
Computer Vision – ACCV 2007 ; 4 ; 279-288
Lecture Notes in Computer Science ; 4844 , 4
2007-01-01
10 pages
Article/Chapter (Book)
Electronic Resource
English
Similar titles
Fast Optimal Three View Triangulation
| Springer Verlag | 2007
Delaunay Triangulation in d-Dimensional Space: A Triangulation-Growth Algorithm
| British Library Conference Proceedings | 1995
Advancing-Front Algorithm For Delaunay Triangulation
| NTRS | 1993
Efficient Suboptimal Solutions to the Optimal Triangulation
| British Library Online Contents | 2011