周建釗，杜文超，顏雨吉，何曉輝，代菊英

(陸軍工程大學 野戰(zhàn)工程學院，江蘇 南京 210007)

0 引言

由于激光以及結構光的物理性質(zhì)以及被掃描物體自身相互遮擋的原因，掃描儀測量范圍無法全方位覆蓋完整的物體表面，需要從不同角度多次對目標物體進行掃描，從而獲取的是多片相互重疊的點云。不同角度獲取的點云具有不同的參考坐標系，必須把從不同角度獲取的點云統(tǒng)一到同一坐標系中，才能獲取被測物體完整的點云，這個過程即為點云配準[1]。

全局配準一般分為兩類：一類是基于幾何特征，常用的幾何特征描述算法如Curvedness、Shape Index、FPFH[2]、3DSC[3]、Spin image[4-5]、VFH[6]等；另一類是基于窮舉思想，比如隨機采樣一致性(Random Sample Consensus,RANSAC)算法[7]、四點全等集(4-Points Congruent Sets,4PCS)算法[8]以及Super4PCS算法[9]等?；趲缀翁卣鞯姆椒ㄟ^于依賴物體的幾何特征，因設備精度以及人為原因產(chǎn)生的噪聲、外點，將會嚴重影響配準的效果。因此，本文采用了對噪聲、點云魯棒性較強的基于窮舉思想配準的方法對點云全局配準進行研究。

1 常用基于窮舉思想的配準算法

1.1 隨機采樣一致性算法

隨機采樣一致性(RANSAC)算法是采用迭代的方式從一組包含離散值的樣本數(shù)據(jù)中估算出數(shù)學模型參數(shù)，得到有效樣本數(shù)據(jù)的一種算法，其基本步驟是：

(1)從樣本P中隨機抽取n個樣本點構成樣本子集D，用于初始化模型M，其中n為初始化模型參數(shù)所需的最小樣本個數(shù)，P的樣本數(shù)大于n。

(2)樣本余集(從樣本P中除去樣本子集D后的集合)PC與模型M誤差小于設定閾值δ的樣本集與樣本子集D構成有效樣本集D*，構成D的一致集(Consensus Set)。

(3)若有效樣本集D*不小于N，則認為得到了正確的模型參數(shù)，并利用有效樣本集D*重新計算新的模型M*；重新隨機抽取新的樣本子集D，迭代重復以上過程。

(4)在完成一定的抽樣次數(shù)后，選取抽樣后得到的最大一致集的模型進行參數(shù)估計，算法結束；若未找到D的一致集則算法失敗。

1.2 四點全等集算法

四點全等集(4PC))算法是在RANSAC算法的基礎上在對應點選取策略上的改進。將RANSAC算法選取三點的策略改進為選取非共線的共面四點的策略，運用仿射變換理論，在目標點云中尋找全等集，運用于RANSAC框架下，實現(xiàn)點云全局配準。該算法在繼承了RANSAC算法對噪聲以及異常點魯棒性較強優(yōu)點的基礎上，改進了算法的穩(wěn)定性，減少了時間復雜度。

算法主要思想描述如下：

(1)基底選擇。在點集P中選擇一個由四個共面點組成的基底B≡{p1,p2,p3,p4}。

(2)全等集查找。通過上一步驟中確定的基底B，從點集Q中尋找出在一定范圍與基底B配對的全部點對構成點集U≡{U1，U2，…，Us}。對于任意一個Ui，通過基底B與Ui都可以計算出相應的剛體變換矩陣Ti，使得B與Ui相互配準。

(3)剔除錯誤點對，計算最優(yōu)剛體變換矩陣T。應用RANSAC思想，計算Ti(P)，并統(tǒng)計與點集Q之間距離小于δ的點的個數(shù)，評估不同的Ti，剔除掉錯誤的對應點對，從而得出最優(yōu)剛體變換矩陣T。

(4)對于P中不同的基底Bj，循環(huán)上述過程均可計算出相應的最優(yōu)變換矩陣Tj，根據(jù)重疊度f測試L組不同的基底Tj，最終得到最優(yōu)剛體變換矩陣Topt。

1.3 超級四點全等集算法

隨著三維掃描技術不斷提升，對算法的高效性、穩(wěn)定性提出了更高的要求。4PCS算法在處理效率上顯然難以滿足目前的要求，這就要求對其進行改進優(yōu)化。該算法受限制于兩個瓶頸：(1)在全等集查找中，查找出給定距離的所有點。對于P中給定的基底B，從Q中查找出所有的距離為d1、d2的兩點對。(2)在剔除錯誤點對中，由于考慮仿射不變量而產(chǎn)生的大量的冗余候選四點對。產(chǎn)生的四點對是所有全等四點對的超集，包含大量冗余。

針對第一個查找兩點對的瓶頸問題，超級四點全等集(Super4PC))算法提出采用柵格化[10]的方法，如圖1的點云柵格化二維示意圖所示，大大地縮短了在從Q中查找出所有距離為d1、d2的兩點對的時間，提高了算法的效率。

圖1 點云柵格化二維示意圖

圖2 錯誤對應點對示意圖

Super4PCS算法針對上述問題提出在提取四點對的同時去除錯誤點對，即可得到與基底B對應的集合，從而在去除冗余點對的同時，大大提高了算法效率。由圖2所示可知，若給定基底B的{p1,p2,p3,p4,θ}五個參數(shù)，在目標點云P中就可以搜索出唯一對應的四點對。

2 基于區(qū)域劃分改進的點云全局配準

經(jīng)過1.2節(jié)分析可知，Super4PCS算法在算法效率上有了巨大的改進，但對重疊率較低的兩片點云執(zhí)行全局配準時，往往容易收斂于局部最優(yōu)，難以達到預想的效果。為提高配準效果，本文提出了基于區(qū)域劃分改進的Super4PCS算法。首先根據(jù)重疊率的大小對兩點云進行適當?shù)膮^(qū)域劃分，然后分別對每個區(qū)域內(nèi)的兩片點云執(zhí)行Super4PCS算法，計算剛體變換矩陣并選擇出配準效果最好的兩片對應區(qū)域，對整體源點云執(zhí)行上述剛體變換，從而實現(xiàn)點云的全局配準[11]。下面重點對區(qū)域劃分以及區(qū)域配準兩個環(huán)節(jié)展開討論。

2.1 區(qū)域劃分

空間柵格法[12]和Voronoi圖法[13]等都是常用于區(qū)域劃分的方法?？臻g柵格法是將包圍點云的最小長方體包圍盒均勻地劃分成邊長為L的小立方體單元柵格的方法。Voronoi圖法是通過求取區(qū)域內(nèi)相鄰兩點的垂直平分線將區(qū)域劃分為多個連續(xù)多邊形的方法。綜合對比上述兩個劃分方法后，本文采用Voronoi圖法進行劃分，如圖3所示。

圖3 二維Voronoi圖法劃分過程示意圖

本文中區(qū)域劃分首先分別對源點云和目標點云進行均勻采樣構成采樣點集合為{pi,i=1,2,…,M}和{qj,j=1,2,…,N}；然后，應用Voronoi圖法對兩點云進行區(qū)域的劃分。M、N分別表示對源點云與目標點云劃分區(qū)域的數(shù)目。區(qū)域數(shù)目由兩點云的重疊比例決定，一般取值為1～20。當重疊比例越小，區(qū)域數(shù)目取值越大；相反，當重疊比例越大，區(qū)域數(shù)目取值越小，當區(qū)域數(shù)目為1時，點云的區(qū)域配準即為全局配準。

2.2 區(qū)域配準

區(qū)域配準實際上是對點云中的一部分點云與另點云中的一部分點云進行配準，本質(zhì)上沒有發(fā)生任何變化?，F(xiàn)有的諸多配準方法均適用于點云內(nèi)區(qū)域間的配準。

Super4PCS算法不依賴于曲率、法線等幾何特征，不會受到噪聲和異常值等因素的嚴重影響，魯棒性較好；該算法是對4PCS算法的改進，大大提高了算法的效率，具有較低的時間復雜度；同時，Super4PCS算法能夠自動估計點云的配準效果，對于每一次區(qū)域配準都能夠給出一個最大化公共點集(LCP)度量，遍歷所有的M×N個配準區(qū)域對，比較其LCP度量值即可得到重疊率最高的兩片區(qū)域。因此，本文選擇采用Super4PCS算法進行點云的區(qū)域間配準。

2.3 算法步驟

針對目前常用算法對于重疊率較低的兩片點云，難以實現(xiàn)理想的全局配準效果的問題，本文提出了基于區(qū)域劃分改進的點云全局配準。圖4所示為算法的流程圖。

圖4 基于區(qū)域劃分改進的點云全局配準算法流程圖

算法具體步驟為：

(1)輸入源點云P={pi|pi∈R}與目標點云Q={qj|qj∈R}；初始化P中M個區(qū)域迭代次數(shù)m=0，Q中N個區(qū)域迭代次數(shù)n=0，Pm中基底迭代次數(shù)i，其中m∈[0，M],n∈[0，N],i∈[0，imax]。

(2)對P和Q進行區(qū)域劃分，分別劃分為M、N個區(qū)域。

(3)在源點云P中的Pm區(qū)域中，選擇基底Bmi={p1,p2,p3,p4,θ}。

(4)運用Super4PCS算法，在目標點云Q中的Qn區(qū)域中查找四點全等集{q1,q2,q3,q4,θ}。

(5)判斷是否i

(6)比較LCPmni度量值，計算出最大的重疊比例，將其對應的旋轉矩陣Rmni和平移向量tmni應用于全局配準中，計算出剛體變換后的點云P′=RmniP+tmni；

(7)輸出變換后的P′以及目標點云Q，實現(xiàn)全局配準。

3 實驗結果與分析

為了驗證本文全局配準算法的實際效果，對斯坦福大學點云模型數(shù)據(jù)庫和PCL官網(wǎng)中的大量點云模型進行了實驗，選取了各具代表性的bunny、dragon和Armadillo點云模型。通過與4PCS算法進行比較，證明本算法的有效性。分別對比驗證了不同類型模型的配準效果，以及不同采樣點數(shù)目和在不同重疊比例下的配準效率。

實驗一：bunny模型的全局配準。圖5(a)和圖5(b)為bunny模型不同視角下獲取的兩片點云。目標點云為5 622個點，如圖5(a)所示，源點云為5 401個點，如圖5(b)所示，兩點云的重疊比例為90%。bunny模型是經(jīng)典的點云配準模型，其具有模型簡單，特征明顯，點云分布均勻等特點。

圖5 bunny模型全局配準效果圖

圖5為bunny模擬采用兩種不同全局配準算法的效果圖，其中(a)為目標點云，(b)為源點云，(c)為采用4PCS算法對兩點云配準后效果圖，(d)為采用本文算法對兩點云配準后效果圖。

實驗二：dragon模型的全局配準。圖6(a)和圖6(b)為dragon模型不同視角下獲取的兩片點云。目標點云為12 197個點，如圖6(a)所示，源點云為8 917個點，如圖6(b)所示。兩點云的重疊比例為60%。dragon模型形狀復雜，較多點的幾何特征相似甚至相同，且選取的兩片點云重疊比例較低。

圖6 dragon模型全局配準效果圖

圖6為dragon模型采用兩種不同全局配準算法的效果圖，其中(a)為目標點云，(b)為源點云，(c)為采用4PCS算法對兩點云配準后效果圖，(d)為采用本文算法對兩點云配準后效果圖。

實驗三：Armadillo模型的全局配準。圖7(a)和圖7(b)為Armadillo模型不同視角下獲取的兩片點云。目標點云為19 283個點，如圖7(a)所示，源點云為22 410個點，，如圖7(b)所示。兩點云的重疊比例為30%。Armadillo模型形狀十分復雜，特征較明顯，且選取的兩片點云分別來自于正面與背面兩個視角，重疊比例十分低。

圖7 Armadillo模型全局配準效果圖

圖7為Armadillo模擬采用兩種不同全局配準算法的效果圖，其中(a)為目標點云，(b)為源點云，(c)為采用4PCS算法對兩點云配準后效果圖，(d)為采用本文算法對兩點云配準后效果圖。

通過實驗數(shù)據(jù)，綜合對比以上三組實驗，如表1所示。橫向對比可發(fā)現(xiàn)，本文算法較4PCS算法在效率上有很大的改進，在較低重疊比例下仍能夠得到較好的配準效果?？v向對比來看，隨著點云數(shù)目總體上的增加，配準平均耗時增加，隨著重疊比例的減少，配準平均耗時也顯著增大。但對于多個變量同時作用的結果，難以得出理想結論。因此，本文采用控制變量的方法，分別研究在相同模型相同重疊比例下不同點云數(shù)目對兩種算法配準效率的影響，以及在相同模型近似點云數(shù)目下不同重疊比例對兩種算法配準效率的影響。

表1 三組實驗數(shù)據(jù)對比

(1)重疊比例對配準效率影響

該實驗采用經(jīng)典的bunny模型，所有組的目標點云數(shù)目近似為40 256，源點云數(shù)目近似為40 097。改變兩點云的重疊比例，每一重疊比例下多次實驗取平均值，分別對比4PCS算法和本文算法，實驗結果如圖8所示。

圖8 不同重疊比例對配準效率的影響

通過對比可發(fā)現(xiàn)兩種算法隨著重疊比例的降低，配準時間增加，且比例越低，耗時增加越顯著。4PCS算法在40%重疊比例時，配準時間顯著增加；而本文算法則低于20%重疊比例時才會顯著變化。橫向對比兩種算法可得，本文算法在較低重疊比例時算法效率明顯優(yōu)于4PCS算法，且4PCS算法在較低重疊比例時易出現(xiàn)錯誤配準。因此，對于低重疊比例的情況，本文算法明顯優(yōu)于4PCS算法。

(2)采樣點數(shù)目對配準效率的影響

該實驗采用經(jīng)典的bunny模型，所有組的重疊比例均為90%。改變采樣點的數(shù)目，對于每一組進行多次實驗取平均值，分別對比4PCS算法和本文算法，實驗結果如圖9所示。

圖9 不同采樣點數(shù)目對配準效率的影響

通過對比可以發(fā)現(xiàn)兩種算法隨著點云數(shù)目的增加，配準時間成比例增加。在點云數(shù)目較少時，兩種算法配準時間相近且變化率較小，說明此時點云數(shù)目對配準時間影響較小。隨著點云數(shù)目增多，配準時間成比例增加，這主要受點云數(shù)目的影響。橫向對比兩種算法可得，整體上本文算法在算法效率優(yōu)于4PCS算法，點云數(shù)目越多，優(yōu)勢越明顯。

4 結論

本文提出的基于區(qū)域劃分的全局配準算法為點云局部配準提供了較好的初始位置，同時大大提高了配準效率，相比于目前常用全局配準算法，該算法對低重疊比例的兩點云具有良好的效果。本文提出的基于區(qū)域劃分的全局配準算法對于幾何特征不明顯且重疊比例較低的點云具有較好的配準效果，對提高點云全局配準的精度及效率具有重要的意義。