Using Set Partition in Hierarchical Tree in the EZW Algorithm

Using Set Partition in Hierarchical Tree in the EZW Algorithm

ECE 533

Digital Image Processing

Fall 2004

Yeon Hyang Kim

William L’Huillier

Introduction:

The embedded zerotree wavelet (EZW) coding was first introduced by J.M Shapiro and has since become a much studied topic in image coding. The EZW coding technique is a fairly simple and efficient technique for compressing the information in an image. Our focus in this project is to analyze the Set Partition in Hierarchical Tree algorithm in the EZW technique and to obtain observations by implementing the structure and testing it.

In order to compress a binary file, some prior information must be known about the properties and structure of the file in order to exploit the abnormalities and assume the consistencies. The information that we know about the image file that is produced from wavelet transformation is that it can be represented in a binary tree format with the root of the tree having a much larger probably of containing a greater pixel magnitude level than that of the branches of the root. The algorithm that takes advantage of this information is the Set Partition in Hierarchical Tree (SPHT) algorithm.

This project has been preformed previously but has produced an inefficient explanation of the implementation of the algorithm and some of its difficulties. In this project, we hope to be able to identify the problems and give more insight to the development and implementation of this algorithm than in previous projects.

Approach:

Matlab offers a set of wavelet tools to be able to produce an image with the needed properties. The concept of wavelet transformation was not our focus in this project but in order to understand how the SPHT algorithm works, the properties of wavelet transformation would need to be identified. Matlab was able to create adequate testing pictures for this project.

To adequately comprehend the advantages of the SPHT algorithm, a top level understanding will be needed to identify its characteristics and differences from other algorithms.

Set Partitioning Algorithm:

The SPHT algorithm is unique in that it does not directly transmit the contents of the sets, the pixel values, or the pixel coordinates. What it does transmit is the decisions made in each step of the progression of the trees that define the structure of the image. Because only decisions are being transmitted, the pixel value is defined by what points the decisions are made and their outcomes, while the coordinates of the pixels are defined by which tree and what part of that tree the decision is being made on. The advantage to this is that the decoder can have an identical algorithm to be able to identify with each of the decisions and create identical sets along with the encoder.

The part of the SPHT that designates the pixel values is the comparison of each pixel value to 2n≤ | ci,j | < 2n+1 with each pass of the algorithm having a decreasing value of n. In this way, the decoding algorithm will not need be passed the pixel values of the sets but can get that bit value from a single value of n per bit depth level. This is also the way in which the magnitude of the compression can be controlled. By having an adequate number for n, there will be many loops of information being passed but the error will be small, and likewise if n is small, the more variation in pixel value will be tolerated for a given final pixel value. A pixel value that is 2n≤ | ci,j | is said to be significant for that pass.

By sorting through the pixel values, certain coordinates can be tagged at “significant” or “insignificant” and then set into partitions of sets. The trouble with traversing through all pixel values multiple times to decide on the contents of each set is an idea that is inefficient and would take a large amount of time. Therefore the SPHT algorithm is able to make judgments by simulating a tree sort and by being able to only traverse into the tree as much as needed on each pass. This works exceptionally well because the wavelet transform produces an image with properties that this algorithm can take advantage of. This “tree” can be defined as having the root at the very upper left most pixel values and extending down into the image with each node having four (2 x 2 pixel group) offspring nodes (see figure 1.0)

Figure 1.0

The wavelet transformed image has the desired property that the offspring of a node will have a smaller pixel magnitude value than the parent node. By exploiting this concept, the SPHT algorithm will not have to progress through all the pixels in a given pass if it need not go past a certain node in the tree. This means that the combined lists do not need to contain all the coordinates of every pixel, just those that will show the adequate comparison information.

Unfortunately, using tree traversal algorithms would slow down the performance of the system and create unnecessary complex data structures. Instead of tree traversal, the SPHT algorithm uses sets of points to be able to hold the minimal amount of values and still make comparisons to other lists instead of many bulky tree structures.

The following sets can represent the corresponding tree representations:

Ō(i,j) is the set of coordinates of all offspring of node (i,j)

Đ(i,j) is the set of all coordinates that are descendants (all nodes that are below) of the node (i,j)

Ł(i,j) is the set of all coordinates that are descendants but not offspring of node (i,j)

The following are the lists that will be used to keep track of important pixels:

LIS: List of Insignificant Sets, this list is one that shows us that we are saving work by not accounting for all coordinates but just the relative ones.

LIP: List of Insignificant Pixels, this list keeps track of pixels to be evaluated

LSP: List of significant Pixels, this list keeps track of pixels already evaluated and need not be evaluated again.

A general procedure for the code is as follows:

1. Initialization: output n, n can be chosen by user or pre defined for maximum efficiency, LSP is empty, add starting root coordinates to LIP and LIS.

2. Sorting pass: (new n value)

a. for entries in LIP: (stop if the rest are all going to be insignificant)

- decide if it is significant and output the decision result

- if it is significant, move the coordinate to LSP and output sign of the coordinate

b. for entries in LIS: (stop if the rest are all going to be insignificant)

IF THE ENTRY IN LIS REPRESENTS Đ(i,j) (every thing below node on tree)

- decide if there will be any more significant pixels further down the tree and output the decision result

- if it is significant, decide if all of its four children (Ō(i,j)) are significant and output decision results

*if significant, add it to LSP, and output sign

*if insignificant, add it to LIP

IF THE ENTRY IN LIS REPRESENTS Ł(i,j) (not children but all others)

- decide if there will be any more significant pixels in Ł(i,j)further down the tree and output the decision result

- if there will be one, add each child to LIS of type Đ(i,j) and remove it from LIS

3. RefinementPass: (all values in LSP are now 2n ≤ | ci,j |)

a. For all pixels in LSP, output the nth most significant bit

4. Quantization-step Update: decrement n by 1 and do another pass at step 2.

The details and complexity of this procedure were left out in order to better explain the idea and to highlight the reasons for its efficiency. These details are explained below in a way that shows the drawbacks of the algorithm.

Work Performed:

Matlab was our primary tool for image testing and algorithm implementation. By using the wavelet commands, the transformation of our images could be composed and presented to the encoding algorithms for the bit stream.

The SPHT algorithm would need an adequate image sample to perform the encoding on so both images were used to explore the properties of the SPHT algorithm.

Having the SPHT algorithm encoded into matlab meant that matrix data structures, recursive algorithms, and a bit stream would be needed. The algorithm was encoded using multiple loops to be able to scan through all the pixel value and be able to evaluate the significance of each. At the same time, the sets would need to be repetitively access to be able to continually update the composition of each.

Many complications introduced themselves during the coding of this algorithm. One of these challenges include the talk of being able to let the traversal of each tree freely but still be able to realize when the bounds of the tree occur. This was difficult because of introduction of checks and bounds cause the operations on the tree to be slow and limited.

Another challenge was that of keeping track and managing all the lists to be in agreement with each other. The rules of moving or adding coordinates to list could be less strict in order to increase speed and decrease redundancy.

Another obstacle was the special operation that was required with the first pixels in each tree. These pixels would correspond to the upper left hand corner of the wavelet transformed image witch contains the highest valued pixels and can not be translated into any other pixel groups down the tree. Special operations were needed to be able to encode these values into the bit stream without using the original algorithm for this “exception” pixel.

Being able to develop the decoder was relatively easy after developing the encoder. By having the composition of the list is identical during each pass of the encoder and the decoder, much of the similar code could be used. There were obstacles that needed to be overcome such as the first pixel in the image being the “exception” pixel and needed to be encoded differently than the rest of the image. Values such as the size of the image also needed to be encoded so as to pass on that information to the decoder. The value of the number of significance levels would not necessarily have to be passed because the decoding algorithm could increase the value of all pixels every time the algorithm had another main loop causing the last increment to all the pixels to be that which would bring the largest pixel value back up to its represented value. We found that doing this would slow down the algorithm and cause too much complexity than using a longer bit stream to encode the number of significance level. The decoding algorithm would also use up more memory than the encoding algorithm because it would need to store values in a ghost image before it was able to retrieve the values that that ghost image would need to be applied to. An example of this would be that the values corresponding to pixel sign would have to be saved as a ghost image while the original image was being constructed. Only after evaluating all the magnitude levels of each pixel could the ghost (sign value) image is applied because if applied to early, pixel values not set (value of 0) would be unchanged.

The end product of the matlab code was a very direct function that could be easily modified and suited to our experimentation. While the algorithm ran relatively slow in matlab, it was able to produce the important data that we needed to evaluate the SPHT algorithm.

Results:

Image 1.1 describes the properties of the Haar (=db1) wavelet compressions and their observations of decomposition and reconstruction using low-pass filter and high-pass filter.

Image 1.1

The original images (image 1.2) were 256x256x8 = 524288 pixels

Image 1.2

We applied the decomposition filter to the images with 3 levels (Image 1.3)

Image 1.3

The uncompressed file length was obtained using the spiht command:
outkim 1x302863 302863 uint8 array
outwill 1x284329 284329 uint8 array
It was found that the outfile length was dependent on the coefficients.
The command, spiht.m was used to be able to obtain a level 3 transformation:
outkim=spiht(ckim,3,0);
outwill=spiht(cwill,3,0);
In the spiht command, the parameter 3 means level 3 and 0 means threshold level = 0

Threshold Level 4

A compression at level 4 will produce:
outkim=spiht(ckim,3,4);
outwill=spiht(cwill,3,4);
outkim1 1x69282 69282 uint8 array
outwill1 1x61907 61907 uint8 array
The compression rates are represented as:
ratekim = 69282 /302863
ratekim = 0.2288
ratewill = 61907/284329

ratewill =0.2177
Image 1.4 shows the reconstruction from this compression

Image 1.4

Note that these compression preserves the L_norm;
norm(kim(:)-kimb1(:),2) = 1.0488e+03
norm(ckim(:)-dekim1(:),2) = 1.0655e+03
norm(will(:)-willb1(:),2) = 853.5350
norm(cwill(:)-dewill1(:),2) = 869.9989
where the kimb1 and willb1 are the reconstructions from the threshold level 4. The variables in the equations are:

ckim and cwill are the coefficients of kim and will
dekim1 and dewill1 are the reconstructed coefficients from the threshold level4

The image produced from this was very accurate and usable. Some pixilation was observed but the compression size benefit showed this to be a good tradeoff.

Threshold Level 6

The same procedure was repeated only with threshold level 10.
ratekim = 38862 /302863
ratekim = 0.1283
ratewill = 37872/284329
ratewill = 0.1332

The 2 norm was used on the images to compare the results and produced values of 2.5048e+03 for Kim’s image and 2.1066e+03 for William’s image. The L_norm produced values of 2.5161e+03 for Kim’s image and 2.1172e+03 for William’s image.

The images produced shows to be more pixilated than the threshold level 4. The images are the same size though.

Threshold Level 10

The same procedure was repeated only threshold level 10.

The compression rates that were produced are as follows:
ratewill = 7664/284329
ratewill = 0.0270
ratekim = 7608 /302863
ratekim =0.0251

The 2 norm was used on the images to compare the results and produced values of 1.7545e+04 for Kim’s image and 1.5034e+04 for William’s image. The L_norm produced values of 1.7548e+04 for Kim’s image and 1.5038e+04for William’s image.

The images produced show much pixilation but have the same appearance and shape. This threshold level would be inadequate for conventional use.

Discussion:

The data that we found during our experiments shows that this algorithm is well calibrated to match with the wavelet transformation algorithm. Even though the code that was used in the experimentation was straight forward and mildly complex, the SPHT algorithm can have many optimizations done to it to become a faster and more efficient algorithm for encoding. Fortunately our data shows that by combining the correct assumption of information with an algorithm that will use those assumptions can produce a very powerful tool that can be used in real life.

It was also found that the compression was very dependent on the pictures structures and image properties. This is yet one more way to improve the SPHT algorithm by optimizing the wavelets chosen to produce a picture of certain quality in order for the SPHT algorithm to perform at an optimal rate.

Tasks performed by each person:

Project: Using Set Partition in Hierarchical Tree in the EZW

Algorithm

Partners: Yeon Hyang Kim and William L’Huillier

Project due date: 12/17/2004

Process / Yeon Hyang Kim / William L’Huillier
Abstract / 25% / 75%
Project Proposal / 25% / 75%
Implementation of matlab tools / 75% / 25%
Experimentation and data / 75% / 25%
Research / 50% / 50%
Synthesis of ideas (meetings, brainstorming) / 50% / 50%
Report Write up / 25% / 75%
Power point presentation / 25% / 75%
Overall Project Total / 50% / 50%

This page must be signed by both project partners:

1