0 引言

    目前主流的視頻編碼標(biāo)準(zhǔn)包括3個(gè)體系：國(guó)際聯(lián)合視頻工作組(Joint Video Team，JVT)的H.26x、國(guó)內(nèi)數(shù)字音視頻編解碼技術(shù)標(biāo)準(zhǔn)工作組(Audio Video Coding Standard，AVS)的AVSx和Google公司的VPx^[1-4]。其中，VPx編解碼器(COder/DECoder，CODEC)憑借開源和免專利費(fèi)的優(yōu)勢(shì)，在全球范圍內(nèi)各種網(wǎng)絡(luò)瀏覽器的支持率已經(jīng)超過92%^[5]。

    視頻編碼標(biāo)準(zhǔn)中的幀內(nèi)壓縮是決定最終編碼效率的關(guān)鍵，但由于該過程的算法復(fù)雜度高而導(dǎo)致非常耗時(shí)，因此對(duì)幀內(nèi)壓縮快速算法的研究顯得尤為必要。近年來這方面的研究主要集中在H.264和H.265/高性能視頻編碼(High Efficiency Video Coding，HEVC)^[6-9]。文獻(xiàn)[6]通過統(tǒng)計(jì)方法與閾值法，文獻(xiàn)[7]基于紋理方向檢測(cè)，文獻(xiàn)[8]利用時(shí)間與時(shí)空相關(guān)性，分別對(duì)HEVC幀內(nèi)預(yù)測(cè)進(jìn)行加速，實(shí)現(xiàn)將編碼時(shí)間減少24~30%。文獻(xiàn)[9]提出梯度法加快確定幀內(nèi)模式，將編碼時(shí)間減少15%，再結(jié)合支持向量機(jī)(Support Vector Machine，SVM)加快確定HEVC編碼單元?jiǎng)澐?，使編碼時(shí)間進(jìn)一步減少到50%以上。文獻(xiàn)[10]對(duì)HEVC和VP9兩種標(biāo)準(zhǔn)的幀內(nèi)壓縮算法及其對(duì)編碼效率的影響進(jìn)行了比較。本文針對(duì)VPx的幀內(nèi)壓縮提出了加速算法，并通過實(shí)驗(yàn)驗(yàn)證了算法的效果。

1 VPx幀內(nèi)壓縮

    幀內(nèi)壓縮是基于相鄰像素之間的相關(guān)性，通過當(dāng)前塊的相鄰塊對(duì)其進(jìn)行預(yù)測(cè)，并對(duì)預(yù)測(cè)值與實(shí)際值之間的殘差進(jìn)行一系列變換、量化和熵編碼，以消除空間冗余達(dá)到壓縮的目的。圖1所示為VPx幀內(nèi)壓縮框圖。VPx幀內(nèi)壓縮以宏塊/超級(jí)塊為單位，其中VP8標(biāo)準(zhǔn)的宏塊大小為16×16，VP9標(biāo)準(zhǔn)的超級(jí)塊大小為64×64。VP8采用4×4的子塊劃分方式將宏塊劃分為4×4大小的子塊，其變換包括離散余弦變換(Discrete Cosine Transform，DCT)和沃爾什-哈達(dá)瑪變換(Walsh-Hadmard Transform，WHT)。VP9采用四叉樹子塊劃分方式將超級(jí)塊劃分為4×4~64×64大小的子塊，其變換包括非對(duì)稱離散正弦變換(Asymmetric Discrete Sine Transform，ADST)和DCT。

    VPx幀內(nèi)預(yù)測(cè)分為亮度塊預(yù)測(cè)和色度塊預(yù)測(cè)。亮度塊預(yù)測(cè)包括以下10種預(yù)測(cè)模式：

其中，DC和TM分別為直流和真運(yùn)動(dòng)預(yù)測(cè)模式，另外8種為角度預(yù)測(cè)模式，圖2中以4×4的亮度塊預(yù)測(cè)為例說明。HE和VE分別為水平和垂直預(yù)測(cè)模式，LD和RD分別為45°和135°預(yù)測(cè)模式，VL和VR分別為63°和117°預(yù)測(cè)模式，HD和HU分別為153°和207°預(yù)測(cè)模式。

    在幀內(nèi)壓縮過程中，要從上述10種預(yù)測(cè)模式中選擇一種，使碼率在不超過某最大碼率的情況下失真最小。VPx采用率失真優(yōu)化(Rate Distortion Optimization，RDO)方法來尋找碼率和失真之間的平衡，其率失真代價(jià)函數(shù)表示為：

其中，J_mode為預(yù)測(cè)模式對(duì)應(yīng)的率失真代價(jià)，D_mode為失真，λ_mode為拉格朗日系數(shù)，B_mode為所需比特?cái)?shù)。通過計(jì)算預(yù)測(cè)殘差的平方和(Sum Squared Error，SSE)得到失真D_mode。對(duì)于每個(gè)亮度子塊，要進(jìn)行10次變換、量化、反量化和反變換的重構(gòu)過程，根據(jù)率失真代價(jià)J_mode最小的原則選取最終預(yù)測(cè)模式，進(jìn)入熵編碼。

    假設(shè)幀內(nèi)壓縮圖像寬度和高度分別為W和H，宏塊/超級(jí)塊大小為C×C，則總的宏塊/超級(jí)塊數(shù)為：

    以1 280×720的圖像為例，宏塊大小為16×16，按4×4的子塊劃分方式，得到4×4的亮度子塊，則RecCnt的理論值為576 000次，意味著如此大量次數(shù)的變換、量化、反量化、反變換和率失真計(jì)算代價(jià)。

2 快速算法

    為減少幀內(nèi)壓縮的運(yùn)算量，可以從兩方面入手：一方面減少亮度子塊的重構(gòu)次數(shù)，另一方面優(yōu)化幀內(nèi)壓縮的算法程序。下面主要討論前者。

2.1 最近鄰加速法

    最近鄰加速法利用當(dāng)前子塊與其最近鄰子塊的相關(guān)性，以最近鄰子塊的預(yù)測(cè)模式作為其最終預(yù)測(cè)模式，從而減少遍歷預(yù)測(cè)模式帶來的重構(gòu)次數(shù)。

    圖3所示為將圖像中一個(gè)16×16的宏塊劃分為16個(gè)4×4的亮度子塊，虛線框表示當(dāng)前子塊，箭頭所在子塊表示其候選最近鄰子塊。

    首先根據(jù)當(dāng)前子塊在宏塊中的位置確定最鄰近子塊。設(shè)當(dāng)前子塊為S_i，j，3個(gè)候選最近鄰子塊分別為S_i-1，j、S_i，j-1、S_{i-1，j-1}。S_1，1作為第一個(gè)子塊，不存在最近鄰子塊。

    將S_i，j的最鄰近子塊定義為NB_i，j，當(dāng)候選最近鄰子塊僅存在于水平和垂直方向時(shí)，有：

    當(dāng)候選最近鄰子塊存在水平、垂直和對(duì)角方向時(shí)，則先根據(jù)不同方向上子塊的率失真代價(jià)從候選最近鄰子塊中確定最近鄰子塊：

其中，J_l，m為3個(gè)方向率失真代價(jià)J_i，j-1、J_i-1，j、J_{i-1，j-1}中最小的，l和m代表最近鄰子塊的坐標(biāo)。則有：

    假設(shè)最近鄰子塊NB_i，j的最佳預(yù)測(cè)模式為mode，對(duì)當(dāng)前子塊在該模式下進(jìn)行重構(gòu)和率失真J_i，j計(jì)算。當(dāng)滿足如下關(guān)系時(shí)，將模式mode作為當(dāng)前子塊的最終預(yù)測(cè)模式。

否則將對(duì)當(dāng)前子塊進(jìn)行預(yù)測(cè)模式的遍歷，得到最終預(yù)測(cè)模式。

    在最近鄰子塊的判斷過程中，要在當(dāng)前宏塊/超級(jí)塊范圍內(nèi)，保存當(dāng)前子塊S_i，j的前序子塊的最佳預(yù)測(cè)模式和與其對(duì)應(yīng)的率失真，用于與當(dāng)前子塊直接比較以簡(jiǎn)化率失真計(jì)算。 2.2 閾值加速法

    對(duì)當(dāng)前子塊的率失真J_i，j設(shè)置閾值TH。當(dāng)某一預(yù)測(cè)模式下的J_i，j滿足如下關(guān)系時(shí)，終止對(duì)預(yù)測(cè)模式的遍歷，將該預(yù)測(cè)模式作為當(dāng)前子塊的最終預(yù)測(cè)模式：

否則將繼續(xù)進(jìn)行下一個(gè)預(yù)測(cè)模式。如果所有預(yù)測(cè)模式對(duì)應(yīng)的率失真均不滿足式(9)，則根據(jù)RDO原則選取最佳預(yù)測(cè)模式。

    閾值的選取直接影響最終結(jié)果。閾值越大，越容易提前終止對(duì)預(yù)測(cè)模式的遍歷，從而提高壓縮速度，同時(shí)降低壓縮質(zhì)量；反之閾值越小，越難滿足閾值要求，遍歷的預(yù)測(cè)模式越多，從而保持壓縮質(zhì)量，但壓縮速度提高少。式(10)給出了閾值選取公式：

其中，J表示已有子塊率失真的集合，J_max和J_min分別為J中的最大率失真和最小率失真，Coef取值0.062 5。

2.3 兩級(jí)加速法

    采用最近鄰法加速時(shí)，如果當(dāng)前子塊存在最近鄰子塊，則能夠減少子塊重構(gòu)運(yùn)算量；否則仍需要對(duì)所有預(yù)測(cè)模式進(jìn)行遍歷。采用閾值加速法時(shí)，如果當(dāng)前子塊的率失真滿足閾值條件，則能夠減少子塊重構(gòu)運(yùn)算量；否則仍需要對(duì)所有預(yù)測(cè)模式進(jìn)行遍歷。

    將上述兩種加速方法結(jié)合，構(gòu)成如圖4所示的兩級(jí)加速法，使幀內(nèi)壓縮速度進(jìn)一步提高。兩級(jí)加速法的第一級(jí)為最近鄰加速，第二級(jí)為閾值加速。

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

    為了驗(yàn)證算法的有效性，將本文算法在Google官方發(fā)布的libwebp-1.0.0上進(jìn)行實(shí)現(xiàn)。該庫利用VP8幀內(nèi)壓縮算法對(duì)WebP圖像進(jìn)行編解碼。

    實(shí)驗(yàn)的硬件環(huán)境：Inter-Core^TM i5-6200 CPU，主頻為2.40 GHz，內(nèi)存為4.00 GB，操作系統(tǒng)為64 位Windows 10。軟件環(huán)境：Visual C++ 6.0。參數(shù)設(shè)置：品質(zhì)因數(shù)(Quality factor)為80。選用源自Wikipedia的6張測(cè)試圖像，如圖5所示。這些圖像涵蓋不同的分辨率和內(nèi)容復(fù)雜度。

    對(duì)測(cè)試圖像分別用原始方法、最近鄰加速法、閾值加速法和兩級(jí)加速法進(jìn)行編碼實(shí)驗(yàn)。表1所示為幾種方法對(duì)應(yīng)的單張圖像子塊重構(gòu)數(shù)統(tǒng)計(jì)?？梢钥闯觯捎米罱彿ê烷撝捣ň棺訅K重構(gòu)次數(shù)在一定程度上降低。對(duì)于圖像Balloon，由于原圖像較平坦，最近鄰法得到的子塊重構(gòu)次數(shù)降低到原重構(gòu)次數(shù)的1/3以下；而對(duì)于圖像Boy，原圖像具有較多細(xì)節(jié)，最近鄰法得到的子塊重構(gòu)次數(shù)僅有少量降低。結(jié)合閾值法后，對(duì)于上述測(cè)試圖像，通過兩級(jí)法加速后得到的子塊重構(gòu)次數(shù)均大幅度減少。

    圖6對(duì)幾種加速方法從編碼時(shí)間T、編碼比特率BR和峰值信噪比PSNR 3個(gè)方面進(jìn)行比較?？梢钥闯鰧?duì)分辨率和內(nèi)容不同的圖像，幀內(nèi)編碼的時(shí)間都有大幅度降低，而BR和PSNR只有很小的變化。通過式(11)可以進(jìn)一步得到上述算法的具體性能指標(biāo)：

其中，ΔT表示所提出算法的編碼時(shí)間減少的百分比，T_org和T_proposed分別為原始編碼時(shí)間和所提出算法的編碼時(shí)間；ΔPSNR表示PSNR減少的dB值，PSNR_org和PSNR_proposed分別為原始編碼的PSNR和所提出算法的PSNR；ΔBR表示BR增加的百分比，BR_org和BR_proposed分別為原始編碼的BR和所提出算法的BR。根據(jù)對(duì)測(cè)試圖像的實(shí)驗(yàn)統(tǒng)計(jì)和計(jì)算結(jié)果，得到最近鄰法的ΔT平均為37%，ΔBR平均為1%，ΔPSNR平均為0.06 dB；兩級(jí)法的ΔT平均為49%，ΔBR平均為4%，ΔPSNR平均為0.14 dB。采用兩級(jí)法加速時(shí)，圖像Balloon加速最多，ΔT達(dá)到59%，對(duì)應(yīng)編碼質(zhì)量ΔBR為6%，ΔPSNR為0.24；圖像Boy加速最少，ΔT為41%，對(duì)應(yīng)編碼質(zhì)量ΔBR為1%，ΔPSNR為0.07。

4 結(jié)論

    為了降低VPx幀內(nèi)壓縮的計(jì)算復(fù)雜度，減少編碼時(shí)間，本文提出了一種快速算法。實(shí)驗(yàn)結(jié)果表明：對(duì)于不同內(nèi)容復(fù)雜度的圖像，所提出的最近鄰法在編碼時(shí)間明顯減少平均37%的情況下，對(duì)圖像質(zhì)量影響極??；基于最近鄰法進(jìn)一步提出的兩級(jí)加速法在對(duì)圖像質(zhì)量影響很小的情況下，編碼時(shí)間大幅度減少平均49%。進(jìn)一步的優(yōu)化工作包括子塊劃分、幀內(nèi)壓縮算法的軟件優(yōu)化和硬件加速。

參考文獻(xiàn)

[1] SULLIVAN G J，OHM J，HAN W J，et al.Overview of the high efficiency video coding(HEVC) standard [J].IEEE Transactions on Circuits & Systems for Video Technology, 2012, 22(12): 1649-1668.

[2] 黃鐵軍.AVS2標(biāo)準(zhǔn)及未來展望[J].電視技術(shù)，2014，38(22)：7-10.

[3] BANKOSKI J，WILKINS P，XU Y W.Technical overview of VP8，an open source video codec for the web[C].2011 IEEE International Conference on Multimedia and Expo，ICME′11.IEEE，2011：1-6.

[4] SRINIVASAN M.VP9 Encoder and decoders for next generation online video platforms and services[C].SMPTE 2016 Annual Technical Conference and Exhibition，SMPTE，2016：1-14.

[5] LI Z R，DUANMU ZH F，LIU W T，et al.AVC，HEVC，VP9，AVS2 or AV1?-A comparative study of state-of-the-art video encoders on 4K videos[C].Image Analysis and Recognition ICIAR 2019，Springer，2019，11662：162-173.

[6] 李偉，王讓定，王家驥.一種HEVC幀內(nèi)預(yù)測(cè)模式快速選擇算法[J].計(jì)算機(jī)工程與應(yīng)用，2016，52(14)：161-166.

[7] RUIZ D，ESCRIBANO G F，MARTINEZ J L，et al.Fast intra mode decision algorithm based on texture orientation detection in HEVC[J].Signal Processing: Image Communication，2016，44：12-28.

[8] 諶博，顧梅花，馬蒙蒙.一種改進(jìn)的HEVC幀內(nèi)預(yù)測(cè)算法[J].計(jì)算機(jī)與數(shù)字工程，2017，45(1)：131-134.

[9] ZHANG T，SUN M T，ZHAO D，et al.Fast intra mode and CU size decision for HEVC[J].IEEE Transactions on Circuits & Systems for Video Technology，2017，27(8)：1714-1726.

[10] SHARABAYKO M P，PONOMAREV O G，CHERNYAK R I.Intra compression effciency in VP9 and HEVC[J].Applied Mathematical Sciences, 2013, 7(137): 6803-6824.

作者信息:

胡金艷，宋紹京

(上海第二工業(yè)大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，上海201209)