面向GPU快速處理的地面材質(zhì)數(shù)據(jù)壓縮方法

陸巍巍，徐　濤，徐珂文

（1.海軍航空工程學(xué)院7系，山東煙臺(tái)264001；2.91206部隊(duì)，山東青島266108）

面向GPU快速處理的地面材質(zhì)數(shù)據(jù)壓縮方法

陸巍巍1，徐濤2，徐珂文1

（1.海軍航空工程學(xué)院7系，山東煙臺(tái)264001；2.91206部隊(duì)，山東青島266108）

為解決雷達(dá)圖像仿真中海量地面材質(zhì)數(shù)據(jù)的存儲(chǔ)和加載問題，采用基于自適應(yīng)最大行程長度編碼和修正偶對(duì)的壓縮算法進(jìn)行材質(zhì)數(shù)據(jù)的壓縮，從而有效地減少了數(shù)據(jù)的存儲(chǔ)量，消除數(shù)據(jù)傳輸?shù)钠款i，提高了數(shù)據(jù)傳輸?shù)耐掏履芰?。壓縮算法面向GPU快速處理，得到壓縮數(shù)據(jù)適用于GPU進(jìn)行快速解壓。

雷達(dá)圖像仿真；材質(zhì)數(shù)據(jù)壓縮；GPU；自適應(yīng)最大行程長度編碼

機(jī)載雷達(dá)圖像仿真需要大規(guī)模地面材質(zhì)數(shù)據(jù)的支持。盡管計(jì)算機(jī)存儲(chǔ)和運(yùn)算速度已經(jīng)有了長足的發(fā)展和進(jìn)步，但仍受限于圖形硬件的顯存容量，事實(shí)上依然沒有足夠的空間來滿足不斷增加的高分辨率地形數(shù)據(jù)的存儲(chǔ)需求，不可能一次加載整個(gè)仿真區(qū)域范圍內(nèi)的材質(zhì)數(shù)據(jù)［1］。

由于在并行運(yùn)算方面的突出優(yōu)勢(shì)，GPU在實(shí)時(shí)雷達(dá)圖像仿真中得到廣泛應(yīng)用［2-3］。雷達(dá)圖像仿真中，仿真圖像最終均需要通過圖形硬件處理核心GPU來完成可視化繪制和渲染。在仿真過程中，材質(zhì)數(shù)據(jù)從外存被調(diào)取到最后的渲染輸出，需要經(jīng)過外存、內(nèi)存到顯存的傳輸過程。雖然可采用固態(tài)硬盤等方法提高外存的數(shù)據(jù)讀取速度，但硬盤的存取速度仍是制約數(shù)據(jù)從外到內(nèi)的主要因素。因此，數(shù)據(jù)讀取和操作占據(jù)了GPU繪制時(shí)間的重要部分，而數(shù)據(jù)傳輸?shù)膸拕t是影響繪制速度的關(guān)鍵。為減少材質(zhì)數(shù)據(jù)量的大小，消除數(shù)據(jù)傳輸?shù)钠款i，提高數(shù)據(jù)傳輸?shù)耐掏履芰?，有必要?duì)材質(zhì)數(shù)據(jù)進(jìn)行預(yù)先壓縮處理，直接將壓縮數(shù)據(jù)傳輸?shù)斤@存中，并采用基于GPU快速解壓的方法，完成視景或者雷達(dá)圖像仿真實(shí)時(shí)繪制過程中的數(shù)據(jù)提取。

為應(yīng)對(duì)雷達(dá)圖像仿真中大規(guī)模地面材質(zhì)數(shù)據(jù)的調(diào)度對(duì)GPU的存儲(chǔ)和運(yùn)算能力帶來的挑戰(zhàn)，本文研究了一種面向GPU快速解壓的地面材質(zhì)數(shù)據(jù)壓縮方法，并對(duì)方法的性能進(jìn)行了實(shí)驗(yàn)驗(yàn)證。

1　地面材質(zhì)數(shù)據(jù)壓縮

雷達(dá)圖像仿真中，地面材質(zhì)數(shù)據(jù)采用與灰度圖像相似的方式進(jìn)行存儲(chǔ)，因而下文在討論壓縮算法時(shí)，會(huì)將地面材質(zhì)數(shù)據(jù)稱為材質(zhì)圖像。針對(duì)灰度圖像的壓縮問題，禹蒲陽和蔣正金等人采用離散余弦變換（Discrete Cosine Transform，DCT）［4］或者離散小波變換（Discrete Wavelet Transform，DWT）和游程編碼（Run-Length Encoded，RLE）技術(shù)相結(jié)合的壓縮方法［5］，其壓縮效果和其他方法相比略有提高，但是這些壓縮算法屬于有損壓縮，不適用于地形材質(zhì)圖像的壓縮。謝耀華等人［6］對(duì)像素進(jìn)行灰度分類并用掩膜圖記錄類別信息，然后采用Hilbert曲線將各類像素進(jìn)行塊間和塊內(nèi)重排，最后采用LZW（Lempel-Ziv-Welch）算法對(duì)掩膜圖與各類像素的數(shù)據(jù)流進(jìn)行編碼，雖然該無損壓縮算法在總體上具有比LZW、RLE和霍夫曼（Huffman）等方法更高的壓縮比，但不便于GPU的并行流處理。鄭運(yùn)平等人［7］通過使用矩形非對(duì)稱逆布局模型和擴(kuò)展的Gouraud陰影法，提出了一種具有更高壓縮比的灰度圖像表示算法，但該算法實(shí)現(xiàn)復(fù)雜，并且會(huì)損失圖像的細(xì)節(jié)，不適合地面材質(zhì)圖像的壓縮處理。

地面材質(zhì)圖像由許多材質(zhì)相同的圖像區(qū)域組成，如圖1所示。

圖1　地面材質(zhì)圖像示例Fig.1 Image sample of surface material

在這些圖像區(qū)域中所有像素表示同一種材質(zhì)，因而在同一掃描行上存在許多連續(xù)的具有相同數(shù)值的像素。在這種情況下，采用RLE壓縮方法，就無須存儲(chǔ)每一個(gè)像素的材質(zhì)值，而僅僅存儲(chǔ)一個(gè)像素值以及具有相同材質(zhì)的像素?cái)?shù)目。采用RLE壓縮方法得到壓縮率的大小與圖像本身的屬性有關(guān)［8］。材質(zhì)圖像中材質(zhì)種類越少，材質(zhì)的連續(xù)性越強(qiáng)，可以得到的壓縮比就越大，反之就越小。解碼的過程根據(jù)像素灰度和個(gè)數(shù)一次填充到原來的圖像中去就可以，不需要較大的計(jì)算開銷就可實(shí)現(xiàn)較好的壓縮效果，非常適合GPU上的運(yùn)算處理實(shí)現(xiàn)［9］。

考慮到地面材質(zhì)圖像的空間相關(guān)性和算法實(shí)現(xiàn)的復(fù)雜性，本文采用無損的RLE壓縮方法實(shí)現(xiàn)材質(zhì)數(shù)據(jù)的壓縮，這樣可以使GPU上解壓縮著色器程序的實(shí)現(xiàn)更為簡單，且具有很高的運(yùn)行效率。

1）行程編碼的基本原理。設(shè)（x1，x2，…，xN）為圖像中某一行像素（如圖2所示），每行圖像都由k段長度為li、灰度值為gi（i∈［1，k］）的片段組成，則該行圖像可由偶對(duì)（li，gi）來表示，每一個(gè)偶對(duì)（li，gi）稱為灰度級(jí)行程［10］。由此可得式（1）所示映射關(guān)系：

如果灰度級(jí)的行程較大，則式（1）可認(rèn)為是對(duì)原像素行的一種壓縮表示。可見，對(duì)地面材質(zhì)數(shù)據(jù)來說，大塊區(qū)域范圍內(nèi)灰度值相同的情況越多，壓縮效果越顯著。

圖2　一行圖像的行程編碼Fig.2 Run length encoding of one line image

2）適用于材質(zhì)圖像的編碼算法描述。行程編碼使用最大行程長度編碼，而最大行程長度不同時(shí)所獲得的壓縮比不同，為獲得較優(yōu)的材質(zhì)圖像壓縮比，本文研究了一種自適應(yīng)最大行程長度編碼壓縮方法。已有文獻(xiàn)雖然也研究了自適應(yīng)最大行程長度編碼的方法，但并沒有給出最大行程長度［11-12］的計(jì)算方法。本文采用如下方法獲得最優(yōu)的最大行程長度L。

設(shè)材質(zhì)圖像行列數(shù)目為M×N，每行灰度值為g的片段連續(xù)出現(xiàn)的長度為li（1≤li≤N），掃描材質(zhì)圖像的每一行，統(tǒng)計(jì)出各行連續(xù)出現(xiàn)相同長度li的次數(shù)Ci，同時(shí)也可統(tǒng)計(jì)出總共有K種長度，即1≤i≤K。則求解最優(yōu)的最大行程長度L的問題可以轉(zhuǎn)化為求函數(shù)的極小值問題。

第1種情況：若［log2li］≤T，則采用最大行程長度L時(shí)，連續(xù)出現(xiàn)Ci次的相同長度li的長度編碼的二進(jìn)制位數(shù)總和Bi（T）=CiT。

第2種情況：若［log2li］＞T，則表示連續(xù)出現(xiàn)的長度li大于最大行程長度L，此時(shí)須要分［li/2T］次進(jìn)行存儲(chǔ)，則長度編碼的二進(jìn)制位數(shù)總和Bi（T）=［li/2T］CiT。

對(duì)于地形的地面材質(zhì)屬性，還存在一個(gè)比較特殊的情形，就是覆蓋絕大部分地形的材質(zhì)種類也就十幾種，即有十幾種的地形材質(zhì)在大部分的地形區(qū)域出現(xiàn)的概率較高，而其他的地形材質(zhì)種類出現(xiàn)的概率較低。因此，可以在材質(zhì)種類編碼時(shí)，將最常見的16種材質(zhì)由4位二進(jìn)制數(shù)表示，而其他不常見的材質(zhì)種類用8位二進(jìn)制數(shù)來表示。

針對(duì)上述的地面材質(zhì)圖像特點(diǎn)，在行程編碼時(shí)，為進(jìn)一步減少編碼后的數(shù)據(jù)量，偶對(duì)（li，gi）中的gi（灰度級(jí)）采用變長的編碼方法，對(duì)出現(xiàn)概率較高的16種材質(zhì)用4位二進(jìn)制數(shù)表示，其他材質(zhì)用8位二進(jìn)制數(shù)來表示。為了使計(jì)算機(jī)在解壓時(shí)，明確當(dāng)前的材質(zhì)到底是4位還是8位二進(jìn)制數(shù)表示的，本文采用（li，B，gi）來替代偶對(duì)（li，gi），其中B為1位的二進(jìn)制數(shù)，B=1表示gi是8位二進(jìn)制數(shù)，B=0表示gi是4位二進(jìn)制數(shù)。

因此，根據(jù)上述采用的材質(zhì)圖像壓縮方法，材質(zhì)圖像碼流數(shù)據(jù)表示的格式如圖3所示。

圖3　材質(zhì)圖像壓縮后的碼流格式Fig.3 Stream format of compressed material image

2　GPU解壓處理

采用上述自適應(yīng)最大行程長度編碼和修正偶對(duì)的壓縮算法，雖然壓縮時(shí)須掃描2遍材質(zhì)圖像，計(jì)算量有所增加，但材質(zhì)圖像的壓縮是離線預(yù)處理的，不會(huì)影響解壓的實(shí)時(shí)性，并且修正后的行程編碼壓縮算法的解壓處理過程與經(jīng)典的行程編碼基本一致。

為減輕雷達(dá)圖像仿真時(shí)CPU的運(yùn)算負(fù)載，減少CPU與GPU間的數(shù)據(jù)傳輸量，編碼壓縮后的材質(zhì)圖像碼流數(shù)據(jù)直接加載到顯存后在GPU上進(jìn)行解壓縮處理。從對(duì)材質(zhì)圖像的壓縮過程可知，每塊地形材質(zhì)圖像的解壓縮不涉及其它材質(zhì)圖像的內(nèi)容，每塊壓縮后材質(zhì)圖像的解壓過程一致，可以有效地利用GPU的并行處理方式提高解壓算法效率。

雷達(dá)圖像實(shí)時(shí)仿真時(shí)，在GPU中使用幾何著色器（Geometry Shader，GS）并配合流式輸出（Stream Output）功能實(shí)現(xiàn)材質(zhì)數(shù)據(jù)的實(shí)時(shí)解壓，其他著色器不做特殊處理。在光柵化階段被屏蔽，輸入輸出的數(shù)據(jù)均以紋理的形式存儲(chǔ)在顯存中，使用單通道的紋理格式保存解壓后的材質(zhì)信息，解壓輸出的材質(zhì)數(shù)據(jù)作為第2個(gè)渲染過程（Pass）的輸入。在雷達(dá)圖像實(shí)時(shí)渲染中，程序通過渲染“NULL”圖元激活GPU解壓程序，GS上解壓的流程如圖4所示。

圖4　GS上解壓的流程Fig.4 Decompression flow on GS

GPU程序根據(jù)輸入的已壓縮的材質(zhì)數(shù)據(jù)流，首先通過前4個(gè)字節(jié)獲取材質(zhì)圖像的行列大小，并據(jù)此構(gòu)建相應(yīng)大小的單通道材質(zhì)紋理緩存；其次，通過最大行程長度編碼位確定每個(gè)偶對(duì)中T的大小，并據(jù)此逐個(gè)讀取偶對(duì)數(shù)據(jù)的長度li；再次，根據(jù)B位的數(shù)值判斷應(yīng)讀取的gi二進(jìn)制位長度，并統(tǒng)一轉(zhuǎn)換為8位的二進(jìn)制數(shù)的材質(zhì)信息；最后將材質(zhì)數(shù)據(jù)填充到單通道材質(zhì)紋理相應(yīng)的位置中，根據(jù)結(jié)束標(biāo)識(shí)“0000”完成當(dāng)前輸入材質(zhì)流的數(shù)據(jù)解壓縮。

3　實(shí)驗(yàn)驗(yàn)證

對(duì)圖5中2幅材質(zhì)圖像采用經(jīng)典行程編碼和本文編碼（不同最大行程長度和最優(yōu)最大行程長度，且修正偶對(duì)）進(jìn)行壓縮試驗(yàn)，得到的壓縮比如表1所示。

圖5　待壓縮材質(zhì)圖像Fig.5 Material images for compression

表1　不同壓縮方法獲得的壓縮比Tab.1 Compression ratio with different encoding mode

從表1中統(tǒng)計(jì)的數(shù)據(jù)可以看到，與經(jīng)典方式相比，采用本文提出的編碼方式壓縮比有顯著提升。

4　結(jié)束語

針對(duì)雷達(dá)圖像仿真中使用的地面材質(zhì)數(shù)據(jù)采用灰度圖像進(jìn)行存儲(chǔ)數(shù)據(jù)量大、地形分塊特性及大塊范圍內(nèi)的材質(zhì)屬性相同特點(diǎn)，提出了面向GPU的基于自適應(yīng)最大行程長度編碼方法，采用單純形法進(jìn)行最優(yōu)最大行程長度的搜索。對(duì)RLE的經(jīng)典偶對(duì)進(jìn)行了修正，以進(jìn)一步減少壓縮后的數(shù)據(jù)量。該方法與已有方法相比顯著提高了數(shù)據(jù)壓縮比，且得到壓縮數(shù)據(jù)適用于GPU進(jìn)行快速解壓。同時(shí)，也給出了GPU解壓縮的方法。

［1］PAJAROLA R，GOBBETTI E.Survey on semi-regular multiresolution models for interactive terrain rendering［J］.Visual Computer，2007，23（8）：583-605.

［2］孟大地，胡玉新，丁赤飚.一種基于GPU的SAR高效成像處理算法［J］.雷達(dá)學(xué)報(bào)，2013，2（2）：210-217. MENG DADI，HU YUXIN，DING CHIBIAO.Efficient algorithm for processing SAR data based on GPU［J］. Journal of Radars，2013，2（2）：210-217.（in Chinese）

［3］王金波，察豪，劉峰.一種利用CUDA技術(shù)實(shí)現(xiàn)雷達(dá)余輝效果的方法［J］.海軍工程大學(xué)學(xué)報(bào)，2013，24（3）：103-106. WANG JINBO，CHA HAO，LIU FENG.A method of achieving radar afterglow by using CUDA［J］.Journal of Naval University of Engineering，2013，24（3）：103-106.（in Chinese）

［4］禹蒲陽.基于DCT和RLE的灰度圖像壓縮方法［J］.湖南科技大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，25（2）：89-93. YU PUYANG.Research on encoding compressing of gray images based on discrete cosine transform and run length encoded［J］.Journal of Hunan University of Science&Technology：Natural Science Edition，2010，25（2）：89-93.（in Chinese）

［5］蔣正金，張長江，端木春江.采用離散小波變換和游程長度編碼的圖像壓縮與恢復(fù)［J］.浙江師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，35（2）：155-160. JIANG ZHENGJIN，ZHANG CHANGJIANG，DUANMU CHUNJIANG.Using discrete wavelet transform and run length encoding to realize image compression and recovery［J］.Journal of Zhejiang Normal University：Natural Sciences，2012，35（2）：155-160.

［6］謝耀華，湯曉安，孫茂印，等.基于分類重排LZW的圖像無損壓縮算法［J］.中國圖象圖形學(xué)報(bào)，2010，15（2）：236-241. XIE YAOHUA，TANG XIAOAN，SUN MAOYIN，et al. A Lossless image compression algorithm based on classification，reordering and LZW［J］.Journal of Image and Graphics，2010，15（2）：236-241.（in Chinese）

［7］鄭運(yùn)平，陳傳波.一種新的灰度圖像表示算法研究［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33（12）：2397-2406. ZHENG YUNPING，CHEN CHUANBO.Study on a new algorithm for gray image representation［J］.Chinese Journal of Computers，2010，33（12）：2397-2406.（in Chinese）

［8］GONZALEZ RAFAEL，WOODS RICHARD.數(shù)字圖像處理［M］.3版.阮秋琦，阮宇智，譯.北京：電子工業(yè)出版社，2011：289-292，334-353. GONZALEZ RAFAEL，WOODS RICHARD.Digital image processing［M］.3rded.RUAN QIUQI，RUAN YUZHI，Translated.Beijing：Publishing House of Electronics Industry，2011：289-292，334-353.（in Chinese）

［9］劉海波，沈晶，郭聳.Visual C++數(shù)字圖像處理技術(shù)詳解［M］.北京：機(jī)械工業(yè)出版社，2010：357-390. LIU HAIBO，SHEN JING，GUO SONG.Visual C++digital image processing technologies［M］.Beijing：China Machine Press，2010：357-390.（in Chinese）

［10］王新年，張濤.數(shù)字圖像壓縮技術(shù)實(shí)用教程［M］.北京：機(jī)械工業(yè)出版社，2009：45-49. WANG XINNIAN，ZHANG TAO.Practical digital image compression technologies［M］.Beijing：China Machine Press，2009：45-49.（in Chinese）

［11］王曉明.自適應(yīng)最大行程長度編碼壓縮算法研究［J］.遼寧工業(yè)大學(xué)學(xué)報(bào)，2008，28（1）：31-33. WANG XIAOMING.Study of max running length RLE to be adjusted by itself［J］.Journal of Liaoning University of Technology，2008，28（1）：31-33.（in Chinese）

［12］王曉明.Visual Basic操作圖像無損編碼壓縮的技術(shù)方案［J］.渤海大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，30（1）：86-88. WANG XIAOMING.Technical methods for lossless image compression by Visual Basic［J］.Journal of Bohai University：Natural Science Edition，2009，30（1）：86-88.（in Chinese）Ground Material Data Compression Method for GPU Rapid Processing

LU Weiwei1，XU Tao2，XU Kewen1
（1.No.7 Department，NAAU，Yantai Shandong 264001，China；2.The 91206thUnit of PLA，Qingdao Shandong 266108，China）

To solve the problems of saving and loading of mass ground materiel data in radar imaging simulation，an adap?tive max run length coding and modified pairing based algorithm is proposed for data compression.It reduces the amount of data in storage，and eliminates bottleneck of data flow.The compression algorithm is designed for GPU rapid processing，so the compressed data can be decompressed in GPU effectively.

radar image simulation；material data compression；GPU acceleration；adaptive max run length coding

TP301.6

A

1673-1522（2015）05-0543-04DOI：10.7682/j.issn.1673-1522.2015.05.009

2015-05-12；

2015-07-25

陸巍?。?983-），男，碩士生。