Optimization Online


A QCQP Approach to Triangulation

Chris Aholt(aholtc***at***uw.edu)
Sameer Agarwal(sameeragarwal***at***google.com)
Rekha Thomas(rrthomas***at***uw.edu)

Abstract: Triangulation of a three-dimensional point from $n\ge 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.

Keywords: QCQP, Computer Vision, Triangulation, SDP

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Nonlinear Optimization (Quadratic Programming )

Citation: To appear in the proceedings of the 12th European Conference on Computer Vision (ECCV 2012).

Download: [PDF]

Entry Submitted: 07/31/2012
Entry Accepted: 07/31/2012
Entry Last Modified: 07/31/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society