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

重慶大學(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)動(dòng)估計(jì)的結(jié)果直接影響最終超分辨率圖像的質(zhì)量，是超分辨率圖像重構(gòu)過(guò)程中一個(gè)極其重要的環(huán)節(jié)。所謂運(yùn)動(dòng)估計(jì)就是估計(jì)同一個(gè)被觀測(cè)物體在相鄰兩幀圖像中的坐標(biāo)差，即該對(duì)象在這兩幀圖像中的運(yùn)動(dòng)偏移矢量。然而運(yùn)動(dòng)估計(jì)的病態(tài)性（即可以使用不同運(yùn)動(dòng)矢量來(lái)描述同一副圖像）導(dǎo)致運(yùn)動(dòng)估計(jì)成為數(shù)字圖像處理領(lǐng)域中一大難題。

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

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

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

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

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

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

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

2 十字菱形搜索法簡(jiǎn)介

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

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

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

圖1 十字菱形搜索模式

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

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

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

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

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

3.1 圖像金字塔

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

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

3.2 高斯金字塔

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

本文通過(guò)對(duì)十字形搜索算法的研究，總結(jié)十字形搜索算法可改進(jìn)的方向，在引入高斯金字塔的思想上，提出了改進(jìn)的小十字形搜索算法INSCS。這里的小十字搜索是指在搜索時(shí)只使用小十字搜索模式（圖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ù)采用絕對(duì)誤差和SAD的情況下，選取512作為零運(yùn)動(dòng)塊預(yù)判閾值可以提高運(yùn)動(dòng)估計(jì)的速度，同時(shí)匹配效果并沒(méi)有受到太大的影響。在這里直接使用512作為判斷搜索是否終止的閾值。實(shí)驗(yàn)表明，在保持圖像質(zhì)量的前提下能顯著提高搜索效率。

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

圖3 本文算法流程圖

算法過(guò)程可描述如下：

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

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

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

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

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

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

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

為了證明本文算法的有效性，將INSCS算法（本文改進(jìn)的小十字形搜索算法）與DS（菱形搜索）算法、NCS（十字搜索算法）以及AHSDS（自適應(yīng)六邊形和小菱形搜索算法）[14]在搜索點(diǎn)數(shù)、峰值信噪比，以及運(yùn)行時(shí)間（為整個(gè)圖像序列運(yùn)行的Matlab的CPUtime）方面進(jìn)行實(shí)驗(yàn)對(duì)比。算法運(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)分為兩個(gè)部分：第一部分將算法應(yīng)用于單張圖片及其衍生圖像上；第二部分將算法應(yīng)用于標(biāo)準(zhǔn)圖像集上。兩組實(shí)驗(yàn)如下：

第一組實(shí)驗(yàn)，對(duì)單個(gè)圖像即圖4進(jìn)行對(duì)比實(shí)驗(yàn)，具體操作為對(duì)圖像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)測(cè)試序列，序列格式為QCIF。第一組測(cè)試序列長(zhǎng)度為61幀 Graden-gray 352×240Ras序列圖像，其中Garden-gray序列主要是鏡頭的平移運(yùn)動(dòng)。第二組測(cè)試序列為33幀Caltrain序列圖像，其中包含鏡頭平移以及內(nèi)部對(duì)象的移動(dòng)。第三組測(cè)試序列為60幀F(xiàn)ootball序列，主要包含內(nèi)部對(duì)象的移動(dòng)。第四組為75幀Susie序列，包含有局部物體運(yùn)動(dòng)。第五組為148幀Tennis序列，包含劇烈的場(chǎng)景運(yùn)動(dòng)。

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

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

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

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

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

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

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

5 結(jié)論

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

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

[2]吳通.基于H.264塊匹配運(yùn)動(dòng)估計(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)動(dòng)估計(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)動(dòng)搜索算法[J].微計(jì)算機(jī)信息，2006，22（8）：1304-1310.

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

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

[10]王純，孫中華，賈克斌.一種綜合搜索策略的快速運(yùn)動(dòng)估計(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)型邊緣檢測(cè)算法[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)動(dòng)估計(jì)自適應(yīng)快速搜索算法研究[J].計(jì)算機(jī)工程與應(yīng)用，2013，49（6）：183-186.