張永軒,霍家道

(江蘇自動化研究所,江蘇 連云港　222061)

?

視頻編碼標(biāo)準(zhǔn)H.264運動矢量搜索算法

張永軒,霍家道

(江蘇自動化研究所,江蘇 連云港222061)

高清視頻的信息量巨大,傳輸比較困難。H.264作為視頻壓縮的主流標(biāo)準(zhǔn),可以有效去除視頻的冗余信息,提高視頻的網(wǎng)絡(luò)傳輸能力。針對H.264中運動估計算法耗時嚴(yán)重的問題,提出一種新的X型搜索算法。X型算法由粗到細(xì)地進(jìn)行搜索,先以X型快速搜索確定運動矢量的可能范圍,然后在可能范圍內(nèi)進(jìn)行局部全搜索,最終確定運動矢量。試驗結(jié)果表明,X型搜索能夠在保證視頻質(zhì)量的情況下大幅度縮短編碼時間,有效提高運動估計算法的效率,兼顧了速度與精度,為高清視頻的實時傳輸提供了保障。

H.264;運動估計;X型搜索

多媒體的進(jìn)步深刻影響著人們生活、工作的方式和質(zhì)量。視頻因為其直觀、生動的特性,受到廣泛的關(guān)注。然而,隨著視頻清晰度的提高,所包含的信息也越來越多,視頻傳輸?shù)膶崟r性問題日益突出。H.264作為視頻壓縮的主力軍,在保證了視頻質(zhì)量的前提下,提供了足夠的壓縮比,保證了高清視頻傳輸?shù)膶崟r性。由于活動圖像鄰近幀中的景物具有一定的相關(guān)性,可將活動圖像分成若干塊,并搜索出每個塊在鄰近幀的位置,兩者之間的相對偏移量就是對應(yīng)塊的運動矢量,這就是運動估計算法[1]。例如,當(dāng)前幀內(nèi)的汽車作為一個分割塊,在鄰近幀內(nèi)找到同樣的汽車,那么傳輸時只要傳遞一個汽車的圖像和相對的運動矢量,就可以知道汽車在鄰近幀的位置,大幅度壓縮了傳輸?shù)男畔⒘?節(jié)約了傳輸帶寬。運動估計算法作為H.264標(biāo)準(zhǔn)的核心技術(shù),也是H.264耗時最嚴(yán)重的部分,占據(jù)了整個視頻編碼時間的50%-80%。因此,怎樣在保證視頻質(zhì)量的前提下縮短運動估計的時間對高清視頻的實時處理具有重要的意義。

1　H.264運動估計幾種核心算法介紹

本節(jié)介紹了幾種主要的運動估計算法,示意圖中的點代表搜索塊的中心像素,假設(shè)分割塊的尺寸為4*4。通過將中心像素對應(yīng)的搜索塊與原始圖像塊進(jìn)行匹配計算,得到最優(yōu)匹配塊。

1.1全局搜索算法

全局搜索算法[2]是最早提出的運動估計算法,其本質(zhì)就是在搜索范圍內(nèi),對每一個塊都與當(dāng)前塊做匹配計算,找到匹配誤差最小的點。這種算法準(zhǔn)確率最高,但計算量急劇增加。這對于高清視頻傳輸是極其不利的,所以很少有實際應(yīng)用。

1.2三步搜索算法(TTS)

三步搜索算法[2]是美國人Koga et al在1981年提出的。它的算法簡單易行,魯棒性強,預(yù)測的結(jié)果與全局搜索比較接近,但在算法第二步中步長被直接減半,如果初始預(yù)測矢量的位置有較大誤差,就很容易陷入局部最優(yōu)的困境。這種算法對于運動幅度小的圖像處理效率較低[2]。具體步驟如圖1所示。

圖1　三步搜索算法

1.3菱形搜索算法

菱形搜索算法[2]簡單、高效而且準(zhǔn)確,是目前性能最好的算法之一。在搜索時,首先用大菱形模板進(jìn)行快速搜索,直到中心匹配塊為最優(yōu)匹配,再用小菱形模板進(jìn)行小范圍搜索,取得最優(yōu)匹配。大模板和小模板的使用,不僅提高了搜索速度,而且兼顧了搜索精度。具體步驟如圖2所示。

圖2　菱形搜索算法

2　改進(jìn)的運動估計算法

快速算法相較全搜索算法而言,有效減少了計算的次數(shù),但也存在以下兩個問題。

1)快速算法大部分遵從由粗到細(xì)的原則進(jìn)行搜索,在初期的搜索中,主要任務(wù)是用最少的搜索次數(shù)確定運動矢量的大致范圍,而通常的快速算法初期搜索的模板搜索點數(shù)過多,要進(jìn)行10次左右的匹配計算,還不夠“快”,而且模板的搜索重心在水平和垂直方向上,不符合物體運動規(guī)律。

2)全搜索計算量巨大,而快速算法為了減少計算次數(shù),不可避免地會漏掉很多點的匹配計算,如果不能合理解決這個問題,會很容易陷入局部最優(yōu)的困境。

2.1對角線式快速搜索確定運動矢量范圍

圖3　物體斜方向運動匹配搜索示意圖

2.2局部全搜索避免局部最優(yōu)

針對問題2),由于全搜索計算量太大,快速算法又不可避免地要省略一些點的匹配計算,所以很難找到最優(yōu)匹配塊。為了減少匹配精度的損失,本文提出局部全搜索的方法。在確定運動矢量大致范圍后,計算水平和垂直5個位置(A,B,C,D,E)的匹配程度,不僅可以彌補水平和垂直方向搜索的不足,還可以進(jìn)一步縮小搜索范圍,在小范圍內(nèi)進(jìn)行全搜索,在提升搜索速度的前提下達(dá)到次優(yōu)匹配的目的,避免局部最優(yōu)的尷尬。具體的搜索范圍分割如圖4所示。

圖4　局部全搜索分割示意圖

2.3X型搜索算法

綜合針對兩個問題的解決方法,本文提出一種新的運動矢量搜索算法——X型搜索算法。具體步驟如圖5所示。

圖5　X型搜索算法

主要步驟:

步驟一:預(yù)測步長d=2,在中心塊和周圍4個角上進(jìn)行匹配測試,若最佳匹配塊在中心塊,則執(zhí)行步驟二,否則以最佳匹配塊為中心塊,重復(fù)步驟一。

步驟二:以中心塊為原點,計算水平和垂直方向d=2的4個塊及中心塊,共5個塊的匹配程度,得到最優(yōu)匹配塊,執(zhí)行步驟三。

步驟三:若最優(yōu)匹配塊不在中心塊,則搜索當(dāng)前最優(yōu)塊和周圍5個塊;否則搜索中心塊周圍8個塊綜合比較,選出最優(yōu)匹配塊。

運動矢量具有零點偏置性[4],所以本文將預(yù)測步長設(shè)置為2。步驟一和步驟二快速確定運動矢量的大致范圍,步驟三進(jìn)行了水平和垂直方向上的搜索,彌補了水平和垂直方向搜索的不足,同時確定了局部全搜索的范圍。步驟四局部全搜索是在小范圍內(nèi)進(jìn)行全搜索,保證了搜索的精度,避免預(yù)測矢量陷入局部最優(yōu)的尷尬,兼顧了搜索速度與運動矢量的準(zhǔn)確性。

3　運動估計算法匹配準(zhǔn)則

為了方便比較幾種運動矢量搜索算法的匹配程度,需要一個比較標(biāo)準(zhǔn)。最常用的有均方誤差(MSE)、平均絕對誤差(MAE)和絕對誤差和(SAE),假設(shè)當(dāng)前塊大小為N*N,則具體算法如公式(1),(2),(3)所示。

(1)

(2)

(3)

式中,Cij表示當(dāng)前塊(i,j)處的像素,Rij表示參考塊的相應(yīng)像素,i,j表示像素在塊內(nèi)水平和垂直方向上的編號。計算結(jié)果越小,表明差異越小,匹配程度越高。

SAE算法全是加減運算,沒有除法運算,絕對值的計算與平方相比,也要簡單許多,有利于減輕硬件的計算壓力,提高運算速度。所以,本文采用SAE作為匹配程度的標(biāo)準(zhǔn)。

4　實驗結(jié)果分析

本文以官方提供的H.264編解碼器JM86為平臺,測試各個運動矢量算法。實驗采用6種搜索算法對不同復(fù)雜度的3個視頻序列進(jìn)行測試,得到的實驗數(shù)據(jù)如表1所示,X型搜索的解碼圖像與初始圖像的成像對比由圖6,7,8所示。

圖6　Foreman成像對比

圖7　ICE成像對比

圖8　SOCCER成像對比

對視頻壓縮性能的評價主要看壓縮比和解碼視頻的質(zhì)量,在保證視頻質(zhì)量的前提下提供最大的壓縮比是視頻壓縮算法的目標(biāo)。接下來對試驗的幾個主要參數(shù)進(jìn)行分析。

壓縮比:在實驗中,視頻編碼的速度始終都控制在30幀/秒,所以碼率可以反映視頻的壓縮程度。從表1能夠看出,X型搜索在三種視頻序列中,雖然碼率比全搜索要高,但高的有限,而且與其他公認(rèn)的快速算法比相差不多,所以X型搜索算法在壓縮比上是符合要求的,視頻壓縮后冗余度不大,有利于傳輸。

信噪比:信噪比反應(yīng)了圖像還原的程度,可以看成視頻質(zhì)量,是運動估計算法的一項重要參數(shù)。Foreman視頻序列的復(fù)雜度一般,主要是人物面部表情的運動,背景幾乎靜止,但又不單調(diào)。從表1可以看出,X型搜索算法的信噪比中等,比全搜索稍有降低,但與其他快速算法相差不多,不影響視頻的主觀質(zhì)量。ICE視頻序列主要是人物運動,背景是冰面,單調(diào)而且很相似。在這種視頻中X型搜索的信噪比稍低,但不會造成視頻的主觀質(zhì)量下降。SOCCER視頻序列較為復(fù)雜,人物的運動較多,背景是細(xì)節(jié)較多的草坪。從實驗數(shù)據(jù)可以看出,X型搜索的各項參數(shù)都是前列的,信噪比很高,很好地保留了視頻的細(xì)節(jié)信息。

編碼時間:編碼時間是最重要的數(shù)據(jù)。在三種復(fù)雜程度的視頻序列編碼中,X型搜索的編碼時間都只占全搜索的40%-50%,運動估計的時間更是只占10%-15%,編碼速度穩(wěn)占第一,反應(yīng)了X型搜索良好的搜索效率,而且視頻越復(fù)雜,細(xì)節(jié)越多,優(yōu)勢越明顯。

表1.　運動估計實驗數(shù)據(jù)對比

5　結(jié)束語

本文提出的X型搜索遵循由粗到細(xì)的搜索原則,在保證視頻質(zhì)量的前提下,兼顧了搜索速度和精度,能夠大幅度去除視頻冗余信息,提高視頻的壓縮比,尤其適合運動多細(xì)節(jié)的視頻編碼,有效提高了幀間預(yù)測中運動矢量估計算法的搜索效率,為高清視頻的實時編碼提供了有力手段。

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

[2]王文芳.H.264幀間預(yù)測算法研究與FPGA設(shè)計[D].北京：北京交通大學(xué),2009.

[3]陳佳,田澤，等.H.264/AVC視頻編碼核基于FPGA驗證的設(shè)計與實現(xiàn)[J].計算機(jī)技術(shù)與發(fā)展,2013,23(7),10-13.

[4]張子敬.H.264多核DSP并行算法研究[D].連云港：江蘇自動化研究所,2013.

[5]鐘明光.H.264編碼器的研究及其部分算法的FPGA實現(xiàn)[D].西安：西安電子科技大學(xué),2013.

[6]車文斌.H.264解碼器的FPGA驗證[D].哈爾濱：哈爾濱工業(yè)大學(xué),2013.

[7]劉洋.H.264運動估計算法的研究與FPGA驗證[D].西安：西安理工大學(xué),2012.

[8]羅亮.高清視頻編解碼電路設(shè)計[D].西安：西安工業(yè)大學(xué),2015.

[9]張玢.基于FPGA的H.264視頻編碼芯片驗證平臺設(shè)計[J].渭南師范學(xué)院學(xué)報,2013，28(9)：74-77.

[10]劉杰,王旭柱.基于H.264的一種視頻編碼算法的研究與FPGA實現(xiàn)[J].中國新技術(shù)新產(chǎn)品,2014(7)：25-26.

Research of The Motion Vector Search Algorithm of H.264

ZHANG Yong-xuan,HUO Jia-dao

(Jiangsu Automation Research Institute,Lianyungang 222061,China)

HD video has large amount of message,so it’s difficult to transport.To improve the real-time transmission ability of HD video,we can use H.264 to compress it.Aiming at the problem of the serious time-consuming of H.264’s motion estimation,this paper propose a new method X-research.X-research search from widely range to details,first search for the possible range of motion estimate algorithm with X form,then search completely in partition.Considering of both sufficiency and precision,then fix the motion estimate algorithm finally.Based on the experiment,X-research can reduce the coding time greatly,and improve the efficiency of H.264’s motion estimation effectively.It provide guarantee to HD video’s real-time transmission.

H.264; motion estimate algorithm; X-research

1673-3819(2016)05-0062-04

2016-05-18

2016-06-21

張永軒(1990-),男,江蘇連云港人，碩士研究生,研究方向為H.264視頻編碼。

霍家道(1970-)，男，博士，碩士生導(dǎo)師。

TN919.81

ADOI:10.3969/j.issn.1673-3819.2016.05.013