<acronym id="owqss"><center id="owqss"></center></acronym>
<acronym id="owqss"></acronym>
<acronym id="owqss"><center id="owqss"></center></acronym>

基于上下文樹的無損壓縮算法

王炯 陳建華 和志圓

引用本文:
Citation:

基于上下文樹的無損壓縮算法

    作者簡介: 王 炯,1994年,女,陜西省西安市,漢族,云南大學碩士;研究方向:圖像壓縮. 通訊地址:云南省昆明市呈貢區云南大學楠苑5幢(650504、15891771802、759739201@qq.com);
    通訊作者: 陳建華, chenjh@ynu.edu.cn
  • 中圖分類號: TN911.21

Lossless compression algorithm based on context tree

    Corresponding author: CHEN Jianhua, chenjh@ynu.edu.cn ;
  • CLC number: TN911.21

  • 摘要: 為解決多進制信源建模面臨的比對二進制信源建模更嚴重的“上下文稀釋”問題,提出了基于上下文樹的無損壓縮算法. 首先,利用了待編碼符號的上下文信息以及信息論中條件降低熵值的原則,建立上下文樹模型,為使信源的統計信息劃分得更加細致,將多叉樹轉化為二叉樹;然后,為了獲得更有利于改進編碼性能的條件概率分布,采用描述長度增量作為樹節點的合并原則;最后,為處理算術編碼過程中產生的零概率符號問題,傳統的方法是將條件概率分布初始化為均勻分布,但在編碼伊始,這種處理方式極不利于提高編碼性能,鑒于此,引入逃逸符號來處理算術編碼過程中產生的零概率符號問題. 實驗結果表明,提出的算法能取得較好的壓縮效果.
  • 圖 1  10階上下文模板,c表示待編碼符號

    Figure 1.  10-order context template, c indicates the current symbol to be encoded

    圖 2  標準圖像集

    Figure 2.  Standard grayscale image set

    圖 3  4階上下文模板,c為待編碼符號

    Figure 3.  4-order context template, c is current symbol

    圖 4  參數T對lena圖像壓縮性能的影響

    Figure 4.  Influence of adjusting the parameter T on the compression performance for the lena

    表 1  閾值為700對圖像編碼的影響(單位:字節)

    Table 1.  The performance of threshold T=700 on image encoding(unit: byte)

    lenapeppersphotographyplaneelainecouple
    不削減
    頻度
    167441408310862140631830423219
    T=700165771400610756140271821922964
    下載: 導出CSV

    表 2  6種方法的壓縮效果比較(單位:字節)

    Table 2.  Comparison of compression performance of six methods (unit: byte)

    實驗圖像初始的3階上下文樹模型初始的4階上下文樹模型初始的5階上下文樹模型文獻[13]文獻[1]提出的方法
    lena172381726918084172391716716577
    peppers145831459715302146091452814006
    photography115761140912174114161127010756
    plane147251454315305145461442714027
    elaine191731882419359188291896118219
    couple241762377524916238032379622964
    下載: 導出CSV
    鸿禾娱乐
  • [1] Weinberger M J, Rissanen J J, Arps R B. Applications of universal context modeling to lossless compression of gray-scale images[J]. IEEE Transactions on Image Processing, 1996, 5(4): 575-586. DOI:  10.1109/83.491334.
    [2] Chen J. Context modeling based on context quantization with application in wavelet image coding[J]. IEEE Transactions on Image Processing, 2004, 13(1): 26-32. DOI:  10.1109/TIP.2003.819224.
    [3] 黃博強, 陳建華, 汪源源. 基于Context模型的ECG信號二維壓縮[J]. 電子學報, 2008, 36(9): 1 810-1 813. DOI:  10.3321/j.issn:0372-2112.2008.09.030. Huang Q Y, Chen J H, Wang Y Y. 2-D Compression of ECG Signals Based on Context Models[J]. Acta Electronica Sinica, 2008, 36(9): 1 810-1 813.
    [4] Auli-Llinas F. Context-adaptive binary arithmetic coding with fixed-length codewords[J]. IEEE Transactions on Multimedia, 2015, 17(8): 1 385-1 390. DOI:  10.1109/TMM.2015.2444797.
    [5] Zhou J, Au O C, Zhai G. Scalable compression of stream cipher encrypted images through context-adaptive sampling[J]. IEEE Transactions on Information Forensics and Security, 2014, 9(11): 1 857-1 868. DOI:  10.1109/TIFS.2014.2352455.
    [6] Chen M, Xu M, Franti P. Adaptive context-tree-based statistical filtering for raster map image denoising[J]. IEEE Transactions on Multimedia, 2011, 13(6): 1 195-1 207. DOI:  10.1109/TMM.2011.2166538.
    [7] Cagnazzo M, Antonini M, Barlaud M. Mutual information-based context quantization[J]. Signal Processing: Image Communication, 2010, 25(1): 64-74. DOI:  10.1016/j.image.2009.09.002.
    [8] 陳建華, 余錦華, 施心陵. 基于Context量化的Context模型[J]. 云南大學學報: 自然科學版, 2002, 24(5): 345-349. DOI:  10.3321/j.issn:0258-7971.2002.05.007. Chen J H, Yu J H, Shi X L. Contex t modeling based on contex t quantization[J]. Journal of Yunnan University, 2002, 24(5): 345-349.
    [9] Akimov A, Kolesnikov A, Franti P. Lossless compression of color map images by context tree modeling[J]. IEEE Transactions on Image Processing, 2007, 16(1): 114-120. DOI:  10.1109/TIP.2006.887721.
    [10] Frnti P, Ageenko E. On the use of context tree for binary image compression[C]//IEEE International Conference on Image Processing, Kobe, Japan, 1999: 752-756. DOI: 10.1109/ICIP.1999.817217
    [11] Kopylov P, Franti P. Compression of map images by multilayer context tree modeling[J]. IEEE Transactions on Image Processing, 2005, 14(1): 1-11. DOI:  10.1109/tip.2004.838694.
    [12] Akimov A, Kolesnikov A, Fr?nti P. Lossless compression of map contours by context tree modeling of chain codes[J]. Pattern Recognition, 2007, 40(3): 944-952. DOI:  10.1016/j.patcog.2006.08.005.
    [13] 楊文濤, 劉衛忠, 鄭立新, 等. 多階上下文自適應二進制算術編碼實現[J]. 華中科技大學學報: 自然科學版, 2007, 35(3): 42-45. DOI:  10.13245/j.hust.2007.03.013.Yang. W T, Liu W Z, Zheng L X. Realization of multi-order context-based adaptive binary arithmetic coding[J]. Journal of Huazhong University of Science and Technology : Natural Science Edition, 2007, 35(3): 42-45.
    [14] Chen M, Xu M, Franti P. Adaptive context-tree-based statistical filtering for raster map image denoising[J]. IEEE Transactions on Multimedia, 2011, 13(6): 1 195-1 207. DOI:  10.1109/TMM.2011.2166538.
    [15] Zheng A, Cheung G, Florencio D. Context tree based image contour coding using a geometric prior[J]. IEEE Transactions on Image Processing, 2017, 26(2): 574-589. DOI:  10.1109/TIP.2016.2627813.
    [16] Zheng A, Cheung G, Florencio D. Joint denoising / compression of image contours via chape prior and context tree[J]. IEEE Transactions on Image Processing, 2018, 27(7): 3 332-3 344. DOI:  10.1109/TIP.2018.2816818.
    [17] 陳建華, 王勇, 張鴻. 基于描述長度的Context建模算法[J]. 電子與信息學報, 2016(3): 661-667. DOI:  10.11999/JEIT150562. Chen J H, Wang Y, Zhang H. Context modeling based on description length[J]. Journal of electronics and information, 2016(3): 661-667.
    [18] Moffat A. Implementing the PPM data compression scheme[J]. IEEE Transactions on Communications, 1990, 38(11): 1 917-1 921. DOI:  10.1109/26.61469.
    [19] Witten I H, Bell T C. The zero-frequency problem: estimating the probabilities of novel events in adaptive text compression[J]. IEEE Transactions on Informaton Theory, 1991, 37(4): 1 085-1 094. DOI:  10.1109/18.87000.
  • [1] 孫文靜秦昊陳建華 . 一種基于JPEG2000的多描述編碼方案. 云南大學學報(自然科學版),
    [2] 張忠玉劉惟一張玉琢 . Bayesian網的信息熵. 云南大學學報(自然科學版),
    [3] 許傳云周忠 . 雙峰映射的一類特殊符號乘法. 云南大學學報(自然科學版),
    [4] 彭守禮 . 符號動力學,星花積及其他. 云南大學學報(自然科學版),
    [5] 李港羅志全楊娟曾曉雄 . 旋轉帶電BTZ黑洞的修正熵. 云南大學學報(自然科學版),
    [6] 曾熙雯張鵬飛陳自明 . 鱗頭鰍觸須畸形個體描述. 云南大學學報(自然科學版),
    [7] 韓澤軍丁洪偉岳昆李春芬楊志軍 . 碰撞長度可變的三時鐘N?CSMA的WSN協議分析. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20170766
    [8] 李勇余江劉言立宗容胡勁松 . 基于CRC-RS編碼的無線雙信道模型. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20120617
    [9] 王佳周華梁志宏代飛白麗瑞 . 基于信息熵的軟件維護風險度量. 云南大學學報(自然科學版),
    [10] 曹克非王參軍 . Tsallis熵與非廣延統計力學. 云南大學學報(自然科學版),
    [11] 支元洪何青海 . 基于實值函數極限理論的無窮大符號討論. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20190419
    [12] 王麗珍孫茂林Enrique Chujoy . 云南馬鈴薯儲藏害蟲及其特征描述. 云南大學學報(自然科學版),
    [13] 錢寧李彤 . 描述軟件過程繼承的一種方法. 云南大學學報(自然科學版),
    [14] 程昆夏幼明高佳樂 . 基于時間區間關系的時態模糊描述邏輯研究. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.2013011a
    [15] 余錦華陳建華李東暉余煒施心陵 . 基于Context模型的非嵌入式小波彩色圖像編碼方案. 云南大學學報(自然科學版),
    [16] 王繪山陳貴元蔣宗敏王文學王維孟勝科張理超余敏崔清華李梅章 . 樹鼩VEGF全長編碼序列的克隆及分子特征分析. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20140027
    [17] 張亞鵬唐猛李海華謝靈運陳建華 . 物理層網絡編碼與LDPC碼聯合系統設計及性能優化. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20190226
    [18] 李海華唐猛張亞鵬謝靈運陳建華 . 多中繼物理層網絡編碼系統與LDPC碼聯合設計及性能分析. 云南大學學報(自然科學版), doi: 10.7540/j.ynu.20190651
    [19] 李慧玲楊樹政蔣青權 . 緩變動態Reissner-Nordström黑洞的熵. 云南大學學報(自然科學版),
    [20] 龍超云何勇龍洪其 . 鐵磁系統中介觀疇壁的雙波描述及量子漲落. 云南大學學報(自然科學版),
  • 加載中
圖(4)表(2)
計量
  • 文章訪問數:  98
  • HTML全文瀏覽量:  93
  • PDF下載量:  6
  • 被引次數: 0
出版歷程
  • 網絡出版日期:  2020-08-28

基于上下文樹的無損壓縮算法

    作者簡介:王 炯,1994年,女,陜西省西安市,漢族,云南大學碩士;研究方向:圖像壓縮. 通訊地址:云南省昆明市呈貢區云南大學楠苑5幢(650504、15891771802、759739201@qq.com)
    通訊作者: 陳建華, chenjh@ynu.edu.cn
  • 云南大學 信息學院,云南 昆明 650500

摘要: 為解決多進制信源建模面臨的比對二進制信源建模更嚴重的“上下文稀釋”問題,提出了基于上下文樹的無損壓縮算法. 首先,利用了待編碼符號的上下文信息以及信息論中條件降低熵值的原則,建立上下文樹模型,為使信源的統計信息劃分得更加細致,將多叉樹轉化為二叉樹;然后,為了獲得更有利于改進編碼性能的條件概率分布,采用描述長度增量作為樹節點的合并原則;最后,為處理算術編碼過程中產生的零概率符號問題,傳統的方法是將條件概率分布初始化為均勻分布,但在編碼伊始,這種處理方式極不利于提高編碼性能,鑒于此,引入逃逸符號來處理算術編碼過程中產生的零概率符號問題. 實驗結果表明,提出的算法能取得較好的壓縮效果.

English Abstract

  • 無損壓縮廣泛應用于對圖像細節要求較高的領域,而上下文(Context)建模技術常常用于對圖像序列建模. 1996年,文獻[1]使用通用的上下文建模來無損地壓縮灰度圖像. 2004年,文獻[2]通過上下文量化的方式來減小上下文模型代價,并將之運用于小波圖像的編碼中. 2008年,文獻[3]使用Context模型來壓縮ECG圖像. 2015年,文獻[4]提出的編碼器采用了一種新的基于上下文的機制,該機制基于可變大小的滑動窗口,可以較高精度地估計編碼符號的概率. 由前人的成果和經驗可以看出,上下文建模是提高圖像編碼性能的有效手段. 但隨著上下文階數的增加,導致模型中條件概率分布的數量呈指數倍增加,但信源序列有限,使得條件概率分布得不到充分的訓練,反而會導致編碼效果變差,這便是“上下文稀釋”問題[5-6].

    為解決上下文稀釋問題,可通過一些Context量化原則來減少條件概率分布的數量,從而降低模型代價以提高編碼效果[7-8]. 雖然Context量化的方法一定程度上能緩解上下文稀釋問題,但更有效的方法是使用上下文樹結構來對信源序列建模,此方法可以考慮更多鄰近的像素而不產生嚴重的上下文稀釋問題[9]. 1999年,Pasi等[10]使用靜態上下文樹來壓縮圖像,但該算法只適用于二進制信源. 2005年,Kopylov等[11]利用上下文樹建模和算術編碼來壓縮彩色地圖圖像,通過顏色分離,將圖像轉化為二進制層,利用層間依賴性來優化上下文樹模型的每個層. 2007,文獻[12]通過對樹修剪來優化樹結構,并將其用來壓縮地圖輪廓,但該算法需要預先離線訓練好上下文樹模型. 同年,楊文濤等[13]提出的一種多階上下文自適應算術編碼算法也只適用于壓縮二進制圖像. 2011年,文獻[14]將上下文樹建模用于光柵地圖圖像去噪. 2017年,文獻[15]將上下文樹結構用來無損壓縮從目標圖像中檢測到的輪廓. 2018年,文獻[16]使用動態規劃算法同時對圖像中檢測到的輪廓進行去噪和壓縮,并使用后綴上下文樹來降低算法的復雜性. 上下文樹結構的廣泛使用表明了其在壓縮編碼中的重要地位.

    通過對前人研究的分析,發現以下幾點問題:(1)上述算法多將上下文樹模型用于對地圖圖像建模;(2)將上下文樹模型用于對二進制圖像建模中,或將多進制圖像映射為二進制圖像;(3)使用靜態上下文樹模型用于圖像編碼. 針對這幾點問題,本文提出了基于上下文樹的無損壓縮算法. 算法使用上下文樹模型對多進制自然圖像編碼,并采用自適應的概率模型,故而無需提前訓練上下文樹模型,避免了使用靜態模型編碼的缺點. 此外,本文引入逃逸符號來處理算術編碼過程中的零頻符號問題,此方法改進了傳統零頻符號處理方式的缺陷. 同時,本文定期削減概率分布中的統計值,使條件概率分布隨著圖像的局部特征變化而變化. 仿真實驗結果表明,本文提出的算法能有效壓縮多進制信源.

    • 設信源的有限符號集Aαα>2)個不同的符號,A={0,$\cdots, $ α-1}. 現有已編碼的符號序列 $s_1^n$=s1,$\cdots, $ s2siA),記當前待編碼符號為sn+1=ccA),則稱已編碼的符號序列 $s_1^n$ 為當前符號c的上下文(Context). 則h階上下文可表示為:$s_{n - h + 1}^n$=sn-h+1,$\cdots, $ sn簡記為S. 對圖像而言,常見的上下文模板如圖1所示.

      圖  1  10階上下文模板,c表示待編碼符號

      Figure 1.  10-order context template, c indicates the current symbol to be encoded

      給定上下文的階數,便可以通過統計不同上下文序列所對應的計數矢量求得相應的條件概率分布. 符號在計數矢量中的統計值表示符號在對應上下文序列后出現的次數. 即

      $ {n_i}({s_{n - h + 1}}, \cdots ,{s_n})=n(c=i|{s_{n - h + 1}}, \cdots ,{s_n}) $

      其中,iA.

    • Context量化不考慮符號之間的相關性大小,很大可能會在量化過程中將最為重要的條件概率分布合并掉. 為了避免此類情況發生,本文考慮了符號重要性的差異,盡可能保留較為重要的上下文符號,引入樹結構來直觀地描述符號之間的相關性大小關系:樹的淺層表示較為重要的符號;樹的深層表示較不重要的符號.

      父節點相較于子節點不易出現“上下文稀釋”問題,因此當子節點的計數向量統計得不夠充分時,可選擇父節點編碼,這就意味著要合并這個節點和它的所有兄弟節點. 為了獲得更多的節點合并的可能性,我們通過公式(2)細致劃分信源的統計信息:根據上下文符號值的二進制表示,將現有的上下文序列(度α>2)轉化為二進制比特序列,對應的上下文樹可轉化為二叉樹[1].

      $I(d,v)={r^d} \times {2^{ - v}}$

      其中,d表示上下文符號位置與當前待編碼符號位置的幾何距離;v表示二進制比特中的比特高低位;r是常數,其取值范圍在0.9~0.95之間. 可用公式(2)依照重要性排出所有比特的順序.

      一般來說,對于二叉上下文樹,樹結構上互為兄弟節點的兩個孩子節點之間的相關性非常高,因此可以通過合并兩個孩子節點來降低模型代價,從而有效改善“上下文稀釋”問題. 上下文樹模型的學習過程的步驟如下:

      步驟1 創建樹的根節點;

      步驟2 創建一顆空的完全二叉樹,樹深為hlog2α. 設置樹上所有節點的計數矢量的初始值都為0;

      步驟3 對圖像中的每個像素執行如下操作:

      ①. 依據上下文模板(如圖1所示),在圖像上提取出待編碼符號的上下文像素. 若有上下文像素位置在圖像之外,則將此上下文像素置為0;

      ②. 將上下文像素值轉化為二進制比特,接著依照公式(2)對所有比特按照重要性由大到小排序,設排好序的上下文比特序列為 $x_0^{h*lo{g_2}\alpha - 1}$=${x_0}$,${x_1}$,$\cdots, $ ${x_{h*lo{g_2}\alpha - 1}}$. 其中某個長度為i(0<=i<h*log2α)的比特子序列 $x_0^{i - 1}$,對應樹結構上第i-1層中的某個節點;

      ③. 從根節點開始,根據路徑 $x_0^{h*lo{g_2}\alpha - 1}$ 遍歷樹上的節點直至到達葉子節點時停止. 對此路徑上經過的每個節點,其計數矢量的當前符號ccA)位置計數值加1.

    • 在對信源編碼的過程中,為了在解碼端正確無誤地恢復已編碼文件,不僅需要存儲實際信源序列的編碼比特數,還要存儲編碼時使用模型的比特數. 若想要提高壓縮效果,可以通過降低模型代價和降低實際信源編碼的碼長這兩部分來實現. 這兩部分的總和稱為描述長度. 因此,為了追求更好的壓縮效果,則需要得到較短的描述長度.

      定義一個α進制信源序列為s1,s2,$\cdots, $ sn. 記當前待編碼符號為sn+1,則當前符號的h階上下文為 $s_{n + 1 - h}^n$. 當前待編碼符號sn+1的條件概率計算如下:

      $P({S_{n + 1}}=c|s_{n + 1 - h}^n)=\frac{{{n_c}(s_{n + 1 - h}^n)}}{{\displaystyle \sum\limits_{j=0}^{\alpha - 1} {{n_j}(s_{n + 1 - h}^n)} }}$

      nc為以 $s_{n + 1 - h}^n$ 為上下文的待編碼符號c在已編碼信源序列 $s_1^n$ 中出現的次數. 所有的 ${n_j}(s_{n + 1 - h}^n)$j∈{0,α-1})構成估計上述條件概率分布的計數矢量.

      由此,第i個具有特定上下文序列的計數矢量其描述長度計算公式如下[17]

      $ {l_i}=[ln({N_i} + \alpha - 1)! - ln(\alpha - 1)!] - \sum\limits_{j=1}^\alpha {ln(n_j^{(i)})!} $

      其中,$n_j^{(i)}$ 為此計數矢量中第j個符號的計數值,${N_i}=\displaystyle \sum\limits_{j=1}^\alpha {n_{_j}^{(i)}}$,則信源序列的總描述長度可表示為 $L=\displaystyle \sum\limits_{i=1}^{{\alpha ^h}} {li}$.

    • 通過合并樹節點可以減小模型的傳輸代價,但使用合并后的節點編碼會導致平均碼長變長. 如果模型減小的代價大于平均碼長的增加量,則會使描述長度變短,進而改善編碼性能. 但若在合并節點時,僅比較上下文序列所對應上下文樹中一條路徑上的子節點與其父節點的編碼代價,并不能有效改善編碼效果. 原因在于:即使父節點的編碼代價小于其中一個子結點的編碼代價,也不能保證合并后的節點編碼代價會小于子節點的編碼代價之和. 因此,在合并節點的過程中需要保證父節點的編碼代價小于子節點的編碼代價之和.

      直觀的說,只有兩個子節點的條件概率分布相似的時候,才能保證使用合并后的節點編碼的平均碼長不會急劇增加,才有可能保證平均碼長的增加量小于模型代價的減少量,從而改善編碼性能. 因此,基于以上的考慮,我們需要保證合并后的節點其描述長度需小于兩個子節點描述長度之和.

      基于以上的分析,本文定義描述長度增量為:

      $ \Delta l_m^{}={l_m} - \left( {{l_{m1}} + {l_{m2}}} \right) $

      其中,lm1,lm2分別表示當前子節點與其兄弟節點的描述長度,lm則是它們父節點的描述長度. 當 $\Delta l_m^{}$<0時,則說明合并當前子節點及其兄弟節點是合理的.

      實際上,通過斯特林公式可將公式(5)近似為如下的形式:

      $ {l_i}= - {N_i}\sum\limits_{j=1}^\alpha {\bigg[\frac{{n_j^{(i)}}}{{{N_i}}}log\frac{{n_j^{(i)}}}{{{N_i}}}\bigg]} + \frac{{\alpha - 1}}{2}log{N_i} $

      lm可表示為:

      $\begin{split} l_m^{}=& - ({N_{m1}} + {N_{m2}})\\ &\sum\limits_{j=1}^\alpha {\bigg[\frac{{n{j^{(m1)}} + n{j^{(m2)}}}}{{N_{m1} + N_{m2}}}log\frac{{n{j^{(m1)}} + n{j^{(m2)}}}}{{N_{m1} + N_{m2}}}\bigg]} +\\ &\frac{{\alpha - 1}}{2}log({N_{m1}} + {N_{m2}}) \end{split}$

      將公式(6)、公式(7)帶入公式(5)并化簡,可得描述長度增量為:

      $ \begin{split} \Delta {l_m}=&\frac{{n_j^{(m1)}}}{{{N_{m1}}}} \times {N_{m1}}\sum\limits_{j=1}^\alpha {log\bigg[\frac{{n{j^{(m1)}}}}{{N_{m1}}}/\frac{{n{j^{(m1)}} + n{j^{(m2)}}}}{{N_{m1} + N_{m2}}}\bigg]} +\\ & \frac{{n_j^{(m2)}}}{{{N_{m2}}}} \times {N_{m2}}\sum\limits_{j=1}^\alpha {log\bigg[\frac{{n{j^{(m2)}}}}{{N_{m2}}}/\frac{{n{j^{(m1)}} + n{j^{(m2)}}}}{{N_{m1} + N_{m2}}}\bigg]} + \\ & \frac{{\alpha - 1}}{2}log\frac{{N_{m1} + N_{m2}}}{{N_{m1}N_{m2}}} \end{split} $

      其中,Nm1表示m1號計數矢量的總計數值,Nm2表示m2號計數矢量的總計數值.

      利用Kullback-Leibler散度公式可將公式(8)化簡為如下所示形式:

      $\begin{split} \Delta l_m^{} =&{N_{m1}} \times D({P_{m1}}|{P_m}) + {N_{m2}} \times D({P_{m2}}|{P_m}) +\\ &\frac{{\alpha - 1}}{2}log\frac{{N_{m1} + N_{m2}}}{{N_{m1}N_{m2}}} \end{split}$

      其中 ${P_m}$m號計數矢量對應的條件概率分布,${P_{m1}}$m1號計數矢量對應的條件概率分布,${P_{m2}}$m2號計數矢量對應的條件概率分布. 由公式(9)可以看出,描述長度增量與概率分布之間的相似度有著不可分割的關系,兩個概率分布越相似,將他們對應的計數矢量合并時,描述長度增量的值就越小. 因此,兩個子節點合并時的描述長度增量如果小于0,由式(9)可知,它們的概率分布一定非常相似,這樣的合并就是合理的. 除此之外,計數矢量中的總計數對描述長度增量的值有很大的影響,計數矢量的總計數越多,該計數矢量對描述長度增量的值產生的影響就越大. 而在概率模型學習的過程中,概率模型的統計值越多則統計越充分,說明此概率分布可信度較高,反之則可信度較低,描述長度增量的公式恰恰也反映了這一原則. 因此,使用描述長度增量作為節點合并原則是合理的.

    • 算術編碼因編碼性能高,故常用于圖像編碼領域. 算術編碼模式分為兩種:靜態模式和自適應模式. 在圖像編碼中常常采用自適應模式編碼,自適應模式需要在編解碼端給定相同的初始分布. 由于算術編碼器無法編碼零概率符號,所以常用的方法是設置初始計數值都為最小的正整數“1”. 使用這種方法會在編碼初期多次使用均勻分布編碼,故不利于改善編碼性能. 因此,本文考慮將初始計數分布的值都置為“0”,能較快統計到接近真實信源統計特性的條件概率分布. 但為了解決由此帶來的零概率問題,在此引入逃逸符號(escape symbol, esc)參與編碼.

    • 處理零頻符號問題需給每個條件概率分布中都設置一個逃逸符號,每個逃逸符號都有其自身的頻度. 當編碼過程中遇到零概率符號時,先編碼一個逃逸符號,再利用預先設置好的沒有零概率符號的概率模型,對當前符號編碼. 實際上,使用逃逸的方法處理零頻符號所產生的編碼代價并不小,但當該符號逃逸過一次之后,該符號位置就有了統計值,相比于其他符號位置計數值為零的情況而言,當再次編碼這個符號時,將會得到非常短的碼長,從而改善壓縮性能.

      每個逃逸符號在一個條件概率分布中至多使用α次. 當在對應的信源上下文子序列中,待編碼符號的頻度大于0時,該符號將不再發生逃逸,將使用自身的頻度來預測編碼概率. 根據當前上下文中的信息估計出對應逃逸符號的頻度,稱為逃逸估計.

      為簡單起見,采用方法A(Method A)來處理逃逸符號的頻度問題,方法A設置逃逸符號的頻度為“1”,且保持不變. 即,f($esc$|w)=1,其中m($esc$|w)為逃逸符號在w號計數矢量中的頻度值. 此外還有方法C[18],方法X[19]等.

    • 隨著編碼的進行,節點計數器中累計的計數值越來越多,長此以往,“數據溢出”問題便隨之而來,這會嚴重降低編碼性能. 因此,當計數矢量的總計數值超過預先設定的閾值T時,應該對總計數值做削減頻度處理. 再者,對于整幅自然圖像而言,統計一般是不平穩的. 削減頻度處理也可視為丟棄掉距離待編碼符號很久的已編碼符號所累計的計數值,使得更新后的條件概率分布能跟隨圖像局部的統計特性同步改變,進而更好地反映圖像的局部統計特性.

      較大的計數T可使計數矢量保留更多的圖像統計信息,從而使計數矢量更好地估計相應的條件概率分布. 但這也會導致條件概率分布的更新速度與圖像局部的特征變化不同步. 當計數T較小時,條件計數分布更新的速度很快,并且能更好的跟隨局部統計特征的變化,但這會導致計數矢量中的計數值較少,因而不能很好的估計條件概率分布. 從而導致編碼性能變差. 因此,可以通過實驗確定大小合適的T.

      削減頻度處理通常是對計數矢量中的所有符號對應的計數值做頻度減半處理. 為了避免再次出現符號逃逸的情況,削減頻度處理后不該產生零概率符號. 頻度削減的處理方式如公式(10)所示.

      $ TotalCount=\sum\limits_{i=0}^{\alpha -1}{{}}\square \left( SymbolCoun{{t}_{i}}+1 \right)/2\square $

      其中 $TotalCount$ 為某一計數矢量的總計數值,$SymbolCoun{t_i}$ 為此計數矢量中第i個符號計數值.

      經過削減頻度處理,節點計數器中的符號概率并不受影響. 接著,從樹的葉子節點到根節點逐層更新父輩節點的計數矢量中的統計值.

    • 在圖像傳輸的過程中,解碼端不能預先獲知待解碼符號,因此在編碼端引入一個預測符號代替待編碼符號,記為 $Symbo{l_c}$$Symbo{l_c}$A). 預測符號的估計方法有多種,經本文研究發現,對于多進制信源而言,較為準確的估計方法為使用具有圖像特性的上下文符號來對待編碼符號做線性預測,如公式(11)所示:

      $ Symbo{l_c} = {\rm{ }}{k_1} \times {S_n} + {k_2} \times {S_{n - 1}} + {k_3} \times {S_{n - 2}} $

      其中Sn,Sn-1,Sn-2分別為與待編碼符號相關性最高的三個上下文符號;k1,k2,k3分別為線性預測的加權系數.

      系統算法的步驟如下:

      步驟1. 創建樹的根節點;

      步驟2. 根據如圖1所示的上下文模板構建h階上下文,再使用算法1構造出完整的二叉上下文樹Tb;

      步驟3. 在上下文 $s_{n - h + 1}^n$ 條件下,判斷葉子節點儲存的計數矢量中 $Symbo{l_c}$ 位置的頻數值;

      ①. 若頻數f$Symbo{l_c}$|$s_{n - h + 1}^n$)等于0,則判斷葉子節點對應的父親節點的頻數f$Symbo{l_c}$|$s_{n - h}^n$)是否為0:

      a. 若頻數f$Symbo{l_c}$|$s_{n - h}^n$)為0,則選擇最深層節點儲存的條件概率分布編碼;

      b. 若頻數f$Symbo{l_c}$|$s_{n - h}^n$)大于0,則通過判斷最深層節點與其父節點處通過條件概率分布編碼的平均碼長,若其父節點的平均碼長稍小,則選用其父節點處的條件概率分布編碼;反之,使用葉子節點處的條件概率分布編碼.

      ②. 若頻數f$Symbo{l_c}$|$s_{n - h + 1}^n$)大于0,則通過由葉子至根逐層判斷路徑上節點的描述長度增量. 若其中某節點處描述長度增量小于0,則選用該節點處儲存的條件概率分布編碼;反之,則不合并節點,繼續使用路徑上的葉子節點的條件概率分布編碼;

      步驟4. 若被選中的編碼節點的計數矢量中實際待編碼符號的頻數為0,則進行逃逸處理;否則,使用被選中節點的實際條件概率分布編碼;

      步驟5. 若葉子節點統計的總計數值超過閾值T,則依照4.2節中的方法對當前計數矢量進行頻度削減. 同時,上下文序列所對應樹的一條路徑上的所有父輩節點的計數矢量都需依照葉子節點的統計值重新計算.

      步驟6. 重復步驟3、步驟4和步驟5,直至信源編碼結束.

    • 本文實驗使用對象為大小為512×512,灰度級為256的標準灰度圖像(如圖2). 為了簡化實驗,我們將原始標準灰度集圖像的灰度級量化至8灰度級. 在基于上下文的壓縮編碼中,由信息論中條件降低熵值可知,增加上下文的階數,就有可能獲得更好的編碼效果,但“Context稀釋”問題也隨之而來,所以對于不同大小的圖像來說,獲得最優編碼效果時所使用的上下文階數是不同的. 就本文提出的算法而言,在構造上下文樹模型之前需要先設定好上下文模型的階數. 使用算術編碼方式對lena圖像編碼的結果可知,使用4階上下文建模時,且上下文模板如圖3時,其壓縮效果最好. 故本文中的實驗皆以4階上下文為基礎. 另一方面,本文設置預測符號的加權系數都為 $\dfrac{1}{3}$,這也可節省逐一對標準圖像集中圖像訓練加權系數所附加的時間.

      圖  2  標準圖像集

      Figure 2.  Standard grayscale image set

      圖  3  4階上下文模板,c為待編碼符號

      Figure 3.  4-order context template, c is current symbol

      由4.2小節的分析可知,通過頻度削減更新概率模型是非常必要的,但不同的計數閾值T對編碼性能的影響不同. 圖4展示了通過調整算法2中的參數T對lena圖像的壓縮性能所產生的影響.

      圖  4  參數T對lena圖像壓縮性能的影響

      Figure 4.  Influence of adjusting the parameter T on the compression performance for the lena

      圖4中的虛線表示未對統計值做削減頻度時lena圖像的編碼文件大小,為16 744 byte. 從圖4可知,隨著參數T的逐漸增大,lena的壓縮文件大小也隨之波動,但整體的變化趨勢呈凹型. 當參數T超過4 000時,lena圖像的壓縮效果越來越差,逐漸趨于未對lena做頻度削減處理時的編碼效果. 此外,當閾值T設置的太小時,lena的壓縮效果非常差,這是由于計數矢量更新的速度太快,導致計數矢量沒有得到充分的學習,因此生成的條件概率分布不能反映圖像局部的真實統計特性,從而導致編碼性能得不到有效的改善. 當T為700時,到達曲線的最小值點,可將lena圖像壓縮至16 577 byte,達到最優的壓縮效果.

      為了檢驗閾值T為700是否也適用絕大多數自然圖像,本文對圖2所示的標準圖像集中的圖像皆比較了當閾值T為700的情況下圖像的編碼效果,以及不對統計值做削減頻度情況下圖像的編碼效果,如表1所示. 結果顯示,設置閾值T為700對于一般的圖像而言都有較好的編碼效果.

      lenapeppersphotographyplaneelainecouple
      不削減
      頻度
      167441408310862140631830423219
      T=700165771400610756140271821922964

      表 1  閾值為700對圖像編碼的影響(單位:字節)

      Table 1.  The performance of threshold T=700 on image encoding(unit: byte)

      接著,我們比較了提出的方法與其他幾種方法做了比較,比較結果如表2所示.

      實驗圖像初始的3階上下文樹模型初始的4階上下文樹模型初始的5階上下文樹模型文獻[13]文獻[1]提出的方法
      lena172381726918084172391716716577
      peppers145831459715302146091452814006
      photography115761140912174114161127010756
      plane147251454315305145461442714027
      elaine191731882419359188291896118219
      couple241762377524916238032379622964

      表 2  6種方法的壓縮效果比較(單位:字節)

      Table 2.  Comparison of compression performance of six methods (unit: byte)

      表2的第二,三和四列顯示了使用初始3階,4階以及5階上下文樹模型編碼的圖像壓縮性能,該模型將初始的計數向量設置為均勻分布,且將初始計數值置為“1”,以此避免在算術編碼過程中遇到零概率問題. 表2的第五列展示了使用文獻[13]中的方法對圖像集中圖像的編碼效果,在編碼過程中,該方法選擇條件概率分布中的大概率值符號代替小概率值符號用于編碼. 表2的第六列展示了使用文獻[1]中的方法對實驗圖像的編碼效果,該方法使用描述長度作為節點合并原則. 表2的最后一列顯示了使用本文所提出方法的壓縮性能.

      比較表2的第二列至第四列,可得出選擇上下文模型的階數為4階時,本文提出的算法獲得了更好的編碼效果. 比較表2的第三列和第七列,可以驗證逃逸處理對編碼性能改善是很有效的. 比較表2中的第五列和第七列,可以明顯看出本文采用線性預測的方式來估計待編碼符號獲得了更好的編碼效果. 比較表2中的第六列和第七列,結果顯示使用描述長度增量作為節點合并原則的編碼性能明顯優于使用描述長度作為節點合并原則的編碼性能,這與我們在本文第3節中的分析一致.

    • 相較于二進制信源序列的無損壓縮而言,多進制信源序列的無損壓縮存在的問題是上下文模型數量太多,且每個條件概率分布當中符號數量也較多,使得信源的統計值分布在太多的用于估計條件概率分布的計數矢量中,這便導致了更嚴重的“上下文稀釋”問題,致使壓縮效果變差. 本文針對此問題提出了基于上下文樹的無損壓縮算法,利用信息論中條件降低熵值的原則,建立了上下文樹模型,并利用描述長度增量作為樹節點的合并原則,從而獲得更有益于編碼的條件概率分布. 并引入逃逸符號來處理編碼過程中的零頻問題,此方式改進了傳統處理零頻問題方式的缺點. 此外,此算法定期更新概率模型,使得條件概率分布跟隨圖像局部特征同步變化,從而有助于提高編碼性能. 與其他的方法相比,本文提出的算法取得了更好的壓縮效果.

參考文獻 (19)

目錄

    /

    返回文章
    返回