基于“滑移”主方向自适应采样的ICP算法优化研究

姜晓通 戴 宁 张长东 崔海华 闫国栋 孙玉春

1.南京航空航天大学，南京，210016 2.北京大学口腔医学院，北京，100081

0 引言

在生物医学、文物保护、工业检测、大型复杂气动物理模型的再设计等领域，都需要获得物体表面的点云数据。目前的光学扫描仪可以在数秒内获得数十万至上百万个点数据。但在点云数据的获取过程中，受测量原理以及被测物体表面形状的影响，物体表面的完整数据往往需要通过多个视角、不同角度的测量完成。对不同视角的测量数据，需要将其统一到同一个全局坐标系下，从而恢复物体原有的表面形态。将各个数据统一到同一个坐标系下完成点云数据配准是获得物体表面完整形态的关键技术之一。

点云配准作为实现上述功能的实现技术之一，一般可分为两个步骤：粗配准和精确配准。粗配准将不同视角获得的点云数据统一到同一坐标系下，常用的方法有转台法［1］、标签法［2］和曲率特征法［3］。粗配准一般很难满足高精度多视角拼合的要求，主要为精确配准提供初始位置。精确配准在粗配准的基础上进一步使点云间的距离误差达到最小，经融合最终得到一个完整的物体表面点云数据。目前国内外最常用的精确配准方法是由Besl等［4］提出的迭代最近点（iterative closest point，ICP）算法。国内外很多学者都对ICP算法进行了扩展研究，其研究重点主要是对ICP算法的精度和速度进行改进。Chen等［5］在ICP的基础上提出利用点的切平面来逼近点云，将点与点之间的距离转换为点到切平面之间的距离的方法，该方法迭代次数少，精度高，但配准速度较慢。Johnson等［6］使用特征提取策略去除没有启发信息的平面点来提高配准速度，但该方法无法达到较高的配准精度。王磊等［7］引入特征点的方法实现点云的配准，但其实质上这些特征点是一种标签点，影响了物体表面点云的完整性。在实际的ICP配准过程中，由于忽略了数据本身的特点，上述ICP配准算法经常不能达到理想的效果。

ICP算法的最终目的在于计算匹配点云间准确的坐标变换矩阵，而计算准确的坐标变换矩阵的关键在于匹配点集的确定。但目前对于ICP处理前的数据点集的重叠区域计算、采样策略确定等前处理研究的文献较少。本文重点研究了ICP算法前处理数据的采样策略，并在此基础上提出一种新的三点插值确定匹配点的方法。首先利用最小欧氏距离确定初始的重叠区域，利用一种基于协方差矩阵的方法对点云重叠区域进行采样，并在迭代的不同阶段采用不同的“滑移”方向的采样组合，有效地避免了迭代陷入局部极值，保证了算法的几何稳定性。在确定匹配点时，利用匹配点的拓扑信息来改善匹配点集的质量，从而实现点云的精确配准。最后通过实验证明了本文算法的有效性。

1 点云采样

1.1 重叠区域分析

重叠区域的选择在点云采样中具有重要地位。重叠区域的准确确定不仅有利于提高采样的准确性，而且有利于提高配准的速度。因为重叠区域是配准的关键区域，只有在重叠区域进行采样，才能确保采样的准确性。在确定重叠区域的同时，需要识别边界区域，去除边界点。边界点的存在会使得在边界区域存在大量的错误对应点，从而造成迭代不收敛的情况。如图1所示，两条短划线段之间部分为实际的重叠区域，两条点划线段之间部分为计算的重叠区域，实线段的两端点是在边界处的匹配点对，大量这样的匹配点对的存在会造成整体的不收敛。在对重叠区域进行分析时，本文利用点到点集的最小欧式距离来进行重叠区域分析，同时利用重叠点的拓扑信息来识别边界点。

图1 未识别边界的配准结果

1.2 基于协方差矩阵重叠区域的采样

在确定匹配点集之前，需对待配准的点云的重叠区域进行采样，采样可以在两片点云或一片点云上进行，Rusinkiewicz等［8］从精度和速度两个方面对两种采样方式进行了比较，当两片点云相距“较远”或重叠区域很小时，从两片点云上都采样对配准速度略有提高，但精度上却没有太大的改进。

采样的方法很多，如均匀采样法［9］、随机采样法［10］和法矢采样法［8］。上述三种采样方法都存在不同程度的采样不准确而影响迭代精度的缺点。Gelfand等［11］提出了一种基于协方差矩阵的方法，此方法有效地保证了采样的有效性，从而提高了ICP算法的几何稳定性。该算法先计算每一个模型的“滑移”主方向。图2所示为各个模型的“滑移”主方向，模型沿着自己的“滑移”主方向平移或旋转，都会让该模型产生一个“复本”，这种在“滑移”主方向上的无约束的平移或旋转会导致迭代的不稳定。为了保证ICP算法的稳定性，需要对该方向上的平移或旋转加以约束，对该方向的运动具有较强约束的点进行采样，从而保证迭代的稳定性。设点集 P ＝ ｛p1，p1，…，pk｝，n1，n1，…，nk为各点所对应的单位法矢，则将各点及对应的单位法矢组合成一个协方差矩阵C如下：

图2 模型的“滑移”主方向

其中，C是一个6×6矩阵，该矩阵的六个向量对应了该模型旋转或平移的一个方向，其中矩阵具有较小特征值的特征向量对应了该模型的“滑移”主方向。设C的六个特征向量分别为x1，x2，…，x6；v1，v2，…，vk为各配准点对应的一个1×6的向量。对每一个向量，｜xivk｜与点vk对向量xi所对应的方向上的旋转或平移的稳定性贡献的大小成正比。因此，在“滑移”方向上，｜xivk｜值较大的点是需要的采样点。图3所示为利用上述方法所得到的不同模型的“滑移”主方向上对旋转或平移的稳定性贡献较大的采样点。

1.3 采取不同的采样策略

改进前后的配准结果对比如图4所示。在实际配准中，若全都采用“滑移”方向上对迭代稳定性贡献较大的采样点，则会存在局部配准不精确的现象，如图4b所示，“滑移”方向的采样点组成的区域配准得较好，但非“滑移”方向采样点组成的区域却存在少量局部区域配准不精确的情况，其原因在于由于采样点的局限性，使得模型在“主方向”上陷入局部极值。为了让点云在重叠区域能够达到最优的全局配准，避免上述情况的出现，在迭代的不同阶段，本文采用不同的“滑移”方向的采样组合。在迭代的过程中，设定一个迭代结束阈值t，以采样点为基础计算配准误差，具体采样策略如下：

图3 不同模型“滑移”主方向对迭代稳定性贡献较大的采样点

图4 改进前与改进后配准结果对比

（1）当配准误差大于λ1t（例如λ1＝1.5）时，采用“滑移”主方向（特征值较小的特征向量对应的方向）上对稳定性贡献较大的点进行配准。由于“滑移”主方向上对配准稳定性贡献较大的点能够有效地限制迭代过程中的“滑移”，这样在配准初期既可以将两配准模型较快地配准到一个相对理想的位置，加快配准的速度，又能够避免在配准初期因为在特征不明显的区域采样过多的点而导致迭代陷入局部极限。

（2）当配准误差小于等于λ1t时，在策略（1）的基础上增加特征值较小的特征向量所对应的方向上对稳定性贡献较大的点来进行配准，这样既可以保证配准的稳定性，又能够避免迭代在模型的“主方向”上陷入局部极值。

（3）当配准误差小于等于λ2t（1＜λ2＜λ1）时，配准精度已接近要求的精度，此时在重叠区域对模型进行均匀采样，对整个重叠区域的配准误差进行“容差分配”，从而保证点云在重叠区域能够达到最优的全局配准。其配准结果如图4c所示，可以看出，此采样策略能够满足精度要求。

2 基于法矢三点插值法确定匹配点

确定匹配点是ICP算法的核心。目前最常用的方法主要有三种［12］，如图5所示。

图5 三种确定匹配点的方法（p为采样点，q为对应的匹配点）

“点到最近点”的方法虽然计算简便、直观、稳定，但因为在所确定的匹配点集中存在大量的错误对应点，算法迭代缓慢，且极易陷入局部极值。“点到视点投影点”的方法因为省去了搜索对应点步骤，可以极大地提高配准速度，但却无法达到较高的拼接精度。“点到切平面垂足点”的方法在三种方法中精度最高，迭代次数少，且不易陷入局部极值，但速度较慢。应用最为广泛的算法为点到切平面垂足点算法。本文提出一种基于法矢的三点插值的方法确定匹配点，此方法通过寻找三个最近点来插值出一个对应点，能够在很大程度上减少错误对应点的存在，不易陷入局部极值，同时由于在重叠区域分析时已经识别并去除了边界点，从而排除了边界点的影响，在实际配准中能够得到很好的配准精度（图6）。然后在协方差采样的基础上进行随机采样，在保证采样准确的同时减少采样点的数量以及在寻找最近点的过程中利用k－d tree来确保配准的效率。其确定配准点算法的过程如下：

图6 三点插值法确定匹配点

设采样点为p，匹配点为q，np和nq分别为两点的法矢，dmean为点云中点和点之间的平均距离。

（1）确定采样点。确定每个采样点p的三个最近点q1、q2、q3，并计算该采样点到这三个点的距离d1、d2、d3。如｜d2－d1｜＞λdmean或｜d3－d1｜＞λ dmean或｜d3－d2｜＞λdmean，则舍去该采样点，反之留下该采样点。

（2）插值出匹配点。设dsum＝d1＋d2＋d3，d′1＝dsum／d1，d′2＝dsum／d2，d′3＝ dsum／d3，则 有d′sun＝d′1＋d′2＋d′3，λ1＝d′1／d′sun，λ2＝d′2／d′sun，λ3＝d′3／d′sun。插值匹配点q＝λ1q1＋λ2q2＋λ3q3。

（3）判断匹配点对的法矢一致性。nq1、nq2、nq3分别为q1、q2、q3的单位法矢，np、nq1、nq2、nq3的计算可转换为求协方差矩阵的最小特征值对应的特征向量问题，则插值点q的法矢为nq＝λ1nq1＋λ2nq2＋λ3nq3。若｜np·nq｜＜u，例如u＝0.9，则舍弃该匹配点，否则留下该匹配点。

3 求解优化迭代矩阵

匹配点确定后，利用最小二乘法迭代求解最优变换矩阵，通常可采用以下四种方法：单位四元数法、奇异值分解法、正交矩阵法和对偶四元数法。Eggert等［13］从精度和稳定性方面对这四种方法做了比较，指出这四种方法的性能相差很小。本文拟采用奇异值分解法来求解最优矩阵。

本文运用前处理优化后的ICP算法进行精确配准，设两片点云为P、Q，主要步骤如下（伪代码表示）：

4 实例与分析

4.1 实例比较

图7 利用经典ICP，Rapidform2006，Geomagic Studio 12以及本文算法匹配结果

表1 不同算法点云配准精度比较 mm

4.2 结果分析

从实例对比中可以看出，本文所采用的基于协方差矩阵的采样能够避免迭代陷入局部极值的现象，算法具有较高的几何稳定性。在基于协方差矩阵采样的基础上，提出了基于法矢三点插值的方法确定匹配点，能够在很大程度上去除错误的匹配点对，从而达到较高的配准精度。

5 结语

散乱点云精确配准技术是获得被测物体完整模型的一个关键步骤。针对这一问题，本文在已有相关理论的基础上，重点研究ICP算法迭代过程中的采样点策略，同时提出一种新的确定匹配点的方法，以及如何在此基础上提高ICP算法的精度及速度。实例表明本文算法对点云数据的配准具有较好的精度，同时具有较高的可靠性和稳定性，能够避免局部极值现象的出现。本文算法在精度以及稳定性上取得了较好的结果，后续研究的重点将在模型的适应性上对算法进行改进，同时将引入并行计算与智能匹配策略，使之能够适应海量数据模型的配准。

［1］谢则晓，张国成，张国雄.线结构光测量数据的自动拼合方法［J］.中国机械工程，2005，16（9）：775－778.Xie Zexiao，Zhang Chengguo，Zhang Guoxiong.An Automatic Registration Method for the Data Patches Obtained by Structured－light Sensons［J］.China Mechanical Engineering，2005，16（9）：775－778.

［2］罗先波，钟约先，李仁举.三维扫描系统中的数据配准技术［J］.清华大学学报，2004，44（8）：1104－1106.Luo Xianbo，Zhong Yuexian，Li Renju.Data Registration in 3－D Scanning Systems［J］.J.Tsinghua Univ.，2004，44（8）：1104－1106.

［3］朱延婿，周来水，张丽艳.散乱点云数据配准算法［J］.计算机辅助设计与图形学学报，2006，18（4）：475－481.Zhu Yanxu，Zhou Laishui，Zhang Liyan.Registration of Scattered Cloud Data［J］.Journal of Computer－aided Design ＆ Computer Graphics，2006，18（4）：475－481.

［4］Besl P J，McKay N D.A Method for Registration of 3－D Shapes［J］.IEEE Transactions on Pattern A－nalysis and Machine Intelligence，1992，14（2）：239－256.

［5］Chen Y，Medioni G.Object Modeling by Registration of Multiple Range Images［J］.Image and Vision Computing，1992，10（3）：145－155.

［6］Johnson A，Hebert M.Surface Registration by Matching Oriented Points［C］／／Proceedings of International Conference on Recent Advances in 3－Digital Imaging and Modeling.Ottawa，1997：121－128.

［7］王磊，邢渊.反向工程中数据点云的拼合［J］.模具技术，2004（1）：47－49.Wang Lei，Xing Yuan.The Merge of Date Point Could in Reverse Engineering［J］.Die and Mould Technology，2004（1）：47－49.

［8］Rusinkiewiez S.Levoy M.Efficient Variants of the ICP Algorithm［C］／／Proceeding of the 3rd International Conference on 3DDigital Imaging and Modeling.Quebec，2001：145－152.

［9］Masuda T.Generation of Geometric Model by Registration and Integration of Multiple Range Images［C］／／Proceedings of the 3rd International Conference on 3DDigital Imaging and Modeling.Quebec，2001：254－261.

［10］Masuda T，Yokoya N.A Robust Method for RegIstration and Segmentation of Multiple Range ImaGes［J］.Computer Vision and Image Uniderstanding，1995，61（3）：295－307.

［11］Gelfand N，Ikemoto L，Rusinkiewicz S，et al.Geometrically Stable Sampling for the ICP Algorithm［C］.／／Proceedings of the 4th International Conference on 3DDigital Imaging and Modeling.Banff，2003：260－267.

［12］谢则晓，徐尚.三维点云数据拼接中ICP及其改进算法综述［J］.中国海洋大学学报，2010，40（1）：99－103.Xie Zexiao，Xu Shang.A Survey on the ICP Algorithm and Its Variants in Registration of 3DPoint Clouds［J］.Periodical of Ocean University of China，2010，40（1）：99－103.

［13］Eggert D W，Lorusso A，Fisher R B.Estimating 3－D Rigid Body Transformations：a Comparison of Four Major Algorithms［J］.Machine Vision and Applications，1997，9（5／6）：272－290.