In this paper, we revisit the pose determination problem of a partially calibrated camera with unknown focal length, hereafter referred to as the PnPf problem, by using n(n ≥ 4) 3D-to-2D point correspondences. Our core contribution is to introduce the angle constraint and derive a compact bivariate polynomial equation for each point triplet. Based on this polynomial equation, we propose a truly general method for the PnPf problem, which is suited both to the minimal 4-point based RANSAC application, and also to large scale scenarios with thousands of points, irrespective of the 3D point configuration. In addition, by solving bivariate polynomial systems via the Sylvester resultant, our method is very simple and easy to implement. Its simplicity is especially obvious when one needs to develop a fast solver for the 4-point case on the basis of the characteristic polynomial technique. Experiment results have also demonstrated its superiority in accuracy and efficiency when compared with the existing state-of-the-art solutions.

We propose a robust method for incrementally estimating a regular-grid ground surface map from stereo image sequences captured by nearly front-looking vehicle-mounted stereo cameras. The method simultaneously estimates a camera ego-motion and vertex heights of a regular mesh, which is composed of piecewise triangular patches drawn on a level plane in the ground coordinate system, by minimizing pixel value differences over the ground surface. The method combinationally uses feature-based approach and pixel-based approach for robustly estimating ego-motion parameters. We also show that this combination is beneficial for removing outlier pixels, which mainly represent the edge of the self-shadow area on the ground surface. The validity of the proposed method is demonstrated through experiments using real images.

Due to its simplicity, the eight-point algorithm has been widely used in fundamental matrix estimation. Unfortunately, the rank-2 constraint of a fundamental matrix is enforced via a posterior rank correction step, thus leading to non-optimal solutions to the original problem. To address this drawback, existing algorithms need to solve either a very high order polynomial or a sequence of convex relaxation problems, both of which are computationally ineffective and numerically unstable. In this work, we present a new rank-2 constrained eight-point algorithm, which directly incorporates the rank-2 constraint in the minimization process. To avoid singularities, we propose to solve seven sub problems and retrieve their globally optimal solutions by using tailored polynomial system solvers. Our proposed method is noniterative, computationally efficient and numerically stable. Experiment results have verified its superiority over existing algebraic error based algorithms in terms of accuracy, as well as its advantages when used to initialize geometric error based algorithms.

In this paper, we revisit the classical perspective-n-point (PnP) problem, and propose the first non-iterative O(n) solution that is fast, generally applicable and globally optimal. Our basic idea is to formulate the PnP problem into a functional minimization problem and retrieve all its stationary points by using the Gr"obner basis technique. The novelty lies in a non-unit quaternion representation to parameterize the rotation and a simple but elegant formulation of the PnP problem into an unconstrained optimization problem. Interestingly, the polynomial system arising from its first-order optimality condition assumes two-fold symmetry, a nice property that can be utilized to improve speed and numerical stability of a Grobner basis solver. Experiment results have demonstrated that, in terms of accuracy, our proposed solution is definitely better than the state-of-the-art O(n) methods, and even comparable with the reprojection error minimization method.

A great variety of computer vision tasks, such as rigid/nonrigid structure from motion and photometric stereo, can be unified into the problem of approximating a low-rank data matrix in the presence of missing data and outliers. To improve robustness, the L1-norm measurement has long been recommended. Unfortunately, existing methods usually fail to minimize the L1-based nonconvex objective function sufficiently. In this work, we propose to add a convex trace-norm regularization term to improve convergence, without introducing too much heterogenous information. We also customize a scalable first-order optimization algorithm to solve the regularized formulation on the basis of the augmented Lagrange multiplier (ALM) method. Extensive experimental results verify that our regularized formulation is reasonable, and the solving algorithm is very efficient, insensitive to initialization and robust to high percentage of missing data and/or outliers1.

In spite of intensive endeavor over decades, rigid and nonrigid factorizations under metric constraints, possibly in the presence of missing components, remain to be very challenging. In this work, we try to break the hard nut by generalizing to these problems the Wiberg algorithm, one of the most successful solutions for unconstrained bilinear factorization. To properly handle missing components, we advocate a bilinear factorization formulation with an extra mean vector. In spirit of the Wiberg algorithm, we first propose an efficient and initialization-insensitive algorithm for unconstrained factorization, posterior correction of whose solution offers reasonable initialization for metric upgrade. For factorization with metric constraints, we reformulate it into an unconstrained problem through quaternion parametrization, which merges elegantly into our unconstrained factorization algorithm. Extensive experiment results verify that our proposed methods are fast, accurate and robust to high percentage of missing components.

Many computer vision problems can be accounted for or properly approximated by linearity, and the robust model fitting (parameter estimation) problem in presence of outliers is actually to find the Maximum Feasible Subsystem (MaxFS) of a set of infeasible linear constraints. We propose a deterministic branch and bound method to solve the MaxFS problem with guaranteed global optimality. It can be used in a wide class of computer vision problems, in which the model variables are subject to the unit norm constraint. In contrast to the convex and concave relaxations in existing works, we introduce a piecewise linear relaxation to build very tight under- and over-estimators for square terms by partitioning variable bounds into smaller segments. Based on this novel relaxation technique, our branch and bound method can converge in a few iterations. For homogeneous linear systems, which correspond to some quasi-convex problems based on L∞-L∞-norm, our method is non-iterative and certainly reaches the globally optimal solution at the root node by partitioning each variable range into two segments with equal length. Throughout this work, we rely on the so-called Big-M method, and successfully avoid potential numerical problems by exploiting proper parametrization and problem structure. Experimental results demonstrate the stability and efficiency of our proposed method.

We propose a unified branch and contract method to estimate the fundamental matrix with guaranteed global optimality, by minimizing either the Sampson error or the point to epipolar line distance, and explicitly handling the rank-2 constraint and scale ambiguity. Based on a novel denominator linearization strategy, the fundamental matrix estimation problem can be transformed into an equivalent problem that involves 9 squared univariate, 12 bilinear and 6 trilin-ear terms. We build tight convex and concave relaxations for these nonconvex terms and solve the problem deterministically under the branch and bound framework. For acceleration, a bound contraction mechanism is introduced to reduce the size of the branching region at the root node. Given high-quality correspondences and proper data normalization, our experiments show that the state-of-the-art locally optimal methods generally converge to the globally optimal solution. However, they indeed have the risk of being trapped into local minimum in case of noise. As another important experimental result, we also demonstrate, from the viewpoint of global optimization, that the point to epipolar line distance is slightly inferior to the Sampson error in case of drastically varying object scales across two views.

A state-of-the-arts biped robot can take foot-steps such that its heels always overhang corner edges while ascending stairs, as humans naturally do. The overhanging footstep is advantageous in terms of relaxation of restrictions on gait planning. However, in a man-made environment without geometry information, the overhanging footstep requires the estimation of the exact step-edge position in real-time. In this paper we propose a real-time method for estimating step edge positions using stereo images. We find a straight edge line, which divides a view area into two regions representing the upper and lower step-able planes at the target edge. The edge line is obtained by minimizing a cost function composed of pixel-value-difference images, which are computed from the two stereo images and the geometry parameters of the planes, estimated by an efficient direct method in high precision. The validity of the proposed method is demonstrated through online experiments using stereo cameras mounted on the body of a biped robot traversing real stairs.

A hexagonal lattice has been researched to improve computer vision and image processing. However, image alignment on the lattice has not been fully discussed yet. In this paper, we perform image alignment on hexagonal and square lattices. Then we compare and evaluate them. We used hexagonal lattices of two sizes. One has the same pixel interval between adjacent pixels as the square lattice, which results in higher resolution than the square one. Another has the same pixel area as the square lattice, which has the same resolution as the square one. The results show that the image alignment of both the hexagonal lattices outperforms that of the square lattice with respect to accuracy and the success rate. Importantly, the results also show that converting an existing large image on the square lattice into the smaller image on the hexagonal ones of both the sizes could improve image alignment.

There are two major approaches for estimating camera motion (egomotion) given an image sequence. Each approach has own strengths and weaknesses. One approach is the feature based methods. In this approach the point feature correspondences are taken as the input. Since initially the depths of point features are unknown, the egomotion is estimated by the depth independent epipolar constraints on the point feature correspondences. This approach is robust in practice, but is relatively limited in accuracy since it exploits no structure assumption, such as planarity. The other approach, termed the direct method, has the advantage in its accuracy. In this method, the egomotion is estimated as the parameters of a homography by directly aligning the planar potion of two images. The direct method may be preferable in the cases with known planes that are persistent in the view. The on-board camera system for ground vehicles is a representative example. Despite the potential accuracy, the direct method fails when the plane lacks proper texture. We propose an egomotion estimation method that is based on both the homographic constraint on a planar region, and on the epipolar constraint on generally non-planar regions, so that the both kinds of visual cues contribute to the estimation. We observe that the method improves the egomotion estimation in robustness while retaining the comparable accuracy to the direct method.

In this paper, we present a novel approach to imaging a panoramic (360°) environment and computing its dense depth map. Our approach adopts a multi-baseline stereo strategy using a set of multi-perspective panoramas where large baseline lengths are available. We design two image acquisition rigs for capturing such multi-perspective panoramas. The first one is composed of two parallel stereo cameras. By rotating the rig about a vertical axis, we generate four multi-perspective panoramas by resampling the regular perspective images captured by the stereo cameras. Then a depth map is estimated from the four multi-perspective panoramas and an original perspective image using a multi-baseline matching technique with different types of epipolar constraints. The second one is composed of a single camera and two mirrors. By rotating the rig, we acquire a spatio-temporal volume that is made up of the sequential images captured by the camera. Then we estimate a depth map by extracting trajectories from the spatio-temporal volume by using a multi-baseline stereo technique by considering occlusions. We can consider both rotating rigs as a single rotating camera with a very large field of view (FOV), that offers a large baseline length in depth estimation. In addition, compared with a previous approach using two multi-perspective panoramas from a single rotating camera, our approach can reduce matching errors due to image noise, repeated patterns, and occlusions by multi-baseline stereo techniques. Experimental results using both synthetic and real images show that our approach produces high quality panoramic 3D reconstruction.

Synthetic Aperture Focusing can produce a virtual image where objects lying on a specified focal plane are focused while object lying off the plane are blurred. by averaging the multiview images warped by planar homographies. In this paper, we propose a method for efficiently estimating a focal plane from multiview stereo images so that a user-specified image region is focused in the virtual image. We estimate the 3D parameters of a focal plane, which corresponds to a planar surface in the image region. by using a fast multiview direct method with image pair selection. We select the ‘best‘ image pair by evaluating both pre-computed condition numbers of Hessian matrices and stereo baseline lengths. Our method can rapidly produce a unique virtual image, referred to as a Virtual Focal Plane (VFP) image, where the image region lying on a non-frontparallel plane in the scene is focused.

In this paper, we propose a direct method for 3D surface reconstruction from stereo images. We reconstruct a 3D surface by estimating all depths of the vertices of a mesh composed of piecewise triangular patches on the reference (template) image. The analyses described in this paper subsume that the deformation of the mesh between the stereo images is specified by homographies, each of which represents the deformation of a single patch. The homography deforms each patch which has 3 d.o.f under epipolar constraints. We first formulate a fast "direct" method for estimating the three parameters of a 3D plane by incorporating inverse compositional expression into the sum of squared differences (SSD) function of two stereo images. This method is about eight times faster than the conventional method. Then we extend the direct method to the estimation of the vertex depths in the mesh for reconstructing piecewise-planar surfaces. The validity of the proposed method is demonstrated through results of experiments using synthetic and real images.

In this paper, we propose a floor sensing method using stereo cameras mounted on a biped robot. In the proposed method, we first determine multiple regions of interest (ROI) in a reference image from footstep positions up to several steps, scheduled by a current footstep plan. Then the 3D plane parameters of the floor with respect to each ROI are estimated by a direct method using stereo images. We adopt the fast plane parameter estimation method [5], along with the compensation for the errors of the initial parameters by using the internal state of the robot, for the enhancement of the robustness and efficiency in the optimization process. Additionally, we estimate the shape of the floor including slopes from the set of the estimated plane parameters, and feedback the results for updating the footstep plan. The validity of the proposed method is demonstrated through on-line experiments using stereo cameras mounted on the body of a biped robot traversing a real environment.

In this paper, we propose a novel method for panoramic 3D scene recovery using rotational stereo cameras with simple epipolar constraints. By rotating two parallel stereo cameras about a vertical axis with a constant velocity, we acquire two sampled spacio-temporal volumes which are made of the sequential images captured by a uniform angular interval. The two spacio-temporal volumes can be resampled into a set of multi-perspective panoramas. We analyze the epipolar geometry among images (panoramas and original images) of two spacio-temporal volumes. The result shows that only three types of simple epipolar constraints (epipolar line is row or column of image) exist in the two spacio-temporal volumes. Then we compute a depth map from four image pairs using a multi-baseline algorithm with the three types of epipolar constraints; that is horizontal, vertical and combination of them. Experimental results using both synthetic and real images show that our approach produces high quality panoramic 3D reconstruction.

We propose a method to recover the 3D shape of an object rotating on a turnable. A spacio-temporal image is made of the sequential images taken by a single camera. Then, the trajectories which correspond to the 3D points on the surface are extracted in the spacio-temporal image by using "weighted voting" of all intensity values on a constrained surface. Since the method consequently utilize intensity information as it is, the method can recover dense 3D positions compared with the one using feature extraction and tracking. Also, it can recover concave shapes unlike the one using silhouettes of the object. The experimental results with real images show the effectiveness of our method.