Registration of 2D Points Using Geometric Algebra and Tensor Voting

In this paper, we present a novel algorithm that combines the power of expression of Geometric Algebra with the robustness of Tensor Voting to find the correspondences between two sets of 2D points with an underlying rigid transformation. Unlike other popular algorithms for point registration (like the Iterated Closest Points), our algorithm does not require an initialization, works equally well with small and large transformations between the data sets, performs even in the presence of large amounts of outliers (90% and more), and have less chance to be trapped in “local minima”. Furthermore, we will show how this algorithm can be easily extended to account for multiple overlapping motions and certain non-rigid transformations.     

Point set registration: coherent point drift

Point set registration is a key component in many computer vision tasks. The goal of point set registration is to assign correspondences between two sets of points and to recover the transformation that maps one point set to the other. Multiple factors, including an unknown nonrigid spatial transformation, large dimensionality of point set, noise, and outliers, make the point set registration a challenging problem. We introduce a probabilistic method, called the Coherent Point Drift (CPD) algorithm, for both rigid and nonrigid point set registration. We consider the alignment of two point sets as a probability density estimation problem. We fit the Gaussian mixture model (GMM) centroids (representing the first point set) to the data (the second point set) by maximizing the likelihood. We force the GMM centroids to move coherently as a group to preserve the topological structure of the point sets. In the rigid case, we impose the coherence constraint by reparameterization of GMM centroid locations with rigid parameters and derive a closed form solution of the maximization step of the EM algorithm in arbitrary dimensions. In the nonrigid case, we impose the coherence constraint by regularizing the displacement field and using the variational calculus to derive the optimal transformation. We also introduce a fast algorithm that reduces the method computation complexity to linear. We test the CPD algorithm for both rigid and nonrigid transformations in the presence of noise, outliers, and missing points, where CPD shows accurate results and outperforms current state-of-the-art methods.     

Multilinear Factorizations for Multi-Camera Rigid Structure from Motion Problems

Camera networks have gained increased importance in recent years. Existing approaches mostly use point correspondences between different camera views to calibrate such systems. However, it is often difficult or even impossible to establish such correspondences. But even without feature point correspondences between different camera views, if the cameras are temporally synchronized then the data from the cameras are strongly linked together by the motion correspondence: all the cameras observe the same motion. The present article therefore develops the necessary theory to use this motion correspondence for general rigid as well as planar rigid motions. Given multiple static affine cameras which observe a rigidly moving object and track feature points located on this object, what can be said about the resulting point trajectories? Are there any useful algebraic constraints hidden in the data? Is a 3D reconstruction of the scene possible even if there are no point correspondences between the different cameras? And if so, how many points are sufficient? Is there an algorithm which warrants finding the correct solution to this highly non-convex problem? This article addresses these questions and thereby introduces the concept of low-dimensional motion subspaces. The constraints provided by these motion subspaces enable an algorithm which ensures finding the correct solution to this non-convex reconstruction problem. The algorithm is based on multilinear analysis, matrix and tensor factorizations. Our new approach can handle extreme configurations, e.g. a camera in a camera network tracking only one single point. Results on synthetic as well as on real data sequences act as a proof of concept for the presented insights.     

Simultaneous Registration of Multiple Corresponding Point Sets

We present a new technique for the simultaneous registration of multiple corresponding point sets with rigid 3D transformations. This class of problems is a generalization of the classic pairwise point set registration task, involving multiple views with multiple correspondences existing between them. The proposed technique requires the computation of a constant matrix which encodes the point correspondence information, followed by an efficient iterative algorithm to compute the optimal rotations. The optimal translations are then recovered directly through the solution of a linear equation system. The algorithm supports weighting of data according to confidence, and we show how it may be incorporated into two robust estimation frameworks to detect and reject outlier data. We have integrated our method into a generalized multiview ICP surface matching system and tested it with synthetic and real data. These tests indicate that the technique is accurate and efficient. The algorithm also compares favorably to another multiview technique from the literature.     

Robust point correspondence applied to two- and three-dimensionalimage registration

Accurate and robust correspondence calculations are very important in many medical and biological applications. Often, the correspondence calculation forms part of a rigid registration algorithm, but accurate correspondences are especially important for elastic registration algorithms and for quantifying changes over time. In this paper, a new correspondence calculation algorithm, CSM (correspondence by sensitivity to movement), is described. A robust corresponding point is calculated by determining the sensitivity of a correspondence to movement of the point being matched. If the correspondence is reliable, a perturbation in the position of this point should not result in a large movement of the correspondence. A measure of reliability is also calculated. This correspondence calculation method is independent of the registration transformation and has been incorporated into both a 2D elastic registration algorithm for warping serial sections and a 3D rigid registration algorithm for registering pre and postoperative facial range scans. These applications use different methods for calculating the registration transformation and accurate rigid and elastic alignment of images has been achieved with the CSM method. It is expected that this method will be applicable to many different applications and that good results would be achieved if it were to be inserted into other methods for calculating a registration transformation from correspondences     

Non‐Rigid Registration Under Isometric Deformations

We present a robust and efficient algorithm for the pairwise non‐rigid registration of partially overlapping 3D surfaces. Our approach treats non‐rigid registration as an optimization problem and solves it by alternating between correspondence and deformation optimization. Assuming approximately isometric deformations, robust correspondences are generated using a pruning mechanism based on geodesic consistency. We iteratively learn an appropriate deformation discretization from the current set of correspondences and use it to update the correspondences in the next iteration. Our algorithm is able to register partially similar point clouds that undergo large deformations, in just a few seconds. We demonstrate the potential of our algorithm in various applications such as example based articulated segmentation, and shape interpolation.     

Extension of Affine Shape

In this paper, we extend the notion of affine shape, introduced by Sparr, from finite point sets to more general sets. It turns out to be possible to generalize most of the theory. The extension makes it possible to reconstruct, for example, 3D-curves up to projective transformations, from a number of their 2D-projections. An algorithm is presented, which is independent of choice of coordinates, is robust, does not rely on any preselected parameters and works for an arbitrary number of images. In particular this means that a solution is given to the aperture problem of finding point correspondences between curves.     

Rigidity checking of 3D point correspondences under perspectiveprojection

An algorithm is described which rapidly verifies the potential rigidity of three-dimensional point correspondences from a pair of two-dimensional views under perspective projection. The output of the algorithm is a simple yes or no answer to the question “Could these corresponding points from two views be the projection of a rigid configuration?” Potential applications include 3D object recognition from a single previous view and correspondence matching for stereo or motion over widely separated views. The rigidity checking problem is different from the structure-from-motion problem because it is often the case that two views cannot provide an accurate structure-from-motion estimate due to ambiguity and ill conditioning, whereas it is still possible to give an accurate yes/no answer to the rigidity question. Rigidity checking verifies point correspondences using 3D recovery equations as a matching condition. The proposed algorithm improves upon other methods that fall under this approach because it works with as few as six corresponding points under full perspective projection, handles correspondences from widely separated views, makes full use of the disparity of the correspondences, and is integrated with a linear algorithm for 3D recovery due to Kontsevich (1993). Results are given for experiments with synthetic and real image data. A complete implementation of this algorithm is being made publicly available     

A high-accuracy method for fine registration of overlapping point clouds

This paper presents a high-accuracy method for fine registration of two partially overlapping point clouds that have been coarsely registered. The proposed algorithm, which is named dual interpolating point-to-surface method, is principally a modified variant of point-to-surface Iterative Closest Point (ICP) algorithm. The original correspondences are established by adopting a dual surface fitting approach using B-spline interpolation. A novel auxiliary pair constraint based on the surface fitting approach, together with surface curvature information, is employed to remove unreliable point matches. The combined constraint directly utilizes global rigid motion consistency in conjunction with local geometric invariant to reject false correspondences precisely and efficiently. The experimental results involving a number of realistic point clouds demonstrate that the new method can obtain accurate and robust fine registration for pairwise 3D point clouds. This method addresses highest accuracy alignment with less focus on recovery from poor coarse registrations.     

A Correntropy-based Affine Iterative Closest Point Algorithm for Robust Point Set Registration

The iterative closest point (ICP) algorithm has the advantages of high accuracy and fast speed for point set registration, but it performs poorly when the point set has a large number of noisy outliers. To solve this problem, we propose a new affine registration algorithm based on correntropy which works well in the affine registration of point sets with outliers. Firstly, we substitute the traditional measure of least squares with a maximum correntropy criterion to build a new registration model, which can avoid the influence of outliers. To maximize the objective function, we then propose a robust affine ICP algorithm. At each iteration of this new algorithm, we set up the index mapping of two point sets according to the known transformation, and then compute the closed-form solution of the new transformation according to the known index mapping. Similar to the traditional ICP algorithm, our algorithm converges to a local maximum monotonously for any given initial value. Finally, the robustness and high efficiency of affine ICP algorithm based on correntropy are demonstrated by 2D and 3D point set registration experiments.      

A new point matching algorithm for non-rigid registration

Feature-based methods for non-rigid registration frequently encounter the correspondence problem. Regardless of whether points, lines, curves or surface parameterizations are used, feature-based non-rigid matching requires us to automatically solve for correspondences between two sets of features. In addition, there could be many features in either set that have no counterparts in the other. This outlier rejection problem further complicates an already difficult correspondence problem. We formulate feature-based non-rigid registration as a non-rigid point matching problem. After a careful review of the problem and an in-depth examination of two types of methods previously designed for rigid robust point matching (RPM), we propose a new general framework for non-rigid point matching. We consider it a general framework because it does not depend on any particular form of spatial mapping. We have also developed an algorithm—the TPS–RPM algorithm—with the thin-plate spline (TPS) as the parameterization of the non-rigid spatial mapping and the softassign for the correspondence. The performance of the TPS–RPM algorithm is demonstrated and validated in a series of carefully designed synthetic experiments. In each of these experiments, an empirical comparison with the popular iterated closest point (ICP) algorithm is also provided. Finally, we apply the algorithm to the problem of non-rigid registration of cortical anatomical structures which is required in brain mapping. While these results are somewhat preliminary, they clearly demonstrate the applicability of our approach to real world tasks involving feature-based non-rigid registration.     

An algorithm for projective point matching in the presence of spurious points

Point matching is the task of finding correspondences between two sets of points such that the two sets of points are aligned with each other. Pure point matching uses only the location of the points to constrain the problem. This is a problem with broad practical applications, but it has only been well studied when the geometric transformation relating the two point sets is of a relatively low order. Here we present a heuristic local search algorithm that can find correspondences between point sets in two dimensions that are related by a projective transform. Point matching is a harder problem when spurious points appear in the sets to be matched. We present a heuristic algorithm which minimizes the effects of spurious points.     

Efficient multi-modal image registration using local-frequency maps

Fusing of multi-modal data involves automatically estimating the coordinate transformation required to align the multi-modal image data sets. Most existing methods in literature are not fast enough for practical use (taking more than 30 min to 1 h for estimating non-rigid deformations). We propose a very fast algorithm based on matching local-frequency image representations, which naturally allows for processing the data at different scales or resolutions, a very desirable property from a computational efficiency view point. For the rigid motion case, this algorithm involves minimizing – over all rigid transformations – the expectation of the squared difference between the local-frequency representations of the source and target images. In the non-rigid deformations case, we propose to approximate the non-rigid motion by piece-wise rigid motions and use a novel and fast PDE-based morphing technique that estimates this non-rigid alignment. We present implementation results for synthesized and real (rigid) misalignments between CT and MR brain scans. In both the cases, we validate our results against ground truth registrations which for the former case are known and for the latter are obtained from manual registration performed by an expert. Currently, these manual registrations are used in daily clinical practice. Finally, we present examples of non-rigid registration between T1-weighted MR and T2-weighted MR brain images wherein validation is only qualitatively achieved. Our algorithm's performance is comparable to the results obtained from algorithms based on mutual information in the context of accuracy of estimated rigid transforms but is much faster in computational speed. Accepted: 13 November 2001     

一种应用于大角度变换点云的配准方法

针对传统配准法不能很好解决大角度变换点云的配准这一问题,提出一种基于精 确对应特征点对及其 K 邻域点云的配准方法。首先分别计算两组点云的 FPFH 值,根据特征值 建立点云间的对应关系;然后通过 RANSAC 滤除其中错误的匹配点对,得到相对精确的特征点 对集合;之后通过 KD-tree 搜索的方式分别找出特征点对 R 半径邻域内的点,应用 ICP 算法得 到两部分点云的最优收敛;最后将计算得到的相对位置关系应用到原始点云上得到配准结果。 通过对斯坦福大学点云库中 Dragon、Happy Buddha 模型以及 Kinect 采集的石膏像数据进行配 准和比较,实验表明该方法能够有效解决大角度变换点云的配准问题,是一种具有高精度和高 鲁棒性的三维点云配准方法。     

Motion analysis of articulated objects from monocular images

This paper presents a new method of motion analysis of articulated objects from feature point correspondences over monocular perspective images without imposing any constraints on motion. An articulated object is modeled as a kinematic chain consisting of joints and links, and its 3D joint positions are estimated within a scale factor using the connection relationship of two links over two or three images. Then, twists and exponential maps are employed to represent the motion of each link, including the general motion of the base link and the rotation of other links around their joints. Finally, constraints from image point correspondences, which are similar to that of the essential matrix in rigid motion, are developed to estimate the motion. In the algorithm, the characteristic of articulated motion, i.e., motion correlation among links, is applied to decrease the complexity of the problem and improve the robustness. A point pattern matching algorithm for articulated objects is also discussed in this paper. Simulations and experiments on real images show the correctness and efficiency of the algorithms.     

Reconstruction of General Curves,Using Factorization and Bundle Adjustment

In this paper, we extend the notion of affine shape, introduced by Sparr, from finite point sets to curves. The extension makes it possible to reconstruct 3D-curves up to projective transformations, from a number of their 2D-projections. We also extend the bundle adjustment technique from point features to curves.The first step of the curve reconstruction algorithm is based on affine shape. It is independent of choice of coordinates, is robust, does not rely on any preselected parameters and works for an arbitrary number of images. In particular this means that, except for a small set of curves (e.g. a moving line), a solution is given to the aperture problem of finding point correspondences between curves. The second step takes advantage of any knowledge of measurement errors in the images. This is possible by extending the bundle adjustment technique to curves.Finally, experiments are performed on both synthetic and real data to show the performance and applicability of the algorithm.     

Branch-and-Bound Methods for Euclidean Registration Problems

In this paper, we propose a practical and efficient method for finding the globally optimal solution to the problem of determining the pose of an object. We present a framework that allows us to use point-to-point, point-to-line, and point-to-plane correspondences for solving various types of pose and registration problems involving euclidean (or similarity) transformations. Traditional methods such as the iterative closest point algorithm or bundle adjustment methods for camera pose may get trapped in local minima due to the nonconvexity of the corresponding optimization problem. Our approach of solving the mathematical optimization problems guarantees global optimality. The optimization scheme is based on ideas from global optimization theory, in particular convex underestimators in combination with branch-and-bound methods. We provide a provably optimal algorithm and demonstrate good performance on both synthetic and real data. We also give examples of where traditional methods fail due to the local minima problem.     

Geometrical Analysis of Two Sets of 3D Correspondence Data Patterns for the Registration of Free-Form Shapes

The iterative closest point (ICP) algorithm represents an efficient method to establish an initial set of possible correspondences between two overlapping range images. An inherent limitation of the algorithm is the introduction of false matches, a problem that has been tackled by a variety of schemes mainly based on local invariants described in a single coordinate frame. In this paper we propose using global rigid motion constraints to deal with false matches. Such constraints are derived from geometric properties of correspondence vectors bridging the points described in different coordinate frames before and after a rigid motion. In order to accurately and efficiently estimate the parameters of interest, the Monte Carlo resampling technique is used and motion parameter candidates are then synthesised by a median filter. The proposed algorithm is validated based on both synthetic data and real range images. Experimental results show that the proposed algorithm has advantages over existing registration methods concerning robustness, accuracy, and efficiency.