魯鐵定，袁志聰，鄭坤

(1.東華理工大學(xué)，南昌 330013；2.流域生態(tài)與地理環(huán)境監(jiān)測(cè)國(guó)家測(cè)繪地理信息局重點(diǎn)實(shí)驗(yàn)室，南昌 330013)

0 引言

隨著三維激光掃描技術(shù)的快速發(fā)展，三維重建技術(shù)的應(yīng)用越來(lái)越廣泛。點(diǎn)云配準(zhǔn)是三維模型重建中的關(guān)鍵環(huán)節(jié)，點(diǎn)云配準(zhǔn)按配準(zhǔn)步驟可分為初配準(zhǔn)和精配準(zhǔn)[1]。初配準(zhǔn)能夠很大程度上減小兩點(diǎn)云的旋轉(zhuǎn)和平移錯(cuò)位，為精配準(zhǔn)提供一個(gè)好的初始位置，提高配準(zhǔn)精度和效率。常用的初配準(zhǔn)[2-3]方法有主成分分析法、標(biāo)簽法、中心重合法、4PCS算法[4-5]等。精配準(zhǔn)是在初配準(zhǔn)的基礎(chǔ)上對(duì)點(diǎn)云進(jìn)行精確配準(zhǔn)，使兩點(diǎn)云盡可能地重合，即兩點(diǎn)云的距離之和最小。應(yīng)用最廣的精配準(zhǔn)方法是由Besl和Mkcya提出的最近點(diǎn)迭代[6-7](ICP)算法。

近年來(lái)，Nicolas Mellado等[8-10]提出的Super 4PCS算法逐漸得到人們的關(guān)注。相對(duì)于4PCS算法，Super 4PCS算法利用智能索引極大地提高了點(diǎn)云初配準(zhǔn)的速率[11]，同時(shí)Super 4PCS也存在一些不足，當(dāng)點(diǎn)云本身具有堆成性時(shí)容易出現(xiàn)錯(cuò)誤匹配等。Rongchun Zhang等[12]結(jié)合Super 4PCS算法與旋轉(zhuǎn)影像完成點(diǎn)云配準(zhǔn)，利用旋轉(zhuǎn)影像對(duì)Super 4PCS算法進(jìn)行了優(yōu)化。

針對(duì)Super 4PCS算法的不足，本文通過(guò)結(jié)合3D-SIFT[13-14]算法與Super 4PCS算法進(jìn)行點(diǎn)云配準(zhǔn)，利用3D-SIFT算法提取特征點(diǎn)，將整片點(diǎn)云縮至特征點(diǎn)集，縮短點(diǎn)對(duì)提取時(shí)間，同時(shí)提高點(diǎn)對(duì)提取的準(zhǔn)確率，最后設(shè)計(jì)了實(shí)驗(yàn)，比分析了相關(guān)算法的配準(zhǔn)性能。

1 Super 4PCS算法原理

1.1 4PCS算法原理

4PCS算法亦稱(chēng)為四點(diǎn)魯棒快速匹配算法，是一種全局快速匹配算法，其原理為：假設(shè)點(diǎn)云P，Q分別為源點(diǎn)云和目標(biāo)點(diǎn)云，4PCS算法以共面不共線的四點(diǎn)作為配準(zhǔn)點(diǎn)基，首先在點(diǎn)云P中選取4個(gè)共面不共線的點(diǎn)作為點(diǎn)基(點(diǎn)基稱(chēng)作C)，如圖1(a)所示，在P中選取的4點(diǎn)必須是P，Q重疊區(qū)域的點(diǎn)，然后在Q中利用點(diǎn)對(duì)間的距離與仿射不變性質(zhì)尋找所有近似全等的點(diǎn)基集合D，D={D1，D2，D3，…，Dn}。由于目標(biāo)點(diǎn)云中有很多點(diǎn)對(duì)并不符合要求，如圖1(b)所示，q′1q′2屬于錯(cuò)誤匹配點(diǎn)對(duì)，q′1q′2與q3q4之間的角度不符合要求，利用C與Di進(jìn)行剛體運(yùn)動(dòng)估計(jì)，得到二者的剛體變換Ti，即對(duì)P進(jìn)行Ti變換后，Ti(P)與Q之間歐式距離平方和最小。

4PCS算法具有較好的配準(zhǔn)精度，但是其時(shí)間復(fù)雜度達(dá)到了二次，效率不高。

圖1 點(diǎn)云與目標(biāo)點(diǎn)云點(diǎn)基

1.2 Super 4PCS算法配準(zhǔn)原理

在Super 4PCS[8]算法中，利用球體提取點(diǎn)對(duì)，大大提高了點(diǎn)對(duì)提取的效率。在點(diǎn)云Q中，以qi(i=1，2，…n)，為球心，半徑為r做球面，圖2(a)為二維表達(dá)形式，在Q中可做n個(gè)球面，形成球面集合，給定一誤差限ε，落在區(qū)間[r-ε，r+ε]上的點(diǎn)都符合要求，如圖2(a)中藍(lán)色點(diǎn)所示。將點(diǎn)云Q進(jìn)行不斷剖分，以陣列存儲(chǔ)落在區(qū)間[r-ε，r+ε]上的點(diǎn)(圖2(b))，圖中藍(lán)色點(diǎn)為提取的點(diǎn)對(duì)，黑色點(diǎn)為不符合要求的點(diǎn)，點(diǎn)對(duì)提取之后，利用仿射不變性質(zhì)在Q中提取與p1p2p3p4對(duì)應(yīng)的q1q2q3q4，令p1p2為r1，p3p4為r2，記Q中對(duì)應(yīng)r1的點(diǎn)對(duì)集合為S1，對(duì)應(yīng)r2集合的點(diǎn)對(duì)為S2，對(duì)S1S2中任意點(diǎn)對(duì)，計(jì)算并存儲(chǔ)對(duì)應(yīng)的方向向量。利用仿射不變性質(zhì)都能求得一交點(diǎn)e(圖2(c))，根據(jù)方向向量以及角度θ，給定區(qū)間[r-ε，r+ε]，即可在Q中獲得唯一的四點(diǎn)，如圖2(d)所示。

2 改進(jìn)Super 4PCS算法原理

2.1 3D-SIFT算法原理

尺度不變特征轉(zhuǎn)換特征提取算法(sale ivariant fature tansform，SIFT)最先應(yīng)用在圖像處理中。3D-SIFT算法是由二維的SIFT[15]算法轉(zhuǎn)換而來(lái)的，利用點(diǎn)云的曲率值代替二維圖像的強(qiáng)度值，建立體素的尺度空間來(lái)提取特征點(diǎn)，3D-SIFT算法的主要原理[13]如下：

①建立點(diǎn)云的尺度空間。在三維點(diǎn)云空間中，通過(guò)體素柵格的方式建立點(diǎn)云體素金字塔，給定體素柵格的大小，求得體素所包含點(diǎn)云的重心，以其重心近似代替該體素內(nèi)所包含的點(diǎn)云，可用公式表達(dá)為：

(1)

式中：Ii(x，y，z，σ)為第i個(gè)體素柵格點(diǎn)云數(shù)據(jù)的重心坐標(biāo)；pk為第i個(gè)體素柵格中第k個(gè)點(diǎn)的三維坐標(biāo)；n為第i個(gè)體素柵格中點(diǎn)的數(shù)量；Ii(x，y，z，σ)組成的集合為原點(diǎn)云在尺度下σ下的采樣點(diǎn)云。

圖2 Super 4PCS算法點(diǎn)基提取

②建立點(diǎn)云高斯差分尺度空間。在步驟①中構(gòu)建了點(diǎn)云的體素金字塔，設(shè)金字塔共有m組，每組有S層，則第s層的尺度為：

(2)

式中：σ0為點(diǎn)云的初始尺度；σs為點(diǎn)云金字塔第s層的尺度。

計(jì)算每個(gè)高斯空間尺度下采樣點(diǎn)的高斯過(guò)濾響應(yīng)值F，以及采樣點(diǎn)相鄰尺度的高斯差分值DOG。對(duì)采樣點(diǎn)及距離3σ鄰域范圍內(nèi)的點(diǎn)進(jìn)行曲率值高斯加權(quán)，高斯過(guò)濾響應(yīng)值F和DOG高斯差分值的計(jì)算公式可表示為：

(3)

(4)

DOG=F-Fpre

(5)

式中：ρi為采樣點(diǎn)第i個(gè)近鄰點(diǎn)的曲率；wi的表達(dá)式如式(4)所示，d為采樣點(diǎn)到鄰域點(diǎn)的距離；σ為當(dāng)前尺度空間的大小；式(5)中Fpre為上一尺度的高斯過(guò)濾響應(yīng)值。

③檢測(cè)DOG尺度空間極值點(diǎn)。若某點(diǎn)的DOG值相比其鄰域范圍內(nèi)的點(diǎn)的DOG值為極值，以及相鄰上下2個(gè)尺度鄰域范圍內(nèi)的DOG相比仍為極值，確保其在點(diǎn)云空間與尺度空間均為極值點(diǎn)，則記該點(diǎn)為特征點(diǎn)。

2.2 結(jié)合SIFT特征點(diǎn)的Super 4PCS算法

Super 4PCS算法具有很快的配準(zhǔn)速度，但當(dāng)點(diǎn)云具有對(duì)稱(chēng)性時(shí)(見(jiàn)算例2)，Super 4PCS算法點(diǎn)對(duì)識(shí)別易出錯(cuò)，針對(duì)以上問(wèn)題，提出了一種結(jié)合點(diǎn)云SIFT特征的Super 4PCS算法，其主要步驟可描述為：

①源點(diǎn)云與目標(biāo)點(diǎn)云的SIFT特征提取，利用3D-SIFT算法能直接對(duì)點(diǎn)云進(jìn)行特征點(diǎn)提取，將點(diǎn)云縮至特征點(diǎn)集，保留點(diǎn)云的主要成分，降低點(diǎn)云噪聲對(duì)配準(zhǔn)結(jié)果的影響，更加凸顯點(diǎn)云的局部特征。

②以提取的SIFT特征點(diǎn)作為Super 4PCS算法的輸入點(diǎn)云，特征點(diǎn)是目標(biāo)的特征部分，易于提取與識(shí)別，能提高Super 4PCS算法同名點(diǎn)對(duì)的識(shí)別度，不用遍歷原先整片點(diǎn)云，搜索源點(diǎn)云與目標(biāo)點(diǎn)云的特征點(diǎn)即可，減少點(diǎn)對(duì)搜索的時(shí)間，使點(diǎn)對(duì)匹配更加準(zhǔn)確。

③經(jīng)過(guò)Super 4PCS算法點(diǎn)對(duì)提取后，在源點(diǎn)云中選取一定數(shù)量的采樣點(diǎn)，對(duì)采樣點(diǎn)進(jìn)行剛體變換。以采樣點(diǎn)與目標(biāo)點(diǎn)云中最近點(diǎn)距離之和作為評(píng)價(jià)分?jǐn)?shù)值，選取評(píng)價(jià)分?jǐn)?shù)值最小的剛體變換參數(shù)作為最終的變換參數(shù)，實(shí)現(xiàn)源點(diǎn)云與目標(biāo)點(diǎn)云的配準(zhǔn)。

④通過(guò)配準(zhǔn)后同名點(diǎn)的均方根誤差來(lái)評(píng)價(jià)點(diǎn)云配準(zhǔn)精度，公式為：

(6)

式中：Xi為源點(diǎn)云與目標(biāo)點(diǎn)云的第i對(duì)同名點(diǎn)的坐標(biāo)差值；n為對(duì)應(yīng)點(diǎn)的個(gè)數(shù)。

本文算法的技術(shù)路線圖如圖3所示。

圖3 本文算法技術(shù)路線圖

3 實(shí)驗(yàn)與分析

3.1 經(jīng)典斯坦福兔子點(diǎn)云配準(zhǔn)

為了驗(yàn)證本文算法的性能，以標(biāo)準(zhǔn)斯坦福兔子作為實(shí)驗(yàn)數(shù)據(jù)，對(duì)比分析SIFT算法、Super 4PCS算法以及本文算法的配準(zhǔn)效果；相關(guān)結(jié)果如圖4所示(配準(zhǔn)結(jié)果由Geomagic studio 2013軟件顯示)，黑色點(diǎn)云為源點(diǎn)云，藍(lán)色點(diǎn)云為目標(biāo)點(diǎn)云。

圖4 斯坦福兔子點(diǎn)云配準(zhǔn)結(jié)果

由圖4(a)可知，兩點(diǎn)云既存在平移位錯(cuò)又存在旋轉(zhuǎn)位錯(cuò)，直接利用ICP算法配準(zhǔn)無(wú)法達(dá)到預(yù)期配準(zhǔn)效果；圖4(b)為提取的同名特征點(diǎn)，可以看出斯坦福兔子的輪廓基本被提取出來(lái)。根據(jù)同名點(diǎn)可以直接估計(jì)出點(diǎn)云的剛體變換參數(shù)，配準(zhǔn)結(jié)果如圖4(c)所示，可以看出兩點(diǎn)云基本重合，為ICP精確配準(zhǔn)提供了一個(gè)良好的初始位置。圖4(d)為ICP精配準(zhǔn)結(jié)果，經(jīng)過(guò)ICP配準(zhǔn)后，兩點(diǎn)云實(shí)現(xiàn)了精確配準(zhǔn)。圖4(e)為Super 4PCS算法的配準(zhǔn)結(jié)果，可看出配準(zhǔn)后縮小了兩點(diǎn)云間的差距；圖4(f)為ICP精配準(zhǔn)結(jié)果，精配準(zhǔn)后，兩點(diǎn)云間的差距進(jìn)一步縮小。圖4(g)為結(jié)合特征點(diǎn)的Super 4PCS算法配準(zhǔn)結(jié)果，以提取的SIFT特征點(diǎn)作為輸入數(shù)據(jù)，再通過(guò)Super 4PCS算法求解剛體變換，可看出兩點(diǎn)云的旋轉(zhuǎn)和平移位錯(cuò)基本消除，源點(diǎn)云與目標(biāo)點(diǎn)云分布均勻。與其他兩種算法配準(zhǔn)效果基本相當(dāng)，圖4(h)為ICP精配準(zhǔn)結(jié)果，可以看出源點(diǎn)云與目標(biāo)點(diǎn)云已經(jīng)完全重合在一起。從斯坦福兔子配準(zhǔn)的視覺(jué)效果來(lái)看，3種算法配準(zhǔn)結(jié)果基本相當(dāng)。

表1給出了3種配準(zhǔn)方法的速度與精度指標(biāo)，從配準(zhǔn)時(shí)間來(lái)看，由于SIFT算法需要先確定兩點(diǎn)云初始對(duì)應(yīng)關(guān)系，初始對(duì)應(yīng)關(guān)系確定后往往存在錯(cuò)誤的對(duì)應(yīng)關(guān)系，刪除錯(cuò)誤的對(duì)應(yīng)關(guān)系也要花費(fèi)大量時(shí)間，增加了算法的時(shí)間復(fù)雜度，所以，SIFT算法配準(zhǔn)速度最慢。Super 4PCS算法快于SIFT算法，耗時(shí)1.54 s；本文算法在特征提取等預(yù)處理階段需要花費(fèi)一定時(shí)間，但后期具有更快的配準(zhǔn)速度，僅花費(fèi)0.3 s就完成了配準(zhǔn)。本文算法配準(zhǔn)后ICP精配準(zhǔn)耗時(shí)2.50 s，Super 4PCS算法配準(zhǔn)后ICP精配準(zhǔn)耗時(shí)2.65 s，SIFT算法配準(zhǔn)后ICP精配準(zhǔn)耗時(shí)2.15 s；從配準(zhǔn)精度來(lái)看，以均方根誤差作為評(píng)價(jià)指標(biāo)，由于是標(biāo)準(zhǔn)的模型數(shù)據(jù)，3種方法配準(zhǔn)精度都很高，都達(dá)到了mm級(jí)，SIFT算法利用抽樣一致性算法刪除了錯(cuò)誤點(diǎn)對(duì)，配準(zhǔn)精度最高；本文算法配準(zhǔn)精度為2 mm，優(yōu)于Super 4PCS算法配準(zhǔn)精度。經(jīng)過(guò)ICP精確配準(zhǔn)后，三者的配準(zhǔn)精度達(dá)到了10-5數(shù)量級(jí)，實(shí)現(xiàn)了源點(diǎn)云與目標(biāo)點(diǎn)云的精確配準(zhǔn)。

表1 斯坦福兔子配準(zhǔn)結(jié)果

3.2 亭子點(diǎn)云配準(zhǔn)

為了進(jìn)一步驗(yàn)證本文算法應(yīng)用在實(shí)測(cè)數(shù)據(jù)上的性能，以實(shí)測(cè)的亭子為例，現(xiàn)分別用SIFT算法、Super 4PCS算法和結(jié)合2種算法的方法(S-Super 4PCS)對(duì)點(diǎn)云進(jìn)行拼接，配準(zhǔn)結(jié)果如圖5所示，黑色點(diǎn)云為源點(diǎn)云，藍(lán)色點(diǎn)云為目標(biāo)點(diǎn)云。

圖5 亭子配準(zhǔn)結(jié)果

如圖5(a)所示，源點(diǎn)云與目標(biāo)點(diǎn)云存在很大的旋轉(zhuǎn)和平移位錯(cuò)；圖5(b)為亭子出口的實(shí)景圖，作為配準(zhǔn)結(jié)果的參照?qǐng)D；圖5(c)為源點(diǎn)云與目標(biāo)點(diǎn)云的SIFT同名特征點(diǎn)，3D-SIFT算法有效地提取了源點(diǎn)云與目標(biāo)點(diǎn)云的特征部分，將整個(gè)點(diǎn)云數(shù)據(jù)集縮小至特征點(diǎn)集；圖5(d)為SIFT算法的配準(zhǔn)結(jié)果，可看出亭子頂部仍然存在錯(cuò)位，由于數(shù)據(jù)為實(shí)測(cè)的數(shù)據(jù)，不可避免的存在噪聲，且源點(diǎn)云與目標(biāo)點(diǎn)云嚴(yán)格的同名點(diǎn)可能并不存在，導(dǎo)致其配準(zhǔn)效果并不是太好；圖5(e)為SIFT算法配準(zhǔn)結(jié)果亭子出口部位的放大圖，可看出亭子的臺(tái)階并沒(méi)有重合在一起；圖5(f)為Super 4PCS算法的配準(zhǔn)結(jié)果，由于亭子點(diǎn)云本身具有對(duì)稱(chēng)性，局部特征不明顯，出現(xiàn)了錯(cuò)誤匹配的結(jié)果。圖中紅色框區(qū)域?yàn)橥ぷ映隹?，?jīng)過(guò)Super 4PCS算法配準(zhǔn)后，源點(diǎn)云亭子出口部位匹配到目標(biāo)點(diǎn)云欄桿部位，在圖5(g)中可以看到紅色框中的黃色點(diǎn)云為一欄桿，并不是源點(diǎn)云亭子的出口；圖5(h)為結(jié)合3D-SIFT算法與Super 4PCS算法的配準(zhǔn)結(jié)果，可以看出，經(jīng)過(guò)本文方法配準(zhǔn)后，兩點(diǎn)云的旋轉(zhuǎn)和平移位錯(cuò)得到了改善，亭子頂端基本重合在一起，紅色框區(qū)域?qū)?yīng)源點(diǎn)云與目標(biāo)點(diǎn)云的亭子出口，實(shí)現(xiàn)了源點(diǎn)云與目標(biāo)點(diǎn)云的正確拼接，特征點(diǎn)集減弱了噪聲的影響，凸顯了點(diǎn)云數(shù)據(jù)集的局部特征，提高了點(diǎn)對(duì)匹配的準(zhǔn)確性；從圖5(i)的局部放大圖可看出，紅色框部分藍(lán)色點(diǎn)云與黃色點(diǎn)云對(duì)應(yīng)為亭子出口的階梯，二者重合效果優(yōu)于SIFT算法的配準(zhǔn)結(jié)果；圖5(j)、圖5(k)、圖5(l)為3種方法配準(zhǔn)后利用ICP精配準(zhǔn)的結(jié)果，經(jīng)過(guò)ICP配準(zhǔn)后，源點(diǎn)云與目標(biāo)點(diǎn)云的位錯(cuò)在初配準(zhǔn)上進(jìn)一步得到改善，從視覺(jué)效果來(lái)看，結(jié)合SIFT算法與Super 4PCS算法的配準(zhǔn)效果最優(yōu)。

表2為3種配準(zhǔn)方法對(duì)應(yīng)的定量指標(biāo)，從配準(zhǔn)時(shí)間來(lái)看，本文算法后期配準(zhǔn)耗時(shí)13.61 s，優(yōu)于Super 4PCS算法的35.82 s，遠(yuǎn)遠(yuǎn)快于SIFT算法的配準(zhǔn)速度；從配準(zhǔn)精度來(lái)看，本文算法的配準(zhǔn)精度為0.222 m，SIFT算法的配準(zhǔn)精度為0.231 m，本文算法效果更好，Super 4PCS算法出現(xiàn)了錯(cuò)誤配準(zhǔn)結(jié)果；相比Super 4PCS算法而言，本文算法將點(diǎn)云縮至特征點(diǎn)集，減弱了噪聲對(duì)配準(zhǔn)結(jié)果的影響，同時(shí)凸顯了點(diǎn)云的局部特征；本文算法初配準(zhǔn)后，利用ICP算法對(duì)點(diǎn)云進(jìn)行精確配準(zhǔn)，耗時(shí)3.63 s，配準(zhǔn)精度為2.6 cm，進(jìn)一步縮小了點(diǎn)云間的差距。

通過(guò)實(shí)測(cè)數(shù)據(jù)配準(zhǔn)結(jié)果表明，本文算法具有更好的配準(zhǔn)性能，驗(yàn)證了本文算法的可行性。

表2 亭子配準(zhǔn)結(jié)果

4 結(jié)束語(yǔ)

點(diǎn)云配準(zhǔn)是點(diǎn)云數(shù)據(jù)處理中的熱點(diǎn)問(wèn)題，針對(duì)傳統(tǒng)的配準(zhǔn)算法效率低等問(wèn)題，本文提出一種結(jié)合SIFT特征的Super 4PCS點(diǎn)云配準(zhǔn)方法，通過(guò)對(duì)源點(diǎn)云與目標(biāo)點(diǎn)云進(jìn)行特征提取，充分利用點(diǎn)云的局部特征，提高了Super 4PCS算法點(diǎn)對(duì)識(shí)別的準(zhǔn)確性；將源點(diǎn)云與目標(biāo)點(diǎn)云縮至特征點(diǎn)集，既保留了點(diǎn)云的主要成分，又縮短了點(diǎn)對(duì)的搜索時(shí)間，提高了算法的配準(zhǔn)效率；通過(guò)實(shí)驗(yàn)對(duì)比分析了SIFT算法、Super 4PCS算法以及本文算法在斯坦福兔子和實(shí)測(cè)點(diǎn)云數(shù)據(jù)上的配準(zhǔn)性能，本文算法在前期特征提取需要花費(fèi)一定時(shí)間，但后期具有更快的配準(zhǔn)速度，總體性能更優(yōu)，能為精配準(zhǔn)提供一個(gè)良好的初始位置。