基本介紹
- 中文名：快速高效無損圖像壓縮系統
- 外文名：Fast and Efficient Lossless Image Compression System, FELICS
- 類別：圖像壓縮算法
歷史,原理,FELICS算法的不足之處,改進,
歷史
原理
FELICS 與其它用熵編碼器針對經過去相關的圖像進行壓縮的無損圖像壓縮算法類似，去相關表示為
，其中
，
， 其中
是用於對當前像素P 進行編碼提供相關信息的兩個相鄰的像素（因果 在解碼器中已經進行編碼並且已知）。
P 可以在區間 [L,H] 之內、也可以大於 H 或者小於 L，第一種情況用 1 位表示，第二種情況用 2 位表示。下面的圖示表示像素的直方圖、沿 x 軸的亮度值以及在 y 軸上的出現頻率。
當 P 落在區間之外的時候使用 Rice code 進行編碼，參數是自適應選擇的，這是因為出現的機率是按照指數分布的。
對於最後在 區間(L，H) 中不再擺動的區域（dead-beat zone）, FELICS 使用修正的二進制編碼對餘數進行編碼。這種使用上下文關係的形式是後向自適應量化，它可以避免前向自適應量化中多餘的標誌從而實現更大的壓縮。
對於指數分布的尾數使用傳統的 Golomb Rice code 進行編碼。在Golomb-rice編碼中，k的選取恰當與否直接關係到編碼效率。因此FELICS算法採用自適應的方法對k值進行估計來選出最適當的k值，估計的過程基於編碼長度的累加表。
FELICS算法的不足之處
FELICS算法原理的分析可以看出，Golomb-rice熵編碼中基數K的選取無須複雜的計算過程，簡單高效。但是它需要U×V×T比特大小的儲存空間，其中U，V 和T分別代表Δ值的個數、備選K值的個數和在每一個K值下累計編碼的長度，若選用硬體的實現方法將會需要相當大的存儲空間。
另外，每處理一個落在[L,H]區間之外的像素點，需要對當前的預測誤差進行V次Golomb-rice編碼，其中一次是用選出的K值對其進行編碼，其餘的(V-1)次是為了更新累加表用未被選中的K值對預測誤差進行編碼。不難發現，每處理一個像素點，將需要額外(V-1)次編碼的時鐘周期來更新累加表，通過像素點的分布機率可以看出，大概有半數的像素點需要用Golomb-rice編碼法進行熵編碼，若所有這些像素點都要以這種形式進行熵編碼將會使編碼效率大幅度降低。
改進
針對Golomb-rice熵編碼中參數K的選取和整體編碼長度的控制兩部分做出了以下改進。
首先是參數K的選取：參考基於圖像上下文的序列參數估計法，將待壓縮的圖像適當分塊來分別進行累加表的更新和K值的選取，這樣可以利用圖像的局部特性來使K值的選取更加精準。另外，保留標準FELICS算法中以Δ值的不同來分別進行參數更新的技術手段，這是因為相同的Δ象徵著相同的上下文環境，因此以Δ為單位進行更新也會使K值的預測更為準確。在每一個Δ值下，需要設定兩個變數N和C來分別記錄當前Δ值下有像素點出現的個數和其預測誤差的累計值，具體的計算步驟會在下文詳細描述。與FELICS算法不同的是，改進後的算法只需要2×U×T 比特的存儲空間，其中2表示的是一個Δ下只需要兩個變數來記錄累計編碼信息，U代表Δ值的個數，T代表兩個變數所需要的存儲位數。和標準的FELICS算法相比，本文所提出的改進算法節省了4倍的存儲空間，使得本方法更加適用於硬體實現。
其次，基於K值的選擇機制，當上下文環境差別，即Δ值較大時，K值的選擇難免會出現不恰當的情況，這將會導致編碼結果變得相當長。因此不僅會使壓縮比受到影響，當考慮到用硬體的方法進行實現時，還會使存儲空間的選擇變得比較困難。因為若因少數幾個編碼長度較長的像素點就選用較大的存儲空間，將會導致存儲資源得不到充分的利用，進而造成硬體資源的嚴重浪費。
因此採用限長編碼的方法，首先計算出一進制編碼的位數，當一進制編碼的位數大於5時，總的Golomb-rice編碼的長度就會大於16，在這種情況下，就將Golomb-rice編碼轉變為限長編碼，用{6’b000000 + 8’b D}作為最終的編碼，其中6比特的‘0’作為標記位，表示要用限長編碼，後面的8比特就是當前像素點預測誤差的二進制表示形式，總的碼長是14位。另外兩位用於表示當前像素點所處的位置，當其處於below-range區域時，用2比特的’10’來表示，當其處於above-range區域時，用2比特的’11’來表示。這2比特加上之前的14比特，限長編碼的總比特數為16比特。
