格倫布編碼

无损数据压缩方法

格倫布編碼是一種無失真資料壓縮方法,由數學家所羅門·格倫布在1960年代提出。其優點為易於編碼與解碼,另外對於擁有機率分布為幾何分佈的資料,格倫布編碼是最佳的前綴碼,且能無限逼近該資料的,目前廣泛用於無損影像壓縮

編碼的建立编辑

 

令輸入值 為正整數 ,參數值為正整數  ,輸出之格倫布碼為  ,其中 由兩種編碼組合而成,

  一元編碼 截斷二進制編碼

計算   

   

 一元編碼 截斷二進制編碼即可得到 

哥倫布-萊斯編碼中的商數 指示了所在區塊,而 指示所在區塊內部的位置。如上圖,對整數  做哥倫布-萊斯編碼, 代表區塊、 表示區塊內部位置、 為參數,每個區塊的大小皆相等且長度為 ,特別注意當編碼方式為哥倫布-萊斯編碼時,即  的整數次方,所有 編碼長度相等。

參數 伯努利過程的函數,其中伯努利過程的參數 定義為 ,則 的所在區間為此伯努利過程中位數-1到中位數+1之間。如下式:

 

 足夠大時,我們可以將其表示成, 

使用符號整數编辑

哥倫布編碼主要是針對非負整數進行編碼,但也可以使用重疊(Overlap)與交錯(Interleave)擴展至對所有整數進行編碼。令一串用於編號的數列,(0,1,2,...),給予非負整數偶數編號,給予負整數奇數編號,使得排列方式如下,(0,-1,1,-2,2,...),即非負整數  映射 ,負整數   映射 

萊斯編碼编辑

萊斯編碼(Rice coding,由Robert F. Rice所提出),為一種前綴碼,歸屬於哥倫布編碼的子集合,參數  的整數次方,即 。此種特例未必是所有格倫布編碼中的最佳編碼方式,但由於目前電腦為二進位運算,萊斯編碼能快速且有效地以二進位運算實現。

性質编辑

范氏霍夫曼編碼编辑

格倫布編碼為一種范氏霍夫曼編碼

演算法编辑

1.選擇參數 

2.待編碼數值為 ,計算:

  1. 商數:  
  2. 餘數:  

3.編碼

  1. 商數編碼,對 進行一元編碼,得到 
  2. 餘數編碼,對  進行截斷二進制編碼,得到 
  3. 合併, 

4.輸出 

範例编辑

M = 10. 則  .  

商數編碼
q 輸出位元
0 0
1 10
2 110
3 1110
4 11110
5 111110
6 1111110
   
N  
餘數編碼
r 偏移 二進位 輸出位元
0 0 0000 000
1 1 0001 001
2 2 0010 010
3 3 0011 011
4 4 0100 100
5 5 0101 101
6 12 1100 1100
7 13 1101 1101
8 14 1110 1110
9 15 1111 1111

選擇42作為編碼時,42會被拆成  ,編碼為11110010,而商數編碼尾數必為0,能標示商數編碼位元的結束。

參考來源编辑