幀內微塊復制的屏幕圖像編碼算法

趙利平 林濤 龔迅煒 朱蓉

摘要：針對現有的幀內塊復制（IBC）算法不能很好地適應屏幕圖像具有各種不同大小和形狀樣圖的問題，為了進一步提高屏幕圖像的編碼效率，提出了一種幀內微塊復制（IMBC）算法。該算法首先將當前編碼單元（CU）劃分成L個微塊。然后以每個微塊作為最小的匹配和復制單元，采用匹配微塊組選擇算法，在參考像素集合R中找到與當前微塊最匹配的“參考微塊”。用L個位移矢量（DV）來表示“參考微塊”所在位置與當前CU所在位置的位移關系。最后，對L個位移矢量應用預測算法以消除位移矢量之間的相關性后進行熵編碼。對于屏幕圖像標準測試數據集合中的視頻序列，IMBC算法與IBC算法相比，在編碼復雜度增加較低的前提下，在全幀內（AI）、隨機接入（RA）、低延遲（LB）三種編碼配置中，有損BDrate降低率分別達3.4%、2.9%、2.6%，無損Bitrate降低率分別達9.5%、5.2%、5.1%，能有效提高屏幕圖像的編碼效率。

關鍵詞：

高效視頻編碼；屏幕圖像編碼；幀內塊復制；微塊劃分；位移矢量

中圖分類號： TN919.81； TP391.413 文獻標志碼：A

0引言

隨著云計算和云—移動計算的發展，屏幕圖像編碼[1-3]（Screen Content Coding，SCC）已經成為當前新興主流的云片計算、虛擬屏幕、遠程桌面、虛擬桌面（Virtual Desktop Infrastructure， VDI）、iPad/iPhone的無線屏幕映像技術、智能手機和平板電腦的第二顯示、數據采集與監視控制系統、超瘦型客戶端和遠程感知等應用中解決客戶端與服務器端數據傳輸瓶頸問題的關鍵技術，因此，SCC作為一個新的研究課題受到了學術界和工業界的廣泛關注。正在聯合制定最新國際視頻編碼標準高效視頻編碼（High Efficiency Video Coding，HEVC）的三大組織國際電信聯盟（International Telecommunication Union，ITU）、國際標準化組織（International Organization for Standardization，ISO）和國際電工委員會（International Electro technical Commission，IEC）于2014年1月聯合正式啟動HEVC第五版即SCC版的標準制定工作并發布了標準提案征集公告[4]。

SCC技術中一個挑戰性的問題是SCC的編碼效率問題，即如何在取得超高清的近似無損圖像重構質量的同時取得高達300∶1～3000∶1倍壓縮比。屏幕圖像作為一類包含自然圖像在內的更普遍的視頻圖像，表現出與傳統視頻不同的特點。屏幕圖像的一個顯著特點是同一幀圖像內通常會有很多相似甚至完全相同的具有不同大小與形狀的像素圖樣。而傳統的圖像和視頻壓縮技術中采用的幀內或幀間預測算法主要適用于由相機或攝像機拍攝的自然圖像，對屏幕圖像的編碼效率較低。

現有的屏幕圖像編碼算法主要包括幀內塊復制（Intra Block Copy， IBC）算法[5-7]、Palette算法[8]、幀內串復制（Intra String Copy，ISC）算法[9-10]。這些算法的共同點是從預定的參考像素集R范圍內，通過一個相同“復制”操作，將參考像素集內的若干像素“粘貼”到當前待編碼的若干像素的位置。而這些算法的不同點主要表現在復制的最小單元與復制的大小與形狀不同。幀內塊復制算法的最小復制單元是以塊為單位，與HEVC的編碼單元（Coding Unit， CU）具有很好的兼容性。Palette算法和幀內串復制算法的最小復制單元是一個像素（也可以是像素對應的索引），可以具有各種各樣形狀與大小的復制串。Palette算法和ISC算法能進一步提升編碼效率；但編碼復雜度（用JCTVC規定使用的編碼器運行時間來衡量）成倍增加[11-13]。

IBC算法在一定程度上是將傳統的幀間預測擴展到當前幀，已經被HEVC SCC版本采納。對于屏幕圖像中重復出現的固定大小與形狀的圖樣編碼效率比較高。然而，這些編碼單元都是采用有限種固定大小的塊匹配模式，對于任意形狀與大小的匹配圖樣缺乏靈活性。文獻[6]提出了非方塊匹配模式，在編碼時間復雜度增加約14%左右，能有效提高屏幕圖像的編碼效率。與Palette算法和ISC算法相比，IBC算法與HEVC具有更好的兼容性，不需要額外增加較多的語法元素等優勢。

本文在IBC算法的基礎上，提出了幀內微塊復制（Intra MiniBlock Copy，IMBC）算法，并給出了IMBC的實現特例一個CU劃分為16個微塊的算法（16個微塊需要用16個位移矢量（Displacement Vector， DV）來表示，因此也稱16DV算法）和關鍵技術。16DV算法僅僅對8×8的塊進行水平微塊劃分。實驗結果表明，對于SCC標準測試數據集合中的視頻序列，16DV算法在編碼復雜度增加較少的情況下，能有效提高屏幕圖像的編碼效率。本文的部分工作是基于提交的視頻編碼聯合協作組（Joint Collaborative Team on Video Coding， JCTVC）提案[14]和提案[15]。微塊復制算法在編碼器中的主要運算是搜索最優匹配的參考微塊，因此，微塊復制算法也稱為微塊匹配算法。

1IMBC算法

IBC算法[7]采用有限種固定大小的塊作為最小復制單元。如圖1所示，設CU的大小為2N×2N，IBC的劃分模式分為4種，分別是2N×2N、2N×N、N×2N和N×N。一般而言，CU的大小可以是64×64、32×32、16×16、8×8。因此，IBC算法中塊的大小可以從64×64至4×4若干種。然而，屏幕圖像中通常具有不同大小與形狀的像素圖樣，比如線條等，因此，需要更精細的IMBC算法。

1.1微塊劃分

IMBC算法中一個核心問題是如何對CU進行微塊劃分。微塊劃分可以分為規則和非規則微塊劃分。圖2給出規則與非規則微塊劃分方式示意圖。對于相同大小的塊，按照不同的劃分方式，可以有不同的微塊劃分方式，因此IMBC算法的實現具有不同的實現特例。顯然，16DV算法（規則微塊劃分方式1至規則微塊劃分方式3和非規則微塊劃分方式1）與ILC算法（水平線條劃分方式和垂直線條劃分方式）均是IMBC的一個特例。IMBC算法可以歸約候選微塊組最優化問題，即匹配微塊組確定問題：對于當前塊Dm×n，按照某種劃分方式劃分成一組L個微塊{D1，D2，…，DL}，以每個微塊為最小的復制單元，在參考集R內所有參考像素候選微塊集合中，確定一個匹配微塊組，使得目標函數率失真代價（Rate Distortion cost， RDcost）達到最小值。用L個復制參數表示L個微塊與匹配微塊之間的位置關系。對L個復制參數以及殘差塊經過熵編碼得到比特率（Rate）以及根據重構像素塊與當前塊之間的失真（Distortion）獲得RDcost，與傳統的幀內、幀間模式及IBC算法進行RDcost比較，將RDcost最小的模式的編碼結果寫入碼流。

IMBC算法是一種基于微塊劃分的IBC改進算法，主要的區別在于復制的最小單元（大?。┖托螤钜约耙粋€CU需要的DV數目不同。一般而言，復制的最小單元決定了復制的精度，復制的最小單元越小，復制精度越高，當前塊與匹配塊的失真一般會減少，殘差塊需要編碼的比特數越少；但是需要的DV數目越多，DV組需要編碼的比特數也就越多。因此，IMBC算法要取得好的編碼效率，需要在微塊的劃分問題（如何提高復制精度）以及DV組熵編碼問題（如何對DV組進行有效熵編碼）進行綜合平衡。

1.2IMBC編解碼框架

在IMBC編碼器端，如圖3（a）所示，IMBC作為一種新的模式，與傳統的幀內/間預測模式以及IBC模式并行地添加到HEVC混合編碼體系中。在預編碼階段，對輸入CU依次作幀內/間預測模式、IBC模式和IMBC模式的預編碼，獲得預測參數或者復制參數（DV或者DV組），根據預測參數或者復制參數在重建Buffer或者參考像素集R內得到預測CU，將輸入CU與預測CU相減得到殘差CU。對預測參數或復制參數和殘差塊進行熵編碼得到各模式的RDcost，從中選擇RDcost最小的模式，最后在編碼階段，將該模式的模式信息和殘差信息等經過上下文自適應二進制算術編碼（ContextAdaptive Binary Arithmetic Coding， CABAC）熵編碼寫入碼流。對于待編碼輸入CU，IMBC算法在參考像素集R內，為了進一步提高復制精度，采用改進的微塊組選擇算法；為了進一步節省比特率，對復制參數DV組首先經過預測，消除DV組之間的相關性，然后進行熵編碼。

在IMBC解碼器端，如圖3（b）所示，首先從IMBC碼流中按照CU的順序讀出模式信息，如果是IMBC模式，則解碼出DV組，在參考像素集R內，根據DV組以及與編碼器指定的微塊劃分方式，從L個位置進行“復制”和“粘貼”操作，獲得預測塊的數據。與此同時解碼出殘差塊的數據，兩者相加獲得重建CU塊數據。如果是其他模式，則按照HEVC現有的方式進行解碼。

1.316DV算法

16DV算法的劃分模式可以是規則微塊劃分方式1，2，3，也可以是非規則微塊劃分方式1。實驗結果表明，規則微塊劃分方式1編碼效率更好，因此，本文給出的16DV算法特指規則微塊劃分方式1。具體而言，對于大小為8×8的CU，首先劃分成16個4×1的微塊，在參考像素集R內，搜索到與當前CU每個微塊相匹配的16個最優參考微塊，用16個DV來表示每個微塊與最優參考微塊之間的復制關系。圖4給出了IBC與16DV算法搜索示意圖。

CU n給出了IBC搜索的過程，而CU m給出了16個微塊搜索的過程。其中：

1）第1個4×1水平條的DV為（-1，-7）；

2）第2個4×1水平條的DV為（4，-3）；

3）第3至第6個水平條的DV是一致的，均為（4，-7）；

4）第7至第16個水平條的DV是一致的，均為（-1，0）。

顯然，IMBC的優勢是復制精度大幅提高，從而使得當前塊與匹配塊（由16個匹配微塊組成的匹配塊）之間的失真大幅減少；同時對于殘差塊編碼的比特數也大幅減少。

216DV算法相關技術

2.1搜索時間優化

為了降低16DV算法的編碼復雜度，采用一次搜索，也即一次遍歷參考像素集R；同時找出IBC算法對應的匹配塊與16DV算法對應的16個匹配微塊。設IBC算法在參考像素集R內搜索的次數為M，對于8×8的CU，搜索復雜度分析見表1。其中運算次數指的是算術邏輯運算次數。搜索階段的主要運算量分為三部分：越界判斷，計算該位置的參考塊與當前塊的差的絕對值的和（Sum of Absolute Difference，SAD），更新匹配塊（包括獲得該DV需要編碼的比特數bits（bits與SAD累加得到參考塊的RDcost）和與最小SAD的預測塊或者預測微塊的RDcost比較）。設當前塊為C，Y（Ci， j）表示當前塊C位置為i、 j的Y分量的數值。參考塊R，Y（Ri， j）表示參考塊R位置為i、 j的Y分量的數值。大小為8×8的當前塊與參考塊的SAD計算如下：

SAD（R，C）=∑8i=1∑8j=1Y（Ri， j）-Y（Ci， j）（1）

根據以上分析，表1給出了16DV與IBC搜索復雜度分析。越界判斷與比特數計算運算次數完全相同，因此沒有列出，實際搜索復雜度增加更小。從表1中可知，16DV的搜索復雜度與IBC相比，增加了16%左右。事實上，由于16DV算法僅僅對8×8的塊進行微塊搜索，因此編碼復雜度要遠遠低于16%。

2.2匹配微塊組選擇算法

IMBC算法可以歸約為匹配微塊組確定問題，也稱為匹配微塊組選擇算法?，F有的匹配微塊組選擇算法是選擇RDcost估計函數取得最小值的微塊組作為匹配微塊組?？紤]到算法復雜度問題，RDcost估計函數只考慮了當前微塊與匹配微塊之間Y分量數據的誤差。而實際的RDcost函數需要考慮各個分量的失真以及各分量殘差塊需要編碼的比特數。顯然，現有的匹配微塊選擇算法對于色度分量可能會帶來較大的失真，從而使得實際的RDcost增大，導致編碼效率降低。另一方面，如果在RDcost估計函數中同時考慮各個分量的失真，會帶來較高的算法復雜度，因此，為了解決色度復制精度不高的問題，提出了一種低復雜度的匹配微塊組選擇算法。該算法主要包括以下3個步驟。

步驟1在參考像素集R內，搜索一次，根據現有的RDcost估計函數，找出k個較優參考微塊組。按照匹配（最優參考）微塊組、次優參考微塊組一直到第k個較優的參考微塊組排序，獲得RDcost估計值costi（0

步驟2遍歷k個較優的16DV組，計算當前塊與參考塊（由微塊組組成的參考塊）色度分量的SAD，累加到costi（0

步驟3costi（0

本文中k取值為4。匹配微塊組選擇算法偽代碼如下。

有序號的程序——————————Shift+Alt+Y

程序前

1）

for y= 搜索范圍的下邊界 to搜索范圍的上邊界

2）

for x=搜索范圍的左邊界to 搜索范圍的右邊界

3）

for l=1 to 16

4）

for i=0 to k-1

5）

do 步驟1；

6）

較優的RDcost估計值costi保存在cost[i]中；

7）

較優的DV組保存在數組multiDV[i][l]中；

8）

end for

9）

end for

10）

end for

11）

end for

12）

for ch=0 to 1//遍歷三個各色度是3個分量，還是4個分量？需明確。分量

13）

for i=0 to k-1

14）

do 步驟2： cost[i]+=色度SAD；

15）

end for

16）

end for

17）

minSadIndex=0；

18）

for i=0 to k-1

19）

do 步驟3：找出最小的costi所對應的下標j，minSadIndex=j；

20）

end for

21）

return multiDV[ minSadIndex]；

程序后

2.3DV組預測算法

為了進一步降低DV組熵編碼的比特數，根據DV組CU內部相關性以及DV組的分布特點（如圖4所示，同一CU內部的DV相同或者相差很?。?，采用垂直方向DV組預測算法。16DV算法采用垂直距離為1的微塊劃分從而垂直方向上的DV之間有很大相關性。為了消除垂直方向上的DV之間的冗余，首先對16DV按照水平優先掃描的順序進行標號，用{DV1，DV2，…，DV16}表示，然后對DV組進行預測得到預測后DV（DV Predictor，DVP）組。預測前DV組與DVP組的關系可表示如下：

具體而言，前兩個DV值不變，后面的14個DV作垂直方向預測，也即分別與前兩個DV的x、y坐標（分別用DV（x）與DV（y）表示）作差值運算獲得預測后的DVP（分別用DVP（x）與DVP（y）表示），然后對差值進行熵編碼。解碼時，先解碼差值即DVP，然后再分別與前兩個DV的x、y坐標相加即得到原始的DV值。表2～3給出了原始的DV值和DVP值的示例。

3實驗結果與分析

作為IMBC的一個實現特例，本文的16DV算法是在HM12.1_RExt5.1[16]參考軟件的基礎上實現的。測試數據集采用HEVC SCC標準測試集合[17]。13個測試數據集合根據序列內容分為4種類別，分別是表4中的移動的文字和圖形（Text and Graphics with Motion， TGM）、混合內容（Mixed content，M）、相機拍攝的內容（Camera Captured content，CC）、動畫（Animation，A）。每個測試數據有YUV版本和RGB兩個版本。每個數據編碼10幀。

為了便于說明IMBC算法的特性，將本文提出的算法以及比較的基準分為以下3種算法：

1）HEVC RExt5.1，簡稱IBC；

2）HEVC RExt5.1+16DV劃分，簡稱16DV；

3）HEVC RExt5.1+16DV劃分及其相關技術，簡稱16DV_R。

其中IBC中搜索范圍為2CTU（即INTRABC_LEFTWIDTH為64），默認快速搜索關閉（即INTRABC_FASTME為0）。16DV算法的配置同IBC。所有的實驗都使用全幀內（All Intra， AI）、隨機接入（Random Access， RA）和低延遲（Low delay B， LB）三種編碼配置[15]。

為了衡量算法的總體編碼效率，采用與HEVC的核心實驗同樣標準的BDrate（Bjntegaard delta rate）[18]降低率來衡量有損編碼效率以及比特率降低率來衡量無損編碼效率。按不同顏色格式（RGB或者YUV格式）和不同的序列內容類別來分別進行總體衡量和比較，對于有損實驗結果，主要用每個分量G/Y、B/U和R/V的平均BDrate降低率來衡量算法的增益，對于無損實驗，主要用總的比特率降低率來衡量算法的增益。表5是16DV_R算法、IBC算法和16DV算法編碼效率的比較。每行數據代表一種顏色格式（YUV或RGB）和序列內容類別的組合。一共有8種組合，每個組合中有1至4個序列。圖5給出了16DV_R與IBC在無損編碼模式下，兩個典型屏幕圖像序列dsk、webb不同色彩格式（dsk_yuv、dsk_rgb分別表示dsk數據YUV色彩格式和RGB格式；webb_yuv、webb_rgb分別表示webb數據YUV色彩格式和RGB格式）的壓縮率比較情況。圖6給出了16DV_R與IBC在有損編碼模式，兩個典型屏幕圖像序列的率失真曲線比較；有損編解碼時間復雜度比較如圖7所示。

由以上實驗結果，可以得出以下結論：

1）從總體的編碼效率來看，16DV_R算法在無損情況和有損情況下均表現出更好的編碼效率。16DV_R與IBC相比，無損情況下，對于TGM（1080p & 720p） YUV數據類別，Bitrate降低率AI配置為9.5%，RA配置為5.2%，LB配置為5.1%。有損情況下，對于TGM（1080p & 720p）RGB數據類別，BDrate降低率AI配置的R分量為3.4%，RA配置為2.9%，LB配置為2.6%。

2）從典型的單個屏幕圖像序列的編碼效率看來，對于部分屏幕圖像序列，16DV_R與IBC相比，無損與有損編碼效率大幅提升。從圖5中可知，對于YUV格式的dsk數據，16DV_R與IBC相比，在RA配置下壓縮比從133.6倍提升至171.5倍；在AI配置下壓縮比從15.2倍提升至20.4倍。從圖6中可知，對于RGB格式的dsk數據，有損情況下的率失真曲線表明，在相同的碼率情況下，峰值信噪比提升可高達6dB以上。

3）從表5中可知，16DV_R與16DV算法相比，無損情況和有損情況下均表現出更好的編碼效率，表明IMBC算法要取得更好的編碼效率，需要在微塊劃分和DV組有效熵編碼之間取得綜合平衡。

4）16DV_R算法與編碼效率的提升程度與屏幕圖像類別相關。表5表明，對于TGM類別，提升比較多，MC也有一些提升，而對于ANI與CC類別（ANI和CC類序列非常近似于自然圖像）幾乎沒有提升。實際上，所有專門針對典型屏幕圖像的算法都有這一性質。

5）根據圖7中有損編解碼時間復雜度對比可知，16DV_R算法與IBC算法相比，AI配置、RA配置與LB配置分別增加的時間復雜度為10%、6.3%和3%，因此編解碼復雜度的增加較小。

4結語

針對屏幕圖像中存在各種不同大小和形狀的相似或相同圖樣，在幀內塊復制的基礎上，提出了一種幀內微塊復制（IMBC）屏幕圖像編碼算法。本文以16DV算法作為IMBC算法的實現特例，給出了16DV算法及其相關技術。實驗結果表明，在編碼復雜度增加較低的情況下，本文提出的算法通過找到更精細的微塊復制能取得更好的編碼效率。降低編碼器的復雜度是一個需繼續研究的課題。16DV的編碼復雜度也還有很大的降低空間。通過Hash搜索降低編碼復雜度或者根據圖像塊的特點自適應采用IMBC與IBC搜索方案是下一步的主要工作。

參考文獻：

[1]

LIN T， ZHOU K， WANG S. Cloudletscreen computing： a clientserver architecture with top graphics performance [J] International Journal of Ad Hoc and Ubiquitous Computing， 2013， 13（2）： 96-108.

[2]

LU Y， LI S， SHEN H. Virtualized screen： a third element for cloudmobile convergence [J]. IEEE Transactions on Multimedia， 2011， 18（2）： 4-11.

[3]

LIN T， WANG S. Cloudletscreen computing： a multicorebased， cloudcomputingoriented， traditional computingcompatible parallel computing paradigm for the masses [C]// Proceedings of 2009 IEEE Workshop on Multimedia Signal Processing and Novel Parallel Computing. Piscataway， NJ： IEEE， 2009： 1805-1808.

[4]

ISO/IEC JTC1/SC29/WG11， ITUT Q6/16. Joint call for proposals for coding of screen content [C]// Proceedings of the 2014 Joint Collaborative Team on Video Coding Meeting. Geneva： JCTVC Press， 2014： JCTVCN14175：1-15.

[5]

BUDAGAVI M， KWON D. AHG8： video coding using Intra motion compensation [C]// Proceedings of the 2013 Joint Collaborative Team on Video Coding Meeting. Geneva： JCTVC Press， 2013： JCTVCM0350： 1-5.

[6]

CHEN C， XU X， LIAO R， et.al. Screen content coding using nonsquare intra block copy for HEVC [C]// Proceedings of the 2014 IEEE International Conference on Multimedia and Expo. Washington， DC： IEEE Computer Society， 2014： 1-6.

[7]

PANG C， SOLE J， CHEN Y， et.al. Intra block copy for HEVC screen content coding [C]// Proceedings of the 2015 Data Compression Conference. Washington， DC： IEEE Computer Society， 2015： 465-465.

[8]

XIU X， HE Y， JOSHI R. Palettebased coding in the screen content coding extension of the HEVC standard [C]// Proceedings of the 2015 Data Compression Conference. Washington， DC： IEEE Computer Society， 2015： 252-262.

[9]

LIN T， ZHANG P， WANG S， et al. Mixed chroma samplingrate high efficiency video coding for fullchroma screen content [J]. IEEE Transactions on Circuits and Systems for Video Technology， 2013， 23（1）： 173-185.

[10]

ZHAO L， LIN T， ZHOU K， et al. Pseudo 2D string matching technique for high efficiency screen content coding [J]. IEEE Transactions on Multimedia， 2016， 18（3）： 339-350.

[11]

LI B， XU J， SULLIVAN G. Comparison of compression performance of HEVC range extensions draft 5 with AVC high 4：4：4 predictive profile [C]// Proceedings of the 2014 Joint Collaborative Team on Video Coding Meeting. Geneva： JCTVC Press， 2014： JCTVCP0213： 1-4.

[12]

ZHAO L， ZHOU K， WANG S， et.al. NonCE3： improvement on intra string copy [C]// Proceedings of the 2015 Joint Collaborative Team on Video Coding Meeting. Geneva： JCTVC Press， 2015： JCTVCT0139： 1-7.

[13]

LI B， XU J， SULLIVAN G. Comparison of compression performance of HEVC test model 16.4 and HEVC screen content coding extensions test model 4 with AVC high 4：4：4 predictive profile [C]// Proceedings of the 2015 Joint Collaborative Team on Video Coding Meeting. Geneva： JCTVC Press， 2015： JCTVCU0051： 1-10.

[14]

ZHAO L， CHEN X， LIN T. NonSCCE2： an improvement on intra line copy of SCCE2 [C]// Proceedings of the 2008 Joint Collaborative Team on Video Coding Meeting. Geneva： JCTVC Press， 2014： JCTVCR0281： 1-4.

[15]

ZHAO L， CHEN X， LIN T. CE4： results of test C [C]// Proceedings of the 2014 Joint Collaborative Team on Video Coding Meeting. Geneva： JCTVC Press， 2014： JCTVCS0194： 1-3.

[16]

BOSSEN F， FLYNN D， SHARMAN K， et al. Test software [EB/OL]. [20151024]. https：//hevc.hhi.fraunhofer.de/svn/svn_HEVCSoftware/tags/HM12.1+RExt5.1/.

[17]

YU H， COHEN R， RAPAKA K， et al. Common conditions for screen content coding tests [C]// Proceedings of the 2014 Joint Collaborative Team on Video Coding Meeting. Geneva： JCTVC Press， 2014： JCTVCQ1015： 1-5.

[18]

BJNTEGAARD G. Improvements of the BDPSNR model [C]// Proceedings of the 2008 Video Coding Experts Group 35th Meeting. Geneva： VCEG Press， 2008： VCEGAI11： 1-3.