【文章內容簡介】 主流視頻壓縮標準(如 ，MPEG 系列等)中，視頻系統(tǒng)編碼器的效率主要取決于運動估計算法，而運動估計的效率主要體現(xiàn)在圖像質量、壓縮碼率和搜索速度 3 個方面 [10]， 這些由采用的搜索策略、匹配準則和初始搜索點的選擇等因素決定。塊匹配運動估計算法算法簡單，便于 VLSI 實現(xiàn)，被廣泛應用。目前，其研究主要集中在：1)利用不同幀相同位置塊和相同幀內相鄰塊運動矢量的相關性，從同幀中左上、上、左等塊的運動矢量及前一幀或前幾幀相同位置塊的運動矢量中挑選出當前塊運動矢量的最優(yōu)初始值 然后再按照某一種算法進行搜索；2)不斷改進運動估計匹配模板的形狀和大小，旨在減少搜索點數(shù)，從而減少搜索時間，提高編碼速度；3)通過數(shù)學不等式來改進目標函數(shù)，通過判斷提前結束搜索，達到節(jié)約運算量和運算時間的目的。其中第 2 點通過改進模板的方法來減少搜索點數(shù)更是當前的研究熱點，出現(xiàn)了許多算法。研究方向。 論文主要工作在視頻運動估計方面，相關技術比較多，也比較成熟，而在人群運動估計方面，主流技術則顯得較不成熟，各種算法層出不窮，用得最多的只有幾種，其中關鍵就在于對時間性和空間性的要求，隨著科學技術的發(fā)展，對這兩點的要求已不再那么強烈，注意力已轉移到性能上，一般來說，性能越好，算法越復雜，而 OpenCV 作為一個開源視覺庫，全部由 C 語言寫就，因此，這是一個十分強大的圖像視覺處理工具，對細微處的處理很好，其功能接口都為函數(shù)，程序員只需調用函數(shù)便可完成一系列高效高質量的操作。而本程序在人群運動估計這一方面運用了一種全新的處理方法，即利用 OpenCV 完成塊匹配法運動估計，其真正達到了高性能高密度。 論文組織與結構第 1 章：緒論。主要介紹了人群監(jiān)控發(fā)展和應用，以及本論文的研究背景和研究工作，利用 OpenCV 實現(xiàn)基于塊匹配的人群運動估計的設計目的；第 2 章：塊匹配法各模塊算法背景與分析。介紹運動估計，把塊匹配法分為各個模塊，并對其算法進行介紹與分析，同時在最后得出各個模塊最合適的算法；第 3 章：算法分析與設計。說明運動估計視頻處理的各個步驟所需處理，并分析處理所需算法，介紹背景建模；第 4 章：算法的實現(xiàn)。介紹實現(xiàn)該算法的工具，并對程序各模塊一一實現(xiàn)；第 5 章：算法的驗證和評價。對算法進行測試，對結果進行分析；第 6 章：結論。本章對全文工作以及畢業(yè)收獲進行總結，指出了還需改進的地方。2 塊匹配算法介紹及分析本章主要介紹塊匹配算法的各個模塊，及各模塊所用到的算法。 運動估計運動估計已發(fā)展得較為成熟，最常用于人群監(jiān)控與視頻壓縮編碼?；趬K的運動估計和補償是視頻編碼中最通用的算法。它把圖像域分割成互相不重疊的稱為塊的小區(qū)域，并且假定每一個塊內的運動都可以用一個簡單的參數(shù)模型特征化，如果快足夠小，那么這種模型是相當合理的。目前這種方法被廣泛用于視頻標準變換運動補償濾波和采用基于塊的運動補償進行的數(shù)字視頻壓縮 [11~12] 。在一幅幅復雜的人群圖像中，如果依靠每個步行者的個體信息來估計人群總體的運動，必須要分離出每個個體的運動。但要做到這點并不容易，因為在開放的空間中，一個步行者可能向各個方向移動，且步行者的身體各部分的移動方式也各不相同，進而，當人群密度較大，個體之間有相互遮擋時，這就變得更加困難，甚至是不可能的。因此，本文提出基于塊匹配的人群運動估計（BMA） 。這種方法由于實現(xiàn)較簡單且容易而受到廣泛關注。BMA 并不借助人群中個體的信息，而是通過統(tǒng)計視頻中各宏塊的運動矢量估計出人群整體的運動 [13] 。 塊匹配基本思想基于塊匹配法的運動估計的基本思想就是將當前幀分成互不重疊的大小為 MN 的宏塊(一般情況下 M==N)，然后對當前幀中的每一個塊都在參考幀中的一定區(qū)域，即搜索窗口內，按照一定的匹配準則搜索與之具有最小匹配誤差的塊(Minimal DistortionBlock，MDB)，該塊即為當前塊的匹配塊，由匹配塊與當前塊的相應位置計算出運動位移，所得運動位移即為當前塊的運動矢量。并且假定每一個塊內的運動只做相等的平移同時可以用一個簡單的參數(shù)模型特征化。如果塊足夠小，那么這種模型是相當合理的。匹配塊與當前塊之間的坐標位移就是運動矢量，匹配塊與當前塊的對應象素點逐個做差就的到差值塊?；谶@樣的方法這樣，當前幀中的每一個塊都可以用一個差值塊和一個運動矢量來表示，對當前幀的編碼就轉化為對每一塊的差值塊和運動矢量的編碼。塊匹配的原理如圖 21。運動估計算法的整體效率主要體現(xiàn)在初始搜索點的選擇、匹配準則和運動搜索策略三個方面。本程序主要用基于塊的運動方式開發(fā)出的運動估計算法——塊匹配算法。塊匹配算法由于它具有較少的硬件復雜度，容易在超大規(guī)模集成電路中實現(xiàn)，因此被認為是最通用的算法。 圖 21 塊匹配原理圖為了提高圖像質量，加快估計速度是運動估計算法的研究目標之一。通常是通過研究初始搜索點的選擇、匹配準則和運動搜索策略等來提高算法效率的 [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:利用相鄰塊和相鄰幀對應塊的運動矢量來預測當前塊的搜索起點。序列圖像的運動矢量在空間、時間上具有很強的相關性。由于保存前一幀運動矢量信息在解碼端需要占用大量內存，使得系統(tǒng)復雜化，故大多算法僅考慮同幀塊的空間相關性來預測運動。比較典型的是“ 平均預測 ”，在 中使用三個相鄰塊的運動矢量的中值作為當前塊的運動矢量的預測值。方法 3:基于相鄰運動矢量相等的起點預測方法。如果當前塊的各相鄰塊的運動矢量相等，則以其作為當前塊運動矢量的預測值。否則，使用方法 1 求出當前塊與其相鄰塊間的 SAD 值，然后選取 SAD 值最小的塊作為預測起點。這種方法在保證精度的基礎上利用運動矢量相關性從而大大減少了計算量。運動估計的復雜度主要取決于匹配計算量和所采用的搜索算法這兩個方面 [14]。在下一節(jié)中將介紹在運動估計常用的一些匹配準則。 塊匹配準則運動估計算法中常用的匹配準則有三種，即最小絕對值差(MAD)、最小均方誤差(MSE)和歸一化互相關函數(shù)(NCCF)，它們分別定義如下 :(1) 最小絕對值差: （1）式中，B 代表 MN 宏塊，(dx,dy)為運動矢量，f k 與 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ōu)的運動矢量。不過，較大的搜索窗通常會使得搜索點增多，從而加大計算量，因此，搜索距離的設定需綜合考慮具體視頻的運動特性、運動估計的質量以及算法的計算量等因素，以獲得最佳的估計性能 [15]。另外三步法、二維對數(shù)法、交叉法等主要是通過限制搜索位置的數(shù)目來減少計算量。這以后的許多搜多策略都是為了平衡搜索精度與計算速度而產生的。 典型的塊匹配算法在 MPEG24 視頻編碼算法中，運動估計(ME)的計算量占整個編碼計算量的 2/3以上 [16]。在視頻編碼系統(tǒng)中，運動估計處理消耗近 50%的功耗 [16]。為了減小運動估計計算量，出現(xiàn)了各種塊匹配算法，它們只是搜索策略各有不同，其中搜索精度最高的是全搜索法，但由于計算復雜度高，不宜于實時應用，為此人們提出了各種改進的快速算法。下面介紹幾種常用的經典算法。 (l)全搜索法 (FS，F(xiàn)ull Seacrh method)①算法思想:全搜索法也稱為窮盡搜索法，或螺旋向外搜索法，是對搜索范圍內所有可能的候選位置計算其 SAD(i，j)值，從中找出最小 SAD，其對應偏移量即為所求運動矢量。此算法計算量雖大，但最簡單，可靠，找到一定是全局的最優(yōu)點。②算法描述:Setpl:從原點出發(fā)，按順時針方向由近及遠，在每個像素處計算 SAD 值，直到遍歷搜索范圍內的所有點。StPe2:在所有的 SAD 中找到最小塊誤差 (MBD)點(即 SAD 最小值的點)，該點所在位置即對應的最佳運動矢量。③模板及搜索過程圖示:如圖 22 所示。 圖 22 全搜索法搜索過程④算法分析: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ū)域內只有一個極小值點，如果搜索區(qū)域內存在多個極小值點時，該方法找到的可能是局部最小點。不能保證找到全局最優(yōu)點也正是大部分快速搜索算法的缺點。 圖 23 二維對數(shù)法過程 (3)三步搜索法 (TSS，而 Three Step Search)三步搜索法與 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ù)字表明了每個階段搜索時計算的候選塊的