高穎敏,李玖玲

摘 要:綜合分析各種運(yùn)動(dòng)估計(jì)搜索算法及算法的基本原理,在充分利用相鄰像素塊之間相關(guān)性的基礎(chǔ)上,提出一種新的快速搜索算法,意在保持圖像質(zhì)量不變的情況下,降低運(yùn)算復(fù)雜度,提高搜索效率。實(shí)驗(yàn)結(jié)果顯示,該算法的運(yùn)動(dòng)估計(jì)時(shí)間是FS算法的25%~30%,UMHexagonS的50%~60%,可見不失為實(shí)時(shí)性較好的算法。

關(guān)鍵詞:H.264;運(yùn)動(dòng)估計(jì);快速搜索算法;UMHexagonS

中圖分類號(hào):TN91981文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):1004-373X(2009)19-125-03

A New Fast Searching Algorithm of Motion Estimation for H.264/AVC

GAO Yingmin,LI Jiuling

(School of Information Engineering,Zhengzhou University,Zhengzhou,450001,China)

Abstract:In this paper,a new fast searching algorithm is proposed on the basis of comprehensive analysis of variety of searching motion estimation algorithm and it′s basic principles.It makes full use of the correlation between the adjacent pixel block.The purpose is to reduce complexity and improve the efficiency of search with maintaining the same image quality.Experimental results show that the time consuming of this algorithm is 25%-30% of FS and 50%-60% of UMHexagons.

Keywords:H.264;motion estimation;fast searching algorithm;UMHexagonS

0 引 言

H.264是由ISO/IEC與ITU-T聯(lián)合制定的新一代視頻壓縮編碼標(biāo)準(zhǔn)[1],與以往標(biāo)準(zhǔn)相比,H.264在性能上有了很大提高。在相同重構(gòu)圖像質(zhì)量下,H.264的預(yù)測精度達(dá)到1/4像素,與H.263和MPEG-4標(biāo)準(zhǔn)相比,能節(jié)約50%的碼率。但其運(yùn)算復(fù)雜度是H.263標(biāo)準(zhǔn)的4~5倍,其中先進(jìn)的運(yùn)動(dòng)估計(jì)算法扮演著不可忽視的角色。無論在硬件實(shí)現(xiàn),還是在軟件編程的過程中,運(yùn)動(dòng)估計(jì)和補(bǔ)償均占很重要的地位,而作為運(yùn)動(dòng)估計(jì)主要部分的搜索算法更為人門所重視。為了降低算法復(fù)雜度,提高算法實(shí)時(shí)性,人們研究出了多種快速算法,在很大程度上提高了算法的性效能。本文將介紹幾種重要的搜索算法,結(jié)合這些算法[2-6],同時(shí)對(duì)H.264中快速搜索原理進(jìn)行分析,給出了新的快速搜索算法。

1 H.264運(yùn)動(dòng)估計(jì)算法的特點(diǎn)

H.264標(biāo)準(zhǔn)中運(yùn)動(dòng)估計(jì)特點(diǎn)主要體現(xiàn)在三個(gè)方面:

(1) 高精度估計(jì)。采用1/4像素運(yùn)動(dòng)估計(jì),運(yùn)動(dòng)補(bǔ)償精度比H.263提高2倍,甚至4倍。由于其運(yùn)動(dòng)矢量的位移以1/4像素為基本單位,使得幀間剩余誤差更小,傳輸碼率更低,即壓縮比更高;

(2) 多宏塊劃分模式。在H.264的預(yù)測模式中,一個(gè)宏塊(MB)可劃分成7種不同模式的尺寸,這種多模式的靈活、細(xì)微的宏塊劃分,更切合圖像中實(shí)際運(yùn)動(dòng)物體的形狀;

(3) 多參考幀。采用多個(gè)參考幀的運(yùn)動(dòng)估計(jì),即在編碼器的緩存中存有多個(gè)剛剛編碼好的參考幀,并指出哪個(gè)幀被用于預(yù)測,這樣就可獲得比只用上一個(gè)剛編碼好的幀作為預(yù)測幀更好的編碼效果。

精確的運(yùn)動(dòng)估計(jì)可以大幅降低數(shù)據(jù)碼率,但同時(shí)也導(dǎo)致了算法的復(fù)雜度增加,其復(fù)雜性主要集中在以下幾個(gè)方面:

(1) 多尺寸幀間像塊模式搜索。多尺寸像塊劃分模式使得幀間預(yù)測時(shí)像塊的匹配更準(zhǔn)確,從而提高PSNR和降低碼率。但幀間像塊模式的快速選擇十分重要,增加了算法復(fù)雜性。

(2) 高精度運(yùn)動(dòng)搜索。運(yùn)動(dòng)矢量精度提高到1/4像素,增加了算法復(fù)雜性。

(3) 多參考幀預(yù)測。H.264在幀間預(yù)測時(shí)可以支持5個(gè)參考幀,通過多個(gè)參考幀進(jìn)行運(yùn)動(dòng)搜索,可以獲得更好的預(yù)測效果,研究表明其可節(jié)省14%的碼率,但也增加了復(fù)雜性。

2 基于H.264的快速搜索算法分析

2.1 三步搜索法(Three Step Search,TSS)和新三步搜索法(NewTSS,NTSS)

三步搜索法[2]是由T.Koga等人提出的在搜索范圍中限制搜索點(diǎn)的一種搜索算法。對(duì)于H.264全搜索法(FS)要完成搜索15×15=225個(gè)點(diǎn)的計(jì)算量,采用TSS搜索法計(jì)算25個(gè)搜索點(diǎn)即可完成。三步搜索法的數(shù)據(jù)讀取比較規(guī)則,也易于硬件實(shí)現(xiàn),所以被許多標(biāo)準(zhǔn)推薦使用。但由于算法第一步過于粗糙,在搜索范圍較大(或更大)時(shí),初始步長相對(duì)于塊的運(yùn)動(dòng)矢量估計(jì)來說太大了,跳出了可能性比較大的區(qū)域,會(huì)導(dǎo)致搜索方向的不確定性,因此很容易陷入局部最優(yōu)。于是Renxiang Li等人提出了新三步搜索法NTSS[3],其核心思想是采用具有中心偏置的搜索點(diǎn)模式,并應(yīng)用中止門限判斷來減少搜索次數(shù)。對(duì)于緩慢變化的序列NTSS,其平均信噪比明顯高于TSS算法,而對(duì)于變化相對(duì)較快,特別是運(yùn)動(dòng)平均的序列NTSS,其優(yōu)勢就不明顯了。如果把新三步法中心的小正方形分別換成十字形、菱形、六邊形等,會(huì)在不同性能方面有所提高。

2.2 菱形搜索算法(Diamond Seacrh,DS)和六邊形搜索(HEXBS)算法

Zhu和Ma在2000年提出了菱形搜索法[4],與過去提出的正方形搜索模式不同,DS算法第一次提出搜索應(yīng)該是各向同性的,即應(yīng)該選用圓形搜索模式。表現(xiàn)在離散化后的平面上,就變成了菱形的搜索模式。DS算法無論在性能,還是質(zhì)量上都優(yōu)于TSS算法。但對(duì)于運(yùn)動(dòng)大的序列,菱形法在搜索最佳點(diǎn)所在區(qū)域時(shí),廣度搜索和梯度下降同時(shí)進(jìn)行,即同等地對(duì)待搜索區(qū)域的各部分,造成較大的搜索冗余,影響了算法的搜索速度。另外,對(duì)于保持靜止的圖像序列,即零運(yùn)動(dòng)矢量的情況,菱形法仍要對(duì)13個(gè)搜索點(diǎn)進(jìn)行搜索,這是有待改進(jìn)之處。

六邊形搜索(HEXBS)算法[5]是將DS的LDSP改成六邊形模式,SDSP仍然保留。實(shí)踐證明,現(xiàn)實(shí)世界的視頻塊運(yùn)動(dòng)矢量有超過80%的概率落在以中心點(diǎn)為圓心,2為半徑的圓內(nèi)。由于大六邊形模式相對(duì)于其他模式來說,更接近于以2為半徑的圓,所以搜索效率更高。

2.3 非對(duì)稱十字型多層次六邊形格點(diǎn)搜索算法(UMHexagonS)

UMHexagonS算法[6]采用多種運(yùn)動(dòng)矢量預(yù)測及六邊形搜索模式,能降低90%的整像素運(yùn)動(dòng)搜索復(fù)雜度,而PSNR的下降小于0.05 dB,是到目前為止效果最高的快速運(yùn)動(dòng)估計(jì)算法。UMHexagonS首先確定搜索起始點(diǎn),在起始搜索矢量的集合中搜索一個(gè)對(duì)應(yīng)費(fèi)用函數(shù)值最小的候選運(yùn)動(dòng)矢量作為起始搜索點(diǎn),然后判斷是否提前截止。該算法搜索過程如圖1所示。

圖1 UMHexagonS的搜索過程

UMHS算法比DS算法可以取得更好的預(yù)測效果,但是UMHS算法因?yàn)椴襟E多,所以在搜索過程中增加了大量的搜索點(diǎn),運(yùn)算時(shí)間消耗較多。

3 新的快速搜索算法

本文將對(duì)文獻(xiàn)[7]中的小菱形分層搜索算法做出改進(jìn),將其第四步的底層搜索換成UMHexagonS,具體步驟與其相同,下面給出詳細(xì)介紹。

由于實(shí)際中絕大部分視頻圖像的運(yùn)動(dòng)都很小,如可視電話、視頻會(huì)議中的視頻圖像序列運(yùn)動(dòng)矢量通常都高度集中在零矢量及其附近,這稱為中心偏移性。對(duì)運(yùn)動(dòng)矢量為零的塊在這里稱其為靜止塊,運(yùn)動(dòng)矢量很小的塊(運(yùn)動(dòng)矢量在以(0,0)為中心的5×5的區(qū)域內(nèi))稱其為準(zhǔn)靜止塊,其他的塊稱為運(yùn)動(dòng)塊,那么有超過80%的塊可被看作靜止或準(zhǔn)靜止塊。由此,可設(shè)一個(gè)閾值T0,當(dāng)零矢量位置的塊匹配的SAD值小于T0時(shí),認(rèn)為當(dāng)前塊為靜止塊,則停止搜索(一步停止法);再設(shè)一個(gè)閾值T1,當(dāng)零矢量位置的塊匹配SAD值大于T0而小于T1時(shí),認(rèn)為當(dāng)前塊為準(zhǔn)靜止塊。在進(jìn)行準(zhǔn)靜止塊搜索時(shí),由于運(yùn)動(dòng)矢量比較小,這里采用小菱形搜索模式。

在對(duì)運(yùn)動(dòng)塊進(jìn)行搜索時(shí),一般分為粗略搜索和精確搜索兩步,如DS搜索時(shí)先用菱形模式進(jìn)行粗略搜索,然后再用小菱形模式進(jìn)行精確定位;HEXBS搜索時(shí)先用大六邊形模式進(jìn)行粗略搜索,然后再用小六邊形模式進(jìn)行精確定位。另一種搜索方法就是運(yùn)用多分辨塔方式進(jìn)行搜索,將圖像金字塔應(yīng)用到運(yùn)動(dòng)估計(jì)是一項(xiàng)新技術(shù),它充分利用了運(yùn)動(dòng)矢量場在空間和時(shí)間兩個(gè)方向的相關(guān)性,在低分辨率的頂層中求出粗略的運(yùn)動(dòng)矢量,然后以此為基礎(chǔ),指導(dǎo)下一層的運(yùn)動(dòng)估計(jì),逐漸縮小運(yùn)動(dòng)搜索范圍。多分辨塔算法的分層不宜太多,在實(shí)際應(yīng)用中一般取2~3層。對(duì)于本文的整像素運(yùn)動(dòng)估計(jì)算法,取2層多分辨塔,采用均值濾波采樣算法,將原圖像幀幀的像素值作為塔的底層,記為S0(x,y,k),(x,y)為平面點(diǎn)坐標(biāo),k為幀序號(hào),頂層塔記為S1(x,y,k),則頂層的采樣公式為:

S1(x,y,k)=14∑1m=0∑1n=0S0(2x+m,2y+n,k)(1)

這樣第k幀就由兩層塔分別構(gòu)成底層{S0(x,y,k),0≤x≤N0-1,0≤y≤M0-1}和頂層{S1(x,y,k),0≤x≤(N0/2)-1,0≤y≤(M0/2)-1},如圖2所示。在進(jìn)行運(yùn)動(dòng)搜索的時(shí)候,先在頂層進(jìn)行搜索,結(jié)果傳遞給下層再進(jìn)行搜索,每一層的搜索方式都采用小菱形搜索模式。由于底層4個(gè)點(diǎn)只能抽樣為頂?shù)囊粋€(gè)點(diǎn),即底層16×l6的宏塊相當(dāng)于頂層8×8的塊,所以在進(jìn)行運(yùn)動(dòng)搜索時(shí),頂層搜索塊應(yīng)相當(dāng)于底層塊的1/4大小,如在頂層進(jìn)行8×8的塊搜索,而在底層進(jìn)行16×16的宏塊搜索,也即是說,中層搜索一個(gè)點(diǎn)計(jì)算量僅相當(dāng)于底層一個(gè)點(diǎn)計(jì)算量的1/4。

圖2 兩層多分辨塔

算法具體步驟如下:

第一步:計(jì)算(0,0)位置的SAD值,判斷SAD值是否小于T0,如果小于,則判定當(dāng)前塊為靜止塊,停止搜索,輸出MV為(0,0),否則進(jìn)行下一步;

第二步:判斷SAD值是否小于T1,如果小于,則判定當(dāng)前塊為準(zhǔn)靜止塊,跳到第四步,否則進(jìn)行第三步;

第三步:進(jìn)行分層搜索的頂層搜索。首先確定搜索起始位置,如圖3所示。選取V1,V2,V3,再加上V4=(0,0)為候選起始運(yùn)動(dòng)矢量,其中V1為當(dāng)前塊左邊塊的運(yùn)動(dòng)矢量,V2為當(dāng)前塊上方塊的運(yùn)動(dòng)矢量,V3為當(dāng)前塊右上方塊的運(yùn)動(dòng)矢量,V4為(0,0)矢量。計(jì)算這四個(gè)位置的SAD值,選取最優(yōu)點(diǎn)為運(yùn)動(dòng)搜索的起始點(diǎn),然后以起始點(diǎn)為中心,進(jìn)行小菱形搜索,結(jié)束后轉(zhuǎn)下一步;

第四步:進(jìn)行底層搜索,如果是由第二步跳轉(zhuǎn)來的,則以(0,0)為中心進(jìn)行UMHexagonS搜素;如果由第三步轉(zhuǎn)來的,則以頂層所得的運(yùn)動(dòng)矢量乘以2為初始運(yùn)動(dòng)矢量進(jìn)行小菱形搜索,結(jié)束后輸出MV。

圖3 候選起始運(yùn)動(dòng)矢量

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

以JVT的JM86為測試平臺(tái),對(duì)圖像格式為QCIF的三種典型的標(biāo)準(zhǔn)圖像序列“Akiyo”(運(yùn)動(dòng)緩慢)、“Foreman”(中等運(yùn)動(dòng))、“Carphone”(運(yùn)動(dòng)劇烈)的前100幀進(jìn)行測試,實(shí)驗(yàn)室選用3個(gè)參考幀,幀速為30 f/s,搜索范圍為16,編碼序列為IPPP格式,量化系數(shù)為28,采用Hadamard變換和CABAC熵編碼,試驗(yàn)測試結(jié)果如表1所示。從表中可以看出,改進(jìn)算法的SPNR與FS算法相比略有下降,但改進(jìn)算法的運(yùn)動(dòng)估計(jì)時(shí)間是FS算法的25%~30%,UMHexagonS的50%~60%,可見實(shí)時(shí)性得到明顯提高。

表1 搜索算法的性能比較

算法Akiyo序列Foreman序列Carphone序列

YPSNR

/dBUPSNR

/dBVPSNR

/dBtME /sYPSNR

/dBUPSNR

/dBVPSNR

/dBtME /sYPSNR

/dBUPSNR

/dBVPSNR

/dBtME /s

FS37.3739.5440.6245736.0239.1340.7247036.1237.2040.63468

UMHexagonS37.3539.5240.5920535.8938.6740.5223435.6935.8940.03221

改進(jìn)算法36.3639.5340.7212136.0139.0240.6913535.9436.9240.52118

5 結(jié) 語

運(yùn)動(dòng)估計(jì)是視頻編碼器中計(jì)算量最大的一個(gè)模塊,由于能夠有效地減少幀間相關(guān)性,被廣泛用于各種視頻編碼標(biāo)準(zhǔn)中。本文對(duì)快速運(yùn)動(dòng)估計(jì)算法原理進(jìn)行了分析,并詳細(xì)介紹了幾種目前比較重要的整像素搜索算法,在此基礎(chǔ)上結(jié)合H.264標(biāo)準(zhǔn)要求,提出了用于H.264標(biāo)準(zhǔn)的快速算法改進(jìn)思路和改進(jìn)算法。本文創(chuàng)新點(diǎn):充分利用相鄰塊之間的相關(guān)性,結(jié)合不同視頻序列的特點(diǎn)設(shè)計(jì)了混合式分層搜索算法。

參考文獻(xiàn)

[1]畢厚杰.新一代視頻壓縮編碼標(biāo)準(zhǔn)H.264/AVC[M].北京:人民郵電出版社,2005.

[2]Babu D V,An P S R,Karthikeyan C.Performance Analysis of Block Matching Algorithms for Highly Scalable Video Compre-ssion[J].IEEE,2006:179-182.

[3]Shan Zhu,Kai Kuang Ma.A New Diamond Search Algorithm for Fast Block Matching Motion Estimation[J].IEEE Trans.on Image Processing,2000,9(2):287-290.

[4]Ce Zhu,Xiao Lin,Lap Pui Chau.Hexagon-based Search Pattern for Fast Block Motion Estimation[J].IEEE Trans.on Circuits and Systems for Video Technology,2002,12(5):349-355.

[5]周巍,史浩山,周欣.基于H.264的快速運(yùn)動(dòng)估計(jì)算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2007,28(2):379-381,385.

[6]Li Renxiang,Zeng Bing,Liu Ming L.A New Three-step Search Algorithm for Block Motion Estimation[J].IEEE Trans.on Circuit and Systems for Video Technology,1994,4(4):438-442.

[7]喬軒.H.26X系列的算法研究[D].杭州:浙江大學(xué),2005.

[8]張淑芳,李華,劉曉青,等.基于H.264的復(fù)雜度-失真最有的運(yùn)動(dòng)估計(jì)算法[J].計(jì)算機(jī)工程,2007,33(9):228-230,234.

[9]陳傳東,陳新.H.264中二進(jìn)制算術(shù)編碼的硬件實(shí)現(xiàn)[J].現(xiàn)代電子技術(shù),2007,30(22):48-50.