基于3D相邻区域宏块相关性的多视点视频快速编码算法

明 艳

(重庆邮电大学 通信学院，重庆 400065)

基于3D相邻区域宏块相关性的多视点视频快速编码算法

明 艳

(重庆邮电大学 通信学院，重庆 400065)

针对多视点视频编码的高复杂度，提出一种利用相邻宏块编码信息的相关性进行编码的快速算法。利用多视点视频相邻宏块率失真代价分布的相关性，对当前宏块进行SKIP模式下的提前判决；根据视点间、时间和空间相邻区域运动矢量差值对当前宏块运动类型进行快速分类；针对不同的运动类型调整搜索范围，选择相应尺寸大小的编码模式。通过对具有不同运动特性的多视点视频编码性能测试，结果表明，相对于联合多视点视频模型(joint multi view video model，JMVM)遍历模式，在增加0.75%输出比特率和降低0.04 dB峰值信噪比的情况下，该快速编码算法能平均减少66%的编码时间。

多视点视频编码；快速算法；相关性；性能测试

0 引 言

多视点视频是由不同视点的多个摄像机从不同视角拍摄同一场景采集到的一组视频数据，由于能生动地再现立体感场景，提供交互功能，广泛应用在自由视点视频[1]、3D电视、远程医学诊疗、视频监视等多媒体业务中。因多视点视频的数据量随摄像机的数目增加呈线性增长，如何对多视点视频数据进行高效压缩是其应用普及和推广的关键。2006年，ITU-T的视频编码专家组(video coding experts group，VCEG)和国际标准化组织/国际电工委员会(international organization for standardization/international electrotechnical commission，ISO/IEC)的运动图像专家组(moving picture experts group，MPEG)完成了多视点视频编码的标准化工作，并作为H.264标准的扩展部分。该标准通过对所有尺寸大小模式进行遍历得到最优模式[2]的方法虽然提高了压缩性能，但带来了极高的运算复杂度。

目前多视点视频编码快速算法主要分为2类：①优化拉格朗日率失真函数；②最佳模式的提前判决[3]。Zhu[4]提出的快速算法是先利用帧内编码信息对当前宏块进行纹理区域分割，然后通过相邻视点间相同纹理区域SKIP宏块的率失真代价值对SKIP模式进行提前判决，由于该算法只对SKIP模式进行了快速判决，降低编码复杂度的效率还有待提高；在文献[5]中，先计算相邻视点间SKIP模式的加权因子，如果加权因子大于阈值，判决为SKIP模式，提前终止模式遍历。该方法在减小运算量方面虽取得了一些效果，但并没有充分利用时间和空间编码信息的相关性；Shen[6]提出了一种基于视点间运动矢量的尺寸大小模式选择方法，根据视点间相邻宏块运动矢量的变化来对当前块运动类型进行判决，但该方法对某些序列效果较差；文献[7]提出了一种利用视点间率失真代价值的信息对当前块的纹理区域进行判决，但该方法并没有对占用编码时间较大的尺寸大小的模式进行快速判决；文献[8]提出了通过摄像机的几何位置关系来减少搜索范围，因此，需要一些摄像机的位置信息，且只对某些特定的序列效果较好。Zeng[9]使用了3D相邻区域宏块的运动矢量信息来对当前块的运动类型进行分类，不同的运动类型只选择相应的尺寸大小的模式。该方法能有效地减少编码复杂度，但对运动类型一致的宏块编码效果不好。

本文提出了一种利用视点间、时间和空间的3D相邻区域的宏块编码信息对当前块进行快速编码的算法。首先，计算已编码相应视点的率失真代价值，对当前宏块做SKIP模式快速判决；然后，通过当前块3D相邻宏块的运动矢量差值信息，对块的运动类型进行快速分类，并根据确定的运动类型动态调整搜索范围；最后，利用运动矢量差值信息进行尺寸大小模式选择。经过对不同类型的多视点视频序列的性能测试和数据对比，本文算法在比特率增加不多，峰值信噪比下降很小的情况下，能有效地降低编码复杂度，大幅度减小编码时间。

1 多视点视频编码快速算法原理

多视点视频编码有SKIP、帧间(Inter)和帧内(Intra)3种模式。Inter模式预测块尺寸包括16×16，8×16，16×8，8×8，8×4，4×8和4×4这7种模式，其中，后4种尺寸合并在一起被称为P4×4。Intra模式预测块尺寸有16×16，8×8和4×4这3种模式[10]。设计这些不同大小尺寸块的目的是为了适用不同类型视频的编码。大的块尺寸适用于图像中静止或低速运动的平坦区域，小的块尺寸则适合快速运动的区域。采用拉格朗日率失真优化函数作为最优判决准则，通过对所有预测模式的遍历，计算出每种模式的率失真代价(Rdcost)值，选择Rdcost值最小的模式作为该宏块编码的最优模式。利用拉格朗日率失真优化函数计算Rdcost的公式为

(1)

(1)式中：J(s,c,MODE|QP,λMODE)为率失真代价；MODE表示当前宏块的编码模式；QP为宏块的量化步长；s和c分别为原始图像和重建图像的像素值；λMODE为预测模式所对应的拉格朗日乘子；R(s,c,MODE|QP)表示在所选QP和MODE下，当前宏块编码输出比特数，SSD(s,c,MODE|QP)为图像失真度。

由上述分析可知，对于编码帧的每个宏块有11种预测模式可供选择，若采用全遍历的方法，则需计算出每种模式的Rdcost值，而每次Rdcost的计算都十分耗时，因此，全遍历方法的计算量巨大。如果能提前判断出最优的编码模式，省去对其他编码模式的检查，就可以降低计算复杂度。本文提出的快速算法就是基于这个思想来减少多视点视频编码的算法复杂度。文中算法测试所用的多视点视频序列参数如表1所示。

1.1 SKIP模式提前判决

SKIP模式是利用运动矢量对当前块进行预测的。由于没有运动估计过程，该模式除了能节省对运动矢量编码的比特数外，还可以降低计算复杂度。表2是附加视点为非关键帧时，在不同量化步长QP下，采用基于率失真最优判决和遍历方法，测试出了表1中视频序列的各种最优模式所占比例。其中63.3%～84.1%的宏块选择的是SKIP模式，选择其他模式的比例较小，这是因为在多数视频中，大部分背景区域是静止的。与其他模式相比，由于计算SKIP模式Rdcost值的时间最少，如果该模式能尽早地被判决为最佳模式，这将可以减小多视点视频编码的时间。

表1 多视点视频测试序列

表2 最优模式的概率分布

由于视点间的视频内容的相似性，视点间相邻宏块的编码信息，如Rdcost值、运动矢量的分布也很相似。如果能利用相邻视点宏块的Rdcost值计算得到一个阈值TSKIP，若当前宏块SKIP模式的Rdcost值小于TSKIP，则可直接选择SKIP模式为最佳模式，这样可以减少所需遍历的模式数，降低编码复杂度。TSKIP的计算公式为

(2)

(2)式中：i表示参考视点V帧的宏块序号；N为参考视点帧的宏块总数；RDcostVSKIP(i)为第i宏块的SKIP模式的Rdcost值；kV(i)的定义如(3)式所示。pV(RDcostVSKIP(i))为参考视点V帧中RDcostVSKIP(i)出现的概率，(4)式为该值的计算公式。

(3)

(4)

(4)式中：N(RDcostVSKIP(i))为RDcostVSKIP(i)量化后的个数；NVSKIP是SKIP模式的总个数。由于Rdcost值一般很小，对于(4)式中的率失真代价用RDcostVSKIP(i)/100进行量化。表3是当测试序列采用遍历模式时，统计出的Rdcost值小于TSKIP的概率分布。从表2可以看出，不同分辨率的序列在采用不同量化步长QP的情况下，最终判决为SKIP模式的概率可达90%～99%，说明采用这种SKIP模式提前判决方法是可行和有效的。

表3 率失真代价值小于TSKIP的模式概率分布

1.2 编码宏块运动类型快速分类

在视频序列中，帧间和帧内不同区域的运动类型一般是不一样的。不同的运动区域通常会有不同的编码方式，因此，可先将运动类型进行分类，再根据某些编码信息对编码区域的运动类型进行快速判决。在编码过程中，运动矢量差值能有效地反映出区域的运动状况。对于静止和运动一致的区域，其编码块的运动矢量差值较小，而运动变化越大的区域，编码块的运动矢量差值就越大。因此，可根据视点间、时间和空间的3D相邻区域宏块的运动矢量差值的分布不同，对当前块的运动类型进行快速分类判决。3D相邻区域宏块位置如图1所示。

图1 3D相邻区域宏块位置Fig.1 3D adjacent area macro block location

在图1中，当前帧编码宏块MB0的3D相邻区域宏块包括：当前帧中相邻的3个宏块MB1～MB3；前一编码帧中相同位置的宏块MB4；参考视点中相应宏块及其周围的8个宏块MB5～MB13。MB0的运动类型判决过程如下。

1)根据图1所示的3D相邻区域，构建运动矢量差值集合{mvd1,mvd2,…,mvd13}。其中，mvdi是宏块MBi的运动矢量差值，i=1,2,…,13。

2)按(5)式计算每个mvdi的距离D(mvdi)，xi和yi分别是运动矢量的水平分量和垂直分量。

D(mvdi)=|xi|+|yi|

(5)

3)在运动矢量差值集合中找到mvdi的最大距离值D。

D=max(D(mvdi))

(6)

4)如果D≤D1，或D1≤D≤D2，或D2≤D≤D3，或D3≤D，则判断当前宏块MB0的运动类型为“运动一致”“简单运动”“中度运动”“剧烈运动”。这里的D1和D2分别为1和5，D3的计算式为

D3=μ+2σ

(7)

(7)式中，μ和σ分别为当前宏块在参考视点帧中D的期望和方差值。

1.3 运动搜索范围动态调整

运动搜索是为了在参考帧的搜索区域内找到编码块的最佳参考块。在多视点视频编码中，搜索范围(search range，SR)是固定的。而在视频帧中，不同区域的运动类型一般是不同的，而不同的运动类型，对应有不同的搜索范围。对于静止和运动一致的区域，其搜索范围较小，而运动越剧烈的区域，其搜索范围就越大。如果能实现编码块搜索范围的动态调整，减少某些编码块的搜索区域，就能降低平均编码时间。针对1.2节中4种运动类型的编码宏块，确定了最大搜索范围如表4所示。

表4 不同运动类型对应的搜索范围

采用全遍历方式，对表1中的视频序列进行编码，统计出编码宏块4种运动类型的搜索范围，并计算出这些搜索范围在SRproposal内的概率，统计结果如表5所示。测试时的实验参数设置为：SR为96，编码图像组(group of pictures，GOP)为12，采用基于上下文自适应二进制算术编码(context-based adaptive binary arithmetic coding，CABAC)。从表5可以看出，运动一致、简单运动和中度运动的区域搜索范围在SRproposal内的概率分别达到了94.8%，98.5%和97.2%，说明利用宏块的运动类型对运动搜索范围进行动态调整的方法是可行的。

表5 遍历方式下运动类型在最大搜索范围内的概率

1.4 模式尺寸的选择

在多视点视频编码中，不同尺寸大小的模式适应于不同的运动类型。对于静止和运动一致的区域，大尺寸编码模式更有效，而对于运动较强或剧烈的区域，小尺寸块编码模式效果最佳。如果能根据运动类型提前选择出最适合的尺寸模式，从而可以减少编码时间。表6是在量化步长QP=28的情况下，采用全遍历方法，对表1中的测试序列进行编码，统计出了不同运动类型选择的最佳模式的概率分布。

对运动一致情况的区域，选择16×16模式的概率为96%，选择其他模式的概率为4%，因此，对这种运动类型，可直接选16×16模式为最佳模式；对于简单运动类型的区域，16×16模式被选择的概率是85.2%，16×8和8×16模式被选择的概率分别为5.2%和5.4%，而P8×8模式和Intra模式被选择的概率仅为3.3%和1.0%，因此，可忽略P8×8模式和Intra模式。而对于中度运动和复杂运动区域，为了得到较高的压缩比，采用遍历方式选择最佳模式。表7总结出了不同运动类型区域需要进行遍历的模式。

1.5 算法流程

通过前面对多视点视频快速编码算法原理的分析，本文快速算法流程如图2所示。

表7 运动类型及相应的模式

2 算法性能测试与分析

文献[11]对多视点视频编码进行快速模式决策时，将编码宏块的运动类型分为运动和背景2种。如果编码宏块的运动矢量超过1/4个整数像素值，判定为运动类型，然后遍历所有大小尺寸模式；如果判断为背景类型，则只遍历SKIP，16×16，16×8和8×16这4种预测模式。由于文献[11]与本文算法具有一定的相似性，所以用于本文算法性能指标的对比。在JMVM测试模型中，对本文算法和文献[11]算法都进行了实现，并分别与JMVM全遍历模式算法的性能指标进行了比较。选择表1的视频序列做为测试对象，测试用的计算机配置为2.59 GHz的Intel(R) Celeron(R)双核处理器和1.96 GByte内存，JMVM测试模型的实验参数设置如表8所示。

表8 实验参数设置

本文算法、文献[11]算法与JMVM算法性能指标的对比如表9所示。

表9中，ΔB为平均比特率变化量，ΔPSNR为平均峰值信噪比(peak signal to noise ratio，PSNR)变化量，ΔT是平均时间变化量，其中，“+”表示增加的量，“-”为减少的量。

表9 本文算法、文献[11]算法与JMVM算法性能指标对比

通过本文算法与JMVM遍历模式，文献[11]算法与JMVM遍历模式的性能数据的对比，本文算法的ΔB和ΔPSNR性能指标均要好于文献[11]算法，文献[11]算法的ΔB平均增加1.62%，而本文算法仅增加0.73%，文献[11]算法的ΔPSNR平均减少0.056 dB，而文本算法平均减小0.043 dB。本文算法的编码时间与JMVM遍历模式相比，则大幅度降低，也明显优于文献[11]算法。无论是背景静止、运动简单的序列还是运动剧烈的序列，本文算法在降低编码时间上均具有良好的性能。对于静态背景、运动轻微的Exit序列，本文算法能减少72.1%编码时间。对于Akko&Kayo，Ballroom，Breakdancers和Uli这些运动比较剧烈的序列，编码时间也能分别减少65.9%，66.3%，61.7%和67.1%。对于相机移动和大片区域中有剧烈运动的Race1序列，采用本文算法，编码时间可减少64%。而文献[11]算法与遍历模式相比，仅减少了18%的编码时间。

图3是采用本文算法和JMVM遍历模式，Uli和Akko&Kayo 2组测试序列的率失真曲线，从曲线波形上看，本文算法与JMVM遍历方法率失真性能基本一致。

图3 本文算法与JMVM遍历模式率失真曲线对比图Fig.3 Contrast diagram of the rate distortion curve of proposed algorithm and JMVM ergodic model

3 结 论

本文算法充分利用了3D相邻区域和当前块的相关性，减少了多视点视频编码的复杂度。通过视点间宏块率失真代价分布的相关性，对当前宏块做SKIP模式自适应提前判决；根据3D相邻区域的运动矢量差值对当前宏块运动类型进行快速分类；针对不同的运动类型选择相应的搜索范围和相应尺寸大小的编码模式。通过实验测试表明，本文算法与JMVM遍历模式相比，在只增加0.73%比特率，降低0.043 dB峰值信噪比的情况下，能平均减少66%的编码时间。与文献[11]相比，也能平均减少20%的编码时间。因此，本文的快速算法可应用于多视点视频编码中。

[1] VETRO A，TOURAPIS A M，MULLER K，et al.3D-TV content storage and transmission[J].Broadcasting，IEEE Transactions on，2011，57(2)：384-394.

[2] VETRO A，WIEGAND T，SULLIVAN G J.Overview of the stereo and multiview video coding extensions of the H.264/MPEG-4 AVC standard[J].Proceedings of the IEEE，2011，99(4)：626-642.

[3] ZENG H，CAI C，MA K K.Fast mode decision for H.264/AVC based on macroblock motion activity[J].Circuits and Systems for Video Technology，IEEE Transactions on，2009，19(4)：491-499.

[4] ZHU W，JIANG W，CHEN Y.A fast inter mode decision for multiview video coding[C]//IEEE.Information Engineering and Computer Science，ICIECS 2009，International Conference on.New York：IEEE Press，2009：1-4.

[5] SHEN L，LIU Z，YAN T，et al.Early SKIP mode decision for MVC using inter-view correlation[J].Signal Processing：Image Communication，2010，25(2)：88-93.

[6] SHEN L，LIU Z，LIU S，et al.Selective disparity estimation and variable size motion estimation based on motion homogeneity for multi-view coding[J].Broadcasting，IEEE Transactions on，2009，55(4)：761-766.

[7] ZHU W，TIAN X，ZHOU F，et al.Fast inter mode decision based on textural segmentation and correlations for multiview video coding[J].Consumer Electronics，IEEE Transactions on，2010，56(3)：1696-1704.

[8] LI X，ZHAO D，JI X，et al.A fast inter frame prediction algorithm for multi-view video coding[C]//IEEE.Image Processing，ICIP 2007，IEEE International Conference on. New York：IEEE Press，2007，3：III-417-III-420.

[9] ZENG H，MA K K，CAI C.Motion activity-based block size decision for multi-view video coding[C]∥IEEE.Picture Coding Symposium(PCS).New York：IEEE Press，2010：166-169.[10] 汪博涵，陈婧，曾焕强，等.采用率失真与模式特征的多视点视频编码快速模式选择[J].信号处理，2015，31(12)：1642-1648. WANG Bohan，CHEN Jing，ZENG Huanqiang，et al.Fast Mode Decision for Multiview Video Coding using Rate-distortion and Mode Characteristic[J].Journal of Signal Processing，2015，31(12)：1642-1648.

[11] HAN D H，LEE Y L.Fast mode decision using global disparity vector for multi-view video coding[C]//IEEE.Future Generation Communication and Networking Symposia，2008.FGCNS'08，Second International Conference on. New York：IEEE Press，2008：209-213.

明 艳(1967-)，女，湖南长沙市人，高级工程师，主要研究方向为数字通信技术。E-mail：mingyan@cqupt.edu.cn。

(编辑：王敏琦)

Fast multi view video coding algorithm based on the relativity of 3D adjacent areas macroblock

MING Yan

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

Aimed at the high complexity of multi view video coding, a fast algorithm based on the correlation of adjacent macro-block’s coding information is proposed in this paper. Using the relativity of adjacent macro-block’s rate distortion cost distribution in inter views of multi view video, current macro-block’s SKIP mode can be prejudge. According to the motion vector difference in the adjoining domains from visual, temporal and spatial perspective, current macro-block’s motion activity can be classified quickly. Search range is adjusted and suitable mode size is chosen in accordance with the different motion activity. Through coding performance testing on multi view video sequences that has respective motion activity characteristics, the simulation results show that this algorithm achieves a reduction of the encoding time by 66% on average, while incurring only 0.04 dB loss in peak signal-to-noise ratio and 0.75% increment on the total bit rate compare with JMVM ergodic model

multi view video coding；fast algorithm；relativity；performance testing

2016-03-15

2016-10-10

明 艳 mingyan@cqupt.edu.cn

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

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

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

TP919.81；TP39

A

1673-825X(2016)06-0783-06