陸尚鴻，李文國

(昆明理工大學(xué) 機電工程學(xué)院,云南 昆明 650500)

近年來，隨著計算機軟硬件設(shè)備不斷發(fā)展和三維掃描設(shè)備日趨完善，人們能夠較為輕松地獲取高精度的點云測量數(shù)據(jù)[1]。因此，基于點云的三維重建技術(shù)被逐漸應(yīng)用在地形測繪[2]、無人駕駛[3]、機器人技術(shù)[4]、虛擬現(xiàn)實[5]、逆向工程[6]、文物保護[7]等領(lǐng)域。由于測量環(huán)境、設(shè)備安裝角度和被測物體尺寸大小的限制，采集到的點云數(shù)據(jù)往往會出現(xiàn)部分特征和信息缺失的情況，所以需要從多個角度對物體表面進行多次數(shù)據(jù)采集。然后，將不同視角的點云數(shù)據(jù)合并到同一坐標系下，并通過坐標轉(zhuǎn)換使那些反映物體同一外貌特征的點集相互重合，形成一個完整的點云數(shù)據(jù)，這個過程就是點云配準[8]。點云的粗配準大體可分為基于全局搜索、概率統(tǒng)計和局部特征3類。

四點法(4-Points Congruent Sets，4PCS)[9]及其改進算法都屬于基于全局搜索的粗配準。這類算法會從源點云選擇一些共面的四點，根據(jù)仿射不變性原理從目標點云中尋找符合條件的四點集合，并求出之間的變換矩陣。超級四點法(Super Generalized 4-Points Congruent Sets，SG4PCS)[10]中加入了角度特征量，通過比對四點之間的夾角來加快原始點云和目標點云中對應(yīng)四點的匹配。基于關(guān)鍵點的四點法(Keypoint-based 4-Points Congruent Sets，K-4PCS)[11]采用關(guān)鍵點提取技術(shù)取代4PCS隨機共面四點采樣法，提高了算法計算速度。語義關(guān)鍵點四點法(Semantic Keypoint-based 4-Points Congruent Sets，SK-4PCS)[12]中加入了分層處理和特征點分類功能，在截面中提取到特征點后，根據(jù)交點、頂點等幾何特征對點進行分類，然后根據(jù)特征點類型優(yōu)化配準策略。這類算法粗配準精度較高，但配準速度普遍較慢，而且由于算法對源點云中共面四點的采樣具有隨機性，容易尋找出錯誤的對應(yīng)點[13]，從而出現(xiàn)配準精度降低的問題。

1 算法描述

本文提出一種基于邊界質(zhì)心的點云粗配準方法。該算法首先對源點云和目標點云分別進行邊界提取[14]。點云邊界作為表達物體表面幾何特征的重要載體，對曲面重構(gòu)精度起著重要作用。提取后的點云邊界能在最大程度保持物體原有表面特征的同時，減少點云內(nèi)部無特征的數(shù)據(jù)點。然后，計算點云邊界質(zhì)心，并把兩個點云的邊界質(zhì)心都移動到坐標原點，使待配準點云初始距離快速減小，增加源點云和目標點云之間的重疊度，減少出現(xiàn)錯誤配準的幾率。最后，使用K-4PCS算法完成粗配準。本文方法的流程圖如圖1所示。

圖1 點云粗配準流程圖Figure 1. Flow chart of point cloud coarse registration

2 點云邊界提取算法

2.1 拓撲關(guān)系的建立與鄰近檢索方法

K-D tree是一種樹形數(shù)據(jù)結(jié)構(gòu)，常用于點的快速檢索[15]。創(chuàng)建K-D tree時，通常隨著樹的深度增加，輪流選擇x、y、z軸，過軸方向上坐標為中位數(shù)的點，作垂直于該軸的分割面。通過這種方式不斷劃分點云所在的三維空間，直到所有數(shù)據(jù)點都劃分完畢。建立K-D tree能加快點的最鄰近檢索[16]。為了搜索點P的最鄰近點，需要先沿著K-D tree搜索到點P，此時的點P作為當前節(jié)點。如果點P到其父節(jié)點的距離小于點P到當前節(jié)點的祖父節(jié)點所在分割面的距離，則點P的父節(jié)點即為點P的最鄰近點。此時，點P及其最鄰近點被分割在同側(cè)子空間中，如圖2所示。

圖2 最鄰近點在同側(cè)子空間Figure 2. The nearest point is in the same side subspace

由圖2可以看出，點P為當前節(jié)點，點N為點P的父節(jié)點，點M為點P的祖父節(jié)點，分割面A為過點M且垂直于z軸的分割面。以點P為球心，以PN為半徑作球，當球與分割面A相離時，父節(jié)點N即為點P的最鄰近點。

當點P到其父節(jié)點的距離大于點P到當前節(jié)點的祖父節(jié)點所在分割面的距離時，則需考慮最鄰近點在另側(cè)子空間的情況。此時，先記錄下點P到其父節(jié)點的距離，然后沿K-D tree搜索路徑逆向查找，當前節(jié)點位置向樹的上方移動一級。在另側(cè)子空間中找出距離點P最近的點，比較兩個距離的大小，算出當前最小距離。然后比較當前最小距離和點P到當前節(jié)點的祖父節(jié)點所在分割面的距離。如果前者小于后者，則當前最小距離即為真實最小距離，所對應(yīng)點為最鄰近點；如果不是，則以相同的方法繼續(xù)向上回溯，直到找出滿足要求的最鄰近點，具體如圖3所示。

圖3 最鄰近點在另側(cè)子空間Figure 3. The nearest point is in the other subspace

由圖3可以看出，以點P為球心，以PN為半徑作球，球與分割面A相交，記錄下PN的距離。沿著K-D tree逆向查找，當前節(jié)點位置向上移動一級，變?yōu)辄cP的父節(jié)點N，分割面B為過點N祖父節(jié)點O且垂直于y軸的分割面，點Q為另側(cè)子空間的最近點，比較PQ和PN的大小，PQ較小。以點P為球心，PQ為半徑作球，球與分割面B相離，則點Q為點P的最鄰近點，最鄰近檢索算法如圖4所示。

圖4 最近鄰點算法流程圖Figure 4. Flow chart of the nearest neighbor algorithm

2.2 平面的擬合

運用K-D tree的k鄰近算法，可以快速查找點P的k個鄰近點，距離從近到遠依次記為N1,N2…,Nk。設(shè)擬合平面的方程為

ax+by+cz+d=0

(1)

把點P及其k個鄰近點的坐標帶入式(1)中，其矩陣方程為AX=0。

(2)

用最小二乘法來擬合平面，當某平面到點P及其k個鄰近點的距離平方和最小，該平面即為其擬合平面，點到平面的距離平方和可以表示為

(3)

求平面到點P及其k個鄰近點的距離平方和最小，等同于求X使式(3)的值最小。用奇異值分解法(Singular Value Decomposition，SVD)求解，當式(3)取最小值時，其值為ATA的最小特征值，X的值為最小特征值所對應(yīng)的特征向量[17]。

2.3 邊界點的判斷與提取

把點P及其k個鄰近點投影到擬合平面上，得點P′,N′1,N′2，…,N′k。以P′為起點，以k個鄰近點的投影為終點，作向量P′N′1,P′N′2，…,P′N′k，如圖5和圖6所示。

圖5 P為邊界點Figure 5.P is the boundary point

圖6 P為內(nèi)部點 Figure 6.P is the internal point

由圖5和圖6可以看出，當點P為邊界點時，最大相鄰夾角θmax比點P為內(nèi)部點時大。根據(jù)這個特點，當最大相鄰夾角θmax大于設(shè)定的閾值ε時，可以認為點P為邊界點。為了求出最大相鄰夾角θmax，需先求出所有相鄰夾角的值。首先確定一個基準向量，然后求出每個向量與基準向量之間的夾角，記為基準夾角，再將相鄰向量的基準夾角相減，即可得到相鄰夾角，如圖7所示。

圖7 相鄰夾角的求解Figure 7. Solution of adjacent angle

如圖7可以看出，P′N′1為基準向量，P′N′a(1≤a≤k)和P′N′b(1≤b≤k)為任意兩個相鄰向量。P′N′a與基準向量之間的基準夾角為αa，P′N′b與基準向量之間的基準夾角為αb，兩者之差即為P′N′a和P′N′b的相鄰夾角θa。

由于基準夾角的取值范圍為0°～360°，而向量夾角計算式只能求解出0°～180°的劣角，所以要先對基準夾角的大小進行判斷。

(4)

式中，P′N′1為基準向量；n為擬合平面的法向量；v為兩者的叉積，方向遵守右手定則。當向量P′N′i(1≤i≤k)與v的夾角為銳角時，基準夾角為劣角；當與v的夾角為鈍角時，基準夾角為優(yōu)角。

基準夾角αi為向量P′N′i與基準向量P′N′1的夾角，其求解如式(5)所示。

(5)

最后，將所有基準夾角α的值從小到大依次排列得β1<β2<…<βk，即可算出所有相鄰夾角θ的值，如式(6)。

(6)

通過比較可得到最大相鄰夾角θmax。邊界判斷流程如圖8所示。

圖8 邊界提取算法流程圖Figure 8. Flow chart of boundary judgment algorithm

3 點云邊界質(zhì)心處理方法

由于點云中每個數(shù)據(jù)點的質(zhì)量相同且分布均勻，所以邊界質(zhì)心相對于點云邊界的位置也是固定的。質(zhì)量均勻的矩形質(zhì)心在其對角線的交點，球的質(zhì)心在球心。邊界質(zhì)心Pc的求解如式(7)所示。

(7)

從不同角度測量得到的點云數(shù)據(jù)所參照的坐標系不同，原始點云數(shù)據(jù)之間會存在較大的初始距離。如果點云之間的初始距離過大，重疊度過低，直接使用K-4PS算法對點云進行粗配準時，會出現(xiàn)對應(yīng)點選取錯誤或運算時間過長等問題，降低粗配準的效率。計算并配準點云的邊界質(zhì)心能快速縮短初始位置距離，并增加點云之間的重疊度。為了盡量避免可能存在的噪聲點對質(zhì)心位置的干擾，本文采用配準邊界質(zhì)心的方法來取代傳統(tǒng)直接配準原始點云數(shù)據(jù)質(zhì)心的方法，以防止質(zhì)心位置因受噪聲點影響而發(fā)生偏離進而導(dǎo)致待配準點云的重疊度降低的問題。由于質(zhì)心與邊界位置的相對性，配準點云的邊界質(zhì)心能在一定程度上減小點云之間的平移誤差。為了方便使用K-4PS進行粗配準，可先將源點云和目標點云的邊界質(zhì)心都移動到坐標原點。此時，平移矩陣T如式(8)所示。

T=[-xc,-yc,-zc]T

(8)

4 結(jié)果與分析

4.1 實驗設(shè)計與環(huán)境說明

在傳統(tǒng)配準誤差算法中，通過計算源點云與目標點云之間所有對應(yīng)點的歐式距離之和來判斷算法的配準效果。這種評價方法只把點云配準前后的位置誤差納入判斷標準，沒有對點云的姿態(tài)誤差給出評價。為了能夠多角度的對粗配準誤差進行分析，本文通過配準矩陣反求出平移距離和旋轉(zhuǎn)角度，再把這些值與標準值進行對比，得出平移誤差和旋轉(zhuǎn)誤差。為了方便比較粗配準前后點云之間的位姿關(guān)系，本文分別計算了3個坐標軸方向的平移和旋轉(zhuǎn)誤差，同時記錄下每種算法完成粗配準所消耗的時間。通過精度和時間兩個方面，對本文粗配準方法的效果進行了更加全面的評估。

在實際測量過程中，受被測物體大小和測量環(huán)境的限制，可能會出現(xiàn)一次測量只能得到物體部分點云數(shù)據(jù)的情況。為了測試本文粗配準方法的適用范圍，特地選取兩組完整點云Dinosaur、Horse和一組非閉合點云Bunny進行粗配準實驗。選取的點云Horse只有平移誤差，點云Dinosaur只有旋轉(zhuǎn)誤差，而點云Bunny既有平移誤差又有旋轉(zhuǎn)誤差，這樣就能測試本文方法對不同類型誤差的配準效果，方便對誤差做出分析。同時，本文選擇在粗配準算法中配準速度較快的采樣一致性初始配準算法(Sample Consensus Initial Alignment，SAC-IA)[18]和精度較高的傳統(tǒng)K-4PCS算法與本文方法進行比較，來驗證本文方法在速度和精度方面的優(yōu)勢。

本文實驗所用計算機配置為：Intel Core i7-8750H 2.20 GHz CPU，8 GB內(nèi)存，Windows 10 64位操作系統(tǒng)，實驗代碼通過Visual Studio 2017和PCL 1.8.1版本進行編譯。

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

4.2.1 點云Dinosaur配準結(jié)果分析

完整點云Dinosaur一共有23 982個數(shù)據(jù)點，源點云與目標點云只有平移誤差，分別使用3種方法對其進行配準實驗，如圖9所示。

由圖9可以看出，本文方法的粗配準效果優(yōu)于SAC-IA算法和傳統(tǒng)K-4PCS算法。SAC-IA算法配準的點云Dinosaur在脖子處都出現(xiàn)了明顯的偏移，傳統(tǒng)K-4PCS算法也在脖子處出現(xiàn)了少量的偏移，本文方法配準的脖子處點云重合度最高。為了能夠更加客觀地對比實驗結(jié)果，分別記錄了旋轉(zhuǎn)誤差、平移誤差和配準時間，結(jié)果如表1所示。

(a) (b)

表1 點云Dinosaur粗配準精度和時間對比Table 1. Comparison of accuracy and time of Dinosaur point cloud coarse registration

由表1可以看出，在粗配準精度方面，本文方法的平移精度約為SAC-IA算法的4.8倍，約為傳統(tǒng)K-4PCS算法的1.6倍；旋轉(zhuǎn)精度約為SAC-IA算法的9倍，約為傳統(tǒng)K-4PCS算法的1.2倍。SAC-IA算法減少了點云平移誤差，但又引入了大量的旋轉(zhuǎn)誤差，整體的配準效果不佳。傳統(tǒng)K-4PCS算法旋轉(zhuǎn)誤差較小，但平移誤差較大，配準效果稍遜本文方法。配準速度方面，本文方法的配準速度達到了SAC-IA算法的1.6倍，是傳統(tǒng)K-4PCS的2倍以上。綜上所述，本文算法在配準只有平移誤差的完整點云Dinosaur時，在精度和速度方面都全面優(yōu)于其他兩種算法。

4.2.2 點云Horse配準結(jié)果分析

完整點云Horse一共有48 485個數(shù)據(jù)點，源點云與目標點云之間只有旋轉(zhuǎn)誤差，分別使用3種方法對其進行配準實驗，如圖10所示。

(a) (b)

由圖10可以看出，本文方法和傳統(tǒng)K-4PCS算法的粗配準效果都優(yōu)于SAC-IA算法。SAC-IA算法配準的點云Horse在馬的頭部出現(xiàn)了大量的未配準點，馬蹄部分也出現(xiàn)了明顯的分離。傳統(tǒng)K-4PCS算法和本文方法的配準效果良好，僅在馬蹄處出現(xiàn)少量未配準點。為了能夠更加客觀地對比實驗結(jié)果，本文分別記錄了旋轉(zhuǎn)誤差、平移誤差和配準時間，結(jié)果如表2所示。

由表2可知，在粗配準精度方面，本文方法的平移精度約為SAC-IA算法的5倍，與傳統(tǒng)K-4PCS相當；旋轉(zhuǎn)精度約為SAC-IA算法的4.5倍，為傳統(tǒng)K-4PCS的2.7倍。在SAC-IA算法配準后，兩點云之間還是存在著一定的平移和旋轉(zhuǎn)誤差，配準效果不佳。盡管傳統(tǒng)K-4PCS算法平移精度與本文方法相當，但是其繞3個軸的旋轉(zhuǎn)誤差普遍都高于本文方法，導(dǎo)致整體配準精度稍遜于本文方法。在粗配準速度方面，本文方法配準速度是SAC-IA算法的1.3倍，是傳統(tǒng)K-4PCS的1.6倍。實驗證明，本文算法在配準只有旋轉(zhuǎn)誤差的完整點云Horse時，在精度和速度方面優(yōu)于其他兩種粗配準算法。

表2 點云Horse粗配準精度和時間對比Table 2. Comparison of accuracy and time of Horse point cloud coarse registration

4.2.3 點云Bunny配準結(jié)果分析

非閉合點云Bunny的目標點云有40 256個數(shù)據(jù)點，源點云有40 097個數(shù)據(jù)點，兩個點云之間既有平移誤差又有旋轉(zhuǎn)誤差，分別使用3種方法對其進行配準實驗，配準結(jié)果如圖11所示。

(a) (b)

由圖11可知，本文方法的粗配準效果依然優(yōu)于SAC-IA算法和傳統(tǒng)K-4PCS算法。SAC-IA算法配準的點云Bunny在背部、尾部和耳朵部分出現(xiàn)了較多的未配準點。傳統(tǒng)K-4PCS算法配準的點云整體上有少許旋轉(zhuǎn)偏移，耳朵部分點云的重合度偏低。本文方法配準的點云重合度較高，點云之間沒有明顯的平移和旋轉(zhuǎn)偏移，特別是兔子耳朵部分點云的配準效果好于其它兩種方法。為了能夠更加客觀的對比實驗結(jié)果，分別記錄了旋轉(zhuǎn)誤差、平移誤差和配準時間，結(jié)果如表3所示。

由表3可知，在粗配準精度方面，本文方法的平移精度約為SAC-IA算法的6倍，為傳統(tǒng)K-4PCS的1.8倍；旋轉(zhuǎn)精度約為SAC-IA算法的5倍，為傳統(tǒng)K-4PCS的1.4倍。由于非閉合點云Bunny的源點云和目標點云的數(shù)據(jù)點個數(shù)不同，存在著大量噪聲點，導(dǎo)致SAC-IA算法的平移精度和旋轉(zhuǎn)精度都較低，配準效果相對一般。傳統(tǒng)K-4PCS也因為噪聲點的干擾，與本文方法的精度差距被稍稍拉大，但總體配準效果較好。而本文方法由于采用了邊界提取算法，剔除了大量的噪聲點，邊界質(zhì)心的配準保障了點云之間的高重疊度，所以在配準非閉合點云時，依舊保持了較高的精度。在粗配準速度方面，本文算法的配準速度是SAC-IA算法的1.6倍，是傳統(tǒng)K-4PCS的2.2倍。所以，對于同時存在平移誤差、旋轉(zhuǎn)誤差和噪聲點的非閉合點云Bunny，與其他兩種粗配準算法相比，本文算法的配準效果具有較大的優(yōu)勢。

表3 點云Bunny粗配準精度和時間對比Table 3. Comparison of accuracy and time of Bunny point cloud coarse registration

5 結(jié)束語

本文提出了一種基于點云邊界質(zhì)心的粗配準方法。該方法通過邊界提取和邊界質(zhì)心配準，在加快粗配準速度的同時保障配準了點云粗配準的精度。選用兩種常用粗配準方法作為參照，選取存在平移和旋轉(zhuǎn)誤差的3組完整和非閉合點云進行對比實驗，并對實驗結(jié)果進行了分析。實驗結(jié)果證明，本文提出的粗配準方法是一種高效率、高精度、抗干擾性較強的粗配準方法。下一步將對點云精配準的加速和點云三維重建方面開展研究工作。依托于計算機技術(shù)的告訴發(fā)展和硬件設(shè)備的升級，實時同步進行三維測量、點云數(shù)據(jù)處理和三維重建的設(shè)備變得未來可期?；诖?，在保證點云配準高精度的同時，提高配準的速度變得尤為重要。5G技術(shù)的發(fā)展為實時三維重建技術(shù)的應(yīng)用渠道創(chuàng)造了可能，實時高效的三維重建技術(shù)的社會化應(yīng)用也將更加廣泛。