Image Compression Based On Curvelet Transform

Image Compression Based On Curvelet Transform

1Chandresh K Parmar 2Prof. Kruti Pancholi

1,2Department of Electronics and Communication

L.J. Institute of Engineering and Technology, GTU, Ahmedabad, Gujarat, India

Abstract

This paper illustrates the compression of the various types of images with the Curvelet transform. In this paper image compression is achieved by the Curvelet transform. Curvelet functions represent functions which have discontinuities along straight lines where wavelet functions are not properly worked. The results are compared with the existing wavelet transform technique and the dead zone quantization technique. The performance is evaluated by the performance parameters like Mean square error and PSNR peak signal to Noise ratio of the original image and reconstructed image.

Key words : Image Compression, Curvelet, wavelet transform coding, Encoder, Decoder

1. Introduction

   IMAGE Compression is the technique to reducing the image size without degrading the quality of the Image for better transmission and reduction in storage space

   .due to this reason various techniques are used for image compression , among this for achieving better quality transform based coding is mostly used. Wavelet transform is regarded as a better choice than Fourier transform due to its capability to localize in frequency and time at the same time.[2]

   The wavelet transform is generally used because wavelet represents large class of signals and allows us to find isotropic features occurring at all spatial scales and locations.

   However wavelets are not generally not best option for the natural images because at the edges of images wavelets are not properly finds smoothness. In other words wavelets cannot provide sparse representation of an image at the curve points Because of this some new transform is required to remove this. Curvelet transform is the transform to represent the sparse representation of objects. Curvelet are better than the

   conventional wavelets

   In the wavelet transform there is an inability to represent edge discontinuity along the curves. So to represents the curves in the wavelet domain large number of coefficients are needed. for this reason the there is a new transform required to represent the two dimensional singularities along the curve in sparse domain. This is the reason behind the birth of the Curvelet transform .Here the fundament of Curvelet and wavelet bases are discussed.

   Basically Curvelet transform represents edges and other singularities along the Curvelet much more efficient compared to other transform. Curvelet require only 1/N coefficients to represent the edge of an image.

   The outline of the rest of the paper is as follows. Section II discusses the basic Fundaments of Curvelet transform. Section III explains basic Curvelet Wrapping technique. Section IV discusses the method and algorithm steps and section V discuss the result analysis and Comparison with various popular techniques.

2. Theory of Curvelet Transform

   1. Need for Curvelet transform

      Wavelet transform is useful smooth functions in one dimension. Still Wavelet transform has following Disadvantage Compare to Curvelet transform

      • 2-D line singularities – piecewise smooth signals resembling images have 1-Dimentional Singularities. These smooth regions are separated by edges. Normally edges are discontinuous across the image[1].

      • Lack of shift invariance- these results from the down sampling operation at each level. The wavelet coefficients amplitude varies largely when the input signal is shifted slightly which is explained in detail in [2], [3].

      • Lack of directional selectivity- as the DWT filters are real and separable the DWT cannot

      distinguish between the opposing diagonal directions. This was explained in [4].

      The first problem of the DWT an anisotropic geometric is solved by the first order Curvelet transform which deals with the 2-D line singularities. The second order Curvelet transform deals with the image boundaries and it is very effective in various image processing applications.

      The second and third problems of wavelet transform can be overcome by the fast discrete Curvelet transform which is also called 2D digital Curvelet transform. In which the directional selectivity and shift invariance is improved compare to conventional DWT.

   2. Importance of Curvelet compare to wavelets

      Curvelet will be superior over wavelets in following cases:

      1. This transform is optimally sparse representation of Objects with edges.

      2. This transform is optimal image reconstruction in severely ill-posed problems.

      3. This transform is optimal sparse representation of Wave Propagators.

      The Curvelet represents optimal sparseness for curved punctured smooth images where the image is smooth with the exception of discontinuity of C2 curves.

      Fig 1 Edge Representation in wavelet (left) and Curvelet (Right)

      In 1999 Candes proposed a new multi scale geometric transform-Curvelet transform [8][9][10]. Because of its high anisotropy and multi resolution, Curvelet transform has provided sparse representation of images, especially for the edges with competent handling of curve singularities. Figure 1 demonstrates sparse approximation of Curvelet transform.

      At present Curvelet has developed for two generations. The First generation Curvelet transform is derived from Ridgelet theory and sub band filter theory. the Curvelet decomposition can be stated in

      four stages including sub band decompositioning, smooth partitioning ,renormalization and Ridgelet analysis

      C Continuous Curvelet transform

      The first Curvelet transform [1] used as a complex series of steps involving the Ridgelet analysis of the radon transform of an image. Performance of the Ridgelet transform is very slow. So the use of Ridgelet transform was discarded and thus new method and approach to Curvelet as tight frame is taken using tight frame, an individual Curvelet has frequency support in a parabolic wedge area of the frequency domain.

      In a heuristic argument is made that all Curvelet fall into one of three categories.

      1. The Curvelet coefficient magnitude will be zero. Whose length wise support does not intersect discontinuity.(Fig. 2.a)

      2. A Curvelet whose length-wise support intersects with a Discontinuity, but not at its critical angle. At this point The Curvelet Coefficient magnitude will be close to zero. (Fig.2.b)

      3. A Curvelet whose length-wise support intersects with a Discontinuity, at there the Curvelet coefficient magnitude will be much larger than zero. (Fig. 2.c) Discrete Curvelet transform

      The second generation Curvelet transform has two

      different implementation: Curvelet via USFFT( Unequally spaced Fast Fourier transform) and frequency wrapping. Both of this Curvelet are simpler, faster and less redundant compare to first generation Curvelet (Ridgelet transform).In this work Curvelet based on frequency wrapping technique is used.

      Fig 3. Curvelet in Fourier Frequency domain (left) and Spatial domain (right).

      Figure 3 shows the division of wedges of the Fourier frequency plane in its left image; the right side image represents Curvelet in spatial Cartesian grid associated with a given scale and orientation.

      Basically multi resolution discrete Curvelet transform have the advantage of FFT (Fast Fourier transform).during the FFT both the image and the Curvelet at a given scale and orentation are transformed into the Fast Fourier domain. In the spatial domain the convolution of the Curvelet transform becomes product in their Fourier domain. Curvelet coefficients are obtained by applying inverse FFT to the spectral product after the end of the whole computation process.

      Fig.4 (a) Digital Curvelet in frequency Domain (b) support of wedge before wrapping (c) support of wedge after wrapping.

      All the coefficients of the scale and orientation are in ascending order .Inverse FFT cannot be applied on the obtained frequency spectrum because the frequency response of a Curvelet is a trapezoidal wedge which needs to be wrapped into a rectangular support to

      perform the inverse Fourier transform. The Frequency wrapping of this trapezoidal wedge which needs to be wrapped into a rectangular support to perform the inverse Fourier domain. The wrapping of this trapezoidal wedge is done by periodically tilting the spectrum inside the wedge and then collecting the rectangular coefficients area in the origin. Due to this periodic tilting the rectangular region collects the wedges corresponding fragmented portions from the surrounding parallelograms. For this wedge wrapping process, this approach of Curvelet transform is known as the wrapping based Curvelet transform

      D. Wrapping Based algorithm for Discrete Curvelet transform

      On the base of the Curvelet transform theory two methods are obtained to get the Curvelet coefficients, USFFT (unequal space fast Fourier transform) in which the coefficients are obtained by irregularly sampling of the Fourier sampling of an image.

      The second method is the wrapping technique in which series of translation and wrap around the technique the coefficients are obtained. Both the algorithm have the same output but the wrapping based algorithm have faster computation time because of this the second method is ignored in this paper.

      Steps for the Curvelet wrapping based method Step 1: Fast Fourier transform (FFT) is applied to the input image.

      Step 2: Curvelet are obtained at given scale s and orientation n

      Step3 : divide the FFT into the digitally small sets Step 4:for every set each set is translated to origin Step5 wrap the parallogram shaped small set to rectangular shaped center at the origin.

      Step 6.take the inverse of the FFT and add the Curvelet arrays into collections of Curvelet coefficients

      Steps for inverse Curvelet wrapping based method Steps 1; For each Curvelet coefficient array inverse FFT of the array is obtained.

      Step2: inverse process is applied to unwrap the rectangular support to the original orientation shape. Step 3: shape is translated to its original position.\ Step 4: the entire Curvelet array are stored

      Step 5: all the stored translated Curvelet array are added

      Step 6 inverse FFT is taken to reconstruct the image.

3. ALGORITHM

   Algorithm Flow for the image compression is given below.

   Step 1. First of all the image is read from the user Step 2 the input image is then decomposed into the Curvelet transform

   Step 3 for the decomposition the 3 level decomposition is used and the Curvelet coefficients are obtained from the discrete Curvelet wrapping technique.

   Step 4 The Curvelet coefficients values are quantized so that the approximate values are obtained from the proper quantization.

   Step 5 after the quantization process the thresholding is applied in which the thresholding value is initially set and the coefficients value below the threshold is neglected and above the threshold is maintained.

   Step 6 after the thresholding the Curvelet coefficients above the threshold values are calculated

   Step7 on the base of the Curvelet coefficients the inverse Curvelet transform is obtained

   Step8 inverse wrapping based algorithm is applied to achieve the inverse Curvelet transform.

   Step9 image is reconstructed from the inverse Curvelet transform

   Step 10 performance parameters related to the image compression are calculated.

4. Results and Comparison

   Compression Ratio: it is a term used to quantify the reduction in the image representation size which is generated by the image compression algorithm; this term is defined by as a ratio of uncompressed image size and the compressed image size.

   Compression Ratio = uncompressed image size/compressed image size

   MSE (mean square error) it is calculated by averaging the squared error between the reconstructed image and original image. The MSE error is calculated as

   MSE = 1/MN[y (i, j) \ y (i, j)]2

   Where the M,N are the dimension of the image and MXN is the size of the image. y(i,j) is the original image and y^ (i,j) is reconstructed image. In this assuming gray scale image 8bits per pixel then PSNR (Peak signal to noise ratio) is defined as

   Algorithm coding is tested on standard images have a size of 512X512. The images are shown below.

   Images	Mean Square Error		PSNR
   	Wavelet	Curvelet	Wavelet	Curvelet
   Lena	9.6621	8.6013	25.4711	28.4238
   Friends	10.2647	9.2412	27.9039	29.8612
   Boat	8.5531	9.5885	26.6123	28.4957
   Barbara	13.7963	12.5221	25.2512	25.3356
   Pepper	7.9010	8.9321	28.3923	30.1718

   Table 1. Simulation Results

   The results shown in the table 1 clearly identify that Curvelet transform gives better PSNR ratio compared to conventional Wavelet transform.

5. Conclusion and Future Work

   In this paper, we have purposed a new method of image compression algorithm based on the second order Curvelet transform coding. in this paper we compressed the standard images with this algorithm and the simulation results shows that this compression algorithm shows better performance compared to conventional transform techniques. The results can be improved by using proper threshold value and proper quantization method. This work inspire to study further in image compression using Curvelet transform.

   Simulation Result

   1. Friends.jpg

   2. Barbara.jpg 512X512

   (c ) boat.bmp

   Figure 5. Simulation results

6. Reference

1. Candes E.J., Laurent Demanet, Donoho D.L., Lexing Ying (2005) Fast Discrete Curvelet Transforms, Stanford University Press Notes

2. Cand`es E. J. and Donoho D. L. (2000) Curvelets, a surprisingly editors, effective non-adaptive representation for objects with edges, In C. Rabut

   1. Cohen and L. L. Schumaker, Curves and Surfaces, 105120, Vanderbilt University Press.

3. Mansoor, A.; Mansoor, A.B.; On Image Compression using Digital Curvelet Transform, 9thInternational Multitopic Conference, Page(s): 1

   4, IEEE INMIC 2005.

4. E. Candès and L. Demanet, The curvelet representation of wave propagators is optimally sparse, Commun. Pure Appl. Math., vol. 58, no. 11, pp. 14721528, 2005.

5. E.J. Candes, D.L. Donoho, Curvelets A surprisingly effective nonadaptive representation for objects with edges, Curve and Surface Fitting, Vanderbilt Univ.Press 1999.

6. E.J. Candes, D.L. Donahue, New Tight Frames of Curvelets and Optimal Representations of Objects with Smooth Singularities, Technical Report, Stanford University, 2003.

7. Emmanuel Cand`es, Laurent Demanet, David Donoho and Lexing Ying. Fast Discrete Curvelet Transform, Jul 2005.

8. B.S. Kashin, V.N. Temlyakov,On best m-term approimations and the entropy of sets in the space L1 Mathematical Notes 56, 1137-1157, 1994.

9. N. Kingsbury, Complex wavelets for shift invariant analysis and altering of signals, Appl.Comput. Harmon. Anal., 10 (3), 234-253 (2001).