计算机研究与发展ＤＯＩ：１０．７５４４ｉｓｓｎ１０００－１２３９．２０１６．２０１４８４５５Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ ５３（４）：８７３－８８３，２０１６
张 峻１，２ 代 锋１ 马宜科１ 张勇东１
１（中国科学院智能信息处理重点实验室（中国科学院计算技术研究所） 北京 １００１９０）
２（中国科学院大学 北京 １０００４９）
（ｚｈａｎｇｊｕｎ０１＠ｉｃｔ．ａｃ．ｃｎ）
Ｍｕｌｔｉ－Ｌｅｖｅｌ ａｎｄ Ｆｉｎｅ－Ｇｒａｉｎｅｄ Ｐａｒａｌｌｅｌ ＨＥＶＣ Ｉｎｔｒａ Ｍｏｄｅ Ｄｅｃｉｓｉｏｎ Ｍｅｔｈｏｄ
Ｚｈａｎｇ Ｊｕｎ１，２，Ｄａｉ Ｆｅｎｇ１，Ｍａ Ｙｉｋｅ１，ａｎｄ Ｚｈａｎｇ Ｙｏｎｇｄｏｎｇ１
１（Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｉｎｔｅｌｌｉｇｅｎｔ Ｉｎｆｏｒｍａｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ（Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｃｏｍｐｕｔｉｎｇ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆＳｃｉｅｎｃｅｓ），Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１００１９０）
２（Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ，Ｂｅｉｊｉｎｇ１０００４９）
Ａｂｓｔｒａｃｔ Ｔｈｅ ｃｏｄｉｎｇ ｍｏｄｅ ｓｐａｃｅ ｏｆ ｈｉｇｈ ｅｆｆｉｃｉｅｎｃｙ ｖｉｄｅｏ ｃｏｄｉｎｇ（ＨＥＶＣ）ｉｓ ｅｘｔｒｅｍｅｌｙ ｌａｒｇｅ ｓｏ ｉｔｎｅｅｄｓ ｈｕｇｅ ａｍｏｕｎｔ ｏｆ ｃｏｍｐｕｔａｔｉｏｎｓ ｆｏｒ ＨＥＶＣ ｅｎｃｏｄｅｒｓ ｔｏ ｄｏ ｍｏｄｅ ｄｅｃｉｓｉｏｎ（ＭＤ）．ＰａｒａｌｌｅｌｉｚｉｎｇＨＥＶＣ ｅｎｃｏｄｉｎｇ ｏｎ ｍａｎｙ－ｃｏｒｅ ｐｌａｔｆｏｒｍｓ ｉｓ ａｎ ｅｆｆｉｃｉｅｎｔ ａｎｄ ｐｒｏｍｉｓｉｎｇ ａｐｐｒｏａｃｈ ｔｏ ｆｕｌｆｉｌｌ ｔｈｅ ｈｉｇｈｃｏｍｐｕｔａｔｉｏｎａｌ ｄｅｍａｎｄｓ．Ｔｒａｄｉｔｉｏｎａｌ ｃｏａｒｓｅ－ｇｒａｉｎｅｄ ｐａｒａｌｌｅｌｉｚｉｎｇ ｓｃｈｅｍｅｓ ｓｕｃｈ ａｓ Ｔｉｌｅｓ ａｎｄ ｗａｖｅｆｒｏｎｔｐａｒａｌｌｅｌ ｐｒｏｃｅｓｓｉｎｇ（ＷＰＰ）ｅｉｔｈｅｒ ｃａｕｓｅ ｔｏｏ ｍｕｃｈ ｑｕａｌｉｔｙ ｌｏｓｓ ｏｒ ｃａｎ’ｔ ａｆ
ｆｏｒｄ ａ ｈｉｇｈ ｐａｒａｌｌｅｌｉｓｍ ｄｅｇｒｅｅ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｔｈｅ ｐｏｔｅｎｔｉａｌ ｐａｒａｌｌｅｌｉｓｍ ｉｎ ＨＥＶＣ ｉｎｔｒａ ＭＤ ｐｒｏｃｅｓｓ ｉｓ ｅｘｐｌｏｉｔｅｄ，ａｎｄ ａ ｍｕｌｔｉ－ｌｅｖｅｌ ａｎｄｆｉｎｅ－ｇｒａｉｎｅｄ ｈｉｇｈｌｙ ｐａｒａｌｌｅｌ ｉｎｔｒａ ＭＤ ｍｅｔｈｏｄ ｗｈｉｃｈ ｗｏｒｋｓ ｉｎ ａ ｃｏｄｉｎｇ ｔｒｅｅ ｕｎｉｔ（ＣＴＵ）ｉｓ ｐｒｏｐｏｓｅｄ．Ｓｐｅｃｉｆｉｃａｌｌｙ，ｔｈｅ ｉｎｔｒａ ＭＤ ｐｒｏｃｅｓｓ ｉｎ ａ ＣＴＵ ｉｓ ｄｉｖｉｄｅｄ ｉｎｔｏ ｓｉｘ ｔｙｐｅｓ ｏｆ ｓｕｂ－ｔａｓｋｓ，ａｎｄ ｔｈｅ ｄａｔａｄｅｐｅｎｄｅｎｃｉｅｓ ａｍｏｎｇ ａｄｊａｃｅｎｔ ｂｌｏｃｋｓ ｔｈａｔ ｈｉｎｄｅｒ ｐａｒａｌｌｅｌ ｐｒｏｃｅｓｓｉｎｇ ａｒｅ ａｎａｌｙｚｅｄ ａｎｄ ｒｅｍｏｖｅｄ，ｉｎｃｌｕｄｉｎｇ ｉｎｔｒａ ｐｒｅｄｉｃｔｉｏｎ ｄｅｐｅｎｄｅｎｃｙ，ｐｒｅｄｉｃｔｉｏｎ ｍｏｄｅ ｄｅｐｅｎｄｅｎｃｙ ａｎｄ ｅｎｔｒｏｐｙ ｃｏｄｉｎｇ ｄｅｐｅｎｄｅｎｃｙ；ｃｏｎｓｅｑｕｅｎｔｌｙ ｔｈｅ ＭＤ ｃｏｍｐｕｔａｔｉｏｎ ｆｏｒ ａｌｌ ｆｉｎｅ－ｇｒａｉｎｅｄ ｃｏｄｉｎｇ ｂｌｏｃｋｓ ｏｆ ｄｉｆｆｅｒｅｎｔ ｌｅｖｅｌｓ ｗｉｔｈｉｎ ｔｈｅ ｓａｍｅＣＴＵ ｃａｎ ｂｅ ｃｏｍｐｕｔｅｄ ｃｏｎｃｕｒｒｅｎｔｌｙ．Ｔｈｅ ｐｒｏｐｏｓｅｄ ｐａｒａｌｌｅｌ ＭＤ ｍｅｔｈｏｄ ｉｓ ｉｍｐｌｅｍｅｎｔｅｄ ｏｎ Ｔｉｌｅ－Ｇｘ３６ｐｌａｔｆｏｒｍ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｅ ｐｒｏｐｏ
ｓｅｄ ｐａｒａｌｌｅｌ ＭＤ ｍｅｔｈｏｄ ｇｅｔｓ ａｎ ｏｖｅｒａｌｌ ｓｐｅｅｄ ｕｐ ｏｆｍｏｒｅ ｔｈａｎ １８ｘｗｉｔｈ ａｃｃｅｐｔａｂｌｅ ｑｕａｌｉｔｙ ｌｏｓｓ（ａｂｏｕｔ ３％ｂｉｔ－ｒａｔｅ ｉｎｃｒｅａｓｉｎｇ），ｃｏｍｐａｒｅｄ ｗｉｔｈ ｔｈｅ ｎｏｎ－
ｐａｒａｌｌｅｌ ｂａｓｅｌｉｎｅ ＨＭ．
Ｋｅｙ ｗｏｒｄｓ ｈｉｇｈ ｅｆｆｉｃｉｅｎｃｙ ｖｉｄｅｏ ｃｏｄｉｎｇ（ＨＥＶＣ）；ｉｎｔｒａ ｐｒｅｄｉｃｔｉｏｎ；ｍａｎｙ－ｃｏｒｅ；ｐａｒａｌｌｅｌ ｍｏｄｅ ｄｅｃｉｓｉｏｎ；ｆｉｎｅ－ｇｒａｉｎｅｄ
交通流摘 要 在众核平台上并行加速是解决高效视频编码（ｈｉｇｈ ｅｆｆｉｃｉｅｎｃｙ ｖｉｄｅｏ ｃｏｄｉｎｇ，ＨＥＶＣ）标准编码复杂度高的有效方法．传统的粗粒度并行方案如Ｔｉｌｅｓ和ＷＰＰ未能在并行度和编码质量之间取得较好的平衡，对编码质量影响较大或者并行度不高．充分挖掘ＨＥＶＣ帧内模式选择中的并行性，提出了一种在ＣＴＵ内使用的多层次细粒度的帧内模式选择算法．具体说来，对帧内模式选择过程进行了子任务划分，分析并消除了相邻编码块之间多种阻碍并行计算的数据依赖关系，包括帧内预测参考像素依赖、预测模式依赖和熵编码依赖等，实现了同一个ＣＴＵ内所有层次的细粒度编码块的代价计算和模式选择并行进行．将算法在Ｔｉｌｅ－Ｇｘ３６平台上实现，实验结果表明此并行算法与ＨＥＶＣ参考代码ＨＭ相比能获得 １８倍的整体编码加速比而且编码质量损失较小（码率上升３％）．
收稿日期：２０１４－１２－３１；修回日期：２０１５－０４－２７
基金项目：国家自然科学基金项目（６１３７９０８４，６１４０２４４０）；中国科学院科研装备研制项目（ＹＺ２０１３２１）
Ｔｈｉｓ ｗｏｒｋ ｗａｓ ｓｕｐｐｏｒｔｅｄ ｂｙ ｔｈｅ Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ（６１３７９０８４，６１４０２４４０）ａｎｄ ｔｈｅ ＩｎｓｔｒｕｍｅｎｔＤｅｖｅｌｏｐｉｎｇ Ｐｒｏｊｅｃｔ ｏｆ ｔｈｅ Ｃｈｉｎｅｓｅ Ａｃａｄｅｍｙ ｏｆ Ｓｃｉｅｎｃｅｓ（ＹＺ２０１３２１）．
关键词 高效视频编码；帧内预测；众核；并行模式选择；细粒度中图法分类号 ＴＰ３９１
高效视频编码（ｈｉｇｈ ｅｆｆｉｃｉｅｎｃｙ ｖｉｄｅｏ ｃｏｄｉｎｇ，ＨＥＶＣ）［１－２］标准的压缩效率超越以往所有标准，比目前最流行的Ｈ．２６４ＡＶＣ提高１倍．虽然ＨＥＶＣ仍然属于基于块的混合编码框架，但是其各个编码阶段都有了增强和改进，其中最重要的变化就是采用了更加灵活的编码结构和高级的编码工具，这也导致ＨＥＶＣ的编码模式搜索空间非常大．为了保证编码质量，编码器要进行大量的计算以寻率失真代价较小的编码模式，即模式选择（ｍｏｄｅ
仪器仪表学报ｄｅｃｉｓｉｏｎ，ＭＤ），编码复杂度非常高．随着多核和众核处理器的发展［３］，在并行计算平台上并行化ＨＥＶＣ编码将是满足其计算能力需求实现实时编码的有效手段［４－１２］．与以往所有标准不同，ＨＥＶＣ标准本身就采纳了多种便于并行编解码的工具，如ＷＰＰ（ｗａｖｅｆｒｏｎｔ ｐａｒａｌｌｅｌｐｒｏｃｅｓｓｉｎｇ）［９］，Ｔｉｌｅｓ［１０］，ＭＥＲ（ｍｏｔｉｏｎ ｅｓｔｉｍａｔｉｏｎｒｅｇｉｏｎ）［１１］，可见并行计算对于ＨＥＶＣ及今后视频编码领域的重要性．
目前ＨＥＶＣ并行相关的研究工作主要集中于计算量较大的帧间ＭＤ尤其是运动估计（ｍｏｔｉｏｎｅｓｔｉｍａｔｉｏｎ，ＭＥ）模块［７－８，１１］，对帧内ＭＤ并行的研究则相对较少．随着帧间ＭＤ的并行化，帧内ＭＤ逐渐成为了速度瓶颈．在文献［１３］中，在帧间ＭＤ被加速了近１５倍之后，Ｉ帧的平均编码时间大大超过了ＰＢ帧的平均编码时间，是其４～５倍，限制了编码器的整体效率，因此对帧内ＭＤ的并行加速同样重要．
现有的对ＨＥＶＣ帧内ＭＤ并行的研究较少，而且算法的并行度不够高［１４－１６］，ＨＥＶＣ标准支持的Ｔｉｌｅｓ和ＷＰＰ也未能在并行度和编码质量取得较好的平衡．针对这些问题，本文提出了一种在编码树单元（ｃｏｄｉｎｇ ｔｒｅｅ ｕｎｉｔ，ＣＴＵ）内使用的并行帧内ＭＤ算法：本文对帧内ＭＤ过程进行了子任务划分，深入分析并解除了各个子任务在相邻编码块之间存在的数据依赖性，包括帧内预测参考像素依赖、ＰＵ预测模式依赖、熵编码概率模型依赖和概率建模依赖，实
现了每个子任务对整个ＣＴＵ里面多层次细粒度的编码块并行处理，最终实现了ＣＴＵ内并行帧内ＭＤ．
１ 背景及研究现状
本节介绍与本文工作相关的一些背景．首先介绍ＨＥＶＣ帧内模式选择基本概念，然后对已有的一些并行帧内模式选择算法进行了介绍和分析．１．１ ＨＥＶＣ帧内模式选择
在ＨＥＶＣ编码标准中，一帧视频图像被均匀地划分成ＣＴＵ，ＣＴＵ的大小可以为６４×６４，３２×３２或１６×１６，典型且不失一般性，本文以下默认ＣＴＵ大小为６４×６４．如图１所示，每一个ＣＴＵ四叉树递归地划分为４个相同大小的子单元，该四叉树的每一个叶子节点叫作一个编码单元（ｃｏｄｉｎｇ ｕｎｉｔ，ＣＵ）；每个ＣＵ也会采用四叉树递归划分，每一个叶子节点叫作变换单元（ｔｒａｎｓｆｏｒｍ ｕｎｉｔ，ＴＵ）．此外，从图１可见，每个ＣＵ有多种预测单元（ｐｒｅｄｉｃｔｉｏｎ ｕｎｉｔ，ＰＵ）划分模式，能更灵活地进行预测编码．ＨＥＶＣ的帧内预测模式也比Ｈ．２６４复杂很多，共３５种模式．ＣＴＵ，ＣＵ，ＰＵ，ＴＵ包含的单一亮度或度分量信息分别记为ＣＴＢ（ｃｏｄｉｎｇ ｔｒｅｅ ｂｌｏｃｋ），ＣＢ（ｃｏｄｉｎｇｂｌｏｃｋ），ＰＢ（ｐｒｅｄｉｃｔｉｏｎ ｂｌｏｃｋ），ＴＢ（ｔｒａｎｓｆｏｒｍ ｂｌｏｃｋ）
．
Ｆｉｇ．１ Ｆｌｅｘｉｂｌｅ ｃｏｄｉｎｇ ｓｔｒｕｃｔｕｒｅｓ ｉｎ ＨＥＶＣ．
图１ ＨＥＶＣ标准中灵活的编码结构
在ＨＥＶＣ帧内ＭＤ过程中，对于一个ＣＴＵ来说，它可以采用四叉树递归划分的方式划分出更小的ＣＵ，最小为８×８．对于８×８ＣＵ有２ Ｎ×２ Ｎ和Ｎ×Ｎ两种ＰＵ划分方式，其他ＣＵ只有２ Ｎ×２ Ｎ的ＰＵ划分．Ｎ×Ｎ划分情况下包含４个亮度ＰＢ和１个度ＰＢ，２ Ｎ×２ Ｎ划分时包含１个亮度ＰＢ和１个度ＰＢ，每个ＰＢ有一个预测模式．对一个帧内编码ＣＵ来说，度ＰＢ和亮度ＰＢ的预测模式可以是不同的，ＴＵ划分模式对亮度和度是相同的，因此一个帧内编码ＣＵ的模式可由亮度ＰＢ预测模式、度ＰＢ预测模式和ＴＵ划分模式来表征，如式（１）所示．帧内ＭＤ即对ＣＴＵ里面的每个ＣＵ从式（１）
４
７
８计算机研究与发展 ２０１６，５３（４）
所表示的模式空间中寻率失真代价最小的模式组合，并且据此决策出整个ＣＴＵ的最佳ＣＵ四叉树划分方式．在ＨＥＶＣ的参考软件ＨＭ中，一个ＣＴＵ里面ＣＵ的ＭＤ计算是按深度优先遍历顺序进行的，如图２所示，为简便起见只画了３层，每个节点表示一个ＣＵ．
ＣＵ
模式（亮度ＰＢ预测模式，度ＰＢ预测模式，
ＴＵ划分模式）．（１
）
Ｆｉｇ．２ Ｄｅｐｔｈ－ｆｉｒｓｔ ｓｅｒｉａｌ ｐｒｏｃｅｓｓｉｎｇ ｏｒｄｅｒ ｏｆ
ＣＵｓ ｉｎ ａ ＣＴＵ ｏｆ ＨＭ．
图２ ＨＭ中一个ＣＴＵ里ＣＵ的深度优先串行处理顺序
１．２ 相关研究工作
由于采用了灵活的编码结构和复杂的预测模
式，帧内ＭＤ计算量非常大．为了加快帧内ＭＤ，许
多研究工作［１７－１９］提出了快速算法．快速算法能在一
瑞利数
定程度上减小计算复杂度，但是获得的加速比有限，
距离实时编码仍然有很大的差距．
并行计算是提高ＨＥＶＣ编码速度的有效手段，
标准本身采纳了几种粗粒度的并行化工具．Ｔｉｌｅｓ将
一帧图像纵横划分成若干可以独立进行编码的子图
像，子图像之间无依赖关系，所以可以并行处理．
Ｔｉｌｅｓ划分对并行编码比较容易实现且并行度比较
灵活，缺点是对编码效率影响较大，经测试［２０］，将
１０８０ｐ的视频均匀划分成６×３的Ｔｉｌｅｓ用于帧内
ＭＤ，在ｉｎｔｒａ＿ｍａｉｎ配置下实际平均加速比为１２，
ＢＤＢＲ［２１］达到５％左右．ＨＥＶＣ采用的另一种并行
方案为ＷＰＰ，由于其尽可能地保持了数据依赖关
系，所以对编码质量影响较小，但是并行度却不高．
对一个宽度为Ｗ个ＣＴＵ、高度为Ｈ个ＣＴＵ的视
频帧来说，如果满足条件２（Ｈ－α－１）＜Ｗ≤２（Ｈ－
α），其中α∈Ｎ且１≤α＜Ｈ，其理论并行度
（ｔｈｅｏｒｅｔｉｃａｌ ｐａｒａｌｌｅｌｉｓｍ ｄｅｇｒｅｅ，ＴＰＤ）为
ＴＰＤ（Ｗ，Ｈ，α）＝
ＷＨ
２Ｗ＋２α－２
，（２）
对于７２０ｐ和１０８０ｐ的视频序列满足α＝２，所以
姚明慈善赛直播
１０８０ｐ的视频ＴＰＤ只能到８［２２］．
在另外一些并行帧内ＭＤ的研究中，文献［１４－
赤祼羔羊１５］都使用前向无环图描述ＣＴＵ之间的依赖关系，
实现了ＣＴＵ之间的并行处理，但本质仍属于ＷＰＰ，
文献［１４］平均获得了５倍的加速比，文献［１５］则使
用分类器决策出最佳ＣＴＵ的大小，通过较小的ＣＴＵ
大小能获得较高的加速比，平均达到１０倍．在文献
［１６］中，该文作者提出了一种在ＴＵ四叉树划分时
４个子节点并行帧内预测的算法，但是由于帧内预
测仍依赖于重构像素，理论并行度只能达到４．
从以上内容可以看出，现有的帧内ＭＤ并行算
法主要是粗粒度并行（Ｔｉｌｅｓ，ＷＰＰ），文献［１６］属于
细粒度并行但是并行度不高．针对它们存在的问题，
本文提出了一种在ＣＴＵ内使用的多层次细粒度的
并行帧内ＭＤ算法，在保证编码质量的前提下获得
了更高的并行度．多层次体现在不同深度的ＣＵ，
ＰＵ，ＴＵ可以并行处理，细粒度则体现在最小计算
单元为一个ＴＢ．
２ 多层次细粒度并行帧内模式选择
本节提出了一种在ＣＴＵ内使用的多层次细粒
度并行帧内ＭＤ算法．本文首先对ＣＵ帧内ＭＤ过
程进行了子任务划分，深入分析并解除了各个子任
务在相邻ＣＵ，ＰＵ，ＴＵ间存在的数据依赖关系，实
现了各个子任务在整个ＣＴＵ范围的并行处理，最
终实现了各个层次的所有ＣＵ并行模式选择．
２．１ 子任务划分
对于一个ＣＵ的模式选择，为了减小计算量，
ＨＭ对式（１）表示的模式空间的搜索分阶段进行，先
选择亮度ＰＢ预测模式，然后选择ＴＵ划分模式，再
选择度ＰＢ的预测模式，如图３所示．
对于亮度ＰＢ预测模式选择，先对所有３５种模
式进行代价粗算（ｒｏｕｇｈ ｍｏｄｅ ｃｏｓｔ ｃｏｍｐｕｔａｔｉｏｎ，
ＲＭＣＣ），代价记作ＲＭＣ，包括ＰＢ预测值与原始值
５
７
８
张 峻等：多层次细粒度并行ＨＥＶＣ帧内模式选择算法
Ｆｉｇ．３ Ｔｈｅ ｆｌｏｗｃｈａｒｔ ｏｆ ｉｎｔｒａ ＭＤ ｆｏｒ ａ ＣＵ ｉｎ ＨＭ
ｅｎｃｏｄｅｒ．
图３ ＨＭ编码器中对一个ＣＵ的帧内ＭＤ流程图
之间的残差变换绝对值（ｓｕｍ ｏｆ ａｂｓｏｌｕｔｅ ｔｒａｎｓｆｏｒｍｅｄｄｉｆｆｅｒｅｎｃｅｓ，ＳＡＴＤ）和预测模式编码位数，从中选择一定数量ＲＭＣ最小的预测模式，与当前ＰＢ的最可能预测模式（ｍｏｓｔ ｐｒｏｂａｂｌｅ ｍｏｄｅ，ＭＰＭ）一起构造候选模式列表（ｃａｎｄｉｄａｔｅ ｍｏｄｅ ｌｉｓｔ ｃｏｎｓｔｒｕｃｔｉｏｎ，ＣＭＬＣ），记作ＣＭＬ，对ＣＭＬ里的每一个模式都去计算率失真代价（ｐｒｅｄｉｃｔｉｏｎ ｍｏｄｅ ｃｏｓｔ ｃｏｍｐｕｔａｔｉｏｎ，ＰＭＣＣ），代价记作ＰＭＣ，选择ＰＭＣ最小的预测模式作为当前ＰＢ的最佳预测模式（ＰＢ ｂｅｓｔ ｐｒｅｄｉｃｔｉｏｎｍｏｄｅ ｓｅｌｅｃｔｉｏｎ，ＰＢＢＰＭＳ），记作ＰＢＢＰＭ．然后对ＴＵ划分模式进行决策，主要计算量是亮度ＴＢ的率失真代价计算（ＴＢ ｃｏｓｔ ｃｏｍｐｕｔａｔｉｏｎ，ＴＢＣＣ），代价记作ＴＢＣ，使用ＴＢＣ进行ＴＵ四叉树决策（ｑｕａｄ－ｔｒｅｅ ｄｅｃｉｓｉｏｎ，ＱＴＤ）．最后选择度预测模式，主要计算是度ＴＢ的ＴＢＣＣ计算．为便于后续引用，在表１对上述子任务以及相应的计算结果进行了归纳．
Ｔａｂｌｅ １ Ｓｕｂ－Ｔａｓｋｓ ａｎｄ Ｔｈｅｉｒ Ｏｕｔｐｕｔ Ｒｅｓｕｌｔｓ
表１ 子任务划分和相应的输出结果
Ｎａｍｅ ｏｆ Ｓｕｂ－Ｔａｓｋｓ Ａｂｂｒｅｖｉａｔｉｏｎ ＲｅｓｕｌｔＲｏｕｇｈ Ｍｏｄｅ Ｃｏｓｔ Ｃｏｍｐｕｔａｔｉｏｎ ＲＭＣＣ ＲＭＣ
Ｃａｎｄｉｄａｔｅ Ｍｏｄｅ Ｌｉｓｔ Ｃｏｎｓｔｒｕｃｔｉｏｎ ＣＭＬＣ ＣＭＬ
Ｐｒｅｄｉｃｔｉｏｎ Ｍｏｄｅ Ｃｏｓｔ Ｃｏｍｐｕｔａｔｉｏｎ ＰＭＣＣ ＰＭＣ
ＰＢ Ｂｅｓｔ Ｐｒｅｄｉｃｔｉｏｎ Ｍｏｄｅ Ｓｅｌｅｃｔｉｏｎ ＰＢＢＰＭＳ ＰＢＢＰＭＴＢ Ｃｏｓｔ Ｃｏｍｐｕｔａｔｉｏｎ ＴＢＣＣ ＴＢＣ
Ｑｕａｄ－Ｔｒｅｅ Ｄｅｃｉｓｉｏｎ ＱＴＤ Ｃｏｍｐｌｅｔｅ ＭＤ 如图２所示，在串行帧内ＭＤ时，由于ＣＵ的ＭＤ计算是按照深度优先遍历顺序去串行进行的，所以对于表１中的每个子任务，在串行ＭＤ时它们在ＣＴＵ范围内的执行路径也是按四叉树深度优先遍历顺序去进行的．本文提出的并行算法将每个子任务在ＣＴＵ范围内进行多层次细粒度的并行，每个子任务都能并行处理一个ＣＴＵ里面的所有ＣＵ，ＰＵ或ＴＵ，即并行处理四叉树中的所有节点，一个节点对于不同的子任务表示一个ＣＵ，ＰＵ或ＴＵ．２．２ 数据依赖性分析与消除
对于每个子任务，要在一个ＣＴＵ范围内进行并行ＭＤ计算，而相邻块之间有多种数据依赖关系，这
些数据依赖会阻碍子任务在ＣＴＵ范围内的并行计算．经过本文的分析，有４种数据依赖需要解除：１）帧内预测时重构像素依赖．此依赖关系出现在帧内预测时，如图４所示，在一个ＰＢ或ＴＢ进行代价计算时，需要进行帧内预测，即参考相邻块已经重构出来的像素对自身进行预测．对于一个Ｍ×Ｍ的ＴＢ来说，需要参考周围的４ Ｍ＋１个重构像素，分别来自于其左、上、左下、右上和左上方向已经编码重构完成的相邻图像区域
．
Ｆｉｇ．４ Ｒｅｃｏｎｓｔｒｕｃｔｅｄ ｐｉｘｅｌｓ ｄｅｐｅｎｄｅｎｃｉｅｓ ｄｕｒｉｎｇ ｉｎｔｒａｐｒｅｄｉｃｔｉｏｎ．
图４ 帧内预测时重构像素依赖
在本文的并行算法中，ＲＭＣＣ，ＰＭＣＣ，ＴＢＣＣ在一个ＣＴＵ里面要对所有ＰＢ或ＴＢ并行进行代价计算，需要进行帧内预测，如果一个ＰＢ或ＴＢ要参考的重构像素跟它位于同一个ＣＴＵ，那么重构像素是不可用的，因为相邻块也同时在进行模式选择，并未重构完成．如图４所示，ｂｌｏｃｋＬ，ｂｌｏｃｋＡ和当前块位于同一个ＣＴＵ进行并行处理，那么当前块所依赖的ｂｌｏｃｋＬ和ｂｌｏｃｋＡ的重构像素不可用．要想并行计算，帧内预测参考像素的依赖关系必须要解除．为了解除这种相关性，本文提出使用原始像素代替重构像素进行帧内预测．为了更准确地模拟实际的编码过程，在对一个ＰＢ或ＴＢ进行参考像素构造
６
７
８计算机研究与发展 ２０１６，５３（４）
的过程中，虽然所有原始像素都是可用的，但依然按照标准遵循Ｚ扫描顺序来决定某一个像素是不是可用，对于不可用的像素则调用替换（ｓｕｂｓｔｉｔｕｔｉｏｎ）过程去生成．另外，对参考像素的滤波操作也同样按照标准进行．由于原始像素是始终可用的，相邻ＰＢ或ＴＢ之间不会再有重构像素的依赖问题，所以同一个ＣＴＵ里面所有ＰＢ和ＴＢ都可以并行地进行帧内预测．
２
）编码预测模式时ＭＰＭ计算依赖．为了提高压缩效率，ＨＥＶＣ在编码帧内预测模式时需要参考相邻（左边和上边）ＰＢ的预测模式，构造出一个长度固定为３的ＭＰＭ列表，如图５（ａ）所示．如果左ＰＢ（ｌｅｆｔ ＰＢ，ＬＰＢ）和上ＰＢ（ａｂｏｖｅ ＰＢ，ＡＰＢ）的预测模式不可用或者相同，则还会加入ＤＣ、ｐｌａｎａｒ、垂直、水平等模式．令（ｘｃ，ｙｃ）表示当前ＰＢ的左上角在当前图像帧中的坐标，ＬＰＢ定义为覆盖点Ｌ（ｘｃ－１，ｙｃ）的ＰＢ，ＡＰＢ定义为覆盖点Ａ（ｘｃ，ｙｃ－
１）的ＰＢ
．Ｆｉｇ．５ Ｐｒｅｄｉｃｔｉｏｎ ｍｏｄｅ ｄｅｐｅｎｄｅｎｃｙ ａｍｏｎｇ ａｄｊａｃｅｎｔＰＵｓ ａｎｄ ｔｈｅ ｐｒｏｐｏｓｅｄ ｄｅｐｅｎｄｅｎｃｙ ｒｅｍｏｖｉｎｇ ｍｅｔｈｏｄ．图５ 相邻Ｐ
Ｕ预测模式依赖和本文提出的依赖性消除方法在本文的并行算法中，ＲＭＣＣ，ＣＭＬＣ，ＰＭＣＣ要对ＣＴＵ内所有ＰＢ并行地进行ＭＰＭ计算，如果当前ＰＢ与参考的ＬＰＢ或ＡＰＢ位于同一个ＣＴＵ
里面，即如式（３）所示，其中（ｘｎ，ｙｎ）对于ＬＰＢ或ＡＰＢ分别为（ｘｃ－１，ｙｃ）或（ｘｃ，ｙｃ－
１），那么ＬＰＢ和ＡＰＢ的预测模式是不可用的，因为它们也同时在进行模式选择，预测模式还未得到．
为了解除此依赖关系，如果当前ＰＢ和ＬＰＢ或ＡＰＢ位于同一个ＣＴＵ，那么本文使用已经编码过的ＣＴＵ里面距离ＬＰＢ和ＡＰＢ最近的对应ＰＢ来代替
它，记作ＬＰＢ′和ＡＰＢ′，如图５（ｂ）所示，用ＬＰＢ′和ＡＰＢ′的预测模式代替ＬＰＢ和ＡＰＢ的预测模式去构
造ＭＰＭ．ＬＰＢ′定义为覆盖点Ｌ′（ｘｃ－ｘｃ％６４－１，ｙｃ）
的ＰＢ，ＡＰＢ′定义为覆盖点Ａ′（ｘｃ，ｙｃ－ｙｃ％６
４－１）的ＰＢ，其中“％”表示取余运算，６４表示ＣＴＵ大小．由于ＣＴＵ是按照扫描顺序进行编码的，所以左ＣＴＵ和上ＣＴＵ里面的信息一定是可以使用的，这样，同一个ＣＴＵ里面ＰＵ的预测模式依赖关系就被解除了，
可以并行进行预测以及代价计算：ｘｎ６４＝＝ｘｃ６４＆＆ｙｎ６４＝＝ｙｃ
６４
．（３
）３）概率模型（ｃｏｎｔｅｘｔ ｍｏｄｅｌ，ＣＭ）继承依赖．ＨＥＶＣ中使用上下文自适应的二进制算术编码（ｃｏｎｔｅｘｔ ａｄａｐｔｉｖｅ ｂｉｎａｒｙ ａｒｉｔｈｍｅｔｉｃ ｃｏｄｉｎｇ，ＣＡＢＡＣ）进行语法元素的熵编码．ＣＡＢＡＣ的主要过程包括语法元素的二进制化、
概率建模、算术编码和ＣＭ更新．为了提高编码效率，在编码的过程中ＣＭ会自适应动态更新，以更
好地反映图像的局部区域特性，获得更高的压缩比．在ＨＭ模式选择过程中，熵编码器会使用ＣＭ去估计编码产生的位数以计算编码代价，ＣＭ是模拟实际编码过程动态更新的，Ｚ扫描顺序更小的块的ＭＤ完成之后会将ＣＭ传递给Ｚ扫描顺序大于它的块使用，如图６（ａ）所示，ＴＵ１使用的ＣＭ是ＴＵ０计算之后的结果，这样就在相邻块之间产生了ＣＭ的继承依赖
．
Ｆｉｇ．６ ＣＭｓ ｉｎｈｅｒｉｔａｎｃｅ ｉｎ ＨＭ ａｎｄ ｏｕｒ ｐｒｏｐ
ｏｓｅｄ ｍｅｔｈｏｄ．图６ ＨＭ中的ＣＭ继承依赖和本文提出的方法
在本文的并行算法中，ＲＭＣＣ，ＰＭＣＣ，ＴＢＣＣ，ＱＴＤ任务要并行地对一个ＣＴＵ内的所有ＣＵ，ＰＵ或ＴＵ进行代价计算，而由于相邻ＣＵ，ＰＵ，ＴＵ之间存在ＣＭ的继承依赖问题而导致无法并行，要想实现并行代价计算，必须要解决此依赖关系．
为了解除同一个ＣＴＵ内ＣＭ继承依赖，本文提出以下解决方法：同一个ＣＴＵ内的所有ＣＵ?ＰＵ?ＴＵ使用同一套ＣＭ，
该ＣＭ来自于上一个已编码的ＣＴＵ经过训练之后的结果．如图６（ｂ）所示，为了简洁，一个ＣＴＵ内只画出４个ＴＵ．通过这种ＣＭ继承方式，一个ＣＴＵ里面所有的ＣＵＰＵ?ＴＵ都有了自己的ＣＭ，所以可以并行处理．
７
广州木偶艺术中心
７８张 峻等：多层次细粒度并行ＨＥＶＣ帧内模式选择算法
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议