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.     

针对大规模点集三维重建问题的分布式捆绑调整方法

捆绑调整(Bundle adjustment, BA)是三维重建中的关键步骤,它需要消耗大量的计算时间和内存存储空间.本 文旨在处理三维点数比相机模型数多很多的捆绑调整问题,我们称之为针对大规模三维点集的捆 绑调整(Massive-points bundle adjustment, MPBA)问题.此类问题在对高分辨率图像进行三 维重建时会经常出现.为了高效地解决MPBA问题,本文提出一种分布式的捆绑调整算法.通过基 于三维点集划分的分解方法,原MPBA问题被分成若干子问题.该分解方法不依赖于输入参数的内在 联系,因而分解结果与具体BA问题无关.算法被映射于两个集群上,一个集群有5台计算机,另一个集 群有3台计算机,其中每台机器都配置一块图形处理器(Graphic processing unit, GPU).通过对若 干MPBA问题的实验,与经典捆绑调整算法SBA (Sparse bundle adjustment)相比,本文算法获得了 最高达75倍的加速比,并保持了算法的高精确度.而且,本文算法的两个实现所消耗的单机内存存储 空间,仅为SBA实现的1/7和1/4.     

RGBD融合明暗恢复形状的全视角三维重建技术研究

为了高效、高精度、低成本地实现对物体的全视角三维重建, 提出一种使用深度相机融合光照约束实现全视角三维重建的方法。该重建方法中,在进行单帧重建时采用RGBD深度图像融合明暗恢复形状(Shape from shading,SFS)的重建方法, 即在原有的深度数据上加上额外的光照约束来优化深度值; 在相邻两帧配准时, 采用快速点特征直方图（Fast point feature histograms, FPFH）特征进行匹配并通过随机采样一致性（Random sample consensus, RANSAC）滤除错误的匹配点对求解粗配准矩阵, 然后通过迭代最近点（Iterative closest point, ICP）算法进行精配准得出两帧间的配准矩阵; 在进行全视角的三维重建时, 采用光束平差法优化相机位姿, 从而消除累积误差使首尾帧完全重合, 最后融合生成一个完整的模型。该方法融入了物体表面的光照信息,因此生成的三维模型更为光顺,也包含了更多物体表面的细节信息,提高了重建精度;同时该方法仅通过单张照片就能在自然光环境下完成对多反射率三维物体的重建,适用范围更广。本文方法的整个实验过程通过手持深度相机就能完成,不需要借助转台,操作更加方便。     

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.     

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.     

基于图像运动的三维重建及虚拟化应用

提出了一种稳定、快速地获取摄像机视频运动图像的三维重建方法,并对该运动图像做适当的虚拟化处理以展示重建效果。采用基于尺度不变特征点匹配的摄像机标定进行三维重建。尺度不变特征对于视频图像中的特征具有优秀敏锐的匹配能力,极大地放宽了摄像机标定对于设备上的限制,拓宽了实时三维重建的适用范围。通过对系统的一系列优化,不但提升了三维重建的精度,减少了错误匹配对摄像机标定的影响,而且进一步提升了处理速度。通过在三维重建的基础之上进行虚拟化处理,展示了本系统的三维重建效果。实验结果表明,该系统适用范围广,处理速度较快,重建精度高,实现了基于视频运动图像的三维重建。     

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.     

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.     

A Survey of Surface Reconstruction from Point Clouds

The area of surface reconstruction has seen substantial progress in the past two decades. The traditional problem addressed by surface reconstruction is to recover the digital representation of a physical shape that has been scanned, where the scanned data contain a wide variety of defects. While much of the earlier work has been focused on reconstructing a piece‐wise smooth representation of the original shape, recent work has taken on more specialized priors to address significantly challenging data imperfections, where the reconstruction can take on different representations—not necessarily the explicit geometry. We survey the field of surface reconstruction, and provide a categorization with respect to priors, data imperfections and reconstruction output. By considering a holistic view of surface reconstruction, we show a detailed characterization of the field, highlight similarities between diverse reconstruction techniques and provide directions for future work in surface reconstruction.     

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维重建优于传统方法,计算效率较高,初始重建鲁棒性强,生成模型质量较好。