區塊匹配演算法簡介

區塊匹配演算法（Block Matching Algorithm，BMA）是計算機視覺和影像處理領域的一種基本技術。它被廣泛應用於影像編碼、運動補償和光流估計等多個領域。

區塊匹配法的起源與發展：
區塊匹配法起源於影像編碼的需求。隨著20世紀70年代和80年代數位影片技術的興起，如何高效地壓縮和傳輸影像數據成為了一個重要的研究課題。當時，數據壓縮的需求驅動了各種算法的開發，其中區塊匹配法逐漸脫穎而出。

這項技術的核心思想是將圖像劃分為小區塊，然後在相鄰幀中搜索這些區塊的最佳匹配，以估計運動向量，這樣一來就可以用上一幀的圖像資訊加上運動向量和較少的新圖像資訊表示出下一幀，從而實現數據壓縮。(圖一)
圖一、一個簡單的例子。紅框是選取區塊，我們可以輕易看出，如果把框的位置進行「往右２像素、往上３像素」的移動，frame n 框裡的內容就會和frame n+1 框裡的內容吻合，所以（2,3）就是我們要找的運動向量。

這一技術被證明是非常有效的，並且成為了隨後影片壓縮標準的基礎，例如MPEG（Moving Picture Experts Group）和H.26x系列標準。區塊匹配法通過利用相鄰幀之間的相似性，顯著減少了需要傳輸或存儲的數據量，從而極大地提升了壓縮效率。

區塊匹配的基本概念：
區塊匹配法將圖像劃分為固定大小的區塊（通常是8x8或16x16像素），然後在參考幀中搜索每個區塊的最佳匹配。這一過程涉及計算每個候選區塊與當前區塊之間的相似性，並選擇相似性最高的候選區塊作為匹配區塊。

相似性度量：
為了評估兩個區塊的相似程度，我們還會需要一個cost function。在區塊匹配法中，最常用的相似性度量是「絕對差值和」（Sum of Absolute Differences, SAD）和「平方差值和」（Sum of Squared Differences, SSD）。這些度量通過計算兩個區塊之間的灰度值差異來評估它們的相似性。顧名思義，SAD就是分別計算兩個區塊裡對應位置的每個像素的灰度差值，取絕對值，再加起來。SSD則是把差值取平方再加起來。總而言之，cost function得出的數字越小，代表兩個區塊越相似，越有可能是（或越接近）要找的目標。

搜索策略：
為了找到最佳匹配區塊，通常需要在參考幀中進行全局或局部搜索。常見的搜索策略包括：
--全搜索法（Full Search ，也叫 Exhaustive Search）：對每個區塊在整個參考幀中進行全面搜索，確保找到全局最優的匹配。但由於計算量巨大，實際應用中通常不採用這種方法。為了提升速度、同時維持準確度，研究者們利用coarse-to-fine、Hierarchical的概念，對全搜索法進行了加速。其核心精神是先在低解析度的圖像上做搜索，找出一個運動向量的大概，然後再用高解析度圖像，於向量所指的一個較小範圍搜索，用搜索結果調整向量，得出正確答案。

不過全搜索法再怎麼加速也還是不夠快，於是又誕生了許多種快速搜索法。其中最重要的是三步搜索法，因為它衍生出了後續其他許多種搜索法。
--三步搜索法（Three-Step Search, TSS）：首先在較大的搜索範圍內進行粗略搜索，然後逐步縮小搜索範圍，進行精細搜索。這種方法在保證效率的同時，能夠取得較為精確的匹配效果。(圖二)
圖二、三步搜索法的示意圖。圓形是第一步搜索的地方，三角形是第二步，方形是第三步。

--鑽石搜索法（Diamond Search, DS）：採用鑽石形狀的搜索範圍，從中點開始向外擴展，逐步逼近最佳匹配點。這種方法在運動不大的情況下效果良好，擁有接近全搜索法的準度，計算量也相對較小。

運動補償：
通過區塊匹配法確定每個區塊的運動向量後，運動補償將這些運動向量應用於參考幀，以預測當前幀。預測誤差（即當前幀與預測幀之間的差異）可以通過編碼傳輸，而非整幀的數據，這極大地減少了需要傳輸的數據量，從而實現壓縮效率的提高。


撰稿人：劉徹


參考資料
1. Bergen, J. R., Anandan, P., Hanna, K. J., & Hingorani, R. (1992). Hierarchical model-based motion estimation. In Computer Vision—ECCV'92: Second European Conference on Computer Vision Santa Margherita Ligure, Italy, May 19–22, 1992 Proceedings 2 (pp. 237-252). Springer Berlin Heidelberg.
2. Jing, X., & Chau, L. P. (2004). An efficient three-step search algorithm for block motion estimation. IEEE transactions on multimedia, 6(3), 435-438.

留言

張貼留言