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

??? 關(guān)鍵詞: H.264/AVC； 運動矢量； 提前終止； 運動估計

?

??? 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)的運動估計采用了可變長宏塊和多參考幀等新的編碼模式，使運動估計的精度更高，同時也使編碼更加復(fù)雜且計算量更大。?

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

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

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

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

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

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

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

???? ???

?

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

2 搜索策略描述?

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

?

?

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

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

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

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

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

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

?

?

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

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

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

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

?

?

??? 通過分析可以得到，本文所提出的算法與FS及DS算法相比，PSNR值基本保持不變。可以得出如下結(jié)論:?

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

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

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

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

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

參考文獻(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.