In this paper, we formulate a stereo matching algorithm with careful handling of disparity, discontinuity and occlusion. The algorithm works with a global matching stereo model based on an energy-minimization framework. The global energy contains two terms, the data term and the smoothness term. The data term is first approximated by a color-weighted correlation, then refined in occluded and low-texture areas in a repeated application of a hierarchical loopy belief propagation algorithm. The experimental results are evaluated on the Middlebury data sets, showing that our algorithm is the top performer among all the algorithms listed there.

In this paper we investigate how to scale a content based image retrieval approach beyond the RAM limits of a single computer and to make use of its hard drive to store the feature database. The feature vectors describing the images in the database are binned in multiple independent ways. Each bin contains images similar to a representative prototype. Each binning is considered through two stages of processing. First, the prototype closest to the query is found. Second, the bin corresponding to the closest prototype is fetched from disk and searched completely. The query process is repeatedly performing these two stages, each time with a binning independent of the previous ones. The scheme cuts down the hard drive access significantly and results in a major speed up. An experimental comparison between the binning scheme and a raw search shows competitive retrieval quality.

We present a minimal-point algorithm for finding fundamental matrices for catadioptric cameras of the parabolic type. Central catadioptric cameras-an optical combination of a mirror and a lens that yields an imaging device equivalent within hemispheres to perspective cameras-have found wide application in robotics, tele-immersion and providing enhanced situational awareness for remote operation. We use an uncalibrated structure-from-motion framework developed for these cameras to consider the problem of estimating the fundamental matrix for such cameras. We present a solution that can compute the para-catadioptirc fundamental matrix with nine point correspondences, the smallest number possible. We compare this algorithm to alternatives and show some results of using the algorithm in conjunction with random sample consensus (RANSAC).

This paper presents a general method, based on Galois theory, for establishing that a problem can not be solved by a 'machine' that is capable of the standard arithmetic operations, extraction of radicals (that is, m-th roots for any m), as well as extraction of roots of polynomials of degree smaller than n, but no other numerical operations. The method is applied to two well known structure from motion problems: five point calibrated relative orientation, which can be realized by solving a tenth degree polynomial [6], and L2-optimal two-view triangulation, which can be realized by solving a sixth degree polynomial [3]. It is shown that both these solutions are optimal in the sense that an exact solution intrinsically requires the solution of a polynomial of the given degree (10 or 6 respectively), and cannot be solved by extracting roots of polynomials of any lesser degree.

Given five motion vectors observed in a calibrated camera, what is the rotational and translational velocity of the camera? This problem is the infinitesimal motion analogue to the five-point relative orientation problem, which has previously been solved through the derivation of a tenth-degree polynomial and extraction of its roots. Here, we present the first efficient solution to the infinitesimal version of the problem. The solution is faster than its finite counterpart. In our experiments, we investigate over which range of motions and scene distances the infinitesimal approximation is valid and show that the infinitesimal approximation works well in applications such as camera tracking.

This paper shows that structure from motion is NP-hard for most sensible cost functions when missing data is allowed. The result provides a fundamental limitation of what is possible to achieve with any structure from motion algorithm. Even though there are recent, promising attempts to compute globally optimal solutions, there is no hope of obtaining a polynomial time algorithm unless P=NP. The proof proceeds by encoding an arbitrary Boolean formula as a structure from motion problem of polynomial size, such that the structure from motion problem has a zero cost solution if and only if the Boolean formula is satisfiable. Hence, if there was a guaranteed way to minimize the error of the relevant family of structure from motion problems in polynomial time, the NP-complete problem 3SAT could be solved in polynomial time, which would imply that P=NP The proof relies heavily on results from both structure from motion and complexity theory.

We present an attempt to determine whether the shape of a generic central-projection camera, such as the eye of an insect or a log-polar camera, can be determined from two motion flows resulting from purely rotational motions with non-collinear axes. Our first contribution is to write the smooth non-parametric calibration problem as a differential equation. It is unclear at present whether this problem has unique solution, up to an orthogonal transformation. Our second contribution is a discretized version of this smooth problem, for which we give a calibration algorithm - a third contribution. Using this algorithm, we explore numerically the properties of the discrete self-calibration problem, giving some insight on the nature of the problem. We show examples of successful self-calibration, but cannot give a definite affirmative answer to the question in the title.

A recognition scheme that scales efficiently to a large number of objects is presented. The efficiency and quality is exhibited in a live demonstration that recognizes CD-covers from a database of 40000 images of popular music CD’s. The scheme builds upon popular techniques of indexing descriptors extracted from local regions, and is robust to background clutter and occlusion. The local region descriptors are hierarchically quantized in a vocabulary tree. The vocabulary tree allows a larger and more discriminatory vocabulary to be used efficiently, which we show experimentally leads to a dramatic improvement in retrieval quality. The most significant property of the scheme is that the tree directly defines the quantization. The quantization and the indexing are therefore fully integrated, essentially being one and the same. The recognition quality is evaluated through retrieval on a database with ground truth, showing the power of the vocabulary tree approach, going as high as 1 million images.

In this paper, we formulate an algorithm for the stereo matching problem with careful handling of disparity, discontinuity and occlusion. The algorithm works with a global matching stereo model based on an energy- minimization framework. The global energy contains two terms, the data term and the smoothness term. The data term is first approximated by a color-weighted correlation, then refined in occluded and low-texture areas in a repeated application of a hierarchical loopy belief propagation algorithm. The experimental results are evaluated on the Middlebury data set, showing that our algorithm is the top performer.

Assume that we have two perspective images with known intrinsic parameters except for an unknown common focal length. It is a minimally constrained problem to find the relative orientation between the two images given six corresponding points. We present an efficient solution to the problem and show that there are 15 solutions in general (including complex solutions). To the best of our knowledge this was a previously unsolved problem. The solutions are found through eigen-decomposition of a 15/spl times/15 matrix. The matrix itself is generated in closed form. We demonstrate through practical experiments that the algorithm is correct and numerically stable.

In this paper, we develop a theory of non-parametric self-calibration. Recently, schemes have been devised for non-parametric laboratory calibration, but not for self-calibration. We allow an arbitrary warp to model the intrinsic mapping, with the only restriction that the camera is central and that the intrinsic mapping has a well-defined non-singular matrix derivative at a finite number of points under study. We give a number of theoretical results, both for infinitesimal motion and finite motion, for a finite number of observations and when observing motion over a dense image, for rotation and translation. Our main result is that through observing the flow induced by three instantaneous rotations at a finite number of points of the distorted image, we can perform projective reconstruction of those image points on the undistorted image. We present some results with synthetic and real data.

We present a solution for optimal triangulation in three views. The solution is guaranteed to find the optimal solution because it computes all the stationary points of the (maximum likelihood) objective function. Internally, the solution is found by computing roots of multivariate polynomial equations, directly solving the conditions for stationarity. The solver makes use of standard methods from computational commutative algebra to convert the root-finding problem into a 47 /spl times/ 47 nonsymmetric eigenproblem. Although there are in general 47 roots, counting both real and complex ones, the number of real roots is usually much smaller. We also show experimentally that the number of stationary points that are local minima and lie in front of each camera is small but does depend on the scene geometry.