We overview techniques for optimal geometric estimation from noisy observations for computer vision applications. We first describe techniques based on minimization of a given cost function: least squares (LS), maximum likelihood (ML), and Sampson error minimization. We then summarize techniques not based on minimization: one solves a given matrix equation. Different choices of the matrices in it result in different methods: LS, iterative reweight, the Taubin method, renormalization, HyperLS, and hyper-renormalization. Doing statistical analysis and conducting numerical examples, we conclude that hyper-renormalization is the best method in terms of accuracy and efficiency.

We present a new technique for calibrating ultrawide fisheye lens cameras by imposing the constraint that collinear points be rectified to be collinear, parallel lines to be parallel, and orthogonal lines to be orthogonal. Exploiting the fact that line fitting reduces to an eigenvalue problem in 3D, we do a rigorous perturbation analysis to obtain a practical calibration procedure. Doing experiments, we point out that spurious solutions exist if collinearity and parallelism alone are imposed. Our technique has many desirable properties. For example, no metric information is required about the reference pattern or the camera position, and separate stripe patterns can be displayed on a video screen to generate a virtual grid, eliminating the grid point extraction processing.

We present a new form of least squares (LS), called "hyper LS", for geometric problems that frequently appear in computer vision applications. Doing rigorous error analysis, we maximize the accuracy by introducing a normalization that eliminates statistical bias up to second order noise terms. Our method yields a solution comparable to maximum likelihood (ML) without iterations, even in large noise situations where ML computation fails.

A higher order scheme is presented for the optimal correction method of Kanatani [5] for triangulation from two views and is compared with the method of Hartley and Sturm [3]. It is pointed out that the epipole is a singu-larity of the Hartley-Sturm method, while the proposed method has no singu-larity. Numerical simulation confirms that both compute identical solutions at other points. However, the proposed method is significantly faster. 1

A very compact algorithm is presented for fitting an ellipse to points in images by maximum likelihood (ML) in the strict sense. Although our algorithm produces the same solution as existing ML-based methods, it is probably the simplest and the smallest of all. By numerical experiments, we show that the strict ML solution practically coincides with the Sampson solution.

A new method is presented for computing the fundamental matrix from point correspondences: its singular value decomposition (SVD) is optimized by the Levenberg-Marquard (LM) method. The search is initialized by optimal correction of unconstrained ML. There is no need for tentative 3-D reconstruction. The accuracy achieves the theoretical bound (the KCR lower bound). 1

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.

We propose a new technique for optimizing a triangular mesh for polyhedral representation of the scene in a video stream. We introduce a specially designed template that can effectively detect color and texture discontinuities. Using real images, we demonstrate that our method is superior to existing methods.

We first investigate the meaning of "statistical methods" for geometric inference based on image feature points. Tracing back the origin of feature uncertainty to image processing operations, we discuss the implications of asymptotic analysis in reference to "geometric fitting" and "geometric model selection" and point out that a correspondence exists between the standard statistical analysis and the geometric inference problem. Then, we derive the "geometric AIC" and the "geometric MDL" as counterparts of Akaike's AIC and Rissanen's MDL. We show by experiments that the two criteria have contrasting characteristics in detecting degeneracy.

Computer vision techniques can estimate 3D shape from images, but usually only up to a scale factor. The scale factor must be obtained by a physical measurement of the scene or the camera motion. Using gauge theory, we show that how this scale factor is determined can significantly affect the accuracy of the estimated shape. And yet these considerations have been ignored in previous works where 3D shape accuracy is optimized. We investigate how scale fixing influences the accuracy of 3D reconstruction and determine what measurement should be made to maximize the shape accuracy.

Reformulating the Costeira-Kanade algorithm as a pure mathematical theorem independent of the Tomasi-Kanade factorization, we present a robust segmentation algorithm by incorporating such techniques as dimension correction, model selection using the geometric AIC, and least-median fitting. Doing numerical simulations, we demonstrate that oar algorithm dramatically outperforms existing methods. It does not involve any parameters which need to be adjusted empirically.

Many studies have been made in the past for optimization using covariance matrices of feature points. We first describe how to compute the covariance matrix of a feature point from the gray levels by integrating existing methods. Then, we experimentally examine if thus computed covariance matrices really reflect the accuracy of the feature points. To test this, we do subpixel template matching and compute the homography and the fundamental matrix. Our conclusion is rather surprising, pointing out important elements often overlooked.

This paper presents a consistent theory for describing indeterminacy and uncertainty of three-dimensional (3-D) reconstruction from a sequence of images. First, we give a group-theoretical analysis of gauges and gauge transformations. We then discuss how to evaluate the reliability of the solution that has indeterminacy and extend the Cramer-Rao lower bound to incorporate internal indeterminacy. We also introduce the free-gauge approach and define the normal form of a covariance matrix that is independent of particular gauges. Finally, we show simulated and real-image examples to illustrate the effect of gauge freedom on uncertainty description.

We evaluate the reliability of the 3D (Euclidean) shape reconstructed from two uncalibrated perspective views. Introducing a statistical model of image noise, we optimally compute the fundamental matrix and evaluate its uncertainty in quantitative terms. We then evaluate the covariance matrices of the reconstructed 3D points by propagating the image noise and the uncertainty in the fundamental matrix using a simple scheme. We show real-image experiments and discuss the effect of the "gauge" on the uncertainty description.

We describe a theoretically optimal algorithm for computing the homography between two images in relation to image mosaicing applications. First, we derive a theoretical accuracy bound based on a mathematical model of image noise and do simulation to confirm that our renormalization technique effectively attains that bound; our algorithm is optimal in that sense. Then, we apply our technique to mosaicing of images with small overlaps. By using real images, we show how our algorithm reduces the instability of the image mapping.

The author points out the existence of a theoretical difficulty that underlies the curve segmentation problem studied in the work of Rosin and West (ibid., vol.17, no.12, p.1140-53, 1995) and present a possible solution to it. The problem arises because curves are segmented into low- and high-order features, and the former are a subset of the latter. In reply, Rosin and West discuss the advantages and disadvantages of two approaches to model selection: their original heuristic sequential method, and the information theoretic method suggested by Kanatani and others.

We point out the existence of a theoretical difficulty that underlies the symmetry detection studied by Zabrodsky et al. (1995) and present a possible solution to it.

Introducing a mathematical model of noise in stereo images, we define the geometric information criterion (geometric AIC) for evaluating the goodness of an assumption about the object we are viewing. We show that we can test whether or not the object is located infinitely far away or the object is a planar surface without using any knowledge about the noise magnitude or any empirically adjustable thresholds. Synthetic and real-image examples are shown to illustrate our theory.

A mathematical model is given for the statistical error characteristics of range sensing, and a numerical scheme called "renormalization" is presented for optimally fitting a planar surface to data points obtained by range sensing. The renormalization method has the advantage that not only an optimal fit is computed but also its reliability is automatically evaluated in the form of the covariance matrix of the optimal fit. A scheme for visualizing the reliability of computation is presented by means of the "primary deviation pair", and its effectiveness is demonstrated by numerical simulation.

Introducing a statistical model of noise in terms of the covariance matrix of the N-vector, we point out that the least-squares conic fitting is statistically biased. We present a new fitting scheme called renormalization for computing an unbiased estimate by automatically adjusting to noise. Relationships to existing methods are discussed, and our method is tested using real and synthetic data.>

Computational techniques for fitting a 3-D rotation to 3-D data are recapitulated in a refined form as minimization over proper rotations, extending three existing methods-the method of singular value decomposition, the method of polar decomposition, and the method of quaternion representation. Then, we describe the problem of 3-D motion estimation in this new light. Finally, we define the covariance matrix of a rotation and analyze the statistical behavior of errors in 3-D rotation fitting.>

In many computer vision problems, it is necessary to robustly estimate parameter values from a large quantity of image data. In such problems, least-squares minimization is computationally the most convenient and practical solution method. The author shows that the least-squares solution is in general statistically biased in the presence of noise. A scheme called renormalization that iteratively removes the statistical bias by automatically adjusting to the image noise is presented. It is applied to the problem of estimating vanishing points and focuses of expansion and conic fitting.>

An optimal grid is designed so that the reliability of the camera focal length calibration using it is theoretically maximized. The analysis is based on a statistical error model of the line fitting in digital images. The reliability of the focal length is quantitatively computed from the reliability of the edges to which lines are fitted. A realistic device is designed by adding many technical improvements, and a prototype model is shown.

The problem of estimating 3D rigid motion from point correspondences over two views is formulated as nonlinear least-squares (LS) optimization, and the statistical behaviors of the errors in the solution are analyzed by introducing a realistic model of noise described in terms of the covariance matrices of N-vectors. It is shown that the LS solution based on the epipolar constraint is statistically biased. The geometry of this bias is described in both quantitative and qualitative terms. Finally, an unbiased estimation scheme is presented, and random number simulations are conducted to observe its effectiveness.>

Camera focal-length calibration is analyzed by applying a statistical error model of edge fitting in digital images. The reliability of the focal length is computed from the reliability of the vanishing points, and the reliability of the vanishing points is computed from the reliability of the edges to which lines are fitted. A planar grid pattern is placed in the scene for this purpose, and the 3-D configuration that maximizes the reliability is theoretically derived. Multiple data are then fused by optimally weighted averaging. A real image example is given.>

A general formalism for detecting geometric configurations of image data is presented. The author first estimates an ideal geometric configuration that supposedly exists, and then checks to what extent the original edges must be displaced in order to support the hypothesis. All types of tests are reduced to computing a single measure of edge displacement which provides a universal measure of uncertainty applicable to all types of decision-making.>

A novel algorithm for reconstructing 3-D road geometry from images is presented for the purpose of autonomously navigating land vehicles. The reconstruction is based on an idealized road model: a road is assumed to be generated by a horizontal line segment of a fixed length sweeping in the scene. The constraints that ideal road images must satisfy are expressed as a set of differential equations; the 3-D road geometry is reconstructed by numerically integrating these equations. In order to prevent numerical instability, a correction scheme is proposed for stabilizing computation: at each numerical integration step, the computed solution is modified in such a way that the required constraint is always satisfied. Some examples based on real road images are shown. The inherent ill-posedness of the problem and related technical issues are discussed in detail.>

Methods of 3D recovery in computer vision for computing the shape and motion of an object from projected images when an object model is available are classified into two types: the 3D Euclidean approach, which is based on geometrical constraints in 3D Euclidean space, and the 2D non-Euclidean space. Implications of these two approaches are discussed, and some illustrating examples are presented.>

Although the 3D orientations of edges and surfaces are theoretically sufficient for reconstructing the 3D object shape, this does not mean that the 3D object shape can actually be reconstructed: Inconsistency may result if image data contain errors. We propose a scheme of oprimization to construct a consistent object shape from inconsistent data. Our optimization is achieved by solving a set of linear equations. This technique is first applied to the problem of shape from motion and then to the 3D recovery based on the rectangularity hypothesis and the parallelism hypothesis. 1. Constraints on 2%D Sketches In the past, various 3D shape recovery techniques called shape from ... have been proposed (shape from motion, shape from shading, shape from texture, etc.). Now, we must ask the following question: Do these techniques really enable us to recover the 3D object shape? The shape from ... paradigms usually present us with object images equipped with the following types of 3D information: (i) The surface gradient (p , q), or equivalently the unit surface nor

The effect of camera rotation on the description of optical flow generated by a planar surface in motion is treated. A transformation law for the parameters is given explicitly by analyzing infinitesimal generators and irreducibly reducing the induced representation of the 3-D rotation group SO(3). The parameter space is decomposed into invariant subspaces, and the optical flow resulting from planar surface motion is accordingly decomposed into two parts, from which an invariant basis is deduced. A procedure is presented to test the equivalence of two optical flows and to reconstruct the camera rotation. The relationship with the analytical expressions for 3-D recovery is discussed.>

This paper discusses how polyhedron interpretation techniques are simplified if the objects are rectangular trihedral polyhedra. This restriction enables one to compute the spatial orientation of a given corner and its motion from its image in terms of polar coordinates, Eulerian angles, and quaternions. One can also interpret the shape and the face adjacency from local information only. The necessary constraints are listed, and some examples are given to compare the presented scheme to existing ones. The possible nonuniqueness of the interpretation is also discussed.