基于多级顺序排除算法(MSEA)的改进  

An Improved Multilevel Successive Elimination Algorithm

作　　者：李国玉[1] 付宇卓[1] 王世明[1] 

机构地区：[1]上海交通大学电子工程系,上海200030

出　　处：《计算机仿真》2005年第9期89-91,112,共4页Computer Simulation

摘　　要：块匹配运动估计是视频编码国际标准中广泛采用的关键技术。许多快速块匹配法通过限制搜索点数来减少运算量,但与全搜索算法相比极易出现匹配误差。该文介绍了一种应用新的判别条件的多级顺序排除算法(MSEA),并在此基础上提出一种新的算法,该算法引入了尺度化的部分失真消除(PDE)技术,用于尺度化累积部分误差和当前最小误差。实验证明,相对于一脉相承的同为穷举搜索算法的全搜索算法(FS)、顺序排除算法(SEA)、多级顺序排除算法(MSEA)等,该算法大幅度提高了搜索效率。与多级顺序排除算法相比,平均每宏块节省了大约75%的运算次数。该算法在保证图像质量的前提下,使视频编码的速度大大提高。The motion estimation based on the block matching is a key technique used in the video coding standards. Many fast block matching algorithms reduce computations by limiting the number of checking points. They can achieve high computation reduction, but often results in relatively higher matching error compared with the full search algorithm. In this article, we present a new multilevel successive elimination algorithm which applies a new decision condition. On this basis, we put forward a novel algorithm which adopts normalized partial distortion elimination algorithm used for normalizing the accumulated partial distortion and the current minimum distortion. Experiments show that, compared with other exhaustive search algorithms like full search algorithm, successive elimination algorithm and multilevel successive elimination algorithm, our algorithm improves searching efficiency prominently. Compared with multilevel successive elimination algorithm, the algorithm saves about 75 percent operation times. The algorithm highly speeds up the video coding on the premise of maintaining the video quality.

关 键 词：运动估计 块匹配算法 多级顺序排除算法 部分失真消除 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]