基于高斯金字塔的圖像運動估計算法

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

重慶大學 計算機學院，重慶 400044

1 引言

在大部分圖像數據應用領域里，為了獲取高質量圖片，常常要求獲得具有高分辨率的圖像，然而現實世界中，能夠獲取的多為低分辨率圖像。因此由低分辨率圖像重構高分辨率圖像成為當前研究的重點，即超分辨率圖像重構技術。圖像運動估計的結果直接影響最終超分辨率圖像的質量，是超分辨率圖像重構過程中一個極其重要的環節。所謂運動估計就是估計同一個被觀測物體在相鄰兩幀圖像中的坐標差，即該對象在這兩幀圖像中的運動偏移矢量。然而運動估計的病態性（即可以使用不同運動矢量來描述同一副圖像）導致運動估計成為數字圖像處理領域中一大難題。

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

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

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

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

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

同時也有一些學者提出了一些綜合幾個搜索策略的搜索算法，如一種綜合搜索策略的快速運動估計算法[10]。

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

2 十字菱形搜索法簡介

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

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

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

圖1 十字菱形搜索模式

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

（3）以該點為中心擴展一個新的大十字，然后轉入第（1）步。

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

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

為了進一步減少搜索點數，在傳統十字形搜索算法的基礎上，引入高斯金字塔思想。

3.1 圖像金字塔

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

圖2 高斯金字塔分層結構

3.2 高斯金字塔

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

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

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

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

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

圖3 本文算法流程圖

算法過程可描述如下：

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

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

其中n是每個采樣值的比特數，在圖像處理中通常n=8。MSE（Mean Square Error）為兩幀圖像間的平方誤差，計算如下：

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

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

4 實驗結果分析

4.1 實驗

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

為了方便討論算法的有效性，將實驗分為兩個部分：第一部分將算法應用于單張圖片及其衍生圖像上；第二部分將算法應用于標準圖像集上。兩組實驗如下：

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

圖4 單張圖像偏移

第二組實驗，選擇5組典型的標準測試序列，序列格式為QCIF。第一組測試序列長度為61幀 Graden-gray 352×240Ras序列圖像，其中Garden-gray序列主要是鏡頭的平移運動。第二組測試序列為33幀Caltrain序列圖像，其中包含鏡頭平移以及內部對象的移動。第三組測試序列為60幀Football序列，主要包含內部對象的移動。第四組為75幀Susie序列，包含有局部物體運動。第五組為148幀Tennis序列，包含劇烈的場景運動。

在實驗結果評價過程中，使用平均絕對距離MAD（Mean Absolute Distance）作為BDM度量標準。塊的大小固定為16×16，搜索窗口為w=±7。最終的評價準則為：搜索點越少，搜索效率越高，峰值信噪比越大，估計的效果越好。

4.2 實驗結果與分析

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

表1 單張圖片實驗結果

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

表2 第二組實驗第一部分實驗結果（圖像序列幀間隔為2幀）

表3 第二組實驗第二部分實驗結果（圖像序列幀間隔為4幀）

表4 第二組實驗第二部分實驗時間結果（圖像序列幀間隔為4幀）

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

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

5 結論

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

[1]胡喜華，劉衛忠，鄭立新.運動估計塊匹配算法的分析與研究[J].電視技術，2005（12）：4-6.

[2]吳通.基于H.264塊匹配運動估計的研究[D].武漢：武漢理工大學，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]孫寧寧，樊超，許柯加，等.一種有效的三步運動估計算法[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]趙躍華，雷茂惠，宋雪燁，等.一種十字形運動搜索算法[J].微計算機信息，2006，22（8）：1304-1310.

[8]劉海華，雷奕，謝長生.改進的十字-菱形運動估計搜索算法研究與實現[J].計算機應用研究，2007，24（8）：212-214.

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

[10]王純，孫中華，賈克斌.一種綜合搜索策略的快速運動估計算法[J].計算機應用研究，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].計算機工程與設計，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塊運動估計自適應快速搜索算法研究[J].計算機工程與應用，2013，49（6）：183-186.