分形維數(shù)的全局點云初始配準(zhǔn)算法

封雪梅，張志毅，楊 龍

西北農(nóng)林科技大學(xué) 信息工程學(xué)院，陜西 楊凌712100

1 引言

隨著三維成像技術(shù)如激光雷達(dá)和結(jié)構(gòu)光主動成像等的快速發(fā)展，從實物模型構(gòu)建數(shù)字模型得到更加廣泛的應(yīng)用。由于受到實物自身形狀和觀察方向的限制，需要從不同角度掃描實物，獲得多角度掃描數(shù)據(jù)。這些掃描數(shù)據(jù)之間包含一定的公共部分，但是幾何位置位于不同的坐標(biāo)系下。點云數(shù)據(jù)配準(zhǔn)就是依據(jù)已經(jīng)存在的公共部分，將各個視角得到的掃描數(shù)據(jù)統(tǒng)一到相同的坐標(biāo)系下，以得到完整的三維點云模型[1]。

文獻(xiàn)[2]提出了全局配準(zhǔn)算法——全局最優(yōu)迭代最近點（Global optimal Iterative Closest Point，Go-ICP）算法。Go-ICP算法將一個半徑為π 的球映射為旋轉(zhuǎn)解空間，將單位立方體映射為平移解空間，利用分枝限界法求解變換矩陣最優(yōu)解。Go-ICP 算法解決了傳統(tǒng)ICP算法容易陷于局部最小值的缺陷，對于部分角度的點云與完整模型的點云之間的配準(zhǔn)問題和重疊率很高的點云數(shù)據(jù)之間的配準(zhǔn)問題都能達(dá)到很好的效果，但是不能很好地解決重疊率低的點云數(shù)據(jù)之間的配準(zhǔn)問題。

針對點云初始配準(zhǔn)算法，一方面采用基于隨機抽樣一致性算法進(jìn)行初始配準(zhǔn)；另一方面采用基于點云幾何特征，從點云中提取特征點進(jìn)行初始配準(zhǔn)?；陔S機抽樣一致性算法的思想，文獻(xiàn)[3]提出了初始配準(zhǔn)算法——4PCS（4-Points Congruent Sets）算法，利用剛體變換保持相交線段的交比不變的性質(zhì)，在點云P 上選取共面的4點作為基底，然后在點云Q 上尋找所有與該基底近似全等的共面4點集合，進(jìn)行配準(zhǔn)。此算法能夠?qū)Υ蠖鄶?shù)的點云數(shù)據(jù)進(jìn)行較好的配準(zhǔn)，但是對于某些存在大量平面的點云數(shù)據(jù)的配準(zhǔn)效果有待提高。為了提高配準(zhǔn)效率，文獻(xiàn)[4]在此基礎(chǔ)上進(jìn)行了改進(jìn)，提出了Super-4PCS算法，進(jìn)行點云初始配準(zhǔn)?；邳c云幾何特征的思想，文獻(xiàn)[5]提出了初始配準(zhǔn)算法，通過鄰域擬合計算點云中點的曲率值信息，通過形狀因子（Shape Index，SI）篩選關(guān)鍵點，構(gòu)建局部參考框架，提取點云中的局部特征點，進(jìn)行點云初始配準(zhǔn)。采用鄰域擬合計算點云中的曲率信息，是將連續(xù)的數(shù)學(xué)曲面理論應(yīng)用于離散的點云數(shù)據(jù)中，是一種啟發(fā)式的思想，理論依據(jù)有待提高。文獻(xiàn)[6]提出通過中心點的鄰域協(xié)方差矩陣來獲得中心點的法向量信息，利用法向量以及歸一化的特征值的變化量等相關(guān)信息作為特征描述符，獲得最初的匹配點對；再利用傳播機制，即在一個正確的匹配點對周圍聚集更多正確的匹配點對，在一個錯誤的匹配點對周圍不會聚集更多的正確匹配點對，從最初的匹配點對中篩選出較高精度的匹配點對進(jìn)行初始配準(zhǔn)；然后采用剪枝迭代最近點（Trimmed Iterative Closest Point，Trimmed-ICP）細(xì)配準(zhǔn)算法進(jìn)行配準(zhǔn)。此算法采用鄰域的協(xié)方差矩陣獲得對應(yīng)點處的法向量有一定的理論依據(jù)；針對鄰域半徑不能確定的問題，采用多尺度鄰域半徑計算得到多組法向量；然而如何獲得最佳鄰域來計算對應(yīng)的協(xié)方差矩陣，獲得較為準(zhǔn)確的法向量信息，從而減少噪聲點的影響還值得進(jìn)一步研究。文獻(xiàn)[7]提出基于沃羅諾伊圖的方法從點云中提取特征點，此方法可以從完整的點云模型中提取出較尖銳的特征點，能夠從部分角度的點云數(shù)據(jù)中提取出完整的輪廓邊界線特征，但是不能很好地從部分角度的點云數(shù)據(jù)中提取出內(nèi)部特征。文獻(xiàn)[8]提出了一種基于熵和粒子群的三維點云配準(zhǔn)算法，該算法可以有效地抑制噪聲并提高配準(zhǔn)精度。文獻(xiàn)[9]提出了一種基于硬分配和軟分配的方法，在重疊百分比較低時，實現(xiàn)點云的良好配準(zhǔn)。

針對細(xì)配準(zhǔn)算法，對于文獻(xiàn)[10]提出的傳統(tǒng)迭代最近點（Iterative Closest Point，ICP）算法，文獻(xiàn)[11]提出了剪枝迭代最近點（Trimmed-ICP）算法，增強了ICP 算法的抗噪性和魯棒性。文獻(xiàn)[12]在傳統(tǒng)ICP 算法基礎(chǔ)上，優(yōu)化目標(biāo)函數(shù)，使對應(yīng)點之間的距離中零距離的數(shù)量最大化，來確定對應(yīng)點，進(jìn)行精細(xì)配準(zhǔn)。

分形理論是由Mandelbrot 提出并建立的理論體系[13]。維數(shù)是分形幾何的中心概念，而Hausdorff維數(shù)是分形維數(shù)的重要內(nèi)容[14]。維數(shù)大多應(yīng)用在圖像特征計盒維數(shù)方面[15-17]。分形維數(shù)是用來衡量自然界不規(guī)則程度的度量參數(shù)[13]，例如分形維數(shù)可以對非光滑、非規(guī)則、破碎等極其復(fù)雜的分形體進(jìn)行定量刻畫。分形維數(shù)參數(shù)，表征了分形體的復(fù)雜程度和粗糙程度，即分形維數(shù)極大或極小，則分形體越不規(guī)則、越復(fù)雜[18]。因此點云數(shù)據(jù)中不同的結(jié)構(gòu)和形狀對應(yīng)著不同的分形維數(shù)。

針對Go-ICP 算法[2]對重疊率低的點云數(shù)據(jù)配準(zhǔn)效果不是很好的問題，提出一種新的點云初始配準(zhǔn)算法——基于分形維數(shù)的全局點云初始配準(zhǔn)算法。首先計算點云中各點的維數(shù)值；然后根據(jù)點云維數(shù)分布提取特征點；將特征點使用密度聚類算法進(jìn)行聚類，用類質(zhì)心代表每類的屬性信息；任意選取三個類質(zhì)心組成一個三角形，從三角形中尋找全等三角形對，作為匹配點對，進(jìn)行初始配準(zhǔn)；最后將初始配準(zhǔn)后的點云數(shù)據(jù)進(jìn)行剪枝ICP細(xì)配準(zhǔn)。該算法對于初始位姿差異大的點云，可以明顯縮小點云之間的錯位，更加有利于點云細(xì)配準(zhǔn)，最后獲得較好的配準(zhǔn)效果。算法流程如圖1所示。

圖1 算法流程圖

2 點云初始配準(zhǔn)

分形幾何理論認(rèn)為，幾何體維數(shù)可以連續(xù)存在，因此常用“相似性維數(shù)”來計算和表達(dá)具有自相似特征的形狀。它可由以下方式來定義：若將一個各邊都為單位長度的基本圖形G 的各邊都割裂為r 個均等的部分，最后能得到由N 個尺度為1 r 的相似于G 的圖形，則該圖形具有相似性維數(shù)logrN 。一維空間中的某長度為m的線段，將它分割為相對尺度標(biāo)準(zhǔn)長度為n 的k 部分時，可以得到k=m/n 個部分，則相似性維數(shù)為logk(m/n)=1，等于線段的拓?fù)渚S數(shù)。任意二維空間中的多邊形均可被分割為一系列三角形，使用面積這一參量代替“被分割的子圖形”的計數(shù)方式時，拓?fù)渚S數(shù)的數(shù)值保持不變；對于兩個相似的平面圖形，選擇圖形的最小包圍圓的半徑作為底，假定其外接圓半徑分別為“R”和“r ”，面積分別為“SR”和“Sr”，則其相似性維數(shù)為log(R/r)(SR/Sr)=2。同理任意三維空間中，對于兩個相似的立體圖形，選擇圖形的最小包圍球的半徑作為底，假定其外接球半徑分別為“R”和“r ”，體積分別為“VR”和“Vr”，則其相似性維數(shù)為log(R/r)(VR/Vr)。目前使用維數(shù)來定義點云數(shù)據(jù)的形狀屬性非常少見。由于Hausdorff維數(shù)在很多情形下都很難計算或估計，因而鮮有應(yīng)用。對于點云數(shù)據(jù)來說并不需要十分嚴(yán)格的維數(shù)定義，只需找到具有維數(shù)特性的表達(dá)式即可。基于以上分析，將計算Hausdorff維數(shù)的思想與表示點云形狀屬性的需求相關(guān)聯(lián)，得出了點云維數(shù)的表達(dá)式dim=logrv=logr(dr3)=3+logrd 。其中r 為幾何體最小包圍球的半徑，v 為幾何體的體積，d 為比例系數(shù)，等號右邊第一項“3”為拓?fù)渚S數(shù)，第二項表示半徑為r 的包圍球尺度下的形狀特征參量[19]。用上述點云維數(shù)表達(dá)式來定義點云數(shù)據(jù)中形狀的復(fù)雜程度。

2.1 點云維數(shù)計算

維數(shù)值用來表示點云形成的局部表面的粗糙程度，因此用維數(shù)可以區(qū)分點云數(shù)據(jù)各點處的不同形狀。計算點云維數(shù)的算法如算法1所示。

算法1 計算點云維數(shù)

輸入：點云集合X={x1,x2,…,xi,…,xn}。

輸出：點云維數(shù)集合Dim={verDim(1),verDim(2),…,verDim(i),…,verDim(n)}，其中verDim(i) 表示第i 個點的維數(shù)值。

針對點云X 中的每個點xi做如下操作：

（1）計算xi的k 近鄰集合N(xi)，計算N(xi)的最小包圍球半徑r；

（2）將N(xi)中的對象進(jìn)行四面體剖分，得到一組四面體集合tr={s1,s2,…,si,…,sm}；

（4）計算點xi的維數(shù)值verDim(i)=logrsumV 。

鄰域選取方法：k 一般取值為10至50之間；當(dāng)點云形成的局部表面比較平滑，凹凸變化不明顯時，k 取值較大；反之，k 取值較小。

2.2 特征點提取

點云中各點的維數(shù)值表示了局部表面的粗糙程度，因此通過維數(shù)值可以將點云中的形狀特征點提取出來。通過大量實驗數(shù)據(jù)證明，點云數(shù)據(jù)中的特征主要分布在維數(shù)直方圖的左右拐點兩側(cè)。而維數(shù)值大于右側(cè)拐點的部分主要分布的是點云數(shù)據(jù)的邊界特征點，維數(shù)值小于左側(cè)拐點的部分主要分布的是點云數(shù)據(jù)內(nèi)部的特征點。

如圖2所示，點云數(shù)據(jù)維數(shù)分布直方圖用棕色和藍(lán)色兩部分表示，提取的特征點的維數(shù)分布用棕色部分表示。點云數(shù)據(jù)維數(shù)分布直方圖中棕色與藍(lán)色交界處的維數(shù)值為左側(cè)拐點，左側(cè)拐點處的維數(shù)值為臨界值DimBound 。點云數(shù)據(jù)內(nèi)部形狀特征點分布在維數(shù)值小于維數(shù)分布直方圖的左側(cè)拐點處的點。特征點集合featurePoints 表示為：

2.3 特征點進(jìn)行密度聚類

用基于密度聚類算法[20]將提取出的特征點進(jìn)行聚類?；诿芏鹊木垲愃惴?，通過特征點分布的緊密程度來確定聚類結(jié)構(gòu)。聚類算法參數(shù)包含鄰域內(nèi)對象數(shù)量最小值MinPts 以及鄰域半徑Radius。

MinPts 的計算方法：MinPts 的確定依賴于數(shù)據(jù)集中對象的數(shù)量，當(dāng)數(shù)據(jù)集中的對象為有限個時，MinPts=integer(m/25)[21]。其中m 是數(shù)據(jù)集中對象的數(shù)量，integer表示取整運算。當(dāng)數(shù)據(jù)集中對象很多時，MinPts=20[21]。點云中特征點聚類時，一般設(shè)置MinPts=20。

鄰域半徑Radius 的計算方法：Radius 是依據(jù)距離計算得到的。例如一個數(shù)據(jù)集A(m×n)，即數(shù)據(jù)集A 中有m 個n 維的數(shù)據(jù)對象。在與數(shù)據(jù)集A 相同的數(shù)據(jù)分布范圍內(nèi)模擬m 個均勻分布的對象，將模擬形成的數(shù)據(jù)集合記作B。計算B 中每個對象bi的第k 個近鄰點與對象bi的歐式距離，此處k=MinPts。接下來將m個距離值從小到大排序，Radius 為距離排序中位于95%[21]位置上對應(yīng)的距離值。因為此處提取的特征點，相對于一般的聚類數(shù)據(jù)，類與類之間區(qū)分明顯，類內(nèi)數(shù)據(jù)比較集中，因此需要增設(shè)另外一個參數(shù)RTimes，表示Radius的倍數(shù)值，此處實際的鄰域半徑為Radius×RTimes。

當(dāng)特征點分布比較明顯、集中時，MinPts 值較大，RTimes(RTimes ∈(0,1])較??；當(dāng)特征點分布略顯分散時，參數(shù)值MinPts 較小，另一個參數(shù)值RTimes(RTimes ∈(0,1])較大。密度聚類算法如算法2所示。

算法2 密度聚類算法

輸入：點云數(shù)據(jù)集合X={x1,x2,…,xi,…,xn}；鄰域參數(shù)(RTimes,MinPts)。

輸出：類劃分，即點云數(shù)據(jù)聚類后形成的類集合C={c1,c2,…,ci,…,cs},ci表示第i 類。

圖2 點云維數(shù)分布以及特征點維數(shù)分布

針對數(shù)據(jù)集合X 做如下操作：

（1）確定X 中的核心對象集合Ω ：

num(N(xi))＞MinPts

其中，num(N(xi))表示點xi的鄰域半徑內(nèi)鄰域點的數(shù)量。若點xi的鄰域半徑內(nèi)鄰域點數(shù)量大于MinPts，則點xi為核心對象，將點xi加入到核心對象集合Ω 中。

（2）將能夠連通[18]的每一組核心對象，以及到核心對象距離小于鄰域半徑的點都放到一起，形成一個類ci。

（3）針對所有的核心對象進(jìn)行（2）的操作，得到聚類結(jié)果。

2.4 獲取匹配點對

進(jìn)行點云配準(zhǔn)，經(jīng)常采用的幾何特征提取方法是將點云中的點鄰域擬合為局部二次曲面來獲得點云的法向量、高斯曲率等信息作為特征信息[6]。

該算法從點云的全局結(jié)構(gòu)進(jìn)行初始配準(zhǔn)，而不是根據(jù)點云的局部信息進(jìn)行配準(zhǔn)。特征點經(jīng)過密度聚類后，獲得每一類的質(zhì)心，類質(zhì)心表示點云數(shù)據(jù)中某一局部位置信息。所有的類質(zhì)心代表了點云中特征點的全局結(jié)構(gòu)。根據(jù)特征點形成的全局結(jié)構(gòu)，尋找相同的結(jié)構(gòu)來獲得匹配點對。從原點云類質(zhì)心集合中任意選取三個類質(zhì)心對象，構(gòu)建三角形；從目標(biāo)點云類質(zhì)心集合中任選三個對象，構(gòu)建三角形；通過比較構(gòu)建的兩個三角形是否全等，判斷是否具有相同的結(jié)構(gòu)，是否是匹配點對。獲取匹配點對的算法如算法3所示。

算法3 獲取匹配點對

輸入：原點云類質(zhì)心集合CenterSrc={cs1,cs2,…,csi,…,css}；目標(biāo)點云類質(zhì)心集合CenterDst={cd1,cd2,…,cdi,…,cdq}。

輸出：三對匹配點對。

（1）通過組合思想從CenterSrc 中任取三個對象，構(gòu)建出原點云的三角形索引集合IndexSrc={inSrc1,inSrc2,…,inSrci,…}；同理得到目標(biāo)點云的三角形索引集合IndexDst={inDst1,inDst2,…,inDsti,…}。

（2）構(gòu)建三角形信息。三角形信息包括頂點坐標(biāo)、頂點的對邊長度；計算三角形索引集合IndexSrc 和IndexDst 中每個三角形的信息，得到原點云三角形集合TrSrc={trSrc1,trSrc2,…,trSrci,…}和目標(biāo)點云三角形集合TrDst={trDst1,trDst2,…,trDsti,…}。

（3）判斷TrSrc 與TrDst 中是否存在全等三角形。三角形全等的判斷過程：依次比較三角形trSrci與trDsti中三條對應(yīng)邊的差值比例是否在閾值參數(shù)內(nèi)，滿足條件則認(rèn)為是全等三角形對。

（4）從獲得的全等三角形對中選擇差值比例和最小的作為最終的全等三角形對，對應(yīng)的三個頂點為匹配點對。

2.5 計算變換矩陣

由三個三維對應(yīng)點對求解變換矩陣，變換矩陣包括旋轉(zhuǎn)矩陣R 和平移向量t 。變換矩陣的計算采用直接計算法[22]。計算變換矩陣的算法如算法4所示。將原點云經(jīng)過估計變換矩陣R 和t 變換后，得到初始配準(zhǔn)后的點云數(shù)據(jù)。

算法4 計算變換矩陣

輸入：原點云中的點srcData={p1,p2,p3}，目標(biāo)點云中的對應(yīng)點dstData={p11,p22,p33}。其中p1的對應(yīng)點是p11,p2的對應(yīng)點是p22,p3的對應(yīng)點是p33。

輸出：旋轉(zhuǎn)矩陣R 和平移向量t。

（1）計算原點云p1、p2、p3構(gòu)成的三角形的重心q1；計算由p1、p2、p3三點構(gòu)成的三角形的單位法向量n1；過重心q1，沿著單位法向量n1方向，取長度為1的點p4。

（2）將srcData 所在的坐標(biāo)原點移動到p4點，得到三點的坐標(biāo)記作s1、s2、s3。

（3）同理，對目標(biāo)點云進(jìn)行上述（1）、（2）操作，將目標(biāo)點云得到的三點坐標(biāo)記作t1、t2、t3。

（4）計算旋轉(zhuǎn)矩陣R：

(t1t2t3)=R×(s1s2s3)

R=(t1t2t3)×inv((s1s2s3))

其中inv((s1s2s3))表示矩陣(s1s2s3)的逆矩陣。

（5）計算平移向量t。已知旋轉(zhuǎn)矩陣R 和原點云與目標(biāo)點云中的任意一對對應(yīng)點si和ti，則有：

ti=R×si+t

3 點云細(xì)配準(zhǔn)

完成上述初始配準(zhǔn)過程后，得到的點云結(jié)果繼續(xù)采用剪枝ICP[11]細(xì)配準(zhǔn)算法進(jìn)行配準(zhǔn)，得到最終的點云配準(zhǔn)結(jié)果。

4 實驗結(jié)果與分析

實 驗 環(huán) 境 為Windows7 操 作 系 統(tǒng)，CPU 為Intel?Pentium?CPU G840@2.80 GHz，內(nèi)存為8 GB。程序使用Matlab編寫。為了驗證該算法的可行性和有效性，實驗采用斯坦福大學(xué)計算機圖形學(xué)實驗室獲取的bunny、dragon、Armadillo、happyStandRight 點云數(shù)據(jù)。實驗分兩種情況進(jìn)行測試：一種是重疊率高的點云數(shù)據(jù)模型；另一種是重疊率低的點云數(shù)據(jù)模型。

4.1 重疊率高的點云數(shù)據(jù)模型實驗

為測試該算法能夠?qū)χ丿B率高的點云數(shù)據(jù)進(jìn)行配準(zhǔn)，采用重疊率在90%左右的點云數(shù)據(jù)進(jìn)行測試。

實驗采用斯坦福大學(xué)計算機圖形學(xué)實驗室獲取的bunny000、bunny045 點云數(shù)據(jù)，點云數(shù)據(jù)的維數(shù)分布直方圖、特征點、特征點聚類結(jié)果以及配準(zhǔn)結(jié)果等具體實驗過程如圖3所示。

圖3：（a）中藍(lán)色與棕色兩部分是bunny000 點云數(shù)據(jù)的維數(shù)分布直方圖，直方圖中棕色部分為bunny000中特征點的維數(shù)分布；（b）為bunny000 提取的特征點，其中紅色為bunny000 點云數(shù)據(jù)，綠色為bunny000 中提取的特征點；（c）為bunny000 特征點聚類結(jié)果，聚類結(jié)果為8類，類與類之間用空間距離和顏色進(jìn)行區(qū)別，其中每一類的類質(zhì)心用黑色的實心點表示；（d）為bunny045維數(shù)分布直方圖；（e）為bunny045特征點提取結(jié)果；（f）為bunny045 特征點聚類結(jié)果，聚類結(jié)果為12 類；（g）為bunny000 與bunny045 的初始位姿；（h）為bunny000 與bunny045 的初始配準(zhǔn)結(jié)果；（i）為bunny000 與bunny045的細(xì)配準(zhǔn)結(jié)果。

按照上述實驗過程，同時對ArmadilloBack_120、ArmadilloBack_150，dragonStandRight_0、dragonStandRight_24，ArmadilloBack_0、ArmadilloBack_30 點云數(shù)據(jù)進(jìn)行實驗，實驗結(jié)果如圖4、圖5、圖6所示。上述點云數(shù)據(jù)的配準(zhǔn)性能如表1所示。

圖3 bunny000與bunny045維數(shù)分布、特征點聚類以及配準(zhǔn)結(jié)果

圖6 ArmadilloBack_0、ArmadilloBack_30配準(zhǔn)結(jié)果

由圖中的實驗結(jié)果可以證明，對于重疊率較高的點云數(shù)據(jù)，本文提出的算法具有良好的配準(zhǔn)效果。配準(zhǔn)時間與維數(shù)計算和由組合算法形成的三角形個數(shù)有關(guān)。由于聚類后的類數(shù)量有限，因此配準(zhǔn)時間主要用于維數(shù)計算。影響維數(shù)計算有兩個因素：點云模型中的點數(shù)量以及維數(shù)計算時k 近鄰值的選擇。當(dāng)點云中點數(shù)量相同時，k 值越小，維數(shù)計算時間越短；k 值越大，維數(shù)計算時間越長。bunny000與bunny045點云形成的局部表面比較平滑，凹凸變化不太明顯，k 取值較大；dragon-StandRight_0與dragonStandRight_24點云形成的局部表面凹凸變化比較明顯，k 取值較小。因此當(dāng)點數(shù)量比較接近時，bunny000 與bunny045 的配準(zhǔn)時間比dragon-StandRight_0與dragonStandRight_24的配準(zhǔn)時間長。

表1 重疊率高的點云模型的配準(zhǔn)性能

4.2 重疊率低的點云數(shù)據(jù)模型實驗

經(jīng)過大量實驗證明，當(dāng)點云數(shù)據(jù)之間的重疊率低于45%時，點云數(shù)據(jù)之間的相同結(jié)構(gòu)存在的可能性較低。因此該算法適用重疊率約在45%以上的點云數(shù)據(jù)之間的配準(zhǔn)。

實驗結(jié)果展示部分選取了幾個具有代表性的較為復(fù)雜的點云數(shù)據(jù)模型，這些點云模型之間的重疊率約為45%。斯坦福大學(xué)計算機圖形學(xué)實驗室獲取的bunny045、bunny090 點云數(shù)據(jù)，對應(yīng)的角度分別為45°、90°；ArmadilloOnHeadMultiple_180、ArmadilloOnHeadMultiple_270點云數(shù)據(jù)（簡記為Armadillo_180、Armadillo_270），對應(yīng)的角度分別為180°、270°；happyStandRight_48、happyStandRight_96點云數(shù)據(jù)（簡記為happy_48、happy_96），對應(yīng)的角度分別為48°、96°。

圖7 bunny045、bunny090點云數(shù)據(jù)配準(zhǔn)結(jié)果

同時該算法的初始配準(zhǔn)結(jié)果與另兩種算法分別進(jìn)行了對比：一種是通過多尺度鄰域信息來獲得對應(yīng)中心點的一組法向量信息，通過法向量等信息作為快速描述符（fastDesp）進(jìn)行初始配準(zhǔn)[6]。由于文獻(xiàn)[6]算法的細(xì)配準(zhǔn)也是采用剪枝ICP[11]算法，與本文算法的細(xì)配準(zhǔn)過程相同，因此將本文算法的初始配準(zhǔn)結(jié)果與fastDesp 的初始配準(zhǔn)算法結(jié)果進(jìn)行對比。另一種算法是Go-ICP算法[2]。

實驗結(jié)果如圖7、圖8、圖9所示。各實驗結(jié)果圖中（b）是本文算法初始配準(zhǔn)結(jié)果，（c）是本文算法細(xì)配準(zhǔn)結(jié)果，（d）是采用fastDesp[6]算法進(jìn)行初始配準(zhǔn)的結(jié)果，（e）是Go-ICP[2]算法配準(zhǔn)結(jié)果。三組點云數(shù)據(jù)的配準(zhǔn)性能如表2所示。

bunny045 與bunny090 的配準(zhǔn)結(jié)果：圖7（a）中第一行綠色圖表示bunny045 的初始位姿，點云角度為45°，紅色圖表示bunny090的初始位姿，點云角度為90°，兩片點云數(shù)據(jù)的重疊率大約為45%，第二行的圖為bunny045與bunny090 在一個坐標(biāo)系下的初始位姿；圖7（b）中兔子耳朵的對應(yīng)位置大致正確，圖7（b）本文算法初始配準(zhǔn)后的位姿差異明顯小于圖7（d）初始配準(zhǔn)算法[2]和圖7（e）Go-ICP算法[6]的位姿差異。

圖8 Armadillo_180、Armadillo_270點云數(shù)據(jù)配準(zhǔn)結(jié)果

Armadillo_180與Armadillo_270的配準(zhǔn)結(jié)果：圖8（a）中第一行綠色圖表示Armadillo_270 的初始位姿，點云角度為270°，紅色圖表示Armadillo_180的初始位姿，點云角度為180°，兩片點云的重疊率大約為45%，第二行為Armadillo_180與Armadillo_270在一個坐標(biāo)系下的初始位姿；圖8（b）本文算法初始配準(zhǔn)結(jié)果明顯優(yōu)于圖8（e）Go-ICP算法[6]的配準(zhǔn)結(jié)果，但是由于k 值的選取不夠精確，Armadillo_180 與Armadillo_270 特征點的選取不夠精確，會存在少部分的遺漏，對應(yīng)點對會存在誤差，配準(zhǔn)結(jié)果存在上下的錯位，因此本文算法的初始配準(zhǔn)效果沒有圖8（d）初始配準(zhǔn)算法[2]效果好。

圖9 happy_48、happy_96點云數(shù)據(jù)配準(zhǔn)結(jié)果

表2 重疊率低的點云模型配準(zhǔn)性能

happy_48 與happy_96 的配準(zhǔn)結(jié)果：圖9（a）中第一行綠色圖表示happy_48 的初始位姿，點云角度為48°，紅色圖表示happy_96的初始位姿，點云角度為96°，兩片點云的重疊率約為45%，第二行為happy_48與happy_96在一個坐標(biāo)系下的初始位姿；圖9（b）初始配準(zhǔn)結(jié)果中happy_48與happy_96的頭部上方部位之間的角度差異明顯變小，位置上存在上下之間的錯位，但對應(yīng)大致是正確的，同時happy_48 與happy_96 的身體側(cè)面部位之間的對應(yīng)大致是正確的；圖9（d）與圖9（e）兩種算法的配準(zhǔn)結(jié)果中happy_48與happy_96的頭部上方部位仍然存在很大的角度差異，同時身體側(cè)面部位也存在很大的角度差異，能明顯看出圖9（b）的配準(zhǔn)結(jié)果優(yōu)于圖9（d）和圖9（e）的配準(zhǔn)結(jié)果。

通過上述三組對比實驗，可以得出本文算法的初始配準(zhǔn)結(jié)果能夠明顯縮小點云之間的位姿差異。

同時觀察上述實驗中圖7、圖8、圖9 中各自對應(yīng)的圖（c）本文算法的細(xì)配準(zhǔn)結(jié)果，可以得出本文算法對于角度差異大、重疊率低的點云數(shù)據(jù)能夠達(dá)到較好的配準(zhǔn)效果。

均方誤差的衡量標(biāo)準(zhǔn)是計算兩片點云中每對對應(yīng)點之間距離的平方和的均值。然而均方誤差中的對應(yīng)點是將一片點云中的點與另一片點云中距離最近的點作為對應(yīng)點來進(jìn)行選擇的。事實上，這種判斷對應(yīng)點的標(biāo)準(zhǔn)并不合理，尤其是針對bunny和happy這兩組實驗，當(dāng)點云重疊率低時真正的對應(yīng)點對數(shù)量較少，按照均方誤差中對應(yīng)點的選取標(biāo)準(zhǔn)會造成均方誤差值較大。例如happy_48 與happy_96 中，本文算法的細(xì)配準(zhǔn)結(jié)果明顯優(yōu)于初始配準(zhǔn)算法[2]的配準(zhǔn)結(jié)果，但是比較各自對應(yīng)的均方誤差發(fā)現(xiàn)，本文算法的細(xì)配準(zhǔn)結(jié)果的均方誤差大于初始配準(zhǔn)算法[2]的均方誤差。因此只用均方誤差來衡量配準(zhǔn)效果是不太合理的。表2 中本文算法比另外兩種算法配準(zhǔn)時間長，還需改進(jìn)提高。

本文算法根據(jù)分形維數(shù)屬性提取點云數(shù)據(jù)內(nèi)部的特征點，將這些特征點進(jìn)行聚類后，得到特征點之間的相對位置分布，通過三角形這種簡單結(jié)構(gòu)信息來尋找兩片點云中相同的相對位置分布，完成初始配準(zhǔn)。上述的實驗結(jié)果可以證明，對于重疊率45%以上，角度差異在45°范圍內(nèi)的點云數(shù)據(jù)之間的配準(zhǔn)，基于分形維數(shù)的全局點云初始配準(zhǔn)算法能夠有效縮小點云之間的位姿差異，更加有利于點云細(xì)配準(zhǔn)。

5 結(jié)束語

基于分形維數(shù)的全局點云初始配準(zhǔn)算法，將二維中的分形維數(shù)用于三維點云中進(jìn)行特征提取，不同于之前的曲率、法向量等點云特征提取方法；沒有采用點云的局部特征信息進(jìn)行配準(zhǔn)，從點云全局結(jié)構(gòu)進(jìn)行配準(zhǔn)。本文算法能夠?qū)Τ跏嘉蛔诵〉狞c云數(shù)據(jù)進(jìn)行有效配準(zhǔn)，同時對于初始位姿差異較大的點云數(shù)據(jù)，可以有效縮小點云之間的位姿差異，縮小點云之間的錯位，達(dá)到較好的配準(zhǔn)效果。

但是，本文算法也存在一定的缺陷：適用于點云局部表面有凹凸的情況，當(dāng)點云中存在大量平面時，此算法不適用。由于使用的是k 近鄰計算維數(shù)，維數(shù)計算所需時間較長。同時k 值的精確選取需要進(jìn)一步研究。