基于EPZS的運動估計算法的改進

孫繼穩　葉水生　陳敏力　張才軍　王萬兵

摘 要：在H.264標準的視頻壓縮編碼中，運動估計和運動補償技術是編碼系統中最為重要的組成部分之一。但是運動估計的計算量非常大，極大地降低了編碼的實時性。為了降低運動估計的時間，提高編碼的效率，在充分研究EPZS算法的基礎上，對EPZS算法進行終止搜索條件和搜索模板進行改進優化。實驗結果表明，在不降低圖像質量的前提下，優化后的算法相比原來的算法，降低了編碼時間損耗，提高了編碼效率。

關鍵詞：視頻壓縮編碼；運動估計；EPZS；搜索模板

中圖分類號：TN911 文獻標識碼：A 文章編號：2095-1302（2015）04-00-02

0 引 言

目前，H.264標準的視頻編解碼受到了廣泛地應用，它的編碼效率很高，但是運動估計作為編碼的核心，其計算量也相當復雜，這就增加了時間損耗，嚴重降低了視頻編解碼的效率。近年來，運動估計一直被作為研究熱點。

在各種視頻編碼標準中，塊匹配運動估計算法是應用最廣泛的。全局算法（FS）能得到最佳的運動矢量，但是計算量很大，嚴重降低了編碼的實時性。為了減少算法的復雜度，很多算法被提出來，其中包括三步法[1]、四步法[2]、MVFAST[3]等經典算法。而EPZS（預測區域的搜索算法）是一種被JM模型采用的整像素運動搜索算法，它由局部逐漸向最佳點靠近，對于搜索范圍較大的、運動很激烈的對象的搜索容易過早陷入局部最優[4]。

在充分分析EPZS算法的基礎上，針對基于六邊形改進的EPZS算法搜索精度不高，搜索點數多的特點[5]，提出了對EPZS終止搜索的條件以及搜索模板進行改進，改進優化后的算法搜索方向細化，精度更高，減少了搜索點數，降低了算法的復雜度，有效節省了運動估計的時間，增強了編碼的實時性。

1 EPZS算法的介紹以及存在的不足

EPZS搜索算法利用視頻運動的空間和時間相關項，對當前編碼的運動矢量進行預測，提出一種相鄰塊失真的提前終止準則來提前終止搜索[6]，進一步來提高搜索速度，減少編碼的復雜度。對于那些不能提前進行終止搜索的，利用搜索模板來進行相關運動矢量地完善。

1.1 計算提前終止搜索條件的不足

EPZS根據相鄰塊的失真具有很高的相似度，而提出了一種基于相鄰塊失真的提前終止準則。通過提前終止準則，減少了算法的計算復雜度。在EPZS算法中，通過當前塊A的左側塊B、正上方塊C、右上方塊D三個相鄰塊的最小SAD值來計算終止條件的標準[7]（分別記為SADB、SADC、SADD）。由此可知，EPZS計算終止搜索的條件過于簡單，對于大多數情況計算出來的搜索終止條件是滿足的，但沒有考慮到運動較小或者靜止情況下，這三個SAD的值非常接近[8]，由此可知，這樣計算出來的SAD不一定是準確的。

1.2 EPZS的搜索模板的不足

改進后的EPZS算法，搜索點數過多，對于運動較為復雜的運動場合，容易陷入局部最優而提前進入終止搜索，這樣就會產生更大的誤差。

2 改進后的EPZS算法

對EPZS算法的優化主要是針對其在計算終止搜索條件和搜索模板方面地優化，通過終止搜索閾值T0地設定和不同的搜索模板方法來對當前塊在不同的范圍內進行搜索，直至搜索到最佳點，得到最佳運動矢量。

2.1 搜索終止條件的優化

我們將起始搜索點的SAD值記為SADM，由于起始預測搜索點最接近于最佳點，SAD的值和SADM的值相關性越大，我們可以更快地利用終止搜索的條件來得到最佳的SAD值，我們設定終止搜索的閾值為T0，如下公式所示：

T0=min（SADM，SADB，SADC，SADD）

2.2 精細搜索模板的改進

通過研究各種搜索模板，我們可以發現搜索模板越是接近圓形，其搜索性能越好[9]，因為圓形的方向覆蓋全，搜索范圍更精確，更容易讓我們找到最佳點，從而得到最佳運動矢量，而這里十二邊形無限接近于圓形，它共有13個點分別為（0，0）、（1，4）、（3，3）、（4，1）、（4，-1）、（3，-3）、（1，-4）、（-1，-4）、（-3，-3）、（-4，-1）、（-4，1）、（-3，3）、（-1，4），搜索中心點和外圍的12個不同方向的點，求得最佳點，判斷搜索到的點是不是最佳點，如不是以此點為中心進行非對稱十字形搜索，判斷是否為最佳點，直到最佳點為中心點，此時的向量為最佳運動矢量MV。利用十二邊形進行最佳點方向的判斷搜索，方向覆蓋更全面，減少了搜索點數，能夠很快很好地得到最佳點，從而得到最佳運動矢量。

這里采用小菱形搜索模板[10]、非對稱十字形搜索模板和（類圓形）十二邊形的搜索模板。

在初始化搜索點后，對塊類型進行判別來選擇相應的模板進行搜索最佳點，然后進行閾值判斷來判別是否終止搜索。算法的搜索步驟和流程如圖2所示。

算法的搜索步驟如下：

（1）判斷當前塊是否是靜止塊，若是靜止塊直接跳入步驟（5），否則進入步驟（2）。

（2）判斷當前塊是小運動塊還是大運動塊，如果當前塊為小運動塊，即運動平緩，則進入步驟（3），否則進入步驟（4）。

（3）當前塊為小運動塊，對其進行小鉆石形模板搜索，直到SAD小于閾值T0，得到最佳運動矢量。

（4）當前塊為大運動塊，即運動比較激烈，此時應該先進行初始搜索點預測，然后對其進行十二邊形模板搜索，對得到的SAD進行分析，是否為最佳點，若為最佳點，則對其進行小鉆石形模板搜索，直到得到最佳運動矢量；若不是最佳點則對其進行非對稱十字形搜索，然后再次判斷是否為最佳點，若不是則一直進行非對稱十字形搜索，直到得到SAD最佳點，然后再對其最佳點進行小鉆石型搜索，直到SAD小于閾值T0，得到最佳運動矢量。

（5）搜索結束。

本文是以H.264官方的標準測試模型JM 10.1為平臺，在此基礎上對改進算法進行測試的實驗。優化后的算法和基于六邊形改進的EPZS算法相比較，在不影響圖像質量的前提下，運動估計的時間明顯減少，搜索效率明顯提高。

3 結 語

本文基于EPZS（預測區域的搜索算法）來展開分析和討論，充分利用圖像運動的空間域和時間域的相關特性，利用初始預測矢量和閾值終止標準來進行相關運動矢量地求解。改進后的算法在搜索中使用小鉆石形、非對稱十字形以及十二邊形等搜索模板，在保證圖像恢復質量不變的情況下，運動估計時間明顯減少，特別是對運動對象較為劇烈的場合有顯著的效果，編碼效率有了顯著地提高，提高了視頻運動序列編碼的實時性，具有一定的實用價值。

參考文獻

[1]陳靖，劉京，曹喜信.深入理解視頻編解碼技術——基于H.264標準及參考模型[M].北京：北京航空航天大學出版社，2012.

[2] ITU-T.H.264，ITU-T rec advanced video coding for generic audio visual [S].2012.

[3] SHI Z，FERNANDO W A C，KONDOZ A.An efficient fast motion estimation in H.264/AVC by exploiting motion correlation character[C]//Proceedings of the 2012 IEEE International Conference on Computer Science and Automation Engineering. Piscataway：IEEE Press，2012（3）： 298-302.

[4] Lakshman H，Schwarz H，Wiegand T.Adaptive motion model selection using a cubic spline based estimation framework[C]//2010 IEEE International Conference on Image Processing.[S.l.]：IEEE Press，2010：805-808.

[5]田東坡，鮑可進.基于EPZS的H.264/AVC運動估計改進算法[J].計算機應用研究，2010，27（7）：2795-2797.

[6] Cai C，Zeng H，Mitra S.Fast motion estimation for H.264[J].Signal Processing：Image Communication，2009，24（8）：630-636.

[7]丁鑫，樊慧津.基于方向自適應的運動估計混合模板搜索算法[J].中國圖象圖形學報，2011，16（1）：14-20.

[8] Zhang K，Zhang L，Song H，et al.Active contours with se-lective local or global segmentation：a new formulationand level set method[J].Image and Vision Computing，2010（28）：668-676.

[9] Masala E， Vesco A， Baldi M， et al. Optimized H.264 Video Encoding and Packetization for Video Transmission Over Pipeline Forwarding Networks[J]. IEEE Transactions on Multimedia， 2009， 11（5）：972-985.

[10] Zhuo Z，Ping L.An efficient parallel architecture for H.264/AVC fractional motion estimation[C]//Intelligent Interactive Multimedia Systems and Services Smart Innovation，Systems and Technologies.[S.l.]：Springer，2011（11）：133-141.

[11] 李軍，周曉慧，葉文龍.基于運動估計 EPZS 算法的優化[J].機電工程，2011， 28（6）：736-738.