林 濤，楊玉芬

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

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

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

1 SMHPLC算法描述

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

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

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

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

統(tǒng)計(jì)數(shù)據(jù)為13個(gè)AVS2屏幕、混合內(nèi)容視頻編碼通用測試序列SCC序列(YUV格式的數(shù)據(jù))[10]和從多個(gè)來源中選取的379個(gè)互聯(lián)網(wǎng)圖像WCC序列(RGB格式的數(shù)據(jù))[11-13]，算法采用SMHPLC算法，level設(shè)定為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)概率較高的幾個(gè)offset的概率(出現(xiàn)的次數(shù)占所有offset的百分比)分布.

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

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

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

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

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

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

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

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

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

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

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

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

4 對比實(shí)驗(yàn)

4.1 實(shí)驗(yàn)結(jié)果

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

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

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

表2給出了SCC序列和WCC序列的ORMSM算法與SMHPLC(level 4,level 6,level 8)算法的每個(gè)level的壓縮碼流總字節(jié)數(shù)比值、編碼時(shí)間比值、編碼+解碼時(shí)間比值和3個(gè)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ù)比值、編碼時(shí)間比值、解碼時(shí)間比值、編碼+解碼時(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ù))和復(fù)雜度的比較結(jié)果.因?yàn)閃CC序列的數(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算法與其他算法的復(fù)雜度的比較結(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序列，在編碼+解碼時(shí)間分別平均降低12.43%和9.15%的前提下，編碼性能分別提升了4.65%和3.29%；從表2可知，level=8配置下，編碼時(shí)間分別降低22.15%和13.14%的前提下，編碼性能分別提升了2.59%和2.44%.這說明，ORMSM算法很好地兼顧了高編碼性能和低計(jì)算復(fù)雜度的雙重優(yōu)勢(從圖4可知，SMHPLC算法的計(jì)算復(fù)雜度本身就非常低).從圖3a可知，相比于SMHPLC算法，ORMSM算法的單個(gè)序列的壓縮比都有所提升，有些序列的提升非常顯著.SMHPLC算法的解碼速度都比編碼速度快很多(圖4)，解碼時(shí)間的增多遠(yuǎn)不及編碼時(shí)間的減少部分(表2)，且總編碼+解碼時(shí)間減少(圖4).

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

5 結(jié)語

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