菱形搜索算法

1、 畢 業(yè) 論 文（設(shè) 計） 2013 屆 通信工程 專業(yè) 0913071 班級 題 目 菱形搜索運動估計算法研究及實現(xiàn) 姓 名 學號 指導教師 職稱 二零一三 年 五 月 二十四 日23 內(nèi) 容 提 要 運動估計是視頻壓縮編碼中的核心技術(shù)之一。采用運動估計和運動補償技術(shù)可以消除視頻信號的時間冗余，從而提高編碼效率；運動估計搜索算法是幀間編碼的基礎(chǔ)，常用的運動估計搜索算法采用在搜索區(qū)域內(nèi)搜索最佳絕對誤差和（SAD，Sum of Absolute Differences）匹配點來進行宏塊匹配，獲得宏塊的運動矢量。不同的搜索方法在搜索最佳SAD點上采用不同的搜索策略。常見的快速搜索算法有三步法、新三

2、步法、四步法、塊梯度下降法以及菱形搜索算法等，本文主要研究菱形搜索運動估計算法并實現(xiàn)，首先闡述了課題的背景與意義和運動估計的研究現(xiàn)狀，其次詳細介紹了運動估計的原理以及典型塊運動估計算法，分析它們的技術(shù)特點，然后重點介紹了菱形搜索算法，并在Visual C+ 6.0環(huán)境下編寫程序代碼將之實現(xiàn)，最后進行仿真得出實驗結(jié)果。 關(guān) 鍵 詞 視頻壓縮;運動估計;塊匹配;菱形搜索 The Realization Of Diamond Searching Motion Estimation Algorithm Author: Tutor: Abstract Motion estimation is the v

3、ideo compression coding technology of the core. Using motion estimation and motion compensation techniques can eliminate temporal redundancy of the video signal, thereby improving the encoding efficiency; motion estimation search algorithm based on inter-coded, the common motion estimation search al

4、gorithm of the search area to search the best absolute error and SAD (Sum of Absolute Differences) matching points to the macro block matching motion vector of the macro block obtained. Different search method searches for the best SAD point different search strategies. Common fast search algorithm

5、has three steps, the new three-step method, four-step, block gradient descent and diamond search algorithm, etc. This paper studies the diamond search motion estimation algorithm and implementation, first describes the background and significance of the subject and motion estimation research status,

6、 followed by details of the motion estimation principle and the typical block motion estimation algorithm to analyze their technical characteristics, and then focuses on the diamond search algorithm, and the Visual C + + 6.0 environment to prepare the program code of the implementation, and finally

7、the simulation The experimental results obtained. KeywordsVideo Compression Motion Estimation Block Matching Diamond Search 目 錄內(nèi)容提要IAbstractII目錄III第一章 緒論11.1 課題的背景與意義11.2 運動估計的研究現(xiàn)狀21.3 本文的主要內(nèi)容及工作安排3第二章 運動估計52.1 運動估計原理52.2 典型塊運動估計算法分析62.2.1 全搜索算法（FS）62.2.2 快速搜索算法7第三章 菱形搜索算法的實現(xiàn)133.1 菱形搜索算法133.1.1 算法分析

8、133.1.2 算法的基本思想143.1.3 算法描述153.2 菱形搜索的核心代碼15第四章 仿真分析184.1 仿真實驗結(jié)果184.2 實驗結(jié)果分析20第五章 結(jié)果與展望21致 謝22參考資料23菱形搜索運動估計算法研究及實現(xiàn) 第一章 緒論 1.1 課題的背景與意義 隨著信息技術(shù)的發(fā)展和社會的不斷進步，人類對信息的需求越來越豐富，人們希望無論何時何地都能夠方便、快捷、靈活的通過語音、數(shù)據(jù)、圖像與視頻等多種方式進行通信。視覺信息給人們直觀生動的形象，圖像/視頻的傳輸更受到廣泛的關(guān)注。數(shù)字信號處理技術(shù)、物理媒體與網(wǎng)絡(luò)技術(shù)、超大規(guī)模集成電路技術(shù)突飛猛進的發(fā)展，使得多媒體通信研究成為研究應用的熱點

9、。其中，最為關(guān)鍵的技術(shù)是數(shù)字視頻的處理與傳輸技術(shù)，它將電視技術(shù)、計算機技術(shù)和通信技術(shù)結(jié)合在一起，在電視系統(tǒng)，計算機網(wǎng)絡(luò)和通信產(chǎn)業(yè)中得到了廣泛的應用，已經(jīng)進入千家萬戶的生活中。數(shù)字視頻硬件方面的進步和數(shù)字視頻壓縮國際標準的推出，使得數(shù)字視頻技術(shù)領(lǐng)域趨于成熟。在圖像通信領(lǐng)域，新的多媒體通信方式的不斷出現(xiàn)，尤其是Internet和數(shù)字移動通信的迅速普及，利用IP網(wǎng)絡(luò)以及寬帶無線網(wǎng)絡(luò)進行圖像和視頻信息的傳輸成為備受人們重視的新方式。但是大量頻繁的圖像、視頻信息的交流與存貯活動也帶來了許多新要求和新問題，視頻通信比其他類型的信息傳輸要占用更多的帶寬資源。例如，幀速率為30幀每秒、圖像大小為1920*10

10、80、每個像素采用24為偽彩來存放亮度和色度分量的高清電視，則該數(shù)字視頻要求帶寬為：1920*1080*24*30=1423.83Mbps=1.3Gbps數(shù)字視頻信息的數(shù)據(jù)量是非常巨大的，若不經(jīng)過壓縮，數(shù)字圖像傳輸所需要的高傳輸速率與數(shù)字圖像存儲所需要的巨大容量將成為推廣應用數(shù)字視頻技術(shù)的最大障礙。雖然視頻圖像的數(shù)據(jù)量大，但是圖像序列以及圖像內(nèi)部數(shù)據(jù)具有高度相關(guān)性，存在大量信息冗余。因此，雖然數(shù)字化的視頻圖像是非常大，仍然可以通過消除冗余實現(xiàn)圖像/視頻的壓縮。這些冗余主要包括：信息熵冗余、時間冗余、結(jié)構(gòu)冗余、知識冗余、空間冗余等形式。視頻圖像壓縮編碼就是要用量少的比特數(shù)來表征圖像/視頻信息，同

11、時又要保證圖像的質(zhì)量。運動估計是視頻壓縮系統(tǒng)中的一個重要組成部分，其效率主要體現(xiàn)在圖像質(zhì)量、壓縮碼率和搜索速度(復雜度)三個方面。其基本原理是利用視頻圖像序列中相鄰幀之間存在的時間相關(guān)性，建立序列相鄰幀之間表達上的相互關(guān)系，從而減少時間冗余，提高視頻壓縮編碼的效率。運動估計越準確，預測補償?shù)膱D像質(zhì)量越高，補償?shù)臍埐罹驮叫?，補償編碼所需位數(shù)越少，比特率越小。運動估計速度越快，越有利于實時應用。因此，提高圖像質(zhì)量，加快估計速度，減小比特率是運動估計算法研究的目標。當前來提高算法效率。常用的方法主要是通過確定初始搜索點、選取合適的匹配準則及運動搜索策略。運動估計首先通過對物體位移的估計得到運動矢量，

12、然后對前一幀進行運動補償，這樣就使得預測幀更接近本幀。因此，運動估計算法對運動補償?shù)男阅芫哂兄匾绊?。通過運動估計算法提高運動矢量的準確性，對減少預測誤差、信息傳輸量，提高系統(tǒng)的碼率壓縮比具有重要作用。運動估計的這些特點可有效減少時間相關(guān)性，針對視頻序列圖像在時間軸上具有較強的相關(guān)性特點，運動估計技術(shù)被廣泛應用于各種視頻壓縮編碼方案中，已經(jīng)成為視頻序列圖像編碼系統(tǒng)實現(xiàn)的重要技術(shù)。1.2 運動估計的研究現(xiàn)狀 運動估計算法通常分為兩類：一類是像素遞歸算法PRA(Pixel recursive Algorithm);另一類是塊匹配算法BMA（Block Matching Algorithm）.PRA

13、是基于遞歸思想，如果連續(xù)幀中像素數(shù)據(jù)的變化是因為物體的移位引起的，算法就會沿著梯度方向?qū)δ硞€像素周圍的若干像素做迭代運算，使連續(xù)的運算最后收斂于一個固定的運動估計矢量，從而預測該像素的位移；而BMA則是基于當前幀中一定大小的塊，在當前幀的前后幀的一定區(qū)域內(nèi)搜索該像素塊的最佳匹配快，作為它的預測快。盡管PRA對比較復雜的運動形式來說，其預測精度要高于BMA，但是由于其計算量比BMA大的多，同時BMA本身也擁有較好的性能，因此目前視頻壓縮編碼國際標準普遍都采用BMA。菱形搜索屬于塊匹配的運動估計算法，因此，本文的研究都是針對塊匹配的運動估計。 運動估計和運動補償是現(xiàn)階段視頻壓縮編碼的關(guān)鍵技術(shù)。運動

14、估計目前面臨的主要問題就是如何比較快速的得到比較準確的運動矢量，因為在整個視頻編碼的過程中，即使采用快速算法，運動估計仍然是耗時最長、資源占用最高的環(huán)節(jié)。高效快速的運動估計算法一直是視頻壓縮編碼領(lǐng)域的研究熱點。常見的快速搜索算法有三步法、新三步法、四步法、塊梯形下降法以及菱形搜索算法，目前的各種搜索算法都存在搜索速度和精度相矛盾的問題，同時在特定的視頻序列中，搜索精度和搜索速度都有提升的空間。1.3 本文的主要內(nèi)容及工作安排第1章 緒論。通過查閱大量的相關(guān)文獻介紹了課題的背景與研究的重要性。簡要介紹了現(xiàn)今運動估計的研究現(xiàn)狀，并敘述了本文的主要內(nèi)容和課題安排第2章 運動估計。介紹了運動估計的原理

15、以及幾種常見搜索算法運動估計。 第三章 菱形搜索算法運動估計的設(shè)計及實現(xiàn)。 第四章 系統(tǒng)仿真。介紹了本文提出的菱形搜索運動估計算法的系統(tǒng)仿真實驗結(jié)果。通過對實驗結(jié)果中數(shù)據(jù)列表的分析實現(xiàn)預期的研究目標。第五章 總結(jié)。總結(jié)全文的研究成果。并對運動估計算法研究進行了展望，提出了進一步的研究工作。 第二章 運動估計 由于視頻序列圖像在時間上具有較強的相關(guān)性，運動估計及運動補償技術(shù)可以有效的減少時間相關(guān)性，因此該技術(shù)被廣泛應用于各種視頻壓縮編碼方案中。運動估計用來估計物體的位移，得到運動矢量；運動補償根據(jù)得到運動矢量，對前一幀中由于運動而產(chǎn)生的位移進行調(diào)整，從而得到盡可能接近本幀的預測幀，由此可見，運動

16、估計算法越完善，估計出的矢量越準確，運動補償?shù)男阅芫驮胶?，從而使預測誤差越小，編碼后需要傳輸?shù)男畔⒘恳矊㈦S之大大減少，整個系統(tǒng)的壓縮效率就會的到很大的提高，因此運動估計和補償技術(shù)已經(jīng)成為視頻序列圖像編碼系統(tǒng)中減少時間冗余、提高壓縮比的重要性。2.1 運動估計原理 運動估計是視頻編碼和視頻處理中廣泛使用的一種技術(shù)。是視頻編碼系統(tǒng)的關(guān)鍵部分，同時也是整個視頻編碼器中計算量最大的部分。運動估計性能的優(yōu)劣直接影響到整個視頻編碼器的運行效率和整個視頻序列的重構(gòu)質(zhì)量。運動估計是將圖像序列的每一幀分成許多互不重疊的宏塊，并認為宏塊內(nèi)所有象素的位移量都相同，然后對每個宏塊到參考幀某一給定特定搜索范圍內(nèi)根據(jù)一定

17、的匹配準則找出與當前塊最相似的塊，即匹配塊，匹配塊與當前塊的相對位移即為運動矢量。視頻壓縮的時候，只需保存運動矢量和殘差數(shù)據(jù)就可以完全恢復出當前塊。在幀間預測編碼中，由于活動圖像鄰近幀中的景物存在著一定的相關(guān)性。因此，可將活動圖像分成若干塊或宏塊，并設(shè)法搜索出每個塊或宏塊在鄰近幀圖像中的位置，并得出兩者之間的空間位置的相對偏移量，得到的相對偏移量就是通常所指的運動矢量，得到運動矢量的過程被稱為運動估計。運動矢量和經(jīng)過運動匹配后得到的預測誤差共同發(fā)送到解碼端，在解碼端按照運動矢量指明的位置，從已經(jīng)解碼的鄰近參考幀圖像中找到相應的塊或宏塊，和預測誤差相加后就得到了塊或宏塊在當前幀中的位置。2.2

18、典型塊運動估計算法分析 常見的塊運動估計算法有全搜索法、三步法、新三步法、四步法塊梯度下降法及菱形搜索法，其算法的基本思想及描述分別如下文所述。 2.2.1 全搜索算法（FS） （1）全搜索算法分析 全搜索算法（Full Search Method,FS）是所有運動估計算法中最簡單、最原始的塊匹配算法，它對整個搜索窗口的每一個點進行塊匹配運算，所以單從塊匹配的角度看，全搜索是最好的匹配方法。但它的計算量很大，需要計算的點數(shù)多，它在整個視頻壓縮編碼過程中占有大部分的運算量，限制了在需要實時壓縮場合的應用，所以實時視頻壓縮編碼實現(xiàn)很大程度上取決于運動估計算法的優(yōu)化。 （2）算法的基本思想 FS算法

19、是一種搜索策略最簡單的搜索算法。它對MN搜索范圍內(nèi)所有可能的候選位置計算SAD（i,j）值，從中找出最小SAD值，其對應偏移量即為所求運動矢量。 （3）算法的描述 第一步:從（0,0）點出發(fā)，按某種搜索路徑由近及遠，逐個像素點計算SAD值，直到遍歷搜索窗內(nèi)所有的點； 第二步:在所有的SAD中找到最小塊誤差（Minimum Block Distortion,MBD）點，該點即為最佳匹配點。 2.2.2 快速搜索算法 1 三步搜索法 （1）算法分析 三步搜索算法（TSS,Three-Step Search）是一種由粗到精的搜索算法，快速而且高效。它通過三步搜索，逐步減小搜索步長。每次搜索都是以上一

20、步的搜索結(jié)果為中心，進行周圍步長為33像素搜索。由于簡單，性能良好等特點，為人們所重視。最大搜索長度為7，搜索精度取一個像素，則步長為4、2、1，共需三步即可滿足要求，因此而得名三步法。 TSS是較早的搜索速度和搜索精度兩者取得比較適當折中的快速搜索算法，因其搜索步驟簡單固定且易于硬件實現(xiàn)，已經(jīng)在很多視頻壓縮系統(tǒng)中的到了應用。針對一個1616的像素子塊，TSS算法共搜索25個點，而FS要進行1515=225個點的搜索，運算時間明顯減少。它還是簡單容易實現(xiàn)、每個塊的搜索點數(shù)相同的優(yōu)點。但它有個致命的缺點：第一步過于粗糙，在搜索范圍較大是（如16或者更大），初始步長相對于塊的運動矢量估計來說就太大

21、了，跳出了運動矢量存在可能性較大的區(qū)域，導致搜索方向的不確定性，因此很容易陷入局部最優(yōu)。 （2）算法的基本思想 三步搜索算法采用一種有粗到細的搜索模式，從搜索窗口中心開始，按一定步長取周圍8個點作匹配運算，文中采用的初始搜索步長為4，得到MBD點后，每次利用上一步搜索得到的最佳匹配位置作為當前搜索的中心位置，沒做一步，搜索步長減半，直至搜索結(jié)束。 （3）算法描述 第一步：以窗口中心（0,0）為中心搜索點，步長為4，包括周圍的8個像素點，計算SAD值各點得到一個MBD點，共搜索9個點。 第二步：以上一步的最佳匹配點中心，步長為2，繼續(xù)搜索周圍8個像素點，計算各點SAD值得到MBD點，共搜索8個點

22、。 第三步：同上一步，只是步長減小1，最后得到的MBD點就是需要的運動估計的點，從而得到運動矢量。 為了克服TSS的上述缺點，1994年出現(xiàn)了新三步搜索法（NTSS）,該算法利用視頻運動矢量的中心偏置分布特點，加強搜索中心區(qū)域，因此搜索精度有一定程度的提高。另外，NTSS引入“中途退出”的思想，雖然比較粗糙，但為以后的快速算法提出了一種新的策略。2 新三步搜索法（1） 算法分析 傳統(tǒng)的快速搜索算法如三步法等屬于多級搜索的第一步，搜索點是固定的，這些點在搜索窗內(nèi)的位置，由于假定全局極值點位置出現(xiàn)的概率在搜索窗內(nèi)均勻分布，所以也是均勻固定分布的，這種搜索模式對于某些僅有細微運動的塊來說，并非準確。

23、因此如何在搜索第一步時優(yōu)化設(shè)計搜索模式非常重要。這種優(yōu)化與全局極值點的概率分布密切相關(guān)。因此，我們需要考慮視頻序列的全局極值點的概率分布特征。Renxiang Li等在三步算法的基礎(chǔ)上做一些改進得到了新三步搜索（New Three-Step Search,NTSS)算法。三步算法由于其簡單高效和數(shù)據(jù)存取的規(guī)律性受到普遍歡迎，但三步算法對現(xiàn)實視頻序列的中心偏置特性欠缺考慮。NTSS算法在這方面做了改進，從而獲得比三步算法更好的性能。 (2) 算法的基本思想 在現(xiàn)實的視頻序列中，運動矢量的分布是具有中心偏置特性的，為驗證此特性，NTSS算法在第一步中通過搜索增加的中心8個點來修改搜索模塊，同時NT

24、SS使用半路終止技術(shù)來增加靜止塊的匹配，從此來減少搜索次數(shù)。 三步算法在第一步對九個點做匹配運算，這九個點在搜索窗口中是等間距分配的，沒有考慮塊的中心偏置，新三步在第一步對搜索中心周圍的八個點也同時做匹配運算，在很多運算情況下可以提前終止。 NTSS算法與三步法的不同在于以下兩點： 改進了原有三步法第一步中搜索固定9個點的方法，采用了中心偏置的搜索模式。 對靜態(tài)子塊或者準靜態(tài)子塊的搜索引入了中途停止的功能。（3）算法描述第一步：對搜索窗口中心99的矩形框和33的矩形框17個點進行匹配運算。17個點的位置如圖2.1所示 圖2.1 NTSS算法第一步搜索點如果第一步搜索中最小SAD像素點發(fā)生在搜索

25、窗中心相鄰的8個點，第二步的搜索模式有兩種可能，其中白點是待搜索點，如圖2.2所示： 圖2.2 NTSS算法第二步搜索點 第二步根據(jù)第一步得到最小SAD值得位置決定第二步匹配的位置：（1） 如果在搜索窗口的中心位置得到最小的SAD值，則停止搜索；（2） 如果最小的SAD值在33的矩形框上得到，則搜索一此點為中心位置的33的窗口，并結(jié)束搜索；（3） 如果最小的SAD值在99的矩形框上得到，則搜索的步驟與TSS算法相同，搜索完成后跳到第三步。第三步：以第二步得到的最佳匹配位置為中心，做最后的33窗口中九個點的匹配，得到最小SAD值得位置，就是最佳匹配位置。 由于運動矢量通?？偸歉叨燃蟹植荚谒阉鞔?/p>

26、的中心位置附近，因此NTSS采用基于中心偏置的搜索模式不僅提高了匹配速度，也減少了陷入局部最優(yōu)的可能性；而采用中止判別技術(shù)則大大降低了搜搜復雜度，提高搜索效率。NTSS針對TSS搜索算法中第一步搜索步長過大而容易陷入局部最優(yōu)的缺陷進行了改進，新增8個搜索點用來保證緩慢運動的要求，第一步大的步長有可以滿足快速運動的要求。 我們一搜索范圍為（-7，7）搜索窗口大小為1515為例說明這種算法的性能。NTSS算法在最好的情況下只需做17個點的匹配，最壞的情況下需要做33個點的匹配，由于運動矢量的中心偏置特性在現(xiàn)實視頻序列中是普遍存在的，在通常情況下，NTSS算法需要做33點匹配的概率比較小，因此，在低

27、速率視頻應用中，如視頻電話或視頻會議中，NTSS算法的優(yōu)點可以得到較好的發(fā)揮。3 四步搜索法（1）算法分析 新三步搜索算法考慮了塊矢量中心偏移的特性，在初步搜索時對中心周圍的位置同時做了匹配運算。在物體做小范圍運動時，這種改進很有效，可以大大減少運算量，然而，在物體做大范圍運動時，這種改進卻帶來了額外的運算量。 現(xiàn)實的情況經(jīng)常是物體既有小范圍的偏移，也有大范圍的運動。因此，在考慮塊匹配算法時，既要照顧塊的中心偏移特性，也要兼顧塊的大范圍運動。四步搜索（Four-Step Search,FSS）能夠兼顧良好種情況，可以的到較好的性能。（2）算法的基本思想 該算法類似于三步法，但它基于現(xiàn)實中序列圖

28、像的一個特征，即運動矢量都是中心分布的，從而在55大小的搜索窗口上構(gòu)造了有九個檢測點的搜索模板，F(xiàn)SS算法首先采用55的搜索窗口，沒有像TSS算法使用99的搜索窗，避免造成搜索方向的偏離，每一步的搜索范圍由上一步的最佳匹配位置決定，并且將搜索窗的中心移向MBD點處，前三部的搜索是定步長搜索，最后一次改變步長，得到最后的最佳匹配位置，且后兩步搜索窗的大小依賴于MBD點的位置。（3）算法描述 FSS算法流程如下： 第一步：對在中心位置周圍等步長的55矩形框上九個點做匹配運算，如果得到最小SAD值在窗口的中心位置，則將搜索窗口改為33 ，轉(zhuǎn)到第四步，否則執(zhí)行第二步； 圖 2.3 第二步：搜索窗口的位

29、置依照第一步的結(jié)果而定：（1） 如果第一步得出的最小SAD值在四個頂點上，則額外的5個位置需要做匹配運算，如圖2.3（b）的情況；（2） 如果第一步得出的最小SAD值在四個邊上，則額外的3個位置需要做匹配運算，如圖2.3（c）的情況;（3） 如果第一步得出的最小SAD 匹配位置在窗口的中心位置，則直接轉(zhuǎn)到第四步，否則執(zhí)行第三步；第三步：與第二步的搜索過程相同，只是做完搜索后直接轉(zhuǎn)到第四步。第四步：對33搜索矩形框的九個點做匹配運算，得出的最佳匹配位置就是最終的匹配位置。4 基于塊的梯度下降搜索法（BBGDS） 基于塊的梯度下降法（Block-Based Gradient Descent Sea

30、rch,BBGDS）利用運動矢量中心分布特性，第一步使用33的正方形模板搜索窗對9個點進行搜索。在第二步中，若MBD點在搜索窗中心，則算法結(jié)束；否則以上一步MBD點為中心，重復第一步。視頻幀內(nèi)相鄰像素間具有漸變性，每一步的MBD點分布具有一定的方向性，也即梯度下降方向來決定下一步的搜索方向。 在每一步搜索過程中，使用了中心匹配塊而不是匹配點，降低了局部最優(yōu)的可能性。引入梯度下降的概念，用梯度下降的方向來指導搜索方向，對該方向進行重點搜索，從而減少和避免了不必要的搜索，大大降低了算法的復雜度。 第三章 菱形搜索算法的實現(xiàn)3.1 菱形搜索算法 菱形搜索法（DS，Diamond Search)采用兩

31、種搜索模板：大菱形搜索模板LDSP（Large Diamond Search Patten）和小菱形搜索模板SDSP（Small Diamond Search Patten）。搜索模板的形狀和大小是決定整個算法運行速度及性能的關(guān)鍵所在。統(tǒng)計數(shù)據(jù)表明，視頻圖像中進行運動估計時，最優(yōu)點通常是零矢量的周圍，如圖3.1所示，以搜索窗口中心為圓心，兩像素為半徑的圓內(nèi)。圖3.1中的13個點便是圓內(nèi)所有可能的檢測點。 圖3.1 菱形法中運動矢量的中心偏置分布規(guī)律 3.1.1 算法分析 DS算法是一種高效的運動估計方法，它分析了視頻圖像中運動矢量的基本規(guī)律，選用了大小兩種形狀的搜索模板LDSP和SDSP。先用

32、LDSP搜索，搜索范圍廣，可以進行粗定位，搜索過程不會陷于局部最?。划敶侄ㄎ唤Y(jié)束后，可以認為最優(yōu)點就在LDSP周圍8個點的菱形區(qū)此外，DS搜索時各步驟之間有很強的相關(guān)性，模板移動時只需在幾個新的檢測點處進行匹配計算，所以也提高了搜索速度。3.1.2 算法的基本思想 根據(jù)實驗數(shù)據(jù)統(tǒng)計表明, 利用全搜索算法計算獲得的運動向量分布概率和距離搜索中心點的距離之間的關(guān)系可以看出, 50%至90%的運動向量集中在以搜索中心為圓心的半徑為2的圓上,如圖3.1所示，根據(jù)實際視頻序列物體運動的統(tǒng)計,實際視頻中塊的運動可以在任何方向上進行運動,但主要集中在水平和垂直兩個方向上(攝像機運動)。所以圖3.1中在半徑為

33、2的圓中的13個搜索點是具有最優(yōu)匹配概率最大的點。所以在該圓形區(qū)域內(nèi)進行搜索,搜索匹配的點數(shù)最小而能獲得最佳的搜索效果?；谏鲜隼碚?菱形搜索算法被提出。為了使得搜索范圍為以搜索中心為原點的圓,菱形搜索算法采用了兩個搜索模式, 如圖3.2所示。一個模式稱為大菱形搜索模式( LDSP)，采用9 個搜索點,包括搜索中心,以及8個按照菱形分布的圍繞點。第二個模式成為小菱形搜索模式( SDSP),采用搜索中心和與其相鄰的水平垂直方向上的4個點共5 個點組成小菱形。DS 搜索算法的搜索過程首先以搜索中心為中心,進行大菱形搜索,計算9個點,如果最小MAD的點不在大菱形的中心的話,將大菱形中心移到相應最小M

34、AD的點上,重復大菱形搜索,直到最小MAD的點位于大菱形的中心為止。然后在該中心點上切換到小菱形搜索,共搜索5 個點得到最終的搜索結(jié)果作為運動估計的最優(yōu)匹配點。 圖3.2 LDSP 模板與SDSP 模板 3.1.3 算法描述 Step1:用LDSP在搜索區(qū)域中心及周圍八個點出進行匹配計算，若MBD位于中心點，則進行Step3；否則進行Step2。 Step2：以Step1找到MBD點作為中心點，用新的LDSP來計算，若MBD位于中心點，則進行Step3；否則重復Step2。 Step3：以Step1找到MBD點作為中心點，將LDSP換為SDSP，在五個點處計算，找出MBD點，該點所在位置及對應

35、最佳運動矢量。 DS 算法的優(yōu)勢在于它把握了視頻序列中運動矢量的基本規(guī)律，所以它的性能優(yōu)于其他算法。但DS 只是一種搜索策略上的折中處理，其性能的缺陷表現(xiàn)在：不論是大運動圖像序列，還是保持靜止的圖像序列，DS 算法同等地對待搜索區(qū)域的各個部分，而且都要經(jīng)歷從大模板到小模板的搜索過程，至少要對13 個搜索點進行計算，這樣造成了較大的搜索冗余，影響了算法的搜索速度。因此，DS算法有待改進。 3.2 菱形搜索的核心代碼 基于3.1節(jié)對菱形搜索算法的描述，設(shè)計編寫程序，其核心代碼為： void search_DS(const int x,const int y,const int heigth,con

36、st int width)const int ox=x*BLOCK_HEIGTH,oy=y*BLOCK_WIDTH;const int LDS92=0,0,0,2,-1,1,-2,0,-1,-1,0,-2,1,-1,2,0,1,1;const int SDS52=0,0,0,1,-1,0,0,-1,1,0;uint32 sad=0xffffff;MV mv=0,0;int mvx,mvy;PATTERN_SEARCH(LDS,9,1)PATTERN_SEARCH(SDS,5,0)frame_info.mvxy=mv;frame_info.sadxy=sad;frame_info.frame_s

37、ad+=sad; void main()int num;if(fp_cur = fopen(news_cif.yuv,rb)=NULL)return;if(fp_ref = fopen(news_cif.yuv.enc,rb)=NULL)return;frame_info.sum_pot=frame_info.sum_sad=frame_info.sum_sse=0;frame_info.mv=_mv_buffer0;frame_info.prev_mv=_mv_buffer1;printf(frametcosttpsnrn);for(num=0;num15;num+)int i,j;fsee

38、k(fp_cur,XX*YY*3/2*(num+1),SEEK_SET);if(fread(current_frame0,XX*YY,1,fp_cur)=0)break;fseek(fp_ref,XX*YY*3/2*(num+0),SEEK_SET);if(fread( ref_frame0,XX*YY,1,fp_ref)=0)break;frame_info.frame_pot=frame_info.frame_sad=frame_info.frame_sse=0;for( i=0;iX;i+)for( j=0;jY;j+)memset(_flag_search,0,SEARCH_RANGE

39、*SEARCH_RANGE);search_DS(i,j,BLOCK_HEIGTH,BLOCK_WIDTH);rebuilt(i,j,BLOCK_HEIGTH,BLOCK_WIDTH);frame_info.sum_pot+=frame_info.frame_pot;frame_info.sum_sad+=frame_info.frame_sad;frame_info.sum_sse+=frame_info.frame_sse;MV (*mv_tmp)Y=frame_info.mv;frame_info.mv=frame_info.prev_mv;frame_info.prev_mv=mv_t

40、mp;memcpy(frame_info.prev_sad,frame_info.sad,X*Y*sizeof(uint32);printf(%dt%.2ft%.2fn,num,(float)frame_info.frame_pot/X/Y,10*log10(XX*YY*255*255.0/frame_info.frame_sse);printf(nAvg:t%.2ft%.2fn,(float)frame_info.sum_pot/X/Y/num,10*log10(XX*YY*255*255.0*num/frame_info.sum_sse);fclose(fp_cur);fclose(fp_

41、ref) 第四章 仿真分析仿真實驗在Visual C+60的環(huán)境下進行，仿真視頻序列為3個CIF（Common intermediate format）標準測試序列 hall、mother-daughter、news的前15幀。 仿真實驗時，在測試過程中，運動估計的宏塊大小為1616，搜索范圍為1515，即7個像素點。測試序列中每幀圖像的大小為352288。最佳搜索點采用最小SAD匹配準則。用cost表示平均每塊的搜索點數(shù)，psnr表示匹配之后的圖像與原始圖像的峰值信噪比。Cost和PSNR值均為在視頻序列15幀內(nèi)計算得到的平均值。4.1 仿真實驗結(jié)果（1）下圖4.1為視頻序列標準測試序列 hall 的實驗結(jié)果： 圖 4.1 由圖4.1可知視頻序列hall的平均搜索點cost為12.71，平均信噪比PSNR為37.98。 （2）下圖4.2為視頻序列標準測試序列Mother-daugh