視覺特征保持的網(wǎng)格模型簡化算法

楊大光， 胡維多， 常 波， 魏 青

（1. 北京航空航天大學(xué)宇航學(xué)院，北京 100191；2. 海軍航空兵學(xué)院，遼寧 葫蘆島 125001）

視覺特征保持的網(wǎng)格模型簡化算法

楊大光1,2， 胡維多1， 常 波2， 魏 青2

（1. 北京航空航天大學(xué)宇航學(xué)院，北京 100191；2. 海軍航空兵學(xué)院，遼寧 葫蘆島 125001）

針對二次誤差測度算法存在幾何特征消失等缺陷，提出了基于頂點(diǎn)視覺特征度的新的網(wǎng)格模型簡化算法。該算法采用半邊折疊，通過引入頂點(diǎn)視覺特征度來優(yōu)化了二次誤差測度，從而改變邊折疊的順序，使模型中的突出視覺特征更多的被保留下來。視覺特征度通過頂點(diǎn)平均曲率熵來定義，它反映了頂點(diǎn)中心區(qū)域的視覺變化情況。實(shí)驗(yàn)表明，該算法高效、可靠、能很好保持模型的視覺特征。

網(wǎng)格簡化；半邊折疊；二次誤差測度；視覺特征

在視景仿真中，為了提高系統(tǒng)渲染速度，減少網(wǎng)絡(luò)數(shù)據(jù)傳輸量，通常采用模型簡化技術(shù)來簡化網(wǎng)格模型。目前，基于不同的算法思想，學(xué)者們提出了多種網(wǎng)格簡化方法。根據(jù)簡化過程中刪除網(wǎng)格元素的不同，可將網(wǎng)格簡化方法大致分為點(diǎn)刪除、面折疊和邊折疊3類[1]，其中邊折疊方法是最常用的三角網(wǎng)格簡化策略。Hoppe[2]于1993年首先采用邊折疊方法來簡化網(wǎng)格模型，該算法通過優(yōu)化一個全局的能量函數(shù)來確定邊折疊的次序和新頂點(diǎn)的位置，生成的簡化模型誤差較小，視覺效果較好。但該算法計(jì)算繁瑣，時(shí)間復(fù)雜度較高。1997年，Garland[3]等提出了基于二次誤差測度的邊折疊算法，其在誤差測度中僅以點(diǎn)到其鄰接面的距離平方作為誤差量，計(jì)算過程較為簡單，簡化效果與Hoppe算法相近，但該算法不能很好地保持模型的幾何特征。

本文在計(jì)算網(wǎng)格模型二次誤差測度的同時(shí)，將頂點(diǎn)視覺特征度概念引入到二次誤差測度計(jì)算中，并采用半邊折疊操作來減少簡化過程的存貯量。實(shí)驗(yàn)結(jié)果表明，本文算法在相同的簡化條件下，能夠很好地保留網(wǎng)格模型的視覺特征，可以獲得比QEM算法更好的簡化效果。

1 二次誤差測度的邊折疊簡化算法

1.1 邊折疊操作

邊折疊是將邊作為被刪除對象，每折疊一條邊，就會生成一個新頂點(diǎn)，并把所有與被刪除邊相連的點(diǎn)與該新頂點(diǎn)相連，保持模型始終由三角網(wǎng)格組成，通過控制邊折疊的順序和數(shù)目，就可以得到不同分辨率的簡化模型，如圖1所示。半邊折疊將邊的兩個端點(diǎn)之一作為折疊后的新頂點(diǎn)，簡化了操作復(fù)雜度,并且不增加存儲量，因此,本文采用半邊折疊操作。

圖1 邊折疊操作

1.2 二次誤差測度

網(wǎng)格中任一頂點(diǎn) v = [x, y, z,1]T折疊到新頂點(diǎn)v，其誤差值 Δv 為v到v相關(guān)聯(lián)的三角形平面集合Planes(v)中每個三角形所在面的距離平方和，即

其中， p =(a, b, c, d )T表示Plane(v)中每個三角形所在面的平面方程 ax + by+cz+d=0，且

其中 Q1和 Q2分別是邊折疊前頂點(diǎn) v1和 v2的初始矩陣。

1.3 新頂點(diǎn)位置選擇

在進(jìn)行邊折疊操作時(shí)，需要先計(jì)算折疊后新頂點(diǎn)的位置。而確定新頂點(diǎn)方法的不同將直接導(dǎo)致計(jì)算邊折疊代價(jià)的不同，從而影響模型簡化過程中邊折疊的順序，最終影響簡化模型的進(jìn)度。新頂點(diǎn)位置的選擇原則是使簡化模型盡可能逼近原始模型。一般而言，邊折疊操作(v1,v2)→時(shí)，可以采取以下兩種方式來選取新頂點(diǎn)位置。

1） 簡單方式：新頂點(diǎn)的位置從折疊邊的兩個端點(diǎn)或中點(diǎn)中選取，即= v1，= v2或= (v1+v2)2，通過比較邊折疊代價(jià) (v1,v2)→ v1，(v1,v2)→ v2和(v1,v2)→ (v1+v2)2來確定。這種方式計(jì)算量小，可提高運(yùn)算速度，而且簡化模型的頂點(diǎn)集是原始模型的子集，有助于保留初始模型的輪廓和幾何特征。

2） 優(yōu)化方式：優(yōu)化選擇的方式是指不直接使用折疊邊的兩個端點(diǎn)或中點(diǎn)作為新頂點(diǎn)的位置，而是在折疊邊上選取使Δ (v )達(dá)到局部極小值的點(diǎn)作為新頂點(diǎn)。

二次誤差測度的邊折疊簡化算法的時(shí)間和空間復(fù)雜度都相對較低，但在簡化過程中只考慮了距離的度量，因此簡化后的網(wǎng)格分布均勻，簡化模型將失去原始模型中的拐點(diǎn)、折痕、尖銳邊和角等重要幾何細(xì)節(jié)特征。

2 視覺特征度

2.1 信息熵定義

信息熵[4]最初由C.E.Shannon與N.Wiener總結(jié)前人成果后提出的。在信息論中，熵用來衡量一個隨機(jī)變量出現(xiàn)的期望值。信息熵是指任意一個離散信源的熵（平均自信息量）。

設(shè)離散隨機(jī)變量X的概率分布為：

其中 pi=pr{X=xi}i∈{1,2,…,n}， 0 ＜ pi＜1，

X的信息熵定義為“加權(quán)平均信息量”，即

其中 - log( p(x))表示隨機(jī)變量x的自信息量。自信息量取決于隨機(jī)變量發(fā)生的概率，即概率越小，其自信息量越大。信息熵 H (X)是從整個信源的統(tǒng)計(jì)特性來考慮的，它是從平均意義上來表征信源的總體體征的。對于某特定的信源，其信息熵只有一個，不同的信源因統(tǒng)計(jì)特性不同，其熵也不同。

熵的特性：

1） 熵值均大于等于零。

2） 當(dāng)且僅當(dāng) P1=P2=…Pn時(shí)，等號成立，熵值最大。

2.2 離散曲率計(jì)算

由于二次誤差測度只考慮了距離的度量，因此,簡化后的網(wǎng)格分布均勻，簡化模型將失去原始模型中的重要幾何細(xì)節(jié)特征。研究發(fā)現(xiàn)，人的視覺特征對網(wǎng)格模型的拐點(diǎn)、折痕、尖銳邊等細(xì)節(jié)特征比較敏感，在簡化過程中應(yīng)重點(diǎn)保留這些部位，考慮到網(wǎng)格模型中這些區(qū)域的曲率較大，而在平坦區(qū)域曲率較小的特點(diǎn)。因此，在計(jì)算頂點(diǎn)視覺特征度首先要估算網(wǎng)格中頂點(diǎn)的平均曲率。頂點(diǎn)的平均曲率估算有很多優(yōu)秀的算法，這里我們采用Meyer[6]方法：得到網(wǎng)格頂點(diǎn)vi的平均曲率KH(vi)：

式中：ijα ，ijβ分別為連接頂點(diǎn)vi和vj邊的對角；為陰影部分面積；i， j分別為三角網(wǎng)格頂點(diǎn)的索引；N (i) 為iv的 1-環(huán)領(lǐng)域中頂點(diǎn)的個數(shù)。

圖2 頂點(diǎn)iv的1-環(huán)領(lǐng)域內(nèi)的角度和面積

2.3 視覺特征度定義

設(shè)網(wǎng)格上的任一頂點(diǎn)v，其鄰域內(nèi)頂點(diǎn)集V=｛v0, v1,… ,vn｝，令 v0=v，鄰域內(nèi)的頂點(diǎn)集由頂點(diǎn)及其相關(guān)頂點(diǎn)組成，其平均曲率可以表示為K=｛k0, k1,… ,kn｝。

網(wǎng)格模型中頂點(diǎn)最小平均曲率熵記為 Hmin，Hmin=0；最大平均曲率熵記為 Hmax，

將所有的頂點(diǎn)平均曲率熵歸一化到[0,1]之間，歸一化的平均曲率熵記為 Hnor，則：

用I(v)來表示任一頂點(diǎn)v的視覺特征度，則

頂點(diǎn)的視覺特征度表示網(wǎng)格中的任一頂點(diǎn)平均曲率在其鄰域內(nèi)的分布情況，jp代表是任一頂點(diǎn)所在鄰域內(nèi)的幾何特征信息，表示的是鄰域內(nèi)的平均幾何信息，例如：當(dāng)網(wǎng)格中的某一區(qū)域頂點(diǎn)曲率變化大時(shí)，視覺特征度也較大，人的視覺對這區(qū)域比較敏感，而這區(qū)域正是網(wǎng)格模型中重要幾何特征部分，因此，頂點(diǎn)視覺特征度能夠不斷地反映網(wǎng)格中的重要局部細(xì)節(jié)特征，如拐點(diǎn)、折痕、尖銳邊等。

3 算法描述與實(shí)現(xiàn)

本文對二次誤差測度進(jìn)行改進(jìn)，引入頂點(diǎn)視覺特征度因子，得到一種新的網(wǎng)格簡化算法。該算法依據(jù)頂點(diǎn)視覺特征度的不同，在簡化過程中能夠?qū)旤c(diǎn)視覺特征度高的區(qū)域進(jìn)行保留，從而達(dá)到保持網(wǎng)格模型細(xì)節(jié)特征的目的。

3.1 改進(jìn)二次誤差測度

由上式可以看出在邊折疊過程中，視覺特征度高的頂點(diǎn)將產(chǎn)生較大的邊折疊代價(jià)，而視覺特征度低的頂點(diǎn)則產(chǎn)生較小的邊折疊代價(jià)。這樣，隨著邊對不斷折疊，頂點(diǎn)視覺特征度高的區(qū)域與頂點(diǎn)視覺特征度低的區(qū)域之間的分化逐漸明顯，產(chǎn)生的結(jié)果就是網(wǎng)格模型中的細(xì)節(jié)特征部分都分布在頂點(diǎn)視覺特征度高的區(qū)域，模型的細(xì)節(jié)特征才能得以保留。

3.2 算法流程

本文簡化過程主要分為初始階段和簡化階段[7]。在初始階段，要計(jì)算頂點(diǎn)的二次誤差矩陣、視覺特征度矩陣、每條邊的折疊代價(jià)，并依據(jù)折疊代價(jià)的大小排序?qū)⒆钚〈鷥r(jià)邊置于堆頂。在簡化階段，取出堆頂?shù)倪呥M(jìn)行折疊操作，更新相關(guān)頂點(diǎn)的二次誤差矩陣和視覺特征度矩陣，并對更新后邊折疊代價(jià)重新排序，如此反復(fù)，直到達(dá)到簡化目標(biāo)為止。具體過程如圖3所示。

由于本文的網(wǎng)格簡化算法主要基于半邊折疊操作，因此,新頂點(diǎn)位置確定如下：分別計(jì)算折疊邊 ),(jivv 的兩個端點(diǎn)iv 和jv 的折疊代價(jià)，從而確定半邊折疊的方向（即新頂點(diǎn)的位置）。如果折疊方向?yàn)?vi→ vj，新頂點(diǎn)是 vj；如果，折疊方向?yàn)?，新頂點(diǎn)是本文算法能夠在邊折疊每次迭代中實(shí)現(xiàn)折疊代價(jià)最小。

圖3 算法流程示意圖

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

本文在2.4GHz CPU和4G內(nèi)存的硬件環(huán)境以及Windows XP操作系統(tǒng)下采用Visual C++運(yùn)行算法的仿真程序，并采用OpenGL圖形庫來渲染模型。不失一般性，采用了3個常用的模型對兩種算法的簡化效果進(jìn)行比較，分別是 cow模型、car模型和helicopter模型。

采用二次誤差測度算法得到的簡化網(wǎng)格模型十分均勻，這樣往往使得較為平坦的區(qū)域占用過密的網(wǎng)格，從而造成網(wǎng)格浪費(fèi)。本文算法能夠按網(wǎng)格模型表面的平均曲率熵值變化合理地分配網(wǎng)格，使得平坦區(qū)域網(wǎng)格稀疏，而曲率變化大的區(qū)域網(wǎng)格稠密，同時(shí)保留了視覺重要的幾何特征，如牛眼、牛角、牛鼻、頜骨和腹部等,如圖4中對比所示。

圖4 特征保持效果對比圖

如圖5和圖6所示, 使用不同的算法得到的簡化網(wǎng)格模型。Car原始模型如圖5(a)所示，圖5(b)、圖 5(d)是僅采用二次誤差測度得到的 car模型。圖5(c)、圖5(e)是采用引入視覺特征度的二次誤差測度得到的car模型。當(dāng)car模型網(wǎng)格被QEM算法簡化到只有530個面片的時(shí)候就失去了部分的幾何特征，但采用本文算法得到的car模型在只有530個面片的時(shí)候仍然可保持形狀幾何特征。helicopter原始模型，如圖6(a)所示，圖6(b)和 6(c)分別是使用二次誤差測度和基于視覺特征度本文算法所得到的簡化模型。同樣當(dāng)helicopter模型被簡化為只有698個面片的時(shí)候，本文算法仍能夠保持良好的幾何特征，具有很好的視覺特征保持。

顯然，本文算法的應(yīng)用保證了簡化后的模型在較低分辨率的情況下依舊能夠保持一些比較重要的幾何特征，從而減少了簡化后的模型在視覺上的退化，更加符合網(wǎng)格簡化的實(shí)質(zhì)，即在減少頂點(diǎn)和三角面片的時(shí)候盡量保持原模型的特征。

圖5 car模型簡化對比圖

圖6 helicopter模型簡化對比圖

采用Cignoni[5]等的評估工具M(jìn)etro對簡化模型進(jìn)行誤差分析，由表1所示。由于本算法能夠產(chǎn)生網(wǎng)格質(zhì)量更好、視覺特征保留更好的簡化模型，因此，應(yīng)用本算法對cow、car和helicopter模型進(jìn)行簡化所產(chǎn)生的簡化誤差比QEM算法的簡化誤差要小。

表1 兩種算法簡化誤差對比

通過對比兩種算法的簡化時(shí)間可以看出，簡化時(shí)間與模型的復(fù)雜度以及三角形面片數(shù)成正比。初始時(shí)間主要用來載入和顯示網(wǎng)格模型、初始二次誤差矩陣計(jì)算、視覺特征度計(jì)算、邊折疊代價(jià)計(jì)算以及邊折疊列表建立。簡化時(shí)間主要用來邊折疊迭代簡化。如表2所示，cow模型、car模型和 helicopter模型的簡化時(shí)間，從表中可以看到，QEM算法在模型的初始階段用時(shí)較短，而本文算法在模型的簡化階段用時(shí)較短，其原因是本文算法在初始階段計(jì)算頂點(diǎn)平均曲率及其熵值耗時(shí)較多。

表2 兩種算法簡化時(shí)間對比

為了驗(yàn)證本文算法在實(shí)際項(xiàng)目中的應(yīng)用價(jià)值，我們對視景仿真中的飛機(jī)網(wǎng)格模型進(jìn)行了簡化，其簡化效果, 如圖7所示。從圖中可以看出在簡化過程中模型細(xì)節(jié)幾何視覺特征保持良好。

圖7 飛機(jī)模型簡化效果圖

5 結(jié) 論

本文提出了基于頂點(diǎn)視覺特征度的二次誤差測度簡化算法，算法通過引入頂點(diǎn)視覺特征度因子，能夠準(zhǔn)確地捕捉網(wǎng)格中感興趣的區(qū)域，使模型中各頂點(diǎn)易于區(qū)分，具有明顯幾何特征區(qū)域的頂點(diǎn)誤差測度能夠被提高，從而調(diào)整了邊折疊順序，保留了模型中重要幾何特征。實(shí)驗(yàn)結(jié)果表明，本算法高效、可靠、能很好保持模型的視覺特征，具有一定的實(shí)際應(yīng)用價(jià)值。

[1] 潘志庚, 龐明勇. 幾何網(wǎng)格簡化研究與進(jìn)展[J]. 江蘇大學(xué)學(xué)報(bào)(自然科學(xué)版), 2005, 26(1): 67-71.

[2] Hoppe H. Progressive meshes[C]//Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH. New York: ACM Press, 1996: 99-108.

[3] Garland M, Heckbert P S. Surface simplification using quadric error metrics[C]//Proc. of the Computer Graphics, 1997, 31: 209-216.

[4] Cover T M, THOMAS J A. 信息論基礎(chǔ)[M]. 北京:清華大學(xué)出版社, 2003, 11.

[5] Cignoni P, Rocchini C, Scopigno R. Metro: Measuring error on simplified surfaces [J]. Computer Graphics Forum, 1998, 17(2): 167-174.

[6] Meyer M, Desbrun M, Schr?der P, et al. Discrete differential-geometry operators for triangulated 2-manifolds [C]//Proceedings of the 3rd International Workshop on Visualization and Mathematics. Berlin: Springer, 2003: 35-57.

[7] 陳偉海, 徐鯉鴻, 劉敬猛, 等. 網(wǎng)格簡化中基于特征矩陣的二次誤差測度算法[J]. 北京航空航天大學(xué)學(xué)報(bào), 2009, 35(5): 572-575.

Mesh Simplification based on Visual Feature Preserved

Yang Daguang1,2, Hu Weiduo1, Chang Bo2, Wei Qing2
( 1. School of Astronautics, Beihang University, Beijing 100191, China; 2. Naval Aviation Institute, Huludao Liaoning 125001, China )

In allusion to the some deficiencies from the algorithm based on error metrics (QEM), such as neglect of some geometric features, a novel approach based on visual feature is proposed for mesh simplification. The approach is driven by introducing a visual feature into the new QEM to optimize error metrics, as well as half-edge collapse, therefore the collapse sequences of edge can be adjusted, and some sharp visual features of the model can be preserved. We define the visual feature of one vertex based on its vertex curvature entropy which reflects the visual variation of the region centered at this vertex. Comparing with QEM algorithm, the algorithm is efficient, reliable, and can maintain the visual characteristics of the model better.

mesh simplification; half-edge collapse; quadric error metrics; visual feature

TP 391

A

2095-302X (2013)04-0035-06

2012-09-12；定稿日期：2012-11-21

楊大光（1982-），男，遼寧葫蘆島人，助教，碩士研究生，主要研究方向?yàn)橐暰胺抡?，三維可視化，計(jì)算機(jī)圖形學(xué)。E-mail：yangdaguang0702@163.com