摘 要： 针对视频压缩标准H.264中运动估计" title="运动估计">运动估计算法的特点，在兼顾视频图像" title="视频图像">视频图像质量和算法运行时间的基础上，提出了基于视频压缩的快速自适应菱形搜索" title="菱形搜索">菱形搜索算法。实验结果表明，该算法与菱形搜索算法相比，搜索时间平均减少了1.5ms, 信噪比平均提高了1.3dB。
    关键词： 视频压缩  自适应  运动估计  菱形搜索

    在多媒体传输和存储中，表示视频信息的数字需要大量的位数，对信道带宽和存储空间提出了很高的要求。相邻两帧之间存在很大的时间相关性，即时间冗余，而基于块匹配的运动估计算法是减少时间冗余的有效方法。目前视频压缩标准中[1]的经典运动估计技术有全搜索算法（ES）、三步搜索" title="三步搜索">三步搜索算法(TSS)及菱形搜索算法(DS)等。全搜索算法在所有运动估计算法中性能最好，但计算量过于庞大，实时性不很理想；三步搜索算法在搜索速度和效率上比全搜索法提高了许多，但没有穷尽所有的点，因而搜索误差较大，搜索精度和性能受到很大的影响；菱形搜索算法对于所有的视频序列，在搜索最佳点时，广度搜索和梯度下降搜索同时进行，即同等地对待搜索区域的各部分，造成较大的搜索冗余，影响了算法的搜索速度。为此，针对视频编码标准H.264中运动估计技术的特点，在兼顾视频图像质量和搜索时间的基础上，提出一种新的改进搜索算法——基于视频压缩的快速自适应菱形搜索算法ADS(fast adaptive diamond search algorithm)，减少了计算的复杂度并提高了运动补偿后的图像质量。
1 经典菱形搜索算法
    经典菱形搜索算法采用两种搜索模式：大菱形搜索模式和小菱形搜索模式。大菱形搜索模式由一个中心点和它周围的8个搜索点构成，步长为2。这9个点组成一个菱形，小菱形搜索模式由5个搜索点构成，步长为1。搜索步骤：第1步，最初的大菱形搜索模式以搜索窗口中心为中心点，计算大菱形的9个搜索点的误差函数。若误差函数最小的搜索点位于中心，则跳到第3步；否则跳到第2步。第2步，以第1步搜索的9个点中最小点为大菱形的中心点，计算大菱形的9个搜索点的误差函数。若误差函数最小的搜索点位于中心，则跳到第3步；否则，跳到第2步。第3步，以上一步搜索的9个点中的最小点为中心点，计算小菱形的5个点的误差函数。误差函数最小的块为最佳匹配快。
    菱形搜索算法虽然计算量少，但实现比较复杂，而且由于在搜索区中存在大量的搜索空区^[2，3]，所以存在搜索到非最优点的情况，从而使得帧间预测误差增大。针对实时性与估计精度^[4-6]这一对矛盾，提出一种基于视频压缩的快速自适应菱形搜索算法，根据运动矢量的时空相关性和中心偏向特性，预测当前块的运动矢量，减小了搜索的盲目性，较好地实现了视频图像的运动估计。
2 快速自适应菱形搜索算法
2.1 中心偏向性
    从研究一幅视频图像运动矢量的分布情况可以看出，在一定的门限判定条件下，（0，0）这个零矢量出现的概率极大。采用全搜索算法，搜索范围为（-15，-15）到（15，15），中心处为（0，0）矢量位置，在此处出现极大单峰。这一特性说明，在运动不太剧烈的情况下，运动矢量大量积聚在零矢量处，在预测下一帧当前块的运动矢量时可以优先考虑零矢量。
2.2 搜索模式的选择
    许多算法的搜索范围是固定的，搜索效率并不是很高。因为在视频图像序列的两帧之间，只有少部分有很大的运动，而且有相当一部分是没有运动的，如固定背景。若能根据不同的块运动情况而采用不同的搜索范围，则可节省计算量，所以应首先判断搜索起点的运动类型。
    因为搜索起点的绝对误差" title="绝对误差">绝对误差总和反映了该块某种程度的运动，搜索起点的绝对误差总和越大，意味着当前帧与前一帧之间的差异越大，这一块的位移可能越大，同时为在前一帧中找到最小的误差块，就需要对这一块做出大范围的搜索，否则只需要做出小范围的搜索。基于这样一个思想，初始运动矢量的绝对误差总和就可作为一个判断运动类型的依据，从而根据不同的运动类型，确定对应于各种预测结果所应采取的搜索范围以及搜索模式。绝对误差总和（SAD）由下式决定：

    式中，F(i，j)为被压缩的(m×n)宏块；G(i，j)为基准(m×n)宏块；(dx，dy)为搜索处的运动矢量，且dx={-p，p}，dy={-p，p}；p是搜索范围参数。

    根据绝对误差总和，把运动类型分为三类：当SAD1≤SAD≤T₂时，当前块为中速运动块, 可采用大菱形搜索算法进行搜索；当SAD>T₂时，当前块为高速运动块，可采用全搜索算法，以求得较好的搜索效果。由于这种块所占的比例较小，计算量的影响并不显著。式中，T₁、T₂为两个阈值。
2.3阈值的选取
    首先计算当前帧所选块与参考帧中的相同位置处的对应块的绝对误差总和，记为prev_SAD。则设

式中，α一般取为0.9<α<1.4，β取为1.2<β<2.5，且α<β，α、β属于经验值。

    若当前帧为第一帧，则不存在prev_SAD。通过大量的实验，在不影响视频图像质量并且考虑传输实时性的情况下，T₁取500左右，T₂取800左右。
3 仿真分析
    为了比较快速自适应菱形搜索算法的效果，采用8bit的视频图像序列对全搜索法、三步搜索法、菱形法以及快速自适应菱形搜索法在相同的条件下进行计算机仿真。
3.1 重建帧的比较
    采用susie（352×240）序列，块的大小为16×16，搜索范围P为7。以第五帧作为参考帧，分别用全搜索算法以及快速自适应菱形搜索算法得到第七帧的重建帧。可以看出，快速自适应菱形搜索算法重建的视频图像非常接近视频图像的原始帧, 结果如图1所示。

3.2 误差帧的比较
    为了直观地观察新算法的效果，用峰值信噪比(PSNR)和均方误差(MSE)来衡量各种运动估计技术的性能。对于8bit的视频图像来说，PSNR定义为：

式中，MSE表示均方误差，由下式决定：

式中，f(i，j)是视频图像序列的原始帧，g(i，j)是利用运动矢量重建的帧。仍然采用susie（352×240）序列的第一帧作为参考帧，块的大小采用16×16，搜索范围P为7。分别用ES算法、TSS算法、DS算法及ADS算法得到第二帧的误差帧。图2中所示为ADS算法和DS算法产生的误差帧。

3.3 性能的比较
    以MSE和PSNR作为衡量搜索算法性能的标准，通过用相应的搜索算法得到各自的性能，采用susie（352×240）序列为视频测试序列，块的大小为16×16，搜索范围p为7，分别用各种搜索方法计算视频序列中连续20帧的MSE和PSNR，实验结果如图3所示。

3.4 搜索匹配时间的比较
    采用missamerican（360×288）序列的第五帧作为参考帧，块的大小采用16×16，搜索范围P为7。在同样的环境下，分别用ES算法、TSS算法、DS算法以及ADS算法进行匹配得到恢复的第六帧，搜索匹配时间分别如表1所示。

    在上面的实验1中，采用susie（352×240）序列的第五帧，用ADS算法对其第七帧进行重建，从主观上看，ADS算法的重建视频图像非常接近原始的视频图像；在实验2中，采用susie(352×240)序列对误差帧进行比较，可以看出ADS算法比DS算法产生的误差平均降低了约300个数量级；在实验3中，采用susie（352×240）序列对算法进行性能比较，可得ADS算法的性能曲线都优于DS算法的性能曲线，峰值信噪比比DS算法平均提高了1.3dB，相应地均方误差也降低了。对于运动缓慢的视频序列，新算法的性能几乎逼近全搜索算法；在实验4中，用各种算法对missamerican(360×288)序列进行匹配，比较可得改进算法的搜索匹配时间比DS算法平均减少了约1.5ms。
    基于视频压缩的快速自适应菱形搜索算法，充分利用了视频图像序列的时空相关特性，采用了大小菱形搜索模式，实现了运动矢量高速而较精确的估计。仿真结果表明，与全搜索算法、三步搜索算法、菱形搜索算法等一些优秀算法相比，新算法的运动估计准确性高、预测质量好。在可视电话、终端会议等的实时视频通信中，该算法可取得较好的效果。
参考文献
[1] 朱秀昌，刘峰，胡栋.数字图像处理与图像通信[M].北京：北京邮电大学出版社，2002.
[2] KELLER Y，AVERBUCH A.Fast motion estimation using bidirectional gradient methods[J].IEEE Trans.Image Processing，2004，13：1042-1054.
[3] ZHU S，MA K K.A new diamond search algorithm for fast block-matching motion estimation[J].IEEE Trans on Image Processing.2000，9：287-290.
[4] ELAD M，HEL-OR Y.A fast super-resolution reconstruction algorithm for pure translational motion and common space invariant blur[J].IEEE Trans.Image Processing，2001，10：1187-1193.
[5] ALTUNBASAK Y，PATTI A，MERSEREAU R.Super-resolution still and video reconstruction from mpeg-coded video[J].IEEE Trans.Circuits Syst.Video Technol.，2002，12：217-226.
[6] LIAW Y C，LAI J Z C，LO W.Image restoration of compressed image using classified vector quantization[J].Pattern Recognit.，2002，35：181-192.