Translation averaging solves for 3D camera translations given many pairwise relative translation directions. The mismatch between inputs (directions) and output estimates (absolute translations) makes translation averaging a challenging problem, which is often addressed by comparing either directions or displacements using relaxed cost functions that are relatively easy to optimize. However, the distinctly different nature of the cost functions leads to varied behaviour under different baselines and noise conditions. In this paper, we argue that translation averaging can benefit from a fusion of the two approaches. Specifically, we recursively fuse the individual updates suggested by direction and displacement-based methods using their uncertainties. The uncertainty of each estimate is modelled by the inverse of the Hessian of the corresponding optimization problem. As a result, our method utilizes the advantages of both methods in a principled manner. The superiority of our translation averaging scheme is demonstrated via the improved accuracies of camera translations on benchmark datasets compared to the state-of-the-art methods.

In Structure-from-Motion (SfM), the underlying view-graphs of unordered image collections generally have a highly redundant set of edges that can be sparsified for efficiency without significant loss of reconstruction quality. Often, there are also false edges due to incorrect image retrieval and repeated structures (symmetries) that give rise to ghosting and superimposed reconstruction artifacts. We present a unified method to simultaneously sparsify the viewgraph and remove false edges. We propose a scoring mechanism based on camera triplets that identifies edge redundancy as well as false edges. Our edge selection is formulated as an optimization problem which can be provably solved using a simple thresholding scheme. This results in a highly efficient algorithm which can be incorporated as a pre-processing step into any SfM pipeline, making it practically usable. We demonstrate the utility of our method on generic and ambiguous datasets that cover the range of small, medium and large-scale datasets, all with different statistical properties. Sparsification of generic datasets using our method significantly reduces reconstruction time while maintaining the accuracy of the reconstructions as well as removing ghosting artifacts. For ambiguous datasets, our method removes false edges, thereby avoiding incorrect superimposed reconstructions.

Geometric estimation problems in vision are often solved via minimization of statistical loss functions which account for the presence of outliers in the observations. The corresponding energy landscape often has many local minima. Many approaches attempt to avoid local minima by an-nealing the scale parameter of loss functions using methods such as graduated non-convexity (GNC). However, little attention has been paid to the annealing schedule, which is often carried out in a fixed manner, resulting in a poor speed-accuracy trade-off and unreliable convergence to the global minimum. In this paper, we propose a principled approach for adaptively annealing the scale for GNC by tracking the positive-definiteness (i.e. local convexity) of the Hessian of the cost function. We illustrate our approach using the classic problem of registering 3D correspondences in the presence of noise and outliers. We also develop approximations to the Hessian that significantly speeds up our method. The effectiveness of our approach is validated by comparing its performance with state-of-the-art 3D registration approaches on a number of synthetic and real datasets. Our approach is accurate and efficient and converges to the global solution more reliably than the state-of-the-art methods.

In 3D computer vision, translation averaging solves for absolute translations given a set of pairwise relative translation directions. While there has been much work on robustness to outliers and studies on the uniqueness of the solution, this paper deals with a distinctly different problem of sensitivity in translation averaging under uncertainty. We first analyze sensitivity in estimating scales corresponding to relative directions under small perturbations of the relative directions. Then, we formally define the conditioning of the translation averaging problem, which assesses the reliability of estimated translations based solely on the input directions. We give a sufficient criterion to ensure that the problem is well-conditioned. Subsequently, we provide an efficient algorithm to identify and remove combinations of directions which make the problem ill-conditioned while ensuring uniqueness of the solution. We demonstrate the utility of such analysis in global structure-from-motion pipelines for obtaining 3D reconstructions, which reveals the benefits of filtering the ill-conditioned set of directions in translation averaging in terms of reduced translation errors, a higher number of 3D points triangulated and faster convergence of bundle adjustment.

Rotation averaging is the problem of recovering 3D camera rotations from a number of pairwise relative rotation estimates. The state-of-the-art method of [51 involves robust averaging in the Lie-algebra of 3D rotations using an $\ell_{\frac{1}{2}}$ loss function which is carried out using an iteratively reweighted least squares (IRLS) minimization. In this paper we argue that the performance of IRLS-based rotation averaging is intimately connected with two factors: a) the nature of the robust loss function used, and b) the initialization. We make two contributions. Firstly, we analyse the pitfalls associated with the unbounded weights in IRLS minimization of $\ell_{p}(0\lt p\lt 2)$ loss functions in the context of rotation averaging. We elucidate the design choices and modifications implicit to the state-of-the-art method of [5] that overcomes these problems. Secondly, we argue that the $\ell_{\frac{1}{2}}$ -based IRLS method is inflexible in adapting to the specific noise characteristics of individual datasets, leading to poorer performance. We remedy this limitation by means of a Geman-McClure loss function embedded in a graduated optimization framework. We present results on a number of large-scale real-world datasets to demonstrate that our proposed method outpetforms state-of-the-art methods in terms of both efficiency and accuracy.

We present 3DRegNet, a novel deep learning architecture for the registration of 3D scans. Given a set of 3D point correspondences, we build a deep neural network to address the following two challenges: (i) classification of the point correspondences into inliers/outliers, and (ii) regression of the motion parameters that align the scans into a common reference frame. With regard to regression, we present two alternative approaches: (i) a Deep Neural Network (DNN) registration and (ii) a Procrustes approach using SVD to estimate the transformation. Our correspondence-based approach achieves a higher speedup compared to competing baselines. We further propose the use of a refinement network, which consists of a smaller 3DRegNet as a refinement to improve the accuracy of the registration. Extensive experiments on two challenging datasets demonstrate that we outperform other methods and achieve state-of-the-art results.

We present a robust, fast and accurate method for registration of 3D scans. Using correspondences, our method optimizes a robust cost function on the intrinsic representation of rigid motions, i.e., the Special Euclidean group SE(3). We exploit the geometric properties of Lie groups as well as the robustness afforded by an iteratively reweighted least squares optimization. We also generalize our approach to a joint multiview method that simultaneously solves for the registration of a set of scans. Our approach significantly outperforms the state-of-the-art robust 3D registration method based on a line process in terms of both speed and accuracy. We show that this line process method is a special case of our principled geometric solution. Finally, we also present scenarios where global registration based on feature correspondences fails but multiview ICP based on our robust motion estimation is successful.

This paper addresses the problem of robust and efficient relative rotation averaging in the context of large-scale Structure from Motion. Relative rotation averaging finds global or absolute rotations for a set of cameras from a set of observed relative rotations between pairs of cameras. We propose a generalized framework of relative rotation averaging that can use different robust loss functions and jointly optimizes for all the unknown camera rotations. Our method uses a quasi-Newton optimization which results in an efficient iteratively reweighted least squares (IRLS) formulation that works in the Lie algebra of the 3D rotation group. We demonstrate the performance of our approach on a number of large-scale data sets. We show that our method outperforms existing methods in the literature both in terms of speed and accuracy.

We present a fast and lightweight method for 3D registration of scenes by exploiting the presence of planar regions. Since planes can be easily and accurately represented by parametric models, we can both efficiently and accurately solve for the motion between pairs of 3D scans. Additionally, our method can also utilize the available non-planar regions if necessary to resolve motion ambiguities. The result is a fast and accurate method for 3D scan registration that can also be easily utilized in a multiview registration framework based on motion averaging. We present extensive results on datasets containing planar regions to demonstrate that our method yields results comparable in accuracy with the state-of-the-art while only taking a fraction of computation time compared with conventional approaches that are based on motion estimates through 3D point correspondences.

In recent years, there have been a variety of proposals for high quality 3D reconstruction by fusion of depth and normal maps that contain good low and high frequency information respectively. Typically, these methods create an initial mesh representation of the complete object or scene being scanned. Subsequently, normal estimates are assigned to each mesh vertex and a mesh-normal fusion step is carried out. In this paper, we present a complete pipeline for such depth-normal fusion. The key innovations in our pipeline are twofold. Firstly, we introduce a global multi-view non-rigid refinement step that corrects for the non-rigid misalignment present in the depth and normal maps. We demonstrate that such a correction is crucial for preserving fine-scale 3D features in the final reconstruction. Secondly, despite adequate care, the averaging of multiple normals invariably results in blurring of 3D detail. To mitigate this problem, we propose an approach that selects one out of many available normals. Our global cost for normal selection incorporates a variety of desirable properties and can be efficiently solved using graph cuts. We demonstrate the efficacy of our approach in generating high quality 3D reconstructions of both synthetic and real 3D models and compare with existing methods in the literature.

The increased availability of point cloud data in recent years has lead to a concomitant requirement for high quality denoising methods. This is particularly the case with data obtained using depth cameras or from multi-view stereo reconstruction as both approaches result in noisy point clouds and include significant outliers. Most of the available denoising methods in the literature are not sufficiently robust to outliers and/or are unable to preserve fine-scale 3D features in the denoised representations. In this paper we propose an approach to point cloud denoising that is both robust to outliers and capable of preserving fine-scale 3D features. We identify and remove outliers by utilising a dissimilarity measure based on point positions and their corresponding normals. Subsequently, we use a robust approach to estimate surface point positions in a manner designed to preserve sharp and fine-scale 3D features. We demonstrate the efficacy of our approach and compare with similar methods in the literature by means of experiments on synthetic and real data including large-scale 3D reconstructions of heritage monuments.

We propose a novel global 3D mesh denoising method that is carried out in two steps, i.e. Mollification of normals followed by vertex correction. Both steps involve minimising sparse, quadratic cost functions that yield efficient non-iterative solutions. In the mollification step, we use adaptive weights that allows for appropriate diffusion while preserving features. While many existing methods only correct for the vertex position along the normal direction, we argue that this is inadequate in many scenarios. Instead, we allow for vertex correction in all directions while enforcing a novel face fairness penalty that preserves face shapes in the denoised mesh. We present a number of tests and examples that demonstrate the efficacy of our method in denoising while preserving face fairness. We demonstrate the superiority of our approach over some relevant methods in the literature.

In this paper, we propose a novel uncalibrated photometric method for refining depth maps of multi-albedo objects obtained from consumer depth cameras like Kinect. Existing uncalibrated photometric methods either assume that the object has constant albedo or rely on segmenting images into constant albedo regions. The method of this paper does not require the constant albedo assumption and we believe it is the first work of its kind to handle objects with arbitrary albedo under uncalibrated illumination. We first robustly estimate a rank 3 approximation of the observed brightness matrix using an iterative reweighting method. Subsequently, we factorize this rank reduced brightness matrix into the corresponding lighting, albedo and surface normal components. The proposed factorization is shown to be convergent. We experimentally demonstrate the value of our approach by presenting highly accurate three-dimensional reconstructions of a wide variety of objects. Additionally, since any photometric method requires a radiometric calibration of the camera used, we also present a direct radiometric calibration technique for the infra-red camera of the structured-light stereo depth scanner. Unlike existing methods, this calibration technique does not depend on a known calibration object or on the properties of the scene illumination used.

Many patch-based image denoising methods can be viewed as data-dependent smoothing filters that carry out a weighted averaging of similar pixels. It has recently been argued that these averaging filters can be improved using their doubly stochastic approximation, which are symmetric and stable smoothing operators. In this paper, we introduce a simple principle of consistency that argues that the relative similarities between pixels as imputed by the averaging matrix should be preserved in the filtered output. The resultant consistency filter has the theoretically desirable properties of being symmetric and stable, and is a generalized doubly stochastic matrix. In addition, we can also interpret our consistency filter as a specific form of Laplacian regularization. Thus, our approach unifies two strands of image denoising methods, i.e., symmetric smoothing filters and spectral graph theory. Our consistency filter provides high-quality image denoising and significantly outperforms the doubly stochastic version. We present a thorough analysis of the properties of our proposed consistency filter and compare its performance with that of other significant methods for image denoising in the literature.

In this paper we present a depth-guided photometric 3D reconstruction method that works solely with a depth camera like the Kinect. Existing methods that fuse depth with normal estimates use an external RGB camera to obtain photometric information and treat the depth camera as a black box that provides a low quality depth estimate. Our contribution to such methods are two fold. Firstly, instead of using an extra RGB camera, we use the infra-red (IR) camera of the depth camera system itself to directly obtain high resolution photometric information. We believe that ours is the first method to use an IR depth camera system in this manner. Secondly, photometric methods applied to complex objects result in numerous holes in the reconstructed surface due to shadows and self-occlusions. To mitigate this problem, we develop a simple and effective multiview reconstruction approach that fuses depth and normal information from multiple viewpoints to build a complete, consistent and accurate 3D surface representation. We demonstrate the efficacy of our method to generate high quality 3D surface reconstructions for some complex 3D figurines.

In this paper, we present an extension of the iterative closest point (ICP) algorithm that simultaneously registers multiple 3D scans. While ICP fails to utilize the multiview constraints available, our method exploits the information redundancy in a set of 3D scans by using the averaging of relative motions. This averaging method utilizes the Lie group structure of motions, resulting in a 3D registration method that is both efficient and accurate. In addition, we present two variants of our approach, i.e., a method that solves for multiview 3D registration while obeying causality and a transitive correspondence variant that efficiently solves the correspondence problem across multiple scans. We present experimental results to characterize our method and explain its behavior as well as those of some other multiview registration methods in the literature. We establish the superior accuracy of our method in comparison to these multiview methods with registration results on a set of well-known real datasets of 3D scans.

In this paper we address the problem of robust and efficient averaging of relative 3D rotations. Apart from having an interesting geometric structure, robust rotation averaging addresses the need for a good initialization for large scale optimization used in structure-from-motion pipelines. Such pipelines often use unstructured image datasets harvested from the internet thereby requiring an initialization method that is robust to outliers. Our approach works on the Lie group structure of 3D rotations and solves the problem of large-scale robust rotation averaging in two ways. Firstly, we use modern ℓ1optimizers to carry out robust averaging of relative rotations that is efficient, scalable and robust to outliers. In addition, we also develop a two step method that uses the ℓ1solution as an initialisation for an iteratively reweighted least squares (IRLS) approach. These methods achieve excellent results on large-scale, real world datasets and significantly outperform existing methods, i.e. the state-of-the-art discrete-continuous optimization method of [3] as well as the Weiszfeld method of [8]. We demonstrate the efficacy of our method on two large scale real world datasets and also provide the results of the two aforementioned methods for comparison.

The higher-order clustering problem arises when data is drawn from multiple subspaces or when observations fit a higher-order parametric model. Most solutions to this problem either decompose higher-order similarity measures for use in spectral clustering or explicitly use low-rank matrix representations. In this paper we present our approach of Sparse Grassmann Clustering (SGC) that combines attributes of both categories. While we decompose the higher order similarity tensor, we cluster data by directly finding a low dimensional representation without explicitly building a similarity matrix. By exploiting recent advances in online estimation on the Grassmann manifold (GROUSE) we develop an efficient and accurate algorithm that works with individual columns of similarities or partial observations thereof. Since it avoids the storage and decomposition of large similarity matrices, our method is efficient, scalable and has low memory requirements even for large-scale data. We demonstrate the performance of our SGC method on a variety of segmentation problems including planar segmentation of Kinect depth maps and motion segmentation of the Hopkins 155 dataset for which we achieve performance comparable to the state-of-the-art.

While spectral clustering has been applied successfully to problems in computer vision, their applicability is limited to pairwise similarity measures that form a probability matrix. However many geometric problems with parametric forms require more than two observations to estimate a similarity measure, e.g. epipolar geometry. In such cases we can only define the probability of belonging to the same cluster for an n-tuple of points and not just a pair, leading to an n-dimensional probability tensor. However spectral clustering methods are not available for tensors. In this paper we present an algorithm to infer a similarity matrix by decomposing the n-dimensional probability tensor. Our method exploits the super-symmetry of the probability tensor to provide a randomised scheme that does not require the explicit computation of the probability tensor. Our approach is fast and accurate and its applicability is illustrated on two significant problems, namely perceptually salient geometric grouping and parametric motion segmentation (like affine, epipolar etc).

In this paper we describe two methods for estimating the motion parameters of an image sequence. For a sequence of N images, the global motion can be described by N-1 independent motion models. On the other hand, in a sequence there exist as many as /sub 2///sup N(N-1)/ pairwise relative motion constraints that can be solve for efficiently. In this paper we show how to linearly solve for consistent global motion models using this highly redundant set of constraints. In the first case, our method involves estimating all available pairwise relative motions and linearly fining a global motion model to these estimates. In the second instance, we exploit the fact that algebraic (i.e. epipolar) constraints between various image pairs are all related to each other by the global motion model. This results in an estimation method that directly computes the motion of the sequence by using all possible algebraic constraints. Unlike using reprojection error, our optimisation method does not solve for the structure of points resulting in a reduction of the dimensionality of the search space. Our algorithms are used for both 3D camera motion estimation and camera calibration. We provide real examples of both applications.

We propose an efficient, non-iterative method for estimating optical flow. We develop a probabilistic framework that is appropriate for describing the inherent uncertainty in the brightness constraint due to errors in image derivative computation. We separate the flow into two 1D representations and pose the problem of flow estimation as one of solving for the most probable configuration of 1D labels in an Markov random fields (MRF) with linear clique potentials. The global optimum for this problem can be efficiently solved for using the maximum flow computation in a graph. We develop this formulation and describe how the use of the probabilistic framework, the parametrisation and MRF formulation together enables one to capture the desirable properties for flow estimation, especially preserving motion discontinuities. We demonstrate the performance of our algorithm and compare our results with that of other algorithms described by Barron et. al. (1994).

We describe a framework for aligning images without needing to establish explicit feature correspondences. We assume that the geometry between the two images can be adequately described by an affine transformation and develop a framework that uses the statistical distribution of geometric properties of image contours to estimate the relevant transformation parameters. The estimates obtained using the proposed method are robust to illumination conditions, sensor characteristics, etc., since image contours are relatively invariant to these changes. Moreover, the distributional nature of our method alleviates some of the common problems due to contour fragmentation, occlusion, clutter, etc. We provide empirical evidence of the accuracy and robustness of our algorithm. Finally, we demonstrate our method on both real and synthetic images, including multisensor image pairs.

We describe an essentially algorithm-independent experimental comparison of projective versus Euclidean reconstruction. The Euclidean approach is as accurate as the projective one, even with significant calibration error and for the pure projective structure. Projective optimization has less of a local-minima problem than its Euclidean equivalent. We describe techniques that enhance the convergence of optimization algorithms.

We describe a framework for image alignment that does not use explicit feature correspondences. We show how certain geometric properties of image contours are related to the parameters of the geometric transformation between the images. For a transformation model, we show how to recover the transformation parameters using simple statistical distributions of geometric properties. The use of these statistical descriptions eliminates the need for establishing explicit feature correspondence. The proposed method is robust to problems of occlusion, clutter and errors in low-level processing. We demonstrate the effectiveness of our method on real images.