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

李由之, 唐志榮, 劉明哲

(1.成都理工大學(xué)核技術(shù)與自動(dòng)化工程學(xué)院,成都 610059；2.成都理工大學(xué)地質(zhì)災(zāi)害防治與地質(zhì)環(huán)境保護(hù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,成都 610059)

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

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

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

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

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

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

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

1 點(diǎn)云孔洞修補(bǔ)

1.1 坐標(biāo)轉(zhuǎn)換

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

(1)

圖1 三維球坐標(biāo)Fig.1 3D spherical coordinates

得到球坐標(biāo)點(diǎn)云：

Q={q1,q2,…,qK}

(2)

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

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

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

Aarea=2MN

(3)

個(gè)區(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ū)域點(diǎn)集的選取滿(mǎn)足以下關(guān)系：

(6)

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

(7)

1.3 尋找孔洞并修補(bǔ)

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

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

(8)

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

(9)

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

(10)

(11)

將Ssample(m,n)中滿(mǎn)足：

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

(12)

的S個(gè)點(diǎn)選取出來(lái)組成新樣本集：

(13)

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

(14)

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

ρ(m,n)<ε

(15)

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

圖2 C個(gè)鄰域的樣本點(diǎn)集Fig.2 Sample point set of C neighborhoods

組成新的樣本點(diǎn)集：

C={c1,c2,…,cC}

(16)

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

(17)

對(duì)點(diǎn)集C形成的復(fù)雜的空間曲面在其局部面元可以利用一個(gè)簡(jiǎn)單的二次曲面：

ri=f(θi,φi)

(18)

去逼近擬合表達(dá);當(dāng)局部面元小到一定程度甚至可以將其近似地表達(dá)成一個(gè)平面。這里采用雙線(xiàn)性插值算法對(duì)曲面進(jìn)行插值,取

(19)

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

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

(20)

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

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

(21)

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

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

(22)

插值點(diǎn)的個(gè)數(shù)為

(23)

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

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

(1)通過(guò)式(1)將點(diǎn)云轉(zhuǎn)為球坐標(biāo)Q。

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

(3)由式(8)、式(9)生成對(duì)應(yīng)樣本點(diǎn)。

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

(5)根據(jù)式(16)～式(23)對(duì)孔洞進(jìn)行填補(bǔ)。

2 實(shí)驗(yàn)分析

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

2.1 孔洞修補(bǔ)

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

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

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

2.2 效果對(duì)比

利用本文算法、文獻(xiàn)[20]算法、文獻(xiàn)[21]算法修補(bǔ)后的效果如圖4所示。

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

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

表1 不同算法區(qū)域內(nèi)點(diǎn)數(shù)及填補(bǔ)時(shí)間對(duì)比

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

3 實(shí)物孔洞填補(bǔ)

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

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

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

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

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

4 結(jié)論

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