基于H.264的新型快速搜索算法研究
2008-01-18
作者：陈 航1，陈占计2，陈 芳3
摘 要：根据视频序列最优运动矢量的分布特性，提出了一种新型快速搜索" title="快速搜索">快速搜索算法。仿真表明，该算法在不改变重建图像质量的条件下，大幅减小了搜索点数，提高了搜索效率。
关键词：H.264 运动估计 搜索算法 SCSP 阈值 中值预测
在H.264标准中，提高运动估计算法效率的主要技术可以归纳为三类：一是起始搜索点的选择，二是更高效的块匹配准则，三是减少搜索点数的搜索策略。其中，效率最高、使用最多的是第三类[1]。
目前，块匹配运动估计算法中搜索精度最高的是全搜索法FS(Full Search Method)[2]，但它计算量大，不适合实时应用。为此，人们提出了许多快速运动估计算法，如交叉法CSA(Cross Search Algorithm)[3]、菱形法DS(Diamond Search)[4]、六边形法HSP(Hexagon Search Pattern_)等。
1 经典搜索算法分析
1.1 交叉法
交叉法CSA是在二维对数法TDL和三步法TSS基础上，为进一步减少计算量而发展起来的快速搜索算法。其搜索策略是：从原点开始，以最大搜索长度的一半为步长，以“×”字形分布的5个点构成每次搜索的点群，搜索计算得到MBD(Minimum Block Distortion)点，以该MBD点为中心点" title="中心点">中心点，步长减半，继续做“×”字形搜索，直至步长为1，之后根据MBD点的位置，分别做“+”字形或“×”字形搜索，从而获得全局最优运动矢量，如图1所示。
1.2 菱形搜索" title="菱形搜索">菱形搜索法
菱形搜索法DS采用2种搜索模板，分别为大菱形搜索模板LDSP（Large Diamond Search Pattern）和小菱形搜索模板SDSP（Small Diamond Search Pattern）。LDSP需计算9个搜索点的SAD（Sum of Absolute Difference）值，而SDSP只需计算5个搜索点的SAD值。其搜索策略是：先以预测的起始搜索点为中心点，计算LDSP中9个点的SAD值，如果MBD点不为中心点，则重复LDSP直至MBD点为中心点，之后转入SDSP，计算5个点的SAD值，SAD值最小点对应的运动矢量为全局最优运动矢量，如图2所示。
1.3 六边形搜索算法
六边形搜索算法是对菱形搜索法的改进，它将DS算法中的LDSP改为六边形，而SDSP仍然保留, 如图3所示。
1.4 优缺点分析
现有搜索算法大都采用大、小两种搜索模板，且先采用大的搜索模板，再转向小的搜索模板。但在实际应用中，视频图像的大部分区域没有发生变化或变化甚微，因此，当运动矢量很小或为零时，会造成极大的搜索冗余，降低了搜索效率。
2 新型快速搜索算法
在众多视频图像中，相邻帧之间通常都具有极强的相关性，在运动平缓区域，这种相关性更加明显。由于视频对象的运动具有连续性，因此在描述视频序列运动特征的宏块" title="宏块">宏块(或宏块分割、亚宏块分割)运动矢量之间，也必然存在时空域的相关性，而相邻块间运动矢量的相关性就更强。统计数据表明，在诸多图像序列中，如视频会议、视频电话等，80%以上块的最优运动矢量分布在一个区域圆中，圆心为搜索窗口中心，半径为2个像素，如图4所示。基于此分布特性，本文提出一种新型搜索模板，即小交叉形搜索模板SCSP(Small Cross Search Pattern)，其搜索策略与交叉法CSA类似，不同之处是搜索步长固定为1个像素，如图5所示。
2.1 搜索模板的自适应选择
搜索模板自适应选择的基本思想是：根据当前块(即预测块)运动矢量的大小，对搜索模板进行动态改变，对于运动矢量较小的区域，即运动平缓区域，采用SCSP搜索模板；而对于运动矢量较大的区域，即运动剧烈区域，采用LHDSP（Large Hexagon Diamond Search Pattern）搜索模板。
多次测试foreman、football、bridge、highway、temple等序列后，本文取T=2为阈值，当运动矢量小于T时，判定当前块为静止块或准静止块，即采用SCSP搜索模板；当运动矢量大于T时，判定当前块为运动块，即采用LHDSP搜索模板。
2.2 当前块运动矢量的获得
获得当前块运动矢量的示意图如图6所示[5]。首先，设E为当前宏块，其运动矢量为MVP。如果E的左侧多于一个块，令E左侧最上方块（图中为A块）的运动矢量为MVA，同理，可以得到E正上方最左侧块（图中为B块)的运动矢量为MVB、E右上方最左侧块(图中为C块)的运动矢量为MVC，采用运动矢量中值预测法可得：MVP=(|MVA|+|MVB|+|MVC|+1)/3。而当前块位于当前帧边缘时有三种情况：
(1)当前块位于当前帧最右边，MVP=(|MVA|+|MVB|+1)/2。
(2)当前块位于当前帧最左边，MVP=(|MVB|+|MVC|+1)/2。
(3)当前块位于当前帧最上边，MVP=MVA。如果右上角宏块不可用，可用左上角宏块的MV代替。
2.3 搜索策略
(1)确定起始搜索点后，比较当前块的预测运动矢量MVP与阈值T的大小。
(2)如果MVP≥T，则转移到第3步，否则，跳转到第4步。
(3)采用六边形法搜索：首先使用HSP模板搜索，计算7个点的SAD值，如果MBD点不为中心点，则重复HSP直至MBD点为中心点，之后转入SDSP模板搜索，计算5个点的SAD值， SAD值最小点对应的运动矢量即为全局最优运动矢量。
(4)采用小交叉法搜索：使用SCSP模板搜索，计算5个点的SAD值，如果MBD点不为中心点，则重复SCSP直至MBD点为中心点，该点对应的运动矢量即为全局最优运动矢量。
3 系统仿真" title="系统仿真">系统仿真与结果分析
为验证新算法的搜索性能，并与FS、DS进行对比分析，本文从搜索点数、峰值信噪比PSNR(YUV分量)和压缩比等三个方面进行系统仿真。其中，测试平台为JM8.2，测试长度为90帧，量化参数分别为QP=5、QP=29，测试序列采用具有很强代表性的bridge.cif(小运动序列)和football.cif(大运动序列)。另外，FS的搜索范围设置在±16之间。
三种搜索算法的性能比较如表1所示，其中，Y代表亮度分量，U、V代表色度分量。当测试序列为小运动序列时，系统仿真得到的搜索点数如图7所示；而测试序列为大运动序列时，系统仿真得到的搜索点数如图8所示。
由表1可以看出，在重建图像质量基本相同的条件下，FS算法的平均搜索点数要远远大于DS算法和新算法，因此，在图7和图8中没有画出FS算法的搜索点数。
分析仿真结果，可以得到如下结论：
(1)新算法、DS算法与FS算法相比，在PSNR值基本保持不变的条件下，大幅度减少了搜索点数，而新算法又明显优于DS算法，特别是在运动平缓区域，表现更加突出；
(2)不同的QP值对压缩比影响较大，QP越大，压缩比越高，从而更有利于实时通信；
(3)不同的QP值对搜索点数影响不大，但对PSNR值影响巨大，QP越大，PSNR越小，从而重建图像的质量也就越差。
本文基于最优运动矢量的分布特性，设计了一种小交叉形搜索模板，同时根据预测值与阈值的比较结果可知，自适应选择搜索模板，使搜索算法的性能得到进一步提高。仿真结果表明，新算法大幅度减少了搜索点数，提高了H.264的编、解码速度，促进了H.264的实时性应用。
参考文献
[1] 唐良瑞.图像处理实用技术[M].北京：化学工业出版社，2002.
[2] 丁贵广.Visual C++6.0 数字图像编码[M].北京：机械工业出版社，2004.
[3] GHANBARI M.The cross-search algorithm for motion estimation[J].IEEE Trans-Communication.1990，38(7)：950-953.
[4] ZHU S，MA K K.A new diamond search algorithm for fast block matching motion estimation[J].IEEE Trans-Image Processing.2000，9(2)：287-290.
[5] 毕厚杰.新一代视频压缩标准H.264/AVC[M].北京：人民邮电出版社，2005.