Loop細(xì)分小波對網(wǎng)格模型的多分辨率分析

王艷艷 羅曉鋒 惠麗峰 王萍

摘 要： 高分辨率網(wǎng)格模型因其數(shù)據(jù)量龐大，對其在網(wǎng)絡(luò)中很難進(jìn)行實時處理，因此，根據(jù)Loop細(xì)分模板，將邊點作為小波的細(xì)節(jié)信息構(gòu)造出了Loop細(xì)分小波，用于對網(wǎng)絡(luò)模型進(jìn)行多分辨率分析。該方法未涉及曲面幾何拓?fù)潢P(guān)系，因而不受曲面拓?fù)涮卣鞯挠绊?，具有很強的適應(yīng)性。利用其對三維網(wǎng)格模型進(jìn)行多分辨率分析，得到的低分辨率模型輪廓逼真，面片數(shù)量大幅度減少。由于該方法對細(xì)節(jié)信息取舍尺度還不能用統(tǒng)一的公式確定下來，因此只適合對模型做一些簡單的處理。

關(guān)鍵詞： 網(wǎng)格模型； Loop細(xì)分小波； 多分辨率分析； 小波重構(gòu)； 小波分解

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號：1006-8228（2013）02-14-03

Application of Loop subdivision wavelets to multi-resolution analysis in the mesh model

Wang Yanyan1， Luo Xiaofeng2， Hui Lifeng1， Wang Ping1

（1. School of Coal， Inner Mongolia University of Science &Technology;， Baotou， Neimenggu 014010， China；

2. School of Mining Engineering， Inner Mongolia University of Science &Technology;）

Abstract： The amount of data of the high-resolution model is very large so that its real-time processing in the network is difficult. Thus the Loop subdivision wavelet is constructed by the way of treating edge points as the details of the wavelet based on the Loop subdivision mask in this paper. This method involving the surface geometry is not independent of the features of the surface topology and thus is of strong adaptability. The three-dimensional grid model is analyzed by using this method. The low-resolution model obtained is vivid and its face number largely decreases. Because it is not yet able to determine scale of option using unified formula， it is only suitable to do some simple processing on models.

Key words： mesh model； Loop subdivision wavelet； multi-resolution analysis； wavelet reconstruction； wavelet decomposition

0 引言

隨著三維掃描技術(shù)與互聯(lián)網(wǎng)的高速發(fā)展，大規(guī)模三維網(wǎng)格模型又成為一種新的數(shù)字媒體。要想在計算機中對這些模型進(jìn)行處理，就需要將其用數(shù)學(xué)形式表示出來。這些模型的數(shù)據(jù)量非常龐大，將其在網(wǎng)絡(luò)中進(jìn)行實時編輯、壓縮、傳輸、濾波等操作是很困難的。多分辨率幾何造型技術(shù)是解決上述問題的強有力工具，而小波變換[1]則是實現(xiàn)多分辨率分析的重要手段。近年來小波技術(shù)在曲面造型中的應(yīng)用越來越普遍，對其 “數(shù)學(xué)顯微鏡”和多分辨率特性的應(yīng)用，可以實現(xiàn)模型的快速造型和靈活修改。Lounsbery[2]提出的基于小波多分辨率分析方法不能直接應(yīng)用于不規(guī)則網(wǎng)格。Bonneau[3]提出了一種能夠直接應(yīng)用于不規(guī)則表面網(wǎng)格的多分辨率分析方法，但它只限于平面的或者球形的網(wǎng)格。王健等[4]提出一種基于半邊數(shù)據(jù)結(jié)構(gòu)的自適應(yīng)分割的動態(tài)網(wǎng)格生成算法，較好地處理了分割邊界。隨著對Loop細(xì)分曲面的研究進(jìn)一步加深，Bertram于2000年給出了基于提升格式構(gòu)造雙正交Loop細(xì)分小波的算法[5]，這在很大程度上提升了Loop細(xì)分曲面的形狀可調(diào)節(jié)性。目前對Loop細(xì)分小波的研究大都集中在對網(wǎng)格內(nèi)部頂點的小波分解和小波重構(gòu)方法[6-7]研究上，對非閉合曲面的研究較少，而在工程應(yīng)用中，非閉合曲面大量存在。針對有邊界的非閉合網(wǎng)格，秦[8]等對其做了簡單的處理，但沒有考慮內(nèi)部點對邊界的影響。

本文根據(jù)傳統(tǒng)的Loop細(xì)分模板構(gòu)造出了不涉及曲面幾何拓?fù)浣Y(jié)構(gòu)的Loop細(xì)分小波，因此不受曲面拓?fù)涮卣鞯挠绊?，具有很強的適應(yīng)性。

1 Loop細(xì)分小波

Loop細(xì)分算法是基于頂點的1-4細(xì)分，細(xì)分規(guī)則如下：對曲面上原有頂點利用其鄰接頂點的加權(quán)平均進(jìn)行調(diào)整，得到頂點V'；對任意一條邊，利用其鄰接三角面片頂點的加權(quán)平均得到邊點Ve；把在一個三角面片內(nèi)的把頂點V'與其相鄰的邊點Ve連接，邊點Ve之間也連接起來，這樣，原來一個三角面片就被分為四個三角面片。

從小波的角度去理解Loop細(xì)分模板，頂點V0、V1、V2、V3可分別看作的是尺度函數(shù)Φ0、Φ1、Φ2、Φ3，邊點Ve被看作是小波基Ψ，Ψ和Φ共同支撐出新的尺度函數(shù)空間。

因此可通過Loop細(xì)分模板構(gòu)造出對應(yīng)細(xì)分小波（圖1所示），使用公式表示如下：

⑴

⑵

其中，Vi1為Vi的1-鄰域頂點，ki為點Vi的價。

[1][3][1][3][Φ1][Φ0][Φ2][Φ3]

圖1 由Loop細(xì)分模板得到的Loop細(xì)分小波示意圖

Loop細(xì)分算法的局部細(xì)分矩陣如下：

⑶

1.1 Loop細(xì)分小波的重構(gòu)

根據(jù)公式⑴，在計算奇頂點過程中加入小波系數(shù)Ve（表示細(xì)節(jié)信息），對原有的細(xì)分矩陣改進(jìn)如下：

⑷

根據(jù)Bertram的小波構(gòu)造思想，把公式⑴、⑵轉(zhuǎn)換為具有Lifting運算性質(zhì)的操作[5]：

⑸

⑹

其中

公式⑸為預(yù)測操作，利用小波系數(shù)Ve來計算奇點；公式⑹為更新操作，從新得到的奇頂點來重新計算偶頂點，即使用來更新 V'，是頂點Vi 的1-鄰域奇頂點。更新操作的細(xì)分矩陣如下：

⑺

與原Loop細(xì)分方法相比，Loop細(xì)分小波在計算奇點時增加了細(xì)節(jié)信息Ve。

1.2 Loop細(xì)分小波的分解

把公式⑸、⑹進(jìn)行逆運算，很容易得到Loop細(xì)分小波的分解過程：

⑻

⑼

其中

公式⑻用來提取小波系數(shù)，公式⑼用來計算偶頂點的幾何信息。保留偶點去掉奇點，同時保存舍棄的小波系數(shù)，這樣就完成了一次高分辨率到低分辨率的曲面分解過程。

上述方法僅僅從幾何角度出發(fā)給出一種曲面數(shù)值分析的簡單策略，沒有使用傳統(tǒng)的正交性作為小波的構(gòu)造條件。由于Loop細(xì)分小波的數(shù)值計算沒有涉及到曲面的幾何拓?fù)?，因而不會受到曲面拓?fù)涮卣鞯挠绊懀哂休^好的適應(yīng)性。

2 算法的實現(xiàn)

Loop細(xì)分小波處理的對象主要是三角面片中的頂點信息，而在模型細(xì)分和化簡這兩個互逆的過程中，就不可避免要處理曲面的幾何拓?fù)湫畔?，即頂點間的鄰接關(guān)系與面片的構(gòu)成信息。因此，對于Loop細(xì)分小波可主要用兩個過程來對模型進(jìn)行處理。

⑴ 模型的細(xì)分。由低分辨率得到高分辨率模型，對曲面上所有的三角面片利用傳統(tǒng)的Loop細(xì)分算法進(jìn)行1-4細(xì)分，這樣便可以得到曲面在高分辨率下的拓?fù)潢P(guān)系。

⑵ 模型的簡化。由高分辨率得到低分辨率模型，這個過程相對細(xì)分過程要復(fù)雜一些。遍歷模型上所有的頂點Vi，判斷出哪些點是奇點，哪些點是偶點。根據(jù)條件去除一定數(shù)量的奇點并保存這些細(xì)節(jié)信息，隨后再利用原來的幾何拓?fù)湫畔?，將偶頂點重新連接構(gòu)造出新的拓?fù)潢P(guān)系。

3 實驗

本文把經(jīng)過Loop細(xì)分的cat模型（頂點數(shù)為352，面片數(shù)為671）、nefertiti模型（頂點數(shù)為654，面片數(shù)為1252）在Matlab中利用三維圖像函數(shù)重新建模型，利用Loop細(xì)分小波對該模型進(jìn)行多分辨率分析，實驗效果如圖2所示。從圖2中可以看出，在經(jīng)過一次小波分解后，兩個模型的面片數(shù)都大量減少，cat模型輪廓較為逼真，加入小波系數(shù)，就可重構(gòu)出原始模型。但nefititi模型就失真較多，這是由于在此試驗中，對奇頂點（即小波系數(shù)）進(jìn)行了取舍，取舍尺度還沒有一個能夠統(tǒng)一確定的公式，這個問題還待進(jìn)一步研究。

（a） cat模型的細(xì)分圖和一次小波分解圖

（b） nefertiti模型的細(xì)分圖和一次小波分解圖

圖2 Loop 細(xì)分小波實驗結(jié)果圖

4 結(jié)束語

用本文構(gòu)造的Loop細(xì)分小波對高分辨率模型進(jìn)行處理的過程中，由于奇點（小波系數(shù)Ve）是由奇點和偶點的拓?fù)湫畔⒂嬎愕玫降?，而偶點應(yīng)用的標(biāo)準(zhǔn)是Loop細(xì)分模板的運算結(jié)果，其在小波的合成與分解過程中都是無損的。因此在對模型的多分辨率分析過程中，將小波系數(shù)作為細(xì)節(jié)信息存儲起來，可以用于無誤差的模型合成；但在對模型的分解過程，就要舍棄一些高頻信息Ve得到一個近似的幾何模型，但這個舍棄尺度還不能用一個公式確定下來，所以對模型分解過程中還存在很大偏差，這是該方法的不足之處，在以后的工作中，需著手對細(xì)節(jié)的取舍尺度做進(jìn)一步深入的研究，將其用公式確定下來。

參考文獻(xiàn)：

[1] Finkelstein， Salesin D H. Multiresolution curves[A]. In： Proceedingsof SIGGRAPH '94[C].ACM，1994：261-268

[2] Eck M， DeRose T， Duchamp T， et al. Multiresolution analysis of arbitrary meshes[A]. In：ACM Siggraph Conference Proceedings[C]. New York，1995：173-182

[3] Bonneau G P. Multiresolution analysis on irregular surface meshes[J]. IEEE Trans. Visualization and Computer Graphics，1998.4（4）：365-378

[4] 王健，何明一.自適應(yīng)分割的動態(tài)網(wǎng)格生成算法[J].計算機輔助設(shè)計與圖形學(xué)學(xué)報，2005.17（7）：1434-1439

[5] Bertram M. Biorthogonal loop subdi-vision wavelets[J].Computing Springer，2004.72（1-2）：29-39

[6] Lounsbery J M. Multiresolution analysis for surfaces of arbitrary topological type[D]. Ph.D.Thesis， Department of Mathematics， University of Washingtown，1994.

[7] Wang H W， Qin K H， Tang K. Efficient wavelet construction with Catmull-Clark subdivision [J]. The Visual Computer，2006.22（9-11）：874-884

[8] Sweldens W. The lifting scheme：A custom-design construction ofbi-orthogonal wavelets[J]. Appl Comput Harmon Anal，1996.3（2）：186-200