基于區(qū)域劃分的點云全局配準(zhǔn)研究

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

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

0 引言

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

全局配準(zhǔn)一般分為兩類：一類是基于幾何特征，常用的幾何特征描述算法如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]等?；趲缀翁卣鞯姆椒ㄟ^于依賴物體的幾何特征，因設(shè)備精度以及人為原因產(chǎn)生的噪聲、外點，將會嚴(yán)重影響配準(zhǔn)的效果。因此，本文采用了對噪聲、點云魯棒性較強的基于窮舉思想配準(zhǔn)的方法對點云全局配準(zhǔn)進行研究。

1 常用基于窮舉思想的配準(zhǔn)算法

1.1 隨機采樣一致性算法

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

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

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

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

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

1.2 四點全等集算法

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

算法主要思想描述如下：

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

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

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

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

1.3 超級四點全等集算法

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

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

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

圖2 錯誤對應(yīng)點對示意圖

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

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

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

2.1 區(qū)域劃分

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

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

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

2.2 區(qū)域配準(zhǔn)

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

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

2.3 算法步驟

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

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

算法具體步驟為：

(1)輸入源點云P={pi|pi∈R}與目標(biāo)點云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算法，在目標(biāo)點云Q中的Qn區(qū)域中查找四點全等集{q1,q2,q3,q4,θ}。

(5)判斷是否i

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

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

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

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

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

圖5 bunny模型全局配準(zhǔn)效果圖

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

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

圖6 dragon模型全局配準(zhǔn)效果圖

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

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

圖7 Armadillo模型全局配準(zhǔn)效果圖

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

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

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

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

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

圖8 不同重疊比例對配準(zhǔn)效率的影響

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

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

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

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

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

4 結(jié)論

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