迭代最近点算法的改进策略

迭代最近点（Iterative Closest Point, ICP）算法是一种最为常见的点云配准方法，虽然配准精度高，但收敛速度慢，对含噪声、覆盖率较低点云的配准效果不佳。鉴于此，本文提出3种ICP算法的改进方法。针对含噪声的点云，采用概率ICP算法来抑制噪声点对配准结果的影响，提高配准精度；为了提高点云配准速度，采用坐标ICP算法实现点云的快速配准；针对低覆盖率点云，采用盒子ICP算法实现配准，可以大大提高配准精度和速度。通过兔子点云配准实验表明，3种改进的ICP算法在点云配准精度和速度方面都有很大程度的提高，均为有效的点云配准方法。     

改进的基于FPFH特征配准点云的方法

ICP(Iterative Closest Point)算法是点云配准中最常用的算法,而点云的FPFH(Fast Point Feature Histograms)特征可在点云配准中为其提供初始匹配信息。针对该方法的初始匹配中距离测度等问题,提出一种改进的基于FPFH特征配准点云的方法。点云配准时首先计算2个点云的点的FPFH特征之间的巴氏距离,以k-d树检索巴氏距离最小的对应点,然后利用奇异值分解计算初始转换矩阵,进行ICP算法精细匹配,求得最终变换矩阵。实验结果表明,改进的基于FPFH特征配准点云的方法能为ICP算法提供良好的初始变换矩阵,在同等迭代次数下该方法具有更高的精度。     

文物点云模型的优化配准算法*

目的 针对带有噪声的文物点云模型,采用一种由粗到细的方法来实现其断裂面的精确配准。方法 首先采用一种变尺度点云配准算法实现粗配准,即配准测度函数的尺度参数由大到小逐渐变化,可避免算法陷入局部极值,并获得较高精度的初始配准结果。然后采用基于高斯概率模型的改进迭代最近点(iterative closest point, ICP)算法进行细配准,可以有效地抑制噪声对配准结果的影响,实现断裂面的快速精确匹配。结果 采用兵马俑文物碎块的配准结果表明,该优化配准算法能够实现文物断裂面的精确配准,而且在细配准阶段取得了较高的配准精度和收敛速度。结论 因此说,该优化配准算法是一种快速、精确、抗噪性强的文物点云配准方法。     

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 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.      

Efficiently registering scan point clouds of 3D printed parts for shape accuracy assessment and modeling

One popular approach to assess the geometric differences between a part produced by additive manufacturing (AM) and its intended design is the use of a 3D scanner to produce a point cloud. This digital scan is then aligned against the part’s intended design, allowing for quantification of print accuracy. One of the most common methods for achieving this alignment is the Iterative Closest Point (ICP) algorithm. This paper evaluates several potential pitfalls that can be encountered when applying ICP for assessment of dimensional accuracy of AM parts. These challenges are then illustrated using simulated data, allowing for quantification of their impact on the accuracy of deviation measurements. Each of these registration errors was shown to be significant enough to noticeably affect the measured deviations. An efficient and practical method to address several of these errors based on engineering informed assumptions is then presented. Both the proposed method and traditional unconstrained ICP are used to produce alignments of real and simulated measurement data. A real designed experiment was conducted to compare the results obtained by the two registration methods using a linear mixed effects modeling approach. The proposed method is shown to produce alignments that were less sensitive to variation sources, and to generate deviation measurements that will not underestimate the true shape deviations as the unconstrained ICP algorithm commonly does.     

ICP算法在文物三维重建中的应用

三维结构光扫描技术作为一种新型的三维数据获取技术,被广泛应用于文物的三维重建中。目前,这项技术在数据获取方面有很多优势,但是在点云数据配准方面还有一些需要优化的地方,特别是在处理大量点数据,为保证配准结果的精确性,就需要对点云数据的配准算法就行优化。利用手持式三维结构光扫描仪获取文物三维数据,在Artec studio9软件中将原始三维数据以ply格式导出为原始点云数据,然后基于Matlab软件对ICP算法通过编程优化,将原始点云数据再通过优化后的ICP算法进行配准,得到文物三维模型的构建数据。实验分析表明,优化后的ICP配准算法不但能提升配准精确度,而且可以保证配准方向的合理性,使得配准得到更佳的展示效果。     

A two-stage registration algorithm for oil spill aerial image by invariants-based similarity and improved ICP

Image registration is a crucial progress in detecting oil spilled on the sea and is also important for estimating the volume of the oil spill, especially when one image cannot cover the entire polluted region. In this article, a new algorithm is proposed to register geometrically distorted aerial images of oil spill accurately and automatically. There are two stages in this algorithm: coarse registration and fine registration. Invariants-based similarity and relative space distance are applied to coarse matching. Then improved iterative closest point (ICP) algorithm is used for registering images finely, which is the combination of ICP and a method of solving assignment problem to deal with mismatches. The performance of the proposed algorithm is evaluated by registering oil spill ultraviolet (UV) and infrared (IR) images, respectively. Compared with traditional ICP and other algorithms, the efficiency and accuracy of the proposed algorithm are highly improved.     

加入迭代因子的层次化颅骨配准方法

目的 在基于知识的颅面复原中,为了对未知颅骨的面貌进行复原,需要在颅骨库里寻找相似颅骨,将相似颅骨的面皮作为参考。寻找相似颅骨的过程即颅骨配准,配准的精度和效率是两个重要性能指标。本文提出一种基于特征区域和改进ICP（iterative closest point）算法的层次化颅骨配准方法。方法 首先,将颅骨模型去噪、简化并归一化,通过计算体积积分不变量,确定每个点的凹凸性;使用K-means方法,将颅骨上的点聚类为多个或凹或凸的特征区域。然后,通过主成分分析法来计算两个颅骨的相似特征区域,对每一个可能的匹配计算3维变换,将两个颅骨粗略对齐;最后,采用加入迭代因子的方法对ICP算法进行改进,使用改进的ICP算法对颅骨进行精配准。结果 将本文方法用于颅骨模型、兵马俑模型以及公共数据集中的3维模型配准,经典ICP算法的配准时间分别为6.23 s、7.61 s、4.17 s,改进的ICP算法配准时间分别为3.02 s、3.23 s、2.83 s,算法效率提高了约2倍,配准效果也有明显提高。实验中通过对迭代因子的测试,发现不同的数据集需要设定不同的迭代因子。结论 本文所提出的基于区域特征的层次化配准方法提高了颅骨配准的精度和效率,整个过程不需要人工干预,该算法具有一定的普适性,可用于相似3维模型配准。     

Improved Iterative Closest Point(ICP) 3D point cloud registration algorithm based on point cloud filtering and adaptive fireworks for coarse registration

ABSTRACT

Aiming at the problem of long computation time and poor registration accuracy in the current three-dimensional point cloud registration problem, this paper presents a k-dimensional Tree(KD-tree) improved ICP algorithm(KD-tree_ICP) that combines point cloud filtering and adaptive fireworks algorithms for coarse registration. On the basis of the typical KD-tree improved ICP algorithm, the point cloud filtering process and adaptive firework coarse registration process are added. Firstly, the point cloud data acquired by the 3D laser scanner is filtered. And then the adaptive fireworks algorithm is used to perform coarse registration on the filtered point cloud data. Next, the KD-tree_ICP algorithm is used to perform accurate registration on the basis of coarse registration, and the obtained translation and rotation relations are applied to the original point cloud data to obtain the result after registration. Finally, 3D point clouds of physical models of five statues are used for experimental verification, including error analysis, stability analysis and comparison with other algorithms. The experimental results show that the method proposed in this paper has greatly improved the calculation speed and accuracy, and the algorithm is stable and reliable, which can also be applied to the reconstruction of 3D building models, restoration of cultural relics, precision machining and other fields.     

A new method to compare planned and achieved position of an orthopaedic implant

The present study describes an automatic method to evaluate the efficacy of a computer aided orthopaedic surgery system by comparing the position of the joint implant, as derived from post-operative computed tomography (CT) scans, to that planned by the surgeon before the operation. The method relies on two spatial registrations, one to align the post-operative femur with the pre-operative femur, the second to compute the planned versus achieved (PVA) accuracy as the roto-translation that registers the pre-operative implant position with the post-operative position. Two surface registration algorithms (a generic average distance minimisation and the specialised iterative closest point (ICP) method) were comparatively evaluated first on a set of test cases to measure the absolute accuracy and robustness with respect to peculiar situations such as a distant starting point. The average distance method failed the registration of one test case and showed peak errors of 0.97 degrees on the rotations and 3.09 mm on the translations. The ICP method was found much more efficient and was able to register all test cases. The peak error was 0.44 degrees on the rotations and 0.67 mm on the translations. The ICP method was then used to compute the PVA accuracy on six clinical cases treated with a CT-based planning system in combination with conventional surgical procedures. The method successfully processed all cases demonstrating the efficacy of the proposed procedure in the specific application.     

面向地图点集的多尺度层级ICP算法

地图点集具有点数多、结构复杂等特点,通常对其配准耗时严重,难以满足自主驾驶等情况下的实时性要求.利用多尺度层级化思想,提出一种多尺度层级ICP算法MSICP( Multi-scale Iterative Closest Points),提高了配准速度和精度.所提算法先对待配准图像点集进行稀疏化,随后将稀疏点集配准后的转换矩阵作为原稠密点集配准的转换矩阵初始值,最终实现对原始图像点集的ICP快速精确配准.实验结果表明,所提算法的配准速度及精度优于其他ICP算法,具有一定的实用价值.     

基于邻域曲率的低特征辨识度点云配准方法

在对特征辨识度低的点云进行配准的过程中,传统的基于局部特征提取和匹配的方法通常精度不高,而基于全局特征匹配的方法精度和效率也难以保证。针对这一问题,提出一种改进的局部特征配准方法。在初步配准阶段,设计了一种基于法向量投影协方差分析的关键点提取方法,结合快速特征直方图(FPFH)对关键点进行特征描述,定义多重匹配条件对特征点进行筛选,最后将对应点的最近距离之和作为优化目标进行粗匹配;在精配准阶段,采用以点到平面的最小距离作为迭代优化对象的改进迭代最近点(ICP)算法进行精确配准。实验结果表明,在配准特征辨识度低的点云时,相较于其他三种配准方法,该方法能保持高配准精度的同时降低配准时间。     

基于特征提取的点云自动配准优化研究

针对三维点云自动配准精度不高、鲁棒性不强等问题,提出一种基于判断点云邻域法向量夹角的自动配准算法。该算法首先计算点云中每个点的法向量与邻域点集的法向量夹角的余弦值,然后把邻域各点的余弦值作为该点的属性特征向量,进行特征分类提取特征点,根据几何特征的相似性初步搜索匹配点对,并采用欧式距离约束条件剔除匹配错误的点对;运用最小二乘法计算初始配准参数,再通过改进的迭代最近点（Iterative Closest Point,ICP）算法进行精匹配。实验证明,该算法相对于经典的ICP算法无论收敛速度还是匹配精度上都有提升。     

A Tracking Registration Method for Augmented Reality Based on Multi-modal Template Matching and Point Clouds

In order to overcome the defects where the surface of the object lacks sufficient texture features and the algorithm cannot meet the real-time requirements of augmented reality, a markerless augmented reality tracking registration method based on multimodal template matching and point clouds is proposed. The method first adapts the linear parallel multi-modal LineMod template matching method with scale invariance to identify the texture-less target and obtain the reference image as the key frame that is most similar to the current perspective. Then, we can obtain the initial pose of the camera and solve the problem of re-initialization because of tracking registration interruption. A point cloud-based method is used to calculate the precise pose of the camera in real time. In order to solve the problem that the traditional iterative closest point (ICP) algorithm cannot meet the real-time requirements of the system, Kd-tree (k-dimensional tree) is used under the graphics processing unit (GPU) to replace the part of finding the nearest points in the original ICP algorithm to improve the speed of tracking registration. At the same time, the random sample consensus (RANSAC) algorithm is used to remove the error point pairs to improve the accuracy of the algorithm. The results show that the proposed tracking registration method has good real-time performance and robustness.

     

基于改进特征点检测的快速图像配准算法

针对传统特征点配准算法效率过慢、对特征点存在误检的现象,提出了一种基于特征点检测的图像配准算法.对特征点检测方法进行了改进,利用像素点与周围像素点的灰度关系滤除非特征点;对剩余的点使用提出的菱形模版进行精确检测,建立了特征点集合;利用迭代最近点(ICP)算法对特征点集合进行配准.实验结果表明:改进算法在特征点检测准确性和检测时间上明显提高,并且具有良好配准效果.     

基于Kinect的改进移动机器人视觉SLAM

针对传统ICP（iterative closest points,迭代最近点算法）存在易陷入局部最优、匹配误差大等问题,提出了一种新的欧氏距离和角度阈值双重限制方法,并在此基础上构建了基于Kinect的室内移动机器人RGB-D SLAM（simultaneous localization and mapping）系统。首先,使用Kinect获取室内环境的彩色信息和深度信息,通过图像特征提取与匹配,结合相机内参与像素点深度值,建立三维点云对应关系;然后,利用RANSAC（random sample consensus）算法剔除外点,完成点云的初匹配;采用改进的点云配准算法完成点云的精匹配;最后,在关键帧选取中引入权重,结合g2o（general graph optimization）算法对机器人位姿进行优化。实验证明该方法的有效性与可行性,提高了三维点云地图的精度,并估计出了机器人运行轨迹。     

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

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

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

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

基于3D-Harris 与FPFH 改进的3D-NDT 配准算法

针对传统点云配准三维正态分布变换(3D-NDT)、迭代最近点(ICP)算法在未给定初 始配准估计的情况下配准效果不佳、配准时间长、误差较大的缺陷,提出了精准且相对高效的 点云匹配算法。首先,运用3D-Harris 算法识别每一幅点云的关键点,并以此为基本点建立局 部参考框架,计算快速点特征直方图(FPFH)描述子;之后,使用最小中值法(LMeds)中的对应 估计算法排除不准确的点对应关系,得到含有对应三维特征关系的特征点对。计算粗配准所需 的变换矩阵,完成初步匹配。随后,根据3D-NDT 算法将点云数据空间体素化,运用概率分布 函数完成最终的点云进行精确地匹配。使用改进配准将3 组分别从网络下载的较少噪声、大规 模与Kinect V2.0 采集的较多噪声、大规模的2 组重叠度不同的点云数据匹配到同一个空间参考 框架中,并通过精度分析对比经典3D-NDT,ICP 等算法。实验结果证明,该算法在迭代次数 较低时,可使室内场景点云数据完成精度较高的配准且受噪声影响较小,但如何将算法的复杂 度适当降低,缩短配准时间需要更进一步的研究。