3D-HEVC深度建模模式的优化及并行设计

谢晓燕，王 昱，石鹏飞，朱 筠

1(西安邮电大学 计算机学院，西安 710121) 2(西安邮电大学 电子工程学院，西安 710121)

1 引 言

伴随着二维视频编码(High Efficiency Video Coding，HEVC)的发展与成熟，三维视频编码方案也在不断推进，对于三维视频的规范化研究早前就得到了标准化组织、世界产业界和学术界的重视，并取得了一定成果.作为HEVC/H.265视频压缩标准的扩展，3D-HEVC采用多视点视图及对应的深度图映射的方式，满足了人们对立体图像的追求，却导致了数据量增加.

由于深度图帧内预测需要处理锐利的边缘区域，而纹理图帧内预测适合处理近似恒定的区域.3D-HEVC中的帧内预测包含纹理图帧内预测和深度图帧内预测两部分，用纹理图帧内预测方法处理深度图会导致在锐利边缘处出现显著失真现象.深度图帧内预测中对大量的楔形模板进行穷举式搜索给帧内预测带来了极高复杂度，因此，深度图帧内预测成为近年来研究的热点.文献[1]提出了一种快速双分区模式决策算法，将计算的RD代价作为阈值来加速3D-HEVC深度编码过程.文献[2]通过计算RD-Cost，终止不必要的候选模式.这两种方法无形当中在原本复杂度较高的模式选择基础上又增加了计算复杂度，基于此，文献[3]通过分析纹理图和深度图边缘方向，从而降低计算复杂度.文献[4]基于父编码单元(Coding Units，CU)与子CU关系提前终止不必要的模式，但该方法在模式选择初期依旧遍历整个模式.以上所示的方法中，无论是通过设置阈值，还是通过预测单元之间的关系降低帧内预测复杂度，都不能从本质上简化楔形模板.笔者通过对楔形搜索表分析和统计，在保证质量的前提下，筛选出8种预测概率较大的尺寸为4×4的楔形模板，经验证，存储空间节约了99.2%，编码时间减少了61.8%.此外，当前多媒体工程师和设计人员已经开始把视频编码向灵活的FPGA、GPU上转移，有效的硬件解决方案对性能的需求是必要的，但这几乎是对帧间预测，对于帧内预测在这方面的研究较为缺乏，由于帧内预测算法在视频编码中具有重要作用，针对前人设计编码过程是串行执行的不足，基于以上精简的楔形搜索模板间无数据相关性的特性，对改进的楔形模板进行并行设计，并映射在项目组提供的具有独特并行特性的阵列处理器上.经验证，该方案数据加载时间的串/并加速比为1.912，执行编码时各模板的串/并加速比达到1.637.这种改进对高效视频编码具有重要研究意义.

2 3D-HEVC预测编码

3D-HEVC帧内预测中几乎恒定的区域可以用纹理图预测算法处理，陡峭的边缘部分需要考虑深度数据编码方式.而深度图中大量的楔形搜索模板需要排队等待计算机的处理，这无疑的加大了预测编码的时间.

如图1所示，深度数据编码在3D-HEVC编码过程中有将近一半的编码占用率，它包含四种深度建模模式(Depth Modeling Modes，DMMS)：DMM-1、DMM-2、DMM-3、DMM-4，由于DMM-2和DMM-3的效率不高，已被标准舍弃，剩下的DMM-1模式占10.16%，DMM-4模式占3.34%，可见分析DMM-1模式具有重要意义.

图1 深度图编码比例Fig.1 Depth map coding ratio

文献[5-8]相对于先前视频编码标准，在质量降低允许范围内降低计算复杂度方面是有效的.而这些快速算法对于3D-HEVC新增的深度图帧内预测不能直接适用或有效改变编码效率，如何有效地降低编码时间和计算复杂度是学术界研究的课题.为此，有专家学者提出了一些关于减少3D-HEVC深度编码时间的快速算法.

文献[9-12]仅用于优化深度编码帧内预测模式，而未充分研究深度图帧内预测算法的并行方法.所以3D-HEVC深度图帧内预测的计算复杂度和编码速度仍然存在优化空间.

针对深度数据在编码时所带来的复杂度：基于对楔形搜索表分析和统计，精简了楔形表的划分方式，利用一些最小编码单元的块作为基准楔形区域，然后进行扩展直至成为当前块的方法进行楔形划分，大大地缩减了楔形表所消耗的时间.

针对传统串行算法中数据串行加载导致部分不具相关性的模块还在排队等待数据这一问题，提出了共享存储加载数据、预测模式并行计算的方式进行算法预测.

3 深度图帧内预测算法的改进

3.1 DMM-1的优化分析

在DMM-1模式中，不同尺寸的编码块楔形模板数量不同，尺寸越大，对应的模板数量越多.待每种模板完成CPVs编码后，DMM-1在上万种模板中穷举式搜索最优楔形模板，这带来了极高的复杂度.

DMM-1的wedgelets分割方式是通过一条直线将块划分为两个非矩形区域，每个区域由一个恒定值表示.分割线由开始点S和结束点E表示.wedgelets分割可分为两类(包括六个方向).两类即相邻边缘分割和相对边缘分割.如图2所示，相邻边缘分割wedgeori的范围包含在0到3之间，而相对边缘分割wedgeori等于4或5.

图2 wedgelets分割选择Fig.2 Wedgelets segmentation selection

以上为编码块的wedgelets划分，此外还要对不同尺寸的PU进行此类的划分.

3.2 DMM-1模式基于楔形搜索表的优化

为了避免对整个wedgelets模板进行处理，由深度图中存在大面积均匀区域，且这些区域大多选择简单方向，以及楔形分割和传统帧内预测的35种预测模式在角度选择上类似的特点.给出8种不同方向(分别是水平模式、垂直模式、模式5、模式14、模式21、模式32、模式16以及模式30)的预测角度.如图3所示，由深度图中楔形分割具有相邻边缘分割和相对边缘分割的特点，给出10种楔形模板.

图3 精简楔形模板Fig.3 Streamlined wedge template

利用3D-HEVC编码器下的全部DMM-1模式搜索进行模拟测试，得出选择6个候选方向(水平模式、垂直模式、Ang-5、Ang-14、Ang-2和Ang-30)的概率为80.19%，剩余27个方向的总概率不超过20%.证明了简化楔形搜索表具有代表性，符合预测时对6个方向的搜索.

如图4所示，基于项目组提供的DPR-CODEC结构精简指令集并行执行程度好、编译器效率高的特点，设计出的DPR-CODEC IDE(programable reconfuger unit Integrated Develop Environment，IDE)仿真平台，给出了改进思路：给定的两个变量是一个4×4的原始wedgelets搜索模板和该块所在的位置(i，j).根据给定的位置将该楔形模板扩展成一个N×N的预测单元(Predict Units，PU).通过利用HTM16.1对测试序列进行统计分析，该楔形模板块所在位置大部分在当前块中央，因此给出楔形模板四个角像素点的位置，分别为(N/2-1，N/2-1)、(N/2-1，N/2+2)、(N/2+2，N/2-1)和(N/2+2，N/2+2).

以预测一个16×16的PU、4×4的楔形模板为例进行具体改进过程的介绍.其中，模板扩展方式如图5所示.

图5 (a)原始Wedgelets搜索模式图案(2，2)(b)用分区边界线和楔形波位置(2，2)检查每个位置Fig.5 (a)Original wedge search pattern (2，2)(b)Check each location with partition boundary and wedge wave position (2，2)

图5(b)中虚线为分割线，分割线函数由原始楔形波中分割线的起始点(X1，Y1)和终点(X2，Y2)决定.则有分割线函数：y=ax+b，其中a，b计算如公式(1)所示.

a=(Y2-Y1)/(X2-X1)，b=(X2Y1-Y2X1)/(X2-X1)

(1)

为了避免不必要的重复分割，则有Pi，j如公式(2)所示.

Pi，j=j(X2-X1)-(Y2-Y1)i<(X2Y1-Y2X1)?1：0

(2)

如图6所示，对PE阵列进行功能区域的设计.DIM(Data Input Memory)缓存YUV视频序列数据；PE00对当前块像素和参考块像素的读取以及将该数据分配到各具体功能模块；PE01到PE13用来处理每种模板的CPV预测过程；PE20到PE33用来处理深度图中二进制映射的过程.

图6 优化后楔形搜索模式的PE功能划分Fig.6 PE function division of optimized wedge search mode

Step1.数据加载，PE00从DIM取数完，通过共享存储的方式把参考像素的数据传递给PE01和PE10，把当前块的数据传递给PE20和PE30.待4个PE数据加载完成，将接收到的数据传递给同一簇内右方PE.

Step2.模板位置确定.此时N=16，则四个角点分别为(7，7)、(7，10)、(10，7)和(10，10).

Step3.模板扩展，PE20到PE33根据(i，j)=(6，6)确定4×4模板四个角的坐标是(10，6)、(6，10)和(10，10)，如图5(a)所示.当前PU的N=16×16，则向两侧扩展时按整像素精度扩展，直至到达PU的块边界，如图5(b)所示.

Step4.CPV编码，PE01到PE23都对二进制区域进行CPV编码.选取参考点，只需上参考样点的行或者左参考样点的列样点里的第一个样点、最后样点或中间样点以生成在不同情况下的DC.

3.3 仿真与验证

将设计方案在DPR-CODEC IDE上进行仿真验证，如表1所示，对改进前后的编码时间进行统计.结果表明，改进前后的平均加速比达到2.619.这是由于在编码时，搜索范围限制于精简的楔形模板，节省了大量的编码时间，既保证了质量，又降低了编码复杂度，充分验证了笔者方案的合理性.

表1 分割方式优化后的时间对比(单位：时钟周期)Table 1 Time comparison after segmentation optimization (unit：clock cycle)

如表2所示，基于优化的楔形模板，分别对不同测试序列：Kendo、Newspaper1、Balloons、Undo_Dancer、Poznsin_Hallz、Poznan_Street进行测试，结果表明，与文献[1,13,14,15]相比更节省编码时间和存储空间，相较于HTM串行编码，时间减少了61.8%，存储空间节约了99.2%.此外，为了发挥阵列处理器的优势，在第四节中将该优化算法进行并行化设计，映射到该阵列处理器中.

表2 时间、存储减少对比Table 2 Time and storage reduction contrast

4 深度图帧内预测算法的并行

4.1 并行化介绍

基于第三节对楔形搜索模板的改进，用项目组提供的阵列处理器DPR-CODEC在数据加载和编码不同尺寸编码块两个方面进行并行化设计.

4.1.1 数据加载的可并行性分析

3D-HEVC预测编码时，数据加载是串行执行.从同一编码单元中不同楔形模板的串行数据加载，到不同尺寸编码单元中不同楔形模板的串行数据加载过程占整个DMM-1编码时间2/3.对同一编码单元中不同楔形模板之间所加载的数据相同，则可对同一编码单元内所有的楔形模板进行并行数据加载，达到合理利用资源和缩减编码时间的效果.

4.1.2 楔形模板的可并行性分析

深度图帧内预测中，当前编码块的参考点从相邻块中选择.这保证了在进行DMM-1模式编码时拥有与纹理图角度预测一样独立完成各角度(楔形模板)预测的特性.因此，用并行处理模板的方式预测当前编码块具有合理性.

以一个8×8PU、4×4楔形模板为例.利用1个PEG来完成显示楔形波预测的并行化映射.DIM是数据缓存区，每个PE完成一种楔形模板的预测编码，PE03用作最优楔形模板的判断.

Step1.数据加载，PE00从DIM中读取当前8×8的编码块，接着向当前PEG00的其余PE传递已获取的当前块及其参考像素.

Step2.二进制映射，按不同楔形模板对当前块进行预测.此时，并不是所有的PE同时进行，而是按照完成数据加载的情况.

Step3.用CPVs编码模式预测.

Step4.由公式(3)计算SAD，其中SA是原始像素值，SB是预测值，i=0…N-1，j=0…N-1；根据SAD值大小选择最优的预测模式.

SAD(i，j)=∑i，j|SA(i，j)- SB(i，j)|

(3)

4.2 仿真与验证

如表3所示，平均串/并行加速比达到1.912，即在数据加载上本方案节约了约50%的加载时间，之所以能缩减一半的加载时间，是巧妙地运用了同一编码单元内所有的楔形模板并行数据加载的方式.

表3 串/并行数据加载时间对比(单位：时钟周期)Table 3 String/parallel data loading time comparison (unit：clock cycle)

注：表3中包含当前编码块以及相应的参考像素.

数据加载完成后，对每个PE进行预测处理.如表4所示，列出了不同编码尺寸的编码块处理精简后的各个楔形模板的串并行编码时间，实验表明，DMM-1模式并行处理的平均串/并行加速比为1.637，这一数据充分验证了该并行方案的实用性、有效性.

表4 并行模板处理(单位：时钟周期)Table 4 Parallel template processing (unit：clock cycles)

注：表4中包含当前编码块以及相应的参考像素.

5 结束语

3D-HEVC作为HEVC的扩展标准，尽管能满足人们对真实场景的追求，但其背后隐藏着复杂的编码过程和庞大的数据处理问题.针对这些问题，本文在前期项目组工作基础上，结合当前视频应用的需求.基于项目组所提供的DPR-CODEC结构天然并行的特点，对深度图的帧内预测编码进行改进和并行化设计.具体研究工作如下：

1)3D-HEVC中深度图帧内预测优化设计.给出了一种简化的楔形搜索表方案.经过仿真验证，从存储角度来讲，该方案节约了99.2%的存储空间.从编码时间来讲，相较于串行编码方式减少了61.8%.

2)3D-HEVC中深度图帧内预测的并行化设计.对于DMM-1，首先筛选出8种预测概率较大的尺寸为4×4的楔形模板，通过对其扩展直至当前编码块边界，得到不同编码尺寸楔形划分的区域，然后完成CPVs编码.经仿真验证，该方案串/并行平均加速比为1.637.

通过上述方案的实验结果可以看出，本方案在合理利用资源的同时有效地缩短了编码时间，提高了运算效率.

另外，由于项目组的仿真平台DPR-CODEC IDE部分功能还不完善，以及个人的能力与时间有限，目前完成了深度图在楔形搜索表方面的改进和深度图的并行化设计.对于深度图帧内预测的发展还有很长一段路要走，基于多核结构DPR-CODEC对帧内预测进行有效合理的并行化仍是今后需要研究的课题.