郭玉潔，劉彥隆，張 剛

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

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

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

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

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

2 SMS全搜索方案

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

圖1 SMS搜索流程

2.1 SMS方案的搜索流程

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

當存在可拼接模式時，前期搜索結果蘊含了圖像之間的相關性，表明當前搜索的圖像塊成為最佳模式的概率大大提升，在此周圍擴展搜索的范圍可以大大減少。有關搜索范圍的討論將在下文涉及。

2.2 模式的可拼接性

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

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

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

2.3 確定搜索范圍

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

表2 覆蓋率對比

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

表3 覆蓋率對比

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

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

表4 8×8模式搜索范圍

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

3 實驗與結果

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

表5 PSNR對比dB

表6 幀率對比f/s

表7 碼率對比kbit/s

表8 幀內模式比例%

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

由上述各表可知，新的全搜索方案與原方案比較，碼率基本沒有變化，PSNR基本保持不變，幀率提升300%左右，與原方案2的處理速度相當?？梢娦碌娜阉鞣桨复a率得到提升，對cif序列和D1序列都有效。

4 結束語

本文將AVS幀間運動矢量搜索算法采用模式拼接新的理念在C語言程序實現(xiàn)。新全搜索方案可以處理cif（352×288）、D1（704×576）的4∶2∶0的視頻圖像，對視頻序列的處理在幀率有大幅提升。本論文的研究內容對AVS幀間運動矢量搜索算法的實現(xiàn)有著實際的參考價值。

：

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

[2]肖敏連.一種快速整像素運動估計算法研究[J].湖南人文科技學院學報，2011（10）：129-141.

[3]張子敬，張志華，霍家道.基于運動矢量分散度的增強型MVFAST搜索算法[J].科學技術與工程，2012（12）：9216-9220.

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

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

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

[7]AVS工作組.GB/T20090.2—2006，信息技術先進音視頻編碼第二部分：視頻[S].北京：中國標準化出版社，2006.