用于ＡＶＳ視頻編碼的快速子像素運(yùn)動(dòng)搜索算法

摘 要：AVS視頻編碼采用1/2像素和1/4像素精度的運(yùn)動(dòng)搜索，算法復(fù)雜度較高。為此，提出了一種新的基于雙線性插值的快速子像素運(yùn)動(dòng)搜索算法，該算法大大降低了子像素運(yùn)動(dòng)搜索的復(fù)雜性，且非常適合硬件實(shí)現(xiàn)。實(shí)驗(yàn)結(jié)果表明，新算法在保證原算法視頻質(zhì)量基本不變的前提下，計(jì)算復(fù)雜度降低了40%以上。

關(guān)鍵詞： 音/視頻編碼標(biāo)準(zhǔn)；雙線性插值；子像素；運(yùn)動(dòng)搜索

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)07-2238-03



Rapid sub-pixels movement search algorithm for AVS video coding

ZHOU Bo1，WANG Li-bo1，LIU Dong-hua2，ZHOU Jing-ye1



(1. College of Information Engineering， Xiangtan University， Xiangtan Hunan 411105，China; 2. National University of Defense Technology， Changsha 410073，China)



Abstract:The accuracy of AVS video Coding inter frame prediction was 1/4 pixel， resulting in a higher complexity of the algorithm. In order to reduce the complexity， this paper proposed a new rapid sub-pixels movement search algorithm based on the bilinear interpolation， which had really reduced the complexity of the sub-pixels movement search， and was suitable for hardware implementation as well. Experimental results show that the new algorithm can reduce computational complexity more than 40% without debasing the quality performance of the video.

Key words：AVS(audio video coding standard); bilinear interpolation; sub-pixels; movement search

AVS是我國擁有自主知識產(chǎn)權(quán)的新一代信源編碼標(biāo)準(zhǔn)^[1]。該標(biāo)準(zhǔn)采用與目前國際最新的視頻標(biāo)準(zhǔn)H.264類似的技術(shù)框架，但在算法上運(yùn)用了許多我國擁有自主知識產(chǎn)權(quán)的核心技術(shù)。AVS的壓縮性能是前一代編碼標(biāo)準(zhǔn)MPEG-2的兩三倍，與H.264和MPEG-4相當(dāng)，且存在明顯優(yōu)勢：算法實(shí)現(xiàn)簡單、專利授權(quán)模式簡單、費(fèi)用明顯低于同類標(biāo)準(zhǔn)，因此其在嵌入式系統(tǒng)將得到廣泛的應(yīng)用。在AVS視頻編碼中，子像素運(yùn)動(dòng)搜索算法的復(fù)雜度較大，需要占用較多的存儲資源，在嵌入式(如DSP)系統(tǒng)上實(shí)現(xiàn)實(shí)時(shí)編碼存在一定難度。本文提出了一種新的快速子

像素運(yùn)動(dòng)搜索算法并在TI TMS320DM642上進(jìn)行了實(shí)現(xiàn)驗(yàn)證。該算法實(shí)現(xiàn)簡單，在保證編碼性能的前提下能有效地提高編碼速度。

1 AVS子像素運(yùn)動(dòng)搜索算法

1．1 亮度插值算法

為了提高運(yùn)動(dòng)搜索精度，在進(jìn)行子像素搜索時(shí)，子像素預(yù)測樣本須通過插值運(yùn)算得到。AVS中視頻編碼采用1/2像素或1/4像素運(yùn)動(dòng)估計(jì)，提高運(yùn)動(dòng)搜索精度。其1/2像素和1/4像素預(yù)測樣本值均采用4抽頭濾波器進(jìn)行插值獲得^[2]。濾波系數(shù)分別為-1，5，5，-1和1，7，7，1。

AVS插值算法如圖1所示。其中大寫字母為整像素，小寫字母為1/2像素，其他位置為1/4像素。



1/2像素值通過一個(gè)4抽頭濾波器(-1，5，5，-1)計(jì)算得到。如圖1所示，e為水平方向1/2像素點(diǎn)，計(jì)算過程如下：

e=Clip1((e′+4)＜＜（3)(1)



其中間值e′ = -1*E+5*A+5*F-1*K。Clip函數(shù)在標(biāo)準(zhǔn)中的定義為

1/4像素值通過4抽頭濾波器(1，7，7，1)計(jì)算得到。1/4像素點(diǎn)預(yù)測樣本值的計(jì)算需要用到計(jì)算1/2像素值時(shí)的中間結(jié)果，計(jì)算較復(fù)雜^[1]。

1．2 子像素運(yùn)動(dòng)搜索算法

1．2．1 最優(yōu)運(yùn)動(dòng)矢量判別準(zhǔn)則

對于當(dāng)前模式的每個(gè)候選運(yùn)動(dòng)矢量，首先計(jì)算原始塊與運(yùn)動(dòng)矢量對應(yīng)的預(yù)測塊亮度值之差；然后根據(jù)得到的殘差矩陣元素絕對值和(sum of absolute difference， SAD)按照式（3）計(jì)算代價(jià)，即

其中：f0(x，y)和 fp(x，y)分別表示原始像素值和預(yù)測像素值； x和 y表示當(dāng)前m×n塊左上角元素坐標(biāo)；m和n分別為16或8；MV_COST為運(yùn)動(dòng)矢量的代價(jià)函數(shù)；lam bda是與QP有關(guān)的參數(shù)；mv是當(dāng)前搜索塊的運(yùn)動(dòng)矢量。

最終選擇代價(jià)最小的運(yùn)動(dòng)矢量作為當(dāng)前模式的最優(yōu)運(yùn)動(dòng)矢量。

1．2．2 AVS子像素運(yùn)動(dòng)搜索過程

a) 根據(jù)預(yù)測運(yùn)動(dòng)矢量搜索最優(yōu)整像素點(diǎn)周圍1/2像素點(diǎn)，比較它們的代價(jià) Cp大小。假設(shè)圖1中A點(diǎn)為最優(yōu)整像素點(diǎn)，則搜索其周圍的八個(gè)1/2像素點(diǎn)a、b、c、d、e、f、g、h，找出計(jì)算代價(jià) Cp最小的像素點(diǎn)。如果最優(yōu)點(diǎn)仍為整像素點(diǎn)A，轉(zhuǎn)到b)，否則轉(zhuǎn)到c)。

b) 搜索整像素點(diǎn)周圍的八個(gè)1/4像素點(diǎn)，得到它們的 Cp，找出 Cp最小的像素點(diǎn)，退出搜索。

c) 搜索1/2像素點(diǎn)周圍的八個(gè)1/4像素點(diǎn)。如圖1所示：假設(shè)點(diǎn)b是最優(yōu)的1/2像素點(diǎn)，則搜索其周圍aa、bb、cc、dd、ee、ff、gg、hh這八個(gè)1/4像素點(diǎn)，比較 Cp，找到 Cp最小的像素點(diǎn)，退出搜索。

2 雙線性插值和快速子像素搜索算法

AVS子像素的運(yùn)動(dòng)搜索算法復(fù)雜度很高，需要進(jìn)行大量的乘法、加法、比較和移位運(yùn)算，對于處理能力有限的DSP來說，要進(jìn)行實(shí)時(shí)編碼將存在一定的難度。這里提出了一種快速子像素運(yùn)動(dòng)搜索算法，有效地降低了計(jì)算復(fù)雜度。快速算法包括兩個(gè)步驟：雙線性插值；快速子像素搜索算法。運(yùn)動(dòng)補(bǔ)償時(shí)仍采用AVS標(biāo)準(zhǔn)中的插值算法。

2．1 雙線性插值

充分考慮DSP的處理能力和資源限制，在進(jìn)行子像素搜索時(shí)，子像素的預(yù)測樣本采用了現(xiàn)場插值方式，用雙線性插值代替了AVS標(biāo)準(zhǔn)中的插值算法，雙線性插值的計(jì)算過程中僅用加法和移位操作計(jì)算子像素的值^[3]，大大降低了算法的復(fù)雜度，而運(yùn)動(dòng)補(bǔ)償則按照標(biāo)準(zhǔn)的子像素插值進(jìn)行計(jì)算。

雙線性插值算法原理：

 a) 1/2樣本點(diǎn)的插值過程

設(shè)圖1所示點(diǎn)A為最優(yōu)整像素點(diǎn)，其周圍八個(gè)1/2樣本點(diǎn)通過整像素點(diǎn)A和另一個(gè)距插值點(diǎn)最近的整像素點(diǎn)插值得到，即a = (A+B+1)/2， b = (A+C+1)/2，c = (A+D+1)/2， d = (A+E+1)/2，e = (A+F+1)/2， f = (A+G+1)/2， g = (A+H+1)/2，h = (A+I+1)/2。其中:B、C、D、E、F、G、H、I為其鄰近的整像素點(diǎn)；a、b、c、d、e、f、g、h為整像素點(diǎn)A周圍的1/2像素點(diǎn)。搜索1/2像素點(diǎn)，如果1/2像素點(diǎn)為最優(yōu)點(diǎn)，則進(jìn)行1/4像素點(diǎn)的插值。

b) 1/4樣本點(diǎn)的插值過程

設(shè)圖1所示點(diǎn)b為最優(yōu)1/2樣本點(diǎn)，則它周圍的1/4樣本點(diǎn)根據(jù)點(diǎn)b插值得到，即aa = (b+m+1)/2，bb = (b+C+1)/2，cc = (b+i+1)/2，dd = (b+a+1)/2，ee = (b+c+1)/2，ff = (b+d+1)/2，gg = (b+A+1)/2，hh = (b+e+1)/2。其中:A、C為其鄰近的整像素點(diǎn)；a、c、d、e、m、i為b子像素點(diǎn)周圍的1/2樣本點(diǎn)；aa、bb、cc、dd、ee、ff、gg、hh為通過雙線性插值得到的1/4樣本點(diǎn)的值。

如在1/2像素搜索過程中，整像素點(diǎn)A仍然是最優(yōu)點(diǎn)，則其周圍的1/4像素點(diǎn)根據(jù)整像素點(diǎn)A插值得到，即ff = (A+a+1)/2，gg = (A+b+1)/2，hh = (A+c+1)/2，jj = (A+d+1)/2，ii = (A+e+1)/2，kk = (A+f+1)/2，ll = (A+g+1)/2，nn = (A+h+1)/2。其中:a、b、c、d、e、f、g、h為1/2像素點(diǎn)。

通過上述算法描述可知，每個(gè)子像素點(diǎn)的值只需要進(jìn)行兩次加法和一次移位操作即可得到。

2．2 快速子像素搜索算法

由于子像素運(yùn)動(dòng)搜索^[4~6]的復(fù)雜度較高，對于嵌入式系統(tǒng)而言實(shí)現(xiàn)實(shí)時(shí)編碼存在很大難度。這里設(shè)計(jì)一種快速子像素運(yùn)動(dòng)搜索算法，步驟如下：

a) 設(shè)圖1所示點(diǎn)A為最優(yōu)整像素點(diǎn)，則搜索整像素點(diǎn)A周圍的b、d、e、g這四個(gè)1/2像素點(diǎn)，分別計(jì)算它們代價(jià) Cp。其中 Cp的計(jì)算如式 (3)所示。比較包括整像素在內(nèi)的五個(gè)像素點(diǎn)的代價(jià)值，如果整像素仍是最優(yōu)點(diǎn)，轉(zhuǎn)到b)，否則轉(zhuǎn)到c)。

b) 搜索整像素點(diǎn)A和a)中次優(yōu)的1/2子像素點(diǎn)之間的1/4像素點(diǎn)。設(shè)b為次優(yōu)1/2像素點(diǎn)，則搜索的1/4像素點(diǎn)分別為ff、gg、hh，比較這三個(gè)1/4像素點(diǎn)與整像素點(diǎn)A的代價(jià)值，找出最優(yōu)像素點(diǎn)，退出搜索。

c) 取a)搜索中代價(jià)最小的1/2像素點(diǎn)，搜索離此像素點(diǎn)最近的兩個(gè)1/2像素點(diǎn)。比較這三個(gè)像素點(diǎn)的代價(jià)值，找出代價(jià)最小的1/2像素點(diǎn)，轉(zhuǎn)到d)。

d) 根據(jù)c)搜索得到的代價(jià)最小1/2像素點(diǎn)，搜索此像素點(diǎn)和a)中點(diǎn)A之間的1/4像素點(diǎn)。設(shè)圖1中點(diǎn)a為搜索到的代價(jià)計(jì)算最小1/2像素點(diǎn)，則開始搜索它們之間的jj、ff、gg這三個(gè)1/4像素點(diǎn)，比較它們的代價(jià)值 Cp (包括最優(yōu)1/2像素點(diǎn))，找出計(jì)算代價(jià) Cp最小的像素點(diǎn)，退出搜索。

3 實(shí)驗(yàn)結(jié)果和分析

3．1 計(jì)算復(fù)雜性

 該算法主要對AVS編碼的子像素運(yùn)動(dòng)搜索進(jìn)行改進(jìn)。在子像素運(yùn)動(dòng)搜索過程中，子像素的預(yù)測樣本值采用雙線性插值得到，在運(yùn)動(dòng)補(bǔ)償時(shí)才選用原始的插值方法。

表1給出了每個(gè)編碼塊在子像素運(yùn)動(dòng)搜索最好的情況和最壞情況下的搜索次數(shù)比較。

從表1可以看出，快速算法的搜索次數(shù)只有原算法搜索次數(shù)的40%~60%。如果搜索結(jié)果為整像素點(diǎn)，則運(yùn)動(dòng)補(bǔ)償時(shí)無須再插值；如果為1/2像素點(diǎn)，則只要按照原始算法進(jìn)行1/2像素插值；最壞的情況下，為1/4像素點(diǎn)，也只需要進(jìn)行部分1/2像素點(diǎn)和1/4像素點(diǎn)的插值。而子像素預(yù)測樣本值通過雙線性插值時(shí)，每個(gè)子像素點(diǎn)只要兩次加法和一次移位即可計(jì)算出，而采用原始插值時(shí)每個(gè)子像素樣本值需要四次乘法、四次加法、二次比較和一次移位操作才可以獲得。因此，本文的快速子像素運(yùn)動(dòng)搜索算法大大減少了計(jì)算量，而在性能上與原始算法相當(dāng)。

3．2 編碼性能

實(shí)驗(yàn)中采用了AVS標(biāo)準(zhǔn)提供的參考軟件rm52i作為實(shí)驗(yàn)平臺。其中編碼參數(shù)配置：視頻格式為CIF，參考幀數(shù)為一幀，開啟RDO(率失真)，編碼序列格式為IPPPP……，I，P幀量化參數(shù)均分別28、30和32，編碼300幀。視頻序列選擇了hall_cif、substation、cross_street這三個(gè)序列。表2列出了參考代碼和本文采用的快速算法編碼的性能比較結(jié)果。



表2中的快速算法分為A和B兩種。其中：A算法是在AVS標(biāo)準(zhǔn)提供的rm52i編碼器中僅加入雙線性插值；B算法是在rm52i編碼器中加入雙線性插值和子像素的快速搜索算法。從表2的實(shí)驗(yàn)結(jié)果可以看出，快速算法相比原算法平均碼長增長了5%~7%，峰值的信噪比下降了0．2~0．5 dB，平均搜索次數(shù)減少了40%~50%。

圖2給出了兩種算法在QP為28時(shí)編碼后解碼的圖像。可以看出，兩者的主觀質(zhì)量相當(dāng)，而快速算法復(fù)雜度較原算法有大幅下降，降低了硬件實(shí)現(xiàn)難度，有利于在DSP上的實(shí)現(xiàn)。

4 結(jié)束語

針對AVS在DSP應(yīng)用中存在的運(yùn)動(dòng)搜索計(jì)算復(fù)雜、存儲量大等不足，本文提出了一種新的基于雙線性插值的快速子像素運(yùn)動(dòng)搜索算法，大大降低了算法復(fù)雜度。實(shí)驗(yàn)結(jié)果證明，該算法在保證編碼性能的前提下能有效提高編碼速度，降低算法復(fù)雜度，對圖像的質(zhì)量影響很小，適合基于DSP硬件平臺實(shí)時(shí)AVS視頻編碼。該算法已成功應(yīng)用到基于AVS編碼的TI TMS320DM642 [7，8]硬件平臺實(shí)時(shí)視頻監(jiān)控系統(tǒng)中。在其他嵌入式系統(tǒng)平臺的實(shí)時(shí)視頻監(jiān)控中，也具有很強(qiáng)的實(shí)用性。

參考文獻(xiàn)：

［1］Audio Video Coding Standard Workgroup of China. Information technology - advanced coding of audio and video-part 2: video (Draft) [S].2006.

[2]嚴(yán)明，胡國榮.AVS視頻標(biāo)準(zhǔn)中的分像素插值算法設(shè)計(jì)[J].中國傳媒大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，13(4)：44-48.

[3]方延龍，周軍.H.264的分?jǐn)?shù)像素內(nèi)插的快速算法[J].計(jì)算機(jī)工程，2006，32(1):218-223.

[4]LIU Long ，HAN Chong-zhao ，BAI Yan.A new adaptive fast motion estimation algorithm based on local motion similarity degree (LMSD) [J].Progress in Natural Science，2005，15(12):1126-1134.

[5]ZHU Shan，MA K K.A new diamond search algorithm for fast block-matching motion estimation [J].IEEE Trans on Image Processing，2000，9(2):287- 290.

[6]ZHU C，LIN X，CHAU L P.Hexagon-based search pattern for fast block motion estimation[J].IEEE Trans on Circuits and Systems for Video Technology，2002，12(5):349-355.

[7]TI.TMS320DM642 video/imaging fixed-point digital signal processor[R].2002.

[8]TI.Image processing example using the TMS320C64x image/video processing library(IMGLIB) [R].2003.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”