??? 摘??要： 提出了一種基于H.264/AVC的快速運(yùn)動(dòng)算法。根據(jù)運(yùn)動(dòng)矢量的時(shí)空相關(guān)性建立一個(gè)預(yù)測(cè)運(yùn)動(dòng)矢量集合，再采用小交叉（SCSA）模板和大六邊形（LHSP）搜索進(jìn)行搜索,。在搜索過(guò)程中采用提前終止技術(shù),，進(jìn)一步減少計(jì)算量。實(shí)驗(yàn)結(jié)果和分析表明,，該算法能夠顯著提高運(yùn)動(dòng)估計(jì)的搜索速度，節(jié)省了大量運(yùn)動(dòng)估計(jì)時(shí)間，而圖像質(zhì)量和比特率只有少量變化,。?

??? 關(guān)鍵詞: H.264/AVC； 運(yùn)動(dòng)矢量,； 提前終止,； 運(yùn)動(dòng)估計(jì)

?

??? H．264/AVC 視頻編碼標(biāo)準(zhǔn)是ISO／IEC MPEG聯(lián)合ITU-T VCEG成立的聯(lián)合視頻組JVT(Joint Video Team)制定的視頻編碼新標(biāo)準(zhǔn)。該標(biāo)準(zhǔn)在2003年正式成為國(guó)際標(biāo)準(zhǔn),，同時(shí)它也成為了MPEG-4的第10部分,，稱為AVC(Advanced Video Coding)。H.264標(biāo)準(zhǔn)的運(yùn)動(dòng)估計(jì)采用了可變長(zhǎng)宏塊和多參考幀等新的編碼模式,，使運(yùn)動(dòng)估計(jì)的精度更高,，同時(shí)也使編碼更加復(fù)雜且計(jì)算量更大。?

??? 在H.264編碼中,，運(yùn)動(dòng)估計(jì)和運(yùn)動(dòng)補(bǔ)償占用了70％以上的編碼時(shí)間,。因此在進(jìn)行H.264優(yōu)化時(shí),，先要考慮的問(wèn)題就是在保證視頻質(zhì)量不顯著下降的情況下，采用高效快速的運(yùn)動(dòng)估計(jì)算法,，盡量提高運(yùn)動(dòng)估計(jì)的搜索速度,，減少編碼的復(fù)雜度。?

1 運(yùn)動(dòng)矢量預(yù)測(cè)及閥值確定?

??? 實(shí)際中絕大部分視頻圖像的運(yùn)動(dòng)都很小,。統(tǒng)計(jì)學(xué)的結(jié)論表明,，在視頻會(huì)議、視頻電話中的視頻圖像序列,，運(yùn)動(dòng)矢量通常都高度集中在零矢量及其附近,，稱為中心偏移性，即大部分運(yùn)動(dòng)矢量為零矢量或運(yùn)動(dòng)很小的矢量,。對(duì)運(yùn)動(dòng)矢量為零的塊在這里稱其為靜止塊,；運(yùn)動(dòng)矢量很小的塊（以搜索窗口中心為圓心，兩像素為半徑的圓內(nèi)）稱其為準(zhǔn)靜止塊,；而其他的塊稱為運(yùn)動(dòng)塊,。如果有超過(guò)80%運(yùn)動(dòng)矢量很小的塊可被看作靜止或準(zhǔn)靜止塊。?

??? 因此,，可設(shè)一個(gè)閥值T,，當(dāng)運(yùn)動(dòng)矢量的值小于T時(shí)，認(rèn)為當(dāng)前塊為靜止塊或者準(zhǔn)靜止塊,，可用小交叉型搜索法直接進(jìn)行精確定位,，找出最優(yōu)點(diǎn)；當(dāng)運(yùn)動(dòng)矢量的值大于T時(shí),，認(rèn)為是運(yùn)動(dòng)塊,，可用大六邊形搜索算法找出最優(yōu)點(diǎn)。?

??? 由于一個(gè)運(yùn)動(dòng)物體會(huì)覆蓋多個(gè)分塊,，所以空間域相鄰塊的運(yùn)動(dòng)矢量具有很強(qiáng)的相關(guān)性,。同時(shí)由于運(yùn)動(dòng)物體運(yùn)動(dòng)具有連續(xù)性，運(yùn)動(dòng)矢量在時(shí)間域也存在一定的相關(guān)性,，因此可以用鄰近參考幀的運(yùn)動(dòng)矢量來(lái)預(yù)測(cè),。運(yùn)動(dòng)矢量空間域的預(yù)測(cè)方式有運(yùn)動(dòng)矢量中值預(yù)測(cè)（Median Prediction）、空間域的上層塊模式運(yùn)動(dòng)矢量（Uplayer Prediction）兩種^[2],。運(yùn)動(dòng)矢量在時(shí)間域的預(yù)測(cè)方式有前幀對(duì)應(yīng)塊運(yùn)動(dòng)矢量預(yù)測(cè)和時(shí)間域的鄰近參考幀運(yùn)動(dòng)矢量預(yù)測(cè)兩種,。?

??? 為了便于尋找匹配塊的運(yùn)動(dòng)矢量，減少計(jì)算復(fù)雜度,，本文采用運(yùn)動(dòng)矢量中值預(yù)測(cè)方式,。根據(jù)與當(dāng)前塊E相鄰的左邊塊A，上邊塊B和右上邊塊C的運(yùn)動(dòng)矢量,，取其中值作為當(dāng)前塊的預(yù)測(cè)運(yùn)動(dòng)矢量,。把預(yù)測(cè)運(yùn)動(dòng)矢量作為運(yùn)動(dòng)估計(jì)的初始搜索位置,。?

　　圖1和圖2中，設(shè)E為當(dāng)前要編碼的塊,，E的運(yùn)動(dòng)矢量為MVp。如果運(yùn)動(dòng)矢量的值MVp≤T,，則認(rèn)為與E塊相鄰的各塊(子塊)間運(yùn)動(dòng)的相關(guān)性較高,，表明該區(qū)域的變化比較平緩。如果運(yùn)動(dòng)矢量的值MVp>T,，則認(rèn)為與E塊相鄰的各塊間運(yùn)動(dòng)的相關(guān)性較低,，表明該區(qū)域變化比較劇烈。?

???? ???

?

??? 通過(guò)對(duì)foreman,、football,、bridge、highway等序列的多次測(cè)試,，可取閥值T=2作為衡量當(dāng)前塊是靜止塊,、準(zhǔn)靜止塊還是運(yùn)動(dòng)塊的判斷及搜索算法選擇的依據(jù)。?

2 搜索策略描述?

??? 根據(jù)預(yù)測(cè)的運(yùn)動(dòng)矢量和相鄰塊間的運(yùn)動(dòng)相關(guān)性的不同(閥值T的不同),，采用兩個(gè)不同的模板,，分別為小交叉^[3]搜索模板SCSA(Small Cross Search Algorithm）和大六邊形^[4]搜索模板LHSP(Large Hexagon Search Pattern),如圖3所示。SCSA搜索模板以起始搜索點(diǎn)為中心,，并由4個(gè)周圍點(diǎn)組成,，如果計(jì)算的最小值點(diǎn)為中心點(diǎn)，則停止搜索,，中心點(diǎn)即為最終的運(yùn)動(dòng)矢量,。如果最小值點(diǎn)在邊緣上，則以該最小值點(diǎn)為中心,，和其相鄰的4個(gè)周圍點(diǎn)進(jìn)行下一次的搜索計(jì)算,，直到最小值點(diǎn)為中心點(diǎn)。同時(shí),，由于H.264采用的是多種塊劃分的模式,，可以根據(jù)塊的不同形狀和大小采用不同的步長(zhǎng)。其搜索步驟如下：?

?

?

??? (1) 設(shè)定當(dāng)前塊的預(yù)測(cè)運(yùn)動(dòng)矢量和起始搜索點(diǎn),，并判斷相鄰塊間的相關(guān)性,。?

??? (2) 如果相鄰塊間的運(yùn)動(dòng)相關(guān)性較高，預(yù)測(cè)的運(yùn)動(dòng)矢量值較小或?yàn)榱?，則轉(zhuǎn)入(5),；否則，進(jìn)入(3),。?

??? (3)利用LHSP模板進(jìn)行搜索,，計(jì)算7個(gè)點(diǎn)的SAD值,，同時(shí)利用排除準(zhǔn)則進(jìn)行條件判斷。如果最小值MBD為中心點(diǎn),，則轉(zhuǎn)到(4),，否則重復(fù)(3)。?

??? (4) 以中心點(diǎn)周圍的上,、下,、左、右4個(gè)點(diǎn)組成1個(gè)小的菱形,，計(jì)算5個(gè)點(diǎn)的SAD值,，同時(shí)利用排除準(zhǔn)則進(jìn)行條件判斷。SAD值最小的點(diǎn)即為最終的運(yùn)動(dòng)矢量,。?

??? (5)利用SCSA模板進(jìn)行搜索,，計(jì)算5個(gè)點(diǎn)的SAD值，重復(fù)點(diǎn)將不再計(jì)算,，同時(shí)利用排除準(zhǔn)則進(jìn)行條件判斷,。如果最小值MBD為中心點(diǎn)，該點(diǎn)對(duì)應(yīng)的運(yùn)動(dòng)矢量即為最終的運(yùn)動(dòng)矢量,；如果最小值點(diǎn)為邊緣點(diǎn),，重復(fù)(5)。?

??? 根據(jù)前面的分析方法和搜索步驟,，可以得出此搜索算法的搜索框圖,，如圖4所示。 ?

?

?

??? 改進(jìn)后的算法大大減少了對(duì)于那些運(yùn)動(dòng)矢量為零的塊的搜索冗余,，同時(shí)對(duì)于運(yùn)動(dòng)比較緩慢的塊直接進(jìn)入小范圍搜索,。這樣既提高了搜索效率，又不會(huì)使搜索結(jié)果只找到局部最優(yōu)點(diǎn),。由于采用了中止判別技術(shù),，因此可大大降低搜索的復(fù)雜度，提高了搜索的效率,，降低了搜索的成本,。?

3 系統(tǒng)仿真與結(jié)果分析?

??? 利用本文提出的算法，使用JM86進(jìn)行仿真實(shí)驗(yàn)^[5],，分別在搜索點(diǎn)數(shù),、峰值信噪比(YUV分量)、比特率等幾個(gè)方面與FS,、DS進(jìn)行對(duì)比,。仿真實(shí)驗(yàn)中采用大運(yùn)動(dòng)序列football。?

??? 由于在量化和反量化過(guò)程中,，量化參數(shù)QP決定了量化器的編碼壓縮率及圖像精度,。如果QP比較大,，則量化值FQ的動(dòng)態(tài)范圍較小，其相應(yīng)的編碼長(zhǎng)度也較小,，但反量化時(shí)損失較多的圖像細(xì)節(jié)信息;如果QP比較小,，則FQ的動(dòng)態(tài)范圍較大，相應(yīng)的編碼長(zhǎng)度也較大,，但圖像細(xì)節(jié)信息損失較少,。H.264中，量化步長(zhǎng)Qstep共有52個(gè)值,，在仿真實(shí)驗(yàn)中，取QP=5,、QP=11(量化參數(shù)每增加6,，則量化步長(zhǎng)增加一倍)、QP=29進(jìn)行同一序列取不同的QP值(為減少仿真實(shí)驗(yàn)的計(jì)算量,，測(cè)試序列只取前90幀),其結(jié)果分別如表1,、表2、表3所示,。?

?

?

??? 通過(guò)分析可以得到,，本文所提出的算法與FS及DS算法相比，PSNR值基本保持不變,?？梢缘贸鋈缦陆Y(jié)論:?

??? (1)在搜索點(diǎn)數(shù)上大大優(yōu)于FS算法，只有FS算法的1.33%,，比DS算法也有很大的改進(jìn),是DS算法的75.75%,。?

??? (2)對(duì)視頻圖像的PSNR值影響甚微，而對(duì)搜索效率有很大的提高,。?

??? (3)對(duì)視頻圖像的壓縮比相對(duì)DS算法差別很小,，F(xiàn)S算法的壓縮比最高。?

??? (4)不同的QP值對(duì)搜索點(diǎn)數(shù)影響不大,，但是對(duì)視頻圖像的數(shù)據(jù)率和PSNR值卻影響很大,，QP越大，PSNR越小,，同時(shí)數(shù)據(jù)率也越小,。?

??? 因此，本文使用優(yōu)化的搜索算法,，PSNR值基本不變,，但大大減少了搜索時(shí)間，提高了搜索效率,，這對(duì)于視頻圖像的實(shí)時(shí)傳輸是很有意義的,。?

參考文獻(xiàn)?

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

[2]?KURCEREN R, KARCZEWICZ M. Synchronization predictive coding for video compression. The SP Frames Design for JVT/H.26L.Proc,ICIP.2002.?

[3]?GHANBARI M. The cross-search algorithm?for motion estimation [J]. IEEE TransCommunication.1990, 38(7):950-953.?

[4]?ZHU S， MA K K.A new big hexagon search?algorithm for fast block matching motion estimation [J].IEEE Trans-Image Processing,，2000,9(2):287-290.?

[5]?丁貴廣.Visual C++6.0數(shù)字圖像編碼.北京：機(jī)械工業(yè)出版社,，2004.