蔣麗峰

（福建工程學(xué)院信息科學(xué)與工程學(xué)院，福建 福州 350108）

基于H.264的改進(jìn)運(yùn)動(dòng)估計(jì)算法及其性能對(duì)比實(shí)驗(yàn)研究

蔣麗峰

（福建工程學(xué)院信息科學(xué)與工程學(xué)院，福建 福州 350108）

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

視頻壓縮；H.264標(biāo)準(zhǔn)；運(yùn)動(dòng)估計(jì)；快速搜索算法

0　引　言

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

因此，為了提高視頻的壓縮效率，本文在菱形搜索算法（DS）和十字菱形搜索算法（CDS）的基礎(chǔ)上，結(jié)合實(shí)際運(yùn)動(dòng)圖像中的運(yùn)動(dòng)向量以水平方向?yàn)橹鞯奶攸c(diǎn)，提出了一種利用偏水平十字模板搜索與偏向雙菱形模板搜索相結(jié)合的改進(jìn)搜索算法。

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

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

圖1　菱形搜索算法

十字菱形搜索算法是在菱形搜索算法的基礎(chǔ)上進(jìn)行了改進(jìn)，同樣遵循先粗后精的的搜索原則，十字型較之菱形與現(xiàn)實(shí)圖像運(yùn)動(dòng)矢量的分布對(duì)接效率更高。十字菱形搜索法的模板為十字菱形狀，它分為9點(diǎn)大十字菱形模板（large cross diamond search pattern，LCDSP）和5點(diǎn)小十字菱形模板（small cross diamond search pattern，SCDSP），如圖2所示。

圖2　十字菱形搜索算法

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

2　運(yùn)動(dòng)估計(jì)新算法

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

2.1搜索模板設(shè)計(jì)

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

2.2最優(yōu)匹配準(zhǔn)則

最優(yōu)匹配準(zhǔn)則是判定當(dāng)前最優(yōu)匹配點(diǎn)是否是全局最優(yōu)匹配點(diǎn)，當(dāng)前匹配塊是否是全局最佳匹配塊的準(zhǔn)則，匹配準(zhǔn)則的定義直接決定了編碼效率和匹配準(zhǔn)確度。本文用絕對(duì)差值和SAD來作為快匹配準(zhǔn)則，如下式表示：

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

SAD最小時(shí)的點(diǎn)即為最優(yōu)的匹配點(diǎn)。

運(yùn)動(dòng)估計(jì)的計(jì)算操作數(shù)可以通過下式計(jì)算：

式中：l1、l2——當(dāng)前塊和參考?jí)K劃分的行數(shù)和列數(shù)；

S——搜索窗范圍內(nèi)的搜索點(diǎn)數(shù)量；

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

SAD計(jì)算中減法、絕對(duì)值和加法的計(jì)算次數(shù)。

2.3搜索策略設(shè)計(jì)

算法流程圖如圖4所示。

圖4　本文改進(jìn)算法流程圖

具體步驟如下：

1）以搜索窗口的坐標(biāo)原點(diǎn)為搜索中心，使用偏十字水平模板作為當(dāng)前模板進(jìn)行搜索，若最小SAD點(diǎn)是模板中心點(diǎn)，說明圖像是靜止的，搜索結(jié)束；若最小SAD點(diǎn)不在中心點(diǎn)則轉(zhuǎn)至步驟2）繼續(xù)搜索。

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

3）若當(dāng)前最佳匹配點(diǎn)在模板中心或者偏中心的位置上，則對(duì)位于模板中心的上一點(diǎn)與位于模板中心的下一點(diǎn)進(jìn)行塊匹配誤差計(jì)算，再和當(dāng)前最佳匹配點(diǎn)進(jìn)行比較，SAD值最小的點(diǎn)即為最佳匹配點(diǎn)，算法結(jié)束。

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

3　對(duì)比實(shí)驗(yàn)與結(jié)果分析

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

從表1可以看出，針對(duì)不同運(yùn)動(dòng)劇烈程度和不同格式大小的所有序列，F(xiàn)S算法的PSNR值均高于其他4種算法的PSNR值，說明FS算法的準(zhǔn)確度最高。本文改進(jìn)算法相對(duì)于FS算法的PSNR值平均只減小了0.033dB，其影響基本可以忽略。說明本文改進(jìn)算法的準(zhǔn)確度基本達(dá)到了最優(yōu)水平。

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

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

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

表2　各算法的碼率BR比較

表3　各算法的運(yùn)動(dòng)估計(jì)時(shí)間MET比較

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

4　結(jié)束語

1）本文在傳統(tǒng)搜索算法的基礎(chǔ)上，結(jié)合實(shí)際運(yùn)動(dòng)圖像中的運(yùn)動(dòng)向量以水平方向向量為主的特點(diǎn)，提出了一種利用偏水平十字模板搜索與偏向雙菱形模板搜索相結(jié)合的改進(jìn)搜索算法。

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

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

[1]王磊，廖怡，朱忠博，等.H.264編碼器設(shè)計(jì)與運(yùn)動(dòng)估計(jì)算法優(yōu)化[J].微計(jì)算機(jī)信息，2007，32（3）：155-156.

[2]朱凱迪，陳一民，譚志鵬，等.H.264運(yùn)動(dòng)估計(jì)算法研究[J].計(jì)算機(jī)工程，2011，37（9）：286-288.

[3]張淑芳，李華，劉曉青，等.基于H.264的復(fù)雜度-失真最優(yōu)的運(yùn)動(dòng)估計(jì)算法[J].計(jì)算機(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，F(xiàn)ujian University of Technology，F(xiàn)uzhou 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類項(xiàng)目（JA13219）

蔣麗峰（1979-），女，湖南婁底市人，碩士，研究方向?yàn)橛?jì)算智能和人工智能。