摘 要： 提出了一种基于预测的自适应六边形搜索方法，并将此算法与其他常用的快速运动估计" title="运动估计">运动估计算法进行实验比较。实验结果表明：该算法有效地降低了搜索点数，搜索精度比较接近于FS算法，在一定程度上提高了搜索的效率。
    关键词： 视频压缩  运动估计  快速搜索

    当今时代，信息技术和计算机互联网飞速发展。为适应技术发展和应用的要求，各种多媒体数据压缩编码技术也在不断发展中，其中视频压缩技术一直是人们研讨的热点。
    视频图像处理实时性要求高，而且视频图像数据量庞大，因此必须对它进行压缩。同时人们注意到，视频图像存在很强的帧间/帧内冗余，为了消除帧间冗余，人们普遍采用运动估计算法" title="估计算法">估计算法和运动补偿算法。运动估计算法的优劣直接影响视频编码的效率和质量。运动估计算法是块匹配算法，如何快而准地在参考帧中搜索到最佳的匹配块是块匹配算法的核心。本文对现有的搜索法进行分析，并给出基于预测的自适应六边形搜索法。
1 对已有搜索算法的分析
    常用的快速搜索算法有：二维对数搜索算法(TDL)、共扼方向搜索算法(CS)、三步搜索算法(TSS)、菱形搜索算法（DS）等。其中，菱形搜索法又叫钻石搜索法，以菱形模板形状而得名，其算法简单高效，是现有性能最优的快速搜索算法之一，被MPEG-4采用。
    在搜索最佳匹配点时，选择小的搜索模板可能会陷入局部最优，选择大的搜索模板可能增加计算量。DS算法采用两种搜索模板：大钻石搜索模板（LDSP）和小钻石搜索模板（SDSP），如图1所示。图1(a)为大钻石搜索模板，该模板包括围绕中心点" title="中心点">中心点的8个点，共计9个点，形成一个大钻石形；图1(b)为小钻石搜索模板，该模板包括5个点，形成一个较小规模的钻石形。

                     
    DS算法的搜索思想是先用LDSP搜索，由于步长大、搜索范围广，可以实现粗定位，使搜索不会陷于局部最小。当粗定位结束时，可以认为最优点就在LDSP周围8个点所围的菱形区域中。然后用SDSP实现最佳匹配块的准确定位，使搜索不至于有较大的起伏，从而提高运动估计精度。
    DS搜索法缺乏自适应性，不管运动矢量是大是小均采用LDSP模板进行粗定位。这样，对于小运动矢量来说，势必会有很多冗余的搜索。因此有必要对DS搜索法进行改进。
2 改进的快速搜索方法
    本文提出一种基于预测的自适应六边形搜索法，该算法主要包含以下几项核心技术：预判别零运动矢量，设定阀值对静止块直接终止运动估计；使用空间相邻块和时间相邻块估计当前块的运动类型；根据运动类型自适应选择搜索起始点；结合使用六边形搜索法和小钻石形搜索法的搜索策略。下面对具体的技术加以介绍。
2.1 预判别零运动矢量
    视频序列的运动矢量具有中心偏移特性，即运动矢量高度集中在搜索窗口的中心附近。其中零运动矢量占有很大的比重，而且零矢量对编码也是很有用的。
    设定阀值Th，在搜索前首先检测（0，0）矢量。在进行块匹配时，一般采用SAD准则。如果满足SAD(0，0)则认为该块属于静止块，其最优运动矢量就是(0，0)，此时直接终止搜索，不需要进行运动估计。

    阀值Th的选择很重要。如果太小，该方法的优势体现不出来；如果太大，则会将一些非静止块误判为静止块。经验表明，取Th=900时，大约50%的块被判为静止块，可以不做运动估计，而且图像质量主观上没有下降。
2.2 判定运动类型
    在视频序列图像中，物体运动是连续的，即在时间域和空间域上相邻宏块" title="宏块">宏块的运动矢量是缓慢变化的。在大多数情况下，当前宏块的运动矢量与帧内和帧间相邻宏块的运动矢量有着相同的大小和方向。因此，描述物体运动的宏块的运动矢量在时间上和空间上具有很强的相关性。利用运动矢量的这种时间上和空间上的相关性可以对当前宏块的运动矢量进行预测，该初始运动矢量在一定程度上反映了当前块的运动情况，利于随后进行自适应搜索。实验统计表明，当前块与帧内上方、左方和右上方的子块" title="子块">子块的相关性最强，而与其他位置子块的相关性则较弱。本文选取与当前块相关性最强的三个空间相邻子块(上方、左方和右上方的子块)和参考帧中相同位置的对应点作为侯选点进行预测(即图2中的块1，2，3，4)。

                            
    令运动矢量集合V={V₀，V₁，V₂，V₃，V₄}，V₀=(0，0)，V₁=(x_i，y_i)，i=1，2，3，4，分别表示块1，2，3和4的运动矢量。l_i=|x_i|+|y_i|，L=max{l₁，l₂，l₃，l₄}。设定阀值L₁和L₂，且L₁≤L₂。当L≤L₁时，当前块被认为是小运动块；当L₁2时，当前块被认为是中等运动块；当L≥L₂时，当前块被认为是大运动块。

2.3 预测搜索起始点
    如果当前块为小运动块或者中等运动块，则最优运动矢量常位于（0，0）附近较小的区域内，不必预测搜索起始点；如果当前块为大运动类型，则最优运动矢量偏离（0，0）点较大，而预测的搜索起始点更接近最优运动矢量，所以需要预测搜索起始点。
    预测搜索起始点的方法有中值法、加权法和SAD比较法。本文采用SAD比较法，选取与当前块相关性最强的三个空间相邻子块(上方、左方和右上方的子块)和参考帧中相同位置的对应点作为侯选点进行预测（即如图2中的块1，2，3，4），比较当前块与上述块的绝对误差和SAD，然后选取SAD最小的块作为预测起点。
    令运动矢量集合V={V₁，V₂，V₃，V₄}，对应的块失真度分别为{SAD₁，SAD₂，SAD₃，SAD₄}，当SAD_n=min{SAD₁，SAD₂，SAD₃，SAD₄}时，运动矢量所对应的点即为搜索起始点。
    利用SAD比较法对各预测矢量进行比较，取SAD最小者作为搜索起始点。从预测精度的角度考虑，使用SAD比较法最好，结合适当的搜索策略，能够最快地找到最优运动矢量，同时使用SAD比较法得到的搜索起始点必然是某个相邻块的运动矢量，使得运动矢量场具有连续性，利于差分编码。
2.4 搜索策略
    圆上的任意一点到圆心的距离都是相同的，如果能利用圆形作为匹配模板，则该模板在各个搜索方向都具有相同的搜索速度。但考虑到计算的复杂度和图像序列的实际情况，本文采用六边形搜索法，包含如图3(a)所示的大六边形模板（HSP）和如图3(b)所示的小钻石模板（SDSP）。
                                      

    搜索时，先用HSP模板进行粗定位，当最小块误差点出现在中心点处时，可以认为最优点位于六边形所围的区域内。这时再用SDSP模板准确定位，SDSP模板5个点中误差最小的点就是最优匹配点。六边形搜索法的搜索过程如图3(c)所示，具体搜索过程如下：
    (1)用HSP搜索法进行匹配运算，如果最小块误差（MBD）点出现在中心点，则转(3)，否则转(2)；
    (2)以上一次找到的MBD点为中心点，转(1)；
    (3)以上一次找到的MBD点为中心点，用SDSP模板代替HSP模板进行匹配运算，在SDSP下的5个点中，MBD点的位置即提供最佳匹配块的运动矢量。
    比较大六边形搜索法和小钻石搜索法，不难而知，HSP模板包含7个搜索点，而LDSP模板包含9个搜索点，因而在粗定位时HSP搜索法比 LDSP搜索法计算复杂度低。而且，HSP比LDSP更接近于圆，其水平方向的顶点到中心点的距离为2像素，对角方向的顶点到中心点的距离为像素。使用HSP在匹配窗移动时，沿水平方向模板的梯度下降速度为2像素/步，沿对角方向模板的梯度下降速度为像素/步，高于LDSP像素/步的搜索速度，且新增搜索点数与方向无关，不管最小点在六边形的边点还是角点，在进行下一次搜索时，都只需要计算3个点。由六边形大模式切换到SDSP模式和DS方法相同。
3 实验结果
    为了验证算法的有效性，选取几种有代表性的快速运动估计算法：FS、TSS、DS等算法，和本文提出的基于预测的自适应六边形算法在相同的条件下进行对比实验。使用的子块大小为16×16像素，搜索窗大小为15像素，匹配准则选用SAD准则。测试序列选用两个QCIF格式视频序列“Mother & Daughter”和“Foreman”，其中，“Mother & Daughter”序列是小运动序列，“Foreman”是大运动序列。对这些序列进行运动估计，计算其PSNR和平均搜索点数，实验结果如表1和表2所示。

                           
    观察表1可以发现，对于小运动序列“Mother & Daughter”，FS算法需要搜索225个点，DS算法需要13.85个点，而本文提出的算法只需要计算2.86个点就可以找到最优运动矢量。对于大运动序列“Foreman”，也有效地降低了搜索点数。
观察表2可以发现，FS算法的平均PSNR值最高，说明FS算法的搜索精度最高。本文提出的算法的搜索精度高于DS算法的搜索精度，比较接近于FS算法的搜索精度。
    总结本文提出的运动估计算法可以看出，它从几个方面对传统的运动估计算法做了改进。首先，在宏块的运动估计中，以DS搜索法为基础，提出了基于预测的六边形搜索法，减少了计算量，提高了搜索速度；其次，搜索具有自适应性，可以根据运动块的类型确定搜索策略。
    实验结果表明，新的算法有效地降低了搜索点数，搜索精度也比较高，特别是进行小运动估计，搜索点数少，搜索速度更快。
参考文献
[1] 钟玉琢，王琪，贺玉文．基于对象的多媒体数据压缩标准——MPEG-4及其效验模型[M]．北京：科学出版社，2000．
[2] 郑翔，叶志远，周秉锋．JVT草案中的核心技术综述[J]．软件学报，2004，(1)：58-68．
[3] Coding of Moving Picture and Associated Audio for Digital Storage Media at up to about 1.5Mbit/s[S].ISO/MPEG-1 ISO11172-2，1991．
[4] Information Technolog-Coding of Moving Picture and  Associated Audio for Digital Storage Media at up to about 1.5Mbit/s-Video[S].ISO/IEC11172-2，1993.
[5] 胡国荣．数字视频压缩及其标准[M].北京:北京广播学院，1999．
[6] 沈兰荪．视频编码与低速率传输[M]．北京：电子工业出版社，2001．
[7] H.26L Test Model Long Term Number 8.VCEG of ITU-T，Apr.2001．
[8] Test Model 5.Draft.ISO/IEC/JTC1/SC29/WGWG11，Apr，1993．