嵌入式零樹小波
 |
嵌入式零樹小波 Embedded Zerotrees of Wavelet transforms (EZW)是一種有損的影像壓縮演算法。在高壓縮率的情況下，大部分次頻帶轉換(如小波轉換)所產生的的系數都會是0，或是非常接近0。這背後的原因是在於真實世界的影像大部分集中在低頻的成分。然而，也確實會有一些高頻成分，例如影像中邊緣的部分。人眼的感知對於這些高頻成分特別的敏感，因此在高清的影像壓縮編碼中，這些資訊需要被妥當地重建並呈現在解壓縮後的影像中。
演算法一開始先把最低頻的系數當作樹狀架構的根節點，每一個節點的子代為其更高層相對應次帶位置的系數。由於每個節點都會有其各自延伸的子代，因此又可以稱這些節點為子樹。由於大部分的資訊被集中在低頻，因此越往高頻成分走系數的值越容易會是0。如果一個子樹的系數的值全部都是0(或者是低於某個門檻值)，那麼我們就會稱此子樹為零樹。基於這個原因，在後文中節點和系數會被交錯使用，且當提及一個系數的子代時，意指的是該子代所相對應位置的系數值。一個節點的子代意指的是該節點下一層相對應的系數，一個節點的後代指的則是一個節點往後的所有衍生的節點，意即包括其子代的子代，即便與該節點並無直接連結。
基於零樹演算法的壓縮演算法(如EZW和SPIHT)的目的是在於說希望能夠利用每個次帶間的統計特性來更有效的對重要的系數進行編碼。由於大部分的系數會是近於0的值，我們會花上大部分的位元在表示那些重要的系數值。一個系數的重要性(significance)是由其值的大小是否超過一個門檻值做決定。在編碼程序的一開始我們可以先將門檻值定為相當接近整張圖片最大的系數值，往後在每個編碼的循環中逐步降低該門檻值，如此產生一個漸進式的表示方式。基於次帶轉換的特性，如果一個系數在其本身的次帶為不重要的，那麼其後代皆為0的可能性也會相當的大。
EZW有一些重要的特性：第一，這個演算法可以停在編碼程序中的任何一點，並產生一個合適的重建影像。因此可以想成是，我們是透過更多的位元數去逐步精煉輸出的重建影像；第二，其演算法基本上是透過相當多的漸進式決策手續，因此可以使用算術編碼來更進一步的提高它的壓縮效率。然而，即便沒有使用算術編碼，它的編碼程序所產生的符號值其實已經相當接近隨機分佈了，因此通常加上熵編碼(如算術編碼)的幫助也會有限。
EZW目前已經有很多衍生的演算法，諸如SPIHT等等，都可以達到比它更好的壓縮效能。
演算法介紹
[編輯]嵌入式零樹小波(EZW) 為J. Shapiro在1993年提出，為一種可擴展性的影像壓縮編碼方式。它主要是基於四個想法，第一點：該影像必須先經過小波轉換或其他次帶轉換產生階層式的架構；第二點：在缺乏一些重要資訊的情況下，該演算法要能夠透過影像本身的局部相似性做一些預測；第三點：透過漸進式的量化熵編碼；第四點，它必須要能夠透過算術編碼達到無損壓縮。
此外，EZW演算法還包含了以下幾個特色：
(1) 透過小波轉換可以產生多解像度版本的影像呈現
(2) 零樹的編碼架構提供了一種多解像度影像的緊緻(compact)表示方式
(3) 可以對重要的系數(significant coefficients)做漸進式的估計
(4) 處理系數的優先順序由其準確度、大小、空間上的相對位置來依序決定
(5) 漸進式層級架構的算術編碼為一種相當有效率又同時表現相當優異的編碼方式
嵌入式零樹小波編碼
[編輯]A. 對重要性數組的系數進行編碼
[編輯]在重要性數組當中，一個系數可以被後述四種符號所代表。透過這些符號我們可以減少壓縮一張影像整體的複雜度。
1. 零樹的根
[編輯]如果一個系數的數值比一個門檻值T還小，以及它的所有子代都比T還小，那麼這個系數就會被作為零樹的根。如果一個系數被標示為零樹的根了，代表說他所有的子代都沒有重要性了，也就沒有必要去標示他的子代了。
2. 分離的零
[編輯]如果一個系數的值比T還小，但是他的子代還有比T還大的，那麼這個系數就會被稱為分離的零。
3. 重要的正系數
[編輯]如果一個系數的值比T還大，而且又是正值，那麼這個系數就會被稱為重要的正系數。
4. 重要的負系數
[編輯]如果一個系數的值比T還大，而且又是負值，那麼這個系數就會被稱為重要的負系數。
B. 定義門檻值
[編輯]門檻值的定義可以參考如下所述
1. 初始的門檻值 T0: (假設 Cmax 是最大的系數值。)
[編輯]
2. 門檻值Ti 被減少為先前的一半大小。
[編輯]
C. 系數的掃描順序
[編輯]逐行掃描是一般常見的影像捕捉和重建所使用的掃描方式。EZW之所以使用這種掃描方式是為了確保所有親節點都會在子節點之前被處理，以及低層的次帶會在高層次帶處理完之後才被處理。
D. 兩道位元平面編碼的程序
[編輯](1) 精煉程序(或稱 次要程序)
[編輯]判斷該系數是否介於[Ti, 2Ti)之間。且每一個系數經過精煉程序會吐出一個精煉位元。 在這個程序中，每一個重要的系數都會被掃過，掃描順序為同一個次帶中的逐行掃描。
(2) 重要性程序(或稱 優勢性程序)
[編輯]這個程序會判斷一個系數是否為重要，如果一個系數被判斷為重要的，在往後的編碼程序中，該系數就會經過精煉程序。反之，如果一個系數被判斷為不重要了，該系數就不會再出現在往後的編碼程序了。
參見
[編輯]- 層次樹集合分劃編碼 (SPIHT)
參考來源
[編輯]- Shapiro, J. M., . IEEE Transactions on Signal Processing, Vol. 41, No. 12 (1993), p. 3445-3462.
