結(jié)合快速層式DCT和動態(tài)LOD的地形壓縮繪制技術(shù)

杜 德，高保祿，田 力

太原理工大學(xué) 軟件學(xué)院，太原 030024

1 引言

虛擬現(xiàn)實技術(shù)具有良好的適應(yīng)性，在相應(yīng)的領(lǐng)域中發(fā)揮著獨(dú)特而有效的作用。特別是室外地形場景的繪制中，由于數(shù)據(jù)規(guī)模不斷增大，導(dǎo)致需要處理和傳輸?shù)臄?shù)據(jù)量急劇增加[1-2]，虛擬現(xiàn)實技術(shù)的普及受到了計算機(jī)性能的嚴(yán)重制約。因此，驅(qū)使傳統(tǒng)的層次細(xì)節(jié)模型（Levels of Detail，LOD）算法[3]與高性能的壓縮算法結(jié)合完成地形渲染成為一種主流方向。

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

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

2 層式DCT算法

2.1 DCT變換

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

2.2 層式DCT原理

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

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

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

圖2 三層DCT編解碼過程

層式DCT編碼的主要步驟：

（1）對第一層原始輸入數(shù)據(jù)執(zhí)行DCT。

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

圖3 DCT塊分割

（3）對低頻執(zhí)行IDCT，作為下層輸入，倒L為本層輸出數(shù)據(jù)。

（4）重復(fù)步驟（2）、（3），循環(huán)執(zhí)行，滿足要求為止。

（5）最后一層直接作為頂層數(shù)據(jù)。

層式DCT解碼的主要步驟：

（1）對頂層數(shù)據(jù)執(zhí)行DCT。

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

（3）完成插值后執(zhí)行IDCT，作為下層的輸入數(shù)據(jù)。

（4）對輸入數(shù)據(jù)執(zhí)行DCT，繼續(xù)插值重復(fù)上述步驟，直到得到第一層數(shù)據(jù)。

（5）最后執(zhí)行IDCT獲得重構(gòu)地形圖像，解碼結(jié)束。

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

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

3.1 快速DCT算法及流程圖

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

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

由數(shù)學(xué)定義可知，余弦函數(shù)天然具有對稱性，其算法的遞推過程可由下式推導(dǎo)而出。

（1）首先計算：

（2）計算四點的值：

（3）最后計算：

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

3.2 無乘法整數(shù)DCT的基本原理及方法

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

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

將數(shù)據(jù)x1、x2轉(zhuǎn)換為二進(jìn)制：

其中，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都是常數(shù)，可以預(yù)先存儲在表中，計算aiω1+biω2時根據(jù)ai、bi的值就能在預(yù)先存儲的表中查詢，避免了兩次乘法和一次加法。aiω1+biω2(i=0,1,…,n)一共有4種情況，已確定的4種不同的結(jié)果，如式（17）：

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

3.3 無乘法整數(shù)DCT快速算法流程圖

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

圖6 無乘法整數(shù)DCT快速算法流程圖

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

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

3.4 對抽樣后的變換數(shù)據(jù)按照零樹框架執(zhí)行編碼操作

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

（1）重要系數(shù)集合的選擇

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

可以通過函數(shù)來確立有效系數(shù)的集合，采用下式進(jìn)行定量計算：

（2）零樹預(yù)測

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

零樹根 |C(i,j)|

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

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

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

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

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

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

POS（正有效系數(shù)）=10，NEG（負(fù)有效系數(shù)）=11

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

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

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

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

圖7 算法流程圖

4 基于視點的動態(tài)LOD多分辨率地形繪制

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

4.1 視景體裁剪

在三維空間里，視點除了視景體內(nèi)的可視區(qū)域外，其他區(qū)域不可見，因此需要對地形數(shù)據(jù)進(jìn)行裁剪。

圖8 視景體視域及裁剪

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

計算C、D點的坐標(biāo)：

已知ED和E的坐標(biāo)，求得D的坐標(biāo)：

根據(jù)向量CD以及D的坐標(biāo)，求出C坐標(biāo)。同理可計算A、B坐標(biāo)，由此可確定圖8中藍(lán)色可視部分的范圍。

4.2 多分辨率等級選擇

大規(guī)模地形多分辨率連續(xù)渲染的關(guān)鍵問題是依據(jù)視點的相關(guān)位置選擇不同的分辨率等級，得以完成層式DCT 的重構(gòu)過程。重構(gòu)過程中提高分辨率層級可以通過對每層的系數(shù)進(jìn)行插值即可實現(xiàn)。近視點可以選擇高分辨率層級，遠(yuǎn)視點可以選擇低分辨率層級，因此就可以將視域內(nèi)的地形劃分為N個可見范圍，選定遠(yuǎn)視點的最大間隔dmax和近視點的最小間隔dmin，取：

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

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

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

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

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

取閾值：

進(jìn)行系數(shù)篩選并通過逆變換重構(gòu)地形。

在視域中以視點位置的變化為基準(zhǔn)，在運(yùn)動過程中選擇不同分辨率的層級模型以及同一分辨率下不同精細(xì)程度進(jìn)行繪制重構(gòu)，因此可以實現(xiàn)地形隨視點的自適應(yīng)連續(xù)繪制。

5 實驗結(jié)果分析及處理

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

5.1 壓縮性能比較

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

表1 各算法比特率均值

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

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

圖9 各算法的峰值信噪比

5.2 幀速率比較

將本文算法的實驗數(shù)據(jù)與傳統(tǒng)LOD 算法、基于DCT的算法和基于小波變換的算法進(jìn)行了比較，如表2所示。

表2 平均幀速比較

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

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

6 結(jié)束語

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

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