一种优化的灰度图像压缩算法

王炳月，贾连印，范 瑶，孙劭文

（昆明理工大学 信息工程与自动化学院，云南 昆明 650500）

0 引 言

图像是重要的信息载体[1]，信息图像的巨大数据量会引发存储空间大和传输速率慢等诸多问题。光电图像处理是图像处理中的一个重要分支，主要包括光电成像技术和数字图像处理技术。随着激光技术、光电子技术及光子学的发展和逐步完善，光电成像技术的优势愈发明显，例如生物医学图像、卫星成像等，但光电图像数据之间有较大的相关性，造成大量时间和空间冗余，不利于存储和传输。图像压缩是数据压缩技术在数字图像上的应用，是图像存储和高效传输的基础。对光电图像压缩，可以有效减少图像数据中的冗余信息，从而更高效地存储和传输数据[2]。

从信息损失的角度来分，图像压缩可分为无损压缩和有损压缩两类[3]。根据图像压缩技术的不同，图像压缩又可分为基于分区[4]的、基于哈夫曼编码[5]的、基于LZW （Lempel-Ziv-Welch）编码[7]的、基于游程编码[9]的以及基于算术编码[10]的图像压缩方式。基于分区的图像压缩是利用相邻像素值相近的思想，将原始图像分割为多个像素值接近的小分区，并用小分区的像素均值来代替原始小分区的压缩方式。哈夫曼编码[5]是一种经典编码方式，依据字符出现频率来构造平均长度最短的码字。RAJIV[6]利用Hufman 编码作为熵并基于小波变换对图像进行压缩，取得了较好的压缩效果。LZW 编码通过构建编译表，实现字符重用及编码，在图像压缩中也得到了广泛应用，如BADSHAH[7]的基于LZW编码的水印压缩技术，谢等人[8]采用Hilbert 扫描将像素进行重排并基于LZW 编码对图像进行压缩等。游程编码是统计编码的一种，利用符号串代替相同连续符号实现数据压缩，例如基于正六边形栅格的游程编码压缩技术[9]等。算术编码是将整个输入编码为一个数的熵的编码方式，如KUMAR等人[10]提出的基于多项式分布和算术编码的压缩方法。

图像压缩[2]的一个重要任务是最大化像素之间的相关性，使得复原的图像在保持质量的同时，尽可能提高压缩率和压缩效率。传统的图像压缩算法多采用栅格扫描的策略，逐行扫描图像然后进行压缩。然而，栅格扫描的图像并不能最大程度地使相邻的位置（往往具有相似的像素值）划分到同一个分段，因此对扫描后的图像压缩时将导致大量小分段的产生。

HILBERT 曲线[11]作为Peano 填充曲线的一个重要分支，因具有较好的内聚性，可更好地把相邻的位置划分到同一分段。相对栅格扫描，它可使得更多像素值接近的位置点压缩为一个分区，进而可降低分区数量，提高压缩效率，所以Hilbert 曲线在图像分析、图像压缩、图像加密以及图像存储与检索等领域得到了广泛应用[8，12]。

KAMATA 提出的Hilbert 扫描灰度图像压缩算法[4]是基于Hilbert曲线对图像进行压缩的经典代表。其在基于Hilbert 扫描的一维数组上进行压缩，比在基于栅格扫描的数组上有更高的压缩率，实验结果表明，该算法有着相较JPEG更好的压缩效果。然而，其采用早期的Hilbert 解码算法，解码时间占压缩总时间的约50%，压缩效率较低。此外，其采用分区后合并（MAP）的策略将小分区进行合并，导致较高的时间和空间开销。

为解决上述问题，本文在对现有Hilbert 解码算 法（ 如Moore-HD、Burkardt-HD[13]、Li-HD[14]、Unistate-HD、FZF-HD[16]）进行深入研究对比的基础上，引入高效的FZF-HD Hilbert 解码算法（FZF）及分区中合并（MIP）的图像压缩算法FZF-MIP。通过FZF-HD 算法，可避免对输入编码值前部为0的阶迭代解码，可大幅降低图像压缩时间。此外，通过设计高效的MIP 策略，将分区和合并的步骤融合，从而避免分区后合并的开销，进一步提高了图像压缩的效率。扩展实验结果表明了FZF-MIP 算法的有效性。

1 基本定义和前提

1.1 Hilbert 曲线

1阶Hilbert曲线将整个空间分割成4个子区域，将左下、左上、右上、右下这4 个子区域依次连接起来，即可构成开口向下的1 阶Hilbert 曲线。通过在1 阶曲线的每个网格嵌入一个1 阶曲线，并进行相应的旋转和翻转，即可得到2 阶Hilbert 曲线。重复这个过程，即可得到n阶Hilbert 曲线。不同分辨率对应Hilbert 曲线如图1 所示。

图1 Hilbert 不同分辨率对照图

1.2 Kamata 算法

KAMATA 提出基于Hilbert 扫描的灰度图像压缩算法[4]，首先基于Hilbert 扫描，将图像映射为一维数组，然后基于线性插值中的零阶插值对数据进行递归分割。最终将图像压缩为一个像素数组A和长度数组L。其算法框架如图2 所示，算法执行流程如下。

图2 Kamata 算法框架图

（1）基于Hilbert 解码算法扫描图像，将初始图像扫描为一个数组D。通过Hilbert 扫描可使空间上相邻的点，在曲线上编码值尽可能地接近。

（2）将数组D分割成具有长度为M的多个初始分区P。

（3）对每个初始分区P按照方差和最小的原则依次划分为2 个分区，即找到一个分割点C，将P划分为P1 和P2 两个分区，使得划分后的两个分区的方差EP1和EP2之和最小，如公式（1）所示。若划分后的分区P1 的长度小于分区长度阈值Lmax且方差小于分区方差阈值Emax，则P1即为一个结果分区。将该分区的像素均值AP1（长度为8 位）和长度LP1（长度为log2(Lmax)位）分别存入位数组A和L，否则，递归对该分区继续划分，直至所有分区的长度小于Lmax且方差小于Emax为止。对P2 也执行同样的操作。

（4）步骤（3）可将原始图像压缩为两个位数组A和L，从而降低图像的存储空间。然而，划分后的分区可能包含大量小分区，为此，该算法引入分区合并步骤。对于待合并的两个相邻分区P1 和P2，如果两个分区满足式（2）、式（3）和式（4），则将P1和P2 进一步合并为一个分区。

式中：L2max表示待合并的小分区的长度阈值，Gmax表示P1 和P2 的像素均值之差。

（5）最终合并小分区后的位数组A和L即为图像压缩后的结果。

2 FZF-MIP 压缩算法设计

2.1 问题分析

尽管有较好的压缩效果，但Kamata 算法仍存在如下2 个问题，影响其压缩效率。

（1）采用传统的Hilbert 解码算法，解码效率低。原文实验结果表明，Hilbert 扫描时间占整个压缩过程的近50%。因此，若能提高Hilbert 扫描效率，必将大幅提高算法的压缩效率。

（2）该算法采用分区后合并（MAP）的方式来合并小分段。直观来看，合并有2 个主要思路：一是直接在位数组A和L中合并，然而这需要大量元素的移动和删除的开销，时间和空间开销大；二是创建2 个新的位数组A´和L´，线性扫描位数组A和L，并将合并后的分区插入A´和L´。这同样需要较大的时间和空间开销。

针对上述问题，本文设计高效的FZF-MIP 压缩算法，引入一种高效Hilbert 解码算法FZF-HD，此外设计高效的分区中合并（MIP）策略，从而大幅提高图像压缩效率。

2.2 高效Hilbert 解码算法

针对Kamata 算法中Hilbert 扫描时间占比大问题，本文引入免计前零阶的高效Hilbert 解码算法FZF-HD[15]。FZF-HD 依托2 个简单、高效的状态视图InvKey和InvType实现。其中，InvKey表示某阶编码值到该阶坐标值的映射，InvType表示某阶状态到下一阶状态的映射，分别如表1 和2 所示。此外，FZF-HD 可检测并跳过输入编码值前部全0 的阶，从而提高编码效率。算法的基本步骤如下：

表1 状态视图InvKey

（1）利用msb算法[16]检测输入编码值前部全为0 的阶的数量q；

（2）从q+1 阶迭代查询状态视图进行编码。

表2 状态视图InvType

最终，FZF-HD 算法（代码截图）如图3 所示。

图3 FZF-HD 算法代码截图

2.3 分区中合并策略MIP

针对Kamata 算法MAP 策略导致大量需合并的小分段的不足，本文设计高效的分区中合并（MIP）的策略来避免这一不足。MIP 的核心思想如下。

（1）设cur为第一个满足分区长度阈值Lmax和分区方差阈值Emax的小分区P1。

（2）对第i个（i≥2）待插入位数组A和L中的小分区Pi，根据式（2）、式（3）和式（4）判断其是否可以与cur合并，如可以合并，则延迟Pi的插入，将其与cur合并后继续执行步骤（2），合并后的新分区cur=的像素均值和长度为计算式为式（5）和式（6）：

（3）如Pi不能和cur合并，则将cur插入到位数组A和L后，令cur=Pi，继续执行步骤（2）。

示例1：假设L2max=10，Gmax=10，Lmax=64，给定依次划分出的小分区P1=<167,6>，P2=<160,8>，P3=<175,6>，P4=<167,27>。

初始时cur=P1，对于分区P2，因其满足LP2≤L2max，|AP1-AP2|=7 ≤Gmax，LP1+LP2=6+8=14 ≤Lmax，故 将P2 并 入 到cur后 如 图4 的 过 程①，得cur=<163,14>。当i=3 时，LP3≤L2max，|A´cur-AP3|=|175-163|=12>Gmax且L´cur+LP3=14+6=20 ≤Lmax因P3 不满足式（3），如图4 中的过程②，故此时将cur插入到位数组得A=(163)2=10 100 011 和L=(14)2=001 110。令cur=P3 后，继续从i=4 重复执行该过程。

图4 MIP 示意图

由上可见，与MAP 不同的是，MIP 采用延迟插入的策略将分区过程和合并过程融为一体，从而减少后续合并的开销，无需额外的存储空间，因此可有效提高图像压缩效率。基于上述介绍，实现的FZF-MIP 算法（代码截图）如图5 所示。

图5 FZF-MIP 算法

算法中，ComputeHOrder 对给定图像的大小，计算其对应的Hilbert 阶数，如对XSIZE=512，YSIZE=512 的图像，其对应的Hilbert 空间的阶数为9。

2.4 解压算法设计

解压过程为压缩过程的逆过程，即将压缩后的图像复原。本文中，分别从位数组L读取log2(Lmax)位分区p的长度信息LP，从A中读取分段p的8位灰度信息AP，通过Hilbert 解码获得物理坐标，将相应坐标对应的像素值设置为AP。循环上述过程，直到处理完数组L和A内的所有分段，完成图像解压。

3 实验结果分析

3.1 实验环境及数据集

实验环境：CPU 为Intel（R）Core（TM）i7-7500U CPU @2.7 GHz，内存为8 GB，操作系统为Windows 10，编译环境为Microsoft Visual Studio 2015且禁用了优化（/Od）。

为详细考察压缩算法的性能，采用以下数据集。

（1）为验证Hilbert 扫描算法FZF-HD 的效率，分别将k=4，8，12，16 阶Hilbert 空间内的所有点作为点数据集，每个空间共包含2k×2k个k阶数据点。

（2）为验证MIP 策略对压缩和解压效率的影响，采用Granada 大学计算机视觉组提供的灰度图像数据集GrayImages 进行压缩和解压。该数据集包含49 张大小为512×512 的灰度图像，每张图像对应Hilbert 阶数为9 阶。

实验中，初始参数设置为：Lmax=64，Emax=2 000，L2max=10，Gmax=10，初始分区长度P=256。

3.2 实验结果

3.2.1 Hilbert 扫描时间对比

为验证Hilbert 扫描算法FZF-HD 的效率，在点数据集上，将FZF-HD 与Moore、Burkardt[13]、Li[14]、Unistate 算法对比。为方便描述，为各解码算法标注后缀“-HD”。实验结果如图6 所示，图6 中y轴坐标为对数坐标。

由图6 可知，在解码2k×2k个数据点时，随着阶数k的增加，所有算法的解码时间均随阶数的增加而指数增加。相对而言，当k为16 时，FZF-HD算法解码效率在Li 的算法基础上提高了11.3%，相对于Burkardt 算法，FZF 算法解码效率提高2.5 倍。由此可见，FZF-HD 算法具有较高的解码效率，且随着阶数的增加，解码优势不断增加。

图6 Hilbert 解码效率对照图

基于不同的解码算法，本文对GrayImages 中的图像进行压缩和解压（其中压缩时采用MAP 的策略），并对比不同Hilbert 扫描时间及其占总的压缩和解码时间的比例，结果分别如图7 和图8 所示。

图7 Hilbert 扫描占压缩比重对照图

图8 Hilbert 扫描占解压比重对照图

由图7、图8 可知，相对Burkardt-HD 算法，基于FZF-HD 算法压缩时间和解压缩时间可以分别减少33.5%和39%。Burkardt 算法和Moore 算法分别占其总压缩时间的40%和解压时间的50%以上，而对于FZF-HD，该值仅分别为21.1%和27.1%。因此，高效Hilbert 解码算法可以显著提高压缩和解压缩效率。

3.2.2 算法压缩性能

为验证小分区合并的必要性，对GrayImages 中所有图像进行压缩，统计平均每张图片合并和未合并的信息对比，如表3 所示。

表3 合并和未合并小分区信息对比

由表3 可知，将小分段合并，能节约大量存储空间，合并后的压缩率由0.210 319%降低至0.175 818%，空间开销降低16.4%。

值得注意的是，本文的优化算法并不会改变原有Kamata 算法的压缩效果。以蝴蝶图片为例，压缩及解压后的图像对比如图9（a）和图9（b）所示。可见，压缩过程中，图像基本保持原貌，损失的部分对理解原始图像的影响很小，却换来了较大的压缩比。

图9 压缩前后对照图

3.2.3 不同分区合并策略的对比

为进一步考察不同分区合并策略的时间开销，在采用FZF-HD 进行Hilbert 扫描的基础上，将FZF-MAP（FZF-HD 和MAP 结合）和FZF-MIP 进行对比，其时间开销如图10 所示。

图10 不同合并策略下效率对照图

由图10 可知，在引入分区中合并策略MIP 后，相对MAP 策略，压缩49 张图片的时间由7.092 s 降低到6.733 s，效率提高5.1%，表明分区中合并策略可避免合并时数组内的大量元素移动，从而提高图像的压缩效率。

总体而言，相对原Kamata 算法，FZF-MIP 压缩GrayImages 数据集用时6.733 s，相对Kamata 的FZF-MAP，综合压缩效率提升近37.8%。

4 结 语

针对Kamata 图像压缩算法中Hilbert 扫描过程在压缩中占的比重较大，分区后合并策略导致压缩过程空间开销大、复杂度较高的不足，本文引入高效的Hilbert 解码算法FZF-HD 和分区中合并策略MIP 对其进行优化，从而有效提升了压缩效率。下一步拟对高维图像压缩领域进一步深入研究。