内容自适应的低复杂度多参考帧快速选择算法

金智鹏，佟树成，罗 铮，王利华

(1.嘉兴职业技术学院信息技术分院，浙江嘉兴314036;2.中国(嘉兴)微软技术研究中心，浙江嘉兴314000)

移动技术的不断发展和广阔的市场需求，为移动视频业务的快速发展提供了必要条件，并使其成为移动运营商、设备制造商和内容提供商关注的焦点之一。目前，移动端尤其是手机端已经成为主流视频屏幕之一;预计到2015年，手机端的视频用户规模将与PC端相当，这必将促进视频行业的新一轮爆发。

H.264/AVC是由ISO/IEC与ITU-T联合制定的新一代国际视频编码标准，具有较高的图像质量、较强的抗误码性和良好的网络亲和性，非常适合于有丢包和抖动的无线信道［1］。H.264目前已广泛地应用在视频通信、移动通信、数字广播和流媒体等领域。

H.264的多参考帧运动估计技术是其编码器中最耗时的模块，且编码复杂度与参考帧数量呈现线性增长关系［2］，这给移动终端硬件设备的处理能力、内存空间和电池容量等带来了巨大挑战。因此，研究相应的快速算法加快编码器的计算速度势在必行。

1 H.264多参考帧选择算法分析

1.1 现有算法分析

为降低多参考帧运动估计补偿的计算量，提高编码实时性，国内外学者提出了许多快速算法。常用的多参考帧快速选择算法总体上可以分成以下两类:

第一类是参考帧预测法，即根据一定的策略，跳过可能性较小的参考帧，以此提高多参考帧运动估计的速度。例如利用视频序列的时域相关性，文献［3］根据前2帧中Skip模式的占比来确定参考帧数目;文献［4］根据前5帧中最优参考帧的选用情况来确定当前编码块的参考帧数目。文献［5］用Sobel算子进行边缘梯度检测，并结合运动矢量最大值和差值的分布情况，确定候选参考帧集合。在文献［6］中，对于宏块级编码，根据已编码帧中Skip模式和16×16模式的占比来确定参考帧数目;对亚宏块级编码，则跟据运动矢量的相关性来确定的参考帧数目。文献［7］根据先前参考帧的运动矢量信息，判断是否使用各个参考帧。在这类算法中，如果块之间的相关性不强，会导致最优参考帧的误判，且这个错误有可能被不断传播，影响编码R-D(Rate-Distortion)性能。

第二类是预测运动矢量法，即根据一定的策略，通过时空相邻块的运动矢量预测各个参考帧的初始运动矢量，减少花费在每个参考帧上的搜索时间。例如文献［8］分析了多参考帧效率和视频对象运动幅度之间的关系，对快速运动块和平缓运动块分别采用不同的搜索策略，并建立了基于哈达玛变换系数的提前终止条件。文献［9］根据多参考帧下运动矢量的中心偏置特性，预测各个参考帧的初始运动矢量，并结合快速运动估计算法降低计算量。文献［10］首先对运动矢量进行中值滤波，然后使用处理后的运动矢量扩展出一个新的参考帧，最后将新的参考帧插入到参考帧列表中进行运动估计，提升了编码质量。文献［11］根据不同参考帧之间的预测运动矢量，选择空间上最接近的候选参考帧。在这类算法中，对遮挡显露等情况，运动矢量的预测精度较难把握，影响编码R-D性能。

1.2 多参考帧选择依据

在H.264中，每一个帧间预测编码宏块最多可支持16个参考帧、10种预测编码模式(Skip模式、16×16、16×8、8×16、8 ×8、8 ×4、4 ×8、4 ×4、intra16 ×16、intra4 ×4)。为找出基于率失真代价(Rate Distortion Optimization，RDO)的最优参考帧，JM校验模型在运动估计过程中采用遍历所有参考帧的方法，并选择代价最小的参考帧作为最优参考帧。H.264中参考帧选择的率失真代价函数定义如下

式中:J(mv，ref)表示率失真代价;SAD表示当前块与参考块的绝对差;S表示当前编码宏块的像素值;C(mv，ref)表示参考块的像素值;ref为当前参考帧序号;mv表示该参考帧的运动矢量;Rmv和Rref分别表示运动矢量和参考帧序号的编码比特数;λ为拉格朗日参数，其值与量化系数有关。这种遍历计算所有候选参考帧的J(mv，ref)，进而得到率失真意义上的最优参考帧的方法，给编码器带来了巨大的计算量。

1.3 最优参考帧分布情况分析

表1是各标准测试序列在16×16模式和亚宏块级模式下的最优参考帧采用情况统计表，本文数据是在H.264的JM86测试平台上进行100帧编码统计的结果，表1选用5个参考帧，量化参数QP=28。图1是多参考帧的运动估计补偿示意图，其中ref0～n是指最优参考帧的序号，ref0最近，refn最远。表1的数据说明绝大多数编码块仅仅需要最临近的1个参考帧就可以获得最好的编码效果，其余的参考帧均被浪费了，没有起到提升编码R-D性能的作用。

表1 最优参考帧采用率统计

图1 运动估计的多参考帧预测

1.4 时空相邻区域的相关性分析

本文对最优参考帧的相关性情况进行了100帧的编码统计，如表2所示。表2中，“时域”指当前块与前一帧对应位置块最优参考帧的相关性统计，“空域”指当前块与同帧中相邻块的相关性统计，其位置关系可以参考图2的位置关系说明。图2中M指当前编码块，E指前一帧中与M对应位置的块，A指M的左边相邻块，B、C、D分别指M的左上边、上边和右上边相邻块。

表2 最优参考帧的时空相关性统计 %

从表2的统计数据可以看出，时空相邻块的最优参考帧具有很强的相关性。而且，亚宏块级模式编码时，块之间的空域相关性要明显高于时域相关性;16×16模式编码时，前后帧之间的时域相关性要高于帧内空域相关性。这是因为上下左右相邻的小尺寸块很有可能属于同一对象，它们选用同一参考帧的概率更大;而大尺寸编码块往往属于背景区或纹理平滑区，前后帧之间的相关性更高，选其前一时刻已编码帧作为最优参考帧的可能性更大。利用这个特性，可以根据已编码块的最优参考帧选用情况，对当前块的最优参考帧进行预测与筛选，从而提高编码速度。

图2 时空相邻块的位置关系图

1.5 各编码模式的采用率分析

本文对帧间编码模式的采用情况也进行了100帧的编码统计，如表3所示。根据统计结果，Skip模式的使用概率最高(使用 ref0作为参考帧)，宏块级(16×16，16×8，8×16)编码模式的采用率要远高于亚宏块级模式(8×8，8×4，4×8，4×4)，而采用帧内编码模式的概率极低。由于本文算法主要针对移动终端小尺寸图像的应用场合，摒弃帧间编码中的帧内模式以提高编码速度，对编码质量不会产生大的影响。此外，在进行参考帧的比较选择时，由于亚宏块级编码模式的采用率较低，可以适当控制计算量的分配;而宏块级编码模式的采用率较高，应保留更多的计算量，从而在编码质量与速度之间达到一个较好的平衡。

表3 各编码模式的采用率统计 %

2 自适应的多参考帧快速选择算法

2.1 候选模式选择策略

根据表2最优参考帧的时空相关性统计结果，在进行宏块级模式编码时，前后帧之间的时域相关性都要高于帧内相邻块间的空域相关性。因此，本文通过统计前一帧中对应位置块的参考帧选用情况来确定当前编码块的候选参考帧集合。在进行亚宏块级模式编码时，帧内相邻块之间的空域相关性明显强于帧间的时域相关性。因此，本文候选参考帧集合的构成如下

式中:Ref1表示宏块级编码时确定的初步候选参考帧集合1;Ref2表示亚宏块级编码时，各8×8子块初步确定的候选参考帧集合2。由于H.264中的参考帧以8×8为单位进行分配和保存，因此宏块级的16×16模式最多可以有4个初步候选参考帧。而对于亚宏块级模式，同一个8×8子块的各个更小分割块(如8×4、4×8、4×4模式)只能指向同一个参考帧。

2.2 参考帧扩展选择策略

多参考帧技术所获得的编码增益并非简单依赖于参考帧数目的多少，而是取决于视频内容的本质特征。在一些特殊情况下，例如在对象发生遮挡和显露时，对象周期性运动时，或发生场景切换时，远端参考帧被选为最优参考帧的概率更大。因此，本文定义一个参考帧范围的扩展条件

参考帧扩展条件

式中:表示候选参考帧集合的最小代价值;Jx(x∈A，B，C，D，E)表示时空相邻块的最优参考帧代价;两个参数用于进行计算量的分配控制。根据1.4节的统计分析和编码实践，本文设置α=0.75，β=1.2。如果当前块满足扩展条件，则认为当前参考帧的补偿结果并不理想，需要通过对更多参考帧进行搜索，以求得更为准确的运动补偿，防止这些块编码质量的降低和可能导致的错误传播。若不满足扩展条件，则根据式(2)，直接从候选参考帧集合中确定最优参考帧。

2.3 本文快速参考帧选择算法流程

本文算法专门针对多参考帧选择模块进行研究，算法通用性强。本文算法具体编码过程描述如下(见图3):

1)当进行宏块级编码时，依据时域相关性确定当前编码块的候选参考帧集合1，见式(2)。进行集合1的运动估计补偿，求得初步最优参考帧和最小代价。

2)宏块级参考帧扩展条件判断。如果不满足式(3)，则说明不需要扩展搜索，直接进入到亚宏块级的编码。如果需要扩展搜索，则将候选参考帧范围扩展至余下的全部参考帧，并根据最小代价确定编码块的最优参考帧。

3)当进行亚宏块级各8×8子块的编码时，依据空域相关性确定当前编码块的候选参考帧集合2，见式(2)。进行集合2的运动估计补偿，求得各8×8子块的初步最优参考帧和最小代价。

4)亚宏块级参考帧扩展条件判断。如果不满足式(3)，则说明不需要扩展搜索，当前子块的最优参考帧选择结束。如果需要扩展，则按参考帧序号逐个扩展搜索;一旦发现，则结束扩展搜索，选取对应的参考帧为各子块的最优参考帧。

图3 本文快速参考帧选择算法流程图

3 实验结果及数据分析

为了测试分析算法的综合性能，本文从编码时间(Time)、峰值信噪比(PSNR)、码率(Rate)等几个方面进行测试比较。实验参考软件为H.264的JM86基本档(baseline)，编码器主要参数设置为:帧率30 f/s(帧/秒)，帧结构为IPPP，采用JM默认的运动估计算法，QCIF序列的搜索范围为±16，CIF序列为±32，5个参考帧，采用RDO优化，CAVLC编码。实验平台为:CPU为奔4双核3 GHz，2 Gbyte内存，Windows XP操作系统。

为了对算法性能进行客观比较，本文对不同画幅和运动类型的多个标准测试序列进行了测试，每个序列编码前100帧，编码结果如表4所示，其中QP=28。各项编码性能指标的变化幅度定义如下

式中:PSNRproposed和PSNRJM分别指本文快速算法和JM86标准算法的编码峰值信噪比;ΔTime指编码时间的变化幅度，-Δ表示快速算法降低了编码时间;ΔRate指码率的变化情况，+Δ表示快速算法的码率有增加。

从表4可以看出，与采用所有参考帧遍历搜索的JM标准相比，本文提出的多参考帧快速选择算法可以大幅降低计算量，平均可降低49.12%的编码时间。与此同时，码率平均仅增加0.28%，图像质量的损失平均为0.02 dB，这样的损失对编码R-D性能的影响是微不足道的，对画面视觉质量的影响基本可以忽略。

表4 本文算法性能以及和H.264标准算法的对比

表5和表6是本文快速算法与其他几种快速算法的性能对比。其中，文献［3］根据空间相关性确定参考帧数目;文献［4］利用时空相关性确定当前宏块的编码模式及参考帧数目;文献［5］根据边缘梯度检测以及运动矢量差值情况来确定候选参考帧;文献［9］根据运动矢量中心偏置特性，结合快速运动估计算法来减少每个参考帧的计算量。

表5 各快速算法的性能对比(CIF，QP=28)

表6 各快速算法的性能对比(QCIF，QP=28)

根据表5和表6的数据对比，本文快速算法的图像质量PSNR和码率都要明显优于其他算法，即本文算法的R-D性能明显优于其他快速算法。在计算量方面，本文算法大幅领先于文献［9］和文献［5］的算法，但是不及文献［4］和文献［3］。这主要是因为文献［4］的算法中加入了编码模式的预判;而文献［3］的算法中加入了Skip模式的快速确定。但本文算法是纯粹的多参考帧快速选择算法，能与其他类型的快速算法(例如快速模式选择、快速运动估计等)结合，这将能获得更好的编码速度。

4 小结

根据移动视频业务的要求，针对多参考帧预测技术计算

[9] LIN CY，CHANG S F.Semi-fragile watermarking for authenticating JPEG visual content[C]//Proc.SPIE Security and Watermarking of Multimedia Content II.San Jose，CA：[s.n.]，2000：140-151.

[10] HO A T S，ZHU X，GUAN Y.Image content authentication using pinned sine transform[J].EURASIP Journal on Applied Signal Processing，2004（14）：2174-2184.

[11] 胡玉平，陈志刚.用于图像认证的小波域半易损水印算法[J].电子学报，2006，34（4）：653-657.

[12]MATRO K，SUN Q，CHANG S，et al.New semi-fragile image authentication watermarking techniques using random bias and nonuniform quantization[J].IEEE Trans.Multimedia，2006，8（1）：32-45.

[13] TSAI M J，CHIEN C C.Authentication and recovery for wavelet based semi-fragile watermarking[J].Optical Engineering，2008，47（6）：1-10.

[14] 高铁杠，谭琳，曹雁军.基于Hash函数和汉明码的半脆弱水印算法[J].光电子·激光，2012，23（9）：1808-1814.

[15]CHANG CC，CHEN K N，LEE C F，et al.A secure fragile watermarking scheme based on chaos-and-hamming code[J].Journal of Systems and Software，2011，84（9）：1462-1470.

[16] 陶孟益，唐军，杨恒伏，等.基于自适应半脆弱水印的图像篡改检测方案[J].电视技术，2014，38（15）：41-43.