引入搜索預(yù)測與閾值決策的改進(jìn)菱形運(yùn)動估計(jì)算法

劉 艷

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

引入搜索預(yù)測與閾值決策的改進(jìn)菱形運(yùn)動估計(jì)算法

劉 艷

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

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

視頻壓縮；H.264；運(yùn)動估計(jì)；菱形搜索；塊匹配

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

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

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

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

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

圖1 菱形搜索算法

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

2 改進(jìn)菱形搜索算法

2.1 起始搜索點(diǎn)預(yù)測和自適應(yīng)搜索模式選擇

圖2 不同運(yùn)動序列運(yùn)動矢量分布特性圖

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

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

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

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

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

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

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

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

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

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

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

2.3 改進(jìn)菱形搜索算法的步驟

改進(jìn)DS算法具體的計(jì)算流程如圖3所示。

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

具體改進(jìn)后的DS算法的步驟如下：

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

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

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

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

3 測試實(shí)驗(yàn)及結(jié)果

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

從表1可以看出：

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

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

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

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

4 結(jié) 論

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

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

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

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

[2] 周 芳, 蔣建國, 王培珍. 一種改進(jìn)的視頻序列超分辨率重建算法及應(yīng)用[J]. 工程圖學(xué)學(xué)報(bào), 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的復(fù)雜度-失真最優(yōu)的運(yùn)動估計(jì)算法[J]. 計(jì)算機(jī)工程, 2007, 33(9)： 228-230.

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

[6] 李子印, 楊 齊. 基于運(yùn)動信息自適應(yīng)的快速運(yùn)動估計(jì)算法[J]. 中國圖象圖形學(xué)報(bào), 2012, 17(9)：1069-1074.

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

[8] 唐澤鵬, 秦 雷, 朱秀昌, 等. 運(yùn)動估計(jì)算法分析[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–)，女，山西平陸人，講師，碩士。主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用。E-mail：shxliuyan0359@163.com