王 斌，何中市，伍 星，賈媛媛

重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044

1 引言

在大部分圖像數(shù)據(jù)應(yīng)用領(lǐng)域里，為了獲取高質(zhì)量圖片，常常要求獲得具有高分辨率的圖像，然而現(xiàn)實(shí)世界中，能夠獲取的多為低分辨率圖像。因此由低分辨率圖像重構(gòu)高分辨率圖像成為當(dāng)前研究的重點(diǎn)，即超分辨率圖像重構(gòu)技術(shù)。圖像運(yùn)動估計(jì)的結(jié)果直接影響最終超分辨率圖像的質(zhì)量，是超分辨率圖像重構(gòu)過程中一個極其重要的環(huán)節(jié)。所謂運(yùn)動估計(jì)就是估計(jì)同一個被觀測物體在相鄰兩幀圖像中的坐標(biāo)差，即該對象在這兩幀圖像中的運(yùn)動偏移矢量。然而運(yùn)動估計(jì)的病態(tài)性（即可以使用不同運(yùn)動矢量來描述同一副圖像）導(dǎo)致運(yùn)動估計(jì)成為數(shù)字圖像處理領(lǐng)域中一大難題。

運(yùn)動估計(jì)方法有多種，其中基于塊匹配的運(yùn)動估計(jì)[1-3]（BMA）算法由于其簡單高效，額外開銷小，易于硬件實(shí)現(xiàn)等優(yōu)點(diǎn)，成為最常見的運(yùn)動估計(jì)算法。塊匹配算法依據(jù)某個衡量準(zhǔn)則，通過在兩幅圖像之間進(jìn)行塊匹配，來尋找使得差異最小的度量，從而獲得參數(shù)估計(jì)?，F(xiàn)有的塊匹配搜索算法有很多，如全搜索算法、三步搜索、四步搜索、菱形搜索法等。

全搜索算法：全搜索算法可以獲得最佳結(jié)果。雖然它能夠找到最優(yōu)解，但其運(yùn)算量大，不利于實(shí)時的應(yīng)用。為減少運(yùn)動搜索復(fù)雜度和運(yùn)算量，研究人員相繼提出了很多基于搜索模式的快速搜索算法，如三步搜索、四步搜索、菱形搜索等。

三步搜索算法[4]：三步搜索算法是一種快速搜索算法。三步搜索算法因其簡單性和有效性被廣泛使用，但容易陷入局部最優(yōu)。

三步搜索、四步搜索都假定運(yùn)動矢量是均勻分布，不符合實(shí)際情況。一些新的改進(jìn)算法，充分考慮了真實(shí)序列的運(yùn)動矢量分布特性，在改進(jìn)搜索策略的同時提高搜索速度。如菱形搜素算法[5-6]擁有很好的匹配效果，且顯著地減少了搜索點(diǎn)數(shù)，提高了運(yùn)動估計(jì)速度。

菱形算法由于其較為優(yōu)越的綜合性能被MPEG國際標(biāo)準(zhǔn)采納并收入驗(yàn)證模型，菱形搜索算法近來有許多改進(jìn)算法的出現(xiàn)，比較出名的有十字形運(yùn)動搜索算法[7]（NCS）。十字形搜索算法將菱形搜索算法的搜索模式改成了一個大的十字形搜索模式，使用十字模版搜索相對傳統(tǒng)菱形搜索模式能減少搜索點(diǎn)數(shù)，但會使圖像質(zhì)量受到一定損傷。之后在原始十字形運(yùn)動搜索算法的基礎(chǔ)上又出現(xiàn)了一些新的改進(jìn)算法，如改進(jìn)的十字-菱形搜索法[8]、改進(jìn)的十字菱形搜索算法INCDS[9]。這些算法雖然能較少搜索點(diǎn)數(shù)，但由于依賴于一些附加條件，使得算法的使用受限，如改進(jìn)的十字菱形搜索算法INCDS需要預(yù)測搜索初始點(diǎn)，且需要復(fù)雜的附加算法確定算法的提前結(jié)束等。

同時也有一些學(xué)者提出了一些綜合幾個搜索策略的搜索算法，如一種綜合搜索策略的快速運(yùn)動估計(jì)算法[10]。

運(yùn)動估計(jì)中的運(yùn)動偏移量以不同的比例集中分布在中心附近區(qū)域，且在不同半徑的搜索區(qū)域內(nèi)大多數(shù)的運(yùn)動偏移量分布在中心十字形區(qū)域上[11]，基于此本文提出了改進(jìn)的小十字形算法INSCS，是在改進(jìn)的十字形搜索的基礎(chǔ)上，引入高斯分層思想。該算法相對于當(dāng)前的一些新的且取得不錯效果的算法（如上文提到的改進(jìn)的十字形搜索算法、基于綜合搜索策略的算法），無需引入附加條件，算法實(shí)現(xiàn)過程簡單，有利于實(shí)時計(jì)算。實(shí)驗(yàn)結(jié)果顯示：改進(jìn)后的小十字形算法INSCS在保證圖像質(zhì)量的前提下，相比經(jīng)典菱形搜索算法以及十字形搜索算法，搜索點(diǎn)數(shù)更少，搜索速度更快，且圖像質(zhì)量基本保持不變。

2 十字菱形搜索法簡介

塊匹配算法的搜索模版決定了其搜索速度，十字菱形搜索算法以大十字和小十字作為搜索模版，如圖1所示，圖1（a）是大十字形搜索模式，圖1（b）是小十字形搜索模式。

十字形搜索算法的搜索過程大概可分為3步：

（1）先使用大十字模式搜索，搜索范圍為大十字模式所包含的9個點(diǎn)，對這個9個點(diǎn)分別計(jì)算以這些點(diǎn)為中心的子塊與被匹配塊之間的平均絕對距離MAD。MAD最小的點(diǎn)可能出現(xiàn)的位置有3種：若該點(diǎn)為中心點(diǎn)，結(jié)束搜索；若該點(diǎn)位于內(nèi)層的4個點(diǎn)之一，轉(zhuǎn)入第（2）步；若該點(diǎn)位于最外層的4個點(diǎn)之一，轉(zhuǎn)入第（3）步。

圖1 十字菱形搜索模式

（2）如果MAD最小的點(diǎn)位于中心點(diǎn)的水平方向上，接著搜索該點(diǎn)上面和下面的兩點(diǎn)，比較其MAD值，最小的MAD值對應(yīng)的點(diǎn)即為最佳匹配點(diǎn)，搜索結(jié)束。如果該點(diǎn)位于中心點(diǎn)的豎直方向上，則比較其和左右兩點(diǎn)的MAD值，值最小的位最佳匹配搜索點(diǎn)，搜索結(jié)束。

（3）以該點(diǎn)為中心擴(kuò)展一個新的大十字，然后轉(zhuǎn)入第（1）步。

本算法不僅兼顧到了運(yùn)動矢量的中心偏移特性，又集中了“力量”搜索中心點(diǎn)水平和豎直兩個方向上的點(diǎn)。初始步長為2，避免由于搜索過粗或過細(xì)而陷入局部最優(yōu)，大十字的迭代適合運(yùn)動范圍較大的圖像，并且可以在大十字搜索完成后，通過得到最佳點(diǎn)來減少搜索點(diǎn)數(shù)；小十字用來“查缺補(bǔ)漏”，用在最佳點(diǎn)位于其余幾個方向上時。

3 基于高斯金字塔的小十字形搜索算法

為了進(jìn)一步減少搜索點(diǎn)數(shù)，在傳統(tǒng)十字形搜索算法的基礎(chǔ)上，引入高斯金字塔思想。

3.1 圖像金字塔

由一個原始圖像經(jīng)過降采樣得到一幅下采樣圖像，再對下采樣圖像繼續(xù)降采樣，重復(fù)多次構(gòu)成一組圖像集合。如果形象的把這些圖像摞起來就像一個金字塔，即圖像金字塔，如圖2所示。

圖2 高斯金字塔分層結(jié)構(gòu)

3.2 高斯金字塔

高斯金字塔是圖像金字塔的一種，它在下采樣之前，先使用高斯平滑濾波器[12]對原圖像進(jìn)行平滑。采用Gaussian金字塔對圖像進(jìn)行重采樣，如果分辨率降低一半，那么運(yùn)動偏移值也將降低為原來的1/2，且搜索范圍也會減少，將大大提高搜索速度。構(gòu)建圖像Gaussian金字塔分兩步計(jì)算：第一步對圖像做高斯（Gaussian）平滑；第二步向下采樣，借助亞采樣可以獲得一幅圖像的一個縮略圖，但如果需要減少一幅圖像的尺寸，僅僅靠亞采樣會丟失許多信息。根據(jù)采樣定理，需要讓所有小于最短波長的1/4采樣而得到的精細(xì)結(jié)構(gòu)能通過平滑濾波器來消除掉，這樣才能獲得一幅正確的采樣圖像。假設(shè)原圖為M×N大小的圖像，金字塔第l層圖像的數(shù)字表達(dá)式，第l層是由l-1層Al-1經(jīng)Gaussian窗口函數(shù)W卷積及下采樣得到，公式如下：

其中 0≤i＜M/2l，0≤j＜N/2l，0≤l≤t（t＞0，為分解層數(shù)），窗口函數(shù)W的大小為(2s+1)×(2s+1)。

3.3 基于高斯金字塔的小十字形搜索算法

本文通過對十字形搜索算法的研究，總結(jié)十字形搜索算法可改進(jìn)的方向，在引入高斯金字塔的思想上，提出了改進(jìn)的小十字形搜索算法INSCS。這里的小十字搜索是指在搜索時只使用小十字搜索模式（圖1（b））進(jìn)行搜索，直到最小的MAD點(diǎn)出現(xiàn)在小十子模式中心點(diǎn)為止。為了進(jìn)一步提高搜索效率，在這里引入了搜索的提前終止原則。關(guān)于提前終止判定閾值的確定[13]，文獻(xiàn)采用全搜索法的實(shí)驗(yàn)結(jié)果表明，在采用像素16×16為塊大小，匹配誤差函數(shù)采用絕對誤差和SAD的情況下，選取512作為零運(yùn)動塊預(yù)判閾值可以提高運(yùn)動估計(jì)的速度，同時匹配效果并沒有受到太大的影響。在這里直接使用512作為判斷搜索是否終止的閾值。實(shí)驗(yàn)表明，在保持圖像質(zhì)量的前提下能顯著提高搜索效率。

算法基本思路為：對原圖像構(gòu)建一個兩層的高斯金字塔，下采樣后的圖像如圖2的Level-2（這里圖2中的K=2），大小為原圖的1/4。由于下采樣后圖片的粒度比原圖大1倍，這里將只使用小十字形搜索模式搜索，并引入提前終止原則，以此估計(jì)出參考圖像與待匹配圖像在Level-2層中的運(yùn)動偏移。然后以此結(jié)果作為初始值，在Level-1（也即原始圖像）中尋找最終運(yùn)動估計(jì)值，由于下采樣后，圖像大小大大減少，因此能夠有效降低了搜索范圍，減少搜索時間。該算法的流程圖如圖3所示。

圖3 本文算法流程圖

算法過程可描述如下：

（1）對原圖像進(jìn)行高斯分層，本文將下采樣因子設(shè)為2，分為兩層?？蓞⒄請D2，這里原圖即為Level-1，下采樣后的圖為Level-2，Level-2為Level-1的1/4大小。

（2）先在Level-2中使用小十字形搜索算法，并使用提前終止原則，估計(jì)出參考圖像與匹配圖像間的運(yùn)動偏移，這里使用PSNR（峰值信噪比）作為MBD的度量。PSNR計(jì)算如下：

其中n是每個采樣值的比特?cái)?shù)，在圖像處理中通常n=8。MSE（Mean Square Error）為兩幀圖像間的平方誤差，計(jì)算如下：

其中，r、c分別為圖像的行列大小，pij為參考圖像中的像素點(diǎn)，是過運(yùn)動估計(jì)后，生成圖像的像素點(diǎn)。如果Level-1即原圖的運(yùn)動估計(jì)的搜索窗口為15×15，那么在Level-2中，只需將其搜索窗口設(shè)為7×7，Level-2中的每一個7×7的窗口對應(yīng)Level-2中的一個15×15的窗口。

（3）以（2）中估計(jì)出來的運(yùn)動偏移，作為初始偏移值，然后在Level-1層即原圖中，分別計(jì)算參考圖像以及匹配圖像以初始點(diǎn)，以及以初始點(diǎn)周圍上、下、左、右4個點(diǎn)為中心的子塊間的MAD（絕對平均值），MAD最小的點(diǎn)為最終被匹配塊的中心點(diǎn)，以此算出運(yùn)動偏移值。

4 實(shí)驗(yàn)結(jié)果分析

4.1 實(shí)驗(yàn)

為了證明本文算法的有效性，將INSCS算法（本文改進(jìn)的小十字形搜索算法）與DS（菱形搜索）算法、NCS（十字搜索算法）以及AHSDS（自適應(yīng)六邊形和小菱形搜索算法）[14]在搜索點(diǎn)數(shù)、峰值信噪比，以及運(yùn)行時間（為整個圖像序列運(yùn)行的Matlab的CPUtime）方面進(jìn)行實(shí)驗(yàn)對比。算法運(yùn)行環(huán)境為 Matlab R2011b；PC配置為2 GB內(nèi)存，Intel Pentium Dual CPU E2180@2.00 GHz，Windows 7系統(tǒng)。

為了方便討論算法的有效性，將實(shí)驗(yàn)分為兩個部分：第一部分將算法應(yīng)用于單張圖片及其衍生圖像上；第二部分將算法應(yīng)用于標(biāo)準(zhǔn)圖像集上。兩組實(shí)驗(yàn)如下：

第一組實(shí)驗(yàn)，對單個圖像即圖4進(jìn)行對比實(shí)驗(yàn)，具體操作為對圖像4分別進(jìn)行[-4，-2]，[-1，-1]平移操作，得到img1（原圖）、img2、img3共3幅圖像，在3幅圖像上進(jìn)行實(shí)驗(yàn)比較。

圖4 單張圖像偏移

第二組實(shí)驗(yàn)，選擇5組典型的標(biāo)準(zhǔn)測試序列，序列格式為QCIF。第一組測試序列長度為61幀 Graden-gray 352×240Ras序列圖像，其中Garden-gray序列主要是鏡頭的平移運(yùn)動。第二組測試序列為33幀Caltrain序列圖像，其中包含鏡頭平移以及內(nèi)部對象的移動。第三組測試序列為60幀F(xiàn)ootball序列，主要包含內(nèi)部對象的移動。第四組為75幀Susie序列，包含有局部物體運(yùn)動。第五組為148幀Tennis序列，包含劇烈的場景運(yùn)動。

在實(shí)驗(yàn)結(jié)果評價過程中，使用平均絕對距離MAD（Mean Absolute Distance）作為BDM度量標(biāo)準(zhǔn)。塊的大小固定為16×16，搜索窗口為w=±7。最終的評價準(zhǔn)則為：搜索點(diǎn)越少，搜索效率越高，峰值信噪比越大，估計(jì)的效果越好。

4.2 實(shí)驗(yàn)結(jié)果與分析

第一組實(shí)驗(yàn)結(jié)果見表1，可知與傳統(tǒng)DS算法以及NCS相比，不論圖像的運(yùn)動偏差大（img2）或者?。╥mg3），本文算法INSCS在保持PNSR性能下降很少的前提下，其搜索點(diǎn)方面的性能明顯優(yōu)于傳統(tǒng)DS算法以及NDS算法；且運(yùn)動偏差越大提高效果越明顯。

表1 單張圖片實(shí)驗(yàn)結(jié)果

第二組實(shí)驗(yàn)，這里將實(shí)驗(yàn)分成兩部分：第一部分，在每一組序列圖像中，以彼此相隔2幀圖像的圖像對為參考對，即圖像對為(i，i+2)，其中i代表序列中的第i幀圖像，結(jié)果見表2，其中Caltrain-2表示幀間間隔為2的Caltrain圖像序列，其余的類似。第二部分以彼此相隔4幀圖像的圖像對為參考對，即圖像對為(i，i+4)，結(jié)果見表3，其中Caltrain-4表示幀間間隔為4的Caltrain圖像序列，其余的類似。由表2可知，在第一部分中，本文算法INSCS在搜索點(diǎn)數(shù)方面相對傳統(tǒng)DS算法以及NDS、AHSDS算法，搜索點(diǎn)個數(shù)最多減少128.24%、96.55%以及16.82%（表中的提高比例為本文算法相對于被比較算法的提高比例），而PNSR最多下降了8.91%、6.76%、4.05%。在第二部分中，見表3，搜索點(diǎn)個數(shù)最多減少168.74%、131.16%、23.91%，PNSR最多下降9.03%、7.43%、4.00%。同時由表4可知，本文算法在實(shí)際執(zhí)行時間上也明顯優(yōu)于被比較的幾種算法。

表2 第二組實(shí)驗(yàn)第一部分實(shí)驗(yàn)結(jié)果（圖像序列幀間隔為2幀）

表3 第二組實(shí)驗(yàn)第二部分實(shí)驗(yàn)結(jié)果（圖像序列幀間隔為4幀）

表4 第二組實(shí)驗(yàn)第二部分實(shí)驗(yàn)時間結(jié)果（圖像序列幀間隔為4幀）

在算法實(shí)現(xiàn)方面，本文在引入高斯金字塔后只使用了小十字搜索模式進(jìn)行搜索。相對傳統(tǒng)DS算法的大小菱形模式，十字搜素算法的大小搜索模式，以及AHSDS算法的六邊形模式和小菱形模式，在搜索模板的存儲以及搜索點(diǎn)確定方面硬件消耗更少。而且相對于AHSDS算法需要較為復(fù)雜的運(yùn)動強(qiáng)度預(yù)測估計(jì)來判斷選擇搜索模式，本文算法更為簡潔，而且由于先使用高斯金字塔將搜索粒度放大，因此相對于AHSDS算法在正常粒度下的小菱形模式搜索，能夠更加快速的定位。但是由于在搜索的第一步要建立高斯金字塔，因此在運(yùn)動偏差很小的時候，未必能夠取得最佳的效果。由表4可知，在Garden序列中（此序列主要包括小幅度平移），搜索時間不如AHDSD算法。這是由于當(dāng)本身運(yùn)動偏差很小的時候，先建立高斯金字塔的附加過程，反而減慢了搜索速度，而AHSDS算法在這種情況下能夠直接通過小菱形搜索模式進(jìn)行搜索，反而提高了搜索速度。

由上可知，總體而言，本文算法INSCS相對于傳統(tǒng)DS算法以及NDS、AHSDS算法，在保持圖像質(zhì)量的前提下，其搜索點(diǎn)效率方面有明顯的提升。而且在運(yùn)動偏移較大的時候，提高更為顯著（第二組實(shí)驗(yàn)第二部分效果好于第一部分）。

5 結(jié)論

通過對十字形搜索算法以及高斯金字塔算法的研究，提出了改進(jìn)的小十字形搜索算法，將高斯金字塔分層的思想引入到十字形搜索算法中來估計(jì)圖像運(yùn)動偏差，并通過設(shè)定閾值提前終止搜索算法。在保持圖像質(zhì)量的前提下，本文算法明顯提高了搜索效率，而且無需引入復(fù)雜的附加條件，算法實(shí)現(xiàn)簡單，便于實(shí)時計(jì)算。但是關(guān)于如何更好地處理運(yùn)動偏差很小的情況，將是后續(xù)研究的重點(diǎn)。

[1]胡喜華，劉衛(wèi)忠，鄭立新.運(yùn)動估計(jì)塊匹配算法的分析與研究[J].電視技術(shù)，2005（12）：4-6.

[2]吳通.基于H.264塊匹配運(yùn)動估計(jì)的研究[D].武漢：武漢理工大學(xué)，2008.

[3]Baby D V，Sumbramanian P，Karthikeyan C.Performance analysis of block matching algorithms for highly scalable video compression[C]//Proc of International Symposium on Ad Hoc and Ubiquitous Computing，2006.

[4]孫寧寧，樊超，許柯加，等.一種有效的三步運(yùn)動估計(jì)算法[J].紅外，2010，31（4）：37-41．

[5]Zhu S，Ma K.A new diamond search algorithm for fast block-matching motion estimation[J].IEEE Trans on Image Processing，2002，9（2）：287-290．

[6]Tham J Y，Ranganath S，Ranganath M.A novel unrestricted center-biased diamond search algorithm for block motion estimation[J].IEEE Transactions on Circuits and Sustems for Video Technology，1998，8（4）：369-377.

[7]趙躍華，雷茂惠，宋雪燁，等.一種十字形運(yùn)動搜索算法[J].微計(jì)算機(jī)信息，2006，22（8）：1304-1310.

[8]劉海華，雷奕，謝長生.改進(jìn)的十字-菱形運(yùn)動估計(jì)搜索算法研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，2007，24（8）：212-214.

[9]張萬緒，吳佳麗，趙麗平，等.改進(jìn)的十字菱形搜索算法INCDS[J].西北大學(xué)學(xué)報，2011，41（2）：226-230.

[10]王純，孫中華，賈克斌.一種綜合搜索策略的快速運(yùn)動估計(jì)算法[J].計(jì)算機(jī)應(yīng)用研究，2010，27（8）：2857-2860.

[11]Xie Chunlai，CheungChunho，Liu Weizhong.A novel adjustable multiple cross-hexagonal search algorithm for fast block motion estimation[J].Science A，2007，8（8）：1304-1310．

[12]張小洪，楊丹，劉亞威.基于Canny算子的改進(jìn)型邊緣檢測算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2003，39（29）：113-115.

[13]Nie Yao，Ma Kaikuang.Adaptive rood pattern search for fast block-matching motion estimation[J].IEEE Trans on Image Processing，2001，11（12）：1442-1449.

[14]張小紅，張東波.H.264塊運(yùn)動估計(jì)自適應(yīng)快速搜索算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（6）：183-186.