基于空域特征的H.264快速多參考幀選擇算法

徐靜，周兵，黃雪莉，李煒，曹蕾

（1.鄭州大學(xué) 信息工程學(xué)院 河南省高等學(xué)校信息網(wǎng)絡(luò)重點(diǎn)學(xué)科開(kāi)放實(shí)驗(yàn)室，河南 鄭州 450052；2.北京航空航天大學(xué) 計(jì)算機(jī)學(xué)院，北京100083）

1 引言

新一代視頻編碼國(guó)際標(biāo)準(zhǔn) H.264[1]采用了眾多先進(jìn)的編碼技術(shù)，如：幀內(nèi)預(yù)測(cè)、四分之一像素運(yùn)動(dòng)補(bǔ)償和多參考幀等，使其在相同圖像質(zhì)量下，編碼效率比MPEG-2、MPEG-4和H.263分別提高了64.46%、38.62%和48.80%[2]，但在這些新技術(shù)提高H.264/AVC性能的同時(shí)，也大幅度增加了編碼器的計(jì)算復(fù)雜度。特別是H.264現(xiàn)有的多參考幀預(yù)測(cè)算法需要對(duì)每個(gè)宏塊遍歷n（從1至16）個(gè)參考幀并計(jì)算各模式下的率失真代價(jià)，此外還需要進(jìn)行運(yùn)動(dòng)估計(jì)、多方向幀內(nèi)預(yù)測(cè)，所以整個(gè)多參考幀預(yù)測(cè)過(guò)程十分耗時(shí)。

為使H.264能夠更廣泛地實(shí)時(shí)應(yīng)用于現(xiàn)有的硬軟件條件下，降低多參考幀技術(shù)帶來(lái)的時(shí)間和空間上的高復(fù)雜度，許多快速算法[3～11]被提出。這些快速算法可分為3種：第1種是基于3D[5,6]運(yùn)動(dòng)估計(jì)的快速算法，即從當(dāng)前幀及其多個(gè)參考幀中建立三維數(shù)學(xué)模型，將搜索點(diǎn)從傳統(tǒng) 2D的簡(jiǎn)單平移擴(kuò)展到 3D空間，但這種技術(shù)需要大規(guī)模的多參考幀存儲(chǔ)操作；第2種基于多參考幀運(yùn)動(dòng)矢量預(yù)測(cè)[7,8]的快速算法，由于每一幀的MV均是由最近參考幀的MV所產(chǎn)生，所以對(duì)參考幀的MV精度要求較高，且這類方法不適用于快速搜索算法；第 3種是多參考幀選擇技術(shù)[9～11]，可直接應(yīng)用于現(xiàn)有的搜索算法中，但選擇參考幀的過(guò)程需要一些額外的計(jì)算量。

本文提出一種基于空間特性的H.264快速多參考幀選擇算法。該算法首先利用自然視頻序列的空間特性，根據(jù)相鄰宏塊Skip編碼模式信息在運(yùn)動(dòng)估計(jì)之前判斷當(dāng)前宏塊是否為Skip編碼模式；然后對(duì)視頻序列Skip編碼模式的占用率進(jìn)行統(tǒng)計(jì)和分析，設(shè)置多模式下參考幀數(shù)量的分布。實(shí)驗(yàn)結(jié)果表明，該算法將性能損失控制在可忽略范圍內(nèi)的情況下，可節(jié)約35%～87%的編碼時(shí)間。

2 H.264快速多參考幀選擇算法

如圖1所示本算法共分為3個(gè)步驟：第1步根據(jù)條件預(yù)測(cè)當(dāng)前宏塊是否為 Skip編碼模式；第 2步根據(jù)視頻空間特性以及宏塊編碼模式與量化參數(shù)值之間的關(guān)系進(jìn)行幀間模式選擇；第 3步統(tǒng)計(jì)Skip編碼模式宏塊在當(dāng)前幀中所占百分比，根據(jù)不同視頻模式設(shè)置合適的參考幀數(shù)量。

圖1 基于空間特性的快速多參考幀選擇算法框架

2.1 Skip模式的提前預(yù)測(cè)

由于在自然視頻序列中存在著大量空間上均勻平坦或時(shí)域靜止的區(qū)域，在這些區(qū)域中Skip編碼模式被大量的使用，所以如果在運(yùn)動(dòng)估計(jì)之前判斷出當(dāng)前宏塊是否為Skip編碼模式，便可極大地降低Skip編碼模式所占比例較大序列的編碼時(shí)間。

圖2的akiyo模式分布中淺色點(diǎn)所在的宏塊為 Skip模式，可見(jiàn)當(dāng)前宏塊的周圍鄰塊為 Skip編碼模式時(shí)，則其最終編碼模式為 Skip的概率高。因此，如果利用鄰塊信息在運(yùn)動(dòng)估計(jì)之前提前預(yù)測(cè)出一部分 Skip編碼模式則能更進(jìn)一步地提高編碼效率。由于當(dāng)前宏塊和其周圍相鄰宏塊存在空間相關(guān)性，在圖3若宏塊A、B、C和D均為Skip編碼模式，則E的編碼模式為Skip編碼的概率很大。

圖2 akiyo模式分布

圖3 宏塊空間相關(guān)圖

由文獻(xiàn)[12]可知，若一宏塊為Skip編碼模式，則該宏塊必須滿足以下4個(gè)條件：

1) 運(yùn)動(dòng)補(bǔ)償?shù)淖罴押陦K劃分為16×16；

2) 參考幀為當(dāng)前幀的前一幀；

3) 通過(guò)運(yùn)動(dòng)搜索得到的最佳運(yùn)動(dòng)矢量與通過(guò)預(yù)測(cè)得到的運(yùn)動(dòng)矢量相同；

4) 殘差經(jīng)過(guò)變換量化后均為0。

當(dāng)宏塊只滿足前3個(gè)條件時(shí)，此時(shí)的宏塊所采用的編碼模式為準(zhǔn) Skip編碼模式。由試驗(yàn)數(shù)據(jù)可知，當(dāng)周圍宏塊都為Skip或準(zhǔn)Skip模式時(shí)，盡管對(duì)運(yùn)動(dòng)緩慢紋理簡(jiǎn)單的序列能比較準(zhǔn)確地判斷出Skip模式；但對(duì)于運(yùn)動(dòng)復(fù)雜紋理豐富的序列而言，其誤判率最差情況達(dá)到63.221 9%，因此需要考慮條件4)來(lái)減少誤判率。滿足以上條件時(shí)，當(dāng)前宏塊編碼模式 M 為 Skip ，16×16，16×8，8×16，8×8，Intra4×4，Intra16×16在各視頻Seq中所占百分比數(shù)值見(jiàn)表1。

表1 當(dāng)前宏塊編碼模式的百分比

2.2 幀間模式選擇算法

由上節(jié)可知 Skip編碼模式在視頻序列的編碼過(guò)程中起著重要的作用，其所具有的特點(diǎn)不僅僅可運(yùn)用于運(yùn)動(dòng)估計(jì)之前也可運(yùn)用于運(yùn)動(dòng)估計(jì)的過(guò)程中，可縮小宏塊級(jí)模式的判斷范圍。本文通過(guò)實(shí)驗(yàn)數(shù)據(jù)分析表2中不同量化參數(shù)下的亞宏塊編碼模式分布，發(fā)現(xiàn)宏塊編碼模式與量化參數(shù)值之間的關(guān)系，即隨著量化參數(shù)的增加，P8×8模式在整個(gè)編碼模式中所占的比例越來(lái)越小；同時(shí)在P8×8模式中8×8模式所占的比例不斷增加，4×4模式所占的比例不斷減少，而8×4和4×8在P8×8種所占的比例變化不大。在量化參數(shù)較小的時(shí)候，亞宏塊的模式分布主要集中在{8×8，4×4}中，量化參數(shù)比較大時(shí)，主要集中在{8×8，8×4}中，當(dāng)量化參數(shù)取中等數(shù)值時(shí)，亞宏塊的模式分布主要集中在{8×8，8×4，4×8}中。根據(jù)這一實(shí)驗(yàn)現(xiàn)象將P8×8劃分成若干子集合，即{8×8，4×4}，{8×8，8×4，4×8}，{8×8，8×4}，分別對(duì)應(yīng)于不同程度的量化參數(shù)值。同時(shí)權(quán)衡到編碼速度，在中等量化參數(shù)情況下添加亞宏塊模式子集合{8×4，4×8}。本文對(duì)亞宏塊級(jí)模式進(jìn)行集合劃分，不同的量化參數(shù)值下的宏塊選擇不同的亞宏塊模式集合，縮小亞宏塊級(jí)模式判斷范圍。

表2 不同量化參數(shù)下的亞宏塊編碼模式分布

因此提出了一種快速幀間編碼模式選擇算法作為H.264快速多參考幀選擇算法中的一部分，流程描述如下：

step 1 設(shè)置當(dāng)前宏塊最終編碼模式為16×16，以16×16編碼模式進(jìn)行運(yùn)動(dòng)估計(jì)，計(jì)算率失真代價(jià)，并設(shè)置為最小代價(jià)；

step 2 判斷運(yùn)動(dòng)估計(jì)的結(jié)果是否滿足 2.1節(jié)中條件2)和3)，若不滿足，則轉(zhuǎn)入step 6；

step 3 設(shè)置最終編碼模式為16×16，對(duì)亮度和色度殘差進(jìn)行變換和量化；

step 4 判斷量化后的系數(shù)是否都為0（2.1節(jié)中條件4），若滿足最終編碼模式為Skip模式，否則轉(zhuǎn)入step 7；

step 5 對(duì)當(dāng)前宏塊進(jìn)行Intra16×16模式選擇，計(jì)算其率失真代價(jià)，與最小代價(jià)相比，取代價(jià)最小的模式為最終模式，同時(shí)更新最小代價(jià)，轉(zhuǎn)入step 9；

step 6 對(duì)當(dāng)前宏塊進(jìn)行16×8、8×16運(yùn)動(dòng)估計(jì)和率失真代價(jià)計(jì)算，與最小代價(jià)相比，取代價(jià)最小的模式為最終模式，同時(shí)更新最小代價(jià)；

step 7 若 qp≤24,對(duì)當(dāng)前宏塊進(jìn)行 8×8、4×4運(yùn)動(dòng)估計(jì)和率失真代價(jià)計(jì)算，若 24＜qp≤36，對(duì)當(dāng)前宏塊進(jìn)行8×4、4×8運(yùn)動(dòng)估計(jì)和率失真代價(jià)計(jì)算，若 qp＞36，對(duì)當(dāng)前宏塊進(jìn)行 8×8、8×4運(yùn)動(dòng)估計(jì)和率失真代價(jià)計(jì)算，與最小代價(jià)相比，取代價(jià)最小的模式為最終模式，同時(shí)更新最小代價(jià)；

step 8 對(duì)當(dāng)前宏塊進(jìn)行 Intra4×4、Intra16×16模式選擇和率失真代價(jià)計(jì)算，與最小代價(jià)相比，取代價(jià)最小模式為最終模式，同時(shí)更新最小代價(jià)；

step 9 為最終編碼模式進(jìn)行相應(yīng)的參數(shù)設(shè)置；

step 10 結(jié)束。

2.3 多參考幀選擇

在H.264中，可支持16個(gè)參考幀（一般設(shè)為5幀）、10種預(yù)測(cè)模式（16×16、8×16、16×8、8×8、4×8、8×4、4×4、intra4×4、intra16×16、Skip）。為找出最合適的參考幀，通常在整個(gè)運(yùn)動(dòng)估計(jì)過(guò)程是遍歷所有參考幀并計(jì)算搜索范圍內(nèi)每個(gè)宏塊的率失真值。

其中，s為當(dāng)前塊像素值，ref為要選擇的參考幀，mv為參考幀 ref的運(yùn)動(dòng)矢量，r(r ef,m v)為參考?jí)K的像素值，SAD(sum of absolute difference)為當(dāng)前塊與參考像素差值的絕對(duì)值和， λMOTION是Lagrange乘數(shù)因子，pred為預(yù)測(cè)矢量，R是宏塊編碼所需的比特?cái)?shù)，包括運(yùn)動(dòng)矢量與其預(yù)測(cè)值的差值編碼比特和參考幀的編碼比特。通過(guò)依次遍歷最近的參考幀1直到最遠(yuǎn)的參考幀 n各宏塊的 JMOTION(m v,ref|λMOTION)值，得到最佳參考幀能夠使得碼率與失真得到優(yōu)化，如圖4所示。

圖4 多參考幀預(yù)測(cè)過(guò)程

同單參考幀相比，多參考幀技術(shù)可有效提高圖像預(yù)測(cè)的精度。然而，多參考幀技術(shù)能在多大程度上提高編碼效率，以及使用多少個(gè)參考幀最合適，完全依賴視頻序列內(nèi)容的特性。實(shí)驗(yàn)發(fā)現(xiàn)，多參考幀技術(shù)的編碼增益主要來(lái)自宏塊內(nèi)子塊所使用不同的參考幀。表3和表4分別列出了量化參數(shù)為28的情況下，標(biāo)準(zhǔn)測(cè)試序列Seq在16×16模式及亞宏塊編碼模式下選擇最佳參考幀的分布情況，其中RF是指選擇的最佳參考幀的序號(hào)（從0（最近）到4（最遠(yuǎn)））。

表3 16×16模式各序列最佳參考幀的分布

表4 亞宏塊模式各序列最佳參考幀的分布

從表3和表4數(shù)據(jù)可知，對(duì)于運(yùn)動(dòng)平緩簡(jiǎn)單的序列其參考幀一般取比較臨近的參考幀，亞宏塊模式與16×16模式相比選擇較遠(yuǎn)參考幀的概率較大。由于參考幀的選擇由其自身所具有的視頻運(yùn)動(dòng)紋理特征確定，從表1數(shù)據(jù)分析可知，對(duì)于運(yùn)動(dòng)復(fù)雜、紋理豐富的視頻序列，其采用Skip編碼模式進(jìn)行編碼的宏塊相對(duì)較少；反之，對(duì)于運(yùn)動(dòng)緩慢、紋理簡(jiǎn)單的序列，其采用Skip編碼模式進(jìn)行編碼的宏塊相對(duì)較多。所以采用Skip模式在所有模式中所占比例大小代表視頻序列的特性是可行的。因此統(tǒng)計(jì)Skip編碼模式的分布，對(duì)于7種不同的編碼模式，可分配與之對(duì)應(yīng)的參考幀數(shù)量。算法描述見(jiàn)2.4節(jié)算法step 5和step 6。

2.4 快速算法流程

本文提出的快速幀間模式選擇算法首先在運(yùn)動(dòng)估計(jì)之前判斷該宏塊是否為Skip模式，然后在運(yùn)動(dòng)估計(jì)過(guò)程中運(yùn)用2.2節(jié)中提出的快速幀間編碼模式選擇算法，最后根據(jù)SKIP編碼模式的比例分配不同的參考幀數(shù)。算法中設(shè)16×16，16×8，8×16，8×8，8×4，4×8，4×4 這 7 種塊模式分別為 m1 至m7，其流程描述如下。

step1 進(jìn)入宏塊級(jí)編碼，宏塊默認(rèn)大小為16×16；

step2 判斷周圍已經(jīng)編碼的宏塊（左臨宏塊和上臨宏塊）是否均為Skip編碼模式或者準(zhǔn)Skip編碼模式，并且判斷當(dāng)前宏塊是否滿足2.1節(jié)2)、3)、4)條件，若不滿足，轉(zhuǎn)入 2.2節(jié)快速幀間編碼模式選擇算法；

step3 設(shè)置當(dāng)前宏塊的最終編碼模式為 Skip編碼模式，若該幀內(nèi)容沒(méi)有編完則轉(zhuǎn)入 step1繼續(xù)下一宏塊編碼，否則轉(zhuǎn)入step4；

step4 統(tǒng)計(jì)前2個(gè)P幀的Skip編碼模式的宏塊個(gè)數(shù)Skip_num；

其中,

step5 根據(jù)不同的模式，求出參考幀數(shù)量RF_num；

step6 若計(jì)時(shí)時(shí)鐘時(shí)間到，則更新 Skip編碼模式的統(tǒng)計(jì)分布，否則轉(zhuǎn)入 step1繼續(xù)下一幀的宏塊編碼。

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

為測(cè)試本文算法的實(shí)際性能，結(jié)合H.264/AVC的參考軟件JM10.2[13]進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)采用運(yùn)動(dòng)特征和紋理特征都不相同的標(biāo)準(zhǔn)測(cè)試序列 bus、mobile、foreman、container、silent和Mother的 CIF格式和QCIF格式的前100幀進(jìn)行測(cè)試。編碼器主要參數(shù)設(shè)置見(jiàn)表5。

表5 編碼器參數(shù)設(shè)置

圖 5是本文算法與全搜索算法客觀性能對(duì)比圖，表6中列出了本文算法和H.264編碼器JM10.2所采用的全模式搜索算法以及張淑芳等提出基于H.264的多參考幀快速選擇算法[9]（這里簡(jiǎn)稱Zhang算法）的編碼性能比較。表6中，比特率(kbit/s)選項(xiàng)中變化率1是指Zhang算法與JM10.2相比較的變化比率，變化率2是本文算法與JM10.2比較的變化比率，“—”表示參考文獻(xiàn)中沒(méi)有提及的項(xiàng)。如表6所示，本文的PSNR表示本文算法相對(duì)于全搜索算法，客觀性能略微下降，這是由于該算法Skip編碼模式覆蓋率增大造成的。從表6中可以看出，客觀性能損失與 JM10.2相比平均下降約為Δ0.07dB，但比Zhang算法提高0.41dB。從人眼視覺(jué)特性來(lái)看，當(dāng)圖像客觀性能的下降在Δ0.5dB以內(nèi)時(shí)，人的主觀感覺(jué)并不會(huì)有太大的變化。所以，本文算法造成的客觀性能下降因其幅度很小，不會(huì)影響到視頻的主觀視覺(jué)效果，如圖5所示，其PSNR和現(xiàn)有算法、全搜索算法非常接近。

圖5 客觀性能對(duì)比圖

同全搜索算法以及文獻(xiàn)[9]相比，本文算法在運(yùn)動(dòng)估計(jì)之前判斷Skip編碼模式，并根據(jù)Skip編碼覆蓋率對(duì)不同的幀間編碼模式選擇不同的多參考幀數(shù)目；同時(shí)本文算法能夠全面地覆蓋Skip模式宏塊，并隨著量化參數(shù)的增加使得Skip模式的覆蓋率增大，編碼節(jié)省的時(shí)間數(shù)值進(jìn)一步增大，多參考幀預(yù)測(cè)時(shí)間減少，可大幅度地降低編碼器復(fù)雜度，因此在編碼時(shí)間和比特率上比現(xiàn)有算法更具有優(yōu)勢(shì)。如圖6所示，針對(duì)運(yùn)動(dòng)緩慢紋理簡(jiǎn)單的視頻序列，如表6中silent_QCIF、container_CIF、ice_4CIF標(biāo)準(zhǔn)測(cè)試序列能使編碼器的時(shí)間開(kāi)銷平均降低75.69%、79.23%、87.63%，特別是針對(duì)相對(duì)靜止的視頻如silent_QCIF，由于silent_QCIF中的絕大部分宏塊的編碼模式均為Skip模式，因此不僅僅可以大幅降低編碼時(shí)間還能夠?qū)⒕幋a比特率降低47.21%；而針對(duì)運(yùn)動(dòng)劇烈紋理復(fù)雜的序列，如表6中 mobile_CIF標(biāo)準(zhǔn)測(cè)試序列本文算法也比現(xiàn)有算法更能明顯提高編碼效率。

表6 本文算法與全搜索算法編碼性能比較

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

本文分析了幾類具有代表性自然視頻的特性，根據(jù)H.264標(biāo)準(zhǔn)要求，提出一種多參考幀選擇快速算法，在保證H.264編碼質(zhì)量的同時(shí)明顯提高了編碼器的編碼效率。該算法不但適于運(yùn)動(dòng)緩慢、紋理簡(jiǎn)單的CIF、QCIF、4CIF視頻序列，而且適于運(yùn)動(dòng)劇烈、紋理復(fù)雜的CIF、QCIF、4CIF視頻序列。此外，該算法雖然對(duì)于不同的編碼模式分配的參考幀數(shù)量是由幾類代表性視頻序列實(shí)驗(yàn)得出，但其結(jié)論對(duì)不同尺寸的一般自然視頻同樣有效。

[1] ITU-T Recommendation and Final Draft International Standard of Joint Video Specification[S].(ITU-T Rec H.264 | ISO/IEC 14496-10 AVC),2003.

[2] SCHAFER R,WIEGAND T,SCHWARZ H.The Emerging H.264/AVC Standard[S].EBU Technical Review,2003.

[3] GAN Z L,ZHU X C.Novel multi-frame fast motion search algorithm based on H.264[J].Journal of Communications,2007,28(1):17-21.

[4] CHEN Y P,ZHANG P R,SUN Y,et al.One low complex reference picture selection optimal method[J].Journal of Electronics and Information Technology,2007,29(4):967-970.

[5] TING C W,LAM W H,PO L M,Fast block-matching motion estimation by recent-biased search for multiple reference frames[A].Proc IEEE Int Conf on Image Processing[C].2004.1445-1448.

[6] PU J H,XIONG Z,LIU Y L.Fast motion estimation algorithm for H.264 with multi-references[J].Journal of Beijing University of Aeronautics and Astronautics,2006,32(5): 617-620.

[7] QIAO R,DONG X C,TANG H Y,et al.Fast motion estimation and inter-frame mode selection algorithm based on H.264 encoding[J].Journal of Xihua University(Natural Science Edition),2008,27(4):13-17.

[8] CHEN M J,CHIANG Y Y,LI H J,et al.Efficient multi-frame motion estimation algorithms for MPEG-4/AVC/JVT/H.264[A].Proc IEEE Int Symp on Circuits and Systems[C].2004.737-740.

[9] ZHANG S F,LI H.A Multi-reference frames fast selection algorithm for H.264[J].Acta Elecironica Sinica,2009,37(1):62-66.

[10] TING C W,PO L M,CHEUNG C H.Center biased frame selection algorithms for fast multi-frame motion estimation in H.264[A].Proc IEEE Int Conf Neural Networks & Signal Processing[C].2003.

[11] HUANG Y W,HSIEH B Y,CHIEN S Y,et al.Analysis and complexity reduction of multiple reference frames motion estimation in H.264/AVC[J].IEEE Trans,Circuits Syst,Video Technol,2006,16(4):507-522.

[12] WOONG I,JEON B,JEONG J.Fast motion estimation with modified diamond search for variable motion block sizes[A].IEEE International Conference on Image Processing[C].Barcelona: Institute of Electrical and Electronics Engineers Computer Society,2003.371-374.

[13] JVT reference software version 10.2[EB/OL].http://iphome.hhi.de/suehring /tml/download/ old_jm.