基于HEVC屏幕圖像編碼的哈希表的優化算法

金小娟，張培君，林濤

同濟大學超大規模集成電路研究所，上海 200092

◎圖形圖像處理◎

基于HEVC屏幕圖像編碼的哈希表的優化算法

金小娟，張培君，林濤

同濟大學超大規模集成電路研究所，上海 200092

仿2維匹配算法對屏幕圖像中的非連續色調區域有很好的壓縮性能，但該算法中哈希表的空間開銷較大，不利于硬件實現。為了減小哈希表的空間，通過對原算法優化提出了一種3字節計算哈希值方法，將源數據看作是一個由以YUV三元組為元素組成的數據集合，然后以YUV三元組為單位計算哈希值，這樣不但減少了哈希值的計算量，而且使哈希表的存儲空間得到很大的節省。實驗結果表明，3字節計算哈希值方法使哈希表的存儲空間減少為原算法的1/3，所測試屏幕圖像的BD-rate性能也有所提高。

高效率視頻編碼（HEVC）；仿2維匹配算法；屏幕圖像；哈希表

1 引言

隨著移動互聯網的快速發展，“云計算”中的大量多媒體不僅引起了IT界的廣泛關注，同時也引起了公眾的廣泛關注。眾所周知，傳輸數據的帶寬有限，通信系統不可能同時滿足眾多用戶高速訪問高分辨率的視頻資源。因此，屏幕圖像編碼（Screen Content Coding）在通訊和網絡領域中成為學者們討論的熱點話題。

2010年，ISO-IEC/MPEG和ITU-T/VCEG成立了JCT-VC（Joint Collaborative Team on Video Coding）合作開發下一代視頻編碼標準，即HEVC（High Efficiency Video Coding），HEVC設計目標是在相同圖像質量的條件下，比特率比H.264/AVC減少50%。為了使視頻達到高清晰度、高幀率和高壓縮率，HEVC進行了大量的技術創新，比如基于四叉樹的編碼結構、自適應樣點補償SAO（Sample Adaptive Offset），宏塊的大小由H.264/AVC中的16×16擴展到了64×64，以提高對高清、超高清視頻的編碼效率。HEVC采用基于四叉樹的編碼結構來提高編碼效率，包括編碼單元CU（CodingUnit）、預測單元PU（Prediction Unit）和變換單元TU（Transform Unit），其中，分割的最大編碼單元被稱為LCU（Largest Coding Unit）。SAO位于編解碼環路內，它將重建后的圖像進行歸類，然后對每一類圖像的像素值加減一個偏移，盡量減少失真[1-5]。

屏幕圖像包括由攝像機捕捉得到的連續色調內容和由計算機產生的非連續色調內容，詳見文獻[6-8]。針對屏幕圖像各向異性的特點，仿2維匹配算法很好地解決了比特率、編碼質量和編碼復雜性三者之間的矛盾。在編碼YUV 444過程中，仿2維匹配算法通過建立哈希表尋找最佳匹配字符串，哈希表通過查表和鏈表搜索快速查找首個3字節匹配樣本，然后逐字節搜索找到匹配最長的字符串，文獻[9-14]的實驗數據證明了仿2維匹配算法在對非連續色調內容編碼時比HEVC編碼器具有更高的編碼效率，但是仿2維匹配算法為達到快速而高效地匹配所建立的哈希表占用了很大的存儲空間，不利于硬件實現。

基于上述因素，再充分利用數據存儲格式的特點，本文對原算法進行了優化，提出一種3字節計算哈希值方法，實驗結果表明在不影響主觀質量的前提下，3字節計算哈希值方法使得哈希表的存儲空間減少為原來的1/3。

2 仿2維匹配算法

實際信源若不經過信源編碼，會存在大量的冗余信息。仿2維匹配算法的目的是盡可能地減少冗余信息，該算法是從已編碼的歷史數據中尋找和當前待編碼數據相匹配的字符串，如果匹配成功，就將（匹配距離，匹配長度）作為一個數據對代替當前待編碼字符串，實現了用最少的信息比特來表示信源，減少信源冗余度，其中已編碼歷史數據的集合稱為字典，將2維的圖像數據以宏塊為單位轉換成1維序列，然后在1維序列上應用上述匹配算法，因此稱為仿2維匹配算法。仿2維匹配算法和HEVC有機融合后組成的雙編碼器系統，有效改善了HEVC對屏幕圖像的編碼性能[15-19]。隨著編碼過程的不斷進行，歷史數據越來越多，這給匹配搜索造成了很大的困難，為了能實時高效地尋找到與當前字節匹配的字符串，將已編碼的數據每三個字節計算一個哈希值HashValue，并將哈希值作為歷史數據的索引存儲在哈希表中，因此通過哈希表可以快速定位與當前三字節開頭的字符串可能發生匹配的字符串位置，其中哈希值的計算是逐字節進行的，文獻[6]中采用這種計算哈希值的方法，本文中稱為逐字節計算哈希值方法。哈希表分為兩部分：Base表和Son表，其中Base表用來存放哈希鏈表的首節點，Son表用來存放哈希值相同的歷史節點，最新的哈希值存放在鏈表首部，在匹配過程中通過哈希表來訪問哈希值相同的所有歷史數據，從而快速定位可能與當前字節可能存在匹配的歷史數據位置。仿2維匹配算法原理如圖1所示。

逐字節計算哈希值方法具體步驟如下：

（1）讀入YUV 444格式數據，把圖像分割成不重疊的宏塊/LCU，然后將數據以宏塊/LCU為單位重排成Packed格式。

（2）計算當前三元組的哈希值，并將其對應數據節點位置存入Base表。

（3）在哈希表中找到和當前哈希值相同的上一個歷史數據位置，開始逐字節匹配搜索，同時，把當前節點位置存入哈希表。

（4）在匹配搜索的過程中，根據匹配距離對當前節點和歷史節點逐字節進行匹配搜索，尋找最優匹配，即字符串的匹配長度最大化，如果搜索進程沒有到達該哈希值所在鏈表的末尾，轉步驟（3）。

（5）如果最佳匹配長度小于2個字節，則認為沒有找到匹配，輸出當前字節；反之，記錄并存儲最優的（匹配距離，匹配長度）。

（6）指針向后移動一個字節，轉步驟（2）。

字典有4個等級，用字典等級（level）表示，字典等級決定字典的大小，字典越大，匹配過程中可參考的歷史數據越多，字符串的匹配效果越好，仿2維匹配算法性能就越好。但是當字典越大時，匹配搜索的時間和空間開銷越大，使得移動或嵌入式設備的硬件實現越難，因此根據字典的大小將字典分為4個等級，分別對應不同大小的字典和哈希表，字典等級作為編碼參數進行設置，以此滿足不同的應用設求。定義Hs為哈希表大小，HSs為Son表大小，HBs為Base表大小，哈希表、Base表、Son表的大小與字典等級level之間的函數關系見公式（1）～（4）：

圖1 仿2維匹配算法原理圖

當level=1時，字典的大小為64 kB，Son表中需要64 kB個單元和字典中的位置一一對應，2個字節能表示的最大值是64 kB，所以哈希表的每個單元分配2個字節即可，用公式（1）計算哈希表的大小；當level＞1時，字典大小超過了64 kB，必須為哈希表的每個單元分配4個字節，用公式（2）計算哈希表的大小。Base表和Son表的大小均由字典等級(level)決定，字典的大小等于Son表的大小。不同的字典等級對應不同大小的Base表和Son表，Base表和Son表的大小與字典等級之間的函數關系分別由公式（3）（4）表示。當level=4時，為了節省內存空間，設定Base表大小和level=3時Base表大小一樣。逐字節計算哈希值方法中字典等級與字典、哈希表三者之間的大小關系如表1所示。

表1 逐字節計算哈希值方法中哈希表大小

由表1可以看出，在逐字節計算哈希值方法中，隨著字典等級的增大，哈希表的存儲空間明顯增大，當字典等級等于4時，哈希表的存儲空間達到了16 644 kB。

3 3字節計算哈希值方法

YUV數據的存儲格式有兩種：Planar格式和Packed格式。Planar格式將YUV三個分量分開保存，而Packed格式將相鄰YUV三個分量打包形成一個三元組進行保存，因此在Packed格式中信源數據可被看作是一個以YUV三元組組成的數據集合。YUV的兩種存儲格式如圖2所示。

圖2 YUV的兩種存儲格式

為了進一步提高字符串匹配效率，仿2維匹配算法在匹配搜索前，首先將當前宏塊的數據重排列成Packed格式，使YUV分量轉變為三元組形式存放，YUV 444數據重排列成packed格式，將其對應位置Pos標示出來，如圖3所示。

圖3 YUV 444數據和其對應位置Pos的關系圖

在逐字節計算哈希值方法中，計算每個Pos處相鄰3個字節的哈希值，并將其全部放入哈希表中，若在搜索匹配過程中找到哈希值與當前哈希值相同的Pos時，開始逐字節匹配，逐字節計算哈希值方法不僅使匹配效率很慢，而且哈希表占用的存儲空間很大。對15幅屏幕圖像進行編碼統計，得到Len-C圖，其中Len為字符串匹配長度，其最大長度為273，C為字符串匹配長度為Len的個數，為了觀察方便，圖4中Len的取值范圍是0～99。

圖4 Len-C關系圖

從圖4中，可以發現當Len等于3的倍數時，C具有局部極大值，而當Len等于其他值時，C相對較小，即大部分最佳匹配長度都是3的倍數。如果哈希表中的Son表只存儲3的倍數處的Pos，這樣不僅可以保證仿2維匹配算法良好的匹配性能，而且可以使Son表的存儲空間減少為原來的1/3，匹配搜索時間也會減少。所以對逐字節計算哈希值方法的第（6）步進行改進，指針向后移動3個字節而不是一個字節，直接計算下一個YUV三元組的哈希值，再進行匹配搜索，這樣在匹配搜索過程中不再是逐字節搜索，而是以3個字節進行匹配搜索，此方法稱為3字節計算哈希值方法。3字節計算哈希值方法不僅提高了仿2維匹配算法的速度，而且減少了哈希表的存儲空間。

3字節計算哈希值方法中，哈希Son表大小的計算公式需要修正，公式（4）修正后得到公式（5）：

根據公式（1）、（2）、（3）和（5）可計算得到3字節計算哈希值方法中字典等級和字典、哈希表三個變量之間的大小關系，如表2所示。

表2 3字節計算哈希值方法中哈希表大小

比較表1和表2可以發現，3字節計算哈希值方法中哈希表大小明顯有所減少，尤其當字典等級等于4時，哈希表的存儲空間僅為5 718 kB，減少為原方法中16 644 kB的1/3，而且實驗測試結果表明屏幕圖像的BD-rate性能還有所提高。

圖3所示的YUV數據每3個字節看作一個像素值，則3字節計算哈希值方法相當于每個像素計算一個哈希值存入哈希表，相對于逐字節算法的每相鄰3個字節計算1個哈希值，3字節計算哈希值方法中Son表的存儲空間減少為原算法的1/3，因此也可將3字節計算哈希值方法稱為1/3算法，那么就可以將這種方法擴展為1/n算法，即

式（8）表示1/8算法是在1/3算法的基礎上跳過了1/6和1/24像素點計算，哈希表空間減少為逐字節算法的1/8。

4 實驗結果

為了驗證仿2維匹配算法的3字節計算哈希值方法優于逐字節計算哈希值方法，本文提出的算法是在參考軟件HM 8.0的基礎上實現的，測試環境如表3所示。

本文選用了圖5所示的4組測試序列都是JCT-VC會議上用于測試HEVC在SCC方面性能的屏幕圖像。圖5（a）是波形圖，圖5（b）是PCB板設計圖，圖5（a）、（b）兩幅圖像都以黑色和線條為主，包含少量顏色的文字，屬于非連續色調居多的屏幕圖像，用來測試本文提出的3字節計算哈希值方法對于非連續色調內容的適應性。圖5（c）是一類網頁屏幕圖像，圖5（d）是一類辦公場景的屏幕圖像，圖5（c）、（d）兩幅圖像不僅包含大量的文字，而且包含很多自然圖像，這一類圖像具有較多的紋理細節，可以認為屬于連續色調居多的屏幕圖像。分別用仿2維匹配算法的逐字節計算哈希值方法和3字節計算哈希值方法對屏幕圖像編碼后在不同字典等級（level）下進行編解碼實驗，4幅屏幕圖像的BD-rate性能比較結果如表4所示，根據HEVC統一的評價準則，若BD-rate為正，表示逐字節計算哈希值方法的性能較好；若BD-rate為負，表示3字節計算哈希值方法的性能較好。

表3 測試環境

圖5 屏幕圖像

從表4中的BD-rate性能比較結果可以得到以下結論：

（1）和逐字節計算哈希值方法相比，本文提出的3字節計算哈希值方法將哈希Son表的大小減小為原方法的1/3，雖然哈希Son表只記錄了1/3的歷史數據位置，但實際上保留了可能存在最優匹配的所有位置，摒棄了大部分低效率的位置記錄。因此，3字節計算哈希值不僅提高了算法的時間空間效率，而且提高了算法的匹配性能。

表4 BD-rate性能比較（%）

（2）對于圖5（a）和（b）這一類像素邊緣很明顯的非連續色調的屏幕圖像，當level=1時，和逐字節計算哈希值方法相比，本文提出的3字節計算哈希值方法對圖像編碼后得到的BD-rate性能稍有所降低，但是對于圖像主觀質量基本沒有影響，因為低的字典等級決定了字典容量較小，字典中可存放的已編碼歷史數據較少，所以在尋找和當前待編碼數據相匹配的字符串時可以參考的歷史數據也較少，導致字符串的匹配效果較差。當level＞1時，和逐字節計算哈希值方法相比，本文提出的3字節計算哈希值方法對圖像編碼后得到的BD-rate性能基本有所提高，而且隨著字典等級越高，BD-rate性能提高也更多，可以得到比較好的匹配效果，說明仿2維匹配算法的3字節計算哈希值方法對非連續色調的屏幕圖像有很好的匹配效果。

（3）對于圖5（c）和（d）這一類包含大量自然圖像的連續色調的屏幕圖像，當level=1和level=2時，和逐字節計算哈希值方法相比，本文提出的3字節計算哈希值方法對圖像編碼后得到的BD-rate性能稍有所降低，但是BD-rate性能減小都在3%以內，對圖像的主觀質量基本沒有影響。當level=3和level=4時，和逐字節計算哈希值方法相比，本文提出的3字節計算哈希值方法對圖像編碼后得到的BD-rate性能基本有所提高，說明仿2維匹配算法的3字節計算哈希值方法對包含有自然圖像的連續色調的屏幕圖像也有較好的匹配性能。

（4）從表4可以看出，字典等級越高，使得字典和哈希表占用的內存空間就越大，此時本文提出的3字節計算哈希值方法對屏幕圖像編碼后得到的BD-rate性能提升效果也越好。

（5）比較表1和表2，再根據表4中的實驗結果，仿2維匹配算法的3字節計算哈希值方法充分利用了YUV數據存儲格式的特點，不僅有效降低了屏幕圖像編碼所需哈希表的大小，而且降低了編碼硬件所需的存儲空間和計算復雜度。因此，仿2維匹配算法的3字節計算哈希值方法比逐字節計算哈希值方法具有更大的優勢。

5 結束語

本文通過對15幅屏幕圖像進行編碼統計實驗，得到了搜索匹配過程中字符串匹配長度Len和Len的個數C之間的統計概率，發現大部分最佳匹配長度都是3的倍數，說明在文獻[6]中逐字節地進行字符串的匹配操作并不是最優的，于是本文提出了一種3字節計算哈希值方法，使得字符串在匹配搜索的過程中不再逐字節地搜索，而是以YUV三元組的形式直接開始搜索匹配。該方法充分利用了YUV數據存儲格式的特點，使得為了快速高效尋找到與當前字符串匹配的哈希表占用的內存空間減少到原方法的1/3，不僅降低了編碼硬件所需的存儲空間，而且降低了計算復雜度，當字典等級比較高時屏幕圖像的BD-rate性能還有所提升。接下來的研究方向可進一步分析1/n算法，使得哈希表自適應地根據字典的大小而變化，從而達到既能減小哈希表的大小，又能使屏幕圖像的BD-rate性能均有所提升的目的，最終實現時間空間效率和匹配性能的最優化。

[1]Cai Xiaoxia，Cui Yansong，Deng Zhongliang，et al.Model of next-generation video standard and relative key technologies[J].TV Technology，2012，36（2）：80-84.

[2]Ugur K，Andersson K，Fuldseth A，et al.High performance，low complexity video coding and the emerging HEVC standard[J].IEEE Transactions on Circuits and Systems for Video Technology，2010，20（12）：1688-1697.

[3]Lainema J，Bossen F，Han W J.Intra coding of the HEVC standard[J].IEEE Transactions on Circuits and Systems for Video Technology，2010，22（12）：1792-1801.

[4]Sole J，Joshi R，Nguyen N，et al.Transform coefficient coding in HEVC[J].IEEE Transactions on Circuits and Systems for Video Technology，2010，22（12）：1765-1777.

[5]Ding Wenpeng，Lu Yan，Wu Feng.Enable efficient compound image compression in H.264/AVC intra coding[C]// IEEE International Conference on Image Processing，San Antonio，2007：337-340.

[6]Lin Tao，Zhang Peijun，Wang Shuhui，et al.mixed chroma sampling-rate high efficiency video coding for full-chroma screen content[J].IEEE Transactions on Circuits and Systems for Video Technology，2013，23（1）：173-185.

[7]Lan Cuiling，Shi Guangm ing，Wu Feng.Compress compound images in H.264/MPEG-4 AVC by exploiting spatial correlation[J].IEEE Transactions on Image Processing，2010，19（4）：946-957.

[8]Lin T，Hao Pengwei.Compound image compression for real-time computer generated compound images[J].IEEE Transactions on Image Processing，2005，14（8）：993-1005.

[9]Lee B，Kim M.Modeling rates and distortions based on a mixture of Laplacian distributions for inter-predicted residues in quadtree coding of HEVC[J].IEEE Signal Processing Letters，2011，18（10）：571-574.

[10]Zhang Peijun，Lin Tao，Wang Shuhui，et al.P2M and P2M+SAP as lossless coding tools for screen content coding[C]//JCTVC-Meeting，Geneva，2013.

[11]Lin Tao，Zhang Peijun，Wang Shuhui，et al.Full-chroma（YUV 444）dictionary+hybrid dual-coder extension of HEVC[C]//JCTVC-Meeting，Shanghai，2012.

[12]Wang Shuhui，Lin Tao，Zhou Kailun.Update on full-chroma（YUV 444）screen content test sequences of JCTVCH0294[C]//JCTVC-Meeting，Shanghai，2012.

[13]Lin Tao，Zhang Peijun，Wang Shuhui，et al.Syntax and semantics of Dual-coder mixed Chroma-sampling-rate（DMC）coding for 4∶4∶4 screen content[C]//JCTVCM eeting，Stockholm，2012.

[14]Lin Tao，Zhang Peijun，Wang Shuhui，et al.AHG7：HM software implementation and source code for JCTVCK 0133[C]//JCTVC-M eeting，Shanghai，2012.

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

[16]Lin Tao，Zhang Peijun，Wang Shuhui，et al.4∶4∶4 screen content coding using Dual-coder mixed Chroma-samplingrate（DMC）techniques[C]//JCTVC-Meeting，Geneva，2012.

[17]Zhang Peijun，Lin Tao，Wang Shuhui，et al.Subjective quality comparison between DMC coding and chromasubsampled 420 coding using YUV 444 screen content test sequences[C]//JCTVC-M eeting，Geneva，2012.

[18]Lin Tao，Wang Shuhui.mixed chroma samp ling-rate coding：combining the merits of 4∶4∶4 and 4∶2∶0 and increasing the value of past 4∶2∶0 investment[C]// JCTVC-Meeting，San Jose，2012.

[19]Wang Shuhui，Lin Tao.4∶4∶4 screen content coding using macroblock-adaptive mixed chroma-sam pling-rate[C]// JCTVC-M eeting，San Jose，2012.

JIN Xiaojuan,ZHANG Peijun,LIN Tao

Institute of Very Large Scale Intergration,Tongji University,Shanghai 200092,China

The preudo 2-D matching algorithm has good compression performance for the discontinuous-tone content of screen content. However, the large space overhead of the hash table is not conductive to realize the hardware in this algorithm.This paper proposes a 3-byte hash value method to reduce the space of the hash table for optimizing the original method. The source data is treated as the data set composed of elements for YUV triples. Then the hash value of YUV triple is calculated as a unit. It not only can reduce the amount of computation of the hash values, but also can minimize the space overhead of the hash table. The experimental results show that the 3-byte hash value method makes the storage space of the hash table reduce to one-third of the original. And the BD-rate performance of some test screen images is alsoimproved.

High Efficiency Video Coding（HEVC）; preudo 2-dimension matching algorithm; screen content; hash table

JIN Xiaojuan,ZHANG Peijun,LIN Tao.Op tim ization algorithm on hash tab le based on HEVC screen content coding.Computer Engineering and Applications,2014,50（17）：155-159.

A

TP393

10.3778/j.issn.1002-8331.1303-0425

國家自然科學基金（No.61201226，No.61271096）；上海市自然科學基金（No.12ZR1433800）；中央高校基本科研業務費專項資金（No.2810219002，No.2810219003）。

金小娟（1989—），女，碩士，研究方向為多媒體算法和SoC設計；張培君（1977—），男，博士，講師，研究方向為多媒體算法和SoC設計；林濤（1958—），男，博士，教授，研究方向為多媒體算法和SoC設計。E-mail：jinxiaojuan08@gmail.com

2013-03-27

2013-06-17

1002-8331（2014）17-0155-05