面向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-），男，硕士生。