基于經(jīng)緯網(wǎng)格的點云孔洞填補算法

李由之, 唐志榮, 劉明哲

(1.成都理工大學核技術(shù)與自動化工程學院,成都 610059；2.成都理工大學地質(zhì)災(zāi)害防治與地質(zhì)環(huán)境保護國家重點實驗室,成都 610059)

在點云數(shù)據(jù)采集過程中,因被遮擋、表面反射、技術(shù)限制等因素影響,不可避免地出現(xiàn)點云數(shù)據(jù)缺失現(xiàn)象,從而產(chǎn)生不利于后續(xù)數(shù)據(jù)處理的孔洞區(qū)域,因此,必須先進行包括排除干擾數(shù)據(jù)、數(shù)據(jù)簡化、目標識別、點云配準和對孔洞進行修復。該過程主要有兩個難點:①怎樣盡可能精確地獲取孔洞邊界；②怎樣獲取更多孔洞區(qū)域的信息,從而使修補接近原始形狀。

雷敏等[1]提出使用包圍盒算法對點云數(shù)據(jù)進行過分聚類,并通過中心點代替過分簇后進行基于密度的再聚類來達到簡化點云數(shù)據(jù)的目的。楊飚等[2]提出先用正態(tài)分布變換(normal distributions transform,NDT)算法進行粗配準,再用迭代就近點(iterative closest point,ICP)算法進行微調(diào)和精確配準的點云配準法。此類方法或適用于孔洞修復前的識別與配準。

文獻[3]提出插值法對孔洞進行填補,對于曲率變化較大或者形狀較為復雜的孔洞區(qū)域。文獻[4-5]通過縮短孔的邊緣流動和分段法等方法進行孔洞修補。Pernot等[6]提出根據(jù)孔洞最小鄰域和插入網(wǎng)格之間的曲率變化進行孔洞修復。文獻[7-9]通過重建函數(shù)、計算傳熱參數(shù)、幾何信息和圖像信息等方法修補孔洞。

Marchandis等[10]提出以初始網(wǎng)格為基礎(chǔ),使用徑向基函數(shù)計算離散參數(shù)重構(gòu)初始網(wǎng)格實現(xiàn)孔洞的修復。Yumer等[11]提出基于神經(jīng)網(wǎng)絡(luò)的孔洞修補算法。Quinsat等[12]提出利用網(wǎng)格變形的方法來填充數(shù)字化點云中的孔。Centin等[13]提出利用泊松方程完成三角形網(wǎng)格無縫修補。Yang等[14]提出形狀可控的點云幾何模型重構(gòu)算法,能夠在光滑模型或具有尖銳特征的表面上修補孔洞。Zhong等[15]將空間域轉(zhuǎn)化為其他域或數(shù)學模型以到達修補孔洞的目的。

Jun[16]將復雜的孔洞依據(jù)孔洞邊界的三維形狀分成幾個簡單的孔洞,然后用平面三角測量法連續(xù)地填充每個離散的簡單孔洞直到整個填充完畢。Kanle等[17]針對圓形孔洞提出了基于四邊形分割和約束優(yōu)化的方法,對指定的圓形孔洞邊界進行重新參數(shù)化,以確保相鄰邊界增長點在連接點上的相容性,方法簡單高效且無需迭代或大規(guī)模矩陣求解。Wang等[18]對于具有陰影信息的點云模型,利用最小二乘法內(nèi)插幾何信息,可以同時內(nèi)插幾何和陰影信息。

張琦等[19]提出了一種基于改進的曲線收縮流虛擬修補點云張開孔洞的方法,利用孔洞邊界點的表面法向量和切向量對孔洞進行修補。曾露露等[20]提出一種基于從運動中恢復結(jié)構(gòu)的三維點云孔洞修補算法,利用光柵投影法中得到的二維相位信息來提取三維點云孔洞區(qū)域的邊界點從而完成對點云孔洞的填補。文獻[21]提出的輪廓提取,或許可以用以輔助解決此類問題。

為解決三維點云數(shù)據(jù)存在的復雜孔洞區(qū)域且難以搜索孔洞位置對后續(xù)處理造成影響的問題,提出一種基于經(jīng)緯網(wǎng)格的點云修補算法。實驗證明,比起傳統(tǒng)修補方法,該算法具有更好的魯棒性,從而更好完成對復雜孔洞的修補以便進行后續(xù)重建處理等過程。

1 點云孔洞修補

1.1 坐標轉(zhuǎn)換

將給定點云A={a1,a2,…,aK},(ai={xi,yi,zi}T)轉(zhuǎn)化到球坐標下：

(1)

圖1 三維球坐標Fig.1 3D spherical coordinates

得到球坐標點云：

Q={q1,q2,…,qK}

(2)

式(2)中：qi={θi,φi,ri}T,i=1,2,…,K表示球坐標下的點。

1.2 經(jīng)緯網(wǎng)格區(qū)域劃分和點集選擇

采用經(jīng)緯網(wǎng)對球坐標點云Q進行劃分,設(shè)有M條經(jīng)線,N條緯線,則可以將球體劃分為

Aarea=2MN

(3)

個區(qū)域，每一塊區(qū)域的角度間隔為

(4)

每一塊區(qū)域可表示為

Aarea(m,n)={(mΔθ,nΔφ),[(m+1)Δθ, (n+1)Δφ]}

n=1,2,…,N-1;m=1,2,…,M-1

(5)

第(m,n)塊區(qū)域點集的選取滿足以下關(guān)系：

(6)

式(6)中：O表示區(qū)域(m,n)中點的數(shù)量。并得到相應(yīng)球坐標下角度坐標集合：

(7)

1.3 尋找孔洞并修補

采用蒙特卡羅方法求取每塊區(qū)域點的平均密度。對(m,n)區(qū)域生成一個樣本數(shù)據(jù)集：

Ssample(m,n)={s1,s2,…st,…,sλ×O}

(8)

式(8)中：λ∈N+表示樣本點數(shù)與原點數(shù)的比例倍數(shù)；st={θt,φt}∈R2×1。滿足：

(9)

選取(m,n)區(qū)域內(nèi)的閾值半徑：

(10)

(11)

將Ssample(m,n)中滿足：

L(t,o)≤r(m,n)

(12)

的S個點選取出來組成新樣本集：

(13)

計算(m,n)區(qū)域內(nèi)點的密度：

(14)

設(shè)定一個閾值ε>0,滿足：

ρ(m,n)<ε

(15)

為有孔洞區(qū)域。尋找孔洞C個鄰域的Sample點集如圖2所示。

圖2 C個鄰域的樣本點集Fig.2 Sample point set of C neighborhoods

組成新的樣本點集：

C={c1,c2,…,cC}

(16)

并計算出鄰域內(nèi)樣本的平均點個數(shù)和密度：

(17)

對點集C形成的復雜的空間曲面在其局部面元可以利用一個簡單的二次曲面：

ri=f(θi,φi)

(18)

去逼近擬合表達;當局部面元小到一定程度甚至可以將其近似地表達成一個平面。這里采用雙線性插值算法對曲面進行插值,取

(19)

式(19)中:[θn]表示不超過θn的最大整數(shù)；[φm]表示不超過φm的最大整數(shù)。首先由f(θ,φ)、f(θ+Δθ,φ)對θn插值：

f(θn,φ)=f(θ,φ)+α[f(θ+Δθ,φ)-f(θ,φ)]

(20)

然后,由f(θ,φ+Δφ)、f(θ+Δθ,φ+Δφ)對φm插值：

f(θn,φ+Δφ)=f(θ,φ+Δφ)+α[f(θ+Δθ,φ+Δφ)-f(θ,φ)]

(21)

最后,由(θn,φ)、(θn,φ+Δφ)做第三次垂直方向的插值計算：

f(θn,φm)=f(θn,φ)+β[f(θn,φ+Δφ)-f(θn,φ)]=f(θ,φ)(1-α)(1-β)+f(θ+Δθ,φ)α(1-β)+f(θ,φ+Δφ)(1-α)β+f(θ+Δθ,φ+Δφ)αβ

(22)

插值點的個數(shù)為

(23)

將插值得到的點集轉(zhuǎn)化為三維坐標即可。本文算法流程如下。

經(jīng)緯網(wǎng)格法:輸入為存在孔洞的點云A；輸出為對孔洞填補后的點云A。

(1)通過式(1)將點云轉(zhuǎn)為球坐標Q。

(2)根據(jù)式(4)～式(5)對球坐標Q進行區(qū)域劃分,根據(jù)式(7)得到每個區(qū)域內(nèi)的點集。

(3)由式(8)、式(9)生成對應(yīng)樣本點。

(4)通過式(10)～式(15)求出孔洞區(qū)域。

(5)根據(jù)式(16)～式(23)對孔洞進行填補。

2 實驗分析

采用Stanford大學提供的Bunny(31607)三維點云數(shù)據(jù)進行仿真試驗。實驗是在MATLAB 2017a版本、i7-6700HQ四核處理器和GTX965M下進行的。經(jīng)過實驗,取N=40,M=40,ε=0.1能夠準確搜尋出所有孔洞位置。

2.1 孔洞修補

在實際掃描數(shù)據(jù)的過程中,由于被掃描物體的表面反光或操作不當,會造成點云表面存在孔洞的現(xiàn)象。為了驗證本文算法對點云孔洞具有有效的填補能力,故對點云進行人工處理,扣掉一部分,再利用本文算法找出孔洞進行填補,狀態(tài)如圖3所示。

圖3 點云Bunny狀態(tài)Fig.3 Shows the Bunny state of the cloud

從圖3可以看出,將原始Bunny點云,如圖3(a)所示,經(jīng)過人工處理后,扣出了一個方形的孔洞如圖3(b)所示。圖3(c)表明本文算法能準確地找出點云孔洞的位置,以及孔洞鄰域內(nèi)的點集。

2.2 效果對比

利用本文算法、文獻[20]算法、文獻[21]算法修補后的效果如圖4所示。

圖4 3種算法修補效果Fig.4 Three algorithm patching effects

將本文算法與文獻[20]、文獻[21]的算法填補狀態(tài)和填補點數(shù)進行對比,如表1所示。

表1 不同算法區(qū)域內(nèi)點數(shù)及填補時間對比

圖4中不同顏色代表不同算法對孔洞的填補狀態(tài)。從圖4可以看出,本文算法的填補狀態(tài)最好,能最大程度地填滿孔洞,而文獻[20]算法對孔洞的填補并不完全,文獻[21]算法對孔洞填補的過多。從表1可以看出,本文算法對Bunny點云填補后的點數(shù)與原始點云數(shù)據(jù)的點數(shù)相差不大且填補時間最短,文獻[20]算法雖然效率快但比源點云數(shù)據(jù)少,文獻[21]算法時間最長且比源點云數(shù)據(jù)多。可見本文算法能較好地補全缺失孔洞的點數(shù),填補的點云數(shù)據(jù)和原始形狀完全貼合,并能準確地描述原始細節(jié)。

3 實物孔洞填補

為驗證本文算法的實用性,利用HandySCAN 700 三維激光掃描儀獲取一組實物心形點云數(shù)據(jù),初始狀態(tài)如圖5所示。

圖5 心形點云狀態(tài)Fig.5 The state of centroid point clouds

從圖5(a)中可以看出,實際掃描出的點云數(shù)據(jù)由于物體表面反光等原因,存在許多孔洞,且分布不規(guī)則,具有隨意性。利用本文算法,把直角坐標系下的點云轉(zhuǎn)換成球坐標形式,如圖5(b)所示,可以清晰地看出,所有的孔洞均位于同一曲面上,這樣便能準確地搜索出每一個孔洞的位置,且能更為精確地提取孔洞信息,如圖5(c)中藍色部分所示(由于軟件自身原因,部分區(qū)域未顯示出來)。再利用插值算法對搜索到的孔洞進行填補,可以有效地對點云數(shù)據(jù)進行修補,修補結(jié)果如圖5(d)中黃色部分所示。對填補前后點云的點數(shù)進行對比，如表2所示。

表2 區(qū)域內(nèi)點數(shù)及填補時間

從表2可以看出填補前后,數(shù)據(jù)增加了1912個點,而算法時間只用了28 s,本文算法的修補效率也較快。

4 結(jié)論

針對三維點云數(shù)據(jù)存在孔洞區(qū)域、對后續(xù)處理造成影響的問題，提出一種基于經(jīng)緯網(wǎng)格的點云修補算法。從實驗結(jié)果可以得到，該算法能較為有效地恢復復雜物體的表面信息。比起傳統(tǒng)修補方法，本文算法能準確提取孔洞信息，較好地補全缺失孔洞的點數(shù)，填補的點云數(shù)據(jù)和原始形狀完全貼合，并能準確地描述原始細節(jié)。且用時較短，并具有更好的魯棒性，從而更好完成對復雜孔洞的修補以便進行后續(xù)重建處理等過程。