Hybrid fractal zerotree wavelet image coding

Presentation on theme: "Hybrid fractal zerotree wavelet image coding"— Presentation transcript:

1 Hybrid fractal zerotree wavelet image coding
Source: Signal Processing: Image Communication 17, 2002, pp Author: Taekon Kim, Robert E. Van Dyck, David J. Miller Date: /04/10 Speaker: Guei-Mei Chen

2 Outline Introduction Embedded zerotree wavelet (EZW) image coding
Fractal image coding The proposed fractal zerotree wavelet (FZW) image coding Experimental results Conclusions

3 Introduction The proposed fractal zerotree wavelet (FZW) algorithm combines zerotree-based encoder, such as EZW coder, with a fractal (碎形) image coder for improving quality of the compressed image.

4 Embedded zerotree wavelet (EZW) (1/3)
The wavelet transform : A B C D E F G H I J K L M N O P A+B C+D E+F G+H I+J K+L M+N O+P A-B C-D E-F G-H I-J K-L M-N O-P 1th level horizontal here, we can do 2th level … (A+B)+(E+F) (C+D)+(G+H) (A-B)+(E-F) (C-D)+(G-H) (I+J)+(M+N) (K+L)+(O+P) (I-J)+(M-N) (K-L)+(O-P) 1th level vertical (A+B)-(E+F) (C+D)-(G+H) (A-B)-(E-F) (C-D)-(G-H) (I+J)-(M+N) (K+L)-(O+P) (I-J)-(M-N) (K-L)-(O-P)

5 Embedded zerotree wavelet (EZW) (2/3)
quadtrees in the wavelet domain : LL3 HL3 HL2 HL1 LH3 HH3 LH2 HH2 LH1 HH1 63 -34 49 10 7 13 -12 -31 23 14 -13 3 4 6 -1 15 5 -7 9 -9 -14 8 -2 2 -5 47 -3 -4 11 -31 15 14 -9 -7 6 -4 5

6 Embedded zerotree wavelet (EZW) (3/3)
We use thresholds (To, T1, T2 …) to filter significant coefficients. If there are insignificant coefficients in low frequency subbands in a tree, then the corresponding coefficients in the higher frequency subbands are also likely insignificant. These coefficients will be denote as “zero”.

7 Fractal (碎形) image coding (1/5)
日常生活中，很多事物均具有與本身某部份自我相似(self-similar)而重複之特性。例如蕨類植物，其每一小部份均與整個葉片具有相似性。事實上，自然界中許多特殊現象，均具備了自我相似之特徵，例如詭變的天氣，山脈的走向，人體內動靜脈循環分支的情形等等。這是碎形(fractal)重要特徵之一。大部份的碎形影像，不論放大近看，都沒有盡頭，好像在往無底洞鑽進去一樣。 Fisher在1996年提出一個例子來解釋碎形壓縮。假設有一台特製影印機能將輸入影像縮小一半並複製三份輸出，反覆使用此影印機，將輸出影像，當作輸入影像，經多次操作，我們可發現，不管最初輸入影像為何，最後得到的影像都會愈來愈相似，意即收歛至一張歸結影像。而且操作次數愈多，所得之影像越相似，不論起始影像是什麼。而決定歸結影像樣式者，為複製方向與位置。  Main idea: 只要用某個具收縮性 (contraction) 的轉換公式，就足夠代表最終影像，與起始之原始影像無關。

8 Fractal image coding (2/5)
Ex.

9 Fractal image coding (3/5)

10 Fractal image coding (4/5)
Domain tree & Range tree : a range tree is fractally encoded by a bigger domain tree. Ex. the contractive transformation (T) is given by , where D denotes domain tree, S is subsampling, O is the orientation operation, and αis the scaling factor. R denotes range tree. We search over all eight orientations and all domain trees to find the best-matching domain tree for a given range tree.

11 Fractal image coding (5/5)
Briefly, for a given range tree, the encoded parameters are the position of the domain tree, index of orientation, and the scaling factor.

12 The proposed FZW algorithm (1/3)
determine if the fractal coding will be used or not  Distortion-rate (D-R) curve

13 The proposed FZW algorithm (2/3)
Encoder Step 1. discrete wavelet transformation Step 2. trial-encoding: encode an image using an EZW coder at a given bit rate Step 3. trial-decoding: then determine the instantaneous slope value “D-R slope” Step 4. fractal range-domain search: find the best matching domain tree for each range tree Step 5. distortion-rate comparison: compute slope value “D-R fractal”, then fractal coding if adopted if Step 6. encoding: send side information for each range tree

14 The proposed FZW algorithm (3/3)
Decoder Step 1. read side information Step 2. EZW decoding Step 3. fractal decoding Step 4. iteration: repeat steps 2 and 3 until the EZW bit stream ends Step 5. inverse discrete wavelet transformation

15 Experimental results (1/3)

16 Experimental results (2/3)
Improve the quality of images:

17 Experimental results (3/3)
Reduce bit rate :

18 Conclusions The new algorithm reduces the bit rate required to achieve a given level of perceptual image quality. It also keeps desirable properties from both types of coders, including progressive transmission, the zerotree structure, and range-domain block decoding.