產(chǎn)海林，曹 璨

(1.中國(guó)科學(xué)技術(shù)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥 230026； 2.中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥 230026)

基于局部特征匹配的網(wǎng)格去噪算法

產(chǎn)海林1，曹 璨2

(1.中國(guó)科學(xué)技術(shù)大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 合肥230026；2.中國(guó)科學(xué)技術(shù)大學(xué) 信息科學(xué)技術(shù)學(xué)院，安徽 合肥230026)

由于三維掃描設(shè)備精度不足以及各類人為因素的影響，掃描獲取的三維模型不可避免地包含了噪聲信息。如何有效地去除掃描模型中的噪聲一直是一個(gè)經(jīng)典熱門問(wèn)題。文中提出了一個(gè)數(shù)據(jù)驅(qū)動(dòng)的算法，通過(guò)分析已有的噪聲模型和對(duì)應(yīng)原始模型數(shù)據(jù)，建立噪聲模型局部幾何特征與原始模型法向量之間的數(shù)據(jù)映射關(guān)系，再利用此信息局部特征匹配得到去噪后網(wǎng)格。實(shí)驗(yàn)結(jié)果表明，該方法可以有效地對(duì)網(wǎng)格進(jìn)行去噪，在去除噪聲的同時(shí)，可以很好地保持網(wǎng)格的特征結(jié)構(gòu)。

網(wǎng)格去噪；局部特征匹配；數(shù)據(jù)驅(qū)動(dòng)；引導(dǎo)法向?yàn)V波

0 引言

三維掃描儀和深度相機(jī)的流行大大簡(jiǎn)化了三維幾何建模的過(guò)程，使得人們可以很容易地得到各種真實(shí)世界物體的三維形狀數(shù)據(jù)。但與藝術(shù)家手動(dòng)生成的模型不同的是，掃描得到的模型往往包含各種噪聲。在數(shù)字幾何處理中，去除掃描模型中的噪聲一直是一個(gè)經(jīng)典熱門的問(wèn)題。本文主要探討了對(duì)三角網(wǎng)格的去噪問(wèn)題，還有一些工作[1]直接考慮了掃描儀獲取的點(diǎn)云數(shù)據(jù)的去噪問(wèn)題。

網(wǎng)格去噪的本質(zhì)是，從測(cè)量數(shù)據(jù)M*=M+ε中去除噪聲ε，得到真實(shí)原始網(wǎng)格M。原始網(wǎng)格M和噪聲ε均未知，這本身就是個(gè)病態(tài)問(wèn)題。由于噪聲和網(wǎng)格的尖銳邊角特征都是高頻的，這導(dǎo)致很難將它們分離開，因而網(wǎng)格去噪問(wèn)題面臨的最大挑戰(zhàn)是如何在去除噪聲的同時(shí)可以保持網(wǎng)格的原始特征。

文獻(xiàn)[2-4]通過(guò)一個(gè)低通濾波器來(lái)去除高頻噪聲，由于各向同性，這些方法不能區(qū)分噪聲和網(wǎng)格特征，在去除噪聲的同時(shí)也會(huì)丟失網(wǎng)格模型的尖銳特征。Jones等人[5]、Fleishman等人[6]提出了各向異性算法，將圖像去噪中的雙邊濾波擴(kuò)展到了網(wǎng)格中，根據(jù)三維網(wǎng)格的幾何特征來(lái)改變雙邊濾波的權(quán)重，達(dá)到保持特征的目的。文獻(xiàn)[7-12]提出了兩步走的方法，首先將濾波器作用到法向量域，調(diào)整法向量，再利用調(diào)整后的法向量信息來(lái)更新頂點(diǎn)坐標(biāo)。雖然以上基于濾波的方法對(duì)各類噪聲模型一定程度上可以有效地去噪，但其需要用戶大量的手動(dòng)調(diào)整參數(shù)工作來(lái)得到一個(gè)較合理的結(jié)果。

基于優(yōu)化的方法，通過(guò)構(gòu)建求解優(yōu)化問(wèn)題得到一個(gè)滿足一系列約束同時(shí)與輸入近似的模型。文獻(xiàn)[13]使用了L0優(yōu)化，要求潛在原始模型是分片光滑的。文獻(xiàn)[14]使用了壓縮感知方法，將模型與噪聲分離開，其要求噪聲是獨(dú)立同分布的。這些方法對(duì)于滿足條件的特定幾何特征或噪聲類型可以生成好的結(jié)果，但對(duì)于其他不符合條件的特征和噪聲類型就很難處理。此外，優(yōu)化過(guò)程往往都很慢。

文獻(xiàn)[15]采用了數(shù)據(jù)驅(qū)動(dòng)的方法，利用大量的帶噪聲模型和原始模型來(lái)做學(xué)習(xí)回歸，建立了兩者間的回歸模型，達(dá)到去除噪聲的目的。數(shù)據(jù)驅(qū)動(dòng)方法的好處在于無(wú)需人工調(diào)整參數(shù)，且不對(duì)模型幾何特征和噪聲類型做特殊限定。但文獻(xiàn)[15]采用了單隱層的神經(jīng)網(wǎng)絡(luò)對(duì)所有數(shù)據(jù)進(jìn)行全局?jǐn)M合，得到回歸函數(shù)，限于神經(jīng)網(wǎng)絡(luò)的表達(dá)能力，全局方法容易產(chǎn)生過(guò)擬合以及存在受無(wú)關(guān)信息干擾等問(wèn)題，其去噪效果依然存在著一定缺陷。

為此，本文在數(shù)據(jù)驅(qū)動(dòng)方法的基礎(chǔ)上，采用了局部特征匹配的方法。首先，利用已有模型信息，構(gòu)建數(shù)據(jù)庫(kù)，存儲(chǔ)帶噪聲模型的局部幾何特征和原始模型面法向間的映射關(guān)系；然后在對(duì)新輸入模型做去噪時(shí)，利用數(shù)據(jù)庫(kù)中最相近的信息構(gòu)造局部擬合函數(shù)，得到校準(zhǔn)后的網(wǎng)格面法向量；最后，根據(jù)校準(zhǔn)面法向量信息來(lái)更新頂點(diǎn)坐標(biāo)，得到去噪后模型。

1 網(wǎng)格幾何特征的計(jì)算

1.1雙邊濾波與聯(lián)合濾波

(1)

式中Λ(·)為向量單位化算子。Ws、Wr為非負(fù)單調(diào)遞減核函數(shù)，分別度量了網(wǎng)格在兩面片fi、fj上的空間相似度和法向域相似度。核函數(shù)通常使用高斯函數(shù)Wσ=exp(-x2/ (2σ2))，Ws、Wr中的標(biāo)準(zhǔn)差σ分別記做σs、σr。

(2)

式中g(shù)i、gj分別為面fi、fj上的引導(dǎo)法向量，引導(dǎo)法向量的計(jì)算可以簡(jiǎn)單采用鄰域加權(quán)平均的策略：

(3)

1.2幾何特征計(jì)算

(4)

(5)

本文方法也采用了類似的思想，不同的是，本文在計(jì)算聯(lián)合濾波時(shí)采用了更加精細(xì)的策略，結(jié)合了文獻(xiàn)[16]中計(jì)算引導(dǎo)信號(hào)G的方法。一般網(wǎng)格模型都是分片光滑的，由尖銳的邊分成不同的光滑區(qū)域。式(3)中，在尖銳的邊附近直接簡(jiǎn)單地采用一鄰域加權(quán)平均作為引導(dǎo)法向量是不合理的，因?yàn)榭缭郊怃J邊的兩個(gè)區(qū)域的面法向量之間是有較大差異的。在計(jì)算式(3)中鄰域N(fi)時(shí)就應(yīng)當(dāng)僅僅考慮面fi所在光滑區(qū)域的面片。

對(duì)于鄰域的選取，考慮鄰域N(fi)的可能候選Nk(fi)，計(jì)算其面法向量一致性評(píng)估函數(shù)H(Nk)，選擇評(píng)估函數(shù)H(Nk)最小的對(duì)應(yīng)候選鄰域N*(fi)來(lái)計(jì)算引導(dǎo)濾波。評(píng)估函數(shù)H(Nk)定義如下：

H(Nk)=Φ(Nk)·R(Nk)

(6)

式中Φ(Nk)、R(Nk)分別為區(qū)域Nk上任兩個(gè)面法向量的最大差異和邊的最大差異，因而H(Nk)越小則反映了區(qū)域Nk上的面法向量越一致。

圖1為式(3)簡(jiǎn)單選取鄰域以及與本文方法的對(duì)比，從左到右依次為噪聲模型、原始模型、簡(jiǎn)單選取鄰域時(shí)法向差異、本文方法法向差異，顏色表示計(jì)算得到的引導(dǎo)法向量與原始法向量間的差異，顏色越接近藍(lán)色表示差異越小?？梢钥吹?，相比式(3)簡(jiǎn)單選取方法，本文的方法得到的引導(dǎo)法向量更加接近真實(shí)數(shù)據(jù)，為后續(xù)的去噪過(guò)程提供了一個(gè)更加魯棒準(zhǔn)確的面法向信息。

圖1 不同引導(dǎo)法向的對(duì)比

綜上，對(duì)于網(wǎng)格M上面fi的幾何特征描述子Sg,i的計(jì)算步驟如下：

(1)對(duì)于面fi的每個(gè)候選鄰域Nk(fi)，根據(jù)式(6)計(jì)算評(píng)估函數(shù)H(Nk)，選擇評(píng)估函數(shù)H(Nk)最小的鄰域作為最佳鄰域N*(fi)；

(2)計(jì)算面fi在鄰域N*(fi)上的高斯濾波作為引導(dǎo)法向gi；

(4)將不同參數(shù)對(duì)(σs,σr)的聯(lián)合法向?yàn)V波聯(lián)立起來(lái)，即得到面fi的幾何特征描述子。

2 局部特征擬合的網(wǎng)格去噪算法

對(duì)于給定的一帶噪聲網(wǎng)格，本文目的是得到去噪之后的潛在原始模型。本文算法可以分為以下三個(gè)步驟：(1)對(duì)已有模型數(shù)據(jù)做處理，計(jì)算帶噪聲模型面片上的局部幾何特征和原始模型的面法向量，并建立數(shù)據(jù)庫(kù)存儲(chǔ)兩者間的對(duì)應(yīng)關(guān)系；(2)對(duì)于輸入的帶噪聲網(wǎng)格，計(jì)算其面片上的局部幾何特征，在數(shù)據(jù)庫(kù)中查找最相近的信息來(lái)局部擬合，得到校準(zhǔn)后的面法向量；(3)基于校準(zhǔn)后的面法向量更新頂點(diǎn)坐標(biāo)，得到去噪模型。

2.1數(shù)據(jù)預(yù)處理

2.2局部特征匹配

(7)

高維流形的每個(gè)局部都可以由線性空間去逼近[17]，此處本文使用了局部線性插值來(lái)得到校準(zhǔn)法向量。 權(quán)重wj反映了面fqi與面fp的關(guān)聯(lián)程度(wj越大表示面fqi與面fp的關(guān)聯(lián)程度越大)，其通過(guò)求解以下優(yōu)化問(wèn)題得到：

(8)

此問(wèn)題可以轉(zhuǎn)化為求解方程(ZT*Z)·W=1，式中W=(w1,…,wk)T,Z=(Sq1-Sp,…,Sqk-Sp)。

圖2展示了本文局部擬合方法和文獻(xiàn)[15]的全局方法的去噪效果對(duì)比，可以看到本文方法去除噪聲效果更好，而全局?jǐn)M合方法依然殘留了一些高頻噪聲信息。

圖2 局部與全局?jǐn)M合方法的對(duì)比結(jié)果

2.3頂點(diǎn)更新

通過(guò)2.2節(jié)可以得到帶噪聲模型校準(zhǔn)后的面法向量，然后基于校準(zhǔn)后的面法向量更新頂點(diǎn)得到去噪模型。類似于很多基于法向量濾波的網(wǎng)格去噪方法[10-11,16]，本文采用以下策略進(jìn)行頂點(diǎn)更新：

(9)

式中，vi為網(wǎng)格頂點(diǎn)，nj為網(wǎng)格面法向量，cj為面的中心，F(xiàn)i為頂點(diǎn)vi的一鄰域面。

與文獻(xiàn)[11]的兩步走方法相類似，本文同樣迭代地進(jìn)行面法向量更新和頂點(diǎn)更新兩個(gè)步驟，直到得到一個(gè)最佳的結(jié)果。

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

本節(jié)中，將展示本文方法的效果圖，并與其他去噪方法的效果做對(duì)比。本文在操作系統(tǒng)為Windows 10、處理主頻為2.8 GHz、系統(tǒng)內(nèi)存16 GB的PC上，采用Microsoft Visual C+ + 2013軟件平臺(tái)實(shí)現(xiàn)了本文的算法。網(wǎng)格數(shù)據(jù)集本文采用了文獻(xiàn)[15]中的數(shù)據(jù)，主要分為兩類，一類為人工制造的各種幾何模型(CAD模型、光滑模型等)，對(duì)其加上不同類型的噪聲得到對(duì)應(yīng)的噪聲模型；另一類為實(shí)際掃描采集的帶噪聲模型，并與人工生成的無(wú)噪聲模型做好了匹配對(duì)應(yīng)。對(duì)于人工制造的模型，本文中主要測(cè)試了高斯噪聲，對(duì)每個(gè)原始模型都加上了三種不同程度的高斯噪聲。對(duì)于掃描模型，本文主要考慮了Kinect、Kinect Fusion采集的模型。

在本文實(shí)驗(yàn)中，式(4)、式(5)中的參數(shù)選取σs為l、2l、4l，其中l(wèi)為網(wǎng)格的平均邊長(zhǎng)，σr為0.1、0.2、0.35、0.5、10，則參數(shù)對(duì)(σs,σr)一共有15種組合。式(7)中k為查找最近鄰的個(gè)數(shù)，實(shí)驗(yàn)中取值為5。

網(wǎng)格去噪的目的是將帶噪聲模型最大程度地恢復(fù)至原始模型，衡量去噪性能的指標(biāo)就是經(jīng)去噪得到的三維模型與原始網(wǎng)格的接近程度，本文采用去噪模型與原始模型的面法向量的平均角度差異作為評(píng)判標(biāo)準(zhǔn)。

本文選擇了目前優(yōu)秀的去噪算法：雙邊濾波[6]、雙邊法向?yàn)V波[11]、指導(dǎo)法向?yàn)V波[16]、L0優(yōu)化[13]、級(jí)聯(lián)法向回歸[15]，將它們與本文方法進(jìn)行對(duì)比。

在圖3中，展示了本文方法與其他方法的對(duì)比，對(duì)人為加高斯噪聲的模型進(jìn)行去噪。一方面，本文方法可以很好地去除噪聲，而雙邊濾波、雙邊法向?yàn)V波、級(jí)聯(lián)法向回歸等方法都依然殘留有噪聲，去除效果不佳；另一方面，相比其他方法，本文方法可以保留更多的細(xì)節(jié)信息，而指導(dǎo)法向?yàn)V波、L0優(yōu)化等方法往往將這些細(xì)節(jié)平滑或尖銳化。同時(shí)從客觀數(shù)值上看，本文方法得到的去噪模型與原始三維網(wǎng)格更為相近，去噪效果最優(yōu)。圖3中，法相平均角度差異分別為：第一行：13.23、8.23、8.08、14.93、8.04、7.89；第二行：7.45、5.46、6.13、7.34、5.19、5.02。

圖3 不同去噪方法的對(duì)比結(jié)果

本文方法也可以很好地應(yīng)用到掃描模型上，例如圖4，對(duì)于Kinect、Kinect Fusion掃描的模型，本文方法在去除噪聲和保持特征方面依然效果很好。圖4中，第一行為Kinect模型，第二行為Kinect Fusion模型。法相平均角度差異分別為：第一行：16.03、16.276、12.38、11.26、8.72、7.57；第二行：10.72,、9.39、7.92、7.82、7.74、7.38。

圖2、圖5也展示了本文方法和級(jí)聯(lián)法向回歸方法的對(duì)比。在這些圖片中，本文局部擬合方法均比文獻(xiàn)[15]的全局?jǐn)M合方法去噪效果更好。

圖4 不同掃描模型下不同去噪方法的比較

圖5 局部與全局?jǐn)M合方法的對(duì)比結(jié)果

4 總結(jié)與展望

本文通過(guò)對(duì)帶噪聲模型與原始模型信息的充分分析，提出了一種新的局部特征擬合的網(wǎng)格去噪方法。實(shí)驗(yàn)表明，對(duì)于人為加噪聲模型和掃描模型，本文方法在去除噪聲和保持網(wǎng)格特征結(jié)構(gòu)方面都效果很好。

在后續(xù)的研究中，將嘗試采用端到端的深度學(xué)習(xí)方法(end-to-end deep learning)，將網(wǎng)格的幾何特征定義與網(wǎng)格去噪過(guò)程結(jié)合起來(lái)，利用深度神經(jīng)網(wǎng)絡(luò)的強(qiáng)大表達(dá)能力來(lái)得到一個(gè)優(yōu)異結(jié)果。

[1] 郝慧麗，劉先勇.含噪點(diǎn)云預(yù)處理技術(shù)研究[J].微型機(jī)與應(yīng)用，2012，31(12): 68-70.

[2] TAUBIN G.A signal processing approach to fair surface design[C].Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques.ACM，1995: 351-358.

[3] DESBRUN M，MEYER M，SCHR?DER P，et al.Implicit fairing of irregular meshes using diffusion and curvature flow[C].Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques.ACM，1999: 317-324.

[4] OHTAKE Y，BELYAEV A，BOGAEVSKI I.Mesh regularization and adaptive smoothing[J].Computer-Aided Design，2001，33(11): 789-800.

[5] JONES T R，DURAND F，DESBRUN M.Non-iterative，feature-preserving mesh smoothing[J].ACM Transactions on Graphics，2003，22(3): 943-949.

[6] FLEISHMAN S，DRORI I，COHEN-OR D.Bilateral mesh denoising[J].ACM Transactions on Graphics, 2003，22(3): 950-953.

[7] YAGOU H，OHTAKE Y，BELYAEV A.Mesh smoothing via mean and median filtering applied to face normals[C].Proceedings of Geometric Modeling and Processing，2002.IEEE，2002: 124-131.

[8] YAGOU H，OHTAKE Y，BELYAEV A G.Mesh denoising via iterative alpha-trimming and nonlinear diffusion of normals with automatic thresholding[C].Computer Graphics International, 2003: 28-34.

[9] SHEN Y，BARNER K E.Fuzzy vector median-based surface smoothing[J].IEEE Transactions on Visualization and Computer Graphics，2004，10(3): 252-265.

[10] SUN X，ROSIN P，MARTIN R，et al.Fast and effective feature-preserving mesh denoising[J].IEEE Transactions on Visualization and Computer Graphics，2007，13(5): 925-938.

[11] ZHENG Y，F(xiàn)U H，AU O K C，et al.Bilateral normal filtering for mesh denoising[J].IEEE Transactions on Visualization and Computer Graphics，2011，17(10): 1521-1530.

[12] WEI M，YU J，PANG W M，et al.Bi-normal filtering for mesh denoising[J].IEEE Transactions on Visualization and Computer Graphics，2015，21(1): 43-55.

[13] HE L，SCHAEFER S.Mesh denoising via L 0 minimization[J].ACM Transactions on Graphics (TOG)，2013，32(4): 64.

[14] WANG R，YANG Z，LIU L，et al.Decoupling noise and features via weighted1-analysis compressed sensing[J].ACM Transactions on Graphics (TOG)，2014，33(2): 18.

[15] WANG P S，LIU Y，TONG X.Mesh denoising via cascaded normal regression[J].ACM Transactions on Graphics (TOG)，2016，35(6): 232.

[16] ZHANG W，DENG B，ZHANG J，et al.Guided mesh normal filtering[J].Computer Graphics Forum, 2015，34(7): 23-34.

[17] ROWEIS S T，SAUL L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science，2000，290(5500): 2323-2326.

Mesh denoising based on local feature matching

Chan Hailin1, Cao Can2

(1.School of Mathematical Sciences，University of Science and Technology of China，Hefei 230026，China;2.School of Information Science and Technology，University of Science and Technology of China，Hefei 230026，China)

Limited by the inaccuracy of three-dimensional scanners and the various human factors，the three-dimensional models acquired by scanning contain noise inevitably.How to remove the noise on the acquisition models effectively is a hot classic topic.In this paper, we present a data-driven algorithm.Through analyzing the existing noisy mesh and their corresponding ground-truth mesh，we establish the correspondence between the local geometric features of the noisy mesh and the facet normals of the ground-truth mesh，which is used to guide the mesh denoising.The results of experiments verify that the method can effectively denoise the mesh，and is significantly better in reducing noisy and preserving the features of the models.

mesh denoising; local feature matching; data-driven; guided normal filter

TP391.41

A

10.19358/j.issn.1674-7720.2017.21.004

產(chǎn)海林，曹璨.基于局部特征匹配的網(wǎng)格去噪算法J.微型機(jī)與應(yīng)用，2017,36(21)：11-14，18.

2017-05-11)

產(chǎn)海林(1992-)，男，碩士，主要研究方向：數(shù)字幾何處理、機(jī)器學(xué)習(xí)。

曹璨(1992-)，女，碩士，主要研究方向：數(shù)據(jù)挖掘。