调色板编码中2-邻域联合转移概率的索引图预测

宋传鸣1,2,3何 兴1闵 新1王相海1

1(辽宁师范大学计算机与信息技术学院 辽宁大连 116081)2(大连理工大学计算机科学与技术学院 辽宁大连 116024)3(计算机软件新技术国家重点实验室(南京大学) 南京 210023) (chmsong@lnnu.edu.cn)

采用4-邻域模板匹配对索引图进行非局部预测是调色板编码的一种典型技术.通过实验分析发现,1个4-邻域模板存在数量众多的干扰模板,并且不能有效捕获边缘反走样区域的颜色转移特征,从而提出一种包含4个子模板的2-邻域匹配模板结构来刻画前景物体或文字边缘在其左上角、左下角、右上角和右下角的特定颜色转移模式;同时,将模板预测建模为一种可通过查表操作实现的转移概率;进而,提出一种2-邻域联合转移概率的索引图预测方法.实验表明:该算法的预测准确率为97.70%,比多级预测算法(MSP)和局部方向预测算法(LDP)分别平均提高了4.50%和2.27%,尤其适用于包含大量字符和由计算机生成的几何图元的复杂屏幕内容编码.并且,计算复杂度与LDP相当,明显低于MSP,可应用实时性需求较高的、基于调色板-索引图的屏幕内容预测编码中.

关键词视频编码;屏幕内容编码;调色板编码;索引图预测;转移概率

高速网络和云——移动计算模型的发展促使视频会议、网络游戏直播、远程教学、屏幕镜像、桌面虚拟化等诸多应用生成了大量高清晰度屏幕内容[1-2],并且这些内容中往往既包含不连续色调的区域(如文本、图表、图形、图标),又包含连续色调的区域(如自然图像、视频).因此,屏幕内容在时间域、空间域和频率域的数据分布特性与自然视频存在明显差异[3],导致MPEG AVC/H.264、高效率视频编码(high efficiency video coding, HEVE)等面向自然图像/视频的典型编码方法无法获得令人满意的压缩效率.为此,国际视频编码联合协作组(Joint Collaborative Team on Video Coding, JCT-VC)自2014年至今致力于面向屏幕内容的HEVC扩展编码标准——屏幕内容编码(high efficiency video coding-screen content coding extension,HEVC-SCC)的制定工作,并且目前已采纳了帧内块拷贝(intra-block copy)、调色板、自适应颜色变换、分量间预测(cross component predic-tion)、残差差分脉冲编码调制(residual differential pulse code modulation)等作为其推荐编码方法[4].其中,帧内块拷贝和调色板是HEVC-SCC的2种最主要的方法,为其贡献了大部分的性能提升[5].前者类似于发生在同一帧内的运动估计,利用矩形区域的像素集合发掘屏幕内容中蕴含的非局部冗余,但是灵活性不够,很难用固定形状的像素集合实现对文本、图表和图标等内容的最佳匹配,计算量较大,并且传统视频编码的运动估计为它提供了很好的参考,技术方法较成熟;后者则通过发掘屏幕内容的颜色数量少、重复图案多的数据特点实现压缩,其计算量也明显低于帧内块拷贝,在压缩比、实时性和复杂性等多方面可以较好地满足屏幕内容编码的需求.

调色板编码算法是一种适用于屏幕图像中非连续色调像素内容的一种压缩算法,其基本思想是首先将屏幕内容中出现次数最多的4种颜色值作为基本颜色(base color),并为其分别指定索引值建立调色板;其次,将屏幕内容中的各个像素量化成基本颜色或逃逸色(escape color),并用基本颜色和逃逸色对应的索引值代替像素值,生成索引图(index map);最后,对建立的调色板和索引图进行编码.目前,调色板的建立和编码已相对成熟,出现了基于局部调色板的预测编码算法[6-8]和基于全局调色板的预测编码算法[9].而相比之下,索引图的编码效率,尤其是那些分布在边缘过渡区或连接区的索引值,则仍有较大的改进空间[5].为解决这个问题,本文提出一种基于2-邻域联合转移概率的索引图预测方法:首先,利用局部方向预测失败的索引值组成训练数据集,计算索引值的2-邻域转移概率;其次,在局部预测失败的情况下,利用与待预测索引相邻的4个索引计算4组2-邻域转移概率及其联合转移概率;最后,选择联合转移概率最大的索引值作为待编码索引的最优预测值.本文算法的主要贡献包括3个方面:

1) 通过实验统计发现,较大尺寸的预测模板(如4-邻域模板)会产生数量众多的候选模板,而其中的大多数却为干扰模板,并且大模板不能有效捕获边缘反走样区域的索引值分布特点,进而导致模板的平均匹配概率和非局部预测效率不高;

2) 将基于模板的索引图预测建模为一种基于颜色转移概率的查表操作,可降低模板匹配的计算复杂度;

3) 实验结果表明,本文算法将索引图的平均预测准确率提高到97.70%,改善了边缘反走样区或过渡区的索引值预测效率.

1相关工作

典型的索引图编码主要有4类:算术编码、行程编码、词典编码和预测编码.

算术编码主要通过减少索引图数据的统计冗余达到压缩的目的,如文献[10]采用自适应算术编码、文献[11]采用上下文重映射和算术编码压缩索引图等.但是,算术编码没有充分利用索引图中特有的重复图案等非局部统计特点,编码效率不高.

行程编码则发掘了相邻索引值出现的重复规则图案,即局部相关性,如文献[12]采用1D行程方法将索引值组织成一系列二元、三元组序列进行压缩;考虑到索引图中的重复图案大多是2D的,文献[13]将一个重复的2D图案表示成四元组,提出了索引图的2D行程编码方法.同时,文献[14]进一步发现在索引图的相邻行(列)之间还存在较强的行(列)局部相关性,并提出若一个图像块的某一行(列)与其相邻的前一行(列)有相同索引值或者仅有1个索引值不同,则用垂直(水平)行程模式编码该行(列)像素的索引图,其预测效率更高,所需同步信息更少.虽然行程编码方法对于规则、平滑区域的索引图非常有效,可是却对边缘、纹理较复杂区域的编码效率偏低.

针对屏幕图像中往往包含较多的相同或相似文字和图形的特点,研究人员提出了一类基于词典的编码算法,利用待编码索引值所在的一个1D或2D连续索引串作为模板,该索引串在空间域上可组织成任意形状,再在已编码区域中搜索与其最匹配的索引串,从而去除数据冗余.文献[15]采用基于Lempel- Ziv字典的gzip算法对复合图像进行编码;文献[16]应用LZMA (Lempel-Ziv-Markov chain algorithm)等提出了面向屏幕内容的字典编码方法;为加快像素串的匹配速度,文献[17]提出了Hash表结构的1D字典编码以及2种字典模式;文献[18]则进一步提出了屏幕内容的2D字典编码方法,将待编码单元的Hash值作为字典索引查找到候选的匹配块.该类方法利用索引图包含大量相同字符或者相同纹理结构这种非局部相关性特点,取得了不错的编码效率.然而,模板索引串越长,所需要的搜索时间或字典空间等代价就越高,并且,由本文第3节的实验结果可知,过长的模板索引串对提高边缘区域的编码效率反而是不利的.另外,字典编码方法对索引图局部相关性的处理效率不高.

为了能同时发掘索引图的局部和非局部冗余,文献[19]提出了一种多级预测(multi-stage prediction, MSP)编码方法,先通过方向预测去除索引值的局部相关性,然后对预测失败的元素采用模板匹配预测发掘其非局部数据冗余,其索引值被准确预测的概率达到了92%;文献[20]提出了一种2级层次预测编码模式,第1级将每个与其左侧或上侧相邻索引值相等的索引用特定符号标识出来,再在第2级对每一行符号进行分组,最后对各标识符号进行熵编码.可见,预测编码是同时发掘索引图局部与非局部相关的有效策略,优于典型的算术编码、行程编码和词典编码.然而,文献[19-20]提出的2种方法涉及多轮扫描,计算量高.在这种情况下,文献[7,21]提出略去MSP算法的模板预测.其中,文献[7]通过简化方向预测过程,将MSP的计算量降低了80%,可是预测方向较少、预测效率有所降低,适合实时要求较高的应用;文献[21]则通过实验统计发现,提出了索引图的“局部方向相关性”特性,进而利用这个性质在MSP的1级预测基础上提出了2次方向预测,其预测准确率达到了95%.不过,由于文献[7,21]仅发掘了索引图的局部数据相关,尚有部分索引值未借助索引图的非局部相关性进行处理,其预测准确率仍有一定的提高空间.本文发现,发生预测失败的索引主要分布在边缘的过渡或连接区域,并且由于文字、线条往往进行边缘反走样处理[5],这些过渡或连接区域的索引值常呈现特定的组合模式.故此,模板预测仍是充分利用这种模式的有效途径.与现有方法不同,本文将模板预测建模为转移概率最大化问题,并进一步缩小模板尺寸,从而以较小的时空复杂度实现了索引值的非局部预测,改善了索引图的预测准确率.

2索引图的局部方向预测和模板预测

本节我们主要对基于局部方向相关性的索引图预测和基于模板匹配的索引图预测方法进行简要介绍.

2.1基于局部方向相关性的索引图预测

文献[21]的实验结果表明,相邻索引值之间存在较强的方向相关性,且沿着垂直、水平方向的相关性高于沿着对角线、反对角线方向的相关性.所以,对于待预测索引值x,文献[21]首先将其水平方向相邻索引值的预测方向作为初始预测方向.如果该索引值沿着某个方向预测成功,则仍然沿着该方向预测x;若前一索引值预测失败,则采用MSP的方向预测算法进行初始预测.此时,若仍旧预测失败,则利用图1所示的模板分水平、竖直、对角线或反角线4种情况进一步对索引值x完成方向预测,继续判别沿着45°,60°,90°,120°,135°,150°,180°方向的几何正则性.

Fig. 1 Template for local directional prediction[21]
图1 局部方向预测模板[21]

当待预测索引值x的初始预测方向为水平时,由于初始预测失败,表明x处不存在水平方向的边缘,即IxIa(IxIa分别表示预测模板中元素xa处的索引值),其2次预测过程如下:

1) 若Ia=Ib并且IaIc,说明x处可能存在竖直边缘,则令索引x的预测值Px=Ic.

2) 若Ia=Ib并且Ia=Ic,则令Px=Id.

3) 若Ia=Ic并且IaId,说明x处可能存在45°方向的边缘,则令Px=Id.

4) 若Ia=Ic并且Ia=Id,则令Px=Ib.

5) 若IaId,

① 若Ic=Ii,说明x处可能存在90°方向的边缘,则令Px=Ic

② 若If=Ib或者Ih=Ib或者Ig=Ib,或者Ic=Ih,说明x处可能存在150°,120°或135°方向的边缘,则令Px=Ib

③ 若Ij=Id或者Ij=Ic,说明x处可能存在60°或45°方向的边缘,则令Px=Id.

6) 若Ia=Id,

① 若Ii=Ic或者Ij=Ic,说明x处可能存在垂直或者60°方向的线,则令Px=Ic

② 若If=Ib或者Ig=Ib或者Ih=Ib,或者Ic=Ih,说明x处可能存在120°,135°或150°方向的线,则令Px=Ib.

7) 若上述1)~6)条件不满足,则表明x处不存在明显的局部几何正则性,其局部方向预测失败,默认令Px=Ic,预测结束.

由于篇幅所限,当初始预测为其他方向时,其2次预测过程可详见文献[21].

2.2基于模板匹配的索引图预测

与文献[21]的思路不同,MSP算法[19]在初始预测失败的情况下引入了一种基于模板匹配的第2级预测,其主要思路是利用上下文内容的统计相关性来计算x的最佳预测值.如图2所示,实线方框内的值“1”是当前待编码的索引值,阴影方框内的值“0 0 2 0”是与其具有统计相关性的上下文预测模板,以模板“0 0 2 0”作为上文,下文“1”出现的概率为0.75,而下文“2”出现的概率为0.25,所以“1”被作为待编码索引x的预测值.这样的模板可以统一地表示成图3所示的形式,其中x表示待预测的索引值,abcd表示与x相邻的已编码索引值,下文约定称其为“4-邻域模板”.

Fig. 2 Diagram of template prediction[19]
图2 模板匹配预测示意图[19]

Fig. 3 Diagram of 4-neighbor template
图3 4-邻域模板示意图

文献[19]的实验结果显示,在初始预测失败的情况下,4-邻域模板预测的准确率为53%.从这个意义上讲,基于4-邻域模板匹配的索引图预测效率还不尽如人意.

34-邻域模板预测效率及转移概率建模

虽然模板匹配预测能够发掘屏幕内容的非局部相关性,但是文献[21]认为模板预测对于那些包含复杂线条(比如汉字)、图案大多不具有特定全局模式的屏幕图像,其预测准确率将低于50%.为此,本节深入分析基于4-邻域模板匹配的预测效率和计算效率偏低的原因,进而提出一种基于联合转移概率的索引值预测思路.

3.1基于模板匹配的预测效率分析

考虑到MSP的初始预测和文献[21]的2次方向预测已经能够较好地解决索引值的局部预测问题,本文主要在2种局部预测算法均失败的情况下,探讨基于4-邻域模板匹配的预测效率.

首先,由于4-邻域模板采用待编码索引x周围的4个相邻索引值ad作为模板,并且xad又各有5种可能的取值(包括4种基本颜色和1种逃逸色),这样将产生55=3 125种可能的组合,模板数量众多.但是,其中45的模板却都属于干扰模板,也就是2 500种.例如当待预测索引x=0且其邻域索引值为“2 3 1 2”时,如图4(a)所示.图4(b)中的4个模板都会对x的预测过程产生干扰.这表明在干扰模板数量多于正确模板数量的情况下,能够获得准确预测值的概率取决于正确的上下文出现的概率.因此,有必要进一步分析各种模板的分布情况.

本文选取JCT-VC公布的19个标准序列的第1帧和3幅文字图像[21],并统计其中经过4-邻域模板匹配预测失败时所采用的模板集合,从中选取匹配次数最多的模板.表1给出了在这些测试序列和图像中的失败索引数量、匹配次数最多的模板数量及对其预测结果构成干扰的模板数量.从表1中能发现,除了“PPT_ Doc_xls”序列,其他18个序列的各项比例相差不大,匹配次数最多的模板平均占预测失败索引数量的7.017%,对其预测结果构成干扰的模板平均比例为5.901%.若不考虑“PPT_Doc_xls”序列,匹配次数最多的模板平均占比为5.719%,其干扰模板的比例则高达5.710%.这说明即使对于匹配最多的模板来说,干扰模板的影响也是非常明显的,单一模板所占比例不高;而对于其他的匹配模板,干扰模板的数量甚至会多于正确模板的数量.例如“PCB_Layout”序列,最多匹配的模板占比12.220%,其干扰模板则占比20.847%.在这种情况下,基于模板匹配的索引预测将全部产生错误的预测值.可见,干扰模板的大量存在是4-邻域模板预测效率不高的基本原因之一.

Fig. 4 Example of 4-neighbor interference template
图4 4-邻域干扰模板示例

Table1TheResultsofMostMatchedTemplateNumberandInterferenceTemplateNumber
表1最多匹配模板数量和干扰模板数量的统计结果

SequenceIndex Numberwith PredictionFailure Number ofMost Matched TemplateNumber ofInterferenceTemplate Ratio of MostMatchedTemplate∕%Ratio ofInterferenceTemplate∕%ChinaSpeed16951165911159.7876.578MissionControlClip353807224734854.1766.477CAD_Waveform24700119017964.8187.271Cg_Twist_Tunnel90575937436.5478.204Console23216224315949.6616.866Desktop44087286825576.5055.800FlyingGraphics54514143318092.6293.318Map49550201116874.0593.405PCB_Layout259333169540312.22020.834PPT_Doc_xls5378118431533234.2709.914Programming18013780 7534.3304.180Video_Conferencing180025678523.1504.733Web_Browsing199435939492.9734.759WordEditing31068184310985.9323.534SlideEditing299258487022.8342.346SlideShow110014766124.3275.563Robot50650397515417.8483.042VenueVu96064529246925.5094.884BasketballDrillText19638154111177.8475.688English Text26760153310085.7293.767Simplified Chinese32561177014445.4364.435Traditional Chinese39216148316573.7824.225Average34020257019157.0175.901

另外,本文进一步分析了“PPT_Doc_xls”序列中上下文正确的模板出现比例较高的原因,发现该序列在边缘位置较少开启反走样,基本不受逃逸色和基本颜色的影响,如图5所示.而对于绝大多数的屏幕内容序列,尤其是那些由显示适配器生成的图形元素丰富的序列,反走样能有效改善其视觉质量.并且,根据文献[22]的研究发现,屏幕内容中前景物体的边缘和文字轮廓的反走样往往出现在2个相邻的像素之间,形成特定的颜色转移模式,如图6所示.故此,边缘反走样不仅会导致局部方向预测的失败,其影响区域、影响方式也与4-邻域模板不同.本文认为,这是4-邻域模板预测效率不高的第2个基本原因.

Fig. 5 Enlargement of part of PPT_Doc_xls sequence
图5 PPT_Doc_xls序列的部分区域放大图

Fig. 6 The color transition pattern in screen content[22]
图6 屏幕内容中的颜色转移模式[22]

3.24-邻域模板预测的计算效率分析

为分析基于4-邻域模板的索引值预测的时间复杂度,设模板匹配的搜索窗口为W×H像素,则该搜索窗口中共有W×H个可能的候选模板,且每个候选模板又至多需要4次比较操作,所以采用4-邻域模板预测1个索引值的时间复杂度为O(W×H),存储搜索窗口中已编码索引的空间复杂度也为O(W×H).从这个意义上讲,模板的尺寸越大,其匹配的计算代价越高.

3.3模板预测的转移概率模型

通过2.2节的论述可知,模板预测的思路是利用上下文内容的统计相关性来计算待编码索引的最佳预测值.以4-邻域模板为例,设IaIbIcId分别表示图3中abcd的索引值,Px表示x的预测值:

(1)

则模板预测在本质上是将使式(1)的联合条件概率取得极值的I作为x的预测值.本文称P{I|Ia,Ib,Ic,Id}为“转移概率”,记为PIabcd.因此,在预测每个索引值时,没必要对已编码索引进行4×W×H次比较操作,而只需仿照Markov过程的转移概率矩阵建立一张如表2所示的顺序表来保存当上文为(Ia,Ib,Ic,Id)时,下文为I∈{0,1,2,3,4}的最大转移概率.其中,NIabcd表示由上文(Ia,Ib,Ic,Id)转移到I的次数.这样,基于模板匹配的索引值预测就转化为查表操作,时间复杂度由O(W×H)降到O(1);同时,由于IaIbIcIdI各有5种可能的取值,即{0,1,2,3,4},转移概率表最多有55=3125行,故此预测1个索引值的空间复杂度就从O(W×H)变成O(3125×7)(7表示每条表项的列数).当然,若搜索窗口较小,这种基于顺序表的实现方式反而会增加内存开销.

Table2TheTableStructureofTransitionProbability
表2转移概率表的结构

IaIbIcIdITimesTransitionProbability00000N0←0000P0←000000001N1←0000P1←0000︙︙︙︙︙︙︙00004N4←0000P4←000000010N0←0001P0←000100011N1←0001P1←0001︙︙︙︙︙︙︙44444N4←4444P4←4444

4基于2-邻域联合转移概率的索引图预测

鉴于4-邻域模板所存在的问题,在本节中,我们根据索引值局部预测失败的情形来讨论恰当的预测模板结构,并给出详细的索引图非局部预测算法.

4.1索引图预测的2-邻域模板

本文从JCT-VC公布的19个标准测试序列的前90帧和3幅文字图像中选取了2 000个局部方向预测失败的索引值,发现这些索引值大多位于逃逸色和基本颜色变化明显的区域,与文献[22]所指出的前景物体边缘和文字轮廓的反走样区域一致.同时,经过仔细对比分析还发现,这些局部预测失败的索引主要分布在前景物体边缘和文字轮廓的左上部、左下部、右上部和右下部,如图7所示.因为只有在这4种位置时,待预测索引才可能频繁出现与其相邻索引不相关的值.

Fig. 7 The color transition pattern in screen content
图7 屏幕内容中的颜色转移模式

基于图7分析结果,本文提出了一种2-邻域模板,如图8所示,它由4个子模板构成,分别对应前景物体边缘或文字轮廓的4种拐角位置.下面对该模板的预测效率进行分析.

Fig. 8 The proposed 2-neighbor template
图8 本文提出的2-邻域模板

首先,每个2-邻域子模板只有3个索引值,每个索引值有5种可能取值(4种基本颜色和1种逃逸色),故而每个2-邻域子模板包含53=125种可能的组合,这个数量仅相当于4-邻域模板的4%.当然,其中也有4/5的模板属于干扰模板,该比例与4-邻域模板相同.

其次,我们统计了19个标准测试序列的第1帧和3幅文字图像中,匹配次数最多的前10个4-邻域模板和前10个2-邻域模板占全部模板的比率,结果如表3所示.从表3可见,约有50%的局部方向预测失败的索引值能够利用前10个2-邻域模板进行预测,而对于前10个4-邻域模板,该比例仅有30%.一方面,该统计结果验证了文献[22]的结论,即边缘反走样在相邻的2个像素之间形成特定的颜色转移模式,使得2-邻域最优匹配模板的比例明显提高;另一方面,由于最佳匹配模板更加集中,其干扰模板所占的平均比例必然降低,基于2-邻域匹配模板的索引预测准确率将得到有效提高.

Table3TheRatioComparisonBetweenTop104-NeighborTemplatesand2-NeighborTemplates
表3匹配最多的前10种4-邻域模板和2-邻域模板所占比例的对比情况

SequenceIndex Numberwith PredictionFailure Most Matched Ratio ∕%4-NeighborTemplate2-NeighborTemplate 12-NeighborTemplate 22-NeighborTemplate 32-NeighborTemplate 4ChinaSpeed1695141.34355.91453.86756.24449.018MissionControlClip35380725.88045.57646.77149.18539.803CAD_Waveform2470024.04046.62344.11747.33231.846Cg_Twist_Tunnel905745.02659.90953.98061.47752.103Console2321632.63357.03447.47651.40441.222Desktop4408728.77352.51447.35952.58041.402FlyingGraphics5451418.51841.31243.48444.04934.663Map4955022.18439.63542.03444.22037.709PCB_Layout2593344.83164.51262.27662.49657.537

Continued(Table3)

SequenceIndex Numberwith PredictionFailure Most Matched Ratio ∕%4-NeighborTemplate2-NeighborTemplate 12-NeighborTemplate 22-NeighborTemplate 32-NeighborTemplate 4PPT_Doc_xls5378151.42366.93365.37668.13460.538Programming1801321.87947.67742.59150.34134.608Video_Conferencing1800222.79742.85648.42244.36232.308Web_Browsing1994318.97443.37443.50943.35432.177WordEditing3106824.22847.86952.44651.52943.460SlideEditing2992518.62342.10542.52044.80532.234SlideShow1100133.11545.88749.74151.50440.860Robot5065045.79361.27958.99561.07458.373VenueVu9606433.69951.54349.92349.59849.467BasketballDrillText1963841.57854.46657.16556.24850.586English Text2676032.17156.51061.36459.48153.714Simplified Chinese3256122.72750.26657.08455.89245.447Traditional Chinese3921619.36746.27255.14151.15041.787Average3402030.43650.91251.16652.56643.676

最后,因为每个2-邻域子模板最多包含125种组合,4个子模板就有500种可能组合,所以若采用3.3节所述的顺序表来实现基于模板匹配的索引预测,那么顺序表只需500条表项,且每条表项只有5列,其空间复杂度为O(500×5),这一复杂度低于多数基于搜索的模板匹配所需的空间代价,对目前几乎所有的计算机系统而言均不构成负担.

4.2基于2-邻域联合转移概率的索引值预测

虽然最佳的2-邻域模板平均占比很高,可是仍然不能避免干扰模板的影响.并且,对于某个局部方向预测失败的索引值x,我们无法有效判定它处于前景物体或文字轮廓的左上部、左下部、右上部还是右下部.故此,本文采用线性加权法计算4个2-邻域子模板的联合转移概率实现对索引x的预测,进而降低干扰模板造成的影响.具体地讲,令PIab表示子模板1(如图8(a)所示)的转移概率(I∈{0,1,2,3,4}),PIcd表示子模板2(如图8(b)所示)的转移概率,PIbc表示子模板3(如图8(c)所示)的转移概率,PIac表示子模板4(如图8(d)所示)的转移概率,则4个子模板同时向索引值“0”的联合转移概率为

(2)

S0=P0←ab+P0←cd+P0←bc+P0←ac.

(3)

同理,4个子模板同时向索引值“1”,“2”,“3”,“4”的联合转移概率分别为

(4)

S1=P1←ab+P1←cd+P1←bc+P1←ac

(5)

(6)

S2=P2←ab+P2←cd+P2←bc+P2←ac

(7)

(8)

S3=P3←ab+P3←cd+P3←bc+P3←ac

(9)

(10)

S4=P4←ab+P4←cd+P4←bc+P4←ac.

(11)

最终,联合转移概率最大的值即为待编码索引x的最佳预测值,即:

(12)

4.3基于联合转移概率的索引值预测步骤

在4.1节和4.2节的基础上,本节给出基于联合转移概率的索引值预测算法的具体预测步骤.

算法1. 基于联合转移概率的索引值预测算法.

输入:待编码视频序列、4个2-邻域子模板对应的转移概率表PIabPIcdPIbcPIac(PIab表结构如表4所示,其余各表与之类似)、序列长度F

输出:索引图的预测误差.

初始化:将转移概率表PIabPIcdPIbcPIac的Times,Transition Probability项均清0.

① 令f=1;

② 利用文献[20]计算得到第f帧的索引图,若f%L=1,则转入步骤③;否则,转入步骤⑦,其中,“%”表示模运算,L为用于调节Markov转移概率表更新频率的预设参数(实验中L=10);

③ 若f=1,则对关键帧进行索引图预测:

④ 对于某个索引值x,采用文献[21]的局部方向预测算法对其进行预测,若算法执行至文献[21]的步骤⑦)(见本文2.1节),表示局部方向预测失败,则转入步骤⑤;否则,转入步骤⑥;

⑤ 利用索引值x及其邻域索引值更新转移概率表PIabPIcdPIbcPIac的相应表项;

⑥ 输出预测误差x-Px,若关键帧的所有索引值都已处理完毕,则转入步骤;否则,返回步骤④;

⑦ 对非关键帧进行索引图预测:

⑧ 对于某个索引值x,采用文献[21]的局部方向预测算法对其进行预测,若算法执行至文献[21]的步骤⑦)(见本文2.1节),则转入步骤⑨;否则,转入步骤⑩;

⑨ 查询转移概率表PIabPIcdPIbcPIac的相应表项,并代入式(2)~(12)中计算Px

⑩ 输出预测误差x-Px,若当前帧的所有索引值都已处理完毕,则转入步骤;否则,返回步骤⑧;

f=f+1,若f>F,则算法结束;否则,转入步骤②.

Table4TheTableStructureofTransitionProbabilityPIab
表4转移概率表PIab的结构

IaIbITimesTransitionProbability000N0←00P0←00001N1←00P1←00︙︙︙︙︙010N0←01P0←01011N1←01P1←01︙︙︙︙︙444N4←44P4←44

5实验与结果

为了验证本文算法的有效性,选用JCT-VC公布的19个标准测试序列的前90帧和3幅包含英文、简体中文和繁体中文的图像进行实验.

所有实验均在各视频帧/图像的亮度分量进行,首先利用文献[20]的算法计算得到亮度分量的索引图,再采用本文算法进行预测并统计预测准确率,同时将结果与MSP[19]算法、局部方向预测算法[21]的预测准确率进行比较.

5.1预测准确率比较

表5给出了本文算法、MSP算法、局部方向预测算法(local directional prediction, LDP)在各个测试序列上得到的预测准确率.对比发现,本文算法对所有测试序列的预测准确率均高于MSP和方向预测方法,分别比两者平均提高4.50%和2.27%.

一方面,Map,Robot,BasketballDrillText,China-Speed这4个视频序列不仅包含字符,还包含由显示适配器生成的大量几何图元,本文算法的预测准确率分别比MSP和方向预测算法提高了9.29%和4.70%.另一方面,对于英文文本、简体中文和繁体中文的纯文本类型图像,本文算法分别比MSP和局部方向预测算法平均提高了8.51%和4.63%.这2类视频序列和图像的共同特点是显示适配器开启了边缘反走样,可见本文算法的2-邻域模板能够比MSP算法的4-邻域模板更加有效地处理屏幕内容在边缘渐变区域的索引值非局部预测.然而,对于平滑区域较多、反走样像素很少甚至未开启反走样的序列(如“PCB_Layout”和“CAD_Waveform”等),局部方向预测已达到很高的准确率,基于2-邻域模板的非局部预测与4-邻域模板基本相当,故此性能提升不如上述序列那么明显.

另外,表5的最后3列分别给出了MSP算法、局部方向预测算法和本文算法在90帧上的预测准确率的平均标准偏差.具体来看,本文算法的预测准确率的平均波动幅度仅是MSP算法的37.5%,是局部方向预测算法的47.37%.所以,本文算法有利于产生更加平稳的预测误差和输出码流.

Table5PredictionAccuracyComparisonAmongVariousAlgorithms
表5不同算法的预测准确率比较

SequencePredictionAccuracy∕%MSPLDPProposedPredictionAccuracy Gainof ProposedAlgorithm overMSP∕%PredictionAccuracy Gainof ProposedAlgorithm overLDP∕%Standard Deviation ofPrediction AccuracyMSPLDPProposedPCB_Layout97.7398.9899.401.67 0.42 0.370.440.21Programming95.8897.1098.302.42 1.20 0.700.510.45WordEditing95.3396.6097.962.63 1.36 1.711.420.91SlideEditing93.7395.1297.373.64 2.25 0.070.060.04FlyingGraphics95.3796.5197.962.59 1.45 0.200.220.12Map87.4093.0395.528.12 2.49 0.890.750.77Video_Conferencing97.0598.0698.911.86 0.85 1.291.070.63Robot88.0893.6696.418.33 2.75 0.180.120.06Web_Browsing95.2196.2197.512.30 1.30 0.860.500.34Cg_Twist_Tunnel97.2898.7499.231.95 0.49 0.420.250.04Console97.6698.5699.161.50 0.60 0.060.040.04Desktop95.5297.1398.342.82 1.21 0.050.020.01PPT_Doc_xls95.9396.9798.622.69 1.65 0.430.310.32BasketballDrillText83.3787.3596.2212.85 8.87 0.240.170.10ChinaSpeed90.4393.5898.297.86 4.71 2.923.030.14MissionControlClip394.4696.2897.893.43 1.61 0.060.030.02CAD_Waveform98.0698.6099.181.12 0.58 0.080.040.03SlideShow97.3998.4099.191.80 0.79 0.820.590.22VenueVu94.9297.3698.653.73 1.29 2.261.200.66English Text89.3892.3496.156.77 3.81 Simplified Chinese83.9290.4495.2311.31 4.79 Traditional Chinese86.3588.5093.817.46 5.31 Average93.2095.4397.704.502.270.720.570.27

5.2时间复杂度比较

需要指出,本文算法仅对2次方向预测失败的索引值才进行2-邻域联合转移概率的预测,其数量约占全部待预测索引值的4.57%.由4.2节和4.3节的论述可知,对于非关键帧中每个局部方向预测失败的索引值,本文算法需首先在转移概率表上进行4次查表操作,取出转移概率PIabPIcdPIbcPIac;然后,将其代入式(2)~(11)计算联合转移概率P(Ix=0),P(Ix=1),P(Ix=2),P(Ix=3),P(Ix=4),由式(2)~(11)的定义,该过程需要20次乘法、20次除法和30次加法;最后,将上述5个联合转移概率代入式(12)计算最大联合转移概率,还需要4次比较运算.故此,本文算法仅用常数次操作即可预测非关键帧的1个索引值,其渐近时间复杂度为O(1).而对于关键帧中每个局部预测方向失败的索引值x,本文算法需先根据x及其邻域索引值abcd对转移概率表PIabPIcdPIbcPIac各执行1次查表操作定位到相应的表项,再各用1次加法、1次除法分别更新表项的Times列和Transition Probability列,显然该过程的时间复杂度也为O(1).综合上述2种情况,本文算法处理1个索引的时间复杂度为O(1),与局部方向预测算法的渐近时间复杂度[21]相同.

同时,由3.2节的分析可知,对于W×H像素的搜索窗口,MSP算法在预测1个索引值时需要匹配W×H个4-邻域模板,且每个模板至多需要4次比较操作,其渐近时间复杂度为O(W×H).从这个意义上讲,本文算法的时间复杂度比MSP降低了W×H倍.

6

本文通过对局部方向预测失败的索引值的4-邻域模板预测结果进行分析,发现4-邻域模板不适合用于刻画边缘反走样区域的颜色转移模式,进而设计了一种2-邻域的匹配模板,并将模板匹配建模为一种可借助查表操作实现的转移概率问题,在此基础上提出一种2-邻域联合转移概率的非局部索引值预测算法.实验结果表明,该算法的预测效率分别比MSP方法和局部方向预测算法平均提高了4.50%和2.27%,并且其计算复杂度明显低于前者,与后者同阶.

参考文献

[1] Lu Yan, Li Shipeng, Shen Huifeng. Virtualized screen: A third element for cloud-mobile convergence[J]. IEEE Multimedia, 2011, 18(2): 4-11

[2]Sanchez V, Aulí-Llinàs F, Serra-Sagristà J. DPCM-based edge prediction for lossless screen content coding in HEVC[J]. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2016, 6(4): 497-507

[3]Liu Dan, Chen Guisheng, Song Chuanming, et al. Research advances in screen content coding methods[J]. Journal of Computer Research and Development, 2017, 54(9): 2059-2076 (in Chinese)

(刘丹, 陈规胜, 宋传鸣, 等. 屏幕内容编码方法研究进展[J].计算机研究与发展, 2017, 54(9): 2059-2076)

[4]Xu Jizheng, Joshi R, Cohen R A. Overview of the emerging HEVC screen content coding extension[J]. IEEE Transactions on Circuits Systems for Video Technology, 2016, 26(1): 50-62

[5]Sun Yuchen, Hsiang S T, Kim J, et al. Improvements of HEVC SCC palette mode and intra block copy[J]. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 2016, 6(4): 433-445

[6]Shen Huifeng, Lu Yan, Wu Feng, et al. Low-cost realtime screen sharing to multiple clients[C] //Proc of the 10th IEEE ICME. Piscataway, NJ: IEEE, 2010: 980-985

[7]Zhu Weijia, Ding Wenpeng, Xu Jizheng, et al. Screen content coding based on HEVC framework[J]. IEEE Transactions on Multimedia, 2014, 16(5): 1316-1326

[8]Xiu Xiaoyu, He Yuwen, Joshi R, et al. Palette-based coding in the screen content coding extension of the HEVC standard[C] //Proc of the 25th IEEE DCC. Piscataway, NJ: IEEE, 2015: 253-262

[9]Zhu Wenjing, Au O C, Dai Wei, et al. Palette-based compound image compression in HEVC by exploiting non-local spatial correlation[C] //Proc of the 39th IEEE ICASSP. Piscataway, NJ: IEEE, 2014: 7348-7352

[10]Ding Wenpeng, Lu Yan, Wu Feng. Enable efficient compound image compression in H.264/AVC intra coding[C] //Proc of the 14th IEEE ICIP. Piscataway, NJ: IEEE, 2007: Ⅱ-337-Ⅱ-340

[11]Lan Cuiling, Shi Guangming, Wu Feng. Compress compound images in H.264/MPGE-4 AVC by exploiting spatial correlation[J]. IEEE Transactions on Image Processing, 2010, 19(4): 946-957

[12]Ma Zhan, Wang Wei, Xu Meng, et al. Advanced screen content coding using color table and index map[J]. IEEE Transactions on Image Processing, 2014, 23(10): 4399-4412

[13]Xu Yiling, Huang Wei, Wang Wei, et al. 2-D index map coding for HEVC screen content compression[C] //Proc of the 25th IEEE DCC. Piscataway, NJ: IEEE, 2015: 263-272

[14]Pu Wei, Karczewicz M, Joshi R, et al. Palette mode coding in HEVC screen content coding extension[J]. IEEE Journal of Emerging and Selected Topics in Circuits and Systems, 2016, 6(4): 420-432

[15]Wang Shuhui, Lin Tao. Compound image compression based on unified LZ and hybrid coding[J]. IET Image Processing, 2013, 7(5): 484-499

[16]JCT-VC. AHG7: Full-chroma (YUV444) dictionary+hybrid dual-coder extension of HEVC, JCTVC-K0133[R]. Geneva, Switzerland: ITU-T, 2012

[17]Li Bin, Xu Jizheng, Wu Feng. 1-D dictionary mode for screen content coding[C] //Proc of the 29th IEEE VCIP. Piscataway, NJ: IEEE, 2014: 189-192

[18]Zhu Weijia, Ding Wenpeng, Xu Jizheng, et al. 2-D dictionary based video coding for screen contents[C] //Proc of the 24th IEEE DCC. Piscataway, NJ: IEEE, 2014: 43-52

[19]Zhu Weijia, Ding Wenpeng, Xiong Ruiqin. Compound image compression by multi-stage prediction[C] //Proc of the 27th IEEE VCIP. Piscataway, NJ: IEEE, 2012: 1-6

[20]Pan Zhaotai, Shen Huifeng, Lu Yan, et al. A low-complexity screen compression scheme for interactive screen sharing[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2013, 23(6): 949-960

[21]Chen Guisheng, Song Chuanming, Wang Xianghai, et al. Fast prediction algorithm of index maps for screen image coding[J]. Journal of Image and Graphics, 2016, 21(9): 1127-1137 (in Chinese)

(陈规胜, 宋传鸣, 王相海, 等. 用于屏幕图像编码的索引图快速预测算法[J].中国图象图形学报, 2016, 21(9): 1127-1137)

[22]Gisquet C, Laroche G, Onno P. Non-RCE4: Transition copy mode for palette mode, JCTVC-P0115[R]. Geneva, Switzerland: ITU-T, 2014SongChuanming, born in 1980. Associate professor of the School of Computer and Information Technology of Liaoning Normal University. Received his PhD degree at the Department of Computer Science & Tech-nology of Nanjing University. Member of CCF. His main research interests include image and video coding, and digital water-marking of multimedia.

IndexMapPredictionby2-NeighborJointTransitionProbabilityinPaletteCoding

Song Chuanming1,2,3, He Xing1, Min Xin1, and Wang Xianghai1

1(SchoolofComputerandInformationTechnology,LiaoningNormalUniversity,Dalian,Liaoning116081)2(SchoolofComputerScienceandTechnology,DalianUniversityofTechnology,Dalian,Liaoning116024)3(StateKeyLaboratoryforNovelSoftwareTechnology(NanjingUniversity),Nanjing210023)

AbstractUsing a 4-neighbor template to perform the nonlocal prediction on the index map is one of typical palette coding techniques. By analyzing the experimental results, it is found that one 4-neighbor template usually has a large number of interference templates and cannot effectively capture the color transition features in the edges’ anti-aliasing area. Therefore, a 2-neighbor template is proposed which includes four subtemplates to represent particular color transition modes of the foreground objects and the text edges at their upper left corners, lower left corners, upper right corners, as well as lower right corners. Meanwhile, the template prediction is further modeled into a transition probability that can be implemented by table lookup operations. An index map prediction method is further addressed using the 2-neighbor joint transition probability. Experimental results show that the prediction accuracy of the proposed method is 97.70%, which is separately 4.50% and 2.27% higher than that of the multi-stage prediction (MSP) method and that of the local directional prediction (LDP) method. It is especially suitable for the complex screen content coding with a large number of characters and computer-generated geometrical primitives. Moreover, the computational complexity of the proposed method is equivalent to that of the LDP method, and obviously lower than that of the MSP. The proposed method can be applied into the palette-index map based screen content predictive coding with high real-time demand.

Keywordsvideo coding; screen content coding; palette coding; index map prediction; transition probability

中图法分类号TN911.73;TP37

基金项目国家自然科学基金项目(61402214,41671439);高等学校博士学科点专项科研基金项目(20132136110002);辽宁省教育厅科学研究一般项目(L201683681);大连市青年科技之星项目支持计划项目(2015R069);计算机软件新技术国家重点实验室(南京大学)开放基金项目(KFKT2018B07)This work was supported by the National Natural Science Foundation of China (61402214, 41671439), the Specialized Research Fund for the Doctoral Program of Higher Education of China (20132136110002), the Foundation of Science and Research for Liaoning Provincial Education Department (L201683681), the Dalian Foundation for Youth Science and Technology Star (2015R069), and the Open Foundation of State Key Laboratory for Novel Software Technology (Nanjing University) (KFKT2018B07)

修回日期:2018-03-16

收稿日期2017-04-07;

HeXing, born in 1990. Received his master degree at the School of Computer and Information Technology of Liaoning Normal University. His main research interest includes educational video coding (hexing953663854@qq.com).

MinXin, born in 1992. Received his master degree at the School of Computer and Information Technology of Liaoning Normal University. His main research interest includes video coding (hy_minxin@126.com).

WangXianghai, born in 1965. Professor and PhD supervisor of the School of Computer and Information Technology of Liaoning Normal University. Senior member of CCF. His main research interests include computer graphics and multimedia information processing (xhwang@lnnu.edu.cn).