基于H.264的改進運動估計算法及其性能對比實驗研究

蔣麗峰

（福建工程學院信息科學與工程學院，福建 福州 350108）

基于H.264的改進運動估計算法及其性能對比實驗研究

蔣麗峰

（福建工程學院信息科學與工程學院，福建 福州 350108）

為提高視頻壓縮效率，在傳統搜索算法的基礎上，結合實際運動圖像中的運動向量，以水平方向向量為主要特點，提出一種利用偏水平十字模板搜索與偏向雙菱形模板搜索相結合的改進搜索算法。該改進算法可以根據運動向量的特點來減少模板的搜索點數，達到提高視頻壓縮效率、節省運動估計時間的目的。性能對比實驗結果表明：該改進算法適合各種運動類型的視頻序列，尤其適用于運動變化劇烈的序列，并且能夠在PSNR值和碼率值極其接近FS算法的情況下，對QCIF格式圖像的運動估計時間（MET）減少約95%，對CIF格式圖像的運動估計時間（MET）減小約94.5%，大大減少運動估計時間。

視頻壓縮；H.264標準；運動估計；快速搜索算法

0　引　言

H.264是ITU-T的聯合視頻組開發的一個新的數字視頻編碼標準，因壓縮比和網絡親和性好而被廣泛使用，但是，H.264標準與其他標準相比需要消耗更多的時間和資源[1]。運動估計算法決定了視頻壓縮的性能和速度，是視頻壓縮編碼系統中的關鍵環節，因此尋求更高效的運動估計算法成了節省編碼時間和資源、提高編碼質量的重中之重。針對運動估計運算速度的問題，國內外學者對此進行了大量的研究，提出了許多簡單高效的運動估計算法。通常，快速算法分為兩類：基于全局的運動估計算法和基于模板的運動估計算法[2-3]?；谌值倪\動估計算法是精度最優算法，主要通過全局搜索來尋找全局最優匹配點，其運算復雜、運算量大，但是估計精度是所有算法中最高的。比較經典的基于模板運動估計算法主要有新三步搜索算法（NTSS）、菱形搜索算法（DS）和十字菱形搜索算法（CDS）等，因其匹配速度快準確度高殘差值小而被廣泛使用[4-8]。傳統搜索算法由于其模板規則對稱，所以無論是在水平方向上搜索還是垂直方向上搜索都規則對稱，而實際運動圖像中的運動向量以水平方向向量為主，在水平方向運動比垂直方向運動劇烈。

因此，為了提高視頻的壓縮效率，本文在菱形搜索算法（DS）和十字菱形搜索算法（CDS）的基礎上，結合實際運動圖像中的運動向量以水平方向為主的特點，提出了一種利用偏水平十字模板搜索與偏向雙菱形模板搜索相結合的改進搜索算法。

1　菱形與十字菱形搜索算法性能分析

菱形搜索算法是性能比較優異的算法之一，它充分考慮到實際視頻序列中物體在水平和垂直兩個方向運動的概率較其他方向大，圖像頻譜多呈菱形分布，所以菱形搜索法的模板為菱形狀，主要分為9點大菱形模板（large diamond search pattern，LDSP）和5點小菱形模板（small diamond search pattern，SDSP），如圖1所示。它遵循先粗后精的搜索原則，先用LDSP模板進行粗定位，避免陷入局部最優，然后使用SDSP模板搜索粗定位中最小SAD值點的周圍4個點，此時得到的SAD值最小點便是最優匹配點。

圖1　菱形搜索算法

十字菱形搜索算法是在菱形搜索算法的基礎上進行了改進，同樣遵循先粗后精的的搜索原則，十字型較之菱形與現實圖像運動矢量的分布對接效率更高。十字菱形搜索法的模板為十字菱形狀，它分為9點大十字菱形模板（large cross diamond search pattern，LCDSP）和5點小十字菱形模板（small cross diamond search pattern，SCDSP），如圖2所示。

圖2　十字菱形搜索算法

菱形搜索算法（DS）充分考慮了實際視頻序列中物體在水平和垂直兩個方向運動的概率較其他方向大，圖像頻譜多呈菱形分布的特點，而十字菱形搜索算法（CDS）與現實圖像運動矢量的分布對接效率更高，這兩種算法是目前綜合性能較好的快速搜索算法。這兩種搜索算法也因其匹配速度快準確率高殘差值小而被廣泛使用。

2　運動估計新算法

為了提高視頻的壓縮效率，本文首先從水平搜索方向出發，利用偏水平十字模板來初步確定搜索位置，然后利用偏向雙菱形模板局部尋優，確定當前最優匹配點，若當前最優匹配點是全局最優匹配點則停止搜索，否則繼續尋優匹配，最后通過比較所有候選點的SAD值（差的絕對值的和）來確定全局最優匹配點。

2.1搜索模板設計

本文結合十字菱形搜索算法的十字菱形模板和菱形搜索算法的菱形模板，設計了一種偏水平十字模板和一種偏向雙菱形模板。偏水平十字模板是結合實際運動圖像中的運動向量以水平方向向量為主的特點將規則完全對稱的十字菱形模板垂直方向上的點進行刪減，以減少模板的搜索點數。偏向雙菱形模板將菱形模板中5點小菱形模板SDSP進行水平方向組合和垂直方向組合，得到了9點偏向雙菱形模板，既繼承了菱形搜索法對實際視頻序列的水平和垂直方向的大概率估計，又得到了單一方向向量主導的自適應選擇。偏水平十字及偏向雙菱形搜索算法模板如圖3所示。

2.2最優匹配準則

最優匹配準則是判定當前最優匹配點是否是全局最優匹配點，當前匹配塊是否是全局最佳匹配塊的準則，匹配準則的定義直接決定了編碼效率和匹配準確度。本文用絕對差值和SAD來作為快匹配準則，如下式表示：

圖3　偏水平十字及偏向雙菱形搜索算法

SAD最小時的點即為最優的匹配點。

運動估計的計算操作數可以通過下式計算：

式中：l1、l2——當前塊和參考塊劃分的行數和列數；

S——搜索窗范圍內的搜索點數量；

Sub、Abs、Add——快匹配原則中絕對誤差和

SAD計算中減法、絕對值和加法的計算次數。

2.3搜索策略設計

算法流程圖如圖4所示。

圖4　本文改進算法流程圖

具體步驟如下：

1）以搜索窗口的坐標原點為搜索中心，使用偏十字水平模板作為當前模板進行搜索，若最小SAD點是模板中心點，說明圖像是靜止的，搜索結束；若最小SAD點不在中心點則轉至步驟2）繼續搜索。

2）最小SAD點不在中心則根據運動矢量的指向來選用偏水平雙菱形模板還是偏垂直雙菱形模板，若當前最佳匹配點在模板中心或者偏中心的位置上則轉至步驟3）；若當前最佳匹配點在模板的邊緣上則轉至步驟4）。

3）若當前最佳匹配點在模板中心或者偏中心的位置上，則對位于模板中心的上一點與位于模板中心的下一點進行塊匹配誤差計算，再和當前最佳匹配點進行比較，SAD值最小的點即為最佳匹配點，算法結束。

4）若當前最佳匹配點在模板的邊緣上，且當前最佳匹配點處在相對于模板中心或者偏中心的水平方向上，則選用偏水平雙菱形模板搜索；若當前最佳匹配點在模板的邊緣上，且當前最佳匹配點處在相對于模板中心或者偏中心的垂直方向上，則選用偏垂直雙菱形模板搜索。得到的最佳匹配點位于模板中心或者偏中心的位置上則轉至步驟3）；若在模板的邊緣上則轉至步驟4）。

3　對比實驗與結果分析

本文在JM12.4的基礎上進行基于偏水平十字及偏向雙菱形搜索法的性能對比實驗。視頻測試序列選擇為代表不同運動劇烈程度和不同格式大小的4個標準序列：運行實驗環境VC++6.0，實驗采用QCIF格式的Akiyo、Coast-Guard測試序列和CIF格式的Foreman、Football測試序列，其中 Football、Coast-Guard為運動變化劇烈序列，Akiyo、Foreman為運動緩慢的序列。將本文提出的算法與幾種常見的運動估計算法比較，評價算法效率的指標包括峰值信噪比PSNR（單位：dB）、碼率BR（單位：kb/s）和運算時間MET（單位：s），MV搜索范圍為16，QP為28。具體的比較結果如表1～表3所示，表中ΔMET%為當前搜索算法相對于FS搜索算法的運動估計時間減少率。計算公式：

從表1可以看出，針對不同運動劇烈程度和不同格式大小的所有序列，FS算法的PSNR值均高于其他4種算法的PSNR值，說明FS算法的準確度最高。本文改進算法相對于FS算法的PSNR值平均只減小了0.033dB，其影響基本可以忽略。說明本文改進算法的準確度基本達到了最優水平。

從表2可以看出，本文改進算法和十字菱形搜索算法（CDS）對運動變化劇烈的Football和Coast-Guard序列的碼率提高明顯，在1.5%～2.5%之間。說明本文改進算法和十字菱形搜索算法（CDS）對運動變化劇烈的序列具有顯著性。

從表3可以看出，針對不同運動劇烈程度和不同格式大小的所有序列均滿足：本文改進算法的MET＜CDS算法的MET＜DS算法的MET＜FS算法的MET，本文改進算法極大地節省了運動估計時間。同時從表3還可以看出，各算法對QCIF大小的圖像運動估計時間均小于CIF大小的圖像運動估計時間，本文改進算法相比于FS搜索法，對QCIF大小圖像的運動估計時間減少約95%，對CIF大小的圖像的運動估計時間減小約94.5%。

表1　各算法的峰值信噪比PSNR比較

表2　各算法的碼率BR比較

表3　各算法的運動估計時間MET比較

綜上所述，本文提出的基于偏水平十字及偏向雙菱形搜索法適合各種運動類型的視頻序列，特別適用于運動變化劇烈的序列，并且能夠在PSNR值和碼率值極其接近于FS算法的情況下，大大減少運動估計時間。

4　結束語

1）本文在傳統搜索算法的基礎上，結合實際運動圖像中的運動向量以水平方向向量為主的特點，提出了一種利用偏水平十字模板搜索與偏向雙菱形模板搜索相結合的改進搜索算法。

2）FS算法的準確度最高，本文改進算法相對于FS算法的PSNR值平均只減小了0.033dB，其影響基本可以忽略。說明本文改進算法的準確度基本達到了最優水平。本文改進算法對運動變化劇烈的Football和Coast-Guard序列的碼率提高明顯，在1.5%～2.5%之間，本文算法對運動變化劇烈的序列具有顯著性。

3）本文提出的基于偏水平十字及偏向雙菱形搜索算法適合各種運動類型的視頻序列，特別適用于運動變化劇烈的序列，并且能夠在PSNR值和碼率值極其接近于FS算法的情況下，對QCIF格式圖像的運動估計時間（MET）減少約95%，對CIF格式圖像的運動估計時間（MET）減小約94.5%，大大減少了運動估計時間。

[1]王磊，廖怡，朱忠博，等.H.264編碼器設計與運動估計算法優化[J].微計算機信息，2007，32（3）：155-156.

[2]朱凱迪，陳一民，譚志鵬，等.H.264運動估計算法研究[J].計算機工程，2011，37（9）：286-288.

[3]張淑芳，李華，劉曉青，等.基于H.264的復雜度-失真最優的運動估計算法[J].計算機工程，2007，33（9）：228-230.

[4]Li R，Zeng B，Liu M L.A new three-step search algorithm for block motion estimation[J].IEEE Trans Circuits Syst Video Technol，1994，4（4）：438-442.

[5]Zhu S，Ma K K.A new diamond search algorithm for fast matching motion estimation[J].IEEE Trans on Image Processing，2000，9（2）：287-290.

[6]Cheung C H，Po L M.A novel cross-diamond search algorithm for fast block motion estimation[J].IEEE Trans Circuits Syst Video Technol，2002，12（12）：1168-1177.

[7]Babu R V，Ramakrishnan K R.Video object segmentation：Acompressed domain approach[J].IEEE Transactions on Circuits and Systems for Video Technology，2004，14（4）：462-474.

[8]Zeng W，Du J，Gao W，et al.Robust moving object segmentation on H.264/AVC compressed video using the block-based MRF model[J].Real-time Imaging，2005，11（4）：290-299.

Research on improved motion estimation algorithm and its performance comparison experiment based on H.264

JIANG Lifeng
（School of Information Science and Engineering，Fujian University of Technology，Fuzhou 350108，China）

Toimprove video compression efficiency，this paper，basedontraditional search algorithms and the motion vector that is chiefly moving in the horizontal direction in actual motion images，has put forward an improved search algorithm，which is a combination of partial to horizontal cross template searching and biased double-diamond template searching.In accordance with the feature of the motion vector，the number of searching spots can be reduced so as to increase the video compression efficiency and shorten the motion estimation time.The performance contrast experiment shows that this improved algorithm suits all types of motional video sequences，especially those changing drastically in movement.Under the condition that the value of PSNR and code rate is very close to FS algorithm，it can decrease around 95%of the motion estimation time(MET)of QCIF pictures and about 94.5%of the MET of CIF pictures respectively compared to the FS algorithm.

video compression；H.264 standard；motion estimation；fast search algorithm

A

1674-5124（2015）12-0128-04

10.11857/j.issn.1674-5124.2015.12.031

2015-05-27；

2015-06-18

福建省教育廳A類項目（JA13219）

蔣麗峰（1979-），女，湖南婁底市人，碩士，研究方向為計算智能和人工智能。