多視點視頻編碼研究畢業(yè)論文

1、<p>　　畢 業(yè) 論 文</p><p><b>　　多視點視頻編碼研究</b></p><p>　　2013年 5月 20日</p><p><b>　　多視點視頻編碼研究</b></p><p><b>　　摘　　要</b></p><

2、p>　　本文在詳細(xì)研究JMVC編碼器（包括對JMVC代碼的閱讀調(diào)試、對各個編碼參數(shù)的提取及顯示）的基礎(chǔ)上，對JMVC編碼器進行改進使其在PSNR和碼率幾乎不變的情況下編碼時間明顯減少。</p><p>　　本文在詳細(xì)閱讀JMVC代碼的基礎(chǔ)上，首先提取編碼參數(shù)并創(chuàng)建了一個非常直觀的編碼參數(shù)顯示界面，利用ChartDirector庫和opencv庫，將所有的以幀為單位的參數(shù)都顯示在圖表之中，所有的以宏塊為單位的

3、參數(shù)都顯示在圖像控件上?？梢杂^察到整個序列的碼率、PSNR等參數(shù)的整體波動情況，并可以把一幀圖像所有運動矢量、宏塊劃分等信息直觀顯示在圖片上。</p><p>　　然后針對JMVC代碼的運動估計算法，本文提出了一種新的改進方法，以往的改進都是通過各種方法確定菱形算法的步長閾值，當(dāng)步長大于閾值時即直接退出，這種方法雖然明顯減少了編碼時間，但由于減少了搜索模板的搜索范圍，PSNR和碼率也會有一定程度的下降。本文從另外

4、的角度來改進菱形算法，即不設(shè)定某個確定的步長閾值作為提前終止的條件，而是根據(jù)運動搜索中最優(yōu)點是否多次沒有變化來作為提前終止的判斷條件。另外借鑒JM模型內(nèi)的UMHexagonS算法的思想，本文還引采用入了更多地預(yù)測矢量；引入基于SAD的提前終止策略。通過以上多種方法的結(jié)合，可以實現(xiàn)在PSNR和碼率幾乎不變的情況下，編碼時間減少20%左右。</p><p>　　關(guān)鍵詞：多試點視頻編碼，運動估計，JMVC，視差估計&l

5、t;/p><p><b>　　目 錄</b></p><p><b>　　（有）</b></p><p><b>　　摘　　要I</b></p><p>　　ABSTRACTII</p><p><b>　　目 錄1</b>&

6、lt;/p><p><b>　　一、緒 論2</b></p><p>　　（一） 課題研究的背景和意義2</p><p>　?。ǘ?多視點視頻編碼技術(shù)概況（以JMVC模型為例）2</p><p>　?。ㄈ?本文章節(jié)安排4</p><p>　　二、單視點視頻編碼技術(shù)簡介5</p>

7、;<p>　?。ㄒ唬?視頻編碼技術(shù)概況5</p><p>　?。ǘ?基于H.264標(biāo)準(zhǔn)的JM編碼器介紹6</p><p>　　三、JMVC代碼閱讀及編碼參數(shù)提取10</p><p>　?。ㄒ唬?JMVC代碼基本流程10</p><p>　　（二） 編碼參數(shù)的提取11</p><p>　?。ㄈ?/p>

8、） 編碼參數(shù)的顯示與分析13</p><p>　?。ㄋ模?本章小節(jié)19</p><p>　　四、各種運動算法的分析及比較21</p><p>　?。ㄒ唬?運動估計算法簡介21</p><p>　　（二） 運動算法比較平臺的搭建27</p><p>　?。ㄈ?各種運動估計算法實現(xiàn)和的性能分析27</p

9、><p>　　五、JMVC運動搜索算法改進38</p><p>　?。ㄒ唬?JMVC中的TZsearch算法38</p><p>　?。ǘ?改進方法38</p><p>　　（三） 改進效果39</p><p><b>　　六、結(jié)論42</b></p><p>&l

10、t;b>　　參考文獻43</b></p><p><b>　　后記44</b></p><p><b>　　附錄45</b></p><p><b>　　一、緒 論</b></p><p>　　本章首先介紹了本論文的選題背景及意義，然后介紹了單視點視頻編

11、碼和多視點視頻編碼的主要技術(shù)和研究現(xiàn)狀。</p><p>　　（一） 課題研究的背景和意義</p><p>　　多視點視頻是利用不同位置的攝像頭對同一場景進行拍攝得到的視頻數(shù)據(jù)，它包含了豐富的3D場景信息，可以為用戶提供傳統(tǒng)單視點視頻無法比擬的視覺感受。多視點視頻被廣泛應(yīng)用于3D電視、自由視點電視 (FreeViewPoint Television，F(xiàn)TV)、視頻會議、遠(yuǎn)程醫(yī)療和虛擬現(xiàn)實等

12、領(lǐng)域[1]。多視點視頻的數(shù)據(jù)量隨著視點個數(shù)的增多而成倍增加，為了解決其傳輸和存儲的問題，多視點視頻編碼 (MultiviewVideoCoding，MVC)對多視點視頻數(shù)據(jù)進行高效的壓縮。隨著新一代顯示設(shè)備的出現(xiàn)以及用戶對真實視覺感受的需求，MVC逐漸成為視頻編碼領(lǐng)域的研究熱點之一。</p><p>　　傳統(tǒng)的視頻編碼算法主要是利用了編碼信息在時間和空間上的相關(guān)性來降低計算量。而在MVC中，多個視點的視頻來源于

13、同一場景，它們除了在視頻內(nèi)容上相似之外，還在編碼信息上具有很強的相關(guān)性，因此MVC可以充分利用視點間編碼信息的相關(guān)性來加速編碼過程。</p><p>　　通過編碼參數(shù)顯示界面分析編碼器的性能，可以直觀的反映各個視點的碼率的大小、編碼時間的長短以及每一幀的各種類型宏塊的分布、運動矢量和視差矢量的分布。</p><p>　　從中可以找到編碼器需要改進的方面。比如編碼時間曲線顯示I幀編碼時間遠(yuǎn)遠(yuǎn)

14、小于B幀和P幀的編碼時間，而B、P幀與I幀的最主要不同就是進行了大量的運動估計，因此提高運動估計的效率是本文減少編碼時間的關(guān)鍵；另外通過視差矢量的分布可以發(fā)現(xiàn)視差矢量的水平位移遠(yuǎn)大于垂直位移，所以搜索最優(yōu)視差矢量時的水平位移范圍要遠(yuǎn)大于垂直位移范圍等等。</p><p>　　（二） 多視點視頻編碼技術(shù)概況（以JMVC模型為例）</p><p>　　JMVC模型的視點內(nèi)編碼部分與JM模型的架

15、構(gòu)幾乎完全相同。即幀內(nèi)預(yù)測部分、熵編碼部分的算法并沒有改變。所以并對JMVC的幀內(nèi)預(yù)測和熵編碼做單獨介紹。本小節(jié)只介紹JMVC和JM模型的主要不同。</p><p><b>　　預(yù)測結(jié)構(gòu)</b></p><p>　　由于JM模型模型面向單視點，所以預(yù)測結(jié)構(gòu)是簡單的IPBBIPBB........類型，其中B幀的數(shù)量可變，由于只有一個視點，所以GOP序列是一維的，只有在

16、時間方向上的延伸。但是JMVC由于引入了視點間預(yù)測，其預(yù)測結(jié)構(gòu)也必然發(fā)生改變。JMVC的預(yù)測結(jié)構(gòu)如下圖1.1所示</p><p>　　圖1.1 JMVC的預(yù)測結(jié)構(gòu)（該圖引自文獻[5]）</p><p>　　圖中總共有八個視點，每個視點的GOP長度均為8（編碼時GOP長度可以在配置文件中修改）。在時間方向上，該結(jié)構(gòu)采用了分層B幀結(jié)構(gòu)來提高時域預(yù)測效率;在視點方向上，該結(jié)構(gòu)使用了IBP預(yù)測結(jié)

17、構(gòu)來提高視點間預(yù)測效率。圖中T0時刻以及T8時刻各視點的幀只需要同時刻的參考幀就可以進行重建，將這些幀稱為錨定幀;圖中Tl時刻到T7時刻的幀需要其它時刻的參考幀才可以進行重建，將這些幀稱為非錨定幀。在時間方向上，錨定幀以及錨定幀和前一錨定幀之間的幀組成一個圖像組 (GOP)。視點S0只采用時間方向預(yù)測，稱為基本視點(Baseview)，可以直接用H.264解碼器進行解碼，實現(xiàn)向下兼容H.264功能的要求。非基本視點（non-basev

18、iew)可以采用視點間的預(yù)測?？梢栽诰幋a配置文件中設(shè)置視點的依賴關(guān)系（即編碼順序，比如途中的依賴關(guān)系就是0-2-1-4-3-6-5-7），某一視點的參考視點必須在該視點之前編碼。并且設(shè)定錨定幀和非錨定幀是否采用視點間預(yù)測。</p><p><b>　　參考幀</b></p><p>　　由于JMVC采用了視點間預(yù)測，所以必須將當(dāng)前時刻參考視點的圖像放入?yún)⒖紟斜碇?，?/p>

19、后對參考幀列表中的所有參考幀（包括同一視點和不同視點的）都進行運動搜索，在所有參考幀中得到一個最優(yōu)匹配塊，由于來自不同的視點，所以采用的運動估計算法最好有所區(qū)別，比如在不同視點參考幀中加入視差矢量作為預(yù)測矢量等。而JM模型的參考幀列表中的參考幀都是來源于單一視點，并無區(qū)別。</p><p><b>　　運動搜索算法</b></p><p>　　目前JM模型采用UMHe

20、xagonS （非對稱十字型多層次六邊形格點搜索算法）作為其快速搜索算法，而JMVC模型采用TZsearch算法作為其快速搜索算法。兩種算法的詳細(xì)說明及簡單比較見第三章。</p><p>　　（三） 本文章節(jié)安排</p><p>　　第一章介紹了課題研究的背景和意義，包括多視點視頻的應(yīng)用，以及多視點視頻編碼的主要技術(shù)和研究現(xiàn)狀。</p><p>　　第二章介紹了單視

21、點視頻編碼的主要技術(shù)和研究現(xiàn)狀，因為單視點編碼是多視點編碼技術(shù)的基礎(chǔ)，而且JM模型是非常成熟的編碼器，對JM代碼的研究可以為JMVC代碼的閱讀打下良好基礎(chǔ)</p><p>　　第三章利用JMVC編碼器對測試序列進行編碼，并將各種編碼參數(shù)通過ChartDirector庫以各種圖表的形式顯示出來。根據(jù)顯示的編碼參數(shù)對JMVC編碼器性能進行分析。</p><p>　　第四章分析各種運動估計算法并

22、對其進行比較，因為一般來說，運動估計是編碼器中復(fù)雜度和運算量最高的部分，而且JMVC運動估計所采用的TZsearch算法的運算復(fù)雜度非常高，速度特別慢，有較大提升空間。通過深入分析各種運動估計算法為優(yōu)化編碼器做基礎(chǔ)。</p><p>　　第五章對編碼器進行優(yōu)化，希望在幾乎不降低比特率和PSNR的基礎(chǔ)上加少編碼時間。主要方法有：新增預(yù)測矢量（同前一幀相同位置宏塊的MV、視差矢量）、 利用相鄰宏塊的Sad評價值作為T

23、Zsearch算法的提前退出閾值、用最優(yōu)預(yù)測適量連續(xù)三次不同步長的菱形搜索模板搜索后沒有改變這一條件作為鉆石搜索的提前終止條件等。實驗結(jié)果表明，在幾乎不降低碼率和PSNR的基礎(chǔ)上，改進后JMVC編碼器減少編碼時間20%~25%左右</p><p>　　二、單視點視頻編碼技術(shù)簡介</p><p>　　雖然多視點視頻編碼和傳統(tǒng)的單視點視頻編碼相比有較多不同，但是基本思想是一樣的，毫無疑問單視點

24、編碼是多視點編碼的基礎(chǔ)，全面了解單視點編碼技術(shù)對分析和改進多視點編碼器的性能有很大幫助。</p><p>　?。ㄒ唬?視頻編碼技術(shù)概況</p><p>　　原始視頻的數(shù)據(jù)量雖然巨大，但它們在時間、空間、以及統(tǒng)計上都存在大量的信息冗余。從20世紀(jì)中期以來，由于數(shù)據(jù)壓縮技術(shù)的發(fā)展和完善，極大的推動了視頻編碼技術(shù)的前進。一些經(jīng)典的視頻編碼技術(shù)隨之出現(xiàn)，主要技術(shù)分為以下幾個方面[2][3]:<

25、;/p><p><b>　　1.預(yù)測編碼</b></p><p>　　預(yù)測編碼是根據(jù)離散信號之間存在著一定關(guān)聯(lián)性的特點，利用前面一個或多個信號預(yù)測下一個信號進行，然后對實際值和預(yù)測值的差（預(yù)測誤差）進行編碼。如果預(yù)測比較準(zhǔn)確，誤差就會很小。在同等精度要求的條件下，就可以用比較少的比特進行編碼，達(dá)到壓縮數(shù)據(jù)的目的。</p><p>　　預(yù)測編碼指的是

26、利用像素的時間上或者空間上的相關(guān)性計算預(yù)測值，并對實際值和預(yù)測值之間的差值進行編碼，如果預(yù)測比較準(zhǔn)確，誤差就會很小，因此可以用較少的比特進行編碼。預(yù)測編碼按預(yù)測方法可以分為線性預(yù)測編碼和非線性預(yù)測編碼。線</p><p>　　性預(yù)測編碼由于算法簡單、易于硬件實現(xiàn)，在視頻編碼中更加常見。其中最為常見的線性預(yù)測編碼方法是差分脈沖編碼調(diào)制 (DiffereniialPulse CodeModulation，DPCM）。

27、預(yù)測編碼分為幀內(nèi)預(yù)測編碼和幀間預(yù)測編碼（按預(yù)測方向劃分）。幀內(nèi)預(yù)測編碼利用幀內(nèi)已預(yù)測像素的信息，幀間預(yù)測編碼利用時間上更早編碼的幀上的像素進行預(yù)測。通常情況下，視頻內(nèi)容變化和攝像頭運動都比較平緩，相鄰幀像素之間的相關(guān)性要比幀內(nèi)像素的相關(guān)性要大。因而幀間預(yù)測編碼的整體效率比幀內(nèi)預(yù)測編碼的效率要高。在幀間預(yù)測編碼中，每幀被分成若干個塊，每個塊到鄰近重建幀中搜索對應(yīng)的匹配塊，然后計算當(dāng)前塊和匹配塊在空間位置上的相對偏移量，最后對當(dāng)前塊和匹配塊

28、的殘差以及空間位置相對偏移量進行編碼。得到的相對偏移量稱為運動矢量，獲取運動矢量的整個過程稱為運動估計或運動搜索。</p><p><b>　　2.變換編碼</b></p><p>　　變換編碼指的是將原本的二維空間方向上的像素值通過變換映射到到另一個正交矢量空間中，然后對轉(zhuǎn)換后的系數(shù)進行量化和編碼。在目前視頻編碼標(biāo)準(zhǔn)中，最為常見的就是離散余弦變換 (Discret

29、ecosineTransform，DCT)。雖然DCT算法復(fù)雜度較高，但隨著一些針對DCT的快速算法（FFT）的提出，DCT很快被各種視頻編碼標(biāo)準(zhǔn)所采用。在每幀圖像在經(jīng)過幀內(nèi)和幀間預(yù)測之后，得到的殘差數(shù)據(jù)的數(shù)值已經(jīng)較小，但這些殘差數(shù)據(jù)之間仍然存在很強的相關(guān)性。使用DCT變換可以將殘差數(shù)據(jù)從空間域變換到頻域，大多數(shù)能量都集中在低頻部分，量化之后可以有效的解除殘差系數(shù)之間的相關(guān)性，以達(dá)到數(shù)據(jù)壓縮的目的。</p><p&g

30、t;<b>　　3.嫡編碼</b></p><p>　　嫡編碼的原理是利用信源的統(tǒng)計特性對數(shù)據(jù)進行壓縮，它是一種無損壓縮編碼技術(shù)。</p><p>　　常用的嫡編碼有霍夫曼編碼、算術(shù)編碼和游程編碼?；舴蚵幋a是根據(jù)變字長編碼 (variableLengtnCode，VLC)理論設(shè)計，它被廣泛用于視頻編碼標(biāo)準(zhǔn)?；舴蚵幋a根據(jù)輸入符號的統(tǒng)計概率大小分配不同長短的碼字，使

31、用的時候需要相應(yīng)的碼表。算術(shù)編碼較霍夫曼編碼復(fù)雜，但不需要為一個符號單獨設(shè)定碼字，也不需要在通信過程中傳送碼表。當(dāng)信源各信息符號的概率分布不能確定的時候，適合于用算術(shù)編碼。H.264/AVC視頻標(biāo)準(zhǔn)就將算術(shù)編碼作為一種可選的嫡編碼方法。游程編碼也稱行程編碼，是用一個符號值替代具有相同值的連續(xù)符號，以減少符號的長度。在靜止圖像壓縮標(biāo)準(zhǔn)中，游程編碼經(jīng)常被用來壓縮數(shù)據(jù);在視頻編碼標(biāo)準(zhǔn)中，游程編碼與霍夫曼編碼相結(jié)合用于對DCT系數(shù)量化后的稀疏矩

32、陣進行編碼。目前絕大部分視頻編碼器的設(shè)計都是以上述經(jīng)典視頻編碼技術(shù)為基礎(chǔ)。</p><p>　?。ǘ?基于H.264標(biāo)準(zhǔn)的JM編碼器介紹</p><p>　　H.264（JM是其標(biāo)準(zhǔn)模型）是目前使用最為廣泛的單視點視頻編碼標(biāo)準(zhǔn)，H.264采用了傳統(tǒng)基于預(yù)測和變換的混合視頻編碼架構(gòu)。與以往視頻編碼標(biāo)準(zhǔn)類似，H.264采用幀間預(yù)測技術(shù)來消除時域上視頻幀間的相關(guān)性，采用幀內(nèi)預(yù)測和變換編碼技術(shù)來

33、消除空間域上視頻數(shù)據(jù)的相關(guān)性，采用嫡編碼技術(shù)來消除統(tǒng)計域上量化系數(shù)的相關(guān)性。但H.264標(biāo)準(zhǔn)為了提高編碼效率，采用了更為細(xì)致的宏塊劃分，更為精細(xì)的運動估計，更多的參考幀，并引入了去塊效益濾波器等先進技術(shù)。其編碼框架如圖2.1。</p><p>　　基本流程為：編碼器以宏塊為單位對輸入圖像（假設(shè)當(dāng)前幀為P幀）進行編碼，當(dāng)前宏塊先進行預(yù)測模式的選擇，便利幀內(nèi)、真間各種預(yù)測模式后，選擇RdCost最低的模式作為當(dāng)前模式

34、，計算當(dāng)前宏塊和參考宏塊的差值（殘差塊）并對其進行變換、量化、編碼（如果為Direct模式，則不對殘差快進行編碼），然后形成編碼碼流進行存儲或者傳輸。另外，量化后的殘差塊經(jīng)過反量化、反變換（如果為幀間預(yù)測模式還要經(jīng)過去塊效應(yīng)濾波）后，產(chǎn)生重建圖像，以用于后續(xù)幀的預(yù)測以及PSNR的計算。</p><p>　　圖2.1 H264編碼框架（該圖引自文獻[6]）</p><p><b&

35、gt;　　(1)幀間預(yù)測</b></p><p>　　幀間預(yù)測是一種充分利用視頻數(shù)據(jù)的時域相關(guān)性來去除時域冗余的編碼方法，它是提高視頻編碼壓縮效率的關(guān)鍵技術(shù)[4]。H.264中的幀間預(yù)測仍然是利用已編碼幀和基于塊運動補償?shù)念A(yù)測模式，但與以往的視頻標(biāo)準(zhǔn)相比，引入了更為精細(xì)的塊劃分模式，更高像素精度的運動矢量以及多參考幀幀間預(yù)測。如圖2.2所示，每個亮度宏塊有4種分塊方式:16xl6，16x8，8x16和

36、8x8，并且8x8塊可以進一步劃分成3種子塊:8x4，4x8和4x4，因此總共有7種分塊方式。</p><p>　　在運動估計的時候，每個宏塊可以有不同大小的子塊，并且每個子塊具有單獨的運動矢量，因此可以更為精確的描述宏塊內(nèi)部的運動狀態(tài)，從而降低整個宏塊的預(yù)測殘差。色度塊的劃分模式和亮度塊相同，只是色度塊的分辨率是亮度塊的一半，因此色度塊可以劃分為:8x8，8x4，4x8，4x4，4x2，2x4和2x2等7種子塊

37、，它們相應(yīng)的運動矢量也是亮度塊的一半。不同的宏塊劃分適應(yīng)于不同的圖像內(nèi)容，對于圖像細(xì)節(jié)豐富的區(qū)域，一般有較為精細(xì)的的宏塊劃分，對于平坦區(qū)域，宏塊劃分一般為16x16等較大的塊。</p><p>　　H.264中亮度塊運動矢量采用了1/4像素精度，色度塊運動矢量的采用了1/8像素精度。而之前的視頻編碼標(biāo)準(zhǔn)(H.263和MPEG一4)亮度塊運算矢量只采用半像素精度，色度塊運動矢量只采用1/4像素精度。由于H.264采

38、用了更高精度的運動矢量，因此可以提供更為精細(xì)的運動補償，補償之后得到的殘差也更小。另外在1/2像素和1/4像素進行插值的過程中，H.264采用了6階有限脈沖響應(yīng)濾波器，可以有效改善運動補償?shù)男阅?。H.264除了采用以上精細(xì)塊劃分和更高精度運動矢量之外，還支持多參考幀預(yù)測。運動估計不再局限于前一幀或后一幀，可以在選擇前向或后向多個不同參考幀中進行搜索，從而提高運動估計的準(zhǔn)確性。</p><p>　　圖2.2 宏

39、塊劃分方式（該圖引自文獻[5]）</p><p><b>　　(2)幀內(nèi)預(yù)測</b></p><p>　　在之前的視頻編碼標(biāo)準(zhǔn)中，宏塊進行幀內(nèi)編碼的時候，都是直接對其原始像素進行DCT變換，沒有考慮空間上的相關(guān)性進行幀內(nèi)預(yù)測，整體壓縮效果不是太好。為了提高幀內(nèi)編碼效率，H.264引入了幀內(nèi)預(yù)測編碼。它利用了當(dāng)前宏塊周圍已重建的像素值從空間方向預(yù)測對當(dāng)前宏塊的像素值，可

40、以很好的降低像素值的相關(guān)性[5]。H.264中亮度塊可以分16x16塊和4x4塊兩類大小的塊進行幀內(nèi)預(yù)測。16xl6亮度塊有4種預(yù)測模式:垂直預(yù)測，水平預(yù)測，DC預(yù)測和平面預(yù)測，它適合于對圖像中平坦區(qū)域進行預(yù)測。4x4亮度塊具有9種預(yù)測模式:垂直預(yù)測、水平預(yù)測、DC預(yù)測、下左對角線預(yù)測、下右對角線預(yù)測、右垂直預(yù)測、下水平水平、左垂直預(yù)測、上水平預(yù)測[4]。4x4亮度塊預(yù)測模式更為精細(xì)，適合于對圖像中紋理豐富區(qū)域進行預(yù)測。</p&g

41、t;<p><b>　　(3)熵編碼</b></p><p>　　H.264使用了三種熵編碼方法:基于上下文的自適應(yīng)變長編碼 (CAVLC）、基于上下文的自適應(yīng)二進制算術(shù)編碼 (CABAC)、以及指數(shù)哥倫布(ExP一Golomb)編碼。對slice</p><p>　　層以上的數(shù)據(jù)編碼采用指數(shù)哥倫布編碼、對于殘差數(shù)據(jù)編碼采用CAVLC或CABAC。由于

42、本文只是對運動估計算法進行研究改進，并沒有深入研究熵編碼有關(guān)內(nèi)容，所以只是簡單介紹，詳細(xì)內(nèi)容請參考文獻[4]。</p><p>　　三、JMVC代碼閱讀及編碼參數(shù)提取</p><p>　　本章在仔細(xì)閱讀JMVC代碼的基礎(chǔ)上，對其進行修改，使編碼器進行編碼的同時將各種編碼參數(shù)輸入到參數(shù)文件中，并利用MFC界面顯示編碼參數(shù)。</p><p>　　以往的參數(shù)分析軟件，主要

43、是利用基于節(jié)點的樹進行參數(shù)的顯示。比如單擊某一節(jié)點，就可以顯示某一幀的大小、PSNR、各種類型的宏塊個數(shù)等參數(shù)信息。這種界面雖然易于實現(xiàn)，但是并不直觀，很難一眼看出不同幀之間各個參數(shù)有那些不同——因為這需要分別單擊兩個幀的節(jié)點，記錄里面的各種數(shù)據(jù)并進行比較。</p><p>　　本文通過ChartDirector庫，把以幀為單位的參數(shù)放入圖表之中，進行非常直觀的顯示，對于以宏塊為單位的參數(shù)，也不是僅僅向傳統(tǒng)軟件哪

44、樣只是提取宏塊類型的統(tǒng)計、運動矢量的均值，或者需要打開許多級節(jié)點之后才能找到某一宏塊的運動矢量——本文利用opencv庫，將重建圖像(YUV文件)中我們指定需要詳細(xì)顯示宏塊參數(shù)的某一幀顯示在MFC的Picture控件上，然后在該Picture控件上繪制各種宏塊信息，比如運動矢量。宏塊劃分等。</p><p>　　通過上文所述的方法，可以將出了SPS、PPS之外的所有信息非常直觀的顯示在界面上。</p>

45、<p>　　（一） JMVC代碼基本流程</p><p>　　JMVC基本流程圖如圖3.1所示</p><p>　　圖3.1 JMVC流程圖（該圖來自網(wǎng)絡(luò)）</p><p>　　其中H264AVCEncoderTest.cpp中的init函數(shù)主要作用是讀取配置文件encoderMVC.cfg的參數(shù)。然后開始對序列進行處理。PicEncoder.cpp

46、中的init函數(shù)是初始化參數(shù)序列集和圖像序列集以及編碼所需緩沖區(qū)等。[6]</p><p>　　然后遍歷所有的圖像幀，對每幀調(diào)用picEncode.cpp中的process處理函數(shù)，該process函數(shù)調(diào)用xEncodePicture函數(shù)對圖像進行編碼。在xEncodePicture函數(shù)中，將圖像幀分為片組，對每個片進行編碼。片再分為宏塊，宏塊為編碼的最小單位，接下來就根據(jù)宏塊的類型采取遍歷各種編碼方式，根據(jù)Rd

47、Cost選擇最優(yōu)的模式作為最終模式。</p><p>　?。ǘ?編碼參數(shù)的提取</p><p><b>　?。?）以幀為單位</b></p><p>　　將編碼序列的每一幀的類型、PSNR、編碼時間、編碼后大小等參數(shù)提取出來并進行顯示。</p><p>　　通過閱讀調(diào)試代碼可以知道，存儲以上參數(shù)的變量分別為：<

48、/p><p>　　幀類型 rcSliceHeader.getSliceType ()</p><p>　　PSNR xGetPSNR( rcRecPicBufUnit, dPSNR )</p><p>　　所需比特數(shù) uiBits</p><p>　　編碼時間 自定

49、義time_t類型變量獲取</p><p>　　修改JMVC代碼的PicEncoder.cpp文件，在編碼每幀圖像結(jié)束后添加寫文件函數(shù)，使得每當(dāng)編碼完一幀，就將上述參數(shù)寫入文件。</p><p>　　一開始的寫入文件格式非常簡單，按照自己定義的寫入順序，各個數(shù)據(jù)以空格為分割符，第一個數(shù)據(jù)為第一幀幀類型，第二、三個數(shù)據(jù)分別為該幀的編碼和解碼順序........第七個參數(shù)為編碼時間、第八個參數(shù)

50、為下一幀的幀類型。</p><p>　　這種方法實現(xiàn)起來非常簡單，讀取編碼參數(shù)文件時也非常方便，但是得到的編碼參數(shù)文件非常不方便閱讀，而且如果手動打開文件觀察參數(shù)時誤刪了某條數(shù)據(jù)，讀取時不但該數(shù)據(jù)丟失，之后的數(shù)據(jù)也會由于錯位而造成讀取錯位，這種錯誤擴散會一直持續(xù)到文件結(jié)尾。</p><p>　　為了使得寫入編碼參數(shù)的文件方便閱讀，避免讀取文件時的錯誤擴散，本文采用各幀參數(shù)用分隔符隔開、并且

51、參數(shù)前都加入?yún)?shù)名稱的方法標(biāo)識參數(shù)類型，防止錯誤的發(fā)生且易于閱讀。</p><p>　　得到的文件內(nèi)容如下頁圖3.2所示</p><p>　　圖3.2 幀編碼參數(shù)文件內(nèi)容（部分）</p><p><b>　　以宏塊為單位</b></p><p>　　將每一幀的各個宏塊信息如宏塊坐標(biāo)、宏塊類型 、宏塊劃分 、 參考宏

52、塊等信息進行提取并顯示。</p><p>　　通過閱讀調(diào)試代碼可以知道，存儲以上參數(shù)的變量分別為：</p><p>　　宏塊位置：rcMbDataAccess.m_uiPosX</p><p>　　rcMbDataAccess.m_uiPosY</p><p>　　宏塊類型：rcMbDataAccess.m_rcMbCurr.getMbMod

53、e()</p><p>　　宏塊劃分：rcMbDataAccess.m_rcMbCurr.getBlkMode()</p><p>　　參考宏塊：rcMbDataAccess.m_rcMbCurr.getMbMotionData().m_ascRefIdx[0]</p><p>　　運動矢量：rcMbDataAccess.m_rcMbCurr .getMbMotio

54、nData().getMv()</p><p>　　修改JMVC代碼，使得每當(dāng)編碼完一個宏塊，就將上述參數(shù)寫入文件。得到的文件內(nèi)容如圖3.3所示</p><p>　　圖3.3 宏塊編碼參數(shù)文件按內(nèi)容（部分） </p><p>　　編碼參數(shù)的顯示與分析</p><p>　　利用MFC程序和ChartDirect庫對獲取的編碼參數(shù)進行處理和

55、顯示。大致流程如下圖3.4：</p><p>　　圖3.4 MFC顯示界面流程圖</p><p>　　以ballroom測試序列為例，將其的前三個視點進行編碼并提取編碼參數(shù)，然后通過界面進行顯示，可以得到效果圖如下：</p><p>　　圖2.5-1 圖2.5-2</p>

56、;<p>　　圖3.5-1 ：幀編碼參數(shù)之碼率效果圖 </p><p>　　圖3.5-2 ： 幀編碼參數(shù)之編碼時間效果圖 </p><p>　　圖3.5-3 ： 幀編碼參數(shù)之PSNR效果圖</p><p>　　圖2.5-3 </p><p>　　由圖3

57、.5可以看到 ：</p><p>　　視點0作為基本視點，碼率最高，PSNR也最高，編碼時間也最長。</p><p>　　視點2由視點0預(yù)測得到，所以碼率減少，PSNR略微降低，但是編碼時間顯著增長。</p><p>　　視點1由視點0和視點2雙向預(yù)測得到，碼率最小，說明去除了更多的冗余，編碼時間和PSNR和視點2沒有太過明顯的差別。</p><

58、p>　　從三個十點的整體趨勢來看，每個序列的錨定幀所需編碼時間明顯小于非錨定幀，碼率和PSNR明顯高于非錨定幀。而通過后面分析可以發(fā)現(xiàn)錨定幀和非錨定幀的主要區(qū)別在于幀內(nèi)編碼宏塊的有無，也就是說，如果僅僅進行幀內(nèi)預(yù)測，編碼時間會減少很多。從另一角度來說，這證明幀間預(yù)測的耗時非常巨大。 </p><p>　　圖3.6 宏塊類型統(tǒng)計</p><p>　　左上：視點0 第0幀 宏塊

59、類型統(tǒng)計</p><p>　　右上：視點0 第10幀 宏塊類型統(tǒng)計</p><p>　　左下：視點1 第0幀 宏塊類型統(tǒng)計</p><p>　　右下：視點1 第10幀 宏塊類型統(tǒng)計</p><p>　　由圖3.6可以看出：</p><p>　　I幀（視點0 第0幀）宏塊類型多為INTRA16，INTRA8和I

60、NTRA4 即幀內(nèi)4x4 幀內(nèi)8x8 幀內(nèi)16x16，因為I幀僅采用幀內(nèi)預(yù)測模式，所以不可能出現(xiàn)INTER16x16等模式</p><p>　　P幀（視點1 第0幀）大多數(shù)為幀間模式如幀間16x16，幀間8x8，SKIP等，少數(shù)為幀內(nèi)模式宏塊</p><p>　　B幀（視點0 第10幀以及視點1 第10幀）幾乎全部為幀間預(yù)測宏塊。在不是I幀的情況下，大多數(shù)宏塊為SKIP模式。<

61、/p><p>　　通過宏塊統(tǒng)計分布圖和編碼時間圖，可以更清晰地發(fā)現(xiàn)，幀內(nèi)預(yù)測宏塊較多時，編碼時間就較短，幀間宏塊較多時，編碼時間飛速增長。</p><p>　　圖3.7-1 視點0 第0幀宏塊預(yù)測類型分布 圖3.7-2 視點0 第7幀宏塊預(yù)測類型分布</p><p>　　圖3.7-3 視點1 第0幀 宏塊預(yù)測類型分布 圖3.7-4 視點1 第7幀宏塊預(yù)測類

62、型分布</p><p>　　紫色：幀內(nèi)預(yù)測宏塊 綠色：視點間預(yù)測宏塊 黃色：幀間預(yù)測宏塊</p><p>　　由圖3.7可以看出各種預(yù)測類型的分布</p><p>　　對于基本視點，沒有視點間預(yù)測，它的錨定幀必然是I幀，只有幀內(nèi)預(yù)測，所以全為紫色，如圖3.7-1，它的非錨定幀絕大多數(shù)采用幀間預(yù)測（黃色），極少數(shù)采用幀內(nèi)預(yù)測（紫色），如圖3.7-2所示。</

63、p><p>　　對于非基本視點，它的錨定幀需要其它視點相同時刻的圖像作為參考幀，所以不止由幀內(nèi)預(yù)測（紫色），還有視點間預(yù)測（綠色），而且視點間預(yù)測占大多數(shù)。如圖3.7-3所示，對于非錨定幀，三種預(yù)測方式均由可能，而實驗證明，非基本視點的非錨定幀中視點內(nèi)幀間預(yù)測宏塊的數(shù)量最多，視點間的其次，幀內(nèi)預(yù)測的宏塊最少。</p><p>　　圖3.8-1 視點0 第0幀 宏塊劃分

64、 圖3.8-2 視點0 第25幀 宏塊劃分 </p><p>　　圖3.8-3 視點2 第0幀 宏塊劃分 圖3.8-1 視點2 第5幀 宏塊劃分</p><p>　　由圖3.8可以看出，I幀（視點0，第0幀圖3.8-1、視點0，第25幀圖2.8-2）幀內(nèi)預(yù)測宏塊較多，INTRA4x4 和INTRA8x8宏塊較多，劃分比較精細(xì)，</p><

65、;p>　　而P幀（視點2，第0幀圖2.8-3）和B幀（視點2，第5幀圖2.8-4）大多采用幀間或者視點間預(yù)測，多數(shù)宏塊劃分為INTER16x16類型。</p><p>　　圖 3.9-1 視點0 第20幀 運動矢量分布 圖3.9-2 視點0 第30幀 運動矢量分布</p><p>　　圖 3.9-3 視點1 第0幀 運動矢量分布 圖 3.9-4 視點2

66、 第0幀 運動矢量分布 </p><p>　　由圖3.9-1、3.9-2可以看出， 當(dāng)僅采用視點內(nèi)幀間預(yù)測時，非零的運動矢量所占比例較少且集中在運動物體附近，大面積的背景部分運動矢量為0（上圖中不顯示運動矢量有兩種情況：運動矢量為0或者沒有運動矢量，即采用幀內(nèi)預(yù)測。 但是參考圖3.7-2可知 視點0的B幀絕大多數(shù)采用幀間預(yù)測，只有極少宏塊采用幀內(nèi)預(yù)測，所以對于視點0來說不顯示運動矢量可以大致等價于運動矢量為0）。

67、</p><p>　　而觀察圖3.9-3和3.9-4可以發(fā)現(xiàn)，當(dāng)采用視點間預(yù)測時大多數(shù)宏塊都有一個非零的運動矢量，并且在一定范圍內(nèi)具有各個宏塊的運動矢量具有一致性。圖下圖所示</p><p>　　圖3.10 運動矢量的一致性示意圖</p><p>　　因此可以考慮把這些運動矢量統(tǒng)一趨向的值作為一個新的運動矢量預(yù)測值，在運動搜索過程中，在把左、上、右上方的宏塊作

68、為運動矢量預(yù)測值計算SAD之后，再把這個統(tǒng)一趨向的值作為運動矢量預(yù)測值計算SAD，然后選取SAD最小的點作為運動搜索的起始點。通過這種方法可以提高運動搜索的準(zhǔn)確度并縮短運動搜索時間，具體效果見第四章。</p><p><b>　　本章小節(jié)</b></p><p>　　本章主要實現(xiàn)了對編碼器參數(shù)的提取與顯示，通過對編碼參數(shù)的分析，可以發(fā)現(xiàn)許多可以改進的方面。例如：<

69、;/p><p>　　編碼時間曲線顯示I幀編碼時間遠(yuǎn)遠(yuǎn)小于B幀和P幀的編碼時間，而B、P幀與I幀的最主要不同就是進行了大量的運動估計，因此提高運動估計的效率是本文減少編碼時間的關(guān)鍵；</p><p>　　通過視差矢量的分布可以發(fā)現(xiàn)視差矢量的水平位移遠(yuǎn)大于垂直位移，所以搜索最優(yōu)視差矢量時的水平位移范圍要遠(yuǎn)大于垂直位移范圍；</p><p>　　通過運動矢量的分布以及宏塊類型

70、的分布可以發(fā)現(xiàn)，P幀和B幀的絕大多數(shù)宏塊都是采用幀間預(yù)測模式，但是可以畫出運動矢量的宏塊較少，這說明采用幀間預(yù)測的宏塊有一大部分的運動矢量為0，因此JMVC把零運動矢量作為預(yù)測矢量之一；</p><p>　　觀察相鄰兩個編碼幀的運動矢量分布可以發(fā)現(xiàn)他們具有一定的相似性，因此可以考慮把前一幀的相同位置的運動矢量也作為預(yù)測矢量。</p><p>　　總而言之，通過觀察編碼參數(shù)，可以得到JMVC

71、編碼器的許多方面性能和特點，這為以后對JMVC的改進提供了依據(jù)。</p><p>　　四、各種運動算法的分析及比較</p><p>　　由之前的分析可知，減少視頻序列編碼時間的關(guān)鍵在于減少P、B幀的編碼時間，</p><p>　　而減少P、B幀編碼時間的關(guān)鍵則在于使用高效的運動估計算法。因此為了改進JMVC中的TZsearch算法，本章對各種基本的運動估計算法如三步

72、法、四步法、菱形算法以及一些提高運動估計效率的常用方法如提前終止策略、增加預(yù)測矢量等進行了C++程序上的實現(xiàn)，以及性能的比較，為第5章改進JMVC的算法做準(zhǔn)備。</p><p>　?。ㄒ唬?運動估計算法簡介</p><p>　　運動估計的基本思想是將圖像序列的每一幀分成許多互不重疊的宏塊，并認(rèn)為宏塊內(nèi)所有象素的位移量都相同，然后對每個宏塊到參考幀某一給定特定搜索范圍內(nèi)根據(jù)一定的匹配準(zhǔn)則找出

73、與當(dāng)前塊最相似的塊，即匹配塊，匹配塊與當(dāng)前塊的相對位移即為運動矢量。視頻壓縮的時候，只需保存運動矢量和殘差數(shù)據(jù)就可以恢復(fù)出當(dāng)前塊。</p><p>　　由于編碼時需要對殘差塊進行量化，所以通過運動搜索所找尋的匹配塊與原始塊相越小，量化噪聲就越小，重建圖像的質(zhì)量也越高。</p><p><b>　　1.全搜索算法</b></p><p>　　全搜

74、索算法FS(Full Search)是一種窮盡式的搜索算法，對給定搜索范圍內(nèi)所有的可能點都計算一次SAD值，從中找到最小值，該宏塊即為匹配宏塊[9]。全搜索算法的特點是一定能得到全局最優(yōu)的運動矢量，但最耗時間巨大。以搜索范圍為129x129為例，每一個宏塊要找到其最佳匹配塊，就要計算129x129=16641次原始宏塊和參考宏塊的SAD值，耗時極為漫長。</p><p><b>　　快速搜索算法<

75、/b></p><p>　　因為全搜索耗時非常漫長，很多運動估計的快速算法從降低計算復(fù)雜度和降低搜索點數(shù)等方面進行了改進來減少編碼時間?？焖偎阉魉惴ù蠖鄶?shù)都基于這樣一個假設(shè)：在搜索范圍內(nèi)有且只有一個最優(yōu)點（谷點），以該點作為運動矢量所得的SAD最小，并且距離改點越遠(yuǎn)，SAD值越大[5]。在這種假設(shè)下SAD與運動矢量的關(guān)系如圖4.1所示。</p><p>　　圖4.1 理想情況下的

76、SAD與運動矢量的關(guān)系圖</p><p>　　在這種假設(shè)下，多種運動算法被提出，例如三步法、四步法、菱形搜索算法等。</p><p>　　但是這些算法雖然加快了運動搜索的速度，其準(zhǔn)確度也有了一定程度的下降。原因就在于實際情況下的SAD與運動矢量的關(guān)系并沒有圖4.1所示的那么理想。以ballroom測試序列第2視點第0幀為例（其參考幀為第0視點第一幀）。對所有宏塊都做全搜索，并將每個宏塊的搜

77、索范圍內(nèi)的所有SAD值都輸入到參數(shù)文件中，然后利用ChartDirector庫進行顯示?？梢缘玫饺缦氯S圖表：</p><p>　　圖4.2-1 宏塊（21，15）的SAD與運動矢量關(guān)系圖</p><p>　　圖4.2-2 宏塊（21，17）的SAD與運動矢量關(guān)系圖</p><p>　　圖4.2-3 宏塊（21，18）的SAD與運動矢量關(guān)系圖</p>

78、<p>　　圖4.2-4 宏塊（21，22）的SAD與運動矢量關(guān)系圖</p><p>　　圖4.2-5 宏塊（22，5）的SAD與運動矢量關(guān)系圖</p><p>　　由圖4.2可以看出，SAD與運動矢量的關(guān)系并不是理想情況，每一個宏塊的SAD分布都有很多“谷點”，快速搜索可以找到這些“谷點”中的其中一個，但是不能保證該“谷點”是所有谷點中的最低點。所以快速搜索算法的準(zhǔn)確度比全局搜

79、索算法有一定程度的下降。具體性能比較見本章第三節(jié)</p><p><b>　　三步法</b></p><p>　　在快速運動估計算法中，三步法的應(yīng)用十分廣泛。三步法在搜索過程中，每次對中心點及其相鄰的八個點進行計算。起始搜索距離為最大搜索距離的一半。在每一步搜索中搜索距離減半，在最大搜索距離為8時，只需要三步就可得到運動矢量，因此稱之為三步法[6]。對于現(xiàn)在分辨率較高

80、的圖像，搜索步數(shù)實際會遠(yuǎn)超過三步。如圖4.3所示，當(dāng)搜索距離為8時，以SAD為匹配準(zhǔn)則。第一步，收搜索點的搜索距離為4，假設(shè)a點SAD值最?。坏诙綍r，搜索距離則減半為2，周圍8個測試點與中心a點比較，其中b點SAD值最?。坏谌綍r，搜索距離再次減半為1，比較結(jié)果C點SAD值最小，則C點對應(yīng)的運動矢量即為最佳運動矢量[6]。由于三步法旳運算時間明顯減少，很多情況加均可以得到較為理想的運動矢量，因此應(yīng)用十分廣泛。其性能分析見本章第三節(jié)。&

81、lt;/p><p>　　圖4..3 三步法步驟示意圖（該圖引自文獻[6]）</p><p><b>　　四步法</b></p><p>　　四步法反復(fù)使用5*5模板進行搜索 直到模板中心出誤差最小或者到達(dá)搜索邊界 ，然后再用3*3小模板進行一次精細(xì)搜索具體步驟如圖4.4所示，其性能分析見本章第三節(jié)。</p><p>　　圖

82、4.4 四步法 步驟示意圖（該圖引自文獻[5]）</p><p><b>　　菱形搜索算法</b></p><p>　　菱形搜索法采用的是非矩形搜索模板，在搜索過程中，所選用搜索模板的形狀影響整個搜索算法的速度和性能[13]。在進行塊匹配的過程中，利用誤差匹配函數(shù)確定誤差最小點，這個誤差函數(shù)全局最小點就是最有運動矢量。在全搜索過程中，對所有點進行遍歷測試，通過誤差

83、函數(shù)可以找到全局最小點。但是在快速搜索算法中，并不是對所有測試點進行遍歷測試，如果搜索窗口選擇的過小就會，在搜索過程中就容易陷入局部最小點；如果搜索窗口過大，在搜索過程中就容易錯過全局最小點。因此，在菱形搜索算法中，采用了擁有9個測試點的大菱形模板和擁有5個測試點的小菱形模板，如圖3.5所示。根據(jù)不同情況分別利用者兩種模板進行快速運動估計。在搜索過程中，先采用大菱形模板進行搜索計算，當(dāng)最小誤差點出現(xiàn)在中心點時，再采用小菱形模板進行下一步

84、匹配計算，這是5個測試點中誤差最小點即為最佳匹配點。</p><p>　　圖4.5 大小菱形搜索模板（該圖引自文獻[6]）</p><p>　　菱形搜索法具體搜索步驟如圖4.6所示。首先，在給定的搜索范圍內(nèi)，采用大菱形搜索模板對中心點己經(jīng)周圍8個點進行測試計算，如果最小誤差點出現(xiàn)在大菱形模板中心，則采用小菱形模板繼續(xù)搜索。小菱形模板進行搜索時，以前面得到的最小誤差點為中心，按小菱形模板對

85、所有測試點進行計算，得到的誤差最小點即為最佳匹配點。在采用大菱形模板搜索時，如果誤差最小點不在大菱形模板的中心點是，則以該誤差最小點為中心點，繼續(xù)采用大菱形模板進行搜索，知道最小誤差點出現(xiàn)在大菱形模板中心點位置時，改用小菱形模板，得到最佳匹配點。該點所在位置多對應(yīng)的矢量即為最佳運動矢量。</p><p>　　另外，為了提高菱形法的性能，可以采用更大的搜索模板,JMVC的TZsearch算法就采用了步長從一到六十四

86、的73點菱形搜索模板。其性能分析見本章第三節(jié)。</p><p>　　圖4.6 菱形法 步驟示意圖（該圖引自文獻[6]）</p><p>　?。ǘ?運動算法比較平臺的搭建</p><p>　　本章主要對各種經(jīng)典的運動估計算法（如三步法、四步法、菱形搜索算法、非對稱十字型多層次六邊形格點搜索算法）進行粗略實現(xiàn)并進行比較。由于如果將各種算法直接放入編碼器中運行并進行比

87、較的話要花費巨大的時間，所以本文設(shè)計了一個可以快速驗證運動算法性能的小程序。程序流程圖如下</p><p>　　圖 3.7 運動搜索算法性能分析程序流程圖</p><p>　　該程序僅實現(xiàn)了編碼器的運動估計部分，并沒有實現(xiàn)運動補償、變換、量化、和熵編碼。但是該程序輸出的COST（計算宏塊SAD的函數(shù)被調(diào)用的次數(shù)，即搜索的點數(shù)）和PSNR（原始圖像和直接根據(jù)運動矢量和參考幀（而未經(jīng)運動

88、補償）重建的圖像的峰值信噪比）可以較好的反應(yīng)運動估計算法的性能——COST越少，說明運動搜索算法計算SAD的次數(shù)越少，復(fù)雜度越低，耗費的時間越少；PSNR越高，運動搜索的準(zhǔn)確度越高。 而運動搜索算法的復(fù)雜度和準(zhǔn)確度恰恰可以較好的反映編碼器的性能，所以利用該軟件比較編碼器的性能可行的。</p><p>　?。ㄈ?各種運動估計算法實現(xiàn)和的性能分析</p><p>　　1. 三步法、四步法、菱

89、形算法的實現(xiàn)和比較</p><p>　　本小節(jié)對以上三種算法進行了實現(xiàn)，考慮到TZsearch算法中菱形模板的點數(shù)不止是9點大模板和5點小模板，所以菱形算法中又分為9點、17點、25點、41點、57點、73點6種。</p><p>　　分別以ballroom、exit、vassar測試序列的第0視點前100幀作為測試對象，利用第二節(jié)介紹的運動算法分析平臺，可以得到以下數(shù)據(jù) 圖

90、4.8-1不同運動搜索方法的代價（ballroom） 圖4.8-2不同運動搜索方法的代價（exit）</p><p>　　圖4.8-3 不同運動搜索方法的代價（vassar）</p><p>　　由以上數(shù)據(jù)可以看到，全搜索算法所需的計算SAD的次數(shù)最多，耗時也就最長，三步法、四步法、菱形算法相對與全搜索算法在復(fù)雜度上有很大的簡化。</p><p>　　圖

91、4.9 不同運動搜索方法的PSNR</p><p>　　由圖4.9可以看出，在大多數(shù)情況下（ballroom序列所有幀，exit序列所有幀，vassar序列后半部分）全搜索算法的PSNR都高于快速搜索算法，只有少數(shù)情況于快速搜索算法的PSNR幾乎相同，通過YUV播放器播放vassar序列可以發(fā)現(xiàn)，PSNR幾乎相同的地方畫面差不多是靜止的，幾乎沒有運動。所以可以說，畫面只要有明顯的運動發(fā)生，全搜索得出的PSNR要高

92、于快速搜索得出的PSNR。</p><p>　　圖4.10 不同運動搜索方法的PSNR-COST關(guān)系圖</p><p>　　由圖4.10可以看出對于ballromm序列和exit序列，三步法、四步法、9點菱形算法沒有太明顯的區(qū)別，但是隨著菱形算法點數(shù)的增加，在計算復(fù)雜度（COST）的增加可以容忍的范圍內(nèi)，PSNR有了明顯的提升。這也就解釋了TZsearch采用的菱形算法模板的點數(shù)遠(yuǎn)多于9點

93、很多的原因。</p><p>　　而vassar序列的提升并不明顯，這是因為vassar序列的運動很不明顯，利用三步法等較簡單算法已經(jīng)可以得到很好的效果，PSNR沒有更大的提升空間。因此可以考慮通過判斷相鄰宏塊平均運動矢量的大小來確定采用的運動搜索方法，以實現(xiàn)對TZsearch算法的改進 。</p><p>　　向菱形算法中加入起始始搜索點的預(yù)測</p><p>　

94、　最簡單的菱形算法的起始搜索點都是（0，0），但是由于運動矢量的空間和時間上的相關(guān)性</p><p>　　可以對運動矢量進行預(yù)測，從而減少SAD計算次數(shù)并提高PSNR。在本文中，加入的預(yù)測矢量的方法如下：</p><p>　　根據(jù)空間相關(guān)性 當(dāng)前宏塊左、上、右上宏塊的MV作為預(yù)測矢量； </p><p>　　根據(jù)時間相關(guān)性 前一幀當(dāng)前位置宏塊的MV作為預(yù)測矢量；

95、</p><p>　　由于一般情況下靜止部分較大 將{0，0}作為預(yù)測矢量；</p><p>　　分別計算以上預(yù)測矢量的SAD值；</p><p>　　然后將SAD最小的預(yù)測矢量作為搜索起點； </p><p>　　可以有效減少SAD計算次數(shù)并提高PSNR，具體效果見下圖。</p><p>　　圖4.11 加入預(yù)測矢量

96、后的菱形算法性能比較</p><p>　　由圖4.11可以看出，加入預(yù)測矢量后，COST-PSNR曲線明顯向左上方移動，說明該方法可以明顯的提高PSNR并降低SAD的計算次數(shù)。TZsearch中也對運動矢量進行了預(yù)測，但是只考慮了空間相關(guān)性并沒由利用前一幀相同位置的宏塊的運動矢量，也沒有利用前一視點對應(yīng)位置的宏塊的運動矢量。因此可以加入以上兩種預(yù)測矢量，以實現(xiàn)對TZsearch算法的改進。</p>

97、<p>　　在菱形搜索中采用提前終止策略</p><p>　　場景中一般都是以某一對象為單位的運動,那么在該對象內(nèi)部，不僅是運動矢量，殘差應(yīng)該也是有很高的相關(guān)性，因此可以利用相鄰塊的SAD值作為閾值，如果某點的SAD小于閾值 則提前終止。這種方法通過利用SAD值的相關(guān)性，以犧牲小部分PSNR為代價，減少了SAD的計算次數(shù)，具體犧牲了多少PSNR，縮短了多少SAD的計算次數(shù)，與閾值的選擇有關(guān)。</p

98、><p>　　在本文中，實現(xiàn)方法如下：</p><p>　　根據(jù)空間相關(guān)性 當(dāng)前宏塊左、上、右上宏塊的SAD值作為預(yù)測值； </p><p>　　根據(jù)時間相關(guān)性 前一幀當(dāng)前位置宏塊的SAD值作為預(yù)測值；</p><p>　　將所有的預(yù)測值求均值，設(shè)其為SADav ；</p><p>　　選取系數(shù)a，令閾值為SADTH=

99、a*SADav；</p><p>　　如果某點的SAD值小于SADTH，則提前終止。</p><p>　　本文令a分別取值為0.95，1.00，1.05，1.10，1.15，1.20，1.25，1.30，1.35</p><p>　　分析以上系數(shù)下的運動估計算法性能，結(jié)果如下</p><p>　　圖3.12-1 ballroom序列采用不

100、同系數(shù)的提前終止運動搜索性能比較</p><p>　　圖4.12-2 exit序列采用不同系數(shù)的提前終止運動搜索性能比較</p><p>　　圖4.12-3 vassar序列采用不同系數(shù)的提前終止運動搜索性能比較</p><p>　　由圖4.12可以看到隨著a取值的增加，曲線向左下方移動，即PSNR略微下降的同時SAD的計算次數(shù)也下降。由于沒有做主觀測評實驗

101、，很難確定兩者的平衡點，目前只是暫定a=1.15。并嘗試把提前終止測略加入TZsearch算法中。</p><p>　　在菱形搜索中引用馬爾科夫鏈</p><p>　　之所以嘗試引入馬爾科夫鏈，是因為在本節(jié)第二小節(jié)中，為了運動搜索算法的性能，引入了5個預(yù)測矢量：</p><p>　　根據(jù)空間相關(guān)性 當(dāng)前宏塊左、上、右上宏塊的MV作為預(yù)測矢量，</p>

102、<p>　　分別設(shè)為MVP1，MVP2，MVP3； </p><p>　　根據(jù)時間相關(guān)性 前一幀當(dāng)前位置宏塊的MV作為預(yù)測矢量，設(shè)為MVP4；</p><p>　　由于一般情況下靜止部分較大 將{0，0}作為預(yù)測矢量，設(shè)為MVP0；</p><p>　　有因為本節(jié)第三小節(jié)中，采用了提前終止策略，所以很有可能這六個預(yù)測值中的某一個可以滿足提前終止條件，但

103、是由于每次計算預(yù)測矢量的SAD時都是按照默認(rèn)順序（本文測試程序中自定義順序為：零預(yù)測矢量-->左宏塊預(yù)測矢量-->上宏塊預(yù)測矢量-->右上宏塊預(yù)測矢量-->前一幀當(dāng)前位置宏塊預(yù)測矢量），當(dāng)SAD計算順序靠后的預(yù)測矢量滿足提前終止條件時（比如僅有MVP4滿足提前終止條件），運動搜索算法需要額外計算4次SAD。</p><p>　　根據(jù)文獻[5]，如果把5個預(yù)測矢量作為5種不同的預(yù)測狀態(tài)，則可

104、以認(rèn)為每幀相同位置的宏塊的預(yù)測狀態(tài)構(gòu)成了一個馬爾科夫鏈。由于馬爾科夫過程的無后效性和視頻運動的連續(xù)性，可以認(rèn)為當(dāng)前宏塊的預(yù)測矢量狀態(tài)只與前一幀對應(yīng)宏塊的預(yù)測矢量狀態(tài)有關(guān)。</p><p>　　而引入馬爾科夫鏈就是希望利用通過統(tǒng)計得到的狀態(tài)轉(zhuǎn)移概率來調(diào)整預(yù)測矢量的SAD值計算順序，把預(yù)測矢量的SAD計算順序按照滿足提前終止條件的概率進行排序。</p><p><b>　　具體過程如

105、下：</b></p><p>　　在第一幀的運動搜索完成后，統(tǒng)計每個宏塊的最優(yōu)預(yù)測矢量（將計算的到的最優(yōu)運動矢量MV分別和MVP0，MVP1，MVP2，MVP3，MVP4求差，將5個預(yù)測矢量中與MV差距最小的作為最優(yōu)預(yù)測矢量）</p><p>　　在第二幀的運動搜索完成后，也統(tǒng)計每個宏塊的最優(yōu)預(yù)測矢量。</p><p>　　計算第一幀中MVP0，MVP1

106、，MVP2，MVP3，MVP4作為最優(yōu)預(yù)測矢量的宏塊個數(shù)，分別記為M0,M1,M2,M3,M4。</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP0，第二幀為MVP0的宏塊個數(shù)，記為N00</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP0，第二幀為MVP1的宏塊個數(shù)，記為N01</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP0，第二幀為MVP2的宏塊

107、個數(shù)，記為N02</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP0，第二幀為MVP3的宏塊個數(shù)，記為N03</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP0，第二幀為MVP4的宏塊個數(shù)，記為N04</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP1，第二幀為MVP0的宏塊個數(shù)，記為N10</p><p>　　計算第一幀中最優(yōu)預(yù)

108、測矢量為MVP1，第二幀為MVP1的宏塊個數(shù)，記為N11</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP1，第二幀為MVP2的宏塊個數(shù)，記為N12</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP1，第二幀為MVP3的宏塊個數(shù)，記為N13</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP1，第二幀為MVP4的宏塊個數(shù)，記為N14</p>

109、<p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP2，第二幀為MVP0的宏塊個數(shù)，記為N20</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP2，第二幀為MVP1的宏塊個數(shù)，記為N21</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP2，第二幀為MVP2的宏塊個數(shù)，記為N22</p><p>　　計算第一幀中最優(yōu)預(yù)測矢量為MVP2，第二幀為MVP3的宏塊