趙文博, 劉賢明, 趙德斌, 高 文,2

(1 哈爾濱工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 哈爾濱150001； 2 北京大學(xué) 電子工程與計(jì)算機(jī)學(xué)院, 北京100871)

0 引 言

隨著計(jì)算機(jī)圖形學(xué)技術(shù)的發(fā)展,三維模型被越來越多的應(yīng)用在不同的領(lǐng)域中,如工業(yè)設(shè)計(jì),虛擬現(xiàn)實(shí),電影,電腦游戲等等。 隨著計(jì)算能力的進(jìn)步,三維模型的精度也越來越高,如今,單個(gè)三維模型可包含上萬至數(shù)百萬個(gè)頂點(diǎn)與面,這種尺度的模型通過人工進(jìn)行繪制十分困難。 為了獲取高精度的模型,通常會(huì)通過不同的設(shè)備掃描真實(shí)物體來創(chuàng)建物體表面的點(diǎn)云數(shù)據(jù),再將點(diǎn)云重構(gòu)為三維模型。 然而,通過這種方法獲得的模型,由于掃描設(shè)備精度的限制,不可避免的帶有一定的噪聲,故在使用這些模型之前,去噪是必不可少的步驟。

三維模型去噪的主要目標(biāo)是在移除噪聲的同時(shí)保持特征的形狀。 由于三維模型的分段平滑特性,對(duì)三維模型的面法向量進(jìn)行去噪,隨后更新頂點(diǎn)坐標(biāo),比直接對(duì)三維模型的頂點(diǎn)坐標(biāo)進(jìn)行去噪更加高效。 而在面法向量去噪的研究中,有相當(dāng)一部分研究是將圖像算法中的相關(guān)濾波算法遷移至三維模型去噪中,例如：雙邊濾波,中值濾波,引導(dǎo)向量濾波等等。 然而,這些方法多半為利用局部信息進(jìn)行去噪,而在圖像去噪算法中,非局部相似性已經(jīng)得到了充分的利用［1-2］。 由于三維模型具有不規(guī)則的結(jié)構(gòu),在三維模型中尋找與利用相似結(jié)構(gòu)并非易事,相關(guān)研究也較少。 部分研究以頂點(diǎn)為尋找相似結(jié)構(gòu)的基本單位,通過構(gòu)建局部描述算符來尋找相似結(jié)構(gòu),并對(duì)頂點(diǎn)坐標(biāo)進(jìn)行去噪［3-5］。 然而,對(duì)面法向量進(jìn)行去噪,再更新頂點(diǎn)坐標(biāo)比直接更新頂點(diǎn)坐標(biāo)更為有效,因此基于頂點(diǎn)的方法并不能獲得很好的結(jié)果。故本文首先提出了一種將面組織為k 環(huán)結(jié)構(gòu),并通過計(jì)算k 環(huán)結(jié)構(gòu)的相似性來尋找相似結(jié)構(gòu)的方法。隨后提出了一種結(jié)合非局部相似性與局部面法向量的濾波方法。

1 k 環(huán)結(jié)構(gòu)的相似性

圖像去噪中,通常以像素塊為基本單位來尋找相似結(jié)構(gòu)。 類似的,在三維模型去噪中需要定義一種結(jié)構(gòu),作為尋找相似結(jié)構(gòu)的基本單位。 本文選擇將面組合為k 環(huán)結(jié)構(gòu)：設(shè)三維模型中的某個(gè)面為fi,以其為中心生成的k 環(huán)結(jié)構(gòu)稱為Pi。 最開始,Pi中只包含fi,而k 環(huán)結(jié)構(gòu)是通過將所有與Pi相鄰的面加入Pi,迭代執(zhí)行該過程k 次得到的。 本文認(rèn)為,如果兩個(gè)面至少有一個(gè)共同的頂點(diǎn),則可以認(rèn)為兩個(gè)面是相鄰的。 圖1 中展示了一個(gè)2 環(huán)結(jié)構(gòu),該結(jié)構(gòu)的中心面為粉色,其余面為藍(lán)色。

圖1 2 環(huán)結(jié)構(gòu)的例子Fig. 1 An example of a 2-ring patch

接下來給出計(jì)算兩個(gè)k 環(huán)結(jié)構(gòu)相似度的方法,設(shè)待計(jì)算相似度的兩個(gè)k 環(huán)結(jié)構(gòu)為Pi與Pj。 考慮到在圖像去噪中,需要將兩個(gè)像素塊重合,再計(jì)算相似度。 由于三維模型具有不規(guī)則的結(jié)構(gòu),無法做到精確的重合兩個(gè)k 環(huán)結(jié)構(gòu)。 因此這里選擇將Pi與Pj的重心重合,以減少噪聲對(duì)形狀的影響。 隨后,考慮到兩個(gè)像素塊的相似度是通過計(jì)算每個(gè)相同位置的像素的差距得到的,而對(duì)于k 環(huán)結(jié)構(gòu),即使將2個(gè)結(jié)構(gòu)重合,也無法得到每個(gè)面的對(duì)應(yīng)面。 因此,需要為每個(gè)面找到一個(gè)與之對(duì)應(yīng)的面,并計(jì)算出對(duì)應(yīng)面的相似性。 假設(shè)fi與fj是分別來自于Pi與Pj的面,從2 個(gè)角度考慮它們之間的相似性：(1)兩者的形狀相似度；(2)兩者的位置相似度。

對(duì)于形狀相似度,選擇使用面法向量來衡量。因?yàn)槊娣ㄏ蛄渴怯庙旤c(diǎn)坐標(biāo)計(jì)算出來的,能在一定程度上代表面的形狀。 兩個(gè)面的法向量差距越大,相似度越低。 另一方面,兩個(gè)像素塊之間的像素是精確對(duì)應(yīng)的,僅僅需要考慮像素值的差距。 在三維模型中,兩個(gè)對(duì)應(yīng)面之間會(huì)有一定的距離,需要考慮距離對(duì)相似度的影響,可以通過計(jì)算兩個(gè)面之間的重心距離來衡量。 顯然,兩個(gè)面的重心距離越遠(yuǎn),其相似度就越低。 綜上所述, fi與fj的相似度Sf( fi,fj) 計(jì)算公式(1)為：

其中,ci,cj是fi與fj的重心,ni,nj是fi與fj的法向量,法向量之差加上1 是為了處理兩個(gè)面的法向量相同,但是距離很遠(yuǎn)的情況。 通過公式(1)計(jì)算出來的值越小,兩個(gè)面的相似度就越高,而相似度最高的兩個(gè)面,就可以認(rèn)為它們是對(duì)應(yīng)面。

為每個(gè)面找到對(duì)應(yīng)的面后,即可計(jì)算Pi與Pj的相似度。 兩個(gè)結(jié)構(gòu)的相似度可以視為所有對(duì)應(yīng)面的相似度的加權(quán)和。 由于每個(gè)面的大小不一,較大的面理應(yīng)具有較大的權(quán)重。 兩個(gè)結(jié)構(gòu)的相似性的計(jì)算公式(2)如下：

其中,aj是fj的面積。

在實(shí)際應(yīng)用中,一般使用2 環(huán)結(jié)構(gòu),過小的結(jié)構(gòu)會(huì)受到噪聲的干擾,而較大的結(jié)構(gòu)會(huì)大幅度提高計(jì)算相似度的時(shí)間復(fù)雜度。 對(duì)于每個(gè)面,將在5 環(huán)范圍內(nèi)尋找相似結(jié)構(gòu),5 環(huán)內(nèi)大致包含200 個(gè)面,這樣可以將尋找相似結(jié)構(gòu)的時(shí)間控制在合理的范圍內(nèi)。 在圖2中,給出該算法在兩個(gè)噪聲模型上尋找相似結(jié)構(gòu)的結(jié)果。 為了方便演示,圖2 中僅僅顯示找到的相似結(jié)構(gòu)的中心。 圖2(a)中,粉色的面為目標(biāo)面,位于特征的邊緣,而找到的相似結(jié)構(gòu)的中心均位于特征邊緣；圖2(b)中,粉色的面位于一段曲面上,這段曲面沒有明顯的特征結(jié)構(gòu),該算法還是能夠找到正確的相似結(jié)構(gòu)。 這證明了該算法的有效性與魯棒性。

圖2 在有噪聲模型上尋找相似結(jié)構(gòu)的結(jié)果Fig. 2 The results of finding similar structures on noisy meshes

2 利用自相似性優(yōu)化引導(dǎo)向量濾波

圖像去噪通常會(huì)將相似結(jié)構(gòu)中的像素加入濾波中,在三維模型中也可以使用類似的方法。 選擇以引導(dǎo)向量濾波為基礎(chǔ),在對(duì)面fi進(jìn)行濾波時(shí),除了對(duì)局部結(jié)構(gòu)中的面進(jìn)行濾波,還將與Pi相似的若干個(gè)結(jié)構(gòu)中與fi相對(duì)應(yīng)的面加入到濾波中,以此利用非局部相似性優(yōu)化濾波結(jié)果。 具體的,對(duì)于三維模型中的某個(gè)面fi,利用相似結(jié)構(gòu)的對(duì)應(yīng)面與局部結(jié)構(gòu)進(jìn)行濾波的公式(3)為：

其中,Ni是以fi為中心的1 環(huán)結(jié)構(gòu),也就是局部結(jié)構(gòu)中的面的集合； gi,gj是引導(dǎo)向量； SFi是與Pi相似的結(jié)構(gòu)中與fi相對(duì)的面的集合,即非局部相似結(jié)構(gòu),該集合的大小為CS； Gd,Gg與GS是高斯權(quán)重函數(shù), 對(duì)應(yīng)的權(quán)重參數(shù)為σd,σg與σs；ei是歸一化因子,保證最后得到的向量的模長為1。

公式(3)中,如果僅僅使用相似面進(jìn)行加權(quán),會(huì)在特征邊形成很明顯的帶狀區(qū)域,圖3 中展示了僅使用相似結(jié)構(gòu)時(shí)產(chǎn)生的帶狀區(qū)域。 可以看到在邊緣處,以及距離邊緣一個(gè)面的位置,形成了明顯的帶狀區(qū)域。 這是因?yàn)樵谶@些區(qū)域,參與濾波的相似面會(huì)呈現(xiàn)類似的帶狀分布。 這種現(xiàn)象會(huì)嚴(yán)重影響主觀評(píng)價(jià)結(jié)果。 故在濾波中同時(shí)使用局部與非局部面是必要的。

圖3 由濾波產(chǎn)生的帶狀區(qū)域Fig. 3 An example of banding region after filtering

3 參數(shù)設(shè)置與實(shí)驗(yàn)結(jié)果

本文使用的5 個(gè)實(shí)驗(yàn)?zāi)Ｐ蜑椋篎andisk, Sphere,Julius, Twelve, Block,其中Twelve 模型添加了脈沖噪聲,而其他模型添加了不同等級(jí)的高斯噪聲。 同時(shí),選擇如下的方法進(jìn)行實(shí)驗(yàn)結(jié)果對(duì)比：雙邊面法向量濾波(BNF),引導(dǎo)向量法向量濾波(GNF),基于L0 優(yōu)化的去噪(L0M),快速保持特征的濾波算法(FE), 本文中的算法則稱為SE。 由于本文算法是一個(gè)對(duì)GNF 進(jìn)行優(yōu)化的算法,因此去噪流程與GNF相同,其參數(shù)設(shè)置接近于GNF。 對(duì)于每個(gè)模型,需要進(jìn)行Nf次面法向量濾波,每次濾波后需進(jìn)行Nv次更新頂點(diǎn)坐標(biāo),σd等于該模型的平均重心距離的2 倍,其他參數(shù)的設(shè)置見表1。

表1 本文算法的參數(shù)設(shè)置Tab. 1 Parameter settings of SE

表2 中給出客觀實(shí)驗(yàn)結(jié)果包含兩部分：面法向量誤差Ea與頂點(diǎn)位置誤差Ev, 每個(gè)模型的最優(yōu)客觀結(jié)果將被加粗。 由于模型尺度的不同,頂點(diǎn)誤差尺度也有較大的區(qū)別。 為了便于比較,Ev將以科學(xué)計(jì)數(shù)法表示,且冪次數(shù)寫在表格前面,在計(jì)算平均值時(shí),忽略冪次數(shù)。

表2 本文與其他算法的客觀實(shí)驗(yàn)結(jié)果對(duì)比Tab. 2 Performance comparisons between SE and the state-of-the-art methods

從表2 中可以看出,該算法在兩個(gè)指標(biāo)上表現(xiàn)優(yōu)異,在10 個(gè)結(jié)果中,該算法獲得了8 個(gè)最優(yōu)值,平均結(jié)果大幅度領(lǐng)先于其他算法,這充分證明了該算法的有效性。 值得注意的是, Sphere 與Julius 這兩個(gè)模型中的曲面較多,故幾乎未考慮特征恢復(fù),重視平滑的BNF 算法表現(xiàn)較好。

最后,進(jìn)行主觀結(jié)果的比較,圖4、圖5 中給出Sphere 與Twelve 兩個(gè)模型的主觀結(jié)果。 圖4 中,本文的算法在曲面與特征恢復(fù)方面均取得了良好的效果,而L0M 與GNF 在曲面恢復(fù)時(shí)結(jié)果不夠平滑,FE與BNF 雖然可以較好的恢復(fù)曲面,但是在特征邊上留下了鋸齒狀的噪聲。 圖5 中,BNF、FE 與L0M 均無法恢復(fù)特征,GNF 與本文的算法則可以正確的恢復(fù)角部特征,但是對(duì)于邊緣,本文的算法由于使用了非局部信息,恢復(fù)出的邊緣更加平直,GNF 的結(jié)果中,邊緣則有一定程度的彎曲。

圖4 Sphere 模型的去噪結(jié)果對(duì)比Fig. 4 Illustration of thedenoising results of Sphere

圖5 Twelve 模型的去噪結(jié)果對(duì)比Fig. 5 Illustration of the denoising results of Twelve

4 結(jié)束語

本文提出了一種基于非局部相似性的三維模型去噪算法。 為了在不規(guī)則的三維模型上尋找相似結(jié)構(gòu),我們定義了k 環(huán)結(jié)構(gòu),并給出了計(jì)算兩個(gè)k 環(huán)結(jié)構(gòu)相似性的方法。 在面法向量去噪時(shí),為了避免產(chǎn)生帶狀區(qū)域,該算法同時(shí)利用了非局部相似結(jié)構(gòu)與局部面法向量進(jìn)行濾波。 實(shí)驗(yàn)結(jié)果表明,該算法在主觀與客觀對(duì)比上均能取得良好的結(jié)果,并且在特征恢復(fù)方面有獨(dú)特的優(yōu)勢。