Computer Knowledge and Technology 电脑知识
与技术计算机工程应用技术本栏目责任编辑：梁书
第6卷第32期(2010年11月)几种经典快速块匹配运动估计算法的比较研究
肖敏连
（湖南人文科技学院计算机科学技术系，湖南娄底417000）
摘要：块匹配运动估计算法被许多视频编码标准采用以消除视频序列帧间的时间冗余信息，而运动估计往往是视频编码器中的最耗时的部分，为了加快视频编码速度，许多快速运动估计被相继提出，该文首先对三种经典的快速运动估计算法进行详细的分析，然后把这三种经典快速运动估计算法嵌入到国际视频编码标准H.264/AVC 中，在相同的条件下分别对这三种算法进行性能测试，最后通过比较测试结果对三种经典快速运动估计算法的各自的特点进行了总结。
关键词：块匹配；运动估计；算法
中图分类号：TP312文献标识码：A 文章编号：1009-3044(2010)32-9152-03
Comparative Research on Several Classical Rapid Algorithms of Block-matching Motion Estimation
XIAO Min-lian
(Department of Computer Science and Technology of Hunan Institute of Humanities,Science and Technology,Loudi 417000,China)
Abstract:Block-matching motion estimation was adopted by many video standards to eliminate the temporal redundancy information be -tween successive frames,and usually the motion estimation is the most time consuming part of the whole encoding process.Many rapid motion estimation algorithms are developed in the past twenty years successively.This paper firstly analyzed the three classical rapid block-matching motion estimation algorithms.Then these algorithms were inserted into the H.264/AVC reference software.The three classic rapid block-matching motion estimation algorithms'performances were tested under the same condition.Finally,the characteristics of the three classical rapid algorithms were summarized according to the experimental results.
Key words:block-matching;motion estimation;algorithm
对于视频图像序列，如果帧与帧之间不是场景变换，运动幅度不是很大，则两帧之间就会存在很大的时间相关性即时间冗余，可以通过运动估计来消除时间冗余，从而达到视频压缩的目的。块匹配运动估计算法是目前应用最广泛的一种运动估计算法，它已被许多视频编码标准所采纳，如MPEG-1/2/4、H.261、H.263及H.264/AVC 等等[1-2]。最基本的块匹配算法是全搜索（FS ，Full Search ）算法，虽然它能通过对搜索范围内所有的点进行搜索而找到最佳匹配点，但其计算量非常巨大，因此寻求快速的块匹配运动估计算法成了视频编码中热点问题。
1几种快速经典运动估计算法的搜索策略
运动搜索的目的就是要寻找最优匹配点。在搜索过程中可以采用上述不同的起点预测方法和块匹配准则来加快搜索速度或提高精度。搜索策略选择适当与否对运动估计的准确性、运动估计的速度都有很大的影响。最简单、最可靠、搜索精度最高的是全搜索法，但由于它计算复杂度高，不易于实时应用，为此人们提出了各种改进的快速算法，下面介绍几种经典的快速运动估计算法。
1.1三步搜索算法
三步搜索算法[3](Three Step Search ，TSS)于1981年由T.KOGA 等人提出，作为
一种简单有效的运动估计技术，被广泛使用在低比特率视频压缩场合中，当最大搜
索距离为7，搜索精度取1个像素，则步长为4、2、1，共需三步即可满足要求，因此
而得名三步法。
TSS 采用一种由粗到细的搜索模式，从搜索窗中心点开始，按一定步长取周围
8个点构成每次搜索的点群，然后进行匹配计算，跟踪到最小块误差MBD 点。
TSS 算法具体执行步骤：①它先确定一个中心点，确定最大搜索长度，然后以
最大搜索长度的1/2作为步长，在中心点周围取离中心点距离为一个步长的8个
点，将这9个点按照匹配原则进行计算，得到最佳匹配点；②然后以上一步得到的
最匹配的块为中心，搜索与此相距为最大搜索长度1/4搜索窗口距离的8个点进
行比较，再通过比较找出最匹配的块；③最后比到步长为1时，找出此时的最佳匹
配点就是最终的结果。
图1为TSS 的一个搜索图示。该算法简单、健壮、性能良好。但第一步的搜索步收稿日期：2010-09-07
基金项目：湖南人文科技学院教改课题（RKJGY0928，RKJGZ0706）资助
作者简介：肖敏连（1969-），女，湖南娄底人，实验师，本科，主要研究方向为多媒体技术。
图1TSS 搜索图示
ISSN 1009-3044Computer Knowledge and Technology 电脑知识与技术Vol.6,No.32,November 2010,pp.9152-9154E-mail:kfyj@ Tel:+86-551-569096356909649152
