運(yùn)動(dòng)估計(jì)快速搜索算法的研究

1、運(yùn)動(dòng)估計(jì)快速搜索算法的研究                        摘要：H.264是ITU-T的VCEG(視頻編碼專家組)和ISOIEC的MPEG(活動(dòng)圖象編碼專家組)的聯(lián)合視頻組(JVT：joint videoteam)開發(fā)的一個(gè)新的數(shù)字視頻編碼標(biāo)準(zhǔn)，它既是ITU-T的H.264，又是1SOIEC的MPEG-4的第10部分。新一代標(biāo)準(zhǔn)H.264可以

2、得到更好的壓縮圖像效果、擁有更多的功能和更大的靈活性。本文主要從實(shí)時(shí)視頻應(yīng)用的角度，對H 264AVC編碼過程中運(yùn)動(dòng)估計(jì)模塊快速搜索算法進(jìn)行了研究。 關(guān)鍵詞：視頻編碼H 264AVC運(yùn)動(dòng)估計(jì)快速搜索算法 隨著信息技術(shù)的發(fā)展和社會(huì)的不斷進(jìn)步，人類對信息的需求越來越豐富，人們希望無論何時(shí)何地都能夠方便的、快捷、靈活的通過語音、數(shù)據(jù)、圖像與視頻等多種方式進(jìn)行通信。數(shù)字信號處理技術(shù)、物理媒體與網(wǎng)絡(luò)技術(shù)、超大規(guī)模集成電路技術(shù)突飛猛進(jìn)的發(fā)展，使得多媒體通信成為研究和應(yīng)用的熱點(diǎn)。本文主要是針對視頻壓縮中的運(yùn)動(dòng)估計(jì)快速搜索算法的研究。視頻壓縮后的數(shù)據(jù)流大小的關(guān)鍵因素在于能否較好的去除其時(shí)間相關(guān)性，尋找到最佳的

3、匹配塊。 1.H.264AVC概述 與早期的視頻編碼標(biāo)準(zhǔn)(H.261，MPEG-1，MPEG-2，H.263，MPEG-4)類似，H.264AVC也是建立在塊匹配的混合編碼框架上。基本算法依然是通過幀間預(yù)測和運(yùn)動(dòng)補(bǔ)償來消除視頻序列中的時(shí)域冗余，經(jīng)過變換編碼消除頻域冗余。因此基本的功能模塊：例如預(yù)測、變換、量化、編碼都沒有發(fā)生根本的變化。 2.運(yùn)動(dòng)估計(jì)原理 2.1運(yùn)動(dòng)估計(jì)概述 在基于塊匹配的混合視頻編碼體系中，運(yùn)動(dòng)搜索是其中計(jì)算復(fù)雜性最高的模塊。H.264AVC為了獲得更精確的預(yù)測和更高的壓縮比，采用了多種塊模式的運(yùn)動(dòng)估計(jì)，多參考幀和更高分辨率的運(yùn)動(dòng)矢量。雖然這樣可以增加預(yù)測的精度，提高壓縮比，

4、但H.264AVC中運(yùn)動(dòng)估計(jì)的計(jì)算復(fù)雜性卻因此急劇增加。運(yùn)動(dòng)搜索快速算法的實(shí)質(zhì)是基于某種策略在減少搜索點(diǎn)數(shù)提高搜索效率的同時(shí)，盡可能保持編碼圖像質(zhì)量不變(與FS的情況相比)。但簡單的減少搜索點(diǎn)數(shù)的算法(例如TTS，2-D對數(shù)等快速算法)通常都假設(shè)匹配誤差曲面是單峰的，而實(shí)際的視頻圖像是非常復(fù)雜的，常常不能滿足這樣的假設(shè)，因此容易在搜索起始階段落入局部最小點(diǎn)。為解決局部最小點(diǎn)的問題，通?？梢圆捎孟噜弶K預(yù)測的方法獲得更好的搜索起點(diǎn)。但有些情況下特別是在運(yùn)動(dòng)復(fù)雜度高的序列中，相鄰塊會(huì)包含與當(dāng)前塊不同的運(yùn)動(dòng)對象，因此也會(huì)產(chǎn)生錯(cuò)誤的運(yùn)動(dòng)矢量。更好的策略是采用覆蓋整個(gè)搜索區(qū)域的全局搜索(Global Se

5、arch)的概念，即搜索點(diǎn)在整個(gè)搜索區(qū)域的稀疏網(wǎng)格上選擇。雖然這種策略增加了搜索點(diǎn)數(shù)，但可以有效的避免在搜索起始階段落入局部最小點(diǎn)以及可能的錯(cuò)誤起始點(diǎn)預(yù)測。 2.2運(yùn)動(dòng)搜索的步驟 最佳匹配塊的確定是通過運(yùn)動(dòng)搜索來實(shí)現(xiàn)的，運(yùn)動(dòng)搜索包含整數(shù)運(yùn)動(dòng)搜索和小數(shù)運(yùn)動(dòng)搜索，具體的流程圖如圖2.1所示： 2.2.1參考幀的選取 在H.264協(xié)議中，定義了三種基本的幀類型，即I、P、B幀類型，其中I幀只能作為其他幀的參考幀，它本身在編碼的時(shí)候，幀內(nèi)宏塊根據(jù)已經(jīng)編編碼的相鄰塊的數(shù)據(jù)來編碼，不參考其它幀；P幀在編碼的時(shí)候，只能參考在時(shí)間軸上靠前的幀，包括之前已經(jīng)編碼的I幀以及P幀，即前向預(yù)測；B幀則可以雙向預(yù)測，它

6、的參考幀可以是時(shí)間上“過去”的幀。也可以是時(shí)間上“將來”的幀，它的參考幀也可以是I幀以及P幀，B幀只能參考其它幀，其本身不能作為其他幀的參考幀，所以他不會(huì)引起預(yù)測誤差擴(kuò)散。在具體的編碼中，當(dāng)遇到B型幀時(shí)，先把它讀到緩存中，編碼后面的P幀，當(dāng)前后的參考幀都被編碼以后，再編碼B幀。在解碼端，當(dāng)解碼解到B幀時(shí)，則先將它讀入緩存，待到解碼完它后面的P幀，再解碼B幀。 2.2.2預(yù)測運(yùn)動(dòng)向量的獲取 如果對每個(gè)塊的運(yùn)動(dòng)矢量進(jìn)行編碼，那么將花費(fèi)相當(dāng)數(shù)目的比特?cái)?shù)，特別是在選擇小尺寸的塊的情況下。由于一個(gè)運(yùn)動(dòng)物體會(huì)覆蓋多個(gè)分塊，所以空間域相鄰塊的運(yùn)動(dòng)矢量具有很強(qiáng)的相關(guān)性。因此，每個(gè)運(yùn)動(dòng)矢量可以根據(jù)臨近先前已編碼

7、的塊進(jìn)行預(yù)測，預(yù)測得到的運(yùn)動(dòng)矢量用MVp表示，當(dāng)前矢量和預(yù)測矢量之間的差值用MVD表示。同時(shí)由于物體運(yùn)動(dòng)具有連續(xù)性，運(yùn)動(dòng)矢量在時(shí)間域也存在一定的相關(guān)性，因此也可以用臨近參考幀的運(yùn)動(dòng)矢量來進(jìn)行預(yù)測。                             2.2.3搜索范圍的確定 當(dāng)獲取了預(yù)測運(yùn)動(dòng)向量以后，在參考幀中找到

8、當(dāng)前塊的對應(yīng)塊，此點(diǎn)即對應(yīng)運(yùn)動(dòng)向量(O，O)，并以此為基點(diǎn)，向其上下左右擴(kuò)出運(yùn)動(dòng)搜索范圍大小，此即我們需要的運(yùn)動(dòng)搜索范圍。 搜索區(qū)域的選擇一般是相對于當(dāng)前塊對稱得，左邊和右邊各有d個(gè)像素，上邊和下邊各有d個(gè)像素。 3.一種新的運(yùn)動(dòng)估計(jì)快速搜索算法 這些年來，許多的快速搜索算法都被提了出來，其中比較好的有三步法，四步法，菱形搜索法等等，它們與全搜索算法相比節(jié)省了大量的運(yùn)動(dòng)時(shí)間?？墒沁@些算法中大部分不論在水平還是在垂直方向上都是規(guī)則對稱的，三步法和四步法等等都是如此，但是在實(shí)際的運(yùn)動(dòng)圖像當(dāng)中都是水平方向的運(yùn)動(dòng)要遠(yuǎn)比垂直方向的運(yùn)動(dòng)要?jiǎng)×业亩啵@是因?yàn)閷τ谝粋€(gè)以常見的現(xiàn)實(shí)世界為內(nèi)容的視頻序列來說，它的

9、前后幀之間的差異來源主要有兩個(gè)方面：視頻目標(biāo)的運(yùn)動(dòng)和視頻獲取設(shè)備的運(yùn)動(dòng)。視頻目標(biāo)的常見運(yùn)動(dòng)集中在水平方向，如汽車和火車的行駛，行人在路上走等；而攝像機(jī)的運(yùn)動(dòng)一般以平動(dòng)和水平轉(zhuǎn)動(dòng)為主，所以運(yùn)動(dòng)向量就應(yīng)該是以水平方向的運(yùn)動(dòng)向量為主。 從運(yùn)動(dòng)向量的搜索過程中我們可以得知，后步的搜索都是建立在前一步的基礎(chǔ)上的，每一步都為下一步指出了運(yùn)動(dòng)向量所在的大致方向，而運(yùn)動(dòng)向量又是以水平方向的運(yùn)動(dòng)向量為主，所以本算法中第一步以偏水平方向的十字搜索模板作為搜索基礎(chǔ)。 基于偏水平十字及偏向雙鉆石搜索算法(DHCDDS)主要是將兩種搜索模版相結(jié)合盡可能的以最小的搜索時(shí)間準(zhǔn)確的確定最佳匹配點(diǎn)，一種是偏水平十字型搜索模板，

10、另一種是偏向雙鉆石搜索模板，其中第一個(gè)偏水平十字搜索模板主要是根據(jù)視頻圖像的運(yùn)動(dòng)變化主要是集中在水平方向上的特點(diǎn)來初步確定搜索的基本位置，第二個(gè)偏向雙鉆石搜索模板是根據(jù)偏水平十字搜索模板的初步定位，進(jìn)一步使用搜索效果比較理想的雙鉆石搜索模板來確定當(dāng)前最佳匹配點(diǎn)，直到當(dāng)前最佳匹配點(diǎn)在中心點(diǎn)或偏中心點(diǎn)才結(jié)束搜索過程，然后通過比較幾個(gè)候選點(diǎn)的SAD值的大小來確定最佳匹配點(diǎn)的位置。該快速運(yùn)動(dòng)估計(jì)搜索算法所要搜索的點(diǎn)數(shù)較少，提高了編碼效率。 4.結(jié)語 本文主要對于視頻壓縮中的運(yùn)動(dòng)估計(jì)快速搜索算法進(jìn)行了簡單的研究。視頻壓縮后的數(shù)據(jù)流大小的關(guān)鍵因素在于能否較好的去除其時(shí)間相關(guān)性，尋找到最佳的匹配塊。實(shí)驗(yàn)表明在信噪比和比特率變化很小的情況下，搜索時(shí)間大為縮短。文中提出的算法僅僅采用了搜索模板