一種改進(jìn)的運(yùn)動(dòng)估值塊匹配準(zhǔn)則

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

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

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

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

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

6、B與塊CB越匹配?；谝陨系慕Y(jié)論，提出如下的算法：如圖2所示，在搜索區(qū)SR中尋找預(yù)測(cè)塊CB的匹配塊，如果采用FS算法，并先選定一合適的門(mén)限T，設(shè)有一組二維數(shù)組Q(2W+1)(2W+1)變量，在每次塊運(yùn)算時(shí)，對(duì)數(shù)組中的每個(gè)變量Q(i，j)(i-W，W，j-W，W)有：當(dāng) CB(i，j)-RB(x+i，y+j)Tx0，M-1，y0，N-1時(shí)，Q(i，j)=Q(i，j)+1? (7)這樣，在FS搜索完畢后，可得到相應(yīng)的(2W+1)2個(gè)Q(i，j)值。之后，在數(shù)組變量中尋找其最大值：則Q(I，J)與對(duì)應(yīng)的子塊為所要尋找的最佳匹配塊，(I，J)即為運(yùn)動(dòng)矢量。3.2 最佳匹配判決方法在運(yùn)動(dòng)估值塊匹配搜索過(guò)

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

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

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

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

11、種低計(jì)算復(fù)雜度的運(yùn)動(dòng)估值匹配準(zhǔn)則RCSAD。實(shí)驗(yàn)證明，該準(zhǔn)則不但獲得了優(yōu)于MSE準(zhǔn)則的仿真性能，而且將運(yùn)動(dòng)估值的計(jì)算量大大降低。若將高速搜索算法集成到本文提出的方法中，還可以使計(jì)算量進(jìn)一步地降低。該準(zhǔn)則復(fù)雜度低，魯棒性強(qiáng)，易于硬件實(shí)現(xiàn)，可用于移動(dòng)終端的實(shí)時(shí)視頻編碼系統(tǒng)。參考文獻(xiàn)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