Loop細分小波對網格模型的多分辨率分析

摘 要： 高分辨率網格模型因其數據量龐大，對其在網絡中很難進行實時處理，因此，根據Loop細分模板，將邊點作為小波的細節信息構造出了Loop細分小波，用于對網絡模型進行多分辨率分析。該方法未涉及曲面幾何拓撲關系，因而不受曲面拓撲特征的影響，具有很強的適應性。利用其對三維網格模型進行多分辨率分析，得到的低分辨率模型輪廓逼真，面片數量大幅度減少。由于該方法對細節信息取舍尺度還不能用統一的公式確定下來，因此只適合對模型做一些簡單的處理。

關鍵詞： 網格模型； Loop細分小波； 多分辨率分析； 小波重構； 小波分解

中圖分類號：TP391 文獻標志碼：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 引言

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

本文根據傳統的Loop細分模板構造出了不涉及曲面幾何拓撲結構的Loop細分小波，因此不受曲面拓撲特征的影響，具有很強的適應性。

1 Loop細分小波

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

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

因此可通過Loop細分模板構造出對應細分小波（圖1所示），使用公式表示如下：

⑴

⑵

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

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

圖1 由Loop細分模板得到的Loop細分小波示意圖

Loop細分算法的局部細分矩陣如下：

⑶

1.1 Loop細分小波的重構

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

⑷

根據Bertram的小波構造思想，把公式⑴、⑵轉換為具有Lifting運算性質的操作[5]：

⑸

⑹

其中

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

⑺

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

1.2 Loop細分小波的分解

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

⑻

⑼

其中

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

上述方法僅僅從幾何角度出發給出一種曲面數值分析的簡單策略，沒有使用傳統的正交性作為小波的構造條件。由于Loop細分小波的數值計算沒有涉及到曲面的幾何拓撲，因而不會受到曲面拓撲特征的影響，具有較好的適應性。

2 算法的實現

Loop細分小波處理的對象主要是三角面片中的頂點信息，而在模型細分和化簡這兩個互逆的過程中，就不可避免要處理曲面的幾何拓撲信息，即頂點間的鄰接關系與面片的構成信息。因此，對于Loop細分小波可主要用兩個過程來對模型進行處理。

⑴ 模型的細分。由低分辨率得到高分辨率模型，對曲面上所有的三角面片利用傳統的Loop細分算法進行1-4細分，這樣便可以得到曲面在高分辨率下的拓撲關系。

⑵ 模型的簡化。由高分辨率得到低分辨率模型，這個過程相對細分過程要復雜一些。遍歷模型上所有的頂點Vi，判斷出哪些點是奇點，哪些點是偶點。根據條件去除一定數量的奇點并保存這些細節信息，隨后再利用原來的幾何拓撲信息，將偶頂點重新連接構造出新的拓撲關系。

3 實驗

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

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

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

圖2 Loop 細分小波實驗結果圖

4 結束語

用本文構造的Loop細分小波對高分辨率模型進行處理的過程中，由于奇點（小波系數Ve）是由奇點和偶點的拓撲信息計算得到的，而偶點應用的標準是Loop細分模板的運算結果，其在小波的合成與分解過程中都是無損的。因此在對模型的多分辨率分析過程中，將小波系數作為細節信息存儲起來，可以用于無誤差的模型合成；但在對模型的分解過程，就要舍棄一些高頻信息Ve得到一個近似的幾何模型，但這個舍棄尺度還不能用一個公式確定下來，所以對模型分解過程中還存在很大偏差，這是該方法的不足之處，在以后的工作中，需著手對細節的取舍尺度做進一步深入的研究，將其用公式確定下來。

參考文獻：

[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] 王健，何明一.自適應分割的動態網格生成算法[J].計算機輔助設計與圖形學學報，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