一种基于马尔科夫链模型的运动估计新方法＊

吴 云，曹志民，唐世伟

（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）避免陷入局部最优。然而，在实际的视频序列中，特别是运动剧烈的视频序列，其运动矢量分布具有较复杂的多峰特性，这两个问题往往是比较矛盾的。文献［8］通过引入马尔科夫链模型，很好地实现了初始搜索点的预测，结合运动矢量场自适应预测技术－PMVFAST的优势，实现了一种有效的FBME算法－MEMCM，但是对运动较剧烈的视频序列，较易陷入局部最优。

为了更好地调和以上所提两方面问题，在文献［8］的基础上利用模糊逻辑和遗传算法等手段，尽可能避免搜索过程中陷入局部最优，从而增加算法匹配精度，实现了一种既快又好的FBME算法。

1 马尔科夫链模型运动估计

视频编码过程中，无论运动补偿滤波结构如何设计，都需要对相对连续视频帧进行运动估计，以实现时间和空间冗余信息的去除。因此，连续运动估计过程中，初始搜索点之间也同样存在很强的时间和空间相关性，而为了更好地利用这种相关性，可以定义三种常用的初始运动矢量预测模式：零矢量模式，中值矢量模式以及参考矢量模式。

S1：零矢量模式，即以零矢量作为初始搜索点；

S2：中值矢量模式，即以当前宏块左、上、右上宏块对应矢量的中值矢量作初始搜索点；

S3：参考矢量模式，即以前一运动矢量场当前位置的运动矢量为初始搜索点。

在连续运动估计过程中，这三种初始搜索点的预测模式即构成了一个马尔科夫链。

当前块的初始预测模式Sinit为：

即表示当前运动估计前一运动矢量场当前宏块预测模式为Sj时，根据状态转移概率对当前宏块初始预测模式进行设定。

当前宏块的实际状态确定方法如下：

式（2）中，i，j＝1，2，3；（mvxi，mvyi）i＝1，2，3分别为零矢量，中值矢量和参考矢量；SAD 为采用的相似性测度准则，即绝对误差和准则。在实现了初始运动矢量的预测和测试后，即可按照PMVFAST算法的流程实现快速运动估计。

2 基于马尔科夫链模型的运动估计新方法

如前所述，现有FBME算法都是一种多步骤顺序结构，因此，各个步骤之间没有交互信息的学习。也就是说，每个步骤所获取的信息只能向下传递，不能实现向上的指导。因此，这种结构的运动估计中，一旦初始搜索环节陷入局部最优，后面的操作将会出现越陷越深的可能。为此，在运动估计框架中，在初始搜索阶段和模板搜索阶段之间加入一个模糊推理阶段，如图1所示。

图1 采用模糊逻辑的运动估计算法框图Fig.1 The block diagram of the motion estimation algorithm with fuzzy logic embeded in

图1中初始搜索过程采用前文所述的马尔科夫链模型进行预测，并对有初始预测矢量和其他两种预测模式矢量及当前宏块左、上、右上宏块对应运动矢量构成的运动矢量集（6个矢量）进行初始搜索，得到初始最优矢量、次优矢量及对应的相似性测度SADinit1、SADinit2，并利用最优解根据式（2）最终确定当前模式。

模糊推理过程采用了两种搜索模板，即图2（a）所示的六边形测试模板及图2（b）所示的小菱形模板。

利用模糊逻辑进行模糊推理，详细过程如下：

首先，进行六边形模板测试，得到该模板对应的最优矢量及相应的相似性测度SADhex。

之后，需要进行模糊逻辑判断。利用如下S形隶属度函数对当前所得到的两个阶段的相似性测度进行比较判断。

图2 搜索模板Fig.2 Searching patterns

式（3）中，SADT＝k＊SADinit1为隶属度上限阈值，k的取值与视频序列的运动剧烈程度有关。

当所得隶属度值小于0.5时，停止搜索，利用次优初试点重新搜索；当模糊推理阶段的隶属度函数值大于0.5时，则利用遗传算法进行小菱形模板（如图2（b）所示）搜索，搜索框图如图3所示。

图3 遗传算法搜索框图Fig.3 The searching block diagram of genetic algorithm

3 实验结果

为了验证文中所提算法的有效性，选取了foreman.qcif，highway.qcif，bus.cif和 Mobile.qcif等四个具有不同运动性质的视频序列进行测试，并与应用普遍的MVFAST、PMVFAST算法进行性能比较，得到各算法与全搜索算法相比较的加速度及峰值信噪比（peak signal to noise ratio，PSNR）。

实验过程中对各视频序列连续各帧间利用不同算法进行测试得到结果如表1所示。图4则给出foreman.qcif序列的测试数据曲线示意图。

表1 文中所提算法与MVFAST、PMVFAST、MEMCM算法性能比较Tab.1 The perfermance comparison of the proposed algorithm，MVFAST and PMVFAST as well as MEMCM

图4 各算法性能数据比较曲线示意图Fig.4 The comparison plots of perfermances among tested algorithms

4 结 论

通过将模糊逻辑推理及遗传算法引入基于马尔科夫链模型运动估计算法中，从而最大限度地避免了快速搜索过程中陷入局部点的可能，实现了运动估计算法在算法速度及重构视频质量之间的较好折中。实验结果表明，文中所提算法确实能够实现在具有较快搜索速度的前提下，较大程度地提高视频重构质量，是一种具有较好鲁棒性的快速运动估计算法解决方案。

［1］MA I K，HOSUR P I.Performance report of motion vector field adaptive search technique［R］.Noordwijkerhout：ISO／IEC，JTC1／SC29／WG11M5851，2000：1－40.

［2］焦斌亮，赵文蕾.小波及分形理论在互有位移图像序列重构中的应用［J］.光学仪器，2005，27（6）：23－28.

［3］HUANG Y，CHO C Y，WANG J S.Adaptive fast block－matching algorithm by switching search patterns for sequences with wide－range motion content［J］.IEEE Trans Circuits Syst Video Technolnogy，2005，15（11）：1373－1384.

［4］CHANG M C，CHIEN J S.An adaptive search algorithm based on block classification for fast block motion estimation［C］∥IEEE International Symposium on Circuits and Systems，Kos Island：IEEE，2006：21－24.

［5］WONG H M，AU O C，HO C W，et al.Enhanced predictive motion vector field adaptive search technique based on future MV prediction［C］∥International Conference on Multimedia and Expo，Amsterdam：ICME，2005：6－8.

［6］NI W，GUO B L，DING G G，et al.A fast motion estimation algorithm based on motion vector field and direction adaptive techniques［J］.Journal of Electronics and Information Technology，2006（12）：2277－2282.

［7］CHEUNG C H，PO L M.A novel cross－diamond search algorithm for fast flock motion estimation［J］.IEEE Trans Circuits and System Video Technology，2002，12（12）：1168－1177.

［8］ZHAO Z J，CAO Z M，LIN M L，et al.A motion estimation algorithm based on Markov chain model［C］∥Acoustics Speech and Signal Processing，Dallas：IEEE，2010：1174－1177.