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

封雪梅，張志毅，楊 龍

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

1 引言

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

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

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

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

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

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

圖1 算法流程圖

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

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

2.1 點(diǎn)云維數(shù)計(jì)算

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

算法1 計(jì)算點(diǎn)云維數(shù)

輸入：點(diǎn)云集合X={x1,x2,…,xi,…,xn}。

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

針對點(diǎn)云X 中的每個點(diǎn)xi做如下操作：

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

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

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

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

2.2 特征點(diǎn)提取

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

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

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

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

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

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

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

算法2 密度聚類算法

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

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

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

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

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

num(N(xi))＞MinPts

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

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

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

2.4 獲取匹配點(diǎn)對

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

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

算法3 獲取匹配點(diǎn)對

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

輸出：三對匹配點(diǎn)對。

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

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

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

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

2.5 計(jì)算變換矩陣

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

算法4 計(jì)算變換矩陣

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

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

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

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

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

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

(t1t2t3)=R×(s1s2s3)

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

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

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

ti=R×si+t

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 重疊率高的點(diǎn)云數(shù)據(jù)模型實(shí)驗(yàn)

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

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

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

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

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

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

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

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

4.2 重疊率低的點(diǎn)云數(shù)據(jù)模型實(shí)驗(yàn)

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

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

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

同時(shí)該算法的初始配準(zhǔn)結(jié)果與另兩種算法分別進(jìn)行了對比：一種是通過多尺度鄰域信息來獲得對應(yīng)中心點(diǎn)的一組法向量信息，通過法向量等信息作為快速描述符（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]。

實(shí)驗(yàn)結(jié)果如圖7、圖8、圖9所示。各實(shí)驗(yàn)結(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é)果。三組點(diǎn)云數(shù)據(jù)的配準(zhǔn)性能如表2所示。

bunny045 與bunny090 的配準(zhǔn)結(jié)果：圖7（a）中第一行綠色圖表示bunny045 的初始位姿，點(diǎn)云角度為45°，紅色圖表示bunny090的初始位姿，點(diǎn)云角度為90°，兩片點(diǎn)云數(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點(diǎn)云數(shù)據(jù)配準(zhǔn)結(jié)果

Armadillo_180與Armadillo_270的配準(zhǔn)結(jié)果：圖8（a）中第一行綠色圖表示Armadillo_270 的初始位姿，點(diǎn)云角度為270°，紅色圖表示Armadillo_180的初始位姿，點(diǎn)云角度為180°，兩片點(diǎn)云的重疊率大約為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 特征點(diǎn)的選取不夠精確，會存在少部分的遺漏，對應(yīng)點(diǎn)對會存在誤差，配準(zhǔn)結(jié)果存在上下的錯位，因此本文算法的初始配準(zhǔn)效果沒有圖8（d）初始配準(zhǔn)算法[2]效果好。

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

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

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

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

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

均方誤差的衡量標(biāo)準(zhǔn)是計(jì)算兩片點(diǎn)云中每對對應(yīng)點(diǎn)之間距離的平方和的均值。然而均方誤差中的對應(yīng)點(diǎn)是將一片點(diǎn)云中的點(diǎn)與另一片點(diǎn)云中距離最近的點(diǎn)作為對應(yīng)點(diǎn)來進(jìn)行選擇的。事實(shí)上，這種判斷對應(yīng)點(diǎn)的標(biāo)準(zhǔn)并不合理，尤其是針對bunny和happy這兩組實(shí)驗(yàn)，當(dāng)點(diǎn)云重疊率低時(shí)真正的對應(yīng)點(diǎn)對數(shù)量較少，按照均方誤差中對應(yīng)點(diǎn)的選取標(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)時(shí)間長，還需改進(jìn)提高。

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

5 結(jié)束語

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

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