基于地形的自適應壓縮和實時可視化

鄭新，王鈺，王曉東

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

1 引言

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

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

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

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

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

2.1 整數小波變換

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

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

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

逆變換格式是:

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

2.2 限制四叉樹三角化

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

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

2.3 基于整數小波變換的限制四叉樹

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

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

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

經過這一步后，每個系數都與地形上相應的頂點構成一一對應的關系，而且系數的量就代表著頂點的高度變化，也就是地形特征。

從圖7可以看出，由對角線的5個系數構成的矩形單元格組成了整個的網格結構。其中HL，LH，和HH的系數分別表示對應頂點水平、垂直和對角線方向上的變化。仔細分析圖3和圖7可以發現，δ和位于相同位置的小波系數的量有相似的地形表面復雜度。

圖7 由5個系數組成的矩形單元格

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

3 地形壓縮和可視化

3.1 地形壓縮

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

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

3.2 地形渲染

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

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

4 實驗結果

本文實現采用的地形數據是分辨率為130175×130175的深圳市地形高度圖，實現平臺是VC6.0和OpenGL，實現環境是 Pentium D 3.0GHz CPU，1024MB內存。

表1 地形數據壓縮時間消耗表

表2 壓縮算法對比實驗數據表

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

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

5 結論與展望

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

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