劉 艷

(山西金融職業(yè)學院信息技術系，山西 太原 030008)

引入搜索預測與閾值決策的改進菱形運動估計算法

劉 艷

(山西金融職業(yè)學院信息技術系，山西 太原 030008)

為了提高視頻的壓縮效率，在傳統(tǒng)菱形搜索算法基礎上提出一種改進菱形搜索算法。該算法通過引入動態(tài)閾值，在起始搜索點預測、菱形搜索模式和搜索中止算法方面進行了優(yōu)化，減少了SAD計算的內(nèi)部冗余和搜索區(qū)域中不相關的塊匹配計算，同時采用自適應搜索模式選擇技術減少運輸復雜度。實驗結(jié)果表明：提出的改進菱形搜索算法適合各種運動類型的視頻序列，特別適用于運動變化劇烈的序列，相比于FS算法，能夠在PSNR值和碼率值極其接近于FS算法的情況下對所有序列的MET減少約95%，大大減少運動估計時間。

視頻壓縮；H.264；運動估計；菱形搜索；塊匹配

在幀間預測編碼中，由于活動圖像鄰近幀中的景物存在著一定的相關性。因此，可將活動圖像分成若干塊或宏塊，并設法搜索出每個塊或宏塊在鄰近幀圖像中的位置，并得出兩者之間的空間位置的相對偏移量，得到的相對偏移量就是通常所指的運動矢量，得到運動矢量的過程被稱為運動估計[1-2]。H.264是ITU-T的聯(lián)合視頻組(joint video team，JVT)開發(fā)的一個新的數(shù)字視頻編碼標

準，因壓縮比和網(wǎng)絡親和性好而被廣泛使用，但是，H.264標準與其他標準相比需要消耗更多的運動估計時間和資源[3-4]。運動估計算法決定了視頻壓縮的性能和速度，是視頻壓縮編碼系統(tǒng)中的關鍵環(huán)節(jié)，因此尋求更高效的運動估計算法成了節(jié)省編碼時間和資源，提高編碼質(zhì)量的重中之重。通常情況下，可以將快速算法分為兩類：基于模板的運動估計算法和基于全局的運動估計算法[5-7]?；谌值倪\動估計算法主要是針對基于模板的運動估計算法容易出現(xiàn)估計精度下降的問題而提出的，雖然其搜索速度比全搜索算法(full search，F(xiàn)S)快，但相對于三步搜索法(three-step search，TSS)[8]、新三步搜索法(novel three-step search，NTSS)[9]、六邊形搜索法(Hexagonal block search algorithm，HEXBS)[10]、菱形搜索法(diamond search，DS)[11]和十字搜索法(cross diamond search，CDS)[12]等基于模板的運動估計算法，其運算復雜度增加。其中，DS法由于充分考慮到實際視頻序列中物體在水平和垂直兩個方向運動的概率較其他方向大，圖像頻譜多呈菱形分布，因此是目前綜合性能較好的快速搜索算法。但是，在傳統(tǒng)的DS算法中，如果單獨采用小菱形搜索模式(small diamond search pattern，SDSP)可以減少運算復雜度，但是在快速運動或是不規(guī)則視頻序列中搜索容易落入局部最優(yōu)。若單獨采用大菱形搜索模式(large diamond search pattern，LDSP)，雖然可以解決搜索落入局部最優(yōu)的問題，但由于搜索點的增加使得運算量大幅增加。因此，本文在傳統(tǒng)DS法的基礎上，引入起始搜索點預測、自適應搜索模式選擇和動態(tài)中止搜索算法，可提高運動估計運算速度且不降低估計精度。

1 傳統(tǒng)菱形搜索算法

DS算法以搜索模板形狀而得名，具有簡單、魯棒、高效的特點，是現(xiàn)有性能最優(yōu)的快速搜索算法之一。其基本思想是利用搜索模板的形狀和大小對運動估計算法速度及精度產(chǎn)生重要影響的特性。在搜索最優(yōu)匹配點時，選擇小的搜索模板可能會陷入局部最優(yōu)，選擇大的搜索模板則可能無法找到最優(yōu)點。因此DS算法針對視頻圖像中運動矢量的基本規(guī)律，選用了兩種形狀大小的搜索模板。

它分為9點LDSP和5點SDSP，如圖1(a)、(b)所示。DS算法考慮到實際視頻序列中物體在水平和垂直兩個方向運動的概率較其他方向大，且圖像頻譜多呈菱形分布。

圖1 菱形搜索算法

搜索遵循先粗后精的原則，先用LDSP進行粗定位，避免陷入局部最優(yōu)，然后使用SDSP搜索粗定位中最小絕對誤差和(sum of absolute difference，SAD)值點的周圍4個點，此時得到的SAD值最小點便是最優(yōu)匹配點。DS算法搜索過程如下：開始階段先重復使用LDSP，直到最佳匹配塊落在大菱形中心。由于LDSP步長大，因而搜索范圍廣，可實現(xiàn)粗定位，使搜索不會陷于局部最小，當粗定位結(jié)束后，可認為最優(yōu)點就在LDSP 周圍8個點所圍菱形區(qū)域中。然后再使用SDSP來實現(xiàn)最佳匹配塊的準確定位，以不產(chǎn)生較大起伏，從而提高運動估計精度。

2 改進菱形搜索算法

2.1 起始搜索點預測和自適應搜索模式選擇

圖2 不同運動序列運動矢量分布特性圖

一般情況下視頻序列是柔和平滑的，其意味著全局最優(yōu)運動矢量通常位于或者接近于搜索中心。圖2給出了FS算法對6種不同運動類型的視頻序列的全局最優(yōu)運動矢量的分布概率，對于慢

速運動視頻序列如：Akiyo、Coast-Guard和News，全局最優(yōu)運動矢量幾乎都分布在搜索窗中心位置，即全局最優(yōu)運動矢量的零偏置特性。而對于中速和快速運動視頻序列如：Mobile、Foreman和Football，全局最優(yōu)運動矢量的位置與搜索窗中心的距離有所增加，即全局最優(yōu)運動矢量的中心偏置特性。

在傳統(tǒng)的DS算法中，如果單獨采用SDSP可以減少運算復雜度，但是在快速運動或是不規(guī)則視頻序列中搜索容易落入局部最優(yōu)。而如果單獨采用LDSP，雖然可以解決搜索落入局部最優(yōu)的問題，但是由于搜索點的增加從而使得運算量大幅增加。為了提高視頻的壓縮效率，可根據(jù)當前塊的運動快慢來決定搜索模式是采用 LDSP還是SDSP，如果為慢速運動序列可采用 SDSP，否則采用LDSP。這是由于相鄰塊之間具有很強的相關性，當前塊的運動類型可以很容易的根據(jù)已編碼塊的運動類型進行估計。確定當前塊的運動類型可以通過采用式(1)的中值函數(shù) Median ｛｝，根據(jù)相鄰塊最小全局運動矢量計算閾值 TP進行判斷，其中GMVmin()表示各相鄰塊 m的最小全局運動矢量；K為用于計算 TP的相鄰塊數(shù)量。若 TP值較小，則說明匹配塊接近于搜索中心，反之則遠離搜索起始中心。

運動估計的操作數(shù)可以通過式(2)進行計算，其中，l1和 l2表示當前塊和參考塊劃分的行數(shù)和列數(shù)；S表示搜索窗范圍內(nèi)的搜索點數(shù)量；Sub、Abs和Add分別表示快匹配原則中絕對誤差和SAD計算中減法、絕對值和加法的計算次數(shù)。

本文中，采用動態(tài)內(nèi)部搜索中止算法(dynamic internal search stopping algorithm，DISS)減少式(2)中的Sub、Abs和Add操作，采用 DISS減少(2)中的搜索點數(shù)量S，即排除搜索窗中不會成為最佳匹配塊的候選塊。

2.2 動態(tài)內(nèi)部搜索中止算法

DISS主要用于減少候選塊運動估計中減法、絕對值和加法計算次數(shù)，即式(2)中］項的計算次數(shù)。為達到此目的，需要引入DISS閾值 T(DISS)(j)。首先，將當前幀中的當前塊和參考幀中的候選塊按行數(shù)分組，每組包含的行數(shù)為2l，其中l(wèi)= 0,1,2,···,l14；然后，從第一組開始，計算當前塊和候選塊的SAD部分累加之和。DISS閾值 T(DISS)(j)的表達如式(3)所示，其中 SADmin表示搜索窗中已搜索塊與當前塊的最小SAD；j表示所累加組的序號數(shù)；P表示該組的像素數(shù)。

比較計算所得的 SAD部分累加之和與T(DISS)(j)的大小。若SAD部分累加之和小于T(DISS)(j)，則繼續(xù)累加下一組的 SAD作為新的SAD部分累加之和，并計算相應的閾值 T(DISS)(j)，然后再進行比較。若 SAD部分累加之和大于T(DISS)(j)，則停止計算，然后對搜索窗中的下一候選塊重復上述步驟，即候選塊和當前塊進行分組、累加SAD、比較SAD與相應 T(DISS)(j)的大小關系。

但在實際操作中如果用式(3)所計算的閾值與SAD部分累加之和進行比較，在算法執(zhí)行的初始階段容易出現(xiàn)錯誤的比較，這是由于參考幀和當前幀的參考宏塊和當前宏塊內(nèi)部的灰度值是不均勻分布的，因此可能會出現(xiàn)第一組的SAD部分累加之和大于 T(DISS)(1)，而第一組和第二組兩組的SAD 部分累加之和小于 T(DISS)(2)，在這種情況下候選塊的匹配就出現(xiàn)了錯誤。為避免上述情況的發(fā)生，需要在計算式(3)的 T(DISS)(j)時，在等式右邊加上控制參數(shù)φ，其表達式為式(4)：

參數(shù)φ選取的越大，則發(fā)生錯誤匹配的概率越小，從而得到最優(yōu)全局運動矢量的概率越大，但是如果參數(shù)φ選取得過大，會使得運算的復雜度增大，削弱了DISS算法的作用。通過驗證發(fā)現(xiàn)，并不是所有候選塊都會出現(xiàn)上述錯誤匹配，其錯誤主要是由于SAD累加的初始組選擇。由此可知，參數(shù)φ隨著計算組數(shù)的增大而減小，因而在計算閾值 T(DISS)(j)時需要在式(3)中引入控制參數(shù)ω，參數(shù)ω的表達式為式(5)，其中N表示宏塊所劃分的總組數(shù)：

綜上所述，閾值 T(DISS)(j)的計算表達式可由式(6)表示，即在初始組的閾值 T(DISS)(j)計算時控制參數(shù)ω需較小，以有效避免匹配錯誤的發(fā)生，隨著計算組數(shù)的增加，控制參數(shù)ω逐漸變大，使得在 T(DISS)(j)計算中則表現(xiàn)為 T(DISS)(j)小于SAD部分累加之和的概率增大，從而有效保證了DISS算法的效率。

2.3 改進菱形搜索算法的步驟

改進DS算法具體的計算流程如圖3所示。

圖3 動態(tài)內(nèi)部中止搜索算法流程圖

具體改進后的DS算法的步驟如下：

步驟1. 計算搜索起始中心處當前塊與候選塊的絕對誤差和 SAD，同時計算動態(tài)零運動預判閾值 T(DESS)(i)和自適應搜索模式選擇閾值 TP，當前塊與候選塊絕對誤差和 SAD小于外部閾值T(DESS)(i)，則搜索中止，并輸出位于搜索起始中心的候選塊為最優(yōu)匹配塊。

步驟2. 利用步驟1計算得到的 TP確定采用何種初始搜索模式，如果 TP＜1，則進入步驟3，否則進入步驟4。

步驟3. 在DESS和DISS技術的基礎上，對SDSP中的4個搜索點逐一進行檢查直到得到最小SAD，從而減少運動估計的計算操作。如果在SDSP中的所有搜索點都不是最佳匹配塊，則檢查最小SAD的點，若該點位于SDSP的中心，則停止搜索，否則將該點作為初始搜索中心，然后重復步驟3。

步驟4. 在DESS和DISS技術的基礎上，對LDSP中的8個搜索點逐一計算，如果所有搜索點均不是最佳匹配塊，則對將最小SAD點作為新的初始搜索中心重復步驟 4。否則，如果最小 SAD點位于初始搜索中心，則以該點為SDSP模式的中心點進行搜索。

3 測試實驗及結(jié)果

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

從表1可以看出：

(1) 針對不同運動的劇烈程度和不同格式大小的所有序列，F(xiàn)S算法的PSNR值均高于其他5種算法，說明 FS算法的準確度最高。本文改進DS算法相對于 FS算法的 PSNR值只減小了0.06 dB，約0.155 6%，說明本文算法的準確度基本達到了最優(yōu)水平。

表1 本文算法的視頻序列測試實驗結(jié)果

(2) 本文改進DS算法相對于FS算法對運動變化緩慢的Akiyo和Foreman的BR值減小明顯，約 0.733 0%，說明其對運動變化緩慢的序列具有顯著性。

(3) 本文改進DS算法適合各種運動類型的視頻序列，特別適用于運動變化劇烈的序列，并且能夠在PSNR值和BR值極其接近于FS算法的情況下，相比于FS算法，對所有序列的MET減少約95%，大大減少了運動估計時間。

4 結(jié) 論

(1) 本文在傳統(tǒng)DS算法的基礎上提出了一種改進DS算法，該算法主要是通過引入動態(tài)閾值，從起始搜索點開始預測、在DS模式和搜索中止算法方面進行優(yōu)化，實現(xiàn)了根據(jù)當前塊的運動快慢來決定采用LDSP還是SDSP的自適應搜索。

(2) FS算法的準確度最高，本文提出的改進DS算法相對于 FS算法的 PSNR值只減小了0.06 dB，約0.155 6%，說明本文算法的準確度基本達到了最優(yōu)水平，同時，本文算法相對于FS算法對運動變化緩慢的Akiyo和Foreman的BR值減小明顯，約 0.733 0%，說明本文算法對運動變化緩慢的序列具有顯著性。

(3) 本文提出的自適應DS算法適合各種運動類型的視頻序列，特別適用于運動變化劇烈的序列，并且能夠在PSNR值和BR值極其接近于FS算法的情況下，相比于 FS算法，對所有序列的MET減少約95%，大大減少了運動估計時間。

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

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

[3] 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.

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

[5] 楊曉琴, 季曉勇. 基于H.264的快速運動估計算法[J].計算機工程與應用, 2011, 47(4)： 174-176.

[6] 李子印, 楊 齊. 基于運動信息自適應的快速運動估計算法[J]. 中國圖象圖形學報, 2012, 17(9)：1069-1074.

[7] 陳 虎, 張 萍, 程 建, 等. 一種雙模式的運動估計算法[J]. 計算機應用研究, 2011, 28(2)： 746-748.

[8] 唐澤鵬, 秦 雷, 朱秀昌, 等. 運動估計算法分析[J].數(shù)字電視與數(shù)字視頻, 2001, 14(10)： 16-19.

[9] Li Renxiang, Zeng Bing, Liu 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.

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

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

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

Improved Diamond Motion Estimation Algorithm Based on Search Prediction and Threshold Decision

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

To improve the compression efficiency of the video, a self-adaptive diamond search algorithm is put forward based on traditional diamond search algorithm. The algorithm is improved in the prediction of the beginning search spot, diamond search mode and search suspended algorithm by bringing in dynamic threshold. It realizes the self-adaptive search, which reduces the internal redundant SAD operation and skips all the irrelevant blocks in the search area. The experiment result shows that the self-adaptive diamond search algorithm suits all kinds of motional video sequence, especially those sequences changing poignantly in movement. Comparing to the FS algorithm, the improved algorithm decreases approximately 95% of the motion estimation time (MET) of all the sequences under the condition that the PSNR and the code rate value are very close to FS algorithm. The motion estimation time is greatly decreased.

video compression; H.264; motion estimation; diamond search; block matching

TP 391

A

2095-302X(2015)04-0576-05

2014-05-26；定稿日期：2014-12-27

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