孫繼穩(wěn)　葉水生　陳敏力　張才軍　王萬(wàn)兵

摘 要：在H.264標(biāo)準(zhǔn)的視頻壓縮編碼中，運(yùn)動(dòng)估計(jì)和運(yùn)動(dòng)補(bǔ)償技術(shù)是編碼系統(tǒng)中最為重要的組成部分之一。但是運(yùn)動(dòng)估計(jì)的計(jì)算量非常大，極大地降低了編碼的實(shí)時(shí)性。為了降低運(yùn)動(dòng)估計(jì)的時(shí)間，提高編碼的效率，在充分研究EPZS算法的基礎(chǔ)上，對(duì)EPZS算法進(jìn)行終止搜索條件和搜索模板進(jìn)行改進(jìn)優(yōu)化。實(shí)驗(yàn)結(jié)果表明，在不降低圖像質(zhì)量的前提下，優(yōu)化后的算法相比原來(lái)的算法，降低了編碼時(shí)間損耗，提高了編碼效率。

關(guān)鍵詞：視頻壓縮編碼；運(yùn)動(dòng)估計(jì)；EPZS；搜索模板

中圖分類號(hào)：TN911 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2095-1302（2015）04-00-02

0 引 言

目前，H.264標(biāo)準(zhǔn)的視頻編解碼受到了廣泛地應(yīng)用，它的編碼效率很高，但是運(yùn)動(dòng)估計(jì)作為編碼的核心，其計(jì)算量也相當(dāng)復(fù)雜，這就增加了時(shí)間損耗，嚴(yán)重降低了視頻編解碼的效率。近年來(lái)，運(yùn)動(dòng)估計(jì)一直被作為研究熱點(diǎn)。

在各種視頻編碼標(biāo)準(zhǔn)中，塊匹配運(yùn)動(dòng)估計(jì)算法是應(yīng)用最廣泛的。全局算法（FS）能得到最佳的運(yùn)動(dòng)矢量，但是計(jì)算量很大，嚴(yán)重降低了編碼的實(shí)時(shí)性。為了減少算法的復(fù)雜度，很多算法被提出來(lái)，其中包括三步法[1]、四步法[2]、MVFAST[3]等經(jīng)典算法。而EPZS（預(yù)測(cè)區(qū)域的搜索算法）是一種被JM模型采用的整像素運(yùn)動(dòng)搜索算法，它由局部逐漸向最佳點(diǎn)靠近，對(duì)于搜索范圍較大的、運(yùn)動(dòng)很激烈的對(duì)象的搜索容易過(guò)早陷入局部最優(yōu)[4]。

在充分分析EPZS算法的基礎(chǔ)上，針對(duì)基于六邊形改進(jìn)的EPZS算法搜索精度不高，搜索點(diǎn)數(shù)多的特點(diǎn)[5]，提出了對(duì)EPZS終止搜索的條件以及搜索模板進(jìn)行改進(jìn)，改進(jìn)優(yōu)化后的算法搜索方向細(xì)化，精度更高，減少了搜索點(diǎn)數(shù)，降低了算法的復(fù)雜度，有效節(jié)省了運(yùn)動(dòng)估計(jì)的時(shí)間，增強(qiáng)了編碼的實(shí)時(shí)性。

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

EPZS搜索算法利用視頻運(yùn)動(dòng)的空間和時(shí)間相關(guān)項(xiàng)，對(duì)當(dāng)前編碼的運(yùn)動(dòng)矢量進(jìn)行預(yù)測(cè)，提出一種相鄰塊失真的提前終止準(zhǔn)則來(lái)提前終止搜索[6]，進(jìn)一步來(lái)提高搜索速度，減少編碼的復(fù)雜度。對(duì)于那些不能提前進(jìn)行終止搜索的，利用搜索模板來(lái)進(jìn)行相關(guān)運(yùn)動(dòng)矢量地完善。

1.1 計(jì)算提前終止搜索條件的不足

EPZS根據(jù)相鄰塊的失真具有很高的相似度，而提出了一種基于相鄰塊失真的提前終止準(zhǔn)則。通過(guò)提前終止準(zhǔn)則，減少了算法的計(jì)算復(fù)雜度。在EPZS算法中，通過(guò)當(dāng)前塊A的左側(cè)塊B、正上方塊C、右上方塊D三個(gè)相鄰塊的最小SAD值來(lái)計(jì)算終止條件的標(biāo)準(zhǔn)[7]（分別記為SADB、SADC、SADD）。由此可知，EPZS計(jì)算終止搜索的條件過(guò)于簡(jiǎn)單，對(duì)于大多數(shù)情況計(jì)算出來(lái)的搜索終止條件是滿足的，但沒(méi)有考慮到運(yùn)動(dòng)較小或者靜止情況下，這三個(gè)SAD的值非常接近[8]，由此可知，這樣計(jì)算出來(lái)的SAD不一定是準(zhǔn)確的。

1.2 EPZS的搜索模板的不足

改進(jìn)后的EPZS算法，搜索點(diǎn)數(shù)過(guò)多，對(duì)于運(yùn)動(dòng)較為復(fù)雜的運(yùn)動(dòng)場(chǎng)合，容易陷入局部最優(yōu)而提前進(jìn)入終止搜索，這樣就會(huì)產(chǎn)生更大的誤差。

2 改進(jìn)后的EPZS算法

對(duì)EPZS算法的優(yōu)化主要是針對(duì)其在計(jì)算終止搜索條件和搜索模板方面地優(yōu)化，通過(guò)終止搜索閾值T0地設(shè)定和不同的搜索模板方法來(lái)對(duì)當(dāng)前塊在不同的范圍內(nèi)進(jìn)行搜索，直至搜索到最佳點(diǎn)，得到最佳運(yùn)動(dòng)矢量。

2.1 搜索終止條件的優(yōu)化

我們將起始搜索點(diǎn)的SAD值記為SADM，由于起始預(yù)測(cè)搜索點(diǎn)最接近于最佳點(diǎn)，SAD的值和SADM的值相關(guān)性越大，我們可以更快地利用終止搜索的條件來(lái)得到最佳的SAD值，我們?cè)O(shè)定終止搜索的閾值為T0，如下公式所示：

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

2.2 精細(xì)搜索模板的改進(jìn)

通過(guò)研究各種搜索模板，我們可以發(fā)現(xiàn)搜索模板越是接近圓形，其搜索性能越好[9]，因?yàn)閳A形的方向覆蓋全，搜索范圍更精確，更容易讓我們找到最佳點(diǎn)，從而得到最佳運(yùn)動(dòng)矢量，而這里十二邊形無(wú)限接近于圓形，它共有13個(gè)點(diǎn)分別為（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），搜索中心點(diǎn)和外圍的12個(gè)不同方向的點(diǎn)，求得最佳點(diǎn)，判斷搜索到的點(diǎn)是不是最佳點(diǎn)，如不是以此點(diǎn)為中心進(jìn)行非對(duì)稱十字形搜索，判斷是否為最佳點(diǎn)，直到最佳點(diǎn)為中心點(diǎn)，此時(shí)的向量為最佳運(yùn)動(dòng)矢量MV。利用十二邊形進(jìn)行最佳點(diǎn)方向的判斷搜索，方向覆蓋更全面，減少了搜索點(diǎn)數(shù)，能夠很快很好地得到最佳點(diǎn)，從而得到最佳運(yùn)動(dòng)矢量。

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

在初始化搜索點(diǎn)后，對(duì)塊類型進(jìn)行判別來(lái)選擇相應(yīng)的模板進(jìn)行搜索最佳點(diǎn)，然后進(jìn)行閾值判斷來(lái)判別是否終止搜索。算法的搜索步驟和流程如圖2所示。

算法的搜索步驟如下：

（1）判斷當(dāng)前塊是否是靜止塊，若是靜止塊直接跳入步驟（5），否則進(jìn)入步驟（2）。

（2）判斷當(dāng)前塊是小運(yùn)動(dòng)塊還是大運(yùn)動(dòng)塊，如果當(dāng)前塊為小運(yùn)動(dòng)塊，即運(yùn)動(dòng)平緩，則進(jìn)入步驟（3），否則進(jìn)入步驟（4）。

（3）當(dāng)前塊為小運(yùn)動(dòng)塊，對(duì)其進(jìn)行小鉆石形模板搜索，直到SAD小于閾值T0，得到最佳運(yùn)動(dòng)矢量。

（4）當(dāng)前塊為大運(yùn)動(dòng)塊，即運(yùn)動(dòng)比較激烈，此時(shí)應(yīng)該先進(jìn)行初始搜索點(diǎn)預(yù)測(cè)，然后對(duì)其進(jìn)行十二邊形模板搜索，對(duì)得到的SAD進(jìn)行分析，是否為最佳點(diǎn)，若為最佳點(diǎn)，則對(duì)其進(jìn)行小鉆石形模板搜索，直到得到最佳運(yùn)動(dòng)矢量；若不是最佳點(diǎn)則對(duì)其進(jìn)行非對(duì)稱十字形搜索，然后再次判斷是否為最佳點(diǎn)，若不是則一直進(jìn)行非對(duì)稱十字形搜索，直到得到SAD最佳點(diǎn)，然后再對(duì)其最佳點(diǎn)進(jìn)行小鉆石型搜索，直到SAD小于閾值T0，得到最佳運(yùn)動(dòng)矢量。

（5）搜索結(jié)束。

本文是以H.264官方的標(biāo)準(zhǔn)測(cè)試模型JM 10.1為平臺(tái)，在此基礎(chǔ)上對(duì)改進(jìn)算法進(jìn)行測(cè)試的實(shí)驗(yàn)。優(yōu)化后的算法和基于六邊形改進(jìn)的EPZS算法相比較，在不影響圖像質(zhì)量的前提下，運(yùn)動(dòng)估計(jì)的時(shí)間明顯減少，搜索效率明顯提高。

3 結(jié) 語(yǔ)

本文基于EPZS（預(yù)測(cè)區(qū)域的搜索算法）來(lái)展開(kāi)分析和討論，充分利用圖像運(yùn)動(dòng)的空間域和時(shí)間域的相關(guān)特性，利用初始預(yù)測(cè)矢量和閾值終止標(biāo)準(zhǔn)來(lái)進(jìn)行相關(guān)運(yùn)動(dòng)矢量地求解。改進(jìn)后的算法在搜索中使用小鉆石形、非對(duì)稱十字形以及十二邊形等搜索模板，在保證圖像恢復(fù)質(zhì)量不變的情況下，運(yùn)動(dòng)估計(jì)時(shí)間明顯減少，特別是對(duì)運(yùn)動(dòng)對(duì)象較為劇烈的場(chǎng)合有顯著的效果，編碼效率有了顯著地提高，提高了視頻運(yùn)動(dòng)序列編碼的實(shí)時(shí)性，具有一定的實(shí)用價(jià)值。

參考文獻(xiàn)

[1]陳靖，劉京，曹喜信.深入理解視頻編解碼技術(shù)——基于H.264標(biāo)準(zhǔn)及參考模型[M].北京：北京航空航天大學(xué)出版社，2012.

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

[3] SHI Z，F(xiàn)ERNANDO 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]田東坡，鮑可進(jìn).基于EPZS的H.264/AVC運(yùn)動(dòng)估計(jì)改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究，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]丁鑫，樊慧津.基于方向自適應(yīng)的運(yùn)動(dòng)估計(jì)混合模板搜索算法[J].中國(guó)圖象圖形學(xué)報(bào)，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] 李軍，周曉慧，葉文龍.基于運(yùn)動(dòng)估計(jì) EPZS 算法的優(yōu)化[J].機(jī)電工程，2011， 28（6）：736-738.