鄭新，王鈺，王曉東

(北京師范大學圖像處理和模式識別實驗室，北京 100875)

1 引言

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

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

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

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

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

2.1 整數(shù)小波變換

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

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

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

逆變換格式是:

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

2.2 限制四叉樹三角化

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

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

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

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

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

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

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

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

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

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

3 地形壓縮和可視化

3.1 地形壓縮

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

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

3.2 地形渲染

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

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

4 實驗結(jié)果

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

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

表2 壓縮算法對比實驗數(shù)據(jù)表

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

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

5 結(jié)論與展望

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

［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.