运动估计是去除视频序列" title="视频序列">视频序列相邻帧之间冗余信息的有效方法，对整个视频编码效果有重要的影响。由两大国际标准化组织(ISO/IEC的MPEG和ITU-T的VCEG)共同制定的最新的国际视频编码标准H.264/AVC仍然采用成熟的基于块的混合编码框架^[1]，但由于引入了很多新的编码技术，如多参考帧预测运动估计，从而可以提供更高的编码效率" title="编码效率">编码效率^[2]。
　　以前的视频编码标准如MPEG-4和H.263等都只支持一个参考帧预测。H.264不同于以前的标准，采用了多参考帧预测技术，使得运动搜索范围从原来的一个参考帧扩展为多个解码后的参考帧，这样通常能找到更精确的匹配，从而有助于获得更高的编码效率。但是多参考帧预测技术同时也存在一些缺点，对存储空间和计算能力要求更高^[3]。
　　H.264中引入的拉格朗日率失真最优策略采用穷尽搜索在所有候选参考帧中选择率失真成本最低的参考帧。拉格朗日率失真最优模式选择问题可表述为[4～5]:
　　
　　其中m=(m_x,m_y)^T表示某个运动矢量，REF表示某个参考帧，J_motion(s,c,m,REF∣λ_motion)表示在运动矢量m和参考帧REF下的率失真成本，s为原始的视频信号，c(m,REF)为在运动矢量m和参考帧REF下的重构视频信号，λ_motion为拉格朗日乘子，R(m-P)表示编码运动矢量m的比特数,R(REF)表示编码参考帧REF的比特数，SAD(s,c(m,REF))(Sum Absolute Difference) 为原始信号和重构信号之间的绝对差和，采用(2)式计算:
　　
　　其中B₁,B₂表示块的水平和垂直像素数，可以取值16, 8或4。
　　设m表示运动矢量搜索范围，若只允许一个参考帧进行预测，那么每个宏块" title="宏块">宏块需要搜索(2×m+1)²个候选点；若允许N个参考帧进行预测，那么每个宏块总共有N×(2×m+1)²个候选搜索点。这意味着，运动搜索的计算量、编码时间随着预测中总参考帧数成倍增长^[6]。允许的参考帧数越多，运动搜索的计算量、编码时间就越大。
　　为了减少上述多参考帧预测技术中存在的问题，本文利用相邻帧间很高的相关性提出了一种低复杂度的快速多参考帧选择算法。
1 快速多参考帧预测算法
　　在H.264运动估计中，多参考帧运动搜索过程在7种不同的块大小和形状条件下进行，按照从16×16到4×4的顺序依次进行。对于每一个块编码大小，需要在所有可能的参考帧中找出率失真成本最低的参考帧和其相应的运动矢量。多参考帧运动搜索过程首先从概率较高的参考帧REF(0)开始，一直进行到距离当前编码帧最远的参考帧REF(N-1)。
　　由于视频序列相邻帧间存在很强的时域相关性，一般情况下，最优的匹配通常位于与当前编码帧紧密相邻的参考帧，本文采用REF(0)表示这一参考帧；其余的参考帧(在本文中表示为REF(i), i=1,2,...,N-1，设允许的最大参考帧数为N)被选中的概率远远小于第一个参考帧REF(0)。
　　为了进一步了解不同参考帧在实际视频序列中被采纳的情况，本文选择了几个典型的视频测试序列，并利用拉格朗日率失真最优搜索策略，在不同参考帧数条件下统计不同参考帧的被选中概率，实验数据如表1所示。从表1可以看出，在所有参考帧中，REF(0)成为最优参考帧的概率最高，概率高达88.67%，而其余所有参考帧被选中的概率远远小于REF(0)。
　　从上述分析可知，参考帧REF(0)成为最终预测帧的概率最高，在这一参考帧中获得的运动搜索结果对整个编码性能" title="编码性能">编码性能有着重要的影响。因此，可以认为在REF(0)中的搜索范围越大，对整个编码性能的改善也会越大。相比较，由于其余的参考帧被选中的概率很低，而且每增加一个参考帧就会增加很大一部分计算量，所以在一定条件下合理地减少在这些参考帧中运动搜索的计算量，对整个编码性能不会产生显著影响。由于相邻帧间存在很强的时域相关性，前一个参考帧中运动搜索后得到的运动信息可以用来预测下一个参考帧的搜索中心。根据运动矢量的中心偏置定理，最优的运动矢量通常位于搜索中心周围的小范围里，利用螺旋搜索顺序，只需搜索这一小部分区域。

　　减少多参考帧预测计算量的思路如图1所示。在最重要的参考帧REF(0)中，搜索范围较大以保证取得较高的预测精度；而在其余不很重要的参考帧中，可以选择较小的搜索范围，同时利用前一帧已得到的运动信息预测下一帧的搜索中心。这样既能减少计算量，同时又不会显著影响整个编码性能。

　　本文提出了一种减少多参考帧预测计算量的快速算法。本算法不仅利用了运动矢量的空域相关性来预测第一个参考帧REF(0)的搜索中心，即利用当前宏块周围的三个空域相邻块的中值运动矢量来预测REF(0)的搜索中心；而且利用了运动矢量的时域相关性，即利用前一帧REF(i-1)所得到的运动信息对下一个参考帧REF(i)的搜索中心进行修正。由于相邻帧间存在很高的时域相关性，下一帧的最优运动矢量很可能就位于修正后的搜索中心附近，只需对搜索中心周围的很少一部分候选点进行匹配运算。这样就省略了很大一部分运算量。
2 模拟结果和分析
　　为了测试本文算法的性能，本文采用H.264参考软件JM7.0作为实验平台。实验参数设置如下：6个典型的视频测试序列(Silent、Mobile、Foreman、Template、Bus 和Suzi)、CIF(352×288) 或QCIF(176×144) 图像格式，每个序列150 帧, 帧率为30f/s，运动矢量搜索范围为16，量化参数为32, 采用Hadamard transform，GOP结构为IPPP。

　　表2列出了本文提出的算法与原始的采用穷尽搜索的拉格朗日率失真最优模式选择方法的比较结果。在表2中，△PSNR表示平均峰值信噪比(PSNR)下降值，单位为dB，△bits表示平均码率增长百分数，△time表示运动估计编码时间的减少百分数。△time和△bits分别采用式(3)和式(4)得到：
　　
　　其中T_original和B_original分别表示采用原始方法时所用的运动估计编码时间和总比特数；T_proposed和B_proposed分别表示采用本文提出的方法时所用的运动估计编码时间和总比特数。
　　从表2中的实验数据可以看出，与原始的采用穷尽搜索的拉格朗日率失真最优模式选择方法相比，本文提出的算法可以使运动估计编码时间平均减少15.18%，同时平均PSNR仅仅下降0.077dB，码率增长仅仅1.56%(5个参考帧情况下)。此外，对比不同参考帧数的实验结果，很容易发现允许的参考帧数越多，节省的编码时间就越多。
　　模拟结果表明本文提出的算法可以节省H.264多参考帧运动预测的计算复杂度，同时对率失真性能的影响很小。这对H.264编码的实时实现很有利。
参考文献
1 Joint Video Team (JVT) of ISO/IEC MPEG & ITU-T VCEG:Draft ITU-T Recommendation and Final Draft International Standard of Joint Video Specification.Doc.JVT-G050. 2003
2 Iain Richardson.H.264 and MPEG-4 video compression, video coding for next-generation multimedia.Wiley, UK.2003
3 Yu Wen Huang, Bing-Yu Hsieh, Tu-Chih Wang, etc.Analysis and reduction of reference frames for motion estima-tion MPEG-4 AVC/JVT/H.264. Proceedings International Conference on Multimedia and Expo, ICME, 2003;2(3):145～148
4 H.Chung, D.Romacho, A.Ortega.Fast long-term motion esti- mation for H.264 using multiresolution search. Proceedings. 2003 International Conference on Image Processing, 2003;1:905～908
5 X.Li, E.Q.Li, Y.K.Chen.Fast multi-frame motion estimation algorithm with adaptive search strategies in H.264. ICASSP, Proceedings. (ICASSP ′04). IEEE International Conference on Acoustics, Speech, and Signal Processing, 2004;3:369～372
6 M.J.Chen, Y.Y.Chiang, H.J.Li, M.C.Chi.Efficient multi-frame motion estimation algorithms for MPEG-4 AVC/JVT/H.264.Proceedings of the 2004 International Symposium on Circuits and Systems, ISCAS ′04.,2004;3:737～740