在医学图像分析中使用ICP算法进行点云配准

作者：天啦噜

来源：公众号@3D视觉工坊

论文标题：3D Registration of the Point Cloud Data Using ICP Algorithm in Medical Image Analysis

论文地址：在公众号「3D视觉工坊」，后台回复「点云配准」，即可直接下载。

1.摘要

在本文中，我们结合了ICP算法（一种基于3D尺度不变特征变换的方法），对3D自由形式闭合的曲面（人类头骨的3D模型）进行配准。不同于点和表面的配准，我们提出的基于ICP算法的方法可以更好地捕获数据的整体性质，例如骨骼厚度。文中提出的ICP算法主要分为3个步骤：3D特征提取、欧氏距离的整体一致性比对以及ICP增强。整个系统的输入是生物医学数据（CT，MRI）。我们提出的方法首先进行图像分割，然后对人类的头骨进行三维重建。此外，点云的3D 模型也被创建。最后，3D模型点云之间的差异也是可视化的。我们对比了3中不同的算法，包括它们的精度以及鲁棒性。和传统医学图像领域中的重建和配准算法相比，文中提出的方法更快、精度更高。我们将算法应用于研究颅骨畸形，骷髅模型的实验证明了这种方法的有效性和鲁棒性。

2.背景知识

配准是解决计算机视觉以及计算机图形学中各种问题的关键。总体目标是找到两个对象之间或者同一对象的几个实例之间的最佳对齐方式，以便把形状数据引入到同一参考系统下。为了解决3D配准问题（位姿估计，对齐和运动估）计），我们决定使用一种著名的方法来配准2个点集（在2D或3D中），是由Bssl和Mskay提出的迭代最近邻算法（ICP）。它一直以来都被用于计算机视觉的诸多实际应用中，比如3D扫描，3D映射以及3D定位中。因为其概念上的简单性及其在实践中表现的优越性 ，ICP是最受欢迎的配准算法之一，

3.本文的工作

3.1 3D特征检测

SIFT算法对于局部失真和特征检测中的错误很鲁棒，被认为是当前可用的最有效的描述子。对于每个识别到的特征，都会创建局部标记。SIFT 3D描述符的特点是以检出的特征点为中心选16x16x16的区域作为local patch，这个区域又可以均分为4x4x4个子区域，每个子区域中各个像素的梯度都可以分到8个bin里面，这样就得到了4x4x4x8=512维的特征向量。3D SIFT结构的示例如图1所示。

图1.3D SIFT描述子的构造

3D SIFT描述子覆盖了16x16x16的体素区域（该区域分为4×4×4个子区域）。

3.2 多模型配准

多模型配准的目标是对齐在多种视野中的同一个目标，该目标可能来源于不同类型的图像采集系统。在我们的实验中，采用3D SIFT描述子的迭代最近邻算法ICP将被用来配准输入的医学图像数据。

1）ICP配准

ICP是一种3D几何模型对齐的方法，被广泛用于配准3D扫描的输出。本文的基本思路是通过重定义以下步骤改善这种方法和最小化误差：

• 减少每个点云上的点数（增加处理速度）；
• 确定对应点对（计算最近的点）
• 最小化点对之间的距离；
• 计算点集之间的均方差；

图2.ICP算法配准模型的框图结构

首先，ICP算法是基于寻找点集之间的最近点对；其次，创建一个优化的刚体变换来对齐两组数据；最后，将变换应用于实际场景的数据点中。重复该过程，直到收敛。

ICP输入：两个n维的点集

• 模型设置：
• 数据设置：

ICP输出：

• 将D映射到M的旋转矩阵R和平移矩阵t
• 当成一个优化问题解决=> 最小化映射矩阵E中的误差

在ICP处理过程中，搜索半径会影响到计算时间，每次迭代都会使用特定的搜索半径。最佳搜索半径取决于点云密度和初始位置估计。最近邻比对是根据欧式距离定义的：

尽管ICP已被成功应用于许多配准问题，但是还有很多难题亟待解决。特别是ICP在以下假设满足的情况下运行得很好：

• 两个视图必须彼此都很接近，如果不是的话，ICP算法可能会陷入局部最小值；
• 两个视图必须完全重叠，或者显示的D数据能作为模型视图M的子集。

ICP计算的速度和精度非常依赖于相关的处理过程，当ICP算法用来配准2个点云文件，Delaunay三角剖分算法用来加速点的搜索（速度以及改善配准效率），四个点构成一个点集。

2） ICP 配准k-D树

k-D树（k维树）是每个节点都为k维点的二叉树，所有非叶子节点可以视作用一个超平面把空间分割成两个半空间。在两个半空间中搜索到的点是两个节点子单元，生成的k-D树能被用于有效地搜索P点的最近邻域。

• 首先，通过从树的根部以对数时间开始递归进行初始估计（选择一个围绕P所在的半空间的子树直到到达叶子的节点）；
• 然后，递归过程中使用前一阶段的估计值（包含一个比第一次估计低的距离为P的点）。

最近点的搜索算法是迭代的，点和分割平面是相对的，这决定了搜索路径的机制。

4. 实验结果

在这部分，我们将评估所提出算法的性能。文中提出的配准算法是基于迭代最近邻（ICP）和3D SIFT算法，所有的测试方法均通过MATLAB编程语言验证。ICP算法的输入是原始点云和目标点云，具体如图3所示。

图3. 基于ICP的配准算法

首先，得到固定点云和移动点云。然后，做点云配准。这些处理流程都可以在图4中点云配准的工作流中看到。第一步是清除两幅点云中的异常值和噪声，下一步是做下采样，这是关键一步。因为配准是否成功依赖于配准的点云中点的个数。我们用pcddownsample函数执行下采样，这个函数用了三种不同的下采样方法。第一种，随机标记，随机划分点云而不需要替换点。使用这种方法的时候，只有输入百分比和期望点的输出个数需要设置。第二种方法称为“gridAverage”，它使用标有“ gridStep”的类似于网格滤波的方式做下采样，我们使用这种方法来减少点云中的点。另外通过实验，我们确定了网格滤波的理想步长是5。

图4.模型配准的流程

完成以上这些过程后，就可以用ICP算法做刚体变换，通过循环的方式迭代执行以下几步：

• 匹配移动和固定点云
• 通过过滤异常值来消除不正确的匹配
• 恢复平移和旋转（最小化误差）。

实验对比如下：

5.总结

本文提出了（ICP+SIFT）算法进行高精度的配准，只处理迭代转换计算。在医学图像配准和重建领域，通过对比三种不同算法的精度和鲁棒性，ICP，ICP+k-d 树，以及文中所提的算法，本问题提出的算法是快速且精度更高的。

参考文献:

[1] P. J. Besl and N.D. Mckay, “A method for registration of 3-D shapes,” IEEE Transactions on Pattern Analysis and Machine Intelligence[online]. 1992, 14(2), 239-256. DOI: 10.1109/34.121791. ISSN 0162-8828.

[2] Y. Chen and G. Medioni, “Object modelling by registration of multiple range images,” Image and vision computing, 1992, 10.3: 145-155.

[3] S. Rusinkiewicz and M. Levoy, “Efficient variants of the ICP algorithm,” In: 3-D Digital Imaging and Modeling, 2001. Proceedings.Third International Conference on. IEEE, 2001. p. 145-152.

[4] D. Chetverikov, D. Stepanov and P. Krsek, “Robust Euclidean alignment of 3D point sets: the trimmed iterative closest point algorithm,” Image and Vision Computing, 2005, 23.3: 299-309.

[5] P. Markelj, “A review of 3D/2D registration methods for image-guided interventions,” Medical image analysis, 2012, 16.3: 642-661.

[6] J. Santamaría, O. Cordón and S. Damas, “A comparative study of stateof-the-art evolutionary image registration methods for 3D modeling,”Computer Vision and Image Understanding, 2011, 115.9: 1340-1354.

[7] J. Yang, H. Li and Y. Jia, “Go-ICP: Solving 3d registration efficiently and globally optimally,” In: Proceedings of the IEEE International Conference on Computer Vision. 2013. p. 1457-1464.

[8] Y. Sahillioglu and L. Kavan, “Skuller: A volumetric shape registration algorithm for modeling skull deformities,” Medical image analysis,2015, 23.1: 15-27.

[9] P. Scovanner, S. Ali, and M. Shah, “A 3-dimensional sift descriptor and its application to action recognition,” In Proceedings of the 15th International Conference on Multimedia (ACM ’07), pp. 357–360, New York, NY, USA, September 2007.

[10] B. Lee and D.D. Lee, “Learning anisotropic ICP (LA-ICP) for robust and efficient 3D registration,” In: Robotics and Automation (ICRA),2016 IEEE International Conference on. IEEE, 2016, p. 5040-5045.

[11] A. Nuchter, K. Lingemann and J. Hertzberg, “Cached k-d tree search for ICP algorithms,” Sixth International Conference

本文仅做学术分享，如有侵权，请联系删文。

下载1

在「3D视觉工坊」公众号后台回复：3D视觉，即可下载 3D视觉相关资料干货，涉及相机标定、三维重建、立体视觉、SLAM、深度学习、点云后处理、多视图几何等方向。

下载2

在「3D视觉工坊」公众号后台回复：3D视觉github资源汇总，即可下载包括结构光、标定源码、缺陷检测源码、深度估计与深度补全源码、点云处理相关源码、立体匹配源码、单目、双目3D检测、基于点云的3D检测、6D姿态估计汇总等。

下载3

在「3D视觉工坊」公众号后台回复：相机标定，即可下载独家相机标定学习课件与视频网址；后台回复：立体匹配，即可下载独家立体匹配学习课件与视频网址。