內(nèi)容自適應的低復雜度多參考幀快速選擇算法

金智鵬，佟樹成，羅 錚，王利華

(1.嘉興職業(yè)技術學院信息技術分院，浙江嘉興314036;2.中國(嘉興)微軟技術研究中心，浙江嘉興314000)

移動技術的不斷發(fā)展和廣闊的市場需求，為移動視頻業(yè)務的快速發(fā)展提供了必要條件，并使其成為移動運營商、設備制造商和內(nèi)容提供商關注的焦點之一。目前，移動端尤其是手機端已經(jīng)成為主流視頻屏幕之一;預計到2015年，手機端的視頻用戶規(guī)模將與PC端相當，這必將促進視頻行業(yè)的新一輪爆發(fā)。

H.264/AVC是由ISO/IEC與ITU-T聯(lián)合制定的新一代國際視頻編碼標準，具有較高的圖像質(zhì)量、較強的抗誤碼性和良好的網(wǎng)絡親和性，非常適合于有丟包和抖動的無線信道［1］。H.264目前已廣泛地應用在視頻通信、移動通信、數(shù)字廣播和流媒體等領域。

H.264的多參考幀運動估計技術是其編碼器中最耗時的模塊，且編碼復雜度與參考幀數(shù)量呈現(xiàn)線性增長關系［2］，這給移動終端硬件設備的處理能力、內(nèi)存空間和電池容量等帶來了巨大挑戰(zhàn)。因此，研究相應的快速算法加快編碼器的計算速度勢在必行。

1 H.264多參考幀選擇算法分析

1.1 現(xiàn)有算法分析

為降低多參考幀運動估計補償?shù)挠嬎懔浚岣呔幋a實時性，國內(nèi)外學者提出了許多快速算法。常用的多參考幀快速選擇算法總體上可以分成以下兩類:

第一類是參考幀預測法，即根據(jù)一定的策略，跳過可能性較小的參考幀，以此提高多參考幀運動估計的速度。例如利用視頻序列的時域相關性，文獻［3］根據(jù)前2幀中Skip模式的占比來確定參考幀數(shù)目;文獻［4］根據(jù)前5幀中最優(yōu)參考幀的選用情況來確定當前編碼塊的參考幀數(shù)目。文獻［5］用Sobel算子進行邊緣梯度檢測，并結(jié)合運動矢量最大值和差值的分布情況，確定候選參考幀集合。在文獻［6］中，對于宏塊級編碼，根據(jù)已編碼幀中Skip模式和16×16模式的占比來確定參考幀數(shù)目;對亞宏塊級編碼，則跟據(jù)運動矢量的相關性來確定的參考幀數(shù)目。文獻［7］根據(jù)先前參考幀的運動矢量信息，判斷是否使用各個參考幀。在這類算法中，如果塊之間的相關性不強，會導致最優(yōu)參考幀的誤判，且這個錯誤有可能被不斷傳播，影響編碼R-D(Rate-Distortion)性能。

第二類是預測運動矢量法，即根據(jù)一定的策略，通過時空相鄰塊的運動矢量預測各個參考幀的初始運動矢量，減少花費在每個參考幀上的搜索時間。例如文獻［8］分析了多參考幀效率和視頻對象運動幅度之間的關系，對快速運動塊和平緩運動塊分別采用不同的搜索策略，并建立了基于哈達瑪變換系數(shù)的提前終止條件。文獻［9］根據(jù)多參考幀下運動矢量的中心偏置特性，預測各個參考幀的初始運動矢量，并結(jié)合快速運動估計算法降低計算量。文獻［10］首先對運動矢量進行中值濾波，然后使用處理后的運動矢量擴展出一個新的參考幀，最后將新的參考幀插入到參考幀列表中進行運動估計，提升了編碼質(zhì)量。文獻［11］根據(jù)不同參考幀之間的預測運動矢量，選擇空間上最接近的候選參考幀。在這類算法中，對遮擋顯露等情況，運動矢量的預測精度較難把握，影響編碼R-D性能。

1.2 多參考幀選擇依據(jù)

在H.264中，每一個幀間預測編碼宏塊最多可支持16個參考幀、10種預測編碼模式(Skip模式、16×16、16×8、8×16、8 ×8、8 ×4、4 ×8、4 ×4、intra16 ×16、intra4 ×4)。為找出基于率失真代價(Rate Distortion Optimization，RDO)的最優(yōu)參考幀，JM校驗模型在運動估計過程中采用遍歷所有參考幀的方法，并選擇代價最小的參考幀作為最優(yōu)參考幀。H.264中參考幀選擇的率失真代價函數(shù)定義如下

式中:J(mv，ref)表示率失真代價;SAD表示當前塊與參考塊的絕對差;S表示當前編碼宏塊的像素值;C(mv，ref)表示參考塊的像素值;ref為當前參考幀序號;mv表示該參考幀的運動矢量;Rmv和Rref分別表示運動矢量和參考幀序號的編碼比特數(shù);λ為拉格朗日參數(shù)，其值與量化系數(shù)有關。這種遍歷計算所有候選參考幀的J(mv，ref)，進而得到率失真意義上的最優(yōu)參考幀的方法，給編碼器帶來了巨大的計算量。

1.3 最優(yōu)參考幀分布情況分析

表1是各標準測試序列在16×16模式和亞宏塊級模式下的最優(yōu)參考幀采用情況統(tǒng)計表，本文數(shù)據(jù)是在H.264的JM86測試平臺上進行100幀編碼統(tǒng)計的結(jié)果，表1選用5個參考幀，量化參數(shù)QP=28。圖1是多參考幀的運動估計補償示意圖，其中ref0～n是指最優(yōu)參考幀的序號，ref0最近，refn最遠。表1的數(shù)據(jù)說明絕大多數(shù)編碼塊僅僅需要最臨近的1個參考幀就可以獲得最好的編碼效果，其余的參考幀均被浪費了，沒有起到提升編碼R-D性能的作用。

表1 最優(yōu)參考幀采用率統(tǒng)計

圖1 運動估計的多參考幀預測

1.4 時空相鄰區(qū)域的相關性分析

本文對最優(yōu)參考幀的相關性情況進行了100幀的編碼統(tǒng)計，如表2所示。表2中，“時域”指當前塊與前一幀對應位置塊最優(yōu)參考幀的相關性統(tǒng)計，“空域”指當前塊與同幀中相鄰塊的相關性統(tǒng)計，其位置關系可以參考圖2的位置關系說明。圖2中M指當前編碼塊，E指前一幀中與M對應位置的塊，A指M的左邊相鄰塊，B、C、D分別指M的左上邊、上邊和右上邊相鄰塊。

表2 最優(yōu)參考幀的時空相關性統(tǒng)計 %

從表2的統(tǒng)計數(shù)據(jù)可以看出，時空相鄰塊的最優(yōu)參考幀具有很強的相關性。而且，亞宏塊級模式編碼時，塊之間的空域相關性要明顯高于時域相關性;16×16模式編碼時，前后幀之間的時域相關性要高于幀內(nèi)空域相關性。這是因為上下左右相鄰的小尺寸塊很有可能屬于同一對象，它們選用同一參考幀的概率更大;而大尺寸編碼塊往往屬于背景區(qū)或紋理平滑區(qū)，前后幀之間的相關性更高，選其前一時刻已編碼幀作為最優(yōu)參考幀的可能性更大。利用這個特性，可以根據(jù)已編碼塊的最優(yōu)參考幀選用情況，對當前塊的最優(yōu)參考幀進行預測與篩選，從而提高編碼速度。

圖2 時空相鄰塊的位置關系圖

1.5 各編碼模式的采用率分析

本文對幀間編碼模式的采用情況也進行了100幀的編碼統(tǒng)計，如表3所示。根據(jù)統(tǒng)計結(jié)果，Skip模式的使用概率最高(使用 ref0作為參考幀)，宏塊級(16×16，16×8，8×16)編碼模式的采用率要遠高于亞宏塊級模式(8×8，8×4，4×8，4×4)，而采用幀內(nèi)編碼模式的概率極低。由于本文算法主要針對移動終端小尺寸圖像的應用場合，摒棄幀間編碼中的幀內(nèi)模式以提高編碼速度，對編碼質(zhì)量不會產(chǎn)生大的影響。此外，在進行參考幀的比較選擇時，由于亞宏塊級編碼模式的采用率較低，可以適當控制計算量的分配;而宏塊級編碼模式的采用率較高，應保留更多的計算量，從而在編碼質(zhì)量與速度之間達到一個較好的平衡。

表3 各編碼模式的采用率統(tǒng)計 %

2 自適應的多參考幀快速選擇算法

2.1 候選模式選擇策略

根據(jù)表2最優(yōu)參考幀的時空相關性統(tǒng)計結(jié)果，在進行宏塊級模式編碼時，前后幀之間的時域相關性都要高于幀內(nèi)相鄰塊間的空域相關性。因此，本文通過統(tǒng)計前一幀中對應位置塊的參考幀選用情況來確定當前編碼塊的候選參考幀集合。在進行亞宏塊級模式編碼時，幀內(nèi)相鄰塊之間的空域相關性明顯強于幀間的時域相關性。因此，本文候選參考幀集合的構(gòu)成如下

式中:Ref1表示宏塊級編碼時確定的初步候選參考幀集合1;Ref2表示亞宏塊級編碼時，各8×8子塊初步確定的候選參考幀集合2。由于H.264中的參考幀以8×8為單位進行分配和保存，因此宏塊級的16×16模式最多可以有4個初步候選參考幀。而對于亞宏塊級模式，同一個8×8子塊的各個更小分割塊(如8×4、4×8、4×4模式)只能指向同一個參考幀。

2.2 參考幀擴展選擇策略

多參考幀技術所獲得的編碼增益并非簡單依賴于參考幀數(shù)目的多少，而是取決于視頻內(nèi)容的本質(zhì)特征。在一些特殊情況下，例如在對象發(fā)生遮擋和顯露時，對象周期性運動時，或發(fā)生場景切換時，遠端參考幀被選為最優(yōu)參考幀的概率更大。因此，本文定義一個參考幀范圍的擴展條件

參考幀擴展條件

式中:表示候選參考幀集合的最小代價值;Jx(x∈A，B，C，D，E)表示時空相鄰塊的最優(yōu)參考幀代價;兩個參數(shù)用于進行計算量的分配控制。根據(jù)1.4節(jié)的統(tǒng)計分析和編碼實踐，本文設置α=0.75，β=1.2。如果當前塊滿足擴展條件，則認為當前參考幀的補償結(jié)果并不理想，需要通過對更多參考幀進行搜索，以求得更為準確的運動補償，防止這些塊編碼質(zhì)量的降低和可能導致的錯誤傳播。若不滿足擴展條件，則根據(jù)式(2)，直接從候選參考幀集合中確定最優(yōu)參考幀。

2.3 本文快速參考幀選擇算法流程

本文算法專門針對多參考幀選擇模塊進行研究，算法通用性強。本文算法具體編碼過程描述如下(見圖3):

1)當進行宏塊級編碼時，依據(jù)時域相關性確定當前編碼塊的候選參考幀集合1，見式(2)。進行集合1的運動估計補償，求得初步最優(yōu)參考幀和最小代價。

2)宏塊級參考幀擴展條件判斷。如果不滿足式(3)，則說明不需要擴展搜索，直接進入到亞宏塊級的編碼。如果需要擴展搜索，則將候選參考幀范圍擴展至余下的全部參考幀，并根據(jù)最小代價確定編碼塊的最優(yōu)參考幀。

3)當進行亞宏塊級各8×8子塊的編碼時，依據(jù)空域相關性確定當前編碼塊的候選參考幀集合2，見式(2)。進行集合2的運動估計補償，求得各8×8子塊的初步最優(yōu)參考幀和最小代價。

4)亞宏塊級參考幀擴展條件判斷。如果不滿足式(3)，則說明不需要擴展搜索，當前子塊的最優(yōu)參考幀選擇結(jié)束。如果需要擴展，則按參考幀序號逐個擴展搜索;一旦發(fā)現(xiàn)，則結(jié)束擴展搜索，選取對應的參考幀為各子塊的最優(yōu)參考幀。

圖3 本文快速參考幀選擇算法流程圖

3 實驗結(jié)果及數(shù)據(jù)分析

為了測試分析算法的綜合性能，本文從編碼時間(Time)、峰值信噪比(PSNR)、碼率(Rate)等幾個方面進行測試比較。實驗參考軟件為H.264的JM86基本檔(baseline)，編碼器主要參數(shù)設置為:幀率30 f/s(幀/秒)，幀結(jié)構(gòu)為IPPP，采用JM默認的運動估計算法，QCIF序列的搜索范圍為±16，CIF序列為±32，5個參考幀，采用RDO優(yōu)化，CAVLC編碼。實驗平臺為:CPU為奔4雙核3 GHz，2 Gbyte內(nèi)存，Windows XP操作系統(tǒng)。

為了對算法性能進行客觀比較，本文對不同畫幅和運動類型的多個標準測試序列進行了測試，每個序列編碼前100幀，編碼結(jié)果如表4所示，其中QP=28。各項編碼性能指標的變化幅度定義如下

式中:PSNRproposed和PSNRJM分別指本文快速算法和JM86標準算法的編碼峰值信噪比;ΔTime指編碼時間的變化幅度，-Δ表示快速算法降低了編碼時間;ΔRate指碼率的變化情況，+Δ表示快速算法的碼率有增加。

從表4可以看出，與采用所有參考幀遍歷搜索的JM標準相比，本文提出的多參考幀快速選擇算法可以大幅降低計算量，平均可降低49.12%的編碼時間。與此同時，碼率平均僅增加0.28%，圖像質(zhì)量的損失平均為0.02 dB，這樣的損失對編碼R-D性能的影響是微不足道的，對畫面視覺質(zhì)量的影響基本可以忽略。

表4 本文算法性能以及和H.264標準算法的對比

表5和表6是本文快速算法與其他幾種快速算法的性能對比。其中，文獻［3］根據(jù)空間相關性確定參考幀數(shù)目;文獻［4］利用時空相關性確定當前宏塊的編碼模式及參考幀數(shù)目;文獻［5］根據(jù)邊緣梯度檢測以及運動矢量差值情況來確定候選參考幀;文獻［9］根據(jù)運動矢量中心偏置特性，結(jié)合快速運動估計算法來減少每個參考幀的計算量。

表5 各快速算法的性能對比(CIF，QP=28)

表6 各快速算法的性能對比(QCIF，QP=28)

根據(jù)表5和表6的數(shù)據(jù)對比，本文快速算法的圖像質(zhì)量PSNR和碼率都要明顯優(yōu)于其他算法，即本文算法的R-D性能明顯優(yōu)于其他快速算法。在計算量方面，本文算法大幅領先于文獻［9］和文獻［5］的算法，但是不及文獻［4］和文獻［3］。這主要是因為文獻［4］的算法中加入了編碼模式的預判;而文獻［3］的算法中加入了Skip模式的快速確定。但本文算法是純粹的多參考幀快速選擇算法，能與其他類型的快速算法(例如快速模式選擇、快速運動估計等)結(jié)合，這將能獲得更好的編碼速度。

4 小結(jié)

根據(jù)移動視頻業(yè)務的要求，針對多參考幀預測技術計算

[9] LIN CY，CHANG S F.Semi-fragile watermarking for authenticating JPEG visual content[C]//Proc.SPIE Security and Watermarking of Multimedia Content II.San Jose，CA：[s.n.]，2000：140-151.

[10] HO A T S，ZHU X，GUAN Y.Image content authentication using pinned sine transform[J].EURASIP Journal on Applied Signal Processing，2004（14）：2174-2184.

[11] 胡玉平，陳志剛.用于圖像認證的小波域半易損水印算法[J].電子學報，2006，34（4）：653-657.

[12]MATRO K，SUN Q，CHANG S，et al.New semi-fragile image authentication watermarking techniques using random bias and nonuniform quantization[J].IEEE Trans.Multimedia，2006，8（1）：32-45.

[13] TSAI M J，CHIEN C C.Authentication and recovery for wavelet based semi-fragile watermarking[J].Optical Engineering，2008，47（6）：1-10.

[14] 高鐵杠，譚琳，曹雁軍.基于Hash函數(shù)和漢明碼的半脆弱水印算法[J].光電子·激光，2012，23（9）：1808-1814.

[15]CHANG CC，CHEN K N，LEE C F，et al.A secure fragile watermarking scheme based on chaos-and-hamming code[J].Journal of Systems and Software，2011，84（9）：1462-1470.

[16] 陶孟益，唐軍，楊恒伏，等.基于自適應半脆弱水印的圖像篡改檢測方案[J].電視技術，2014，38（15）：41-43.