一種新的H.264運動估計快速搜索算法

高穎敏,李玖玲

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

關鍵詞:H.264;運動估計;快速搜索算法;UMHexagonS

中圖分類號:TN91981文獻標識碼:A

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

1 H.264運動估計算法的特點

H.264標準中運動估計特點主要體現(xiàn)在三個方面:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖1 UMHexagonS的搜索過程

UMHS算法比DS算法可以取得更好的預測效果,但是UMHS算法因為步驟多,所以在搜索過程中增加了大量的搜索點,運算時間消耗較多。

3 新的快速搜索算法

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

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

在對運動塊進行搜索時,一般分為粗略搜索和精確搜索兩步,如DS搜索時先用菱形模式進行粗略搜索,然后再用小菱形模式進行精確定位;HEXBS搜索時先用大六邊形模式進行粗略搜索,然后再用小六邊形模式進行精確定位。另一種搜索方法就是運用多分辨塔方式進行搜索,將圖像金字塔應用到運動估計是一項新技術,它充分利用了運動矢量場在空間和時間兩個方向的相關性,在低分辨率的頂層中求出粗略的運動矢量,然后以此為基礎,指導下一層的運動估計,逐漸縮小運動搜索范圍。多分辨塔算法的分層不宜太多,在實際應用中一般取2~3層。對于本文的整像素運動估計算法,取2層多分辨塔,采用均值濾波采樣算法,將原圖像幀幀的像素值作為塔的底層,記為S0(x,y,k),(x,y)為平面點坐標,k為幀序號,頂層塔記為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所示。在進行運動搜索的時候,先在頂層進行搜索,結(jié)果傳遞給下層再進行搜索,每一層的搜索方式都采用小菱形搜索模式。由于底層4個點只能抽樣為頂?shù)囊粋€點,即底層16×l6的宏塊相當于頂層8×8的塊,所以在進行運動搜索時,頂層搜索塊應相當于底層塊的1/4大小,如在頂層進行8×8的塊搜索,而在底層進行16×16的宏塊搜索,也即是說,中層搜索一個點計算量僅相當于底層一個點計算量的1/4。

圖2 兩層多分辨塔

算法具體步驟如下:

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

第二步:判斷SAD值是否小于T1,如果小于,則判定當前塊為準靜止塊,跳到第四步,否則進行第三步;

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

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

圖3 候選起始運動矢量

4 實驗結(jié)果

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

表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

改進算法36.3639.5340.7212136.0139.0240.6913535.9436.9240.52118

5 結(jié) 語

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

參考文獻

[1]畢厚杰.新一代視頻壓縮編碼標準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的快速運動估計算法[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].杭州:浙江大學,2005.

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

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