鄭新，王鈺，王曉東

(北京師范大學(xué)圖像處理和模式識(shí)別實(shí)驗(yàn)室，北京 100875)

1 引言

地形渲染是虛擬現(xiàn)實(shí)的一個(gè)重要組成部分。隨著虛擬現(xiàn)實(shí)技術(shù)的進(jìn)一步使用和數(shù)據(jù)獲取設(shè)備分辨率的不斷提高，在虛擬環(huán)境中被渲染的數(shù)據(jù)越來(lái)越多。這些數(shù)據(jù)超出了個(gè)人計(jì)算機(jī)內(nèi)存的裝載能力，不得不把大批量的數(shù)據(jù)進(jìn)行分批裝載。頻繁的讀取數(shù)據(jù)使得渲染的效率受到很大影響。

為了降低數(shù)據(jù)讀取的頻率，許多人提出了他們的數(shù)據(jù)壓縮方法，比如降低存取缺失率的高速緩存高效算法［1］，基于頂點(diǎn)聚類(lèi)的網(wǎng)格簡(jiǎn)化方法［2，3］，基于拓?fù)湫畔⒌木W(wǎng)格簡(jiǎn)化算法［4］，C － BDAM［5］和 geometry clipmap［6］等等。

二十世紀(jì)八十年代，Mallat首次將小波變換引入圖像處理。很好的時(shí)頻局部化特征和多分辨率的分析方法使得小波變換被廣泛地應(yīng)用于圖像壓縮［1－6］。然而作為傳統(tǒng)小波變換的離散小波變換(DCT)往往會(huì)導(dǎo)致浮點(diǎn)系數(shù)，這增加了計(jì)算的復(fù)雜度并且不適合進(jìn)行高效的無(wú)損壓縮。為了解決這個(gè)問(wèn)題，I.Daubechies和W.Sweldens提出了一種提升格式(LS)［4］。基于這種提升格式，一種新型的變換被提了出來(lái)，稱作整數(shù)小波變換(IWT)。IWT降低了計(jì)算復(fù)雜度，能高效地執(zhí)行DCT，還能夠支持圖像的無(wú)損壓縮。所以在我們?cè)缙诘墓ぷ髦校?］就是使用這種方法對(duì)地形進(jìn)行無(wú)損壓縮的。但是在此工作中沒(méi)有考慮地形平坦、起伏等變化，尤其是復(fù)雜區(qū)域的地形，而是使用了相同的分辨率對(duì)地形進(jìn)行規(guī)則化統(tǒng)一渲染。為了克服了這個(gè)缺點(diǎn)，本文使用限制四叉樹(shù)三角化方法(RQT)［8］，提出了一種高效的海量地形自適應(yīng)壓縮和渲染算法，該算法除了具有較高的壓縮比和運(yùn)行效率，對(duì)于海量地形漫游也能達(dá)到高效、實(shí)時(shí)、連續(xù)的視覺(jué)效果。

本文的組織結(jié)構(gòu)如下:第二部分將介紹基于整數(shù)小波變換的限制四叉樹(shù)三角化。第三部分討論地形壓縮，基于視點(diǎn)的多分辨率解壓縮和實(shí)時(shí)渲染中的場(chǎng)景更新算法。最后兩部分將給出一些實(shí)驗(yàn)結(jié)果，并對(duì)本文的工作作出一個(gè)簡(jiǎn)單的總結(jié)。

2 基于整數(shù)小波變換的限制四叉樹(shù)三角化

2.1 整數(shù)小波變換

小波變換是一種用來(lái)描述多分辨率分析中的1D/2D信號(hào)的數(shù)學(xué)工具。通過(guò)一系列的低通和高通濾波器，小波變換能夠把一幅圖像分解為一個(gè)低頻子帶和三個(gè)高頻子帶。由于原始圖像的大部分信息集中在低頻子帶中，則低頻子帶能夠以同樣的方式被分解，并且原始圖像的合成可以被認(rèn)為是分解過(guò)程的反過(guò)程，如圖1所示。

圖1 灰度圖像小波分解示意圖

與傳統(tǒng)的小波變換相比，整數(shù)小波變換除了能夠進(jìn)行多分辨率的分解和合成外，還有一些其他的優(yōu)點(diǎn)，比如，整數(shù)小波變換使用提升格式。提升格式是一種設(shè)計(jì)小波和執(zhí)行離散小波變換的技術(shù)，它的每一步變換都是可逆的。這意味著能夠毫無(wú)誤差地將數(shù)據(jù)進(jìn)行合成。本文壓縮方法中使用的5/3無(wú)損小波能夠解釋這個(gè)屬性。5/3小波提升格的正變換格式如下:

逆變換格式是:

從上面的分析可知，整數(shù)小波變換能夠僅僅占用常數(shù)值的內(nèi)存開(kāi)銷(xiāo)直接在內(nèi)存中處理數(shù)據(jù)，而且它還具有很好的合成性，也能進(jìn)行多分辨率分析。因此它非常適合用在地形壓縮和渲染中。

2.2 限制四叉樹(shù)三角化

圖2所示是一個(gè)平面四叉樹(shù)遞歸三角化的例子。這里定義一個(gè)變量δ，它表示該頂點(diǎn)的高度值和垂直方向鄰接4個(gè)頂點(diǎn)平均高度值的差值。如果δ比給定的閾值大，那么相對(duì)應(yīng)的頂點(diǎn)就分裂。但是如右圖所示在對(duì)應(yīng)的三維平面上就會(huì)出現(xiàn)裂縫。為了避免相鄰兩個(gè)不同的分辨率節(jié)點(diǎn)在鄰接處的裂縫現(xiàn)象，采用限制四叉樹(shù)方法進(jìn)行動(dòng)態(tài)的網(wǎng)格構(gòu)造。每個(gè)頂點(diǎn)依賴相同層或是下一層的兩個(gè)其它頂點(diǎn)，這意味著如果選定某一細(xì)節(jié)層次中的某一頂點(diǎn)，那么與其有約束關(guān)系的頂點(diǎn)也應(yīng)該被選定。圖3表示頂點(diǎn)之間的相互約束關(guān)系。

通過(guò)連續(xù)地限制點(diǎn)的選擇區(qū)域，頂點(diǎn)的依附約束關(guān)系能消除裂縫，從而得到一個(gè)匹配的三角化結(jié)果。圖4表示利用限制四叉樹(shù)消除圖3中裂縫的方法，其中右邊的圖形是頂點(diǎn)之間相互約束的關(guān)系圖。由于三角化過(guò)程是隱式給出的，所以它能被高效地合成。

2.3 基于整數(shù)小波變換的限制四叉樹(shù)

地形數(shù)據(jù)往往存儲(chǔ)為被看做灰度圖像的DEM數(shù)據(jù)。如圖1所示，變換的每一層被分解成一個(gè)低頻部分和三個(gè)高頻部分。仔細(xì)分析可以發(fā)現(xiàn)，小波系數(shù)其實(shí)代表著地形變化特征。地形變化比較復(fù)雜的區(qū)域，小波系數(shù)就比較大，相反地形比較平坦的區(qū)域，小波系數(shù)基本相同而且比較小。

如前所述，小波系數(shù)含有時(shí)域和頻域中的信息。它的頻域位置對(duì)應(yīng)著分辨率的層次，而它的時(shí)域位置是從變換域中對(duì)應(yīng)的子帶的位置推導(dǎo)出的。圖5所示是對(duì)圖2進(jìn)行1D小波提升算法分解8個(gè)頂點(diǎn)后的結(jié)果(WD)和小波系數(shù)的實(shí)際位置(EP)。

由上述公式(1)，(2)，(3)和(4)可知，沿著行和列的方向相繼執(zhí)行1D小波變換后就能得到2D小波系數(shù)。對(duì)圖1進(jìn)行2D整數(shù)小波變換的結(jié)果和小波系數(shù)的實(shí)際位置如圖6所示。這里○，□，和△各自表示一次變換中的子圖HL1，LH1，和HH1。而

經(jīng)過(guò)這一步后，每個(gè)系數(shù)都與地形上相應(yīng)的頂點(diǎn)構(gòu)成一一對(duì)應(yīng)的關(guān)系，而且系數(shù)的量就代表著頂點(diǎn)的高度變化，也就是地形特征。

從圖7可以看出，由對(duì)角線的5個(gè)系數(shù)構(gòu)成的矩形單元格組成了整個(gè)的網(wǎng)格結(jié)構(gòu)。其中HL，LH，和HH的系數(shù)分別表示對(duì)應(yīng)頂點(diǎn)水平、垂直和對(duì)角線方向上的變化。仔細(xì)分析圖3和圖7可以發(fā)現(xiàn)，δ和位于相同位置的小波系數(shù)的量有相似的地形表面復(fù)雜度。

圖7 由5個(gè)系數(shù)組成的矩形單元格

對(duì)于網(wǎng)格的構(gòu)造，本文采用基于小波系數(shù)的限制四叉樹(shù)算法。首先根據(jù)頂點(diǎn)對(duì)應(yīng)的小波系數(shù)與給定閾值的比較來(lái)判斷這個(gè)頂點(diǎn)是進(jìn)行分裂還是合并，然后采用限制四叉樹(shù)結(jié)構(gòu)的分裂和合并對(duì)地形模型進(jìn)行更新。

3 地形壓縮和可視化

3.1 地形壓縮

考慮到地形數(shù)據(jù)非常龐大，我們使用分區(qū)壓縮方法，因?yàn)檫@種方法能夠隨機(jī)訪問(wèn)壓縮的比特流，并且能夠調(diào)整內(nèi)存的使用和變換數(shù)據(jù)的數(shù)量。為了解決邊界問(wèn)題，壓縮算法在劃分之前先對(duì)整個(gè)地形數(shù)據(jù)進(jìn)行n次整數(shù)小波變換，然后再把整個(gè)的小波系數(shù)分離到這些塊中(圖8)。這里存儲(chǔ)最后2次整數(shù)小波分解后的數(shù)據(jù)的目的是構(gòu)造全景圖，也就是當(dāng)視點(diǎn)所在位置高度非常高的情況。通過(guò)第二部分中提到的逆變換公式(3)和(4)，可以直接渲染含有大部分信息的地形數(shù)據(jù)，然后將第(n－2)個(gè)變換小波系數(shù)分離到小塊中。

在上面所述的基于整數(shù)小波變換的限制四叉樹(shù)算法中，小波系數(shù)是唯一需要存儲(chǔ)的數(shù)據(jù)。在圖像處理領(lǐng)域，已經(jīng)有很多經(jīng)典的基于小波變換的壓縮算法。本文所采用的壓縮算法是SPIHT(分層樹(shù)集合分割排序)［9］算法。它利用位平面分層劃分的方法，間接實(shí)現(xiàn)了空間小波樹(shù)的比特平面排序，有效地減少了位平面的編碼符號(hào)集的規(guī)模，提高了壓縮比。

3.2 地形渲染

本階段將描述如何使用本文提出的實(shí)時(shí)地形可視化算法來(lái)顯示海量地形數(shù)據(jù)。圖9顯示了算法的整個(gè)流程。

如果需要繪制全景圖，只需把存儲(chǔ)的數(shù)據(jù)做整數(shù)小波逆變換，得到高度數(shù)據(jù)后直接繪制即可。隨著視點(diǎn)靠近地形表面，地形網(wǎng)格需要細(xì)化到精細(xì)的分辨率，所以選擇視域內(nèi)的壓縮數(shù)據(jù)并讀入內(nèi)存，進(jìn)行解壓縮和整數(shù)小波逆變換得到高度值和限制四叉樹(shù)結(jié)構(gòu)，完成繪制。當(dāng)視點(diǎn)移動(dòng)時(shí)，先前的地形網(wǎng)格就通過(guò)限制四叉樹(shù)進(jìn)行頂點(diǎn)分裂或者合并，從而實(shí)現(xiàn)地形模型的更新。

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

本文實(shí)現(xiàn)采用的地形數(shù)據(jù)是分辨率為130175×130175的深圳市地形高度圖，實(shí)現(xiàn)平臺(tái)是VC6.0和OpenGL，實(shí)現(xiàn)環(huán)境是 Pentium D 3.0GHz CPU，1024MB內(nèi)存。

表1 地形數(shù)據(jù)壓縮時(shí)間消耗表

表2 壓縮算法對(duì)比實(shí)驗(yàn)數(shù)據(jù)表

首先對(duì)16G的數(shù)據(jù)進(jìn)行10次整數(shù)小波變換分解，然后存儲(chǔ)第10次LL10(27×27)和第9次LL9(28×28)分解的結(jié)果。存儲(chǔ)數(shù)據(jù)的大小為80KB。然后把小波系數(shù)劃分成大小為1025×1025的塊，總共有127×127塊。對(duì)于每一塊都采用SPIHT完成壓縮，表1顯示了每一步所消耗的時(shí)間。

壓縮后的數(shù)據(jù)大小是286MB，與原始數(shù)據(jù)比為60:1。該算法與 CBDAM［5］和 Geometry clipmap［6］的比較如表2所示。雖然［6］在壓縮比上優(yōu)于本文的算法，但是它采用的是規(guī)則網(wǎng)格。在繪制效果上肯定要遜色一些。

5 結(jié)論與展望

本文結(jié)合整數(shù)小波變換和限制四叉樹(shù)的特點(diǎn)，提出了一種更為科學(xué)的基于地形特點(diǎn)的自適應(yīng)壓縮算法，并且能對(duì)地形進(jìn)行實(shí)時(shí)地渲染。整個(gè)繪制過(guò)程不僅可以達(dá)到實(shí)時(shí)連續(xù)的視覺(jué)效果，而且保持著較低的平均內(nèi)存占用率，但是在地形繪制過(guò)程中沒(méi)有考慮地形的自身遮擋問(wèn)題。在地面漫游時(shí)，地形的遮擋將對(duì)地貌的視覺(jué)效果產(chǎn)生明顯的影響，特別是在地形表面起伏比較大的區(qū)域。因此，下一步的目標(biāo)是使用小波技術(shù)進(jìn)一步改進(jìn)海量地形壓縮和對(duì)地形的遮擋進(jìn)行剔除以達(dá)到更好的渲染效果。

［1］ Yoon S E，Lindstrom P，Pascucci V，Manocha D.Cache － oblivious mesh layouts［J］.ACM SIGGRAPH，2005，886 －893.

［2］ Lindstrom P.Out－of－core simplification of large polygonal models［C］.In SIGGRAPH’00 Conference Proceedings，2000，259 －262.

［3］ Lindstrom P.Out－of－core construction and visualization of multiresolution surfaces［C］.ACM Symp on Interactive 3D Graphics，2003，93－102.

［4］ Isenburg M，Lindstrom P.Streaming meshes［R］.In Visualization ’05 Proceedings，2005，231－238.

［5］ Gobbetti E，Marton F，Ganovelli F.CBDAM—Compressed batched dynamic adaptive meshes for terrain rendering［R］.Computer Graphics Forum，2006，333 －342.

［6］ Losasso F，Hoppe H.Geometry clipmaps:terrain rendering using nested regular grids［J］.ACM Trans.Graph 23，2004，769 －776.

［7］ Xiaodong Wang，Xin Zheng，Qian Yin.Large Scale Terrain Compression and Real－Time Rendering Based on Wavelet Transform［R］.2008 International Conference on Computational Intelligence and Security，December 2008，489－493.

［8］ PajarolaR.Large scale terrain visualization using the restricted quadtree triangulation［C］.In:Proceedings of Visualization’98，October 1998，19 －26.

［9］ Said A，Pearlman W A.A new fast and efficient image codec based upon set partitioning in hierarchical trees［J］.IEEE Transactions on circuits and systems for video technology，June 1996，243－250.