一種新的用于屏幕圖像編碼的HEVC幀內模式

陳先義 趙利平② 林 濤

?

一種新的用于屏幕圖像編碼的HEVC幀內模式

陳先義*①趙利平①②林 濤①

①(同濟大學超大規模集成電路研究所 上海 200092)②(嘉興學院數理與信息工程學院 嘉興 314000)

由于傳統編碼方式對屏幕圖像的編碼效果不佳，該文根據屏幕圖像包含大量非連續色調內容的特點，在HEVC(High Efficiency Video Coding)基礎上，提出一種新的幀內編碼模式稱為幀內串匹配(Intra String Copy, ISC)。基本思想是在HEVC的編碼單元(Coding Unit, CU)級別上，引入字典編碼工具：編碼時，在一定長度的字典窗口內，利用散列表，對當前CU內的像素，進行串搜索和匹配；解碼時，根據像素串匹配的距離和匹配長度，在重建緩存內復制相應位置像素重建當前CU像素。實驗結果表明，在編碼復雜度增加很少的情況下，對于典型的屏幕圖像測試序列，在全幀內(All Intra, AI)，隨機接入(Random Access, RA)，低延遲(Low-delay B, LB)3種配置下，有損編碼模式比HEVC分別節省碼率15.1%, 12.0%, 8.3%，無損編碼模式分別節省碼率23.3%, 14.9%, 11.6%。

高效視頻編碼；屏幕圖像編碼；字典編碼；散列表

1 引言

隨著云計算、移動云計算、遠程桌面和無線顯示技術的發展，如何在低碼率下使屏幕圖像在電腦屏幕、手機屏幕、電視屏幕和其它客戶端上高質量地顯示，吸引了學術界和工業界的關注。現有的視頻編碼標準比如H.264/AVC, VC-1, AVS, HEVC (High Efficiency Video Coding)，都是對于包含大量連續色調內容的自然圖像和視頻有很高的壓縮比，但是對于包含大量非連續色調內容的屏幕圖像壓縮效果并不好。為提高屏幕圖像編碼(Screen Content Coding, SCC)性能，國際電信聯盟電信標準化部門(ITU-T)、國際標準化組織(ISO)和國際電工委員會(IEC)于2014年1月開始聯合開發HEVC標準的SCC版本，并已經采用了一些有利于屏幕圖像編碼的工具：比如跳過變換直接量化(Transform Skip, TS)[1]和IBC(Intra Block Copy)[2,3]。

典型的屏幕圖像包含兩類內容，一類是計算機生成的非連續色調的內容，往往包含大量的小而尖的位圖結構如文本、菜單、圖標、按鈕、滑動條和網格，另一類是攝像機拍攝的包含大量連續色調的內容，例如電影/電視片段，自然圖像視頻。

傳統的基于角度預測的幀內編碼模式，無法對非連續色調的內容進行準確的預測，因而壓縮性能不好。而字典編碼工具比如gzip和LZMA (Lempel- Ziv-Markov chain Algorithm)卻對非連續色調內容有很好的壓縮性能[4]。于是文獻[5~7]提出將字典編碼工具融合到傳統的混合編碼框架中的DMC (Dual-coder Mixed Chroma-sampling-rate)算法，實驗顯示取得很好的性能。但是，DMC算法是在條帶內，基于HEVC編碼樹單元(Coding Tree Unit, CTU, HEVC中的基本編碼單元)實現的，而CTU大小默認是64×64，顯然，適用字典編碼的區域可能小于64×64，并且DMC算法對4:4:4格式的數據進行了子采樣，轉變為4:2:0格式，不可避免地引入失真。為了進一步提升編碼性能，本文將字典編碼工具應用于HEVC的編碼單元(Coding Unit, CU，由CTU按照四叉樹劃分得到，大小8×8~64×64)，使之成為HEVC的一種幀內模式，叫做ISC (Intra String Copy)，能夠與HEVC原有編碼工具更加和諧地融合在一起。實驗顯示比僅僅應用于CTU的DMC算法，性能明顯提高。

2 ISC算法概述

包含ISC的HEVC編碼框架[8]如圖1所示。按照CU自適應的方式，每個輸入的CU經過幀間、幀內、IBC, ISC編碼后，通過HEVC的率失真優化選擇機制，選取RD(Rate Distortion)代價最小的編碼模式，將編碼結果放入碼流。

圖1 包含ISC的HEVC編碼器框圖

2.1 ISC編碼器和解碼器

ISC編碼器和解碼器如圖2所示。

在編碼端，輸入的CU像素數據，首先經過像素重排器重新組織和排列。因為，在HEVC中，像素以YUV或RGB分量的2維平面格式組織，而ISC編碼器實質上是1維字典編碼器，其基于散列表的搜索需要在1維空間進行，于是需要通過一定的方式把CU像素數據重新排列，把2維數據1維化，同時把分離的YUV或RGB數據結合在一起，成為一個像素，以像素為單位存入搜索緩存。像素重排之后，在搜索緩存內，基于散列表尋找盡可能長的匹配串，串的長度最小值為1，最大值為當前CU內像素總數。如果找到匹配串，保存串的長度和匹配點到當前位置的距離；如果沒有找到匹配串，則保存當前像素，稱為未匹配像素。然后在下一個位置像素繼續搜索。整個CU搜索完成之后，對搜索的結果進行熵編碼，得到RD 代價，進行HEVC模式選擇。如果確定采用ISC編碼模式，需要在碼流中寫入一個比特的標識位。

圖2 CU自適應ISC編解碼器架構

在解碼端，解碼標識位，確定當前CU采用ISC編碼之后，碼流經過熵解碼得到匹配串的長度、匹配距離、未匹配像素等句法元素。然后在搜索緩存內，根據這些句法元素重建當前CU。即，如果有匹配，則根據匹配串的長度和距離，從搜索緩存內相應位置復制相應長度的像素到當前位置；如果沒有匹配，則將解碼得到的未匹配像素直接填充到當前位置。在搜索緩存內重建整個CU之后，需要把1維像素格式的重建數據，按照HEVC的2維平面格式，把YUV或RGB分量分別存入相應的HEVC重建緩存。

2.2 ISC算法的相關句法

經由熵編碼產生的ISC碼流由以下句法元素組成：匹配標志(標識在搜索緩存中是否搜索到匹配串)，未匹配像素，距離(當前位置與搜索緩存中匹配位置之間的距離減1)，長度(匹配串的長度減1)，八元組標志(最近使用的8個距離值存放在一個數組中，稱為八元組)，八元組索引(0~7)。對這些句法元素熵編碼的解析過程如圖3所示。

圖3 ISC熵編碼解析流程圖

3 ISC算法相關技術

3.1 搜索緩存

搜索緩存即字典，是ISC專用緩存，在編碼器里用于匹配串搜索，在解碼器中用于匹配串重建。在編碼器，搜索緩存里存放當前正在編碼CU的原始像素和之前已經編碼的CU的重建像素。搜索緩存的大小是預先指定的，有7個級別，Level1~7分別為4, 8, 16, 64, 256, 1024, 4096 kB。

顯然，搜索緩存越大，越可能找到更優的匹配，但增加的時間和空間開銷也就越多。實際最常用的緩存大小是Level 4的64 kB。

3.2像素重排

在HEVC中，像素以3個分量的平面格式組織，即Y, U, V或R, G, B 3個獨立矩陣。但是這種像素組織方式并不適合ISC字典編碼器。事實上，輸入到ISC字典編碼器的CU圖像數據，首先在像素重排器內按照圖4所示的某種掃描順序，把Y, U, V或R, G, B 3個獨立分量打包成一個像素Pixel (YUV)或Pixel(RGB)，以像素為單位，按照1維方式存放在搜索緩存中，即：Pixel0(Y0U0V0), Pixel1(Y1U1V1)或Pixel0(R0G0B0), Pixel1(R1G1B1)。可用的掃描順序有圖4所示的水平掃描、垂直掃描、水平旋轉掃描和垂直旋轉掃描4種。本文實際采用水平掃描方式。

圖4 4種掃描順序

3.3 基于散列表的搜索

ISC的基本操作是在搜索緩存里，找到與當前要編碼的像素相一致的像素，也就是尋找匹配串。如果在搜索范圍和限定的搜索次數內能夠找到匹配串，編碼器輸出匹配位置和當前位置之間的距離以及匹配串的長度；如果不能找到匹配串，編碼器就會輸出當前像素，即未匹配像素。然后處理下一個像素。如果逐個像素地搜索整個緩存尋找匹配串，消耗的時間不可接受，為了加快搜索速度，有必要使用散列表：通過散列函數，將每個像素的YUV或RGB分量的24 bit映射為更少bit的散列值，依據散列值將像素在圖像中的位置存入散列表，采用拉鏈開散列的方法處理散列沖突，即將相同散列值的像素位置放在同一條鏈上。搜索的時候，只需要計算當前像素的散列值，然后到對應的散列表的鏈上依次取得匹配位置，嘗試匹配，搜索速度能夠大大加快。散列函數如式(1)所示，其中是經過初始化的大小為256數組，Pix.Y, Pix.U, Pix.V是像素的Y, U, V或R, G, B值，HashMask為散列表表頭大小減1。

由于每次編碼完一個CU，ISC的搜索緩存指針(指示搜索位置)和散列表存儲的內容都會發生變化，而HEVC對每一個CTU內所有CU的編碼過程是先根遍歷四叉樹的過程，于是在進行下一個CU編碼之前，需要將搜索緩存指針和散列表表頭恢復到一個正確的狀態。可以按照如下步驟進行：

(1)每個CU在編碼之前，首先保存搜索緩存指針和散列表表頭。

(2)編碼父CU的第1個子CU時，將搜索緩存指針和散列表恢復至父CU起始狀態。

(3)編碼其他子CU時，將搜索緩存指針和散列表恢復至這個CU的緊鄰兄弟CU的起始狀態，并讀入這個兄弟CU的重構像素，用這些重構像素更新散列表。

散列表包括表頭和鏈表兩部分，其中鏈表與搜索緩存大小相同，隨字典Level的變化而變化，在固定的字典Level下，表頭的大小對ISC編碼性能影響很小，對編碼時間影響較大。表頭太小，鏈表長度增加，搜索次數相應增加，增加編碼時間；表頭太大，由于表頭需要頻繁的保存和恢復，也會增加編碼時間。實際選取12位的散列表位(Hash Bits)，即散列表的表頭大小為, 4k。

3.4 八元組

句法元素中的匹配距離，取值范圍是(1~搜索緩存大小)，假設搜索緩存為Level 4，匹配距離的取值范圍就是(1~16384)。顯然，這是一個比較大的范圍，為了更有效的編碼匹配距離，引入了八元組，即：將最近出現的八個匹配距離存入數組，用索引(0~7)表示。在尋找匹配串的時候，首先在散列表里查找，記錄下最長匹配串長度(mainLen)和匹配距離(mainDist)；然后對八元組里保存的匹配距離嘗試尋找匹配，如果找到的匹配串的長度(refLen)滿足式(2)，則認為八元組里尋找的匹配更優。

4 實驗結果

為驗證算法性能，以HEVC的SCC測試軟件HM14.0_RExt7.0_SCM1.0[9]為基礎，實現ISC算法。所有實驗以文獻[10]規定的測試條件進行，分為無損(lossless)和有損(lossy)兩種編碼模式，每種模式有全幀內(All Intra, AI)，隨機接入(Random Access, RA)，低延遲(Low-delay B, LB)3種配置。

實驗選用的13個測試序列[11]分為4類，分別為TGM(Text and Graphics with Motion), MC(Mixed Content), CC(Camera Captured)和A(Animation)。每個序列有RGB和YUV兩種色彩格式，所以實際使用的測試序列有26個。測試序列的分辨率為720 p, 1080 p或1440 p，幀數為120~600不等。

為了評估算法性能，HEVC規定，對于無損編碼，使用比特數變化表示碼率變化，對于有損編碼，使用BD-rate[12,13]衡量同樣客觀質量下的碼率變化。為了評估編碼器和解碼器復雜度，軟件運行的編碼時間和解碼時間也進行比較。

實驗比較了下述的3種編碼方法：

(1)HM14.0_RExt7.0_SCM1.0(SCM)默認設置。

(2)HM14.0_RExt7.0_SCM1.0集成基于CTU的DMC算法(DMC)。

(3)HM14.0_RExt7.0_SCM1.0集成ISC算法(ISC)。

SCM中IBC的搜索范圍是整幅圖像，DMC和ISC均為64 kB。

表1是ISC與SCM和DMC的編碼、解碼時間比較，其中數據為本文算法與對比算法時間總和的比值。表2列出了全部測試序列選中ISC模式的CU占圖像面積的百分比。表3是ISC與SCM和DMC在無損和有損模式下的性能比較，每一行數據是一組色彩格式、類別、分辨率均相同的測試序列的平均值，所有的26個測試序列共分為12組，每組1~4個序列，負值表示本文算法與對比算法相比較節省了碼率。圖5給出了SCM, DMC, ISC 3種編碼器在有損編碼模式，AI配置下，兩個典型屏幕圖像序列的率失真曲線。本文所列數據經過嚴格解碼驗證，ISC數據經過微軟交叉驗證[14]。

表1 ISC與SCM和DMC時間比較(%)

表2 ISC模式的CU占圖像面積(%)

從實驗數據可以看出：

(1)無損模式下，本文ISC比SCM最大減少碼率AI 23.3%, RA 14.9%, LB 11.6%；有損模式下，ISC比SCM最多節省碼率15.1%。無損模式下，本文ISC算法比DMC最大減少碼率AI 7.1%, RA 6.9%, LB 6.9%；有損模式下，ISC比DMC最多節省碼率5%。

(2)對于不同類別的測試序列，ISC算法的性能不同。對于YUV TGM(1080p)這一組測試序列ISC算法有最好性能，比SCM無損模式平均提高23.3%，有損模式平均提高Y 13.9%, U 15.1%, V 14.3%；比DMC無損模式平均提高7.1%，有損模式平均提高Y 5.0%, U 5.0%, V 4.9%。對于其他的TGM以及MC類測試序列，ISC也有較好的性能增益。對于A類和CC類測試序列，ISC沒有增益。這是由于，A和CC類序列非常近似于自然圖像，不是嚴格意義上的屏幕圖像，幾乎所有屏幕圖像相關算法均對這兩類序列沒有增益。

(3)ISC算法對于無損編碼性能增益大于有損編碼。這是因為，ISC算法本身是一種無損匹配，搜索過程中不會產生殘差，在無損編碼情況下，避免了殘差熵編碼，較其他會產生殘差的算法更有優勢，獲得的性能增益更多。從表2可以看出，選中ISC的CU的圖像面積的占比，全I幀，無損最多有36.3%，平均21.2%，有損最多有16.9%，平均6.4%，無損模式高于有損模式，并且對于TGM類序列選中的面積明顯高于其他類序列。這些都與ISC性能增益的數據保持一致，選中ISC的CU越多，ISC的增益往往越大。

(4)從圖5的率失真曲線可以看出，在高碼率的情況下，ISC的性能增益大于低碼率的情況。這是因為，隨著量化參數增大，碼率降低，在率失真優化選擇的時候，碼率越來越重要，失真重要性相應降低，沒有失真的ISC模式越來越難以在率失真優化選擇中勝出。

(5)從表1編碼時間來看，ISC算法復雜度增加非常少。從解碼時間來看，ISC比DMC和ISC都有所減少，且ISC性能提升越多的序列，解碼時間越短，這是由于ISC無需進行殘差解碼，重構過程比較簡單。另外，ISC算法的空間開銷也十分有限，以Level 4為例，僅僅需要64 kB搜索緩存和272 kB散列表。

表3 ISC與SCM和DMC性能比較(%)

圖5 3種編碼器率失真(RD)曲線比較

5 結束語

根據屏幕圖像的特點，結合字典編碼工具，在前人工作的基礎上，本文提出了一種基于HEVC的CU自適應的處理屏幕圖像的ISC幀內編碼模式。在復雜度增加很有限的情況下，對屏幕圖像的編碼性能有顯著改善。采用標準測試條件的實驗顯示，在無損編碼模式下，AI, RA, LB 3種配置分別比HEVC降低碼率23.3%, 14.9%, 11.6%，有損編碼模式下，分別比HEVC降低碼率15.1%, 12.0%, 8.3%。ISC在無損編碼方面有著更大的性能增益，這得益于ISC本身的無損匹配。

ISC性能還可以進一步提升：一種方法是，對于有損編碼模式，引入顏色量化的方法，使像素值的分布更加集中，減少整個搜索空間內像素的種類，進行模糊匹配，更容易找到長的匹配串。另一種方法是增加CU內像素自適應掃描順序，即改變現在單一的水平掃描方式，增加垂直掃描，旋轉掃描等其他方式，CU自適應選擇最優掃描方式，可以同時提升有損和無損編碼性能。這些是下一步的研究方向。

[1] Zhou M H, Gao W, Jiang M Q,.. HEVC lossless coding andimprovements[J]., 2012, 22(12): 1839-1843.

[2] Budagavi M and Kwon D K. Video coding using intra motion compensation[C]. Joint Collaborative Team on Video Coding 13th Meeting, Incheon, 2013: JCTVC-M0350.

[3] Pang C, Sole J, Guo L W,.. Intra motion compensation with 2-d MVs[C]. Joint Collaborative Team on Video Coding 14th Meeting, Vienna, 2013: JCTVC-N0256.

[4] Sullivan G and Ohm J R. Meeting report of the fifth meeting of the Joint Collaborative Team on Video Coding (JCT-VC) [C]. Joint Collaborative Team on Video Coding 5th Meeting, Geneva, 2011: JCTVC-E600.

[5] Lin T, Zhang P J, Wang S H,.. Mixed chroma Sampling-rate high efficiency video coding for full- chromascreen content[J]., 2013, 23(1): 173-185.

[6] 張培君, 王淑慧, 周開倫, 等. 融合全色度LZMA與色度子采樣HEVC的屏幕圖像編碼[J]. 電子與信息學報, 2013, 35(1): 196-202.

Zhang P J, Wang S H, Zhou K L,.. Screen content coding by combined full-chroma LZMA and subsampled- chromaHEVC[J].&, 2013, 35(1): 196-202.

[7] Lin T, Wang S H, Zhang P J,.. P2M based dual-coder extension of HEVC[C]. Joint Collaborative Team on Video Coding 12th Meeting, Geneva, 2013: JCTVC-L0303.

[8] Sullivan G J, Ohm J R, Han W J,.. Overview of the high efficiency video coding (HEVC) standard[J]., 2012, 22(12): 1649-1668.

[9] Bossen F, Flynn D, Sharman K,.. Test Software [CP/OL]. https://hevc.hhi.fraunhofer.de/svn/svn_HEVCS oftware/tags/HM-14.0+RExt-7.0+SCM-1.0, 2014.

[10] Yu H P, Cohen R, Rapaka K,.. Common conditions for screen content coding tests[C]. Joint Collaborative Team on Video Coding 17th Meeting, Valencia, 2014: JCTVC-Q1015.

[11] Yu H, Cohen R, Rapaka K,.. Test Sequences[DB/OL]. ftp://hevc@ftp.tnt.uni-hannover.de/testsequences /FrExt-candidate-sequences/screen_content/ScExt-TestSequences, 2014.

[12] Bj?ntegaard G. Calculation of average PSNR differences between RD-Curves[C]. Video Coding Experts Group 13th Meeting, Austin, 2001: VCEG-M33.

[13] Bj?ntegaard G. Improvements of the BD-PSNR model[C]. Video Coding Experts Group 35th Meeting, Berlin, 2008: VCEG-AI11.

[14] Li B and Xu J Z. SCCE4: Cross-check of test 3.3[C]. Joint Collaborative Team on Video Coding 18th Meeting, Sapporo, 2014: JCTVC-R0060.

A New HEVC Intra Mode for Screen Content Coding

Chen Xian-yi①Zhao Li-ping①②Lin Tao①

①(,,200092,)②(,,,314000,)

Because of the poor effect of the traditional coding methods on the screen content coding, considering the screen content is rich in non-continuous tone content, a new intra coding mode based on High Efficiency Video Coding (HEVC), which is called Intra String Copy (ISC), is proposed. The basic idea is adopting the dictionary coding tool on the HEVC Coding Unit (CU) level. When encoding, the current CU pixels are searched and matched in a certain length dictionary window by using Hash table. When decoding, according to the pixels string matching distances and lengths, the current CU pixels in the reconstruction cache are restored by copying the corresponding position pixels. Experiment results show that with little coding complexity increase than HEVC, for typical screen content test sequences, ISC can achieve lossy coding bit-rate saving of 15.1%, 12.0%, 8.3% for All Intra (AI), Random Access (RA), and Low-delay B (LB) configurations, respectively, and lossless coding bit-rate saving of 23.3%, 14.9%, 11.6% for AI, RA, and LB configurations.

High Efficiency Video Coding (HEVC); Screen content coding; Dictionary coding; Hash table

TN919.8

A

1009-5896(2015)11-2685-06

10.11999/JEIT150261

2015-02-22；改回日期：2015-06-10；

2015-07-27

陳先義 chenxy666@126.com

國家自然科學基金(61201226, 61271096)；上海市自然科學基金(12ZR1433800)；高等學校博士學科點專項科研基金(20130072110054)

The National Natural Science Foundation of China (61201226, 61271096); Natural Science Foundation of Shanghai (12ZR1433800); Specialized Research Fund for the Doctoral Program of Higher Education (20130072110054)

陳先義： 男，1981年生，博士生，研究方向為視頻編碼算法.

趙利平： 女，1983年生，博士生，研究方向為視頻編碼算法.

林 濤： 男，1958年生，教授，主要研究方向為多媒體算法和SoC設計.