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

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

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

0 引言

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

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

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

1.1 隨機(jī)采樣一致性算法

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

(1)從樣本P中隨機(jī)抽取n個(gè)樣本點(diǎn)構(gòu)成樣本子集D，用于初始化模型M，其中n為初始化模型參數(shù)所需的最小樣本個(gè)數(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*重新計(jì)算新的模型M*；重新隨機(jī)抽取新的樣本子集D，迭代重復(fù)以上過程。

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

1.2 四點(diǎn)全等集算法

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

算法主要思想描述如下：

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

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

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

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

1.3 超級(jí)四點(diǎn)全等集算法

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

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

圖1 點(diǎn)云柵格化二維示意圖

圖2 錯(cuò)誤對應(yīng)點(diǎn)對示意圖

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

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

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

2.1 區(qū)域劃分

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

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

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

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

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

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

2.3 算法步驟

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

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

算法具體步驟為：

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

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

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

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

(5)判斷是否i

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表1 三組實(shí)驗(yàn)數(shù)據(jù)對比

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

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

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

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

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

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

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

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

4 結(jié)論

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