论文部分内容阅读
摘要： 提出了一种基于梯度的帧内候选模式裁剪算法，通过自适应深度划分并利用空间信息来简化帧内预测过程，大大减少了计算复杂度.实验结果显示，所提出的算法对比HM16.7，可以减少35.25%的计算复杂度，且只有极小的编码效率损失.
关键词：
高效率视频编码； 高清、超高清视频； 快速算法； 帧内预测
中图分类号： TN 919.8文献标志码： A文章编号： 10005137（2018）02024805
Gradientbased and intraframe adaptive depth decision algorithm
Shi Zhengcheng1， Zhang Qian1*， Jing Ruihai1， Cui Pengtao1， Wang Bin1， Yan Tao2， Huang Jifeng1
（1.The College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai 200234，China；
2.School of Information Science and Technology，Jiujiang University，Jiangxi 332005，China）
Abstract：
To reduce this computational complexity，agradientbased clipping algorithm for intraframe candidatemode is proposed，which simplifies the intra prediction process by adaptive deep division and spatial information usage.Experimental results show that the proposed algorithm reduces the computational complexity by 35.25% compared with HM16.7 with only mininal loss of coding efficiency.
Key words：
high efficiency video coding； high definition，ultra high definition video； fast algorithm； intra prediction
收稿日期： 20171128
基金项目： 国家自然科学基金（61741111）；上海市自然科学基金（15ZR1431500，15ZR1430400）
作者简介： 施正城（1993-），男，硕士研究生，主要从事视频编码方面的研究.Email：paws66cc@163.com
导师简介： 张倩（1983-），女，副教授，主要从事视频图像处理与多媒体通信方面的研究.Email：qianzhang@shnu.edu.cn
*通信作者
引用格式： 施正城，张倩，景瑞海，等.基于梯度的帧内自适应深度决策算法 [J].上海师范大学学报（自然科学版），2018，47（2）：248-252.
Citation format： Shi Z C，Zhang Q，Jing R H，et al.Gradientbased and intraframe adaptive depth decision algorithm [J].Journal of Shanghai Normal University （Natural Sciences），2018，47（2）：248-252.
0引言
联合视频编码工作组JCTVC组织在2013年发布了新一代视频编码标准高效率视频编码（HEVC）[1-2]，相比较于前一代标准H.264/AVC[3]，HEVC能够更高效地编码高清及超高清视频.HEVC包含了众多新技术，例如基于大尺寸四叉树的分割结构、新的帧内预测模式、自适应滤波器、残差编码结构等等.这些新的技术在极大提高编码效率的同时，也带来很高的计算复杂度，尤其提高了编码过程中的复杂度.
为了减少编码复杂度，加快编码过程，近年来学者们提出了许多快速帧内预测算法.Zhao等[4]提出了相邻块最优预测模式（MPM），并将其加入Rate Distortion Optimization（RDO）候选模式列表，利用空间上相邻编码单元（CU）的方向信息来进一步加快帧内模式决策过程；Silva等[5]分析了当前预测单元（PU）的纹理信息，排除部分帧内预测方向，从而降低了帧内预测的复杂度；Shen等[6]在分析图像内容相关性的基础上，參照周围CU的深度划分当前CU深度；Heindel等[7]提出了一种利用参考样本的两段式提前终止策略，来执行快速编码的算法；Min等[8]提出了基于指定全局和局部边缘复杂度的HEVC帧内CU快速决策算法，结合当前CU和其四个子CU的边缘复杂度决定当前CU是否需要划分；Wang等[9]提出了一种三步快速帧内预测算法，使用CU分割预测和低精度的粗略模式决策（RMD）加速帧内预测过程.Sun等[10]通过计算编码树单元（CTU）的绝对变换差值和（SATD），并以SATD为阈值，减少帧内预测CU层次和帧内预测方向数目，从而降低了帧内预测复杂度.
上述算法在增加了编码速度的同时也增加了编码比特率.为了克服这一问题，本文作者提出了一种基于梯度的自适应深度决策算法，以期降低算法的复杂度. 1HEVC帧内预测概述
在HEVC中，视频帧由一系列CTU构成.CTU尺寸最大为64 pixels×64 pixels，最小为16 pixels×16 pixels.HEVC 的 CTU尺寸突破了16 pixels×16 pixels的限制，更加适合处理高清、超高清视频，这也是 HEVC 编码效率提升的重要原因.HEVC 编码标准中将 CTU的叶节点定义为CU，编码器根据 CU 内部视频内容的复杂程度，以四叉树的方式将 CU 递归划分为多个编码单元.CU的尺寸可以递归划分为64 pixels×64 pixels、32 pixels×32 pixels、16 pixels×16 pixels和8 pixels×8 pixels，其递归深度分别为0、1、2和3.PU包含帧内预测模式信息和帧间的运动信息，是进行帧内/帧间预测的基本单元.变换单元（TU）是对残差数据进行变换和量化的基本单元.HEVC从预测方向的个数及判断过程对帧内预测进行扩展和深入.对于亮度分量，HEVC 有35种帧内预测模式.
另外，HEVC采用了与H.264类似的RDO技术[11]，为每一种预测模式计算失真代价，有效地提高了编码性能.首先对最大编码单元（LCU）进行帧内预测，定义此时的率失真为R0，然后將LCU划分4个子CU，对每个子CU进行帧内预测并算出率失真代价和为R1.如果R0 2本研究的快速帧内模式选择算法
2.1自适应深度决策裁剪算法
HEVC原有的标准算法采用穷尽式CU划分决策，但并不高效.大尺寸的CU具有较大的深度值，对应于视频中均匀分布的图像或者运动平缓的区域；小尺寸的CU具有深度值，对应于描述视频图像中的细节部分以及动作快速变化的区域.因此，CU的划分深度应根据图像的具体内容，如动作的变化度与纹理的丰富度，进行自适应的调整.与此同时，空域临近的CU间有很强的相关性.
当前CU的深度与空域临近的4个CU相关，分别是左（Left）、上（Up）、左上（LeftUp）以及右上（RightUp）4个CU，如图1所示.
其中，N为当前的已编码CU个数，μi为权值系数，di为相应的深度取值.左CU以及上CU的权值系数为0.35，左上CU以及右上CU的权值系数为0.15.
由（1）式计算当前待编码CU的深度值，将其分类[12]：（1）Dpre≤0.5，（2） 0.52.5.
利用CU的空间信息进一步简化帧内预测过程.由于RMD候选列表中的候选模式以代价函数值降序进行排列，Zhao[4]通过统计分析发现一个CU的最优预测模式大概率等于候选模式列表中模式1或2.Shen[6]讨论了当RMD列表中的第一项、父CU的编码模式和MPM均相等时，该模式很可能是当前模式的最优预测模式，无需再通过对RDO进行筛选.
通过定义预测模式序号小于等于2的所有模式为一组，Shen[12]对RMD候选模式序号的差异性做出了统计，结果显示，90%的RMD候选模式可以归类到上述定义的组别之中.即使是纹理复杂度较高或变化较大的编码区域，编码CU中涵盖的主要边缘类型大概率不超过2.于是将候选模式的序号差值小于等于2的模式缩减为一个CU代表所表征的纹理方向，从而达到对于RDO的进一步缩减.而当候选模式序号差值大于2时，将通过下一小节的方法来减少RDO.
2.2基于梯度的帧内预测算法
利用平面直角坐标系和sobel算子计算当前PU的像素梯度.定义pi，j为一个像素点，则像素的梯度向量Gi，j={Gxi，j，Gyi，j}，Gxi，j和Gyi，j分别代表像素梯度的水平和垂直信息，
3实验结果及讨论
利用HEVC标准测试软件HM16.7对提出的算法进行评估.实验平台的硬件配置为：英特尔酷睿 i77500U（双核）的CPU，主频2.9 GHZ，内存8 GBytes，操作系统Windows10.
本次测试中所采用的量化参数QP分别为22、27、32、37，其余所有的帧内编码参数均正确设定.实验所用的测试序列为不同类别（Class）中不同场景的高清、超高清视频序列，包括Class A （2 560 pixels×1 600 pixels），Class B （1 920 pixels×1 080 pixels） 和Class E （1 280 pixels×720 pixels）.采用平均码流差（BDBR），平均峰值信噪比（BDPSNR）以及编码时间节省比3个指标，衡量和评价所提出的算法.其中，编码效率由BDBR以及BDPSNR衡量，而编码减少时间由下式衡量：
图2给出了本算法与HM16.7标准算法在对序列ParkScene编码后的率失真（RD）曲线.从图2中可以看出所提算法较HM16.7标准算法只有可以忽略不计的编码质量损失.其余序列的RD曲线与当前曲线均近似.
4总结
本文作者提出了一种HEVC帧内快速模式选择算法，包括：快速CU深度决策裁剪算法与基于梯度的帧内预测算法.算法的评估由最新的HEVC参考软件HM16.7完成.实验结果表明，所提出的算法可以节省平均35.25%的总编码时间，并且BDrate只增加了1.26%，BDPSNR减少了0.06 dB.
参考文献：
[1]Bross B，Han W J，Ohm J R，et al.High Efficiency Video Coding （HEVC） text specification draft 9 [R].San Jose：Joint Collaborative Team on Video Coding，2012. [2]Sullivan G J，Ohm J R，Han W 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.
[3]Wiegand T，Sullivan G J，Bjontegaard G，et al.Overview of the H.264/AVC video coding standard [J].IEEE Transactions on Circuits and Systems for Video Technology，2003，13（7）：560-576.
[4]Zhao L，Zhang L，Ma S W，et al.Fast mode decision algorithm for intra prediction in HEVC [C].Proceedings of 2011 IEEE Visual Communications and Image Processing.Tainan：IEEE，2011.
[5]DaSilva T L，Agostini L V，DaSilvaCruz L A.Fast HEVC intra prediction mode decision based on EDGE direction information [C].Proceedings of the 20th European Signal Processing Conference.Bucharest：IEEE，2012.
[6]Shen L Q，Zhang Z Y，An P.Fast CU size decision and mode decision algorithm for HEVC intra coding [J].IEEE Transactions on Consumer Electronics，2013，59（1）：207-213.
[7]Heindel A，Pylinski C，Kaup A.Twostage exclusion of angular intra prediction modes for fast mode decision in HEVC [C].Proceedings of 2016 IEEE International Conference on Image Processing.Phoenix：IEEE，2016.
[8]Min B，Cheung R C C.Afast CU size decision algorithm for the HEVC intra encoder [J].IEEE Transactions on Circuits and Systems for Video Technology，2015，25（5）：892-896.
[9]Wang Y，Fan X P，Zhao L，et al.A fast intra coding algorithm for HEVC [C].Proceedings of 2014 IEEE International Conference on Image Processing.Paris：IEEE，2014.
[10]Zhang Y F，Li Z，Li B.Gradientbased fast decision for intra prediction in HEVC [C].Proceedings of 2012 IEEE Visual Communications and Image Processing.San Diego：IEEE，2012.
[11]Sun H M，Zhou D J，Goto S.A lowcomplexity HEVC intra prediction algorithm based on level and mode filtering [C].Proceedings of 2012 IEEE International Conference on Multimedia and Expo.Melbourne：IEEE，2012.
[12]Shen L Q，Liu Z，Zhang X P，et al.An effective CU size decision method for HEVC encoders [J].IEEE Transactions on Multimedia，2013，15（2）：465-470.
（責任编辑：包震宇）
关键词：
高效率视频编码； 高清、超高清视频； 快速算法； 帧内预测
中图分类号： TN 919.8文献标志码： A文章编号： 10005137（2018）02024805
Gradientbased and intraframe adaptive depth decision algorithm
Shi Zhengcheng1， Zhang Qian1*， Jing Ruihai1， Cui Pengtao1， Wang Bin1， Yan Tao2， Huang Jifeng1
（1.The College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai 200234，China；
2.School of Information Science and Technology，Jiujiang University，Jiangxi 332005，China）
Abstract：
To reduce this computational complexity，agradientbased clipping algorithm for intraframe candidatemode is proposed，which simplifies the intra prediction process by adaptive deep division and spatial information usage.Experimental results show that the proposed algorithm reduces the computational complexity by 35.25% compared with HM16.7 with only mininal loss of coding efficiency.
Key words：
high efficiency video coding； high definition，ultra high definition video； fast algorithm； intra prediction
收稿日期： 20171128
基金项目： 国家自然科学基金（61741111）；上海市自然科学基金（15ZR1431500，15ZR1430400）
作者简介： 施正城（1993-），男，硕士研究生，主要从事视频编码方面的研究.Email：paws66cc@163.com
导师简介： 张倩（1983-），女，副教授，主要从事视频图像处理与多媒体通信方面的研究.Email：qianzhang@shnu.edu.cn
*通信作者
引用格式： 施正城，张倩，景瑞海，等.基于梯度的帧内自适应深度决策算法 [J].上海师范大学学报（自然科学版），2018，47（2）：248-252.
Citation format： Shi Z C，Zhang Q，Jing R H，et al.Gradientbased and intraframe adaptive depth decision algorithm [J].Journal of Shanghai Normal University （Natural Sciences），2018，47（2）：248-252.
0引言
联合视频编码工作组JCTVC组织在2013年发布了新一代视频编码标准高效率视频编码（HEVC）[1-2]，相比较于前一代标准H.264/AVC[3]，HEVC能够更高效地编码高清及超高清视频.HEVC包含了众多新技术，例如基于大尺寸四叉树的分割结构、新的帧内预测模式、自适应滤波器、残差编码结构等等.这些新的技术在极大提高编码效率的同时，也带来很高的计算复杂度，尤其提高了编码过程中的复杂度.
为了减少编码复杂度，加快编码过程，近年来学者们提出了许多快速帧内预测算法.Zhao等[4]提出了相邻块最优预测模式（MPM），并将其加入Rate Distortion Optimization（RDO）候选模式列表，利用空间上相邻编码单元（CU）的方向信息来进一步加快帧内模式决策过程；Silva等[5]分析了当前预测单元（PU）的纹理信息，排除部分帧内预测方向，从而降低了帧内预测的复杂度；Shen等[6]在分析图像内容相关性的基础上，參照周围CU的深度划分当前CU深度；Heindel等[7]提出了一种利用参考样本的两段式提前终止策略，来执行快速编码的算法；Min等[8]提出了基于指定全局和局部边缘复杂度的HEVC帧内CU快速决策算法，结合当前CU和其四个子CU的边缘复杂度决定当前CU是否需要划分；Wang等[9]提出了一种三步快速帧内预测算法，使用CU分割预测和低精度的粗略模式决策（RMD）加速帧内预测过程.Sun等[10]通过计算编码树单元（CTU）的绝对变换差值和（SATD），并以SATD为阈值，减少帧内预测CU层次和帧内预测方向数目，从而降低了帧内预测复杂度.
上述算法在增加了编码速度的同时也增加了编码比特率.为了克服这一问题，本文作者提出了一种基于梯度的自适应深度决策算法，以期降低算法的复杂度. 1HEVC帧内预测概述
在HEVC中，视频帧由一系列CTU构成.CTU尺寸最大为64 pixels×64 pixels，最小为16 pixels×16 pixels.HEVC 的 CTU尺寸突破了16 pixels×16 pixels的限制，更加适合处理高清、超高清视频，这也是 HEVC 编码效率提升的重要原因.HEVC 编码标准中将 CTU的叶节点定义为CU，编码器根据 CU 内部视频内容的复杂程度，以四叉树的方式将 CU 递归划分为多个编码单元.CU的尺寸可以递归划分为64 pixels×64 pixels、32 pixels×32 pixels、16 pixels×16 pixels和8 pixels×8 pixels，其递归深度分别为0、1、2和3.PU包含帧内预测模式信息和帧间的运动信息，是进行帧内/帧间预测的基本单元.变换单元（TU）是对残差数据进行变换和量化的基本单元.HEVC从预测方向的个数及判断过程对帧内预测进行扩展和深入.对于亮度分量，HEVC 有35种帧内预测模式.
另外，HEVC采用了与H.264类似的RDO技术[11]，为每一种预测模式计算失真代价，有效地提高了编码性能.首先对最大编码单元（LCU）进行帧内预测，定义此时的率失真为R0，然后將LCU划分4个子CU，对每个子CU进行帧内预测并算出率失真代价和为R1.如果R0
2.1自适应深度决策裁剪算法
HEVC原有的标准算法采用穷尽式CU划分决策，但并不高效.大尺寸的CU具有较大的深度值，对应于视频中均匀分布的图像或者运动平缓的区域；小尺寸的CU具有深度值，对应于描述视频图像中的细节部分以及动作快速变化的区域.因此，CU的划分深度应根据图像的具体内容，如动作的变化度与纹理的丰富度，进行自适应的调整.与此同时，空域临近的CU间有很强的相关性.
当前CU的深度与空域临近的4个CU相关，分别是左（Left）、上（Up）、左上（LeftUp）以及右上（RightUp）4个CU，如图1所示.
其中，N为当前的已编码CU个数，μi为权值系数，di为相应的深度取值.左CU以及上CU的权值系数为0.35，左上CU以及右上CU的权值系数为0.15.
由（1）式计算当前待编码CU的深度值，将其分类[12]：（1）Dpre≤0.5，（2） 0.5
利用CU的空间信息进一步简化帧内预测过程.由于RMD候选列表中的候选模式以代价函数值降序进行排列，Zhao[4]通过统计分析发现一个CU的最优预测模式大概率等于候选模式列表中模式1或2.Shen[6]讨论了当RMD列表中的第一项、父CU的编码模式和MPM均相等时，该模式很可能是当前模式的最优预测模式，无需再通过对RDO进行筛选.
通过定义预测模式序号小于等于2的所有模式为一组，Shen[12]对RMD候选模式序号的差异性做出了统计，结果显示，90%的RMD候选模式可以归类到上述定义的组别之中.即使是纹理复杂度较高或变化较大的编码区域，编码CU中涵盖的主要边缘类型大概率不超过2.于是将候选模式的序号差值小于等于2的模式缩减为一个CU代表所表征的纹理方向，从而达到对于RDO的进一步缩减.而当候选模式序号差值大于2时，将通过下一小节的方法来减少RDO.
2.2基于梯度的帧内预测算法
利用平面直角坐标系和sobel算子计算当前PU的像素梯度.定义pi，j为一个像素点，则像素的梯度向量Gi，j={Gxi，j，Gyi，j}，Gxi，j和Gyi，j分别代表像素梯度的水平和垂直信息，
3实验结果及讨论
利用HEVC标准测试软件HM16.7对提出的算法进行评估.实验平台的硬件配置为：英特尔酷睿 i77500U（双核）的CPU，主频2.9 GHZ，内存8 GBytes，操作系统Windows10.
本次测试中所采用的量化参数QP分别为22、27、32、37，其余所有的帧内编码参数均正确设定.实验所用的测试序列为不同类别（Class）中不同场景的高清、超高清视频序列，包括Class A （2 560 pixels×1 600 pixels），Class B （1 920 pixels×1 080 pixels） 和Class E （1 280 pixels×720 pixels）.采用平均码流差（BDBR），平均峰值信噪比（BDPSNR）以及编码时间节省比3个指标，衡量和评价所提出的算法.其中，编码效率由BDBR以及BDPSNR衡量，而编码减少时间由下式衡量：
图2给出了本算法与HM16.7标准算法在对序列ParkScene编码后的率失真（RD）曲线.从图2中可以看出所提算法较HM16.7标准算法只有可以忽略不计的编码质量损失.其余序列的RD曲线与当前曲线均近似.
4总结
本文作者提出了一种HEVC帧内快速模式选择算法，包括：快速CU深度决策裁剪算法与基于梯度的帧内预测算法.算法的评估由最新的HEVC参考软件HM16.7完成.实验结果表明，所提出的算法可以节省平均35.25%的总编码时间，并且BDrate只增加了1.26%，BDPSNR减少了0.06 dB.
参考文献：
[1]Bross B，Han W J，Ohm J R，et al.High Efficiency Video Coding （HEVC） text specification draft 9 [R].San Jose：Joint Collaborative Team on Video Coding，2012. [2]Sullivan G J，Ohm J R，Han W 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.
[3]Wiegand T，Sullivan G J，Bjontegaard G，et al.Overview of the H.264/AVC video coding standard [J].IEEE Transactions on Circuits and Systems for Video Technology，2003，13（7）：560-576.
[4]Zhao L，Zhang L，Ma S W，et al.Fast mode decision algorithm for intra prediction in HEVC [C].Proceedings of 2011 IEEE Visual Communications and Image Processing.Tainan：IEEE，2011.
[5]DaSilva T L，Agostini L V，DaSilvaCruz L A.Fast HEVC intra prediction mode decision based on EDGE direction information [C].Proceedings of the 20th European Signal Processing Conference.Bucharest：IEEE，2012.
[6]Shen L Q，Zhang Z Y，An P.Fast CU size decision and mode decision algorithm for HEVC intra coding [J].IEEE Transactions on Consumer Electronics，2013，59（1）：207-213.
[7]Heindel A，Pylinski C，Kaup A.Twostage exclusion of angular intra prediction modes for fast mode decision in HEVC [C].Proceedings of 2016 IEEE International Conference on Image Processing.Phoenix：IEEE，2016.
[8]Min B，Cheung R C C.Afast CU size decision algorithm for the HEVC intra encoder [J].IEEE Transactions on Circuits and Systems for Video Technology，2015，25（5）：892-896.
[9]Wang Y，Fan X P，Zhao L，et al.A fast intra coding algorithm for HEVC [C].Proceedings of 2014 IEEE International Conference on Image Processing.Paris：IEEE，2014.
[10]Zhang Y F，Li Z，Li B.Gradientbased fast decision for intra prediction in HEVC [C].Proceedings of 2012 IEEE Visual Communications and Image Processing.San Diego：IEEE，2012.
[11]Sun H M，Zhou D J，Goto S.A lowcomplexity HEVC intra prediction algorithm based on level and mode filtering [C].Proceedings of 2012 IEEE International Conference on Multimedia and Expo.Melbourne：IEEE，2012.
[12]Shen L Q，Liu Z，Zhang X P，et al.An effective CU size decision method for HEVC encoders [J].IEEE Transactions on Multimedia，2013，15（2）：465-470.
（責任编辑：包震宇）