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

??? 關(guān)鍵詞: H.264/AVC； 運(yùn)動矢量； 提前終止； 運(yùn)動估計(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年正式成為國際標(biāo)準(zhǔn)，同時它也成為了MPEG-4的第10部分，稱為AVC(Advanced Video Coding)。H.264標(biāo)準(zhǔn)的運(yùn)動估計(jì)采用了可變長宏塊和多參考幀等新的編碼模式，使運(yùn)動估計(jì)的精度更高，同時也使編碼更加復(fù)雜且計(jì)算量更大。?

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

1 運(yùn)動矢量預(yù)測及閥值確定?

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

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

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

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

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

???? ???

?

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

2 搜索策略描述?

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

?

?

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

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

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

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

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

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

?

?

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

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

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

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

?

?

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

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

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

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

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

??? 因此，本文使用優(yōu)化的搜索算法，PSNR值基本不變，但大大減少了搜索時間，提高了搜索效率，這對于視頻圖像的實(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.