一種基于馬爾科夫鏈模型的運(yùn)動(dòng)估計(jì)新方法＊

吳 云，曹志民，唐世偉

（1.東北石油大學(xué) 電子科學(xué)學(xué)院，黑龍江 大慶 163318；2.東北石油大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，黑龍江 大慶 163318）

引 言

運(yùn)動(dòng)估計(jì)技術(shù)在視頻編解碼系統(tǒng)以及很多視頻處理應(yīng)用領(lǐng)域（如視頻降噪，幀速率變頻等）有著非常重要的作用［1，2］。由于塊匹配運(yùn)動(dòng)估計(jì)（block－matching motion estimation，BME）算法通過(guò)將視頻幀分割為一定數(shù)目的宏塊，并通過(guò)尋找指定范圍內(nèi)相鄰幀匹配最佳宏塊的方法實(shí)現(xiàn)運(yùn)動(dòng)估計(jì)，算法原理簡(jiǎn)單且易于硬件實(shí)現(xiàn)，因此BME算法在實(shí)際的工程項(xiàng)目中得到了非常廣泛的應(yīng)用，并且BME算法已經(jīng)被很多國(guó)際視頻編解碼標(biāo)準(zhǔn)所采納，如國(guó)際標(biāo)準(zhǔn)化組織ISO的 MPEG－1／2／4標(biāo)準(zhǔn)，國(guó)際電信聯(lián)盟ITU－T的H.261，H.263和 H.264標(biāo)準(zhǔn)［3，4］。其中，全搜索（full searching，F(xiàn)S）算法通過(guò)測(cè)試搜索范圍內(nèi)所有點(diǎn)的方法實(shí)現(xiàn)最佳匹配，因此是匹配效果最好的BME算法。但是，由于其計(jì)算成本太高，很難直接應(yīng)用于實(shí)際的系統(tǒng)中。為此，各種各樣的快速塊匹配運(yùn)動(dòng)估計(jì)（fast block－matching motion estimation，F(xiàn)BME）算法層出不窮［5］。

模板匹配類(lèi)運(yùn)動(dòng)估計(jì)（pattern based block－matching motion estimation，PBME）算法通過(guò)對(duì)運(yùn)動(dòng)矢量統(tǒng)計(jì)特性的分析，對(duì)搜索模板進(jìn)行巧妙的設(shè)計(jì)，用盡可能少的搜索實(shí)現(xiàn)最優(yōu)匹配，成為現(xiàn)有FBME的主流方案［6］。這種方法是一種典型的多步實(shí)現(xiàn)過(guò)程，往往包含如下幾個(gè)典型技術(shù)的應(yīng)用［7］：（1）搜索起始點(diǎn)的確定；（2）提前退出策略；（3）搜索模板設(shè)計(jì)。這些技術(shù)的應(yīng)用主要為了解決FBME所需面對(duì)的兩個(gè)問(wèn)題：（1）減少搜索點(diǎn)數(shù)，加快搜索速度；（2）避免陷入局部最優(yōu)。然而，在實(shí)際的視頻序列中，特別是運(yùn)動(dòng)劇烈的視頻序列，其運(yùn)動(dòng)矢量分布具有較復(fù)雜的多峰特性，這兩個(gè)問(wèn)題往往是比較矛盾的。文獻(xiàn)［8］通過(guò)引入馬爾科夫鏈模型，很好地實(shí)現(xiàn)了初始搜索點(diǎn)的預(yù)測(cè)，結(jié)合運(yùn)動(dòng)矢量場(chǎng)自適應(yīng)預(yù)測(cè)技術(shù)－PMVFAST的優(yōu)勢(shì)，實(shí)現(xiàn)了一種有效的FBME算法－MEMCM，但是對(duì)運(yùn)動(dòng)較劇烈的視頻序列，較易陷入局部最優(yōu)。

為了更好地調(diào)和以上所提兩方面問(wèn)題，在文獻(xiàn)［8］的基礎(chǔ)上利用模糊邏輯和遺傳算法等手段，盡可能避免搜索過(guò)程中陷入局部最優(yōu)，從而增加算法匹配精度，實(shí)現(xiàn)了一種既快又好的FBME算法。

1 馬爾科夫鏈模型運(yùn)動(dòng)估計(jì)

視頻編碼過(guò)程中，無(wú)論運(yùn)動(dòng)補(bǔ)償濾波結(jié)構(gòu)如何設(shè)計(jì)，都需要對(duì)相對(duì)連續(xù)視頻幀進(jìn)行運(yùn)動(dòng)估計(jì)，以實(shí)現(xiàn)時(shí)間和空間冗余信息的去除。因此，連續(xù)運(yùn)動(dòng)估計(jì)過(guò)程中，初始搜索點(diǎn)之間也同樣存在很強(qiáng)的時(shí)間和空間相關(guān)性，而為了更好地利用這種相關(guān)性，可以定義三種常用的初始運(yùn)動(dòng)矢量預(yù)測(cè)模式：零矢量模式，中值矢量模式以及參考矢量模式。

S1：零矢量模式，即以零矢量作為初始搜索點(diǎn)；

S2：中值矢量模式，即以當(dāng)前宏塊左、上、右上宏塊對(duì)應(yīng)矢量的中值矢量作初始搜索點(diǎn)；

S3：參考矢量模式，即以前一運(yùn)動(dòng)矢量場(chǎng)當(dāng)前位置的運(yùn)動(dòng)矢量為初始搜索點(diǎn)。

在連續(xù)運(yùn)動(dòng)估計(jì)過(guò)程中，這三種初始搜索點(diǎn)的預(yù)測(cè)模式即構(gòu)成了一個(gè)馬爾科夫鏈。

當(dāng)前塊的初始預(yù)測(cè)模式Sinit為：

即表示當(dāng)前運(yùn)動(dòng)估計(jì)前一運(yùn)動(dòng)矢量場(chǎng)當(dāng)前宏塊預(yù)測(cè)模式為Sj時(shí)，根據(jù)狀態(tài)轉(zhuǎn)移概率對(duì)當(dāng)前宏塊初始預(yù)測(cè)模式進(jìn)行設(shè)定。

當(dāng)前宏塊的實(shí)際狀態(tài)確定方法如下：

式（2）中，i，j＝1，2，3；（mvxi，mvyi）i＝1，2，3分別為零矢量，中值矢量和參考矢量；SAD 為采用的相似性測(cè)度準(zhǔn)則，即絕對(duì)誤差和準(zhǔn)則。在實(shí)現(xiàn)了初始運(yùn)動(dòng)矢量的預(yù)測(cè)和測(cè)試后，即可按照PMVFAST算法的流程實(shí)現(xiàn)快速運(yùn)動(dòng)估計(jì)。

2 基于馬爾科夫鏈模型的運(yùn)動(dòng)估計(jì)新方法

如前所述，現(xiàn)有FBME算法都是一種多步驟順序結(jié)構(gòu)，因此，各個(gè)步驟之間沒(méi)有交互信息的學(xué)習(xí)。也就是說(shuō)，每個(gè)步驟所獲取的信息只能向下傳遞，不能實(shí)現(xiàn)向上的指導(dǎo)。因此，這種結(jié)構(gòu)的運(yùn)動(dòng)估計(jì)中，一旦初始搜索環(huán)節(jié)陷入局部最優(yōu)，后面的操作將會(huì)出現(xiàn)越陷越深的可能。為此，在運(yùn)動(dòng)估計(jì)框架中，在初始搜索階段和模板搜索階段之間加入一個(gè)模糊推理階段，如圖1所示。

圖1 采用模糊邏輯的運(yùn)動(dòng)估計(jì)算法框圖Fig.1 The block diagram of the motion estimation algorithm with fuzzy logic embeded in

圖1中初始搜索過(guò)程采用前文所述的馬爾科夫鏈模型進(jìn)行預(yù)測(cè)，并對(duì)有初始預(yù)測(cè)矢量和其他兩種預(yù)測(cè)模式矢量及當(dāng)前宏塊左、上、右上宏塊對(duì)應(yīng)運(yùn)動(dòng)矢量構(gòu)成的運(yùn)動(dòng)矢量集（6個(gè)矢量）進(jìn)行初始搜索，得到初始最優(yōu)矢量、次優(yōu)矢量及對(duì)應(yīng)的相似性測(cè)度SADinit1、SADinit2，并利用最優(yōu)解根據(jù)式（2）最終確定當(dāng)前模式。

模糊推理過(guò)程采用了兩種搜索模板，即圖2（a）所示的六邊形測(cè)試模板及圖2（b）所示的小菱形模板。

利用模糊邏輯進(jìn)行模糊推理，詳細(xì)過(guò)程如下：

首先，進(jìn)行六邊形模板測(cè)試，得到該模板對(duì)應(yīng)的最優(yōu)矢量及相應(yīng)的相似性測(cè)度SADhex。

之后，需要進(jìn)行模糊邏輯判斷。利用如下S形隸屬度函數(shù)對(duì)當(dāng)前所得到的兩個(gè)階段的相似性測(cè)度進(jìn)行比較判斷。

圖2 搜索模板Fig.2 Searching patterns

式（3）中，SADT＝k＊SADinit1為隸屬度上限閾值，k的取值與視頻序列的運(yùn)動(dòng)劇烈程度有關(guān)。

當(dāng)所得隸屬度值小于0.5時(shí)，停止搜索，利用次優(yōu)初試點(diǎn)重新搜索；當(dāng)模糊推理階段的隸屬度函數(shù)值大于0.5時(shí)，則利用遺傳算法進(jìn)行小菱形模板（如圖2（b）所示）搜索，搜索框圖如圖3所示。

圖3 遺傳算法搜索框圖Fig.3 The searching block diagram of genetic algorithm

3 實(shí)驗(yàn)結(jié)果

為了驗(yàn)證文中所提算法的有效性，選取了foreman.qcif，highway.qcif，bus.cif和 Mobile.qcif等四個(gè)具有不同運(yùn)動(dòng)性質(zhì)的視頻序列進(jìn)行測(cè)試，并與應(yīng)用普遍的MVFAST、PMVFAST算法進(jìn)行性能比較，得到各算法與全搜索算法相比較的加速度及峰值信噪比（peak signal to noise ratio，PSNR）。

實(shí)驗(yàn)過(guò)程中對(duì)各視頻序列連續(xù)各幀間利用不同算法進(jìn)行測(cè)試得到結(jié)果如表1所示。圖4則給出foreman.qcif序列的測(cè)試數(shù)據(jù)曲線(xiàn)示意圖。

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

圖4 各算法性能數(shù)據(jù)比較曲線(xiàn)示意圖Fig.4 The comparison plots of perfermances among tested algorithms

4 結(jié) 論

通過(guò)將模糊邏輯推理及遺傳算法引入基于馬爾科夫鏈模型運(yùn)動(dòng)估計(jì)算法中，從而最大限度地避免了快速搜索過(guò)程中陷入局部點(diǎn)的可能，實(shí)現(xiàn)了運(yùn)動(dòng)估計(jì)算法在算法速度及重構(gòu)視頻質(zhì)量之間的較好折中。實(shí)驗(yàn)結(jié)果表明，文中所提算法確實(shí)能夠?qū)崿F(xiàn)在具有較快搜索速度的前提下，較大程度地提高視頻重構(gòu)質(zhì)量，是一種具有較好魯棒性的快速運(yùn)動(dòng)估計(jì)算法解決方案。

［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］焦斌亮，趙文蕾.小波及分形理論在互有位移圖像序列重構(gòu)中的應(yīng)用［J］.光學(xué)儀器，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.