最佳化截取內嵌碼塊編碼

最佳化截取內嵌碼塊編碼(embedded block coding with optimized truncation)，簡稱EBCOT，是最新靜態圖像編碼國際標準JPEG2000的核心。JPEG2000中採用EBCOT進行熵編碼。

通過EBCOT能實現對圖像的有效壓縮，此外，產生的碼流具有解析度可伸縮性、質量(信噪比)可伸縮性、隨機訪問和處理等非常好的特性。JPEG2000 將 EBCOT 編碼分為兩級(Two Tiers)，第一級為塊編碼(Block Coding )，即比特平面編碼和算術編碼(MQ)，第二級為碼流組織。

基本介紹

• 中文名：最佳化截取內嵌碼塊編碼
• 外文名：embedded block coding with optimized truncation
• 簡稱：EBCOT
• 提出者：David Taubma
• 套用：圖像編碼
• 組成結構：塊編碼和碼流組織

基本結構

JPEG2000 的基本結構如圖1所示。首先對原始圖像數據預處理，接著進行離散小波變換，然後在形成輸出碼流(比特流)之前，對變換係數進行量化、比特平面編碼和算術解碼，最後進行率失真控制和碼流組織，形成壓縮碼流。壓縮碼流通過存儲或傳輸後，進行與上述過程相反的變換後恢復出圖像數據。

圖1 JPEG2000 系統的基本編碼框圖

簡介

EBCOT 算法是建立在碼塊(code-block)的基礎上，將每個子帶分成若干塊，如 32x32 或 64x64，每個碼塊獨立編碼，利用內部的相關特性進行壓縮，對於每個碼塊再按質量進行分層，分成若干塊段，各個塊段之間就是截斷點；選擇一些碼塊和碼塊中的一些碼段，就可以支持多解析度和質量的碼流結構。

圖2 EBCOT 的組成框圖

EBCOT 算法可以分為 T1 和 T2 兩部分，圖2所示。T1包括比特平面編碼、算術編碼，負責數據的具體壓縮；T2負責碼流組織，主要根據壓縮後率失真最最佳化算法(PCRD)實現的碼流進行組織，並完成最後的打包工作。

優點

(1) 定質量解釋：由於每個質量層可包含來自每個碼塊的任意貢獻，質量的概念容易適應面向特定套用的顯著性量度。與EZW和SPIHT和其他嵌入式壓縮算法相比，當已知對應的空間區域或頻帶對某個套用並不重要時，EBCOT允許截斷不需要的質量層數據。

(2) 靈活的結構：EBCOT 具有解析度可伸縮性、失真可伸縮性(只要採用多重質量層)和一定程度的空間可伸縮性。當壓縮多重圖像分量(例如，彩色分量)時，這些分量構成了可伸縮性的第四維。JPEG2000 支持所有沿四維的漸進。

(3) 局部處理：獨立編碼允許對每個碼塊中的樣本進行局部處理，這有利於硬體的實現。獨立編碼引入高度並行實現的可能性，其中多個碼塊可以同時進行編碼和解碼。

(4) 有效壓縮：PCRD(壓縮後率失真最佳化)算法可以更多的補償由於施加獨立塊編碼產生的效率損失，算法也能夠適應空間變化和與圖像有關的失真度量。

(5) 抗誤碼：在任何塊編碼的位流中遇到的誤差對其他塊編碼沒有影響，即所有JPEG2000 的碼流都是解析度可分割的。

比特編碼

原理

比特平面編碼的任務就是生成數據的上下文信息，以供熵編碼使用。它以碼塊為單位，掃描方式如圖3所示。在某一比特平面上，一列中 4 個相鄰的點組成一個條帶。算法從第一個點(左上角)開始,依次掃描當前條帶內的 4 個點，然後跳到右側相鄰條帶，掃描到碼塊的右側邊界時，折回到左側的下一條帶。

圖3 碼塊的掃描方式

碼塊的每個比特平面要經過 3 道掃描。重要性傳播過程(SignificancePropagation Pass)，使用零編碼 ZC 和符號編碼 SC 原語編碼；幅度細化過程(Magnitude Refinement Coding )，使用 MRC 原語編碼；清理過程(Clear Pass )，使用遊程編碼 RLC 和符號編碼 SC 原語編碼。

很多情況下，子帶的小波係數的高位比特平面出現全零的情況，編碼從最高重要比特平面 MSB 開始可節約大量時間。每層比特平面按 3 道掃描順序處理完該比特平面，然後再用同樣的方法處理低一層的比特平面，直到第 0 比特平面處理完成，表明該碼塊的比特平面編碼完成。

具體算法步驟

具體的比特平面編碼算法如下：

(1) 重要性傳播， ：對於自己不重要但有重要鄰居的係數進行ZC編碼，如果係數由不重要變成重要則進行SC 編碼。

(2) 幅值細化， ：對於己經重要的且在當前比特平面沒有編碼的係數進行MR編碼。

(3) 清理更新， ：對於自己不重要且未編碼過的係數進行ZC或RLC 編碼，如果有係數由不重要變成重要則進行SC 編碼。這裡又引入一個訪問狀態變數ηi[m,n]來表示 在當前比特平面是否編碼過。

(4) ηi[m,n]置0，返回第1步進行下一個比特平面p-1的編碼。

算術編碼

算術編碼是一種用於數據壓縮的編碼技術，它是基於 Shannon 定理的可變長的熵編碼。算術編碼的基本思想是用區域劃分來表示信源輸出序列，信源輸出的任何一種組合，與[0 ,1) 區間內的某一區域一一對應。用算術方法表示這一區域為一個二進制小數。這個二進制小數是信源輸出序列的一種編碼，且它是唯一可解碼的。算術編碼的編碼過程與信源的機率模型是分離的。在實際中使用機率估值表。

最優算法

T1編碼器產生的比特流是內嵌的，利用率失真最佳化截取算法可以獲得最優的壓縮性能。設碼塊 在T1部分產生的內嵌比特流的碼率截止到 ， 是某個截取點，即T1某個編碼過程的結束點，則圖像總的碼率為：

設碼塊 的係數在恢復圖像中產生的失真為 且其失真是加性的，即：

其中，D表示整幅圖像的失真大小。

現在需要找到一組 ，使得在滿足 時，D最小。解決這種條件極值問題可以通過拉格朗日算法。因此問題等價於使下式最小化：

其中調整 直到產生一組截取點使得上式在滿足 時最小。對於上式最小化問題很可以歸結為單個碼塊的最小化問題。即對於碼塊 找到截取點 使得 最小。查找算法如下：

(1) 令 =0(即沒有比特流)；

(2) 對於k=1,2,3…，計算 ， ；

(3) 若 ，則 =k。

由於這個算法要對不同的 進行查找，因此先剔除一些奇異點，使率失真斜率隨著k嚴格單調減。確定候選截取點算法如下：

(1) 令 ={n}，n∈N，即所有過程的截止點；

(2) 令p=0；

(3) 對於 k，k∈ 。

計算，，。若p≠0且，則從剔除p並返回(2)；否則，令p=k。