面向GPU快速處理的地面材質數據壓縮方法

陸巍巍，徐　濤，徐珂文

（1.海軍航空工程學院7系，山東煙臺264001；2.91206部隊，山東青島266108）

面向GPU快速處理的地面材質數據壓縮方法

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

（1.海軍航空工程學院7系，山東煙臺264001；2.91206部隊，山東青島266108）

為解決雷達圖像仿真中海量地面材質數據的存儲和加載問題，采用基于自適應最大行程長度編碼和修正偶對的壓縮算法進行材質數據的壓縮，從而有效地減少了數據的存儲量，消除數據傳輸的瓶頸，提高了數據傳輸的吞吐能力。壓縮算法面向GPU快速處理，得到壓縮數據適用于GPU進行快速解壓。

雷達圖像仿真；材質數據壓縮；GPU；自適應最大行程長度編碼

機載雷達圖像仿真需要大規模地面材質數據的支持。盡管計算機存儲和運算速度已經有了長足的發展和進步，但仍受限于圖形硬件的顯存容量，事實上依然沒有足夠的空間來滿足不斷增加的高分辨率地形數據的存儲需求，不可能一次加載整個仿真區域范圍內的材質數據［1］。

由于在并行運算方面的突出優勢，GPU在實時雷達圖像仿真中得到廣泛應用［2-3］。雷達圖像仿真中，仿真圖像最終均需要通過圖形硬件處理核心GPU來完成可視化繪制和渲染。在仿真過程中，材質數據從外存被調取到最后的渲染輸出，需要經過外存、內存到顯存的傳輸過程。雖然可采用固態硬盤等方法提高外存的數據讀取速度，但硬盤的存取速度仍是制約數據從外到內的主要因素。因此，數據讀取和操作占據了GPU繪制時間的重要部分，而數據傳輸的帶寬則是影響繪制速度的關鍵。為減少材質數據量的大小，消除數據傳輸的瓶頸，提高數據傳輸的吞吐能力，有必要對材質數據進行預先壓縮處理，直接將壓縮數據傳輸到顯存中，并采用基于GPU快速解壓的方法，完成視景或者雷達圖像仿真實時繪制過程中的數據提取。

為應對雷達圖像仿真中大規模地面材質數據的調度對GPU的存儲和運算能力帶來的挑戰，本文研究了一種面向GPU快速解壓的地面材質數據壓縮方法，并對方法的性能進行了實驗驗證。

1　地面材質數據壓縮

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

地面材質圖像由許多材質相同的圖像區域組成，如圖1所示。

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

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

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

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

如果灰度級的行程較大，則式（1）可認為是對原像素行的一種壓縮表示。可見，對地面材質數據來說，大塊區域范圍內灰度值相同的情況越多，壓縮效果越顯著。

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

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

設材質圖像行列數目為M×N，每行灰度值為g的片段連續出現的長度為li（1≤li≤N），掃描材質圖像的每一行，統計出各行連續出現相同長度li的次數Ci，同時也可統計出總共有K種長度，即1≤i≤K。則求解最優的最大行程長度L的問題可以轉化為求函數的極小值問題。

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

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

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

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

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

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

2　GPU解壓處理

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

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

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

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

GPU程序根據輸入的已壓縮的材質數據流，首先通過前4個字節獲取材質圖像的行列大小，并據此構建相應大小的單通道材質紋理緩存；其次，通過最大行程長度編碼位確定每個偶對中T的大小，并據此逐個讀取偶對數據的長度li；再次，根據B位的數值判斷應讀取的gi二進制位長度，并統一轉換為8位的二進制數的材質信息；最后將材質數據填充到單通道材質紋理相應的位置中，根據結束標識“0000”完成當前輸入材質流的數據解壓縮。

3　實驗驗證

對圖5中2幅材質圖像采用經典行程編碼和本文編碼（不同最大行程長度和最優最大行程長度，且修正偶對）進行壓縮試驗，得到的壓縮比如表1所示。

圖5　待壓縮材質圖像Fig.5 Material images for compression

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

從表1中統計的數據可以看到，與經典方式相比，采用本文提出的編碼方式壓縮比有顯著提升。

4　結束語

針對雷達圖像仿真中使用的地面材質數據采用灰度圖像進行存儲數據量大、地形分塊特性及大塊范圍內的材質屬性相同特點，提出了面向GPU的基于自適應最大行程長度編碼方法，采用單純形法進行最優最大行程長度的搜索。對RLE的經典偶對進行了修正，以進一步減少壓縮后的數據量。該方法與已有方法相比顯著提高了數據壓縮比，且得到壓縮數據適用于GPU進行快速解壓。同時，也給出了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］.雷達學報，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技術實現雷達余輝效果的方法［J］.海軍工程大學學報，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］.湖南科技大學學報：自然科學版，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］蔣正金，張長江，端木春江.采用離散小波變換和游程長度編碼的圖像壓縮與恢復［J］.浙江師范大學學報：自然科學版，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］.中國圖象圖形學報，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］鄭運平，陳傳波.一種新的灰度圖像表示算法研究［J］.計算機學報，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.數字圖像處理［M］.3版.阮秋琦，阮宇智，譯.北京：電子工業出版社，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++數字圖像處理技術詳解［M］.北京：機械工業出版社，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］王新年，張濤.數字圖像壓縮技術實用教程［M］.北京：機械工業出版社，2009：45-49. WANG XINNIAN，ZHANG TAO.Practical digital image compression technologies［M］.Beijing：China Machine Press，2009：45-49.（in Chinese）

［11］王曉明.自適應最大行程長度編碼壓縮算法研究［J］.遼寧工業大學學報，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操作圖像無損編碼壓縮的技術方案［J］.渤海大學學報：自然科學版，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

陸巍巍（1983-），男，碩士生。