基于DS-CDS的改進運動估計算法及實驗

劉 艷

（山西金融職業(yè)學(xué)院信息技術(shù)系，山西 太原 030008）

基于DS-CDS的改進運動估計算法及實驗

劉 艷

（山西金融職業(yè)學(xué)院信息技術(shù)系，山西 太原 030008）

為了提高視頻的壓縮效率，在菱形搜索算法和十字菱形搜索算法的基礎(chǔ)上，結(jié)合實際運動圖像中的運動向量以水平方向向量為主的特點，提出了一種利用偏水平十字模板搜索與偏向雙菱形模板搜索相結(jié)合的改進搜索算法。為檢驗本文改進算法的效果進行了對比實驗，結(jié)果表明：本文提出的基于偏水平十字及偏向雙菱形搜索法適合各種運動類型的視頻序列，更適用于運動變化劇烈的序列，并且能夠在PSNR值和BR值接近最優(yōu)水平時，大大減少運動估計時間，相比于FS算法，對QCIF格式圖像的運動估計時間減少約95%，對CIF格式圖像的運動估計時間減小約94%。

視頻壓縮；H.264；運動估計；菱形搜索算法；十字菱形搜索算法

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

因此，為了提高視頻的壓縮效率，本文在DS算法和CDS算法的基礎(chǔ)上，結(jié)合實際運動圖像中的運動向量以水平方向向量為主的特點，提出了一種利用偏水平十字模板搜索與偏向雙菱形模板搜索相結(jié)合的改進搜索算法。本文改進算法可以根據(jù)運動向量的特點來減少模板的搜索點數(shù)，達到提高視頻壓縮效率，節(jié)省運動估計時間的目的。

1 DS與CDS算法性能分析

1.1 DS算法

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

具體步驟如下：

(1) 以搜索窗口的坐標原點為搜索中心，檢查LDSP模板上的9個點，若最小SAD點是中心點則轉(zhuǎn)至步驟(3)；若最小SAD點不在中心點則轉(zhuǎn)至步驟(2)繼續(xù)搜索。

(2) 以上一步搜索到的SAD最小點為搜索中心，構(gòu)造另一個LDSP進行匹配，如果新得到的最小SAD值點是中心點則轉(zhuǎn)至步驟(3)；若最小SAD點不在中心點則繼續(xù)步驟(2)直至匹配點到達搜索窗的邊緣即停止搜索。

(3) 以上一步搜索到的SAD最小點為搜索中心，按采用SDSP進行精匹配；此時搜索到的SAD最小的點即為最優(yōu)匹配點，該點相對原點的位移即是運動矢量。

圖1 菱形搜索算法

1.2 CDS算法

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

圖2 十字菱形搜索算法

具體步驟如下：

(1) 以搜索窗口的坐標原點為搜索中心，使用LCDSP模板作為當前模板進行搜索，若最小 SAD點是LCDSP中心點，說明圖像是靜止的，算法結(jié)束。

(2) 若最小SAD點在LCDSP中小十字的位置上，說明圖像的運動矢量較小，則反復(fù)按照SCDSP的模板交叉搜索，此時搜索到的 SAD最小的點即為最優(yōu)匹配點。

(3) 若最小SAD點在LCDSP中大十字的位置上，說明圖像的運動矢量較大，則反復(fù)按照LCDSP的模板交叉搜索，此時搜索到的 SAD最小的點即為最優(yōu)匹配點。

CDS算法可以根據(jù)圖像的運動變換大小不同，自動選擇下一步搜索的模板，做到搜索與具體的內(nèi)容相關(guān)，搜索效果較理想。但是，無論DS算法還是CDS算法的搜索模板都是對稱的，其在搜索時無論是在水平還是垂直方向搜索都是規(guī)則對稱的。而實際運動圖像中的運動向量不是規(guī)則對稱的，往往以水平方向向量為主，在水平方向運動比垂直方向運動更劇烈。

2 運動估計改進算法

為了提高視頻的壓縮效率，本文在DS算法和CDS算法的基礎(chǔ)上，結(jié)合實際運動圖像中的運動向量以水平方向向量為主的特點，提出了一種利用偏水平十字模板搜索與偏向雙菱形模板搜索相結(jié)合的改進搜索算法。首先從水平搜索方向出發(fā)，利用偏水平十字模板來初步確定搜索位置，然后利用偏向雙菱形模板局部尋優(yōu)，確定當前最優(yōu)匹配點，若當前最優(yōu)匹配點是全局最優(yōu)匹配點則停止搜索，若不是，則繼續(xù)尋優(yōu)匹配，最后通過比較所有候選點的SAD值來確定全局最優(yōu)匹配點。

2.1 搜索模板設(shè)計

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

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

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

最優(yōu)匹配準則是判定當前最優(yōu)匹配點是否是全局最優(yōu)匹配點，當前匹配塊是否是全局最佳匹配塊的準則，匹配準則的定義直接決定了編碼效率和匹配精度。本算法用絕對差值和 SAD來作為快匹配準則，如式(1)：

其中，M、N分別為模板水平和垂直像素數(shù)，fk(m,n)為第k幀像素點(m,n)值，fk-1(m+i,n+j)為第k-1幀像素點(m+i,n+j)的亮度值，(i,j)為點(m,n)的偏移量。

SAD點值最小時的點即為最優(yōu)的匹配點，此時的(i,j)是該模板的最佳運動矢量。

運動估計的計算如式(2)：

其中，1l和2l表示當前塊和參考塊劃分的行數(shù)和列數(shù)；S表示搜索窗范圍內(nèi)的搜索點數(shù)量；Sub，Abs和Add分別表示快匹配原則中絕對誤差和SAD計算中減法、絕對值和加法的計算次數(shù)。

2.3 搜索策略設(shè)計

本文改進算法流程圖如圖4所示。

具體步驟如下：

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

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

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

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

圖4 本文改進算法流程圖

3 實驗與結(jié)果分析

本文在JM12.4的平臺上進行基于偏水平十字及偏向雙菱形搜索法的性能對比實驗。視頻測試序列選擇為代表不同運動劇烈程度和不同格式大小的4個標準序列：運行實驗環(huán)境VC++6.0，實驗采用QCIF格式的Akiyo、Coast-Guard測試序列和CIF格式的Foreman、Football測試序列，其中Football、Coast-Guard為運動變化劇烈序列，Akiyo、Foreman為運動緩慢的序列。將本文提出的算法與幾種常見的運動估計算法比較，評價算法效率的指標包括峰值信噪比(peak signal noise ratio, PSNR)、碼率BR和運算時間MET，MV搜索范圍為16，QP為28。實驗結(jié)果如表1～3所示。

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

從表1可以看出，F(xiàn)S算法的PSNR值均高于其他4種算法，說明FS算法的準確度最高，但是，本文改進算、FS算法、DS算法、CDS算法基本處于同一水平，差異可以忽略，說明本文改進算法的精確度基本達到了最優(yōu)水平。同時，還可以看出NTSS算法對CIF格式測試序列上具有不適應(yīng)性。

表2 各種算法的碼率BR比較

從表2可以看出，本文改進算法對運動變化劇烈的Football和Coast-Guard序列的BR值提高明顯，說明本文改進算法對運動變化劇烈的序列具有顯著性。

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

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

綜上所述，本文提出的基于偏水平十字及偏向雙菱形搜索法適合各種運動類型的視頻序列，更適用于運動變化劇烈的序列，且能夠在PSNR值和BR值接近最優(yōu)水平時，還能大大減少了運動估計時間。

4 結(jié) 論

(1) 本文在DS算法和CDS算法的基礎(chǔ)上，結(jié)合實際運動圖像中的運動向量以水平方向向量為主的特點，提出了一種利用偏水平十字模板搜索與偏向雙菱形模板搜索相結(jié)合的改進搜索算法。首先從水平搜索方向出發(fā)，利用偏水平十字模板來初步確定搜索位置，然后利用偏向雙菱形模板局部尋優(yōu)，確定當前最優(yōu)匹配點；若當前最優(yōu)匹配點是全局最優(yōu)匹配點則停止搜索，若不是，則繼續(xù)尋優(yōu)匹配，最后通過比較所有候選點的 SAD值來確定全局最優(yōu)匹配點。

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

(3) 實驗結(jié)果表明：本文提出的基于偏水平十字及偏向雙菱形搜索法適合各種運動類型的視頻序列，特別適用于運動變化劇烈的序列，并且能夠在PSNR值和BR值接近最優(yōu)水平時，還能大大減少了運動估計時間，相比于FS算法，對QCIF及CIF格式圖像的運動估計時間分別減少約95%和94%。

[1] Joint Video Team of ITU-Tand150/IECJTCI, Draft ITU-T. Recommendation and final draft international standard of joint video specification [S/OL]. [2004-03-20]. http://www.itu.int/home/index.html.

[2] 王 磊, 廖 怡, 朱忠博, 等. H.264編碼器設(shè)計與運動估計算法優(yōu)化[J]. 微計算機信息, 2007, 32(3): 155-156.

[3] 田 波, 楊宜民, 蔡述庭. 一種基于視覺感知的 H.264碼率控制算法[J]. 圖學(xué)學(xué)報, 2014, 35(5): 762-767.

[4] 周 芳, 蔣建國, 王培珍. 一種改進的視頻序列超分辨率重建算法及應(yīng)用[J]. 工程圖學(xué)學(xué)報, 2011, 32(1): 45-51.

[5] 朱凱迪, 陳一民, 譚志鵬, 等. H.264運動估計算法研究[J].計算機工程, 2011, 37(19): 286-288.

[6] 張淑芳, 李 華, 劉曉青, 等. 基于H.264的復(fù)雜度-失真最優(yōu)的運動估計算法[J]. 計算機工程, 2007, (9): 228-230.

[7] Li Renxiang, Zeng Bing, Liou M L. A new three-step search algorithm for block motion estimation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 1994, 4(4): 438-442.

[8] Zhu Ce, Lin Xiao, Chau L P. Hexagon-based search pattern for fast block motion estimation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2002, 12(5): 349-355.

[9] Zhu Shan, Ma Kaikuang. A new diamond search algorithm for fast matching motion estimation [J]. IEEE Transactions on Image Processing, 2000, 9(2): 287-290.

[10] Cheung C H, Po L M. A novel cross-diamond search algorithm for fast block motion estimation [J]. IEEE Transactions on Circuits and Systems for Video Technology, 2002, 12(12): 1168-1177.

Improvement of Motion Estimation Algorithm and Experiment Based on DS-CDS

Liu Yan

(Department of Information Technology, Shanxi Professional College of Finance, Taiyuan Shanxi 030008, China)

To improve the compression efficiency of the video, based on diamond search algorithm and cross diamond search algorithm, combined with the feature that motion vector was mainly focused on horizontal direction vector in actual motion images, the thesis put forward an improved search algorithm which combined partial to horizontal cross template search with biased toward double diamond template search. Comparative experiments were conducted to test the effect of improved algorithm. The result of the performance contrast experiment shows that the thesis′s improved algorithm suits all kinds of motional video sequences, especially those sequences changing poignantly in movement. Under the condition that the PSNR and the BR value are very close to the optimal level, compared to the FS algorithm, the improved algorithm decreases approximately 95% of the motion estimation time of the QCIF pictures, and decreases about 94% of the motion estimation time of the CIF pictures, thus decreases greatly the motion estimation time.

video compression; H.264; motion estimation; diamond search algorithm; cross diamond search algorithm

TP 391

A

2095-302X(2015)03-0457-05

2014-05-26；定稿日期：2015-01-14

劉 艷(1982-)，女，山西平陸人，講師，碩士。主要研究方向為計算機應(yīng)用。E-mail：shxliuyan0359@163.com