Ｈ．２６４運(yùn)動(dòng)估計(jì)算法研究

摘要：在分析國(guó)際視頻編碼標(biāo)準(zhǔn)H.264的研究背景、研究現(xiàn)狀的基礎(chǔ)上，介紹了幾種典型的運(yùn)動(dòng)估計(jì)算法，研究了現(xiàn)有H.264的快速運(yùn)動(dòng)估計(jì)算法的優(yōu)勢(shì)與不足，指出今后研究的方向。

關(guān)鍵詞：視頻編碼；運(yùn)動(dòng)估計(jì)；算法研究

中圖分類(lèi)號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2008)22-794-02

Study on the Motion Estimation Algorithm in H.264

ZHENG Yi-ling

(Department of Information Engineering， Liuzhou Vocational Technical College， Liuzhou 545006， China)

Abstract: Based on the studying background and studying current situation of H.264 which is thestandard of international video code ， several kinds algorithms of the motion estimation were introduced， and the advantage and deficiency of the motion estimationalgorithm in H.264wasstudied， then thefuture studies directionwas pointed out.

Key words: video coding; motion estimation; algorithm study

1 H.264概述

H.264是ITU-T的VCEG（視頻編碼專(zhuān)家組）和ISO/IEC 的MPEG（活動(dòng)圖像編碼專(zhuān)家組）共同組成的JVT（聯(lián)合視頻組）開(kāi)發(fā)的一個(gè)新的數(shù)字視頻編碼標(biāo)準(zhǔn)，它既是ITU-T的H.264 ， 又是ISO/IEC的MPEG-4的第10部分。H.264 和H.261、H.263 一樣，也是采用混合編碼結(jié)構(gòu)，同時(shí)引入了新的編碼方式，提高了編碼效率。與以往標(biāo)準(zhǔn)相比，在相同編碼質(zhì)量時(shí)，H.264可以節(jié)省大概50%的碼率。[1]

2 研究背景

雖然H.264標(biāo)準(zhǔn)草案已經(jīng)頒布幾年了，可是H.264在實(shí)際當(dāng)中的應(yīng)用仍然存在著一些不足。其原因在于先進(jìn)算法的采用是以犧牲編碼復(fù)雜度為代價(jià)的。隨著視頻壓縮技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展，視頻通信成為新的應(yīng)用需求熱點(diǎn)。由于視頻編解碼器計(jì)算度復(fù)雜，各類(lèi)視頻應(yīng)用終端產(chǎn)品為了保證視頻質(zhì)量，都要采用高端的處理器來(lái)完成視頻編解碼的任務(wù)，且需要專(zhuān)業(yè)人員耗費(fèi)大量時(shí)間移植到具體的平臺(tái)上，因此增加了產(chǎn)品的成本，延長(zhǎng)產(chǎn)品的研發(fā)時(shí)間。如何更好的提升H.264在實(shí)際當(dāng)中的應(yīng)用，這成為了H.264研究的關(guān)鍵所在，其中針對(duì)H.264編碼過(guò)程中復(fù)雜度高、耗時(shí)最大的運(yùn)動(dòng)估計(jì)模塊的研究成為熱點(diǎn)，其最終目的在于減少H.264算法中的編碼復(fù)雜度，提升編碼性能，推進(jìn)H.264向?qū)崟r(shí)應(yīng)用發(fā)展。

3 研究現(xiàn)狀

由于H.264在實(shí)際應(yīng)用當(dāng)中仍然存在不足，因此相關(guān)的研究和開(kāi)發(fā)包括以下兩方面：

1）軟件方面：主要集中在對(duì)H.264的參考模型進(jìn)行算法級(jí)的改進(jìn)和指令級(jí)的改進(jìn)兩個(gè)方面。

目前開(kāi)發(fā)的軟件主要有：

JM：H.264的官方測(cè)試源碼，由德國(guó)HHI研究所負(fù)責(zé)開(kāi)發(fā)。它實(shí)現(xiàn)了H.264的所有特性，學(xué)術(shù)研究的算法都是在JM基礎(chǔ)上實(shí)現(xiàn)并和JM進(jìn)行比較。但其程序結(jié)構(gòu)冗長(zhǎng)，編碼復(fù)雜度極高，不宜實(shí)用。

X264：網(wǎng)上自由組織聯(lián)合開(kāi)發(fā)的兼容H.264標(biāo)準(zhǔn)碼流的編碼器，和H.264相比，在不明顯降低編碼性能的前提下，努力降低編碼的計(jì)算復(fù)雜度，故X264擯棄了H.264中一些對(duì)編碼性能貢獻(xiàn)微小但計(jì)算復(fù)雜度極高的新特性。

T264：中國(guó)視頻編碼自由組織聯(lián)合開(kāi)發(fā)的264編解碼器，編碼器編碼輸出標(biāo)準(zhǔn)的264碼流，解碼器只能解T264編碼器生成的碼流。

2）硬件方面：當(dāng)前H.264在許多領(lǐng)域得到廣泛應(yīng)用，硬件實(shí)現(xiàn)方面目前國(guó)外已經(jīng)有公司研制出來(lái)H.264的編解碼器。主流的視頻會(huì)議產(chǎn)品和監(jiān)控產(chǎn)品多數(shù)采用H.264。

3.1 H.264中的運(yùn)動(dòng)估計(jì)原理

幀間編碼是H.264標(biāo)準(zhǔn)的關(guān)鍵技術(shù)，占有其計(jì)算量的絕大部分。

由于視頻序列圖像在時(shí)間上存在很強(qiáng)的相關(guān)性，采用運(yùn)動(dòng)估計(jì)和運(yùn)動(dòng)補(bǔ)償技術(shù)可以消除時(shí)間冗余以提高編碼效率。視頻序列在時(shí)域的冗余度一般是相當(dāng)大的，主要表現(xiàn)在：

1）對(duì)于靜止不動(dòng)的場(chǎng)景，前后幀的圖像內(nèi)容基本上是相同的[2]；

2）對(duì)于運(yùn)動(dòng)的物體，只要知道其運(yùn)動(dòng)規(guī)律，就可以從前一幀圖像推算出它在當(dāng)前幀的位置。

因此，在視頻編碼和通信中，不需要將每一幀的所有像素信息都傳送到解碼端，而只需傳送物體的運(yùn)動(dòng)信息，解碼器即可根據(jù)前一幀圖像和運(yùn)動(dòng)信息更新當(dāng)前幀，從而達(dá)到壓縮的目的。

3.2 現(xiàn)有的運(yùn)動(dòng)估計(jì)算法的分類(lèi)

由于對(duì)H.264的研究正在進(jìn)行之中，針對(duì)現(xiàn)有的H264中的運(yùn)動(dòng)估計(jì)算法的分類(lèi)也沒(méi)有統(tǒng)一的標(biāo)準(zhǔn)。根據(jù)當(dāng)前的研究情況，介紹以下幾種分類(lèi)情況。

1）將運(yùn)動(dòng)估計(jì)技術(shù)分為二維運(yùn)動(dòng)估計(jì)和三維運(yùn)動(dòng)估計(jì)兩大類(lèi)。其中，二維運(yùn)動(dòng)估計(jì)又分為區(qū)域匹配法（其中包括塊匹配法）、頻率法、光流法、像素遞歸法、隨機(jī)法、分層運(yùn)動(dòng)估計(jì)法、半像素精度運(yùn)動(dòng)估計(jì)等方法。三維運(yùn)動(dòng)估計(jì)又分為本質(zhì)矩陣法（八點(diǎn)法）、三維結(jié)構(gòu)模型等[2]；

2）將運(yùn)動(dòng)估計(jì)分為全局運(yùn)動(dòng)估計(jì)、基于像素點(diǎn)的運(yùn)動(dòng)估計(jì)、基于塊的運(yùn)動(dòng)估計(jì)、基于區(qū)域的運(yùn)動(dòng)估計(jì)、基于網(wǎng)格的運(yùn)動(dòng)估計(jì)；

3）將運(yùn)動(dòng)估計(jì)分為時(shí)域運(yùn)動(dòng)估計(jì)和頻域運(yùn)動(dòng)估計(jì)（DFT、DCT、DWT）；

4）將運(yùn)動(dòng)估計(jì)分為全搜索技術(shù)和快速搜索技術(shù)；

5）將運(yùn)動(dòng)估計(jì)分為無(wú)損方式運(yùn)動(dòng)估計(jì)和有損方式運(yùn)動(dòng)估計(jì)……

3.3 塊匹配運(yùn)動(dòng)估計(jì)算法分析

塊匹配方法的基本思想是：將圖像序列的每一幀分成許多互不重疊的宏塊，并認(rèn)為宏塊內(nèi)所有像素的位移量都相同，然后對(duì)每個(gè)宏塊到參考幀某一給定特定搜索范圍內(nèi)根據(jù)一定的匹配準(zhǔn)則找出與當(dāng)前塊最相似的塊，即匹配塊。匹配塊與當(dāng)前塊的相對(duì)位移即為運(yùn)動(dòng)矢量。視頻壓縮時(shí)，只需保存運(yùn)動(dòng)矢量和殘差數(shù)據(jù)就可以完全恢復(fù)出當(dāng)前塊。

塊匹配法因算法簡(jiǎn)單、便于硬件實(shí)現(xiàn)得到廣泛應(yīng)用，也最為流行，幾乎被現(xiàn)存所有視頻壓縮的國(guó)際標(biāo)準(zhǔn)所采用，是目前最成功和應(yīng)用廣泛的幀間預(yù)測(cè)技術(shù)，也是H.264編碼器的核心內(nèi)容之一。由于對(duì)圖像塊進(jìn)行匹配搜索的計(jì)算量是巨大的。為在保證一定圖像質(zhì)量條件下，盡量減少對(duì)運(yùn)動(dòng)估計(jì)的計(jì)算，很多針對(duì)塊匹配的快速搜索算法被提出來(lái)。

目前塊匹配運(yùn)動(dòng)估計(jì)方法大致包括以下幾種：

1）固定搜索模式法；2）連續(xù)消除法；3）象素子抽樣法；4）基于時(shí)空相關(guān)性和視覺(jué)特性的快速塊匹配方法；5）分層的和多分辨率的快速塊匹配方法等。

3.4 典型塊匹配運(yùn)動(dòng)估計(jì)算法介紹

1） 全搜索算法:對(duì)規(guī)定的搜索區(qū)域內(nèi)的所有點(diǎn)進(jìn)行搜索。該算法簡(jiǎn)單可靠的，能保證全局最優(yōu)，易于實(shí)現(xiàn)。但計(jì)算量較大，難于進(jìn)行實(shí)時(shí)處理。

2）三步搜索法：將整個(gè)搜索簡(jiǎn)化為三步完成，逐步減少搜索范圍。相對(duì)于全搜索算法計(jì)算復(fù)雜度大大降低。

3）基于塊的梯度下降搜索法：在梯度下降搜索法中，搜索程序總是沿著最優(yōu)的梯度下降方法移動(dòng)，所以可以認(rèn)為程序最終能找到最優(yōu)匹配點(diǎn)。

4）菱形搜索法：采用大菱形搜索模式和小菱形搜索模式，搜索效率相當(dāng)高。

5）六邊形搜索法：采用大六邊形模式和小六邊形模式。相對(duì)于菱形搜索法，搜索點(diǎn)數(shù)進(jìn)一步減少。

6）混合的非對(duì)稱(chēng)多六邊形搜索算法：即由陳志波等提出的UMHexagonS算法[3]，為H.264標(biāo)準(zhǔn)所采納，是目前效率最高的快速運(yùn)動(dòng)估計(jì)算。包括四個(gè)步驟:運(yùn)動(dòng)矢量預(yù)測(cè)；非對(duì)稱(chēng)的十字形搜索；多層六邊形搜索；擴(kuò)展的細(xì)化搜索。

3.5 當(dāng)前運(yùn)動(dòng)估計(jì)算法研究的思路和方向

可以概括如下[4]：

1）初始搜索點(diǎn)預(yù)測(cè)：使用多種預(yù)測(cè)模式，盡可能使初始搜索點(diǎn)接近全局最小，減少不必要的搜索點(diǎn)數(shù)；

2）減少搜索點(diǎn)數(shù)：使用早停止判斷、閾值判斷等方法調(diào)整搜索流程，減少不必要的搜索點(diǎn)數(shù)。

3）降低匹配計(jì)算復(fù)雜度：使用快速匹配技術(shù)，盡可能降低每個(gè)搜索點(diǎn)的匹配計(jì)算復(fù)雜度；

4）使用混合搜索策略：使用混合搜索策略，盡可能適應(yīng)各種運(yùn)動(dòng)序列場(chǎng)景的復(fù)雜性。

可見(jiàn)，當(dāng)前研究由單一搜索模式向自適應(yīng)、混合模式發(fā)展，目的在于降低計(jì)算復(fù)雜度，減少搜索時(shí)間，提高搜索速度，使其向有利于實(shí)時(shí)應(yīng)用發(fā)展，但目前的研究仍然不能達(dá)到實(shí)時(shí)編碼。

3.6當(dāng)前運(yùn)動(dòng)估計(jì)算法的不足之處

主要表現(xiàn)在以下方面：

1）采用固定的搜索模板和固定的搜索半徑，對(duì)于不同形狀特征的塊，搜索覆蓋效果不好；

2）固定的搜索模板不能根據(jù)不同特征的塊模式和物體運(yùn)動(dòng)的方向和運(yùn)動(dòng)的劇烈程度自適應(yīng)的改變搜索半徑和搜索范圍。

3）沒(méi)有充分挖掘和利用數(shù)據(jù)特征（如可變塊大小與運(yùn)動(dòng)矢量）等內(nèi)在信息及關(guān)聯(lián)性，并應(yīng)用于搜索過(guò)程，采用統(tǒng)一固定的多塊估計(jì)和多參考幀預(yù)測(cè)，使算法復(fù)雜度較高。

4）搜索的點(diǎn)數(shù)還相對(duì)較多、運(yùn)算量較大。

從以上分析可以看出，該算法仍然存在可以改進(jìn)的空間。

4 今后研究方向

視頻編碼中的運(yùn)動(dòng)估計(jì)算法的研究是與多學(xué)科有聯(lián)系的交叉學(xué)科，其研究范圍十分廣泛，在圖象壓縮中的應(yīng)用的涉及面也很廣，其中的許多理論和實(shí)際問(wèn)題還有待進(jìn)一步解決，技術(shù)發(fā)展十分迅速，新的挑戰(zhàn)層出不窮。今后可從以下幾個(gè)方面繼續(xù)開(kāi)展研究工作：

1）H.264研究?jī)?nèi)容的深入和擴(kuò)展：繼續(xù)挖掘宏塊和運(yùn)動(dòng)矢量?jī)?nèi)部之間的特征及其相關(guān)性，深入研究快速運(yùn)動(dòng)估計(jì)算法，可將幀間預(yù)測(cè)與幀內(nèi)預(yù)測(cè)結(jié)合進(jìn)行研究，以期進(jìn)一步優(yōu)化現(xiàn)有算法。

2）探索新的編碼模式：借鑒、對(duì)比、分析、研究和探索H.264框架以外的視頻編碼模式，擴(kuò)展思路，尋求更有效的視頻編碼方法。

參考文獻(xiàn)：

[1] Wiegand T. Overview of the H.264/AVC video coding standard[J].IEEE Tansactions on Circuits and Systems for Video Technology，2003，13(7):560-576.

[2] 沈蘭蓀，卓力.小波編碼與網(wǎng)絡(luò)視頻傳輸[M].北京：科學(xué)出版社，2004:146-248.

[3] CHEN Zhi-bo，ZHOU Peng，HE Yun.Fast Motion Estimation for JVT[C]. Joint Video Team (JVT)7th Meeting:Pattaya II，Thailand，2003.

[4] 林巍峣，方向忠，黃修超，等.一種快速的H.264幀間模式選擇算法[J].上海交通大學(xué)學(xué)報(bào)，2006，40(1):1-6.