基于H.264快速運(yùn)動估計算法研究

戴小新

（衡陽師范學(xué)院 計算機(jī)科學(xué)系，湖南 衡陽 421002）

H.264是由ITU－T和ISO／IEC組成的聯(lián)合視頻組提出的高度壓縮數(shù)字視頻編解碼器標(biāo)準(zhǔn)。H.264最大的優(yōu)勢是具有很高的數(shù)據(jù)壓縮比率，在同等圖像質(zhì)量的條件下，H.264的壓縮比是MPEG－2的2倍以上，是MPEG－4的1.5～2倍。然而，其效率的提高是以增加計算復(fù)雜度為代價的，視頻壓縮編碼的關(guān)鍵部分是運(yùn)動估計，其時間開銷占整個編碼時間的60%以上。因此，以犧牲較少的圖像質(zhì)量為代價來降低運(yùn)動估的計算復(fù)雜度就顯得很有必要了。

運(yùn)動估計快速搜索算法是以犧牲最佳匹配塊的運(yùn)動矢量準(zhǔn)確度，來減少搜索計算的復(fù)雜度，做到搜索時間與搜索結(jié)果的最優(yōu)平衡。研究者們提出了許多新的算法，比較早的主要有二維對數(shù)搜索（TDLS）法、三步搜索（TSS）法和變方向搜索（CDS）法，這些算法在處理小運(yùn)動視頻序列時效果比較好，而對大運(yùn)動視頻序列效果不理想，容易陷入局部最優(yōu)陷阱；后來又提出了新三步搜索（NTSS）法、四步搜索（FSS）法、梯度下降搜索（BBGDS）法、菱形搜索（DS）法、混合非對稱多層次六邊形搜索（UMHexagonS）法和六邊形搜索（HEXBS）法等算法［1］。其中UMHexagonS算法在一定程度上避免了這一問題，被H.264標(biāo)準(zhǔn)所采用，本文算法與該算法進(jìn)行比較，作為評估本文算法水平的標(biāo)準(zhǔn)。

在運(yùn)動估計過程中，如何利用提前終止策略來加速H.264的視頻編碼，一直是研究者們研究的問題。塊匹配運(yùn)動估計算法由于簡單、高效、開銷小、易于實現(xiàn)等優(yōu)點(diǎn)而被大多數(shù)視頻編碼標(biāo)準(zhǔn)所采用，該算法匹配的準(zhǔn)則有三種，即平均均方誤差（MSE）、平均絕對差（MAD）和歸一化函數(shù)（NCCF）［2］，為了降低計算復(fù)雜度，在運(yùn)動估計過程中，通常用絕對誤差和（SAD）來代替MAD，SAD的定義如下：

1 基于H.264快速運(yùn)動估計

本文算法對當(dāng)前宏塊在原點(diǎn)的SAD值和預(yù)設(shè)閾值進(jìn)行比較，確定候選尺寸塊，通過部分像素和多參考幀技術(shù)搜索出整像素最佳運(yùn)動矢量，并以其為搜索中心，通過基于部分像素的亞像素運(yùn)動估計獲得亞像素最佳運(yùn)動矢量，最終確定運(yùn)動估計的最佳尺寸塊，本文提出的算法就從這三個方面進(jìn)行改進(jìn)的。

1.1 塊尺寸預(yù)選

H.264支持七種尺寸塊分割用于運(yùn)動估計，本文把七種尺寸塊分為大尺寸塊和小尺寸塊兩類：16×16、16×8、8×16為大尺寸塊，8×8、8×4、4×8、4×4為小尺寸塊。在H.264中，宏塊的SAD值確定了其運(yùn)動特性，首先計算出宏塊在原點(diǎn)的SAD值，如果SAD值小于預(yù)設(shè)閾值，則只搜索大尺寸塊，否則，搜索所有尺寸塊，確定宏塊的最佳劃分方式。

1.2 整像素匹配

為了減少宏塊的運(yùn)動估計時間，本文所提的算法僅抽取所有像素中具有代表性的一部分像素參與塊匹配，按照計算精度不同，本算法設(shè)計了兩種匹配模板：把當(dāng)前宏塊及其參考塊分成4個子塊或16個子塊，并計算出SAD值，記作SAD（4）或SAD（16）。

步驟描述如下：

（1）計算出初始幀給定尺寸塊在零運(yùn)動矢量（ZMV）和預(yù)測運(yùn)動矢量（PMV）的SAD值，把較小值記作SAD（a），預(yù)設(shè)的閾值記為T（i）。如果SAD（a）＜T（i），則確定SAD（a）所在點(diǎn)為最佳整像素匹配點(diǎn)，并停止搜索；否則，以SAD（a）所在點(diǎn)為搜索的中心，轉(zhuǎn)至步驟（b）。

（2）以SAD（4）匹配模板和全搜索策略進(jìn)行分辨率匹配，把具有最小SAD（4）值的點(diǎn)確定為初始匹配點(diǎn)。

（3）把初始匹配點(diǎn)與其八鄰域點(diǎn)中具有最小SAD（16）值的點(diǎn)確定為初始幀的最佳匹配點(diǎn)。

（4）除初始幀外，其他幀的初始匹配點(diǎn)由其前一幀的最佳匹配點(diǎn)確定。

（5）以步驟（3）的方法確定當(dāng)前幀的最佳匹配點(diǎn)。

（6）重復(fù)步驟（4）－（5），確定各幀的最佳匹配點(diǎn)。

（7）選擇各幀中具有最小SAD（16）值的點(diǎn)作為整像素最佳匹配點(diǎn)。

1.3 亞像素匹配

在進(jìn)行亞像素搜索時，先搜索位于最佳整像素匹配點(diǎn)相鄰的1／2像素點(diǎn)（8個），確定1／2像素最佳點(diǎn)，然后再搜索其相鄰的1／4像素點(diǎn)（8個），確定最佳1／4像素點(diǎn)，以其作為最終運(yùn)動估計矢量，如圖1所示，整像素點(diǎn)用黑點(diǎn)表示，1／2像素點(diǎn)用三角形表示，最佳整像素匹配點(diǎn)用O點(diǎn)表示。

圖1 亞像素運(yùn)動估計優(yōu)化圖

實驗表明，最佳匹配點(diǎn)一般為SAD值較小的1／2像素點(diǎn)，為了減少計算量，我們只搜索其中概率較大的候選點(diǎn)，如圖1，首先把V1、V2、H1、H2四個整像素點(diǎn)的SAD值記為SAD（V1）、SAD（V2）、SAD（H1）、SAD（H2），則本文的亞像素運(yùn)動估計算法步驟描述如下：

（1）找出V1，V2，H1，H2中SAD值最小的點(diǎn)，并將其命名為A。

（2）從V1，V2，H1，H2中找出A的相鄰點(diǎn)中SAD值較小的點(diǎn)，并將其命名為B。如A＝V1，則H1、H2為其相鄰點(diǎn)。如果SAD（H2）＜SAD（H1），則B＝H2；反之亦然。

（3）以位于點(diǎn)A和點(diǎn)O中間、點(diǎn)A和點(diǎn)B中間的1／2像素點(diǎn)和O點(diǎn)作為1／2像素候選點(diǎn)。如果：A＝V1、B＝H2，則點(diǎn)5、6和O為候選點(diǎn)。搜索這3個候選點(diǎn)，確定1／2像素最佳匹配點(diǎn)。

（4）通過搜索1／2像素最佳匹配點(diǎn)和其相鄰的8個1／4像素點(diǎn)確定1／4像素最佳匹配點(diǎn)。

1.4 算法描述

綜上所述，本文的快速運(yùn)動估計算法描述如下：

（1）計算當(dāng)前宏塊在搜索原點(diǎn)的SAD值，記為SAD（0），預(yù)設(shè)的閾值記為T（i），如果SAD（0）＜T（i），則跳過小尺寸塊；否則搜索所有7種尺寸塊。

（2）抽取塊中的部分像素，通過多參考幀技術(shù)確定整像素最佳匹配點(diǎn)。

（3）以步驟（2）確定的整像素最佳匹配點(diǎn)為搜索中心，通過亞像素匹配確定亞像素最佳匹配點(diǎn)。

（4）重復(fù)步驟（2）－（3），對其他尺寸塊進(jìn)行搜索，選擇開銷最小的尺寸塊為最佳運(yùn)動矢量。

2 實驗及結(jié)果分析

本算法在JM10.2代碼中實現(xiàn)，通過UMHexagonS算法和本文算法與FS算法進(jìn)行比較，來分析本算法的性能，選取CABAC編碼模式在量化系數(shù)QP分別為24、28、32、36、40的條件下編碼300幀進(jìn)行測試，選取Akiyo、News、Foreman、Tempete、Mobile、和Stefan為測試序列，取5個參考幀數(shù)，格式為IPPP的GOP，搜索半徑為16像素，其余編碼參數(shù)使用默認(rèn)值。

實驗對算法得出的PSNR、碼率、序列編碼時間和運(yùn)動估計時間進(jìn)行了統(tǒng)計，并計算出UMHexagonS算法和本文算法參照FS算法的PSNR變化（△PSNR）、碼率增加百分比（△B），編碼時間增加百分比（△T），運(yùn)動估計時間增加百（△MET），因篇幅所限，表1給出了QP＝32下的比較結(jié)果，表中正表示增加，負(fù)表示減少，（a）為UMHexagonS算法結(jié)果，（b）為本文算法結(jié)果。從表1可以看出，本文算法與FS算法比較，其運(yùn)動估計耗時最多降低72.15%，平均降低69%；編碼總時間平均降低58%；其PSNR僅減少0.033dB，對圖像質(zhì)量基本沒有影響；碼率增加最大不超過1.42%，平均僅增加0.657%，壓縮比基本保持不變。與UMHexagonS算法比較，本文所提算法在保持了相近的PSNR和碼率的情況下，運(yùn)動估計耗時下降了13%。

表1 QP＝32時算法性能比較

3 結(jié)束語

針對H.264中運(yùn)動估計計算復(fù)雜度過高的問題，提出在運(yùn)動估計過程中使用宏塊預(yù)測的提前終止策略來縮小搜索范圍，并且通過部分像素匹配、多參考幀選取、亞像素匹配，及基于兩種匹配模板進(jìn)行搜索，實驗表明，與FS算法和UMHexagonS算法比較，本文算法在保證編碼質(zhì)量的情況下，運(yùn)動估計耗時平均下降了69%和13%，是一種效率較高的快速運(yùn)動估計算法。

［1］毛小明，鮑可進(jìn).一種基于H.264／AVC的高性能快速運(yùn)動估計算法［J］.計算機(jī)應(yīng)用，2012（4）：1598－1600.

［2］余兆明，查日勇，黃磊，等.圖像編碼標(biāo)準(zhǔn)H.264技術(shù)［M］.北京：人民郵電出版社，2003.