碩士學(xué)位論文h.264運(yùn)動估計算法的研究與FPGA驗(yàn)證

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

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

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

4、脈動結(jié)構(gòu)title: the research of h.264 motion estimation algorithm and fpga verificationmajor: circuits and systemsname: yang liusignature: )supervisor: associate prof. shijie qiao(signature: )abstractwith the rapid development of the internet, multimedia technology in peoples 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 運(yùn)動估計算法的介紹52.1 h.264標(biāo)準(zhǔn)概述52.2 運(yùn)功估計技術(shù)的概述62.2.1 運(yùn)動估計的基本概念62.2.2運(yùn)動估計的基本過程62.3 塊匹配技術(shù)概述62.4 塊匹配運(yùn)動估計的參數(shù)和準(zhǔn)則72.4.1 分塊大小72.4.2 匹配準(zhǔn)則82.4.3 搜索策略92.4.4 搜索范圍的確定92.4.5 算法評定指標(biāo)92.4.6 估計精度102.5經(jīng)典塊匹配運(yùn)動估計算法介紹和性能分析112.5.1 全搜索算法（fs）112.5.2 三步搜索法 （tss）122.5.3新三步搜索法 (new three step sea

14、rch)132.5.4菱形搜索法 (diamond search)142.5.5 四步搜索法(four step search)152.5.6 混合非對稱十字多六邊形格點(diǎn)搜索（umhexagons）162.6 本章小結(jié)173 運(yùn)動估計的經(jīng)典硬件結(jié)構(gòu)193.1 流水線技術(shù)概述193.2 脈動陣列概述203.3 全搜索運(yùn)動估計算法的硬件結(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)253.3.5樹形結(jié)構(gòu)263.4 本章小結(jié)274運(yùn)動估計硬件結(jié)構(gòu)的設(shè)計284.

15、1設(shè)計流程284.2設(shè)計方法294.3 運(yùn)動估計算法和相關(guān)參數(shù)的確定294.3.1 運(yùn)動估計算法的選擇294.3.2相關(guān)參數(shù)的確定304.4 數(shù)據(jù)復(fù)用304.5 脈動陣列結(jié)構(gòu)的設(shè)計和實(shí)現(xiàn)流程304.6本章小節(jié)335運(yùn)動估計模塊的設(shè)計和仿真355.1運(yùn)動估計模塊的總體結(jié)構(gòu)355.2 存儲單元功能模塊365.3 數(shù)據(jù)選擇功能模塊375.4 pe 運(yùn)算模塊395.5 比較運(yùn)算模塊415.6 整體控制模塊435.7整體結(jié)構(gòu)功能測試和分析435.8 fpga驗(yàn)證435.9 本章小結(jié)456 總結(jié)和展望47致謝49參考文獻(xiàn)511 前言1.1 研究背景與意義在當(dāng)今這個信息化的社會，信息技術(shù)影響著我們?nèi)粘Ｉ畹?/p>

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

17、64較以往標(biāo)準(zhǔn)，同等質(zhì)量下，壓縮比方面有了明顯的提高，明顯增進(jìn)了網(wǎng)絡(luò)的可靠性和視頻傳輸安全，大大改善了網(wǎng)絡(luò)傳輸時易阻塞、易誤碼、qos沒有保證的情況【1】。h.264標(biāo)準(zhǔn)中，為了提高其性能和編碼效率，增加了很多相當(dāng)復(fù)雜的算法，提高了編碼效率的同時使得編解碼更難。h.264/avc標(biāo)準(zhǔn)仍然是基于塊的混合編碼，但采用了大量以往標(biāo)準(zhǔn)中沒有的技術(shù)，大大提高了編碼性能。視頻編碼層vcl和網(wǎng)絡(luò)提取層nal構(gòu)成了h.264/avc視頻編碼標(biāo)準(zhǔn)。h.264/avc標(biāo)準(zhǔn)顯著提高了壓縮比，同等圖像質(zhì)量下，h.264/avc要比h.263和mpeg-4節(jié)省大約50%的碼率【2】，因此也被廣泛的應(yīng)用，像可視電話、實(shí)況

18、轉(zhuǎn)播、視頻會議和監(jiān)控等。實(shí)時視頻效果的好壞不僅與網(wǎng)絡(luò)性能有關(guān)，而且還與所采用的視頻壓縮標(biāo)準(zhǔn)以及所利用的實(shí)現(xiàn)平臺有關(guān)。h.264視頻編碼標(biāo)準(zhǔn)計算雜度高，運(yùn)算量也龐大，要想在實(shí)時方面得到很好的應(yīng)用，就必須要考慮用硬件來實(shí)現(xiàn)。 運(yùn)動估計，一種幀間編碼方法。由于兩幀圖像間相隔的時間很短，因此存在很大的相似性，運(yùn)動估計就是利用了這個相似性，減少時間的冗余度，這個時間的多少取決于運(yùn)動估計算法的好壞，所以它是視頻編碼中的一個關(guān)鍵技術(shù)，視頻的壓縮比完全體現(xiàn)在這里。fpga，一種大規(guī)模的可編程器件【8】，有著邏輯單元靈活、集成度高，開發(fā)周期短、開發(fā)工具先進(jìn)、制造成本低等特點(diǎn)，因此被廣泛的應(yīng)用于各種設(shè)計之中。它對

19、執(zhí)行運(yùn)算量龐大，但原理簡單，運(yùn)算工整的算法，有著自己獨(dú)特的優(yōu)勢，因?yàn)樗膬?nèi)部有大量的觸發(fā)器和i/o引腳，擁有強(qiáng)大的并行計算能力。h.264中的加法和位移，原理簡單，運(yùn)算工整，使得它能在fpga中能夠高效并行進(jìn)行，大大縮短了處理時間，提高了系統(tǒng)的實(shí)時性。因此，深入研究h.264視頻編碼核心算法中的運(yùn)動估計硬件實(shí)現(xiàn)結(jié)構(gòu)是一件值得做的工作。1.2 國內(nèi)外研究現(xiàn)狀隨著各種視頻編碼技術(shù)的快速發(fā)展，與之相對應(yīng)的硬件視頻編碼器也陸續(xù)出現(xiàn)，各自有一定的優(yōu)缺點(diǎn)。為了促進(jìn)h.264/avc在硬件方面的發(fā)展，國內(nèi)外在優(yōu)化h.264/avc編碼算法各個模塊的同時，提出了很多像三步搜索法、鉆石搜索法、混合非對稱十字多六

20、邊形格點(diǎn)搜索等算法，這些算法降低了計算復(fù)雜度，減小了運(yùn)算量，效果也不錯，也提出了現(xiàn)在最常用的匹配準(zhǔn)則：sad準(zhǔn)則，大大降低了計算復(fù)雜度。asic是早期視頻編碼方案采取的主要芯片，眾所周知，asic是固化了特定功能的芯片，不可編程，從設(shè)計到使用需要很長時間，產(chǎn)品一旦做出來就不允許再更改，導(dǎo)致它跟不上視頻編碼技術(shù)的發(fā)展，因此出現(xiàn)了其他方案，并替代了該方案。大多數(shù)的視視頻編碼設(shè)計方案，伴隨著dsp技術(shù)的飛速發(fā)展，都相繼轉(zhuǎn)向了dsp平臺。新一代高性能dsp芯片的陸續(xù)推出，并成為了現(xiàn)今視頻編碼設(shè)計方案的主流。主要有equator的bsp16、 sigma design公司的em86xx【9】和davin

21、ci平臺、adi blackfin【10】處理器和philip公司的trimedia系列及新品pnx1500 【11】以及 ti的 dm642 dsp 等。這些產(chǎn)品的設(shè)計都利用了dsp高性能的數(shù)字信號處理能力，同時dsp成本低，功耗也低，因此廣受歡迎。加拿大ub video公司制作的一套基于tms320c64x系列dsp芯片的h.26l實(shí)時視頻通信系統(tǒng)，可以在h.263+的1/20倍的碼率情況下，獲得相同的圖像質(zhì)量【12】。隨著人們需求的提高，編碼技術(shù)在飛速的發(fā)展，視頻編碼的算法越來越復(fù)雜，控制也越來越難，需要更高性能的硬件結(jié)構(gòu)。僅僅靠dsp芯片來完成運(yùn)算量龐大的h.264視頻編碼算法已沒有一

22、點(diǎn)優(yōu)勢可言，雖然dsp芯片擁有強(qiáng)大的數(shù)字信號處理能力，但無法完成復(fù)雜的控制操作。在市場的壓力下，大多數(shù)視頻編碼公司逐步轉(zhuǎn)向dsp+fpga或者dsp+arm【13】的設(shè)計方案。在dsp+arm的方案中，控制部分由arm完成，dsp處理算法，軟硬協(xié)同處理。在dsp+fpga的方案中，控制部分交給fpga完成，也是由dsp來完成算法的處理。nios ii軟核技術(shù)【14】的發(fā)展使得sopc的應(yīng)用逐漸成熟，用fpga來實(shí)現(xiàn)軟硬協(xié)同工作也不再是難事。上述的兩種方案有一個共同點(diǎn)，就是算法部分都由dsp芯片來完成，不同的是一個控制部分由arm完成，一個控制部分由fpga來完成。隨著流水線技術(shù)在dsp芯片中的

23、應(yīng)用，使得其性能有了進(jìn)一步的提升，但對實(shí)時性要求很高的應(yīng)用，計算速度有限的中低端dsp芯片已無用武之地。高端的dsp，雖然能夠滿足要求很高的實(shí)時應(yīng)用的需求，但這樣做又顯得成本太高，使得整個設(shè)計投入過大，投入市場收益甚微。fpga作為一種新型的邏輯器件，擁有強(qiáng)大的并行運(yùn)行能力和很高的計算速度。h.264視頻編碼的算法簡單，運(yùn)算工整，很適合利用fpga來完成它的設(shè)計。大規(guī)模fpga的出現(xiàn)，使得在fpga上實(shí)現(xiàn)h.264視頻編碼的全部算法和控制成為了可能。已經(jīng)有很多公司和研究所在從事基于pfga的h.264視頻編碼器的設(shè)計。由altera和 xilinx altera公司開發(fā)的基于大規(guī)模fpga的視

24、頻處理套件很早就已經(jīng)在市場上出售。經(jīng)過近3年的努力，jointwave公司在2007年3月完成了h.264 main profile encoder的純verilog語言的設(shè)計，并且fpga驗(yàn)證順利通過，通過封裝和處理已在全球發(fā)行。它是第一款，也是現(xiàn)在業(yè)內(nèi)水平遙遙領(lǐng)先的h.264 main profile level 3.0級別的純硬件編碼器。h.264視頻編碼技術(shù)雖然在迅速發(fā)展，但是采用fpga設(shè)計的編碼器卻發(fā)展緩慢，我國還處在起步階段。為了滿足人們在日常生活和工作中對實(shí)時通信和娛樂的需求，大力發(fā)展h.264基于fpga的視頻編碼器的設(shè)計與實(shí)現(xiàn)，將會贏得很大的市場。這將極大的改善實(shí)時通信，滿

25、足人們的需求。1.3 論文的主要研究內(nèi)容和章節(jié)安排1.3.1 主要研究內(nèi)容運(yùn)動估計是視頻編碼中運(yùn)算量最大，但同時也是最關(guān)鍵的部分，它對視頻壓縮的性能起著決定性的作用。采用fpga強(qiáng)大的并行能力來完成強(qiáng)大的運(yùn)算量，改善h.264視頻編碼的實(shí)時性，是一個很有意義的設(shè)計。本文主要研究了運(yùn)動估計算法，在已有的運(yùn)動估計硬件實(shí)現(xiàn)的基礎(chǔ)上，通過揚(yáng)長避短，提出了本文的數(shù)據(jù)流，根據(jù)數(shù)據(jù)流的特點(diǎn)給出了相應(yīng)的硬件結(jié)構(gòu)，通過數(shù)據(jù)流的串行輸入、最終結(jié)果的并行輸出，大大減小了i/o帶寬，pe的利用率也一直保持在100%，充分利用了硬件資源。最后利用fpga 的分塊設(shè)計思想，先詳細(xì)的劃分了全搜索運(yùn)動估計算法的各個功能子模塊

26、，使用硬件描述語言 verilog hdl完成了各個模塊的代碼編寫并進(jìn)行了功能仿真，然后把各個模塊綜合在一起進(jìn)行了功能仿真。最后在altera公司的fpga開發(fā)板上進(jìn)行了驗(yàn)證。1.3.2 論文的章節(jié)安排全文共六章，各章節(jié)內(nèi)容如下：第一章 首先介紹了研究的目的和意義，國內(nèi)外的研究和發(fā)展現(xiàn)狀，最后介紹了本文的主要研究內(nèi)容及章節(jié)安排。第二章 介紹了運(yùn)動估計的概念和塊匹配運(yùn)動估計的原理，詳細(xì)介紹了塊匹配運(yùn)動估計中的幾項(xiàng)重要技術(shù)指標(biāo)以及它們對運(yùn)動估計效果的影響，對全搜索算法（fs）和幾種常用的效果不錯的快速搜索算法在匹配速度、運(yùn)算量、匹配效果、硬件實(shí)現(xiàn)起來的難易程度等方面進(jìn)行了對比分析。第三章 對全搜索

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

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

29、法最簡單，效果也相當(dāng)不錯，促進(jìn)了實(shí)時實(shí)現(xiàn)的可行性，因此它成為目前最常用的方法，國際視頻編碼標(biāo)準(zhǔn)也采用塊匹配算法。2.1 h.264標(biāo)準(zhǔn)概述h.264，一個視頻壓縮編解碼的標(biāo)準(zhǔn)，雖然它的編碼技術(shù)簡單，卻達(dá)到了增強(qiáng)壓縮性能，提高了網(wǎng)絡(luò)傳輸（network-friendly）的能力，以滿足日益增長的“對話型”（視頻電話，會議等）和“非對話型”（視頻存儲、廣播以及流媒體等）視頻應(yīng)用的需求。h.264是在h.26l基礎(chǔ)上提出來的，保留了mpeg-4等以往標(biāo)準(zhǔn)的優(yōu)點(diǎn)，并沿用了mc-dct，同時增加了cavlc等新技術(shù)的應(yīng)用，使得壓縮效率更高，同時也提高了視頻質(zhì)量。其主要優(yōu)點(diǎn)【15】有以下幾點(diǎn):(l)更高的

30、編碼效率。在大多數(shù)的碼率下，與以前的標(biāo)準(zhǔn)相比，當(dāng)獲得等同的視頻質(zhì)量時，h.264的碼率只有它們的40%左右；(2)更高的視頻質(zhì)量。在任何碼率下，經(jīng)過h.264處理的視頻，通過解碼后，視頻的質(zhì)量比其它標(biāo)準(zhǔn)偏高；(3)自適應(yīng)的延時特性?？捎糜谘訒r小的視頻會議等，也能夠用于無延時的視頻監(jiān)控等；(4)錯誤恢復(fù)功能。h.264能夠很好的解決網(wǎng)絡(luò)傳輸時丟包的問題，適用于高誤碼率下，無線網(wǎng)絡(luò)中的數(shù)據(jù)傳輸；(5)良好的網(wǎng)絡(luò)傳輸功能。如圖2-1所示，h.264標(biāo)準(zhǔn)分為兩個層次。視頻編碼層（vcl: video coding layer）負(fù)責(zé)對視頻的壓縮，網(wǎng)絡(luò)適配層（nal: network adaptation

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

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

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

34、：依據(jù)每個當(dāng)前塊的運(yùn)動矢量，找到在前一幀的對應(yīng)的最佳匹配塊，加上殘差塊的像素，便可以得到一個和原當(dāng)前塊基本一樣的宏塊。運(yùn)動估計越準(zhǔn)確，得到的運(yùn)動矢量也就越精確。運(yùn)動補(bǔ)償?shù)男ЧQ于運(yùn)動矢量的精確程度，運(yùn)動矢量的精確程度又取決于運(yùn)動估計的準(zhǔn)確度，因此，選擇一個好的運(yùn)動估計算法很重要。實(shí)際上，兩幀之間的物體運(yùn)動一般是剛體的平移運(yùn)動，位移量不大，因此往往把一幀圖像分成若干mn塊，以塊為單位分配運(yùn)動矢量，大大降低碼率。如圖2-2所示。圖2-2 塊匹配算法fig2-2 block matching algorithm設(shè)前一幀搜索區(qū)為（m+2wx, n+2wy），當(dāng)前幀塊與前一幀塊的位移為d(i, j)，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

49、搜索算法采用相同的搜索范圍，卻需要計算225個點(diǎn)的sad值，相比可見，三步法大大降低了運(yùn)算量。但是，雖然三步搜索法大大降低了運(yùn)算量，但第一步過于簡單，在搜索范圍較大時，第一步就有很大的可能偏離了最佳的搜索區(qū)域，像那種靜止的運(yùn)動，運(yùn)動估計得到的就不是真正的最佳匹配點(diǎn)，只是局部最優(yōu)，最終影響壓縮編碼的性能，導(dǎo)致圖像失真。2.5.3新三步搜索法 (new three step search)ntss算法16彌補(bǔ)了tss算法在估計運(yùn)動不劇烈的的運(yùn)動上的不足。新三步法在三步法第一步搜索的基礎(chǔ)上增加了對中心點(diǎn)的8個鄰域的測試，并采用了提前終止的策略，倘若最小的bdm (block distortion m

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

51、塊只需測試17個點(diǎn)，對于亞靜止的塊需要測試20或者22個點(diǎn)，所以ntss相對于tss有了一定的改善，加速了約18%。 圖2-6 新三步搜索法fig2-6 new three step search2.5.4菱形搜索法 (diamond search)菱形搜索法因其搜索模板像鉆石又被稱為 “鉆石”搜索算法17，它采用ldsp（large diamond search pattern，大鉆石搜索模板）和sdsp（small diamond search pattern，小鉆石搜索模板）兩種搜索模板，如圖2-7所示?！般@石”搜索算法，先采用步長大、范圍廣ldsp模板搜索，進(jìn)行一個粗略的定位，這也符合

52、視頻圖像運(yùn)動的基本規(guī)律，陷于局部最優(yōu)的可能性降低；當(dāng)完成了粗略定位后，再采用sdsp模板搜索ldsp中得到的最小sad值點(diǎn)的周圍4個點(diǎn)，這時得到的sad值最小點(diǎn)便是最優(yōu)匹配點(diǎn)，這樣做避免了陷入局部最優(yōu)，提升了運(yùn)動估計的準(zhǔn)確度。 （a）大菱形 （b）小菱形圖2-7 “鉆石”搜索模板fig2-7 diamond search templateds算法流程如下:第一步:以搜索窗口的原點(diǎn)(o，0)為中心，采用ldsp模板，檢測這九個點(diǎn)。如果mbd(minimum block distortion)點(diǎn)位于中心，就轉(zhuǎn)至第三步;否則，轉(zhuǎn)至第二步繼續(xù)搜索。第二步:以第一步搜索得到的mbd點(diǎn)為中心，構(gòu)造另一個l

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

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

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

56、一步的最佳匹配點(diǎn)的位置作為搜索中心，做一個55 范圍的全搜索，如圖 2-9 中 step3-1 的圓圈所示；第二步進(jìn)行多層次六邊形搜索，采用了16 點(diǎn)的六邊形，即圖 2-9 中 step3-2 的小方形所示，如圖 2-9 所示，六邊形覆蓋的區(qū)域比較大，而且六邊形左右兩側(cè)的點(diǎn)數(shù)比上下兩側(cè)的搜索點(diǎn)數(shù)多，這也符合運(yùn)動的規(guī)律。六邊形由里到外層層搜索，等搜索結(jié)束后，比較每層中相對較小的sad值，其中最小的sad值所對應(yīng)的位置便是下一步繼續(xù)搜索位置的中心。第四步：擴(kuò)展的六邊形搜索，第三步的多層次六邊形搜索可以得到不同精度的運(yùn)動矢量，當(dāng)最佳匹配塊在外部六邊形時，得到的運(yùn)動矢量精度就偏低，故需要進(jìn)一步細(xì)化搜索，通常用六邊形繼續(xù)下一步的搜索，如圖 2-9 step4 所示。先采用半徑為 2 的六邊形反復(fù)搜索，直到最佳點(diǎn)出現(xiàn)在六邊形中心，接下來用半徑為 1 的小菱形繼續(xù)搜索，直至最佳匹配塊位于小菱形的中心。圖2-9 非對稱十字型多層次六邊形格點(diǎn)運(yùn)動搜索算法fig2-9 asymmetric cross-shaped multi-layered hexagonal movement grid search algorithm通過對以上幾種搜索算法的實(shí)現(xiàn)過程對比，