Optimal Structure From Motion: Local Ambiguities and Global Estimates

"Structure From Motion" (SFM) refers to the problem of estimating three-dimensional information about the environment from the motion of its two-dimensional projection onto a surface (for instance the retina). We present an analysis of SFM from the point of view of noise. This analysis results in algorithms that are provably convergent and provably optimal with respect to a chosen norm. In particular, we cast SFM as a nonlinear optimization problem and define a bilinear projection iteration that converges to fixed points of a certain cost-function. We then show that such fixed points are "fundamental", i.e. intrinsic to the problem of SFM and not an artifact introduced by our algorithms. We classify and interpret geometrically local extrema, and we argue that they correspond to phenomena observed in visual psychophysics. Finally, we show under what conditions it is possible - given convergence to a local extremum - to "jump" to the valley containing the optimum; this leads us to sugges..