严燚坤，屈建勤，王本淇

（汕头大学工学院，广东 汕头 515063）

0 引言

随着工业产品的设计水平日益提升，不同的三维曲面和复杂型面[1]在工业零件的设计中的应用越来越广泛.这其中的关键技术是测量数据与CAD模型之间的配准[2-3].在将CAD模型的配准技术运用到工业生产过程中，有几个亟待解决的问题.

我们知道，当我们采集目标的三维坐标数据的时候，由于点集的不完整，旋转错位，平移错位等因素的干扰，可能在原始的数据中存在大量的噪声数据和离群点，最后导致配准的准确率大幅度下降，无法进行正常的配准.另外，当噪声数据占比越大，配准需要花费的时间也会越多，而在实时处理系统中，我们往往需要及时地对研究的对象进行配准工作，这时候对算法效率要求很高.因此，如果能够在一定程度上降低算法的复杂度，就能让其能更好的服务于实时的配准系统中.

目前，大部分研究都是基于ICP算法[4].例如，Zhang[5]提出了采用k-d树加速的ICP算法；Sharp等[6]人则提出了一种基于欧几里得不变特征的ICP算法；Truk等[7]人则利用三角网格作为基本的运算单元进行配准的工作.在国内，石爱军和白瑞林等[8]人将遗传算法和ICP算法相结合进行研究；刘一凡和蔡振江[9]提出了ICP和SFM结合的算法.

上述各种算法都是在ICP算法的基础上，通过不同的匹配对象的特征有针对性的提出改进措施，并且取得了不错的效果.但是ICP类算法对点集的初始位置要求比较高，容易陷入局部最优解，并且当点集中存在大量噪声的情况下配准效果变得很差.

而由于张量投票算法是基于全局的数据，并采用投票的方式进行计算的，因而能很好地避免噪声对算法输出的影响.作为一种鲁棒性很强的算法，即使在存在大量噪声数据的情况下，张量投票算法依然能保持很高的配准准确率.但是，原始的张量投票算法计算复杂度虽然相比ICP等迭代算法下降了很多，但是当噪声比例很大时，其运行效率也会降低.在实时的处理系统中，由于对及时性要求非常苛刻，对于效率的每一点提升都有很大的价值.

基于此，本文改进了原始的张量投票算法[10]，通过简化token的表示，简化衰退性函数的模型，同时对计票的计算方式进行细化和补充，使得算法的运行效率有了很大的提高.

1 原始张量投票算法

张量投票算法由Gerard Medioni领导的研究组所提出，是一种符合人类视觉特征性的空间结构特征的提取算法，该算法运用到了张量分析[11]，几何学，矩阵论这些方面的知识和Gestalt定律[12].

张量投票算法的主要思想有两点：一是张量[13-14]的数字化表示，张量的特征值大小构成了特征的分层表示；二是特征的计算，通过收集附近邻域以及方向信息来确定.张量投票算法的精髓在于用张量叠加的方式来加强待提取的特征，得到显著性特征程度图，然后用张量的分解来解释投票产生的结果.

张量投票算法中主要是对矩阵的特征向量和特征值进行分解.该算法对噪声数据和离群点具有较好的鲁棒性，同时能有效避免算法陷入局部最优.在2007年，Leo Reyes和Gerard Medioni等人将张量投票算法应用到三维点集的配准过程中[15]，并且取得了很好的实验效果.

2 配准的数学描述

2.1 配准的实质

配准的本质其实就是将不同坐标或者不同系统的同一对象的几何特征，通过刚性变换让两个对象在方向和位置上完全重合的过程.一般在我们采集数据进行完预处理后可以得到其测量坐标系，而CAD模型处于设计坐标系，这两个坐标系相互独立.为了完成配准工作，我们需要将测量坐标下的数据经过几何转换到设计坐标系下，让测量数据和CAD模型尽可能多的重合.所以配准的本质就是求测量数据到CAD模型所经历的平移和旋转变换的参数.

2.2 刚性变化的过程

在欧式空间中，如果一个物体被看作是理想情况下的刚体，那么不管是物体的方向或位置发生变化还是我们在不同的坐标系下观察同一个物体，物体的大小和形状都会保持不变.所以，在欧氏变换中，只要对象的形状和大小不发生改变就叫刚性变换.刚性变化包含两个方面，一是平移变换，二是旋转变换，我们研究的CAD模型配准问题中的对象都是刚体.设在坐标系 O（x，y，z）下的点 P 的坐标是（x，y，z），在坐标系 O（x′，y′，z′）下点Q的坐标为（x′，y′，z′）.则从点P到Q的刚性变换如下式所示：

上式中，T＝（tx，ty，tz）T表示刚性变换的平移矩阵，R表示刚性变换的旋转矩阵，即

由式（2）可知，旋转矩阵包含9个参数.一般情况下，R是由绕X，Y，Z三个轴的基本的旋转方向复合而成，设绕三个轴旋转的角度分别为w，φ和k.用欧拉角表示法如图2所示：

我们将绕X轴旋转的矩阵RX（w）定义为：

我们将绕Y轴旋转的矩阵RY（φ）定义为：

我们将绕Z轴旋转的矩阵RZ（k）定义为：

其中R＝RX（w）RY（φ）RZ（k）.

对于3D点集的配准问题，其本质就是求解刚体运动方程的过程

2.3 几何约束

在配准相关的研究中，很多都是基于纯几何或者纯代数的方式去描述配准过程中的约束关系，其过程复杂而且繁琐.为了表达上的简洁，本文使用几何代数的方式来描述配准过程中的约束关系.在文献[15]中，Medioni利用几何代数对配准问题的描述进行了简化，并最终将约束方程的简化成了式（6）.

我们假设A＝[0 0 1]T，则问题变成了二维的形式.我们只需要探讨x和y之间的关系，通过上面的方程可以得到如图2.

图2 点对之间的对应关系

图2中的（a）和（d）表示两个属于相同刚性变换和几何图形的对应点.（b）和（e）表示两个属于不同变换（旋转角度）和几何平面的对应点.（c）和（f）表示多个对应点的例子.

由图可知，方程（6）的约束可以用来拒绝错误的匹配.通过这个过程，我们可以将寻找两组三维点对刚性变换方程的过程转换成在接点空间中寻找满足三组几何约束的三维平面的问题.

3 张量投票算法的改进

在本文的研究过程中发现，文献[15]中使用张量投票算法进行三维点集配准的过程中有两个存在优化和细化的地方.一是token如何编码成张量的形式，二是在计票方式上细化和补充.

3.1 token的张量的表示

在文献[15]中，Medioni将token全部编码成球张量，然后参与投票，而本文改进了原文中的编码方式.在本文中，我们通过将token和其转置矩阵相乘编码成一个张量.

同时，原文中生成新的张量的方式是通过张量积分的方式进行，笔者将其进行了简化，通过将token领域内的张量和衰退性函数DF（s，k，σ）积的累加和得到最后新的张量.这种方式有效的减小了计算的复杂度，在一定程度上提升了算法的效率.

3.2 计票的方式

在文献[15]中，Medioni采用原始张量投票的计票方式，即选择被投票点特定范围内的token所表示的张量对其进行投票.笔者认为这种方式可能存在一些问题，比如当领域内的token数量较少时可能会导致投票结果和实际情况存在偏差，所以本文在此基础上进行细化和改进.

本文所采用的计票方式分为下面的步骤进行：

1）设定参与投票的点不得少于m个，如果被投票的token领域内的token数量n＞m时，投票步骤按张量投票的原始算法进行；

2）当统计得到的n＜m时，我们采用另一种计票方式.即筛选出距离被投票token最近的m个点参与投票.

通过上面的计票方式可以避免部分token领域中的投票稀疏的问题.

3.3 模型评价标准

在本文中，我们使用随机生成的点集数据做测试数据，利用这些数据来比较本文改进的张量投票算法和文献[15]中的配准算法的结果.为了测试结果尽可能客观和公平，本文共设计了多组对比实验用来观察旋转角度的大小、平移的距离、数据规模和离群点比例等因素对配准效率和准确率的影响.最终，通过统计不同情况下的配准结果来做对比.

4 实验与结果分析

4.1 实验条件

本文算法采用Matlab作为编程工具，在一台个人笔记本电脑上进行实验.笔记本电脑的配置和环境为：CPU为Intel Core i7-8750H（主频为2.2 GHZ，六核十二线程），内存为8G，显卡为NVIDIA GTX1060（显存为6G），硬盘容量为128G的SSD，操作系统为Windows 10.

4.2 实验数据

在本节，我们将设计两组实验来比较和验证算法的配准效果.两组实验分别对比的是F-ICP算法，原始张量投票算法和改进后的张量投票算法，比较的指标是配准准确率和配准时间.

在第一组实验中，我们利用合成数据进行配准的实验.我们通过Matlab的rand函数在空间1×1×1内生成随机的40 000个数据.为了测试结果尽可能客观和公平，实验进行了多次，并取实验的平均值作为结果.最终，通过统计不同情况下的平均配准结果作对比.

在第二组实验中，我们对斯坦福兔子进行配准实验，对算法在实际应用中的效果进行验证.

4.3 实验结果

除了测试改进后的张量投票算法，本文还接着利用随机数据对F-ICP算法和原始的张量投票算法作对比，得出了在不同离群点程度的情况下各算法的配准率和配准效率.表1为F-ICP算法的配准结果.

表1 F-ICP算法的配准结果

为了实验结果更具有说服性，第二组测试数据的旋转角度的限制扩展到0°～360°，平移距离也扩大到-10～＋10.表2为本文改进后的算法的配准结果.

表2 本文改进后的张量投票算法的配准结果

表3的实验结果来自文献[15]，其实验环境和约束与表2中的一致，其实验结果为使用原始的张量投票算法进行配准的结果.

表3 原始张量投票算法的配准结果

在第二组实验中，首先我们对著名的斯坦福兔子模型进行配准实验，在配准前，其输入数据为测量点集数据和兔子的模型数据，如图3所示.

其中图3上方是测试点集数据，图下方是兔子的模型数据.使用改进后的张量投票算法进行配准后的效果如图4所示.

图3 测试的兔子数据

图4 斯坦福兔子配准后的效果图

从第一组测试数据可以看出，改进后的张量投票算法相比F-ICP算法而言，在离群点比例逐渐增加的情况下具有很大的优势，即使在旋转角度和平移距离明显大于F-ICP算法的环境下，改进后的张量投票算法的配准准确率仍然大大超过F-ICP算法，同时运行效率也远远高于F-ICP算法，效率的提升在10倍以上.从表格1的实验结果可以得出F-ICP算法对原始点集和目标点集之间的变换幅度很敏感.当离群点的比例超过75%时，配准的准确率下降到了60%，而改进后的算法在离群点占比高达93%的情况下，配准准确率依然保持在75%.从中可以得出结论：相比于ICP类算法，张量投票算法对噪声数据和离群点具有很好的鲁棒性，并且其对初始位置的要求不高，算法的普适性更好.

与原始的张量投票算法相比，两者的配准准确率差别不是很明显，但是实验的结果表明，改进后的张量投票算法稳定性更好.在离群点比例逐步变大的过程中，改进后的算法的配准准确率更加均匀地下降.在离群点的比例达到83%，88%和93%的情况下，本文改进的算法的配准准确率相对于原始的张量投票算法有了小幅的提升.另一方面，对于算法运行的效率而言，改进后的算法比原始算法提升了39.2%～90.8%，说明改进后的算法在复杂度方面更低.

我们知道，在实时的配准系统中，往往对于配准的精确度没有那么高，并且在实际的情况中，噪声数据的比例一般维持在一定的范围内，不会过于夸张.而其对配准效率的要求很高，所以配准效率的提升对于配准的实际应用有很大的价值.而本文通过改进张量投票算法，在保证配准精准度与原始张量投票算法基本持平的情况下，有效的提升了配准的效率.使得改进后的算法能够更好的应用于实时的配准系统中.

5 总结

为了实现CAD模型的配准，本文通过一种基于张量投票的配准算法，并对文献[15]中的部分实验步骤进行了改进，最后通过和原文的实验结果进行比较，取得了一定的效果.并且，本文利用斯坦福兔子作为测试对象，证明了改进后的张量投票算法在实际的配准工作中取得了很好的效果.但是仍然需要更大的样本空间进一步的研究去提升算法效率和准确率.文本可以在一下几个方面继续研究和改进：（1）扩展算法的应用场景，让其能适配非刚性的变换；（2）进一步扩大样本空间，从多个角度出发设计实验，进一步测试算法的稳定性；（3）优化算法的计算复杂度.