翟 銳，呂 科，代雙鳳，潘衛(wèi)國(guó)

(中國(guó)科學(xué)院大學(xué)工程管理與信息技術(shù)學(xué)院，北京，100049)

基于地形高度域的數(shù)據(jù)壓縮算法研究

翟 銳，呂 科，代雙鳳，潘衛(wèi)國(guó)

(中國(guó)科學(xué)院大學(xué)工程管理與信息技術(shù)學(xué)院，北京，100049)

隨著遙感技術(shù)的發(fā)展，地形數(shù)據(jù)規(guī)模越來(lái)越大，遠(yuǎn)遠(yuǎn)超過(guò)了內(nèi)存處理的范圍，成為急需解決的問(wèn)題.通過(guò)數(shù)據(jù)壓縮提高系統(tǒng)吞吐量是常用技術(shù)之一，隨著GPU技術(shù)的快速發(fā)展，傳統(tǒng)的壓縮算法無(wú)法充分利用GPU的能力.鑒于此，本文提出了一種基于GPU的地形數(shù)據(jù)壓縮方法，實(shí)現(xiàn)了高度域和位置信息的壓縮.不同于其他的算法僅對(duì)高度或位置進(jìn)行壓縮，本文的主要貢獻(xiàn)在于將地形的位置和高度同時(shí)進(jìn)行處理，當(dāng)前頂點(diǎn)的所有信息都可以根據(jù)當(dāng)前分段計(jì)算得到.算法對(duì)地形的高度域進(jìn)行貝塞爾曲線的近似，保存每個(gè)頂點(diǎn)的差值，實(shí)現(xiàn)有損和無(wú)損的相結(jié)合的高比率的壓縮.通過(guò)與傳統(tǒng)方法的比較，實(shí)驗(yàn)結(jié)果表明，能夠取得很好的壓縮效果.

數(shù)據(jù)壓縮；地形渲染；圖形處理器

1 引言

大規(guī)模地形渲染是計(jì)算機(jī)圖形學(xué)的主要研究?jī)?nèi)容之一，廣泛應(yīng)用于虛擬現(xiàn)實(shí)、地理信息系統(tǒng)、飛行模擬和游戲等領(lǐng)域.隨著遙感技術(shù)的發(fā)展，數(shù)字地形數(shù)據(jù)的分辨率日益增高，數(shù)據(jù)規(guī)模越來(lái)越大.近幾年，GPU計(jì)算能力得到了飛速提升，處理速度比從內(nèi)存?zhèn)鬏斨翀D形顯卡的速度更快，目前的渲染算法中已從早期處理單個(gè)三角形變?yōu)樘幚砣切螇K，因此數(shù)據(jù)傳輸成為地形渲染的瓶頸之一，而通過(guò)對(duì)地形數(shù)據(jù)采用壓縮技術(shù)增大系統(tǒng)的吞吐量可以有效的解決這一問(wèn)題，所以壓縮技術(shù)的研究已成為國(guó)內(nèi)外研究的熱點(diǎn).

在地形渲染中，數(shù)據(jù)壓縮可用于多種數(shù)據(jù)：包括紋理、高度域或位置等.根據(jù)壓縮方法的不同，可以分為有損壓縮、無(wú)損壓縮和兩種相結(jié)合的方法.針對(duì)于不同的應(yīng)用場(chǎng)景，需求也有一定的差異.例如，對(duì)于無(wú)交互的應(yīng)用，解碼速度要求相對(duì)較低，可以使用無(wú)損的壓縮方法.而對(duì)渲染速度要求較高的場(chǎng)合，可能需要采用有損的壓縮方法.結(jié)合目前的GPU技術(shù)，本文提出了一種無(wú)損和有損相結(jié)合的地形位置信息和高度域信息的壓縮算法，可以實(shí)現(xiàn)高比率的數(shù)據(jù)壓縮，提高系統(tǒng)的吞吐量.

2 國(guó)內(nèi)外研究現(xiàn)狀

根據(jù)數(shù)據(jù)結(jié)構(gòu)的不同，地形渲染算法可以分為兩大類：基于規(guī)則網(wǎng)格的算法如實(shí)時(shí)優(yōu)化自適應(yīng)網(wǎng)格算法翟 銳：基于地形高度域的數(shù)據(jù)壓縮算法研究(Real-Time Optimally Adapting Mesh，ROAM)[1]和基于不規(guī)則三角網(wǎng)的算法(Triangulated Irregular Network，TIN)，如漸進(jìn)網(wǎng)格(Progressive Mesh)[2]等.與不規(guī)則網(wǎng)格相比，規(guī)則結(jié)構(gòu)更適合基于GPU的并行的環(huán)境，統(tǒng)一的結(jié)構(gòu)更易于編碼與實(shí)現(xiàn)，在壓縮領(lǐng)域也是如此.本文的研究?jī)?nèi)容是基于約束四叉樹的位置信息和高度域信息的壓縮.

根據(jù)壓縮策略的不同，可以分為有損壓縮、無(wú)損壓縮或兩者相結(jié)合的方法.有損壓縮常被用于實(shí)時(shí)渲染領(lǐng)域，對(duì)渲染速度要求較高的系統(tǒng).例如Gerstner[3]處理原始地形數(shù)據(jù)的子集來(lái)壓縮高度域，通過(guò)線性的插值計(jì)算被刪除的頂點(diǎn).Kim[4]等將地形數(shù)據(jù)進(jìn)行小波變換來(lái)構(gòu)建近似的三角化網(wǎng)格.但是這些方法編碼速度較慢.除了實(shí)時(shí)渲染系統(tǒng)，有損壓縮還用于分布的網(wǎng)絡(luò)傳輸中[5].

無(wú)損壓縮方法中，根據(jù)相鄰頂點(diǎn)的信息預(yù)測(cè)頂點(diǎn)的高度，使用通用的無(wú)損壓縮方法對(duì)預(yù)測(cè)誤差進(jìn)行編碼.早期的一些算法中，使用各種方法對(duì)編碼進(jìn)行預(yù)測(cè)，如霍夫曼編碼、拉格朗日乘數(shù)優(yōu)化的線性方法或算術(shù)編碼[6,7]等.這些方法的壓縮效率比直接使用數(shù)字圖像編碼的壓縮效率要高，但處理數(shù)據(jù)的方式是順序的，不適用于并行的壓縮.還有一些算法將高度域映射到更高階的表面[8]，實(shí)現(xiàn)基于點(diǎn)的并行，不過(guò)這些方法提出的時(shí)間較早，在可編程的GPU之前出現(xiàn)，并沒(méi)有考慮到目前的并行的框架.也有一些算法將圖像的壓縮算法應(yīng)用于地形的壓縮方法中.與圖像的灰度壓縮不同，在一些地形的壓縮算法中，地形的壓縮算法需要考慮到地形的結(jié)構(gòu)，而在灰度圖的壓縮中通常沒(méi)有考慮到這一點(diǎn).

最近的一些壓縮方法在GPU上處理數(shù)據(jù).Dick等[9]使用與文獻(xiàn)[3]中類似的編碼，在GPU上進(jìn)行了實(shí)現(xiàn)，不過(guò)該方法只對(duì)位置進(jìn)行了壓縮，并沒(méi)有針對(duì)處理高度域進(jìn)行處理.Lindstrom[10]等使用線性預(yù)測(cè)方法，不過(guò)這種方法中每一塊的解壓實(shí)際上是順序的過(guò)程，因?yàn)榇鈮旱捻旤c(diǎn)的高度是根據(jù)之前壓縮的頂點(diǎn)獲得，無(wú)法獲取任意頂點(diǎn)的值.此外，Stookey[11]采用了有損壓縮的方法并在網(wǎng)絡(luò)上實(shí)現(xiàn)了分布傳輸.Olanda[12]使用小波分塊的金字塔用于在線的三維可視化系統(tǒng).Li[13]等人采用類似于文獻(xiàn)[11]中的方法進(jìn)行5D的數(shù)據(jù)壓縮，并使用CUDA解方程.但是上述方法需要迭代過(guò)程，本質(zhì)上仍然是順序的方法.Dore[14,15]等人最近提出了一種基于高度域壓縮的算法，將一塊地形的高度值近似到貝塞爾曲面，只需保存控制點(diǎn)的信息，運(yùn)行時(shí)動(dòng)態(tài)的計(jì)算頂點(diǎn)的高度.但這種方法中的分塊只能是一個(gè)層次，而且只對(duì)頂點(diǎn)進(jìn)行了壓縮，并沒(méi)有結(jié)合位置信息.Niski[16]將高度域作為紋理進(jìn)程處理，利用圖像壓縮的算法對(duì)高度域進(jìn)行壓縮.但該方法沒(méi)有考慮到位置的壓縮，因此不夠靈活.隨著通用圖形處理器(General Purpose GPU,GPGPU)的發(fā)展，研究者使用并行技術(shù)實(shí)現(xiàn)經(jīng)典的編碼，如基于CUDA實(shí)現(xiàn)的霍夫曼編碼[17]，JPEG2000編碼[18]等.不過(guò)這些編碼靈活性有限，而且將其用于地形壓縮時(shí)的效果還需要進(jìn)一步的考慮.

根據(jù)上述的研究基礎(chǔ)，本文提出了一種對(duì)位置信息和高度信息同時(shí)進(jìn)行壓縮的壓縮方法.與之前的算法不同，應(yīng)用本文的算法，在獲取任意點(diǎn)的位置和高度時(shí)，只需要局部的參考信息，并且結(jié)合GPU并行環(huán)境，實(shí)現(xiàn)了完全的并行數(shù)據(jù)處理.實(shí)驗(yàn)結(jié)果表明，本文所提算法在數(shù)據(jù)壓縮比和運(yùn)行效率上都得到了很大的提高.

3 算法

在地形渲染領(lǐng)域，約束四叉樹是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，與不規(guī)則的三角形網(wǎng)格相比，更加適用于基于GPU的環(huán)境.本文所提方法采用約束四叉樹的數(shù)據(jù)結(jié)構(gòu)，并對(duì)地形數(shù)據(jù)的位置信息采用無(wú)損壓縮方法，對(duì)地形數(shù)據(jù)的高度信息可以采用有損或無(wú)損的壓縮方法.

地形數(shù)據(jù)的預(yù)處理流程如圖1所示，包含如下幾個(gè)步驟：首先是將顯示所需的地形數(shù)據(jù)以約束四叉樹的結(jié)構(gòu)表示并三角化.然后對(duì)地形的位置信息和高度信息分別進(jìn)行壓縮.

3.1 位置信息壓縮

對(duì)于位置信息的壓縮時(shí)，借鑒了Gerstiner提出約束四叉樹的序列化方法[3].主要思想如下：對(duì)于每個(gè)網(wǎng)格，初始化階段時(shí)，選擇兩個(gè)頂點(diǎn)并記錄其位置信息，然后根據(jù)前兩個(gè)頂點(diǎn)和標(biāo)識(shí)符計(jì)算第三個(gè)頂點(diǎn)的信息，重復(fù)該步驟直至訪問(wèn)所有的頂點(diǎn).

構(gòu)建鏈表的步驟如下：首先根據(jù)觀察者與該塊的距離等信息決定該塊的細(xì)分層次，隨后進(jìn)行三角化.三角化后，選擇其中一個(gè)三角形的兩個(gè)頂點(diǎn)作為初始頂點(diǎn)，根據(jù)該三角形的最后一個(gè)頂點(diǎn)的位置和與前兩個(gè)頂點(diǎn)的相對(duì)位置決定三角形的類型.完成當(dāng)前三角形的構(gòu)建后，根據(jù)該頂點(diǎn)和其中一個(gè)起始頂點(diǎn)(由方向決定)作為下一個(gè)三角形的初始頂點(diǎn)，重復(fù)上述構(gòu)建過(guò)程直至訪問(wèn)所有的頂點(diǎn).

三角形包括三種類型：直角邊到直角邊，直角邊到斜邊，斜邊到直角邊.方向?yàn)閮煞N：順時(shí)針和逆時(shí)針.圖2表示了這幾種情況，壓縮時(shí)，已知頂點(diǎn)為V0和V1，根據(jù)V2的位置決定三角形的類型.解壓時(shí)，對(duì)于直角三角形的三個(gè)頂點(diǎn)V0、V1、V2，已知頂點(diǎn)V0和V1，可以根據(jù)兩個(gè)頂點(diǎn)的位置和三角形的類型計(jì)算得到另一個(gè)頂點(diǎn)V2的位置信息.

除了頂點(diǎn)的位置信息進(jìn)行編碼外，還需要處理頂點(diǎn)的高度信息.本文采用了一種分層的方法對(duì)高度域進(jìn)行壓縮，將高度域分為多個(gè)層次，然后分別對(duì)每一層進(jìn)行處理.第一層是對(duì)整個(gè)高度域的粗糙近似，第二層在第一層的基礎(chǔ)上增加了細(xì)節(jié)，最后一層是與真實(shí)地形的最終的差值，其中第二層和第三層的值可能都為0，因此在實(shí)際中可能不需要保存這些數(shù)據(jù).

一塊數(shù)據(jù)可能包含多個(gè)子帶，每個(gè)子帶包含頭信息和數(shù)據(jù)信息.一塊數(shù)據(jù)可能包含多個(gè)頭信息和多個(gè)頂點(diǎn)，之所以這樣設(shè)計(jì)是可以靈活的添加和刪除頂點(diǎn)，除非結(jié)構(gòu)有大的變化，無(wú)需對(duì)結(jié)構(gòu)進(jìn)行大的調(diào)整.

表1為本文所采用的數(shù)據(jù)結(jié)構(gòu)，可以分為頭信息和每個(gè)頂點(diǎn)的信息.頭信息包含當(dāng)前子帶中的頂點(diǎn)的共有信息，包括頂點(diǎn)個(gè)數(shù)、子帶中第一個(gè)頂點(diǎn)的高度和最后一個(gè)頂點(diǎn)的高度.頂點(diǎn)數(shù)表明每一個(gè)貝塞爾曲線覆蓋多少個(gè)頂點(diǎn).對(duì)于地形變化較大的區(qū)域，如果包含的頂點(diǎn)數(shù)過(guò)多，可能導(dǎo)致差值1和差值2較大，反而不能得到好的壓縮效率.相比于粗糙的區(qū)域，平坦區(qū)域中的貝塞爾曲線可能可以包含更多的頂點(diǎn)也能有較好壓縮比率.除了第一個(gè)和最后一個(gè)頂點(diǎn)，其他的頂點(diǎn)使用兩個(gè)字段保存差值信息，實(shí)際應(yīng)用中，根據(jù)實(shí)際需求，可以決定是否對(duì)兩個(gè)差值進(jìn)行無(wú)損壓縮.運(yùn)行時(shí)，根據(jù)頭信息中的貝塞爾參數(shù)和每個(gè)頂點(diǎn)自帶的信息計(jì)算相應(yīng)頂點(diǎn)的高度.

表1 數(shù)據(jù)結(jié)構(gòu)

3.2 高度域壓縮

上一節(jié)中對(duì)數(shù)據(jù)的編碼和結(jié)構(gòu)進(jìn)行了介紹，本節(jié)中主要介紹如何使用貝塞爾曲線對(duì)高度域進(jìn)行模擬.由于地形高度域具有規(guī)則性，可以使用一些專門的曲線對(duì)其進(jìn)行近似.貝塞爾曲線是一種常用的構(gòu)建地形的工具，只需要幾個(gè)控制點(diǎn)信息即可計(jì)算曲線上頂點(diǎn)的位置.

在大多數(shù)的場(chǎng)合中，原始的高度域和根據(jù)貝塞爾曲線構(gòu)建的層次1的差值的范圍集中在0的周圍.這樣的分布在基于預(yù)測(cè)的方法中是非常常見(jiàn)的.大多數(shù)的差值可以使用一個(gè)相對(duì)較小的位數(shù)保存.若還不滿足需求，將最終的值保存在層次3中.此外，層次2和層次3還可以進(jìn)一步的壓縮.

實(shí)際中，可以使用二階或更高階的貝塞爾進(jìn)行模擬，階數(shù)越高，模擬結(jié)果越精確.但是如果階數(shù)越高，導(dǎo)致計(jì)算開銷過(guò)大，因此，在實(shí)際應(yīng)用中，通常使用二階的貝塞爾曲線進(jìn)行模擬，通過(guò)修改每個(gè)貝塞爾曲線覆蓋的頂點(diǎn)個(gè)數(shù)修正壓縮率.二階貝塞爾曲線包含兩個(gè)頂點(diǎn)V0，Vn和一個(gè)控制點(diǎn)C0.其中V0和Vn高度為H0和Hn，C0是貝塞爾參數(shù)的控制點(diǎn)的值.

已知頂點(diǎn)V0，Vn的信息，只需計(jì)算控制點(diǎn)C0的位置，可以考慮使用最小二乘法對(duì)貝塞爾曲線進(jìn)行擬合.

解壓時(shí)，中間頂點(diǎn)的高度通過(guò)下述的公式計(jì)算得到.每個(gè)頂點(diǎn)保存了一個(gè)參數(shù)t，相應(yīng)頂點(diǎn)的高度H(t)的計(jì)算方法如式(1)所示：

H(t)=(1-t)2H0+2t(1-t)H1+t2H2,t∈[0,1]

(1)

應(yīng)當(dāng)指出的是，每個(gè)頂點(diǎn)的高度可以并行獲得.已知V1和Vn的高度，其他頂點(diǎn)的高度V2,V3,…,Vn-1可以獨(dú)立計(jì)算.差值1可以以稀疏矩陣方式存儲(chǔ)在層次2.差值2存儲(chǔ)在第3層.如果為了直接和快速的訪問(wèn)每個(gè)最終的殘留，可以不對(duì)差值進(jìn)行壓縮.

3.3 基于GPU的實(shí)現(xiàn)

目前GPU不僅用于繪制，由于其具有很強(qiáng)的浮點(diǎn)數(shù)計(jì)算能力，被廣泛應(yīng)用在通用計(jì)算領(lǐng)域[19～21].

在基于CUDA的壓縮中，壓縮在不同的核中執(zhí)行，其中一個(gè)核計(jì)算近似的貝塞爾曲線，另外兩個(gè)核計(jì)算層次2和層次3，將中間結(jié)果保存在訪問(wèn)速度較快的共享存儲(chǔ)器中.計(jì)算近似的貝塞爾曲線時(shí)，分別對(duì)每個(gè)高度域頂點(diǎn)分配一個(gè)線程，使用最小二乘法實(shí)現(xiàn)對(duì)曲線的近似，對(duì)于大小為32×32的線程塊，可以計(jì)算128個(gè)分段的信息.構(gòu)建層次2時(shí)，將高度值和上一個(gè)步驟的近似做差值計(jì)算，然后將最終的殘留保存在層次3中.

目前的圖形硬件支持可編程的著色器，在渲染每一幀時(shí)，將可見(jiàn)的未緩存的塊進(jìn)行壓縮，并傳輸?shù)斤@存中，在GPU中解壓.在對(duì)某一塊數(shù)據(jù)進(jìn)行解碼時(shí)，首先讀取帶頭信息，加載到頂點(diǎn)緩沖區(qū)中.根據(jù)帶頭信息得到第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)的高度值，結(jié)合子帶中兩個(gè)頂點(diǎn)V0、V1和下一個(gè)頂點(diǎn)的類型得到第三個(gè)頂點(diǎn)的位置.然后按照上文中的步驟構(gòu)建其他的三角形.通過(guò)貝塞爾曲線得到近似高度，根據(jù)實(shí)際需要與兩個(gè)差值相加，得到最終的頂點(diǎn)高度.

壓縮和解壓步驟分別可以并行的執(zhí)行，壓縮過(guò)程中同時(shí)對(duì)多個(gè)帶進(jìn)行計(jì)算.在解壓過(guò)程中，可以分別計(jì)算每個(gè)段中的頂點(diǎn)的詳細(xì)位置，而無(wú)需考慮其他的信息.整個(gè)系統(tǒng)可以并行的執(zhí)行，壓縮和解壓過(guò)程中的最小單位即貝塞爾曲線包含的頂點(diǎn)個(gè)數(shù)，例如一個(gè)貝塞爾曲線包含10個(gè)頂點(diǎn)，實(shí)現(xiàn)了細(xì)粒度的并行.

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

本節(jié)中，我們通過(guò)實(shí)驗(yàn)對(duì)本文算法進(jìn)行驗(yàn)證和分析.數(shù)據(jù)對(duì)象是結(jié)構(gòu)較為復(fù)雜的Pudget Sound和結(jié)構(gòu)較為平坦的夏威夷的數(shù)據(jù)，如圖5所示.實(shí)驗(yàn)運(yùn)行環(huán)境為：微軟Win7 32位系統(tǒng)，Intel i7-3610，2.3GHz內(nèi)存，3.14GB內(nèi)存，顯卡為NVIDIA GeForce GT630M.

在未經(jīng)壓縮的結(jié)構(gòu)中，每個(gè)頂點(diǎn)占用32bit，其中高度域12bit，位置x和y分別是10bit，共32bit.每個(gè)三角形占用96bit.經(jīng)過(guò)本文方法的壓縮后，頭文件中，頂點(diǎn)數(shù)為6bit，高度1和高度2共為24bit，兩個(gè)貝塞爾參數(shù)共為16bit.共計(jì)42bit.對(duì)于單個(gè)頂點(diǎn)而言，第一個(gè)頂點(diǎn)只需要保存位置信息20bit，第二個(gè)頂點(diǎn)20bit和差值2～7bit，共計(jì)22～27.頂點(diǎn)3至(n-1)為類型3bit和插值2～7bit，共計(jì)5～10bit.最后一個(gè)頂點(diǎn)3bit.這些頂點(diǎn)所占用的bit數(shù)共計(jì)：[5(n+6),10(n+2)]bit，共計(jì)可組成n-2個(gè)三角形.如果n=8，8個(gè)頂點(diǎn)能夠組成6個(gè)三角形，占用的空間共計(jì)為70～100bit，與之前每個(gè)三角形占用96bit相比，壓縮效率為：5.76～8.2.在實(shí)際應(yīng)用中，由于差值可能為0，壓縮效率可能更高.

表2和表3分別表示了Puget Sound和夏威夷的數(shù)據(jù)使用不同的貝塞爾個(gè)數(shù)的壓縮效率，第一行表示貝塞爾參數(shù)包含的頂點(diǎn)個(gè)數(shù)，第二行表示其壓縮效率.圖6和圖7是與表2和表3相對(duì)應(yīng)的柱狀圖的顯示.橫軸表示貝塞爾曲線包含不同的頂點(diǎn)時(shí)的壓縮效率，縱軸表示相應(yīng)的壓縮率.

表2 Puget Sound壓縮結(jié)果

表3 夏威夷壓縮結(jié)果

圖6和圖7中的數(shù)據(jù)表明，對(duì)于單個(gè)地形而言，貝塞爾曲線包含的頂點(diǎn)增多，壓縮率會(huì)逐步提高，但是到達(dá)某臨界值之后，壓縮效率會(huì)有所下降，需要額外空間保存差值2和差值3的值.對(duì)于不同的地形而言，壓縮效率也有所不同，在地形較為平坦的區(qū)域，壓縮的效率更高.而且出現(xiàn)拐點(diǎn)的貝塞爾曲線包含的頂點(diǎn)的值也不同，平坦區(qū)域的拐點(diǎn)的值大于粗糙的區(qū)域的拐點(diǎn)的值.總體上而言，平坦的數(shù)據(jù)的壓縮效果要好于結(jié)構(gòu)復(fù)雜的數(shù)據(jù)的壓縮效果.

使用經(jīng)典的算法ZIP對(duì)數(shù)據(jù)進(jìn)行壓縮，其壓縮比率大概為2.5∶1，而本文所提算法相對(duì)于結(jié)構(gòu)復(fù)雜的數(shù)據(jù)的平均壓縮比率為6.3∶1，相對(duì)于平坦的數(shù)據(jù)的平均壓縮比率為7.06∶1.可以看出，本文所提算法具有更好的壓縮效果.由于壓縮過(guò)程中包含復(fù)雜的計(jì)算，因此解壓速度要快于壓縮速度.不過(guò)貝塞爾曲線包含的頂點(diǎn)個(gè)數(shù)對(duì)壓縮和解壓的速度不會(huì)有太大的影響，這是因?yàn)閷?shí)際的操作基本是基于每個(gè)頂點(diǎn)執(zhí)行.實(shí)際應(yīng)用中，每秒可以解壓108的頂點(diǎn)，滿足了實(shí)時(shí)的需求.如果提高壓縮的速度，可以更進(jìn)一步的提高吞吐量.

5 結(jié)語(yǔ)

本文提出了一種新的高度域快速壓縮和解壓方法，可以充分利用GPU的并行功能.實(shí)現(xiàn)了有損和無(wú)損的壓縮.我們的方法在兩個(gè)無(wú)關(guān)的數(shù)據(jù)中進(jìn)行了試驗(yàn)，實(shí)驗(yàn)結(jié)果表明，能夠?qū)崿F(xiàn)非常高效的壓縮效果.與傳統(tǒng)的壓縮方法相比，我們的壓縮率要遠(yuǎn)遠(yuǎn)高于其壓縮效率，隨著數(shù)據(jù)規(guī)模的增大，可能實(shí)現(xiàn)進(jìn)一步的提升.

本文的方法可以用于大規(guī)模的地形數(shù)據(jù)處理的二次處理中.解壓速度和經(jīng)典的基于GPU的解壓速度相當(dāng).此外，系統(tǒng)還可以與其他壓縮方法相結(jié)合.下一步的工作中，我們將考慮更高階的貝塞爾曲線能否取得更好的壓縮效率，以及如何快速的計(jì)算高階貝塞爾曲線的控制點(diǎn).

[1]Duchaineau M,Wolinsky M,Sigeti D E,et al.ROAMing terrain:real-time optimally adapting meshes[A].Visualization'97[C].Phoenix,AZ,USA:IEEE,1997.81-88.

[2]Hoppe H.View-dependent refinement of progressive meshes[A].ProcSiggraph[C].Los Angeles,USA:ACM,1997.189-198.

[3]Gerstner T.Multi-resolution visualization and compression of global topographic data[J].Geoinformatica,2003,7(1):7-32.

[4]Kim J K,Ra J B.A real-time terrain visualization algorithm using wavelet-based compression[J].Visual Computer,2004,20(2):67-85.

[5]Xie Z,Marcus A,Randolph F,Barbara C,et al.Progressive transmission of lossily compressed terrain[A].Conferencialatinoamericana de informática (CLEI 2008)[C].Santa Fe,Argentina:2008.8-12.

[6]Kidner B,Derek S.Advances in the data compression of digital elevation models[J].Computers & Geosciences,2003,29(8):985-1002.

[7]Inanc M.Compressing terrain elevation datasets[D].NY,USA:Rensselaer Polytechnic Institute Troy,2008.

[8]Kidner B,Derek S.Storageefficient techniques for representing digital terrain models[A].Innovations in GIS 4[C].London,England:Taylor & Francis,1997.25-41.

[9]Dick C,Schneider J,Westermann R.Efficient geometry compression for GPU-based decoding in realtime terrain rendering[J].Computer Graphics Forum,2009,28(1):67-83.

[10]Lindstrom P,Cohen D.On-the-fly decompression and rendering of multiresolution terrain[A].Proceedings of the 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games[C].Bethesda,MD,USA:ACM,2010.65-73.

[11]Jared S,Randolph F,Xie Z,et al.Parallel ODETLAP for terrain compression and reconstruction[A].Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems[C].Irvine,California,USA:ACM,2008.17.

[12]Olanda R,Pérez M,et al.Terrain data compression using wavelet-tiled pyramids for online 3D terrain visualization[J].International Journal of Geographical Information Science,2013,28(2):407-425.

[13]Li Y.CUDA-accelerated HD-ODETLAP:A high dimensional geospatial data compression framework[D].NY,USA:Rensselaer Polytechnic Institute Troy,2011.

[16]Niski K,Purnomo B,Cohen J.Multi-grained level of detail using a hierarchical seamless texture atlas[A].Proceedings of the 2007 Symposium on Interactive 3D Graphics and Games[C].Seattle,WA,USA:ACM,2007.153-160.

[17]Rahmani H,CihanT,Cuneyt A.A parallel huffman coder on the CUDA architecture[A].Visual Communications and Image Processing Conference,2014 IEEE[C].Valletta,Malta:IEEE,2014.311-314.

[18]Lee J,Kim B,Yoon K.CUDA-based JPEG2000 encoding scheme[A].International Conference on Advanced Communication Technology[C].Pyeongchang,Korea:IEEE,2014.671-674.

[19]趙星,胡晶晶,潘曉川,張朋.一種新的基于GPU實(shí)現(xiàn)的錐束CT正投影算法[J].電子學(xué)報(bào),2009,37(6):1165-1169. Zhao Xing,Hu Jingjing,Pan Xiaochuan,Zhang Peng.A novel GPU based cone beam CT forward projection method[J].Acta Electronica Sinica,2009,37(6):1165-1169.(in Chinese)

[20]楊正龍,金林,李蔚清.基于GPU的圖形電磁計(jì)算加速算法[J].電子學(xué)報(bào),2007,35(6):1056-1060. Yang Zhenglong,Jin Lin,Li Weiqing.Accelerated GRECO based on GPU[J].Acta Electronica Sinica,2007,35(6):1056-1060.(in Chinese)

[21]王綱,季振洲,張澤旭.大規(guī)模真實(shí)感雪景實(shí)時(shí)渲染[J].電子學(xué)報(bào),2012,40(9):1746-1751. Wang Gang,Ji Zhenzhou,Zhang Zexu.Large scale realistic snow scene real-time rendering[J].Acta Electronica Sinica,2012,40(9):1746-1751.(in Chinese)

翟 銳 男，1981年生于河南焦作,中國(guó)科學(xué)院大學(xué)在讀博士生，主要研究方向?yàn)閿?shù)字圖像處理、計(jì)算機(jī)圖形學(xué)、三維可視化.

E-mail:zhairui11b@mails.ucas.ac.cn

呂 科 男，1971出生于寧夏西吉，教授，博士生導(dǎo)師，主要研究方向?yàn)閿?shù)字圖像處理、計(jì)算機(jī)圖形學(xué)、智能信息處理技術(shù).

E-mail:luk@ucas.ac.cn

Research on Terrain Height Field Compression Algorithm

ZHAI Rui,Lü Ke,DAI Shuang-feng,PAN Wei-guo

(CollegeofEngineeringandInformationTechnology,UniversityofChineseAcademyofSciences,Beijing100049,China)

With the development of remote sensing technology,the size of terrain is growing rapidly,and far beyond the scope of main memory,has become an urgent problem.Data compression is a popular technology to increase system throughput.With the rapid development of GPU(Graphics Processing Unit) technology,the traditional compression algorithms cannot take full advantage of the ability of the current GPU.In this paper,we propose a GPU-based terrain data compression method,and achieve a high rate compression of terrain height field and location.Comparing to other algorithms,the main contribution of our algorithm is that the compression of terrain height filed and position is executed in the same time,and all the information of a node can be calculated according to the presentstrip.For terrain height domain,we firstly make Bezier curve approximation,then save the difference.After the steps above,we can achieve high compression ratio.By comparison with traditional methods,we get reasonable experimental results.

data compression;terrain rendering;graphics processing unit (GPU)

2015-04-09;

2015-05-05;責(zé)任編輯：梅志強(qiáng)

國(guó)家自然科學(xué)基金(No.61271435);北京市自然科學(xué)基金重點(diǎn)項(xiàng)目(No.4141003)

TP302.7

A

0372-2112 (2016)12-2894-06

??學(xué)報(bào)URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.12.012