An Approach On Image Compression Technique In Multi Resolution Using Wavelets And Fractals Transforms

An Approach On Image Compression Technique In Multi Resolution Using Wavelets And Fractals Transforms

Ravi Mathey1 , Prof.P.S.Avadhani 2

1Associate Professor and HOD CSE, Vidya Jyothi Institute of Technology, Hyderabad, India

2 Professor, Department Of Computer Science & Systems Engineering, College Of Engineering Andhra University, Visakhapatnam ,India

Abstract:

The proposed multi resolution fractals coders are image compression schemes that combine wavelets and fractals transforms. They improve the performance of conventional fractal compression algorithms. They reduce the characteristics distortions of fractal algorithms: blocking artifacts and image blurring, by better coding of high frequencies. The main idea behind all fractal algorithms is to exploit the similarities present within many natural images: one block image is represented by an affine transform of larger block taken from the image it self .The characteristics property of fractal coders is to exploit similarities between scales. Wavelets transforms perform Multiresolution decompositions of images ,i.e decomposition of the originals images into sub images at different scales

.The translation of the fractal property in the wavelets transforms domain is straightforward .Multiresolution decomposition through wavelets transform of fractals coded images reveal strong relationships limit the frequency content .Multiresolution fractals coders introduces degrees of freedom on these constraints The research is includes other extensions of the Multiresolution fractal coders are wavelet transform and fractals are wavelet transform. The Multiresolution fractals codes present all the advantages the conventional fractals coders. Good reconstructed image quality are obtained with multi resolution fractals coders at very low bit rates where they outperformed the JPEG standard algorithm ,both in terms of PSNR and direct visual evolution .Image obtained with the multiresolution fractals schemes are more natural looking than those coded with JPEG.

Keywords: Multi resolution, wavelets transforms, fractals transforms

1. INTRODUCTION

   In the early 1980s, the wavelet transform was studied theoretically in geophysics and mathematics by Morlet,

   Grossman and Meyer. In the late 1980s, links with digital signal processing were pursued by Daubechies

   and Mallat, thereby putting wavelets firmly into the application domain.

   The Fourier transform is a tool widely used for many scientific purposes, and it will serve as a basis for another introduction to the wavelet transform A range of very different ideas have been used to formulate the human ability to view and comprehend phenomena on different scales. Wavelet and other multiscale transforms Data classification may be carried out using hierarchical classification. A sequence of agglomerative steps is used, merging data objects into a new cluster at each step. There is a fixed number of total operations in this case. Such an approach is bottom-up, starting with the set of data objects, considered independently. Spatial and other constraints may be incorporated, to provide segmentation or regionalization methods. This approach is combinatorial since neither continuous data values, nor stochasticity, are presupposed An image represents an important class of data structures. Data objects may be taken as pixels, but it is more meaningful for image interpretation if we try, in some appropriate way, to take regions of the image as the data objects. Such regions may be approximate. One approach is to recursively divide the image into smaller regions. Such regions may be square or rectangular, to facilitate general implementation. Decomposition halts whenever a node meets a homogeneity criterion, based on the pixel values or gray-levels within the corresponding image region. A pyramid is a set of successively smoothed and down sampled versions of the original image. A wavelet is a localized function of mean zero. Wavelet transforms often incorporate a pyramidal representation of the result Wavelet transforms are computationally efficient, and part of the reason for this is that the scaling or wavelet function used is often of compact support, i.e. defined on a limited and finite domain. Wavelets also usually allow exact reconstitution of the original data. A sufficient condition for this in the case of the continuous wavelet

   transform is that the wavelet coefficients, which allow reconstitution, are of zero mean. Wavelet functions are often wave-like but clipped to a finite domain

   .Compared to other methods the wavelet transform can be determined very efficiently. Unlike scale-space filtering, it can introduce artifacts. To limit the retrograde impact of these, we may wish to develop other similar multiscale methods, with specific desirable properties. The choice of method to apply in practice is a function of the problem, and quite often of the properties of the signal.

   The proposed multi resolution fractals coders are image compression schemes that combine wavelets and fractals transforms. They improve the performance of conventional fractal compression algorithms The main idea behind all fractal algorithms is to exploit the similarities present within many natural images Wavelets transforms perform Multiresolution decompositions of images ,i.e decomposition of the originals images into sub images at different scales

   .The translation of the fractal property in the wavelets transforms domain is straightforward .Multiresolution decomposition through wavelets transform of fractals coded images reveal strong relationships limit the frequency content .Multiresolution fractals coders introduces degrees of freedom on these constraints The proposed paper is includes other extensions of the Multiresolution fractal coders are wavelet transform and fractals are wavelet transform. The Multiresolution fractals codes present all the advantages the conventional fractals coders and propose solution to some of the drawbacks.Multiresolution fractals schemes are defined by many parameters: wavelet basis, number of bands and cut-off frequencies in the frequency decomposition, range block sizes. A thorough study still has to be performed to determine the parameters values yielding to the smallest image distortions for a target bit rate. Good reconstructed image quality are obtained with multiresolution fractals coders at very low bit rates where they outperformed the JPEG standard algorithm ,both in terms of PSNR and direct visual evolution .Image obtained with the multiresolution fractals schemes are more natural looking than those coded with JPEG. However coding of the low-pass components of image blocks with the JPEG standard is very efficient .The high pass components of the multiresolution coders are may be incorporated in the JPEG schemes for better coding of high frequency components of JPEG images

   .Alternatively ,the low pass components of the multiresolution fractals coders may be replaced by any other compression schemes that performs well on low resolution images.

2. .Wavelet transform and Fourier transform

Wavelet transform (WT) represents an image as a sum of wavelet functions with different locations and scales

.Any decomposition of an image into wavelets involves a pair of waveforms: one to represent the high frequencies corresponding to the detailed parts of an image (wavelet function) and one for the low frequencies or smooth parts of an image (scaling function).

Fig 2.1: wavelet Transform

Fig.2. 1 shows two waveforms of a family discovered in the late 1980s by Daubechies: the right one can be used to represent detailed parts of the image and the left one to represent smooth parts of the image. The two waveforms are translated and scaled on the time axis to produce a set of wavelet functions at different locations and on different scales. Each wavelet contains the same number of cycles, such that, as the frequency reduces, the wavelet gets longer. High frequencies are transformed with short functions (low scale). Low frequencies are transformed with long functions (high scale). During computation, the analyzing wavelet is shifted over the full domain of the analyzed function. The result of WT is a set of wavelet coefficients, which measure the contribution of the wavelets at these locations and scales.

Wavelets can be introduced in different ways. In the following we can think of our input data as a time-varying signal. If discretely sampled, this amounts to considering an input vector of values. The input data may be sampled at discrete wavelength values, yielding a spectrum, or one dimensional image. A two- dimensional, or more complicated input image, can be fed to the analysis engine as a rasterized data stream. Analysis of such a two-dimensional image may be carried out independently on each dimension. Without undue loss of generality, we will now consider each input to be a continuous signal or a discrete vector of values. In the continuous wavelet transform, the input signal is correlated with an analyzing continuous wavelet. The latter is a function of two parameters, scale and position. An admissibility condition is required, so that the original signal can be reconstituted from its wavelet transform. In practice, some discrete version of this continuous transform will be used. A

later section will give definitions and will examine the continuous wavelet transform in more detail. The widely-used Fourier transform maps the input data into a new space, the basis functions of which are sines and cosines. Such basis functions extend to + and , which suggests that Fourier analysis is appropriate for signals which are similarly defined on this infinite range, or which can be assumed to be periodic. The wavelet transform maps the input data into a new space, the basis functions of which are quite localized in space. They are usually of compact support. The term

wavelet arose as a localized wave-like function. Wavelets are localized in frequency as well as space,

i.e. their rate of variation is restricted. Fourier analysis is not local in space, but is local in frequency. Fourier analysis is unique, but wavelet analysis is not: there are many possible sets of wavelets which one can choose. One trade-off between different wavelet sets is between their compactness versus their smoothness. Compactness has implications for computational complexity: while the Fast Fourier Transform (FFT) has computational complexity O(n log n) for n-valued inputs, the wavelet transform is often more efficient, O(n). Another point of view on the wavelet transform is by means of filter banks. The filtering of the input signal is some transformation of it, e.g. a low-pass filter, or convolution with a smoothing function. Low pass and high-pass filters are both considered in the wavelet transform, and their complementary use provides signal analysis and synthesis. The Fourier transform is a tool widely used for many scientific purposes, and it will serve as a basis for another introduction to the wavelet transform. For the present, we assume a time-varying signal. Generalization to any x as independent variable, or image pixels (x, y), in the place of time t, is immediate. The Fourier transform is well suited only to the study of stationary signals where all frequencies have an infinite coherence time, or otherwise expressed the signals statistical properties do not change over time. Fourier analysis is based on global information which is not adequate for the study of compact or local patterns.

Fourier analysis uses basis functions consisting of sine and cosine functions. These are time- independent. Hence the description of the signal provided by Fourier analysis is purely in the frequency domain. Music, or the voice, however, impart information in both the time and the frequency domain. The windowed Fourier transform, and the wavelet transform, aim at an analysis of both time and frequency. For non-stationary analysis, a windowed Fourier transform (STFT, short time Fourier transform) can be used. introduced a local Fourier analysis, taking into account a sliding Gaussian window. Such approaches provide tools for investigating time as well

as frequency. Stationarity is assumed within the window. The smaller the window size, the better the time-resolution. However the smaller the window size also, the more the number of discrete frequencies which can be represented in the frequency domain will be reduced, and therefore the more weakened will be the discrimination-potential among frequencies

2.1 Applications of the wavelet transform

The some of applications of wavelet transform are:

The human visual interpretation system does a good job at taking scales of a phenomenon or scene into account simultaneously. A wavelet or other multiscale transform may help us with visualizing image or other data. A decomposition into different resolution scales may open up, or lay bare, faint phenomena which are part of what is under investigation. In capturing a view of multilayered reality in an image, we are also picking up noise at different levels. Therefore, in trying to specify what noise in an image is, we may find it effective to look for noise in a range of resolution levels. Such a strategy has proven quite successful in practice. Noise of course is pivotal for the effective operation of, or even selection of, analysis methods. Image deblurring, or disconsolation or restoration would be trivially solved, were it not for the difficulties posed by noise. Image compression would also be easy, were it not for the presence of what is by definition non-compressible, i.e. noise. Image or data filtering may take different forms. For instance, we may wish to prioritize the high-frequency (rapidly-varying) parts of the image, and de-emphasize the low-frequency (smoother) parts of the image. Or, alternatively, we may wish to separate noise as far as possible from real image signal. In the latter case, we may wish to

protect important parts of the image from the slightest alteration. An image may contain smooth and sharp features. We may need to consider a trade-off in quality between results obtained for such types of features. Introducing an entropy constraint in the image analysis procedure is one way to do this. This comes under the general heading of regularization. An image analysis often is directed towards particular objects, or object classes, contained in the image. Template matching is the seeking of patterns which match a query pattern. A catalog or inventory of all objects may be used to facilitate later querying. Content-based queries may need to be supported, based on an image database. Image registration involves matching parts of images taken with different detectors, or taken at different times. A top-down approach to this problem is offered by a multiscale approach: the crudest, most evident, features are matched first; followed by increasingly better resolved features. In the analysis of multivariate data, we integrate the wavelet transform with methods

such as cluster analysis, neural networks and (supervised and unsupervised) pattern recognition. In all of these applications, efficiency and effectiveness (or quality of the result) is important. Varied application fields come immediately to mind: astronomy, remote sensing, medicine, industrial vision, and so on. All told, there are many and varied applications for the methods described in this book. Based on the description of many applications, we aim to arm the reader well for tackling other similar applications. Clearly this objective holds too for tackling new and challengng applications.

3. Multi resolution

Fractal T performs multi resolution image analysis. The result of multi resolution analysis is simultaneous image representation on different resolution (and quality) levels . The resolution is determined by a threshold below which all fluctuations or details are ignored. The difference between two neighboring resolutions represents details. Therefore, an image can be represented by a low-resolution image (approximation or average part) and the details on each higher resolution level. Let us consider a one- dimensional (1-D) function f(t). At the resolution j level, the approximation of the function. The intuition behind using lossy compression for denoising may be explained as follows. A signal typically has structural correlations that a good coder can exploit to yield a concise representation. White noise, however, does not have structural redundancies and thus is not easily compressible. Hence, a good compression method can provide a suitable model for distinguishing between signal and noise. The discussion will be restricted to wavelet-based coders, though these insights can be extended to other transform domain coders as well. A concrete connection between lossy compression and denoising can easily be seen when one examines the similarity between thresholding and quantization, the latter of which is a necessary step in a practical lossy coder. That is, the quantization of wavelet coefficients with a zero-zone is an approximation to the thresholding function (see Fig. 2.1). Thus, provided that the quantization outside of the zero-zone does not introduce significant distortion, it follows that wavelet- based lossy compression achieves denoising. With this connection in mind, the threshold choice aids the lossy coder to choose its zero-zone, and the resulting coder achieves simultaneous denoising and compression if such property is desired.

The multi resolution support of an image describes in a logical or boolean way whether an image I contains information at a given scale j and at a given position (x, y). If M(I)(j, x, y) = 1 (or true), then I contains

information at scale j and at the position (x, y).M depends on several parameters:

• The input image.

• The algorithm used for the multiresolution decomposition.

• The noise.

• All constraints we want the support additionally to satisfy.

Such a support results from the data, the treatment (noise estimation, etc.), and from knowledge on our part of the objects contained in the data (size of objects, alignment, etc).

The wavelet transform of an image by an algorithm such as the `a trous one produces a set {wj} at each scale j. This has the same number of pixels as the image. The original image c0 can be expressed as the sum of all the wavelet planes and the smoothed array cp and a pixel at position x, y can be expressed also as the sum over all the wavelet coefficients at this position, plus the smoothed array. The multi resolution support will be obtained by detecting at each scale the significant coefficients. The multi resolution support is defined by:

M(j, x, y) =1 if wj(x, y) is significant

0 if wj(x, y) is not significant

3.1. Algorithm:

The algorithm to create the multiresolution support is as follows:

1. We compute the wavelet transform of the image.

2. We estimate the noise standard deviation at each scale. We deduce the statistically significant level at each scale.

3. The binarization of each scale leads to the multiresolution support.

4. Modification using a priori knowledge (if desired).

The multiresolution support allows us to integrate, in a visualizable manner, and in a way which is very suitable for ancillary image alteration, information coming from data, knowledge, and processing.

1. Related work:

   Image Processing is defined as analyzing and manipulating images. Image Compression has become the most recent emerging trend throughout the world. Some of the common advantages image compressions over the internet are reduction in time of webpage uploading and downloading and lesser storage space in terms of bandwidth. Compressed images also make it possible to view more images in a shorter period of time .Image compression is essential

   where images need to be stored, transmitted or viewed quickly and efficiently. The benefits can be classified under two ways as

   follows: First, even uncompressed raw images can be stored and transmitted easily. Secondly, compression provides better resources for transmission and storage. Image compression is the representation of image in a digitized form with a few bits maintenance only allowing acceptable level of image quality. Compression addresses the problem of reducing the amount of data required to represent a digital image. A good compression scheme is always composed of many compression methods namely wavelet transformation, predicative coding, and vector quantization and so on. Wavelet transformation is an essential coding technique for both spatial and frequency domains, where it is used to divide the information of an image into approximation and detail sub signals . Artificial Neural Networks (ANN) is also used for image compression. It is a system where many algorithms are used.

   Wavelet analysis is based on a decomposition of a signal using an orthonormal family of basic functions

   .Wavelets are well suited for the analysis of transient and time-varying signals . The wavelet transform has been developed as an alternate approach to Short Time Fourier transform to overcome the resolution problem. The wavelets transform is computed separately for different segments of the time domain signal at different frequencies. This approach is called Multi resolution analysis, as it analyzes the signal at different frequencies giving different resolutions.

   The constraints imposed on images by fractal coders do not exist within original images. The formulation of the fractal property in the Haar wavelet transform domain is thus modified to improve the conventional fractal algorithm. A new fractal coder is implemented: high frequencies are better rendered if two different fractal transforms are used inside the algorithm. The wavelet transform is applied once to the original image, yielding to a low resolution image and three detail images. These three detail images are recombined to obtain a high-pass image. The low-resolution image one fourth the original size, is coded with a first fractal code. The image obtained after iteration of this fractal code from any original image is used to compute a second fractal code to represent the high-pass original image. At the decoder, the reconstructed image is the combination of the low-resolution image obtained with the first fractal code and the detail image obtained with the second fractal code. The modification of the fractal coding algorithm may be generalized to any kind of frequency

   decomposition. The generalized multi resolution fractal coder is decomposed into two steps. First, a wavelet transform is applied to the original image. Two subimages are obtained, a low resolution one and a detail one. For the low-resolution image a first fractal code is computed. For the detail subimage, a second fractal code is derived using information from the image obtained with the first fractal code. The decoding part iterates the first fractal code to construct an approximation of the low-resolution subimage. From this image and the second fractal code, an approximation of the detail subimage is reconstructed. The coded image is obtained by a combination of these sub images using an inverse wavelet transform

2. Results and evaluation:

Multiresolution fractal schemes are defined by many parameters: wavelet basis, number of bands and cut-off frequencies in the frequency decomposition, range block sizes. A thorough study still has to be performed to determine the parametersvalues yielding to the smallest image distortions for a target bit rate. Good reconstructed image quality are obtained with multiresolution fractal coders at very low bit rates where they outperformed the JPEG standard algorithm, both in terms of PSNR and direct visual evaluation. Images obtained with the multiresolution fractal schemes are more natural-looking than those coded with JPEG. However, coding of the low-pass components of image blocks with the JPEG standard is very efficient. The high-pass component of the multiresolution coders may be incorporated in the JPEG scheme for a better coding of high frequency components of JPEG images. Alternatively, the low pass component of the multiresolution fractal coders may be replaced by any other compression schemes that perform well on low resolution images.

Figures below shows Baboon image (512 . 512): (a) original image, (b) fractal algorithm (PSNR = 17.87 dB, 0.016 bpp), multiresolution fractal coder

(a)original Image

(b) Multi resolution fractal coder

Future scope:

Future work includes other extensions of the multiresolution fractal coders. The two basis blocks of multiresolution fractal coders are wavelet transform and fractal transform. Only separable wavelets have been considered, either orthonormal or bi-orthogonal. Other multiresolution decomposition schemes may considered non-separable wavelets. The implemented fractal algorithm may also be improved to take into account domain block isometries or recursive splitting of range blocks .

1. CONCLUSION:

   Multiresolution fractal coders present all the advantages of conventional fractal coders and propose solutions to some of their drawbacks. Image quality of reconstructed images is good, even for very low bit rates. The characteristic distortions of fractal coders are reduced: blocking artifacts are less annoying, images are less blurred. For the implemented conventional fractal coder, the achievable bit rates are very limited. This range is drastically increased with the multiresolution coders. Since successive steps of the multiresolution fractal coders correspond to more and more details, these algorithms may be incorporated in a hierarchical scheme and progressive transmission to adapt to time-varying channel or display resources.

2. References

[1].F. C. Cesbron and F. J. Malassenet, Wavelet and fractal transforms for image compression, in Fractals in Engineering. From Theory to Industrial Applications (J. L. Vehel, E. Lutton, and C. Tricot, eds.), pp. 32938, Springer Verlag, 1997.

1. E. Yuval Fisher, Fractal Image Compression: Theory and Application. Springer-Verlag, 1994.

2. F. C. Cesbron and F. J. Malassenet, Multiresolution fractal coding of still images, in International Conference on Signal Processing Applications and Technology, ICSPAT, Boston, USA, Oct. 1996.

3. F. Argoul, A. Arn´eodo, G. Grasseau, Y. Gagne, E.

   J. Hopfinger and U. Frisch, 1989. Wavelet analysis of turbulence reveals the multifractal nature of the Richardson cascade. Nature, 338, 5153.

4. A. Azzalini, M. Farge and K. Schneider, 2005. Nonlinear wavelet thresholding : A recursive method to determine the optimal denoising threshold. Appl. Comput. Harm. Analysis, 18 (2), 177185.

5. R. Balian, 1981. Un principe dincertitude en th´eorie du signal ou en m´ecanique quantique.

C.R.A.S. Paris, 292, srie 2, 13571361

[7].M. Barnsley and L. Hurd, Fractal Image Compression, Wellesley, MA : AK peters, 1993

1. A. E. Jacquin, A fractal theory of iterated Markov operators with applications to digital image coding, Ph.D. dissertation, Georgia Institute of Technology,

   Atlanta, GA, Aug. 1989

2. M. Barnsley, Fractals Everywhere, San Diego, CA: Academic, 1988.

3. D. M. Monro and F. Dudbridge, Fractal Approximation of image blocks, in Proc. Int. Conf. Acoust., speech, Signal Processing 92, vol. III, San Francisco, Ca, Mar. 1992, pp. 485-488.

Authors Information

1 Ravi Mathey is a post- graduate specialized in Computer Science from BIT – Ranchi and he did Instrumentation technology in Andhra university. He has more than 18 years of experience in Research and Development, Presently he is working as a Associate Professor and HOD of

CSE Department at Vidya Jyothi Institute of Technology (VJIT). His area of research is wireless embedded application and image compression techniques by using fractals and wavelets.

2.Prof. P.S.Avadhani did his Masters Degree and PhD from IIT, Kanpur. He is presently working as Professor in Dept. of Computer Science and Systems Engineering in Andhra University college of Engg., in Visakhapatnam. He has more than 50 papers published in various National / International journals and conferences. His research areas include Cryptography, Data Security, Algorithms, and Computer Graphics, Digital Forensics