Copyright is owned by the Author of the thesis.  Permission is given for 
a copy to be downloaded by an individual for the purpose of research and 
private study only.  The thesis may not be reproduced elsewhere without 
the permission of the Author. 
 



A Fuzzy and Wavelet-Based Image Compression 

Algorithm 

A thesis presented in partial fulfillment 

of the requirements for the degree of 

Master 

In 

Computer Science 

At Massey University, Albany, 

New Zealand 

Li Huang 

2006 



Abstract 

Nowadays, the Internet and digital image widespread are used in the industry, 

commerce, military, traffic and all walks of life. However, this kind of general use 

resulted in required for less transmission time and storage space. Image compression 

can address the problem of reducing the amount of data to represent a digital image. 

The image will satisfy the transmission and the preserved request after the 

compression. With the increasing use some technologies in the image processing, 

image compression also requires new technology to get the high compression ratio 

and more better image quality. Therefore, a new standard has been developed by Joint 

Photographic Experts Group (JPEG). Apart from JPEG, there are other algorithms 

developed for image compression, Normally, EZW, SHIPT and VQ algorithms. 

However, they all deal with the calculation of coefficients with too much complexity; 

as a consequence, compressing still image takes too much time. In the light of these 

problems, this thesis introduces a new method for dealing with the requirements of the 

coefficients while retaining the important detail in the image, by employing a Fuzzy 

Logic technique reduce the number of the coefficients, and then utilizes the Huffman 

or LZW algorithm to complete the image compression. The algorithm developed in 

this research , called IWF algorithm, is based on four key techniques: I) a wavelet 

transform for decomposition. This technique allows the combination of lossless and 

lossy compression with extremely high compression rate and image quality. 2) 

Quantization, this technique generally works by compressing a range of value to a 

single quantum value. By reducing the number of discrete symbols in a given stream, 

the stream becomes more compressible. This step in the IWF process is a lossy 

transformation. 3) Adaptation of Fuzzy logic techniques. This step uses the Fuzzy 

Logic techniques to handle the wavelet coefficients, enable the wavelet coefficients to 

have the same value in the high subbands. 4) Adaptation of Lossless data compression 

techniques. 

Keywords: Image Compression, Fuzzy Logic, Wavelet transforms, Decomposition, 

Haar Wavelet transform, 



Acknowledgments 

I thank Reyes,Napoleon for his invaluable support and guidance as my 

supervisor. His readiness to give help and suggestions throughout the year 

has been highly appreciated. 

I would also like to thank my famjly for their support throughout this year. 

Massey University 

March 2006 

ii 

Li Huang 



ABSTRACT ................................................................................................ 1 

CHAPTER 1 ............................................................................................. 1 

INTRODUCTION ...................................... ..................... .... ....................... 1 

1.1 Overview of the Current State of Technology ............................... 1 
1.2 Research Objectives ............................. .... ...................................... 2 
1.3 Scope and Limitations of Research ................................................ 3 
1.4 Assumptions .. .. ......... ........ .............. ................................................ 3 
1.5 Significance of the Research ................. ...... .................................. .4 
1.6 Research Methodology ................................................................... 5 
1. 7 Organization of the Thesis ............................................................. 6 

CHAPTER 2 ............................................................................................... 7 

THEORETICAL FRAMEWORK ..... ... .... ........ .... ..................................... 7 

2.1 Basic Image Compression Concepts ... .... .......... ................................ 7 
2.1.1 linage Types .. .... ... .................................... .................. ..... ............ 7 
2.1.2 Colour Space ....... ... ..................................................................... 8 
2. I .3 Data Redundancy ...................................................................... 11 
2.1.4 Two Categories of Image Compress ion Technique ... .... ..... .. .. .. I 3 
2. I .5 Compression Ratio and Error Metrics ........... ........ .. ...... ........... 14 

2.2 Image Coding ...... .... ....................... .. ..... ... .. ....................... .. ... .. .. .. ... 15 
2.2. I Introduction ............................................................................... 15 
2.2.2 Run Length Encoding ... ........ .... .. ........ ...................................... 16 
2.2.3 Huffman Coding ............ ......... .... ........ ... ................... ...... .......... . 17 
2.2.4 LZW Coding .................................... ......... ................. ........ ....... . 22 
2.2.5 Huffman Algorithm Vs LZW Algorithm (Results) ................... 29 

2.3 Transform coding ............................................................................ 30 
2.3.1 Introduction ............................................................................... 30 
2.3.2 Discrete Cosine Transform ................................ .. .............. ........ 31 
2.3.3 Wavelet Transform .......... ........... ... .. ..... .. ................ .... ... .... ........ 33 

2.3.3.1 Haar Wavelet ................................. .... ... .. .... ... ...... ..... ........... 37 
2.3.3.2 Morlet Wavelet .................................................................... 38 
2.3.3.3 Marr Wavelet ............ .... ....... .. .............................................. 38 

2.3.4 Typical Image Compression Algorithms based on Wavelet 
Transform .................................................................... ....................... 39 

2.3.4.1 EZW Algorithm ........................... ........................................ 39 
2.3.4.2 SPIHT Algorithm ............................................................... .46 

2.4 Fuzzy Logic and Fuzzy Image Processing ..................................... .48 
2.4.1 What is Fuzzy Logic? ............................................................... .48 
2.4.2 What is Fuzzy Set Theory? ...................................................... .49 
2.4.3 Fuzzy Membership Functions ................................................... 50 
2.4.4 Applications of Fuzzy Techniques in Image Processing ........... 53 

2.4.4.1 Fuzzy Image Enhancement. ................................................ 53 

iii 



2.4.4.2 Fuzzy Image Segmentation ................................................. 54 
2.4.4.3 Fuzzy Edge Detection ......................................................... 55 

CHAPTER 3 ............................................................................................. 56 

REVIEW OF RELATED LITERATURE ................................................ 56 

3 .1 YCC Colour Space and Image Compression ..................... ........ ..... 56 
3.2 JPEG Compression Techniques ...................................................... 57 
3.3 JPEG 2000: The Next Compression Standard Using Wavelet 
Technology ........ ........................ .......... ........ .......... ....... ..... .................... 58 
3.4 Image Compression Techniques ...................................................... 59 
3.5 Image Compression Method of Vector Coding Based on Wavelet 
Transform .............................................................................................. 59 
3.6 Embedded Image Coding Using Zerotrees of Wavelet Coefficients 
............. ..... ................. ..................................................................... ...... . 60 
3.7 A Comparative Study on Digital Mamography Enhancement 
Algorithm Based on Fuzzy Theory .. .................... ........ .. ....................... 60 
3.8 An algorithm for Image Clustering and Compression .................... 61 
3.9 Image Coding Using Wavelet Transform ........................................ 61 
3.10 On Embedded Zerotree Wavelets Coding and other Improved 
Algorithms ................................. ... ................... .... ........... ....... .. ..... .. .. .. .. . 62 
3.11 Wavelet-based Image Compression ...... ................. ..... ....... ........... 62 
3 .12 EZW Encoding .............................................................................. 62 
3 .13 Colour Image Compression/Reconstruction by YUV Fuzzy 
Wavelets .................. ... ......... .. ..................... ... ................. ........ ... ... ... .... .. 62 

CHAPTER 4 ............................................................................................. 64 

THE IMAGE COMPRESSION ALGORITHM BASED ON WAVELET 
AND FUZZY LOGIC (IWF) ...................................................... ............. 64 

4.1 Central Thesis .................................................................................. 64 
4.2 General System Architecture ........ ... ..... ... ... .. ... ..... .... .. ... .. .. .............. 65 
4.3 Wavelet Transform (Haar Wavelet) ................................................. 65 
4.4 Fuzzification Function ..................................................................... 67 

4.4.1 Possibility Distribution algorithm .............. ............................... 68 
4.4.2 Contrast Improvement with Intensification Operator ............... 68 
4.4.3 Contrast Improvement with Fuzzy Histogram Hyperbolization 
............................................................................................................ 69 
4.4.4 Contrast Improvement based on Fuzzy If-Then Rules ............. 70 
4.4.5 Experiment Results ................................................................... 70 

4.5 IWF Algorithm ................................................................................ 71 
4.6 Sample Application of the IWF Algorithm ..................................... 74 
4.7 Grayscale Image Compression ........................................................ 76 

4.7.1 Introduction ........ ....................................................................... 76 
4.7.2 IWF Algorithm (grayscale image) ............................................ 76 

iv 



4.7.3 Experimental Result .................................................................. 77 
4. 7 .3 .1 Time and Compression Ratio Analysis ............................... 77 
4. 7 .3 .2 Image Compression Results ................................................ 81 

4.8 Colour Image Compression ............................................................. 85 
4.8.1 Introduction ............................................................................... 85 
4.8.2 IWF Algorithm (Colour Image) ................................................ 86 
4.8.3 Experimental Result .............. .......................... .. ........................ 88 
4.8.4 Comparison between the IWF Algorithm and Other Algorithms 
(based on Colour I mag es) .................................................................. 91 

CHAPTER 5 ...... ....................................................................................... 93 

CONCLUSIONS AND FUTURE WORKS ............................................ 93 

5 .1 Wavelet Image Compression ................................ ............ ............... 93 
5.2 Fuzzy Image Compression ....................................................... ....... 94 
5.3 Synopsis ... .................... .......................... .. .......................... .............. 95 
5.4 Research Papers Published ............................................... 96 
5.4 Suggestions for Future Work ........................................................... 96 

APPENDIX: ............................................................................................. 97 

REFERENCES: ...................................................................................... 108 

V 



List Figures 

Fig. l The Comparison of RGB, YUV, YIQ and YCrCb Colour Space ... 11 

Fig.2 Source Encoder and Decoder Model .............................................. 13 

Fig.3 Binary Tree Creations ..................................................................... 19 

Fig.4 Delphi Implementation of the Huffman Algorithm ....... ............ ..... 21 

Fig.5 Comparison the between Original Image and Reconstructed Image 

(Huffman algorithm) ....................... ... ............... .... ............. .... .. .... .... ... ..... 21 

Fig.6 Delphi Implementation the LZW Algorithm ........ .......................... 28 

Fig.7 Comparison the between Original Image and Reconstructed Image 

(LZW algorithm) .......................................... .... .... .... ... .. ...... .. .......... ... 29 

Fig.8 The Transform Coding System ... .......... .......................................... 30 

Fig.9 I-D DCT Basis Functions for N=8 ........................... ...................... 33 

Fig. IO Basis Function of an 8x8 OCT ...... ................ ............................... 33 

Fig. I I Wavelet Decomposition ................................................................ 35 

Fig. I2 Vertical and Horizontal Decomposition Image ............................. 35 

Fig.13 l to 3 Levels Wavelet Decomposition Image .. .. ..... .. ............ ....... . 36 

Fig.14 Haar Wavelet .. ..... .... .... .. .... ...... .... .................................................. 37 

Fig.15 Morlet Wavelet.. ..... ... ...... .... ............ .............................................. 38 

Fig.16 Marr Wavelet. ...................... ..................................... ... .................. 39 

Fig.17 Three Level Wavelet Decomposition ........................................... .40 

Fig.18 Flow Chart for Encoding a Coefficient.. ...................................... .42 

Fig.19 Two l(jnd of Scan Ordering ...................................... ... ................ .43 

Fig.20 Coefficients ....................... ....... ..................... ...... ...... ... ................. 44 

Fig.21 Representation of "dark gray-levels" with a Crisp and a Fuzzy Set 

............................................................................................................ 50 

Fig.22 The Triangular Membership Function .......................................... 51 

Fig.23 The Trapezoidal Membership Function .................. ...................... 51 

Fig.24 The Gaussian Membership Function ............................ ..... ........... 52 

Fig.25 The Generalized bell Membership Function ................................ 53 

vi 



Fig.26 The Main Principle of Fuzzy Image Enhancement ...................... 54 

Fig.27 Basic Idea of Compression Scheme .............................................. 56 

Fig.28 Block Diagram of JPEG Compression ......................................... 57 

Fig.29 Block Diagram of JPEG2000 Compression ................................. 59 

Fig.30 The Image Compression Process ...................... .. .......................... 59 

Fig.31 General Architecture of a Fuzzy and Wavelet-Based Image 

Compression ..................... ... ... .. ........ .. ...................... ... ......... .............. 65 

Fig.32 Results using different fuzzification functions .. . .................. . 71 

Fig.33 The Fuzzification Function ........................................................... 73 

Fig.34 8x8 Image Data ............................................................................. 74 

Fig.35 2-level Wavelet Decomposition ............... ................... .... .. .. .. ...... .. 74 

Fig.36 Coefficients after Mapping ........................................................... 75 

Fig.37 Coefficients after Fuzzification .......... .. ....... .................. ............... 75 

Fig.38 Original Image (lena.bmp 512 x 512) ...... .... ........... ... .. ..... ... ... .... . 77 

Fig.39 Relationship between the Time and the Level of Wavelet 

Decon1position ............................................ .. ........ ... ... ... ... ...... ........... 78 

Fig.40 Relationship between the Time and the Compress ion .................. 78 

Fig.41 Relationship between the Time and the Decompression .............. 79 

Fig.42 Relationship between the Time and the Reconstruction ............... 79 

Fig.43 Relationship between the Total Time and the Level of 

Decomposition ................................................................................... 80 

Fig.44 Relationship between the Compression Ratio and the Level of 

Decomposition ................................................................................... 80 

Fig.45 Test Images .................................................................................... 81 

Fig.46 Compressed Images (3-Level of Wavelet Decomposition) .......... 81 

Fig.4 7 Relationship between the Compression Ratio and the Level of 

Decomposition ............................................................... 82 

Fig.48 Original Test Image (lena.bmp 512 x 512) ................................... 82 

Fig.49 Compressed Image (I-Level Wavelet Decomposition, 

vii 



Compression Ration 3: 1) .................................................................... 83 

Fig.50 Compressed Image 

(2-Level Wavelet Decomposition, Compression Ration 6: 1) .................. 83 

Fig.51 Compressed Image 

(3-Level Wavelet Decomposition, Compression Ration 13:1) ................ 84 

Fig.52 Compressed Image 

(5-Level Wavelet Decomposition, Compression Ration 62: 1) .... .......... .. 84 

Fig.53 The Diagram of IWF Colour Image Compression ....................... 87 

Fig.54 The Transform the Colour Scpace ......... ............ ........................... 87 

Fig.55 Original colour images ....... ...................................... ....... ...... ..... ... 88 

Fig.56 Compressed colour images (]-level wavelet decomposition) ...... 88 

Fig.57 Compressed colour images (2-level wavelet decomposition) ...... 88 

Fig.58 Original Test Image (lena.bmp 256x256) ............. .... ...... ....... ...... . 89 

Fig.59 Compressed Image ( I-Level Wavelet Decomposition, 

Compression Ratio 2: I ) .... .. ...... .... ........ ............. ........ ... ............. ... ... ... 89 

Fig.60 Compressed Image 

(2-Level wavelet Decomposition, Compression Ratio 3.2: I ) .... ..... ..... .. .. 90 

Fig.6 1 Compressed Image 

(3-Level Wavelet Decomposition, Compression Ratio 7.2: 1) ................. 90 

Fig.62 Compression of an Image ... .. ............. .. ......................................... 94 

Fig.63 Decompression of an Image ... ......................... ............. ....... ......... 94 

viii 



List Tables 

Table. I Sample 8 x 8 screen of red, green, blue, cyan, magenta, yellow, 

and black pixels .................................................................................. 18 

Table.2 Frequency Table for Table 3.1 ..................................................... 19 

Table.3 Huffman Codes for Fig 2.3 .......................................................... 20 

Table.4 A String Table for LZW Algorithm ............................................. 25 

Table.5 A LZW Compression Table ......................................................... 26 

Table.6 A LZW Decompression Table ..................................................... 27 

Table.7 Comparison the between Huffman and LZW Algorithms .......... 29 

Table.8 Comparing the Probability and Fuzzy Theory ............................ 49 

Table.9 Comparing the RMSE of two Algorithms ................................... 92 

IX 



List of Abbreviation 

1-D - 1 Dimension 

2-D - 2 Dimension 

ANN Artificial neural Network 

DCT Discrete Cosine Transformation 

DFT Discrete Fourier Transformation 

DHT Discrete Hada Masurium transformation 

DM - Delta Modulation 

DPCM - Differential Pulse Code Modulation 

EZW Embedded Zerotree Wavelet 

GIF 

ISDN 

IWF 

IZ 

LIP 

LIS 

LSP -

LZW 

MSE 

N 

p 

PCM 

graphic interchange format 

- Integrated Services Digital Network 

Image Compression Based on Wavelet and Fuzzy Logic 

Isolated Zero 

List of Insignificant Pixels 

List of Insignificant Set 

List of Significant Pixels 

Lempe) Ziv Welch 

- Mean Square Error 

Negative 

Positive 

Pulse Code Modulation 

PDF portable document format 

PSNR - Peak Signal to Noise Ratio 

RMSE - root mean square error 

SPHIT - Set Partitioning in Hierarchical Trees 

TIFF tagged image file format 

VQ Vector Quantification 

ZTR - Zero Tree Root 

X 



Chapter 1 

Introduction 

1.1 Overview of the Current State of Technology 

The main goal of image compression is to minimjse the data volume of an image with 

no significant loss of information. The reduction in file size allows more images to be 

stored in a given amount of disk or memory space, and it also reduces the 

transmission cost of images sent over the Internet or downloaded from Web pages. 

Several different methods exist for the compression of images. All basic image 

compression groups have advantages and disadvantages. Methods for image 

compression fall into several major categories: 

• 

• 

• 

• 

• 

Transform-based methods 

Vector quantisation methods 

Pyramid-based techniques 

Hybrid compression methods 

Huffman encoding 

Transform-based techniques are renowned to better preserve subjective image quality 

and are less susceptible to statistical image property changes both inside a single 

image, and between images. One attractive quality of transform-based techniques is 

their insensitivity to transmission channel noise. If one transform coefficient is altered 

during transmission, the resulting image distortion is distributed homogeneously 

through the image or image section and therefore undesirable disruptive effects are 

rrunimised. Predictive compression techniques is transmjtted, the error causes image 

distortion not only in a particular pixel, but withln a neighbourhood of pixels because 



the predictor involved has a considerable visual effect in a reconstructed image.are 

plagued with the problem of propagating difference value transmission errors. When 

an erroneous difference value 

Vector quantisation methods have the advantage of only employing a single decoding 

scheme; comprising of a look-up table on ly. Vector quantisation methods, however, 

require complex code, and parameters are very sensitive to image data, often blurring 

the edges of images. 

Pyramid-based techniques have a natural compression ability, and are suitable for 

dynamic image compression and smart transmission approaches. Pyramid-based 

methods have shown the potential for further improvement of compression ratios. 

Hybrid compression methods general ly combine the different dimensionalities of 

transform compressions with predictive compressions. Hybrid compression methods 

can also combine predictive approaches with vector quantisation. 

Huffman encoding fal ls into a separate category of image compression, and is 

distinguished by its provision of optimal compression and error-free decompression. 

1.2 Research Objectives 

The focus of this study is on developing a new image compression method based on 

Wavelet transforms and Fuzzy Logic techniques. Many researches have been 

conducted using Wavelet transforms, however, only very few researches have been 

done using the fuzzy approach, and the full potential of Fuzzy Logic in the field of 

image compression has not yet been fully explored. 

The general objectives of this study are: 

1. To understand the basic concepts of wavelet transform operation. 

2. To learn about image compression techniques developed using the Wavelet 

2 



transform and Fuzzy Logic. 

3. To combine Wavelet transforms and Fuzzy techniques to reduce the 

computational cost of image compression. 

The specific objectives of this study are: 

1. To develop a Hybrid Wavelet approach to image compression that would be faster 

and more efficient than other Fuzzy Logic approaches. 

2. To develop a fast and simple Fuzzy coding technique for generating the Wavelet 

coefficients. 

1.3 Scope and Limitations of Research 

The scope of this study will include only static images. Both grey-scale and colour 

images will be used. The scope of the study will not, however, be extended to testing 

the algorithm on video sequences. 

1.4 Assumptions 

rt is assumed that the performance of the algorithm developed in this research can be 

compared against other algorithms by compressing and decompressing the same set 

of images used by other algorithms and inspecting speed, compression ratios, and root 

mean square errors. 

3 



1.5 Significance of Research 

Image compression addresses the problem of reducing the amount of data required to 

represent a digital image. From the information theory viewpoint, image compression 

is the removal of redundant information, namely keeping the non-definite information, 

and removing the determined information. From a mathematical viewpoint, image 

compression means to transform a 2-D pixel array into a statistically uncorrelated 

data set, where such transformation is applied to storage or transmission of the image. 

At some rate, the compressed image is decompressed to reconstruct the original 

image or an approximation of it. 

Wavelet compression [Antonini, M., Barlaud, M., Mathieu, P., & Daubechies, I. 

( 1992)] is one of the most effective methods of image compression. The algorithm is 

based on multi-resolutional analysis. Like conventional JPEG compression, the JPEG 

compression algorithm is based on the OCT transform, and separated the whole 

image to small sub-images. This method however, returns grainy compressed images, 

or those reflecting the "block effect". On the other hand, Wavelet compression 

algorithm presents an image as sets of real coefficients. After the wavelet 

decomposition step, the most important image information is located at the low 

frequency subband. In addition, the other Wavelet coefficients of a typical image 

are nearly zero, and the image is thus well-approximated with a small number of 

high-valued Wavelet coefficients. The advantage of Wavelet compression is that, in 

contrast to JPEG, the Wavelet algorithm does not divide the image into small blocks, 

but takes and analyzes the whole image. The distinguishing characteristic of Wavelet 

compression is that it allows arriving at the best compression ratio. 

Fuzzy Logic techniques are mainly employed in digital imaging for Contrast 

Adjustment, Image Enhancement, Image Segmentation, and Image Edge Detection 

[Tizhoosh, H. R. (1997)]. 

4 



By and large, Wavelet image compression is gaining acceptance m the internet 

community for its robustness in the presence of noise during the transmission of 

images. Unlike predictive methods, Wavelet-based techniques do not generate square 

image compression artifacts. On the other hand, one advantage of predictive 

methods over Wavelet-based techniques is that they achieve larger compression ratios 

in a much less expensive way. In light of this problem, this research amends the 

weaknesses of pure Wavelet image compression techniques by injecting Fuzzy 

techniques to speed up the calculation of Wavelet coefficients. As a result, image 

compression is achieved by utilizing Fuzzy logic in the quantization of Wavelet 

coefficients, allowing for the preservation of important image details while discarding 

less significant ones. 

1.6 Research Methodology 

In devising a new Fuzzy and Wavelet-based image compression algorithm, the 

following steps have been taken: 

l. Study of the basic concepts of image compression. 

2. Study of the different colour spaces and implementation of colour space 

transformation equations. 

3. Study of the Run Length Coding. 

4. Study and implementation of the Huffman algorithm. 

5. Study and implementation the LZW algorithm. 

6. Study of Wavelet transforms. 

7. Study and implementation of the EZW algorithm. 

8. Study of the SPHIT algorithm. 

9. Comparison of EZW and SPHIT. 

10. Study of JPEG and JPEG 2000. 

11. Comparison of JPEG and JPEG 2000. 

12. Study of Fuzzy Logic and Fuzzy image processing. 

5 



13. Study and analysis of other image compression algorithms based on Wavelet 

transforms. 

14. Study and analysis of other existing image compression algorithms based on 

Fuzzy logic. 

1. 7 Organisation of the Thesis 

This work is divided into five chapters and is described briefly as follows: 

Chapter 2 provides a theoretical framework for the issues relating to different kinds of 

image compression and Fuzzy Logic technique (Basic image concepts, image coding, 

transform coding, Fuzzy Logic and Fuzzy image processing). 

Chapter 3 presents a review of related literature, and discusses relevant algorithms in 

detail with analysis. 

Chapter 4 presents a brief overview of the algorithm developed. The chapter starts by 

introducing the principles of the algorithm, and then fo llows with the intricacies of 

the algorithm applied to both grey-scale and colour images, including analysis and 

experimental results. 

Lastly, in Chapter 5, conclusions and future works are presented. 

6