A QCQP Approach to Triangulation

Chris Aholt¹, Sameer Agarwal², and Rekha Thomas¹

¹University of Washington, USA

²Google Inc., USA

Abstract. Triangulation of a three-dimensional point from n  2 two-dimensional images can be formulated as a quadratically constrained quadratic program. We propose an algorithm to extract candidate solutions to this problem from its semidefinite programming relaxations. We then describe a sufficient condition and a polynomial time test for certifying when such a solution is optimal. This test has no false positives. Experiments indicate that false negatives are rare, and the algorithm has excellent performance in practice. We explain this phenomenon in terms of the geometry of the triangulation problem.

LNCS 7572, p. 654 ff.

Full article in PDF | BibTeX

lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012