【正文】 ―‖字形的五點(diǎn)搜索。 本思想 :CSA 是從原點(diǎn)開始，以 ―‖字形分布的五個(gè)點(diǎn)構(gòu)成每次搜索的點(diǎn)群，以 TDL的搜索方法檢測(cè)為 MBD 點(diǎn)，僅在最后一步采用 ―十 ‖字形點(diǎn)群。 圖 24 三步搜索法搜索過程 ④ 算法分析 :TSS 算法搜索時(shí)，整個(gè)過程采用了統(tǒng)一的搜索模板，使得第一步的步長過大，容易引起誤導(dǎo)，因此對(duì)小運(yùn)動(dòng)模式的效率較低 。圖 24 中點(diǎn) [+4， +4]、 [+6，+4]是第一、第二步的最小塊誤差點(diǎn)。否則，重復(fù) Step 2。 Step 2:將步長減半，中心移到上一步的 MBD 點(diǎn)，重新在中心點(diǎn)及周圍的 8 個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算并比較。 ① 基本思想 :TSS 算法的基本思想是采用一種由粗到細(xì)的搜索模式，從原點(diǎn)開始，按一定步長取周圍 8 個(gè)點(diǎn)構(gòu)成每次搜索的點(diǎn)群，然后進(jìn)行匹配運(yùn)算，跟蹤最小塊誤差MBD 點(diǎn)。 圖 23 二維對(duì)數(shù)法過程 (3)三步搜索法 (TSS，而 Three Step Search) 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 11 三步搜索法與 TDL 類似，由于其簡(jiǎn)單、健壯、性能良好的特點(diǎn)，已被人們所重視。 TDL 算法的前提是假設(shè)搜索區(qū)域內(nèi)只有一個(gè)極小值點(diǎn)，如果搜索區(qū)域內(nèi)存在多個(gè)極小值點(diǎn)時(shí)，該方法找到的可能是局部最小點(diǎn)。后來有人提出應(yīng)該在搜索的每個(gè)階段都將步長減半。 ④ 算法分析 :TDL 算法搜索時(shí)，最大搜索點(diǎn)數(shù)為 2+7lbW，這里 W 表示最大偏移量max(dxmax,dymax)。否則，重復(fù) Step 2。若為 MBD 點(diǎn)位于中心點(diǎn)，則保持中心點(diǎn)位置不變，將步長減半，構(gòu)成 ―十 ‖字形點(diǎn)群，在五個(gè)點(diǎn)處計(jì)算。 ② 算法描述 : Step 1:從原點(diǎn)開始，選取一定的步長，在以 ―十 ‖字形分布的五個(gè)點(diǎn)處進(jìn)行塊匹配計(jì)算并比較。 (2)二維對(duì)數(shù)法 (TDL， TwoDimensional Logarithmic) 二維對(duì)數(shù)搜索法由 和 提出，它開創(chuàng)了快速算法的先例，分多個(gè)階段搜索，逐次減小搜索范圍直到不能再小時(shí)結(jié)束。 ③ 模板及搜索過程圖示 :如圖 22 所示。 ② 算法描述 : Setpl:從原點(diǎn)出發(fā)，按順時(shí)針方向由近及遠(yuǎn)，在每個(gè)像素處計(jì)算 SAD 值，直到遍 歷搜索范圍內(nèi)的所有點(diǎn)。 (l)全搜索法 (FS， Full Seacrh method) ① 算法思想 :全搜索法也稱為窮盡搜索法，或螺旋向外搜索法，是對(duì)搜索范圍內(nèi)所有可能的候選位置計(jì)算其 SAD(i， j)值，從中找出最小 SAD，其對(duì)應(yīng)偏移量即為所求運(yùn)動(dòng)矢量。為了減小運(yùn)動(dòng)估計(jì)計(jì)算量 ，出現(xiàn)了各種塊匹配算法，它們只是搜索策略各有不同 ，其中搜索精度最高的是全搜索法，但由于計(jì)算復(fù)雜度高，不宜于實(shí)時(shí)應(yīng)用，為此人們提出了各種改進(jìn)的快速算法。 典型的塊匹配算法 在 MPEG24 視頻編碼算法中，運(yùn)動(dòng)估計(jì) (ME)的計(jì)算量占整個(gè)編碼計(jì)算量的 2/3 以上 [16]。 另外三步法、二維對(duì)數(shù)法、交叉法等主要是通過限制搜索位置的數(shù)目來減少計(jì)算量。如四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 9 全搜索法，它對(duì)搜索范圍內(nèi)的每一個(gè)像素點(diǎn)進(jìn)行塊匹配運(yùn)算以得到一個(gè)最優(yōu)的運(yùn)動(dòng)矢量。 SAD 即求和絕對(duì)誤差，其定義如下 : （ 4） 搜索策略 搜索策論選擇恰當(dāng)與否對(duì)運(yùn)動(dòng)估計(jì)的準(zhǔn)確性，運(yùn)動(dòng)估計(jì)的速度有很大的影響。 (3)歸一化互相關(guān)函數(shù)： （ 3） 式中 NCCF 的最大值點(diǎn)為最優(yōu)匹配點(diǎn)。若在某一個(gè)點(diǎn) (x,y)處 MAD(dx,dy)達(dá)到最小，則該點(diǎn)為要找的最優(yōu)匹配點(diǎn)。在下一節(jié)中將介紹在運(yùn)動(dòng)估計(jì)常用的一些匹配準(zhǔn)則。這種方法在保證精度的基礎(chǔ)上利用運(yùn)動(dòng)矢量相關(guān)性從而大大減少了計(jì)算量。如果當(dāng)前塊的各相鄰塊的運(yùn)動(dòng)矢量相等，則以其作為當(dāng)前塊運(yùn)動(dòng)矢量的預(yù)測(cè)值 。比較典型的是 ―平均預(yù)測(cè) ‖，在 中使用三個(gè)相鄰塊的運(yùn)動(dòng)矢量的中值作為當(dāng)前塊的運(yùn)動(dòng)矢量的預(yù)測(cè)值。序列圖像的運(yùn)動(dòng)矢量在空間、時(shí)間上具有很強(qiáng)的相關(guān)性。改進(jìn)的方法是利用運(yùn)動(dòng)矢量的相關(guān)性來預(yù)測(cè)起點(diǎn)。分別求出 當(dāng)前塊與其相鄰塊間的 SAD 值，然后選取 SAD 最小的塊的運(yùn)動(dòng)矢量作為預(yù)測(cè)值。 下面舉例說明幾種常見的預(yù)測(cè)方法。由于相鄰塊之間和相鄰幀之間具有很強(qiáng)的相關(guān)性，因而許多算法都利用這種相關(guān)性先對(duì)初始搜索點(diǎn)進(jìn)行預(yù)測(cè)，以預(yù)測(cè)點(diǎn)作為搜索起點(diǎn)。如果采用的算法初始步長太大，而原點(diǎn) (以下均指待搜索塊的中心點(diǎn)在參考幀中的相同位置的對(duì)應(yīng)點(diǎn)，而不是坐標(biāo)位置的 真正原點(diǎn) )又不是最優(yōu)點(diǎn)，有可能使快速搜索跳出原人群的運(yùn)動(dòng)估計(jì)點(diǎn)周圍的區(qū)域 (這些區(qū)域可能包含最優(yōu)點(diǎn) )而去搜索遠(yuǎn)距離的點(diǎn)，導(dǎo)致搜索方向的不確定性，這就有可能陷入局部最優(yōu)。 初始搜索點(diǎn)的選擇 (1)直接選擇參考幀對(duì)應(yīng)塊的中心位置。 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 7 圖 21 塊匹配原理圖 為了提高圖像質(zhì)量，加快估計(jì)速度是運(yùn)動(dòng)估計(jì)算法的研究目標(biāo) 之一 。本程序主要用基于塊的運(yùn)動(dòng)方式開發(fā)出的運(yùn)動(dòng)估計(jì)算法——塊匹配算法。 塊匹配的原理如圖 21。匹配塊與當(dāng)前塊之間的坐標(biāo)位移就是運(yùn)動(dòng)矢量，匹配塊與當(dāng)前塊的對(duì)應(yīng)象素點(diǎn)逐個(gè)做差就的到差值塊。并且假定每一個(gè)塊內(nèi)的運(yùn)動(dòng)只做 相等的平移同時(shí)可以用一個(gè)簡(jiǎn)單的參數(shù)模型特征化。 BMA 并不 借助人群中個(gè)體的信息，而是通過統(tǒng)計(jì)視頻中各宏塊的運(yùn)動(dòng)矢量估計(jì)出人群整體的運(yùn)動(dòng) [13] 。因此，本文提出基于塊匹配的人群運(yùn)動(dòng)估計(jì)（ BMA）。 在一幅幅復(fù)雜的人群圖像中，如果依靠每個(gè)步行者的個(gè)體信息來估計(jì)人群總體的運(yùn)動(dòng)，必須要分離出每個(gè)個(gè)體的運(yùn)動(dòng)。它把圖像域分割成互相不重疊的稱為塊的小區(qū)域，并且假定每一個(gè)塊內(nèi)的運(yùn)動(dòng)都可以用一個(gè)簡(jiǎn)單的參數(shù)模型特征化，如果快足夠小，那么這種模型是相當(dāng)合理 的。 運(yùn)動(dòng)估計(jì) 運(yùn)動(dòng)估計(jì)已發(fā)展得較為成熟，最常用于人群監(jiān)控與視頻壓縮編碼。本章對(duì)全文工作以及畢業(yè)收獲進(jìn)行總結(jié)，指出了還需改進(jìn)的地方。介紹實(shí)現(xiàn)該算法的工具 ，并對(duì)程序各模塊一一實(shí)現(xiàn)； 第 5 章：算法的驗(yàn)證和評(píng)價(jià)。介紹運(yùn)動(dòng)估計(jì)，把塊匹配法分為各個(gè)模塊，并對(duì)其算法進(jìn)行介紹與分析，同時(shí)在最后得出各個(gè)模塊最合適的算法； 第 3 章：算法分析與設(shè)計(jì)。 論文組織與結(jié)構(gòu) 第 1 章：緒論。 論文主要工作 在視頻運(yùn)動(dòng)估計(jì)方面，相關(guān)技術(shù)比較多，也比較成熟，而在人群運(yùn)動(dòng)估計(jì)方面，主流技術(shù)則顯得較不成熟，各種算法層出不窮，用得最多的只有幾種，其中關(guān)鍵就在于對(duì)時(shí)間性和空間性的要求，隨著科學(xué)技術(shù)的發(fā)展，對(duì)這兩點(diǎn)的要求已不再那么強(qiáng)烈，注意力已轉(zhuǎn)移到性能上，一般來說，性能越好，算法越復(fù)雜，而 OpenCV 作為一個(gè)開源視覺庫，全部由 C 語言寫就，因此，這是一個(gè)十分強(qiáng)大的圖像視覺處理工具，對(duì)細(xì)微處的處理很好，其功能接口都為函數(shù)，程序員只需調(diào)用函數(shù)便可完成一系列高效高質(zhì)量的操作。其中第 2 點(diǎn)通過改進(jìn)模板的方法來減少搜索點(diǎn)數(shù)更是當(dāng)前的研究熱點(diǎn)，出現(xiàn)了許多算法。塊匹配運(yùn)動(dòng)估計(jì)算法算法簡(jiǎn)單，便于 VLSI 實(shí)現(xiàn)，被廣泛應(yīng)用。 Rourke 等人的人群運(yùn)動(dòng)估計(jì)的方法都限于低密度人群，如果人群密度較高，出現(xiàn)個(gè)體間的相互遮擋使得個(gè)體信息提取不全對(duì)，就會(huì)遇到困難 [9]。 Davies 和 Chow 的方法在人群密度較高時(shí)，由于人群遮擋現(xiàn)象，測(cè)量值與人群人數(shù)之間的線性關(guān)系消失，導(dǎo)致誤差很大，且這些方法要求提供場(chǎng)景的背景圖像。在密度估計(jì)上主要有Davies， Chow， Marana 等人的方法；在運(yùn)動(dòng)估計(jì)上主要有 Rourke 等人的方法。 人群運(yùn)動(dòng)估計(jì)的傳統(tǒng)方法是人工估計(jì)，但這種方法比較主觀，不能做定量判斷。要想用精確的數(shù)學(xué)模型來描述人群的狀態(tài)和行為非常困難，但我們?nèi)匀豢吹搅艘恍┠軌虮平巳赫鎸?shí)行為的數(shù)學(xué)模型的出現(xiàn)，如 ， Corwd Dynamic Limted 公司依據(jù) AuotCAD 做出了一些建筑設(shè)施的設(shè)計(jì)方案。 近年來，對(duì)人群的研究越來越引起人們的關(guān)注，對(duì)人群狀態(tài)和行為的研究也越來越多，而人群研究的前提是要弄清如何對(duì)人群進(jìn)行適當(dāng)?shù)拿枋?。這種方法雖然解決了建筑物某個(gè)入口處的擁擠問題，但是人群很可能又涌向別的入口造成新的擁擠。 ② 易造成漏報(bào)。 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 4 但是這樣做主要有如下缺 點(diǎn) : ① 不能起到預(yù)防的作用。 ② 利用閉路電視監(jiān)控某一場(chǎng)景。 傳統(tǒng)的保障人群安全的途徑主要有 : 人群的密度估計(jì)與運(yùn)動(dòng)估計(jì) ① 采用物理方法修正建筑物。 國內(nèi)外研究與技術(shù)現(xiàn)狀 智能人群監(jiān)控的研究現(xiàn)狀 目前，國內(nèi)的安全防范工作中，智能人群估計(jì)領(lǐng)域基本還是一項(xiàng)空白，相關(guān)的文獻(xiàn)和技 術(shù)資料很少，基礎(chǔ)理論和相關(guān)技術(shù)不多，沒有成熟的產(chǎn)品，國外在人群運(yùn)動(dòng)分析方面研究較多。 為了更好的進(jìn)行人群運(yùn)動(dòng)估計(jì)，前期準(zhǔn)備必不可少， 1. 學(xué)習(xí)圖像處理的基本原理，了解人群監(jiān)控的意義，采集 若干組實(shí)驗(yàn)用視頻序列； 2. 了解現(xiàn)有圖像處理的運(yùn)動(dòng)估計(jì)方法，學(xué)習(xí) OpenCV 視頻處理的基本知識(shí)，掌握塊匹配的主要方法，利用 OpenCV 實(shí)現(xiàn)塊匹配的原理和技術(shù)。截至 2020 年 8 月，在 的下載次數(shù)已經(jīng)超過 2 200 000 次，大量用戶來自中國。 它包含許多常用的算法，為圖像處理、模式識(shí)別、三維重建、物體跟蹤、機(jī)器學(xué)習(xí)和線性代數(shù)提供了各種各樣的算法 [7]。同時(shí)使用絕對(duì)差和（ SAD, the Sum of Absolute Difference）標(biāo)準(zhǔn)作為匹配準(zhǔn)則，它具有便于硬件實(shí)現(xiàn)的優(yōu)點(diǎn)。運(yùn)動(dòng)估計(jì)的估計(jì)精度和運(yùn)算復(fù)雜度取決于搜索策略和塊匹配準(zhǔn)則。 塊匹配算法 塊匹配法的基本思想是先將圖像劃分為許多子塊，然后對(duì)當(dāng)前幀中的每一塊根據(jù)一定的匹配準(zhǔn)則在相鄰幀中找出當(dāng)前塊的匹配塊，由此得到兩者的相對(duì)位移，即當(dāng)前塊的運(yùn)動(dòng)矢量。高質(zhì)量的運(yùn)動(dòng)估計(jì)算法是高效 視頻編碼 的前提和基礎(chǔ)。 運(yùn)動(dòng)估計(jì)和 運(yùn)動(dòng)補(bǔ)償 是 AVS 中去除時(shí)間冗余的主要方法，作為視頻壓縮編碼系統(tǒng)的核心算法，占整個(gè)系統(tǒng)運(yùn)算量的 60%80%，它采用多種宏塊劃分方式， 1P4 像素插值、雙向估計(jì)和多參考幀等技術(shù)大大提高了編碼效率，但同時(shí)也給編解碼器增加了一定的復(fù)雜度。 運(yùn)動(dòng)估計(jì)法的基本思想是將圖像序列的每一幀分成許多互不重疊的宏塊，并認(rèn)為宏塊內(nèi)所有象素的位移量都相同，然后對(duì)每個(gè)宏塊到參考幀某一給定特定搜索范圍內(nèi)根據(jù)一定的匹配準(zhǔn)則找出與當(dāng)前塊最相似的塊，即匹配塊，匹配塊與當(dāng)前塊的相對(duì)位移即為運(yùn)動(dòng)矢量。 從而分別提出了密度估計(jì)法與運(yùn)動(dòng)估計(jì)法這兩類技術(shù)。 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 2 人群監(jiān)控分為人群密度估計(jì)和人群運(yùn)動(dòng)估計(jì)，本文著手解決人群運(yùn)動(dòng)估計(jì)。將圖像處理、模式識(shí)別、計(jì)算機(jī)視覺等技術(shù)應(yīng)用在人群監(jiān)控中 ,可以達(dá)到對(duì)人群的自動(dòng)、客觀、實(shí)時(shí)、定量分析。隨著智能化技術(shù)的發(fā)展，智能化的人群監(jiān)控技術(shù) 已成為研究的熱點(diǎn)。 人群監(jiān)控是借助于數(shù)字圖像處理技術(shù)對(duì)某一區(qū)域的人群進(jìn)行監(jiān)控 ,它在社會(huì)生活和生產(chǎn)的許多領(lǐng)域有著廣闊的應(yīng)用前景 [3]。 現(xiàn)代社會(huì)，伴隨經(jīng)濟(jì)的發(fā)展 ,各種高層建筑、地下建筑和大型商 業(yè)娛樂設(shè)施也越來越多 ,同時(shí)出入或圍繞這些建筑物的人群也在加大，一旦擁擠人群發(fā)生突發(fā)事件 ,容易造成群死群傷事故，因此必須考慮到人群的安全問題。08 年全球人口已達(dá)到 67 億，預(yù)計(jì)到 2050 年，全球人口將超過 90 億。 智能化人群監(jiān)控是智能視頻監(jiān)控研究中的一個(gè)重要課題，它作為智能監(jiān)控中的一項(xiàng)關(guān)鍵技術(shù)，在人群管理、公共場(chǎng)所設(shè)計(jì)、虛擬環(huán)境建模、視覺監(jiān) 控、智能環(huán)境模擬等方面都有著重要的應(yīng)用價(jià)值 [1]。目前，智能監(jiān)控的研究大多集中于少數(shù)目標(biāo)個(gè)體上。 本文結(jié)合 OpenCV，采用塊匹配算法對(duì)人群的運(yùn)動(dòng)進(jìn)行估計(jì)，并在功能實(shí)現(xiàn)前對(duì)OpenCV 與塊匹配各重要環(huán)節(jié)有具體分析。本文著手解決人群運(yùn)動(dòng)估計(jì)這一塊，智能化運(yùn)動(dòng)估計(jì)可以用于人群的監(jiān)測(cè)和管理，也可應(yīng)用于商業(yè)領(lǐng)域，如市場(chǎng)調(diào)查、交通安全以及建筑設(shè)計(jì)領(lǐng)域等。如何對(duì)公共場(chǎng)合的人群進(jìn)行有效管理與控制，是不得不考慮的重大問題。 本科生畢業(yè)論文（設(shè)計(jì)） 題 目 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 學(xué) 院 軟 件 學(xué) 院 專 業(yè) 軟 件 工 程 教務(wù)處制表 二Ο 一Ο 年六月一日 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 基于塊匹配的人群運(yùn)動(dòng)估計(jì) 軟件工程 學(xué)生 舒禹銘 指導(dǎo)