Optimal structure from motion: Local ambiguities and global estimates

"Structure From Motion" (SFM) refers to the problem of estimating spatial p roperties of a three-dimensional scene from the motion of its projection on to a two-dimensional surface, such as the retina. We present an analysis of SFM which results in algorithms that are provably convergent and provably optimal with respect to a chosen norm. In particular, we cast SFM as the minimization of a high-dimensional quadra tic cost function, and show how it is possible to reduce it to the minimiza tion of a two-dimensional function whose stationary points are in one-to-on e correspondence with those of the original cost function. As a consequence , we can plot the reduced cost function and characterize the configurations of structure and motion that result in local minima. As an example, we dis cuss two local minima that are associated with well-known visual illusions. Knowledge of the topology of the residual in the presence of such local mi nima allows us to formulate minimization algorithms that, in addition to pr ovably converge to stationary points of the original cost function, can swi tch between different local extrema in order to converge to the global mini mum, under suitable conditions. We also offer an experimental study of the distribution of the estimation error in the presence of noise in the measur ements, and characterize the sensitivity of the algorithm using the structu re of Fisher's Information matrix.