Exact Simultaneous Recovery of Locations and Structure from Known Orientations and Corrupted Point Correspondences
Let t[subscript 1],…,t[subscript nl] ∈Rd and p[subscript 1],…,p[subscript n[subscript s]] ∈ R[superscript d] and consider the bipartite location recovery problem: given a subset of pairwise direction observations {(t[subscript i]−p[subscript j])/∥t[subscript i]−p[subscript j]∥2}[subscript i,...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2018
|
| Online Access: | http://hdl.handle.net/1721.1/117027 https://orcid.org/0000-0002-5798-3509 https://orcid.org/0000-0002-1624-6238 |
| Summary: | Let t[subscript 1],…,t[subscript nl] ∈Rd and p[subscript 1],…,p[subscript n[subscript s]] ∈ R[superscript d] and consider the bipartite location recovery problem: given a subset of pairwise direction observations {(t[subscript i]−p[subscript j])/∥t[subscript i]−p[subscript j]∥2}[subscript i,j∈[nℓ]×[ns]], where a constant fraction of these observations are arbitrarily corrupted, find {t[subscript i]}[subscript i∈[nℓ]] and {pj}[subscript j∈[ns]] up to a global translation and scale. This task arises in the Structure from Motion problem from computer vision, which consists of recovering the three-dimensional structure of a scene from photographs at unknown vantage points. We study the recently introduced ShapeFit algorithm as a method for solving this bipartite location recovery problem. In this case, ShapeFit consists of a simple convex program over d(n[subscript l]+n[subscript s]) real variables. We prove that this program recovers a set of n[subscript l]+n[subscript s] i.i.d. Gaussian locations exactly and with high probability if the observations are given by a bipartite Erdős–Rényi graph, d is large enough, and provided that at most a constant fraction of observations involving any particular location are adversarially corrupted. This recovery theorem is based on a set of deterministic conditions that we prove are sufficient for exact recovery. Finally, we propose a modified pipeline for the Structure for Motion problem, based on this bipartite location recovery problem.
Keywords: Structure from Motion, Corruption robust recovery, Convex programming |
|---|