基于網格顯著度的視點質量計算方法

摘 要:從模糊貼近度的角度，結合網格顯著度概念，給出了一種新的視點質量計算方法。首先將場景中的每個三角形看做論域中的一個樣本，從可見度大小的角度定義隸屬函數，為視點構造一個模糊集合;然后結合三角形的幾何面積及面片顯著度給出一個對應理想視點的模糊集;最后求取兩個模糊集合的貼近度作為視點質量的評價準則。實驗結果表明，該算法能夠較好地反映視點質量。

關鍵詞:視點質量; 網格顯著度; 模糊貼近度

中圖分類號:TP391文獻標志碼:A

文章編號:1001-3695(2009)09-3523-03

doi:10.3969/j.issn.1001-3695.2009.09.092

Viewpoint quality computing method based on mesh saliency

ZHAO Jian， XU Jiang-bin， WU Ling-da

(College of Information Systems Management， National University of Defense Technology， Changsha 410073， China)

Abstract:This paper put forward a new method ， which combined the notion of mesh saliency and fuzzy nearness. First， it constructed a fuzzy set for the viewpoint. The elements of the set were faces in the scene， and based membership function on the visibility of faces. Then， defined a ideal fuzzy set， the membership degree was in proportion to the mesh saliency weighted fact area of the face. Finally， took the fuzzy nearness of these two fuzzy set as the measure of viewpoint quality. The experiment results show that this method works well.

Key words:viewpoint quality; mesh saliency; fuzzy nearness

視點質量在計算機圖形學領域有著相當廣泛的應用，如自由漫游[1]、場景理解[2]、光線跟蹤[3]、科學計算可視化[4]、基于圖像的建模與繪制[5]、三維模型的簡化[6，7]等。雖然視點質量的應用如此廣泛，但到目前為止，對于視點質量仍然沒有一個明確的定義。目前，得到普遍認可的一種說法是:從某一個視點觀察場景所獲得的信息越多，則該視點的質量越好[8]。從這一角度出發，國內外學者給出了許多衡量視點質量的標準。這些評價標準的出發點主要集中于場景的幾何信息，如可見面數量和投影面積的大小，而忽略了場景本身所具有的視覺特性。本文提出了一種新的視點質量計算方法，在視點質量的計算過程中融入了網格顯著度因素，使得視點質量不僅能夠反映場景的幾何信息，而且能夠反映場景的視覺信息。

1 相關工作

Kamada等人[9]提出了一種使場景中退化面片的數量達到最小的方法來衡量視點的質量，但其僅僅考慮了視線與面片法向之間的夾角。Plemenos等人[10]擴展了Kamada的算法，他們認為當視線與面片法向夾角的最大值較小，且可見面片的數量較大時該視點的質量較好。

Vzquez等人[11，12]從信息論的角度提出了一種基于信息熵的視點質量評價標準，即將場景看做一個信源，場景中的每個面片看做信源符號，定義信源符號的出現概率為面片投影面積與屏幕分辨率的商。這種評價方法存在一個缺點，即視點熵受網格細化程度影響較大，同一區域，細化程度越高，則視點熵越大。

Sbert等人[8]提出了一種根據兩概率分布之間的KL距離(Kullback-Leibler distance)計算視點質量的方法，即將面片的原始幾何面積看做一個概率分布，將面片的投影面積看做一個概率分布，當兩個概率分布的KL距離越小時，視點的質量越好。這種計算方法沒有考慮背景的影響，適用于封閉場景中的視點質量評價，但對于開放場景，當視點拉遠或拉近時，按照這種方法計算的視點質量沒有改變。

Feixas等人[13]對視點熵的評價標準進行了拓展，從互信息的角度提出了視點互信息(viewpoint mutual information， VMI)的概念，建立了從視點到場景的信道，用來計算視點與場景之間的互信息。視點互信息越小，則視點質量越好。這種評價標準主要是通過視點間的相互比較來確定視點質量，因此當評價一個視點的好壞時，需要求得面片在其他視點觀察時的投影面積，當視點數目較大時，占用系統資源多，計算耗時較長。

Lee等人[14]提出了網格顯著度的概念，主要是從人的視覺感知特性出發，使用高斯加權的平均曲率對網格上的重要區域進行描述，并在此基礎上定義了一種視點質量評價方法，即將投影后的可見頂點的顯著度之和作為衡量視點質量的標準，但這種方法沒有考慮投影面積及可見面數量，因此該方法對場景幾何信息的描述具有一定的局限性。

上述算法大都從兩個主要因素來描述視點質量:a)場景中的可見面片的數量;b)每個可見面片的投影面積。但僅僅從這兩個因素來計算視點質量是不全面的，如從某一視點觀察場景，雖然能夠獲得較大的投影面積或較多的可見面片，但觀察不到場景的一些重要區域。本文算法融入了場景本身的視覺特性及人的感知特性，對視點質量的描述更加客觀，這是本文算法與上述算法的一個主要區別。

2 本文算法

2.1 基本思想

場景中的三角形可以分為可見和不可見兩種。可見與不可見只是一個質上的衡量，兩者之間并沒有一個明顯的界限。因此可以從模糊數學的角度對場景中三角形的可見度進行量的評價。

不失一般性，假設場景的面片都為三角形，定義論域T={t1，t2，…，tn}表示場景中的所有三角形，n為三角形的數量，則有下面的定義:

定義1 某三角形的投影面積占整個場景投影面積的比重越大，則其可見度越大。

對于視點φ，設V為T上的一個模糊集，表示從視點觀察場景得到的可見度大的三角形集合。根據定義，對模糊集V給出下面的隸屬度函數:

V(ti)=vi=ai/at(1)

其中:ai表示第i個三角形的投影面積;at表示所有三角形的投影面積之和。模糊集表示為V={(t1，v1)，(t2，v2)，…，(tn，vn)}。假設論域T上存在一個理想的模糊集I={(t1，θ1)，(t2，θ2)，…，(tn，θn)}，其中三角形ti的隸屬度θi為

I(ti)=θi=Ai/At×λi(2)

其中:Ai表示第i個三角形的實際幾何面積;At表示所有三角形的實際幾何面積之和;λi表示三角形ti的顯著度，則有

λi=1/3∑v∈tiψv(3)

其中ψv表示頂點顯著度，具體計算公式詳見文獻[14]。上述理想模糊集的定義表明:存在一個理想的視點η，從該視點出發，場景中所有三角形都可見，且其可見度大小為θi。

本文使用歐幾里德貼近度來衡量兩個模糊集之間的接近程度。模糊集V與理想模糊集I之間的歐幾里德貼近度為

N(V，I)=1-1/n[∑ni=1(vi-θi)2]1/2(4)

無論是模糊集V還是理想模糊集I，都是根據特定的視點而得到的，而N(V，I)衡量的是模糊集V與理想模糊集I之間的接近程度，因此完全可以用做衡量視點φ與理想視點η之間的接近程度，N(V，I)越大，表示視點φ越接近于理想視點。

由于開放場景中背景對于視點質量具有一定的影響，當背景的投影面積所占的比重越大時，視點的質量越低。考慮背景因素，定義視點質量的計算公式:

F(φ)=[at/(a0+at)]N(V，I)(5)

其中:a0表示背景的投影面積。對于封閉場景而言，a0=0。稱F(φ)為視點模糊貼近度(viewpoint fuzzy nearness，VFN)，其取值為[0，1]，VFN值越大，說明視點質量越好。

2.2 理想視點

從某一個視點觀察場景所獲得的信息越多，則該視點的質量越好。根據國內外學者普遍認可的這一說法，從信息論的角度建立下面的投影觀察信道模型，如圖1所示。

將場景作為信源，場景中的每一個三角形作為符號樣本，屏幕作為信宿，給定視點(投影變換)則確定了信道。由于場景在投影觀察前屬于三維范疇，場景中的三角形所包含的信息量不僅與其幾何面積有關，而且與其顯著程度相關，如凹凸不平的場景中有一平整區域，或者平坦的場景中有一凹陷或突起，那么這些區域中的面片則包含了更多的信息。因此定義信源的輸出符號xi的概率為Ai/At#8226;λi。場景經過投影變換后屬于二維的范疇，接受符號只與每個三角形的投影面積相關，因此定義信宿接受符號yi的概率為ai/at。

根據式(2)定義的理想模糊集I具有兩層含義:a)場景中的所有三角形都可見，即可見三角形的數量達到最大;b)場景信息的接收概率等于發送概率。對于理想視點確定的信道，由于xi和yi存在一一對應的關系，信宿接受到信源發出的全部信號，并且接受概率與發送概率相等，該信道是理想信道。由于信源所包含的信息量是確定的，通過該信道獲得的信息量最大，即通過理想視點觀察場景所獲得視覺效果最好。當然，對于大多數場景這種理想視點是不存在的。

3 計算流程

為了計算和實現方便，一般利用繪制到紋理(render to texture)技術，將場景繪制到一個2n×2n的紋理塊上，而不是繪制到屏幕上。另外，算法在執行過程中需要計算三角形的投影面積與實際幾何面積，對于三角形的實際幾何面積可以采用解析幾何方法進行求取，但對于投影面積如果采用解析的方法，則計算相對復雜。文獻[15]中提出了關于投影面積的幾種計算方法，本文采用其中的SW+HW的方法，即首先將場景中的每個三角形按照顏色進行編碼;然后利用圖形硬件統計每個三角形所占的像素數，從而得到三角形的投影面積。

下面以觀察三維物體為例，給出本文算法的計算步驟:

a)讀入三維模型，對三維模型的面索引及頂點索引進行優化。

b)利用解析方法計算每個三角形的幾何面積。

c)計算場景中每個三角形的顯著度。

d)根據面索引對三角形面片ti進行顏色編碼。

e)根據某一視點，采用繪制到紋理技術將物體繪制到一個2n×2n的紋理塊上。

f)對紋理塊中的像素數據采用SW+HW的方法進行像素統計，并根據步驟d)中的編碼規則得到三角形ti的投影面積。

g)根據式(5)計算視點質量。

4 實驗結果

本文以VC.NET 2003作為開發平臺，采用OpenGL及OpenMesh開發包[16]對算法進行了實驗，硬件環境為P4 2.8 GHz、1 GB內存、顯卡Geforce 8600，256 MB顯存。

實驗過程中采用透視畫法，繪制紋理大小為512×512。為了方便與其他視點質量計算方法進行對比，將所有的視點均勻分布在以場景的幾何中心為圓心，以場景包圍球的三倍半徑為半徑的球面上。對視點質量進行顏色編碼，紅色表示視點質量最大，藍色表示視點質量最小。圖2給出了觀察Beethoven模型的實驗結果。實驗過程中使用了1 226個視點，其中第1、2、3行分別為使用視點熵(viewpoint entropy，VE)、視點KL距離(viewpoint Kullback-Leibler Distance，VKL)和VFN方法的計算結果，(a)和(b)分別給出了最優視點和最差視點對應的觀察視圖;(c)和(d)則給出了球面上視點質量分布的正視圖和俯視圖。從圖2中可以發現，使用三種方法得到的最差視圖是相同的，但對應的最優視圖卻不相同，相比之下，本文算法所得到的最優視圖具有最佳的視覺效果。

圖3給出了觀察Triceratops模型時三種方法的比較與圖2一樣，1、2、3行分別對應VE、VKL和VFN算法，從左到右，每一列分別對應最優視圖、最差視圖、球面上視點質量分布的正視圖和右視圖。從圖中可以看出，VE和VKL給出的最優視圖雖然能夠獲得較大的投影面積，但對模型的重要區域觀察不夠充分，而采用本文算法所求得的最優視圖則具有更好的視覺效果。

圖4給出了模型Beethoven與Triceratops的平均曲率與顯著度分布。其中:(a)和(b)分別對應了兩個模型的平均曲率分布;(c)和(d)為兩個模型的顯著度分布。對于模型的平均曲率的計算采用文獻[17]中的方法，圖中紅色表示平均曲率最大，藍色為最小。對于網格顯著度的計算，與文獻[14]不同的是將網格中的最短邊ε作為基尺度。網格顯著度本質上是衡量頂點與周圍頂點的平均曲率之間的差異，因此網格顯著度比平均曲率更能夠描述網格的重要區域。

圖5給出了從128個頂點觀察car模型時，分別采用三種方法計算視點質量的對比。由于VKL值越小表示視點質量越好，VFN的取值在[0，1]。為了便于比較，本文對VKL取其倒數，并將VFN的值擴大10倍。從圖中可以看出，三條曲線的形狀基本一致，但在某些點處還是存在一定的差異。在這些差異點處，VFN更能夠客觀地描述視點質量。

5 結束語

本文結合了網格的顯著度特性，從模糊貼近度的角度提出了一種新的視點質量評價方法。該方法與其他視點質量評價方法相比，主要優點在于:考慮了場景的視覺特性，能夠更加客觀地反映視點質量;計算結果與場景的細分程度無關，并能夠反映背景因素對視點質量的影響。

該方法是使用模糊貼近度進行視點質量評價的一次探索與嘗試。將來的研究可以從兩個方面考慮:一方面可以考慮采用其他的隸屬度函數和貼近度來衡量視點質量;另一方面在計算視點質量時，可以考慮場景的其他信息，如紋理、顏色等。

參考文獻:

[1]ANDJAR C， VZQUZ P P， FAIREN M. Way-finder: guided tours through complex walthrough models[J]. Computer Graphics Forum， 2004，23(3):499-508.

[2]SOKOLOV D， PLEMENOS D. Viewpoint quality and scene understanding[C]// Porc of the 6th International Symposium on Virtual Reality， Archaeology and Cultural Heritage. Pisa:[s.n]，2005:67-73.

[3]RIGAU J， FEIXAS M， SBERT M. New contrast measures for pixel super sampling[C]// Proc of CGI’02. London:Springer-Verlag， 2002:439-451.

[4]VZQUEZ P P， FEIXAS M， SBERT M， et al. A new tool for obtaining good views for molecules[C]// Proc of Eurographics IEEE TCVG Symposium on Visualization. 2002:183-188.

[5]VZQUEZ P P， FEIXAS M， SBERT M， et al. Automatic view selection using viewpoint entropy and its application to image-based modelling[J]. Computer Graphics Forum， 2004，22(4): 689-700.

[6]CASTELL P， SBERT M， CHOVER M， et al. Viewpoint entropy-driven simplification[C]// Proc of WSCG’07. Plzen:[s.n]，2007:249-256.

[7]PASCUALC B. Viewpoint driven simplification of polygonal models using information theoretic measures[D]. [S.l.]:Universitat Jaume Ies， 2007.

[8]SBERT M， PLEMENOS D， FEIXAS M， et al. Viewpoint quality:measures and applications[C]// Proc of the 15th Computational Aesthetics in Graphics， Visualization and Imaging. 2005:185-192.

[9]KAMADA T， KAWAI S. A simple method for computing general position in displaying three dimensional objects[J]. Computer Vision Graph， Image Process， 1988， 41(1):43-56.

[10]PLEMENOS D， BENAYADA M. Intelligent display in scene mode-ling: new techniques to automatically compute good views[C]// Proc of International Conference on GraphiCon. 1996.

[11]VZQUEZ P P， FEIXAS M， SBERT M， et al. Viewpoint selection using viewpoint entropy[C]// Proc of Vision， Modeling， and Visuali-zation Conference. Burgdort:Aka GmbH，2001:273-280.

[12]VZQUEZ P P. On the selection of good views and its application to computer graphics[D]. Brarcelnoa: Universitat Politecnica de Ca-talunya， 2003.

[13]FEIXAS M， SBERT M， GONZALEZ F. A unified information-theoretic framework for viewpoint selection and mesh saliency[J]. ACM Trans on Applied Perception， 2009， 6(1):1-23.

[14]LEE C H， VARSHNEY A， JACOBS D W. Mesh saliency[J]. ACM Trans on Graph， 2005，24(3): 659-666.

[15]CASTELL P， SBERT M， CHOVER M， et al. Techniques for computing viewpoint entropy of a 3D scene[C]// Proc of ICCS’06. Berlin: Springer， 2006:263-270.

[16]OpenMesh[EB/OL].http://www.openmesh.org.

[17]TAUBIN G. Estimating the tensor of curvature of a surface from a polyhedral approximation[C]// Proc of IEEE International Conference on Computer Vision. Washington DC:IEEE Computer Society，1995:902-907.