A QCQP Approach to Triangulation
Venue
European Conference on Computer Vision, Springer Verlag (2012)
Publication Year
2012
Authors
Chris Aholt, Rekha Thomas, Sameer Agarwal
BibTeX
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 sucient 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.
