POLYNOMIAL METHODS FOR STRUCTURE FROM MOTION

Most structure from motion (SFM) methods presented in the literature have the following demonstrated problems. First, the nonlinear least-squares methods are crucially dependent on a good starting point. Second, the linear methods depend on the distribution of errors, since they omit certain necessary constraints. They only work well for larger numbers of data points where such errors tend to cancel. Third, they generally ignore the multiple solutions of a set of nonlinear equations, and use the nonlinear least-squares method to find zeros; the nonlinear least squares often converges to a local minimum and not to zero. We propose the use of a polynomial system of equations, with the unit quaternions representing rotation, to recover SFM under perspective projection. We combine the equations by the method of resultants with the MAXIMA symbolic algebra system, reducing the system to a single polynomial. Then, we find its real roots with Sturm sequences. Since this system has multiple solutions, we use a hypothesize and verify scheme to eliminate the incorrect ones. Hypothesize and verify diminishes the sensitivity of using polynomial equations. We examine the effect of different rotation axes and angles on SFM accuracy and compare the performance of our algorithm to a few earlier approaches. Generally we found that large rotation angles are more important than multiple frames for structure recovery. Our results show that a large amount of motion is the most important factor in getting good SFM accuracy. © 1990 IEEE