Image Compression

1.0 INTRODUCTION

1.1 Objective

Image Compression forms the backbone for several applications such as storage of images in a database, TV and facsimile transmission, video conferencing. Compression of images involves taking advantage of the redundancy in data present within an image. Vector quantization is often used when high compression ratios are required.

Quantization is referred to produce of approximating continuous with discrete values. (Digitizing the amplitude values). Vector Quantization is stated as finding the reference vectors(Code words) which approximate minimum error with the input data according to some distortion criteria

In VQ, the transformed image has to be coded into vectors. Each of these vectors is then approximated and replaced by the index of one of the elements of the codebook. The only useful information in this is the index for each of the blocks of the original image, thus reducing the transmission bit rate [1,2,3]. DWT has received significant and several very efficient wavelet based compression have been proposed [4,5]. This is due to the fact that the wavelet transform can provide multi resolution for image with localization of both frequency and time.

There are many approaches to code design. The two most common approaches are to use some subset of a lattice to force a highly structured codebook or to apply a clustering algorithm such as the Lloyd (Forgey, Isodata, k-means) algorithm. The generalized Lloyd algorithm (GLA), which is sometimes referred to as the Linde-Buzo-Gray (LBG) algorithm, has been updating codebook by replacing the value that makes less distortion[6]. This update step will iterate until the distortion is under the LBG limit.

In Tree Structured VQ, the codeword is selected by a sequence of binary minimum distortion decisions comparing the input vector to stored vector reproductions at each available node. The encoder produces binary symbols to represent its sequence of decisions from the root node of the tree through the terminal node. This binary sequence or path map is the final codeword [7].

Multistage VQ divides the encoding task into several stages [8,9,10]. The first stage performs a relatively crude encoding of the input vector using a small codebook. Then, a second-stage quantizer operates on the error vector between the original vector and the quantized first stage output. The quantized error vector provides a refinement to the first approximation. At the decoder, the reproduction vectors produced by the first and second stages will be added together. MVQ is sometimes referred to as residual VQ but those words better apply to a variation on multistage VQ that effectively uses the same codebook but allows a non greedy search. [11,12,13].

SPIHT belongs to the next generation of wavelet encoders, employing more sophisticated coding. In fact, SPIHT exploits the properties of the wavelet transformed images to increase its efficiency. The SPIHT algorithm uses a partitioning of the tree in a manner that tends to keep insignificant coefficients together in larger subsets[14].

Pyramid vector quantization uses the lattice points [15] of a pyramidal shape in multidimensional space as the quantizer codebook. PVQ was introduced by Fischer [16] as a fast an efficient method of quantizing Laplacian-like data, such as generated by transforms or subband filters in an image compression system. It combines the robustness of fixed-rate codes with the performance of entropy-coded scalar quantization. PVQ takes its name from the geometric shape of the points in its codebook. It is designed for Laplacian random variables, whose equiprobable contours form multidimensional pyramids.

The role of FPCM in the field of vector quantization has not been reported earlier. It has been extensively used in the field of segmentation. Therefore, it is proposed to use this technique for vector quantizer codebook generation and to analyze its the impact in the field of image compression. The implementation consists of three steps. First, image is decomposed into a set of sub bands with different resolution corresponding to different frequency bands. The output of all frequency banks are fed to Vector quantization [17]. The proposed clustering technique is used for the codebook design. It iteratively improves a codebook by ultimately optimizing the encoder for the decoder (using a minimum distortion) and the decoder for the encoder (replacing the old codebook by generalized “centroids”). Image quality is compared using mean squared error and PSNR along with subjective visual appearance measure.

1.2 Need for Compression

Image compression is a natural technology used in spatial resolution of today's imaging sensors and broadcast standards. These techniques play an important role in diverse applications such as video conferencing, remote sensing, document and medical imaging, facsimile auto Xerox, space and waste management applications.

1.3 Overview of Image Compression

An image is represented as two dimensional functions f(x,y) where x and y are spatial coordinates and the amplitudes of f at any pair of coordinates is called the intensity or gray level of the image at that point. The image is composed of finite number of elements, each of which has a particular location and values. The elements are referred as picture elements, image elements, pels and pixels.

1.4 Application of Image Compression

Application of image compression are classified as

1. Transmission

* Remote sensing via satellite

* Military communication via aircraft

* Radar and sonar

* Teleconferencing

* Computer communications

* Facsimile transmission

* Broadcast TV

2. Storage

* Educational business documents

* Medical images(X-rays, CT, MRI)

* Motion pictures

* Satellite images

* Weather maps

* Geological surveys

2.0 Literature survey

2.1 Image Compression

The purpose of image compression is to represent images with less data in order to save storage costs or transmission time. Without compression, file size is significantly larger, usually several megabytes, but with compression it is possible to reduce file size to 10 percent from the original without noticeable loss in quality. Image compression can be lossless or lossy. Lossless compression means that we are able to reconstruct the exact original data from the compressed data. Image quality is not reduced when using lossless compression. Unlike lossless compression, lossy compression reduces image quality. The original image can't get back after using lossy compression methods[18].

2.2 Compression Techniques

2.2.1 Lossless compression

Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. The term lossless is in contrast to lossy data compression, which only allows an approximation of the original data to be reconstructed, in exchange for better compression rates.

Lossless data compression is used in many applications. For example, it is used in the popular ZIP file format and in the Unix tool gzip. It is also often used as a component within lossy data compression technologies.

Lossless compression is used when it is important that the original and the decompressed data be identical, or when no assumption can be made on whether certain deviation is uncritical. Typical examples are executable programs and source code. Some image file formats, like PNG or GIF, use only lossless compression, while others like TIFF and MNG may use either lossless or lossy methods
Lossless compression techniques

Most lossless compression programs use two different kinds of algorithms: one which generates a statistical model for the input data, and another which maps the input data to bit sequences using this model in such a way that "probable" (e.g. frequently encountered) data will produce shorter output than "improbable" data.

The primary encoding algorithms used to produce bit sequences are Huffman coding and arithmetic coding. Arithmetic coding achieves compression rates close to the best possible for a particular statistical model, which is given by the information entropy, whereas Huffman compression is simpler and faster but produces poor results for models that deal with symbol probabilities close to 1.

There are two primary ways of constructing statistical models: in a static model, the data is analyzed and a model is constructed, then this model is stored with the compressed data. This approach is simple and modular, but has the disadvantage that the model itself can be expensive to store, and also that it forces a single model to be used for all data being compressed, and so performs poorly on files containing heterogeneous data. Adaptive models dynamically update the model as the data is compressed. Both the encoder and decoder begin with a trivial model, yielding poor compression of initial data, but as they learn more about the data performance improve. Most popular types of compression used in practice now use adaptive coders.

Lossless compression methods may be categorized according to the type of data they are designed to compress. While, in principle, any general-purpose lossless compression algorithm can be used on any type of data, many are unable to achieve significant compression on data that is not of the form for which they were designed to compress. Many of the lossless compression techniques used for text also work reasonably well for indexed images.

2.2.2 Lossy compression

A lossy compression method is one where compressing data and then decompressing it retrieves data that may well be different from the original, but is close enough to be useful in some way. Lossy compression is most commonly used to compress multimedia data (audio, video, still images), especially in applications such as streaming media and internet telephony. By contrast, lossless compression is required for text and data files, such as bank records, text articles, etc.

Lossy compression formats suffer from generation loss: repeatedly compressing and decompressing the file will cause it to progressively lose quality. This is in contrast with lossless data compression.

Information-theoretical foundations for lossy data compression are provided by rate-distortion theory. Much like the use of probability in optimal coding theory, rate-distortion theory heavily draws on Bayesian estimation and decision theory in order to model perceptual distortion and even aesthetic judgment

Types

There are two basic lossy compression schemes:

* In lossy transform codecs, samples of picture or sound are taken, chopped into small segments, transformed into a new basis space, and quantized. The resulting quantized values are then entropy coded.

* In lossy predictive codecs, previous and/or subsequent decoded data is used to predict the current sound sample or image frame. The error between the predicted data and the real data, together with any extra information needed to reproduce the prediction, is then quantized and coded.

In some systems the two techniques are combined, with transform codecs being used to compress the error signals generated by the predictive stage.

2.3 Vector Quantization

Several variations of the vector quantization have been successfully used in image compression [19-25]. Clustering or codebook design is an essential process image compression based on vector quantization. Clustering refers to a broad spectrum of methods that attempt to subdivide a random data set into subsets, or clusters, which are pair-wise disjoint, all non-empty, and reproduce the original data set via union. The application of vector quantization to images is based on the decomposition of one or more sampled images into rectangular blocks that form vectors of fixed size. The available vectors, also called training vectors, are divided into clusters on the basis of some optimality criterion, while the cluster centers provide the codebook vectors. In the context of vector quantization, the clustering process is also referred to as the codebook design. Given a codebook, each block of the image can be represented by the binary address of its closest codebook vector. Such a strategy results in significant reduction of the information involved in image transmission and storage. The image is reconstructed by replacing each image block by its closest codebook vector. As a result, the quality of the reconstructed image strongly depends on the codebook design.

Codebook design is usually based on the minimization of an average distortion measure between the training vectors and the codebook vectors . The minimization of the distortion measure is wisely performed by a gradient descent based iterative algorithm that is known as K-Means (or c-means) algorithm or Generalized Lloyd Algorithm. A variation of the K-Means algorithm is known in the engineering literature as the LBG (Linde, Buzo, Gray) algorithm[26]. The K-Means algorithm begins with the selection of an initial set of codebook vectors, which implies the partition of the training vector space into quantization cells. Each cell is represented by its center, which implies the partition of the training vector space into quantization cells. Each cell is represented by its center, which evaluated as the centroid of the training vectors belonging to that cell. Each of the training vectors is assigned to the cluster whose center is its closest neighbor. The new set of centers is evaluated from the results of the new partition. The process of determining a new partition of the training vectors by selecting a new set of centers is called Lloyd iteration.

Although the K-Means algorithm is simple and intuitively appealing, it strongly depends on the selection of the initial codebook, and it can easily be trapped in local minima. The selection of a good initial codebook was attempted by random code, splitting, and pair-wise nearest neighbor techniques. However, there seems to be no simple solution to the local minima problem. For a given initial codebook, the algorithm finds the nearest local minimum in the space of all possible codebooks.

The search for a globally optimum codebook was attempted in recent years by minimizing the average distortion measure using stochastic relaxation techniques[27]. The common characteristics of these techniques is that during each iteration of the search, for the minimum of the average distortion, the independent variables involved in the distortion measure are perturbed in a random fashion. Simulated annealing is a stochastic optimization technique introduced by Kirkpatrick et al. that is widely used in nonconvex optimization[28]. Zeger et al. proposed a vector quantized design technique that combines simulated annealing and the Lloyd iteration. According to this approach, training vectors are randomly moving between neighboring partition regions until thermal equilibrium is reached. The new centers are subsequently evaluated by using the Lloyd iteration. Flanagan et al. simplified this method by minimizing a cost function that can easily be computed and also omitting the Lloyd iteration[29].

Yair et al. attempted the development of vector quantizer design techniques by combining stochastic relaxation with competitive learning algorithms and a soft competition scheme[30]. Stochastic relaxation provided the basis for the development of a vector quantizer design technique that produces the global minimum but is computationally expensive. Yair et al. also proposed a new deterministic vector quantizer design algorithm, called the competition scheme, by incorporating the principles of the stochastic approach into the unsupervised learning rule proposed by Kohonen for ordering feature maps.

Although simulated annealing generally produces better codebooks than the k-means algorithm, it is typically a very time consuming process. In addition, simulated annealing can be a difficult method to apply because several control parameters must be properly adjusted in order to obtain good results. In an attempt to overcome the time requirements of simulated annealing, Rose et al proposed an alternative codebook design scheme based on deterministic annealing. Deterministic annealing is an optimization technique designed to capture the advantages of simulated annealing without any randomness in the design process[31].

The techniques for codebook design mentioned above are based on crisp decisions in the sense that each training vector is assigned to a single cluster according to some criterion. A common ingredient of all these techniques is that they assign each training vector to a single cluster and ignore the possibility of training vector which may also belong to other clusters.

Fuzzy sets were introduced by Zadeh as a new way to represent vagueness in everyday life[32]. The use of fuzzy sets in clustering was first proposed in[33] and several classification schemes were subsequently developed[34]. Based on the idea of fuzzy sets, Ruspini developed the first fuzzy clustering algorithm[35]. Dunn considered an alternative formulation of the clustering process and proposed the fuzzy k-means algorithm, which is also known as the fuzzy ISODATA algorithm.

Bezdek extended Dunn's formulation and produced a family of infinitely many fuzzy k-means algorithms, which includes Dunn's original algorithm as a special case. Fuzzy clustering algorithms consider each cluster as a fuzzy set, while a membership function measures the possibility that each training vector belongs to a cluster. As a result, each training vector may be assigned to multiple clusters with some degree of certainty measured by the membership function. Thus, the partition of the training vector space is based on soft decisions.

The main reason for the lack of interest among engineers in fuzzy clustering techniques is that vector quantization is based on the representation of any image block by a single codebook vector, which is essentially a crisp decision making process. In addition, the existing fuzzy algorithms require a priori assumptions about the level of fuzziness appropriate for a certain clustering task. Such assumptions are implicitly made by selecting any of the fuzzy k-means algorithms. Nevertheless, fuzzy clustering algorithms offer a framework for quantitatively formulation the uncertainty involved in the partition of the training vector space. The use of such an approach during the initial stages of the codebook design process could eliminate, or at least significantly reduce, the dependence of the resulting codebook on the selection of the initial codebook.

Efficient algorithms for vector quantizer design, which exploit the advantages offered by fuzzy clustering algorithms while satisfying the requirements imposed by the vector quantization problem. The development of these algorithms is based on effective strategies for the transition from soft decisions to hard or crisp decisions during the clustering process.

The Possibilistic approach was proposed by Krishnapuram and Keller to surmount limited algorithms of fuzzy classification in the presence of noise, and outliers they released the constraint of probabilistic inspiration and proposed a new partition.

2.3.1 Code vector Size Optimization

Consider N x N images with r bits per pixel, and let L = p x p is the block size. Let the of the code book being Nc. Therefore Size S of the compressed image in terms of bits is:

The first term is to represent the number bits required for specifying the index. The second term is the number bits required to transmit the code book. The bit rate (R ) in terms of bits per pixel is given by

After dividing the previous equation by N2, we get

For minimum bit rate R, the derivative

Since

We have

For an image size N=512, the optimal value image size can be tabulated as follows.

Table 1: Code book size and their corresponding block size

Nc

24

25

26

27

28

29

210

211

P

9.5137

8.4590

7.4448

6.5063

5.6569

4.8990

4.2295

3.6423

Value of p rounded to closest to 2

8

8

8

8

4

4

4

4

Interestingly, statistical studies on natural images have shown that there is little correlation between pixels more than 8 positions apart, and in fact, most of the correlations are among pixels that are within 4 positions away. Therefore, 4 x 4 and 8 x 8 code words are excellent choices from both the bit rate standpoint and the correlation exploitation standpoint. Therefore, optimal 2D code vector sizes are 4 x 4 and 8 x 8 for powers of 2 sizes[36].

2.3.2 Optimality and Convergence Criteria

If C is the solution to the minimization problem, then it must satisfy the following two criteria.

Nearest neighbor condition

This condition says that the encoding region Sn should consists of all vectors that are closer to Cn than any of the other code vectors. A data point will be associated to the centroid which is more close to that data point.

Centroid Condition

This condition says that average of all those training vectors that are in encoding region Sn. In implementation, one should ensure that at least one training vector belongs to each encoding region (so that the denominator in the above equation is never 0)

Associated with each reproduction code-vector is a partition of Rn, called a region or cell, S = {Si: i , I }. The most popular form of vector quantizer is the Voroanoi or nearest neighbour cluster where for each input source vector, x, a search is done through the entire codebook to find the nearest code-vector, yi, which has the minimum distance

yi =Q[x] if d(x, yi) < d(x, yj ) for all i = j

where d(x, y) is a distance measure between the vectors, x and y. The regions in a nearest neighbour cluster are also called Voronoi regions and these are shown in Fig.2.

The various regions show the centroid allocation. For highly probabilistic data regions centroids are more clustered. For less probabilistic data centroids are far apart, where the mean squared error (MSE) is used as the distance measure. Depending on the coding application, other more meaningful distance measures may be used such as the Mahalanobis distance, Itakura–Saito distance, or other perceptually-weighted distance measures.

2.4 Wavelets

2.4.1 Subband Decompositions

Subband coding was introduced in the context of speech coding in 1976 by Croisier et al. [37] and Crochiere et al. [ 38]. Croisier et al. were the first to solve the critical problem of aliasing cancellation after decimation and reconstruction in subbands, using “quadrature mirror filters” (QMF's). The theoretical extension of subband filtering from 1-D to 2-D was made by Vetterli [39]. Two-dimensional subband filtering was first applied to image coding by Woods and O'Neil [40]. A subband decomposition is produced by an analysis filter bank followed by downsampling. Any or all of the resulting subbands can be further input to an analysis filter bank and downsampling operation for as many stages as desired.

Fig. 3 shows one stage of such a system using 2-D separable filters. In the , ↓ 2 denotes downsampling by a factor of two, H0 denotes a lowpass filter, and H1 denotes a highpass filter. The initial high and lowpass filters and downsampling are applied to the rows of an image. The subsequent filters and downsampling are then applied to the resulting columns. Because there are only two filters, this is called a twochannel system. Multichannel systems have been much less explored than two-channel systems. The image is split into four bands- LL, LH, HL, and HH-according to whether the rows and columns received the low- or high-frequency filtering. The reconstruction operation consists of an upsampling operator followed by a synthesis filter bank, as shown in Fig. 4. One stage of reconstruction is used for each stage of decomposition. The term “decomposition” to refer to the filtering and downsampling operations for as many stages as desired.

Ideally, decomposition followed by reconstruction will provide a perfect replica of the original signal. This perfect reconstruction requirement is usually built into the decomposition as a requirement if real inputs and analog arithmetic are assumed, but it is only an approximation when dealing with digital signals because of round-off error in the arithmetic. Furthermore, in image compression, the decomposed signal is compressed in a lossy fashion, typically by SQ or VQ. The term “encoding” refers to the combination of decomposing and quantizing with or without subsequent entropy coding. The term “decoding” refers to the inverse operation to encoding; therefore, it consists of the combination of inverse quantization followed by reconstruction.

If all four of the subbands are subjected to another stage of filtering and downsampling, this leads to a uniform decomposition, as depicted in Fig. 5(a). This decomposition is a balanced tree. If only the low band is further decomposed, this is referred to as an octave-band decomposition (which is also often called a logarithmic-tree or pyramid' decomposition). This situation, which is represented by a highly unbalanced tree, is shown in Fig. 5(b). In fact, for the fixed maximum depth of the tree, this octave-band decomposition is as unbalanced a tree as one can have. For the fixed maximum depth of the tree, the balanced tree produced by a uniform decomposition and the maximally unbalanced tree produced by a pyramidal decomposition represent the two extremes of possible choices. Anything between these extremes is called a wavelet packet [41].

Techniques for producing image subband decompositions can be quite general. One type of decomposition, called a wavelet transform, uses octave-band filter banks with regularity conditions imposed on the lowpass filters. The wavelet transform can be interpreted as a subband decomposition of the signal into a set of overlapping frequency channels having the same bandwidth on a logarithmic scale. This type of octave-band decomposition is called as wavelet decomposition. The more general term “subband decomposition” will be used for the uniform-band case and as the general term.

The various subband / VQ systems surveyed used a wide variety of filters. One of the goals of signal decomposition theory is to find conditions such that in the absence of noise or quantization, the overall reconstruction is perfect or nearly so. The simplest and shortest filter-the Haar wavelet-is important for historical and theoretical reasons but is rarely used as part of a wavelet/SQ or wavelet/VQ scheme. By far, the most common choice is one of the quadrature mirror filters QMF's that are listed in [42]. Many authors refer to these as “Johnston's near-perfect reconstruction filters” or near-PR filters. The second most popular choice is one of the family of Daubechies orthogonal filters [43], [44]. The biorthogonal filters[45], which possess the advantage of linear phase, are also common. The Gabor functions, which are Gaussians modulated by complex exponentials, are more rarely used. Use of the latter for wavelet transforms is motivated by the fact that they have joint localization in the spatialkpatial-frequency domains that is optimal in a certain sense and that, according to recent experiments, the majority of receptive field profiles of the human visual system fit quite well this type of function.

The choice of filter reflects a tradeoff among many factors, such as spatial localization, frequency selectivity, regularity, and coding gain.

3.0 pROPOSED System

3.1pROPOSED fUZZY POSSIBILISTIC C MEANS ALGORITHM

FPCM algorithm was proposed by N.R.Pal, K.Pal, and J.C.Bezdek, it includes both possibility(typicality) and membership values. It is a combination of a fuzzy partition and a possibilistic partition is presented. The idea behind is that the membership value of the fuzzy partition is important to be able to assign a hard label to classify an input vector, but at the same time, it is very useful to use the typicality (possibility) value to move the centers around the input vectors space, avoiding undesirable effects due to the presence of outliers. The distortion function to be minimized is

with following constraints

and

Let T = [tik], then, the constraint shown above requires each row of T to sum up to 1 but its columns are free up to the requirement that each column contains at least one non-zero entry, thus, there is a possibility of input vectors not belonging to any cluster.

It is believed that memberships (or relative typicalities) and possibilities (or absolute typicalities) are both important for correct interpretation of data substructure. When we want to crisply label a data point, membership is a plausible choice as it is natural to assign a point to the cluster whose prototype is closest to the point. On the other hand, while estimating the centroids, typicality is an important means for alleviating the undesirable effects of outliers.

The FPCM membership concept is defined by the following three rules:

R1: If an object belongs to the influence zone of a class then one assigns it to the latter with a fuzzy degree and to the others with possibilistics degrees.

R2: If an object belongs to the intersection of two or several influences zones, on assigns it with a fuzzy degree to each overlapping class.

R3: If an object does not belong to any influence zone, one assigns it with a possibilistic degree to each class.

The above proposed clustering Algorithm is not used in the field of image compression so far.

The 6 below shows the block diagram of the new proposed FPCM algorithm.

ALGORITHM

Step 1: Divide the image(X) into blocks of size (4 x 4).

Step 2: Decompose these image blocks using DWT.

Step 3: Rearrange each decomposed sub bands into matrix of size N/2 x N/2 (N=4).

Step 4: Reshape sub bands of a given block into a vector of size [1 x N2/ 4].

Step 5: Apply FPCM to cluster these vectors and calculate the centroids(Vi) for those clusters using the formula,

Step 6: Design the codebook using the centroids as the code vectors (cm).

Step 7: Encode the input image using this newly designed codebook.

i) Compute the distance between each input vector(xi ) and every code vector(cm) using Euclidean Distance(Ed) Measure,

ii) Find the closest code vector to each input vector.

iii) Assign the index of the closest code vector (m) to the respective input vector.

Step 8: Apply Huffman coding and send the Huffman encoded data (compressed image) to the receiver.

Step 9: Apply Inverse DWT, index reassignment followed by Huffman decoding to reconstruct the image.

Step 10.Compute the following performance parameters

i)Compression Ratio=The number of bits in the original image/ The number of bits in the compressed image.

4.0 SYSTEM REQUIREMENTS

4.1 Hardware Requirements

Processor : Intel Pentium Dual core

Clock Speed : 2.16 GHz

Ram Capacity : 3GB

Floppy Disk Drive : 1.44mb

Hard Disk : 250GB

Keyboard : 108keys

Mouse : Samsung Serial Mouse

4.2 Software Requirements

Operating System : microsoft windows xP

Software tools : MATLAB 7.0

5.0 Implemention and Testing

Proposed Fuzzy Possibilistic C-means Clustering Algorithm

Algorithm

Step 1: Get an input as image

Step 2: Divide the image(X) into blocks of size (4 x 4).

Step 3: Decompose these image blocks using DWT.

Step 4: Rearrange each decomposed sub bands into matrix of size N/2 x N/2 (N=4).

Step 5: Reshape sub bands of a given block into a vector of size [1 x N2/ 4].

Step 6: Apply FPCM to cluster these vectors and calculate the centroids(Vi) for those clusters using the formula,

Step 7: Design the codebook using the centroids as the code vectors (cm).

Step 8: Encode the input image using this newly designed codebook.

i)Compute the distance between each input vector(xi ) and every code vector(cm) using Euclidean Distance(Ed) Measure,

ii)Find the closest code vector to each input vector.

iii)Assign the index of the closest code vector (m) to the respective input vector.

Step 9: Apply Huffman coding and send the Huffman encoded data (compressed image) to the receiver.

Step 10: Compression Ratio can be calculated as follows

CR = Size of the original Image / Size of the compressed image

Step 11: Apply Inverse DWT, index reassignment followed by Huffman decoding to reconstruct the image.

Step 12.Compute the following performance parameters

i)Compression Ratio=The number of bits in the original image/ The number of bits in the compressed image.

ii)=30.13db

6.0 Result Analysis

A number of "standard" gray-scale test images are available in the website,

http://www.imagecompression.com. The researchers in the field of image processing predominantly use these test images for discussion of their results. These images contain low frequency, high frequency and as well as medium frequency components. In addition, these images are characterized by different values of energies. Below shows 5 test images, each of size 256 x 256

6.1 Compression scores

The following metrics are used for the evaluation of the algorithm

* Peak Signal to Noise Ratio.

* Compression Ratio

Peak Signal to Noise Ratio

The phrase Peak Signal to Noise Ratio, often abbreviated PSNR, is ratio between the maximum possible power of the signal and the power of corrupting noise that affects the fidelity of its representation. Because many signals have a very wide dynamic range, PSNR is usually expressed in terms of logarithmic decibel scale.

The PSNR is defined as:

Here, MaxI is the maximum pixel value of the image.

Compression Ratio

A logical way of measuring how well a compression algorithm compresses a given set of data is to look at the ratio of the number of bits required to represent the data before compression to the number of bits required to present the data after compression. This ratio is called as compression ratio

CR = Size of the original Image / Size of the compressed image

6.2 Performance comparison of proposed FPCM with all algorithms in Spatial domain

The performance analysis of test images with all algorithms are compared along with the results pertaining to PSNR, Compression ratio is tabulated below.

Table 2: Performance comparison of proposed work with existing techniques for cluster size 256 , compression ratio in Spatial Domain

LBG

K MEANS

FCM

PCM

FPCM

ZELDA

27.25

28.45

29.59

25.39

29.59

WOMAN DARK HAIR

23.80

26.76

28.55

25.57

29.16

WOMAN

15.08

26.74

27.10

24.37

27.11

TRACY

21.55

28.21

28.76

21.02

28.78

BOTTOM _LEFT

32.92

32.51

33.70

30.03

34.61

6.3 Performance comparison of proposed FPCM with all algorithms in Wavelet domain

The performance analysis of test images with all algorithms are compared along with the results pertaining to PSNR, Compression ratio is tabulated below.

For the simulation of the entire compression process, we used 4 x 4 points image blocks. The LBG, K-Means, FCM, PCM, FPCM clustering was used to obtain the centroids of each each sub band. Simulations have been carried out on test images Zelda, WomanDarkHair, Woman , Tracy, Bottom_left images of 256 x 256. For each test image, objective and subjective picture quality are analyzed. Table 2 shows PSNR ratios of various clustering algorithms for 256 cluster.

Table 3: Performance comparison of proposed work with existing techniques for cluster size 256 , compression ratio in Wavelet Domain

LBG

K MEANS

FCM

PCM

FPCM

ZELDA

25.88

29.04

30.04

27.08

30.13

WOMAN DARK HAIR

25.61

24.00

29.00

25.37

29.57

WOMAN

23.89

27.00

27.45

24.80

27.46

TRACY

25.88

28.93

29.38

25.81

29.39

BOTTOM _LEFT

31.34

35.06

35.05

32.54

36.51

From the above Tables 2 and 3 it is found that the PSNR ratio of the clustering algorithms in wavelet domain is better than the spatial domain. Also it is observed that the proposed method perform better than the existing methods irrespective of the domain(either spatial and wavelet). In addition it is inferred that the proposed method gives better PSNR ratioin the wavelet domain than in the spatial domain. The fidelity criteria both subjective and objective are pretty good.

The following are the reconstructed images using LBG, KMEANS, FCM , PCM , FPCM algorithms of 256 x 256 zelda image for the cluster size 256, and rest of the reconstructed images are shown in appendix. The subjective quality measure for the reconstructed Zelda image is better for the proposed method than the existing methods. This is observed from 9.

RECONSTRUCTED IMAGES USING ALL ALGORITHMS OF ZELDA - 256CLUSTERS , 4 BLOCK OF 256 X 256 IMAGES IN WAVELET DOMAIN

7.0 Conclusion

A novel idea of using FPCM technique for image compression in wavelet domain is presented. The proposed method consists of four advantages which makes it very efficient in image coding. First the inter sub band self similarity of different sub band coefficients in the wavelet transform domain is taken. Second, FPCM clustering technique is used to compute the centroids of each sub band cluster. Third, VQ technique is employed to achieve higher compression ratios. Finally, Huffman coding is used for encoding. The analysis of the experimental results shows that the proposed method provides better PSNR ratio than the existing methods.

8.0 Future enhancements

The following can be carried out for future enhancements

1. All algorithms can be tested for color image and their performance can be analyzed.

2. The algorithms can be extended to Wavelet Packet tree and tested.

3. The algorithms can be tested for multistage VQ in Spatial, Wavelet, Wavelet Packet Tree Domain.

4. The algorithms can be tested for SPIHT, Pyramid based image compression

9.0 References

1.Gersho, “On the structure of vector quantizers,” IEEE Transactions on Information Theory, vol. 28,no. 2, pp. 157–166, March 1982.

2.R. Gray, “Vector quantization,” IEEE Acoustic, Speech and Signal Processing Magazine, vol. 1, pp. 4–29, 1984.

3.Gersho and R.M. Gray, Vector Quantization Signal Compression. Boston, MA: Kluwer Academic, 1992.

4.M.Antonini, and I. Daubechies, Image coding using wavelet transform” IEEE transactions Image processing , vol.1 no.2, pp 205-220, apr.1992

5.Cosman, P.C. 1996. vector quantization sub bands; a survey. IEEE trans .image processing 5 202-225

6.Y. Linde, A. Buzo, and R.M. Gray, “An algorithm for vector quantizer design,” IEEE Trans. Commun. Vol. 28, pp. 84-95, 1980.

7.E. A. Riskin and R. M. Gray, “A greedy tree growing algorithm for the design of variable rate vector quantizers,” IEEE Trans. Signal Processing, vol. 39, pp. 2500-2507, Nov. 1991.

8.B.-H. Juang and A. H. Gray, Jr., “Multiple stage vector quantization for speech coding,” in Proc ICASSP, Paris, vol. 1, Apr. 1982, pp. 597-600.

9.Y.A. Ho and A. Gersho, “Variable-rate multi-stage vector quantization for image coding,” in Proc.ZCASSP, Apr. 1988, pp. 1156-1159.

10.W. Y. Chan, S. Gupta, and A. Gersho, “Enhanced multistage vector quantization by joint codebook design,” IEEE Trans. Commun., vol. 40,no. 11, pp. 1693-1697, Nov. 1992.

11.F. Barnes and R. L. Frost, “Necessary conditions for the optimality of residual Vector quantizers,” in Abs. 1990 IEEE Int. Symp. Inform.Theory, San Diego, CA, USA, Jan. 1990, p. 34.

12.R. L. Frost, C. F. Barnes, and F. Xu, “Design and performance of residual quantizers,” in Proc. Data Compression Conference, J. A. Storer and J. H. Reif, Eds., Snowbird, UT, USA, Apr. 1991, pp. 129- 138.

13.F. Barnes and R. L. Frost, “Vector quantizers with direct sum codebooks,” IEEE Trans. Inform. Theory, vol. 39, no. 2, pp. 565-580, Mar. 1993.

14.A.Said & W.Pearlman, “A new fast and efficient image codec based on set partitioning in hierarchical trees”,IEEE Trans. On Circuits Syst. On Video Tech.,vol.6,pp.243-250,1996.

15.M. Antonini, P. Sole, T.Gordon and M.Barlaud, “Pyramidal lattice vector quantization for multiscale image coding”, IEEE Trans. Image processing, vol.3, pp.367-381, 1994.

16.T. R. Fischer, “A pyramid vector quantizer,” IEEE Trans. Inform. Theory, vol.32, pp.568-583, July 1986.

17.N.Venkateswaran and y.V. Ramana Rao, K-Means clustering based Image compression in wavelet Domain”, Information Technology Journal 6(1) 148-153, 2007.

18. Wikipedia-www.wikipedia.com

19. A.Gesho and B.Rammurthi,” Image coding using vector quantization” in Proc.IEEE Int. Conf.Acoust., Speech, Signal Processing, Vol I, Paris,Apr 1982,pp. 428-431.

20.H.M.Hang and J.W.Woods, “Predictive vector quantization of images,”IEEE Trans. Commun., Vol 33 pp 1208-1219,1985.

21. B. Ramamurthi and A. Gersho, “Classified vector quantization of images,” IEEE Trans. Commun., vol. 34, pp. 1105-1115, 1986.

22. N.M. Nasrabadi and R.A King, “Image coding using vector quantization: A review,” IEEE Tans. Commun., vol.36,957-971, 1988.

23. P.H. Westerink, D.E. Boekee, J. Biemond, and J.W.Woods, “Subband coding of images using vector quantization,” IEEE Trans. Commun., vol. 36,pp.713-719,1988

24. E.A. Riskin, T. Lookabaugh, P.A Chou. and R.M. Gray, “Variable rate vector quantization for medical image compression,” IEEE Tans. Med. Imaging, vol, 9pp. 290-298, 1990.

25. N.M Nasrabadi and Y. Feng, “Image compression using address-vector quantization,” IEEE Trans. Commun., vol. 38, pp.2166-2173, 1990.

26. K. Zeger, J.Vaisey. and A Gersho, “Globally optimal vector quantizer design by stochastic relaxation,” IEEE Tans. Signal Processing, vol. 40, no. 2, pp. 310-322, Feb. 1992.

27. S.Kirkpatrick, C.D Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol 220, pp. 671-680. 1989

28. J. K. Flanagan, D.R. Morrell, R.L. Frost, C.J. Read, and B.E. Nelson, “Vector quantization codebook generation using simulated annealing,” in Proc. IEEE Int. Conf. Acoust., Speech, Signal Processing, Glasgow, Scotland, May 1990, pp.1759-1762.

29. E. Yair, K. Zeger, and A. Gersho, “Competitive learning and soft competition for vector quantizer design,” IEEE Tans. Signal Processing vol. 40, no. 2, pp. 294-309, Feb. 1992.

30. K. Rose, E. Gurewitz, and G.C Fox, “A deterministic annealing approach to clustering,” Pattern Recognition Lett., vol. 11, pp. 589-594, 1990.

31. L.A Zadeh, “Fuzzy sets,” Inform. Contr., vol. 8, pp. 338-353, 1965.

32. R.E Bellman, R.A. Kalaba, and L.A. Zadeh, “Abstraction and pattern classification,” J.Math. Anal. Appl., vol. 13, pp. 1-7, 1966.

33. I. Gitman and M. D. Levine, “An algorithm for detecting unimodal fuzzy sets and its application as a clustering technique,” IEEE Tans. Comput., vol. 19, no. 7, 583-593, 1970.

34.E. H. Ruspini, “A new approach to clustering,” Inform. Contr., vol. 15, pp. 22-32, 1969.

35. J. C. Dunn, “A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters,” J. Cybernetics, vol. 3, no. 3, pp. 32-57, 1973.

DWT

36. Hyun-Sook Rhee and Kyung-Whan Oh, A Validity Measure for Fuzzy Clustering and Its Use in Selecting Optimal Number of Cluster", IEEE International Conference on Fuzzy Systems, New Orleans-USA, Vol. 2, pp.1020-1025, 1996.

37.A. Croisier, D. Esteban, and C. Galand, “Perfect channel splitting by use of interpolation/decimation/tree decomposition techniques,” in Int. Con$ Inform. Sci. Syst., Patras, Greece, Aug. 1976, pp. 4 4 3- 44 6 .

38.R. E. Crochiese, S. M. Webber, and J. K. L. Flanagan, “Digital coding of speech in subbands,” Bell Syst. Tech. J., vol. 55, pp. 1069-1086, Oct. 1976.

39.M. Vetterli, “Multi-dimensional sub-band coding: Some theory and algorithms,” Signal Processing, vol. 6, pp. 97-1 12, Apr. 1984.

40.J. W. Woods and S. D. O'Neil, “Subhand coding of images,” IEEE Trans. Acoust. Speech Signal Processing, vol. ASSP-34, pp. 1278-1288, Oct. 1986.

41.R. R. Coifman and M. V. Wickerhauser, “Entropy-based algorithms for best basis selection,” IEEE Trans. Inform. Theory, vol. 38, no. 2, pp. 713-718, 1992. Boston: Kluwer, 1991.

42. J. D. Johnston, “A filter family designed for use in quadrature mirror filter hanks,” in Proc. ICASSP, Denver, CO, 1980, pp. 291-294.

43. I. Daubechies, “Orthonormal bases of compactly supported wavelets,” Commun. Pure Appl. Math., vol. 41, pp. 909-996, Nov. 1988.

44. A. Cohen, I. Daubechies, and J.-C. Feauveau, “Biortbogonal bases of compactly supported wavelets,” Commun. Pure Applied Math., vol. 45,

45. M. Vetterli and C. Herley, “Wavelets and filter hanks: Theory and design,” IEEE Trans. Signal Processing, vol. 40, no. 9, pp. 2207-2232, Sept. 1992.

B. SAMPLE CODE

SAMPLE CODE FOR KMEANS ALGORITHM IN SPATIAL DOMAIN

%%Clear Screen and memory varibles

clc;

clear all;

close all;

%user variable

bs=4;%block size

Nc=16; %no.of codebook vectors (i.e) Codebook Size

Threshold=0.001;

D0=9876543.0;

%read image

[I,colormap]=imread('lena512.bmp');

[imgsize t]=size(I); %height/width of the image (should be square)

imshow(I);

title('Original Image');

tic;

%Split image into m*m blocks

BI=im2col(I,[bs bs],'distinct');

BI=double(BI');

n=size(BI,1);

mm=0;

[idx CB]=kmeans(BI,Nc,'emptyaction','drop','Display','iter','start','uniform');

toc

for i=1:size(idx,1)

RI(i,:)=CB(idx(i),:);

end

disp('Done.');

;

REI=col2im(RI',[bs bs],[imgsize imgsize],'distinct');

imshow(REI,colormap);

title('Decompressed Image');

p=psnr(I,REI,255);

disp('Compressed to : ');

cr=size(CB,1) * size(CB,2)+size(BI,1);

os=size(I,1)*size(I,2);

cr=1-cr/os;

cr

SAMPLE CODE FOR KMEANS ALGORITHM IN WAVELET DOMAIN

clc;

clear all;

close all;

Nc=8; %no.of codebook vectors (i.e) Codebook Size

Threshold=0.001;

D0=9876543.0;

[I,colormap]=imread('zelda256.bmp');

[imgsize t]=size(I); %height/width of the image (should be square)

imshow(I);

title('Original Image');

tic;

T=wpdec2(double(I),2,'db1');

cfs = read(T,'allcfs');

mm=0;

[idx CB]=kmeans(cfs',Nc,'emptyaction','drop','Display','iter','start','uniform');

for i=1:length(CB)

if isnan(CB(i))

CB(i)=0;

end

end

CB1=uint16(CB);

disp('Encoding Please wait............');

compidx=[idx]';

compimg=[CB];

compimg=compimg(:);

% compimg=reshape(compimg,[10 256]);

symbols=unique(compimg);

p=hist(double(symbols),length(symbols));

p=p/sum(p);

% comp=huffmanenco(compimg,p);

[dict,avglen] = huffmandict(symbols,p); % Create dictionary.

comp = huffmanenco(compimg,dict); % Encode the data.

disp('Decoding Please wait............');

dsig = huffmandeco(comp,dict); % Decode the Huffman code.

compidx=[idx]';

compidx=compidx(:);

symbols=unique(compidx);

p=hist(double(symbols),length(symbols));

p=p/sum(p);

[dict,avglen] = huffmandict(symbols,p); % Create dictionary.

compindexs = huffmanenco(compidx,dict); % Encode the data.

[r11 c11]=size(compimg);

[r12 c12]=size(compidx);

disp('Code Book + Index Size :');

disp(r11*c11);

disp(r12*c12);

disp(r11*c11 + r12*c12 );

disp('Bytes');

for i=1:length(idx)

RI(i,:)=CB(idx(i),:);

end

disp('Done.');

;

% REI=col2im(RI',[bs bs],[imgsize imgsize],'distinct');

ri=RI';

rii=cfs2wpt('db1',size(I),tnodes(T),4,ri);

REI=wprec2(rii);

imshow(REI,colormap);

title('Decompressed Image');

p=psnr(I,REI,255);

[h1 w1]=size(I);

[h2 w2]=size(comp);

[h3 w3]=size(compindexs);

%CR=Original/Compressed

disp('Image Compressed to:');

(h2*w2+h3*w3)/8

disp('Bytes');

disp('Compression Ratio');

cr=(h1*w1)/((h2*w2+h3*w3)/8) %%Bytes


Request the removal of this essay...

Struggling?

A custom
essay
can
help...







Need help with your essay?