This paper studies the problem of reconstructing a planar surface from stereo images of multiple feature points that are known to be coplanar in the scene. We present a direct method by applying maximum likelihood estimation based on a statistical model of image noise. The significant fact about our method is that not only the 3-D position of the surface is reconstructed accurately but its reliability is also computed quantitatively. The effectiveness of our method is demonstrated by doing numerical simulation.

Many techniques have been proposed for segmenting feature point trajectories tracked through a video sequence into independent motions, but objects in the scene are usually assumed to undergo general 3-D motions. As a result, the segmentation accuracy considerably deteriorates in realistic video sequences in which object motions are nearly degenerate. In this paper, we propose a multi-stage unsupervised learning scheme first assuming degenerate motions and then assuming general 3-D motions and show by simulated and real video experiments that the segmentation accuracy significantly improves without compromising the accuracy for general 3-D motions.

Introducing a mathematical model of noise in stereo images, we propose a new criterion for intelligent statistical inference about the scene we are viewing by using the geometric information criterion (geometric AIC). Using synthetic and real-image experiments, we demonstrate that a robot can test whether or not the object is located very far away or the object is a planar surface without using any knowledge about the noise magnitude or any empirically adjustable thresholds.

We present an alternative approach to what we call the "standard optimization", which minimizes a cost function by searching a parameter space. Instead, our approach "projects" in the joint observation space onto the manifold defined by the "consistency constraint", which demands that any minimal subset of observations produce the same result. This approach avoids many difficulties encountered in the standard optimization. As typical examples, we apply it to line fitting and multiview triangulation. The latter produces a new algorithm far more efficient than existing methods. We also discuss the optimality of our approach.

We show that moving objects can be detected from optical flow without using any knowledge about the magnitude of the noise in the flow or any thresholds to be adjusted empirically. The underlying principle is viewing a particular interpretation about the flow as a geometric model and comparing the relative "goodness" of candidate models measured by the geometric AIC.

Many feature tracking algorithms have been proposed for motion segmentation, but the resulting trajectories are not necessarily correct. In this paper, we propose a technique for removing outliers based on the knowledge that correct trajectories are constrained to be in a subspace of their domain. We first fit an appropriate subspace to the detected trajectories using RANSAC and then remove outliers by considering the error behavior of actual video tracking. Using real video sequences, we demonstrate that our method can be applied if multiple motions exist in the scene. We also confirm that the separation accuracy is indeed improved by our method.

We discuss optimal estimation of the current location of a mobile robot by matching an image of the scene taken by the robot with the model of the environment. We first present a theoretical accuracy bound and then give a method that attains that bound, which can be viewed as describing the probability distribution of the current location. Using real images, we demonstrate that our method is superior to the naive least-squares method. We also confirm the theoretical predictions of our theory by applying the bootstrap procedure.

We implement a graphical interface that automatically transforms a figure input by a mouse into a regular figure which the system infers is the closest to the input. The difficulty lies in the fact that the classes into which the input is to be classified have inclusion relations, which prohibit us from using a simple distance criterion. In this letter, we show that this problem can be resolved by introducing the geometric AIC.

Theoretically, corresponding pairs of feature points between two stereo images can determine their 3-D locations uniquely by triangulation. In the presence of noise, however, corresponding feature points may not satisfy the epipolar equation exactly, so we must first correct the corresponding pairs so as to satisfy the epipolar equation. In this paper, we present an optimal correction method based on a statistical model of image noise. Our method allows us to evaluate the magnitude of image noise a posteriori and compute the covariance matrix of each of the reconstructed 3-D points. We demonstrate the effectiveness of our method by doing numerical simulation and real-image experiments.

Introducing a mathematical model of image noise, we formalize the problem of fitting a line to point data as statistical estimation. It is shown that the reliability of the fitted line can be evaluated quantitatively in the form of the covariance matrix of the parameters. We present a numerical scheme called renormalization for computing an optimal fit and at the same time evaluating its reliability. We also present a scheme for visualizing the reliability of the fit by means of the primary deviation pair and derive an analytical expression for the reliability of a line fitted to an edge segment by using an asymptotic approximation. Our method is illustrated by showing simulations and real-image examples.

Introducing a general statistical model of image noise, we present an optimal algorithm for computing 3-D motion from two views without involving numerical search: () the essential matrix is computed by a scheme called renormalization; () the decomposability condition is optimally imposed on it so that it exactly decomposes into motion parameters; () image feature points are optimally corrected so that they define their 3-D depths. Our scheme not only produces a statistically optimal solution but also evaluates the reliability of the computed motion parameters and reconstructed points in quantitative terms.

Feature point tracking over a video sequence fails when the points go out of the field of view or behind other objects. In this paper, we extend such interrupted tracking by imposing the constraint that under the affine camera model all feature trajectories should be in an affine space. Our method consists of iterations for optimally extending the trajectories and for optimally estimating the affine space, coupled with an outlier removal process. Using real video images, we demonstrate that our method can restore a sufficient number of trajectories for detailed 3-D reconstruction.

We compare the convergence performance of different numerical schemes for computing the fundamental matrix from point correspondences over two images. First, we state the problem and the associated KCR lower bound. Then, we describe the algorithms of three well-known methods: FNS, HEIV, and renormalization. We also introduce Gauss-Newton iterations as a new method for fundamental matrix computation. For initial values, we test random choice, least squares, and Taubin's method. Experiments using simulated and real images reveal different characteristics of each method. Overall, FNS exhibits the best convergence properties.

In order to reconstruct 3-D Euclidean shape by the Tomasi-Kanade factorization, one needs to specify an affine camera model such as orthographic, weak perspective, and paraperspective. We present a new method that does not require any such specific models. We show that a minimal requirement for an affine camera to mimic perspective projection leads to a unique camera model, called symmetric affine camera, which has two free functions. We determine their values from input images by linear computation and demonstrate by experiments that an appropriate camera model is automatically selected.

For fitting an ellipse to a point sequence, ML (maximum likelihood) has been regarded as having the highest accuracy. In this paper, we demonstrate the existence of a "hyperaccurate" method which outperforms ML. This is made possible by error analysis of ML followed by subtraction of high-order bias terms. Since ML nearly achieves the theoretical accuracy bound (the KCR lower bound), the resulting improvement is very small. Nevertheless, our analysis has theoretical significance, illuminating the relationship between ML and the KCR lower bound.

Introducing a mathematical model of image noise, we formalize the problem of fitting a conic to point data as statistical estimation. It is shown that the reliability of the fitted conic can be evaluated quantitatively in the form of the covariance tensor. We present a numerical scheme called renormalization for computing an optimal fit and at the same time evaluating its reliability. We also present a scheme for visualizing the reliability of the fit by means of the primary deviation pair. Our method is illustrated by showing simulations and real-image examples.

This paper presents a new method for solving the structure-from-motion problem for optical flow. The fact that the structure-from-motion problem can be simplified by using the linearization technique is well known. However, it has been pointed out that the linearization technique reduces the accuracy of the computation. In this paper, we overcome this disadvantage by correcting the linearized solution in a statistically optimal way. Computer simulation experiments show that our method yields an unbiased estimator of the motion parameters which almost attains the theoretical bound on accuracy. Our method also enables us to evaluate the reliability of the reconstructed structure in the form of the covariance matrix. Real-image experiments are conducted to demonstrate the effectiveness of our method.

The "geometric AIC" and the "geometric MDL" have been proposed as model selection criteria for geometric fitting problems. These correspond to Akaike's "AIC" and Rissanen's "BIC" well known in the statistical estimation framework. Another well known criterion is Schwarz' "BIC", but its counterpart for geometric fitting has not been known. This paper introduces the corresponding criterion, which we call the "geometric BIC", and shows that it is of the same form as the geometric MDL. Our result gives a justification to the geometric MDL from the Bayesian principle.

This paper presents a theoretically best algorithm within the framework of our image noise model for reconstructing 3-D from two views when all the feature points are on a planar surface. Pointing out that statistical bias is introduced if the least-squares scheme is used in the presence of image noise, we propose a scheme called renormalization, which automatically removes statistical bias. We also present an optimal correction scheme for canceling the effect of image noise in individual feature points. Finally, we show numerical simulation and confirm the effectiveness of our method.

A new mathematical formalism is proposed for constructing elements of camera calibration that measure the focal length and the orientation of the camera: the focal length and the camera orientation are computed by detecting, on the image plane, the vanishing points of two sets of lines that are mutually orthogonal in the scene; the distance of the scene coordinate origin from the camera is determined by location, on the image plane, a point whose scene coordinates are known. We show that the separation of the calibration process into atomic modules enables us to not only predict theoretically optimal estimates but also estimate their reliability.