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

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

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

中圖分類(lèi)號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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ì)算機(jī)中對(duì)這些模型進(jìn)行處理，就需要將其用數(shù)學(xué)形式表示出來(lái)。這些模型的數(shù)據(jù)量非常龐大，將其在網(wǎng)絡(luò)中進(jìn)行實(shí)時(shí)編輯、壓縮、傳輸、濾波等操作是很困難的。多分辨率幾何造型技術(shù)是解決上述問(wèn)題的強(qiáng)有力工具，而小波變換[1]則是實(shí)現(xiàn)多分辨率分析的重要手段。近年來(lái)小波技術(shù)在曲面造型中的應(yīng)用越來(lái)越普遍，對(duì)其 “數(shù)學(xué)顯微鏡”和多分辨率特性的應(yīng)用，可以實(shí)現(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)分割的動(dòng)態(tài)網(wǎng)格生成算法，較好地處理了分割邊界。隨著對(duì)Loop細(xì)分曲面的研究進(jìn)一步加深，Bertram于2000年給出了基于提升格式構(gòu)造雙正交Loop細(xì)分小波的算法[5]，這在很大程度上提升了Loop細(xì)分曲面的形狀可調(diào)節(jié)性。目前對(duì)Loop細(xì)分小波的研究大都集中在對(duì)網(wǎng)格內(nèi)部頂點(diǎn)的小波分解和小波重構(gòu)方法[6-7]研究上，對(duì)非閉合曲面的研究較少，而在工程應(yīng)用中，非閉合曲面大量存在。針對(duì)有邊界的非閉合網(wǎng)格，秦[8]等對(duì)其做了簡(jiǎn)單的處理，但沒(méi)有考慮內(nèi)部點(diǎn)對(duì)邊界的影響。

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

1 Loop細(xì)分小波

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

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

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

⑴

⑵

其中，Vi1為Vi的1-鄰域頂點(diǎn)，ki為點(diǎn)Vi的價(jià)。

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

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

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

⑶

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

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

⑷

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

⑸

⑹

其中

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

⑺

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

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

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

⑻

⑼

其中

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

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

2 算法的實(shí)現(xiàn)

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

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

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

3 實(shí)驗(yàn)

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

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

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

圖2 Loop 細(xì)分小波實(shí)驗(yàn)結(jié)果圖

4 結(jié)束語(yǔ)

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

參考文獻(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)分割的動(dòng)態(tài)網(wǎng)格生成算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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