基于点云数据的数字化比对检测系统设计与实现
陈芷+吴捷+马小虎
摘 要： 点云数据与CAD模型的坐标匹配和对应关系的建立是数字化比对检测系统的关键技术。利用k?D树空间快速搜索策略改进传统ICP算法实现点云数据与CAD模型坐标精确匹配，采用半边数据结构建立点云数据与CAD模型对应关系，利用点到边和点到点的对应关系解决待测工件的边缘和棱线以及特征明显变化区域的偏差检测问题。在此基础上研制了数字化比对检测系统。试验结果表明该系统运算速度快、精度高，具有很好的应用效果。
关键词： 坐标匹配； 点云数据； 对应关系建立； 对比检测
中图分类号： TN911.23?34； TP391.7 文献标识码： A 文章编号： 1004?373X（2017）12?0162?03
Abstract： The coordinate matching between point cloud data and CAD model and establishment of their corresponding relation are the key technologies of digital contrast detection system. The k?D tree space fast search strategy is used to improve the traditional ICP algorithm to achieve the coordinate accurate match between point cloud data and CAD model. The half edge data structure is adopted to build the corresponding relation between point cloud data and CAD model. The corresponding relation of point?to?edge and point?to?point is employed to solve the deviation detection problem of edge and ridge of UUT， and the region with obvious feature variation. On the above basis， a digital contrast detection system was developed. The test results indicate that the system has fast calculating speed and high precision and good application effect.
Keywords： coordinate matching； point cloud data； corresponding relation establishment； contrast detection
随着制造业的发展，自由曲面等复杂型面已广泛地应用于产品的设计和制造过程中。为了保证具有复杂型面工件的加工质量以及生产效率，需要对其进行快速精确的误差检测。而传统模板检测方法由于自身诸多不足已不能满足实际生产要求[1]。数字化比对检测技术的出现为解决这一难题提供了新的途径[2]。目前在国外，许多著名的汽车制造厂商比如丰田、大众、通用等均已将数字化比对检测技术逐渐应用于实际生产过程中，大大降低了产品开发制造成本，缩短了产品开发制造周期[3]。而在国内，数字化比对检测技术的应用几乎还是空白，数字化比对检测技术尚未成熟，其中主要的关键技术有待进一步的研究。因此，必须要对这些关键技术进行深入研究，讓数字化比对技术能够真正地应用于实际，满足生产要求。
1 坐标匹配
坐标匹配就是要计算得到点云数据与CAD模型之间的坐标变换矩阵，通过矩阵运算，使得点云数据与CAD模型处于同一个坐标空间下[4]。
1.1 ICP算法
ICP（Iterative Closest Points）算法通过搜索点云数据与CAD模型中的最近点点对，并利用这些最近点对间的距离构造目标函数，进行迭代运算最终求出坐标旋转、平移矩阵，使得目标函数值最小[5]。通常原始ICP算法空间搜索的时间复杂度是，其中和表示点云数据和CAD模型顶点集中点的数目。如果点的数量很大，这个过程将非常耗时，因此最近点点对的搜索是ICP算法的瓶颈。本文利用k?D树来进行最近点对的搜索，大大提高了搜索效率。
1.2 k?D树空间搜索策略
k?D树是一个针对K维度空间所设计的二元搜索树，其本质是一个二叉树[6]，其典型应用是求点的k个最近点。k?D树的生成过程就是平面被轴和轴连续递归划分的过程，直到最后分割的区域内只有一个点。这样的分割过程就对应了一个完全二叉树，二叉树的分支节点对应一条分割线，而每个叶子节点就对应一个数据点。利用k?D树进行最近点对搜索的时间复杂度为，远小于传统的遍历算法。因此，运用k?D树空间搜索策略可以在很大程度上提高ICP算法的计算效率。
2 对应关系
通常对于点云数据与CAD模型对应关系的建立主要是寻找各点所对应的CAD模型上的面片，利用点云各点与CAD模型面片之间的距离表示偏差[7]，然而这些方法不能保证在所有区域都能得到正确的计算结果。通过建立半边数据结构表达CAD模型表面三角形面、边、顶点的拓扑关系，增加点到边的对应关系和点到点的对应关系，可以弥补传统方法的不足。
2.1 半边数据结构
半边数据结构是一种以界限为基础的拓扑结构。其基本原理是把三角网格的每条连线分为两个相等且方向相反的半边（边界除外）[8]，如图1所示。图1中有四条边以点为起点，分别为：，，和。索引信息分别储存在点的结构里，通过找到点，就可以遍历其所连接边的邻边、孪边快速得到邻近三角形的所有信息。
2.2 点对面的关系
建立点对面的对应关系是点云数据比对检测的基础。首先对于CAD模型中所有顶点的坐标信息建立k?D树数据结构，快速搜索点云中各点所对应的CAD模型上的最近顶点。然后通过半边结构从该对应点开始遍历与该点相连的所有三角面片，根据判断准则找出符合要求的三角面片。
2.3 点对边的关系
由于在待测工件的边缘和棱线以及特征明显变化的区域附近，点云数据中的点很难在CAD模型上找到满足要求的对应三角面片。如果在这些地方依然采用点对面的对应关系来进行处理显然是行不通的，必须寻找出满足条件的对应边来建立对应关系。其对应边判断准则如图2所示。
首先，计算出点数据中点对于CAD模型中边的投影点坐标；其次，通过计算投影点到边的两个端点的距离之和是否大于该边的长度判断投影点是否在边上，若大于则说明投影点不在边上。根据这个判断条件，图2（a）满足条件，则可以确定该边是点的对应边，而图2（b）则不满足该判断条件，则认为点与该边没有对应关系。
2.4 点对点的关系
如果经过上述两个步骤，点云上的点依然没能够建立点对面或者点对边的对应关系的话，那么将此点与其在CAD模型中的最近点组成点对点的对应关系，以这两个点的距离来表示偏差。这种情况一般会出现在待测工件中的棱角和具有尖锐特征的地方。
3 系统实现
检测系统主要功能包括：点云数据与CAD模型初步坐標匹配、坐标精匹配、点云数据各点偏差计算以及色斑图显示偏差结果等功能模块。图3表明了本文所开发的整个数字化比对检测系统各个功能模块的关系。
4 试验分析
4.1 处理效率
对于改进ICP法的计算效率主要取决于收敛速度，即进行多少次的迭代运算。下面通过某水轮机叶片的点云数据与其CAD模型来对该系统的ICP坐标匹配模块进行分析。利用改进ICP法进行坐标精匹配时，选择最近点对距离的平均值作为目标函数，并设置ICP法的收敛条件为两次迭代运算的目标函数值相差的绝对值小于作为收敛判断条件，经过了9次迭代运算之后最终满足收敛条件，完成匹配，效果如图4所示。
根据测量，最终得到的改进ICP法的计算效率如表1所示。从上述试验检测结果来看，改进ICP算法实现点云数据与CAD模型坐标精匹配计算效率较快，能够满足实际使用需求。
4.2 偏差精度
本系统采用与德国GOM公司开发的TRITOP系统中的点云数据检测模块进行偏差计算结果比较分析来侧面地反映系统的精度。两个点云检测模块对叶片的检测结果如图5所示。可以看到两者的处理结果在大体上是一致的。
然而由于TRITOP软件的检测原理是指用计算点云数据各点对CAD模型面片的最近距离来表示偏差，因此在边缘棱角或者特征显著变化的区域，其计算结果是不准确的，如图6（a）所示，当偏差计算范围是时发现TRITOP系统对于左侧边缘的部分点云数据由于与CAD模型上错误的面片建立了对应关系，导致偏差计算的失效。而本系统由于在边缘等特定区域采取了建立点对边和点对点的对应关系，很好地解决了这些特殊区域偏差的检测问题，取得了很好的效果。如图6（b）所示，在相同的偏差计算范围下，可以看到在TRITOP系统中处理错误的点都得到了正确的偏差计算结果。
5 结 语
本文利用k?D树空间快速搜索策略改进ICP算法，采用半边结构来表达单元三角网格形式CAD模型的点、边、面拓扑结构，以满足在建立点云数据与CAD模型对应关系时要快速遍历CAD模型中所有几何元素的要求，并在此基础上研制了数字化比对检测系统。通过对某水轮机叶片检测，结果表明该系统运行效率快、精度高，具有很好的应用效果。
参考文献
[1] 高中亚，李振平，方海滨，等.二维复杂型面数字化比较技术的应用[J].工具技术，2015，49（5）：60?62.
[2] 陆峰，李宁，赵德宏.复杂曲面三维轮廓精度数字化比对检测与误差分析[J].制造业自动化，2014（18）：46?50.
[3] 陈胜利.快速成形技术及其发展趋势[J].制造业自动化，2009，31（10）：24?26.
[4] MA Hongchao， SUN Jie. Intelligent optimization of seam?line finding for orthophoto mosaicking with LiDAR point clouds [J]. Journal of Zhejiang University： Science C， 2011， 12（5）： 417?429.
[5] LI Jianchuan， YU Jianfeng. A new posture evaluation method of wing based on iterative closest point algorithm [J]. Advanced materials research， 2013， 718/720： 1279?1285.
[6] 魏海涛，杜云艳，任浩玮，等.基于N?KD树的空间点数据分组算法[J].地球信息科学学报，2015（1）：1?7.
[7] 徐伟恒，冯仲科，苏志芳，等.一种基于三维激光点云数据的单木树冠投影面积和树冠体积自动提取算法[J].光谱学与光谱分析，2014（2）：465?471.
[8] 王继东，陈桂林.基于半边数据结构的最短路径算法及其实现[J].计算机工程与应用，2009（8）：118?120.
摘 要： 点云数据与CAD模型的坐标匹配和对应关系的建立是数字化比对检测系统的关键技术。利用k?D树空间快速搜索策略改进传统ICP算法实现点云数据与CAD模型坐标精确匹配，采用半边数据结构建立点云数据与CAD模型对应关系，利用点到边和点到点的对应关系解决待测工件的边缘和棱线以及特征明显变化区域的偏差检测问题。在此基础上研制了数字化比对检测系统。试验结果表明该系统运算速度快、精度高，具有很好的应用效果。
关键词： 坐标匹配； 点云数据； 对应关系建立； 对比检测
中图分类号： TN911.23?34； TP391.7 文献标识码： A 文章编号： 1004?373X（2017）12?0162?03
Abstract： The coordinate matching between point cloud data and CAD model and establishment of their corresponding relation are the key technologies of digital contrast detection system. The k?D tree space fast search strategy is used to improve the traditional ICP algorithm to achieve the coordinate accurate match between point cloud data and CAD model. The half edge data structure is adopted to build the corresponding relation between point cloud data and CAD model. The corresponding relation of point?to?edge and point?to?point is employed to solve the deviation detection problem of edge and ridge of UUT， and the region with obvious feature variation. On the above basis， a digital contrast detection system was developed. The test results indicate that the system has fast calculating speed and high precision and good application effect.
Keywords： coordinate matching； point cloud data； corresponding relation establishment； contrast detection
随着制造业的发展，自由曲面等复杂型面已广泛地应用于产品的设计和制造过程中。为了保证具有复杂型面工件的加工质量以及生产效率，需要对其进行快速精确的误差检测。而传统模板检测方法由于自身诸多不足已不能满足实际生产要求[1]。数字化比对检测技术的出现为解决这一难题提供了新的途径[2]。目前在国外，许多著名的汽车制造厂商比如丰田、大众、通用等均已将数字化比对检测技术逐渐应用于实际生产过程中，大大降低了产品开发制造成本，缩短了产品开发制造周期[3]。而在国内，数字化比对检测技术的应用几乎还是空白，数字化比对检测技术尚未成熟，其中主要的关键技术有待进一步的研究。因此，必须要对这些关键技术进行深入研究，讓数字化比对技术能够真正地应用于实际，满足生产要求。
1 坐标匹配
坐标匹配就是要计算得到点云数据与CAD模型之间的坐标变换矩阵，通过矩阵运算，使得点云数据与CAD模型处于同一个坐标空间下[4]。
1.1 ICP算法
ICP（Iterative Closest Points）算法通过搜索点云数据与CAD模型中的最近点点对，并利用这些最近点对间的距离构造目标函数，进行迭代运算最终求出坐标旋转、平移矩阵，使得目标函数值最小[5]。通常原始ICP算法空间搜索的时间复杂度是，其中和表示点云数据和CAD模型顶点集中点的数目。如果点的数量很大，这个过程将非常耗时，因此最近点点对的搜索是ICP算法的瓶颈。本文利用k?D树来进行最近点对的搜索，大大提高了搜索效率。
1.2 k?D树空间搜索策略
k?D树是一个针对K维度空间所设计的二元搜索树，其本质是一个二叉树[6]，其典型应用是求点的k个最近点。k?D树的生成过程就是平面被轴和轴连续递归划分的过程，直到最后分割的区域内只有一个点。这样的分割过程就对应了一个完全二叉树，二叉树的分支节点对应一条分割线，而每个叶子节点就对应一个数据点。利用k?D树进行最近点对搜索的时间复杂度为，远小于传统的遍历算法。因此，运用k?D树空间搜索策略可以在很大程度上提高ICP算法的计算效率。
2 对应关系
通常对于点云数据与CAD模型对应关系的建立主要是寻找各点所对应的CAD模型上的面片，利用点云各点与CAD模型面片之间的距离表示偏差[7]，然而这些方法不能保证在所有区域都能得到正确的计算结果。通过建立半边数据结构表达CAD模型表面三角形面、边、顶点的拓扑关系，增加点到边的对应关系和点到点的对应关系，可以弥补传统方法的不足。
2.1 半边数据结构
半边数据结构是一种以界限为基础的拓扑结构。其基本原理是把三角网格的每条连线分为两个相等且方向相反的半边（边界除外）[8]，如图1所示。图1中有四条边以点为起点，分别为：，，和。索引信息分别储存在点的结构里，通过找到点，就可以遍历其所连接边的邻边、孪边快速得到邻近三角形的所有信息。
2.2 点对面的关系
建立点对面的对应关系是点云数据比对检测的基础。首先对于CAD模型中所有顶点的坐标信息建立k?D树数据结构，快速搜索点云中各点所对应的CAD模型上的最近顶点。然后通过半边结构从该对应点开始遍历与该点相连的所有三角面片，根据判断准则找出符合要求的三角面片。
2.3 点对边的关系
由于在待测工件的边缘和棱线以及特征明显变化的区域附近，点云数据中的点很难在CAD模型上找到满足要求的对应三角面片。如果在这些地方依然采用点对面的对应关系来进行处理显然是行不通的，必须寻找出满足条件的对应边来建立对应关系。其对应边判断准则如图2所示。
首先，计算出点数据中点对于CAD模型中边的投影点坐标；其次，通过计算投影点到边的两个端点的距离之和是否大于该边的长度判断投影点是否在边上，若大于则说明投影点不在边上。根据这个判断条件，图2（a）满足条件，则可以确定该边是点的对应边，而图2（b）则不满足该判断条件，则认为点与该边没有对应关系。
2.4 点对点的关系
如果经过上述两个步骤，点云上的点依然没能够建立点对面或者点对边的对应关系的话，那么将此点与其在CAD模型中的最近点组成点对点的对应关系，以这两个点的距离来表示偏差。这种情况一般会出现在待测工件中的棱角和具有尖锐特征的地方。
3 系统实现
检测系统主要功能包括：点云数据与CAD模型初步坐標匹配、坐标精匹配、点云数据各点偏差计算以及色斑图显示偏差结果等功能模块。图3表明了本文所开发的整个数字化比对检测系统各个功能模块的关系。
4 试验分析
4.1 处理效率
对于改进ICP法的计算效率主要取决于收敛速度，即进行多少次的迭代运算。下面通过某水轮机叶片的点云数据与其CAD模型来对该系统的ICP坐标匹配模块进行分析。利用改进ICP法进行坐标精匹配时，选择最近点对距离的平均值作为目标函数，并设置ICP法的收敛条件为两次迭代运算的目标函数值相差的绝对值小于作为收敛判断条件，经过了9次迭代运算之后最终满足收敛条件，完成匹配，效果如图4所示。
根据测量，最终得到的改进ICP法的计算效率如表1所示。从上述试验检测结果来看，改进ICP算法实现点云数据与CAD模型坐标精匹配计算效率较快，能够满足实际使用需求。
4.2 偏差精度
本系统采用与德国GOM公司开发的TRITOP系统中的点云数据检测模块进行偏差计算结果比较分析来侧面地反映系统的精度。两个点云检测模块对叶片的检测结果如图5所示。可以看到两者的处理结果在大体上是一致的。
然而由于TRITOP软件的检测原理是指用计算点云数据各点对CAD模型面片的最近距离来表示偏差，因此在边缘棱角或者特征显著变化的区域，其计算结果是不准确的，如图6（a）所示，当偏差计算范围是时发现TRITOP系统对于左侧边缘的部分点云数据由于与CAD模型上错误的面片建立了对应关系，导致偏差计算的失效。而本系统由于在边缘等特定区域采取了建立点对边和点对点的对应关系，很好地解决了这些特殊区域偏差的检测问题，取得了很好的效果。如图6（b）所示，在相同的偏差计算范围下，可以看到在TRITOP系统中处理错误的点都得到了正确的偏差计算结果。
5 结 语
本文利用k?D树空间快速搜索策略改进ICP算法，采用半边结构来表达单元三角网格形式CAD模型的点、边、面拓扑结构，以满足在建立点云数据与CAD模型对应关系时要快速遍历CAD模型中所有几何元素的要求，并在此基础上研制了数字化比对检测系统。通过对某水轮机叶片检测，结果表明该系统运行效率快、精度高，具有很好的应用效果。
参考文献
[1] 高中亚，李振平，方海滨，等.二维复杂型面数字化比较技术的应用[J].工具技术，2015，49（5）：60?62.
[2] 陆峰，李宁，赵德宏.复杂曲面三维轮廓精度数字化比对检测与误差分析[J].制造业自动化，2014（18）：46?50.
[3] 陈胜利.快速成形技术及其发展趋势[J].制造业自动化，2009，31（10）：24?26.
[4] MA Hongchao， SUN Jie. Intelligent optimization of seam?line finding for orthophoto mosaicking with LiDAR point clouds [J]. Journal of Zhejiang University： Science C， 2011， 12（5）： 417?429.
[5] LI Jianchuan， YU Jianfeng. A new posture evaluation method of wing based on iterative closest point algorithm [J]. Advanced materials research， 2013， 718/720： 1279?1285.
[6] 魏海涛，杜云艳，任浩玮，等.基于N?KD树的空间点数据分组算法[J].地球信息科学学报，2015（1）：1?7.
[7] 徐伟恒，冯仲科，苏志芳，等.一种基于三维激光点云数据的单木树冠投影面积和树冠体积自动提取算法[J].光谱学与光谱分析，2014（2）：465?471.
[8] 王继东，陈桂林.基于半边数据结构的最短路径算法及其实现[J].计算机工程与应用，2009（8）：118?120.
