| Recovering the relative motion of a moving camera from images is a classic problem in computer vision. In addition to being an important problem in its own right, the successful recovery of camera motion is vital for tasks such as building 3D models, recognition, robot localization, navigation, and map building, just to name a few. The two parts to most motion recovery algorithms are matching, or correspondence, and the estimation of epipolar geometry. The most difficult of these, and arguably one of the most difficult tasks in all of image processing, is in determining correspondence. In fact, one can recover the epipolar geometry of a moving camera without having solved for correspondences perfectly, however even knowing the epipolar geometry does not always ensure a solution to the correspondence problem. While motion estimation is well-studied when the camera motion is relatively small, the problem becomes even more difficult as the camera motions get larger (large rotation or wider baseline).; In this thesis, our primary objective is to present a family of algorithms designed to provide robust estimation of camera motions while circumventing the difficult task of identifying correspondences. For 3D rotations, our approach is based on maximizing the overlap of spherical images. Such a computation can be expressed as a spherical correlation, which in turn can be computed as a multiplication of the images' spherical Fourier transforms. This method requires neither correspondences nor features.; For general 3D motions, we present a novel approach using the Radon transform. The feasibility of any camera motion is computed by integrating over all feature pairs that satisfy the epipolar constraint. This integration is equivalent to taking the inner product of a similarity function on feature pairs with a Dirac function embedding the epipolar constraint. The maxima in this five dimensional motion space will correspond to compatible rigid motions. The main novelty is in the realization that the Radon transform is a filtering operator: If we assume that the similarity and Dirac functions are defined on spheres and the epipolar constraint is a group action of rotations on spheres, then the Radon transform is a correlation integral. We propose a new algorithm to compute this integral from the spherical harmonics of the similarity and Dirac functions. Generating the similarity function now becomes a preprocessing step which reduces the complexity of the Radon computation by a factor equal to the number of feature pairs processed. The strength of the algorithm is in avoiding a commitment to correspondences, thus being robust to erroneous feature detection, outliers, and multiple motions.; In developing the algorithms to study camera motions, we have also built a foundation for addressing difficult data association tasks with a novel combination of robust, exhaustive algorithms and theoretical harmonic analysis techniques. This framework is quite general and applies to various seemingly unrelated problems. In this thesis we examine two specific tasks: automatic alignment of 3D point clouds, and 3D model retrieval. |
