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