碩士學位論文h運動估計算法的研究與FPGA驗證

1、H.264運動估計算法的研究與FPGA驗證 分類號UDC密 級學 號碩士學位論文 H.264運動估計算法的研究與FPGA驗證學 科 名 稱： 電路與系統(tǒng) 學 科 門 類： 工 學 指 導 教 師： 申 請 日 期： 論文題目：H.264運動估計算法的研究與FPGA驗證學科專業(yè)：電路與系統(tǒng)研 究 生：摘 要隨著互聯(lián)網(wǎng)的飛速發(fā)展，人們的生活中充滿了各種多媒體技術。2003年3月份，ITU-T（國際電信聯(lián)盟）頒布了H.264視頻編碼標準。H.264是一個新的數(shù)字視頻編碼標準，這個標準下，可獲得比以往標準都高的編碼效率，滿足低帶寬、高質(zhì)量網(wǎng)絡視頻應用的需要。為了達到實時性，對視頻編碼技術提出了更高的挑

2、戰(zhàn)。作為視頻壓縮編碼中運算量最大也最重要的一部分運動估計，它能有效去除視頻信號中存在的大量的時間冗余和空間冗余，使視頻數(shù)據(jù)得到高效壓縮，這是能夠解決實時性的關鍵，也是視頻壓縮編碼標準中的一個重要研究方向。在分析了運動估計幾種典型的算法，結(jié)合前人已有的硬件結(jié)構(gòu)的基礎上，結(jié)合高性能 VLSI 設計實現(xiàn)的特點，提出了一種改進的脈動陣列及流水線相結(jié)合的全搜索塊匹配的整像素運動估計結(jié)構(gòu)，并完成了其 VLSI 設計。先簡要描述了H.264標準及其性能，對塊匹配運動估計原理和相關參數(shù)對運動估計效果的影響進行了詳細的介紹。接下來對全搜索算法和幾種快速搜索算法作了一一介紹。然后重點介紹了兩種脈動結(jié)構(gòu) ：1-D

3、和2-D ，闡述了各自的優(yōu)點和不足。由于搜索區(qū)域中的相鄰參考塊之間有一定的數(shù)據(jù)重疊，為了重用這些重疊數(shù)據(jù)，提出了本文的數(shù)據(jù)流，根據(jù)數(shù)據(jù)流的特點給出了相應的硬件結(jié)構(gòu)，采用串入并出的流水線，提高了計算速度的同時也大大減小了 I/O 帶寬。最后利用FPGA 的分塊設計思想，先詳細的劃分了全搜索運動估計算法的各個功能子模塊，編寫了各個子模塊的 Verilog 代碼，并分塊進行了功能仿真，子模塊仿真通過后，把所有模塊綜合起來，進行了仿真。通過分析仿真數(shù)據(jù)，證明了本文設計的全搜索運動估計模塊能夠正常工作，并且能夠?qū)崿F(xiàn)全搜索算法的功能，輸出正確的運動矢量。關鍵詞：H.264；視頻編碼；運動估計；VLSI；脈

4、動結(jié)構(gòu)Title: THE RESEARCH OF H.264 MOTION ESTIMATION ALGORITHMAND FPGA VERIFICATIONMajor: Circuits and SystemsName: Yang LiuSignature: Supervisor: Associate Prof. Shijie QiaoSignature: AbstractWith the rapid development of the internet, multimedia technology in people's daily lives has been more wi

5、dely used, multimedia communications is one indispensable part of daily life. In March of 2003, ITU-T ( International Telecommunication Union ) issued H.264 video coding standard. H.264 is a new digital video coding standard, this standard has a high coding efficiency, it is suitable for high qualit

6、y network video and low-bandwidth applications. In order to achieve real-time，video coding technology faced a higher challenge. As video compression coding in computing the largest and most important part - motion estimation, it can effectively remove the use of the video signal in the presence of a

7、 large number of temporal redundancy and spatial redundancy and compressed video data efficiently, real-time requirements is a solution bottlenecks, which is an important research direction of the video compression.Based on the analysis of integer motion estimation algorithm and architecture, combin

8、ed characteristics of high-performance VLSI design and implementation, suggested an improved pipelined systolic array and a combination of full-search block-matching motion estimation structure of integers, and completed its VLSI design. Firstly，described the H.264 standard and its performance brief

9、ly. Detailedly introduced the block-matching motion estimation principle and some relevant parameterss effect on the result of motion estimation. Secondly, introduced the full search algorithm and several fast search algorithms.Thirdly, presented two kinds of pulse structure :1-D and 2-D and their r

10、espective advantages and weaknesses . In order to reuse the overlapping data among the adjacent reference block data in search area, put forward the data stream，gave the structure according to the characteristics of the data stream, used the pipeline operation to improve the computing speed and redu

11、ce the I/O bandwidth greatly.Finally, through the FPGA block design thinking, devided the full search motion estimation algorithm into many functional sub-modules，Write the Verilog code for each sub-module, after function simulation of sub-modules，synthesized all the sub-modules and simulated.Analys

12、ysed the simulation data and proved the design of full search motion estimation module can work properly, be able to realize the full search function and output correct motion vectors.Key words：H.264; Video Coding; Motion Estimation; VLSI; Pulsating Structure目 錄1 前言11.1 研究背景與意義11.2 國內(nèi)外研究現(xiàn)狀21.3 論文的主要

13、研究內(nèi)容和章節(jié)安排31.3.1 主要研究內(nèi)容31.3.2 論文的章節(jié)安排32 運動估計算法的介紹52.1 H.264標準概述52.2 運功估計技術的概述62.2.1 運動估計的基本概念6運動估計的基本過程62.3 塊匹配技術概述62.4 塊匹配運動估計的參數(shù)和準則72.4.1 分塊大小72.4.2 匹配準則82.4.3 搜索策略92.4.4 搜索范圍的確定92.4.5 算法評定指標92.4.6 估計精度102.5經(jīng)典塊匹配運動估計算法介紹和性能分析112.5.1 全搜索算法（FS）112.5.2 三步搜索法 （TSS）12新三步搜索法 (New Three Step Search)13菱形搜索

14、法 (Diamond Search)142.5.5 四步搜索法(Four Step Search)152.5.6 混合非對稱十字多六邊形格點搜索（UMHexagonS）162.6 本章小結(jié)173 運動估計的經(jīng)典硬件結(jié)構(gòu)193.1 流水線技術概述193.2 脈動陣列概述203.3 全搜索運動估計算法的硬件結(jié)構(gòu)203.3.1 經(jīng)典的 1-D 脈動結(jié)構(gòu)213.3.2 AB1 類型的 1-D 脈動結(jié)構(gòu)233.3.3 AS2 類型的 2-D 脈動結(jié)構(gòu)243.3.4 AB2 類型的 2-D 脈動結(jié)構(gòu)25樹形結(jié)構(gòu)263.4 本章小結(jié)274運動估計硬件結(jié)構(gòu)的設計284.1設計流程284.2設計方法294.3

15、運動估計算法和相關參數(shù)的確定294.3.1 運動估計算法的選擇29相關參數(shù)的確定304.4 數(shù)據(jù)復用304.5 脈動陣列結(jié)構(gòu)的設計和實現(xiàn)流程304.6本章小節(jié)335運動估計模塊的設計和仿真355.1運動估計模塊的總體結(jié)構(gòu)355.2 存儲單元功能模塊365.3 數(shù)據(jù)選擇功能模塊375.4 PE 運算模塊395.5 比較運算模塊415.6 整體控制模塊435.7整體結(jié)構(gòu)功能測試和分析435.8 FPGA驗證435.9 本章小結(jié)456 總結(jié)和展望47致謝49參考文獻511 前言1.1 研究背景與意義在當今這個信息化的社會，信息技術影響著我們?nèi)粘Ｉ畹姆椒矫婷?。在我們的生活中有?0%的信息，通過我們

16、的視覺系統(tǒng)獲得，即圖像，而視頻是由運動的圖像構(gòu)成的，這里面就包含了更為豐富的信息。從普通電話到可視電話，普通手機到智能手機，有線電視到數(shù)字電視的飛速發(fā)展。人們更希望無論何時，無論何地，都能實時、方便的通過圖像和視頻等方式進行通信，但受到客觀條件的的限制，比如處理器的處理能力，要想達到實時性，就需要有視頻壓縮編碼方面高性能的處理器，同時也可以提出更好的視頻壓縮編碼方法。人們的生活因為視覺而豐富多彩。為了更好的生活和娛樂，數(shù)字視頻的質(zhì)量需要不斷的提高，因此加大了對數(shù)字視頻編碼技術的研究。2003年3月，H.264標準經(jīng)過多次修改后，最終確定。H.264較以往標準，同等質(zhì)量下，壓縮比方面有了明顯的提

17、高，明顯增進了網(wǎng)絡的可靠性和視頻傳輸安全，大大改善了網(wǎng)絡傳輸時易阻塞、易誤碼、QoS沒有保證的情況【1】。H.264標準中，為了提高其性能和編碼效率，增加了很多相當復雜的算法，提高了編碼效率的同時使得編解碼更難。H.264/AVC標準仍然是基于塊的混合編碼，但采用了大量以往標準中沒有的技術，大大提高了編碼性能。視頻編碼層VCL和網(wǎng)絡提取層NAL構(gòu)成了H.264/AVC視頻編碼標準。H.264/AVC標準顯著提高了壓縮比，同等圖像質(zhì)量下，H.264/AVC要比H.263和MPEG-4節(jié)省大約50%的碼率【2】，因此也被廣泛的應用，像可視電話、實況轉(zhuǎn)播、視頻會議和監(jiān)控等。實時視頻效果的好壞不僅與網(wǎng)

18、絡性能有關，而且還與所采用的視頻壓縮標準以及所利用的實現(xiàn)平臺有關。H.264視頻編碼標準計算雜度高，運算量也龐大，要想在實時方面得到很好的應用，就必須要考慮用硬件來實現(xiàn)。 運動估計，一種幀間編碼方法。由于兩幀圖像間相隔的時間很短，因此存在很大的相似性，運動估計就是利用了這個相似性，減少時間的冗余度，這個時間的多少取決于運動估計算法的好壞，所以它是視頻編碼中的一個關鍵技術，視頻的壓縮比完全體現(xiàn)在這里。FPGA，一種大規(guī)模的可編程器件【8】，有著邏輯單元靈活、集成度高，開發(fā)周期短、開發(fā)工具先進、制造成本低等特點，因此被廣泛的應用于各種設計之中。它對執(zhí)行運算量龐大，但原理簡單，運算工整的算法，有著自

19、己獨特的優(yōu)勢，因為它的內(nèi)部有大量的觸發(fā)器和I/O引腳，擁有強大的并行計算能力。H.264中的加法和位移，原理簡單，運算工整，使得它能在FPGA中能夠高效并行進行，大大縮短了處理時間，提高了系統(tǒng)的實時性。因此，深入研究H.264視頻編碼核心算法中的運動估計硬件實現(xiàn)結(jié)構(gòu)是一件值得做的工作。1.2 國內(nèi)外研究現(xiàn)狀隨著各種視頻編碼技術的快速發(fā)展，與之相對應的硬件視頻編碼器也陸續(xù)出現(xiàn)，各自有一定的優(yōu)缺點。為了促進H.264/AVC在硬件方面的發(fā)展，國內(nèi)外在優(yōu)化H.264/AVC編碼算法各個模塊的同時，提出了很多像三步搜索法、鉆石搜索法、混合非對稱十字多六邊形格點搜索等算法，這些算法降低了計算復雜度，減小

20、了運算量，效果也不錯，也提出了現(xiàn)在最常用的匹配準則：SAD準則，大大降低了計算復雜度。ASIC是早期視頻編碼方案采取的主要芯片，眾所周知，ASIC是固化了特定功能的芯片，不可編程，從設計到使用需要很長時間，產(chǎn)品一旦做出來就不允許再更改，導致它跟不上視頻編碼技術的發(fā)展，因此出現(xiàn)了其他方案，并替代了該方案。大多數(shù)的視視頻編碼設計方案，伴隨著DSP技術的飛速發(fā)展，都相繼轉(zhuǎn)向了DSP平臺。新一代高性能DSP芯片的陸續(xù)推出，并成為了現(xiàn)今視頻編碼設計方案的主流。主要有EQUATOR的BSP16、 Sigma Design公司的EM86XX【9】和Davinci平臺、ADI Blackfin【10】處理器和

21、Philip公司的TriMedia系列及新品PNX1500 【11】以及 TI的 DM642 DSP 等。這些產(chǎn)品的設計都利用了DSP高性能的數(shù)字信號處理能力，同時DSP成本低，功耗也低，因此廣受歡迎。加拿大UB Video公司制作的一套基于TMS320C64x系列DSP芯片的H.26L實時視頻通信系統(tǒng)，可以在H.263+的1/20倍的碼率情況下，獲得相同的圖像質(zhì)量【12】。隨著人們需求的提高，編碼技術在飛速的發(fā)展，視頻編碼的算法越來越復雜，控制也越來越難，需要更高性能的硬件結(jié)構(gòu)。僅僅靠DSP芯片來完成運算量龐大的H.264視頻編碼算法已沒有一點優(yōu)勢可言，雖然DSP芯片擁有強大的數(shù)字信號處理能

22、力，但無法完成復雜的控制操作。在市場的壓力下，大多數(shù)視頻編碼公司逐步轉(zhuǎn)向DSP+FPGA或者DSP+ARM【13】的設計方案。在DSP+ARM的方案中，控制部分由ARM完成，DSP處理算法，軟硬協(xié)同處理。在DSP+FPGA的方案中，控制部分交給FPGA完成，也是由DSP來完成算法的處理。Nios II軟核技術【14】的發(fā)展使得SOPC的應用逐漸成熟，用FPGA來實現(xiàn)軟硬協(xié)同工作也不再是難事。上述的兩種方案有一個共同點，就是算法部分都由DSP芯片來完成，不同的是一個控制部分由ARM完成，一個控制部分由FPGA來完成。隨著流水線技術在DSP芯片中的應用，使得其性能有了進一步的提升，但對實時性要求很

23、高的應用，計算速度有限的中低端DSP芯片已無用武之地。高端的DSP，雖然能夠滿足要求很高的實時應用的需求，但這樣做又顯得成本太高，使得整個設計投入過大，投入市場收益甚微。FPGA作為一種新型的邏輯器件，擁有強大的并行運行能力和很高的計算速度。H.264視頻編碼的算法簡單，運算工整，很適合利用FPGA來完成它的設計。大規(guī)模FPGA的出現(xiàn)，使得在FPGA上實現(xiàn)H.264視頻編碼的全部算法和控制成為了可能。已經(jīng)有很多公司和研究所在從事基于PFGA的H.264視頻編碼器的設計。由Altera和 Xilinx Altera公司開發(fā)的基于大規(guī)模FPGA的視頻處理套件很早就已經(jīng)在市場上出售。經(jīng)過近3年的努力

24、，JointWave公司在2007年3月完成了H.264 Main Profile Encoder的純verilog語言的設計，并且FPGA驗證順利通過，通過封裝和處理已在全球發(fā)行。它是第一款，也是現(xiàn)在業(yè)內(nèi)水平遙遙領先的H.264 Main Profile Level 3.0級別的純硬件編碼器。H.264視頻編碼技術雖然在迅速發(fā)展，但是采用FPGA設計的編碼器卻發(fā)展緩慢，我國還處在起步階段。為了滿足人們在日常生活和工作中對實時通信和娛樂的需求，大力發(fā)展H.264基于FPGA的視頻編碼器的設計與實現(xiàn)，將會贏得很大的市場。這將極大的改善實時通信，滿足人們的需求。1.3 論文的主要研究內(nèi)容和章節(jié)安排

25、1.3.1 主要研究內(nèi)容運動估計是視頻編碼中運算量最大，但同時也是最關鍵的部分，它對視頻壓縮的性能起著決定性的作用。采用FPGA強大的并行能力來完成強大的運算量，改善H.264視頻編碼的實時性，是一個很有意義的設計。本文主要研究了運動估計算法，在已有的運動估計硬件實現(xiàn)的基礎上，通過揚長避短，提出了本文的數(shù)據(jù)流，根據(jù)數(shù)據(jù)流的特點給出了相應的硬件結(jié)構(gòu)，通過數(shù)據(jù)流的串行輸入、最終結(jié)果的并行輸出，大大減小了I/O帶寬，PE的利用率也一直保持在100%，充分利用了硬件資源。最后利用FPGA 的分塊設計思想，先詳細的劃分了全搜索運動估計算法的各個功能子模塊，使用硬件描述語言 Verilog HDL完成了各

26、個模塊的代碼編寫并進行了功能仿真，然后把各個模塊綜合在一起進行了功能仿真。最后在Altera公司的FPGA開發(fā)板上進行了驗證。1.3.2 論文的章節(jié)安排全文共六章，各章節(jié)內(nèi)容如下：第一章 首先介紹了研究的目的和意義，國內(nèi)外的研究和發(fā)展現(xiàn)狀，最后介紹了本文的主要研究內(nèi)容及章節(jié)安排。第二章 介紹了運動估計的概念和塊匹配運動估計的原理，詳細介紹了塊匹配運動估計中的幾項重要技術指標以及它們對運動估計效果的影響，對全搜索算法（FS）和幾種常用的效果不錯的快速搜索算法在匹配速度、運算量、匹配效果、硬件實現(xiàn)起來的難易程度等方面進行了對比分析。第三章 對全搜索算法已有的兩種脈動處理結(jié)構(gòu)： 1-D 和 2-D，

27、進行了詳細的分析，通過比較它們各自的優(yōu)點和存在的弊端，取長補短，為后面的設計奠定一定的基礎。最后簡要的介紹了一下樹形結(jié)構(gòu)，分析了它的工作原理，并指出了其存在的嚴重不足。第四章 介紹了VLSI 的設計流程和方法，確定了本文設計中的運動估計算法和參數(shù)指標。通過對前一章兩種脈動結(jié)構(gòu)的揚長補短，同時充分利用參考幀中相鄰當前塊匹配區(qū)域數(shù)據(jù)的交疊，給出了一種本文的數(shù)據(jù)流，根據(jù)數(shù)據(jù)流的特點映射出相應的 2-D 脈動結(jié)構(gòu)，大大減小了 I/O 帶寬。第五章 將整個運動估計模塊劃分為一個個功能子模塊，然后使用硬件描述語言 Verilog HDL完成了各個子模塊的代碼編寫并進行了功能仿真。子模塊仿真通過后，把所有模

28、塊綜合起來，進行了仿真。通過分析仿真數(shù)據(jù)，證明了本文設計的全搜索運動估計模塊能夠正常工作，并且能夠?qū)崿F(xiàn)全搜索算法的功能，輸出正確的運動矢量。第六章 總結(jié)與展望，總結(jié)了本文完成的主要工作，指出了其中存在的不足之處，為以后的研究指明了方向。2 運動估計算法的介紹運動估計是視頻壓縮編碼技術中一個相當重要的組成部分。它能夠降低相鄰幀間存在的大量時間冗余，提高了視頻壓縮比。運動估計的效果好壞決定了視頻編碼器的性能。運動估計占用了整個編碼時間的70%左右，所以運動估計算法的復雜度直接決定了視頻編碼器的性能和效率。H.264中運動估計算法采用塊匹配算法，該算法最簡單，效果也相當不錯，促進了實時實現(xiàn)的可行性，

29、因此它成為目前最常用的方法，國際視頻編碼標準也采用塊匹配算法。2.1 H.264標準概述H.264，一個視頻壓縮編解碼的標準，雖然它的編碼技術簡單，卻達到了增強壓縮性能，提高了網(wǎng)絡傳輸（network-friendly）的能力，以滿足日益增長的“對話型”（視頻電話，會議等）和“非對話型”（視頻存儲、廣播以及流媒體等）視頻應用的需求。H.264是在H.26L基礎上提出來的，保留了MPEG-4等以往標準的優(yōu)點，并沿用了MC-DCT，同時增加了CAVLC等新技術的應用，使得壓縮效率更高，同時也提高了視頻質(zhì)量。其主要優(yōu)點【15】有以下幾點:(l)更高的編碼效率。在大多數(shù)的碼率下，與以前的標準相比，當獲

30、得等同的視頻質(zhì)量時，H.264的碼率只有它們的40%左右；(2)更高的視頻質(zhì)量。在任何碼率下，經(jīng)過H.264處理的視頻，通過解碼后，視頻的質(zhì)量比其它標準偏高；(3)自適應的延時特性。可用于延時小的視頻會議等，也能夠用于無延時的視頻監(jiān)控等；(4)錯誤恢復功能。H.264能夠很好的解決網(wǎng)絡傳輸時丟包的問題，適用于高誤碼率下，無線網(wǎng)絡中的數(shù)據(jù)傳輸；(5)良好的網(wǎng)絡傳輸功能。如圖2-1所示，H.264標準分為兩個層次。視頻編碼層（VCL: Video Coding Layer）負責對視頻的壓縮，網(wǎng)絡適配層（NAL: Network Adaptation Layer）負責對特定網(wǎng)絡信息包的傳輸，因此，H

31、.264能夠優(yōu)先控制信息，更好的完成對網(wǎng)絡數(shù)據(jù)的封裝。圖2-1 H.264標準結(jié)構(gòu)圖Fig. 2-1 H.264 standard structure2.2 運功估計技術的概述2.2.1 運動估計的基本概念在幀間編碼中，相鄰幀間的時間間隔很小，人眼分辨不出來，其中的運動量很小，兩幀的相似度很高，可以將圖像幀分成互不重疊等大小的宏塊，找到每個宏塊在相鄰幀中的最佳相似位置，計算出相對偏移量，這個偏移量就是運動矢量，這個過程就是運動估計。 運動估計能夠大大減小幀間存在的大量時間冗余，增大了視頻壓縮比，也就減少了視頻需要傳輸?shù)谋忍財?shù)，減小了傳輸帶寬，因此它在視頻壓縮處理中起著很大的作用。運動估計的基本

32、過程運動估計分以下幾步完成:第一步，把當前視頻幀分為若干個等大小的互不重疊的宏塊，設法找到當前塊每個宏塊在前一幀給定的搜索區(qū)域中最佳相似位置，計算出運動矢量；第二步，將在搜索區(qū)域中得到的最相似宏塊和當前幀對應宏塊的對應像素作減法，求的絕對值和，也就是殘差塊像素；第三步，把得到的每個當前塊的運動矢量和殘差塊的像素傳遞給下一個模塊，經(jīng)過下一個模塊的處理后進行傳輸。2.3 塊匹配技術概述實際上，兩幀圖像之間的物體運動一般是剛體的平移運動，位移量不大，彼此間存在著很強的相關性。塊匹配法就是將圖像分成若干個子塊，并有以下的假設：（1）當前塊中的所有像素有著相同的運動；（2）運動物體不會隨著時間的變化而改

33、變了像素值。塊匹配算法就是將當前幀圖像分為等大小且互不重疊的宏塊，滿足以上的兩點假設，這時候就可以根據(jù)預定的搜索范圍16，按照匹配準則，在搜索區(qū)域中找到和當前塊最相似的宏塊，計算出兩個塊之間的相對位移量，并記錄，這個便為當前塊相對于前一幀的運動矢量，然后將在搜索區(qū)域中得到的最相似宏塊和當前幀對應宏塊的對應像素作減法，求的絕對值和，也就是殘差塊像素，這樣每個當前塊就可由一個運動矢量和殘差塊像素進行表示。運動估計越準確，得到的匹配塊就越相似，對應的殘差塊像素越小，經(jīng)過處理后變?yōu)楹苄〉谋忍財?shù)，傳輸?shù)倪^程中占用的帶寬將大大減小。運動補償過程：依據(jù)每個當前塊的運動矢量，找到在前一幀的對應的最佳匹配塊，加

34、上殘差塊的像素，便可以得到一個和原當前塊基本一樣的宏塊。運動估計越準確，得到的運動矢量也就越精確。運動補償?shù)男ЧQ于運動矢量的精確程度，運動矢量的精確程度又取決于運動估計的準確度，因此，選擇一個好的運動估計算法很重要。實際上，兩幀之間的物體運動一般是剛體的平移運動，位移量不大，因此往往把一幀圖像分成若干M×N塊，以塊為單位分配運動矢量，大大降低碼率。如圖2-2所示。圖2-2 塊匹配算法Fig2-2 Block matching algorithm設前一幀搜索區(qū)為（M+2Wx, N+2Wy），當前幀塊與前一幀塊的位移為d(i, j)，在搜索區(qū)中，如能找到與當前幀塊匹配的前一幀塊，則該

35、塊運動矢量為(i, j)。2.4 塊匹配運動估計的參數(shù)和準則塊匹配算法中，涉及到分塊大小、搜索范圍、匹配準則等幾個參數(shù)的選取，這些參數(shù)的選取需要綜合考慮，它們的好壞嚴重影響著運動估計的準確度及實現(xiàn)難易程度。2.4.1 分塊大小塊匹配算法的使用是有前提的，這個前提就是假設每個分塊內(nèi)所有點做著位移相同的運動，而且運動過程中，物體各個點的像素不會發(fā)生變化。運動的劇烈程度不同，需要采用的分塊大小最好也不要相同。塊太大時，塊內(nèi)各像素位移相同的假設，與實際情況不相符，會對運動估計的準確度造成很大的影響；分塊太小時，很容易受到噪聲等因素的影響，也使運動估計的準確度不高，同時還會得到大量的運動矢量，大大增加了

36、計算量，降低了編碼效率。因此有必要選擇合適的塊大小，滿足既定的前提。H.26x 和 MPEG一般采用 16×16 宏塊，這種分法已被證明很平衡，為了進一步提高預測的精度，H.263 和 MPEG-4增加了對8×8宏塊的處理，而H.264 將最小宏塊分到了 4×4，更進一步的提高了運動估計的結(jié)果精確度。采用4x4的分塊，雖然在一定程度上能夠提高運動估計的精度，但這樣每一幀圖像就需要更過的運動矢量和殘差塊來表示，編碼效率降低，傳輸時也將占用更多的帶寬。故在選擇分塊大小時要綜合考慮上述因素，提高編碼效率。2.4.2 匹配準則任何事物的執(zhí)行都需要一定的標準。在H.264中

37、，衡量當前塊和匹配塊之間的相似程度的準則是塊匹配準則，同時匹配準則直接決定了運算復雜度和匹配精度，因此匹配準則的選取很重要。常見的匹配準則有：(1)MAD是最小絕對差。公式如下: （2.1）式中(i，j)為位移矢量，和分別為當前塊和參考幀中相對當前塊的位移為（i，j）的亮度像素值，MxN為分塊的大小，經(jīng)過匹配比較，MAD的值最小的點，就是最優(yōu)匹配點。（2）最小均方誤差函數(shù) (MSE)。公式如下： （2.2） MSE 值最小的點即為最優(yōu)匹配點。（3）歸一化互相關函數(shù) (NCCF)。公式如下： （2.3） 結(jié)果最大時即為最優(yōu)的匹配點。（4）絕對差值和（SAD）。公式如下： （2.4）SAD最小是即

38、為最優(yōu)的匹配點。由于 MSE 準則和 NCCF 準則中有乘方運算，實現(xiàn)時相比之下就要占用更多的資源，計算復雜度也較其它的高。而 MAD 準則相比之下就有一定的優(yōu)勢。確定了需要采用的運動估計算法和搜索范圍的大小，匹配準則對運動估計精度的影響可以忽略不計，但采用SAD能夠明顯的降低計算復雜度，它和MAD相比只是少了一個除法因子，其它一樣，雖然如此，但它卻和MAD準則有著相同的匹配效果。因為分塊大小一旦確定，MxN的大小也就固定，在進行除法操作顯得有點多余，所以MAD準則逐漸被SAD準則取代。 2.4.3 搜索策略搜索策略選擇恰當與否，嚴重影響著運動估計的準確性和速度。搜索策略體現(xiàn)在搜索方向和搜索路

39、線兩個方面，二者結(jié)合不同的搜索步長就能成為不同的搜索模式。但不能讓搜索過程無限制的進行下去，有時候沒有必要，比方對靜止的圖像，那么多搜索步驟都是在做無用功，因此需要一個提前終止準則，保證搜索過程能夠及時終止，減少時間的浪費。搜索算法的效率取決于搜索模式，提前終止準則也可以在一定程度上提高搜索算法的效率。2.4.4 搜索范圍的確定搜索范圍的大小嚴重影響著運動估計的精度，它的確定需要綜合、慎重的考慮。搜索范圍的確定需要注意以下兩點：1 要根據(jù)視頻的清晰度來確定搜索范圍的大小，清晰度越高，相對搜索范圍就越大；清晰度較低，就可以選取較小的搜索范圍；2 要根據(jù)視頻圖像運動的劇烈程度來確定搜索范圍的大小，

40、運動相對劇烈，需要的搜索范圍就相對較大；運動相對平緩，只需要一個較小的搜索范圍就能達到預期目的；以上兩點是確定搜索范圍時需要考慮的重要因素，可見，搜索區(qū)域的大小的確定需要從實際情況出發(fā)，不能采用一個相同的標準。當搜索區(qū)域增大時，雖然能在一定程度上提高運動估計的準確度，但是增大了計算量，這就意味著將要占用更多的硬件資源。因此搜索區(qū)域的大小的選擇就要視具體情況而定，具體情況具體分析。2.4.5 算法評定指標 運動估計就是為了在前一幀搜索區(qū)域中找到與當前塊最為相似的塊，運動估計越準確，得到的相似塊的相似度就越高，壓縮性能就越好，需要傳輸?shù)臍埐顗K像素就越少。如何判斷一個算法的好壞，就要通過觀察匹配的效

41、果和花費搜索時間的多少，時間多少可以用客觀條件衡量，匹配效果的好差最直接的辦法就是人眼觀察。但人眼看到的圖像是諸多因素相互作用的過程。這些因素具有不確定性，其中都加入了人的主觀意識，用人眼的觀察來衡量匹配效果的好差顯得不科學?？陀^的標準不受任何因素的影響，因此采取客觀的標準來衡量匹配效果的好差，其中最常用的是峰值信噪比 PSNR(Peak Signal to Noise Ratio)： (2.5)PSNR 值越大，圖像的質(zhì)量就越高，PSNR 值越小，圖像的質(zhì)量相對較低。PSNR的計算簡單，也能夠很好的反映圖像的質(zhì)量，不受主觀因素的影響，因此被廣泛的使用2.4.6 估計精度實際中的物體并不是都在

42、做著整像素的位移，所以整像素運動估計的精度在這個時候就不能真實反映物體的位移。物體運動具有連續(xù)性，相鄰兩幀之間不可能都是是以整像素為基本單位的運動的，可能是以1/2像素或者1/4像素等亞像素作為運動單位的。圖2-3給出了一個視頻序列分別用1/2像素、1/4像素和1/8像素精度時編碼的效率，從圖中可看到采用1/4像素精度時的編碼效率相對于1/2像素精度有了顯著的提高，但1/8像素精度和1/4像素精度的編碼效率相比并沒有明顯的提高，1/8像素的內(nèi)插公式也更為復雜，所以1/8像素精度的運動矢量模型漸漸被1/4像素精度的運動矢量模型所取代。圖2-3 不同亞像素的編碼效率Fig2-4 Coding ef

43、ficiency of the different sub-pixel為了進一步提高運動估計的準確度，后來的標準采用了亞像素的運動估計，雖然在一定程度上提升了性能，但卻大大增加了運算量。亞像素并不存在于參考圖像中，它的像素值需要通過鄰近已編碼點的像素按一定的準則內(nèi)插而得到。亞像素運動估計通常在整像素搜索得到的最佳匹配點的附近插值形成一個虛擬的亞像素塊，將步長變?yōu)榉謹?shù)進行下一步的搜索。亞像素運動估計的實現(xiàn)很復雜，考慮到本人的能力和時間問題，只研究了整像素運動估計。2.5經(jīng)典塊匹配運動估計算法介紹和性能分析運動估計的算法決定了視頻壓縮的性能和速度，是視頻壓縮編碼系統(tǒng)中至關重要的一環(huán)。運動估計的準確

44、度和匹配的速度反映了一個算法的優(yōu)劣。準確度越高，殘差值越小，編碼后需要傳輸?shù)谋忍財?shù)就越少，降低了傳輸帶寬。匹配速度客觀的表現(xiàn)在得到一個運動矢量所搜索的點數(shù)。下面介紹幾種常用的運動估計算法。2.5.1 全搜索算法（FS）全搜索算法是一種窮盡的搜索算法，將當前塊和參考幀搜索區(qū)域中的每一個可能的塊都進行一次匹配比較，按照匹配準則找到最佳匹配塊。全搜索法有光柵式和螺旋式兩種搜索方式，如圖 2-4 所示。光柵式搜索如圖(a)，從左上角的開始，按行搜索，直到將整個搜索范圍內(nèi)的可能塊匹配完畢；螺旋式搜索如圖(b)，從中心開始，螺旋搜索到最后一個邊緣塊，各個塊的運動矢量規(guī)律性比較差，實現(xiàn)起來困難，相對于光柵式

45、搜索略顯復雜。（a）光柵式搜索（b）螺旋式搜索圖2-4 全搜索的兩種搜索方式Fig2-4 Two search methods of full search全搜索法（FS）擁有最高的運動估計準確度，也不容易陷入局部最優(yōu)，也是其它快速搜索算法的判斷準則，將匹配結(jié)果和全搜索法進行對比，來評判該算法的好壞。全搜索法高的準確度是建立在龐大的運算量之上的。全搜索算法(FS)的規(guī)則最簡單的，但運算量卻占到了視頻壓縮編碼過程的 70%左右，當搜索范圍為(-f,+f)時，需要進行(2f+1)2次的運算，因此加大了實時性實現(xiàn)的難度，要想實時實現(xiàn)，就需要很高的硬件水平。后來，為了減小全搜索算法龐大的運算量，出現(xiàn)了

46、很多快速運動估計算法，運動估計的準確度也挺高，運算量卻大大減小。全搜索法的算法簡單，性能也最好，易于VLSI實現(xiàn)，考慮到現(xiàn)有的硬件條件，要實現(xiàn)它已成為一種可能，某些要求高的應用場合非的采用全搜索算法不可，因此對它的研究還是很有意義的。2.5.2 三步搜索法 （TSS）目前，在全搜索算法的基礎上，已發(fā)展出了一些快速搜索算法?？焖偎阉鞣ㄖ皇菍斍皦K與對應搜索區(qū)域中的部分宏塊進行匹配計算，從這幾個宏塊中找到最佳的匹配塊，這樣做就減小了全搜索算法需要的匹配次數(shù)。在減小了匹配次數(shù)的同時，另一個問題也相繼而生，就是快速搜索算法所找到的最優(yōu)匹配塊，到底是真正的最優(yōu)，還是局部的最優(yōu)。為了保證速度，快速搜索算法

47、并沒有像全搜索算法那樣進行窮盡的搜索，只搜索了特定的宏塊，雖然保證了速度，卻容易陷入局部最優(yōu)，而全搜索算法能夠保證找到全局最優(yōu)的匹配塊，保證最匹配的宏塊運動矢量信息。由于快速搜索算法得到的不是最優(yōu)匹配塊，因此得到的殘差塊像素也就越大，傳輸?shù)臅r候就要占用更多的帶寬。三步搜索法（TSS），顧名思義，得到最終的運動矢量需要三個步驟。它從搜索區(qū)域的中心開始，搜索周圍的8個點，該步得到的最小SAD值點，作為下一步搜索的中心，步長減半，搜索周圍的8個點，第三步也是如此，最終找到的SAD值最小點就是最優(yōu)點，該點相對原點的位移就是運動矢量。三步法思想簡單，性能良好，被許多軟件采用。如果選定搜索范圍為（-7，+

48、7），三步搜索過程如圖2-5所示：第一步，從搜索區(qū)域的中心開始，步長為 4，匹配運算周圍8個帶1的圓圈點；第二步，以第一步中SAD值最小的點為新的中心，步長為2，匹配運算周圍8個帶2的圓圈點；第三步，以第二步中SAD值最小的點為新的中心，步長為1，匹配運算周圍 8 個帶3的圓圈點，這時候得到的便是最佳匹配塊，計算出該塊相對搜索中心的位移，就是當前塊的運動矢量。圖2-5 三步搜索法Fig2-5 Three-step search method圖 2-5 示意了最大搜索距離為 7 時的搜索過程。各步操作如圓圈中的數(shù)字和對應位置所示。三步搜索法，最多需要計算 25 個點的SAD值，而全搜索算法采用相

49、同的搜索范圍，卻需要計算225個點的SAD值，相比可見，三步法大大降低了運算量。但是，雖然三步搜索法大大降低了運算量，但第一步過于簡單，在搜索范圍較大時，第一步就有很大的可能偏離了最佳的搜索區(qū)域，像那種靜止的運動，運動估計得到的就不是真正的最佳匹配點，只是局部最優(yōu)，最終影響壓縮編碼的性能，導致圖像失真。新三步搜索法 (New Three Step Search)NTSS算法16彌補了TSS算法在估計運動不劇烈的的運動上的不足。新三步法在三步法第一步搜索的基礎上增加了對中心點的8個鄰域的測試，并采用了提前終止的策略，倘若最小的BDM (Block Distortion Measure)出現(xiàn)在8鄰

50、域的中心就停止搜索，這樣對于估計靜止塊是非常有效的。具體步驟如下:(l)在三步法的第一步的基礎上，增加對中心點的8個鄰域的測試。(2)提前終止策略對估估計靜止塊和亞靜止塊(運動范圍在2個像素內(nèi))的運動矢量有很大的優(yōu)勢。如果第一步最小的BDM在搜索窗口的中心，就停止搜索;如果出現(xiàn)在中心點的8鄰域中，則以最小BDM為中心計算其8個鄰域，重復該步驟，直至最小BDM出現(xiàn)在中心。如果最小的BDM出現(xiàn)在w/2上，接下來就按三步搜索法的第二步和第三步執(zhí)行，找到最佳的運動矢量。NTSS算法執(zhí)行完所有的步驟需要測試33個點，但NTSS算法有時會在第一步或第二步的時候就提前終止，對于靜止的塊只需測試17個點，對于

51、亞靜止的塊需要測試20或者22個點，所以NTSS相對于TSS有了一定的改善，加速了約18%。圖2-6 新三步搜索法Fig2-6 New three step search菱形搜索法 (Diamond Search)菱形搜索法因其搜索模板像鉆石又被稱為 “鉆石”搜索算法17，它采用LDSP（Large Diamond Search Pattern，大鉆石搜索模板）和SDSP（Small Diamond Search Pattern，小鉆石搜索模板）兩種搜索模板，如圖2-7所示?！般@石”搜索算法，先采用步長大、范圍廣LDSP模板搜索，進行一個粗略的定位，這也符合視頻圖像運動的基本規(guī)律，陷于局部最優(yōu)

52、的可能性降低；當完成了粗略定位后，再采用SDSP模板搜索LDSP中得到的最小SAD值點的周圍4個點，這時得到的SAD值最小點便是最優(yōu)匹配點，這樣做避免了陷入局部最優(yōu)，提升了運動估計的準確度。 （a）大菱形 （b）小菱形圖2-7 “鉆石”搜索模板Fig2-7 "Diamond" search templateDS算法流程如下:第一步:以搜索窗口的原點(O，0)為中心，采用LDSP模板，檢測這九個點。如果MBD(Minimum Block Distortion)點位于中心，就轉(zhuǎn)至第三步;否則，轉(zhuǎn)至第二步繼續(xù)搜索。第二步:以第一步搜索得到的MBD點為中心，構(gòu)造另一個LDSP。如果

53、得到的新MBD點位于中心，轉(zhuǎn)至第三步，否則，重復此步操作，直至匹配點到達搜索窗的邊緣，停止搜索。第三步:采用SDSP模板，這一步搜索得到的MBD點便是最優(yōu)匹配點，其相對位移便是運動矢量。2.5.5 四步搜索法(Four Step Search)四步搜索法也利用了運動矢量靠近中心分布的理論，將TSS的9x9搜索窗改為5x5，每一步都以上一步最小的BDM的位置為中心，繼續(xù)下一步的搜索，步長取決于最小BDM的位置。四步搜索法的四步操作如下:(l)在搜索區(qū)域的中心用一個5x5的窗口，如果最小BDM出現(xiàn)在窗口中心，轉(zhuǎn)到第四步，否則繼續(xù);(2)搜索窗口仍用5x5，但搜索模式要依賴上一步最小BDM的位置，若

54、在窗口的四個角，就增加五個測試點，若在窗口四條邊的中心，就增加三個測試點，若出現(xiàn)在窗口的中心，轉(zhuǎn)至第四步繼續(xù)，否則繼續(xù);(3)搜索模式和第二步一樣，但該步下來不管怎樣都轉(zhuǎn)至第四步;(4)搜索窗口換為3x3，這時得到的最小BDM點便是最優(yōu)匹配點，其相對位移便是運動矢量。圖2-8 四步搜索法Fig2-8 Four-step search methodFSS又一次改進了快速搜索算法，搜索速度不一定比TSS快，但是FSS的計算復雜度相比TSS有所降低，而且整個搜索過程比較平緩，減小了出現(xiàn)局部最優(yōu)的可能，并對靜止的塊縮短了搜索時間，所以獲得了較好的搜索效果。2.5.6 混合非對稱十字多六邊形格點搜索（U

55、MHexagonS）混合非對稱十字多六邊形格點搜索算法【18】(UMHexagonS)是已有的快速搜索算法中估計效果最好的，已被 H.264 官方采用。UMHexagonS 算法分四步完成搜索，搜索步驟如下：第一步：進行矢量預測，確定搜索的起始點。第二步：非對稱的十字搜索，在一般的運動中，水平方向的運動幅度大于垂直方向的運動幅度，故可以通過非對稱的十字形搜索先做一個初步的搜索。所謂非對稱十字，如圖 2-9 中 step2 的點所示，水平方向的搜索長度為垂直方向搜索高度的2倍，搜索點間距2個步長。這一步得到最佳匹配點便是下一步搜索的中心。第三步：多層次六邊形搜索，分兩步完成。首先以上一步的最佳匹

56、配點的位置作為搜索中心，做一個5×5 范圍的全搜索，如圖 2-9 中 step3-1 的圓圈所示；第二步進行多層次六邊形搜索，采用了16 點的六邊形，即圖 2-9 中 step3-2 的小方形所示，如圖 2-9 所示，六邊形覆蓋的區(qū)域比較大，而且六邊形左右兩側(cè)的點數(shù)比上下兩側(cè)的搜索點數(shù)多，這也符合運動的規(guī)律。六邊形由里到外層層搜索，等搜索結(jié)束后，比較每層中相對較小的SAD值，其中最小的SAD值所對應的位置便是下一步繼續(xù)搜索位置的中心。第四步：擴展的六邊形搜索，第三步的多層次六邊形搜索可以得到不同精度的運動矢量，當最佳匹配塊在外部六邊形時，得到的運動矢量精度就偏低，故需要進一步細化搜索

57、，通常用六邊形繼續(xù)下一步的搜索，如圖 2-9 Step4 所示。先采用半徑為 2 的六邊形反復搜索，直到最佳點出現(xiàn)在六邊形中心，接下來用半徑為 1 的小菱形繼續(xù)搜索，直至最佳匹配塊位于小菱形的中心。圖2-9 非對稱十字型多層次六邊形格點運動搜索算法Fig2-9 Asymmetric cross-shaped multi-layered hexagonal movement grid search algorithm通過對以上幾種搜索算法的實現(xiàn)過程對比，發(fā)現(xiàn)全搜索算法雖然計算量最龐大，但是匹配效果卻是最好的，而UMHexagonS 算法雖然能達到和全搜索算法差不多的效果，但是搜索模板多樣化，不利與硬件實現(xiàn)，通過權(quán)衡，最終選擇了全搜索法進行研究。2.6 本章小結(jié)本章介紹了運動估計的概念和塊匹配的原理，分析了分塊大小、匹配準則、搜索策略、搜索范圍、估計精度對視頻壓縮編碼性能的影響，以及它們選取和確定中需要注意的問題，介紹了幾種運動