基于串匹配的Offset循環(huán)映射屏幕圖像編碼算法*

林 濤，楊玉芬

(1.同濟大學電子與信息工程學院，上海 200092；2.同濟大學 超大規(guī)模集成電路研究所，上海 200092)

我國第3代AVS(即AVS3)視頻編碼標準需要支持互聯(lián)網(wǎng)圖像編碼[1](Webpage Content Coding,WCC).國際上，最新HEVC標準的3大國際組織ISO，ITU，IEC聯(lián)合發(fā)布的下一代視頻編碼標準(Versatile Video Coding,VVC)需要支持屏幕圖像和互聯(lián)網(wǎng)圖像[2].因此，如何根據(jù)新的需求，設計更加有效的圖像編碼算法和工具，成為具有挑戰(zhàn)性的新課題.針對計算機屏幕圖像，國際上現(xiàn)有的編碼效率最高的算法，是在高效視頻編碼(High Efficiency Video Coding,HEVC)國際標準的屏幕圖像編碼(Screen Content Coding,SCC)擴展版的基礎上改進的串匹配算法[3-5].目前，工業(yè)界使用較多的是HEVC標準的經(jīng)過充分代碼優(yōu)化的面向商用的編碼器x265[6].這些算法和編碼器都存在編解碼復雜度非常高、不適合于軟件實現(xiàn)，特別是在計算能力差異很大的互聯(lián)網(wǎng)設備上軟件實現(xiàn)的嚴峻問題.

具有低復雜度的算法，是在互聯(lián)網(wǎng)設備上廣泛用于屏幕截圖的PNG壓縮算法[7]和以高壓縮率LZ4HC[8]為基礎的高性能低復雜度的串匹配(String Matching with High Performance and Low Complexity,SMHPLC)算法[9].SMHPLC算法充分利用像素點間的冗余，進一步提高了壓縮率，降低了復雜度.但是，SMHPLC算法沒有充分考慮到計算機屏幕圖像和互聯(lián)網(wǎng)圖像編碼匹配參數(shù)offset的內(nèi)在特性，于是筆者在其基礎上提出一種基于串匹配的offset循環(huán)映射屏幕圖像編碼(Offset Rotation Mapping Based on String Matching,ORMSM)算法，并采用全面搜索和特殊位置搜索相結(jié)合的快速搜索方式，進一步提高編碼效率，降低編解碼復雜度.

1 SMHPLC算法描述

SMHPLC算法對參考串搜索的結(jié)果，是交替出現(xiàn)的未匹配像素串(用其長度uml(≥0)和uml個未匹配像素的數(shù)值um作為語法元素來表示)和匹配像素串(用其長度ml(≥1)和當前像素串與參考像素串之間的偏移量offset作為語法元素來表示).ORMSM算法只針對編碼參數(shù)偏移量offset，因此重點對offset的編碼方式進行說明.具體如圖1所示.

圖1 uml，um，ml，Offset的比特分配Fig. 1 Bit Allocation for uml,um,ml,Offset

類型1：前2個比特的數(shù)值為10，表示uml=0且ml=1；后6個比特的數(shù)值為0～61，分別表示offset =1～62，無需額外字節(jié)，數(shù)值為62表示63≤offset≤63+255，需額外1個字節(jié)，數(shù)值為63表示offset>63+255，需使用額外的多個字節(jié).類型2：第1個比特的數(shù)值為0，表示uml = 0且ml > 1；第2—6個比特分配給ml；最后2個比特的數(shù)值為0～1，分別表示offset=1～2，無需額外字節(jié)，數(shù)值為2表示3≤offset≤3+255，需額外1個字節(jié)，數(shù)值為3表示offset>3+255，需使用額外的多個字節(jié).類型3：前2個比特的數(shù)值為11，表示uml> 0且ml≥1；第2，3個比特分配給uml；第4—6個比特分配給ml；最后1個比特的數(shù)值為1表示offset>256，需額外2個字節(jié)，數(shù)值為0表示offset≤256，需額外1個字節(jié).

2 串匹配編碼參數(shù)偏移量Offset的統(tǒng)計特性

統(tǒng)計數(shù)據(jù)為13個AVS2屏幕、混合內(nèi)容視頻編碼通用測試序列SCC序列(YUV格式的數(shù)據(jù))[10]和從多個來源中選取的379個互聯(lián)網(wǎng)圖像WCC序列(RGB格式的數(shù)據(jù))[11-13]，算法采用SMHPLC算法，level設定為4.圖2a示出了SCC序列和WCC序列的offset從左到右為1，w，2到193，w的鄰近值(包括w-6，w-5，w-4,w-3，w-2，w-1，w+1，w+2，w+3，w+4，w+5，w+6，2*w-3，2*w-2，2*w-1，2*w，2*w+1，2*w+2，2*w+3，3*w)的總體分布結(jié)果，其中w為圖像寬度.圖2b示出了SCC序列和WCC序列出現(xiàn)概率較高的幾個offset的概率(出現(xiàn)的次數(shù)占所有offset的百分比)分布.

圖2 SCC序列和WCC序列的偏移量Offset的統(tǒng)計結(jié)果Fig. 2 Statistical Results of the Offset for SCC Sequences and WCC Sequences

偏移量offset至少包括如下2個統(tǒng)計特性：

特性1屏幕圖像和互聯(lián)網(wǎng)圖像的偏移量具有很大的特殊位置w相關(guān)性.

從圖2a可知，offset=1時，offset出現(xiàn)的頻率最高；offset=w時，次之.具體地，從圖2b可知，相比于其他幾個出現(xiàn)概率較高的offset，offset=w時其數(shù)目明顯要高.

特性2特殊位置w的offset只需消耗小于或者等于1個字節(jié).

offset為w時，出現(xiàn)的概率高出其他的offset，并且有些SCC序列和WCC序列分辨率較高，那么offset值就會很大.當這樣的offset采用SMHPLC算法中offset的編碼方式編入碼流時，會消耗很多字節(jié)數(shù).將offset映射為很小的數(shù)，就可以只需消耗小于或者等于1個字節(jié).

3 匹配串特殊位置搜索算法和偏移量Offset循環(huán)映射算法

3.1 匹配串特殊位置搜索算法

針對偏移量offset特性1，SMHPLC算法在進行全面搜索之前先進行特殊位置搜索.即對于當前串，先搜索串匹配偏移量為w的參考串，若該參考串與當前串像素相同，則找到匹配像素串并計算匹配像素串長度，終止全面搜索；否則進行全面搜索，尋找匹配像素串.由于全面搜索包含哈希表和鏈表的更新，以及受到搜索次數(shù)的限制，并且統(tǒng)計結(jié)果顯示offset為特殊位置w的概率很大，因此如果成功進行特殊位置搜索，那么會降低計算復雜度.

3.2 偏移量Offset循環(huán)映射算法

偏移量offset的循環(huán)映射算法是將w映射為1，1映射為2，2映射為3，…，w-1映射為w.具體地，編碼前先將offset的映射值放入1維數(shù)組中，在offset編入碼流之前，從1維數(shù)組中取映射值進行offset循環(huán)映射，再將映射后的offset減1，并按照第1節(jié)中3種類型的offset的編碼方式編入碼流.

對于SCC序列和WCC序列本身而言，圖像的寬度從10到8k，offset為圖像寬度的情況下，可能需要消耗6個比特或者1個字節(jié)或者多個字節(jié).采用offset的循環(huán)映射算法，offset只需消耗小于或者等于1個字節(jié).對于類型1和類型2，只需要分別利用最后6個比特和2個比特表示offset數(shù)值，無需額外字節(jié)；對于類型3，即使圖像的寬度大于256，也只需額外1個字節(jié)表示offset數(shù)值.這樣，消耗的比特數(shù)大大減少，提高了編碼性能.

4 對比實驗

4.1 實驗結(jié)果

為了說明ORMSM算法的特性，將其與現(xiàn)有的SMHPLC算法、PNG算法[7]和x265算法[6]進行比較.測試數(shù)據(jù)與統(tǒng)計數(shù)據(jù)相同.實驗環(huán)境配置為Intel(R) Core(TM) i5 CPU 760 @2.8 GHz (4核處理器)、8 GB內(nèi)存和Win7 x64位操作系統(tǒng)的服務器.每次執(zhí)行1個任務.

表1 編碼算法的配置參數(shù)Table 1 Configurations of the Coding Algorithms

表1給出了5種算法的參數(shù)配置.level是字典編碼中，在編碼效率與編碼復雜度之間進行權(quán)衡的配置參數(shù)，表示在哈希鏈上搜索的次數(shù)為2level-1.一般而言，level越大，編碼時間越長，編碼性能越好.

表2給出了SCC序列和WCC序列的ORMSM算法與SMHPLC(level 4,level 6,level 8)算法的每個level的壓縮碼流總字節(jié)數(shù)比值、編碼時間比值、編碼+解碼時間比值和3個level的平均值.

表2 ORMSM算法與SMHPLC算法的SCC序列和WCC序列的比較結(jié)果Table 2 Experimental Results Between ORMSM and SMHPLC (SCC Sequences and WCC Sequences) %

表3給出了SCC序列和WCC序列的ORMSM-level 4算法與PNG算法(fast，default，slow配置)及x265算法(fast 0，fast 1配置)的壓縮碼流總字節(jié)數(shù)比值、編碼時間比值、解碼時間比值、編碼+解碼時間比值.

表3 ORMSM-Level 4算法與PNG算法及x265算法的SCC序列和WCC序列的比較結(jié)果Table 3 Experimental Comparison Results Among ORMSM-Level 4 and PNG and x265 (SCC Sequences and WCC Sequences) %

圖3和圖4分別示出了SCC序列和WCC序列的ORMSM算法與其他算法的編碼效率(壓縮比=原始序列字節(jié)數(shù)/壓縮后碼流字節(jié)數(shù))和復雜度的比較結(jié)果.因為WCC序列的數(shù)據(jù)較多，所以按照SMHPLC算法的壓縮比的升序排列，ORMSM算法的壓縮比的順序隨著SMHPLC算法自動改變.

圖3 SCC序列和WCC序列的ORMSM算法與其他算法的編碼效率(壓縮比)的比較結(jié)果Fig. 3 Coding Efficiency (Compression Ratio) Comparison Results Among ORMSM and Other Comparison Coding Algorithms for SCC Sequences and WCC Sequences

圖4 SCC序列和WCC序列的ORMSM算法與其他算法的復雜度的比較結(jié)果Fig. 4 Complexity Comparison Results Among ORMSM and Other Comparison Coding Algorithms for SCC Sequences and WCC Sequences

4.2 討論

ORMSM算法與SMHPLC算法相比較，對于SCC序列和WCC序列，在編碼+解碼時間分別平均降低12.43%和9.15%的前提下，編碼性能分別提升了4.65%和3.29%；從表2可知，level=8配置下，編碼時間分別降低22.15%和13.14%的前提下，編碼性能分別提升了2.59%和2.44%.這說明，ORMSM算法很好地兼顧了高編碼性能和低計算復雜度的雙重優(yōu)勢(從圖4可知，SMHPLC算法的計算復雜度本身就非常低).從圖3a可知，相比于SMHPLC算法，ORMSM算法的單個序列的壓縮比都有所提升，有些序列的提升非常顯著.SMHPLC算法的解碼速度都比編碼速度快很多(圖4)，解碼時間的增多遠不及編碼時間的減少部分(表2)，且總編碼+解碼時間減少(圖4).

ORMSM-level 4算法與PNG算法、x265算法相比較，兼具了高編碼性能和超低計算復雜度的優(yōu)勢.從表3可知，相比于PNG(fast配置)算法和x265算法(fast 0配置)，ORMSM-level 4算法在編碼時間和解碼時間降低了幾十倍的前提下，編碼性能得到了進一步的提升或者幾乎沒有損失.PNG算法和x265算法的其他配置(default和slow)與ORMSM-level 4算法的相比，編解碼復雜度成倍地增加(最多增加了80倍以上)，但編碼效率提升不顯著(不超過40%).從圖3b和圖4可知，相比于PNG(fast配置)和x265算法(fast 0配置)，ORMSM-level 4算法在總編碼時間、總解碼時間和總編碼+解碼時間顯著減少的前提下，編碼效率顯著提升，且ORMSM算法的平均壓縮比都是最高的，遠遠超過PNG算法和x265算法.

5 結(jié)語

通過串匹配算法來分析計算機屏幕圖像和互聯(lián)網(wǎng)圖像的圖像編碼的編碼參數(shù)offset的統(tǒng)計特性，在SMHPLC算法的基礎上，提出了ORMSM算法.將ORMSM算法與SMHPLC，PNG，HEVC(x265)算法進行比較，結(jié)果表明ORMSM算法具有明顯的高性能和低復雜度的雙重優(yōu)勢.接下來的主要工作是進一步優(yōu)化ORMSM算法，包括對最大的編碼單元(Largest Coding Unit,LCU)的一維串匹配(1-Dimension String Matching,1DSM)和語法元素編碼方式的優(yōu)化.