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

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

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

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

1.1 泊松算法概述

1.2 點(diǎn)云分類與存儲(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 算法流程圖

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

圖2 混合樹建樹示意圖

具體做法見下。首先求出點(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)差。對點(diǎn)集S1和S2分別建立線性八叉樹和二叉樹進(jìn)行點(diǎn)云的存儲(chǔ)與索引。

為了有效過濾點(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)的能量對,αS1表示點(diǎn)集S1的權(quán)重,αS2表示點(diǎn)集S2的權(quán)重,αs取αS1或αS2均可,實(shí)際計(jì)算過程中取為α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)云的能量,起到過濾噪點(diǎn)的作用。

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

(4)

其中,

(5)

式中,E2是衡量邊緣點(diǎn)云標(biāo)簽分配是否錯(cuò)誤的懲戒能量函數(shù),對于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ù)估平面的夾角。

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

1.3 法向量估計(jì)

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

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

求某點(diǎn)s(sx,sy,sz)對應(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)行針對性稠密化。

對s點(diǎn)所在鄰域使用改進(jìn)移動(dòng)最小二乘法進(jìn)行點(diǎn)云的稠密化,將上文所得ri作為移動(dòng)最小二乘法中的系數(shù)向量ri,球面以內(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)附近擬合三次曲線對點(diǎn)云進(jìn)行針對性的插值稠密化。

重新記錄稠密化后的鄰域點(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)成,上述問題就轉(zhuǎn)化為目標(biāo)函數(shù)的最優(yōu)化問題,即：

ming(ns)=minnsTQns

(18)

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

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

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

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

首先,在建樹深度分別為6～10的情況下采用本文中的算法對曲軸箱模型進(jìn)行表面重建,從圖4可以看出,隨著樹深的增加,模型重建表面精度不斷提高,并且在不同樹深情況下都表現(xiàn)出較好的效果?？梢姌渖钍怯绊懼亟ㄐЧ闹匾獏?shù)。樹深增加,索引到的點(diǎn)云數(shù)量增加,重建結(jié)果的細(xì)節(jié)也就更好。

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

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

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

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

2.2 算法效率對比

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

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

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)來定性評(píng)價(jià)對比實(shí)驗(yàn)中各個(gè)算法重建表面與原掃描模型表面的差距。將HD和RMSE值分別與此項(xiàng)最大值比較做歸一化處理后各算法實(shí)測值[20]如圖7和圖8所示?？梢钥闯?本文中算法的誤差在對比實(shí)驗(yàn)中最小。

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

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

為了更加直觀地展現(xiàn)重建表面模型與原始模型的偏差,使用相關(guān)軟件將重建表面模型與原始模型作3-D比較處理,具體操作方法如下：(a)將原始模型轉(zhuǎn)換為step機(jī)械文件格式;(b)將重建表面模型與原始模型導(dǎo)入3-D檢測軟件;(c)依次執(zhí)行初始對齊,最佳擬合對齊,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公差的不同顯示不同顏色(參見圖9中右側(cè)色條)。在此公差設(shè)置下,統(tǒng)計(jì)各個(gè)算法重建結(jié)果在可接受公差范圍內(nèi)的比例、均方根值、平均偏離程度與離散程度來衡量重建結(jié)果的準(zhǔn)確性,實(shí)驗(yàn)結(jié)果如圖9和表2所示。本文中的算法的各項(xiàng)指標(biāo)總體表現(xiàn)最優(yōu),但有個(gè)別模型的平均偏離和離散程度不是最小,原因是部分點(diǎn)云稠密化過程引入了較多的噪點(diǎn)。

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

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

3 結(jié) 論

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