【正文】 Container，Coastguard，News，Table Tennis的前100幀。但是由于它的計算量過大，在某些情況下發(fā)展了快速搜索算法。同時在得到同樣的運動矢量情況下，HEXBS算法使用了比DS算法更少的檢測點，因此提高了算法的搜索速度。搜索共用4步，每一步的MBn點分別為(l，2)、(2，4)、(2，4)、(2，4)，使用了三次LHSP和一次SHSP，總共搜索了17個點。(a)大六邊形模板 (b)小六邊形模板圖310六邊形搜索模板HSP2)算法描述第一步:用六邊形模板在搜索區(qū)域中心及中心周圍的6個點處進行匹配計算，若得到的MBD點位于中心點上，則執(zhí)行第二步，否則執(zhí)行第一步。HSP更接近圓形，其周圍各點到圓心的距離都是相同的，因此HSP在各個搜索方向都具有相同的梯度下降速度，搜索速度更快。HEXBS分析了菱形搜索算法中使用的大菱形模板(LDSP)的一些缺點，提出了新的六邊形搜索模板(Hexagon Seareh Pattern，HSP)。同理點11，13有相同的結(jié)論。鉆石搜索法的搜索過程如圖38所示:圖38 磚石搜索法鉆石搜索法最大的特點是提出了菱形的搜索模式，不限制搜索的步數(shù)，以及它對各個方向都進行搜索，而且著重考慮水平和垂直方向，因此可以使得搜索避免陷入局部最佳；另一方面，采用鉆石搜索法時各個步驟之間有很強的相關(guān)性，模板移動時只需在幾個新的檢測點處進行匹配，降低了計算量，從而也提高了搜索速度。鉆石搜索法的基本思想是減少進行塊匹配的搜索點，由圖26可以看到，搜索點大都位于圖像的水平和垂直方向上，這是因為現(xiàn)實中的物體在這兩個方向運動的概率比較大，圖像的頻譜多呈菱形分布，是由于圖像在水平和垂直方向的相關(guān)性大于斜線方向的。第一種模式為大鉆石型搜索模式(LDSP)。 鉆石搜索法（DS）1）算法基本思想當(dāng)視頻序列的運動比較劇烈時，固定步數(shù)模板匹配算法容易陷入局部最優(yōu)，使得視頻序列的質(zhì)量大為下降，因此出現(xiàn)了步數(shù)不限的快速模板匹配方法。第三步，與第二步操作相同，搜索新的點并進行匹配，不過不管結(jié)果如何，進行第四步。2）算法描述第一步，從原點開始，選取最大搜索長度的四分之一為步長（步長為2），在周圍距離步長的8個點處進行塊匹配計算并比較。同樣它的思想也是在搜索窗口中，以原點為中心，以一定的步長為距離，分四步來匹配特定的宏塊，來找到運動矢量。NTSS針對TSS搜索算法中第一步搜索步長過大而容易陷入局部最優(yōu)的缺陷進行了改進，新增8個搜索點用來保證緩慢運動的要求，第一步大的步長又可以滿足快速運動的要求。搜索完成后跳到第三步。這17個點的位置如下圖34。三步算法在第一步對九個點作匹配運算，這九個點在搜索窗口中是等間距分配的，沒有考慮塊的中心偏置，新三步在第一步對搜索中心周圍的八個點也同時作匹配運算，在很多情況下運算可以提前中止。三步算法由于其簡單高效和數(shù)據(jù)存取的規(guī)律性受到普遍歡迎，但三步算法對現(xiàn)實視頻序列的中心偏置特性欠缺考慮。通過用全搜索算法對全局極值點的概率分布進行統(tǒng)計，研究者發(fā)現(xiàn)全局極值點的分布并非像傳統(tǒng)的快速搜索算法預(yù)先假定的那樣在搜索窗內(nèi)均勻分布，而通常是基于中心偏移的，即在搜索窗中心附近出現(xiàn)全局極值點的概率遠(yuǎn)遠(yuǎn)大于在搜索窗邊緣出現(xiàn)的概率[11]。因此如何在搜索第一步時優(yōu)化設(shè)計搜索模式非常重要。而且它的思想相對簡單，在現(xiàn)實中也大為流行。第三步，當(dāng)搜索步長為1時，該點即為最后的最佳匹配點，這個點的位置就是當(dāng)前塊的運動矢量。三步搜索算法的基本思想是采用一種從粗到細(xì)的搜索模式，利用上一步搜索得到的最佳匹配位置作為當(dāng)前搜索的中心，每完成一步搜索的步長減半。全搜索算法能夠保證找到全局最小的SAD，保證最匹配的宏塊信息，而快速搜索算法為了保證速度，只在搜索區(qū)域中搜索特定的幾個可能的宏塊，因而易陷入局部最小。 快速匹配算法 三步搜索法（FSS）1）算法基本思想全搜索算法計算的復(fù)雜度讓人望而卻步，特別是對于要求實時的軟件編解碼器。但是有利必有弊，在高準(zhǔn)確度的光環(huán)下，隱藏著高運算量的陰影。全搜索主要有兩種具體形式：光柵式和螺旋式搜索。匹配速度主要看要匹配的總的像素數(shù)目，也就是估計一個運動矢量的平均搜索點的個數(shù)。第3章 典型塊匹配運動估計算法分析運動估計的搜索算法決定了視頻壓縮的性能和速度，是系統(tǒng)中最重要的一個環(huán)節(jié)。通常地，PSNR值高表示圖像具有比較高的質(zhì)量，PSNR值低則表示圖像具有比較低的質(zhì)量。人類視覺感知受空間保真度和時間保真度的影響，同時還受到其它因素的影響，如觀察環(huán)境、觀察者的精神狀態(tài)等。本文重點研究的是運動估計的硬件結(jié)構(gòu)，因此在條件允許和自身能力的范圍內(nèi)，選擇了整像素進行研究。所以整像素運動估計的精度在這個時候就捉襟見肘了。搜索區(qū)域的大小的確定就需要具體情況具體分析。搜索范圍有以下幾個特點：（1）不同的清晰度對應(yīng)的搜索范圍不同，清晰度越高就需要越大的搜索范圍來配合；（2）圖像的運動程度也有關(guān)系，圖像運動越劇烈，運動越明顯，就需要相應(yīng)比較大的搜索范圍；（3）搜索范圍的大小也決定了運算量的大小，當(dāng)搜索范圍取比較大時，就相應(yīng)計算量也多，占用的資源也越多。從而不需作乘法運算又易于硬件實現(xiàn)的MAD算法得到廣泛的應(yīng)用。 （24）結(jié)果最大時為最優(yōu)的匹配點。而且匹配運算、數(shù)據(jù)讀取復(fù)雜度很大程度上決定于所采用的塊匹配準(zhǔn)則。當(dāng)前的視頻壓縮標(biāo)準(zhǔn)，16大小的塊作為一個宏塊，這是一個已經(jīng)證明的較好的平衡結(jié)果。 分塊大小上面已經(jīng)提到過一點，塊匹配法有個前提，就是同一個塊內(nèi)的像素運動方向是一致的。對象的運動速度越塊，搜索窗也應(yīng)越大，即和的取值需加大，以覆蓋更大的運動范圍，從而獲得更高的預(yù)測精度。需要說明的是，由于假設(shè)宏塊中的所有像素都作相同的平移運動，因此宏塊中的任意一點都可以標(biāo)明其位置。這種方法在運動估計精度與計算復(fù)雜度之間提供了一個較好的折衷，其基本原理如圖23所示。運動估計的一個基本問題是如何選擇運動信息的表示方式，這又與運動估計的算法模型密切相關(guān)。目前研究最多的快速搜索算法，有三步法、四步法、新三步法、菱形法等，這些算法將在第三章詳細(xì)介紹。這樣運動補償方法是基于局部運動估計的，它對圖像中的宏塊進行操作，在參考幀圖像的搜索范圍內(nèi)，搜索與當(dāng)前幀最接近的宏塊，從而得到這個宏塊的運動矢量。運動估計是以宏塊為單位進行，計算被壓縮圖像與參考圖像的對應(yīng)位置上的宏塊間的位置偏移。這方面一種有效的方法就是基于塊匹配的運動估計(Motion Estimation，ME)，因為算法簡單，便于實現(xiàn)等優(yōu)點而得到廣泛的應(yīng)用?；谏鲜鲈?，高效快速的運動估計算法一直是視頻壓縮領(lǐng)域的研究熱點。(a)編碼器（b）解碼器圖21 典型的視頻壓縮編解碼系統(tǒng)在解碼端，如圖21(b)所示，壓縮碼流經(jīng)過變長解碼分成兩部分:運動矢量和預(yù)測誤差的逆信息，然后將預(yù)測誤差的逆信息經(jīng)過反量化、IDCT變換得到預(yù)測誤差，將運動矢量與幀存器里的前一幀進行運動補償?shù)玫筋A(yù)測幀，再將預(yù)測幀與預(yù)測誤差相加就得到了當(dāng)前幀的重構(gòu)圖像，同時保存到幀存器里作為下一幀的參考幀。運動補償根據(jù)得到的運動矢量，對前一幀中由于運動而產(chǎn)生的位移進行調(diào)整，從而得到盡可能接近本幀的預(yù)測幀?？偨Y(jié)與展望。介紹了運動估計的思想，著重分析了塊匹配運動估計的原理，對塊匹配運動估計的幾項重要的技術(shù)指標(biāo)(分塊的大小，匹配準(zhǔn)則，搜索范圍，估計精度)的確定進行了重點討論。在此基礎(chǔ)上，力爭提出一種優(yōu)化和改進后的塊匹配運動估計算法，使其能夠在保證圖像質(zhì)量的同時，搜索速度得到較大的提高。模板搜索快速算法是提出最早，發(fā)展最為成熟，也是應(yīng)用最為廣泛的一類快速算法。本文的研究都是針對塊匹配的運動估計算法，在后文中，如無特別說明，所提到的運動估計也都是指基于塊匹配的運動估計。另一類是塊匹配算法BMA(Block Matching Algorithm)。這里所說的變換去除空間相關(guān)性，僅僅局限在所變換的塊內(nèi)，如88或者44，并沒有塊與塊之間的處理。相對于早期的視頻壓縮標(biāo)準(zhǔn)，包括44的整數(shù)變換、空域內(nèi)的幀內(nèi)預(yù)測、1/4象素精度的運動估計、多參考幀與多種大小塊的幀間預(yù)測技術(shù)等。(3) (JVT)制定的新一代視頻壓縮編碼標(biāo)準(zhǔn)。且增加了4種有效的壓縮編碼模式。每幀圖像被分成圖像層、宏塊組(GOB)層、宏塊(MB)層、塊(Block)層來處理。該標(biāo)準(zhǔn)沒有規(guī)定利用描述進行搜索的工具或任何程序。這一變化會與1990年MPEG2壓縮標(biāo)準(zhǔn)的推出一樣巨大，而且隨著視頻通信應(yīng)用的快速發(fā)展，MPEG4標(biāo)準(zhǔn)勢會影響到范圍廣泛的多種應(yīng)用領(lǐng)域。據(jù)此目標(biāo)，MPEG4引入了AV對象(Audio/Visual Objects)，從而使得更多的交互操作成為可能。(4)MPEG4MPEG4于1998年11月公布，該標(biāo)準(zhǔn)提出了基于對象編碼的概念，不僅針對一定比特率下的視頻編碼、音頻編碼，更加注重于多媒體系統(tǒng)的交互性和靈活性。還可提供一個較廣的范圍改變壓縮比，以適應(yīng)不同畫面質(zhì)量、存儲容量以及帶寬的要求。MPEG2在NTSC制式下的分辨率可達720486,MPEG2能夠提供廣播級的視像和CD級的音質(zhì)。它可針對SIF標(biāo)準(zhǔn)分辨率(對于NTSC制為352240；對于PAL制為352288)的圖像進行壓縮，每秒播放30幀。1988年，MPEG(Moving Picture Expert Group)運動圖像專家組成立，它致力于運動圖像及其伴音編碼標(biāo)準(zhǔn)化的工作，包括MPEG系統(tǒng)，即MPEG視頻和MPEG音頻。經(jīng)過這個處理，殘差幀將包含很少的數(shù)據(jù)，因而可以用圖像解碼器對它進行有效的壓縮。每一幀都可以利用圖像編解碼器(JPEG)進行幀內(nèi)編碼(Intraframe Coding),每一幀在內(nèi)部先進行編碼而沒有考慮到其它的幀。視覺冗余：人類的視覺系統(tǒng)對圖像的敏感性是非均勻的和非線性的。研究數(shù)據(jù)表明，圖像幀內(nèi)的行、列相鄰點之間的相關(guān)性可以達到90%以上。普通的未壓縮視頻都是由一幀幀圖像序列組成的，一般1秒中包含24幀圖像。它的研究和應(yīng)用必將促進計算機通信、圖像通信和多媒體技術(shù)的發(fā)展?；谏鲜鲈?，高效快速的運動估計算法一直是視頻壓縮編碼領(lǐng)域的研究熱點。而幀間預(yù)測的方法基本上是以基于塊匹配的運動估計(補償)算法為主。運動估計和運動補償技術(shù)就是解決圖像幀間時間冗余的很好的方法。對于靜態(tài)圖像，最主要的數(shù)據(jù)冗余是空間冗余。由此可見，數(shù)字視頻信息的數(shù)據(jù)量是非常巨大的，若不經(jīng)過壓縮，數(shù)字圖像傳輸所需要的高傳輸速率和數(shù)字圖像存儲所需要的巨大容量將成為推廣應(yīng)用數(shù)字視頻技術(shù)的最大障礙。它們?yōu)橐曨l編碼技術(shù)的發(fā)展起到了巨大的推動作用。數(shù)字視頻硬件方面的進步和有關(guān)數(shù)字視頻壓縮國際標(biāo)準(zhǔn)的推出，使得數(shù)字視頻技術(shù)領(lǐng)域趨于成熟。 Threestep search method目 錄第1章 緒論 1 引言 1 課題的背景與意義 1 視頻壓縮技術(shù)介紹 3 運動估計的研究現(xiàn)狀 7 本文主要內(nèi)容和工作安排 7第2章 運動估計概述及其技術(shù)指標(biāo) 9 運動估計 10 塊匹配運動估計的基本原理 12 塊匹配的運動估計的參數(shù)和指標(biāo) 14 分塊大小 14 匹配準(zhǔn)則 14 搜索范圍的確定 15 估計精度 16 算法評定指標(biāo) 16第3章 典型塊匹配運動估計算法分析 18（FS） 18 快速匹配算法 19 三步搜索法（FSS） 19 新三步搜索法（NTSS） 21 四步搜索法（FSS） 24 鉆石搜索法（DS） 25 六邊形搜索法（HEXBS） 27 運動估計算法仿真 30 實驗平臺 30 三步搜索法仿真示例 31 實驗結(jié)果 33 實驗結(jié)果分析 35 本章小結(jié) 35結(jié)束語 37 本文工作總結(jié) 37 研究展望 37致謝 39參考文獻 40第1章 緒論 引言 課題的背景與意義隨著信息技術(shù)的發(fā)展和社會的不斷進步，人類對信息的需求越來越豐富，人們希望無論何時何地都能夠方便、快捷、靈活的通過語音、數(shù)據(jù)、圖像與視頻等多種方式進行通信。塊匹配。本論文中，主要的任務(wù)是分析和研究幾種經(jīng)典的運動估計算法，并對它們進行相關(guān)比較。采用運動估計和運動補償技術(shù)可以消除視頻信號的時間冗余，從而提高編碼效率。影響視頻壓縮編碼質(zhì)量和效率的因素很多，運動估計是其中最有影響力的因素之一。 學(xué)生應(yīng)完成的任務(wù) （1）了解運動補償?shù)哪康囊饬x和發(fā)展史； （2）掌握MATLAB仿真工具； （3）對基于塊匹配算法的運動補償預(yù)測方法進行仿真； （4）要求所編制的軟件在答辯時演示； （5）嚴(yán)格按照格式要求完成設(shè)計論文的排版打印，；