萬智萍

（中山大學 新華學院，廣東 廣州510520）

0 引 言

運動估計算法在對視頻壓縮時，其特有的塊匹配方法與高效的預測模式使得在視頻壓縮領域被人們廣泛的運用［1－4］。為了進一步減少運動估計算法耗時，人們相繼提出了各種新的快速估計算法，例如三步搜索算法 （TSS）［5］、鉆石搜索算法 （DS）［6，7］以及全搜索算法 （FS）［8］等；這 些算法雖然進一步完善了現(xiàn)有的壓縮技術，但仍然存在著許多不足，如FS算法在對視頻圖像進行壓縮時，雖能夠得到較為清晰的視頻圖像但算法需要計算的搜索點太多；TSS算法與DS算法雖然能夠利用運動矢量的中心偏置分布特性來提高算法的搜索速度，但當處理的視頻運動幅度較大時，容易出現(xiàn)局部最優(yōu)化現(xiàn)象。因此，為了彌補上述的不足，人們提出了UMHexagonS算法［9，10］，通過結(jié)合運動矢量的水平垂直偏置分布特性與半路中止條件，得到與FS質(zhì)量相近而時間卻縮短90%的運動估計效果。但通過對UMHexagonS算法的研究發(fā)現(xiàn)，該算法中仍然存在著不足，如在搜索過程中，未能充分利用視頻圖像的運動方向性和存在著一些多余的搜索點等；因此，本文通過優(yōu)化起始搜索點的預測方式，并根據(jù)視頻序列的運動幅度與方向特性［11］，提出了一種新的閾值運動估計算法，充分利用SAD 準則與圖像的運動特性對視頻圖像進行分類；并結(jié)合改變搜索過程中的搜索長度與搜索模式，提出了具有自適應的方向搜索模式來對各類運動塊進行處理，經(jīng)測試，本文算法能夠在保持視頻圖像的質(zhì)量的情況下，有效減少算法搜索過程中的搜索點數(shù)。

1 自適應搜索長度

為了方便算法的計算。在運動估計算法中，將其搜索目標進行切割處理，而H.264標準算法中共有7種不同尺寸的分割塊分別為：16×16、16×8、8×16、8×8、8×4、4×8、4×4，圖1為這7種分割塊的形式。

圖1 H.264標準下的7種模式

而通過對傳統(tǒng)算法的研究，我們可以發(fā)現(xiàn)在傳統(tǒng)的運動估計算法中，為了得到清晰的視頻圖像，通常對圖像中不同的分割塊采用相同的搜索窗進行預測；雖然這樣有效的降低了算法的復雜程度，但顯然容易造成圖像的搜索冗余，例如采用32×32搜索窗來對8×8的分割塊和16×16的分割塊進行搜索就容易出現(xiàn)搜索的冗余現(xiàn)象，從而降低了算法的搜索效率。

為了減少算法在搜索過程中的冗余現(xiàn)象的發(fā)生，本文針對不同大小的分割快模式，采用動態(tài)的搜索窗來定義各搜索模式的長度，其函數(shù)的表達式

其中，SR為在算法中固定搜索窗的尺寸大小，mvuplayer＿x、mvuplayer＿y是上層預測時預測運動矢量中的水平分量與垂直分量，mvmedian＿x、mvmedian＿y是中值預測時預測運動矢量中的水平分量與垂直分量。通過采用上述方法，來減少算法搜索過程中多余的搜索點，從而為算法的進一步完善提供有利的條件。

2 起始搜索點的預測

在進行的運動矢量預測時，先使用中值預測，得到當前搜索點，并將其設為最佳點best，引入自適應的閾值Th1、Th2進行預先判斷

公式

其中βstop 為塊的尺寸，αstop為常數(shù)組，常數(shù)組αstop＝｛0.30，0.33，0.33，0.27，0.13，0.13，0.44｝；

通過在起始點的預測搜索過程中引入閾值，來到減少算法中的必要的搜索，從而節(jié)約了搜索的點數(shù)；在此過程中，對運動矢量幅度較小的采用菱形模板進行搜索；

3 運動類型分類

為了減少算法中的計算量與降低運動估計算法的算法復雜度，采用當前塊與預測起始點對應塊的像素值SAD 進行分類；SAD（s，c（m））為源視頻信號s與編碼視頻信號c之間的絕對誤差和，能夠較好的反映視頻圖像的塊運動幅度的大小，本文通過引入閾值λ1來對其進行判斷。

其計算函數(shù)表達式，定義如下

其中B1，B2＝16，8或4；s是當前編碼的數(shù)據(jù)；c （m）是編碼重建的參考幀數(shù)。

為了進一步提高算法的分類的準確性，根據(jù)視頻的運動特性；本文引入運動的特性，令

其中i的取值為1，2，3，4；得到運動特性的函數(shù)表達式：L ＝max｛l1，l2，l3，l4｝。

其函數(shù)的分類如下：

當SADP≤λ1時，可直接定為靜止狀態(tài)；

當λ1＜SADP＜λ2＆L ≤L1時，為運動幅度慢的運動塊；

當（λ1＜SADP＜λ2＆L1＜L ＜L2）｜｜ （λ2≤SADP＆L ≤L2）時，則當前塊為運動幅度中等的運動塊；

當λ2≤SADP＆L2≤L 時，則當前塊為運動幅度快的運動塊；

其中L1、L2為預設的門限常數(shù)。

下面對閾值的取值進行定義，如下所示：

（1）閾值L1、L2根據(jù)多次試驗最終總結(jié)出來經(jīng)驗，即當L1＝1，L2＝2時，其分離出來的運動塊最為精確。

（2）若當前塊的第一個P 幀內(nèi)的塊，則此時令閾值λ1＝512，否則令λ1＝a×REF＿SAD ，其中a為常數(shù)，在本文中a的取值為0.95，REF＿SAD 為參考幀對應位置塊的SAD 最小值。

若λ1＜512，則λ1＝512

若λ1＞1024，則λ1＝1024

閾值λ2的取值則為λ2＝λ1＋256；

研究發(fā)現(xiàn)，對于視頻圖像的運動塊，當其運動塊運動幅值較小的時候，由于其搜索目標主要集中在搜索原點以及其附近，則直接對其進行小菱形搜索模式就能精確的得到搜索目標；而當運動幅值中等的時候，其搜索目標由于運動幅度大使其偏離模式原點，因此采用圓形搜索模式先對其進行初步的搜索，后進行菱形搜索模式進行縮小搜索范圍，最終由小菱形搜索模式對其進行精確定位；當運動幅值較大的時候，其搜索目標點由于運動太過于激烈使其遠離了搜索原點并分散在離原點較遠的范圍，而十字搜索模式能較好的對分布較為廣的運動塊進行搜索，因此可以采用十字搜索模式對其進行搜索，最后采用小菱形搜索模式定向精確搜索。其最終的分類處理方法如下所示：

當SADp≤λ1時，直接提前停止搜索；

當λ1＜SADp＜λ2＆L ＜L1時，采用菱形搜索模式；

當滿足（λ1＜SADp＜λ2＆L1＜L＜L2）或者滿足（λ2＜SADp＆L ＜L2）；則采用圓形＋菱形＋小菱形搜索模式；

當λ2＜SADp＆L2＜L時，采用十字＋小菱形搜索模式。

4 運動塊的運動分布情況

在現(xiàn)實的生活中，采集回來的視頻圖像通常是沿著水平方向與垂直方向上進行掃描，為了驗證運動塊中搜索目標所分布的位置，本對QCIF 的3 個標準視頻測試序列：news、foreman、coastguard分別進行仿真并取其平均值進行統(tǒng)計，其中news的空間細節(jié)比較少，并且運動較為緩慢，因此用來表示運動幅度小的運動序列；foreman雖然鏡頭與畫面的背景一起運動，但其紋理復雜度一般，因此用來表示運動幅度中等的運動序列；coastguard運動形式豐富并且其紋理的復雜度極高，因此用來表示運動幅度很大的運動序列。在標準搜索窗下，得到的數(shù)據(jù)，表1 為通過仿真后各視頻搜索目標所在位置平均概率表。

表1 搜索目標所在位置概率

由表1可以看到，搜索點在出現(xiàn)在預測中心的概率最高，高達60.05%；而其他則基本上集中在水平方向與垂直方向上；因此，本文在對搜索目標點的時候，主要將搜索重心集中在搜索原點 （0，0）、水平方向與垂直方向上，將上面的圓形搜索模式與十字搜索模式引入運動塊的方向特性，提高算法估計效率。

5 方向性搜索模式

5.1 方向六邊形搜索模式的選用

采用圓形搜索模式，圓形搜索模式包括三角搜索模式、正方形搜索模式以及正六邊形搜索模式；而其中正六邊形的搜索中心間隔最大且其覆蓋面最廣，有利于更為精確的搜索。

根據(jù)表1數(shù)據(jù)中搜索點的分布情況，則先進行搜索原點進行判斷，如果不是最優(yōu)點，則將正六邊形搜索模式分為水平六邊形搜索模式與垂直搜索模式，并采用式 （1）定義其搜索窗的長度；圖2為水平六邊形搜索模式，圖3為垂直六邊形搜索模式。

為了更好的對視頻進行搜索，本文采用閾值判斷算法將其進行選擇如下所示：

令水平方向與垂直方向的相對二價距為Lx，Ly；

其中N 為運動矢量集的元素個數(shù)，MVix、MViy為MVi的水平與垂直方向的分量，MVpredx、MVpredy是MVpred在水平與垂直方向的分量；

當處于Lx＜λ3＜Ly時，說明在垂直方向上相對劇烈，即在該范圍內(nèi)可采用垂直六邊形搜索模式進行搜索；

當處于Lx＜λ3＜Ly時，說明在水平方向上相對劇烈，即在該范圍內(nèi)可采用水平六邊形搜索模式進行搜索。

5.2 非對稱十字搜索模式的選用

為了更好的利用視頻的方向特性［12］，本文將十字搜索模塊分為兩類：水平十字搜索模塊、垂直十字搜索模塊。在對視頻進行搜索的時候，對其進行判斷，判斷搜索點是否在搜索中心，是則進行小菱形搜索；否則，根據(jù)最佳匹配點的位置來確定，根據(jù)運動方向函數(shù)來確定采用什么十字搜索模塊進行搜索，并通過采用式 （1）定義其搜索窗的長度。圖4為水平十字搜索模式，圖5為垂直十字搜索模式，如下所示。

其中水平十字搜索模板，該模板在水平方向上的移動速度快于垂直方向，將其運用于具有水平特性的運動塊上，可以明顯加快水平方向上的搜索速度，并且減少對不必要點的匹配計算，提高運動估計速度。同理，垂直十字搜索模板也具有相同的效果；引入判斷法則，將當前宏塊運動估計得到的最佳運動矢量記為MV，則該運動矢量方向的計算方法

其中MVx、MVy分別為MV 的水平與垂直分量。

6 算法的流程

步驟1 起始搜索點的預測，先使用中值預測，得到當前搜索點，并將其設為最佳點best；引入自適應的閾值Th1與Th2，對其best進行判斷：若best＜Th1；提前停止搜索；若Th1 ＜best＜Th2；跳到菱形模板搜索；若Th2＜best；則執(zhí)行步驟2。

步驟2 根據(jù)運動類型自適應法，采用SAD 值與運動特性來對視頻進行分類處理，當SADp≤λ1時，為靜止模塊，提前停住搜索；當λ1＜SADp＜λ2＆L ＜L1時，即為運動幅度小的運動塊，則采用菱形搜索模式，后可以轉(zhuǎn)至步驟7；（λ1＜SADp＜λ2＆L1＜L ＜L2）｜｜（λ2＜SADp＆L ＜L2）時，即為運動幅度中等的運動塊，轉(zhuǎn)至步驟3；當λ2＜SADp＆L2＜L 時，即為運動幅度大的運動塊，轉(zhuǎn)至步驟4；

步驟3 采用方向六邊形搜索模式，通過比較Lx、Ly與閾值λ3的大小關系來選擇方向六邊形搜索模式；當Lx＜λ3＜Ly，使用垂直六邊形搜索模式，當Lx＜λ3＜Ly，使用水平六邊形搜索模式；經(jīng)過方向六邊形搜索模式后，采用菱形搜索模式進行進一步精確搜索，最后轉(zhuǎn)至步驟5；

步驟4 采用非對稱十字搜索模式，并通過式 （3）來獲得水平分量與垂直分量的比例，來獲得的θ 的范圍；當＜θ＜π 4 時，采用水平十字搜索模式，當＜θ＜時，采用垂直十字搜索模式；經(jīng)過十字搜索模式后，轉(zhuǎn)至步驟5；

步驟5 小菱形模板反復搜索，得到運動矢量；

步驟6 輸出MV。

7 仿真實驗

本文在JM12.2平臺上進行算法驗證，采用的視頻測試序列為代表不同運動劇烈程度的兩種不同格式的6個標準序列：其中QCIF 格式的采用news、foreman、coastguard，而CIF格式采用akiyo、foreman、football；并設置編碼幀數(shù)為60，參考幀數(shù)為5，幀率30，編碼格式為IPPPP，QP值為32。各視頻序列的分類，見表2。

表2 各視頻序列的分類

7.1 搜索點與搜索時間的比較

算法的搜索消耗時間可以用宏塊中的搜索點數(shù)來衡量，其中搜索點數(shù)越少，其過程越簡單，所花費的時間也就越少；因此，為了更好的驗證算法在搜索方面的優(yōu)越性，本文通過對比各算法間的搜索點數(shù)，體現(xiàn)算法在搜索方向的優(yōu)勢，經(jīng)檢測，得到表3為各算法每個宏塊中的平均搜索點數(shù)數(shù)據(jù)表。

由表3可以清晰的看到，全搜索算法的搜索點數(shù)最多，而鉆石搜索法由于有效的利用運動矢量的中心偏置分布這一特性來進行搜索，大幅度的減少了運動估計算法中的搜索點數(shù)，有表可以看到，其平均搜索點數(shù)相比全搜索算法減少了95%的搜索點數(shù)；UMHexagonS算法卻在其基礎上進一步提升，使搜索點數(shù)進一步減少；而本文算法的搜索點數(shù)比UMHexagonS算法的搜索點數(shù)將近一半，有效的證明了算法的優(yōu)越性。表4為UMHexagonS算法與本文算法的耗時數(shù)據(jù)表。

表3 各算法每個宏塊平均搜索點數(shù)

表4 UMHexagonS算法與本文算法的平均耗時

7.2 峰值信噪比的比較

本文采用的峰值信噪比計算公式如下所示

其中M，N 為視頻圖像的長和寬，f（x，y）為原始圖像的像素灰度值而f′（x，y）為重構(gòu)后的視頻圖像像素灰度值，其中所測得的PSNR 值越大，則表示的視頻處理效果最好。通過檢查，得表5為各算法的峰值信噪比數(shù)據(jù)表。

表5 各算法的峰值信噪比數(shù)據(jù)

由表5可以看到，本文算法所測得的峰值信噪比與全搜索算法的峰值信比相差無幾，并且伴隨著所測視頻的運動幅度的變換，本文算法的PSNR 值依然與全搜索算法相同，其中最大的比全搜索差0.46dB，最少相差只有0.25dB；而鉆石搜索法與UMHexagonS算法由于其算法的局部最優(yōu)解，使得得到的視頻質(zhì)量受到視頻運動幅度大小的影響。進而有效的驗證了算法在視頻保質(zhì)的優(yōu)越性。

為了檢驗算法的可行性，本文采用運動幅度相對較大點的football標準序列對以上算法進行測試，其中采用QP＝28；其仿真結(jié)果圖如圖6所示，圖6為football第47幀各算法的主觀效果對比圖。

圖6 football第47幀各算法的主觀效果對比

當QP＝28時，通過采用FS、DS、UMHexagonS算法以及本文算法對football進行仿真的最終效果圖，從圖6我們可以看到，本文算法與DS、UMHexagonS算法相比，其解碼圖的效果與理想的FS算法的效果很接近，與預期的效果相符，具有一定的可行性。

8 結(jié)束語

本文提出一種融合運動幅度與方向特性的快速運動估計算法，充分調(diào)用運動塊的SAD 值與運動特性進行分類，并結(jié)合方向搜索模式來減少算法中不必要的搜索點，到達算法的最優(yōu)化。經(jīng)實驗，該算法能夠在保證圖像質(zhì)量的情況下有效的減少算法中的搜索點數(shù)，進而大大減少算法花費的時間；而且在搜索的過程中不受圖像運動幅度大小的影響，始終保持與全搜索算法相近的搜索效果。

［1］Juwon Byun，Jinha Choi，Jaeseok Kim.A fast multi－reference frame motion estimation algorithm ［J］.IEEE Transactions on Consumer Electronics，2010，56 （3）：1911－1917.

［2］LIU Shaowei，WEI Shouder，LAI Shanghong.Fast optimal motion estimation based on gradient－based adaptive multilevel successive elimination ［J］.IEEE Transactions on Circuits and Systems for Video Technology，2008，18 （2）：263－267.

［3］Sangkwon Na，Chong－Min Kyung.Activity－based motion estimation scheme for H.264 scalable video coding ［J］.IEEE Transactions on Circuits and Systems for Video Technology，2010，20 （11）：475－1485.

［4］Yasser Ismail，Jason B McNeely，Mohsen Shaaban，et al.Fast motion estimation system using dynamic models for H.264／AVC video coding ［J］.IEEE Transactions on Circuits and Systems for Video Technology，2012，22 （1）：28－42.

［5］Su Chungyen，Hsu Yipin.Reused SAD for partial search area in efficient three－step search algorithm ［J］.Journal of the Chinese Institute of Engineers，2007，30 （3）：537－543.

［6］Chatterjee S K，Chakrabart I I.Low power VLSI architectures for one bit transformation based fast motion estimation ［J］.IEEE Transactions on Consumer Electronics，2010，56 （4）：2652－2660.

［7］Po L M，Ting C W，Wong K M，et al.Novel point－oriented inner searches for fast block motion estimation ［J］.IEEE Transactions on Multimedia，2007，9 （1）：9－15.

［8］Sarwer M G，Wu Q M J.Efficient two step edge based partial distortion search for fast block motion estimation ［J］.IEEE Transactions on Consumer Electronics，2009，55 （4）：2154－2162.

［9］Xu Xiaozhong，He Yun.Improvements on fast motion estimation strategy for H.264／AVC ［J］.IEEE Transactions on Circuits and Systems for Video Technology，2008，18 （3）：285－293.

［10］Martin Schwalb，Ralph Ewerth，Bernd Freisleben.Fast motion estimation on graphics hardware for H.264video encoding ［J］.IEEE Transactions on Multimedia，2009，11 （1）：1－10.

［11］Takumi Kobayashi，Nobuyuki Otsu.Motion recognition using local auto－correlation of space－time gradients［J］.Pattern Recognition Letters，2012，33 （9）：1188－1195.

［12］Hannah M Dee，Anthony G Cohn，David C Hogg.Building semantic scene models from unconstrained video［J］.Computer Vision and Image Understanding，2012，116 （3）：446－456.