视频编码标准H.264运动矢量搜索算法

张永轩,霍家道

(江苏自动化研究所,江苏 连云港　222061)



视频编码标准H.264运动矢量搜索算法

张永轩,霍家道

(江苏自动化研究所,江苏 连云港222061)

高清视频的信息量巨大,传输比较困难。H.264作为视频压缩的主流标准,可以有效去除视频的冗余信息,提高视频的网络传输能力。针对H.264中运动估计算法耗时严重的问题,提出一种新的X型搜索算法。X型算法由粗到细地进行搜索,先以X型快速搜索确定运动矢量的可能范围,然后在可能范围内进行局部全搜索,最终确定运动矢量。试验结果表明,X型搜索能够在保证视频质量的情况下大幅度缩短编码时间,有效提高运动估计算法的效率,兼顾了速度与精度,为高清视频的实时传输提供了保障。

H.264;运动估计;X型搜索

多媒体的进步深刻影响着人们生活、工作的方式和质量。视频因为其直观、生动的特性,受到广泛的关注。然而,随着视频清晰度的提高,所包含的信息也越来越多,视频传输的实时性问题日益突出。H.264作为视频压缩的主力军,在保证了视频质量的前提下,提供了足够的压缩比,保证了高清视频传输的实时性。由于活动图像邻近帧中的景物具有一定的相关性,可将活动图像分成若干块,并搜索出每个块在邻近帧的位置,两者之间的相对偏移量就是对应块的运动矢量,这就是运动估计算法[1]。例如,当前帧内的汽车作为一个分割块,在邻近帧内找到同样的汽车,那么传输时只要传递一个汽车的图像和相对的运动矢量,就可以知道汽车在邻近帧的位置,大幅度压缩了传输的信息量,节约了传输带宽。运动估计算法作为H.264标准的核心技术,也是H.264耗时最严重的部分,占据了整个视频编码时间的50%-80%。因此,怎样在保证视频质量的前提下缩短运动估计的时间对高清视频的实时处理具有重要的意义。

1　H.264运动估计几种核心算法介绍

本节介绍了几种主要的运动估计算法,示意图中的点代表搜索块的中心像素,假设分割块的尺寸为4*4。通过将中心像素对应的搜索块与原始图像块进行匹配计算,得到最优匹配块。

1.1全局搜索算法

全局搜索算法[2]是最早提出的运动估计算法,其本质就是在搜索范围内,对每一个块都与当前块做匹配计算,找到匹配误差最小的点。这种算法准确率最高,但计算量急剧增加。这对于高清视频传输是极其不利的,所以很少有实际应用。

1.2三步搜索算法(TTS)

三步搜索算法[2]是美国人Koga et al在1981年提出的。它的算法简单易行,鲁棒性强,预测的结果与全局搜索比较接近,但在算法第二步中步长被直接减半,如果初始预测矢量的位置有较大误差,就很容易陷入局部最优的困境。这种算法对于运动幅度小的图像处理效率较低[2]。具体步骤如图1所示。

图1　三步搜索算法

1.3菱形搜索算法

菱形搜索算法[2]简单、高效而且准确,是目前性能最好的算法之一。在搜索时,首先用大菱形模板进行快速搜索,直到中心匹配块为最优匹配,再用小菱形模板进行小范围搜索,取得最优匹配。大模板和小模板的使用,不仅提高了搜索速度,而且兼顾了搜索精度。具体步骤如图2所示。

图2　菱形搜索算法

2　改进的运动估计算法

快速算法相较全搜索算法而言,有效减少了计算的次数,但也存在以下两个问题。

1)快速算法大部分遵从由粗到细的原则进行搜索,在初期的搜索中,主要任务是用最少的搜索次数确定运动矢量的大致范围,而通常的快速算法初期搜索的模板搜索点数过多,要进行10次左右的匹配计算,还不够“快”,而且模板的搜索重心在水平和垂直方向上,不符合物体运动规律。

2)全搜索计算量巨大,而快速算法为了减少计算次数,不可避免地会漏掉很多点的匹配计算,如果不能合理解决这个问题,会很容易陷入局部最优的困境。

2.1对角线式快速搜索确定运动矢量范围

图3　物体斜方向运动匹配搜索示意图

2.2局部全搜索避免局部最优

针对问题2),由于全搜索计算量太大,快速算法又不可避免地要省略一些点的匹配计算,所以很难找到最优匹配块。为了减少匹配精度的损失,本文提出局部全搜索的方法。在确定运动矢量大致范围后,计算水平和垂直5个位置(A,B,C,D,E)的匹配程度,不仅可以弥补水平和垂直方向搜索的不足,还可以进一步缩小搜索范围,在小范围内进行全搜索,在提升搜索速度的前提下达到次优匹配的目的,避免局部最优的尴尬。具体的搜索范围分割如图4所示。

图4　局部全搜索分割示意图

2.3X型搜索算法

综合针对两个问题的解决方法,本文提出一种新的运动矢量搜索算法——X型搜索算法。具体步骤如图5所示。

图5　X型搜索算法

主要步骤:

步骤一:预测步长d=2,在中心块和周围4个角上进行匹配测试,若最佳匹配块在中心块,则执行步骤二,否则以最佳匹配块为中心块,重复步骤一。

步骤二:以中心块为原点,计算水平和垂直方向d=2的4个块及中心块,共5个块的匹配程度,得到最优匹配块,执行步骤三。

步骤三:若最优匹配块不在中心块,则搜索当前最优块和周围5个块;否则搜索中心块周围8个块综合比较,选出最优匹配块。

运动矢量具有零点偏置性[4],所以本文将预测步长设置为2。步骤一和步骤二快速确定运动矢量的大致范围,步骤三进行了水平和垂直方向上的搜索,弥补了水平和垂直方向搜索的不足,同时确定了局部全搜索的范围。步骤四局部全搜索是在小范围内进行全搜索,保证了搜索的精度,避免预测矢量陷入局部最优的尴尬,兼顾了搜索速度与运动矢量的准确性。

3　运动估计算法匹配准则

为了方便比较几种运动矢量搜索算法的匹配程度,需要一个比较标准。最常用的有均方误差(MSE)、平均绝对误差(MAE)和绝对误差和(SAE),假设当前块大小为N*N,则具体算法如公式(1),(2),(3)所示。

(1)

(2)

(3)

式中,Cij表示当前块(i,j)处的像素,Rij表示参考块的相应像素,i,j表示像素在块内水平和垂直方向上的编号。计算结果越小,表明差异越小,匹配程度越高。

SAE算法全是加减运算,没有除法运算,绝对值的计算与平方相比,也要简单许多,有利于减轻硬件的计算压力,提高运算速度。所以,本文采用SAE作为匹配程度的标准。

4　实验结果分析

本文以官方提供的H.264编解码器JM86为平台,测试各个运动矢量算法。实验采用6种搜索算法对不同复杂度的3个视频序列进行测试,得到的实验数据如表1所示,X型搜索的解码图像与初始图像的成像对比由图6,7,8所示。

图6　Foreman成像对比

图7　ICE成像对比

图8　SOCCER成像对比

对视频压缩性能的评价主要看压缩比和解码视频的质量,在保证视频质量的前提下提供最大的压缩比是视频压缩算法的目标。接下来对试验的几个主要参数进行分析。

压缩比:在实验中,视频编码的速度始终都控制在30帧/秒,所以码率可以反映视频的压缩程度。从表1能够看出,X型搜索在三种视频序列中,虽然码率比全搜索要高,但高的有限,而且与其他公认的快速算法比相差不多,所以X型搜索算法在压缩比上是符合要求的,视频压缩后冗余度不大,有利于传输。

信噪比:信噪比反应了图像还原的程度,可以看成视频质量,是运动估计算法的一项重要参数。Foreman视频序列的复杂度一般,主要是人物面部表情的运动,背景几乎静止,但又不单调。从表1可以看出,X型搜索算法的信噪比中等,比全搜索稍有降低,但与其他快速算法相差不多,不影响视频的主观质量。ICE视频序列主要是人物运动,背景是冰面,单调而且很相似。在这种视频中X型搜索的信噪比稍低,但不会造成视频的主观质量下降。SOCCER视频序列较为复杂,人物的运动较多,背景是细节较多的草坪。从实验数据可以看出,X型搜索的各项参数都是前列的,信噪比很高,很好地保留了视频的细节信息。

编码时间:编码时间是最重要的数据。在三种复杂程度的视频序列编码中,X型搜索的编码时间都只占全搜索的40%-50%,运动估计的时间更是只占10%-15%,编码速度稳占第一,反应了X型搜索良好的搜索效率,而且视频越复杂,细节越多,优势越明显。

表1.　运动估计实验数据对比

5　结束语

本文提出的X型搜索遵循由粗到细的搜索原则,在保证视频质量的前提下,兼顾了搜索速度和精度,能够大幅度去除视频冗余信息,提高视频的压缩比,尤其适合运动多细节的视频编码,有效提高了帧间预测中运动矢量估计算法的搜索效率,为高清视频的实时编码提供了有力手段。

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

[2]王文芳.H.264帧间预测算法研究与FPGA设计[D].北京：北京交通大学,2009.

[3]陈佳,田泽，等.H.264/AVC视频编码核基于FPGA验证的设计与实现[J].计算机技术与发展,2013,23(7),10-13.

[4]张子敬.H.264多核DSP并行算法研究[D].连云港：江苏自动化研究所,2013.

[5]钟明光.H.264编码器的研究及其部分算法的FPGA实现[D].西安：西安电子科技大学,2013.

[6]车文斌.H.264解码器的FPGA验证[D].哈尔滨：哈尔滨工业大学,2013.

[7]刘洋.H.264运动估计算法的研究与FPGA验证[D].西安：西安理工大学,2012.

[8]罗亮.高清视频编解码电路设计[D].西安：西安工业大学,2015.

[9]张玢.基于FPGA的H.264视频编码芯片验证平台设计[J].渭南师范学院学报,2013，28(9)：74-77.

[10]刘杰,王旭柱.基于H.264的一种视频编码算法的研究与FPGA实现[J].中国新技术新产品,2014(7)：25-26.

Research of The Motion Vector Search Algorithm of H.264

ZHANG Yong-xuan,HUO Jia-dao

(Jiangsu Automation Research Institute,Lianyungang 222061,China)

HD video has large amount of message,so it’s difficult to transport.To improve the real-time transmission ability of HD video,we can use H.264 to compress it.Aiming at the problem of the serious time-consuming of H.264’s motion estimation,this paper propose a new method X-research.X-research search from widely range to details,first search for the possible range of motion estimate algorithm with X form,then search completely in partition.Considering of both sufficiency and precision,then fix the motion estimate algorithm finally.Based on the experiment,X-research can reduce the coding time greatly,and improve the efficiency of H.264’s motion estimation effectively.It provide guarantee to HD video’s real-time transmission.

H.264; motion estimate algorithm; X-research

1673-3819(2016)05-0062-04

2016-05-18

2016-06-21

张永轩(1990-),男,江苏连云港人，硕士研究生,研究方向为H.264视频编码。

霍家道(1970-)，男，博士，硕士生导师。

TN919.81

ADOI:10.3969/j.issn.1673-3819.2016.05.013