Break and Splice: A Statistical Method for Non-Rigid Point Cloud Registration

3D object matching and registration on point clouds are widely used in computer vision. However, most existing point cloud registration methods have limitations in handling non-rigid point sets or topology changes (e.g. connections and separations). As a result, critical characteristics such as large inter-frame motions of the point clouds may not be accurately captured. This paper proposes a statistical algorithm for non-rigid point sets registration, addressing the challenge of handling topology changes without the need to estimate correspondence. The algorithm uses a novel Break and Splice framework to treat the non-rigid registration challenges as a reproduction process and a Dirichlet Process Gaussian Mixture Model (DPGMM) to cluster a pair of point sets. Labels are assigned to the source point set with an iterative classification procedure, and the source is registered to the target with the same labels using the Bayesian Coherent Point Drift (BCPD) method. The results demonstrate that the proposed approach achieves lower registration errors and efficiently registers point sets undergoing topology changes and large inter-frame motions. The proposed approach is evaluated on several data sets using various qualitative and quantitative metrics. The results demonstrate that the Break and Splice framework outperforms state-of-the-art methods, achieving an average error reduction of about 60% and a registration time reduction of about 57.8%.     

基于线性规划和相似变换的点匹配算法

为解决点匹配过程中非刚性形变、位置噪声和出格点等因素导致点匹配不理想的问题,提出一种基于线性规划和相似变换的特征点匹配算法。点匹配被建模成一个能量函数最小化问题。在该函数中,形状上下文特征用于降低点对应关系的歧义性,相似变换用于保持空间映射的连续性,连续松弛问题归结为一个线性规划。仿真结果证实了该算法的有效性。     

基于图匹配的旋转不变弹性点匹配算法

针对旋转不变的弹性点匹配问题,提出一种基于图匹配的算法。对两点集分别构造边集合,然后定向的形状上下文距离和边长度的差别被用于度量两点集的边之间的相似性。基于边的相似性,点对应关系通过求解一个图匹配问题而恢复。实验结果表明该算法可以获得很好的配准结果并且鲁棒、高效。     

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

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

基于确定性退火技术的鲁棒性的点匹配算法

点匹配问题一直是计算机视觉和模式识别领域的一项重要的基础性工作，该文提出了一种基于确定性退火技术的准确，快速和鲁棒性的点匹配方法，该方法首先确定在一一对应双向约束的点匹配问题的自由能函数，通过最小化该能量函数可以同时得到点集之间的匹配矩阵和映射参数，由于将匹配矩阵的估计嵌入到确定性退火算法的框架下，利用退火温度来控制匹配矩阵的模糊度，不仅增强了算法的鲁棒性，而且减小了陷入局部极小的可能性，另外，在该算法中通过引入松驰变量，可以鲁棒性地处理出格点（outliers)，实验结果验证了该算法的有效性和鲁棒性。     

Articulated motion reconstruction from feature points

A fundamental task of reconstructing non-rigid articulated motion from sequences of unstructured feature points is to solve the problem of feature correspondence and motion estimation. This problem is challenging in high-dimensional configuration spaces. In this paper, we propose a general model-based dynamic point matching algorithm to reconstruct freeform non-rigid articulated movements from data presented solely by sparse feature points. The algorithm integrates key-frame-based self-initialising hierarchial segmental matching with inter-frame tracking to achieve computation effectiveness and robustness in the presence of data noise. A dynamic scheme of motion verification, dynamic key-frame-shift identification and backward parent-segment correction, incorporating temporal coherency embedded in inter-frames, is employed to enhance the segment-based spatial matching. Such a spatial–temporal approach ultimately reduces the ambiguity of identification inherent in a single frame. Performance evaluation is provided by a series of empirical analyses using synthetic data. Testing on motion capture data for a common articulated motion, namely human motion, gave feature-point identification and matching without the need for manual intervention, in buffered real-time. These results demonstrate the proposed algorithm to be a candidate for feature-based real-time reconstruction tasks involving self-resuming tracking for articulated motion.     

A semi-direct approach to structure from motion

The problem of structure from motion is often decomposed into two steps: feature correspondence and three-dimensional reconstruction. This separation often causes gross errors when establishing correspondence fails. Therefore, we advocate the necessity to integrate visual information not only in time (i.e. across different views), but also in space, by matching regions – rather than points – using explicit photometric deformation models. We present an algorithm that integrates image-feature tracking and three-dimensional motion estimation into a closed loop, while detecting and rejecting outlier regions that do not fit the model. Due to occlusions and the causal nature of our algorithm, a drift in the estimates accumulates over time. We describe a method to perform global registration of local estimates of motion and structure by matching the appearance of feature regions stored over long time periods. We use image intensities to construct a score function that takes into account changes in brightness and contrast. Our algorithm is recursive and suitable for real-time implementation.     

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.     

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

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

基于模糊形状上下文与局部向量相似性约束的配准算法

非刚性点集配准研究是模式识别领域的一项重要基础研究.本文在当前流行的非刚性点集配准算法的基础上提出了两个主要贡献:1)模糊形状上下文(Fuzzy shape context, FSC)特征;2)基于局部向量特征的局部空间向量相似性约束项.本文首先进行基于特征互补的对应关系评估,在这一步骤中定义了模糊形状上下文特征,然后基于模糊形状上下文特征差异和全局特征差异设计了特征互补的高斯混合模型.其次,进行基于约束互补的空间变化更新.在这一步骤中,定义了局部向量特征,建立了局部空间向量相似性约束项.本文算法通过使用特征互补的高斯混合模型进行对应关系评估,并将配准问题转化为可以用期望最大化(Expectation maximization, EM)算法解决的参数优化问题,通过创建包含局部空间向量相似性约束项的能量方程优化了空间变换更新.本文首先测试了模糊形状上下文特征的检索率,然后采用公开数据集测试了算法在点集配准与图像配准的性能.在与当前流行的十种算法的对比实验中,本文算法均给出了精确的配准结果,并在大部分实验中精度超过了当前流行算法.     

Enhanced pose normalization and matching of non-rigid objects based on support vector machine modelling

The estimation of 3D surface correspondence constitutes a fundamental problem in shape matching and analysis applications. In the presence of non-rigid shape deformations, the ambiguity of surface correspondence increases together with the complexity of registration algorithms.     

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.     

Mesh deformation-based multi-tissue mesh generation for brain images

Multi-tissue meshing is necessary for the realistic building of a biomechanical model of the brain, which has been widely used in brain surgery simulation, brain shift, and non-rigid registration. A two step multi-tissue mesher is developed. First, a coarse multi-tissue mesh is generated by redistributing labels of a body-centered cubic (BCC) mesh. Second, all the surfaces of the submeshes are deformed to their corresponding tissue boundaries. To deform the mesh, two strategies are developed. One is based on a point-based registration (PBR) and the other is based on a robust point matching (RPM). The PBR method explicitly calculates the correspondence, which takes both smoothing and quality into account, then resolves the displacement vector by minimizing an energy function. Unlike PBR method, RPM does not require the correspondence between the source points and the target points to be known in advance. To simultaneously resolve the displacement vector and the correspondence, the Expectation and Maximization optimization is employed to alternately estimate the correspondence and the displacement vector. To effectively cope with outliers, least trimmed square, a robust regression technique, is employed to correct the regression bias induced by outliers. Both methods are effective in deforming the multi-tissue mesh. However, the PBR method favors quality and smoothing, and the RPM method favors fidelity. The resulting mesh is characterized by its flexible control of four mesh properties: (1) tissue-dependent resolution, (2) fidelity to tissue boundaries, (3) smoothness of mesh surfaces, and (4) element quality. Each mesh property can be controlled on a tissue level. Our experiments conducted on synthetic data, clinic MRI, visible human data, and brain atlas effectively demonstrate these features of this multi-tissue mesher.     

Robust track-to-track association in the presence of sensor biases and missed detections

The paper addresses the problem of robust track-to-track association in the presence of sensor biases and missed detections. Under the condition of large range biases with sensors, it is validated that the structural difference between two sets of local tracks from different sensors can be described by a non-rigid transformation. After that, we turn the robust track-to-track association problem into the non-rigid point matching problem in the framework of TPS-RPM (Thin Plate Spline-Robust Point Matching). Further, to improve the performance of the track-to-track association, the structural feature is introduced for each local track, and the structural similarity is incorporated by regularizing the energy function of the TPS-RPM algorithm. Simulation results demonstrate the effectiveness of the proposed approaches compared with competing algorithms.     

融合SIFT特征的熵图估计医学图像非刚性配准

配准准确性是医学图像配准算法的一项重要指标,像素灰度是目前图像配准中广泛使用的特征,但是灰度特征来源单一,而且忽略空间信息,在一些情况下容易产生误配。针对这个问题,本文提出一种融合SIFT特征的熵图估计医学图像非刚性配准算法。该算法首先使用基于互信息的刚性配准算法对两幅待配准图像进行粗配;然后,在采样点上提取像素灰度和SIFT高维特征,并在此基础上构造k-最邻近图(kNNG);最后,使用k-最邻近图来估计α互信息(αMI)。实验结果表明:和传统的基于互信息和像素灰度的刚性配准算法,基于熵图估计和单一像素灰度特征的非刚性配准算法相比,本文提出的算法具有更高的配准准确性。     

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.     

Hough Pyramid Matching: Speeded-Up Geometry Re-ranking for Large Scale Image Retrieval

Exploiting local feature shape has made geometry indexing possible, but at a high cost of index space, while a sequential spatial verification and re-ranking stage is still indispensable for large scale image retrieval. In this work we investigate an accelerated approach for the latter problem. We develop a simple spatial matching model inspired by Hough voting in the transformation space, where votes arise from single feature correspondences. Using a histogram pyramid, we effectively compute pair-wise affinities of correspondences without ever enumerating all pairs. Our Hough pyramid matching algorithm is linear in the number of correspondences and allows for multiple matching surfaces or non-rigid objects under one-to-one mapping. We achieve re-ranking one order of magnitude more images at the same query time with superior performance compared to state of the art methods, while requiring the same index space. We show that soft assignment is compatible with this matching scheme, preserving one-to-one mapping and further increasing performance.     

Efficient constrained local model fitting for non-rigid face alignment

Active appearance models (AAMs) have demonstrated great utility when being employed for non-rigid face alignment/tracking. The “simultaneous” algorithm for fitting an AAM achieves good non-rigid face registration performance, but has poor real time performance (2–3 fps). The “project-out” algorithm for fitting an AAM achieves faster than real time performance (>200 fps) but suffers from poor generic alignment performance. In this paper we introduce an extension to a discriminative method for non-rigid face registration/tracking referred to as a constrained local model (CLM). Our proposed method is able to achieve superior performance to the “simultaneous” AAM algorithm along with real time fitting speeds (35 fps). We improve upon the canonical CLM formulation, to gain this performance, in a number of ways by employing: (i) linear SVMs as patch-experts, (ii) a simplified optimization criteria, and (iii) a composite rather than additive warp update step. Most notably, our simplified optimization criteria for fitting the CLM divides the problem of finding a single complex registration/warp displacement into that of finding N simple warp displacements. From these N simple warp displacements, a single complex warp displacement is estimated using a weighted least-squares constraint. Another major advantage of this simplified optimization lends from its ability to be parallelized, a step which we also theoretically explore in this paper. We refer to our approach for fitting the CLM as the “exhaustive local search” (ELS) algorithm. Experiments were conducted on the CMU MultiPIE database.     

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.