<address id="japib"><nav id="japib"></nav></address>

<cite id="japib"></cite>

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

        王炯 陳建華 和志圓

        引用本文:
        Citation:

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

          作者簡介: 王 炯(1994?),女,陜西人,碩士生,主要研究圖像壓縮.E-mail:759739201@qq.com;
          通訊作者: 陳建華, chenjh@ynu.edu.cn
        • 中圖分類號: TN911.21

        Lossless compression algorithm based on context tree

          Corresponding author: CHEN Jian-hua, 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對圖像編碼的影響(單位:Byte)

          Table 1.  The performance of no reduction frequency and threshold T=700 on image encoding (unit: Byte)

          圖像不削減頻度T=700
          lena1674416577
          peppers1408314006
          photography1086210756
          plane1406314027
          elaine1830418219
          couple2321922964
          下載: 導出CSV

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

          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] Aulinas 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, Oscar C A, Zhai G T. 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. Chen J H, Yu J H, Shi X L. Context modeling based on context quantization[J]. Journal of Yunnan University: Natural Science Edition, 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] Fränti 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, Fr?nti 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,et al. 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] 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.
          [15] 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.
          [16] 陳建華, 王勇, 張鴻. 基于描述長度的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.
          [17] 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.
          [18] 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的多描述編碼方案. 云南大學學報(自然科學版), 2012, 34(6): 648-652.
          [2] 張忠玉劉惟一張玉琢 . Bayesian網的信息熵. 云南大學學報(自然科學版), 2002, 24(3): 183-185,191.
          [3] 許傳云周忠 . 雙峰映射的一類特殊符號乘法. 云南大學學報(自然科學版), 2002, 24(3): 192-194,198.
          [4] 彭守禮 . 符號動力學,星花積及其他. 云南大學學報(自然科學版), 2003, 25(3): 221-224.
          [5] 李港羅志全楊娟曾曉雄 . 旋轉帶電BTZ黑洞的修正熵. 云南大學學報(自然科學版), 2010, 32(4): 437-442 .
          [6] 曾熙雯張鵬飛陳自明 . 鱗頭鰍觸須畸形個體描述. 云南大學學報(自然科學版), 2011, 33(S2): 440-443.
          [7] 韓澤軍丁洪偉岳昆李春芬楊志軍 . 碰撞長度可變的三時鐘N?CSMA的WSN協議分析. 云南大學學報(自然科學版), 2019, 41(4): 699-706. doi: 10.7540/j.ynu.20170766
          [8] 李勇余江劉言立宗容胡勁松 . 基于CRC-RS編碼的無線雙信道模型. 云南大學學報(自然科學版), 2013, 35(6): 756-761. doi: 10.7540/j.ynu.20120617
          [9] 王佳周華梁志宏代飛白麗瑞 . 基于信息熵的軟件維護風險度量. 云南大學學報(自然科學版), 2012, 34(2): 159-164.
          [10] 曹克非王參軍 . Tsallis熵與非廣延統計力學. 云南大學學報(自然科學版), 2005, 27(6): 514-520.
          [11] 支元洪何青海 . 基于實值函數極限理論的無窮大符號討論. 云南大學學報(自然科學版), 2019, 41(6): 1090-1100. doi: 10.7540/j.ynu.20190419
          [12] 王麗珍孫茂林Enrique Chujoy . 云南馬鈴薯儲藏害蟲及其特征描述. 云南大學學報(自然科學版), 2002, 24(5): 398-400.
          [13] 錢寧李彤 . 描述軟件過程繼承的一種方法. 云南大學學報(自然科學版), 2008, 30(4): 367-370.
          [14] 程昆夏幼明高佳樂 . 基于時間區間關系的時態模糊描述邏輯研究. 云南大學學報(自然科學版), 2014, 36(3): 335-340. doi: 10.7540/j.ynu.2013011a
          [15] 余錦華陳建華李東暉余煒施心陵 . 基于Context模型的非嵌入式小波彩色圖像編碼方案. 云南大學學報(自然科學版), 2003, 25(2): 110-114,132.
          [16] 王繪山陳貴元蔣宗敏王文學王維孟勝科張理超余敏崔清華李梅章 . 樹鼩VEGF全長編碼序列的克隆及分子特征分析. 云南大學學報(自然科學版), 2014, 36(5): 781-787. doi: 10.7540/j.ynu.20140027
          [17] 張亞鵬唐猛李海華謝靈運陳建華 . 物理層網絡編碼與LDPC碼聯合系統設計及性能優化. 云南大學學報(自然科學版), 2020, 42(1): 28-35. doi: 10.7540/j.ynu.20190226
          [18] 李海華唐猛張亞鵬謝靈運陳建華 . 多中繼物理層網絡編碼系統與LDPC碼聯合設計及性能分析. 云南大學學報(自然科學版), 2020, 42(): 1-9. doi: 10.7540/j.ynu.20190651
          [19] 李慧玲楊樹政蔣青權 . 緩變動態Reissner-Nordström黑洞的熵. 云南大學學報(自然科學版), 2005, 27(5): 416-420.
          [20] 龍超云何勇龍洪其 . 鐵磁系統中介觀疇壁的雙波描述及量子漲落. 云南大學學報(自然科學版), 2003, 25(1): 29-32.
        • 加載中
        圖(4)表(2)
        計量
        • 文章訪問數:  305
        • HTML全文瀏覽量:  326
        • PDF下載量:  10
        • 被引次數: 0
        出版歷程
        • 收稿日期:  2019-11-25
        • 錄用日期:  2020-05-20
        • 網絡出版日期:  2020-08-28
        • 刊出日期:  2020-11-10

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

          作者簡介:王 炯(1994?),女,陜西人,碩士生,主要研究圖像壓縮.E-mail:759739201@qq.com
          通訊作者: 陳建華, chenjh@ynu.edu.cn
        • 云南大學 信息學院,云南 昆明 650500

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

        English Abstract

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

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

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

          • 設信源的有限符號集Aαα>2)個不同的符號,A={0,$\cdots, $ α-1}. 現有已編碼的符號序列 $s_1^n$=s1,$\cdots, $ sisiA),記當前待編碼符號為sn+1=ccA),則稱已編碼的符號序列 $s_1^n$ 為當前符號c的上下文. 則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.

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

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

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

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

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

            步驟 1 創建樹的根節點.

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

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

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

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

            (3) 從根節點開始,根據路徑 $x_0^{h{\log_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個具有特定上下文序列的計數向量其描述長度計算公式如下[16]

            $ {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}} {l_i}$.

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

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

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

            $ \Delta l_{\rm{m}}={l_{\rm{m}}} - \left( {{l_{{\rm{m}}1}} + {l_{{\rm{m}}2}}} \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_{\rm{m}}^{}=& - ({N_{{\rm{m}}1}} + {N_{{\rm{m}}2}})\cdot\\ &\sum\limits_{j=1}^\alpha {\bigg[\frac{{n_j^{{\rm{m}}1} + n_j^{{\rm{m}}2}}}{{N_{{\rm{m}}1} + N_{{\rm{m}}2}}}\log\frac{{n_j^{{\rm{m}}1} + n_j^{{\rm{m}}2}}}{{N_{{\rm{m}}1} + N_{{\rm{m}}2}}}\bigg]} +\\ &\frac{{\alpha - 1}}{2}\log({N_{{\rm{m}}1}} + {N_{{\rm{m}}2}}). \end{split}$

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

            $ \begin{split} \Delta {l_m}=&\frac{{n_j^{{\rm{m}}1}}}{{{N_{{\rm{m}}1}}}} {N_{{\rm{m}}1}}\sum\limits_{j=1}^\alpha {\log\bigg[\frac{{n_j^{{\rm{m}}1}}}{{N_{{\rm{m}}1}}}/\frac{{n_j^{{\rm{m}}1} + n_j^{{\rm{m}}2}}}{{N_{{\rm{m}}1} + N_{{\rm{m}}2}}}\bigg]} +\\ & \frac{{n_j^{{\rm{m}}2}}}{{{N_{{\rm{m}}2}}}} {N_{{\rm{m}}2}}\sum\limits_{j=1}^\alpha {\log\bigg[\frac{{n_j^{{\rm{m}}2}}}{{N_{{\rm{m}}2}}}/\frac{{n_j^{{\rm{m}}1} + n_j^{{\rm{m}}2}}}{{N_{{\rm{m}}1} + N_{{\rm{m}}2}}}\bigg]} + \\ & \frac{{\alpha - 1}}{2}\log\frac{{N_{{\rm{m}}1} + N_{{\rm{m}}2}}}{{N_{{\rm{m}}1}N_{{\rm{m}}2}}}, \end{split} $

            其中,Nm1表示m1號計數向量的總計數值,Nm2表示m2號計數向量的總計數值,$n_j^{{\rm{m}}1} $表示第 m1 個計數向量中第 j 個符號的計數值,$n_j^{{\rm{m}}2} $表示第 m2 個計數向量中第 j 個符號的計數值.

            利用Kullback-Leibler散度公式可將公式(8)簡化為:

            $\begin{split} \Delta l_{\rm{m}} =&{N_{{\rm{m}}1}} D({P_{{\rm{m}}1}}|{P_{\rm{m}}}) + {N_{{\rm{m}}2}} D({P_{{\rm{m}}2}}|{P_{\rm{m}}}) +\\ &\frac{{\alpha - 1}}{2}\log\frac{{N_{{\rm{m}}1} + N_{{\rm{m}}2}}}{{N_{{\rm{m}}1}N_{{\rm{m}}2}}}, \end{split}$

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

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

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

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

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

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

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

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

            $ C_{{\rm{total}}}=\sum\limits_{i=0}^{\alpha -1}{{}}\left\lfloor \left( {{C}_{i}}+1 \right)/2\right\rfloor, $

            其中 ,$C_{{\rm{total}}}$ 為某一計數向量的總計數值,${C_i}$ 為此計數向量中第i個符號計數值.

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

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

            $ {Q_c} = {\rm{ }}{k_1} {S_n} + {k_2} {S_{n - 1}} + {k_3} {S_{n - 2}}, $

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

            系統算法的步驟如下:

            步驟 1 創建樹的根節點.

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

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

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

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

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

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

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

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

            步驟 6 重復步驟3~5,直到信源編碼結束.

          • 本文實驗使用512×512、256灰度級的標準圖像(如圖2). 為了簡化實驗,我們將原始圖像的灰度級量化至8灰度級. 在基于上下文的壓縮編碼中,由信息論中條件降低熵值可知,增加上下文的階數,有可能獲得更好的編碼效果,但“上下文稀釋”問題也隨之而來,另外模型階數也和圖像的大小有關. 就本文提出的算法而言,在構造上下文樹模型之前需要先設定好上下文模型的階數. 使用算術編碼方式對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

            由3.2小節的分析可知,通過頻度削減更新概率模型是非常必要的,但不同的計數閾值T對編碼性能的影響不同. 圖4展示了通過調整系統算法中的參數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對于一般的圖像而言都有較好的編碼效果.

            圖像不削減頻度T=700
            lena1674416577
            peppers1408314006
            photography1086210756
            plane1406314027
            elaine1830418219
            couple2321922964

            表 1  不消減頻度和閾值為700對圖像編碼的影響(單位:Byte)

            Table 1.  The performance of no reduction frequency and threshold T=700 on image encoding (unit: Byte)

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

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

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

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

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

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

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

        參考文獻 (18)

        目錄

          /

          返回文章
          返回