基于視頻壓縮的快速自適應(yīng)菱形搜索算法

1、    基于視頻壓縮的快速自適應(yīng)菱形搜索算法        王燕妮1，2，樊養(yǎng)余1，彭 軻 時(shí)間:2008年07月10日     字 體: 大 中 小        關(guān)鍵詞:<"cblue" " target='_blank'>菱形搜索<"cblue" " targ

2、et='_blank'>視頻圖像<"cblue" " target='_blank'>絕對(duì)誤差<"cblue" " target='_blank'>運(yùn)動(dòng)估計(jì)<"cblue" " target='_blank'>三步搜索            ? 摘 要： 針對(duì)視頻壓縮標(biāo)準(zhǔn)H.264中

3、<"cblue" " title="運(yùn)動(dòng)估計(jì)">運(yùn)動(dòng)估計(jì)算法的特點(diǎn)，在兼顧<"cblue" " title="視頻圖像">視頻圖像質(zhì)量和算法運(yùn)行時(shí)間的基礎(chǔ)上，提出了基于視頻壓縮的快速自適應(yīng)<"cblue" " title="菱形搜索">菱形搜索算法。實(shí)驗(yàn)結(jié)果表明，該算法與菱形搜索算法相比，搜索時(shí)間平均減少了1.5ms, 信噪比平均提高了1.3dB。? 關(guān)鍵詞： 視頻壓縮? 自適應(yīng)? 運(yùn)動(dòng)估計(jì)? 菱形搜索? 在多

4、媒體傳輸和存儲(chǔ)中，表示視頻信息的數(shù)字需要大量的位數(shù)，對(duì)信道帶寬和存儲(chǔ)空間提出了很高的要求。相鄰兩幀之間存在很大的時(shí)間相關(guān)性，即時(shí)間冗余，而基于塊匹配的運(yùn)動(dòng)估計(jì)算法是減少時(shí)間冗余的有效方法。目前視頻壓縮標(biāo)準(zhǔn)中1的經(jīng)典運(yùn)動(dòng)估計(jì)技術(shù)有全搜索算法（ES）、<"cblue" " title="三步搜索">三步搜索算法(TSS)及菱形搜索算法(DS)等。全搜索算法在所有運(yùn)動(dòng)估計(jì)算法中性能最好，但計(jì)算量過(guò)于龐大，實(shí)時(shí)性不很理想；三步搜索算法在搜索速度和效率上比全搜索法提高了許多，但沒(méi)有窮盡所有的點(diǎn)，因而搜索誤差較大，搜索精度和性能受到很大的影響；

5、菱形搜索算法對(duì)于所有的視頻序列，在搜索最佳點(diǎn)時(shí)，廣度搜索和梯度下降搜索同時(shí)進(jìn)行，即同等地對(duì)待搜索區(qū)域的各部分，造成較大的搜索冗余，影響了算法的搜索速度。為此，針對(duì)視頻編碼標(biāo)準(zhǔn)H.264中運(yùn)動(dòng)估計(jì)技術(shù)的特點(diǎn)，在兼顧視頻圖像質(zhì)量和搜索時(shí)間的基礎(chǔ)上，提出一種新的改進(jìn)搜索算法基于視頻壓縮的快速自適應(yīng)菱形搜索算法ADS(fast adaptive diamond search algorithm)，減少了計(jì)算的復(fù)雜度并提高了運(yùn)動(dòng)補(bǔ)償后的圖像質(zhì)量。1 經(jīng)典菱形搜索算法? 經(jīng)典菱形搜索算法采用兩種搜索模式：大菱形搜索模式和小菱形搜索模式。大菱形搜索模式由一個(gè)中心點(diǎn)和它周?chē)?個(gè)搜索點(diǎn)構(gòu)成，步長(zhǎng)為2。這9個(gè)點(diǎn)

6、組成一個(gè)菱形，小菱形搜索模式由5個(gè)搜索點(diǎn)構(gòu)成，步長(zhǎng)為1。搜索步驟：第1步，最初的大菱形搜索模式以搜索窗口中心為中心點(diǎn)，計(jì)算大菱形的9個(gè)搜索點(diǎn)的誤差函數(shù)。若誤差函數(shù)最小的搜索點(diǎn)位于中心，則跳到第3步；否則跳到第2步。第2步，以第1步搜索的9個(gè)點(diǎn)中最小點(diǎn)為大菱形的中心點(diǎn)，計(jì)算大菱形的9個(gè)搜索點(diǎn)的誤差函數(shù)。若誤差函數(shù)最小的搜索點(diǎn)位于中心，則跳到第3步；否則，跳到第2步。第3步，以上一步搜索的9個(gè)點(diǎn)中的最小點(diǎn)為中心點(diǎn)，計(jì)算小菱形的5個(gè)點(diǎn)的誤差函數(shù)。誤差函數(shù)最小的塊為最佳匹配快。? 菱形搜索算法雖然計(jì)算量少，但實(shí)現(xiàn)比較復(fù)雜，而且由于在搜索區(qū)中存在大量的搜索空區(qū)2，3，所以存在搜索到非最優(yōu)點(diǎn)的情況，從而使

7、得幀間預(yù)測(cè)誤差增大。針對(duì)實(shí)時(shí)性與估計(jì)精度4-6這一對(duì)矛盾，提出一種基于視頻壓縮的快速自適應(yīng)菱形搜索算法，根據(jù)運(yùn)動(dòng)矢量的時(shí)空相關(guān)性和中心偏向特性，預(yù)測(cè)當(dāng)前塊的運(yùn)動(dòng)矢量，減小了搜索的盲目性，較好地實(shí)現(xiàn)了視頻圖像的運(yùn)動(dòng)估計(jì)。2 快速自適應(yīng)菱形搜索算法2.1 中心偏向性? 從研究一幅視頻圖像運(yùn)動(dòng)矢量的分布情況可以看出，在一定的門(mén)限判定條件下，（0，0）這個(gè)零矢量出現(xiàn)的概率極大。采用全搜索算法，搜索范圍為（-15，-15）到（15，15），中心處為（0，0）矢量位置，在此處出現(xiàn)極大單峰。這一特性說(shuō)明，在運(yùn)動(dòng)不太劇烈的情況下，運(yùn)動(dòng)矢量大量積聚在零矢量處，在預(yù)測(cè)下一幀當(dāng)前塊的運(yùn)動(dòng)矢量時(shí)可以優(yōu)先考慮零矢量。2

8、.2 搜索模式的選擇? 許多算法的搜索范圍是固定的，搜索效率并不是很高。因?yàn)樵谝曨l圖像序列的兩幀之間，只有少部分有很大的運(yùn)動(dòng)，而且有相當(dāng)一部分是沒(méi)有運(yùn)動(dòng)的，如固定背景。若能根據(jù)不同的塊運(yùn)動(dòng)情況而采用不同的搜索范圍，則可節(jié)省計(jì)算量，所以應(yīng)首先判斷搜索起點(diǎn)的運(yùn)動(dòng)類(lèi)型。? 因?yàn)樗阉髌瘘c(diǎn)的<"cblue" " title="絕對(duì)誤差">絕對(duì)誤差總和反映了該塊某種程度的運(yùn)動(dòng)，搜索起點(diǎn)的絕對(duì)誤差總和越大，意味著當(dāng)前幀與前一幀之間的差異越大，這一塊的位移可能越大，同時(shí)為在前一幀中找到最小的誤差塊，就需要對(duì)這一塊做出大范圍的搜索，否則只需要做出小范

9、圍的搜索。基于這樣一個(gè)思想，初始運(yùn)動(dòng)矢量的絕對(duì)誤差總和就可作為一個(gè)判斷運(yùn)動(dòng)類(lèi)型的依據(jù)，從而根據(jù)不同的運(yùn)動(dòng)類(lèi)型，確定對(duì)應(yīng)于各種預(yù)測(cè)結(jié)果所應(yīng)采取的搜索范圍以及搜索模式。絕對(duì)誤差總和（SAD）由下式?jīng)Q定：? ? 式中，F(xiàn)(i，j)為被壓縮的(m×n)宏塊；G(i，j)為基準(zhǔn)(m×n)宏塊；(dx，dy)為搜索處的運(yùn)動(dòng)矢量，且dx=-p，p，dy=-p，p；p是搜索范圍參數(shù)。? 根據(jù)絕對(duì)誤差總和，把運(yùn)動(dòng)類(lèi)型分為三類(lèi)：當(dāng)SAD<T1時(shí)，當(dāng)前塊為低速運(yùn)動(dòng)塊，可直接采用小菱形搜索算法搜索最佳運(yùn)動(dòng)矢量；當(dāng)T1SADT2時(shí)，當(dāng)前塊為中速運(yùn)動(dòng)塊, 可采用大菱形搜索算法進(jìn)行搜索；當(dāng)SAD&

10、gt;T2時(shí)，當(dāng)前塊為高速運(yùn)動(dòng)塊，可采用全搜索算法，以求得較好的搜索效果。由于這種塊所占的比例較小，計(jì)算量的影響并不顯著。式中，T1、T2為兩個(gè)閾值。? 首先計(jì)算當(dāng)前幀所選塊與參考幀中的相同位置處的對(duì)應(yīng)塊的絕對(duì)誤差總和，記為prev_SAD。則設(shè)? 式中，一般取為0.9<<1.4，取為1.2<<2.5，且<，、屬于經(jīng)驗(yàn)值。? 若當(dāng)前幀為第一幀，則不存在prev_SAD。通過(guò)大量的實(shí)驗(yàn)，在不影響視頻圖像質(zhì)量并且考慮傳輸實(shí)時(shí)性的情況下，T1取500左右，T2取800左右。3 仿真分析? 為了比較快速自適應(yīng)菱形搜索算法的效果，采用8bit的視頻圖像序列對(duì)全搜索法、三步搜

11、索法、菱形法以及快速自適應(yīng)菱形搜索法在相同的條件下進(jìn)行計(jì)算機(jī)仿真。3.1 重建幀的比較? 采用susie（352×240）序列，塊的大小為16×16，搜索范圍P為7。以第五幀作為參考幀，分別用全搜索算法以及快速自適應(yīng)菱形搜索算法得到第七幀的重建幀。可以看出，快速自適應(yīng)菱形搜索算法重建的視頻圖像非常接近視頻圖像的原始幀, 結(jié)果如圖1所示。?3.2 誤差幀的比較? 為了直觀地觀察新算法的效果，用峰值信噪比(PSNR)和均方誤差(MSE)來(lái)衡量各種運(yùn)動(dòng)估計(jì)技術(shù)的性能。對(duì)于8bit的視頻圖像來(lái)說(shuō)，PSNR定義為：? 式中，MSE表示均方誤差，由下式?jīng)Q定：? 式中，f(i，j)是視頻

12、圖像序列的原始幀，g(i，j)是利用運(yùn)動(dòng)矢量重建的幀。仍然采用susie（352×240）序列的第一幀作為參考幀，塊的大小采用16×16，搜索范圍P為7。分別用ES算法、TSS算法、DS算法及ADS算法得到第二幀的誤差幀。圖2中所示為ADS算法和DS算法產(chǎn)生的誤差幀。?3.3 性能的比較? 以MSE和PSNR作為衡量搜索算法性能的標(biāo)準(zhǔn)，通過(guò)用相應(yīng)的搜索算法得到各自的性能，采用susie（352×240）序列為視頻測(cè)試序列，塊的大小為16×16，搜索范圍p為7，分別用各種搜索方法計(jì)算視頻序列中連續(xù)20幀的MSE和PSNR，實(shí)驗(yàn)結(jié)果如圖3所示。?3.4 搜索

13、匹配時(shí)間的比較? 采用missamerican（360×288）序列的第五幀作為參考幀，塊的大小采用16×16，搜索范圍P為7。在同樣的環(huán)境下，分別用ES算法、TSS算法、DS算法以及ADS算法進(jìn)行匹配得到恢復(fù)的第六幀，搜索匹配時(shí)間分別如表1所示。? 在上面的實(shí)驗(yàn)1中，采用susie（352×240）序列的第五幀，用ADS算法對(duì)其第七幀進(jìn)行重建，從主觀上看，ADS算法的重建視頻圖像非常接近原始的視頻圖像；在實(shí)驗(yàn)2中，采用susie(352×240)序列對(duì)誤差幀進(jìn)行比較，可以看出ADS算法比DS算法產(chǎn)生的誤差平均降低了約300個(gè)數(shù)量級(jí)；在實(shí)驗(yàn)3中，采用su

14、sie（352×240）序列對(duì)算法進(jìn)行性能比較，可得ADS算法的性能曲線都優(yōu)于DS算法的性能曲線，峰值信噪比比DS算法平均提高了1.3dB，相應(yīng)地均方誤差也降低了。對(duì)于運(yùn)動(dòng)緩慢的視頻序列，新算法的性能幾乎逼近全搜索算法；在實(shí)驗(yàn)4中，用各種算法對(duì)missamerican(360×288)序列進(jìn)行匹配，比較可得改進(jìn)算法的搜索匹配時(shí)間比DS算法平均減少了約1.5ms。? 基于視頻壓縮的快速自適應(yīng)菱形搜索算法，充分利用了視頻圖像序列的時(shí)空相關(guān)特性，采用了大小菱形搜索模式，實(shí)現(xiàn)了運(yùn)動(dòng)矢量高速而較精確的估計(jì)。仿真結(jié)果表明，與全搜索算法、三步搜索算法、菱形搜索算法等一些優(yōu)秀算法相比，新算

15、法的運(yùn)動(dòng)估計(jì)準(zhǔn)確性高、預(yù)測(cè)質(zhì)量好。在可視電話、終端會(huì)議等的實(shí)時(shí)視頻通信中，該算法可取得較好的效果。參考文獻(xiàn)1 朱秀昌，劉峰，胡棟.數(shù)字圖像處理與圖像通信M.北京：北京郵電大學(xué)出版社，2002.2 KELLER Y，AVERBUCH A.Fast motion estimation using?bidirectional gradient methodsJ.IEEE Trans.Image Processing，2004，13：1042-1054.3 ZHU S，MA K K.A new diamond search algorithm for fast block-matching motio

16、n estimationJ.IEEE Trans on Image Processing.2000，9：287-290.4 ELAD M，HEL-OR Y.A fast super-resolution reconstruction algorithm for pure translational motion and common space?invariant blurJ.IEEE Trans.Image Processing，2001，10：1187-1193.5 ALTUNBASAK Y，PATTI A，MERSEREAU R.Super-resolution still and video re