金小娟,張培君,林濤
同濟大學(xué)超大規(guī)模集成電路研究所,上海 200092
◎圖形圖像處理◎
基于HEVC屏幕圖像編碼的哈希表的優(yōu)化算法
金小娟,張培君,林濤
同濟大學(xué)超大規(guī)模集成電路研究所,上海 200092
仿2維匹配算法對屏幕圖像中的非連續(xù)色調(diào)區(qū)域有很好的壓縮性能,但該算法中哈希表的空間開銷較大,不利于硬件實現(xiàn)。為了減小哈希表的空間,通過對原算法優(yōu)化提出了一種3字節(jié)計算哈希值方法,將源數(shù)據(jù)看作是一個由以YUV三元組為元素組成的數(shù)據(jù)集合,然后以YUV三元組為單位計算哈希值,這樣不但減少了哈希值的計算量,而且使哈希表的存儲空間得到很大的節(jié)省。實驗結(jié)果表明,3字節(jié)計算哈希值方法使哈希表的存儲空間減少為原算法的1/3,所測試屏幕圖像的BD-rate性能也有所提高。
高效率視頻編碼(HEVC);仿2維匹配算法;屏幕圖像;哈希表
隨著移動互聯(lián)網(wǎng)的快速發(fā)展,“云計算”中的大量多媒體不僅引起了IT界的廣泛關(guān)注,同時也引起了公眾的廣泛關(guān)注。眾所周知,傳輸數(shù)據(jù)的帶寬有限,通信系統(tǒng)不可能同時滿足眾多用戶高速訪問高分辨率的視頻資源。因此,屏幕圖像編碼(Screen Content Coding)在通訊和網(wǎng)絡(luò)領(lǐng)域中成為學(xué)者們討論的熱點話題。
2010年,ISO-IEC/MPEG和ITU-T/VCEG成立了JCT-VC(Joint Collaborative Team on Video Coding)合作開發(fā)下一代視頻編碼標準,即HEVC(High Efficiency Video Coding),HEVC設(shè)計目標是在相同圖像質(zhì)量的條件下,比特率比H.264/AVC減少50%。為了使視頻達到高清晰度、高幀率和高壓縮率,HEVC進行了大量的技術(shù)創(chuàng)新,比如基于四叉樹的編碼結(jié)構(gòu)、自適應(yīng)樣點補償SAO(Sample Adaptive Offset),宏塊的大小由H.264/AVC中的16×16擴展到了64×64,以提高對高清、超高清視頻的編碼效率。HEVC采用基于四叉樹的編碼結(jié)構(gòu)來提高編碼效率,包括編碼單元CU(CodingUnit)、預(yù)測單元PU(Prediction Unit)和變換單元TU(Transform Unit),其中,分割的最大編碼單元被稱為LCU(Largest Coding Unit)。SAO位于編解碼環(huán)路內(nèi),它將重建后的圖像進行歸類,然后對每一類圖像的像素值加減一個偏移,盡量減少失真[1-5]。
屏幕圖像包括由攝像機捕捉得到的連續(xù)色調(diào)內(nèi)容和由計算機產(chǎn)生的非連續(xù)色調(diào)內(nèi)容,詳見文獻[6-8]。針對屏幕圖像各向異性的特點,仿2維匹配算法很好地解決了比特率、編碼質(zhì)量和編碼復(fù)雜性三者之間的矛盾。在編碼YUV 444過程中,仿2維匹配算法通過建立哈希表尋找最佳匹配字符串,哈希表通過查表和鏈表搜索快速查找首個3字節(jié)匹配樣本,然后逐字節(jié)搜索找到匹配最長的字符串,文獻[9-14]的實驗數(shù)據(jù)證明了仿2維匹配算法在對非連續(xù)色調(diào)內(nèi)容編碼時比HEVC編碼器具有更高的編碼效率,但是仿2維匹配算法為達到快速而高效地匹配所建立的哈希表占用了很大的存儲空間,不利于硬件實現(xiàn)。
基于上述因素,再充分利用數(shù)據(jù)存儲格式的特點,本文對原算法進行了優(yōu)化,提出一種3字節(jié)計算哈希值方法,實驗結(jié)果表明在不影響主觀質(zhì)量的前提下,3字節(jié)計算哈希值方法使得哈希表的存儲空間減少為原來的1/3。
實際信源若不經(jīng)過信源編碼,會存在大量的冗余信息。仿2維匹配算法的目的是盡可能地減少冗余信息,該算法是從已編碼的歷史數(shù)據(jù)中尋找和當前待編碼數(shù)據(jù)相匹配的字符串,如果匹配成功,就將(匹配距離,匹配長度)作為一個數(shù)據(jù)對代替當前待編碼字符串,實現(xiàn)了用最少的信息比特來表示信源,減少信源冗余度,其中已編碼歷史數(shù)據(jù)的集合稱為字典,將2維的圖像數(shù)據(jù)以宏塊為單位轉(zhuǎn)換成1維序列,然后在1維序列上應(yīng)用上述匹配算法,因此稱為仿2維匹配算法。仿2維匹配算法和HEVC有機融合后組成的雙編碼器系統(tǒng),有效改善了HEVC對屏幕圖像的編碼性能[15-19]。隨著編碼過程的不斷進行,歷史數(shù)據(jù)越來越多,這給匹配搜索造成了很大的困難,為了能實時高效地尋找到與當前字節(jié)匹配的字符串,將已編碼的數(shù)據(jù)每三個字節(jié)計算一個哈希值HashValue,并將哈希值作為歷史數(shù)據(jù)的索引存儲在哈希表中,因此通過哈希表可以快速定位與當前三字節(jié)開頭的字符串可能發(fā)生匹配的字符串位置,其中哈希值的計算是逐字節(jié)進行的,文獻[6]中采用這種計算哈希值的方法,本文中稱為逐字節(jié)計算哈希值方法。哈希表分為兩部分:Base表和Son表,其中Base表用來存放哈希鏈表的首節(jié)點,Son表用來存放哈希值相同的歷史節(jié)點,最新的哈希值存放在鏈表首部,在匹配過程中通過哈希表來訪問哈希值相同的所有歷史數(shù)據(jù),從而快速定位可能與當前字節(jié)可能存在匹配的歷史數(shù)據(jù)位置。仿2維匹配算法原理如圖1所示。
逐字節(jié)計算哈希值方法具體步驟如下:
(1)讀入YUV 444格式數(shù)據(jù),把圖像分割成不重疊的宏塊/LCU,然后將數(shù)據(jù)以宏塊/LCU為單位重排成Packed格式。
(2)計算當前三元組的哈希值,并將其對應(yīng)數(shù)據(jù)節(jié)點位置存入Base表。
(3)在哈希表中找到和當前哈希值相同的上一個歷史數(shù)據(jù)位置,開始逐字節(jié)匹配搜索,同時,把當前節(jié)點位置存入哈希表。
(4)在匹配搜索的過程中,根據(jù)匹配距離對當前節(jié)點和歷史節(jié)點逐字節(jié)進行匹配搜索,尋找最優(yōu)匹配,即字符串的匹配長度最大化,如果搜索進程沒有到達該哈希值所在鏈表的末尾,轉(zhuǎn)步驟(3)。
(5)如果最佳匹配長度小于2個字節(jié),則認為沒有找到匹配,輸出當前字節(jié);反之,記錄并存儲最優(yōu)的(匹配距離,匹配長度)。
(6)指針向后移動一個字節(jié),轉(zhuǎn)步驟(2)。
字典有4個等級,用字典等級(level)表示,字典等級決定字典的大小,字典越大,匹配過程中可參考的歷史數(shù)據(jù)越多,字符串的匹配效果越好,仿2維匹配算法性能就越好。但是當字典越大時,匹配搜索的時間和空間開銷越大,使得移動或嵌入式設(shè)備的硬件實現(xiàn)越難,因此根據(jù)字典的大小將字典分為4個等級,分別對應(yīng)不同大小的字典和哈希表,字典等級作為編碼參數(shù)進行設(shè)置,以此滿足不同的應(yīng)用設(shè)求。定義Hs為哈希表大小,HSs為Son表大小,HBs為Base表大小,哈希表、Base表、Son表的大小與字典等級level之間的函數(shù)關(guān)系見公式(1)~(4):
圖1 仿2維匹配算法原理圖
當level=1時,字典的大小為64 kB,Son表中需要64 kB個單元和字典中的位置一一對應(yīng),2個字節(jié)能表示的最大值是64 kB,所以哈希表的每個單元分配2個字節(jié)即可,用公式(1)計算哈希表的大?。划攍evel>1時,字典大小超過了64 kB,必須為哈希表的每個單元分配4個字節(jié),用公式(2)計算哈希表的大小。Base表和Son表的大小均由字典等級(level)決定,字典的大小等于Son表的大小。不同的字典等級對應(yīng)不同大小的Base表和Son表,Base表和Son表的大小與字典等級之間的函數(shù)關(guān)系分別由公式(3)(4)表示。當level=4時,為了節(jié)省內(nèi)存空間,設(shè)定Base表大小和level=3時Base表大小一樣。逐字節(jié)計算哈希值方法中字典等級與字典、哈希表三者之間的大小關(guān)系如表1所示。
表1 逐字節(jié)計算哈希值方法中哈希表大小
由表1可以看出,在逐字節(jié)計算哈希值方法中,隨著字典等級的增大,哈希表的存儲空間明顯增大,當字典等級等于4時,哈希表的存儲空間達到了16 644 kB。
YUV數(shù)據(jù)的存儲格式有兩種:Planar格式和Packed格式。Planar格式將YUV三個分量分開保存,而Packed格式將相鄰YUV三個分量打包形成一個三元組進行保存,因此在Packed格式中信源數(shù)據(jù)可被看作是一個以YUV三元組組成的數(shù)據(jù)集合。YUV的兩種存儲格式如圖2所示。
圖2 YUV的兩種存儲格式
為了進一步提高字符串匹配效率,仿2維匹配算法在匹配搜索前,首先將當前宏塊的數(shù)據(jù)重排列成Packed格式,使YUV分量轉(zhuǎn)變?yōu)槿M形式存放,YUV 444數(shù)據(jù)重排列成packed格式,將其對應(yīng)位置Pos標示出來,如圖3所示。
圖3 YUV 444數(shù)據(jù)和其對應(yīng)位置Pos的關(guān)系圖
在逐字節(jié)計算哈希值方法中,計算每個Pos處相鄰3個字節(jié)的哈希值,并將其全部放入哈希表中,若在搜索匹配過程中找到哈希值與當前哈希值相同的Pos時,開始逐字節(jié)匹配,逐字節(jié)計算哈希值方法不僅使匹配效率很慢,而且哈希表占用的存儲空間很大。對15幅屏幕圖像進行編碼統(tǒng)計,得到Len-C圖,其中Len為字符串匹配長度,其最大長度為273,C為字符串匹配長度為Len的個數(shù),為了觀察方便,圖4中Len的取值范圍是0~99。
圖4 Len-C關(guān)系圖
從圖4中,可以發(fā)現(xiàn)當Len等于3的倍數(shù)時,C具有局部極大值,而當Len等于其他值時,C相對較小,即大部分最佳匹配長度都是3的倍數(shù)。如果哈希表中的Son表只存儲3的倍數(shù)處的Pos,這樣不僅可以保證仿2維匹配算法良好的匹配性能,而且可以使Son表的存儲空間減少為原來的1/3,匹配搜索時間也會減少。所以對逐字節(jié)計算哈希值方法的第(6)步進行改進,指針向后移動3個字節(jié)而不是一個字節(jié),直接計算下一個YUV三元組的哈希值,再進行匹配搜索,這樣在匹配搜索過程中不再是逐字節(jié)搜索,而是以3個字節(jié)進行匹配搜索,此方法稱為3字節(jié)計算哈希值方法。3字節(jié)計算哈希值方法不僅提高了仿2維匹配算法的速度,而且減少了哈希表的存儲空間。
3字節(jié)計算哈希值方法中,哈希Son表大小的計算公式需要修正,公式(4)修正后得到公式(5):
根據(jù)公式(1)、(2)、(3)和(5)可計算得到3字節(jié)計算哈希值方法中字典等級和字典、哈希表三個變量之間的大小關(guān)系,如表2所示。
表2 3字節(jié)計算哈希值方法中哈希表大小
比較表1和表2可以發(fā)現(xiàn),3字節(jié)計算哈希值方法中哈希表大小明顯有所減少,尤其當字典等級等于4時,哈希表的存儲空間僅為5 718 kB,減少為原方法中16 644 kB的1/3,而且實驗測試結(jié)果表明屏幕圖像的BD-rate性能還有所提高。
圖3所示的YUV數(shù)據(jù)每3個字節(jié)看作一個像素值,則3字節(jié)計算哈希值方法相當于每個像素計算一個哈希值存入哈希表,相對于逐字節(jié)算法的每相鄰3個字節(jié)計算1個哈希值,3字節(jié)計算哈希值方法中Son表的存儲空間減少為原算法的1/3,因此也可將3字節(jié)計算哈希值方法稱為1/3算法,那么就可以將這種方法擴展為1/n算法,即
式(8)表示1/8算法是在1/3算法的基礎(chǔ)上跳過了1/6和1/24像素點計算,哈希表空間減少為逐字節(jié)算法的1/8。
為了驗證仿2維匹配算法的3字節(jié)計算哈希值方法優(yōu)于逐字節(jié)計算哈希值方法,本文提出的算法是在參考軟件HM 8.0的基礎(chǔ)上實現(xiàn)的,測試環(huán)境如表3所示。
本文選用了圖5所示的4組測試序列都是JCT-VC會議上用于測試HEVC在SCC方面性能的屏幕圖像。圖5(a)是波形圖,圖5(b)是PCB板設(shè)計圖,圖5(a)、(b)兩幅圖像都以黑色和線條為主,包含少量顏色的文字,屬于非連續(xù)色調(diào)居多的屏幕圖像,用來測試本文提出的3字節(jié)計算哈希值方法對于非連續(xù)色調(diào)內(nèi)容的適應(yīng)性。圖5(c)是一類網(wǎng)頁屏幕圖像,圖5(d)是一類辦公場景的屏幕圖像,圖5(c)、(d)兩幅圖像不僅包含大量的文字,而且包含很多自然圖像,這一類圖像具有較多的紋理細節(jié),可以認為屬于連續(xù)色調(diào)居多的屏幕圖像。分別用仿2維匹配算法的逐字節(jié)計算哈希值方法和3字節(jié)計算哈希值方法對屏幕圖像編碼后在不同字典等級(level)下進行編解碼實驗,4幅屏幕圖像的BD-rate性能比較結(jié)果如表4所示,根據(jù)HEVC統(tǒng)一的評價準則,若BD-rate為正,表示逐字節(jié)計算哈希值方法的性能較好;若BD-rate為負,表示3字節(jié)計算哈希值方法的性能較好。
表3 測試環(huán)境
圖5 屏幕圖像
從表4中的BD-rate性能比較結(jié)果可以得到以下結(jié)論:
(1)和逐字節(jié)計算哈希值方法相比,本文提出的3字節(jié)計算哈希值方法將哈希Son表的大小減小為原方法的1/3,雖然哈希Son表只記錄了1/3的歷史數(shù)據(jù)位置,但實際上保留了可能存在最優(yōu)匹配的所有位置,摒棄了大部分低效率的位置記錄。因此,3字節(jié)計算哈希值不僅提高了算法的時間空間效率,而且提高了算法的匹配性能。
表4 BD-rate性能比較(%)
(2)對于圖5(a)和(b)這一類像素邊緣很明顯的非連續(xù)色調(diào)的屏幕圖像,當level=1時,和逐字節(jié)計算哈希值方法相比,本文提出的3字節(jié)計算哈希值方法對圖像編碼后得到的BD-rate性能稍有所降低,但是對于圖像主觀質(zhì)量基本沒有影響,因為低的字典等級決定了字典容量較小,字典中可存放的已編碼歷史數(shù)據(jù)較少,所以在尋找和當前待編碼數(shù)據(jù)相匹配的字符串時可以參考的歷史數(shù)據(jù)也較少,導(dǎo)致字符串的匹配效果較差。當level>1時,和逐字節(jié)計算哈希值方法相比,本文提出的3字節(jié)計算哈希值方法對圖像編碼后得到的BD-rate性能基本有所提高,而且隨著字典等級越高,BD-rate性能提高也更多,可以得到比較好的匹配效果,說明仿2維匹配算法的3字節(jié)計算哈希值方法對非連續(xù)色調(diào)的屏幕圖像有很好的匹配效果。
(3)對于圖5(c)和(d)這一類包含大量自然圖像的連續(xù)色調(diào)的屏幕圖像,當level=1和level=2時,和逐字節(jié)計算哈希值方法相比,本文提出的3字節(jié)計算哈希值方法對圖像編碼后得到的BD-rate性能稍有所降低,但是BD-rate性能減小都在3%以內(nèi),對圖像的主觀質(zhì)量基本沒有影響。當level=3和level=4時,和逐字節(jié)計算哈希值方法相比,本文提出的3字節(jié)計算哈希值方法對圖像編碼后得到的BD-rate性能基本有所提高,說明仿2維匹配算法的3字節(jié)計算哈希值方法對包含有自然圖像的連續(xù)色調(diào)的屏幕圖像也有較好的匹配性能。
(4)從表4可以看出,字典等級越高,使得字典和哈希表占用的內(nèi)存空間就越大,此時本文提出的3字節(jié)計算哈希值方法對屏幕圖像編碼后得到的BD-rate性能提升效果也越好。
(5)比較表1和表2,再根據(jù)表4中的實驗結(jié)果,仿2維匹配算法的3字節(jié)計算哈希值方法充分利用了YUV數(shù)據(jù)存儲格式的特點,不僅有效降低了屏幕圖像編碼所需哈希表的大小,而且降低了編碼硬件所需的存儲空間和計算復(fù)雜度。因此,仿2維匹配算法的3字節(jié)計算哈希值方法比逐字節(jié)計算哈希值方法具有更大的優(yōu)勢。
本文通過對15幅屏幕圖像進行編碼統(tǒng)計實驗,得到了搜索匹配過程中字符串匹配長度Len和Len的個數(shù)C之間的統(tǒng)計概率,發(fā)現(xiàn)大部分最佳匹配長度都是3的倍數(shù),說明在文獻[6]中逐字節(jié)地進行字符串的匹配操作并不是最優(yōu)的,于是本文提出了一種3字節(jié)計算哈希值方法,使得字符串在匹配搜索的過程中不再逐字節(jié)地搜索,而是以YUV三元組的形式直接開始搜索匹配。該方法充分利用了YUV數(shù)據(jù)存儲格式的特點,使得為了快速高效尋找到與當前字符串匹配的哈希表占用的內(nèi)存空間減少到原方法的1/3,不僅降低了編碼硬件所需的存儲空間,而且降低了計算復(fù)雜度,當字典等級比較高時屏幕圖像的BD-rate性能還有所提升。接下來的研究方向可進一步分析1/n算法,使得哈希表自適應(yīng)地根據(jù)字典的大小而變化,從而達到既能減小哈希表的大小,又能使屏幕圖像的BD-rate性能均有所提升的目的,最終實現(xiàn)時間空間效率和匹配性能的最優(yōu)化。
[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,F(xiàn)uldseth 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].電子與信息學(xué)報,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
國家自然科學(xué)基金(No.61201226,No.61271096);上海市自然科學(xué)基金(No.12ZR1433800);中央高?;究蒲袠I(yè)務(wù)費專項資金(No.2810219002,No.2810219003)。
金小娟(1989—),女,碩士,研究方向為多媒體算法和SoC設(shè)計;張培君(1977—),男,博士,講師,研究方向為多媒體算法和SoC設(shè)計;林濤(1958—),男,博士,教授,研究方向為多媒體算法和SoC設(shè)計。E-mail:jinxiaojuan08@gmail.com
2013-03-27
2013-06-17
1002-8331(2014)17-0155-05