小议运动搜索算法的发展及运用.doc

小议运动搜索算法的发展及运用
摘要:随着视频压缩技术的发展以及人们对大尺寸、高质量图像日益增长的需求,视频压缩算法已成为当前视频技术发展研究的热点,而搜索策略又是视频压缩算法中研究最多的领域。以传统经典快速搜索算法为依托,重点对当前研究的各种快速运动估计算法进行阐述、分析和比较。
关键词:运动;搜索算法;发展;应用
引言
随着网络上图像传输需求的增多,视频实时图像的处理越来越受到人们的重视,庞大的图像数据使视频的实时处理变得困难,因此,图像压缩技术成为视频实时图像处理技术的关键问题。
视频压缩可以从不同的角度进行优化,帧间预测算法的改进是提高整体视频压缩算法效率的关键。它改进和优化主要涉及以下三方面:搜索策略、块匹配准则和块尺寸的选择。块匹配算法主要有最小绝对误差和(SAD)、最小平均绝对误差(MAD)或最小均方误差(MSE)算法,还有改进后的最小绝对差分误差和(SADD)算法以及基于内容的运动搜索算法等。块尺寸方面,搜索的块尺寸从16×16到8×8,再到4×4,精度单位从整像素到1/2像素,再到1/4像素,这些算法的改进减少了不必要的搜索点,细化了块单位,提高了搜索精度和速度。
多数运动估计算法都是基于对搜索算法的改进,通过对搜索算法的改进,以消除搜索所带来的时间冗余和空间冗余。
最初提出的快速搜索算法是全搜索法(FullSearch,FS)。全搜索算法运算准确度最高,但是运算量巨大,在编码过程中占据了总运算量的60%~80%,所以很少为实际所使用。为减小运动估计过程中的计算量,保证运动估计的准确性,运动估计领域提出了很多新的快速算法。
早期的快速估计算法有三步搜索法、二维对数搜索法、正交搜索算法、交叉搜索算法等。这些方法通过限制搜索点的数目有效地减少了运算量,相对全搜索算法有了较大改进,但这些算法为了满足搜索点的减少,往往将初始步长设的较大,使得搜索容易陷入局部最小,导致估计准确度不高。同时早期的算法在设计搜索策略时,多数会选择全向性作为搜索的方向,即会选择上下左右四向八点,或选择菱形搜索等作为搜索模型。这种搜索策略从搜索的全面性以及匹配的精度来讲,是有其优越性,但全向性搜索往往同时带来搜索计算量增大,产生大量计算冗余。针对这些问题,现阶段提出的新的快速搜索算法,从不同方面入手,改善搜索算法中的不足,提高搜索效率。为此本文将以经典算法作为研究前提,重点对当前研究的各种快速运动估计算法的对比分析其各自的利弊,提出对运动估计算法发展的新构思。
一、基于分层的自适应运动估计算法
基于分层的自适应运动估计算法,主要选取菱形作为搜索模型,通过相邻宏块间的运动矢量关系来判断运动状况,并对不同运动块采用不同的搜索方法,对于大运动块,采用分层结构搜索;其他运动使用小菱形搜索。同时结合多种提前截至准则,在保证匹配精度的前提下,提高了搜索速度。
基于分层的自适应运动估计算法是基于一种分层塔形的搜索思路延伸而成,但在算法上又明显优于分层塔形搜索。基于分层塔形的搜索,它的做法是:对于那些运动比较剧烈的宏块,先在低分辨力下一层层地搜索,然后再转到原始分辨力下搜索,从而以较低的计算复杂度获得较高的搜索精度。但现行的分层算法有时会出现重复搜索的问题,特别是在大运动搜索中,当预测起点已经是最优匹配点时,若判决准则不认为是最优,则还要先转到低分辨力层搜索,再