一种改进的串匹配参数编码算法及在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图像的编码效率.