HEVC编码单位是编码树单元(Coding Tree Unit,CTU),其大小可为64×64,32×32或16×16.与以前标准类似,HEVC帧内编码的预测图像是通过相邻上面和左面的CTU重构图像边界和预测角度得到的,在相同预测角度上的预测值相差不大[2].文献[3]利用残余图像和预测的角度计算当前位置的预测值来进一步改进预测图像质量[3].对屏幕图像来说,文献[4]则移除双线性插值来降低编码后的码率[4].这些方法的共同点是着重于CTU级别的预测方法来得到更高质量预测图像,从而达到降低码率的目的.
HEVC与以前的H.264/AVC视频压缩标准一样都是采用预测编码和变换编码的混合编解码器.帧内的预测编码利用空间统计相似性,帧间预测编码则利用时间统计相似性.变换编码则进一步利用残差图像频域统计特性.但在屏幕内容视频编码中,频域统计特性与传统视频不同.屏幕内容的文字体积小、颜色少但对比度高、相似性高,采取传统的预测方法,会导致残差图像的空间统计特性发生改变,导致标准的变换编码方法编码效率变低.
目前的无损压缩方法是在基于块的编码框架下利用屏幕内容的特点进行编码.在帧内图像将当前编码块中的颜色进行分组建立索引,然后生成索引图,最后对索引图进行熵编码后与索引一起传输[5].基于索引图,利用参考帧上的颜色组分类和在当前编码块上组分类的映射关系,可以在帧间很好地处理一些特殊的颜色变化[6].基于当前编码块的直方图,对索引图进行预测也可以减少无损压缩的码率[7].而基于标准HEVC编码和字典编码的双编码器也可以减少码率[8].在帧内利用运动补偿[9]和改进帧内预测的方法[3, 4]以及在帧内运用运动补偿的方法[10]也可以提高编码的效率.
利用模板匹配的方法消除屏幕图像中的重复内容可以提高屏幕视频帧内图像的压缩率.模板匹配在视频编码中也有广泛的应用.在H.264/AVC(Advanced Video Coding)中可以直接将最优模板匹配的结果[11]或将几个候选的模板匹配结果求平均数[12]作为当前块的预测值.通过带权重的模板匹配和最优模板匹配也可提高无损情况的压缩比[13].对残差图像用自适应的变换[14]或非对称的离散正弦变换[15]编码同样可以改进编码的效率.
模板匹配因为不需传输额外的信息和改善预测图像质量,可以显著提升编码质量.但模板匹配也带来了图像预测准确性差、编码时间增加、空间复杂度提升等问题.上述前人的方法都是基于块为单位来在一定范围内进行模板匹配,本文提出一种像素级别的整帧模板匹配方法,可以更好地解决这些问题.本文的方法通过哈希表快速找到最佳匹配模板,而以帧为单位进行编码可将模板匹配初始误差最小化,以像素为单位则可最大程度利用模板匹配方法的预测优势.最后,对残差图像利用熵编码进行进一步地压缩.
1 整帧模板匹配方法通过观察和量化分析,发现在屏幕内容图像中存在许多重复的图像区域,例如在阅读本文的屏幕图像中,可以发现同一个文字在许多位置出现多次.基于这一屏幕图像中存在的规律,本文提出了一种整帧的模板匹配帧内图像编码方法(Template Matching Method,TMM),通过在一帧图像内尽可能地挖掘相似性从而提升帧内编码的效率.前人的研究中,模板匹配方法一般是以块为单位,比如在4×4大小的块上进行模板匹配.由于块的边界不一定和相似图像区域的边界正好匹配,因此基于块的模板匹配效果有时并不够理想.此外,以块的方式进行模板匹配和预测,一般还需要记录最优匹配的位置信息,这将给编码器带来比较大的编码代价.如果以像素为单位进行预测时,每个像素点都要记录最佳匹配的位置信息,其代价几乎不可接受.因此本文提出的整帧模板匹配方法并不在码流中记录最佳匹配的位置,而是通过编解码器使用同样的数据集合和同样的方法寻找最佳匹配模板的位置,从而不需要在码流中存储位置信息,节省了比特流.
本文提出的整帧模板匹配方法以单个像素为模板匹配单位,针对相似性很强的屏幕内容图像,可以在绝大部分像素点上取得残差为0的模板匹配预测结果,该方法的编码器结构框图如图 1所示.
 |
| 图 1 模板匹配帧内编码算法框架Fig. 1 Algorithm framework of TMM intra frame coding |
| 图选项 |
在图 1中,帧内图像与预测图像的残差经过LZMA无损压缩后形成压缩码流,同时残差与预测图像相加后形成重构图像,由于这一过程是无损的,重构图像中每个像素的值和原始图像实际上完全相同,只是重构图像在编码过程中是逐步填充的,只有已经被编码的像素点出现在重构图像中,并用于后续像素点的预测.编码器内部有一个哈希表,每帧图像开始编码前哈希表为空,每个像素点被编码后,其左侧和上方的已重构像素点构成一个待匹配模板,该模板经过哈希后被加入编码器内建立的哈希索引表中,并用这个索引表和下一个待编码像素点周围已重构像素点构成的模板进行匹配,根据最佳匹配来预测待编码像素点的预测值,所形成的残差再送入LZMA无损编码器.
帧内图像中的所有像素点按照从左到右,从上到下的顺序依次进行预测和编码.在整帧的所有像素点都被编码完毕后,输出缓存区得到的就是当前帧的残差图像.对残差图像进行熵编码,比如本文中使用LZMA熵编码算法,就得到了编码后的码流.对一帧图像的全部区域进行最优模板匹配的查找是一项非常耗时的操作,对高清或更高分辨率的图像更是如此,普通的方法往往需要数个小时才能完成全部匹配计算,且复杂度随图像大小呈级数增长.为了提升模板匹配方法的匹配准确度和匹配查找速度,TMM算法设计了良好的匹配模板和快速匹配查找算法,这是算法设计的两个核心问题.本文提出的方法设计了一种由21个像素点组成的匹配模板,并通过在重构像素点基础上建立哈希表来加速模板的查找过程.值得注意的是因为所有的操作都是基于重构图像的数据,所以解码端与编码端在哈希表的构建和查找过程是完全一样的,这就保证了解码端的解码正确性.此外,虽然哈希表相对全搜索将会得到次优的匹配结果,但精心设计的哈希表可以减弱这方面的负面影响.实验结果表明:哈希表和哈希查询过程在屏幕视频中效果很好,速度也非常快.在1.1~1.3节中将分别给出模板设计、哈希表构建和预测过程的具体细节.
1.1 模板设计通常来说,如果模板较大会导致计算量增大和准确性变差,而模板较小也会降低预测的准确性,因此合理选择模板的大小和形状对预测的效率具有重要影响.对H.264来说,实验表明4×4大小的模板对屏幕内容是一种合理的选择[11, 12].如图 2所示,本文采用21个像素点组成模板,其中X表示模板对应的像素点.它的左面和上面的21个像素点位置构成匹配模板,这些像素点都是已重构的像素点,如果相应位置的像素点不存在或者尚未重构,该位置在模板中的值记为0.
 |
| 图 2 21个像素点模板Fig. 2 21 pixel points template |
| 图选项 |
如图 3所示,将这21个像素点根据位置分为G1~G8的8组:
| G1:{1} | G2:{2} |
| G3:{3} | G4:{4,5} |
| G5:{6,7,13,14} | G6:{8,15,16,17} |
| G7:{9,10,18,19} | G8:{11,12,20,21} |
 |
| 图 3 21个像素点模板分为8组Fig. 3 21 pixel paints template classified into eight groups |
| 图选项 |
计算每组像素点值的平均值gi(i=1,2,…,8),作为模板的特征值.因此一个模板template可以被表示为8个值域在0~255之间的特征值.1.3节中的模板匹配操作就是基于这8维特征向量的比较.
template=vector{g1,g2,g3，g4,g5,g6,g7,g8}
显然越靠近待预测像素X的模板中的点越重要,因此G1,G2,G3只包含一个像素,G4包含两个像素,G5~G8包括4个像素.求平均值的操作可以在模板匹配过程中抑制远离X位置的模板噪音的影响.
1.2 哈希表构建在图像中通过全搜索进行模板匹配是一个非常耗时的操作,特别是对于图像中底部的像素来说.例如,对于一个分辨率为1920像素×1080像素的图像来说,右下角的最后一个像素,如果要用全搜索方式进行模式匹配,需要执行1920×1080-1=2073599次匹配操作,也就是约200万次匹配操作,在普通台式机上这一个像素的匹配操作需要超过0.5h的时间.为了加快匹配过程,本文提出的整帧模板匹配引入哈希表来大幅度提升匹配操作的速度.
从1.1节可知,每个模板的特征向量由8个在0~255之间的数值组成.本文选择每一个特征值的高位的3个比特来构成整个模板的哈希值,8维特征向量共计形成24 bit的哈希值,这样整个哈希表的长度为224=16 M.在帧内预测编码过程中,每个哈希值都对应一个链表,该链表保存模板特征为该哈希值,且模板中21像素值不重复的所有对应像素点在图像中的位置.进行模板匹配操作时,首先计算模板的哈希值,然后以O(1)的复杂度迅速找到该哈希值对应的链表,再在当前链表中逐个比较对应位置的模板,从而找到最佳匹配的模板.
为了进一步加速模板匹配的速度,每个新像素被编码后,该像素的模板在加入链表时,还将与链表中已有的模板进行比较,如果模板相同或相近,则不再在链表中增加该模板的信息,从而可以有效缩短链表的长度,提高了哈希查找的速度.如果模板与链表中的已有模板差距较大,则在链表的末尾增加一个新的节点,记录新模板的X像素所在位置等信息,以备后续编码的像素点获得更好的匹配.由于模板中的每一位向量都只取前3个比特作为哈希值,所以哈希值对模板之间的细微区别是不敏感的,从而可以帮助编解码器都能快速准确地找到接近最佳的匹配.
随着一帧图像的帧内编码过程的进行,哈希表也会在相应的链表中包含越来越多模板.假定在最坏情况下,帧内图像中每个像素都有不同的模板,比如对1 920像素×1 080像素分辨率的帧来说,在哈希表中最多有大约两百万个模板.这样在16 M个哈希表项中,平均每个哈希表项所对应的模板数量不到1/8个,也就是哈希表项对应的链表长度较短.实际的一帧屏幕图像来说,由于存在很多相同或类似的模板,总模板数远小于两百万个.实验结果显示,在实际屏幕帧内图像上,哈希表项对应的最长链表长度不超过1 000,大部分哈希表项对应的链表长度为0,不为0的哈希表项对应的平均链表长度大约是20.这意味着对每个像素点来说,只需要约20次模板查找操作就可以找到接近最佳的匹配模板.因此,通过引入哈希方法,模板匹配查找的速度得到了大幅度的提高.
1.3 预测过程对一帧图像中的每个像素,可以利用1.2节设计的哈希表快速找到相对当前模板的最佳匹配模板.与最佳匹配模板对应的像素被用作当前像素的预测值.这就是模板匹配的预测过程,它几乎和哈希表的构建过程相似,但也有一些微小的差异.
对当前像素来说,模板和哈希值的计算是与哈希表构造过程是完全一样的.利用哈希值,模板匹配的方法在哈希表中找到对应的链表.通过分别比较当前像素和链表中模板对应位置的21个像素是否相等,计数完全相同的模板中像素点个数,计算两个模板的相似度.
预测的过程要遍历对应链表中的所有节点,从链表中找到与当前待预测像素点对应模板最相似的模板,将该模板对应X像素点位置的值做为待预测像素点的预测值,从而完成像素的预测操作.
对屏幕内容的图像来说,有大约80%左右的像素点会得到与原始值相同的预测值.这就意味着图像中超过80%的像素点预测残差是0,这为后续的LZMA等熵编码打下了非常好的基础.
2 实 验在实验中用到了5个屏幕视频的序列,如图 4所示.这些测试序列是HEVC在屏幕编码方面的标准测试序列[16].这些序列的视频格式都是RGB 4∶4∶4,包含3个分量红色、黄色和蓝色.作为对比的基准编码器是HEVC的屏幕视频编码HM12-RExt4.1参考软件,采用的是每帧均做帧内编码的配置.
 |
| 图 4 屏幕内容视频测试序列Fig. 4 Screen content testing video sequences |
| 图选项 |
对屏幕图像的每个像素点进行模板匹配,模板匹配方法就是1.1节到1.3节中介绍的21个像素点组成的模板和24比特哈希表,最后的熵编码采用的是7-zip软件中的LZMA熵编码器.
每个序列的的前10帧图像用整帧模板匹配的方法进行无损帧内编码,计算10帧图像的平均码率和编码时间,如表 1所示.与文献[10]中的帧内运动补偿方向相比,压缩率更高,编码时间更少.其中:Seq.为序列名称；M为编码器所采用算法,分别为HEVC视频编码HM12-RExt4.1参考软件所实现的算法和本文提出的TMM算法;Bits为编码后所占的比特数,KB;CR为压缩率;CR ratio为TMM算法的压缩率与参考软件对应算法压缩率的比值,大于1表示TMM算法压缩效率更优;Time为编码时间，s；Time ration为参考软件对应算法编码时间与TMM算法编码时间的比值，大于1表示TMM算法编码时间更短.
表 1 实验结果Table 1 Experimental results
| Seq. | M | Bits/KB | CR | CR ratio | Time/s | Time ratio |
| CAD waveform | HM12-RExt4.1 | 426.1 | 14.26 | 2.86 | 371.9 | 1.99 |
| TMM | 149.1 | 40.74 | 186.3 | |||
| cg twist tunnel | HM12-RExt4.1 | 425.1 | 6.35 | 1.91 | 219.0 | 1.75 |
| TMM | 222.1 | 12.2 | 125.3 | |||
| pch layout | HM12-RExt4.1 | 505.1 | 12.08 | 2.1 | 381.5 | 1.73 |
| TMM | 239.5 | 25.37 | 219.9 | |||
| Programming | HM12-RExt4.1 | 567.8 | 4.77 | 1.57 | 232.8 | 1.73 |
| TMM | 361 | 7.48 | 134.8 | |||
| Word editting | HM12-RExt4.1 | 712 | 3.79 | 1.88 | 213.9 | 1.75 |
| TMM | 378.1 | 7.14 | 121.9 |
表选项
实验结果表明:整帧无损模板匹配的编码方法相对当前的HEVC HM12-RExt4.1编码算法,有2倍左右的压缩比提升,同时编码时间也较少,时间只有参考软件的
左右,且模板匹配方法具有高度的并行性,未来可以考虑使用GPU(Graphics Processing Unit)等方式给予并行加速,还可以进一步提高编码速度.以图 3 (a)中的CAD waveform序列的第一帧图像的第一个分量黄色来说,残差图像为0的就有1 959 263个,绝对值在[1.5]有27474个,[6,20]有2621个,大于100的有66231个,它们占整个残差图像的比例分别为94.5%、1.3%、0.1%和3.2%.残差图像不为0的点按照行来说,总的趋势是越来越少,最少的只有5个点,但不稳定.对哈希表来说,共有26890项,链表的总长度是50322,平均长度为1.87,链表长度超过30的共有42个,链表最长为1485.
3 结 论屏幕图像相较自然图像有更多的结构相似性.模板匹配方法可充分利用这种特性减少数据相关性,从而得到更高的压缩效率.本文提出了一种针对屏幕视频的整帧无损帧内模板匹配的编码方法,该方法在无损情况下相比当前最新技术水平的HEVC扩展软件可以达到约2倍的压缩比提升,压缩算法执行时间只需一半左右.下一步的研究工作通过改善模板设计和哈希表设计,采取其他的熵编码器,该方法有更大的潜力取得更好的性能.
参考文献
| [1] | Vermeir T.Use cases and requirements for lossless and screen content coding[C]//Proceedings of 13th Meeting of Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 2013: JCTVC-M0172. |
| [2] | Woo-Jin H, Sullivan G J, Ohm J, et al.Overview of the high efficiency video coding (HEVC) standard[J].IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(12): 1649-1668. |
| Click to display the text | |
| [3] | Zhou M H, Gao W, Jiang M Q, et al.HEVC lossless coding and improvements[J].IEEE Transactions on Circuits and Systems for Video Technology, 2012, 22(12): 1839-1843. |
| Click to display the text | |
| [4] | Saxena A, Chen H M, Felix F C.Rce3: Nearest-neighbor intra prediction for screen content video coding[C]//Proceedings of 15th Meeting of Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 2013: JCTVC-O0049. |
| Click to display the text | |
| [5] | Lan C L, Shi G M, Wu F.Compress compound images in H.264/MPGE-4 AVC by exploiting spatial correlation[J].IEEE Transactions on Image Processing, 2010, 19(4): 946-957. |
| [6] | Peng X, Xu J, Wu F.Exploiting inter-frame correlations in compound video coding[C]//Proceedings of IEEE Visual Communications and Image Processing (VCIP).Piscataway, NJ: IEEE Press, 2011: 6115952. |
| Click to display the text | |
| [7] | Guo X, Li B, Xu J Z, et al.AHG8: Major-color-based screen content coding[C]//Proceedings of 15th Meeting of Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 2013: JCTVC-O0182. |
| [8] | Lin T, Zhang P J, Wang S H, et al.Mixed chroma sampling-rate high efficiency video coding for full-chroma screen content[J].IEEE Transactions on Circuits and Systems for Video Technology, 2013, 23(1): 173-185. |
| Click to display the text | |
| [9] | Pang C, Sole J, Guo L W, et al.Nonrce3: Intra motion compensation with 2-D MVS[C]//Proceedings of 14th Meeting of Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 2013: JCTVC-N0256. |
| [10] | Budagavi M, Kwon D-K.AHG8: Video coding using intra motion compensation[C]//Proceedings of 13th Meeting of Joint Collaborative Team on Video Coding (JCT-VC) of ITU-T SG 16 WP 3 and ISO/IEC JTC 1/SC 29/WG 11, 2013: JCTVC-M0350. |
| [11] | Tan T K, Boon C S, Suzuki Y.Intra prediction by template matching[C]//Proceedings of International Conference on Image Processing, ICIP.Piscataway, NJ: IEEE Press, 2006: 1693-1696. |
| [12] | Tan T K, Boon C S, Suzuki Y.Intra prediction by averaged template matching predictors[C]//Proceedings of 4th Annual IEEE Consumer Communications and Networking Conference, CNCC.Piscataway, NJ: IEEE Press, 2007: 405-409. |
| Click to display the text | |
| [13] | Wige E, Yammine G, Amon P, et al.Sample-based weighted prediction with directional template matching for HEVC lossless coding[C]//Proceedings of 2013 Picture Coding Symposium (PCS).Piscataway, NJ: IEEE Press, 2013: 305-308. |
| [14] | Lan C, Xu J, Wu F, et al.Intra frame coding with template matching prediction and adaptive transform[C]//Proceedings of International Conference on Image Processing, ICIP.Piscataway, NJ: IEEE Press, 2010: 1221-1224. |
| Click to display the text | |
| [15] | Su H, Han J N, Xu Y W.An optimized template matching approach to intra coding in video/image compression[C]//Proceedings of SPIE-IS Electronic Imaging-Visual Information Processing and Communication V.Bellingham WA: SPIE, 2014: 902904. |
| Click to display the text |
