AVS的自適應提前終止運動估計算法

王園園，張 剛，李付江

(太原理工大學信息工程學院，山西 太原 030024)

責任編輯:哈宏疆

AVS(Advanced Video Standard)標準［1］，是我國自主研發的視頻壓縮標準。AVS視頻編碼主要包括運動估計、DCT變換、量化、掃描、熵編碼等模塊。由于運動估計采用了高精度的運動矢量，使得運算量大幅增加，因此，縮短運動估計時間是提高AVS視頻編碼實時性的重要內容。運動估計研究主要分兩個方向:一是整像素運動估計［2-4］，參考文獻［5］中根據中心偏移特性提出了在起始搜索點預測中加入原點預測;另一個是亞像素運動估計［1］。本文針對UMHexagonS搜索算法提出了搜索的提前終止判斷以及SAD計算的提前結束條件判斷，提高了最佳匹配塊的搜索速度;在模式選擇中提出了代價值的提前比較，有效減小了搜索量。

1 AVS運動估計過程

在視頻編碼中，幀間預測編碼就是找出每個編碼塊在鄰近幀中的位置，并得到兩者空間位置的相對偏移量即運動矢量。運動估計就是得到運動矢量的過程［6］。在AVS標準中幀間預測模式有5種:skip模式、16×16模式、16×8模式、8×16模式和8×8模式。運動估計過程分為運動搜索和模式選擇兩個步驟。

AVS的運動搜索主要是基于塊的搜索，在搜索算法中，經典的UMHexagonS搜索算法是通過多種搜索模型的混合使用［7］，得到比較準確的最佳匹配塊，運算量也相對較小。每種搜索模型搜索得到的SAD的最小值記為min_sad，SAD閾值的上限和下限記為threshold1和threshold2。UMHexagonS搜索算法主要流程如圖1所示。

除skip預測模式外，每種預測模式通過運動搜索得到最佳匹配塊后，按16×16模式、8×8模式、16×8模式和8×16模式順序分別得到各種模式的代價值，逐一進行比較，代價取值最小的預測模式即為當前塊的最佳預測模式。

2 運動估計算法優化

2.1 運動估計分析

經過深入的研究發現，UMHexagonS搜索算法和模式選擇仍存在以下4點不足:

1)SAD閾值是固定的，使得運動劇烈的視頻序列過早終止搜索，運動緩慢的視頻序列不能很好地提前結束搜索。

圖1 UMHexagonS搜索算法流程圖

2)經測試發現，視頻序列中靜止塊的SAD值小于SAD閾值下限的約有98%。此值通常是參考幀的搜索區域中候選搜索起始點(0，0)所對應的塊計算得到，候選搜索起始點之后的搜索有些多余。

3)據統計約有80%的搜索塊，當計算了塊中約50%像素點數時，累加值就已經大于已有最小SAD值，塊中另外50%像素點的計算是多余的。

4)模式選擇時，靜止或者運動緩慢的塊，通常選擇16×16模式。算法中先是計算16×16預測模式的代價值me16x16.cost。然后，無條件的計算8×8模式4個塊代價值的累加和i_cost8x8。實際1個8×8塊的代價值已經大于me16x16.cost，所以，多余計算了其余3個8×8塊的代價值。

2.2 運動估計優化

本文根據前文提到的幾點不足，提出以下4個方面的優化:

1)自適應地選擇SAD閾值。UMHexagonS搜索算法中SAD閾值是固定的，其中16×16預測模式的SAD閾值threshold1和threshold2分別為2000和500。以16×16模式為基準，得到16×8預測模式和8×16預測模式SAD的閾值threshold1＞＞1和threshold2＞＞1，8×8預測模式SAD的閾值為threshold1＞＞2和threshold2＞＞2。本文提出了以下改進方法:根據物體運動的空間和時間相關性，當前塊的最佳匹配塊的SAD值和候選搜索起始點對應塊所得到的SAD值密切相關。所以，SAD閾值的設定可以根據候選搜索起始點得到的SAD值來確定。因此，SAD閾值的設定如下:

根據16×8模式、8×16模式和8×8模式的SAD閾值與16×16模式閾值的關系得到如下3個數組:

(1)data500［4］={500，250，250，125};

(2)data1000［4］={1000，500，500，250};

(3)data2000［4］={2000，1000，1000，500}。

其中，data500［4］表示4種預測模式閾值下限的最小取值;data1000［4］表示4種預測模式閾值下限的最大取值以及上限和下限的差值;data2000［4］表示4種預測模式閾值上限的最大取值。

通過候選搜索起始點得到的SAD的最小值記為min_sad。自適應選擇SAD閾值的流程如圖2所示。其中，4種預測模式 i_pixel取值分別為 0，1，2，3。該方法可使每種預測模式的閾值上限和下限都不再是固定值，而是存在一定的取值范圍。采用上述自適應的SAD閾值，能有效地減少搜索點數，更快地搜索到最優點，使得計算量大大降低。

圖2 自適應選擇SAD閾值流程圖

2)搜索提前終止判斷。經候選起始點得到自適應SAD閾值上限threshold1和下限threshold2后加入條件判斷語句“if(sad＜threshold2)”，滿足條件則提前終止搜索。在不影響視頻質量的前提下，可以平均減少24～36個搜索點的計算量。

3)SAD計算的優化。UMHexagonS搜索算法中每一種搜索模型都是通過一定的宏定義函數實現的。宏定義中用的SAD值計算函數的主要代碼如下:

針對4 種預測模式(lx，ly)分別為(16，16)，(16，8)，(8，16)和(8，8)。將SAD值比較提前放入SAD計算函數中，每累加一個絕對差值進行一次“if(sum ＞=bcost)”比較，如果滿足條件則跳出循環，提前結束計算，可以節省m－count次循環的計算量。

4)模式選擇的提前結束判斷。在幀間模式選擇時，在函數xavs_mb_analyse_inter_p8x8()中每累加一個8×8塊的代價執行一次條件判斷“if(a-＞l0.i_cost8x8＞=a-＞l0.me16x16.cost)”，如果已有8×8代價值不小于16×16預測模式的代價值，則可以提前結束對代價值的計算，便可省去對其余8×8塊的運動搜索和代價值計算。這種優化算法對靜止或運動緩慢的視頻序列改善較為明顯。

3 實驗結果與分析

實驗分別從峰值信噪比(PSNR)、碼率(BR)和幀率(FR)3個方面將優化后算法和優化前算法進行了比較。主要參數設置:參考幀為1幀，I幀的QP設為28，編碼序列為IPPP格式，其中P幀預測模式不包括幀內預測模式。本實驗測試了不同格式(QCIF，CIF，D1)和不同運動劇烈程度(如運動幅度較小的bridge序列，運動幅度中等的coastguard序列，運動幅度較大的football序列)的經典測試序列在不同QP(28，30)下的峰值信噪比、碼率和幀率的變化。實驗數據見表1～表6。

表1 QP=28時QCIF格式的實驗結果

表2 QP=30時QCIF格式的實驗結果

表3 QP=28時CIF格式的實驗結果

表4 QP=30時CIF格式的實驗結果

表5 QP=28時D1格式的實驗結果

表6 QP=30時D1格式的實驗結果

實驗結果中前兩項數據均為:變化率 =(優化后-優化前 )/優化前×100%，其中“-”號表示降低，“+”號表示增加，對于信噪比“+”號表示視頻質量得到提高，而對于碼率“-”號表示壓縮率越大。由測試結果可以看出，所有測試序列信噪比降低不超出0.3%，碼率增加不超出0.4%，幀率都有了明顯提高，并且針對同一種格式的序列，QP越小時幀率提高越大。另外，部分測試序列的信噪比有所增加，也有部分測試序列碼率有所減小?？傮w來看，在峰值信噪比和碼率變化不明顯的情況下，幀率平均提高1.4倍，更好地滿足了視頻壓縮編碼的實時性要求。

4 小結

本文通過對AVS編碼器中整像素運動估計算法的深入研究和分析，分別針對運動搜索的UMHexagonS搜索算法和模式選擇在SAD閾值選擇、搜索的終止判斷、SAD計算和代價值比較幾方面進行了改進。實驗表明，對于不同格式和量化參數的測試序列，在峰值信噪比和碼率基本不變的情況下，編碼速度大幅度提高，增強了編碼器的實時性，更有利于視頻的實時編碼傳輸。

［1］周波，王力波，劉東華，等.用于AVS視頻編碼的快速子像素運動搜索算法［J］.計算機應用研究，2008，25(7):2238-2240.

［2］劉易，李太君.H.264中快速運動估計UMHexagonS算法的改進［J］.計算機技術與應用，2011，37(8):128-130.

［3］ZHU Shang，MA Kaikuang.A new diamond search algorithm for fast block-matching motion estimation［J］.IEEE Trans.Image Processing，2000，9(2):287-290.

［4］王超，于洪珍，厲丹，等.帶有閥值的自適應混合搜索算法的設計與實現［J］.計算機工程與設計，2010，31(9):1968-1970.

［5］楊齊，李子印.一種改進的UMHexagonS運動估計算法［J］.電視技術，2012，36(5):15-17.

［6］畢厚杰.視頻壓縮編碼標準——H.264/AVC［M］.北京:人民郵電出版社，2005.

［7］黃春慶，邱曉彬.基于x264的快速運動估計算法優化［J］.控制工程，2010，17(6):820-823.