We use segmentations to match images by shape. The new matching technique does not require point-to-point edge correspondence and is robust to small shape variations and spatial shifts. To address the unreliability of segmentations computed bottom-up, we give a closed form approximation to an average over all segmentations. Our method has many extensions, yielding new algorithms for tracking, object detection, segmentation, and edge-preserving smoothing. For segmentation, instead of a maximum a posteriori approach, we compute the "central" segmentation minimizing the average distance to all segmentations of an image. For smoothing, instead of smoothing images based on local structures, we smooth based on the global optimal image structures. Our methods for segmentation, smoothing, and object detection perform competitively, and we also show promising results in shape-based tracking.

We give the first complete theoretical convergence analysis for the iterative extensions of the Sturm/Triggs algorithm. We show that the simplest extension, SIESTA, converges to nonsense results. Another proposed extension has similar problems, and experiments with "balanced" iterations show that they can fail to converge or become unstable. We present CIESTA, an algorithm which avoids these problems. It is identical to SIESTA except for one simple extra computation. Under weak assumptions, we prove that CIESTA iteratively decreases an error and approaches fixed points. With one more assumption, we prove it converges uniquely. Our results imply that CIESTA gives a reliable way of initializing other algorithms such as bundle adjustment. A descent method such as Gauss-Newton can be used to minimize the CIESTA error, combining quadratic convergence with the advantage of minimizing in the projective depths. Experiments show that CIESTA performs better than other iterations.

We present a model based approach to the integration of multiple cues for tracking high degree of freedom articulated motions and model refinement. We then apply it to the problem of hand tracking using a single camera sequence. Hand tracking is particularly challenging because of occlusions, shading variations, and the high dimensionality of the motion. The novelty of our approach is in the combination of multiple sources of information, which come from edges, optical flow, and shading information in order to refine the model during tracking. We first use a previously formulated generalized version of the gradient-based optical flow constraint, that includes shading flow i.e., the variation of the shading of the object as it rotates with respect to the light source. Using this model we track its complex articulated motion in the presence of shading changes. We use a forward recursive dynamic model to track the motion in response to data derived 3D forces applied to the model. However, due to inaccurate initial shape, the generalized optical flow constraint is violated. We use the error in the generalized optical flow equation to compute generalized forces that correct the model shape at each step. The effectiveness of our approach is demonstrated with experiments on a number of different hand motions with shading changes, rotations and occlusions of significant parts of the hand.

For two-image structure from motion, we present a simple, exact expression for a least-squares image-reprojection error for finite motion that depends only on the motion. Optimal estimates of the structure and motion can be computed by minimizing this expression just over the motion parameters. Also, we present a solution to the triangulation problem: an exact, explicit expression for the optimal structure estimate given the motion. We identify a new ambiguity in recovering the structure for known motion. We study the exact error's properties experimentally and demonstrate that it often has several local minima for forward or backward motion estimates. Our experiments also show that the "reflected" local minimum of Oliensis (2001) and Soatto et al. (1998) occurs for large translational motions. Our exact results assume that the camera is calibrated and use a least-squares image-reprojection error that applies most naturally to a spherical imaging surface. We approximately extend our approach to the standard least-squares error in the image plane and uncalibrated cameras. We present an improved version of the Sampson error which gives better results experimentally.

We describe algorithms for computing projective structure and motion from a multi-image sequence of tracked points. The algorithms are essentially linear, work for any motion of moderate size, and give accuracies similar to those of a maximum-likelihood estimate. They give better results than the factorization approach of Sturm and Triggs (1996) and are equally fast and they are much faster than bundle adjustment. Our experiments show that the (iterated) Sturm-Triggs approach often fails for linear camera motions. In addition, we study experimentally the common situation where the calibration is fixed and approximately known, comparing the projective versions of our algorithms to mixed projective/Euclidean strategies. We clarify the nature of dominant-plane compensation, showing that it can be considered a small-translation approximation rather than an approximation that the scene is planar. We show that projective algorithms accurately recover the (projected) inverse depths and homographies despite the possibility of transforming the structure and motion by a projective transformation.

We present a fast factorization algorithm for estimating structure and motion simultaneously from points, lines, and/or directly from the image intensities under full perspective. It generalizes the Oliensis method for points to include lines and intensities as well.

We present two linear algorithms for recovering the camera motion and 3D scene structure directly from the image data in a a multi-image sequence. The first algorithm generalizes the point-based approach of Oliensis (1999) to intensities. The second generalizes the Lucas-Kanade (1981) optical-flow method to a direct method.

Demonstrates the existence of an approximate, intrinsic ambiguity in Euclidean structure from motion (SFM) which occurs as generically as the bas-relief ambiguity but, unlike it, strengthens for scenes with more depth variation. The ambiguity does not occur in projective SFM, but the reasons for this make projective reconstructions more likely to have large errors. Our analysis gives a semiquantitative characterization of the least-squares error surface over a domain complementary to that analyzed by Jepson, Heeger, and Maybank. As part of our analysis, we show that the least-squares error for infinitesimal motion-the optical-flow error-gives a good approximation to the least-squares error for moderate finite motions. We propose that many high-error local minima occur for epipoles in or near the image. We also establish the existence of a new local minimum in minimizing over the rotation, given the translation direction.

This paper demonstrates the existence of a generic approximate ambiguity in Euclidean structure from motion (SFM) which applies to scenes with large depth variation. In projective SFM the ambiguity is absent, but the maximum-likelihood reconstruction is more likely to have occasional very large errors. The analysis gives a semi-quantitative characterization of the least-squares error surface over a domain complementary to that analyzed by Jepson/Heeger/Maybank.

We describe new techniques for self-calibration and for recovering the motion from a projective reconstruction when the calibration is known. We show that our approach deals with the ambiguities in self-calibration produced by special motions. We extend our techniques to deal with varying calibration parameters. In passing, we prove convergence for the iterative projective-reconstruction algorithm of (Sturm and Triggs, 1996) and (Berthilsson et al., 1997).

We describe new algorithms for multi-frame structure from motion from tracked point features. The algorithms are essentially linear and give accuracies similar to those of a maximum-likelihood estimate. For the common situations where the calibration is fixed and approximately known, we experimentally compare the fully projective versions of our algorithms to mixed projective/Euclidean strategies. Our theoretical results clarify the nature of dominant-plane compensation and the effect of calibration error on translation recovery.

We describe two new algorithms for two-frame structure from motion from tracked point features. One is the first fast algorithm for computing an exact least-squares estimate. It exploits our observation that the rotationally invariant least-squares error can be written in a simple form that depends just on the motion. The other is essentially as accurate as the least-squares estimate and is more efficient, probably faster, and potentially more robust than previous algorithms of comparable accuracy. We also analyze theoretically the accuracy of the optical-flow approximation to the least-squares error.

The problem of structure from motion (SFM) is to obtain a 3D model of a scene using multiple images taken from different camera locations. Traditional SFM algorithms using just two images often produce inaccurate 3D reconstructions, mainly due to incorrect estimation of the camera's motion. More recent algorithms have used multiple (>2) image sequences. This paper describes a new incremental algorithm for reconstructing structure from multi-image sequences which estimates and corrects for the error in computing the camera motion. Experimental results of the algorithm are reported on one synthetic and three real image sequences. Unlike many previous incremental algorithms, the new algorithm in principle is capable of reconstructing a 3D model of the scene to arbitrary accuracy given a sufficient number of images. It is demonstrated experimentally that the algorithm gives superior results compared to others which do not correct for the error in recovering motion.

We describe an essentially algorithm-independent experimental comparison of projective versus Euclidean reconstruction. The Euclidean approach is as accurate as the projective one, even with significant calibration error and for the pure projective structure. Projective optimization has less of a local-minima problem than its Euclidean equivalent. We describe techniques that enhance the convergence of optimization algorithms.

We present a new algorithm for computing the heading from multiple frames which improves on previous approaches. It exploits our discovery and analysis of a new structure-from-motion ambiguity. Allowing for this ambiguity also makes two-frame reconstruction more robust. We show experimentally that the error landscape for planar scenes has few significant local minima.

We recently demonstrated a new approach to multiframe structure from motion from point features which, in the appropriate domain, provably reconstructs structure and motion correctly. The algorithm works for general motion and large perspective effects. In this paper, we describe how to adapt our approach to translational motion lying along a line or in a plane, with arbitrary rotations. An analysis of the bas-relief effect for multiple-motion sequences is also presented.

Image deformations due to relative motion between an observer and an object may be used to infer 3-D structure. Up to the first order, these deformations can be written in terms of an affine transform. A novel approach is adopted to measuring affine transforms which correctly handles the problem of corresponding deformed patches. The patches are filtered using Gaussians and derivatives of Gaussians and the filters deformed according to the affine transform. The problem of finding the affine transform is therefore reduced to that of finding the appropriate deformed filter to use. In the special case where the affine transform can be written as a scale change and an in-plane rotation, the Gaussian and first derivative equations are solved for the scale. The robustness of the method is demonstrated experimentally.>

A global algorithm for reconstructing shape from shading is described. This algorithm incorporates an earlier local algorithm that has been shown to be capable of fast, robust surface reconstruction for general surfaces if a small amount of information on the surface is provided. The new algorithm is capable of determining this information automatically, and thus can reconstruct a general surface from shading with no a priori information on the surface. In experimental tests on complex synthetic images, this algorithm has produced good surface reconstructions over most of the image. For 128 /spl times/ 128 images, the reconstruction took less than 30 s on a DECstation 5000. The algorithm appears noise resistant, giving good reconstructions even with an added pixel noise of /spl plusmn/10%.>

In structure from motion algorithms, the error in the estimated motion affects each reconstructed 3-D point in a systematic way. The authors attempt to isolate the effect of the motion error as correlations in the structure error and show theoretically that these correlations can improve existing multi-frame structure from motion techniques. Experimental results and previously reported work confirm the theoretical predictions.>

A simple local smoothing filter is defined for curves or surfaces, combining the advantages of Gaussian smoothing and Fourier curve description. Unlike Gaussian filters, the filter described has no shrinkage problem. Repeated application of the filter does not yield a curve or surface smaller than the original but simply reproduces the approximate result that would have been obtained by a single application at the largest scale. Unlike Fourier description, the filter is local in space. The wavelet transform of Y. Meyer (1989) is also shown to have these properties.>

A new technique for reconstructing the 3-D structure and motion of a scene undergoing relative rotational motion with respect to the camera is discussed. Given image correspondences of point features tracked over many frames, a two-stage technique for reconstruction is presented. A grouping algorithm that exploits spatio-temporal constraints of the common motion to achieve a reliable description of discrete point correspondences as curved trajectories in the image plane is developed. In contrast, trajectories fitted to points independent of each other lead to arbitrary image descriptions and very inaccurate 3-D parameters. A new closed-form solution, under perspective projection, for the 3-D motion and location of points from the computed image trajectories is also presented. Both stages are applied to real image sequences with good results. This approach represents a first step in a longer-term research effort examining the role of explicit spatio-temporal organization in the interpretation of scenes from dynamic images.>

An approach to shape-from-shading that is based on a connection with a calculus of variations/optimal control problem is proposed. An explicit representation corresponding to a shaded image is given for the surface; uniqueness of the surface (under suitable conditions) is an immediate consequence. The approach leads naturally to an algorithm for shape reconstruction that is simple, fast, provably convergent (in many cases, provably convergent to the correct solution), and does not require regularization. Given a continuous image, the algorithm can be proved to converge to the continuous surface solution as the image sampling frequency is taken to infinity. Experimental results are presented for synthetic and real images.>

A simple local smoothing filter for curves or surfaces, combining the advantages of Gaussian smoothing and Fourier curve description, is defined. Unlike Gaussian filters, the filter described has no shrinkage problem. Repeated application of the filter does not yield a curve or surface smaller than the original, but simply reproduces the approximate result that would have been obtained by a single application at the largest scale. Unlike Fourier description, the filter is local in space. The wavelet transform of Y. Meyer (1989) is shown to have these properties.>

For general objects, and for illumination from a general direction, the constraints on shape imposed by shading are studied. It is argued that, for a typical image, shading determines shape essentially up to a finite ambiguity. Thus regularization is often unnecessary and should be avoided. For some images, shape from shading is a partially well-constrained problem: the surface is uniquely determined over most of the image, but infinitely ambiguous in small regions bordering the image boundary, even though the image contains singular points. The main result is that, contrary to previous belief, the image of the occluding boundary does not strongly constrain the surface solution. It is shown that characteristic strips are curves of steepest ascent on the imaged surface. A theorem characterizing the properties of generic images is presented.>

A novel technique is presented for reconstructing the 3-D structure, and motion, of a scene undergoing relative rotational motion with respect to the camera. Given image correspondences of point features tracked over many frames, first, a grouping algorithm developed which exploits spatio-temporal constraints of the common motion to achieve a reliable description of discrete point correspondences as curved trajectories (general conics in the case of rotational motion) in the image plane. In contrast, trajectories fitted to points independent of each other lead to arbitrary image descriptions and very inaccurate 3-D parameters. Second, a novel closed-form solution, under perspective projection, for the 3-D motion and location of points from the computed image trajectories is presented. Both stages are applied to real image sequences with good results.>

A generically valid proof of uniqueness for the surface solution to shape from shading is presented. Local surface solutions around a singular point have at most a fourfold ambiguity. These results apply to a reflectance function corresponding to illumination symmetric around the viewer direction of a uniform-albedo Lambertian object. Generic surfaces are studied, and their properties are established. It is noted that the proof may lead to new, faster algorithms for shape recovery. Questions of existence are also discussed. It is argued that most images are impossible in the sense that they cannot be a depiction of any physical object. The proof is based on ideas of dynamical systems theory, and global analysis.>