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.     

Outlier correction from uncalibrated image sequence using the Triangulation method

We propose a robust algorithm for estimating the projective reconstruction from image features using the RANSAC-based Triangulation method. In this method, we select input points randomly, separate the input points into inliers and outliers by computing their reprojection error, and correct the outliers so that they can become inliers. The reprojection error and correcting outliers are computed using the Triangulation method. After correcting the outliers, we can reliably recover projective motion and structure using the projective factorization method. Experimental results showed that errors can be reduced significantly compared to the previous research as a result of robustly estimated projective reconstruction.     

一个基本矩阵的鲁棒估计算法

通过分析基本矩阵的鲁棒估计方法的特点,提出了三点改进：在RANSAC（RANdom SAmpling Consensus）方法中采用了极小化再投影误差判别数据点的类别;给出再投影误差的一阶近似算法;由求出的基本矩阵和局内点数据采用LM算法对结果过一步求精,给出更好的基本矩阵估计值,使得再投影误差进一步减小,避免结果趋于局部极值。合成数据和真实图像实验均证明了该方法的有效性和可靠性。     

Removing outliers by minimizing the sum of infeasibilities

This paper shows that we can classify latent outliers efficiently through the process of minimizing the sum of infeasibilities (SOI). The SOI minimization has been developed in the area of convex optimization to find an initial solution, solve a feasibility problem, or check out some inconsistent constraints. It was also adopted recently as an approximation method to minimize a robust error function under the framework of the _L∞$L_{\infty }$ norm minimization for geometric vision problems. In this paper, we show that the SOI minimization is practically effective in collecting outliers when it is applied to geometric vision problems. In particular, this method is useful in structure and motion reconstruction where methods such as RANSAC are not applicable. We demonstrate the effectiveness of the method through experiments with synthetic and real data sets.     

Imposing Semi-Local Geometric Constraints for Accurate Correspondences Selection in Structure from Motion: A Game-Theoretic Perspective

Most Structure from Motion pipelines are based on the iterative refinement of an initial batch of feature correspondences. Typically this is performed by selecting a set of match candidates based on their photometric similarity; an initial estimate of camera intrinsic and extrinsic parameters is then computed by minimizing the reprojection error. Finally, outliers in the initial correspondences are filtered by enforcing some global geometric property such as the epipolar constraint. In the literature many different approaches have been proposed to deal with each of these three steps, but almost invariably they separate the first inlier selection step, which is based only on local image properties, from the enforcement of global geometric consistency. Unfortunately, these two steps are not independent since outliers can lead to inaccurate parameter estimation or even prevent convergence, leading to the well known sensitivity of all filtering approaches to the number of outliers, especially in the presence of structured noise, which can arise, for example, when the images present several repeated patterns. In this paper we introduce a novel stereo correspondence selection scheme that casts the problem into a Game-Theoretic framework in order to guide the inlier selection towards a consistent subset of correspondences. This is done by enforcing geometric constraints that do not depend on full knowledge of the motion parameters but rather on some semi-local property that can be estimated from the local appearance of the image features. The practical effectiveness of the proposed approach is confirmed by an extensive set of experiments and comparisons with state-of-the-art techniques.     

Projective reconstruction of ellipses from multiple images

This paper presents a new approach for reconstructing 3D ellipses (including circles) from a sequence of 2D images taken by uncalibrated cameras. Our strategy is to estimate an ellipse in 3D space by reconstructing N(≥5) 3D points (called representative points) on it, where the representative points are reconstructed by minimizing the distances from their projections to the measured 2D ellipses on different images (i.e., 2D reprojection error). This minimization problem is transformed into a sequence of minimization sub-problems that can be readily solved by an algorithm which is guaranteed to converge to a (local) minimum of the 2D reprojection error. Our method can reconstruct multiple 3D ellipses simultaneously from multiple images and it readily handles images with missing and/or partially occluded ellipses. The proposed method is evaluated using both synthetic and real data.     

改进L∞优化算法用于三维空间点快速精确重建

多视几何中的多种问题可以通过最小化L_∞范数误差获得全局最优解。但最小化L_∞范数误差算法的缺点是对外点敏感,相关的改进算法虽然可以克服外点带来的影响,但计算速度较慢。提出一种改进的最小化L_∞范数误差算法,用于从包含外点的图像序列中快速精确重建三维空间点。真实测试图像的实验结果证明该算法可以在包含外点的情况下获得空间点的全局最优解,相比其他算法速度有较大的提高。     

Practical Global Optimization for Multiview Geometry

This paper presents a practical method for finding the provably globally optimal solution to numerous problems in projective geometry including multiview triangulation, camera resectioning and homography estimation. Unlike traditional methods which may get trapped in local minima due to the non-convex nature of these problems, this approach provides a theoretical guarantee of global optimality. The formulation relies on recent developments in fractional programming and the theory of convex underestimators and allows a unified framework for minimizing the standard L ₂-norm of reprojection errors which is optimal under Gaussian noise as well as the more robust L ₁-norm which is less sensitive to outliers. Even though the worst case complexity of our algorithm is exponential, the practical efficacy is empirically demonstrated by good performance on experiments for both synthetic and real data. An open source MATLAB toolbox that implements the algorithm is also made available to facilitate further research.     

Multi-stage 3D reconstruction under circular motion

In this paper, we propose a new method for 3D reconstruction from an image sequence captured by a camera with constant intrinsic parameters undergoing circular motion. We introduce a method, called circular projective reconstruction, for enforcing the circular constraint in a factorization-based projective reconstruction. To deal with the missing data problem, our method uses a multi-stage approach to reconstructing the objects and cameras, which first computes a circular projective reconstruction of a sub-sequence and then extends the reconstruction to the complete sequence. Camera matrix, rotation angles, and 3D structure are computed iteratively in a way that the 2D reprojection error is minimized. The algorithm is evaluated using real image sequences.     

Spectral moving removal of non-isolated surface outlier clusters

In this paper, we propose a new algorithm for the fast removal of non-isolated surface outlier clusters. It consists of three basic components: (a) an intrinsic metric for detecting outliers on the basis of minimum variance principle; (b) bi-means clustering of a normalized histogram; (c) surface propagation for a geometric coherence check. The unique contributions of our approach include (a) a new idea of identifying non-isolated outlier clusters and linking the local spectral property to a global outlier removal process; (b) a modified data clustering scheme with a geometric coherence check. In comparison with existing algorithms, our algorithm is evaluated in terms of the quality and computational cost of outlier removal. Numerical experiments indicate the effectiveness of our approach in the aspects of convergence, accuracy, time and space efficiency.     

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

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

全局优化的一类新的F-C函数

针对求解全局优化问题,有很多种求解方法。文中提出了一种快速求解一般无约束最优化问题的辅助函数方法。即F-C函数方法。该方法与填充函数法和跨越函数法相比较,既有相同点又有不同点。F-C函数法最大的优点就是在极小化F-C函数阶段中只需要进行一次局部极小化算法就能得到比当前极小值更低的目标函数局部极小点。文中在无Lipschitz连续的条件下,给出了一类新的求解全局优化问题的F-C函数。文中讨论了该F-C函数的优良性质并对该函数设计了相应的算法。最后,通过数值试验表明该F-C函数方法具有有效性和可行性。     

基于序列图像的鲁棒三维重建方法

提出了基于序列图像的鲁棒三维重建方法。首先利用两幅图像的最优参数估计,然后添加新图像并采用稀疏调整,减少图像坐标测量值的最小几何误差。通过对三维结构和摄像机参数进行全局优化处理,以提高重建的鲁棒性。实验结果表明,该方法提高了重建的精度和鲁棒性,并真实地再现了物体的三维模型。     

一种新的射影重建方法

提出一种新的射影重建方法。它以最小化射影三维空间点的平均二维反投影误差为准则,以奇异值分解为工具,分步线性迭代实现求解过程,避免了传统射影重建方法中复杂的非线性优化过程和基础矩阵计算过程,且不需要任何初始估计,适用于匹配特征点存在“丢失点”的情况,不受相机特殊运动的限制。利用虚拟物体和真实物体图像序列进行了实验,证明该方法具有计算简单、准确性和鲁棒性高等方面的特点,具有较高的实用价值。     

Robust refinement methods for camera calibration and 3D reconstruction from multiple images

This paper proposes robust refinement methods to improve the popular patch multi-view 3D reconstruction algorithm by Furukawa and Ponce (2008). Specifically, a new method is proposed to improve the robustness by removing outliers based on a filtering approach. In addition, this work also proposes a method to divide the 3D points in to several buckets for applying the sparse bundle adjustment algorithm (SBA) individually, removing the outliers and finally merging them. The residuals are used to filter potential outliers to reduce the re-projection error used as the performance evaluation of refinement. In our experiments, the original mean re-projection error is about 47.6. After applying the proposed methods, the mean error is reduced to 2.13.     

Unified Computation of Strict Maximum Likelihood for Geometric Fitting

A new numerical scheme is presented for computing strict maximum likelihood (ML) of geometric fitting problems having an implicit constraint. Our approach is orthogonal projection of observations onto a parameterized surface defined by the constraint. Assuming a linearly separable nonlinear constraint, we show that a theoretically global solution can be obtained by iterative Sampson error minimization. Our approach is illustrated by ellipse fitting and fundamental matrix computation. Our method also encompasses optimal correction, computing, e.g., perpendiculars to an ellipse and triangulating stereo images. A detailed discussion is given to technical and practical issues about our approach.     

基于未标定图像的三维重建算法

提出一种基于多幅未标定图像的三维重建算法。在标记点匹配的基础上进行射影重建,通过施加度量约束将射影重建升级为欧氏重建,即利用未标定的透视图像恢复相机的内、外部参数以及标记点的三维空间坐标,实现场景的三维重建。标记点易于进行点对精确匹配,较手动拾取匹配提高了效率。实验结果表明,利用该算法能够大幅减小再投影误差。     

Robust dense reconstruction by range merging based on confidence estimation

Although the stereo matching problem has been extensively studied during the past decades, automatically computing a dense 3D reconstruction from several multiple views is still a difficult task owing to the problems of textureless regions, outliers, detail loss, and various other factors. In this paper, these difficult problems are handled effectively by a robust model that outputs an accurate and dense reconstruction as the final result from an input of multiple images captured by a normal camera. First, the positions of the camera and sparse 3D points are estimated by a structure-from-motion algorithm and we compute the range map with a confidence estimation for each image in our approach. Then all the range maps are integrated into a fine point cloud data set. In the final step we use a Poisson reconstruction algorithm to finish the reconstruction. The major contributions of the work lie in the following points: effective range-computation and confidence-estimation methods are proposed to handle the problems of textureless regions, outliers and detail loss. Then, the range maps are merged into the point cloud data in terms of a confidence-estimation. Finally, Poisson reconstruction algorithm completes the dense mesh. In addition, texture mapping is also implemented as a post-processing work for obtaining good visual effects. Experimental results are presented to demonstrate the effectiveness of the proposed approach.     

Shape Reconstruction Incorporating Multiple Nonlinear Geometric Constraints

This paper deals with the reconstruction of three-dimensional (3D) geometric shapes based on observed noisy 3D measurements and multiple coupled nonlinear shape constraints. Here a shape could be a complete object, a portion of an object, a part of a building etc. The paper suggests a general incremental framework whereby constraints can be added and integrated in the model reconstruction process, resulting in an optimal trade-off between minimization of the shape fitting error and the constraint tolerances. After defining sets of main constraints for objects containing planar and quadric surfaces, the paper shows that our scheme is well behaved and the approach is valid through application on different real parts. This work is the first to give such a large framework for the integration of numerical geometric relationships in object modeling from range data. The technique is expected to have a great impact in reverse engineering applications and manufactured object modeling where the majority of parts are designed with intended feature relationships.     

A Surface Reconstruction Method Using Global Graph Cut Optimization

Surface reconstruction from multiple calibrated images has been mainly approached using local methods, either as a continuous optimization problem driven by level sets, or by discrete volumetric methods such as space carving. We propose a direct surface reconstruction approach which starts from a continuous geometric functional that is minimized up to a discretization by a global graph-cut algorithm operating on a 3D embedded graph. The method is related to the stereo disparity computation based on graph-cut formulation, but fundamentally different in two aspects. First, existing stereo disparity methods are only interested in obtaining layers of constant disparity, while we focus on high resolution surface geometry. Second, most of the existing graph-cut algorithms only reach approximate solutions, while we guarantee a global minimum. The whole procedure is consistently incorporated into a voxel representation that handles both occlusions and discontinuities. We demonstrate our algorithm on real sequences, yielding remarkably detailed surface geometry up to 1/10th of a pixel. Author has worked on this project during his Ph. D. at ARTIS