基于塊運(yùn)動(dòng)模型的塊匹配算法簡單、高效且易于硬件實(shí)現(xiàn)，已被很多國際視頻編碼標(biāo)準(zhǔn)采納，并得到廣泛的應(yīng)用^[1][2]。其主要思想是把編碼幀分成若干個(gè)大小相同的圖像塊，對每個(gè)圖像塊，根據(jù)塊匹配算法在預(yù)測幀中尋找最佳的匹配塊，然后對其殘差進(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)則——約束條件求和絕對差匹配準(zhǔn)則(RCSAD)。
1 塊匹配準(zhǔn)則
　　在現(xiàn)有搜索算法中，最常用的匹配準(zhǔn)則有如下幾種：
　　(1)歸一化互相關(guān)函數(shù)準(zhǔn)則NCCF

　　由以上公式可知，前兩種準(zhǔn)則得到的運(yùn)動(dòng)位移矢量要比按平均絕對幀差準(zhǔn)則及求和絕對差值準(zhǔn)則得到的結(jié)果更加準(zhǔn)確,但是函數(shù)的計(jì)算量很大，從硬件使用的角度來說，目前尋找匹配塊一般使用SAD準(zhǔn)則。

2 SAD準(zhǔn)則存在的問題
　　這里涉及一個(gè)基本假設(shè)，即SAD最小值能否準(zhǔn)確地反映真實(shí)運(yùn)動(dòng)和圖像細(xì)節(jié)。舉一簡單例子說明SAD塊匹配準(zhǔn)則的不足。圖1是一個(gè)4×4待匹配像素塊A和兩個(gè)參考匹配像素塊XY。采用SAD匹配準(zhǔn)則進(jìn)行最簡單可靠的全搜索法，對搜索范圍內(nèi)的每一點(diǎn)都計(jì)算MAD值。
　　像素塊A與像素塊X、Y之間的SAD值：
　　SAD(A，X)=80 SAD(A，Y)=70
　　顯然，SAD(A，X)>SAD(A，Y)，按SAD匹配準(zhǔn)則，Y像素塊應(yīng)為最佳匹配塊。但從主觀質(zhì)量評價(jià)看，最佳匹配塊不是Y而是X。實(shí)際上，像素塊A和X都是圖像的平坦區(qū)域，它們對應(yīng)像素值之差均在5以內(nèi)，人眼主觀感覺不出它們之間的明顯差別，而像素塊Y卻存在一條明顯的黑色豎線，與A的主觀感覺相差甚大。
　　從上述簡單例子可以看到，SAD準(zhǔn)則只是簡單地將像素塊之間的差異進(jìn)行累加，并以此效果作為匹配程度的判斷準(zhǔn)則，而未考慮兩匹配像素塊中各像素之間的差值大小程度，忽視了像素塊內(nèi)的細(xì)節(jié)特征，因而造成了主、客觀評價(jià)的差異，帶來了運(yùn)動(dòng)估值的不精確。

3 約束條件求和絕對差匹配準(zhǔn)則
3.1 SAD塊匹配準(zhǔn)則的優(yōu)化
　　塊匹配算法搜索區(qū)域幾何關(guān)系如圖2所示。子塊" title="子塊">子塊CB為當(dāng)前幀中待匹配的子塊，SR為該子塊在前一相鄰幀中的搜索區(qū)間。假設(shè)子塊RB為搜索區(qū)SR中的任一子塊，如果用abs(i，j)來表示子塊RB中相對坐標(biāo)為(i，j)的像素點(diǎn)與它在CB中對應(yīng)像素點(diǎn)的差值的絕對值(以下簡稱預(yù)測殘差)，即：
　　abs(i，j)=RB(i，j)-CB(i，j) (0≤i≤M-1，0≤j≤N-1)
　　假設(shè)圖像為256灰度值，用n_L(x)表示在以上兩子塊內(nèi)對應(yīng)像素的預(yù)測殘值為x的數(shù)量(x∈[0，255]，x為整數(shù))。則在兩子塊完全匹配的情況下， n_L-x的分布有以下結(jié)果：
　　n_L(x)=M×N，x=0
　　n_L(x)=0，x=(1，…，255)????????? (5)
　　一般地，塊RB是搜索區(qū)SR中的任意一個(gè)待匹配塊，則有：
　　n_L(x)=p[abs(i，j)=x]×(M×N)
　　abs(i，j)∈[0，255]
　　i∈[0，M-1]，j∈[0，N-1]
　　式中n_L(x)=p[abs(i，j)=x]為預(yù)測殘差值為x的概率密度函數(shù)?？捎妙A(yù)測殘差的分布圖來描述n_L-x分布，其預(yù)測殘差分布圖如圖3所示。圖中，曲線1已經(jīng)歸一化。由圖3可知：
　　
　　從統(tǒng)計(jì)的觀點(diǎn)來看，2個(gè)塊越匹配，其分布曲線的峰值越趨向于0點(diǎn)(即分布曲線的中心點(diǎn)越趨于x軸的原點(diǎn))，上述分布曲線越趨于呈現(xiàn)正脈沖特性(即標(biāo)準(zhǔn)方差越小)。
　　理論上，當(dāng)子塊RB與子塊CB完全匹配時(shí)(即兩子塊的像素一一對應(yīng))，則其n_L-x的分布圖退化為位于原點(diǎn)的幅度為MN的一條豎線，即此時(shí)分布圖描述的是式(5)的情況。
　　類似于在分布函數(shù)中取方差的方法，如果在橫軸x方向上對分布曲線3取門限T(T為整數(shù)，如假設(shè)某最佳匹配塊使預(yù)測殘差分布的均值為μ₀，方差為σ₀，可令T= μ₀+2σ₀ ，或視情況而定)，且令：
　　
　　則式(6)的物理意義為子塊RB和子塊CB中對應(yīng)像素之差的絕對值比T小的所有數(shù)目。由統(tǒng)計(jì)特性可知，在相同的門限T下，如果某待匹配的子塊越趨近于預(yù)測子塊CB，則其對應(yīng)的Q值越大。反之，在一確定的T值下，Q越大，則塊RB與塊CB越匹配?；谝陨系慕Y(jié)論，提出如下的算法：如圖2所示，在搜索區(qū)SR中尋找預(yù)測塊CB的匹配塊，如果采用FS算法，并先選定一合適的門限T，設(shè)有一組二維數(shù)組Q_{(2W+1)×(2W+1)}變量，在每次塊運(yùn)算時(shí)，對數(shù)組中的每個(gè)變量Q(i，j)(i∈[-W，W]，j∈[-W，W])有：
　　當(dāng) CB(i，j)-RB(x+i，y+j)≤T
　　x∈[0，M-1]，y∈[0，N-1]時(shí)，Q(i，j)=Q(i，j)+1?????????????? (7)
　　這樣，在FS搜索完畢后，可得到相應(yīng)的(2W+1)²個(gè)Q(i，j)值。之后，在數(shù)組變量中尋找其最大值：
　　
　　則Q(I，J)與對應(yīng)的子塊為所要尋找的最佳匹配塊，(I，J)即為運(yùn)動(dòng)矢量。

3.2 最佳匹配判決方法
　　在運(yùn)動(dòng)估值塊匹配搜索過程中，最早被提出的搜索算法是全搜索法FS^[3]，雖然它的搜索精度很高，但巨大的時(shí)間開銷和計(jì)算量是實(shí)時(shí)視頻編碼系統(tǒng)不能接受的，從而出現(xiàn)了很多快速搜索算法，如二維對數(shù)法、三步法、菱形搜索" title="菱形搜索">菱形搜索法等^[4～7]。
　　在搜索過程中，無論使用哪種搜索算法進(jìn)行搜索匹配，往往存在一些像素點(diǎn)求得的匹配值是相等的。在這種情況下，如何確定此時(shí)哪一點(diǎn)對應(yīng)最佳運(yùn)動(dòng)矢量或下一步搜索的中心點(diǎn)，成為一個(gè)比較棘手的問題。菱形搜索示意圖如圖4 所示。在使用菱形搜索法時(shí)，若搜索點(diǎn)A和B的SAD值相等，如何進(jìn)行下一步的搜索。如果使用MSD或其他準(zhǔn)則進(jìn)行二次判別，會大大增加算法的復(fù)雜性和一致性，也失去了SAD準(zhǔn)則本來的意義。該問題得不到解決，SAD準(zhǔn)則運(yùn)動(dòng)估值算法的穩(wěn)定性就得不到保證。

　　對此，提出了如下的約束判別方法：
　　假設(shè)子塊CB為當(dāng)前幀中待匹配的子塊，運(yùn)動(dòng)矢量為(i_k，j_k)；塊RB為與CB相鄰的子塊，運(yùn)動(dòng)矢量為(i_k′，j_k′)。根據(jù)上節(jié)中得到的SAD優(yōu)化準(zhǔn)則求出CB在參考幀上對i、j位移塊的匹配像素?cái)?shù)Q(i，j)，若有位移值I、J使
　　
　　當(dāng)且僅當(dāng)有惟一的I、J使上式成立時(shí)，位移矢量i_k=I，j_k=J。
　　若有{i_u，j_u}，u=1，2，…，U₀同時(shí)滿足(9)式，根據(jù)相鄰空間塊對應(yīng)的運(yùn)動(dòng)矢量存在高度的空間相關(guān)性，特別是屬于統(tǒng)一對象的塊運(yùn)動(dòng)保持一致的可能性更大，計(jì)算
　　
　　選取與△d(i_min，j_min)對應(yīng)的位移矢量(i_min，j_min)為最佳運(yùn)動(dòng)矢量。即在SAD優(yōu)化準(zhǔn)則意義下，若多個(gè)不同位移的像素點(diǎn)有相同最小風(fēng)險(xiǎn)時(shí)，選擇與相鄰塊相對位移最小的像素點(diǎn)為當(dāng)前塊的最佳匹配點(diǎn)。顯而易見，這一判決準(zhǔn)則不僅顯著提高了判決的惟一性，而且由于在相同風(fēng)險(xiǎn)下選擇最小相對位移使得相鄰圖像區(qū)域的運(yùn)動(dòng)矢量場的一致性得到進(jìn)一步提高。
　　將這種基于SAD優(yōu)化準(zhǔn)則下的最佳匹配判決方法稱為約束條件求和絕對差匹配準(zhǔn)則RCSAD(Restrictive Conditional SAD)。
4 實(shí)驗(yàn)結(jié)果
　　為比較RCSAD與SAD、MSE準(zhǔn)則下塊匹配算法的性能，分別運(yùn)用三種準(zhǔn)則對標(biāo)準(zhǔn)測試序列Miss America (QCIF格式)進(jìn)行運(yùn)動(dòng)位移矢量估值實(shí)驗(yàn)。對每個(gè)16×16的子塊進(jìn)行運(yùn)動(dòng)矢量估值，預(yù)測誤差進(jìn)行二維離散余弦變換(DCT)，并將DCT 系數(shù)量化，對量化后的系數(shù)采用變字長碼編碼。
　　圖5給出了三種匹配準(zhǔn)則下，測試序列Miss America各圖像幀N_k(k=1，2，…45)的預(yù)測峰值信噪比PSNR曲線?？梢钥闯?，約束條件求和絕對差準(zhǔn)則的性能(視頻序列的圖像質(zhì)量)優(yōu)于均方誤差準(zhǔn)則，比求和絕對差準(zhǔn)則有了很大提高。

?