劉 艷

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

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

劉 艷

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

為了提高視頻的壓縮效率，在傳統(tǒng)菱形搜索算法基礎(chǔ)上提出一種改進(jìn)菱形搜索算法。該算法通過(guò)引入動(dòng)態(tài)閾值，在起始搜索點(diǎn)預(yù)測(cè)、菱形搜索模式和搜索中止算法方面進(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)動(dòng)類(lèi)型的視頻序列，特別適用于運(yùn)動(dòng)變化劇烈的序列，相比于FS算法，能夠在PSNR值和碼率值極其接近于FS算法的情況下對(duì)所有序列的MET減少約95%，大大減少運(yùn)動(dòng)估計(jì)時(shí)間。

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

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

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

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

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

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

圖1 菱形搜索算法

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

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

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

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

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

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

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

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

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

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

DISS主要用于減少候選塊運(yùn)動(dòng)估計(jì)中減法、絕對(duì)值和加法計(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；然后，從第一組開(kāi)始，計(jì)算當(dāng)前塊和候選塊的SAD部分累加之和。DISS閾值 T(DISS)(j)的表達(dá)如式(3)所示，其中 SADmin表示搜索窗中已搜索塊與當(dāng)前塊的最小SAD；j表示所累加組的序號(hào)數(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ì)算，然后對(duì)搜索窗中的下一候選塊重復(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)部的灰度值是不均勻分布的，因此可能會(huì)出現(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)動(dòng)矢量的概率越大，但是如果參數(shù)φ選取得過(guò)大，會(huì)使得運(yùn)算的復(fù)雜度增大，削弱了DISS算法的作用。通過(guò)驗(yàn)證發(fā)現(xiàn)，并不是所有候選塊都會(huì)出現(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 動(dòng)態(tài)內(nèi)部中止搜索算法流程圖

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

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

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

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

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

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

本文在JM12.4的基礎(chǔ)上進(jìn)行了基于改進(jìn)DS算法的視頻序列測(cè)試實(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)緩慢的序列。將本文算法與幾種常見(jiàn)的運(yùn)動(dòng)估計(jì)算法比較，評(píng)價(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) 針對(duì)不同運(yùn)動(dòng)的劇烈程度和不同格式大小的所有序列，F(xiàn)S算法的PSNR值均高于其他5種算法，說(shuō)明 FS算法的準(zhǔn)確度最高。本文改進(jìn)DS算法相對(duì)于 FS算法的 PSNR值只減小了0.06 dB，約0.155 6%，說(shuō)明本文算法的準(zhǔn)確度基本達(dá)到了最優(yōu)水平。

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

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

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

4 結(jié) 論

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

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

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

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

[2] 周 芳, 蔣建國(guó), 王培珍. 一種改進(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)動(dòng)估計(jì)算法[J]. 計(jì)算機(jī)工程, 2007, 33(9)： 228-230.

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

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

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

[8] 唐澤鵬, 秦 雷, 朱秀昌, 等. 運(yùn)動(dòng)估計(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