基于视频压缩的快速自适应菱形搜索算法

1、    基于视频压缩的快速自适应菱形搜索算法        王燕妮1，2，樊养余1，彭 轲 时间:2008年07月10日     字 体: 大 中 小        关键词:        ? 摘 要：关键词： 视频压缩? 自适应? 运动估计? 菱形搜索?1 经典菱形搜索算法?

2、经典菱形搜索算法采用两种搜索模式：大菱形搜索模式和小菱形搜索模式。大菱形搜索模式由一个中心点和它周围的8个搜索点构成，步长为2。这9个点组成一个菱形，小菱形搜索模式由5个搜索点构成，步长为1。搜索步骤：第1步，最初的大菱形搜索模式以搜索窗口中心为中心点，计算大菱形的9个搜索点的误差函数。若误差函数最小的搜索点位于中心，则跳到第3步；否则跳到第2步。第2步，以第1步搜索的9个点中最小点为大菱形的中心点，计算大菱形的9个搜索点的误差函数。若误差函数最小的搜索点位于中心，则跳到第3步；否则，跳到第2步。第3步，以上一步搜索的9个点中的最小点为中心点，计算小菱形的5个点的误差函数。误差函数最小的块为最

3、佳匹配快。? 菱形搜索算法虽然计算量少，但实现比较复杂，而且由于在搜索区中存在大量的搜索空区2，3，所以存在搜索到非最优点的情况，从而使得帧间预测误差增大。针对实时性与估计精度4-6这一对矛盾，提出一种基于视频压缩的快速自适应菱形搜索算法，根据运动矢量的时空相关性和中心偏向特性，预测当前块的运动矢量，减小了搜索的盲目性，较好地实现了视频图像的运动估计。2 快速自适应菱形搜索算法2.1 中心偏向性? 从研究一幅视频图像运动矢量的分布情况可以看出，在一定的门限判定条件下，（0，0）这个零矢量出现的概率极大。采用全搜索算法，搜索范围为（-15，-15）到（15，15），中心处为（0，0）矢量位置，在

4、此处出现极大单峰。这一特性说明，在运动不太剧烈的情况下，运动矢量大量积聚在零矢量处，在预测下一帧当前块的运动矢量时可以优先考虑零矢量。2.2 搜索模式的选择? ? 式中，F(i，j)为被压缩的(m×n)宏块；G(i，j)为基准(m×n)宏块；(dx，dy)为搜索处的运动矢量，且dx=-p，p，dy=-p，p；p是搜索范围参数。? 根据绝对误差总和，把运动类型分为三类：当SAD<T1时，当前块为低速运动块，可直接采用小菱形搜索算法搜索最佳运动矢量；当T1SADT2时，当前块为中速运动块, 可采用大菱形搜索算法进行搜索；当SAD>T2时，当前块为高速运动块，可采用全

5、搜索算法，以求得较好的搜索效果。由于这种块所占的比例较小，计算量的影响并不显著。式中，T1、T2为两个阈值。2.3阈值的选取? 首先计算当前帧所选块与参考帧中的相同位置处的对应块的绝对误差总和，记为prev_SAD。则设? 式中，一般取为0.9<<1.4，取为1.2<<2.5，且<，、属于经验值。? 若当前帧为第一帧，则不存在prev_SAD。通过大量的实验，在不影响视频图像质量并且考虑传输实时性的情况下，T1取500左右，T2取800左右。3 仿真分析? 为了比较快速自适应菱形搜索算法的效果，采用8bit的视频图像序列对全搜索法、三步搜索法、菱形法以及快速自适应

6、菱形搜索法在相同的条件下进行计算机仿真。3.1 重建帧的比较? 采用susie（352×240）序列，块的大小为16×16，搜索范围P为7。以第五帧作为参考帧，分别用全搜索算法以及快速自适应菱形搜索算法得到第七帧的重建帧。可以看出，快速自适应菱形搜索算法重建的视频图像非常接近视频图像的原始帧, 结果如图1所示。?3.2 误差帧的比较? 为了直观地观察新算法的效果，用峰值信噪比(PSNR)和均方误差(MSE)来衡量各种运动估计技术的性能。对于8bit的视频图像来说，PSNR定义为：? 式中，MSE表示均方误差，由下式决定：? 式中，f(i，j)是视频图像序列的原始帧，g(i，

7、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 搜索匹配时间的比较? 采用mi

8、ssamerican（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×

9、240）序列对算法进行性能比较，可得ADS算法的性能曲线都优于DS算法的性能曲线，峰值信噪比比DS算法平均提高了1.3dB，相应地均方误差也降低了。对于运动缓慢的视频序列，新算法的性能几乎逼近全搜索算法；在实验4中，用各种算法对missamerican(360×288)序列进行匹配，比较可得改进算法的搜索匹配时间比DS算法平均减少了约1.5ms。? 基于视频压缩的快速自适应菱形搜索算法，充分利用了视频图像序列的时空相关特性，采用了大小菱形搜索模式，实现了运动矢量高速而较精确的估计。仿真结果表明，与全搜索算法、三步搜索算法、菱形搜索算法等一些优秀算法相比，新算法的运动估计准确性高、预测

10、质量好。在可视电话、终端会议等的实时视频通信中，该算法可取得较好的效果。参考文献1 朱秀昌，刘峰，胡栋.数字图像处理与图像通信M.北京：北京邮电大学出版社，2002.2 KELLER Y，AVERBUCH A.Fast motion estimation using?bidirectional gradient methodsJ.IEEE Trans.Image Processing，2004，13：1042-1054.3 ZHU S，MA K K.A new diamond search algorithm for fast block-matching motion estimationJ

11、.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 blurJ.IEEE Trans.Image Processing，2001，10：1187-1193.5 ALTUNBASAK Y，PATTI A，MERSEREAU R.Super-resolution still and video reconstruction from mpeg-coded videoJ.IEEE Trans.Circuits Syst.Video Technol.