基于H.264的视频编码运动估计算法优化

摘要：针对H.264视频编码在运动估计定位及搜索时，现有算法普遍效率偏低、计算复杂度偏大的现状，本文从H.264视频编码的基本原理和编码过程入手，设计了在模式选择时的过滤方法，从而实现新了对运动估计算法的优化，仿真试验结果表明了该优化算法具有良好的搜索速度和准确的搜索结果。

关键词：H.264；视频编码；运动估计算法；模式过滤优化

1　引言

H.264是ITU-T浑和MPEG组联合专家组JVT制定的目前最新的视频编码标准，这一编码标准可以获得很高的编码效率，尤其是在低码率方面比MPEG-4有明显的提高，非常适合低宽带、高质量网络视频应用的需要。但是，H.264为了提高编码效率，采用了许多高计算复杂度的算法，使得编解码计算量很大，因此对软硬件的要求甚高，同时也加大了编解码的难度。因为在通常情况下，很多方法无法实现在有限硬件支持的条件下，使得编码质量达到最优。

为了使H.264能比较容易的在低码率高时性的应用系统中实现，必须对其编码算法进行优化。对H264编码器各个算法模块进行分析可以得出，运动估计模块的计算量占了整个编码器运算量的70％以上。因此，要对整个编码器进行优化，运动估计模块应作为首选。

2　研究背景

H.264在进行运动估计时，首选进行运动矢量预测，预测后获得初始运动矢量，把这个初始的运动矢量作为搜索中心进行块匹配搜索，收缩时采用全搜索算法，即给出搜索中心周围的一个范围，对该范围内矩形区域内的所有的点，都要计算一次匹配结果，从中选出最佳匹配点作为整像素搜索的结果。H.264的全搜索算法，优点是可以找到限定范围内的全局最优匹配结果，运动估计精度很高；其不足在于算法的复杂度太高，成为整个编码体系中最为耗时的一部分，因此，在尽可能小的质量损失前提下，提高运动估计搜索速度，是对H264进行优化的关键。

当前，对于H.264的视频编码运动估计算法，研究并应用的较为成熟的算法有很多，主要有三步查找算法、2D对数查找算法、新三步查找算法、四步查找算法、自适应块匹配算法，以及混合自适应查找算法。

上述各种运动估计算法，更多的是为低比特率视频应用服务的，因此除了考虑减少计算量从而进行快速运动估计外，他们更多的是考虑MSE性能，这是因为这些算法追求的目标是误差项尽可能小从而减少编码的长度；从运动分析的角度出发，考虑的更多的是匹配的准确性，从这个意义上讲，基于CCF的匹配准则和基于像素差的匹配准则更适合，尽管他们的计算量更大一些，另外，跟视频压缩比较起来，运动分析的计算量要小一些，因此减少计算量是值得考虑的，但是并不是考虑的重点，典型的运动估计算法解决方案通常采用减少搜索点以及设置阀值来降低计算的计算复杂度。经过大量的试验数据统计，可以发现很多块的模式（尤其在H.264中）可以直接确定，这样可以减少判断块的模式类型选择的过程，因此，结合上述分析，本研究课题试图提出一种在模式过滤基础上的运动估计算法，从而实现对传统的H.264视频编码运动估计算法的优化。

3　优化算法的实现

在标准的代码中，有10个模式可供选择，即SKIP，16×16，16×8，8×16，8×8，8×4，4×8，4×4，intra4×4和intra16×16。H.264在进行模式选择时，首先对当前块采用所有的模式进行运动估计，然后比较在每种模式下码率的大小，码率小的模式作为最终的选择模式。该过程是一个非常繁琐的搜索方法，它盲目的搜索了所有的候选模式，造成了冗余度很大的计算复杂度。

本研究课题所提出的对H.264进行运动估计编码算法的思想是，对所有的候选模式进行过滤，从而减少对运动编码模式定位搜索的耗时，因此该算法的关键是如何在10种模式中过滤出发生概率很小但又不影响编码效果的模式。

3.1候选模式的过滤

在很多现实的应用场合，尤其是视频电话和视频监控系统，其背景大部分都是静止的，因此在视频帧中有很多的8×8块都可以认为是静止的。通过数据统计发现，某一个8×8块可以直接被判定为静止块，只要它的SAD8×8值小于某一阀值T1。经过大量的视频测试数据显示，得到判断一个8×8子块为静止的阀值T1为150-300。考虑到阀值越大，产生的误差越大，因此取T1=150。即SAD8×8

经过试验的进一步发现，块的模式选择跟一个宏块中静止的8×8块个数密切相关。通过全搜索方法可获得最佳块模式在不同静止8×8块个数的条件下的累计概率，如表1所示，实际上，可以忽略那些概率小于0.1％的模式，因为它们对视频编码的质量影响不大，但是经过这些模式的排除却极大地降低了计算的复杂度。

表1各种模式在不同静止块个数下的积累概率

模式

N=4

N=3

N=2

N=1

N=0

SKIP

25.74%

7.65%

6.44%

6.78%

10.71%

16×16

0.31%

1.07%

3.46%

4.15%

12.00%

16×8

0.06%

0.21%

0.94%

1.33%

4.39%

8×16

0.04%

0.19%

0.99%

1.49%

4.64%

8×8

0.00%

0.01%

0.09%

0.52%

1.88%

8×4

25.54%

7.65%

6.44%

6.78%

10.71%

4×8

0.31%

1.07%

3.46%

4.15%

12.00%

4×4

0.06%

0.21%

0.94%

1.33%

4.39%

intra4×4

0.04%

0.19%

0.99%

1.49%

4.64%

intra16×16

0.00%

0.01%

0.09%

0.52%

1.88%

结合上表的概率统计，可以在不同情况下采用下面的标准来过滤那些影响因素小的块模式：用N记录一个宏块中SAD8×8

如果N=4，那么SKIP，16×16和intra16×16模式为候选模式；

如果N=3，那么SKIP，16×16，16×8，8×16和intra16×16模式为候选模式；

如果N=2，那么SKIP，16×16，16×8，8×16，intra4×4和intra16×16模式为候选模式；

如果N=1，那么SKIP，16×16，16×8，8×16，8×8，intra4×4和intra16×16模式为候选模式。

3.2多层模式的过滤

从上面的分析可以发现，在经过候选模式的初步过滤之后，每一种情况下仍然有不止一种的块模式可供选择，如何在剩下的几个模式中进一步过滤，以最快的实现运动估计定位搜索呢？

为了实现在初步过滤后剩下的多层模式中快速过滤定位运动估计模式，需要引入一种信的运动矢量预测值。在传统的运动估计中运动矢量的预测值，通常是假设块周围的运动矢量是一致和平滑的，因此对于某一个宏块而言，它通常把周围宏块的运动矢量、周围运动矢量的平均值或SAD值最小的宏块的运动矢量作为预测值。在很多视频序列中，可以发现一个宏块内部的块的运动矢量更能够提供一个好的预测值。例如，在一个宏块中可以分割成4个8×8块，而SAD值最大的那个8×8块的运动矢量可以很好的作为整个宏块和包含该块的上一层块的运动矢量的预测值，故该方法能够很快的实现通过运动矢量预测值实现对于多层模式的进一步过滤。其优越性尤其体现在当块周围的运动矢量场不是一个平滑区域的时候。

下面具体通过3个步骤来说明该过滤方法的有效性：

首先，对于在一个宏块中SAD最大的那个8×8块采用菱形搜索法得到其运动矢量；

其次，把得到的运动矢量作为包含该8×8块的上层块模式的运动矢量预测值(PMV)；

最后，定义一个该运动矢量预测值和真实运动矢量(MV)的差值(MD)公式：

；

上式中，PMVx和PMVy表示运动矢量预测值PMV的x、y分量；MVx和MVy表示真实运动矢量的x、y分量。

通过上式对MD进行计算，并通过大量统计试验找出MD的概率分布区间，如下表2所示，从而完成进一步的块模式的过滤，进而实现视频编码运动估计的快速定位和搜索。

表2真实运动矢量和预测值的差值MD的分布概率

MD=0

MD=1

MD=2

MD=3

67.69%

67.63%

90.26%

95.45%

57.78%

78.66%

87.34%

91.32%

62.21%

79.21%

82.43%

92.24%

63.53%

80.95%

89.10%

93.63%

通过对运动矢量预测值和真实运动矢量的差值MD的快速计算，利用差值MD作为进一步过滤的阀值准则，大大减少了编码运动估计模式判断选择的计算量，有效的提升了H.264视频编码的效率，有利于实现快速定位及搜索。

4　仿真分析

为了评价和衡量算法的优越性，把该算法移植到JVT的参考代码JM8.5版本中。采用一系列CIF（352×288）格式和代表不同运动轨迹的视频序列作为实验测试数据，同时在试验中，量化参数QP设置为20，24，28，32、36和40。搜索范围设置为[-16，15]，并且只参考一个参考帧，在试验中采用了H.264中基准的编码部分并且保证视频的输入频率为30fps；同时，采用峰值信噪比（PSNR）的变化、码率（bitrate）和编码的加速度作为实验的结果跟标准代码的结果进行比较。实验结果入表3所示：

表3模块过滤算法仿真试验结果

Sequence

QP

PSNR

(dB)

Bittare

Speedup

Sequence

QP

PSNR

(dB)

Bittare

Speedup

news

20

-0.10

0.94%

80.05%

flower

20

-0.04

1.01%

28.80%

24

-0.07

0.12%

77.59%

24

-0.04

1.21%

29.06%

28

-0.05

0.36%

72.47%

28

-0.03

1.41%

30.02%

32

-0.05

0.10%

64.35%

32

-0.02

1.92%

30.96%

36

-0.01

0.74%

58.32%

36

-0.02

2.56%

31.17%

40

-0.01

0.24%

51.19%

40

-0.03

1.63%

31.94%

akyio

20

-0.13

1.73%

79.04%

coastguard

20

-0.05

0.03%

24.66%

24

-0.09

1.74%

75.01%

24

-0.05

0.02%

23.21%

28

-0.03

1.52%

67.06%

28

-0.03

0.01%

21.66%

32

-0.05

2.15%

59.60%

32

-0.04

0.02%

19.30%

36

-0.06

1.75%

53.37%

36

-0.03

0.04%

21.76%

40

-0.02

2.29%

50.05%

40

-0.05

0.08%

20.02%

M&D

20

-0.11

0.25%

75.78%

foreman

20

-0.10

3.59%

51.83%

24

-0.07

0.62%

71.59%

24

-0.07

4.20%

51.42%

28

-0.03

0.84%

60.60%

28

-0.07

4.58%

47.79%

32

-0.01

0.54%

54.02%

32

-0.09

4.89%

43.63%

36

-0.04

0.21%

48.35%

36

-0.10

5.39%

47.06%

40

-0.06

0.14%

42.92%

40

-0.09

6.37%

36.27%

average

-0.058

1.53%

48.11%

从实验数据可以得出：同标准代码的实验数据相比，视频序列“akyio”、“news”和“M&D”中的峰值信噪比降低了0.065，同时码率上升了0.90%，但是提升了63.41％的编码加速度；另一方面，对于那些趋向于全局运动的视频序列包括“mobile”，和“flower”，提升了26.04％的编码加速度，峰值信噪比降低了0.034，同时码率上升了0.83％；而对于运动幅度剧烈且杂乱的视频序列“foreman”，峰值信噪比降低了0.086，同时码率上升了4.84%，但是提升了46.33％的编码加速度。

从上述实验数据看来，算法在视频编码的效果、码率以及编码速度之间取得了一个很好的折中，同时算法能够适用于各种不同的视频场合，尤其适用于那些背景变化幅度不大的视频场景，比如视频电话和视频监控等低码率的应用场合（尤其类似于视频序列中的“news”和“akyio”），而对于那些空间相关性很强的视频场合，算法提供的模式过滤方法也能提供很好的效果。

5　结语

本论文对块模式匹配的运动估计算法进行了改进，提出了一些传统算法很少解决但在很大程度上影响运动估计速度和性能的模式选择方法，克服了现有的搜索方式存在的通病——容易陷入局部最优而得不到全局最优的运动矢量，这比现有的运动估计算法更合理；同时，结合等级过滤块模式的方法能够更好的把点的匹配搜索与块的匹配搜索统一起来，因此既能够兼顾全局又有效的提升了搜索精度和速度。仿真测试表明，本算法可获得比一般的算法更小的匹配误差和更快的搜索速度。

参考文献：

[1] 毕厚杰. 新一代视频压缩编码标准——H.264/AVC[M]. 北京: 人民邮电出版社, 2005.

[2]T.Stockhammer, M.M.Hannuksela, T.Wiegand. H.264/AVC in wirelessenvironments[J]. IEEE Trans. Circuits Syst. Video Technol., 2003, 13(1):657-673.

[3]H.Malvar, A.Hallapuro, M.Karczewicz, L.Kerofsky. Low-Complexitytransform and quantization in H.264/AVC[J]. IEEE Trans. CircuitsSyst.Video Technol., 2003, 16(3): 598-603.

[4] 杨黎波. H.264视频编码快速算法研究[D]. 杭州: 浙江大学, 2005.

[5] 周敬利, 金毅, 余胜生等. 基于H.264/AVC视频编码技术的研究[J]. 华中科技大学学报(自然科学版), 2003, 31(8): 32-34.