基于标志点的三维点云自动拼接技术

杨 帆，权 巍，白宝兴，薛耀红

（长春理工大学 计算机科学技术学院，吉林 长春130022）

0 引 言

点云拼接［1］的方法中，最常用的是在物体表面粘贴标志点，通过标志点的匹配进行变换矩阵的求解，再对点云数据进行拼接。目前，点云拼接所面临的问题是拼接自动化程度不是很高，而且拼接的速度和精度也有待提高。为此，本文提出了一种基于标志点的三维点云自动拼接算法，首先匹配重叠区域内标志点，然后利用最小二乘法求取坐标变换矩阵进行点云拼接。

1 标志点的自动匹配

对于通过三维扫描仪测量得到的2组点云，其重叠区域一定位于2组点云的边界区域；为了自动匹配重叠区域内的标志点，首先根据标志点间的空间不变性，匹配位于重叠区域最外围的3个标志点。然后，通过三点法［2］求取三对标志点的变换矩阵。最后，匹配重叠区域内其它标志点。

1.1 匹配重叠区域内的三对标志点

设2组点云的标志点集合分别为移动标志点集合P 和参考标志点集合Q。首先，获取P 中x 坐标值最大的3个标志点，分别用Pxmax1、Pxmax2、Pxmax3表示，并计算x 坐标值最大的标志点到其它两标志点的距离，用‖Pxmax1Pxmax2‖2、‖Pxmax1Pxmax3‖2表示，其中‖.‖2表示欧式距离。接着，获取P 中x 坐标值最小的3个标志点，分别用Pxmin1，Pxmin2，Pxmin3表示，并计算x 坐标值最小的标志点到其它两标志点的距离，用‖Pxmin1Pxmin2‖2、‖Pxmin1Pxmin3‖2表示。同理在y 方向上也进行相同操作，获取到的标志点分别用Pymax1、Pymax2、Pymax3、Pymin1、Pymin2、Pymin3表示，设其中y坐标值最大和最小的标志点为Pymax1、Pymin1，其距离分别用‖Pymax1Pymax2‖2、‖Pymax1Pymax3‖2、‖Pymin1Pymin2‖2、‖Pymin1Pymin3‖2表示，把标志点集合P 计算得到的距离组成如式 （1）的距离矩阵A。计算标志点集Q 中任意两标志点的距离，组成如式 （2）的距离矩阵B，其中k为Q 中标志点的个数［3］

由于在提取标志点的圆心坐标时存在误差，因此如果2个标志点距离值的差值不超过指定阈值，则认为这2个标志点距离值是相等的。在三维测量中，重叠区域在视点1下某个点到其它J 个点 （J≥2）的距离，与在视点2下某个点到J 个点 （J≥2）的距离都对应相等，则很有可能这2点为一对标志点对。基于此把A 中每一行和B 中的每一行进行比对，即如果A 中的某一行全部元素和B 某一行中2个元素相等，则组成A 中该行元素的3个点和在B 中对应相等的2个元素组成的3个点，有可能为3个标志点对，再通过任意一点到其它2点的夹角是否相等来进一步确定是否为标志点对［4］。

1.2 三点法求解初始变换矩阵

1.3 匹配其它标志点对

根据R、T 对标志点集合P 中的所有标志点进行坐标变换得到标志点集合P′。为了匹配坐标变换前的重叠区域内的标志点，引入哈希表［6］来保存标志点变换前后的对应关系。经过坐标变换后，标志点集合P′和参考标志点集合Q 的重叠区域内的标志点对非常接近。匹配其他标志点的算法如下：

（1）首先用哈希表记录标志点集合P 和P′中各个标志点对应关系。

（2）参考标志点集合Q 根据文献 ［7］的方式构建k－d树，搜索目标标志点集合P′中每个标志点在Q 中最接近的标志点。

（3）由于需要排除掉不在重叠区域内的最接近点对，所以设置一个最大距离阈值dmax，如果最接近点对的距离超过dmax，则删除该点对。一般dmax设置不易过大，因为重叠区域内的标志点对已经非常接近。

（4）通过步骤 （3）搜索完重叠区域内标志点对，再用哈希表把P′中位于重叠区域内的标志点替换成标志点集合P 中的标志点。

2 求取点云变换矩阵

重叠区域内的标志点匹配完成后，采用最小二乘法求取点云变换矩阵进行点云拼接。设待拼接的2组点云分别用M 和N 来表示，M 中搜索到位于重叠区域的标志点集为I，其中第i个标志点用Ii表示，一共有n个标志点。在点云N 中对应的标志点集为L，其第i个标志点用Li表示，对应的也有n个标志点，目标函数采用式 （7）的形式，其中X 为坐标变换矩阵，其由旋转矩阵珟R 和平移矩阵珟T 组成，即如式 （8），而Ii和Li用齐次坐标表示。对于式 （7）可以通过奇异值分解法 （SVD）［8］，四元素法［9］和最小二乘法的方法求取坐标变换阵。

由于在提取标志点的坐标时存在测量误差，所以本文采用最小二乘法［10］进行求解。标志点集进行坐标变换时，有式 （9）的坐标变换关系，而相应的、珟L 用矩阵表示如式 （10）所示。为了便于求解，对矩阵珟L 进行变换，设置变量，其值如式 （11）。则式 （9）相应的可以转变成式 （12）的形式。由于要求解变换矩阵X，也就是求解目标函数的最小值，只需要求取变换矩阵X 的最小值，等价于求取式 （9）的极小值。通过式 （12）可以知道其极小值为式 （13）的形式，其中为的广义逆矩阵。当求解出各个Xi的极小值，则可以通过式 （14）求出X 的最小值

3 点云拼接实验

结构光扫描仪通过投射结构光来获取物体表面的三维信息，避免了传统接触式测量方式，具有扫描速度快、测量精度高、方便快捷等优点［11］。故本文采用结构光扫描仪获取点云的信息。其中实验系统配置环境为CPU 2.00GHz，内存2.00GB，windows 7操作系统。一般进行三维重构方法分为系统参数标定、结构光的编解码和特征点的三维信息计算3个部分［12］，本实验通过上述操作以后进行多角度点云数据提取。

为了检验本文提出的拼接算法，使用如图1所示的人脸模型进行了拼接实验。在实验过程中，将黑底白面的圆形标志点粘贴在模型表面，采用结构光三维扫描仪在2个视角分别投射结构光进行采集点云信息，如图2所示。其中右部视角获取到的点云个数为30680个，左部视角获取到的点云个数为37392个。通过本方法首次获取重叠区域内的标志点对信息，见表1，而表2是进一步获取重叠区域内其它标志点对信息。

图1 实物模型

图2 模型在2个视角下的点云信息

本文获取标志点对的方法和文献 ［13］的方法进行对比。文献［13］提出根据标志点对间的相容性进行匹配标志点对，其首先分别计算2组点云中任意2个标志点之间的距离，组成2个距离矩阵，通过比对距离矩阵以后再判断匹配信息表是否含有匹配标志点对集。这不仅降低了匹配速度，还提高了误匹配率，其针对匹配歧义问题，还通过3个策略来处理匹配歧义问题，使匹配标志点对的算法更加复杂。而本文主要考虑到拼接完成后重叠区域内标志点对非常接近这一特性，匹配重叠区域内的标志点对，本文的方法从整体上降低了比对复杂性，不会出现匹配歧义问题。

表1 首次获取到的3个标志点对信息

表2 获取重叠区域的其它标志点对信息

由于目前对拼接精度没有达成一致的评估标准，而最常用的拼接精度一般采用标志点对的平均重合度误差，也就是拼接后标志点对之间的平均距离误差。所以利用本文提出的标志点的三维点云自动拼接方法对2 组点云进行拼接，拼接后的效果图如图3 所示，通过表3计算的拼接平均距离误差达到0.0275 mm。而文献［13］的在其自己的系统环境下对汽车门进行拼接实验后其整体的拼接误差达到0.0545 mm。为了便于比较，本文对人头模型采用文献 ［13］的方法再次进行拼接实验，其拼接后的效果如图4 所示，相应的拼接平均距离误差达到0.0423 mm，见表4。可以看出本文的方法的拼接精度高。

图3 本文拼接后的效果

图4 文献 ［13］拼接后的效果

表3 本文方法拼接后标志点拼接误差

表4 文献 ［13］拼接后标志点拼接误差

4 结束语

本文提出了一种标志点的三维点云自动拼接方法。由于三点可以确定坐标转换关系，所以利用标志点间的空间特征不变性匹配位于重叠区域最外围的3个标志点，根据三点法求取变换矩阵。通过变换矩阵对待拼接点云的所有标志点进行坐标变换，变换后位于重叠区域内的标志点对非常接近，引入哈希表来记录标志点变换前后对应关系。用k－d树来搜索最接近点对，设置最大距离阈值来排除错误点对，提取坐标变换后的重叠区域内标志点对。由于需要匹配坐标变换前的重叠区域内的标志点对，所以利用哈希表把变换后位于重叠区域内标志点替换成变换前的标志点。通过三维拼接实验可以看出本文方法的拼接精度达到0.0275mm，符合工业要求；能够很好的运用在工业测量。

［1］YANG Yingbao，LIU Xianyong，YANG Junping.Pointclouds registration algorithm based on improve projection ［J］.Application Research of Computers，2011，28 （10）：3954－3956 （in Chinese）. ［杨英保，刘先勇，杨俊平.一种基于改进投影方法的点云拼接算法 ［J］.计算机应用研究，2011，28（10）：3954－3956.］

［2］WANG He.Research on registration method of point cloud data and key technology in vision measurement ［D］.Harbin：Harbin University of Science and Technology，2011：25－38 （in Chinese）.［王赫.视觉测量点云数据拼接方法及关键技术研究 ［D］.哈尔滨：哈尔滨理工大学，2011：25－38.］

［3］WANG Li，LI Guangyun，HE Lei，et al.Marked automatic matching method in the registration of point clouds［J］.Science of Surveying and Mapping，2011，36 （2）：144－145 （in Chinese）.［王力，李广云，贺磊，等.点云拼接中标志自动匹配方法 ［J］，测绘科学，2011，36 （2）：144－145.］

［4］GENG Yun，SUN Junhua，LIU Qianzhe，et al.3D matching of mark points for free－form surface vision measurement［J］.Measurement and Control Technology，2011，30 （7）：105－109 （in Chinese）.［耿云，孙军华，刘谦哲，等.自由曲面视觉测量标志点三维匹配方法研究 ［J］.测控技术，2011，30（7）：105－109.］

［5］WANG Jianqi.Research on registration and integration technology for large－scale point cloud model［D］.Zhejiang：Zhejiang University of Technology，2012：17－18 （in Chinese）.［王建奇.大规模点云模型拼接与融合技术研究 ［D］.浙江：浙江工业大学，2012：17－18.］

［6］SONG Yejun，YUAN Chang’an，WANG Yan.Algorithm of classification information matching and discriminating model based on Hash table ［J］.Computer Engineering and Design，2009，30 （16）：1552－1554 （in Chinese）. ［宋叶俊，元昌安，王艳.基于Hash表的分类信息匹配及甄别算法 ［J］.计算机工程与设计，2009，30 （16）：1552－1554.］

［7］CAI Jing，DONG Lin，SUN Xiaopeng.Parallel softassign algorithm for 3Dhuman ear point clouds registration ［J］.Computer Engineering and Design，2013，34 （10）：3629－3634 （in Chinese）. ［蔡静，董琳，孙晓鹏.3D 人耳点云配准的并行Softassign算法 ［J］.计算机工程与设计，2013，34 （10）：3629－3634.］

［8］QIN Xujia，WANG Jianqi，ZHENG Hongbo，et al.Point clouds registration of 3D moment invariant feature estimation［J］.Journal of Mechanical Enginerring，2013，49 （1）：129－134 （in Chinese）.［秦绪佳，王建奇，郑红波，等.三维不变矩特征估计的点云拼接 ［J］.机械工程学报，2013，49 （1）：129－134.］

［9］TENG Zhiyuan，ZHANG Aiwu.Application of unit four elements method to laser point cloud coordinate transformation［J］.Bulletin of Surveying and Mapping，2010 （11）：7－10 （in Chinese）.［滕志远，张爱武.单位四元素法在激光点云坐标转换中的应用 ［J］.测绘通报，2010 （11）：7－10.］

［10］CHEN Zhandong.Research on structured light reconstruction based on multi－projection ［D］.Changchun：Changchun University of Science and Technology，2011：44－47 （in Chinese）.［陈展东.基于多投影的结构光三维重建技术的研究［D］.长春：长春理工大学，2011：44－47.］

［11］HU Minzheng，CHEN Xiaobo，XI Juntong.2－axis turntable three－dimensional measuring system based on structured light and automatic registration of multi－view ［J］.Journal of Test and Measurement Technology，2010，24 （2）：161－169 （in Chinese）.［胡民政，陈晓波，习俊通.两轴转台结构光三维扫描仪及多视自动拼合 ［J］.测试技术学报，2010，24 （2）：161－169.］

［12］HAN Cheng，QIN Guihe，GONG YU，et al.Method for three－dimensional reconstruction based on color structured light［J］.Journal of Jilin University （Engineering and Technology Edition），2013，43 （5）：1343－1351 （in Chinese）. ［韩成，秦贵和，宫宇.等.基于彩色结构光的三维重构方法 ［J］.吉林大学学报 （工学版），2013，43 （5）：1343－1351.］

［13］LIANG Yunbo，DENG Wenyi，LOU Xiaoping，et al.Automatic registration method of multi－view 3D data based on marked points［J］.Journal of Beijing Information Science and Technology Universtiy，2010，25 （1）：30－34 （in Chinese）.［梁云波，邓文怡，娄小平，等.基于标志点的多视三维数据自动拼接方法 ［J］.北京信息科技大学报，2010，25 （1）：30－34.］