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

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

?

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

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

1 運動矢量預測及閥值確定?

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

??? 因此，可設一個閥值T，當運動矢量的值小于T時，認為當前塊為靜止塊或者準靜止塊，可用小交叉型搜索法直接進行精確定位，找出最優點；當運動矢量的值大于T時，認為是運動塊，可用大六邊形搜索算法找出最優點。?

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

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

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

???? ???

?

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

2 搜索策略描述?

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

?

?

??? (1) 設定當前塊的預測運動矢量和起始搜索點，并判斷相鄰塊間的相關性。?

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

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

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

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

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

?

?

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

3 系統仿真與結果分析?

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

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

?

?

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

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

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

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

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

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

參考文獻?

[1]?畢厚杰.新一代視頻壓縮標準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數字圖像編碼.北京：機械工業出版社，2004.