The projections of world parallel lines in an image intersect at a single point called the vanishing point (VP). VPs are a key ingredient for various vision tasks including rotation estimation and 3D reconstruction. Urban environments generally exhibit some dominant orthogonal VPs. Given a set of lines extracted from a calibrated image, this paper aims to (1) determine the line clustering, i.e. find which line belongs to which VP, and (2) estimate the associated orthogonal VPs. None of the existing methods is fully satisfactory because of the inherent difficulties of the problem, such as the local minima and the chicken-and-egg aspect. In this paper, we present a new algorithm that solves the problem in a mathematically guaranteed globally optimal manner and can inherently enforce the VP orthogonality. Specifically, we formulate the task as a consensus set maximization problem over the rotation search space, and further solve it efficiently by a branch-and-bound procedure based on the Interval Analysis theory. Our algorithm has been validated successfully on sets of challenging real images as well as synthetic data sets.

This paper presents a global minimization framework for estimating analytical BRDF model parameters using the techniques of convex programming and branch and bound. Traditional local minimization suffers from local minima and requires a large number of initial conditions and supervision for successful results especially when a model is highly complex and nonlinear. We consider the Cook-Torrance model, a parametric model with the Gaussian-like Beckmann distributions for specular reflectances. Instead of optimizing the multiple parameters simultaneously, we search over all possible surface roughness values based on a branch-and-bound algorithm, and reduce the estimation problem to convex minimization with known fixed surface roughness. Our algorithm guarantees globally optimal solutions. Experiments have been carried out for isotropic surfaces to validate the method using the extensive high-precision measurements from the MERL BRDF database.

We propose a branch-and-bound algorithm to obtain the globally optimal relative rotation between a camera and the rotation sensor attached to it. Compared to previous methods, our approach directly minimizes the image space error related to the measurements which is very natural for camera-based systems. Our algorithm is based on the observation that we may evaluate the residual when the rotation matrix is known. We propose a feasibility test algorithm for the branch-and-bound to efficiently reduce the search volume of the rotation domain. Experimental results are provided using synthetic and real data sets.

We consider the least-squares (L2) triangulation problem and structure-and-motion with known rotatation, or known plane. Although optimal algorithms have been given for these algorithms under an L-infinity cost function, finding optimal least-squares (L2) solutions to these problems is difficult, since the cost functions are not convex, and in the worst case can have multiple minima. Iterative methods can usually be used to find a good solution, but this may be a local minimum. This paper provides a method for verifying whether a local-minimum solution is globally optimal, by providing a simple and rapid test involving the Hessian of the cost function. In tests of a data set involving 277,000 independent triangulation problems, it is shown that the test verifies the global optimality of an iterative solution in over 99.9% of the cases.

Minimizing L∞error norm for some geometric vision problems provides global optimization using the well- developed algorithm called SOCP (second order cone programming). Because the error norm belongs to quasi- convex functions, bisection method is utilized to attain the global optimum. It tests the feasibility of the intersection of all the second order cones due to measurements, repeatedly adjusting the global error level. The computation time increases according to the size of measurement data since the number of second order cones for the feasibility test inflates correspondingly. We observe in this paper that not all the data need be included for the feasibility test because we minimize the maximum of the errors; we may use only a subset of the measurements to obtain the optimal estimate, and therefore we obtain a decreased computation time. In addition, by using L∞image error instead of L2Euclidean distance, we show that the problem is still a quasi-convex problem and can be solved by bisection method but with linear programming (LP). Our algorithm and experimental results are provided.

This paper deals with the problem of estimating structure and motion from long continuous image sequences, applying the expectation maximization algorithm based on an extended Kalman smoother to impose time-continuity of the motion parameters. By repeatedly estimating the state transition matrix of the dynamic equation and the parameters of noise processes in dynamic and measurement equations, this optimization gives maximum likelihood estimates of the motion and structure parameters. Practically, this research is essential for dealing with a long video-rate image sequence with partially unknown system equation and noise. The algorithm is implemented and tested for a real image sequence.

In this paper, an iterative algorithm for auto-calibration is presented. The proposed algorithm switches between linearly estimating the dual of the absolute conic and the intrinsic parameters, while also incorporating the rank-3 constraint on the intrinsic parameters. The most important property of the algorithm is that it is completely general in the sense that any type of constraint on the intrinsic parameters might be used. The proposed algorithm locates in-between of a non-linear optimization and initial linear computation, and provides robust and sufficiently accurate initial values for a bundle adjustment routine. The performance of the algorithm is shown for both simulated and real data, especially in the important case of natural (zero skew and unit aspect ratio) cameras.

In this paper, we propose a method for generating realistic shadows of virtual objects inserted into a real video sequence. Our aim is to improve and extend the work of Sato, Sato, and Ikeuchi, (1999), which is based on a static camera, to the case of a video sequence. This extension consists of several procedures: calibration of a moving video camera and a graphic camera, removing false shadows occurring due to a shortcoming of the static camera approach for the estimation of an illumination distribution, and so on. The calibration of the moving camera is solved by camera self-calibration and, with it, we designed a flexible graphic world coordinate system embedding technique called "match move". We also show that the shortcoming of the previous static camera approach is overcome by using information from video sequence. Finally we present the experimental results of a real video sequence.

This paper describes an iterative algorithm for making Euclidean reconstruction of a scene from an image sequence captured by a camera with zero skew. The output consists of both the Euclidean reconstruction and the intrinsic parameters of the camera at the different imaging instants, i.e. it also provides a camera calibration. The problem is solved in two different steps. Firstly, the projective structure is obtained from a factorization method followed by a bundle adjustment method. Secondly, the Euclidean reconstruction is obtained from an iterative method that estimates the location of the absolute conic and the intrinsic parameters iteratively, using linear operations in each iteration. In this method a new constraint, called the orthogonality constraint, is used to constrain the absolute conic. Results are shown on experiments on both synthetic and real data.

This paper deals with video-based augmented reality and proposes an algorithm for augmenting a real video sequence with views of graphics objects without metric calibration of the video camera by representing the motion of the video camera in projective space. A virtual camera, by which views of graphics objects are generated, is attached to a real camera by specifying image locations of the world coordinate system of the virtual world. The virtual camera is decomposed into calibration and motion components in order to make full use of graphics tools. The projective motion of the real camera recovered from image matches has the function of transferring the virtual camera and makes the virtual camera move according to the motion of the real camera. The virtual camera also follows the change of the internal parameters of the real camera. This paper shows the theoretical and experimental results of our application of nonmetric vision to augmented reality.

This paper deals with the uniqueness of the self-calibration of a rotating and zooming camera theoretically. We assume that the principal point and the aspect ratio are fixed but the focal length changes as the camera moves. In this case, at least one inter-image homography is required in order to compute the internal calibration parameters as well as the rotation. We analyze the effects of the deviation of the principal point on the estimation of the focal length and the rotation. The more the camera changes its zoom, the larger the effects are, and the larger the rotation angle is, the smaller the effects are. Thus, we may take the image center as the principal point in practical applications. Experiments using real images are given.

In this paper, we propose a method for locating 3D position of a soccer ball from monocular image sequence of soccer games. Toward this goal, we adopted ground-model-to-image transformation together with physics-based approach, that a ball follows the parabolic trajectory in the air. By using the transformation the heights of a ball can be easily calculated using simple triangular geometric relations given the start and the end position of the ball on the ground. Here the heights of a ball are determined in terms of a player's height. Even if the end position of a ball is not given on the ground due to kicking or heading of a falling ball before it touches the ground, the most probable trajectory can be determined by searching based on the physical fact that the ball follows a parabolic trajectory in the air. We have tested and experimented with a real image sequence the results of which seem promising.

In this paper video streams are augmented by novel views of an object generated by an image-based rendering method. Reference views of the object and video images are captured by general uncalibrated perspective cameras. Our algorithm can be divided into three parts: 1) recovering structure information for reference views and video images; 2) interactive embedding of the model object into video images; and 3) rendering views of the object according to the motion of the video camera. Multiple model views are used to render views as the video camera changes its viewpoint. Generated views of the model are overlayed on the corresponding video images. Experimental results for real video and model images are given. Finally, a discussion on the limitations of the proposed method and subjects for future research are provided.

This paper reconstructs structure of lines sequentially in projective space. Grassmann (Plucker) coordinates are used in order to represent the structure of 3D lines. Since intrinsic camera parameters are not known and are changed during motion, the reconstruction is only up to a projectivity. Line correspondences are obtained through tracking 2D line segments in a sequence of images. Initial camera matrices are computed using trilinear constraints and Grassmann coordinates are used to represent recovered 3D lines. In the sequence, the Grassmann coordinates are utilized to obtain camera matrices linearly, which are then refined through nonlinear optimization with a constraint among three views. After camera matrix is computed the Grassmann coordinates are updated through IEKF (iterated extended Kalman filter). Performance of the algorithm is shown by experimental results.