楊 帆，權 巍，白寶興，薛耀紅

（長春理工大學 計算機科學技術學院，吉林 長春130022）

0 引 言

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

1 標志點的自動匹配

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

1.1 匹配重疊區(qū)域內(nèi)的三對標志點

設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 中標志點的個數(shù)［3］

由于在提取標志點的圓心坐標時存在誤差，因此如果2個標志點距離值的差值不超過指定閾值，則認為這2個標志點距離值是相等的。在三維測量中，重疊區(qū)域在視點1下某個點到其它J 個點 （J≥2）的距離，與在視點2下某個點到J 個點 （J≥2）的距離都對應相等，則很有可能這2點為一對標志點對?；诖税袮 中每一行和B 中的每一行進行比對，即如果A 中的某一行全部元素和B 某一行中2個元素相等，則組成A 中該行元素的3個點和在B 中對應相等的2個元素組成的3個點，有可能為3個標志點對，再通過任意一點到其它2點的夾角是否相等來進一步確定是否為標志點對［4］。

1.2 三點法求解初始變換矩陣

1.3 匹配其它標志點對

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

（1）首先用哈希表記錄標志點集合P 和P′中各個標志點對應關系。

（2）參考標志點集合Q 根據(jù)文獻 ［7］的方式構建k－d樹，搜索目標標志點集合P′中每個標志點在Q 中最接近的標志點。

（3）由于需要排除掉不在重疊區(qū)域內(nèi)的最接近點對，所以設置一個最大距離閾值dmax，如果最接近點對的距離超過dmax，則刪除該點對。一般dmax設置不易過大，因為重疊區(qū)域內(nèi)的標志點對已經(jīng)非常接近。

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

2 求取點云變換矩陣

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

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

3 點云拼接實驗

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

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

圖1 實物模型

圖2 模型在2個視角下的點云信息

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

表1 首次獲取到的3個標志點對信息

表2 獲取重疊區(qū)域的其它標志點對信息

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

圖3 本文拼接后的效果

圖4 文獻 ［13］拼接后的效果

表3 本文方法拼接后標志點拼接誤差

表4 文獻 ［13］拼接后標志點拼接誤差

4 結(jié)束語

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

［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）.［王赫.視覺測量點云數(shù)據(jù)拼接方法及關鍵技術研究 ［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）.［王建奇.大規(guī)模點云模型拼接與融合技術研究 ［D］.浙江：浙江工業(yè)大學，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）.［滕志遠，張愛武.單位四元素法在激光點云坐標轉(zhuǎn)換中的應用 ［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）.［陳展東.基于多投影的結(jié)構光三維重建技術的研究［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）.［胡民政，陳曉波，習俊通.兩軸轉(zhuǎn)臺結(jié)構光三維掃描儀及多視自動拼合 ［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）. ［韓成，秦貴和，宮宇.等.基于彩色結(jié)構光的三維重構方法 ［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）.［梁云波，鄧文怡，婁小平，等.基于標志點的多視三維數(shù)據(jù)自動拼接方法 ［J］.北京信息科技大學報，2010，25 （1）：30－34.］