一種改進的運動估值塊匹配準則

1、一種改進的運動估值塊匹配準則許 磊，王匯源 時間:2008年05月16日 字 體: 大 中 小關鍵詞:摘要：關鍵詞：基于塊運動模型的塊匹配算法簡單、高效且易于硬件實現(xiàn)，已被很多國際視頻編碼標準采納，并得到廣泛的應用12。其主要思想是把編碼幀分成若干個大小相同的圖像塊，對每個圖像塊，根據塊匹配算法在預測幀中尋找最佳的匹配塊，然后對其殘差進行編碼。編碼殘差系數所用的比特數和編碼運動矢量所用的比特數越少，則整體的編碼效率就越高。本文在塊運動模型的基礎上，分析了當前使用的塊匹配準則的優(yōu)缺點，提出一種改進的塊匹配準則約束條件求和絕對差匹配準則(RCSAD)。1 塊匹配準則在現(xiàn)有搜索算法中，最常用的匹配準

2、則有如下幾種：(1)歸一化互相關函數準則NCCF由以上公式可知，前兩種準則得到的運動位移矢量要比按平均絕對幀差準則及求和絕對差值準則得到的結果更加準確,但是函數的計算量很大，從硬件使用的角度來說，目前尋找匹配塊一般使用SAD準則。2 SAD準則存在的問題這里涉及一個基本假設，即SAD最小值能否準確地反映真實運動和圖像細節(jié)。舉一簡單例子說明SAD塊匹配準則的不足。圖1是一個44待匹配像素塊A和兩個參考匹配像素塊XY。采用SAD匹配準則進行最簡單可靠的全搜索法，對搜索范圍內的每一點都計算MAD值。像素塊A與像素塊X、Y之間的SAD值：SAD(A，X)=80 SAD(A，Y)=70顯然，SAD(A，

3、X)SAD(A，Y)，按SAD匹配準則，Y像素塊應為最佳匹配塊。但從主觀質量評價看，最佳匹配塊不是Y而是X。實際上，像素塊A和X都是圖像的平坦區(qū)域，它們對應像素值之差均在5以內，人眼主觀感覺不出它們之間的明顯差別，而像素塊Y卻存在一條明顯的黑色豎線，與A的主觀感覺相差甚大。從上述簡單例子可以看到，SAD準則只是簡單地將像素塊之間的差異進行累加，并以此效果作為匹配程度的判斷準則，而未考慮兩匹配像素塊中各像素之間的差值大小程度，忽視了像素塊內的細節(jié)特征，因而造成了主、客觀評價的差異，帶來了運動估值的不精確。3 約束條件求和絕對差匹配準則3.1 SAD塊匹配準則的優(yōu)化L(x)表示在以上兩子塊內對應像

4、素的預測殘值為x的數量(x0，255，x為整數)。則在兩子塊完全匹配的情況下， nL-x的分布有以下結果：nL(x)=MN，x=0nL(x)=0，x=(1，255)? (5)一般地，塊RB是搜索區(qū)SR中的任意一個待匹配塊，則有：nL(x)=pabs(i，j)=x(MN)abs(i，j)0，255i0，M-1，j0，N-1式中nL(x)=pabs(i，j)=x為預測殘差值為x的概率密度函數?？捎妙A測殘差的分布圖來描述nL-x分布，其預測殘差分布圖如圖3所示。圖中，曲線1已經歸一化。由圖3可知：從統(tǒng)計的觀點來看，2個塊越匹配，其分布曲線的峰值越趨向于0點(即分布曲線的中心點越趨于x軸的原點)，上述

5、分布曲線越趨于呈現(xiàn)正脈沖特性(即標準方差越小)。理論上，當子塊RB與子塊CB完全匹配時(即兩子塊的像素一一對應)，則其nL-x的分布圖退化為位于原點的幅度為MN的一條豎線，即此時分布圖描述的是式(5)的情況。類似于在分布函數中取方差的方法，如果在橫軸x方向上對分布曲線3取門限T(T為整數，如假設某最佳匹配塊使預測殘差分布的均值為0，方差為0，可令T= 0+20 ，或視情況而定)，且令：則式(6)的物理意義為子塊RB和子塊CB中對應像素之差的絕對值比T小的所有數目。由統(tǒng)計特性可知，在相同的門限T下，如果某待匹配的子塊越趨近于預測子塊CB，則其對應的Q值越大。反之，在一確定的T值下，Q越大，則塊R

6、B與塊CB越匹配。基于以上的結論，提出如下的算法：如圖2所示，在搜索區(qū)SR中尋找預測塊CB的匹配塊，如果采用FS算法，并先選定一合適的門限T，設有一組二維數組Q(2W+1)(2W+1)變量，在每次塊運算時，對數組中的每個變量Q(i，j)(i-W，W，j-W，W)有：當 CB(i，j)-RB(x+i，y+j)Tx0，M-1，y0，N-1時，Q(i，j)=Q(i，j)+1? (7)這樣，在FS搜索完畢后，可得到相應的(2W+1)2個Q(i，j)值。之后，在數組變量中尋找其最大值：則Q(I，J)與對應的子塊為所要尋找的最佳匹配塊，(I，J)即為運動矢量。3.2 最佳匹配判決方法在運動估值塊匹配搜索過

7、程中，最早被提出的搜索算法是全搜索法FS347。在搜索過程中，無論使用哪種搜索算法進行搜索匹配，往往存在一些像素點求得的匹配值是相等的。在這種情況下，如何確定此時哪一點對應最佳運動矢量或下一步搜索的中心點，成為一個比較棘手的問題。菱形搜索示意圖如圖4 所示。在使用菱形搜索法時，若搜索點A和B的SAD值相等，如何進行下一步的搜索。如果使用MSD或其他準則進行二次判別，會大大增加算法的復雜性和一致性，也失去了SAD準則本來的意義。該問題得不到解決，SAD準則運動估值算法的穩(wěn)定性就得不到保證。對此，提出了如下的約束判別方法：假設子塊CB為當前幀中待匹配的子塊，運動矢量為(ik，jk)；塊RB為與CB

8、相鄰的子塊，運動矢量為(ik，jk)。根據上節(jié)中得到的SAD優(yōu)化準則求出CB在參考幀上對i、j位移塊的匹配像素數Q(i，j)，若有位移值I、J使當且僅當有惟一的I、J使上式成立時，位移矢量ik=I，jk=J。若有iu，ju，u=1，2，U0同時滿足(9)式，根據相鄰空間塊對應的運動矢量存在高度的空間相關性，特別是屬于統(tǒng)一對象的塊運動保持一致的可能性更大，計算選取與d(imin，jmin)對應的位移矢量(imin，jmin)為最佳運動矢量。即在SAD優(yōu)化準則意義下，若多個不同位移的像素點有相同最小風險時，選擇與相鄰塊相對位移最小的像素點為當前塊的最佳匹配點。顯而易見，這一判決準則不僅顯著提高了判

9、決的惟一性，而且由于在相同風險下選擇最小相對位移使得相鄰圖像區(qū)域的運動矢量場的一致性得到進一步提高。將這種基于SAD優(yōu)化準則下的最佳匹配判決方法稱為約束條件求和絕對差匹配準則RCSAD(Restrictive Conditional SAD)。4 實驗結果為比較RCSAD與SAD、MSE準則下塊匹配算法的性能，分別運用三種準則對標準測試序列Miss America (QCIF格式)進行運動位移矢量估值實驗。對每個1616的子塊進行運動矢量估值，預測誤差進行二維離散余弦變換(DCT)，并將DCT 系數量化，對量化后的系數采用變字長碼編碼。圖5給出了三種匹配準則下，測試序列Miss America

10、各圖像幀Nk(k=1，2，45)的預測峰值信噪比PSNR曲線?？梢钥闯?，約束條件求和絕對差準則的性能(視頻序列的圖像質量)優(yōu)于均方誤差準則，比求和絕對差準則有了很大提高。?表1是按三種準則進行運動位移估值時平均每個子塊所用運算量與運算時間的統(tǒng)計表。輸入圖像序列為標準測試序列Miss America，子塊大小為1616，搜索范圍水平方向是1615，豎直方向是1615，搜索方法是全搜索法和菱形搜索法。RCSAD準則的運算主要為加減運算與絕對值運算。由表1可以看出，RCSAD準則運算量約為MSE準則的10%，運算速度約為MSE的4倍，從而使整個匹配準則的效率有了較大的提升。本文在塊運動模型上實現(xiàn)了一

11、種低計算復雜度的運動估值匹配準則RCSAD。實驗證明，該準則不但獲得了優(yōu)于MSE準則的仿真性能，而且將運動估值的計算量大大降低。若將高速搜索算法集成到本文提出的方法中，還可以使計算量進一步地降低。該準則復雜度低，魯棒性強，易于硬件實現(xiàn)，可用于移動終端的實時視頻編碼系統(tǒng)。參考文獻1 Fukunaga S，Nakaya Y，Nagumo T.MPEG-4 video verification model version 14.0S.ISO/IEC JTCI/SC29/WG11 MPEG 1999/N2932，19992 MPEG-4 Optimization model version 1.0S.

12、ISO/IEC JTCI/SC29/WG11 MPEG 2000/N3324，20003 Tourapis A M，Au O C，Liou M L.An advanced zonal block based algorithm for motion estimation.In：IEEE International conference on image processing proceedings，Kobe，Japan，19994 Koga T，Linuma K，Hirano A.Motion compensated interframe coding for video conferencing.In：Proc Nat telecommun Conf.New Orleans，19815 Li R，Zeng B，liou M L.A new three-step search algorithm for block motion esti- mation.IEEE Trans Circuits Systems for Video Technology，1994；4(4)：4384426 Po M L，Ma C W.A novel four-step search algorithm for fast block motion estim