結合快速層式DCT和動態LOD的地形壓縮繪制技術

杜 德，高保祿，田 力

太原理工大學 軟件學院，太原 030024

1 引言

虛擬現實技術具有良好的適應性，在相應的領域中發揮著獨特而有效的作用。特別是室外地形場景的繪制中，由于數據規模不斷增大，導致需要處理和傳輸的數據量急劇增加[1-2]，虛擬現實技術的普及受到了計算機性能的嚴重制約。因此，驅使傳統的層次細節模型（Levels of Detail，LOD）算法[3]與高性能的壓縮算法結合完成地形渲染成為一種主流方向。

針對地形數據的處理方法，主要的研究方法是各種改進四叉樹的結構來進行數據處理。羅想[4]提出了一種線性和常規兩種四叉樹結合的復合四叉樹的改進方法，一定程度上減少了無效數據，提高了有效數據的占比，但是只限于較小規模的地形數據，且沒有對分辨率進行區分。于卓等人[5]提出了一種將binLBT 壓縮解壓算法用GPU 進行加速來提高算法效率，但其底層還是基于離散余弦變換（Discrete Cosine Transform，DCT），DCT的塊效應和不具備多分辨率的特性使得該算法依然難以滿足大規模地形數據的壓縮。魏迎梅[6]等人提出了通過小波算法壓縮地形數據結合動態LOD[7]完成地形的多分辨率連續繪制，壓縮算法與LOD 結合是一個很好地切入點，但小波變換復雜度高，導致繪制過程中幀速率[8]的不穩定性，并且實時性又對處理速度有很高的要求。

基于此，本文深入研究了層式DCT算法[9-10]，提出了一種快速層式DCT 嵌入式零樹編碼算法，并且與動態LOD相結合完成對地形的壓縮繪制。先用快速DCT[11-12]代替傳統的DCT 對地形數據進行變換，將變換后的系數根據不同頻帶按原來的空間位置重新組合，對左上角的低頻信息執行逆離散余弦變換（Inverse Discrete Cosine Transform，IDCT）作為下層輸入，重復上述步驟使其具有多分辨率特性，最后結合基于視點的動態LOD技術完成多分辨率地形的大規模連續繪制。實驗結果證明，由于快速DCT 計算簡單，變換時間減少，幀速率得到有效提升，同時又能保證穩定的壓縮率，極大地減少了對計算機性能的依賴。

2 層式DCT算法

2.1 DCT變換

類似于離散傅里葉變換[13]，DCT 是酉變換，并且信號熵和能量在變換前后是守恒的。DCT 的變換核由于是余弦函數，因此時域（或空域）中的n維信號X是可分離的，其正、逆DCT的數學計算公式分別如下：

2.2 層式DCT原理

執行層式DCT 后，整個數據的能量主要集中在左上角的低頻部分，是重構整個地形最重要的部分。如圖1為三層DCT的分等級帶寬示意圖。

圖1 三層DCT的分等級帶寬示意圖

首先介紹DCT域抽樣和插值的概念：先執行N×NDCT，并提取低頻的M×M子塊，然后對低頻執行M×MIDCT，此為M/NDCT抽樣，記為M→N，逆過程稱為插值。抽樣之后，地形數據分為低通抽樣和高通細節。其中“Cosine塔”為低通抽樣部分，是重構的主要信息；而“DCT塔”為高通細節部分，只為提高圖像清晰度，其量化過程可粗略進行。圖2為三層DCT的編解碼過程。

圖2 三層DCT編解碼過程

層式DCT編碼的主要步驟：

（1）對第一層原始輸入數據執行DCT。

（2）按照原來的空間位置，重組DCT4 個頻帶子塊。如圖3所示。

圖3 DCT塊分割

（3）對低頻執行IDCT，作為下層輸入，倒L為本層輸出數據。

（4）重復步驟（2）、（3），循環執行，滿足要求為止。

（5）最后一層直接作為頂層數據。

層式DCT解碼的主要步驟：

（1）對頂層數據執行DCT。

（2）下層對上層插值，提高圖像分辨率。

（3）完成插值后執行IDCT，作為下層的輸入數據。

（4）對輸入數據執行DCT，繼續插值重復上述步驟，直到得到第一層數據。

（5）最后執行IDCT獲得重構地形圖像，解碼結束。

3 快速層式DCT嵌入式零樹編碼算法

本文提出的基于快速層式DCT嵌入式零樹編碼算法是在原來的層式DCT 算法的基礎上，將傳統的DCT改為無乘法整數DCT 快速算法，先對地形數據進行分層抽樣操作，即按步驟分層執行快速DCT 與IDCT，使其具有多分辨率特性，然后再按照零樹編碼框架進行編碼操作[14-15]。解碼先按照零樹編碼框架進行解碼操作，對得到的系數按照層式DCT 的解碼步驟進行插值，從而得到重構的地形數據。由于現有的層式DCT算法存在大量的DCT計算，所以為了節省時間，滿足地形渲染過程中的實時性要求，因此采用DCT 的一種快速實現形式。

3.1 快速DCT算法及流程圖

DCT快速算法有眾多類型，本文選取對應離散余弦變換類型Ⅱ（DCT-Ⅱ）的一種快速算法。以N=8 為例的快速計算過程如下（流程圖如圖4所示）。

圖4 DCT-Ⅱ快速計算流程圖

由數學定義可知，余弦函數天然具有對稱性，其算法的遞推過程可由下式推導而出。

（1）首先計算：

（2）計算四點的值：

（3）最后計算：

上述以N=8 為例的DCT-Ⅱ快速計算過程中需要分別執行12次乘法和29次加法運算。如果對一副8×8個點的圖像進行處理時，在編碼的過程中需要執行96次浮點數的乘法計算，相對應的在解碼時也需要進行96乘法計算，乘法運算消耗系統CPU資源，從而增加變換所消耗的時間，因此需要在此基礎上做進一步的改進以提高算法的效率。

3.2 無乘法整數DCT的基本原理及方法

由3.1 節可知，DCT 計算的耗時操作主要在于乘法，因此盡可能減少乘法計算，將會極大地降低DCT的時間復雜度。在此基礎上，改用無乘法整數DCT 快速算法[16]，通過查表簡化蝶形運算將查詢結果進行移位累加，并將運算數學公式中的浮點數按一定的倍數放大并取整，最后計算完成后再減小相應倍數。使用快速DCT 算法，一定程度上有效提高了地形數據的壓縮效率。

假設離散余弦變換中蝶形運算公式的一般數學形式為T=x1ω1+x2ω2，其中輸入數據是x1、x2，常數項是ω1、ω2。為了便于整數形式的DCT 變換，對蝶形運算中的常數項進行放大，將浮點數放大一定倍數并取整，因此，在整個DCT 轉換期間，所有操作都將是在整數之間進行，而不是相對復雜的浮點計算，故而可以提升DCT變換的效率。最后，結果減少相同的倍數，并獲得DCT后的最終結果。

將數據x1、x2轉換為二進制：

其中，ai，bi=0或1，i=0,1,…,n。

如圖5 所示，計算aiω1+biω2(i=0,1,…,n)，就可以通過位移累加計算T。由于ai、bi取值為0 或1，因此有4種組合0，ω1，ω2，ω1+ω2，又由于ω1和ω2都是常數，可以預先存儲在表中，計算aiω1+biω2時根據ai、bi的值就能在預先存儲的表中查詢，避免了兩次乘法和一次加法。aiω1+biω2(i=0,1,…,n)一共有4種情況，已確定的4種不同的結果，如式（17）：

圖5 查表、位移和累加處理原理

3.3 無乘法整數DCT快速算法流程圖

根據3.2 節的基本原理，合并圖4 算法流程圖中參數的系數，將得到新的形式為T=x1ω1+x2ω2的蝶形運算公式，如圖6 所示，其中每個蝶形運算公式中的常數項為：

圖6 無乘法整數DCT快速算法流程圖

根據上述算法可知，若以N=8 為例進行一維的無乘法整數DCT快速算法，在消除乘法運算之后，只需要進行80次移位運算和95次加法運算。

根據一維DCT的計算方法，在對地形數據進行8×8的二維DCT處理時，首先依據基本原理，將蝶形公式中每個常數項放大1 024 倍后取整。要進行二維DCT，可以先對地形數據做水平方向的一維DCT 運算，然后在對地形數據做垂直方向的二維DCT運算，分別設置L、R標志位，分別表示當前數據左移或者右移的位數，從而得到地形數據經過二維DCT處理后的最終結果集。

3.4 對抽樣后的變換數據按照零樹框架執行編碼操作

如圖2 所示，在量化編碼階段，可以使用零樹框架編碼算法代替原來壓縮效率較低的行程編碼等方式，提高地形數據的壓縮效率。變換后地形數據的系數在給定的尺度等級上與其相同方向的下一等級細尺度上的系數相關聯。需要先對系數進行重要程度的判別，篩選出不同閾值平面的重要系數集合之后執行零樹編碼，其過程如下：

（1）重要系數集合的選擇

本文算法的閾值平面選擇類似小波變換的零樹框架結構，采用2 的正整數冪為基礎，有效系數按照閾值平面n的降序從最大閾值平面順序編碼輸出，此為有效系數在閾值平面n上的搜索過程。 滿足如式（18）為執行快速層式DCT后的有效系數集合Ω。

可以通過函數來確立有效系數的集合，采用下式進行定量計算：

（2）零樹預測

地形數據通過快速層式DCT 后，構成了頻率依次增高的多分辨率頻帶系數分解圖像。給定閾值T，將系數C(i,j)以及相同方向上較細尺度的系數集合C∏(i,j)（T與C∏(i,j)中每個系數進行比較）與閾值進行比較，判斷其重要程度，可將所有系數可分為三類：

零樹根 |C(i,j)|

孤立零 |C(i,j)|T

正、負有效系數 |C(i,j)|≥T

代表位置信息的有效系數(|C(i,j)|≥T)通過零樹結構進行描述之后，信息量大為減少。

（3）用零樹框架編碼重要圖

重要圖包括三種要素：（1）零根；（2）孤立零；（3）有效系數。為了簡化內嵌編碼，將正有效系數和負有效系數與重要圖合并編碼。采用4種符號：零根、孤立零、正有效系數、負有效系數，使4 種符號與之一一對應。例如：

TR（零根）=00，IZ（孤立零）=01

POS（正有效系數）=10，NEG（負有效系數）=11

（4）逐次逼近量化（SAQ）

SAQ是內嵌編碼的主要實現方法。SAQ是采用一系列可變閾值對其重要性進行判斷，T0,T1,…,TN-1，其中Ti=Ti-1/2，初始閾值的取值條件為：|Xj|<2T0，Xj表示所有變換系數。

在編解碼過程中將分為主輔兩個過程，主過程通過不同的閾值Ti判斷是否為有效系數，若是放入輔表，主表記0，不影響下次系數的判斷；輔過程由于有效系數在[Ti,2Ti]之間，用“0”、“1”分別表示有效系數在前半區間和后半區間。編碼時每次閾值減半，并依次進行主輔過程；解碼時輔表選擇區間中心值作為重構值，將輔表中的有效系數重新填充到主表中相應位置，重新恢復各重要值的空間位置結構。

快速層式DCT嵌入式零樹編碼算法流程圖，如圖7所示。

圖7 算法流程圖

4 基于視點的動態LOD多分辨率地形繪制

在使用快速層式DCT嵌入式零樹編碼對地形數據進行編碼之后，本文提出結合動態LOD 技術實現在渲染地形過程中的自適應多分辨率連續繪制。其中，確定有效的可見區域與合理的分辨率等級能夠降低地形繪制的復雜度，同時能夠確保在地形漫游時提高用戶視覺的真實感，也就是說，需要進行視景體裁剪和選擇由遠及近的分辨率等級提升方法。

4.1 視景體裁剪

在三維空間里，視點除了視景體內的可視區域外，其他區域不可見，因此需要對地形數據進行裁剪。

圖8 視景體視域及裁剪

由圖8 可知，四邊形ABCD 為視景體的可見區域（視域），因此需要計算4個點的坐標值。

計算C、D點的坐標：

已知ED和E的坐標，求得D的坐標：

根據向量CD以及D的坐標，求出C坐標。同理可計算A、B坐標，由此可確定圖8中藍色可視部分的范圍。

4.2 多分辨率等級選擇

大規模地形多分辨率連續渲染的關鍵問題是依據視點的相關位置選擇不同的分辨率等級，得以完成層式DCT 的重構過程。重構過程中提高分辨率層級可以通過對每層的系數進行插值即可實現。近視點可以選擇高分辨率層級，遠視點可以選擇低分辨率層級，因此就可以將視域內的地形劃分為N個可見范圍，選定遠視點的最大間隔dmax和近視點的最小間隔dmin，?。?/p>

分辨率等級i與視點之間的距離的映射函數為：

根據式（21）可知視域被分割成N個擁有固定分辨率的段，要使視點運動時能夠平滑過渡，同時考慮到繪制效率，可繼續利用離散化方法將Δd繼續細化為n個等級，可以通過閾值篩選方法動態的對距離視點越近的系數進行插值操作，以視距作為度量尺度實現地形的漸進重構。

設視點距離為d，且dmin≤d≤dmax，在第i分辨率等級上，令：

根據式（22）可以選擇最大閾值εmax和最小閾值εmin，依據系數分布特點定義篩選閾值的函數：

進行地形層級模型的重構時，考慮到頻繁的重構可能會帶來系統資源的過度消耗，因此選擇一個合適的等級系數n逐步細化 Δd的范圍，取 Δd′=Δd/n，當：

取閾值：

進行系數篩選并通過逆變換重構地形。

在視域中以視點位置的變化為基準，在運動過程中選擇不同分辨率的層級模型以及同一分辨率下不同精細程度進行繪制重構，因此可以實現地形隨視點的自適應連續繪制。

5 實驗結果分析及處理

本文實驗采用的數據為包含1 025×1 025、4097×4 097 的高程數據和1 024×1 024、4 096×4 096 的紋理數據的The Puget Sound Area 地形數據，該數據由Large Geometric Models Archive at Georgia Tech 網站提供。實驗程序是在Windows環境下，使用VS2013和OpenGL完成的。采用的硬件環境為CPUi5-3210M @ 2.50 GHz），顯卡（AMD Radeon HD 7500M）。

5.1 壓縮性能比較

在保證采樣點數目和采樣間距相同的情況下，比特率的大小可作為衡量壓縮效率的一個因素。傳統LOD算法、基于DCT變換的算法、基于小波變換的算法以及快速層式DCT算法的比特率（BPS），如表1所示。

表1 各算法比特率均值

傳統LOD算法比特率的值遠高于其他3種方法，相同時間間隔內傳輸的數據量也是最大的；基于DCT 的算法比特率的值相對較低，有一定的壓縮率，但其本身所具有的局限性促使其不適合作為大規模地形的連續實時繪制；基于小波變換算法[12]有最好的壓縮性能，但小波變換實現困難，導致計算速度較低，從而不能滿足實時性的條件；而基于快速層式DCT 算法的壓縮性能相對較好，由于采用快速DCT 變換，提高了計算速度，最符合實時性的條件。

各算法的峰值信噪比如圖9所示，不管在何種數值的碼率之下，基于DCT 算法的峰值信噪比[16]都相對較低，而快速層式DCT 和小波變換算法在相同的碼率下具有相似的峰值信噪比值，因此當對地形執行連續實時渲染時，通過使用快速層式DCT 算法也可以獲得相對較好的圖像質量。

圖9 各算法的峰值信噪比

5.2 幀速率比較

將本文算法的實驗數據與傳統LOD 算法、基于DCT的算法和基于小波變換的算法進行了比較，如表2所示。

表2 平均幀速比較

在相同的條件下，保持其運動軌跡不變，傳統的LOD 算法不需要對地形數據進行額外的壓縮解壓操作，因此平均幀速率較快，然而隨著地形規模和復雜度的不斷增加，越來越多的數據會給計算機帶來很大的負擔，影響計算機的性能，導致幀速率變低以及較大的幀率方差；基于DCT的算法雖然平均幀速較高，但其存在不具有多分辨率特性和塊效應的問題，并且壓縮比也相對較低；由于計算過程實現復雜，基于小波變換的算法導致計算機的性能偏低，因而幀速率也相對較低。對比之下，快速層式DCT 算法能夠找到高壓縮性能和高幀速之間的平衡點，使兩者都具有較為不錯的性能優勢。

上述實驗結果說明，快速層式DCT 嵌入式零樹編碼算法在幀速率和壓縮性能方面并不是最佳的，但卻平衡了兩者之間的關系，既可以保證高幀率，又能保持高壓縮性能。此外相比于傳統DCT 本身存在的缺陷，以及小波變換計算復雜，實現困難等缺點，快速層式DCT算法可以很好地對壓縮地形數據，以減少數據傳輸量并加速地形渲染的渲染速度，同時保證一定的精度，滿足人們對實時性的需求。

6 結束語

本文采用快速層式DCT嵌入式零樹編碼算法結合動態LOD技術完成地形的多分辨率連續繪制。相較于小波變換來說，本文算法由于采用一種快速DCT，計算速率較高，實現較為簡單，在保證了較好的壓縮性能的基礎上，同時也保證了較高的幀速率，減少了在地形渲染過程中數據處理和繪制效率對計算機性能的依賴，本文算法確保了大規模地形實時渲染的及時性和平滑性，使渲染更加連續和平穩。

實驗結果進一步表明，本文采用的快速層式DCT嵌入式零樹編碼算法能夠有效提高幀率，同時相比其他算法也具有較高的壓縮性能。與現有的結合基于視點的動態LOD 壓縮方法相比，快速層式DCT 算法各方面更加均衡。但是，文本算法仍有不足之處，比如數據量過大的話，頻繁的正逆DCT 可能會對CPU 造成很大的負荷，從而導致精度缺失問題。因此，下一步將重點放在GPU研究上，以提升算法的效率。