AVS編碼算法全搜索方案優(yōu)化

郭玉潔，劉彥隆，張 剛

（太原理工大學(xué) 信息工程學(xué)院，山西 太原 030024）

運(yùn)動(dòng)估計(jì)與運(yùn)動(dòng)補(bǔ)償是視頻編碼中一個(gè)重要的組成部分。利用該技術(shù)可以有效去除視頻序列相鄰幀存在的時(shí)間冗余，極大地降低傳輸?shù)拇a率，提高編碼效率。塊匹配運(yùn)動(dòng)估計(jì)算法是目前應(yīng)用最廣泛的一種運(yùn)動(dòng)估計(jì)算法。最基本的塊匹配的算法是全搜索（Full Search，F(xiàn)S）算法，通過(guò)對(duì)搜索范圍內(nèi)所有點(diǎn)進(jìn)行搜索從而得到最佳匹配點(diǎn)，全搜索算法有描述語(yǔ)言簡(jiǎn)單、在硬件上容易實(shí)現(xiàn)的特點(diǎn)，所以改進(jìn)全搜索是最基本、對(duì)硬件實(shí)現(xiàn)有實(shí)際的指導(dǎo)意義。在整個(gè)視頻處理的過(guò)程中，98%以上的計(jì)算時(shí)間被運(yùn)動(dòng)估計(jì)占用，所以改進(jìn)運(yùn)動(dòng)矢量的搜索對(duì)視頻處理有極大的意義。時(shí)間、碼率、信噪比是視頻壓縮的主要指標(biāo)，減少時(shí)間、降低碼率、增強(qiáng)信噪比是每種改進(jìn)算法的目標(biāo)。

1 傳統(tǒng)全搜索算法

傳統(tǒng)全搜索算法先分別計(jì)算目標(biāo)宏塊與mvp和（0，0）點(diǎn)所對(duì)應(yīng)的參考宏塊的代價(jià)值，選二者中較小代價(jià)值的為搜索對(duì)象，在擴(kuò)展range=32個(gè)像素范圍內(nèi)搜索。在搜索范圍內(nèi)先以16×16模式在前兩個(gè)恢復(fù)幀中搜索出代價(jià)值較小的一幀做為整個(gè)宏塊的參考幀，然后在確定的參考幀中搜索其余模式（順序?yàn)?×8，16×8，8×16以及幀內(nèi)模式）。在確定8×8模式代價(jià)值后與16×16模式代價(jià)值比較，若高于16×16模式代價(jià)值則結(jié)束搜索；否則拋棄16×16模式繼續(xù)搜索16×8和8×16模式，根據(jù)最小代價(jià)值原則確定該宏塊最佳搜索模式。

一般在碼率相同情況下全搜索方案可以獲得最好的信噪比，但是計(jì)算復(fù)雜性太高導(dǎo)致幀率降低。一些改進(jìn)的搜索算法不做全搜索，針對(duì)特定情況設(shè)計(jì)特殊搜索路徑以便縮小搜索范圍，但是不具有通用性。降低全搜索方案計(jì)算復(fù)雜性主要采用兩種措施：只搜索16×16模式或縮小各個(gè)搜索區(qū)域尺寸，對(duì)于大多視頻序列這種全搜索的改進(jìn)方案將會(huì)導(dǎo)致信噪比下降和碼率增高的現(xiàn)象。事實(shí)上，基于塊匹配原理的各種不同搜索模式所包含的相關(guān)性信息有著緊密的關(guān)聯(lián)性，但是傳統(tǒng)全搜索方案沒(méi)有充分利用不同模式搜索結(jié)果中蘊(yùn)含的圖像相似性信息來(lái)降低計(jì)算復(fù)雜性。本文提出一種新的全搜索方案，其信噪比和碼率與傳統(tǒng)全搜索方案具有相同的水平，但計(jì)算復(fù)雜性?xún)H略高于16×16搜索模式。

2 SMS全搜索方案

本論文提出一種新的基于子模式拼接（Sub-Model Stitching，SMS）的高效運(yùn)動(dòng)矢量全搜索方案，充分利用既有搜索模式的代價(jià)值和位置信息，通過(guò)子模式拼接來(lái)確定后續(xù)搜索模式和縮小搜索范圍，把全搜索的計(jì)算量降低到相當(dāng)于只作16×16模式搜索。由于SMS算法包括了所有模式的更加精細(xì)搜索，在處理運(yùn)動(dòng)劇烈的視頻序列時(shí)有較好效果。SMS基本流程如圖1所示。

圖1 SMS搜索流程

2.1 SMS方案的搜索流程

SMS的基本流程是：先在兩個(gè)恢復(fù)幀中搜索8×8模式得到 4 個(gè)最佳匹配子宏塊和相應(yīng)的mv={mv0（i0），...，mv3（i3）}，其中ik=0或ik=1，k=0，1，2，3是參考的恢復(fù)幀索引值，并用它們指導(dǎo)后續(xù)模式的搜索。若相應(yīng)的4個(gè)恢復(fù)幀索引值有3個(gè)以上相同，則將其定為唯一的參考幀，否則確定2個(gè)參考幀。確定參考幀后，若是唯一的參考幀且含有3個(gè)以上相鄰mv，則將這4個(gè)子宏塊直接拼接生成一個(gè)16×16的最佳模式，并且不進(jìn)行其余模式的搜索；若不存在3個(gè)以上相鄰的mv或者參考幀不唯一，則在一個(gè)參考幀或兩個(gè)參考幀中進(jìn)行判斷：是否有2個(gè)相鄰的8×8子宏塊可以拼接組合成為一個(gè)16×8（或8×16）塊；如果有則完成拼接并且只在包含該塊的小范圍內(nèi)進(jìn)行相應(yīng)16×16最佳模式的搜索；如果沒(méi)有則在4個(gè)8×8塊的mv周?chē)鷶U(kuò)展進(jìn)行小范圍16×16最佳模式的搜索。將搜索的16×16最佳模式代價(jià)值與綜合后的8×8最佳模式代價(jià)值進(jìn)行比較并確定16×16最佳模式是否為最終模式，若是則搜索過(guò)程結(jié)束；否則進(jìn)行16×8（或8×16）模式搜索，此時(shí)若在4個(gè)mv中可以進(jìn)行拼接組合則實(shí)現(xiàn)拼接并作如下判別，如果存在一組16×8拼接，判斷是否存在另一組16×8拼接；如存在另一組16×8拼接則實(shí)現(xiàn)拼接并終止搜索，以16×8為候選模式；否則不存在另一組16×8拼接，在余下的2個(gè)8×8塊周?chē)鷶U(kuò)展成16×8塊進(jìn)行搜索，并且不進(jìn)行8×16模式搜索。如果不存在一組16×8拼接則按上述原則進(jìn)行8×16模式的處理。若不存在任何可以拼接的情況，4個(gè)8×8塊的mv周?chē)鷶U(kuò)展分別進(jìn)行16×8模式和8×16模式的搜索，最后比較它們的代價(jià)值確定此宏塊的最佳模式。

當(dāng)存在可拼接模式時(shí)，前期搜索結(jié)果蘊(yùn)含了圖像之間的相關(guān)性，表明當(dāng)前搜索的圖像塊成為最佳模式的概率大大提升，在此周?chē)鷶U(kuò)展搜索的范圍可以大大減少。有關(guān)搜索范圍的討論將在下文涉及。

2.2 模式的可拼接性

傳統(tǒng)全搜索方案中所有宏塊必需經(jīng)過(guò)8×8模式和16×16模式的搜索，大部分模塊要經(jīng)過(guò)16×8模式或8×16模式搜索。所以若能不經(jīng)搜索便直接確定這些模式的mv和參考索引，則可以大量節(jié)約搜索時(shí)間。表1是對(duì)新的全搜索方案拼接組合成功比率的測(cè)試結(jié)果，選取AVS官網(wǎng)提供的5個(gè)視頻序列，其中cif格式有Foreman，Chil?dren和Football，D1格式有Ice和Soccer。

表1的每個(gè)模式項(xiàng)下，總數(shù)是經(jīng)過(guò)該模式搜索的宏塊數(shù)目，命中數(shù)目指的是可以進(jìn)行拼接的宏塊數(shù)目。由表1可知經(jīng)過(guò)8×8模式搜索之后，除了運(yùn)動(dòng)較為劇烈的Football碼流之外，其余序列可以直接拼接組合生成16×16模式的宏塊占比超過(guò)60%以上，剩余的宏塊中有48%～70%可以經(jīng)過(guò)組合拼接成為16×8塊或8×16塊，不經(jīng)搜索直接與其他模式代價(jià)值比較。由此可知，新算法主要通過(guò)拼接組合而不是搜索獲得最佳模式，可以大大降低計(jì)算復(fù)雜性。

表1 新全搜索方案拼接組合命中率

2.3 確定搜索范圍

進(jìn)行8×8模式搜索后，SMS的mv值所對(duì)應(yīng)的像素塊最有可能包含在最佳模式中，因此在其周?chē)鷧^(qū)域搜索其余模式，搜索范圍可以相應(yīng)地縮小。在傳統(tǒng)全搜索算法中加入測(cè)試語(yǔ)句，記錄各模式最佳搜索結(jié)果的mv與8×8模式mv之間的距離，以其距8×8模式的4個(gè)mv中最小者為準(zhǔn)。以8×8模式的mv為中心作圓使其覆蓋其他各個(gè)模式的mv，半徑分別取102，82和5 2進(jìn)行統(tǒng)計(jì)，考查不同半徑覆蓋圓的覆蓋效率。取5個(gè)cif格式的視頻序列，測(cè)試結(jié)果如表2所示。

表2 覆蓋率對(duì)比

由表2可知，半徑為5的覆蓋率不到80%，搜索范圍過(guò)??；半徑為10的覆蓋率雖然較理想，但10不是2的整數(shù)次冪，不利于硬件實(shí)現(xiàn)；半徑為8的搜索范圍比較合適，運(yùn)動(dòng)最快的圖像序列也有87.2%的覆蓋率，一般的圖像序列平均覆蓋率在95%左右。由于程序可實(shí)現(xiàn)的搜索范圍是矩形的，所以將半徑為82改為上下左右擴(kuò)展8個(gè)像素點(diǎn)的范圍進(jìn)行測(cè)試，結(jié)果如表3所示。

表3 覆蓋率對(duì)比

矩形搜索的覆蓋率并沒(méi)有大幅降低，權(quán)衡處理速度和搜索精度后將16×16模式、16×8模式、8×16模式的搜索范圍定為在8×8模式的mv上下左右擴(kuò)展8像素比較合理。

確定8×8模式的搜索范圍是range=32和range=16，即對(duì)原始數(shù)據(jù)上下左右都擴(kuò)展16和32，主要考察其對(duì)PSNR、碼率和幀率3個(gè)參數(shù)的影響。表4是新的全搜索方案對(duì)搜索范圍的測(cè)試結(jié)果，其中范圍①和②分別是range=16和range=32，在進(jìn)行其余模式搜索時(shí)均采用上下左右擴(kuò)展8像素。

表4 8×8模式搜索范圍

由表4的實(shí)驗(yàn)數(shù)據(jù)可知，對(duì)于新的全搜索算法，搜索范圍①比范圍②的PSNR和幀率都高且碼率小，因此將全搜索新算法的8×8模式搜索范圍定為上下左右擴(kuò)展16個(gè)像素。

3 實(shí)驗(yàn)與結(jié)果

測(cè)試的4個(gè)全搜索方案分別是原全搜索方案、原方案1（上下左右擴(kuò)展32像素，僅16×16搜索）、原方案2（上下左右擴(kuò)展16像素，僅16×16搜索）和SMS搜索方案。新的全搜索方案中8×8模式的搜索范圍為擴(kuò)展16像素。實(shí)驗(yàn)程序用pentium（R）Dull-wre cpu處理器，型號(hào)是E5500，主頻2.80 GHz，內(nèi)存2 Gbyte。測(cè)試序列采用IPPPP…結(jié)構(gòu)，測(cè)試結(jié)果列在表5～表8中。

表5 PSNR對(duì)比dB

表6 幀率對(duì)比f(wàn)/s

表7 碼率對(duì)比kbit/s

表8 幀內(nèi)模式比例%

由表5～表7可知，新搜索方案的PSNR與原搜索方案基本保持一致，表明圖像質(zhì)量保持不變；僅16×16搜索的兩個(gè)原方案出現(xiàn)PSNR下降的現(xiàn)象，尤其是對(duì)運(yùn)動(dòng)劇烈的視頻序列PSNR下降尤為明顯，原因是僅作16×16搜索對(duì)圖像細(xì)節(jié)描述粗糙。在幀率方面，原全搜索方案由于搜索模式多、范圍大所以搜索時(shí)間長(zhǎng)、幀率低；新全搜索方案通增加模式拼接，比較原全搜索算法幀率大大提升，幾乎能夠達(dá)到僅16×16搜索的原方案水平。新全搜索與原全搜索兩種算法的PSNR和碼率基本相同，而僅作16×16搜索的原方案，對(duì)運(yùn)動(dòng)劇烈的視頻序列碼率相對(duì)較低，而對(duì)運(yùn)動(dòng)稍微平緩的視頻序列碼率反而要高，原因是缺少16×8、8×16和8×8模式的精細(xì)描述，導(dǎo)致幀內(nèi)模式比例提高，詳見(jiàn)表8。

由上述各表可知，新的全搜索方案與原方案比較，碼率基本沒(méi)有變化，PSNR基本保持不變，幀率提升300%左右，與原方案2的處理速度相當(dāng)?？梢?jiàn)新的全搜索方案碼率得到提升，對(duì)cif序列和D1序列都有效。

4 結(jié)束語(yǔ)

本文將AVS幀間運(yùn)動(dòng)矢量搜索算法采用模式拼接新的理念在C語(yǔ)言程序?qū)崿F(xiàn)。新全搜索方案可以處理cif（352×288）、D1（704×576）的4∶2∶0的視頻圖像，對(duì)視頻序列的處理在幀率有大幅提升。本論文的研究?jī)?nèi)容對(duì)AVS幀間運(yùn)動(dòng)矢量搜索算法的實(shí)現(xiàn)有著實(shí)際的參考價(jià)值。

：

[1]畢厚杰.視頻壓縮編碼標(biāo)準(zhǔn)——H.264/AVC[M].北京：人民郵電出版社，2005.

[2]肖敏連.一種快速整像素運(yùn)動(dòng)估計(jì)算法研究[J].湖南人文科技學(xué)院學(xué)報(bào)，2011（10）：129-141.

[3]張子敬，張志華，霍家道.基于運(yùn)動(dòng)矢量分散度的增強(qiáng)型MVFAST搜索算法[J].科學(xué)技術(shù)與工程，2012（12）：9216-9220.

[4]王荃，鮑衛(wèi)兵，張永智.搜索模式自適應(yīng)快速運(yùn)動(dòng)估計(jì)算法[J].電視技術(shù)，2009，33（7）：16-17.

[5]包國(guó)興，諶德榮，胡宏華，等.一種快速H.264幀間模式選擇算法[J].博士論壇，2010（26）：1-2.

[6]劉海華，雷奕，謝長(zhǎng)生.基于塊匹配的運(yùn)動(dòng)估計(jì)搜索算法研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用，2006（6）：1354-1356.

[7]AVS工作組.GB/T20090.2—2006，信息技術(shù)先進(jìn)音視頻編碼第二部分：視頻[S].北京：中國(guó)標(biāo)準(zhǔn)化出版社，2006.