Multiple View Geometry of General Algebraic Curves

We introduce a number of new results in the context of multi-view geometry from general algebraic curves. We start with the recovery of camera geometry from matching curves. We first show how one can compute, without any knowledge on the camera, the homography induced by a single planar curve. Then we continue with the derivation of the extended Kruppa's equations which are responsible for describing the epipolar constraint of two projections of a general algebraic curve. As part of the derivation of those constraints we address the issue of dimension analysis and as a result establish the minimal number of algebraic curves required for a solution of the epipolar geometry as a function of their degree and genus.We then establish new results on the reconstruction of general algebraic curves from multiple views. We address three different representations of curves: (i) the regular point representation in which we show that the reconstruction from two views of a curve of degree d admits two solutions, one of degree d and the other of degree d(d – 1). Moreover using this representation, we address the problem of homography recovery for planar curves, (ii) dual space representation (tangents) for which we derive a lower bound for the number of views necessary for reconstruction as a function of the curve degree and genus, and (iii) a new representation (to computer vision) based on the set of lines meeting the curve which does not require any curve fitting in image space, for which we also derive lower bounds for the number of views necessary for reconstruction as a function of curve degree alone.     

Scene Reconstruction and Robot Navigation Using Dynamic Fields

In this paper, we present an approach to autonomous robot navigation in an unknown environment. We design and integrate algorithms to reconstruct the scene, locate obstacles and do short-term field-based path planning. The scene reconstruction is done using a region matching flow algorithm to recover image deformation and structure from motion to recover depth. Obstacles are located by comparing the surface normal of the known floor with the surface normal of the scene. Our path planning method is based on electric-like fields and uses current densities that can guarantee fields without local minima and maxima which can provide solutions without the need of heuristics that plague the more traditional potential fields approaches. We implemented a modular distributed software platform (FBN) to test this approach and we ran several experiments to verify the performance with very encouraging results.     

A Multibody Factorization Method for Independently Moving Objects

The structure-from-motion problem has been extensively studied in the field of computer vision. Yet, the bulk of the existing work assumes that the scene contains only a single moving object. The more realistic case where an unknown number of objects move in the scene has received little attention, especially for its theoretical treatment. In this paper we present a new method for separating and recovering the motion and shape of multiple independently moving objects in a sequence of images. The method does not require prior knowledge of the number of objects, nor is dependent on any grouping of features into an object at the image level. For this purpose, we introduce a mathematical construct of object shapes, called the shape interaction matrix, which is invariant to both the object motions and the selection of coordinate systems. This invariant structure is computable solely from the observed trajectories of image features without grouping them into individual objects. Once the matrix is computed, it allows for segmenting features into objects by the process of transforming it into a canonical form, as well as recovering the shape and motion of each object. The theory works under a broad set of projection models (scaled orthography, paraperspective and affine) but they must be linear, so it excludes projective cameras.     

Accurate Camera Calibration from Multi-View Stereo and Bundle Adjustment

The advent of high-resolution digital cameras and sophisticated multi-view stereo algorithms offers the promise of unprecedented geometric fidelity in image-based modeling tasks, but it also puts unprecedented demands on camera calibration to fulfill these promises. This paper presents a novel approach to camera calibration where top-down information from rough camera parameter estimates and the output of a multi-view-stereo system on scaled-down input images is used to effectively guide the search for additional image correspondences and significantly improve camera calibration parameters using a standard bundle adjustment algorithm (Lourakis and Argyros 2008). The proposed method has been tested on six real datasets including objects without salient features for which image correspondences cannot be found in a purely bottom-up fashion, and objects with high curvature and thin structures that are lost in visual hull construction even with small errors in camera parameters. Three different methods have been used to qualitatively assess the improvements of the camera parameters. The implementation of the proposed algorithm is publicly available at Furukawa and Ponce (2008b).     

摄像机沿光轴运动下的场景三维重建

讨论了采用针孔摄像机进行摄像机沿光轴运动下的场景三维重建的方法．基于摄像机轴向运动的特点和性质,利用该方法找到图像间的缩放因子,进而解决了轴向运动下的特征匹配;采用Sturm的摄像机自标定方法得到摄像机的内外参数;从而实现了摄像机沿光轴运动下的场景三维重建．     

3D Reconstruction by Shadow Carving: Theory and Practical Evaluation

Cast shadows are an informative cue to the shape of objects. They are particularly valuable for discovering object’s concavities which are not available from other cues such as occluding boundaries. We propose a new method for recovering shape from shadows which we call shadow carving. Given a conservative estimate of the volume occupied by an object, it is possible to identify and carve away regions of this volume that are inconsistent with the observed pattern of shadows. We prove a theorem that guarantees that when these regions are carved away from the shape, the shape still remains conservative. Shadow carving overcomes limitations of previous studies on shape from shadows because it is robust with respect to errors in shadows detection and it allows the reconstruction of objects in the round, rather than just bas-reliefs. We propose a reconstruction system to recover shape from silhouettes and shadow carving. The silhouettes are used to reconstruct the initial conservative estimate of the object’s shape and shadow carving is used to carve out the concavities. We have simulated our reconstruction system with a commercial rendering package to explore the design parameters and assess the accuracy of the reconstruction. We have also implemented our reconstruction scheme in a table-top system and present the results of scanning of several objects.     

Geometry of Distorted Visual Space and Cremona Transformation

An important issue concerning the design of any vision system is the choice of a proper space representation. In order to search for clues to a suitable representation, we look at the distortion of space arising from errors in motion or stereo estimates. Understanding this space distortion has important epistemological implications for the problem of space representation because it tells us what can be and what cannot be computed. This paper is therefore an enquiry into the nature of space representation through the study of the space distortion, though it is not a psychophysical or physiological study but rather a computational one. We show that the distortion transformation is a quadratic Cremona transformation, which is bijective almost everywhere except on the set of fundamental elements. We identify the fundamental elements of both the direct and the inverse transformations, and study the behaviour of the space distortion by analyzing the transformation of space elements (lines, planes) that pass through these fundamental elements.     

面向大规模三维重建的快速鲁棒集束调整算法

集束调整是运动推断结构的核心,针对现有算法在大规模场景下易受外点影响,空间占用率过高和效率较低问题,提出一种快速鲁棒的集束调整（fast and robust bundle adjustment,FRBA）算法.首先,为了避免外点（outliers）的影响,采用Cauchy损失降低外点的权重,提高算法精度.其次,充分利用运动推断结构中三维点与摄像机之间的稀疏性对大规模集束调整进行稀疏分解,降低内存空间的使用.最后,根据稀疏分解后矩阵的固有特性,采用快速矩阵分解法求解正态方程的解.在合成数据集、BAL数据集和真实图像数据集上对FRBA算法进行测试,并与现有经典算法进行比较.实验结果表明无论在时间效率还是精度上,FRBA算法均处于领先位置.     

EM-GPA: Generalized Procrustes analysis with hidden variables for 3D shape modeling

Aligning shapes is essential in many computer vision problems and generalized Procrustes analysis (GPA) is one of the most popular algorithms to align shapes. However, if some of the shape data are missing, GPA cannot be applied. In this paper, we propose EM-GPA, which extends GPA to handle shapes with hidden (missing) variables by using the expectation-maximization (EM) algorithm. For example, 2D shapes can be considered as 3D shapes with missing depth information due to the projection of 3D shapes into the image plane. For a set of 2D shapes, EM-GPA finds scales, rotations and 3D shapes along with their mean and covariance matrix for 3D shape modeling. A distinctive characteristic of EM-GPA is that it does not enforce any rank constraint often appeared in other work and instead uses GPA constraints to resolve the ambiguity in finding scales, rotations, and 3D shapes. The experimental results show that EM-GPA can recover depth information accurately even when the noise level is high and there are a large number of missing variables. By using the images from the FRGC database, we show that EM-GPA can successfully align 2D shapes by taking the missing information into consideration. We also demonstrate that the 3D mean shape and its covariance matrix are accurately estimated. As an application of EM-GPA, we construct a 2D + 3D AAM (active appearance model) using the 3D shapes obtained by EM-GPA, and it gives a similar success rate in model fitting compared to the method using real 3D shapes. EM-GPA is not limited to the case of missing depth information, but it can be easily extended to more general cases.     

Some Results on Minimal Euclidean Reconstruction from Four Points

Methods for reconstruction and camera estimation from miminal data are often used to boot-strap robust (RANSAC and LMS) and optimal (bundle adjustment) structure and motion estimates. Minimal methods are known for projective reconstruction from two or more uncalibrated images, and for “5 point” relative orientation and Euclidean reconstruction from two calibrated parameters, but we know of no efficient minimal method for three or more calibrated cameras except the uniqueness proof by Holt and Netravali. We reformulate the problem of Euclidean reconstruction from minimal data of four points in three or more calibrated images, and develop a random rational simulation method to show some new results on this problem. In addition to an alternative proof of the uniqueness of the solutions in general cases, we further show that unknown coplanar configurations are not singular, but the true solution is a double root. The solution from a known coplanar configuration is also generally unique. Some especially symmetric point-camera configurations lead to multiple solutions, but only symmetry of points or the cameras gives a unique solution.     

多视点图像中线特征的三维重建

将多视点图像中的离散线段(称为线特征)用于场景的三维重建过程.首先将平均重投影几何误差作为线特征三角形法和光束平差法的目标函数,保证了重建结果的最优性;其次提出一种对含噪声的空间直线Plucker坐标进行双线性约束矫正的解析方法,并给出理论证明;最后推导出针对具有4自由度空间直线的最少参数化迭代方法,消除了优化过程中的过参数化问题,以避免由于内约束存在而导致迭代难于收敛的情况,提高了重建结果的精度.仿真数据以及真实图像的实验结果验证了该方法的有效性和精确性.     

Projective Reconstruction from Multiple Views with Minimization of 2D Reprojection Error

The problem of projective reconstruction by minimization of the 2D reprojection error in multiple images is considered. Although bundle adjustment techniques can be used to minimize the 2D reprojection error, these methods being based on nonlinear optimization algorithms require a good starting point. Quasi-linear algorithms with better global convergence properties can be used to generate an initial solution before submitting it to bundle adjustment for refinement. In this paper, we propose a factorization-based method to integrate the initial search as well as the bundle adjustment into a single algorithm consisting of a sequence of weighted least-squares problems, in which a control parameter is initially set to a relaxed state to allow the search of a good initial solution, and subsequently tightened up to force the final solution to approach a minimum point of the 2D reprojection error. The proposed algorithm is guaranteed to converge. Our method readily handles images with missing points.     

Robust and Rapid Generation of Animated Faces from Video Images: A Model-Based Modeling Approach

We have developed an easy-to-use and cost-effective system to construct textured 3D animated face models from videos with minimal user interaction. This is a particularly challenging task for faces due to a lack of prominent textures. We develop a robust system by following a model-based approach: we make full use of generic knowledge of faces in head motion determination, head tracking, model fitting, and multiple-view bundle adjustment. Our system first takes, with an ordinary video camera, images of a face of a person sitting in front of the camera turning their head from one side to the other. After five manual clicks on two images to indicate the position of the eye corners, nose tip and mouth corners, the system automatically generates a realistic looking 3D human head model that can be animated immediately (different poses, facial expressions and talking). A user, with a PC and a video camera, can use our system to generate his/her face model in a few minutes. The face model can then be imported in his/her favorite game, and the user sees themselves and their friends take part in the game they are playing. We have demonstrated the system on a laptop computer live at many events, and constructed face models for hundreds of people. It works robustly under various environment settings.     

The Least-Squares Error for Structure from Infinitesimal Motion

We analyze the least-squares error for structure from motion with a single infinitesimal motion (structure from optical flo). We present asymptotic approximations to the noiseless error over two, complementary regions of motion estimates: roughly forward and non-forward translations. Our approximations are powerful tools for understanding the error. Experiments show that they capture its detailed behavior over the entire range of motions. We illustrate the use of our approximations by deriving new properties of the least-squares error. We generalize the earlier results of Jepson/Heeger/Maybank on the bas-relief ambiguity and of Oliensis on the reflected minimum. We explain the error's complexity and its multiple local minima for roughly forward translation estimates (epipoles within the field of view) and identify the factors that make this complexity likely. For planar scenes, we clarify the effects of the two-fold ambiguity, show the existence of a new, double bas-relief ambiguity, and analyze the error's local minima. For nonplanar scenes, we derive simplified error approximations for reasonable assumptions on the image and scene. For example, we show that the error tends to have a simpler form when many points are tracked. We show experimentally that our analysis for zero image noise gives a good model of the error for large noise. We show theoretically and experimentally that the error for projective structure from motion is simpler but flatter than the error for calibrated images.     

Geometrical recovery of missing data for shape from motion

This paper studies the geometrical recovery of an incomplete observation matrix for converting existing 2D video sequences to 3D content. In situations when converting previously recorded monoscopic video to 3D, several entries of the observation matrix have not been observed and other entries have been perturbed by the influence of noise. In such cases, there is no simple solution for SVD factorization for shape from motion. In this paper, a new recovery algorithm is proposed for recovering missing feature points, by minimizing the influence of noise, using iteratively geometrical correlations between a 2D observation matrix and 3D shape. Results in practical situations demonstrated with synthetic and real video sequences verify the efficiency and flexibility of the proposed method.     

图像序列的增量式运动结构恢复

目的 传统增量式运动结构恢复算法中,初始图像对选择鲁棒性差,增量求解过程效率较低,捆绑调整策略存在计算冗余,模型修正后仍存在较大误差。为解决上述问题,以基于图像序列的3维重建为基础,提出一种新的增量式运动结构恢复算法（SFM-Y）。方法 首先,采用改进的自适应异常值过滤方法增强初始图像对选择的鲁棒性,得到用于初始重建的初始图像对;其次,通过增量迭代重建丰富点云模型,采用改进的EPNP（efficient perspective-n-point）解算方法提高增量添加过程的计算效率和精确度;最后,采用优化的捆绑调整策略进行模型修正,解决模型漂移问题,修正重投影误差。结果 实验选取不同数据规模的数据集,在本文方法及传统方法间进行测试对比,以便更加全面地分析算法性能。实验结果表明,SFM-Y算法相比传统的增量式运动结构恢复算法,在计算效率和结果质量方面均有所提高,根据性能分析对比的结果所示,本文方法较传统方法在计算效率和重建精度上约有10%的提升。结论 提出的增量式运动结构恢复算法能够高效准确地实现基于图像序列的3维重建优于传统方法,计算效率较高,初始重建鲁棒性强,生成模型质量较好。     

An Efficient and Accurate Method for 3D-Point Reconstruction from Multiple Views

In this paper we consider the problem of finding the position of a point in space given its projections in multiple images taken by cameras with known calibration and pose. Ideally the 3D point can be obtained as the intersection of multiple known rays in space. However, with noise the rays do not meet at a single point generally. Therefore, it is necessary to find a best point of intersection. In this paper we propose a modification of the method (Ma et al., 2001. Journal of Communications in Information and Systems, (1):51–73) based on the multiple-view epipolar constraints. The solution is simple in concept and straightforward to implement. It includes generally two steps: first, image points are corrected through approximating the error model to the first order, and then the 3D point can be reconstructed from the corrected image points using any generic triangulation method. Experiments are conducted both on simulated data and on real data to test the proposed method against previous methods. It is shown that results obtained with the proposed method are consistently more accurate than those of other linear methods. When the measurement error of image points is relatively small, its results are comparable to those of maximum likelihood estimation using Newton-type optimizers; and when processing image-point correspondences cross a small number of views, the proposed method is by far more efficient than the Newton-type optimizers.     

Linear Multi View Reconstruction and Camera Recovery Using a Reference Plane

This paper presents a linear algorithm for simultaneous computation of 3D points and camera positions from multiple perspective views based on having a reference plane visible in all views. The reconstruction and camera recovery is achieved in a single step by finding the null-space of a matrix built from image data using Singular Value Decomposition. Contrary to factorization algorithms this approach does not need to have all points visible in all views. This paper investigates two reference plane configurations: Finite reference planes defined by four coplanar points and infinite reference planes defined by vanishing points. A further contribution of this paper is the study of critical configurations for configurations with four coplanar points. By simultaneously reconstructing points and views we can exploit the numerical stabilizing effect of having wide spread cameras with large mutual baselines. This is demonstrated by reconstructing the outsideand inside (courtyard) of a building on the basis of 35 views in one single Singular Value Decomposition.     

On the Wiberg Algorithm for Matrix Factorization in the Presence of Missing Components

This paper considers the problem of factorizing a matrix with missing components into a product of two smaller matrices, also known as principal component analysis with missing data (PCAMD). The Wiberg algorithm is a numerical algorithm developed for the problem in the community of applied mathematics. We argue that the algorithm has not been correctly understood in the computer vision community. Although there are many studies in our community, almost every one of which refers to the Wiberg study, as far as we know, there is no literature in which the performance of the Wiberg algorithm is investigated or the detail of the algorithm is presented. In this paper, we present derivation of the algorithm along with a problem in its implementation that needs to be carefully considered, and then examine its performance. The experimental results demonstrate that the Wiberg algorithm shows a considerably good performance, which should contradict the conventional view in our community, namely that minimization-based algorithms tend to fail to converge to a global minimum relatively frequently. The performance of the Wiberg algorithm is such that even starting with random initial values, it converges in most cases to a correct solution, even when the matrix has many missing components and the data are contaminated with very strong noise. Our conclusion is that the Wiberg algorithm can also be used as a standard algorithm for the problems of computer vision.