High Resolution Tracking of Non-Rigid Motion of Densely Sampled 3D Data Using Harmonic Maps

We present a novel automatic method for high resolution, non-rigid dense 3D point tracking. High quality dense point clouds of non-rigid geometry moving at video speeds are acquired using a phase-shifting structured light ranging technique. To use such data for the temporal study of subtle motions such as those seen in facial expressions, an efficient non-rigid 3D motion tracking algorithm is needed to establish inter-frame correspondences. The novelty of this paper is the development of an algorithmic framework for 3D tracking that unifies tracking of intensity and geometric features, using harmonic maps with added feature correspondence constraints. While the previous uses of harmonic maps provided only global alignment, the proposed introduction of interior feature constraints allows to track non-rigid deformations accurately as well. The harmonic map between two topological disks is a diffeomorphism with minimal stretching energy and bounded angle distortion. The map is stable, insensitive to resolution changes and is robust to noise. Due to the strong implicit and explicit smoothness constraints imposed by the algorithm and the high-resolution data, the resulting registration/deformation field is smooth, continuous and gives dense one-to-one inter-frame correspondences. Our method is validated through a series of experiments demonstrating its accuracy and efficiency.     

Robust Non-rigid Registration Based on Affine ICP Algorithm and Part-Based Method

The classical affine iterative closest point (ICP) algorithm is fast and accurate for affine registration between two point sets, but it is easy to fall into a local minimum. As an extension of the classical affine registration algorithm, this paper first proposes an affine ICP algorithm based on control point guided, and then applies this new method to establish a robust non-rigid registration algorithm based on local affine registration. The algorithm uses a hierarchical iterative method to complete the point set non-rigid registration from coarse to fine. In each iteration, the sub data point sets and sub model point sets are divided, meanwhile, the shape control points of each sub point set are updated. Then we use the control point guided affine ICP algorithm to solve the local affine transformation between the corresponding sub point sets. Next, the local affine transformation obtained by the previous step is used to update the sub data point sets and their shape control point sets. Experimental results demonstrate that the accuracy and convergence of our algorithm are greatly improved compared with the traditional point set non-rigid registration algorithms.     

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.     

The thin plate spline robust point matching (TPS-RPM) algorithm: A revisit

This paper reviews the TPS-RPM algorithm (Chui and Rangarajan, 2003) for robustly registering two sets of points and demonstrates from a theoretical point of view its inherent limited performance when outliers are present in both point sets simultaneously. A double-sided outlier handling approach is proposed to overcome this limitation with a rigorous mathematical proof as the underlying theoretical support. This double-sided outlier handling approach is proved to be equivalent to the original formulation of the point matching problem. For a practical application, we also extend the TPS-RPM algorithms to non-rigid image registration by registering two sets of sparse features extracted from images. The intensity information of the extracted features are incorporated into feature matching in order to reduce the impact from outliers. Our experiments demonstrate the double-sided outlier handling approach and the efficiency of intensity information in assisting outlier detection.     

Registration of 3D Points Using Geometric Algebra and Tensor Voting

We address the problem of finding the correspondences of two point sets in 3D undergoing a rigid transformation. Using these correspondences the motion between the two sets can be computed to perform registration. Our approach is based on the analysis of the rigid motion equations as expressed in the Geometric Algebra framework. Through this analysis it was apparent that this problem could be cast into a problem of finding a certain 3D plane in a different space that satisfies certain geometric constraints. In order to find this plane in a robust way, the Tensor Voting methodology was used. Unlike other common algorithms for point registration (like the Iterated Closest Points algorithm), ours does not require an initialization, works equally well with small and large transformations, it cannot be trapped in “local minima” and works even in the presence of large amounts of outliers. We also show that this algorithm is easily extended to account for multiple motions and certain non-rigid or elastic transformations.     

A robust and outlier-adaptive method for non-rigid point registration

In this paper, a flexible probabilistic method is introduced for non-rigid point registration, which is motivated by the pioneering research named Coherent Point Drift (CPD). Being different from CPD, our algorithm is robust and outlier-adaptive, which does not need prior information about data such as the appropriate outlier ratio when the point sets are perturbed by outliers. We consider the registration as the alignment of the data (one point set) to a set of Gaussian Mixture Model centroids (the other point set), and initially formulate it as maximizing the likelihood problem, then the problem is solved under Expectation–Maximization (EM) framework. The outlier ratio is also formulated in EM framework and will be updated during the EM iteration. Moreover, we use the volume of the point set region to determine the uniform distribution for modeling the outliers. The resulting registration algorithm exhibits inherent statistical robustness and has an explicit interpretation. The experiments demonstrate that our algorithm outperforms the state-of-the-art method.     

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     

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.     

A Variational Approach to Registration with Local Exponential Coordinates

We identify a novel parameterization for the group of finite rotations (SO₃), consisting of an atlas of exponential maps defined over local tangent planes, for the purpose of computing isometric transformations in registration problems that arise in machine vision applications. Together with a simple representation for translations, the resulting system of coordinates for rigid body motions is proper, free from singularities, is unrestricted in the magnitude of motions that can be represented and poses no difficulties in computer implementations despite their multi‐chart nature. Crucially, such a parameterization helps to admit varied types of data sets, to adopt data‐dependent error functionals for registration, seamlessly bridges correspondence and pose calculations, and inspires systematic variational procedures for computing optimal solutions. As a representative problem, we consider that of registering point clouds onto implicit surfaces without introducing any discretization of the latter. We derive coordinate‐free stationarity conditions, compute consistent linearizations, provide algorithms to compute optimal solutions and examine their performance with detailed examples. The algorithm generalizes naturally to registering curves and surfaces onto implicit manifolds, is directly adaptable to handle the familiar problem of pairwise registration of point clouds and allows for incorporating scale factors during registration.     

含局部空间约束的t分布混合模型的点集配准

基于高斯混合模型（Gaussian mixture model,GMM）的点集非刚性配准算法易受重尾点和异常点影响,提出含局部空间约束的t分布混合模型的点集非刚性配准算法. 通过期望最大化（Expectation maximization,EM）框架将高斯混合模型推广为t分布混合模型;把Dirichlet分布作为浮动点的先验权重,并构造含局部空间约束性质的Dirichlet 分布参数. 使用EM算法获得配准参数的闭合解;计算浮动点的自由度,改变其概率密度分布,避免异常点水平估计误差. 实验表明,本文提出的配准算法具有配准误差小、鲁棒性好、抗干扰能力强等优点.     

基于松弛标号算法的多传感抗差航迹关联

针对多传感抗差航迹关联问题,从理论上分析传感器系统偏差对航迹点集拓扑结构的影响,利用非刚性变换表征两点集之间的拓扑差异.建立抗差航迹关联问题的点模式匹配模型,采用基于松弛标号迭代的非刚性点匹配方法对其进行求解.针对不同测距、测角偏差、目标密度和检测概率水平构造多组典型仿真场景,仿真实验验证了所提出算法的有效性.     

基于全局与局部相似性测度的非刚性点集配准

非刚性点集配准算法中，能否找到正确的对应关系对配准结果起着至关重要的作用，而通常两个点集中的对应点除了距离比较接近之外还具有相似的邻域结构，因此提出基于全局与局部相似性测度的非刚性点集配准算法。首先，使用一致性点漂移（CPD）算法作为配准框架，采用高斯混合模型对点集进行建模。然后，对全局局部混合距离进行改进，形成全局与局部相似性测度准则。最后，采用期望最大化（EM）算法迭代地求解对应关系和变换公式：在迭代初期局部相似性所占比重较大，从而能够尽快地找到正确的对应关系；随着迭代的进展全局相似性比重逐渐增大，从而确保得到较小的配准误差。实验结果表明，与薄板样条鲁棒点匹配（TPS-RPM）算法、高斯混合模型点集配准（GMMREG）算法、基于L₂E估计的鲁棒点匹配算法（RPM-L2E）、基于全局局部混合距离与薄板样条的点集配准算法（GLMDTPS）和CPD算法相比，所提算法的均方根误差（RMSE）分别下降了39.93%、42.45%、32.51%、22.36%和11.76%，说明该算法具有较好的配准效果。     

Group-Wise Point-Set Registration Using a Novel CDF-Based Havrda-Charvát Divergence

This paper presents a novel and robust technique for group-wise registration of point sets with unknown correspondence. We begin by defining a Havrda-Charvát (HC) entropy valid for cumulative distribution functions (CDFs) which we dub the HC Cumulative Residual Entropy (HC-CRE). Based on this definition, we propose a new measure called the CDF-HC divergence which is used to quantify the dis-similarity between CDFs estimated from each point-set in the given population of point sets. This CDF-HC divergence generalizes the CDF Jensen-Shannon (CDF-JS) divergence introduced earlier in the literature, but is much simpler in implementation and computationally more efficient. A closed-form formula for the analytic gradient of the cost function with respect to the non-rigid registration parameters has been derived, which is conducive for efficient quasi-Newton optimization. Our CDF-HC algorithm is especially useful for unbiased point-set atlas construction and can do so without the need to establish correspondences. Mathematical analysis and experimental results indicate that this CDF-HC registration algorithm outperforms the previous group-wise point-set registration algorithms in terms of efficiency, accuracy and robustness.     

基于多个关键点对应性的手部动态重建

提出了一种新的基于单视图深度序列的手部运动跟踪和表面重建方法。在假设任 意一对关键点的对应性在所有手部姿态上均一致基础上,使用一个平滑的手部网格模板来提供 形状和拓扑先验,引入多个能量函数构造输入扫描与模板之间三维关键点到关键点的对应性, 并将其整合到一个可用的非刚性配准管线中,以实现精确的表面拟合。通过最小化手部模板和 输入深度图像序列之间的误差来捕获非刚性的手部运动。采用迭代求解的方法,通过显式的关 键点到关键点之间的对应性,逐步细化手部关节区域的变形,从而达到快速收敛和合理变形的 目的。在含有噪声的手部深度图像序列上的大量实验表明,该方法能够重建精确的手部运动, 并且对较大的变形和遮挡具有鲁棒性。     

基于线特征及迭代最近点算法的地基建筑物点云自动配准方法

为克服迭代最近点(ICP)算法易陷入局部最优的缺陷，提出一种基于线特征及ICP算法的地基建筑物点云自动配准方法。首先，基于法向一致性进行建筑物点云平面分割；接着，采用alpha-shape算法进行点簇轮廓线提取，并拆分和拟合处理得到特征线段；然后，以线对作为配准基元，以线对夹角和距离作为相似性测度进行同名特征匹配，实现建筑物点云的粗配准；最后，以粗配准结果为初值，进一步采用ICP算法完成点云精确配准。利用两组部分重叠的建筑物点云进行配准实验，实验结果表明，采用由粗到精的配准方法能有效改善ICP算法对初值依赖的问题，实现具有部分重叠的建筑物点云的有效配准。     

Correspondence estimation for non-rigid point clouds with automatic part discovery

We propose an approach for estimating non-rigid correspondences between two shapes that can handle articulation and deformation of the surfaces to be matched. It operates on open or closed surfaces represented by point clouds and, therefore, it can be applied on other representations that can be converted into point clouds. Our method is capable of automatically discovering the articulated parts of the surface without requiring knowledge of the topology or the number of rigid parts. Processing begins by estimating potential sparse correspondences between the source and the target surface. These are used to align the largest corresponding parts of the two surfaces. Fragments of the surface that are not consistent with this alignment generate part hypotheses on which the algorithm is applied recursively. We present qualitative and quantitative results on four datasets comprising open and closed surfaces.     

基于区域分割的低覆盖点云配准算法

针对低覆盖点云配准的时间复杂度高、收敛速度缓慢以及对应点匹配易错等问题,提出一种基于区域分割的点云配准算法。首先,利用体积积分不变量计算点云上点的凹凸性,并提取凹凸特征点集;然后,采用基于混合流形谱聚类的分割算法对特征点集进行区域分割,并采用基于奇异值分解（SVD）的迭代最近点（ICP）算法对区域进行配准,从而实现点云的精确配准。实验结果表明,所提算法通过区域分割可以大幅提高点云区域的覆盖率,并且无需迭代即可计算刚体变换的最佳旋转矩阵,其配准精度比已有算法提高了10%以上,配准时间降低了20%以上。因此,所提算法是一种精度高、速度快的低覆盖点云配准算法。     

Efficient RANSAC for Point-Cloud Shape Detection

In this paper we present an automatic algorithm to detect basic shapes in unorganized point clouds. The algorithm decomposes the point cloud into a concise, hybrid structure of inherent shapes and a set of remaining points. Each detected shape serves as a proxy for a set of corresponding points. Our method is based on random sampling and detects planes, spheres, cylinders, cones and tori. For models with surfaces composed of these basic shapes only, for example, CAD models, we automatically obtain a representation solely consisting of shape proxies. We demonstrate that the algorithm is robust even in the presence of many outliers and a high degree of noise. The proposed method scales well with respect to the size of the input point cloud and the number and size of the shapes within the data. Even point sets with several millions of samples are robustly decomposed within less than a minute. Moreover, the algorithm is conceptually simple and easy to implement. Application areas include measurement of physical parameters, scan registration, surface compression, hybrid rendering, shape classification, meshing, simplification, approximation and reverse engineering.     

A topology preserving non-rigid registration algorithm with integration shape knowledge to segment brain subcortical structures from MRI images

A new non-rigid registration method combining image intensity and a priori shape knowledge of the objects in the image is proposed. This method, based on optical flow theory, uses a topology correction strategy to prevent topological changes of the deformed objects and the a priori shape knowledge to keep the object shapes during the deformation process. Advantages of the method over classical intensity based non-rigid registration are that it can improve the registration precision with the a priori knowledge and allows to segment objects at the same time, especially efficient in the case of segmenting adjacent objects having similar intensities. The proposed algorithm is applied to segment brain subcortical structures from 15 real brain MRI images and evaluated by comparing with ground truths. The obtained results show the efficiency and robustness of our method.