基于塊運動模型的塊匹配算法簡單、高效且易于硬件實現，已被很多國際視頻編碼標準采納，并得到廣泛的應用^[1][2]。其主要思想是把編碼幀分成若干個大小相同的圖像塊，對每個圖像塊，根據塊匹配算法在預測幀中尋找最佳的匹配塊，然后對其殘差進行編碼。編碼殘差系數所用的比特數和編碼運動矢量所用的比特數越少，則整體的編碼效率就越高。
　　本文在塊運動模型的基礎上，分析了當前使用的塊匹配準則的優缺點，提出一種改進的塊匹配準則——約束條件求和絕對差匹配準則(RCSAD)。
1 塊匹配準則
　　在現有搜索算法中，最常用的匹配準則有如下幾種：
　　(1)歸一化互相關函數準則NCCF

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

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

3 約束條件求和絕對差匹配準則
3.1 SAD塊匹配準則的優化
　　塊匹配算法搜索區域幾何關系如圖2所示。子塊" title="子塊">子塊CB為當前幀中待匹配的子塊，SR為該子塊在前一相鄰幀中的搜索區間。假設子塊RB為搜索區SR中的任一子塊，如果用abs(i，j)來表示子塊RB中相對坐標為(i，j)的像素點與它在CB中對應像素點的差值的絕對值(以下簡稱預測殘差)，即：
　　abs(i，j)=RB(i，j)-CB(i，j) (0≤i≤M-1，0≤j≤N-1)
　　假設圖像為256灰度值，用n_L(x)表示在以上兩子塊內對應像素的預測殘值為x的數量(x∈[0，255]，x為整數)。則在兩子塊完全匹配的情況下， n_L-x的分布有以下結果：
　　n_L(x)=M×N，x=0
　　n_L(x)=0，x=(1，…，255)????????? (5)
　　一般地，塊RB是搜索區SR中的任意一個待匹配塊，則有：
　　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]為預測殘差值為x的概率密度函數。可用預測殘差的分布圖來描述n_L-x分布，其預測殘差分布圖如圖3所示。圖中，曲線1已經歸一化。由圖3可知：
　　
　　從統計的觀點來看，2個塊越匹配，其分布曲線的峰值越趨向于0點(即分布曲線的中心點越趨于x軸的原點)，上述分布曲線越趨于呈現正脈沖特性(即標準方差越小)。
　　理論上，當子塊RB與子塊CB完全匹配時(即兩子塊的像素一一對應)，則其n_L-x的分布圖退化為位于原點的幅度為MN的一條豎線，即此時分布圖描述的是式(5)的情況。
　　類似于在分布函數中取方差的方法，如果在橫軸x方向上對分布曲線3取門限T(T為整數，如假設某最佳匹配塊使預測殘差分布的均值為μ₀，方差為σ₀，可令T= μ₀+2σ₀ ，或視情況而定)，且令：
　　
　　則式(6)的物理意義為子塊RB和子塊CB中對應像素之差的絕對值比T小的所有數目。由統計特性可知，在相同的門限T下，如果某待匹配的子塊越趨近于預測子塊CB，則其對應的Q值越大。反之，在一確定的T值下，Q越大，則塊RB與塊CB越匹配。基于以上的結論，提出如下的算法：如圖2所示，在搜索區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)≤T
　　x∈[0，M-1]，y∈[0，N-1]時，Q(i，j)=Q(i，j)+1?????????????? (7)
　　這樣，在FS搜索完畢后，可得到相應的(2W+1)²個Q(i，j)值。之后，在數組變量中尋找其最大值：
　　
　　則Q(I，J)與對應的子塊為所要尋找的最佳匹配塊，(I，J)即為運動矢量。

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

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

?