1、本科生畢業論文（設計）題 目 基于塊匹配的人群運動估計基于塊匹配的人群運動估計學 院 軟軟 件件 學學 院院專 業 軟軟 件件 工工 程程學生姓名 學 號 年級 指導教師 教務處制表二 一 年六月一日基于塊匹配的人群運動估計基于塊匹配的人群運動估計軟件工程摘要摘要 智能化人群監控是智能視頻監控研究中的一個重要課題，它作為智能監控中的一項關鍵技術，在人群管理、公共場所設計、虛擬環境建模、視覺監控、智能環境模擬等方面都有著重要的應用價值。隨著經濟社會的發展，各種公共場地和設施中的人群流動越來越頻繁。如何對公共場合的人群進行有效管理與控制，是不得不考慮的重大問題。智能化人群監控技術應運而生，它主要包

2、括人群的密度估計和運動估計兩部分內容。本文著手解決人群運動估計這一塊，智能化運動估計可以用于人群的監測和管理，也可應用于商業領域，如市場調查、交通安全以及建筑設計領域等。它們能夠直接或間接地提高上述場合工作人員的工作效率和建筑設施的利用率，因此對人群密度估計和運動估計方法的研究有著深遠的意義和廣闊的前景。本文結合 OpenCV，采用塊匹配算法對人群的運動進行估計，并在功能實現前對OpenCV 與塊匹配各重要環節有具體分析。主題詞主題詞 人群監控；人群運動估計；塊匹配；OpenCV Crowd motion estimation based on BMASoftware EngineeringS

3、tudent： YuMingshu Adviser: XiaoHualiAbstract Intelligentized crowd surveillance tecllIlology is an important research subfield in intelligem video surveillance systemAs a key tecllnology of intelligent surveillarlce，it is of great value in a large number of applications such as crowd management，publ

4、ic space design virtual environments simulate，visual surveillanlce，intelligent enviroments aIlalysis,etcWith the development of economic society, the crowd in various kinds of public places flows more and more frequently. How to manage and control the crowd effectively comes to be an important issue

5、 which we have to consider nowadays. Intelligentized crowd surveillance technology arises at the very moment. It mainly includes both density estimation and motion estimation.This paper set about the crowd motion estimation. Intelligentized crowd motion estimation can be used for monitoring and mana

6、ging the crowd, at the same time, it can also be used for market survrey in the commercial field，traffic safety and architectural design field,etc. it can help staff members in the above mentioned occasions improve working efficiency and improve utilization ratio of building facilities directly or i

7、ndirectly,so there is far-reaching meaning and wide prospect in crowds density and motion estimation research.According to OpenCV, this paper use BMA(Block Matching Algorithm) for crowd motion estimation，and before the function running ,it has a specific analysis about OpenCV and the important case

8、of BMA.Key Words crowd surveillance；crowd motion estimation；Block Matching Algorithm；OpenCV目目 錄錄1 1緒論緒論.1 11.1 研究背景.11.1.1智能監控.11.1.2人群監控的提出.11.1.3運動估計.21.1.4塊匹配算法.21.1.5OpenCV.21.1.6論文工作構思.31.2 國內外研究與技術現狀.31.2.1智能人群監控的研究現狀.31.2.2運動估計方法的研究現狀.41.2.3塊匹配現狀.41.3 論文主要工作 .51.4 論文組織與結構 .52 2塊匹配算法介紹及分析塊匹配算法

9、介紹及分析.6 62.1 運動估計.62.2 塊匹配基本思想.62.2.1 初始搜索點的選擇.72.2.2 塊匹配準則.82.2.3 搜索策略.82.3 典型的塊匹配算法.92.4 各模塊擬采用的算法.153 3人群運動估計的塊匹配算法實現人群運動估計的塊匹配算法實現.16163.1 實現工具 OPENCV.163.2 CXCORE.H.173.2.1 CvPoint,CvSize.173.2.2 CvMat.173.2.3 IplImage.193.2.4 其他函數.213.3 CV.H.243.3.1 cvCvtColor.243.3.2 cvSmooth.263.3.3 cvCalcOp

10、ticalFlowBM.273.4 HIGHGUI.H.283.4.1 CvCapture.283.4.2 窗口函數.283.4.3 cvWaitKey.313.5 算法實現 .313.5.1 圖像處理（視頻處理）.323.5.2 塊匹配.373.5.3 過濾非運動的物體.393.5.4 連線.403.6 程序算法流程圖 .413.7 程序實現截圖 .424 4軟件的測試軟件的測試.45454.1 測試環境 .454.1.1 硬件環境.454.1.2 軟件環境.454.2 測試步驟 .454.2.1 測試總體目標.454.2.2 測試計劃實施步驟.454.3 測試用例 .454.3.1 分支測

11、試.454.3.2 集成測試.554.4 測試結果分析 .575 5總結和展望總結和展望.58585.1 工作總結 .585.2 心得體會 .58致致 謝謝.6262附錄附錄 1 1 程序源代碼程序源代碼 .6363附錄附錄 2 2 翻譯（原文和譯文）翻譯（原文和譯文） .76761緒論緒論1.1 研究背景研究背景1.1.1智能監控智能監控隨著視頻分析技術和人工智能技術的發展，智能視頻監控已成為一個非常活躍的研究領域，它涉及信號分析、圖像處理、計算機視覺、機器學習、模式識別等多門學科，主要研究圖像序列中感興趣目標的檢測、跟蹤、行為分析與識別等問題。目前，智能監控的研究大多集中于少數目標個體上。

12、如對單個人的檢測、跟蹤、行為識別，對車輛的監控，以及人和車輛的交互行為等。智能化人群監控是智能視頻監控研究中的一個重要課題，它作為智能監控中的一項關鍵技術，在人群管理、公共場所設計、虛擬環境建模、視覺監控、智能環境模擬等方面都有著重要的應用價值1。1.1.2人群監控的提出人群監控的提出隨著社會的發展，公共安全需求的提高，群體運動分析受到越來越多人的關注,美國人口普查局在 08 年的一份報告中指出，1999 年，世界人口達到 60 億，比 1960 年翻了一倍。08 年全球人口已達到 67 億，預計到 2050 年，全球人口將超過 90 億。隨著人口的增加，人群活動日益增加，相對應地，人群安全問

13、題也越來越突出，對人群的分析研究分別在社會學、心理學、建筑學、計算機等各個學科受到了極大的關注。現代社會，伴隨經濟的發展 ,各種高層建筑、地下建筑和大型商業娛樂設施也越來越多 ,同時出入或圍繞這些建筑物的人群也在加大，一旦擁擠人群發生突發事件,容易造成群死群傷事故，因此必須考慮到人群的安全問題。人們經過探索，最終提出了人群監控這一技術2。人群監控是借助于數字圖像處理技術對某一區域的人群進行監控,它在社會生活和生產的許多領域有著廣闊的應用前景3。傳統的人群監控通過監控場景所安裝的閉路電視進行人工監控，費時費力且缺乏實時性，不能做到每時每刻監控，且比較主觀，不能做定量判斷，起不到預防的作用且容易發

14、生漏報現象。隨著智能化技術的發展，智能化的人群監控技術已成為研究的熱點?，F代數字圖像處理技術的發展 ,為解決上述問題提供了途徑。將圖像處理、模式識別、計算機視覺等技術應用在人群監控中 ,可以達到對人群的自動、客觀、實時、定量分析。自智能化人群監控技術提出以后 ,人們對其進行了廣泛研究 ,目前已有許多算法 ,一些實用的系統也開始應用在廣場、車站等場合的人流監控中。人群監控分為人群密度估計和人群運動估計，本文著手解決人群運動估計。1.1.3運動估計運動估計考慮到人群密度和運動的自動監測量和以及智能檢測人群分布和流量的重要性，需要一個不管在人群密度大或小都能正常測量的新技術，但是這是一個困難的問題，

15、因為在視頻顯示人群中，通常只會出現一部分人，重疊現象很嚴重4。從而分別提出了密度估計法與運動估計法這兩類技術。密度估計法提出一種紋理法分析法，它可以在重疊現象嚴重的視頻中進行較精確的估計5，這里略過。運動估計法的基本思想是將圖像序列的每一幀分成許多互不重疊的宏塊，并認為宏塊內所有象素的位移量都相同，然后對每個宏塊到參考幀某一給定特定搜索范圍內根據一定的匹配準則找出與當前塊最相似的塊，即匹配塊，匹配塊與當前塊的相對位移即為運動矢量。視頻壓縮的時候，只需保存運動矢量和殘差數據就可以完全恢復出當前塊。 運動估計和運動補償是 AVS 中去除時間冗余的主要方法，作為視頻壓縮編碼系統的核心算法，占整個系統

16、運算量的60%-80%，它采用多種宏塊劃分方式，1P4 像素插值、雙向估計和多參考幀等技術大大提高了編碼效率，但同時也給編解碼器增加了一定的復雜度。運動估計算法是視頻壓縮編碼的核心算法之一。高質量的運動估計算法是高效視頻編碼的前提和基礎。其中塊匹配法（BMA, Block Match Algorithm）由于算法簡單和易于硬件實現，被廣泛應用于各視頻編碼標準中。1.1.4塊匹配算法塊匹配算法塊匹配法的基本思想是先將圖像劃分為許多子塊，然后對當前幀中的每一塊根據一定的匹配準則在相鄰幀中找出當前塊的匹配塊，由此得到兩者的相對位移，即當前塊的運動矢量。在 H.264 標準的搜索算法中，圖像序列的當前

17、幀被劃分成互不重疊 1616 大小的子塊，而每個子塊又可劃分成更小的子塊，當前子塊按一定的塊匹配準則在參考幀中對應位置的一定搜索范圍內尋找最佳匹配塊，由此得到運動矢量和匹配誤差。運動估計的估計精度和運算復雜度取決于搜索策略和塊匹配準則。這里使用 H.264 推薦算法UMHexagonS（Unsymmetrical-cross Multi-Hexagon-grid Search）作為 DSP 實現的算法參考，與 FS 算法比較，它在保證可靠搜索精度的前提下大幅降低搜索復雜度。同時使用絕對差和（SAD, the Sum of Absolute Difference）標準作為匹配準則，它具有便于硬件

18、實現的優點。1.1.5OpenCV計算機視覺是在圖像處理的基礎上發展起來的新興學科，OpenCV(Open Source Computer Vision Library，開源計算機視覺庫) 是一種數字圖像處理和計算機視覺的函數庫，它是一個跨平臺的開源計算機視覺庫，最初由 Intel 公司微處理器實驗室(IntelS Microprocessor Research Lab)的視覺交互組(The Visual Inter-activity Group)開發6，是 Intel 資助的兩大圖像處理利器之一，以 BSD 許可證授權發行，可免費用于商業和研究領域，它可以在 Windows 系統、Linux

19、 系統、Mac0Sx 系統等操作平臺上使用，也可以和其他編程工具結合，以滿足不同的使用要求。它包含許多常用的算法，為圖像處理、模式識別、三維重建、物體跟蹤、機器學習和線性代數提供了各種各樣的算法7。它已經廣泛應用于對實時性要求較高的計算機視覺和模式識別系統的開發。截至 2009 年 8 月，在 的下載次數已經超過 2 200 000次，大量用戶來自中國。1.1.6論文工作構思論文工作構思關于人群運動估計，本文用到的方法是塊匹配，工具有 OpenCV 和 vc6，程序用 C和 C+編寫。為了更好的進行人群運動估計，前期準備必不可少，1. 學習圖像處理的基本原理，了解人群監控的意義，采集若干組實驗

20、用視頻序列；2. 了解現有圖像處理的運動估計方法，學習 OpenCV 視頻處理的基本知識，掌握塊匹配的主要方法，利用 OpenCV 實現塊匹配的原理和技術。完成以上兩點后，利用 C 和 C+編寫程序實現功能。1.2 國內外研究與技術現狀國內外研究與技術現狀1.2.1智能人群監控的研究現狀智能人群監控的研究現狀目前，國內的安全防范工作中，智能人群估計領域基本還是一項空白，相關的文獻和技術資料很少，基礎理論和相關技術不多，沒有成熟的產品，國外在人群運動分析方面研究較多。本文的研究對象是運動群體(這里的群體特指人群)，研究內容是運動人群的運動估計。傳統的保障人群安全的途徑主要有:人群的密度估計與運動

21、估計采用物理方法修正建筑物。在一些容易發生人群聚集的地方，采取適當地修正現有建筑物的方法，比如在人多的地方增加出入口等。利用閉路電視監控某一場景。閉路電視對周圍環境進行例行地掃描來查找發生危險的地方，并有專門的工作人員盯著屏幕，以便發生情況及時通報并采取措施。但是這樣做主要有如下缺點:不能起到預防的作用。即使人可以根據經驗來發出危險警告，但由于人的主觀性太強，很容易發生預告太晚或者錯誤預告的情況。易造成漏報。當人群己經發生擁塞時，一般采取的方法是:關閉人群正在大量涌入的入口。這種方法雖然解決了建筑物某個入口處的擁擠問題，但是人群很可能又涌向別的入口造成新的擁擠。所以這種做法往往不能從根本上解決

22、問題。近年來，對人群的研究越來越引起人們的關注，對人群狀態和行為的研究也越來越多，而人群研究的前提是要弄清如何對人群進行適當的描述。雖然人群由獨立個體組成，而每一個個體又有他自己的行為模式，但作為總體的人群有它整體性的特征，且可被描述出來。要想用精確的數學模型來描述人群的狀態和行為非常困難，但我們仍然看到了一些能夠逼近人群真實行為的數學模型的出現，如 stliiG.K.的人群動力學，Corwd Dynamic Limted 公司依據 StlilG.K.的數學模型應用 AuotCAD 做出了一些建筑設施的設計方案。1.2.2運動估計方法的研究現狀運動估計方法的研究現狀作為視頻編碼器中計算量最大的

23、一個模塊，運動估計能夠有效地減少幀問相關性，因此被廣泛用于各種視頻編碼標準中，如 MPEG-1、MPEG-2、MPEG-4、H26l、H263 和 H264/AVC 等8。人群運動估計的傳統方法是人工估計，但這種方法比較主觀，不能做定量判斷。二十世紀以來，人群人群密度和運動估計的自動方法逐漸發展起來。在密度估計上主要有Davies，Chow，Marana 等人的方法；在運動估計上主要有 Rourke 等人的方法。這些方法各有不足。Davies 和 Chow 的方法在人群密度較高時，由于人群遮擋現象，測量值與人群人數之間的線性關系消失，導致誤差很大，且這些方法要求提供場景的背景圖像。Marana

24、 的方法雖然可以解決高密度人群的估計問題，但計算量較大，處理時間較長，而且該方法沒有考慮攝像機透視效應問題。Rourke 等人的人群運動估計的方法都限于低密度人群，如果人群密度較高，出現個體間的相互遮擋使得個體信息提取不全對，就會遇到困難9。1.2.3塊匹配現狀塊匹配現狀在主流視頻壓縮標準(如 H.26x，MPEG 系列等)中，視頻系統編碼器的效率主要取決于運動估計算法，而運動估計的效率主要體現在圖像質量、壓縮碼率和搜索速度 3 個方面10， 這些由采用的搜索策略、匹配準則和初始搜索點的選擇等因素決定。塊匹配運動估計算法算法簡單，便于 VLSI 實現，被廣泛應用。目前，其研究主要集中在：1)利

25、用不同幀相同位置塊和相同幀內相鄰塊運動矢量的相關性，從同幀中左上、上、左等塊的運動矢量及前一幀或前幾幀相同位置塊的運動矢量中挑選出當前塊運動矢量的最優初始值 然后再按照某一種算法進行搜索；2)不斷改進運動估計匹配模板的形狀和大小，旨在減少搜索點數，從而減少搜索時間，提高編碼速度；3)通過數學不等式來改進目標函數，通過判斷提前結束搜索，達到節約運算量和運算時間的目的。其中第 2 點通過改進模板的方法來減少搜索點數更是當前的研究熱點，出現了許多算法。研究方向。1.3 論文主要工作論文主要工作在視頻運動估計方面，相關技術比較多，也比較成熟，而在人群運動估計方面，主流技術則顯得較不成熟，各種算法層出不

26、窮，用得最多的只有幾種，其中關鍵就在于對時間性和空間性的要求，隨著科學技術的發展，對這兩點的要求已不再那么強烈，注意力已轉移到性能上，一般來說，性能越好，算法越復雜，而 OpenCV 作為一個開源視覺庫，全部由 C 語言寫就，因此，這是一個十分強大的圖像視覺處理工具，對細微處的處理很好，其功能接口都為函數，程序員只需調用函數便可完成一系列高效高質量的操作。而本程序在人群運動估計這一方面運用了一種全新的處理方法，即利用 OpenCV 完成塊匹配法運動估計，其真正達到了高性能高密度。1.4 論文組織與結構論文組織與結構第 1 章：緒論。主要介紹了人群監控發展和應用，以及本論文的研究背景和研究工作，

27、利用 OpenCV 實現基于塊匹配的人群運動估計的設計目的；第 2 章：塊匹配法各模塊算法背景與分析。介紹運動估計，把塊匹配法分為各個模塊，并對其算法進行介紹與分析，同時在最后得出各個模塊最合適的算法；第 3 章：算法分析與設計。說明運動估計視頻處理的各個步驟所需處理，并分析處理所需算法，介紹背景建模；第 4 章：算法的實現。介紹實現該算法的工具，并對程序各模塊一一實現；第 5 章：算法的驗證和評價。對算法進行測試，對結果進行分析；第 6 章：結論。本章對全文工作以及畢業收獲進行總結，指出了還需改進的地方。2塊匹配算法介紹及分析塊匹配算法介紹及分析本章主要介紹塊匹配算法的各個模塊，及各模塊所用

28、到的算法。2.1 運動估計運動估計運動估計已發展得較為成熟，最常用于人群監控與視頻壓縮編碼。基于塊的運動估計和補償是視頻編碼中最通用的算法。它把圖像域分割成互相不重疊的稱為塊的小區域，并且假定每一個塊內的運動都可以用一個簡單的參數模型特征化，如果快足夠小，那么這種模型是相當合理的。目前這種方法被廣泛用于視頻標準變換運動補償濾波和采用基于塊的運動補償進行的數字視頻壓縮 1112 。在一幅幅復雜的人群圖像中，如果依靠每個步行者的個體信息來估計人群總體的運動，必須要分離出每個個體的運動。但要做到這點并不容易，因為在開放的空間中，一個步行者可能向各個方向移動，且步行者的身體各部分的移動方式也各不相同，

29、進而，當人群密度較大，個體之間有相互遮擋時，這就變得更加困難，甚至是不可能的。因此，本文提出基于塊匹配的人群運動估計（BMA） 。這種方法由于實現較簡單且容易而受到廣泛關注。BMA 并不借助人群中個體的信息，而是通過統計視頻中各宏塊的運動矢量估計出人群整體的運動 13 。2.2 塊匹配基本思想塊匹配基本思想基于塊匹配法的運動估計的基本思想就是將當前幀分成互不重疊的大小為 MN 的宏塊(一般情況下 M=N)，然后對當前幀中的每一個塊都在參考幀中的一定區域，即搜索窗口內，按照一定的匹配準則搜索與之具有最小匹配誤差的塊(Minimal DistortionBlock，MDB)，該塊即為當前塊的匹配塊

30、，由匹配塊與當前塊的相應位置計算出運動位移，所得運動位移即為當前塊的運動矢量。并且假定每一個塊內的運動只做相等的平移同時可以用一個簡單的參數模型特征化。如果塊足夠小，那么這種模型是相當合理的。匹配塊與當前塊之間的坐標位移就是運動矢量，匹配塊與當前塊的對應象素點逐個做差就的到差值塊?；谶@樣的方法這樣，當前幀中的每一個塊都可以用一個差值塊和一個運動矢量來表示，對當前幀的編碼就轉化為對每一塊的差值塊和運動矢量的編碼。塊匹配的原理如圖 2-1。運動估計算法的整體效率主要體現在初始搜索點的選擇、匹配準則和運動搜索策略三個方面。本程序主要用基于塊的運動方式開發出的運動估計算法塊匹配算法。塊匹配算法由于它

31、具有較少的硬件復雜度，容易在超大規模集成電路中實現，因此被認為是最通用的算法。 圖 2-1 塊匹配原理圖為了提高圖像質量，加快估計速度是運動估計算法的研究目標之一。通常是通過研究初始搜索點的選擇、匹配準則和運動搜索策略等來提高算法效率的13。2.2.1 初始搜索點的選擇初始搜索點的選擇(1)直接選擇參考幀對應塊的中心位置。這種方法簡單，但容易陷入局部最優點。如果采用的算法初始步長太大，而原點(以下均指待搜索塊的中心點在參考幀中的相同位置的對應點，而不是坐標位置的真正原點)又不是最優點，有可能使快速搜索跳出原人群的運動估計點周圍的區域(這些區域可能包含最優點)而去搜索遠距離的點，導致搜索方向的不

32、確定性，這就有可能陷入局部最優。(2)選擇預測的起點。由于相鄰塊之間和相鄰幀之間具有很強的相關性，因而許多算法都利用這種相關性先對初始搜索點進行預測，以預測點作為搜索起點。大量實驗證明預測點越靠近最優匹配點，越會使得搜索次數減少。下面舉例說明幾種常見的預測方法。方法方法 1:基于 SAD(the Sum of Absolute Differences)值的起點預測方法。分別求出當前塊與其相鄰塊間的 SAD 值，然后選取 SAD 最小的塊的運動矢量作為預測值。這種方法預測精度高，但計算 SAD 值的時間開銷大。改進的方法是利用運動矢量的相關性來預測起點。方法方法 2:利用相鄰塊和相鄰幀對應塊的運

33、動矢量來預測當前塊的搜索起點。序列圖像的運動矢量在空間、時間上具有很強的相關性。由于保存前一幀運動矢量信息在解碼端需要占用大量內存，使得系統復雜化，故大多算法僅考慮同幀塊的空間相關性來預測運動。比較典型的是“平均預測”，在 H.263 中使用三個相鄰塊的運動矢量的中值作為當前塊的運動矢量的預測值。方法方法 3:基于相鄰運動矢量相等的起點預測方法。如果當前塊的各相鄰塊的運動矢量相等，則以其作為當前塊運動矢量的預測值;否則，使用方法 1 求出當前塊與其相鄰塊間的 SAD 值，然后選取 SAD 值最小的塊作為預測起點。這種方法在保證精度的基礎上利用運動矢量相關性從而大大減少了計算量。運動估計的復雜度

34、主要取決于匹配計算量和所采用的搜索算法這兩個方面14。在下一節中將介紹在運動估計常用的一些匹配準則。2.2.2 塊匹配準則塊匹配準則運動估計算法中常用的匹配準則有三種，即最小絕對值差(MAD)、最小均方誤差(MSE)和歸一化互相關函數(NCCF)，它們分別定義如下:(1) 最小絕對值差: （1）式中，B 代表 MN 宏塊，(dx,dy)為運動矢量，fk與 fk-1分別為當前幀和前一幀的灰度值，若在某一個點(x，y)處 MAD(dx,dy)達到最小，則該點為要找的最優匹配點。若在某一個點(x,y)處 MAD(dx,dy)達到最小，則該點為要找的最優匹配點。(2)最小均方誤差: （2）能夠使 MS

35、E 值最小的點為最優匹配點。(3)歸一化互相關函數： （3）式中 NCCF 的最大值點為最優匹配點。在運動估計中，匹配準則對匹配的精度影響不是很大，由于 MAD 準則不需要作乘法運算，實現簡單、方便，所以使用最多，通常使用 ASD 代替 MAD。SAD 即求和絕對誤差，其定義如下: （4） 2.2.3 搜索策略搜索策略搜索策論選擇恰當與否對運動估計的準確性，運動估計的速度有很大的影響。有關搜索策略的研究主要是解決運動估計中存在的計算復雜度和搜索精度這一矛盾。如全搜索法，它對搜索范圍內的每一個像素點進行塊匹配運算以得到一個最優的運動矢量。不過，較大的搜索窗通常會使得搜索點增多，從而加大計算量，因

36、此，搜索距離的設定需綜合考慮具體視頻的運動特性、運動估計的質量以及算法的計算量等因素，以獲得最佳的估計性能15。另外三步法、二維對數法、交叉法等主要是通過限制搜索位置的數目來減少計算量。這以后的許多搜多策略都是為了平衡搜索精度與計算速度而產生的。2.3 典型的塊匹配算法典型的塊匹配算法在 MPEG2-4 視頻編碼算法中，運動估計(ME)的計算量占整個編碼計算量的 2/3以上16。在視頻編碼系統中，運動估計處理消耗近 50%的功耗16。為了減小運動估計計算量，出現了各種塊匹配算法，它們只是搜索策略各有不同，其中搜索精度最高的是全搜索法，但由于計算復雜度高，不宜于實時應用，為此人們提出了各種改進的

37、快速算法。下面介紹幾種常用的經典算法。 (l)全搜索法全搜索法(FS，Full Seacrh method)算法思想:全搜索法也稱為窮盡搜索法，或螺旋向外搜索法，是對搜索范圍內所有可能的候選位置計算其 SAD(i，j)值，從中找出最小 SAD，其對應偏移量即為所求運動矢量。此算法計算量雖大，但最簡單，可靠，找到一定是全局的最優點。算法描述:Setpl:從原點出發，按順時針方向由近及遠，在每個像素處計算 SAD 值，直到遍歷搜索范圍內的所有點。StPe2:在所有的 SAD 中找到最小塊誤差(MBD)點(即 SAD 最小值的點)，該點所在位置即對應的最佳運動矢量。模板及搜索過程圖示:如圖 2-2

38、所示。 圖 2-2 全搜索法搜索過程算法分析:FS 算法是最簡單、最原始的塊匹配算法，由于可靠，且能夠得到全局最優的結果，通常是其它算法性能比較的標準，但它的計算量很大，這就限制了在需要實時性較強的場合的應用，所以有必要進一步研究其它快速算法。(2)二維對數法二維對數法(TDL，Two-Dimensional Logarithmic)二維對數搜索法由 J.R.Jain 和 A.K.Jaini 提出，它開創了快速算法的先例，分多個階段搜索，逐次減小搜索范圍直到不能再小時結束?；舅枷?二維對數搜索法是由原點開始，以“十”字形分布的五個點構成每次搜索的點群，通過快速搜索跟蹤加 MBD 點。算法描述

39、:Step 1:從原點開始，選取一定的步長，在以“十”字形分布的五個點處進行塊匹配計算并比較。Step 2:若 MBD 點在邊緣四個點處，則以該點做為中心點，保持步長不變，重新搜索“十”字形分布的五個點;若為 MBD 點位于中心點，則保持中心點位置不變，將步長減半，構成“十”字形點群，在五個點處計算。Step 3:若步長為 1，在中心及周圍 8 個點處找出 MBD 點，該點所在位置即對應最佳運動矢量，算法結束;否則，重復 Step 2。搜索過程圖示:如圖 2-3 所示。算法分析:TDL 算法搜索時，最大搜索點數為 2+7lbW，這里 W 表示最大偏移量max(dxmax,dymax)。若發現新

40、的“十”字形點群的中心點位于搜索區域的邊緣，則步長也減半。后來有人提出應該在搜索的每個階段都將步長減半。所有這些改動都是為了使算法搜索范圍很快變小，提高收斂速度。TDL 算法的前提是假設搜索區域內只有一個極小值點，如果搜索區域內存在多個極小值點時，該方法找到的可能是局部最小點。不能保證找到全局最優點也正是大部分快速搜索算法的缺點。 圖 2-3 二維對數法過程 (3)三步搜索法三步搜索法(TSS，而，而 Three Step Search)三步搜索法與 TDL 類似，由于其簡單、健壯、性能良好的特點，已被人們所重視。若最大搜索長度為 7，搜索精度取 1 個像素，則步長為 4、2、1，共需要三步即

41、可滿足?；舅枷?TSS 算法的基本思想是采用一種由粗到細的搜索模式，從原點開始，按一定步長取周圍 8 個點構成每次搜索的點群，然后進行匹配運算，跟蹤最小塊誤差MBD 點。.算法描述:Step 1:從原點開始，選取最大搜索長度的一半為步長，在中心點及周圍 8 個點處進行塊匹配計算并比較。Step 2:將步長減半，中心移到上一步的 MBD 點，重新在中心點及周圍的 8 個點處進行塊匹配計算并比較。Step 3:在中心點及周圍 8 個點處找出加 MBD 點，若步長為 1，該點所在位置即對應最佳運動矢量，算法結束;否則，重復 Step 2。搜索過程圖示:一個可能的搜索過程如圖 2-4 所示。圖 2-

42、4 中點+4，+4、 +6，+4是第一、第二步的最小塊誤差點。第三步得到最終運動矢量為+7，+5，每個點上的數字表明了每個階段搜索時計算的候選塊的位置。 圖 2-4 三步搜索法搜索過程算法分析:TSS 算法搜索時，整個過程采用了統一的搜索模板，使得第一步的步長過大，容易引起誤導，因此對小運動模式的效率較低。最大搜索點數為 1+8blW，當搜索范圍大于 7 時，僅用三步是不夠的，搜索步數的一般表達式為 lb(dmax+1).(4)交叉法交叉法(CSA，Cross Search Algorithm)1990 年，Chanbari 提出了交叉搜索算法，它也是在 TDL 和 TSS 基礎上為進一步減小

43、計算量而發展起來的快速搜索法。本思想:CSA 是從原點開始，以“”字形分布的五個點構成每次搜索的點群，以TDL 的搜索方法檢測為 MBD 點，僅在最后一步采用“十”字形點群。算法描述:Step l:從原點開始，選取最大搜索長度的一半為步長，在以“”字形分布的五個點處進行塊匹配計算并比較，然后移動中心點。Step 2:以上一步的 MBD 點為中心點，步長減半，繼續進行“”字形的五點搜索。若步長大于 1，則重復 Step 2;若步長為 1，則進行 Step 3。Step 3:最后一步根據為 MBD 點的位置，分別進行“十”字形和“”字形搜索。若上一步 MBD 點處于中心點、左下角或右上角，則做“十

44、”字形搜索;若上一步 MBD 點處于左上角或右下角，則做“”字形搜索。由當前為 MBD 點得到的最佳運動矢量，算法結束。搜索過程圖示:圖 2-5 是 CSA 搜索的一個具體實例。圖中每個點上的數字表明了每個階段搜索時計算的候選塊的位置，點+4，+4、+6，+21是第一、第二步搜索的 MBD 點。第三步箭頭說明了兩種不同的搜索模式。算法分析:CSA 的最大搜索點數為 5+4lbW，搜索速度很快，但是運動補償的效果不是太好。在搜索區域的邊界上有四分之一的點 CSA 沒有考慮到，因此它不適用于較復雜的運動模式。 圖 2-5 交叉法搜索過程(5)四步搜索法四步搜索法(FSS，Four Step Sea

45、rch)四步搜索法是 1996 年由 Lai 一 man Po。和 Wing-Chung Ma 提出的，該算法類似三步法，但它基于現實中序列圖像的一個特征，即運動矢量大多都是中心分布的，從而在 55 大小的搜索窗口上構造了有 9 個檢測點的搜索模板。本思想:TSS 算法第一步用了 99 的搜索窗，這很容易造成搜索方向的偏離，FSS算法首先采用 55 的搜索窗口，每一步搜索窗的中心移向 MBD 點處，且后兩步搜索窗的大小依賴于 MBD 點的位置。算法描述:Step 1:以搜索區域原點為中心選定 5x5 的搜索窗，然后在 9 個檢測點處進行匹配計算，如圖 2-6a 所示。若 MBD 點位于中心點，

46、則跳到 Step 4;否則進行 Step2。Step 2:窗口保持 5x5 大小，但搜索模式取決于上一步的 MBD 點位置。若上一步為 MBD 點位于窗口的四個角上，則另外再搜索 5 個檢測點，如圖 2-6b所示;若上一步 MBD 點位于窗口的四邊中心點處，則只需再搜索 3 個檢測點，如圖 2-6c 所示;若上一步 MBD 點在窗口中心，則跳到 Step 4，否則，進行 Step 3。Step 3:搜索模式同 Step 2，但最終要進行 Step 4。Step 4:將窗口縮小到 33，這時計算出最小誤差點的位置即對應最佳運動矢量，如圖 2-6d 所示。 圖 2-6 四步搜索法的搜索模塊（a,b

47、,c,d）搜索過程圖示:圖 2-7 是 FSS 搜索的一個具體實例。首先搜索點0，2，由于該點處于邊的中心點處，故采用圖 2-6c 的模板進行搜索，結果為2，4;由于該點處于搜索窗的角上，故用圖 2-6b 的模板進行搜索，結果為模板中心點2，41;接著采用圖 2-6d 的模板進行搜索，得到的結果為3，5，故最終得到的運動矢量為3，5。圖中每個點上的數字表明了每個階段搜索時計算的候選點的位置。 圖 2-7 四步搜索法搜索模板算法分析:FSS 是快速搜索算法的又一次進步，它在搜索速度上不一定快于TSS，搜索范圍為7 時，FSS 最多需要進行 27 次塊匹配。但是 FSS 的計算復雜度比TSS 低，

48、它的搜索幅度比較平滑，不至于出現方向上的誤導，所以獲得了較好的搜索效果，在攝像機鏡頭伸縮、有快速運動物體的圖像序列中被廣泛應用。(6)菱形搜索法菱形搜索法(DSS，Dimaond Seaerh)菱形搜索算法最早由 Shan Zhu 和 Kai-kuang 兩人提出，后又經過多次改進，已成為目前快速匹配算法中性能最優異的算法之一。1999 年 10 月，DS 算法被 MPEG-4 國際標準采用并收入驗證模型?；舅枷?搜索模板的形狀和大小不但影響整個算法的運算速度，而且也影響它的性能。塊匹配的誤差實際上是在搜索范圍內建立了誤差表面函數，全局最小點即對應著最佳運動矢量。由于這個誤差表面通常不是單調

49、的，所以如果搜索窗口太小，就容易陷入局部最優;而搜索窗口太大，又容易產生錯誤的搜索路徑。另外，統計數據表明，視頻圖像中進行運動估計時，最優點通常在零矢量周圍(以搜索窗口中心為圓心，兩像素為半徑的圓內)，如圖 2-8a 所示?；谶@兩點事實，DS 算法采用了兩種搜索模板，分別是 9 個檢測點的大模板LDSP 和有 5 個檢測點的小模板 SDSP，如圖 2-8b 和 2-8c 所示。 圖 2-8 搜索模塊算法描述:Step 1:用 LDSP 在搜索區域中心及周圍 8 個點處進行匹配計算，若 MBD 點位于中心點，則進行 step3;否則，到 Step 2。Step 2:以上一次找到的 MBD 點為

50、中心點，用新的 LDSP 來計算，若 MBD 點位于中心點，則進行 Step 3;否則，重復 Step 2。Step 3:以上一次找到的 MBD 點為中心點，將 LDSP 換為 SDSP，在 5 個點處計算，找出 MBD 點，該點所在位置即為最佳運動矢量。搜索過程圖示:圖 2-9 顯示了一個用 DS 算法搜索到運動矢量(一 4，一 2)的例子。搜索共分 5 步，MBD 點分別為(-2，0)、(-3，-1)、(-4，-2)，使用了 4 次 LDSP 和 l 次SDSP，共搜索了 24 個點。算法分析:DS 算法的特點在于它分析了視頻圖像中運動矢量的基本規律，選用了大小兩種形狀的搜索模板 LDSP

51、 和 SDSP。先用 LDSP 搜索，由于步長過大，搜索范圍廣，可以進行粗定位，使搜索過程不會陷于局部最小;當粗定位結束后，可以認為最優點就在 LDSP 周圍 8 個點所圍的菱形區域內，這時再用 SDSP 來準確定位，使搜索不至于有大的起伏，所以它的性能優于其它算法。另外，DS 搜索時各步驟之間有很強的相關性，模板移動時只需要在幾個新的檢測點處進行匹配計算，所以也提高了搜索速度。 圖 2-9 菱形搜索法搜索過程綜上，比較有代表性的算法是三步搜索法(3SS)和二維對數法(2LOGS)等。由于這些算法主要利用運動矢量的均勻分布模式進行搜索，其搜索步長較大，因此可能導致搜索方向的不確定和搜索的局部性

52、。為了解決上述問題，人們提出了利用現實圖像序列運動矢量空間分布中心偏置特性的算法，如四步搜索法(4SS)、新三步搜索法(N3SS)。由于這些算法充分考慮了運動矢量概率(MVP)分布，因此在保持與相當的圖像質量的同時，提高了搜索速度。在此基礎上，出現了大量的非矩形搜索模型的算法，如菱形搜索算法(DS)和六邊形搜索算法(HEXBS)等，其中 DS 算法被 MPEG2/4 標準所采用。除了搜索模型的形狀對搜索的影響之外，搜索模型的大小以及搜索策略對搜索速度和圖像質量同樣有影響。為此，近來出現了十字菱形搜索(CDS)算法、十字菱形六邊形搜索(CDHS)算法等。但這些算法沒有充分考慮運動矢量概率分布的方

53、向性，因此，在搜索過程中還需要比較多的搜索點數17。2.4 各模塊擬采用的算法各模塊擬采用的算法對于初始搜索點的選擇上，先選擇預測的起始點，但起過實驗，發現其一，計算量大，其二，系統復雜性高，其三，結果與直接選擇選擇參考幀對應塊的中心位置相差并不大，所以本文直接選擇參考幀對應塊的中心位置；在視頻壓縮中為了能夠提高壓縮速度，往往使用快速搜索算法進行塊匹配，雖然得到的匹配塊不一定是最優解18。不過由于算法搜索的是匹配塊，匹配并不與實際的運動有好的相關性，在忽略遮擋的前提下，采用過于快速的搜索算法可能會產生較大的誤差，而隨著科技日新月異，算法執行的時間也在大大縮短，在精度的方面考慮的更多，本文采用的

54、塊匹配算法為全搜索法。塊匹配準則為最小絕對值差的和在尺寸和步長的選擇上，應和實際應用場景及目的有關，總體上應當保證每一個子塊都只具有單一運動或者沒有運動，并且子塊尺寸不能過小，步長不宜過長。經過多次實驗，得到最佳數值（見后） 。3人群運動估計的塊匹配算法實現人群運動估計的塊匹配算法實現表 3-1 軟件開發環境表設備設備/軟件名稱軟件名稱規格規格體系結構視頻處理器開發平臺Microsoft Visual Studio C+ 6.0開發工具OpenCV,C/C+函數庫開發語言C/C+Server 運行環境CPU 0.5 GHz 以上、內存 128M、硬盤 100M3.1 實現工具實現工具 Open

55、CVOpenCV 使用 c/c+編寫，擁有包括 300 多個 C 函數的跨平臺的中、高層 API，它不依賴于其它的外部庫盡管也可以使用某些外部庫19。OpenCV 由以下幾個對立的子庫組成：1) CXCORE：包含數據結構，矩陣運算，數據變換，對象持久，內存管理，錯誤處理，動態裝載，文本和基本的數學功能等；2) CV：圖像處理和計算機視覺算法（圖像結構分析，運動描述，跟蹤，模式識別和攝像機標定） ，只存在于 OpenCV1.0 中，今后的版本把 CV 中的功能分散到了其他子庫中去；3) HIGHGUI：用戶交互部分(圖形界面，圖像視頻讀寫，系統調用函數)；4) CVAUX：一些實驗性的函數(三

56、維跟蹤等)；5) Machine Learning (ML)：包含許多聚類，分類和數據分析函數；6) CVCAM：攝像機借口，在 OpenCV1.0 以后的版本中被移除；7) Haaartreining：如何訓練 boosted 級聯物體分類器。在這些庫函數的支持下，用戶可以直接調用濾波函數，形態學處理，圖像特征提取，輪廓提取算法和跟蹤算法，也可以添加自己編寫的子函數，不但能完成復雜的開發任務，還可以提高效率，達到事半功倍的效果。OpenCV 目錄下還有一個 IPLMAN 的 PDF 文件，它是 OpenCV 的早期文檔。這個文檔已經過時，但是之中詳細描述了一些算法以及某些算法中應該使用何種類

57、型的圖像。本程序使用 OpenCV 在實現中用到的各種數據結構與函數如下：(1)cxcore：CvMat，cvCreateMat，cvReleaseMat，IplImage，cvCreateImage，cvReleaseImage，cvSetZero，ConvertScale，cvCmpS，cvCopy，GetReal*D，cvLine，cvPoint；(2)highgui：CvCapture，cvCreateFileCapture，cvReleaseCapture，cvQueryFrame，cvSetCaptureProperty，cvGetCaptureProperty，cvCreateT

58、rackbar，cvNamedWindow，cvMoveWindow，cvDestroyWindow，cvShowImage，cvWaitKey；(3)cv：cvCvtColor，cvSmooth，cvCalcOpticalFlowBM；(4)c 語言中數學庫里的函數語言中數學庫里的函數：ceil；(5)其他函數其他函數：cvsize,cvpoint。下面介紹程序中用到的各種重要函數與數據結構。3.2 cxcore.h該文件中都是圖像處理的函數與數據結構。3.2.1 CvPoint,CvSizeOpenCV 提供了多種基本數據類型，雖然這些數據類型在 C 語言中不是基本類型，但結構都很簡單，可

59、將它們作為原子類型，定義在“/OpenCV/cxcore/include” 的cxtypes.h 中。1. 在這些數據類型中最簡單的就是 CvPoint。CvPoint 是一個簡單的機構體，定義如下：CvPoint 二維坐標系下的點，類型為整型 typedef struct CvPointint x; /* X 坐標, 通常以 0 為基點 */int y; /* y 坐標, 通常以 0 為基點 */CvPoint;CvPoint 有兩個變體類型；CvPoint2D32f 和 CvPoint3D32f。前者同樣有兩個成員x,y，但他們是浮點類型；后者多一個浮點類型的成員 z。2. CvSize

60、類型與 cvPoint 非常相似，但它的數據成員是 integer 類型的 width 和height。如果希望使用浮點類型，則選用 CvSize 的變體類型 CvSize2D32f。3.2.2 CvMatOpenCV 里有三大數據結構：CvArr、CvMat、IplImage，它們遵循面向對象的思想。實際上，IplImage 是 CvMat 的派生，而 CvMat 由 CvArr 派生： 圖 3-1 CvArr，CvMat，IplImage 的關系圖在 OpenCV 中沒有向量結構。任何時候需要向量，都只需要一個列矩陣。OpenCV 矩陣的概念與線性代數課里的概念相比，更抽象，尤其是矩陣的元素，并非只能取