楊 帆，權(quán) 巍，白寶興，薛耀紅

（長春理工大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，吉林 長春130022）

0 引 言

點(diǎn)云拼接［1］的方法中，最常用的是在物體表面粘貼標(biāo)志點(diǎn)，通過標(biāo)志點(diǎn)的匹配進(jìn)行變換矩陣的求解，再對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行拼接。目前，點(diǎn)云拼接所面臨的問題是拼接自動(dòng)化程度不是很高，而且拼接的速度和精度也有待提高。為此，本文提出了一種基于標(biāo)志點(diǎn)的三維點(diǎn)云自動(dòng)拼接算法，首先匹配重疊區(qū)域內(nèi)標(biāo)志點(diǎn)，然后利用最小二乘法求取坐標(biāo)變換矩陣進(jìn)行點(diǎn)云拼接。

1 標(biāo)志點(diǎn)的自動(dòng)匹配

對(duì)于通過三維掃描儀測(cè)量得到的2組點(diǎn)云，其重疊區(qū)域一定位于2組點(diǎn)云的邊界區(qū)域；為了自動(dòng)匹配重疊區(qū)域內(nèi)的標(biāo)志點(diǎn)，首先根據(jù)標(biāo)志點(diǎn)間的空間不變性，匹配位于重疊區(qū)域最外圍的3個(gè)標(biāo)志點(diǎn)。然后，通過三點(diǎn)法［2］求取三對(duì)標(biāo)志點(diǎn)的變換矩陣。最后，匹配重疊區(qū)域內(nèi)其它標(biāo)志點(diǎn)。

1.1 匹配重疊區(qū)域內(nèi)的三對(duì)標(biāo)志點(diǎn)

設(shè)2組點(diǎn)云的標(biāo)志點(diǎn)集合分別為移動(dòng)標(biāo)志點(diǎn)集合P 和參考標(biāo)志點(diǎn)集合Q。首先，獲取P 中x 坐標(biāo)值最大的3個(gè)標(biāo)志點(diǎn)，分別用Pxmax1、Pxmax2、Pxmax3表示，并計(jì)算x 坐標(biāo)值最大的標(biāo)志點(diǎn)到其它兩標(biāo)志點(diǎn)的距離，用‖Pxmax1Pxmax2‖2、‖Pxmax1Pxmax3‖2表示，其中‖.‖2表示歐式距離。接著，獲取P 中x 坐標(biāo)值最小的3個(gè)標(biāo)志點(diǎn)，分別用Pxmin1，Pxmin2，Pxmin3表示，并計(jì)算x 坐標(biāo)值最小的標(biāo)志點(diǎn)到其它兩標(biāo)志點(diǎn)的距離，用‖Pxmin1Pxmin2‖2、‖Pxmin1Pxmin3‖2表示。同理在y 方向上也進(jìn)行相同操作，獲取到的標(biāo)志點(diǎn)分別用Pymax1、Pymax2、Pymax3、Pymin1、Pymin2、Pymin3表示，設(shè)其中y坐標(biāo)值最大和最小的標(biāo)志點(diǎn)為Pymax1、Pymin1，其距離分別用‖Pymax1Pymax2‖2、‖Pymax1Pymax3‖2、‖Pymin1Pymin2‖2、‖Pymin1Pymin3‖2表示，把標(biāo)志點(diǎn)集合P 計(jì)算得到的距離組成如式 （1）的距離矩陣A。計(jì)算標(biāo)志點(diǎn)集Q 中任意兩標(biāo)志點(diǎn)的距離，組成如式 （2）的距離矩陣B，其中k為Q 中標(biāo)志點(diǎn)的個(gè)數(shù)［3］

由于在提取標(biāo)志點(diǎn)的圓心坐標(biāo)時(shí)存在誤差，因此如果2個(gè)標(biāo)志點(diǎn)距離值的差值不超過指定閾值，則認(rèn)為這2個(gè)標(biāo)志點(diǎn)距離值是相等的。在三維測(cè)量中，重疊區(qū)域在視點(diǎn)1下某個(gè)點(diǎn)到其它J 個(gè)點(diǎn) （J≥2）的距離，與在視點(diǎn)2下某個(gè)點(diǎn)到J 個(gè)點(diǎn) （J≥2）的距離都對(duì)應(yīng)相等，則很有可能這2點(diǎn)為一對(duì)標(biāo)志點(diǎn)對(duì)。基于此把A 中每一行和B 中的每一行進(jìn)行比對(duì)，即如果A 中的某一行全部元素和B 某一行中2個(gè)元素相等，則組成A 中該行元素的3個(gè)點(diǎn)和在B 中對(duì)應(yīng)相等的2個(gè)元素組成的3個(gè)點(diǎn)，有可能為3個(gè)標(biāo)志點(diǎn)對(duì)，再通過任意一點(diǎn)到其它2點(diǎn)的夾角是否相等來進(jìn)一步確定是否為標(biāo)志點(diǎn)對(duì)［4］。

1.2 三點(diǎn)法求解初始變換矩陣

1.3 匹配其它標(biāo)志點(diǎn)對(duì)

根據(jù)R、T 對(duì)標(biāo)志點(diǎn)集合P 中的所有標(biāo)志點(diǎn)進(jìn)行坐標(biāo)變換得到標(biāo)志點(diǎn)集合P′。為了匹配坐標(biāo)變換前的重疊區(qū)域內(nèi)的標(biāo)志點(diǎn)，引入哈希表［6］來保存標(biāo)志點(diǎn)變換前后的對(duì)應(yīng)關(guān)系。經(jīng)過坐標(biāo)變換后，標(biāo)志點(diǎn)集合P′和參考標(biāo)志點(diǎn)集合Q 的重疊區(qū)域內(nèi)的標(biāo)志點(diǎn)對(duì)非常接近。匹配其他標(biāo)志點(diǎn)的算法如下：

（1）首先用哈希表記錄標(biāo)志點(diǎn)集合P 和P′中各個(gè)標(biāo)志點(diǎn)對(duì)應(yīng)關(guān)系。

（2）參考標(biāo)志點(diǎn)集合Q 根據(jù)文獻(xiàn) ［7］的方式構(gòu)建k－d樹，搜索目標(biāo)標(biāo)志點(diǎn)集合P′中每個(gè)標(biāo)志點(diǎn)在Q 中最接近的標(biāo)志點(diǎn)。

（3）由于需要排除掉不在重疊區(qū)域內(nèi)的最接近點(diǎn)對(duì)，所以設(shè)置一個(gè)最大距離閾值dmax，如果最接近點(diǎn)對(duì)的距離超過dmax，則刪除該點(diǎn)對(duì)。一般dmax設(shè)置不易過大，因?yàn)橹丿B區(qū)域內(nèi)的標(biāo)志點(diǎn)對(duì)已經(jīng)非常接近。

（4）通過步驟 （3）搜索完重疊區(qū)域內(nèi)標(biāo)志點(diǎn)對(duì)，再用哈希表把P′中位于重疊區(qū)域內(nèi)的標(biāo)志點(diǎn)替換成標(biāo)志點(diǎn)集合P 中的標(biāo)志點(diǎn)。

2 求取點(diǎn)云變換矩陣

重疊區(qū)域內(nèi)的標(biāo)志點(diǎn)匹配完成后，采用最小二乘法求取點(diǎn)云變換矩陣進(jìn)行點(diǎn)云拼接。設(shè)待拼接的2組點(diǎn)云分別用M 和N 來表示，M 中搜索到位于重疊區(qū)域的標(biāo)志點(diǎn)集為I，其中第i個(gè)標(biāo)志點(diǎn)用Ii表示，一共有n個(gè)標(biāo)志點(diǎn)。在點(diǎn)云N 中對(duì)應(yīng)的標(biāo)志點(diǎn)集為L，其第i個(gè)標(biāo)志點(diǎn)用Li表示，對(duì)應(yīng)的也有n個(gè)標(biāo)志點(diǎn)，目標(biāo)函數(shù)采用式 （7）的形式，其中X 為坐標(biāo)變換矩陣，其由旋轉(zhuǎn)矩陣珟R 和平移矩陣珟T 組成，即如式 （8），而Ii和Li用齊次坐標(biāo)表示。對(duì)于式 （7）可以通過奇異值分解法 （SVD）［8］，四元素法［9］和最小二乘法的方法求取坐標(biāo)變換陣。

由于在提取標(biāo)志點(diǎn)的坐標(biāo)時(shí)存在測(cè)量誤差，所以本文采用最小二乘法［10］進(jìn)行求解。標(biāo)志點(diǎn)集進(jìn)行坐標(biāo)變換時(shí)，有式 （9）的坐標(biāo)變換關(guān)系，而相應(yīng)的、珟L 用矩陣表示如式 （10）所示。為了便于求解，對(duì)矩陣珟L 進(jìn)行變換，設(shè)置變量，其值如式 （11）。則式 （9）相應(yīng)的可以轉(zhuǎn)變成式 （12）的形式。由于要求解變換矩陣X，也就是求解目標(biāo)函數(shù)的最小值，只需要求取變換矩陣X 的最小值，等價(jià)于求取式 （9）的極小值。通過式 （12）可以知道其極小值為式 （13）的形式，其中為的廣義逆矩陣。當(dāng)求解出各個(gè)Xi的極小值，則可以通過式 （14）求出X 的最小值

3 點(diǎn)云拼接實(shí)驗(yàn)

結(jié)構(gòu)光掃描儀通過投射結(jié)構(gòu)光來獲取物體表面的三維信息，避免了傳統(tǒng)接觸式測(cè)量方式，具有掃描速度快、測(cè)量精度高、方便快捷等優(yōu)點(diǎn)［11］。故本文采用結(jié)構(gòu)光掃描儀獲取點(diǎn)云的信息。其中實(shí)驗(yàn)系統(tǒng)配置環(huán)境為CPU 2.00GHz，內(nèi)存2.00GB，windows 7操作系統(tǒng)。一般進(jìn)行三維重構(gòu)方法分為系統(tǒng)參數(shù)標(biāo)定、結(jié)構(gòu)光的編解碼和特征點(diǎn)的三維信息計(jì)算3個(gè)部分［12］，本實(shí)驗(yàn)通過上述操作以后進(jìn)行多角度點(diǎn)云數(shù)據(jù)提取。

為了檢驗(yàn)本文提出的拼接算法，使用如圖1所示的人臉模型進(jìn)行了拼接實(shí)驗(yàn)。在實(shí)驗(yàn)過程中，將黑底白面的圓形標(biāo)志點(diǎn)粘貼在模型表面，采用結(jié)構(gòu)光三維掃描儀在2個(gè)視角分別投射結(jié)構(gòu)光進(jìn)行采集點(diǎn)云信息，如圖2所示。其中右部視角獲取到的點(diǎn)云個(gè)數(shù)為30680個(gè)，左部視角獲取到的點(diǎn)云個(gè)數(shù)為37392個(gè)。通過本方法首次獲取重疊區(qū)域內(nèi)的標(biāo)志點(diǎn)對(duì)信息，見表1，而表2是進(jìn)一步獲取重疊區(qū)域內(nèi)其它標(biāo)志點(diǎn)對(duì)信息。

圖1 實(shí)物模型

圖2 模型在2個(gè)視角下的點(diǎn)云信息

本文獲取標(biāo)志點(diǎn)對(duì)的方法和文獻(xiàn) ［13］的方法進(jìn)行對(duì)比。文獻(xiàn)［13］提出根據(jù)標(biāo)志點(diǎn)對(duì)間的相容性進(jìn)行匹配標(biāo)志點(diǎn)對(duì)，其首先分別計(jì)算2組點(diǎn)云中任意2個(gè)標(biāo)志點(diǎn)之間的距離，組成2個(gè)距離矩陣，通過比對(duì)距離矩陣以后再判斷匹配信息表是否含有匹配標(biāo)志點(diǎn)對(duì)集。這不僅降低了匹配速度，還提高了誤匹配率，其針對(duì)匹配歧義問題，還通過3個(gè)策略來處理匹配歧義問題，使匹配標(biāo)志點(diǎn)對(duì)的算法更加復(fù)雜。而本文主要考慮到拼接完成后重疊區(qū)域內(nèi)標(biāo)志點(diǎn)對(duì)非常接近這一特性，匹配重疊區(qū)域內(nèi)的標(biāo)志點(diǎn)對(duì)，本文的方法從整體上降低了比對(duì)復(fù)雜性，不會(huì)出現(xiàn)匹配歧義問題。

表1 首次獲取到的3個(gè)標(biāo)志點(diǎn)對(duì)信息

表2 獲取重疊區(qū)域的其它標(biāo)志點(diǎn)對(duì)信息

由于目前對(duì)拼接精度沒有達(dá)成一致的評(píng)估標(biāo)準(zhǔn)，而最常用的拼接精度一般采用標(biāo)志點(diǎn)對(duì)的平均重合度誤差，也就是拼接后標(biāo)志點(diǎn)對(duì)之間的平均距離誤差。所以利用本文提出的標(biāo)志點(diǎn)的三維點(diǎn)云自動(dòng)拼接方法對(duì)2 組點(diǎn)云進(jìn)行拼接，拼接后的效果圖如圖3 所示，通過表3計(jì)算的拼接平均距離誤差達(dá)到0.0275 mm。而文獻(xiàn)［13］的在其自己的系統(tǒng)環(huán)境下對(duì)汽車門進(jìn)行拼接實(shí)驗(yàn)后其整體的拼接誤差達(dá)到0.0545 mm。為了便于比較，本文對(duì)人頭模型采用文獻(xiàn) ［13］的方法再次進(jìn)行拼接實(shí)驗(yàn)，其拼接后的效果如圖4 所示，相應(yīng)的拼接平均距離誤差達(dá)到0.0423 mm，見表4?？梢钥闯霰疚牡姆椒ǖ钠唇泳雀摺?/p>

圖3 本文拼接后的效果

圖4 文獻(xiàn) ［13］拼接后的效果

表3 本文方法拼接后標(biāo)志點(diǎn)拼接誤差

表4 文獻(xiàn) ［13］拼接后標(biāo)志點(diǎn)拼接誤差

4 結(jié)束語

本文提出了一種標(biāo)志點(diǎn)的三維點(diǎn)云自動(dòng)拼接方法。由于三點(diǎn)可以確定坐標(biāo)轉(zhuǎn)換關(guān)系，所以利用標(biāo)志點(diǎn)間的空間特征不變性匹配位于重疊區(qū)域最外圍的3個(gè)標(biāo)志點(diǎn)，根據(jù)三點(diǎn)法求取變換矩陣。通過變換矩陣對(duì)待拼接點(diǎn)云的所有標(biāo)志點(diǎn)進(jìn)行坐標(biāo)變換，變換后位于重疊區(qū)域內(nèi)的標(biāo)志點(diǎn)對(duì)非常接近，引入哈希表來記錄標(biāo)志點(diǎn)變換前后對(duì)應(yīng)關(guān)系。用k－d樹來搜索最接近點(diǎn)對(duì)，設(shè)置最大距離閾值來排除錯(cuò)誤點(diǎn)對(duì)，提取坐標(biāo)變換后的重疊區(qū)域內(nèi)標(biāo)志點(diǎn)對(duì)。由于需要匹配坐標(biāo)變換前的重疊區(qū)域內(nèi)的標(biāo)志點(diǎn)對(duì)，所以利用哈希表把變換后位于重疊區(qū)域內(nèi)標(biāo)志點(diǎn)替換成變換前的標(biāo)志點(diǎn)。通過三維拼接實(shí)驗(yàn)可以看出本文方法的拼接精度達(dá)到0.0275mm，符合工業(yè)要求；能夠很好的運(yùn)用在工業(yè)測(cè)量。

［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ìn)投影方法的點(diǎn)云拼接算法 ［J］.計(jì)算機(jī)應(yīng)用研究，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）.［王赫.視覺測(cè)量點(diǎn)云數(shù)據(jù)拼接方法及關(guān)鍵技術(shù)研究 ［D］.哈爾濱：哈爾濱理工大學(xué)，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）.［王力，李廣云，賀磊，等.點(diǎn)云拼接中標(biāo)志自動(dòng)匹配方法 ［J］，測(cè)繪科學(xué)，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）.［耿云，孫軍華，劉謙哲，等.自由曲面視覺測(cè)量標(biāo)志點(diǎn)三維匹配方法研究 ［J］.測(cè)控技術(shù)，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）.［王建奇.大規(guī)模點(diǎn)云模型拼接與融合技術(shù)研究 ［D］.浙江：浙江工業(yè)大學(xué)，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］.計(jì)算機(jī)工程與設(shè)計(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 人耳點(diǎn)云配準(zhǔn)的并行Softassign算法 ［J］.計(jì)算機(jī)工程與設(shè)計(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ì)的點(diǎn)云拼接 ［J］.機(jī)械工程學(xué)報(bào)，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）.［滕志遠(yuǎn)，張愛武.單位四元素法在激光點(diǎn)云坐標(biāo)轉(zhuǎn)換中的應(yīng)用 ［J］.測(cè)繪通報(bào)，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）.［陳展東.基于多投影的結(jié)構(gòu)光三維重建技術(shù)的研究［D］.長春：長春理工大學(xué)，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）.［胡民政，陳曉波，習(xí)俊通.兩軸轉(zhuǎn)臺(tái)結(jié)構(gòu)光三維掃描儀及多視自動(dòng)拼合 ［J］.測(cè)試技術(shù)學(xué)報(bào)，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）. ［韓成，秦貴和，宮宇.等.基于彩色結(jié)構(gòu)光的三維重構(gòu)方法 ［J］.吉林大學(xué)學(xué)報(bào) （工學(xué)版），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）.［梁云波，鄧文怡，婁小平，等.基于標(biāo)志點(diǎn)的多視三維數(shù)據(jù)自動(dòng)拼接方法 ［J］.北京信息科技大學(xué)報(bào)，2010，25 （1）：30－34.］