一种改进的串匹配参数编码算法及在Alpha图像中的应用

潘承宝 赵利平 李星霞 任浩东 伍振虎 廖 滔

(绍兴文理学院 计算机科学与技术系,浙江 绍兴 312000)

0 引言

随着互联网的飞速发展及其相关衍生产业的进步，催生出了种类繁多的互联网应用技术及产品，而这其中的图像或视频是互联网带宽的主要消耗者.Alpha图像也称透明度图像或α通道图像,因其具有可变的透明特性以及能够创作出十分丰富、逼真的图像效果,而在多媒体、电影、电视、动画等领域的应用日益广泛，如何对Alpha图像进行高效编码已成为当前各界研究的热点.

在2018年4月召开的JVET(Joint Video Experts Team)会议上，正式启动了下一代国际视频编码标准VVC(Versatile Video Coding)的制定工作[1]，其工作重点就包括Alpha图像的编码.2017年3月，我国的数字视音频编解码技术标准化工作组在其文件中，也指出了Alpha图像的编码需求[2].目前Alpha图像的编码工作主要包括：(1)随着视频编码标准的制定而开展的一些相关研究工作，从基于H.264标准的二值Alpha图像编码算法[3]，到基于HEVC标准的无损二值Alpha图像编码算法[4]和AVS2标准[5]的TPG图像格式[6]；(2)各种图片压缩格式的编码，如PNG[7]格式也支持Alpha图像的编码.

传统Alpha图像编码算法或各种图片压缩算法[3，8-9]既没有考虑Alpha图像的特性，也无法达到在当前主流移动设备上对Alpha图像进行超低复杂度编解码的需求.在这样的背景下，本文根据Alpha图像固有的物理特性和串匹配算法编码参数的统计特性，以LZ4HC算法[10]开源代码作为具体实现的基础，提出了一种改进的串匹配参数的Alpha图像编码算法，使其具有超低复杂度和高效的优势.

1 LZ4HC算法简介

LZ4HC算法主要由两部分组成：串搜索和串匹配参数编码[10].

串搜索：LZ4HC算法通过哈希值散列表(将相同的哈希值进行连接)，使其可以快速找到参考串的起始点.

串匹配参数编码：如图1所示，LZ4HC算法串匹配参数包括四部分——未匹配串长度(uml)、未匹配串数值(umn)、匹配串长度(ml)和匹配串偏移量(offset).

图2给出了LZ4HC算法编码示例.对于一维串：{177,143,116,177,143,116,177,143,116,178,143,116,177,143,116,177}，首先编码第一个字节177，由于此时hash表为空，因此找不到任何匹配，第一个字节177为未匹配像素；同理，第二和第三个字节仍然为未匹配像素；然后编码第四个字节，此时在偏移量为3的位置上可找到一个长度为6的串匹配，因此获得第一个编码串的信息：{uml:3；umn:177,143,116；ml:6；offset:3}.依次类推，可以得到第二个串的编码信息.因此，LZ4HC编码算法的本质是首先将输入的编码数据分解成N个编码串；其次，是对编码参数进行图2所示的编码.

LZ4HC算法采用定长字节的方式编码(比如offset统一用2个字节的长度来编码)，由于没有采用任何熵编码，所以能节省大量的编解码时间.但是其缺点也显而易见：(1)无法对某些较小的参数进行有效编码，比如在offset为1的情况下，采用2字节的编码方式将造成很大浪费；(2)参数编码方案没有考虑将出现频率高的编码参数映射成较短的码值；(3)没有考虑对offset和ml进行联合优化编码.

2 改进的LZ4HC编码算法

2.1 改进的LZ4HC算法语法格式

图3给出了改进的LZ4HC算法(以下简称ELZ4HC算法)示意图.新增的语法元素为T1，取值为0和1，具体为以下两类：

2.1.1 当T1为0时(第一类)

标识字节(编码首字节)包括T1、匹配串长度和偏移量3个参数，其首个比特(bit)表示T1，之后的4bit表示匹配串长度，剩余3bit用来表示偏移量.对于出现频率较高的匹配串偏移量，映射成可用3bit表示的数值较小的偏移量(偏移量编码参数分段映射方案，具体见2.2节)；对出现频率较高且数值较大的偏移量进行优先编码，不用新开辟两字节去储存部分较大偏移量，从而避免字节浪费(节省0～2字节).

图1 LZ4HC算法中的串匹配参数及其码流格式

图2 LZ4HC算法编码示意图

2.1.2 当T1为1时(第二类)

类似第一类，标识字节包括T1、未匹配串长度和匹配串长度3个参数，其首个bit表示T1，之后的2bit表示未匹配串长度，剩余5bit用来表示匹配串长度.根据Alpha图像的特点，未匹配串长度出现0的频率较高，Alpha图像存在大量同值区域从而导致匹配串长度较大.对标识字节进行不等划分，采用较少的字节储存未匹配串长度，较多的字节储存匹配串长度，对于避免字节浪费十分有利(部分节省1字节).

2.2 邻近偏移量优先编码及偏移量参数分段映射方案

根据Alpha图像的固有规律可知，偏移量出现1、W(图像宽度)、W-1和W-2的概率相对比较高，因此提出了对邻近位置偏移量概率较高的数值进行优先编码，以及对偏移量数值进行参数映射的方案(如图4).将偏移量为W-2、W-1、W、0-3的数据映射为0、1、2、3-6并存储于标识字节中，其他偏移量数值的情况则是将本标识字节内表示偏移量的3bit置为111，并使用后续2字节储存偏移量.

2.3 匹配串长度分段编码方案

设MarkML为标识字节中表示匹配串长度的数值，以MarkMLMax表示标识字节储存匹配串长度的最大值.根据匹配串长度特性，提出了如下匹配串长度分段编码方案：

(1)当Ml<(MarkMLMax-1)时，MarkML用5(或者4)bit表示；

(2)当(MarkMLMax-1)<=ml<=(MarkMLMax+255)时，MarkML用5(或者4)bit表示(置为11110或1110)，用1个字节表示ml-30(或14)部分；

(3)当(MarkMLMax+255)

(4)当ml>=(MarkMLMax+65535)时，MarkML用5(或4)bit表示(置为11111或1111)，后续匹配串长度2个字节全置为1，ml-655665-31(或15)的部分同LZ4HC编码方案.

例如，图3中第一类MarkMLMax为15，第二类为31.

图3 改进的LZ4HC算法的语法格式及其与LZ4HC算法编码字节数目比较

图4 偏移量参数分段映射方案

3 实验结果与分析

本文的236个Alpha测试数据来源于：(1)从腾讯公司网站提供的PNG图片中提取出来的47个Alpha数据；(2)从千度网上下载的PNG图片中提取出来的178个Alpha数据；(3)从PNG网站上下载的PNG图片中提取出来的11个Alpha数据.

图5给出了4组典型的Alpha图像.

图5 典型的Alpha图像

为了便于说明本文算法的特性，将本文提出的算法与以下4种算法进行比较实验：(1)LZ4HC算法[10]；(2)zlib算法[11]；(3)PNG算法[7]；(4)x265算法[12].

实验环境配置为Intel(R)Core(TM)i7-7500U CPU@2.70GHz(4核处理器)、4GB内存、1TB硬盘以及Win7_64位旗舰版操作系统.实验结果从编码效率(评价指标包括压缩码流总字节数的比值、单个序列的压缩比和236个序列的平均压缩比)和复杂度(评价指标包括国际标准制定工作中通用的编解码运行时间的比值和编码+解码运行时间比值)来衡量算法的性能.采用微秒计时器进行计时.

表1给出了5种算法的参数配置.level表示在哈希链上搜索的次数为2level-1.一般而言，level越大，编码时间越长，编码效率越好.preset是x265的配置参数.表2给出了ELZ4HC(level 4)与其他算法(zlib、PNG和x265)的实验比较结果.表3给出了ELZ4HC和LZ4HC(level 1～level 4)算法实验参数的比较结果，所有序列对应每个level的压缩码流总字节数比值、编码时间比值、编解码时间比值和4个level的平均值.表4给出了在4组典型分辨率下各算法压缩比(原文件大小与压缩后文件大小比值).

表1 编码算法配置

编码算法 配置参数 LZ4HClevel 1～level 4 ELZ4HClevel 1～level 4 zlibfast(level 1) PNGfast(level 1) x265fast(preset 0)

表2 ELZ4HC(level 4)与其他算法(zlib、PNG和x265) 实验比较结果 (%)

表3 ELZ4HC和LZ4HC(level 1 ～level 4)算法实验各参数的比较结果 (%)

ELZ4HC/LZ4HClevel 1level 2level 3level 4 平均压 缩 比84.81 86.78 88.38 89.63 87.40 编码时间比88.24 87.13 74.47 61.01 77.71 解码时间比108.27 110.70 111.26 112.96 110.80 编解码时间比91.82 91.12 79.66 66.80 82.35

表4 针对图5中的4组典型数据各种算法的压缩比

像 素 ELZ4HC LZ4HC Zlib Png X2653000×30003261431201181181708×17083151971411242371900×220248424138276392×61927660575467

综上，可以得出以下结论：

(1)由表2可知，ELZ4HC算法(level 4)与zlib、png、x256算法相比(均采用时间最快的fast比较)，压缩效率相差不大，但是总编解码时间分别仅为3种算法的21.92%、16.41%和1.70%，速度提升了几倍到几十倍.可见ELZ4HC算法在保证压缩效率前提下,编解码时间具有很大的优势.

(2)由表3可知，在236组实验数据中，ELZ4HC算法对比LZ4HC算法，在编码效率提升12.60%的情况下，编码、解码总时间降低了17.65%.可见ELZ4HC算法明显具备高效率编码和超低复杂度的优势.在ELZ4HC算法中，虽然解码时间增加，但是编码时间减少量远大于解码时间增加量，所以ELZ4HC算法使得编解码总时间减少很多.对于图5中4组典型Alpha数据，表4给出各种算法的压缩比，充分显示出ELZ4HC算法的压缩效率比LZ4HC、Zlib、Png、X265等算法都要更加高效.

4 总结

本文讨论的ELZ4HC算法是在LZ4HC算法基础上，针对Alpha图像的特征提出了对多个参数采用联合优化的语法格式表示，并对出现频率高的参数采用经改进的较短码值表示的编码方案.实验结果验证了该算法具有高效和超低复杂度的优势.算法的后续改进方向是进一步挖掘Alpha图像的特征性，并进一步提高Alpha图像的编码效率.