一種基于UMHexagonS運動估計的優化算法

劉學謙，張 濤，王 贊

(天津大學 電子信息工程學院，天津300072)

責任編輯:時 雯

由JVT制定的最新視頻編碼標準H.264/AVC[1]，因其采用了很多新技術、新方法，特別是幀間預測中的可變化尺寸塊運動估計、1/4像素精度的運動估計、多參考幀的使用，所以其比以往的視頻標準有更高的編碼質量，同時也有更高的復雜性。運動估計所需要的時間占整個編碼器編碼時間的60%～80%[2]。為了提高編碼速度，研究運動估計快速算法，也非常必要。

近年來，各國學者提出多種運動估計的快速算法，在保證編碼質量基本不變的前提下，提高運動估計的效率。比如，三步法(TSS)[3]、四步法(FSS)[4]、六邊形搜索法(HEXBS)[5]、鉆石搜索法(DS)[6]、改進的預測式區域搜索算法(EPZS)[7]、非對稱十字型多層次六邊形格點搜索(UMHexagonS)算法[2]。

本文基于UMHexagonS算法，根據運動情況，使用動態搜索窗口以及自適應的搜索模板，在圖像質量和碼率沒有太大變化的情況下，降低了算法的復雜度，大大減少了運動估計的時間。

1 UMHexagonS算法描述

UMHexagonS搜索算法主要包括4個步驟[2]:

1)非對稱的十字形搜索;

2)5×5小矩形搜索;

3)非均勻多層次六邊形搜索;

4)擴展的六邊形搜索。

算法流程如圖1所示。

圖1 UMHexagonS搜索算法的步驟

在開始搜索之前，起始搜索點要根據當前塊的運動情況，在原點預測值、中值預測值(MVpred_MP)、上層預測值(MVpred_UP)、相鄰參考幀預測值(MVpred_NRP)和時域對應塊預測值(MVpred_CP)這5種預測模式中來進行選擇。搜索范圍的大小通過配置文件的search_range參數設置:search_range=16/32/48/64。在搜索的同時，UMHexagonS算法中還設定了提前終止搜索和跳轉搜索步驟的閾值，這就大大減少搜索的點數，節省了搜索時間。

2 UMHexagonS算法的優化

2.1 動態的搜索范圍

最新的編碼標準中，分塊模式不再是單一的16×16。比如H.264/AVC標準有7種分塊模式，最大塊為16×16，最小塊4×4。雖然已經引入了動態搜索范圍[8]，但是并沒有考慮到不同模式，比如會對4×4的塊增加額外的搜索。因此為了進一步優化搜索范圍，可以利用MVpred_MP和MVpred_UP來針對非16×16(該模式沒有MVpred_UP)模式，再計算一個新的搜索范圍[9]，取新的搜索范圍與以前搜索范圍中的最小值作為最后的搜索范圍。動態搜索窗口的計算方法如圖2所示。

圖2 動態搜索窗口計算方法

A是從配置文件獲得的search_range;B是計算得出的新的動態搜索范圍(new_search_range)，由C和D構成;C是固定的搜索范圍。D是動態范圍。其中，MVpred_UPX，MVpred_UPY和MVpred_MPX，MVpred_MPY分 別 是MVpred_UP，MVpred_MP的X和Y分量。C，D兩個搜索范圍的計算公式定義如下

2.2 搜索模板的改進

2.2.1 十字模板的優化

原始的十字搜索模板要搜索24個點，雖然是不對稱的模板，但在某些情況下垂直方向上發現最優點的可能性要比水平方向大，如果使用同一個模板，不利于更快找到最優點。可以根據當前的預測運動矢量MVpred的X方向與Y方向的不同，選擇以下不同的模板，如圖3所示。

模板是不對稱的小十字模板，一個步長是2，一個步長是1。如果abs(MVpred_x)＜abs(MVpred_y)選用模板2;否則選用模板1。搜索方式是:以當前點為中心，搜索周圍四個點，直到最優點為中心點，停止搜索。實驗結果顯示，采用這種方法，平均每次搜索不到5個點。

圖3 不對稱小十字模板

2.2.2 5×5小矩形搜索的改進

由于運動矢量的最優點在13點的菱形和25點的小矩形出現的概率分布是80.7%和82.6%[10]，所以本文采用了13點菱形來替代25點的小矩形，如圖4所示。

圖4 13點菱形和25點小矩形

2.3 多層次多角度自適應模板

UMHexagonS中的非均勻多層次六邊形搜索，為了有效避免陷入局部最優，每次需要檢測4×16個點。此步驟可以結合運動矢量分布的空間方向性[11]，并結合MVpred_MP來簡化搜索模板的層數。具體方法如下:

1)當Num_Big_Hexagon≥4時

如果Mv_Big_Hexagon≥12，則修改Num_Big_Hexagon=4;

如果8≤Mv_Big_Hexagon＜12，則修改Num_Big_Hexagon=3;

其他情況，則修改Num_Big_Hexagon=2。

2)當3≤Num_Big_Hexagon＜4時

如果Mv_Big_Hexagon≥8，則修改Num_Big_Hexagon=3;

如果6≤Mv_Big_Hexagon＜8，則修改Num_Big_Hexagon=2;

其他情況，則修改Num_Big_Hexagon=1。

3)當2≤Num_Big_Hexagon＜3時

如果Mv_Big_Hexagon≥6，則修改Num_Big_Hexagon=2;

其他情況，則修改Num_Big_Hexagon=1。

4)當Num_Big_Hexagon≤1時

Num_Big_Hexagon=1。

其中，Mv_Big_Hexagon是MVpred_MP中X方向和Y方向的最大值;Num_Big_Hexagon為最后的搜索層次數，1即為圖5的單層，2即為在單層的基礎上，再向外擴展一層，搜索點坐標為單層的2倍，3層、4層以此類推;Num_Big_Hexagon=new_search_range/4。

經過以上幾步搜索后，可以利用當前獲得的最佳運動矢量與上一幀對應位置塊的運動矢量的偏離方向，確定自適應模板的搜索方向，既減少了搜索點數，又能準確地避免陷入局部最優。搜索方向的角度在第一/三象限，使用12，13，14，15，0，4，5，6，7，8十點構成的模板;角度在第二/四象限，使用0，1，2，3，4，8，9，10，11，12十點構成的模板;X軸方向，即X軸方向不為0，Y軸方向為0使用2，4，6，10，12，14六點構成的模板;Y軸方向，使用1，5，0，1，7，8，9六點構成的模板。模板的示意圖如圖5所示。

圖5 非均勻多層次六邊形搜索的單層模板

3 實驗結果和分析

3.1 測試平臺和配置

本文采用H.264/AVC的JM11.0平臺進行測試。實驗所用計算機的硬件配置為:Intel(R)Core(TM)i5-2310@2.90 GHz，4 Gbyte內存，操作系統為Windows XP SP3。為了更好地評價本文算法，實驗選取幾組不同運動類型的、不同分辨率的標準測試序列，設定不同的搜索范圍，序列格式為YUV 420，編碼檔次為Baseline Profile。實驗所用到的編碼參數及測試序列如表1所示。

3.2 測試結果和分析

對于運動估計搜索算法的復雜度，可以由搜索點的個數來評價。對于16×16大小的塊在搜索范圍為16時，UMHexagonS算法的搜索點個數至少為N1=step1+step2+step3+step4=25+24+64+10=123點，而本文改進算法的搜索點個數至少為N2=step1+step2+step3+step4=5+12+6+10=34點。由上可知，本文的改進算法能有效地降低搜索點個數，相應地也極大地減少了運動估計時間，編碼時間也會減少，所以從理論上可以證明本文算法的有效性。

表1 實驗用到的測試序列

測試中將本文改進的算法與原有的UMHexagonS算法進行了對比，實驗數據如表2和表3所示，其中同一分辨率下的序列平均值就是統計表1中同一分辨率的序列測試結果的平均值作為最終測試結果。

表2 圖像運動緩慢的序列實驗結果

表3 不同分辨率不同搜索范圍的實驗結果

實驗主要是將本文算法和UMHexagonS算法在不同搜索范圍下的PSNR、碼率、編碼時間、運動估計時間等方面進行了比較。從實驗結果來看，本文算法的PSNR與UMHexagonS算法比幾乎相同，下降時的幅度也都在0.02 dB以內;本文算法的碼率與UMHexagonS算法比，幅度變化不大;從表2可以看出，本文算法在簡化運動估計方面有很大的優勢，特別是對圖像運動劇烈的序列，效果尤為明顯。一般情況下，本文算法在PSNR和碼率變化不大的同時，QCIF分辨率搜索范圍設置為32，平均可節省32.64%的運動估計時間;由表3可知，隨著搜索范圍的擴大，本文算法在運動估計時間上優勢就越明顯，有時都能節省47.05%。

4 小結

視頻編碼系統在有效提高編碼質量的同時，也提高了其復雜性。本文對運動估計的UMHexagonS算法進行了研究和分析，對不同搜索模式下的動態搜索范圍進行了改進，用自適應不對稱小十字模板替代原有的十字模板，用小菱形替代原有的小矩形搜索，又提出多層次多角度的自適應六邊形模板，并對小菱形搜索進行了簡化，這在一定程度上減少了搜索點數。從實驗結果可以看出，本文提出的新算法，在保證圖像質量和碼率基本不變的前提下，編碼時間和運動估計時間都有不同程度的減少，特別是對運動較劇烈的序列有更好的效果，并且搜索范圍越大，本文算法在運動估計時間上的優勢就越明顯。

[1]WIEGAND T，SULLIVAN G，LUTHRA A.Overview of the H.264/AVC video coding standard[J].IEEE Trans.Circuits and System for Video Technology，2003，13(7):560-576.

[2]CHEN Zhibo，XU Jianfeng，HE Yun，et al.Fast integer-pel and fractionalpel motion estimation for H.264/AVC[J].Journal of Visual Communication and Image Representation，2006，17(2):264-290.

[3]KOGA T，IINUMA K，HIRANO A，et al.Motion compensated interframe coding for video conferencing[EB/OL].[2013-05-02].http://citeseer.uark.edu:8080/citeseerx/showciting;jsessionid=228570CE9CB7B FDA1E15A138A877B06C?cid=20547.

[4]PO L，MA W.A novel four-step search algorithm for fast block motion estimation[J].IEEE Trans.Circuits and Systems for Video Technology，1996，6(3):313-317.

[5]ZHU C，LIN X，CHAU L.Hexagon-based search patten for fast block motion estimation[J].IEEE Trans.Circuits and Systems for Video Technology，2002，12(5):349-355.

[6]ZHU Shan，MA Kaikuang.A new diamond search algorithm for fast block matching motion estimation[J].IEEE Trans.Image Processing，1997，9(2):292-296.

[7]TOURAPIS A，AU O，LIOU M.New results on zonal based motion estimation algorithms-advanced predictive diamond zonal search[C]//Proc.ISCAS 2001.Sydney，NSW:IEEE Press，2001:183-186.

[8]XU Xiaozhong，HE Yun.Modification of dynamic search range for JVT[S].2005.

[9]CHEN Z，SONG Y，IKENAGA T，et al.A dynamic search range algorithm for variable block size motion estimation in H.264/AVC[C]//Proc.6th International Conference on Information，Communications &Signal Processing.Singapore:IEEE Press，2007:1-4.

[10]LIU Haihua，XIE Changsheng，LEI Yi.An unsymmetrical dual cross search algorithm for fast block-matching motion estimation[C]//Proc.ICTAI 2005.Hong Kong:IEEE Press，2005:613-620.

[11]TOURAPIS A，AU O，LIOU M.Predictive motion vector field adaptive search technique(PMVFAST)enhancing block based motion estimation[C]//Proc.VCIP 2001.San Josc，CA:IEEE Press，2001:24-26.