基于串匹配的Offset循环映射屏幕图像编码算法*

林 涛，杨玉芬

(1.同济大学电子与信息工程学院，上海 200092；2.同济大学 超大规模集成电路研究所，上海 200092)

我国第3代AVS(即AVS3)视频编码标准需要支持互联网图像编码[1](Webpage Content Coding,WCC).国际上，最新HEVC标准的3大国际组织ISO，ITU，IEC联合发布的下一代视频编码标准(Versatile Video Coding,VVC)需要支持屏幕图像和互联网图像[2].因此，如何根据新的需求，设计更加有效的图像编码算法和工具，成为具有挑战性的新课题.针对计算机屏幕图像，国际上现有的编码效率最高的算法，是在高效视频编码(High Efficiency Video Coding,HEVC)国际标准的屏幕图像编码(Screen Content Coding,SCC)扩展版的基础上改进的串匹配算法[3-5].目前，工业界使用较多的是HEVC标准的经过充分代码优化的面向商用的编码器x265[6].这些算法和编码器都存在编解码复杂度非常高、不适合于软件实现，特别是在计算能力差异很大的互联网设备上软件实现的严峻问题.

具有低复杂度的算法，是在互联网设备上广泛用于屏幕截图的PNG压缩算法[7]和以高压缩率LZ4HC[8]为基础的高性能低复杂度的串匹配(String Matching with High Performance and Low Complexity,SMHPLC)算法[9].SMHPLC算法充分利用像素点间的冗余，进一步提高了压缩率，降低了复杂度.但是，SMHPLC算法没有充分考虑到计算机屏幕图像和互联网图像编码匹配参数offset的内在特性，于是笔者在其基础上提出一种基于串匹配的offset循环映射屏幕图像编码(Offset Rotation Mapping Based on String Matching,ORMSM)算法，并采用全面搜索和特殊位置搜索相结合的快速搜索方式，进一步提高编码效率，降低编解码复杂度.

1 SMHPLC算法描述

SMHPLC算法对参考串搜索的结果，是交替出现的未匹配像素串(用其长度uml(≥0)和uml个未匹配像素的数值um作为语法元素来表示)和匹配像素串(用其长度ml(≥1)和当前像素串与参考像素串之间的偏移量offset作为语法元素来表示).ORMSM算法只针对编码参数偏移量offset，因此重点对offset的编码方式进行说明.具体如图1所示.

图1 uml，um，ml，Offset的比特分配Fig. 1 Bit Allocation for uml,um,ml,Offset

类型1：前2个比特的数值为10，表示uml=0且ml=1；后6个比特的数值为0～61，分别表示offset =1～62，无需额外字节，数值为62表示63≤offset≤63+255，需额外1个字节，数值为63表示offset>63+255，需使用额外的多个字节.类型2：第1个比特的数值为0，表示uml = 0且ml > 1；第2—6个比特分配给ml；最后2个比特的数值为0～1，分别表示offset=1～2，无需额外字节，数值为2表示3≤offset≤3+255，需额外1个字节，数值为3表示offset>3+255，需使用额外的多个字节.类型3：前2个比特的数值为11，表示uml> 0且ml≥1；第2，3个比特分配给uml；第4—6个比特分配给ml；最后1个比特的数值为1表示offset>256，需额外2个字节，数值为0表示offset≤256，需额外1个字节.

2 串匹配编码参数偏移量Offset的统计特性

统计数据为13个AVS2屏幕、混合内容视频编码通用测试序列SCC序列(YUV格式的数据)[10]和从多个来源中选取的379个互联网图像WCC序列(RGB格式的数据)[11-13]，算法采用SMHPLC算法，level设定为4.图2a示出了SCC序列和WCC序列的offset从左到右为1，w，2到193，w的邻近值(包括w-6，w-5，w-4,w-3，w-2，w-1，w+1，w+2，w+3，w+4，w+5，w+6，2*w-3，2*w-2，2*w-1，2*w，2*w+1，2*w+2，2*w+3，3*w)的总体分布结果，其中w为图像宽度.图2b示出了SCC序列和WCC序列出现概率较高的几个offset的概率(出现的次数占所有offset的百分比)分布.

图2 SCC序列和WCC序列的偏移量Offset的统计结果Fig. 2 Statistical Results of the Offset for SCC Sequences and WCC Sequences

偏移量offset至少包括如下2个统计特性：

特性1屏幕图像和互联网图像的偏移量具有很大的特殊位置w相关性.

从图2a可知，offset=1时，offset出现的频率最高；offset=w时，次之.具体地，从图2b可知，相比于其他几个出现概率较高的offset，offset=w时其数目明显要高.

特性2特殊位置w的offset只需消耗小于或者等于1个字节.

offset为w时，出现的概率高出其他的offset，并且有些SCC序列和WCC序列分辨率较高，那么offset值就会很大.当这样的offset采用SMHPLC算法中offset的编码方式编入码流时，会消耗很多字节数.将offset映射为很小的数，就可以只需消耗小于或者等于1个字节.

3 匹配串特殊位置搜索算法和偏移量Offset循环映射算法

3.1 匹配串特殊位置搜索算法

针对偏移量offset特性1，SMHPLC算法在进行全面搜索之前先进行特殊位置搜索.即对于当前串，先搜索串匹配偏移量为w的参考串，若该参考串与当前串像素相同，则找到匹配像素串并计算匹配像素串长度，终止全面搜索；否则进行全面搜索，寻找匹配像素串.由于全面搜索包含哈希表和链表的更新，以及受到搜索次数的限制，并且统计结果显示offset为特殊位置w的概率很大，因此如果成功进行特殊位置搜索，那么会降低计算复杂度.

3.2 偏移量Offset循环映射算法

偏移量offset的循环映射算法是将w映射为1，1映射为2，2映射为3，…，w-1映射为w.具体地，编码前先将offset的映射值放入1维数组中，在offset编入码流之前，从1维数组中取映射值进行offset循环映射，再将映射后的offset减1，并按照第1节中3种类型的offset的编码方式编入码流.

对于SCC序列和WCC序列本身而言，图像的宽度从10到8k，offset为图像宽度的情况下，可能需要消耗6个比特或者1个字节或者多个字节.采用offset的循环映射算法，offset只需消耗小于或者等于1个字节.对于类型1和类型2，只需要分别利用最后6个比特和2个比特表示offset数值，无需额外字节；对于类型3，即使图像的宽度大于256，也只需额外1个字节表示offset数值.这样，消耗的比特数大大减少，提高了编码性能.

4 对比实验

4.1 实验结果

为了说明ORMSM算法的特性，将其与现有的SMHPLC算法、PNG算法[7]和x265算法[6]进行比较.测试数据与统计数据相同.实验环境配置为Intel(R) Core(TM) i5 CPU 760 @2.8 GHz (4核处理器)、8 GB内存和Win7 x64位操作系统的服务器.每次执行1个任务.

表1 编码算法的配置参数Table 1 Configurations of the Coding Algorithms

表1给出了5种算法的参数配置.level是字典编码中，在编码效率与编码复杂度之间进行权衡的配置参数，表示在哈希链上搜索的次数为2level-1.一般而言，level越大，编码时间越长，编码性能越好.

表2给出了SCC序列和WCC序列的ORMSM算法与SMHPLC(level 4,level 6,level 8)算法的每个level的压缩码流总字节数比值、编码时间比值、编码+解码时间比值和3个level的平均值.

表2 ORMSM算法与SMHPLC算法的SCC序列和WCC序列的比较结果Table 2 Experimental Results Between ORMSM and SMHPLC (SCC Sequences and WCC Sequences) %

表3给出了SCC序列和WCC序列的ORMSM-level 4算法与PNG算法(fast，default，slow配置)及x265算法(fast 0，fast 1配置)的压缩码流总字节数比值、编码时间比值、解码时间比值、编码+解码时间比值.

表3 ORMSM-Level 4算法与PNG算法及x265算法的SCC序列和WCC序列的比较结果Table 3 Experimental Comparison Results Among ORMSM-Level 4 and PNG and x265 (SCC Sequences and WCC Sequences) %

图3和图4分别示出了SCC序列和WCC序列的ORMSM算法与其他算法的编码效率(压缩比=原始序列字节数/压缩后码流字节数)和复杂度的比较结果.因为WCC序列的数据较多，所以按照SMHPLC算法的压缩比的升序排列，ORMSM算法的压缩比的顺序随着SMHPLC算法自动改变.

图3 SCC序列和WCC序列的ORMSM算法与其他算法的编码效率(压缩比)的比较结果Fig. 3 Coding Efficiency (Compression Ratio) Comparison Results Among ORMSM and Other Comparison Coding Algorithms for SCC Sequences and WCC Sequences

图4 SCC序列和WCC序列的ORMSM算法与其他算法的复杂度的比较结果Fig. 4 Complexity Comparison Results Among ORMSM and Other Comparison Coding Algorithms for SCC Sequences and WCC Sequences

4.2 讨论

ORMSM算法与SMHPLC算法相比较，对于SCC序列和WCC序列，在编码+解码时间分别平均降低12.43%和9.15%的前提下，编码性能分别提升了4.65%和3.29%；从表2可知，level=8配置下，编码时间分别降低22.15%和13.14%的前提下，编码性能分别提升了2.59%和2.44%.这说明，ORMSM算法很好地兼顾了高编码性能和低计算复杂度的双重优势(从图4可知，SMHPLC算法的计算复杂度本身就非常低).从图3a可知，相比于SMHPLC算法，ORMSM算法的单个序列的压缩比都有所提升，有些序列的提升非常显著.SMHPLC算法的解码速度都比编码速度快很多(图4)，解码时间的增多远不及编码时间的减少部分(表2)，且总编码+解码时间减少(图4).

ORMSM-level 4算法与PNG算法、x265算法相比较，兼具了高编码性能和超低计算复杂度的优势.从表3可知，相比于PNG(fast配置)算法和x265算法(fast 0配置)，ORMSM-level 4算法在编码时间和解码时间降低了几十倍的前提下，编码性能得到了进一步的提升或者几乎没有损失.PNG算法和x265算法的其他配置(default和slow)与ORMSM-level 4算法的相比，编解码复杂度成倍地增加(最多增加了80倍以上)，但编码效率提升不显著(不超过40%).从图3b和图4可知，相比于PNG(fast配置)和x265算法(fast 0配置)，ORMSM-level 4算法在总编码时间、总解码时间和总编码+解码时间显著减少的前提下，编码效率显著提升，且ORMSM算法的平均压缩比都是最高的，远远超过PNG算法和x265算法.

5 结语

通过串匹配算法来分析计算机屏幕图像和互联网图像的图像编码的编码参数offset的统计特性，在SMHPLC算法的基础上，提出了ORMSM算法.将ORMSM算法与SMHPLC，PNG，HEVC(x265)算法进行比较，结果表明ORMSM算法具有明显的高性能和低复杂度的双重优势.接下来的主要工作是进一步优化ORMSM算法，包括对最大的编码单元(Largest Coding Unit,LCU)的一维串匹配(1-Dimension String Matching,1DSM)和语法元素编码方式的优化.