吴 云，曹志民，唐世伟

（1.东北石油大学 电子科学学院，黑龙江 大庆 163318；2.东北石油大学 计算机与信息工程学院，黑龙江 大庆 163318）

引 言

运动估计技术在视频编解码系统以及很多视频处理应用领域（如视频降噪，帧速率变频等）有着非常重要的作用［1，2］。由于块匹配运动估计（block－matching motion estimation，BME）算法通过将视频帧分割为一定数目的宏块，并通过寻找指定范围内相邻帧匹配最佳宏块的方法实现运动估计，算法原理简单且易于硬件实现，因此BME算法在实际的工程项目中得到了非常广泛的应用，并且BME算法已经被很多国际视频编解码标准所采纳，如国际标准化组织ISO的 MPEG－1／2／4标准，国际电信联盟ITU－T的H.261，H.263和 H.264标准［3，4］。其中，全搜索（full searching，FS）算法通过测试搜索范围内所有点的方法实现最佳匹配，因此是匹配效果最好的BME算法。但是，由于其计算成本太高，很难直接应用于实际的系统中。为此，各种各样的快速块匹配运动估计（fast block－matching motion estimation，FBME）算法层出不穷［5］。

模板匹配类运动估计（pattern based block－matching motion estimation，PBME）算法通过对运动矢量统计特性的分析，对搜索模板进行巧妙的设计，用尽可能少的搜索实现最优匹配，成为现有FBME的主流方案［6］。这种方法是一种典型的多步实现过程，往往包含如下几个典型技术的应用［7］：（1）搜索起始点的确定；（2）提前退出策略；（3）搜索模板设计。这些技术的应用主要为了解决FBME所需面对的两个问题：（1）减少搜索点数，加快搜索速度；（2）避免陷入局部最优。然而，在实际的视频序列中，特别是运动剧烈的视频序列，其运动矢量分布具有较复杂的多峰特性，这两个问题往往是比较矛盾的。……