張永軒,霍家道

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

?

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

張永軒,霍家道

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

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

H.264;運(yùn)動(dòng)估計(jì);X型搜索

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

1　H.264運(yùn)動(dòng)估計(jì)幾種核心算法介紹

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

1.1全局搜索算法

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

1.2三步搜索算法(TTS)

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

圖1　三步搜索算法

1.3菱形搜索算法

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

圖2　菱形搜索算法

2　改進(jìn)的運(yùn)動(dòng)估計(jì)算法

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

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

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

2.1對(duì)角線式快速搜索確定運(yùn)動(dòng)矢量范圍

圖3　物體斜方向運(yùn)動(dòng)匹配搜索示意圖

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

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

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

2.3X型搜索算法

綜合針對(duì)兩個(gè)問(wèn)題的解決方法,本文提出一種新的運(yùn)動(dòng)矢量搜索算法——X型搜索算法。具體步驟如圖5所示。

圖5　X型搜索算法

主要步驟:

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

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

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

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

3　運(yùn)動(dòng)估計(jì)算法匹配準(zhǔn)則

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

(1)

(2)

(3)

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

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

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

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

圖6　Foreman成像對(duì)比

圖7　ICE成像對(duì)比

圖8　SOCCER成像對(duì)比

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

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

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

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

表1.　運(yùn)動(dòng)估計(jì)實(shí)驗(yàn)數(shù)據(jù)對(duì)比

5　結(jié)束語(yǔ)

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

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

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

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

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

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

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

[7]劉洋.H.264運(yùn)動(dòng)估計(jì)算法的研究與FPGA驗(yàn)證[D].西安：西安理工大學(xué),2012.

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

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

[10]劉杰,王旭柱.基于H.264的一種視頻編碼算法的研究與FPGA實(shí)現(xiàn)[J].中國(guó)新技術(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-),男,江蘇連云港人，碩士研究生,研究方向?yàn)镠.264視頻編碼。

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

TN919.81

ADOI:10.3969/j.issn.1673-3819.2016.05.013