三维点云拼接是三维面型反求中的关键和难点。提出了一种特征点三维点云拼接技术。整个拼接过程由粗拼接和精拼接两部分组成。通过引入被测物的特征点，分析了坐标变换矩阵的求解方法，首先，粗略拼接的初始变换矩阵由SVD算法求解，其次，两片点云之间的最近点通过SNN算法加速搜索，从而，利用改进的最近点迭代算法实现了精确拼接，最后，给出了程序设计思路。 标签：三维点云拼接；特征点；SVD ；SNN； 最近邻迭代
1 引言
激光三维扫描法是曲面形体检测技术中一个十分活跃的分支，在工业上获得了越来越广泛的运用。然而，由于实际测量中，有多种大型物体或者形状复杂的物体，这样一来，物体的三维模型就不能够直接测量。物体分片测量成为了近年来发展起来的一种复杂物体测量技术，通过获得物体的局部参数，然后对多个局部物理参数进行拼接，得到完整的物体模型。
三维拼接技术的本质就是把不同局部参量的物理参数所在的局部坐标系进行变换，合成为同
一坐标系的一组数据[1～2]。迭代最近点匹配（Iterative Closet Point，ICP）算法最早是由由Besl等[3]提出，目前该方法在物体模型拼接中得到了广泛应用，并且衍生了大量改进算法。但目前大多数算法仍然存在许多问题，比如由于数据量大造成的拼接速度慢、精度低等缺点。本文在现有算法的基础上，基于特征点拼接，提出了一种速度快、精度高的改进最近点迭代算法，分为粗拼接和精拼接两个步骤，可以实现较好的效果。 2 特征点粗略拼接石榴套袋技术
2.1 特征点对的选取
特征点是三维拼接技术中非常重要的标识点，在该方法中，我们可以将特征点贴于被测物两个视角的重叠区，然后利用三维测量系统对两个局部曲面分别进行测量， 从而得到两个曲面的物理点云数据。
首先，和分别为两个不同局部曲面的特征点集。那么根据特征点的空间特征不变性，可以得到组匹配点对和，U、V分别为在两个曲面下所获得的三维数据点集的子集，并且 和 一一对应。在此基础上，根据三维数据拼接技术的原理，坐标变换参数（旋转矩阵） 和（平移向量） 应满足如下目标函数取得最小值 [4]：
2.2 坐标变换矩阵的获取
最小二乘法是处理和分析观测数据的一种经典方法。对于三维空间两个视角下的特征点集和，可由以下的SVD分解法求得旋转矩阵和平移矩阵，SVD法可以确保拼接不发生畸变，而且精度比较高。
（1）将式（1）改写为以下形式：
其中。这里，我们引入正规阵
（2）记，计算上式的SVD分解，由Lemma定理，可得。
（3）对于空间点集分别计算和。
紫铜止水片（4）计算平移向量。
得到和以后，特征点集中的任意一点都可以通过转换到中。将两组数据转换到同一坐标系下。从而实现拼接技术。
3 精确拼接
在上一步粗略拼接的基础上，根据上述测量得到的初始特征点匹配点对，采用上述两个局部曲面的拼接位置作为初始定位。在精确拼接的迭代匹配中，基于Besl等提出的ICP算法，进一步，采用SNN算法，基于距离阈值限制条件，从以上粗略的特征点对中选取精确匹配点对，从而实现将两片曲面点云中属于正确匹配区域范围的点加入精确匹配点对集合。最后，利用经典的带系数修正的四元素（Quaternion）法[5]作为每一次迭代循环的最优化解析方法。 3.1 最近点搜索
现有的ICP算法计算速度比较慢，主要原因在于搜索策略的选择，基于现有算法的缺点，我们运用一种新的最近点搜索算法——SNN算法[6]。
传统算法求解所有的特征点的两两之间的距离，从而造成计算数据量大，拼接速度慢。而SNN 算法具有计算速度快的优点，首先，它将所有的扫描数据按照某一维度进行优先排序，然后，限定该维的某一邻域作为距离阈值，从而只计算该范围内的任意两两点之间的距离，最后根据计算结果相比较的出ICP算法中的最近相邻点。由于该算法只需要求解距离阈值较小邻域内的点云数据，所以大大节约了拼接时间，提高了计算速度。根据SNN算
法，如果扫描数据集合中的点在排序维的分布情况比较均匀，即在距离限制阈值邻域内，其所包含的有效数据点的个数不超过某一个与数据集合中点的总数无关的常数，则SNN 算法的时间复杂度为。如果通过扫描空间维度得到拼接数据，那么扫描后所得到的数据必然会按照某一维度自然排序，所以其时间复杂度会降为。因此，基于ICP算法中最近邻点迭代的原则，利用SNN算法进行最近邻点的搜索方法，可以大大节约搜索时间，提高点云拼接效率。
3.2 点云之间的距离与收敛性
由Besl提出的ICP算法，点云之间的距离由两个数据点在三维空间中的欧氏距离决定，但这种度量方法在某些情况下会误差较大（比如当两个平行平面滑动时）[1]。因此，寻求有效的定义两最近点之间的距离的方法，对提高算法的效率有很大帮助。
鉴于此，本文提出利用两点之间的均方距离作为最近邻点之间的距离的度量准则，假设和分别为在次迭代中所得到的最近点的数据点集。则点集和的均方距离定义为
毒死蜱颗粒剂
上式中，为重叠曲面中点云数据的个数，通过使用该最近点距离度量准则，可以大大加快算法的收敛速度。
薄荷棒
因此，该改进的最近点迭代算法程序如下：
软化器（1）初始化并设置误差门限，求解三维数据拼接的坐标变换矩阵和，并根据初始坐标变换关系对两组点云数据进行坐标变换，最后求得变换后两组点云数据之间的距离。
（2）根据距离阈值限制条件，由SNN算法搜索出两组匹配点云中的最临近匹配点对。
（3）消除无效匹配点对后，对剩余最邻近匹配点对，进而利用带修正系数的四元素算法优化求解转换参数 和。（4）再次利用、对以上两组点云数据进行变换，并求出该变换后两者之间的距离。
（5）如果小于初始设定阈值S，则停止搜索。否则返回步骤（2），继续搜索最邻近匹配点对 ，直到 小于初始设定阈值为止。
4 结论
三维点云拼接作为三维物体逆向反求中的一个关键技术，其精度直接关系到三维曲面重建的精度。本文提出了一种改进的最近点迭代算法的点云拼接技术，通过在重构曲面引入特
征标识点，粗略拼接中利用SVD算法求得初始变换矩阵，搜索匹配特征点，从而实现精确拼接。该改进的ICP算法，结合了SNN算法，大大提高了最邻近点的搜索速度，有效提高了检索效率，实现精确的拼接效果。该方法拼接精度较高，也适合于大型物体，并且具有很好的收敛性。
参考文献：
[1]Chen Y， Medioni G. Object modeling by registration of multiple range images [J].Image and Vision Computing，1992， 10（03）：145-155.
[2]李万松，苏礼坤.相位检测面形术在大尺度三维面形测量中的应用[J].光学学报，2000，20（06）：792-796.
[3]Besl P J， M ckay N D. A method for registration of 3D shapes [J].IEEE Transactions on Pattern Analysis and Machine Intelligence， 1992，14（02）：239-256.
[4]Shinji Umeyama. Least-Squares estimation of transformation parameters between two point patterns [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1991，
13（4）：376-380.
[5]Horn B K P. Closed-form solution of absolute orientation using unit quaternions[J].J Opt Soc Am，1987， A（04）：629-642.
座便器结构[6]胡建军，唐常杰，李川等.基于最近邻优先的高效聚类算法[J].四川大学学报：工程科学版，2004，36（06） ：93-99.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议