第九章 植基於小波係數的影像壓縮法.

Presentation on theme: "第九章 植基於小波係數的影像壓縮法."— Presentation transcript:

1 第九章 植基於小波係數的影像壓縮法

2 9.1 前言 9.2 EZW法 9.3 二個改良式EZW法 9.4 局部區域壓縮法 9.5 EBCOT法 9.7 作業
9.1 前言 9.2 EZW法 9.3 二個改良式EZW法 9.4 局部區域壓縮法 9.5 EBCOT法 9.7 作業 9.3.1 SPIHT法 9.3.2 連結係數法

3 9.2 EZW法 門檻值： , max Yij為小波係數中取絕對值後最大者。
ZTR ︰假若有一小波係數的絕對值小於某一門檻值T，且該小波係 數的子孫之係數值皆小於T時，則該小波係數稱為ZTR類的係數。 IZ︰假若有一小波係數的絕對值小於T，但在其子孫中，存在有至 少一個係數大於T時，則該小波係數稱為IZ類的係數 。 POS︰假若有一正的小波係數，其值大於T，則該小波係數稱為 POS類的係數。 NEG︰假若有一負的小波係數，其絕對值大於T，則該小波係數稱 為NEG類的係數。 Z︰假若該係數已沒子孫了。

4 以一8×8的三階小波係數矩陣為例(下圖左)，資料讀取順序用Z字型 掃描方式(下圖右) 。
EZW壓縮法實例說明 以一8×8的三階小波係數矩陣為例(下圖左)，資料讀取順序用Z字型 掃描方式(下圖右) 。 圖9.3 Z字型掃描方式 圖9.1 三階小波係數矩陣

5 第一階段 門檻值：max Yij = 54，所以可得T0 = 25 = 32。 依順序輸入的係數依次為：54, -33, -30, 22, 47, 11, 15, -13, 14, 13, -8, -8,2,-11, -14, 9, 8, …, 1, -6, …, 46, …, 5, 4, …, 3 由54 > T0 ，我們送出POS，|-33| > T0 ，送出NEG，|-30| < T0 ，但其子孫中有一係數46 > T0 ，以送出IZ。22 < T0 ，因其子孫也都小於T0 ，所以送出ZTR。以下以此類推。得： DP(1)=POS, NEG, IZ, ZTR, POS, ZTR, ZTR, ZTR,ZTR, IZ, ZTR, ZTR, ZTR, ZTR, ZTR, ZTR,ZTR, POS, ZTR, ZTR 另外解碼時，由於54介於32和64之間，54會被解碼48 (=(32+64)/2)。 -33會被解碼-48，以此類推可得以下結果：

6 另外POS、NEG、IZ和ZTR以上表來編碼， 則DP(1)可編碼成
第一階段後小波係數與對應的符號 圖9.7 四個符號的編碼 另外POS、NEG、IZ和ZTR以上表來編碼， 則DP(1)可編碼成 DP(1)= 圖9.4 第一階段後小波係數與對應的符號

7 第一修正回合結束後，我們得到RP(1) = 1000。
重要係數的修正(第一回合) 圖9.5 重建值的估計(第一回合) 由上圖，重要係數54，T0 < 54 <2T0 (= 64)，我們可用1.5×T0 = 48來當作54的分界點，利用布林符號1代表54介於48和64之間。係數-33為NEG，故真正的修正值為-40，如此一來，第一個修正回合可以結果如下：修正值是取區間的中間值。 圖9.6 重要係數的修正(第一回合) 第一修正回合結束後，我們得到RP(1) = 1000。

8 第二階段 第一階段結束後，我們只需將這四個係數編碼後的差額放回對應位置即可。下圖為第二階段開始前輸入的小波係數矩陣。圖中打三角形的四個小波係數值為待進一步修正的係數值。 圖 9.8 第二階段前輸入係數矩陣

9 經第二回合的支配回合及修正回合，可得到下表的結果。 輸出DP(2)=101101001111111111111111
第二階段後小波係數與對應的符號 門檻值：T1 = 0.5T0 = 16 經第二回合的支配回合及修正回合，可得到下表的結果。 輸出DP(2)= 圖9.9 第二階段後小波係數與對應的符號

10 利用以上重建值之估計區間。可得第二回合重要小波係數的布林代號如下。
重要係數的修正(第二回合) 圖9.10 重建值的估計(第二回合) 利用以上重建值之估計區間。可得第二回合重要小波係數的布林代號如下。 圖9.11 重要係數的修正(第二回合)

11 前一回合的重要係數再修正 第一回合的四個重要係數之修正值也需要更精確的被調整。以下為第二回合對第一回合的修正值之估計區間和原始重要係數對應的布林代號 。所以我們還需記錄0011以便修正前四個重要係數以得更精確的值。 圖9.12 重建值的估計(第二回合) 圖 9.13 重要係數的修正(第二回合) 在第三階段，共有前二回合的六個重要係數需被修正，也就是需用六個位元記錄。有了前面兩個階段的編碼過程，不難模擬出第三個階段的編碼和如何將編出來的碼予以解碼 。

12 9.3 二個改良式EZW法 SPIHT法 O(i, j)︰為位於(i, j)位置的小波係數之子孫 (Offsprings) 位置集。 D(i, j)︰為位於 (i, j) 位置的小波係數之所有子孫位置集。 H：為小波係數矩陣左上角係數所在和另外三個金字塔 (Pyramid) 的樹根所在。 L(i, j) = D(i, j)-O(i, j)。 SPIHT方法主要使用到三個串列︰LIP (List of Insignificant Pixels)、 LSP(List of Significant Pixels)和LIS (List of Insignificant Sets)。

13 SPIHT壓縮法實例說明 以上個EZW壓縮法使用的小波係數矩陣為例， LIP = H， LIS = H中有子孫者， LSP為空，三個List的初始狀態如下： LIP =〈(0,0), (1,0), (0,1), (1,1)〉=〈54, -33, -30, 22〉 LIS =〈A(1,0), A(0,1), A(1,1)〉 LSP =〈〉 以下一步一步的對三個List做輸出 LIP =〈(1, 0),(0, 1),(1, 1)〉=〈-33, -30, 22〉 LIS = 〈A(1, 0), A(0,1), A(1, 1)〉 LSP = 〈(0, 0)〉 輸出 = 10 LIP = 〈(0, 1), (1, 1)〉=〈-30, 22〉 LIS = 〈A(1, 0), A(0, 1), A(1, 1)〉 LSP = 〈(0, 0), (1, 0)〉 輸出 = 1011

14 LIP =〈(0, 1), (1, 1)〉=〈22〉 LIS =〈A(1, 0), A(0, 1), A(1, 1)〉 LSP =〈(0, 0), (1, 0)〉 輸出 = 10110 LIP =〈(0, 1), (1, 1)〉 輸出 = LIP=〈(0, 1), (1, 1), (2, 0), (3, 0), (1, 2), (3, 1)〉 LIS=〈A(0, 1), A(1, 1)〉 LSP=〈(0, 0), (1, 0)〉 輸出 = 模擬到此，以下類推，另外SPIHT法的重建值修正法和EZW法類似。

15 9.3.2 連結係數法 小波係數矩陣最下層的樹葉所對應的4×4係數矩陣經過一量化過程，可能造成許多量化後的係數變成零的情形。絕對值大過零的係數可視為重要係數，這些量化後的重要係數往往以叢聚的形式呈現 。我們可以只記錄叢聚的起始位置和用字串記錄該叢聚。 假設小波係數矩陣的樹葉層，每個小波係數皆除以8做量化，這裡的量化計算一律將所得的商之小數去掉，得下圖左的結果。可看出第一列的四個係數為重要係數，其黑白圖表示法為下圖右。 圖9.14 除以8後的量化結果 圖9.15 圖9.14的黑白圖表示法

16 接下來，以 (1, 0) 為中心，用同樣的掃描方式，我們又輸出10。 再來以 (2, 0) 為中心，我們又輸出10。
連結係數法實例說明 從 (0, 0) 位置的黑色點開始進行編碼。首先拿一3×3的視窗並將視窗的中心和 (0, 0) 的黑色點貼齊。這時輸出 (0, 0)，然後先查看東方並以順時針方向掃描 (0, 0) 的四個鄰居。接著輸出10。 接下來，以 (1, 0) 為中心，用同樣的掃描方式，我們又輸出10。 再來以 (2, 0) 為中心，我們又輸出10。 最後，以 (3, 0) 為中心，我們又輸出0。 總結起來，可得到 (0, 0) 的輸出。除了考慮視窗中心的四個方位外，也可用別種的方位考量。例如，八方位。有了對應的結構化元素視窗，屆時可用型態學 (Morphology) 中的擴張 (Dilation) 算子來完成。 圖9.16 八方位的結構化元素視窗

17 另外一很重要的觀念︰重要連結 (Significance-Link)。下圖為一個重要連結的例子，父親為重要係數，而在孩子中至少有一個小波係數為重要係數。這裡的父親與孩子的空間關係和EZW是一樣的。
圖9.17 重要連結示意圖 前面介紹的同一頻帶內的重要係數連結所帶來的節省記憶體效能和二個重要係數的連結所帶來的節省記憶體效能是一樣的，只是後者連結的是不同頻帶。由於在EZW中，符號ZTR出現的頻率頗高的，二個重要係數的連結法確實可有效省去儲存眾多ZTR所花的記憶體。

18 9.4 局部區域壓縮法 首先將有興趣的部份圍起來，這個圍起的的部份稱為ROI (Region-of-Interest)，下圖為一個4×4ROI的例子。 圖9.18 一個4×4的ROI例子

19 在上圖中，ROI為一正方形；利用一階的9/7濾波器進行小波轉換小波轉換後，原先的ROI由於小波轉換在運算時的空間相依關係會如下所示：

20 我們在SPIHT法的基礎上導入ROI的觀念於其中。假設三階小波轉換後的係數矩陣當中： R1代表重要係數且受到ROI的影響。
局部區域壓縮法實例說明 我們在SPIHT法的基礎上導入ROI的觀念於其中。假設三階小波轉換後的係數矩陣當中： R1代表重要係數且受到ROI的影響。 R0代表不重要的係數且受到ROI的影響。 NR表示不受到ROI影響的部分。 以一個空間方向樹為例(右下圖)，一步一步的模擬如下： LIP =〈(1, 0)〉 LIS =〈A(1, 0)〉 LSP =〈〉 輸出 =〈〉 LIP =〈〉 LSP =〈(1, 0)〉 輸出 = 10 圖9.21 一個在空間方向樹上的ROI 表示圖

21 LIP =〈(3, 0), (3, 1)〉 LIS =〈B(1, 0)〉 LSP =〈(1, 0), (2, 0), (2, 1)〉 輸出 = LIP =〈(3, 0),(3, 1)〉 LIS =〈A(2, 0), A(3, 0), A(2, 1), A(3, 1)〉 輸出 = 以下類推。這裡介紹植基於ROI之改良式SPIHT不失為一種漸進式傳輸的好方法。

22 9.5 EBCOT法 EBCOT同時具備的兩個好性質：
品質縮放(Quality Scalability)：再一植入式的二元流(Embedded Bitstream)中，若我們對各個層(Layer)進行截去(Truncate)的動作， 則對任一層而言，其解析度在不變的情況下具備有品質縮放的功 能。 解析度縮放(Resolution Scalability)：在植入式的二元流中，對單層 而言，若進行同程度的截去動作，具有解析度縮放的功能。 在EBCOT中，首先我們將輸入的影像分割成許多區塊，像地板上的磁磚(Tile)。接著EBCOT對每一區塊磁塊進行多階的小波轉換。針對每一個頻帶，將其分割成許多區塊(Block)。EBCOT法就是以區塊為基本單位進行壓縮的動作。

23 EBCOT分割示意圖 右圖為EBCOT的分割示意圖，在流程圖的最後兩步，假設區塊 i已經完成二階小波轉換而得七個頻帶，則任一頻帶的大小是可除盡一個區塊的大小的。以右圖為例，在LL頻帶上共切出16個區塊。 完成區塊化後，每一個區塊再分解成若干個位元平面(Bit-plane)。以每一區塊上的最大係數，經取log後來決定位元平面的個數。將該區塊轉換為多個位元平面後，EBCOT接著利用可調式算數法技術結合文件鄰屬(Context-based)的方式，將各區塊予以編碼。 圖9.24 EBCOT的分割示意圖

24 EBCOT法的位元平面 首先得先決定一個位元平面的掃描次序，這裡假設每一個區塊上的係數之正負號已儲存於符號位元平面(Sign Bit-plane)上，下圖為符號位元平面和其他位元平面的示意圖，為簡化起見，這裡假設有八個位元平面。 圖9.25 分割區塊為多位元平面

25 EBCOT的五種文件類型和對應的十六進位之值
UNIFORM的文件欄編號為十六進位的 12，這相當於十進位的18。 RLC為Run-length Coding的縮寫，代表 該行程為四個0。 ZC為Zero Coding的縮寫，代表打算編 的更下層之位元可能為重要位元，其文 件鄰屬編號的種類共有九種。 SC(Sign Coding)用以註明重要係數的正 負號，其文件欄編號有五種類型 。 MR (Magnitude Refinement)其三種編號列表於下，欄位C的1代表量 精鍊關被引用過；欄位H+V中的X代表Don’t Care。 圖9.27 文件類型與編號 圖9.31 MR的三種文件欄位編號

26 符號H(V)代表目前係數C的水平(垂直)重要係數的個數，而符號D代表四個斜角的重要係數的個數。
ZC的文件類屬的九種編號 (b) 鄰屬定義 (a) 九種編號種類 圖9.28 ZC的文件鄰屬的九種編號 符號H(V)代表目前係數C的水平(垂直)重要係數的個數，而符號D代表四個斜角的重要係數的個數。

27 SC的五種文件欄編號 圖9.29 SC的五種文件欄編號 上圖中的H和V之1代表至少一個正係數0代表有兩個不重要係數或兩個重要係數但正負號相反；-1代表至少有一個負係數。屆時到底所編碼的係數之正負號如何？由所編的SC值和對應的XOR相位之位元進行XOR而得，0代表正而1代表負。

28 第一個行程(Run-length)讀入的位元字串為 0000，所以符號欄記為0，文件欄記為00。 第二行程讀入位元字串仍為0000，所以符
EBCOT壓縮法實例說明 在EBCOT法當中，分重要係數傳遞關(Significance Propagation Pass)、 量精練關(Magnitude Refinement Pass)和掃除關(Cleanup Pass)，位元平面1只用到掃除關。 在右下圖中的8×8二元矩陣中 ，我們將其一分為二；上半部為矩陣的前四列，而下半部則為矩陣的後四列 ，先處理上半部的四列，依行為主(Column-major)的原則，由左掃描到右。 第一個行程(Run-length)讀入的位元字串為 0000，所以符號欄記為0，文件欄記為00。 第二行程讀入位元字串仍為0000，所以符 號欄位仍記為0，而文件欄仍記為00。 第三個行程讀入的位元字串且代表重要位 元為0010，這個字串中，位元1位於第三個 位置，所以符號欄記為01，而文件欄記為 十六進位的12。 圖9.26 位元平面1

29 位元平面1上半部編碼完的結果 圖9.30 圖9.26的上半位元平面編碼結果

30 第二回合重要係數傳遞關的編碼結果 給位元平面2表示如下圖左，用粗體小正方形框住的兩個地方代表其原在位元平面處為重要係數所在。和位元平面1一樣，我們仍然以上半位元平面為主。首先進行重要係數傳遞關，在這一關只會使用到ZC和SC的文件類型。下圖右為執行完重要係數傳遞關後的編碼結果。 圖9.32 位元平面2 圖9.33 圖9.32的上半位元平面第一關編碼結果

31 繼續上半位元平面2的量精鍊關和掃除關編碼之模擬。下圖灰色區域表示待處理的區域。右圖為編碼後的結果。
第二回合量精練關和掃除關的編碼結果 繼續上半位元平面2的量精鍊關和掃除關編碼之模擬。下圖灰色區域表示待處理的區域。右圖為編碼後的結果。 圖9.34 位元平面2的上半區域之待編碼部份 圖9.35 圖9.34待編碼部份的編碼結果

32 壓縮比和失真之間的最佳化 假設所有相關的區塊皆以編碼完成。令 , , , ，為第k個區塊中的第 i 個位元平面之第 j 關編號碼位元串。對任一個區塊之編碼位元串，在EBCOT方法中，我們可選在 後以為切點。令 的長度為length(i, j, k) 。 假如要達到某個壓縮比，則編碼後的位元串長度可設為T，則下式需被滿足 如何決定每個區塊的最佳切點的問題，在EBCOT方法中，等於是在壓縮比和失真之間取得最佳化的問題，也就是解出λ使得 為最小。

33 9.7 作業 習題一： 試說明JPEG和EZW中的壓縮精神之不同處。 習題二：
在EBCOT方法中，對位元平面的編碼和EZW方法中的何者是 具備類似功能的？試敘述之。