【正文】 銘 學(xué) 號 0643111170 年級 20xx 指導(dǎo)教師 李 曉 華 教務(wù)處制表 二Ο 一Ο 年六月一日 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運動估計 基于塊匹配的人群運動估計 軟件工程 學(xué)生 舒禹銘 指導(dǎo)老師 李曉華 [摘要 ] 智能化人群監(jiān)控是智能視頻監(jiān)控研究中的一個重要課題，它作為智能監(jiān)控中的一項關(guān)鍵技術(shù)，在人群管理、公共場所設(shè)計、虛擬環(huán)境建模、視覺監(jiān)控、智能環(huán)境模擬等方面都有著重要的應(yīng)用價值。本文著手解決人群運動估計這一塊，智能化運動估計可以用于人群的監(jiān)測和管理，也可應(yīng)用于商業(yè)領(lǐng)域，如市場調(diào)查、交通安全以及建筑設(shè)計領(lǐng)域等。目前，智能監(jiān)控的研究大多集中于少數(shù)目標(biāo)個體上。08 年全球人口已達(dá)到 67 億，預(yù)計到 2050 年，全球人口將超過 90 億。 人群監(jiān)控是借助于數(shù)字圖像處理技術(shù)對某一區(qū)域的人群進(jìn)行監(jiān)控 ,它在社會生活和生產(chǎn)的許多領(lǐng)域有著廣闊的應(yīng)用前景 [3]。將圖像處理、模式識別、計算機視覺等技術(shù)應(yīng)用在人群監(jiān)控中 ,可以達(dá)到對人群的自動、客觀、實時、定量分析。 從而分別提出了密度估計法與運動估計法這兩類技術(shù)。 運動估計和 運動補償 是 AVS 中去除時間冗余的主要方法，作為視頻壓縮編碼系統(tǒng)的核心算法，占整個系統(tǒng)運算量的 60%80%，它采用多種宏塊劃分方式， 1P4 像素插值、雙向估計和多參考幀等技術(shù)大大提高了編碼效率，但同時也給編解碼器增加了一定的復(fù)雜度。 塊匹配算法 塊匹配法的基本思想是先將圖像劃分為許多子塊，然后對當(dāng)前幀中的每一塊根據(jù)一定的匹配準(zhǔn)則在相鄰幀中找出當(dāng)前塊的匹配塊，由此得到兩者的相對位移，即當(dāng)前塊的運動矢量。同時使用絕對差和（ SAD, the Sum of Absolute Difference）標(biāo)準(zhǔn)作為匹配準(zhǔn)則，它具有便于硬件實現(xiàn)的優(yōu)點。截至 20xx 年 8 月，在 的下載次數(shù)已經(jīng)超過 2 200 000 次，大量用戶來自中國。 國內(nèi)外研究與技術(shù)現(xiàn)狀 智能人群監(jiān)控的研究現(xiàn)狀 目前，國內(nèi)的安全防范工作中，智能人群估計領(lǐng)域基本還是一項空白，相關(guān)的文獻(xiàn)和技 術(shù)資料很少，基礎(chǔ)理論和相關(guān)技術(shù)不多，沒有成熟的產(chǎn)品，國外在人群運動分析方面研究較多。 ② 利用閉路電視監(jiān)控某一場景。 ② 易造成漏報。 近年來，對人群的研究越來越引起人們的關(guān)注，對人群狀態(tài)和行為的研究也越來越多，而人群研究的前提是要弄清如何對人群進(jìn)行適當(dāng)?shù)拿枋觥? 人群運動估計的傳統(tǒng)方法是人工估計，但這種方法比較主觀，不能做定量判斷。 Davies 和 Chow 的方法在人群密度較高時，由于人群遮擋現(xiàn)象，測量值與人群人數(shù)之間的線性關(guān)系消失，導(dǎo)致誤差很大，且這些方法要求提供場景的背景圖像。塊匹配運動估計算法算法簡單，便于 VLSI 實現(xiàn)，被廣泛應(yīng)用。 論文主要工作 在視頻運動估計方面，相關(guān)技術(shù)比較多，也比較成熟，而在人群運動估計方面，主流技術(shù)則顯得較不成熟，各種算法層出不窮，用得最多的只有幾種，其中關(guān)鍵就在于對時間性和空間性的要求，隨著科學(xué)技術(shù)的發(fā)展，對這兩點的要求已不再那么強烈，注意力已轉(zhuǎn)移到性能上，一般來說，性能越好，算法越復(fù)雜，而 OpenCV 作為一個開源視覺庫，全部由 C 語言寫就，因此，這是一個十分強大的圖像視覺處理工具，對細(xì)微處的處理很好，其功能接口都為函數(shù)，程序員只需調(diào)用函數(shù)便可完成一系列高效高質(zhì)量的操作。介紹運動估計，把塊匹配法分為各個模塊，并對其算法進(jìn)行介紹與分析，同時在最后得出各個模塊最合適的算法； 第 3 章：算法分析與設(shè)計。本章對全文工作以及畢業(yè)收獲進(jìn)行總結(jié)，指出了還需改進(jìn)的地方。它把圖像域分割成互相不重疊的稱為塊的小區(qū)域，并且假定每一個塊內(nèi)的運動都可以用一個簡單的參數(shù)模型特征化，如果快足夠小，那么這種模型是相當(dāng)合理 的。因此，本文提出基于塊匹配的人群運動估計（ BMA）。并且假定每一個塊內(nèi)的運動只做 相等的平移同時可以用一個簡單的參數(shù)模型特征化。 塊匹配的原理如圖 21。 四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運動估計 7 圖 21 塊匹配原理圖 為了提高圖像質(zhì)量，加快估計速度是運動估計算法的研究目標(biāo) 之一 。如果采用的算法初始步長太大，而原點 (以下均指待搜索塊的中心點在參考幀中的相同位置的對應(yīng)點，而不是坐標(biāo)位置的 真正原點 )又不是最優(yōu)點，有可能使快速搜索跳出原人群的運動估計點周圍的區(qū)域 (這些區(qū)域可能包含最優(yōu)點 )而去搜索遠(yuǎn)距離的點，導(dǎo)致搜索方向的不確定性，這就有可能陷入局部最優(yōu)。 下面舉例說明幾種常見的預(yù)測方法。改進(jìn)的方法是利用運動矢量的相關(guān)性來預(yù)測起點。比較典型的是 ―平均預(yù)測 ‖，在 中使用三個相鄰塊的運動矢量的中值作為當(dāng)前塊的運動矢量的預(yù)測值。這種方法在保證精度的基礎(chǔ)上利用運動矢量相關(guān)性從而大大減少了計算量。若在某一個點 (x,y)處 MAD(dx,dy)達(dá)到最小，則該點為要找的最優(yōu)匹配點。 SAD 即求和絕對誤差，其定義如下 : （ 4） 搜索策略 搜索策論選擇恰當(dāng)與否對運動估計的準(zhǔn)確性，運動估計的速度有很大的影響。 另外三步法、二維對數(shù)法、交叉法等主要是通過限制搜索位置的數(shù)目來減少計算量。為了減小運動估計計算量 ，出現(xiàn)了各種塊匹配算法，它們只是搜索策略各有不同 ，其中搜索精度最高的是全搜索法，但由于計算復(fù)雜度高，不宜于實時應(yīng)用，為此人們提出了各種改進(jìn)的快速算法。 ② 算法描述 : Setpl:從原點出發(fā)，按順時針方向由近及遠(yuǎn)，在每個像素處計算 SAD 值，直到遍 歷搜索范圍內(nèi)的所有點。 (2)二維對數(shù)法 (TDL， TwoDimensional Logarithmic) 二維對數(shù)搜索法由 和 提出，它開創(chuàng)了快速算法的先例，分多個階段搜索，逐次減小搜索范圍直到不能再小時結(jié)束。若為 MBD 點位于中心點，則保持中心點位置不變，將步長減半，構(gòu)成 ―十 ‖字形點群，在五個點處計算。 ④ 算法分析 :TDL 算法搜索時，最大搜索點數(shù)為 2+7lbW，這里 W 表示最大偏移量max(dxmax,dymax)。 TDL 算法的前提是假設(shè)搜索區(qū)域內(nèi)只有一個極小值點，如果搜索區(qū)域內(nèi)存在多個極小值點時，該方法找到的可能是局部最小點。 ① 基本思想 :TSS 算法的基本思想是采用一種由粗到細(xì)的搜索模式，從原點開始，按一定步長取周圍 8 個點構(gòu)成每次搜索的點群，然后進(jìn)行匹配運算，跟蹤最小塊誤差MBD 點。否則，重復(fù) Step 2。 圖 24 三步搜索法搜索過程 ④ 算法分析 :TSS 算法搜索時，整個過程采用了統(tǒng)一的搜索模板，使得第一步的步長過大，容易引起誤導(dǎo)，因此對小運動模式的效率較低 。 Step 2:以上一步的 MBD 點為中心點，步長減半，繼續(xù)進(jìn)行 ―‖字形的五點搜索。若上一步 MBD 點處于中心點、左下角或右上角，則做 ―十 ‖字形搜索 。圖中每個點上的數(shù)字表明了每個階段搜索時計算的候選塊的位置，點 [+4， +4]、 [+6， +21]是第一、第二步搜索的MBD 點。 圖 25 交叉法搜索過程 (5)四步搜索法 (FSS， Four Step Search) 四步搜索法是 1996 年由 Lai一 man Po。若 MBD 點位于中心點，則跳到 Step 4。 若上一步 MBD 點位于窗口的四邊中心點處，則只需再搜索 3 個檢測點，如圖 26c所示 。 圖 26 四步搜索法的搜索模塊（ a,b,c,d） ③ 搜索過程圖示 :圖 27 是 FSS 搜索的一個具體實例。圖 中每個點上的數(shù)字表明了每個階段搜索時計算的候選點的位置。 (6)菱形搜索法 (DSS， Dimaond Seaerh) 菱形搜索算法最早由 Shan Zhu 和 Kaikuang 兩人提出，后又經(jīng)過多次改進(jìn)，已成四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運 動估計 14 為目前快速匹配算法中性能最優(yōu)異的算法之一。由于這個誤差表面通常不是單調(diào)的，所以如果搜索窗口太小，就容易陷入局部最優(yōu) 。 圖 28 搜索模塊 ② 算法描述 : Step 1:用 LDSP 在搜索區(qū)域中心及周圍 8 個點處進(jìn)行匹配計算，若 MBD 點位于中心點，則進(jìn)行 step3。 Step 3:以上一次找到的 MBD 點為中心點，將 LDSP 換為 SDSP，在 5 個點處計算，找出 MBD 點，該點所在位置即為最佳運動矢量。先用 LDSP 搜索，由于步長過大，搜索范圍廣，可以進(jìn)行粗定位，使搜索過程不會陷于局部最小 。由于這些算法主要利用運動矢量的均勻分布模式進(jìn)行搜索，其搜索步長較大，因此可能導(dǎo)致搜索方向的不確定和搜索的局部性。除了搜索模型的形狀對搜索的影響之外，搜索模型的大小以及搜索策略對搜索速度和圖像質(zhì)量同樣有影響。不過 由于算法搜索的是匹配塊，匹配并不與實際的運動有好的相關(guān)性，在忽略遮擋的前提下，采用過于快速的搜索算法可能會產(chǎn)生較大的誤差，而隨著科技日新月異，算法執(zhí)行的時間也在大大縮短，在精度的方面考慮的更多，本文采用的塊匹配算法為全搜索法。 OpenCV 由以下幾個對立的子庫組成： 1) CXCORE： 包含數(shù)據(jù)結(jié)構(gòu)，矩陣運算，數(shù)據(jù)變換，對象持久，內(nèi)存管理，錯誤處理，動態(tài)裝載，文本和基本的數(shù)學(xué)功能等； 2) CV： 圖像處理和計算機視覺算法（圖像結(jié)構(gòu)分析，運動描述，跟蹤，模式識別和攝像機標(biāo)定），只存在于 中，今后的版本把 CV 中的功能分散到了其他子庫中去； 3) HIGHGUI： 用戶交互部分 (圖形界面，圖像視頻讀寫，系統(tǒng)調(diào)用函數(shù) )； 4) CVAUX： 一些實驗性的函數(shù) (三維跟蹤等 )； 5) Machine Learning (ML)： 包含許多聚類，分類和數(shù)據(jù)分析函數(shù)； 6) CVCAM： 攝像機借口，在 以后的版本中被移除； 7) Haaartreining： 如何訓(xùn)練 boosted 級聯(lián)物體分類器。 本程序 使用 OpenCV 在實現(xiàn)中用到的各種數(shù)據(jù)結(jié)構(gòu)與函數(shù)如下： (1) cxcore ： CvMat， cvCreateMat， cvReleaseMat ， IplImage ， cvCreateImage，cvReleaseImage， cvSetZero， ConvertScale， cvCmpS， cvCopy， GetReal*D， cvLine，四川大學(xué)本科畢業(yè)論文 基于塊匹配的人群運動估計 17 cvPoint； (2) highgui： CvCapture， cvCreateFileCapture， cvReleaseCapture， cvQueryFrame，cvSetCaptureProperty， cvGetCaptureProperty， cvCreateTrackbar， cvNamedWindow，cvMoveWindow， cvDestroyWindow， cvShowImage， cvWaitKey； (3) cv： cvCvtColor， cvSmooth， cvCalcOpticalFlowBM； (4) c 語言中數(shù)學(xué)庫里的函數(shù) ： ceil； (5) 其他函數(shù) ： cvsize,cvpoint。 1. 在這些數(shù)據(jù)類型中最簡單的就是 CvPoint。 CvPoint 有兩個變體類型； CvPoint2D32f 和 CvPoint3D32f。 CvMat OpenCV 里有三大數(shù)據(jù)結(jié)構(gòu)： CvArr、 CvMat、 IplImage，它們遵循面向?qū)ο蟮乃枷?。例如，一個用于新建一個二維矩陣的例程具有以下原型： cvMat* cvCreateMat ( int rows, int cols, int type )。 /* 數(shù)據(jù)引用計數(shù) */ union { uchar* ptr。 double* db。 }。 else int rows。 cvReleaseMat 用來釋放 CvMat， cvReleaseMat（ amp。 int ID。 char colorModel[4]。 int align。 struct _IplImage* maskROI。 char* imageData。 char* imageDataOrigin。因為在圖像中，往往將深度和通道數(shù)分開處理，而在矩陣中，往往同時表示它們 . 可用的深度值