基于混合樹(shù)的改進(jìn)泊松曲面重建算法

潘方超,劉 瑾*,楊海馬,趙紅壯,陳 偉,張 銳,張建偉

(1.上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院,上海 201620;2.上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093;3.中國(guó)科學(xué)院 空間主動(dòng)光電技術(shù)重點(diǎn)實(shí)驗(yàn)室,上海 200083)

引 言

隨著現(xiàn)代社會(huì)科學(xué)技術(shù)的不斷發(fā)展,點(diǎn)云處理與曲面重建技術(shù)在各個(gè)領(lǐng)域的應(yīng)用顯得日益重要。點(diǎn)云處理與曲面重建技術(shù)是文物保護(hù)、醫(yī)工交叉、智慧城市、視覺(jué)導(dǎo)航、航空航天等領(lǐng)域不可或缺的技術(shù)[1-5]。點(diǎn)云處理技術(shù)是3維重建逆向工程重要的一步,其處理結(jié)果直接關(guān)系后續(xù)重建的精確度,而曲面重建就是根據(jù)點(diǎn)云處理過(guò)后的被測(cè)物體完整數(shù)據(jù)獲得其3維表面模型[6]。2006年,KAZHDAN等人[7]首次提出泊松曲面重建算法(Poisson surface reconstruction,PSR),此方案將重建轉(zhuǎn)化為全局問(wèn)題,通過(guò)求解泊松函數(shù)并提取等值面完成有向點(diǎn)集的空間重建。此后該團(tuán)隊(duì)分別改進(jìn)原算法為并行泊松曲面重建方法[8]和屏蔽泊松重建算法(screened Poisson surface reconstruction,SPSR)[9],使原算法分別提高了處理速度,降低了時(shí)間復(fù)雜度。SHEN等人[10]提出一種基于體素感知的重建方法,通過(guò)將3維物體分解成多個(gè)組件,分塊預(yù)測(cè)重組實(shí)現(xiàn)高分辨率表面重建。KAZHDAN等人[11]提出一種包絡(luò)約束下的泊松曲面重建方法(Poisson surface reconstruction with envelope constraints,PSR-EC),通過(guò)施加狄利克雷邊界條件,迫使重建的隱函數(shù)在這個(gè)約束表面之外為零,使缺失數(shù)據(jù)區(qū)域獲得了大幅度改進(jìn)。WEN等人[12]提出一種基于三角面片周長(zhǎng)的閾值分割方法,有效避免了重建過(guò)程中偽曲面的生成。LI等人[13]提出一種基于移動(dòng)廣義三棱柱的等值面提取算法,有效解決了表面重建過(guò)程中等值面提取的剖分二義性和拓?fù)涠x性問(wèn)題。HUANG等人[14]提出一種法線定向方法,解決了由于點(diǎn)云法向量方向不一致導(dǎo)致重構(gòu)曲面出現(xiàn)偏差的問(wèn)題。AMENTA等人[15]提出了一種采用 Voronoi濾波分段線性逼近平滑表面的重建方法,實(shí)現(xiàn)對(duì)密集采樣點(diǎn)云的高精確性表面拓?fù)渲亟āHOU等人[16]提出了一種引入可見(jiàn)性模型和稠密可見(jiàn)性技術(shù)的表面重建,使重建更好地保持場(chǎng)景細(xì)節(jié)。

以上部分是采用局部擬合、分塊預(yù)測(cè)拓?fù)潢P(guān)系并拼接成完整表面模型的方法,雖然在局部能取得較好效果,但是不能在全局情況下擬合表面。其余全局方法多是在法點(diǎn)云濾波、向量估計(jì)或生成面片等階段對(duì)算法作出優(yōu)化。本文作者則是在點(diǎn)云存儲(chǔ)與搜索階段提出一種混合樹(shù)索引方法,平衡了八叉樹(shù)和二叉樹(shù)之間的矛盾,在建樹(shù)過(guò)程中逐層記錄體素內(nèi)點(diǎn)云數(shù)量以期對(duì)局部點(diǎn)云進(jìn)行密度評(píng)估,針對(duì)稀疏部分進(jìn)行不同程度的稠密化,以完成更加精細(xì)的重建并提升算法效率。

1 泊松重建與改進(jìn)

1.1 泊松算法概述

1.2 點(diǎn)云分類(lèi)與存儲(chǔ)

估計(jì)3維點(diǎn)云中某點(diǎn)的法向量可以歸納為兩個(gè)步驟：一是確定某點(diǎn)的特定鄰域;二是將該鄰域內(nèi)所有點(diǎn)擬合出最優(yōu)平面,得到所要估計(jì)的法向量。本文中分別在點(diǎn)云存儲(chǔ)與搜索階段進(jìn)行優(yōu)化,主要步驟如圖1所示。

圖1 算法流程圖

掃描得來(lái)的散亂點(diǎn)云數(shù)據(jù)分布混亂,消耗內(nèi)存空間大,對(duì)后續(xù)處理帶來(lái)很大困難,因此建立一種簡(jiǎn)明的點(diǎn)云拓?fù)潢P(guān)系、高效的存儲(chǔ)與搜索方法至關(guān)重要。八叉樹(shù)和二叉樹(shù)是最常用適用于3維空間點(diǎn)云數(shù)據(jù)劃分存儲(chǔ)的方式,其中八叉樹(shù)算法實(shí)現(xiàn)簡(jiǎn)單、效率高,二叉樹(shù)在數(shù)據(jù)鄰域搜索比較有優(yōu)勢(shì),四叉樹(shù)等其它樹(shù)形結(jié)構(gòu)適用于2維空間以及其它形式數(shù)據(jù)的處理。鑒于3維點(diǎn)云數(shù)據(jù)的空間特性與數(shù)據(jù)量,本文中提出使用基于八叉樹(shù)和二叉樹(shù)混合樹(shù)進(jìn)行3維空間點(diǎn)云數(shù)據(jù)的分割與搜索,如圖2所示,旨在減小算法的時(shí)間復(fù)雜度與空間復(fù)雜度。

圖2 混合樹(shù)建樹(shù)示意圖

具體做法見(jiàn)下。首先求出點(diǎn)集S所有點(diǎn)云數(shù)據(jù)的幾何中心：

(1)

式中,si表示點(diǎn)集S中第i個(gè)點(diǎn)構(gòu)成的向量,然后求出所有點(diǎn)與中心點(diǎn)c的距離以及所有n個(gè)距離的高斯分布,分布在[μ-3σ,μ+3σ]區(qū)間內(nèi)的點(diǎn)集記為S1,[μ-3σ,μ+3σ]區(qū)間外的點(diǎn)集記為S2,μ和σ分別為高斯的期望值與標(biāo)準(zhǔn)差。對(duì)點(diǎn)集S1和S2分別建立線性八叉樹(shù)和二叉樹(shù)進(jìn)行點(diǎn)云的存儲(chǔ)與索引。

為了有效過(guò)濾點(diǎn)云集合中的噪聲點(diǎn)并平衡濾波與細(xì)節(jié)保持之間的矛盾,提出以下點(diǎn)云能量模型E1：

(2)

其中：

(3)

式中,s是點(diǎn)集S中任意一點(diǎn),lS1,i表示點(diǎn)集S1中第i點(diǎn)的標(biāo)簽,D(lS1,i)則表示其權(quán)重,lS2,j表示點(diǎn)集S2中第j點(diǎn)的標(biāo)簽,D(lS2,j)則表示其權(quán)重,W(lS1,i,lS2,j)表示點(diǎn)集S1和S2邊緣重合點(diǎn)的能量對(duì),αS1表示點(diǎn)集S1的權(quán)重,αS2表示點(diǎn)集S2的權(quán)重,αs取αS1或αS2均可,實(shí)際計(jì)算過(guò)程中取為αS1,r表示點(diǎn)到點(diǎn)集中心的距離,σs是松弛系數(shù),N表示點(diǎn)集S1和S2交集中點(diǎn)云個(gè)數(shù),權(quán)重因子1-exp[-r2/(2σs2)]的作用是削弱邊緣點(diǎn)云的能量,起到過(guò)濾噪點(diǎn)的作用。

當(dāng)點(diǎn)云非常密集時(shí),上述能量模型會(huì)在兩組點(diǎn)云邊界處出現(xiàn)二義性,導(dǎo)致重建曲面過(guò)程的錯(cuò)誤連接,為此引入點(diǎn)云的似然能量E2：

(4)

其中,

(5)

式中,E2是衡量邊緣點(diǎn)云標(biāo)簽分配是否錯(cuò)誤的懲戒能量函數(shù),對(duì)于S1∩S2內(nèi)每一個(gè)點(diǎn)云,它都具有二義性,用于描述是否在點(diǎn)集內(nèi)部,遍歷點(diǎn)集S1中的q個(gè)點(diǎn),根據(jù)點(diǎn)云實(shí)際分布選擇具體的懲戒能量函數(shù)Uout(S1)和Uin(S1)。為了評(píng)估標(biāo)簽分配的可能性,引入空間支持函數(shù)f(S3)度量點(diǎn)集所在空間的松弛性：

(6)

其中,

S3={s|S1∩S2≠?}

(7)

為了使f(S3)更好地描述似然能量函數(shù)E2,設(shè)：

(8)

式中,λ是平衡因子,β是大于所有點(diǎn)f(S3)的常數(shù),令：

E=E1+λ2E2+λ3E3

(9)

式中,λ2和λ3是縮放常數(shù),E是點(diǎn)云的總能量,E3為提高重建表面質(zhì)量引入的面片能量項(xiàng),且：

(10)

其中,

wf=1-min{cosφ,cosφ}

(11)

式中,φ和φ是邊界某點(diǎn)與兩個(gè)點(diǎn)集中心點(diǎn)預(yù)估平面的夾角。

最后通過(guò)Maxflow-Mincut實(shí)現(xiàn)總能量的最小化,完成點(diǎn)云的分組存儲(chǔ)與濾波。

1.3 法向量估計(jì)

法向量估計(jì)可以分為兩個(gè)步驟：一是以某點(diǎn)為中心做適當(dāng)鄰域;二是在此鄰域內(nèi)將所有點(diǎn)擬合一個(gè)最佳平面求出法向量。為提高算法輸入端點(diǎn)云的法向量精度,本文中算法對(duì)法向量估計(jì)作如下改進(jìn),如圖3所示。

圖3 法向量估計(jì)示意圖

求某點(diǎn)s(sx,sy,sz)對(duì)應(yīng)的法向量為ns(nsx,nsy,nsz)。(a)建立以s點(diǎn)為圓心、R為半徑的球面：(x-sx)3+(y-sy)3+(z-sz)3=R3;(b)設(shè)置初始點(diǎn)云數(shù)量統(tǒng)計(jì)區(qū)間[23i,23(i+1)];(c)判斷以s點(diǎn)為中心的23i個(gè)最小體素單元是否完全落入球面內(nèi);(d)若條件(c)判斷為假,將當(dāng)前值i-1,直至條件(c)判斷為真;(e)若條件(c)判斷為真,統(tǒng)計(jì)球面內(nèi)點(diǎn)云數(shù)量并計(jì)算它占樣本集內(nèi)點(diǎn)云總數(shù)的比例ri,顯然ri取值在區(qū)間[0,1]之間,當(dāng)ri取值在[μ-3σ,μ+3σ]左側(cè)外,認(rèn)為點(diǎn)云塊稀疏,進(jìn)行針對(duì)性稠密化。

對(duì)s點(diǎn)所在鄰域使用改進(jìn)移動(dòng)最小二乘法進(jìn)行點(diǎn)云的稠密化,將上文所得ri作為移動(dòng)最小二乘法中的系數(shù)向量ri,球面以?xún)?nèi)區(qū)域作為s點(diǎn)的影響區(qū)域,擬合函數(shù)可表示為：

(12)

選用立方基：

pT=(1,x,y,x2,xy,y2,x3,x2y,xy2,y3),

(m=10)

(13)

則擬合函數(shù)為：

f(x,y)=r1+r2x+r3y+r4x2+r5xy+

r6y2+r7x3+r8x2y+r9xy2+r10y3

(14)

即：

(15)

擬合完成后就可以在s點(diǎn)附近擬合三次曲線對(duì)點(diǎn)云進(jìn)行針對(duì)性的插值稠密化。

重新記錄稠密化后的鄰域點(diǎn)云數(shù)量k值。采用奇異值分解(singular value decomposition,SVD)求法向量,首先求該點(diǎn)δ鄰域內(nèi)所有k個(gè)點(diǎn)(s1,s2,s3,….sk-1,sk)到s點(diǎn)的向量fi=si-s(i=1,2,…,k)。

設(shè)置優(yōu)化函數(shù)：

(16)

進(jìn)一步推導(dǎo)有：

minnsTFFTns

(17)

式中,F由向量組fi構(gòu)成,上述問(wèn)題就轉(zhuǎn)化為目標(biāo)函數(shù)的最優(yōu)化問(wèn)題,即：

ming(ns)=minnsTQns

(18)

式中,Q=FFT,Q是關(guān)于點(diǎn)s3個(gè)坐標(biāo)分量的協(xié)方差矩陣。對(duì)矩陣F進(jìn)行SVD分解即可得到s點(diǎn)的法向量,最后通過(guò)最小生成樹(shù)法對(duì)所有法向量的方向進(jìn)行矯正,獲得朝向一致的法向量[17-18]。

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

為了評(píng)價(jià)本文中所提重建算法的效果以及與其它不同算法對(duì)來(lái)自公共數(shù)據(jù)集進(jìn)行重建的性能對(duì)比,選取了Artec 3D公司的曲軸箱、齒輪、螺絲、渦輪進(jìn)行算法的比對(duì)分析。

2.1 重建細(xì)節(jié)比較

首先,在建樹(shù)深度分別為6～10的情況下采用本文中的算法對(duì)曲軸箱模型進(jìn)行表面重建,從圖4可以看出,隨著樹(shù)深的增加,模型重建表面精度不斷提高,并且在不同樹(shù)深情況下都表現(xiàn)出較好的效果。可見(jiàn)樹(shù)深是影響重建效果的重要參數(shù)。樹(shù)深增加,索引到的點(diǎn)云數(shù)量增加,重建結(jié)果的細(xì)節(jié)也就更好。

圖4 曲軸箱在本文中算法不同樹(shù)深下的重建效果

在對(duì)算法效果的橫向比較評(píng)價(jià)中,選取了PSR算法、SPSR算法、與PSR-EC算法與本文中所提算法進(jìn)行比較,將每種算法的可變參數(shù)調(diào)制與所用掃描模型最佳匹配的情況下,各算法重建效果與局部細(xì)節(jié)放大圖如圖5所示。PSR算法由于沒(méi)有引入與模型形態(tài)相關(guān)的信息,比如掃描過(guò)程中的視線信息,導(dǎo)致重建結(jié)果在細(xì)節(jié)方面表現(xiàn)較差。SPSR算法雖然引入了點(diǎn)作為插值約束使重建細(xì)節(jié)有所改善,但其算法效率仍然不高。SPR-EC算法雖然算法效率較高,但由于表面提取過(guò)程中以遠(yuǎn)離真實(shí)解為代價(jià),使得重建表面遠(yuǎn)離真實(shí)模型表面。本文中的算法由于搜索方法的改進(jìn)使得算法效率明顯提高,并且根據(jù)前文改進(jìn)的點(diǎn)云稠密化插值方法針對(duì)性地對(duì)部分稀疏點(diǎn)云稠密化,結(jié)果如表1所示。針對(duì)不同模型分別引入了0.86%～1.95%的重建頂點(diǎn)信息,在不影響算法效率的前提下,使法向量估計(jì)階段更加精確,展現(xiàn)出了最佳的重建完整性,更加貼近掃描模型真實(shí)表面細(xì)節(jié)。

表1 各算法重建實(shí)際所用頂點(diǎn)數(shù)

圖5 模型在不同算法下最優(yōu)重建效果與細(xì)節(jié)對(duì)比

2.2 算法效率對(duì)比

如圖6所示,在算法運(yùn)行時(shí)間對(duì)比實(shí)驗(yàn)中,隨著樹(shù)深的增加,各算法運(yùn)行時(shí)間呈指數(shù)增加。本文中的算法引入點(diǎn)云密度評(píng)估,并在法向量估計(jì)階段采用自適應(yīng)球半徑的搜索方法,相比PSR算法與SPSR算法,速度均有明顯提高,且在樹(shù)深值較小時(shí)更加顯著;相比PSR算法,速度平均提高約33%,比SPSR算法速度平均提高約15%。但由于PSR-EC算法引入了Dirichlet條件作為提取等值面的包絡(luò)約束,降低了內(nèi)存開(kāi)銷(xiāo),本文中的算法與之相比,速度仍然較慢。

圖6 各模型在不同算法下的重建時(shí)間對(duì)比

2.3 誤差評(píng)價(jià)

此外,由于原始數(shù)據(jù)與重建后數(shù)據(jù)有點(diǎn)云模型和網(wǎng)格模型等表示形式,所以,本文中選擇原始數(shù)據(jù)點(diǎn)云形式與重建數(shù)據(jù)網(wǎng)格形式之間的豪斯多夫距離[19](Hausdorff distance,HD)、原始點(diǎn)云模型到重建表面的均方根誤差(root mean square error,RMSE)來(lái)定性評(píng)價(jià)對(duì)比實(shí)驗(yàn)中各個(gè)算法重建表面與原掃描模型表面的差距。將HD和RMSE值分別與此項(xiàng)最大值比較做歸一化處理后各算法實(shí)測(cè)值[20]如圖7和圖8所示。可以看出,本文中算法的誤差在對(duì)比實(shí)驗(yàn)中最小。

圖7 模型在不同算法、不同樹(shù)深下實(shí)測(cè)HD值

圖8 模型在不同算法、不同樹(shù)深下實(shí)測(cè)RMSE值

為了更加直觀地展現(xiàn)重建表面模型與原始模型的偏差,使用相關(guān)軟件將重建表面模型與原始模型作3-D比較處理,具體操作方法如下：(a)將原始模型轉(zhuǎn)換為step機(jī)械文件格式;(b)將重建表面模型與原始模型導(dǎo)入3-D檢測(cè)軟件;(c)依次執(zhí)行初始對(duì)齊,最佳擬合對(duì)齊,3-D比較命令,4組實(shí)驗(yàn)中參數(shù)設(shè)置均相同。

本組設(shè)置中設(shè)置可顯示公差范圍為[-0.1 mm,+0.1 mm],可接受公差范圍為[-0.01 mm,+0.01 mm],且在此范圍內(nèi)的模型匹配范圍顯示綠色,模型3-D比較的可視化結(jié)果根據(jù)各區(qū)域?qū)嶋H公差的不同顯示不同顏色(參見(jiàn)圖9中右側(cè)色條)。在此公差設(shè)置下,統(tǒng)計(jì)各個(gè)算法重建結(jié)果在可接受公差范圍內(nèi)的比例、均方根值、平均偏離程度與離散程度來(lái)衡量重建結(jié)果的準(zhǔn)確性,實(shí)驗(yàn)結(jié)果如圖9和表2所示。本文中的算法的各項(xiàng)指標(biāo)總體表現(xiàn)最優(yōu),但有個(gè)別模型的平均偏離和離散程度不是最小,原因是部分點(diǎn)云稠密化過(guò)程引入了較多的噪點(diǎn)。

表2 模型誤差項(xiàng)實(shí)測(cè)表

圖9 模型在各算法下的重建結(jié)果與原模型3-D比較圖

3 結(jié) 論

從點(diǎn)云的存儲(chǔ)與搜索角度出發(fā)對(duì)泊松重建算法提出了改進(jìn),采用一種新的點(diǎn)云搜索方法,提高了算法效率;并根據(jù)引入的能量函數(shù)對(duì)點(diǎn)云進(jìn)行密度評(píng)估,根據(jù)統(tǒng)計(jì)結(jié)果對(duì)點(diǎn)云稀疏過(guò)程進(jìn)行針對(duì)性的稠密化,使得重建結(jié)果細(xì)節(jié)表現(xiàn)更好。經(jīng)過(guò)在4個(gè)不同數(shù)據(jù)集上的實(shí)驗(yàn)對(duì)比,本文中算法的處理速度對(duì)比泊松表面重建算法和屏蔽泊松算法有較大提高,并且在重建的完整性與精確性總體表現(xiàn)最優(yōu),偏離原模型的程度最小,對(duì)中小型物體的重建與誤差評(píng)價(jià)具有借鑒意義。下一步工作將針對(duì)泊松方程求解過(guò)程與約束條件展開(kāi)研究,以期降低算法的時(shí)間復(fù)雜度,使重建效率更高。