一種高性能低復(fù)雜度的基于串匹配的屏幕圖像無(wú)損壓縮算法

林 濤 蔡文婷 陳先義 周開(kāi)倫 王淑慧

?

一種高性能低復(fù)雜度的基于串匹配的屏幕圖像無(wú)損壓縮算法

林 濤 蔡文婷*陳先義 周開(kāi)倫 王淑慧

(同濟(jì)大學(xué)超大規(guī)模集成電路研究所 上海 200092)

傳統(tǒng)無(wú)損壓縮算法對(duì)屏幕圖像的壓縮效果不佳。該文根據(jù)典型屏幕圖像的特性，以LZ4HC(LZ4High Compression)算法為具體實(shí)現(xiàn)基礎(chǔ)，提出一種基于串匹配的高性能低復(fù)雜度(String Matching with High Performance and Low Complexity, SMHPLC)的屏幕圖像無(wú)損壓縮算法。相對(duì)于傳統(tǒng)字典編碼無(wú)損壓縮算法，新算法提出了以像素為搜索和匹配單位，對(duì)未匹配串長(zhǎng)度、匹配串長(zhǎng)度以及匹配偏移量這3個(gè)編碼參數(shù)進(jìn)行聯(lián)合優(yōu)化編碼，并對(duì)參數(shù)進(jìn)行映射編碼。實(shí)驗(yàn)結(jié)果表明，SMHPLC具有高性能和低復(fù)雜度的綜合優(yōu)勢(shì)，大幅降低編碼復(fù)雜度，提高了編碼效率。使用移動(dòng)的文字和圖形類(lèi)的AVS2通用測(cè)試序列作為測(cè)試對(duì)象，對(duì)于YUV和RGB兩種格式，SMHPLC算法比LZ4HC總體節(jié)省碼率分別為22.4%，21.2%，同時(shí)編碼復(fù)雜度降低分別為35.5%，46.8%。

無(wú)損壓縮算法；屏幕圖像編碼；字典編碼；LZ4High Compression (LZ4HC)

1 引言

隨著移動(dòng)互聯(lián)網(wǎng)的飛速發(fā)展以及虛擬化技術(shù)的日益成熟，在市場(chǎng)需求的推動(dòng)下，移動(dòng)平臺(tái)和云計(jì)算平臺(tái)[1]逐步得到廣泛的應(yīng)用。云計(jì)算平臺(tái)作為傳統(tǒng)計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)發(fā)展融合的產(chǎn)物，通過(guò)整合分布式資源，可以把海量的數(shù)據(jù)存儲(chǔ)和程序執(zhí)行遷移到云端，提高安全性，降低成本和能耗[2]。作為云計(jì)算平臺(tái)的典型應(yīng)用之一，桌面云可以實(shí)現(xiàn)用戶(hù)在瘦客戶(hù)端或者其他與網(wǎng)絡(luò)連接的設(shè)備(如普通臺(tái)式機(jī)、筆記本電腦、智能手機(jī)等)通過(guò)網(wǎng)絡(luò)訪問(wèn)數(shù)據(jù)中心云端服務(wù)器和應(yīng)用程序[3]。用戶(hù)由傳統(tǒng)的終端至應(yīng)用的訪問(wèn)模型變?yōu)閺谋镜乜蛻?hù)端連接到桌面云獲取到應(yīng)用并顯示在屏幕上。因此，提高屏幕圖像的傳輸效率是亟需解決的重要問(wèn)題[4]。

屏幕圖像包含自然圖片和文本圖形等。對(duì)于拍攝的自然圖像，現(xiàn)有的圖像和視頻編碼標(biāo)準(zhǔn)(如JPEG, H.264/AVC, AVS, HEVC等)具有出色的編碼性能。但對(duì)于計(jì)算機(jī)產(chǎn)生的文本、圖形、圖標(biāo)等區(qū)域，傳統(tǒng)視頻編解碼器的效果并不理想。為了提高屏幕圖像編碼的性能，國(guó)際電信聯(lián)盟(ITU-T)、國(guó)際標(biāo)準(zhǔn)化組織(ISO)和國(guó)際電工委員會(huì)(IEC)聯(lián)合啟動(dòng)了基于屏幕圖像編碼(Screen Content Coding, SCC)標(biāo)準(zhǔn)的研究。

對(duì)于屏幕圖像中非連續(xù)色調(diào)內(nèi)容，基于串匹配的字典編碼有很好的壓縮性能。字典編碼的基本原理是建立一個(gè)已經(jīng)完成編碼的歷史數(shù)據(jù)的空間(字典)，在其中尋找待編碼數(shù)據(jù)的匹配串(即參考串)，以編碼匹配參數(shù)(匹配的位置，匹配的長(zhǎng)度)替代當(dāng)前數(shù)據(jù)串寫(xiě)入碼流。當(dāng)前主流的字典編碼算法中，Gzip和zlib有很高的壓縮率但處理器資源消耗較大，速度較慢[9]。Bzip2和7zip算法有很好的壓縮效果，但對(duì)計(jì)算資源的消耗比Gzip和zlib還要高得多。LZ4作為當(dāng)今高性能的無(wú)損壓縮算法的典型代表，編碼速度遠(yuǎn)超zlib并且解碼速度近乎是其5倍。它的編碼速度能達(dá)到超過(guò)400 MB/s，解碼速度也能超過(guò)1.8 GB/s。作為L(zhǎng)Z4的高壓縮率(High Compression, HC)版本[13]，LZ4HC以更全面的搜索方式彌補(bǔ)了LZ4進(jìn)行快速搜索而引起壓縮比的損失，雖然編碼時(shí)間有所增加，但解碼時(shí)間不受影響，是目前商用屏幕圖像編碼產(chǎn)品的首選算法。

屏幕圖像由像素構(gòu)成。而傳統(tǒng)的LZ4和LZ4HC等算法都是以字節(jié)為單位，將像素的3個(gè)分量看成3個(gè)獨(dú)立的字節(jié)，未充分利用像素的冗余，尤其是匹配串的位置可能不是整像素的邊界而降低了編碼效率。

針對(duì)傳統(tǒng)字典編碼無(wú)損壓縮算法的這些缺陷，本文提出了基于像素為單位的字典編碼無(wú)損壓縮算法，結(jié)合典型屏幕圖像的特有統(tǒng)計(jì)特性，采用對(duì)匹配參數(shù)進(jìn)行映射和可變字節(jié)聯(lián)合優(yōu)化編碼的方式進(jìn)一步提高壓縮性能，同時(shí)也大大降低計(jì)算復(fù)雜度。

2 本文提出的方法

本文以LZ4HC算法為具體實(shí)現(xiàn)的基礎(chǔ)，提出一種充分利用屏幕圖像的數(shù)據(jù)特性的基于串匹配(String Matching)的高性能低復(fù)雜度(High Performance Low Complexity)屏幕圖像無(wú)損壓縮方法：SMHPLC算法。

2.1 傳統(tǒng)的LZ4HC算法的基本原理

LZ4HC的壓縮后碼流的數(shù)據(jù)[14]由4個(gè)部分組成：未匹配串長(zhǎng)度、未匹配串字節(jié)、匹配串長(zhǎng)度及匹配偏移量。如圖1所示，寫(xiě)入碼流的數(shù)據(jù)依次為1個(gè)字節(jié)的Token, 0至多個(gè)字節(jié)的Literal Length (未匹配串長(zhǎng)度)，0至多個(gè)字節(jié)的Literals(未匹配串字節(jié))，兩個(gè)字節(jié)的匹配串Offset(匹配偏移量)以及0至多字節(jié)的Match Length(匹配串長(zhǎng)度)。Token的高4位表示Literal Length，低4位表示Match Length，取值范圍均為0~15。當(dāng)未匹配串長(zhǎng)度或者匹配串長(zhǎng)度小于15時(shí)，則不需要消耗額外的字節(jié)，否則剩下的長(zhǎng)度1次消耗1 Byte寫(xiě)入碼流，直到寫(xiě)入的最后一個(gè)字節(jié)小于255，每個(gè)字節(jié)表示的長(zhǎng)度范圍是0~255。Offset是當(dāng)前串距離參考串的偏移量，以Byte為單位，范圍是1~65535。匹配串的默認(rèn)最小允許長(zhǎng)度為4 Byte，因此將Match Length減去4后再進(jìn)行編碼，實(shí)際最小值為0。下文中提到的Match Length均為實(shí)際編碼的Match Length。

LZ4HC利用散列表(Hash Table)查找最佳匹配串，通過(guò)鍵值對(duì)(key, value)的映射關(guān)系進(jìn)行搜索。默認(rèn)的Hash表大小是16 kB。Hash表中存放具有相同Hash值且離當(dāng)前待編碼位置最近的參考點(diǎn)與參考基(Base)之間的距離，如式(1)所示。LZ4HC中還分配了鏈表(Chain Table)數(shù)組用來(lái)多次嘗試匹配以獲取最長(zhǎng)匹配串，當(dāng)前位置對(duì)應(yīng)的參考索引(index)取低16位作為鏈表的下標(biāo)，如式(2)，式(3)所示，計(jì)算index與Hash表中對(duì)應(yīng)值之間的差值delta，并將其存入鏈表數(shù)組中。下面提到的索引均為當(dāng)前地址到Base的距離，默認(rèn)的Base位置為輸入的壓縮數(shù)據(jù)塊的起始位置減去64 kB。默認(rèn)鏈表使用內(nèi)存是64 kB，故Offset只需要兩個(gè)字節(jié)。對(duì)當(dāng)前待匹配串前面的字符串按每4 Byte采用至之間的黃金分割素?cái)?shù)2654435761U計(jì)算Hash值。搜索Level可設(shè)定的最大值為16，即最大搜索次數(shù)為。

(2)

(3)

搜索過(guò)程如下：

圖1 數(shù)據(jù)塊的輸出碼流的格式

(1)當(dāng)前地址指針ip，當(dāng)前地址索引為index，上一次已編碼的串的起始地址索引為nextTo Update。若index

(2)計(jì)算當(dāng)前待編碼位置的Hash值hcur。最佳匹配長(zhǎng)度ml 置為0。

(3)若該位置為首次尋找匹配，則根據(jù)hcur獲取Hash表中的匹配位置；否則，從Chain Table中獲取匹配位置。匹配位置索引matchIdx，對(duì)應(yīng)的地址為ref。

(4)如果ref在限制條件的范圍內(nèi)且不超過(guò)搜索次數(shù)，

(a)如果ref等于ip，繼續(xù)計(jì)算匹配長(zhǎng)度。獲得該匹配位置的匹配長(zhǎng)度為mlt。若mlt>ml，則ml=mlt。

(b)否則跳轉(zhuǎn)到步驟(3)。

不符合匹配前提條件，則跳轉(zhuǎn)到步驟(5)

(5)按照?qǐng)D1數(shù)據(jù)塊的輸出格式編碼Literal Length, Literals, Offset, Match Length，寫(xiě)入碼流中。

默認(rèn)的最小匹配串長(zhǎng)度是4 Byte，若當(dāng)前位置未搜索成功，則將當(dāng)前指針ip右移4 Byte繼續(xù)進(jìn)行下輪搜索。默認(rèn)設(shè)置下，當(dāng)待編碼串長(zhǎng)度大于13 Byte的時(shí)候才會(huì)進(jìn)行Hash搜索匹配，且最后5 Byte總是Literals。傳統(tǒng)的LZ4HC在Hash搜索后還會(huì)擴(kuò)大范圍進(jìn)行第2次搜索，本文改進(jìn)該算法時(shí)并沒(méi)有采用。

2.2 SMHPLC算法

針對(duì)屏幕圖像特性和傳統(tǒng)字典編碼算法的缺陷，本文提出如下改進(jìn)以提高編碼效率和降低計(jì)算復(fù)雜度：

(1)將基于字節(jié)的搜索和匹配改為基于像素的搜索和匹配。

(2)對(duì)Literal Length和Match Length等匹配參數(shù)進(jìn)行聯(lián)合優(yōu)化編碼。

(3)建立映射數(shù)組，將匹配參數(shù)中出現(xiàn)頻度很高且數(shù)值很大的區(qū)段映射為數(shù)值較小的區(qū)段。

SMHPLC算法的整體框架如圖2所示，主要分為更新Hash Table和Chain Table，在最大搜索次數(shù)的限制內(nèi)尋找最佳匹配，和編碼 (包括3個(gè)編碼參數(shù)，以及復(fù)制Literals)這3個(gè)部分。

2.2.1 基于像素的搜索和匹配 對(duì)輸入的編碼塊(也可以是整幅圖像)按照水平或者垂直掃描順序把圖像數(shù)據(jù)排列成像素串，如圖3所示，以YUV色彩格式為例，將Y, U, V 3個(gè)分量以該順序打包成一個(gè)像素Pixel(YUV)?；诖耍疚膶鹘y(tǒng)算法中連續(xù)4 Byte計(jì)算Hash值的方式改為計(jì)算1個(gè)像素的Hash值，即連續(xù)的3 Byte的Hash值。所以在進(jìn)行Hash搜索前，以像素為單位增加index，將位置信息存入Hash Table和Chain Table中。在搜索最佳匹配串時(shí)，匹配串的長(zhǎng)度也以像素為單位來(lái)計(jì)算，最小匹配串長(zhǎng)度則是一個(gè)像素(即3 Byte)。這樣，既能找到更長(zhǎng)匹配串，也能將有關(guān)匹配參數(shù)的數(shù)值縮小為原來(lái)的1/3，從而進(jìn)一步提高編碼的性能。

圖2 SMHPLC算法的整體框架

圖3 像素打包排列

本文提出的方法對(duì)YUV色彩格式或者RGB色彩格式的屏幕圖像均有效，同時(shí)對(duì)按照水平或者垂直掃描順序排列的屏幕圖像也都同樣有效。對(duì)于大多數(shù)屏幕內(nèi)容，水平掃描比垂直掃描的編碼壓縮性能相對(duì)高一些。但對(duì)于有些屏幕內(nèi)容，如垂直線(xiàn)條比較多的屏幕圖像，垂直掃描的編碼壓縮性能高一些。

2.2.2 對(duì)匹配參數(shù)的聯(lián)合優(yōu)化編碼 使用LZ4HC和SMHPLC，以8個(gè)移動(dòng)的文字和圖形類(lèi)的AVS2屏幕與混合內(nèi)容視頻編碼通用測(cè)試序列[15]為統(tǒng)計(jì)樣本空間，對(duì)測(cè)試數(shù)據(jù)分別進(jìn)行搜索Level為4時(shí)基于像素和字節(jié)匹配的Literal Length和Match Length的聯(lián)合分布統(tǒng)計(jì)。聯(lián)合分布結(jié)果如表1所示，按像素匹配時(shí)，Literal Length = 0同時(shí)Match Length = 0的情形比例達(dá)到24.10%，而按字節(jié)匹配時(shí)只占4.12%。由此可見(jiàn)，按像素匹配時(shí)，如果沿用LZ4HC的方法，Token的高4位和低4位均為0，另外還消耗2 Byte編碼Offset，總共消耗3 Byte來(lái)編碼這種匹配串。實(shí)際上，可能更好的策略是在Token中拿出1 bit或者2 bit作為Flag，將剩下的比特用來(lái)編碼Offset，在某些情況下可以不需要額外的字節(jié)就能完成一個(gè)匹配串的編碼。因此，本文進(jìn)行了如下兩種方案的嘗試：

方案1：

A類(lèi) Token中的最高位0表示Literal Length和Match Length 均為0的情形；

B類(lèi) Token中的高兩位10表示Literal Length等于0且Match Length大于0的情形；

C類(lèi) Token中的高兩位11表示Literal Length大于0且Match Length不小于0的情形。

表1 Literal Length和Match Length聯(lián)合分布(%)

方案2：

A類(lèi) Token中的最高位0表示Literal Length等于0且Match Length大于0的情形；

B類(lèi) Token中的高兩位10表示Literal Length和Match Length均為0的情形；

C類(lèi) Token中的高兩位11表示Literal Length大于0且Match Length不小于0的情形。

經(jīng)實(shí)驗(yàn)，方案2優(yōu)于方案1，故本文采用了方案2，并在此基礎(chǔ)上繼續(xù)對(duì)3個(gè)匹配參數(shù)的編碼進(jìn)行改進(jìn)。

傳統(tǒng)的LZ4HC編碼Match Length和Literal Length都是用1 Byte表示0～255，多個(gè)字節(jié)逐個(gè)累加的方式編碼1個(gè)長(zhǎng)度。對(duì)上述測(cè)試序列進(jìn)行Match Length的統(tǒng)計(jì)，長(zhǎng)度小于256所占比例高達(dá)99%，除Token編碼的長(zhǎng)度外最多只需要1 Byte就可以編碼Match Length的整個(gè)長(zhǎng)度。因此，本文提出了根據(jù)掩碼分段編碼的算法(記為MaskLevelExtend)，編碼部分描述如表2所示。

這樣，根據(jù)輸入的編碼參數(shù)值所在的掩碼區(qū)間分成4段進(jìn)行編碼，以只利用Token中分配的比特?cái)?shù)，或者還需要額外的1 Byte、2 Byte或更多字節(jié)進(jìn)行編碼，可以大幅減少字節(jié)消耗，提高數(shù)據(jù)壓縮率。

基于像素匹配的Offset的最大值為65535/3= 21845，經(jīng)統(tǒng)計(jì)Offset小于255的部分占總數(shù)的70.3%，因此為所有的Offset都分配兩個(gè)字節(jié)造成了很大的浪費(fèi)。針對(duì)C類(lèi)Literal Length>0且Match Length=0和Literal Length>0且Match Length>0的情形，本文提出在Token中再利用1 bit作為Offset是否小于255的標(biāo)志，當(dāng)Offset小于255時(shí)只分配1 Byte，以此進(jìn)一步提高壓縮率。對(duì)于A類(lèi)和B類(lèi)，由于Literal Length等于0，可以將Token中除去標(biāo)志位以外剩下的比特共同編碼Match Length和Offset，通過(guò)嘗試不同的分配策略找出最佳方案。經(jīng)試驗(yàn)，A, B, C類(lèi)中最終的Token比特分配如圖4所示。

圖4 A, B, C類(lèi)中Token的比特分配

表2 掩碼分段編碼的算法的編碼

2.2.3 對(duì)匹配參數(shù)的映射 映射的思想是將匹配參數(shù)中部分出現(xiàn)頻度較高且需要較多字節(jié)編碼的值映射為頻度較小且字節(jié)消耗較少的值，從而減少總體字節(jié)消耗。根據(jù)對(duì)Match Length和Offset的頻度統(tǒng)計(jì)，建立映射數(shù)組，從數(shù)組中取出該匹配參數(shù)值對(duì)應(yīng)的映射值后，再對(duì)該映射值進(jìn)行后續(xù)的編碼。

本文采用了整體映射與局部映射相結(jié)合的方案，取值如表3所示。對(duì)于整體映射，考慮Token中各編碼參數(shù)的比特分配以及頻度統(tǒng)計(jì)，建立上文中A, B, C 3類(lèi)情況均適用的Offset映射數(shù)組。對(duì)于局部映射，統(tǒng)計(jì)情況A中Match Length和Offset的聯(lián)合頻度，對(duì)滿(mǎn)足映射要求的Match Length和Offset建立聯(lián)合映射對(duì)，在編碼參數(shù)前進(jìn)行局部一一映射。由于情況B實(shí)際只編碼Offset，比較不同的掩碼分段區(qū)間內(nèi)出現(xiàn)的頻度，選取合適的數(shù)值進(jìn)行映射。映射的具體過(guò)程為，在進(jìn)行分類(lèi)編碼前，首先對(duì)Offset進(jìn)行整體映射，從映射數(shù)組中取得對(duì)應(yīng)的映射值作為接下來(lái)編碼的Offset。然后在A, B兩種情況下，對(duì)待編碼的Match Length, Offset進(jìn)行該情況下的局部映射，再對(duì)參數(shù)的映射值進(jìn)行編碼。由于情況C下Token中用于編碼的Match Length的比特?cái)?shù)較少，所以該情況未進(jìn)行局部映射。

表3 整體映射和局部映射取值

在LZ4HC算法基礎(chǔ)上實(shí)現(xiàn)的SMHPLC算法的流程如圖5所示，F(xiàn)lag的取值范圍為0, 2, 3，分別對(duì)應(yīng)A, B, C 3類(lèi)情形。

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

本文的實(shí)驗(yàn)在lz4-r127[16]代碼基礎(chǔ)上實(shí)現(xiàn)SMHPLC算法，并且使用表4所示8個(gè)AVS2屏幕與混合內(nèi)容視頻編碼通用測(cè)試序列的前10幀來(lái)測(cè)試和評(píng)估SMHPLC算法的性能和復(fù)雜度。

表4 8個(gè)AVS2屏幕與混合內(nèi)容視頻編碼通用測(cè)試序列

圖5 SMHPLC算法編碼流程

每個(gè)序列有RGB和YUV兩種色彩格式。實(shí)驗(yàn)的硬件環(huán)境為Intel(R) Xeon(R) CPU X5460 @3.16 GHZ。

實(shí)驗(yàn)比較了傳統(tǒng)的LZ4HC算法，在其基礎(chǔ)上實(shí)現(xiàn)的SMHPLC算法，zlib算法和LZMA算法之間的性能和復(fù)雜度(使用HEVC標(biāo)準(zhǔn)制定工作組和AVS標(biāo)準(zhǔn)制定工作組規(guī)定的編解碼運(yùn)行時(shí)間來(lái)衡量復(fù)雜度)。

表5和表6是兩種色彩格式下SMHPLC算法和傳統(tǒng)的LZ4HC算法在相同的搜索Level下總體的壓縮后碼流比特率、編碼時(shí)間和解碼時(shí)間的比較。比較的搜索Level的范圍為4至14，隨著搜索Level的增加，YUV格式下SMHPLC算法與LZ4HC算法的比特率之比和解碼時(shí)間之比均逐步減少，雖然編碼時(shí)間的比值有一定的增大，但SMHPLC算法的編碼速度依然遠(yuǎn)超過(guò)LZ4HC算法。RGB格式下這兩種算法的比特率之比、解碼時(shí)間之比、編碼時(shí)間之比與YUV格式下有相似的變化趨勢(shì)。LZ4HC本身是一種極低復(fù)雜度的算法，YUV格式下SMHPLC算法減少了35.5%~47.5%的編碼時(shí)間，性能卻提高了17.3%~22.4%，RGB格式下減少了45.3%~51.3%的編碼時(shí)間，性能提升了18.4%~21.2%。同時(shí)，SMHPLC算法仍然保持著很快的解碼速度，YUV格式下解碼時(shí)間只增加了15.7%~29.9%，RGB格式下解碼時(shí)間只增加了14.9％~25.7%。

表5 YUV格式下SMHPLC算法與LZ4HC算法的比較

表6 RGB格式下SMHPLC算法與LZ4HC算法的比較

表4, 表5中不同的搜索Level的LZ4HC算法的平均比特率都不同，從約100 Mbps到130 Mbps不等。實(shí)際上，RGB序列FLYG在Level為4時(shí)的比特率是342389.7 kbps，而YUV序列CLP在Level為14時(shí)的比特率是55120.8 kbps。這些實(shí)驗(yàn)結(jié)果表明本文的方法對(duì)不同比特率的碼流都有效。由于對(duì)比算法LZ4HC，zlib與本文方法均為無(wú)損壓縮算法，所以壓縮后重建圖像都具有與原始圖像相同的圖像質(zhì)量。

表7比較了搜索Level為6至9時(shí)兩種色彩格式下zlib算法與SMHPLC算法之間的編碼性能和復(fù)雜度。在相同Level下對(duì)于YUV和RGB序列，zlib算法總體比特率分別比SMHPLC算法增大2.4%~5.2%與1.3%~5.7%，反而消耗了超過(guò)1倍至2倍的總體編碼時(shí)間，總體解碼時(shí)間也多出了1倍左右。

表8比較了搜索Level為2的LZMA與搜索Level為12時(shí)兩種色彩格式下SMHPLC算法之間的編碼性能和復(fù)雜度。對(duì)于YUV序列，LZMA-2算法的總體比特率比SMHPLC-12算法低10.3%，但是需要消耗更多的編解碼時(shí)間，編碼時(shí)間增加了178.3%，同時(shí)解碼時(shí)間增加了接近4倍。對(duì)于RGB序列，LZMA-2算法的總體比特率只比SMHPLC-12算法低6.4%，但編碼時(shí)間增加了190.7%，解碼時(shí)間增加了超過(guò)4倍。

表7 zlib算法與SMHPLC算法的比較

表8 LZMA-2算法與SMHPLC-12算法的比較

4 結(jié)束語(yǔ)

通過(guò)分析屏幕圖像的特點(diǎn)，本文提出了基于像素串匹配的SMHPLC算法，在對(duì)典型屏幕圖像測(cè)試序列的Literal Length, Match Length以及Offset這3個(gè)匹配參數(shù)進(jìn)行統(tǒng)計(jì)和分析的基礎(chǔ)上，提出了分類(lèi)編碼的思想對(duì)這些參數(shù)進(jìn)行聯(lián)合優(yōu)化編碼。此外，還引入了參數(shù)映射編碼。SMHPLC算法不但大幅減少編碼復(fù)雜度，而且大幅提升了壓縮性能，降低了比特率。從實(shí)驗(yàn)結(jié)果來(lái)看，對(duì)于YUV序列Level為13時(shí)SMHPLC算法對(duì)于測(cè)試序列的壓縮后碼流比特率比LZ4HC算法總體降低了22.4%，對(duì)于RGB序列Level為12時(shí)總體降低了21.2%。SMHPLC算法達(dá)到的對(duì)屏幕圖像的壓縮后碼流比特率比zlib算法對(duì)于YUV和RGB序列分別降低了2.4%~5.2%和1.3%~5.7%，減少的編碼時(shí)間均超過(guò)1/2，同時(shí)解碼時(shí)間也都降低了約1/2。LZMA-2算法雖然在比特率上比SMHPLC-12算法有一定的優(yōu)勢(shì)，但是其編解碼時(shí)間卻比SMHPLC算法長(zhǎng)很多，特別是對(duì)于RGB序列編碼時(shí)間長(zhǎng)190.7％，同時(shí)其解碼時(shí)間也長(zhǎng)了超過(guò)4倍，但是碼流比特率只降低了6.4%。所以SMHPLC算法在高性能低復(fù)雜度方面的綜合優(yōu)勢(shì)是其他算法難以比擬的。

對(duì)SMHPLC算法還可以做進(jìn)一步優(yōu)化。在降低比特率方面，可以對(duì)匹配參數(shù)采用編碼效率更高的熵編碼方案，進(jìn)一步提高整體編碼效率；在降低算法復(fù)雜度方面，可以考慮更佳的Chain Table的存儲(chǔ)和索引的方式，減少搜索時(shí)間。

[1] LIN Tao, ZHOU Kailun, and WANG Shuhui. Cloudlet-screen computing: A client-server architecture with top graphics performance[J]., 2013, 13(2): 96-108. doi: 10.1504/ IJAHUC.2013.054174.

[2] 李德毅, 張?zhí)炖? 黃立威. 位置服務(wù)：接地氣的云計(jì)算[J]. 電子學(xué)報(bào), 2014, 42(4): 786-790. doi: 10.3969/j.issn.0372-2112. 2014.04.025.

LI Deyi, ZHANG Tianlei, and HUANG Liwei. A down-to-earth cloud computing: Location-based service[J]., 2014, 42(4): 786-790. doi: 10.3969/ j.issn.0372-2112.2014.04.025.

[3] WANG Haiyang, WANG Feng, LIU Jiangchuan,Enabling customer-provided resources for cloud computing: Potentials, challenges, and implementation[J].,2015, 26(7): 1874-1876. doi: 10.1109/TPDS.2014.2339841.

[4] SHIRMOHAMMADI S, ABDALLA M, AHMED D T,Introduction to the specialsection on visual computing in the cloud: Cloud gaming and virtualization[J].2015, 25(12): 1955-1959. doi: 10.1109/TCSVT.2015.2473075.

[5] 張培君, 王淑慧, 周開(kāi)倫, 等. 融合全色度LZMA與色度子采樣HEVC的屏幕圖像編碼[J]. 電子與信息學(xué)報(bào), 2013, 35(1): 196-202. doi: 10.3724/SP.J.1146.2012.00746.

ZHANG Peijun, WANG Shuhui, ZHOU Kailun,Screen content coding by combined full-chroma LZMA and subsampled-chroma HEVC[J].&, 2013, 35(1): 196-202. doi: 10.3724/ SP.J.1146.2012.00746.

[6] 陳先義, 趙利平, 林濤. 一種新的用于屏幕圖像編碼的HEVC幀內(nèi)模式[J]. 電子與信息學(xué)報(bào), 2015, 37(11): 2685-2690. doi: 10.11999/JEIT150261

CHEN Xianyi, ZHAO Liping, and LIN Tao. A new HEVC intra mode for screen content coding[J].&, 2015, 37(11): 2685-2690. doi: 10.11999/JEIT150261.

[7] LIN Tao, ZHANG Peijun, WANG Shuhui,. Mixed chroma sampling-rate high efficiency video coding for full-chroma screen content[J]., 2013, 23(1): 173-185. doi: 10.1109/TCSVT.2012.2223871.

[8] ZHAO Liping, LIN Tao, ZHOU Kailun,. Pseudo 2D string matching technique for high efficiency screen content coding[J]., 2016, 18(3): 339-350. doi: 10.1109/TMM.2015.2512539.

[9] DHAWALE N. Implementation of Huffman algorithm and study for optimization[C]. International Conference on Advances in Communication and Computing Technologies (ICACACT), Mumbai, 2014: 1-6. doi: 10.1109/EIC.2015. 7230711.

[10] BARTIK M, UBIK S, and KUBALIK P. LZ4 compression algorithm on FPGA[C]. IEEE International Conference on Electronics, Circuits, and Systems(ICECS), Cairo, 2015: 179-182. doi: 10.1109/ICECS.2015.7440278.

[11] ALMEIDA S, OLIVEIRA V, PINA A,. Two High-performance Alternatives to ZLIB Scientific-data Compression. Computational Science and Its applicationsICCSA 2014[M]. Switzerland, Springer International Publishing, 2014: 623-638.

[12] SANG D K, LEE S M, SANG M L,. Compression Accelerator for Hadoop Appliance. Internet of Vehicles – Technologies and Services[M]. Switzerland, Springer International Publishing, 2014: 416-423.

[13] YANN Collet. LZ4-extremely fast compression[OL]. https:// github.com/Cyan4973/lz4.git, 2016.3.

[14] YANN Collet. LZ4 Block Format Description[OL]. https:// github.com/Cyan4973/lz4/lz4_Block_format.md, 2016.3.

[15] AVS工作組文件(AVS2-P2 20110149-T-469). AVS2-P2屏幕與混合內(nèi)容視頻編碼(S&MCVC)通用測(cè)試條件[S]. 2016.3.

Documents of AVS2 working group. Common conditions for AVS2-P2 Screen and Mixed Content Video Coding (S&MCVC)[S]. 2016.3.

[16] ARTEM Zaytsev. LZ4-r127[OL]. https://github.com/avz/ mysql-lz4.git, 2016.3 .

Lossless Compression Algorithm Based on String Matching with High Performance and Low Complexity for Screen Content Coding

LIN Tao CAI Wenting CHEN Xianyi ZHOU Kailun WANG Shuhui

(,,200092,)

Traditional lossless compression algorithms are not efficient for screen content coding. To take the full advantage of special characteristics of screen content, a lossless compression algorithm based on String Matching with High Performance and Low Complexity (SMHPLC) is proposed. It is implemented on the basis of LZ4HC (LZ4 High Compression). The main new ideas are using pixel instead of byte as the basic unit for string searching and matching, adopting joint optimal coding of three parameters of literal length, match length and offset and mapping for three parameters. Experiment results show that SMHPLC has both high coding efficiency and low complexity. Compared to LZ4HC, SMHPLC not only has a coding complexity reduction of 34.6%, 46.8%, but also achieve overall bit-rate saving of 22.4%, 21.2% in YUV, RGB color formats respectively for AVS2 common test sequences in moving text and graphicscategory.

Lossless compression algorithm; Screen content coding; Dictionary coding; LZ4High Compression (LZ4HC)

TN919.8

A

1009-5896(2017)02-0351-09

10.11999/JEIT160560

2016-05-28；改回日期：2016-11-19；

2016-12-29

蔡文婷 caiwenting@tongji.edu.cn

國(guó)家自然科學(xué)基金(61601200, 61271096)，高等學(xué)校博士學(xué)科點(diǎn)專(zhuān)項(xiàng)科研基金(20130072110054)

The National Natural Science Foundation of China (61601200, 61271096), Specialized Research Fund for the Doctoral Program of Higher Education (20130072110054)

林 濤： 男，1958年生，教授，主要研究方向?yàn)槎嗝襟w算法和SoC設(shè)計(jì).

蔡文婷： 女，1990年生，碩士生，研究方向?yàn)橐曨l編碼算法.

陳先義： 男，1981年生，博士生，研究方向?yàn)橐曨l編碼算法.

周開(kāi)倫： 男，1977年生，博士生，講師，研究方向?yàn)橐曨l編碼、屏幕圖像編碼、多媒體集成電路等.

王淑慧： 女，1973年生，副研究員，研究方向?yàn)橐曨l編碼、屏幕圖像編碼等.