一种深度图帧内预测模式决策改进算法

李 强，范杰羚，明 艳

(重庆邮电大学 信号与信息处理重庆市重点实验室，重庆 400065)

一种深度图帧内预测模式决策改进算法

李 强，范杰羚，明 艳

(重庆邮电大学 信号与信息处理重庆市重点实验室，重庆 400065)

为减小3D-高效视频编码(three dimensional-high efficiency video coding，3D-HEVC)的编码复杂度，提出一种深度图帧内预测模式决策改进算法。一方面，采用拉普拉斯边缘检测法对是否遍历深度模型模式(depth modeling modes，DMMs)进行快速判决；另一方面，利用预测单元(prediction unit，PU)的楔形分割线与其纹理特征的相关性，只对候选预测模式中的帧内角度模式相关的楔形分割进行搜索，减少楔形分割模式遍历的数量，实现DMM1模式的快速决策。经测试，算法在平均编码比特率增加很少的情况下，深度模型模式的平均编码时间降低了53.65%，而深度图的合成质量基本不变。

多视点视频加深度；帧内预测模式；楔形分割；快速决策

0 引 言

3D(three dimensional)视频可提供自然场景的立体表达，为人们带来“身临其境”的视觉体验，深受广大观众的喜爱。3D电影、支持3D视频播放的电视、平板电脑和游戏终端已经进入到了百姓的生活中。3D视频技术应用的普及，对3D视频编码技术[1]提出了更高的要求。为了发展和推广3D视频编码技术，2012年，国际电信联盟ITU第16工作组视频编码专家组(video coding experts group，VCEG)和动态图像专家组(moving picture experts group，MPEG)共同发起成立了3D视频联合组JCT-3V，制定出了新一代3D视频编码标准，将基于高效视频编码技术H.265/HEVC[2]的3D视频编码扩展为3D-高效视频编码(three dimensional-high efficiency video coding，3D-HEVC)[3]。

多视点视频加深度(multi-view video plus depth，MVD)在不需要传输所有视点信息的情况下，可实现用户观看视点的自由选择，是3D-HEVC的标准编码数据格式。MVD中的深度图用于接收端合成虚拟视点而非直接为观众可见，具有大范围平坦区域和分割这些区域的尖锐边缘，图中尖锐边缘的编码质量决定了合成虚拟视点的准确性，如果采用与纹理图像相同的基于块的预测算法，会在边缘处产生明显的失真。因此，MVD一方面继承了HEVC的四叉树编码结构以及预测模式的遍历过程；另一方面根据深度图的特征，增加了新的帧内预测模式，即深度模型模式(depth modeling modes，DMMs)[4]。DMMs的引入提升了深度图中边缘轮廓的编码质量，但带来了编码复杂度的急剧增加。如何在保证深度图编码质量的情况下，有效降低编码复杂度成为3D-HEVC的研究重点。目前很多学者在如何有效降低深度视频编码的复杂度上开展了研究，提出了很多有效算法。如文献[5]对编码块进行方差计算，得到楔形最有可能分区，然后对这些分区中的楔形分割进行遍历，虽然减少了编码时间，但并未考虑是否需要遍历深度模型模式。文献[6]利用父辈编码单元(coding unit，CU)的最优帧内预测模式与子辈CU的帧内预测模式的相关性，减少遍历模式数，并且对SDC(segment-wise DC coding)进行提前终止。该方法对CU进行了快速判决，但是视频质量下降较多。文献[7]对预测单元(prediction unit，PU)进行率失真(rate-distortion，RD)值计算，判定RD值是否大于阈值，决定是否进行双部分粗略模式决策(rough mode decision，RMD)，以达到快速决策的目的，但该算法并未考虑深度模型模式是否遍历。文献[8]利用35种帧内模式的RD值，判定是否进行DMM计算，以减少计算复杂度，但算法只对DMM模式进行了快速判决，对复杂度较高的楔形分割没有进行优化。文献[9]判定CU中的像素点是否属于Lookup Table，如果CU中的像素点属于Lookup Table，则对CU进行提前终止，以减小计算复杂度。但算法只对CU进行了快速决策，并未对PU的划分进行优化。

本文针对深度图帧内预测模式提出了一种决策改进算法，采用拉普拉斯检测法对是否遍历DMMs模式做快速判决，利用帧内预测模式和DMMs之间的相关性，减少模式遍历的数量，实现模式的快速决策。实验测试结果表明，本文改进算法在平均编码比特率增加很少的情况下，平均编码时间大幅度减少，而视频质量基本不变。

1 深度图帧内预测模式快速决策

1.1 深度图帧内预测模式决策过程

3D-HEVC深度图帧内预测包括传统的35种帧内预测模式和2种DMMs。35帧内预测包含33种角度预测模式，1种平面模式Planar和1种直流模式DC，DMMs包含了楔形(wedgelet)分割模式DMM1和轮廓(contour)分割模式DMM4，如图1所示。

图1 HEVC帧内预测模式(0：Planar 1：DC)Fig.1 Intra prediction modes in HEVC(0：Planar 1：DC)

深度图的帧内预测模式决策以预测单元PU为对象，通过粗略模式决策、最有可能模式决策和最优模式决策3个过程得到PU块的最优模式判决，具体过程如下。

步骤1对35种帧内预测模式进行粗略模式决策，选择N个最小Cost值所对应的帧内预测模式作为粗略模式决策的候选预测模式。对4×4和8×8的PU块，N为8；对16×16，32×32和64×64的PU块，N为3。在Cost值的计算公式(1)中，SATD是PU块的预测残差进行Hadamard变换后得到的残差绝对值总和；λ为拉格朗日算子；Bits是对某个预测模式编码后的二进制比特数。

Cost=SATD+λ×Bits

(1)

步骤2从当前PU块相邻已编码的左块和上块的最终帧内预测模式中选择0～2种模式作为最有可能模式(most probably modes，MPMs)。

步骤3把N种候选预测模式，MPMs和DMMs添加到全搜索列表RDModeList中，计算出列表中所有预测模式的全RD值。最小全RD值所对应的预测模式即为PU块的最优预测模式。全RD值的计算式为

J=D+ls×λ×R

(2)

(2)式中：J表示率失真值；D为深度图像和合成视点失真的加权平均值；ls表示缩放因子；R是指在每个决策模式下，需要消耗的比特率。

深度图帧内预测模式决策过程中的DMM判决占整个帧内编码近40%的时间[10]，如果能实现对是否遍历DMMs进行快速判决，以及在对DMM1决策时，降低遍历楔形分割模式的数量，即可实现深度图帧内预测模式的快速判决，降低3D视频编码的时间。

1.2 是否遍历DMMs的快速判决

DMMs用于深度图陡峭边界的编码。由于在深度图中存在大面积的平坦或缓慢变化区域，如图2所示的Dancer深度图，因此，在实际编码过程中，选择DMMs为最优编码模式的概率不大。

图2 深度图dancer(1 920×1 088)Fig.2 Depth map dancer(1 920×1 088)

本文选择3D-HEVC/HTM测试序列作为编码对象， 7个测试序列的编码参数如表1所示。对表1的测试序列在不同深度量化步长(QP)下，统计帧内预测编码选择DMMs为最优模式的概率，如表2所示。选择DMMs为最优模式概率，最小为0.09%，最大也只有5.65%。如果在深度图帧内编码过程中，总是将DMMs全部加入RDModeList，这将导致预测模式判决的运算量增大。

表1 测试序列参数Tab.1 Test sequence parameters

在PU块的N个候选预测模式中，如果第1个模式为Planar，PU块为平坦区域，在这种情况下，不用把DMMs添加到RDModeList中；除此之外，如果能通过对PU块纹理特征的分析，决定是否在RDModeList表中添加DMMs，就可减小遍历DMMs的数量，加快帧内预测模式的决策。

表2 DMMs为最优模式的统计概率Tab.2 DMMs statistical rate as best mode

由于DMMs为最优模式的PU块的亮度方差值要大于其他帧内预测模式为最优模式的PU块的方差值，因此，常采用方差法来判决是否遍历DMMs。首先，计算出PU块亮度方差Var；然后，与某一阈值Tth做比较，如果Var大于Tth，则把DMMs添加到RDModeList中。Var和Tth的计算式如(3)-(5)式。

(3)

Tth=Vth×Vth-8

(4)

(5)

(3)-(5)式中：QP为PU块的深度量化步长；max表示取2个数值中的最大值；fi，M和n分别为PU块像素的亮度值，亮度平均值和个数。

方差是PU块亮度对比度的一种粗略估计，其值越大，亮度对比度越高。因此，根据方差值的大小可判断出PU块是否存在边缘，但这种判定方法的计算量较大。本文采用如图3所示的拉普拉斯(Laplace)算子对PU块进行边缘检测，采用(6)式计算出PU块亮度的二阶差分值▽2f，如果▽2f不为0，则把DMMs添加到RDModeList中。

0101-41010

图3拉普拉斯算子
Fig.3 Laplace operator

▽2f=f(i+1,j)+f(i-1,j)+f(i,j+1)+

f(i,j-1)-4f(i,j)

(6)

(6)式中：f(i+1,j)，f(i-1,j)，f(i,j+1)，f(i,j-1)和f(i,j)分别为Laplace算子对应深度图像素的亮度值。

Laplace检测法和方差法的运算量的对比如表3所示。当PU块为32×32和16×16时，Laplace检测法需要的最大加法次数要略多于方差法，但Laplace检测法不需要做乘法运算，因此，Laplace检测法的运算量要小于方差法。在本文算法中，对32×32，16×16和8×8的PU块采用Laplace检测法，对4×4的PU块，采用方差法进行检测。

表3 方差法和Laplace检测法运算量的比较Tab.3 Comparison of operation for variance and Laplace detection method

1.3 楔形分割模式快速判决

DMMs将深度图中的PU块分割成2个非矩形区域后，判断出最优分割模式，计算每个区域的分块常数值。楔形分割用一条直线将PU块分成2个非矩形区域，遍历PU块所有可能的起始点和终点后，选择失真最小的分割模式作为最优分割模式。该方法在初始化时，先建立一个包含楔形所有分割模式的索引初始化列表，然后对PU块的分割模式进行决策，遍历PU块对应的楔形分割模式列表中的每一种模式，因此，这种全搜索楔形分割模式算法的计算量很大。图4为4×4的PU块86种全搜索楔形分割模式，黑色区域和白色区域分别表示楔形分割线两侧的区域。当PU块较大时(如16×16)，楔形分割模式数达到1 349，其决策过程耗时很大。

3D-HEVC对全搜索法进行了改进，采用粗略搜索和精细搜索相结合的双层搜索算法来减小决策复杂度，如图5所示。双层搜索算法决策过程为：①建立粗略搜索列表集。以8×8的PU为例，在图5a中，横纵坐标每隔一个点作为起始点和终点，2点之间的黑实连线为粗略搜索集的一种分割模式。图5b中的虚线表示某个粗略分割模式周围8个参考方向的精细搜索；②遍历PU对应的楔形粗略搜索集中的所有模式，得到最小失真楔形分割模式索引；③遍历楔形粗略模式的8种精确搜索，最小失真的楔形分割模式即为该PU块的最终分割模式。

图4 4×4PU块的86种楔形分割模式Fig.4 4×4 PU 86 wedgelet pattern

图5 双层搜索算法的粗略搜索和精细搜索Fig.5 Double-layer search of rough and refine search

与全搜索算法相比，双层搜索算法减小了遍历楔形分割模式的数量，降低了计算复杂度。这2种算法遍历分割模式数的对比如表4所示。

表4 全搜索法与双层搜索法遍历楔形分割模式数的比较Tab.4 Wedgelet patterns’ comparison of full search and double-layer search

为了降低DMM1存储楔形分割模式需要的存储容量，3D-HEVC采用16×16块的楔形分割模式来代替32×32块的楔形分割模式[10]。

由表4可以看出，双层搜索算法仍需遍历较多的楔形分割模式，复杂度仍然很高。由于PU块的楔形分割线与其纹理特征具有很强的相关性，因此，可利用这种相关性来减小遍历楔形分割模式的次数。在PU块N个候选预测模式中，存在一个或几个帧内角度模式，可只对与这些角度模式相关的楔形分割模式进行搜索。基于这种相关性，本文提出一种楔形分割模式快速决策算法，具体过程如下。

步骤1建立一个与33种帧内角度模式相关的初始化楔形分割列表WedModeList。以4×4的PU块为例，根据楔形分割模式与帧内角度模式的相关性，把86种楔形分割模式分成33个子集。帧内角度预测模式7对应4种楔形分割，模式20对应3种楔形分割模式，如图6所示。

图6 角度模式7和角度模式20对应的楔形分割Fig.6 Angle 7 and 20 mode corresponding to the wedgelet patterns

步骤2经过粗略搜索和最有可能模式搜索后，得到PU块的全搜索列表RdModeList。如果列表中需遍历DMMs，则根据RdModeList列表包含的帧内角度模式遍历对应的楔形分割，最小失真的楔形分割模式即为PU块的最终楔形分割模式。

与双层搜索算法相比，本文算法大幅度减小了遍历楔形分割模式的数量，降低了帧内模式决策复杂度。表5是本文算法与双层搜索算法遍历分割模式数的对比。

表5 本文算法与双层搜索法遍历楔形模式数Tab.5 Number of wedgelet patterns for double-layer search and fast search

1.4 深度图帧内模式快速决策算法流程

基于以上分析，本文提出的一种深度图帧内模式快速决策算法流程如图7所示。

图7 快速帧内模式决策算法流程Fig.7 Flow chart of a fast intra mode decision algorithm

2 性能测试

本文提出的深度图帧内预测模式决策改进算法和文献[5]的算法均在HTM-13.0[11]测试平台上进行了实现，并分别通过与HTM-13.0测试平台原有算法性能指标的对比来评估本文改进算法性能。

2.1 客观性能指标的测试和对比

按照JCT-3V制定的测试标准对帧内预测模式决策算法性能进行评估，编码对象为表1中的7个测试序列；深度量化步长QP取4个值，分别为39，42，45和48[12]；测试设备为泰克公司的PQA600A图像质量分析仪(CPU为Intel Xeon E5-2630，内存为32 GBtye)；测试指标采用BD-PSNR，BDBR[13]和DT[14]。BD-PSNR是评价图像质量的指标，表示在给定的同等码率下，2种方法的亮度峰值信噪比PSNR-Y的差异；BDBR是衡量编码效率的指标，是在同样客观质量下，2种方法的码率节省情况；DT是评估算法复杂度的指标，表示2种算法编码时间的节省比例。

表6 本文算法与文献[5]算法DT值的比较Tab.6 Comparison of DT cost for the proposed algorithm and the reference[5] algorithm %

表7 本文算法与文献[5]算法BDBR值的比较Tab.7 Comparison of BDBR for the proposed algorithm and the reference [5] algorithm %

表8 本文算法与文献[5]算法BD-PSNR值的比较Tab.8 Comparison of BD-PSNR for the proposed algorithm and the reference [5] algorithm dB

表6-表8是本文算法与文献[5]算法性能指标的对比，正值和负值分别表示与深度模型模式原算法相比性能指标数值的增加和减少量，表6-表8中的每个数据是编码器分别在4个不同量化步长下测试结果的平均值。本文算法相对深度模型模式原算法平均编码时间节省了53.65%，平均编码比特率增加了1%，亮度峰值信噪比减小了0.15 dB。而文献[5]算法相对深度模型模式原算法平均编码时间减少了45.73%，平均编码比特率增加了1.12%,亮度峰值信噪比减小了0.17 dB。测试结果说明，本文算法与深度模型模式原算法相比，平均编码时间大幅度减少，而平均编码比特率增加较少，客观视频质量指标下降不多。与文献[5]算法相比，本文算法在有效降低编码复杂度方面要优于文献[5]算法，平均编码比特率和亮度峰值信噪比相差不大。

2.2 虚拟视点合成图主观质量的对比

本文通过解码后的彩色视频和深度图对虚拟视点进行了合成，测试对象为表1中的7个测试序列，彩色视频的量化步长QP为30，深度图的QP为39。

图8 分别采用HTM13.0、文献[5]和本文3种算法 得到的虚拟视点合成图Fig.8 Virtual viewpoint composite maps for original algorithm in HTM-13.0，the reference [5] and the proposed algorithm

图8是分别采用HTM13.0原有算法、文献[5]算法和本文算法对7个测试序列进行编解码后得到的虚拟视点合成图的第1帧。左列图为采用HTM-13原有算法生成的合成图，中间列图为参考文献[5]的合成图，右列图为采用本文算法生成的合成图。从合成图的效果表明，本文算法对图像主观质量的影响很小，很难用肉眼分辨出来。

3 结 论

本文提出了一种深度图帧内预测模式决策改进算法，通过对是否遍历DMMs进行快速判决，减少遍历楔形分割模式的数量来减小计算复杂度。主观和客观实验测试结果表明，本文算法在大幅度降低编码时间的同时，编码比特率增加很少，合成的虚拟视点图像质量几乎不变，对3D-HEVC的应用具有较大的现实意义。下一步将对视点间编码算法进行研究，对CU的快速决策进行分析，以进一步降低编码计算复杂度。

[1] 田恬，姜秀华，王彩虹．新一代基于HEVC的3D视频编码技术[J].电视技术，2014， 38(11)：5-8.

TIAN Tian，JIANG Xiuhua，WANG Xinhua. Next-generation 3D Video Coding Technology Based on HEVC[J].Video Engineering，2014，38(11)：5-8．

[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 & Systems for Video Technology，2012，22(12)：1649-1668．

[3] MULLER K，SSHWARZ H，MARPE D， et al．3D High-Efficiency Video Coding for Multi-View Video and Depth Data[J]．IEEE Transactions on Image Processing A Publication of the IEEE Signal Processing Society，2013，22(9)：3366-3378．

[4] LIU H，JIA J．Depth modeling mode coding and decoding method and video codec：WO，2014114168 A1[P]．2014．

[5] FU C H，ZHANG H B，SU W M，et al．Fast wedgelet pattern decision for DMM in 3D-HEVC[C]//IEEE.IEEE International Conference on Digital Signal Processing．Singapore：IEEE Press，2015：447-481．

[6] ZHANG H B，TSANG S H，CHAN Y L，et al．Early determination of intra mode and segment-wise DC coding for depth map based on hierarchical coding structure in 3D-HEVC[C]//Asia-Pacific Signal and Information Processing Association Summit and Conference．HK，China：APSIPA，2015:396-400．

[7] GU Z, ZHENG J， LING N，et al．Fast bi-partition mode selection for 3D HEVC depth intra coding[C]//IEEE.Multimedia and Expo (ICME)，2014 IEEE International Conference on Multimedia & Expo．Sydney，Australia：IEEE Press，2014：1-6．

[8] PARK C S.Efficient intra-mode decision algorithm skipping unnecessary depth-modelling modes in 3D-HEVC[J]. Electronics Letters, 2015, 51(10):756-758.

[9] CHUNG K, HUANG Y, LIN C, et al. Novel Bitrate-Saving and Fast Coding for Depth Videos in 3D-HEVC[J]. IEEE Transactions on Circuits & Systems for Video Technology,2016, 26(10):1859-1869.

[10] TAKESHI T．JCT3V-I0110 Lookup table size reduction in DMM1 [S]．Sapporo，Japan：ISO/EC，2014．

[11] JCT3V．HTM-13．[EB/OL]．(2015-02-11)[2016-07-11]．https://hevc.hhi.fraunhofer.de/svn/svn_3DVCSoftware/tags/HTM-13.0/．

[12] KARSTEN M，ANTHONY V．JCT3V-G1100 Common test conditions of 3DV core experiment[S]. San Jose，US：ISO/EC，2014．

[13] BJONTEGAARD G．Calculation of average PSNR difference between RD-curves[C]// ITU-Telecommunications Standardization Sector Study Group 16 Question6 Video Coding Experts Group(VCEG) 13th Meeting．Austin， US：ITU，2001．

[14] 谢红，魏丽莎，解武．纹理图的3D-HEVC深度图编码单元快速划分算法[J]．应用科技，2016，43(2)：14-18．

XIE Hong，WEI Lisha，XIE Wu．A fast coding unit size decision algorithm for the depth map based on texture in 3D-HEVC[J]．Applied Science and Technology，2016，43(2)：14-18．

s：The National Natural Science Foundation of China(61102131); The Science & Technology Research Project of Chongqing Education Committee of China(KJ1400425)

Improveddepthintramodeselectionalgorithm

LI Qiang, FAN Jieling, MING Yan

Chongqing Key Laboratory of Signal and Information Processing, Chongqing University of Posts and Telecommunications, Chongqing 400065, P. R. China)

In order to reduce the 3D-HEVC coding complexity, there is an improved intra prediction mode decision algorithm for depth maps. On the one hand, the proposed algorithm uses Laplace operator edge detection, and determines whether it traverses depth modeling modes or not. On the other hand, a fast DMM1 decision can be realized efficiently by using the correlation between the line of wedgelet pattern and its textural features in prediction unit. Then, it reduces the number of wedgelet pattern modes through wedgelet pattern related to angle modes in candidate list. After tests, the experiments show that the DMMs algorithm is able to reduce the average time of the encoder by 53.65% while minimally reduced bitrate of coding. Besides, the quality of encoded video almost remains unchanged.

multi-view video and depth；intra prediction mode；wedgelet pattern；fast decision

10.3979/j.issn.1673-825X.2017.06.019

2016-07-15

2017-02-24

范杰羚 445413391@qq.com

国家自然科学基金(61102131)；重庆市教委科技项目(KJ1400425)

TP919.81；TP39

A

1673-825X(2017)06-0837-07

李 强(1968 -)，男，湖南益阳人，副教授，硕士，主要研究方向为音视频信号处理。E-mail：liqiang@cqupt.edu.cn。

范杰羚(1992 -)，男，湖南娄底人，硕士研究生，主要研究方向为视频编码。E-mail：445413391@qq.com。

明 艳(1967 -)，女，湖南长沙人，副教授，本科，主要研究方向为数字通信技术。

(编辑：王敏琦)