菱形搜索算法

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

2、步法、四步法、塊梯度下降法以及菱形搜索算法等，本文主要研究菱形搜索運(yùn)動(dòng)估計(jì)算法并實(shí)現(xiàn)，首先闡述了課題的背景與意義和運(yùn)動(dòng)估計(jì)的研究現(xiàn)狀，其次詳細(xì)介紹了運(yùn)動(dòng)估計(jì)的原理以及典型塊運(yùn)動(dòng)估計(jì)算法，分析它們的技術(shù)特點(diǎn)，然后重點(diǎn)介紹了菱形搜索算法，并在Visual C+ 6.0環(huán)境下編寫程序代碼將之實(shí)現(xiàn)，最后進(jìn)行仿真得出實(shí)驗(yàn)結(jié)果。 關(guān) 鍵 詞 視頻壓縮;運(yùn)動(dòng)估計(jì);塊匹配;菱形搜索 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 運(yùn)動(dòng)估計(jì)的研究現(xiàn)狀21.3 本文的主要內(nèi)容及工作安排3第二章 運(yùn)動(dòng)估計(jì)52.1 運(yùn)動(dòng)估計(jì)原理52.2 典型塊運(yùn)動(dòng)估計(jì)算法分析62.2.1 全搜索算法（FS）62.2.2 快速搜索算法7第三章 菱形搜索算法的實(shí)現(xiàn)133.1 菱形搜索算法133.1.1 算法分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

35、最佳運(yùn)動(dòng)矢量。 DS 算法的優(yōu)勢(shì)在于它把握了視頻序列中運(yùn)動(dòng)矢量的基本規(guī)律，所以它的性能優(yōu)于其他算法。但DS 只是一種搜索策略上的折中處理，其性能的缺陷表現(xiàn)在：不論是大運(yùn)動(dòng)圖像序列，還是保持靜止的圖像序列，DS 算法同等地對(duì)待搜索區(qū)域的各個(gè)部分，而且都要經(jīng)歷從大模板到小模板的搜索過程，至少要對(duì)13 個(gè)搜索點(diǎn)進(jìn)行計(jì)算，這樣造成了較大的搜索冗余，影響了算法的搜索速度。因此，DS算法有待改進(jìn)。 3.2 菱形搜索的核心代碼 基于3.1節(jié)對(duì)菱形搜索算法的描述，設(shè)計(jì)編寫程序，其核心代碼為： 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) 第四章 仿真分析仿真實(shí)驗(yàn)在Visual C+60的環(huán)境下進(jìn)行，仿真視頻序列為3個(gè)CIF（Common intermediate format）標(biāo)準(zhǔn)測(cè)試序列 hall、mother-daughter、news的前15幀。 仿真實(shí)驗(yàn)時(shí)，在測(cè)試過程中，運(yùn)動(dòng)估計(jì)的宏塊大小為1616，搜索范圍為1515，即7個(gè)像素點(diǎn)。測(cè)試序列中每幀圖像的大小為352288。最佳搜索點(diǎn)采用最小SAD匹配準(zhǔn)則。用cost表示平均每塊的搜索點(diǎn)數(shù)，psnr表示匹配之后的圖像與原始圖像的峰值信噪比。Cost和PSNR值均為在視頻序列15幀內(nèi)計(jì)算得到的平均值。4.1 仿真實(shí)驗(yàn)結(jié)果（1）下圖4.1為視頻序列標(biāo)準(zhǔn)測(cè)試序列 hall 的實(shí)驗(yàn)結(jié)果： 圖 4.1 由圖4.1可知視頻序列hall的平均搜索點(diǎn)cost為12.71，平均信噪比PSNR為37.98。 （2）下圖4.2為視頻序列標(biāo)準(zhǔn)測(cè)試序列Mother-daugh