【文章內(nèi)容簡介】 對程序各模塊一一實現(xiàn)； 第 5 章：算法的驗證和評價。對算法進行測試，對結果進行分析； 第 6 章：結論。本章對全文工作以及畢業(yè)收獲進行總結，指出了還需改進的地方。 四川大學本科畢業(yè)論文 基于塊匹配的人群運動估計 6 2 塊匹配算法介紹及分析 本章主要介紹塊匹配算法的各個模塊，及各模塊所用到的算法。 運動估計 運動估計已發(fā)展得較為成熟，最常用于人群監(jiān)控與視頻壓縮編碼。 基于塊的運動估計和補償是視頻編碼中最通用的算法。它把圖像域分割成互相不重疊的稱為塊的小區(qū)域，并且假定每一個塊內(nèi)的運動都可以用一個簡單的參數(shù)模型特征化，如果快足夠小，那么這種模型是相當合理 的。目前這種方法被廣泛用于視頻標準變換運動補償濾波和采用基于塊的運動補償進行的數(shù)字視頻壓縮 [11~12] 。 在一幅幅復雜的人群圖像中，如果依靠每個步行者的個體信息來估計人群總體的運動，必須要分離出每個個體的運動。但要做到這點并不容易，因為在開放的空間中，一個步行者可能向各個方向移動，且步行者的身體各部分的移動方式也各不相同，進而，當人群密度較大，個體之間有相互遮擋時，這就變得更加困難，甚至是不可能的。因此，本文提出基于塊匹配的人群運動估計（ BMA）。這種方法由于實現(xiàn)較簡單且容易而受到廣泛關注。 BMA 并不 借助人群中個體的信息，而是通過統(tǒng)計視頻中各宏塊的運動矢量估計出人群整體的運動 [13] 。 塊匹配基本思想 基于塊匹配法的運動估計的基本思想就是將當前幀分成互不重疊的大小為 MN 的宏塊 (一般情況下 M==N)，然后對當前幀中的每一個塊都在參考幀中的一定區(qū)域，即搜索窗口內(nèi)，按照一定的匹配準則搜索與之具有最小匹配誤差的塊 (Minimal DistortionBlock，MDB)，該塊即為當前塊的匹配塊，由匹配塊與當前塊的相應位置計算出運動位移，所得運動位移即為當前塊的運動矢量。并且假定每一個塊內(nèi)的運動只做 相等的平移同時可以用一個簡單的參數(shù)模型特征化。如果塊足夠小，那么這種模型是相當合理的。匹配塊與當前塊之間的坐標位移就是運動矢量，匹配塊與當前塊的對應象素點逐個做差就的到差值塊?；谶@樣的方法這樣，當前幀中的每一個塊都可以用一個差值塊和一個運動矢量來表示，對當前幀的編碼就轉化為對每一塊的差值塊和運動矢量的編碼。 塊匹配的原理如圖 21。運動估計算法的整體效率主要體現(xiàn)在初始搜索點的選擇、匹配準則和運動搜索策略三個方面。本程序主要用基于塊的運動方式開發(fā)出的運動估計算法——塊匹配算法。塊匹配算法由于它具有較少的硬件 復雜度，容易在超大規(guī)模集成電路中實現(xiàn)，因此被認為是最通用的算法。 四川大學本科畢業(yè)論文 基于塊匹配的人群運動估計 7 圖 21 塊匹配原理圖 為了提高圖像質(zhì)量，加快估計速度是運動估計算法的研究目標 之一 。通常是通過研究初始搜索點的選擇、匹配準則和運動搜索策略等來提高算法效率的 [13]。 初始搜索點的選擇 (1)直接選擇參考幀對應塊的中心位置。這種方法簡單，但容易陷入局部最優(yōu)點。如果采用的算法初始步長太大，而原點 (以下均指待搜索塊的中心點在參考幀中的相同位置的對應點，而不是坐標位置的 真正原點 )又不是最優(yōu)點，有可能使快速搜索跳出原人群的運動估計點周圍的區(qū)域 (這些區(qū)域可能包含最優(yōu)點 )而去搜索遠距離的點，導致搜索方向的不確定性，這就有可能陷入局部最優(yōu)。 (2)選擇預測的起點。由于相鄰塊之間和相鄰幀之間具有很強的相關性，因而許多算法都利用這種相關性先對初始搜索點進行預測，以預測點作為搜索起點。大量實驗證明預測點越靠近最優(yōu)匹配點，越會使得搜索次數(shù)減少。 下面舉例說明幾種常見的預測方法。 方法 1:基于 SAD(the Sum of Absolute Differences)值的起點預測方法。分別求出 當前塊與其相鄰塊間的 SAD 值，然后選取 SAD 最小的塊的運動矢量作為預測值。這種方法預測精度高，但計算 SAD 值的時間開銷大。改進的方法是利用運動矢量的相關性來預測起點。 方法 2:利用相鄰塊和相鄰幀對應塊的運動矢量來預測當前塊的搜索起點。序列圖像的運動矢量在空間、時間上具有很強的相關性。由于保存前一幀運動矢量信息在解碼端需要占用大量內(nèi)存，使得系統(tǒng)復雜化，故大多算法僅考慮同幀塊的空間相關性來預測運動。比較典型的是 ―平均預測 ‖，在 中使用三個相鄰塊的運動矢量的中值作為當前塊的運動矢量的預測值。 方法 3:基于 相鄰運動矢量相等的起點預測方法。如果當前塊的各相鄰塊的運動矢量相等，則以其作為當前塊運動矢量的預測值 。否則，使用方法 1 求出當前塊與其相鄰塊間的SAD 值，然后選取 SAD 值最小的塊作為預測起點。這種方法在保證精度的基礎上利用運動矢量相關性從而大大減少了計算量。 四川大學本科畢業(yè)論文 基于塊匹配的人群運動估計 8 運動估計的復雜度主要取決于匹配計算量和所采用的搜索算法這兩個方面 [14]。在下一節(jié)中將介紹在運動估計常用的一些匹配準則。 塊匹配準則 運動估計算法中常用的匹配準則有三種，即最小絕對值差 (MAD)、最小均方誤差 (MSE)和歸一化互相關函數(shù) (NCCF)，它們分別定義如下 : (1) 最小絕對值差 : （ 1） 式中， B 代表 MN 宏塊， (dx,dy)為運動矢量， fk 與 fk1 分別為當前幀和前一幀的灰度值，若在某一個點 (x， y)處 MAD(dx,dy)達到最小，則該點為要找的最優(yōu)匹配點。若在某一個點 (x,y)處 MAD(dx,dy)達到最小，則該點為要找的最優(yōu)匹配點。 (2)最小均方誤差 : （ 2） 能夠使 MSE 值最小的點為最優(yōu)匹配點。 (3)歸一化互相關函數(shù)： （ 3） 式中 NCCF 的最大值點為最優(yōu)匹配點。在運動估計中，匹配準則對匹配的精度影響不是很大，由于 MAD 準則不需要作乘法運算，實現(xiàn)簡單、方便，所以使用最 多，通常使用 ASD 代替 MAD。 SAD 即求和絕對誤差，其定義如下 : （ 4） 搜索策略 搜索策論選擇恰當與否對運動估計的準確性，運動估計的速度有很大的影響。有關搜索策略的研究主要是解決運動估計中存在的計算復雜度和搜索精度這一矛盾。如四川大學本科畢業(yè)論文 基于塊匹配的人群運動估計 9 全搜索法，它對搜索范圍內(nèi)的每一個像素點進行塊匹配運算以得到一個最優(yōu)的運動矢量。 不過，較大的搜索窗通常會使得搜索點增多，從而加 大計算量，因此，搜索距離的設定需綜合考慮具體視頻的運動特性、運動估計的質(zhì)量以及算法的計算量等因素，以獲得最佳的估計性能 [15]。 另外三步法、二維對數(shù)法、交叉法等主要是通過限制搜索位置的數(shù)目來減少計算量。這以后的許多搜多策略都是為了平衡搜索精度與計算速度而產(chǎn)生的。 典型的塊匹配算法 在 MPEG24 視頻編碼算法中，運動估計 (ME)的計算量占整個編碼計算量的 2/3 以上 [16]。在視頻編碼系統(tǒng)中，運動估計處理消耗近 50%的功耗 [16]。為了減小運動估計計算量 ，出現(xiàn)了各種塊匹配算法，它們只是搜索策略各有不同 ，其中搜索精度最高的是全搜索法，但由于計算復雜度高，不宜于實時應用，為此人們提出了各種改進的快速算法。下面介紹幾種常用的經(jīng)典算法。 (l)全搜索法 (FS， Full Seacrh method) ① 算法思想 :全搜索法也稱為窮盡搜索法，或螺旋向外搜索法，是對搜索范圍內(nèi)所有可能的候選位置計算其 SAD(i， j)值，從中找出最小 SAD，其對應偏移量即為所求運動矢量。此算法計算量雖大，但最簡單，可靠，找到一定是全局的最優(yōu)點。 ② 算法描述 : Setpl:從原點出發(fā)，按順時針方向由近及遠，在每個像素處計算 SAD 值，直到遍 歷搜索范圍內(nèi)的所有點。 StPe2:在所有的 SAD 中找到最小塊誤差 (MBD)點 (即 SAD 最小值的點 )，該點所在位置即對應的最佳運動矢量。 ③ 模板及搜索過程圖示 :如圖 22 所示。 圖 22 全搜索法搜索過程 四川大學本科畢業(yè)論文 基于塊匹配的人群運動估計 10 ④ 算法分析 :FS 算法是最簡單、最原始的塊匹配算法，由于可靠，且能夠得到全局最優(yōu)的結果，通常是其它算法性能比較的標準，但它的計算量很大，這就限制了在需要實時性較強的場合的應用，所以有必要進一步研究其它快速算法。 (2)二維對數(shù)法 (TDL， TwoDimensional Logarithmic) 二維對數(shù)搜索法由 和 提出，它開創(chuàng)了快速算法的先例，分多個階段搜索，逐次減小搜索范圍直到不能再小時結束。 ① 基本思想 :二維對數(shù)搜索法是由原點開始，以 ―十 ‖字形分布的五個點構成每次搜索的點群，通過快速搜索跟蹤加 MBD 點。 ② 算法描述 : Step 1:從原點開始，選取一定的步長，在以 ―十 ‖字形分布的五個點處進行塊匹配計算并比較。 Step 2:若 MBD 點在邊緣四個點處，則以該點做為中心點，保持步長不變，重新搜索 ―十 ‖字形分布的五個點 。若為 MBD 點位于中心點，則保持中心點位置不變，將步長減半，構成 ―十 ‖字形點群，在五個點處計算。 Step 3::若步長為 1，在中心及周圍 8 個點處找出 MBD 點，該點所在位置即對應最佳運動矢量，算法結束 。否則，重復 Step 2。 ③ 搜索過程圖示 :如圖 23 所示。 ④ 算法分析 :TDL 算法搜索時，最大搜索點數(shù)為 2+7lbW，這里 W 表示最大偏移量max(dxmax,dymax)。若發(fā)現(xiàn)新的 ―十 ‖字形點群的中心點位于搜索區(qū)域的邊緣，則步長也減半。后來有人提出應該在搜索的每個階段都將步長減半。所有這些改 動都是為了使算法搜索范圍很快變小，提高收斂速度。 TDL 算法的前提是假設搜索區(qū)域內(nèi)只有一個極小值點，如果搜索區(qū)域內(nèi)存在多個極小值點時，該方法找到的可能是局部最小點。不能保證找到全局最優(yōu)點也正是大部分快速搜索算法的缺點。 圖 23 二維對數(shù)法過程 (3)三步搜索法 (TSS，而 Three Step Search) 四川大學本科畢業(yè)論文 基于塊匹配的人群運動估計 11 三步搜索法與 TDL 類似，由于其簡單、健壯、性能良好的特點，已被人們所重視。若最大搜索長度為 7，搜索精 度取 1 個像素，則步長為 1，共需要三步即可滿足。 ① 基本思想 :TSS 算法的基本思想是采用一種由粗到細的搜索模式，從原點開始，按一定步長取周圍 8 個點構成每次搜索的點群，然后進行匹配運算，跟蹤最小塊誤差MBD 點。 . ② 算法描述 : Step 1:從原點開始，選取最大搜索長度的一半為步長，在中心點及周圍 8 個點處進行塊匹配計算并比較。 Step 2:將步長減半，中心移到上一步的 MBD 點，重新在中心點及周圍的 8 個點處進行塊匹配計算并比較。 Step 3:在中心點及周圍 8 個點處找出加 MBD 點，若步長為 1，該點所在位 置即對應最佳運動矢量，算法結束 。否則，重復 Step 2。 ③ 搜索過程圖示 :一個可能的搜索過程如圖 24 所示。圖 24 中點 [+4， +4]、 [+6，+4]是第一、第二步的最小塊誤差點。第三步得到最終運動矢量為 [+7， +5]，每個點上的數(shù)字表明了每個階段搜索時計算的候選塊的位置。 圖 24 三步搜索法搜索過程 ④ 算法分析 :TSS 算法搜索時，整個過程采用了統(tǒng)一的搜索模板，使得第一步的步長過大，容易引起誤導，因此對小運動模式的效率較低 。最大搜索點數(shù)為 1+8blW，當搜索范圍大于 7 時，僅用三步是不夠的，搜索步數(shù)的一般表達式為 lb(dmax+1). (4)交叉法 (CSA， Cross Search Algorithm) 1990 年， Chanbari 提出了交叉搜索算法，它也是在 TDL 和 TSS 基礎上為進一步減小計算量而發(fā)展起來的快速搜索法。 本思想 :CSA 是從原點開始，以