RMF Based EZW Algorithm School of Computer Science University of Central Florida VLSI and M 5 Research Group June 1 2000 Organization The EZW algorithm A brief introduction of RMF 1 D RMF example 2 D RMF example The RMF based EZW algorithm Basic concept Introduction of the algorithm An example Basic Idea Band max construction algorithm An example Experimental results Conclusions EZW basic concepts 1 E The EZW encoder is based on progressive encoding Progressive encoding is also known as embedded encoding Z A data structure called zero tree is used in EZW algorithm to encode the data W The EZW encoder is specially designed to use with wavelet transform It was originally designed to operate on images 2 D signals EZW basic concepts 2 Lower octave has higher resolution and contains higher frequency information A Multi resolution Analysis Example EZW basic concepts 3 The EZW algorithm is based on two observations Natural images in general have a 631 544 86 10 7 29 55 low pass spectrum When an image is wavelet transformed the 54 730 655 13 30 12 44 41 energy in the sub bands decreases 32 with the scale goes lower low 19 23 37 17 4 13 13 39 scale means high resolution so 25 49 32 4 9 23 17 the wavelet coefficient will on 35 average be smaller in the lower 32 10 56 22 7 25 40 levels than in the higher levels 10 typical wavelet coefficients 6 44 block 4 13 in 12a real 21 for34a 8 8 Large wavelet coefficients are 24 image more important than small 12 2 8 24 42 9 21 45 wavelet coefficients 13 3 16 15 31 11 10 17 EZW basic concepts 4 The observations give rise to the basic progressive coding idea 1 2 3 We can set a threshold T if the wavelet coefficient is larger than T then encode it as 1 otherwise we code it as 0 1 will be reconstructed as T or a number larger than T and 0 will be reconstructed as 0 We then decrease T to a lower value repeat 1 and 2 So we get finer and finer reconstructed data The actual implementation of EZA algorithm should consider 1 What should we do to the sign of the coefficients positive or negative answer use POS and NEG 2 Can we code the 0 s more efficiently answer zero tree 3 How to decide the threshold T and how to reconstruct answer see the algorithm EZW basic concepts 5 coefficients that are in the same spatial location consist of a quadtree EZW basic concepts 6 The definition of the zero tree There are coefficients in different subbands that represent the same spatial location in the image and this spatial relation can be depicted by a quad tree except for the root node at top left corner representing the DC coeeficient which only has three children nodes Zero tree Hypothesis If a wavelet coefficient c at a coarse scale is insignificant with respect to a given threshold T i e c T then all wavelet coefficients of the same orientation at finer scales are also likely to be insignificant with respect to T EZW the algorithm 1 First step The DWT of the entire 2 D image will be computed by FWT Second step Progressively EZW encodes the coefficients by decreasing the threshold Third step Arithmetic coding is used to entropy code the symbols EZW the algorithm 2 What is inside the second step threshold initial threshold do dominant pass image subordinate pass image threshold threshold 2 while threshold minimum threshold The main loop ends when the threshold reaches a minimum value which could be specified to control the encoding performance a 0 minimum value gives the lossless reconstruction of the image The initial threshold t0 is decided as Here MAX means the maximum coefficient value in the image and y x y denotes the coefficient With this threshold we enter the main coding loop EZW the algorithm 3 In the dominant pass All the coefficients are scanned in a special order If the coefficient is a zero tree root it will be encoded as ZTR All its descendants don t need to be encoded they will be reconstructed as zero at this threshold level If the coefficient itself is insignificant but one of its descendants is significant it is encoded as IZ isolated zero If the coefficient is significant then it is encoded as POS positive or NEG negative depends on its sign This encoding of the zero tree produces significant compression because gray level images resulting from natural sources typically result in DWTs with many ZTR symbols Each ZTR indicates that no more bits are needed for encoding the descendants of the corresponding coefficient EZW the algorithm 5 At the end of dominant pass all the coefficients that are in absolute value larger than the current threshold are extracted and placed without their sign on the subordinate list and their positions in the image are filled with zeroes This will prevent them from being coded again In the subordinate pass All the values in the subordinate list are refined this gives rise to some juggling with uncertainty intervals and it outputs next most significant bit of all the coefficients in the subordinate list EZW An example 1 Wavelet coefficients for a 8 8 block EZW An example 2 The initial threshold is 32 and the result from the dominant pass is shown in the figure 63 POS 34 NEG 49 POS 10 ZTR 7 IZ 13 IZ 12 7 31 IZ 23 ZTR 14 ZTR 13 ZTR 3 IZ 4 IZ 6 1 15 ZTR 14 IZ 3 12 5 7 3 9 9 ZTR 7 ZTR 14 8 4 2 3 2 5 9 1 IZ 47 POS 4 6 2 2 3 0 3 IZ 2 IZ 3 2 0 4 2 3 6 4 3 6 3 6 5 11 5 6 0 3 4 4 Data without any symbol is a node in the zero tree EZW An example 3 The result from the dominant pass is output as the following POS NEG IZ ZTR POS ZTR ZTR ZTR ZTR IZ ZTR ZTR IZ IZ IZ IZ IZ POS IZ IZ POS 01 NEG 11 ZTR 00 IZ 10 The significant coefficients are put in a subordinate list and are refined A one bit symbol is output to the decoder Original data 63 34 49 47 Output symbol 1 0 1 0 Reconstructed data 56 40 56 40 For example the output for 63 is sign 32 16 8 4 2 1 0 1 1 If T 5T is less than data item take the average of 2T and 1 5T So 63 will be reconstructed as the average of 48 and 64 which is 56 If it is more put a 0 in the code and encode this as t 5T 25T Thus 34 is reconstructed as 40 EZW An example 4 10 7 13 12 7 31 23 14 13 3 4 6 1 15 14 3 12 5 7 3 9 9 7 14 8 4 …