Lifting Based 3-D Discrete Wavelet Transform for Optimized Image Compression

Lifting Based 3-D Discrete Wavelet Transform for Optimized Image Compression

Vol. 1 Issue 9, November- 2012

J. Satheesh D. P. Raju

Assistant professor

Dept. of Electronics & communication engineering, Dept. of Electronics & communication engineering Kaushik College Of Engineering Kaushik College Of Engineering

ABSTRACT

The lifting scheme based running 3-D discrete wavelet transform (DWT), which is a powerful image and video compression algorithm. The design is one of the lifting based complete 3-D DWT architectures without group of pictures restrictions. The new computing technique based on analysis of lifting signal flow graph minimizes the storage requirement. This architecture enjoys reduces memory and low power consumption, low latency, and throughput compared to those of earlier reported works.

KEYWORDS Descrete wavelet transform, image compression, lifting, video, VLSI architecture

I.INTRODUCTION

1. Wavelet Definition

   A wavelet is a small wave which has its energy concentrated in time. It has an oscillating wavelike characteristic but also has the ability to allow simultaneous time and frequency analysis and it is a suitable tool for transient, non- stationary or time-varying phenomena.

   a)

   b)

   Fig.1. a) wave b) wavelet

2. Wavelet Characteristics

   The difference between wave (sinusoids) and wavelet is shown in figure 1 Waves are smooth, predictable and everlasting, whereas wavelets are of limited duration, irregular and may be asymmetric. Waves are used as deterministic basis functions in Fourier analysis for the expansion of functions (signals), which are time-invariant, or stationary. The important characteristic of wavelets is that they can serve as deterministic or non-deterministic basis for generation and analysis of the most natural signals to provide better time-frequency representation, which is not possible with waves using conventional Fourier analysis.

3. What is discrete wavelet transform?

   Discrete wavelet transform (DWT), which transforms a discrete time signal to a discrete wavelet representation

4. Why discrete wavelet transform?

The wavelet transform has gained widespread acceptance in signal processing and image compression. Because of their inherent multi-resolution nature, wavelet-coding schemes are especially suitable for applications where scalability and tolerable degradation are important.

1. TYPES OF TRANSFORMS

   1. Fourier Transform (FT):

      Fourier transform is a well-known mathematical tool to transform time-domain signal to frequency-domain for efficient extraction of information and it is reversible also. For a signal x(t), the FT is given by

      Though FT has a great ability to capture signals frequency content as long as x(t) is composed of few stationary components (e.g. sine waves). However, any abrupt change in time for non- stationary signal x(t) is spread out over the whole frequency axis in X(f). Hence the time-domain signal sampled with Dirac-delta function is highly localized in time but spills over entire frequency band and vice versa. The limitation of FT is that it cannot offer both time and frequency localization of a signal at the same time.

   2. Short Time Fourier Transform (STFT):

      To overcome the limitations of the standard FT, Gabor introduced the initial concept of Short Time Fourier Transform (STFT). The advantage of STFT is that it uses an arbitrary but fixed-length window g(t) for analysis, over which the actual non-stationary signal is assumed to be approximately stationary. The STFT decomposes such a pseudo-stationary signal x(t) into a two dimensional time-frequency representation S( , f) using that sliding window g(t) at different times . Thus the FT of windowed signal x(t) g*(t-) yields STFT as

   3. Wavelet Transform (WT):

      Fixed resolution limitation of STFT can be resolved by letting the resolution in time- frequency plane in order to obtain Multi resolution analysis. The Wavelet Transform (WT) in its continuous (CWT) form provides a flexible time- frequency, which narrows when observing high frequency phenomena and widens when analyzing low frequency behavior. Thus time resolution becomes arbitrarily good at high frequencies, while the frequency resolution becomes arbitrarily good at low frequencies. This kind of analysis is suitable for signals composed of high frequency components with short duration and low frequency components with long duration, which is often the case in practical situations.

   4. Discrete Wavelet Transform:

      The Discrete Wavelet Transform (DWT) is a popular signal processing technique best known for its results in data compression. As hardware designers, we are concerned more with the algorithmic details of the DWT, rather than the mathematical details discussed in the many papers

      which provide the foundationVsol. 1foIsrsue w9, Navoveelmebtesr.- 2012 Algorithmically, the DWT is a recursive filtering process. At each level, the input data is filtered

      by two related filters to produce two result data- streams. These data-streams are then sub samples by two (or decimated) to reduce the output to the same number of data-words as the original signal. The low-pass filter output of this result is then further processed by the same two filters, and this continues recursively for the desired depth or until no further filtering can occur. This recursive filtering process of the one-dimensional DWT is shown in Figure 2, where z is the input data- stream, a and d are approximation (low-pass filter output) and difference (high-pass filter output) data-streams respectively. The subscript values show the level of output.

      Fig.2.The 1-DWT filtering process

   5. Inverse discrete wavelet transform:

   The inverse DWT (IDWT) is the computational reverse. The lowest low-pass and high pass data- streams are up-sampled (ie. a zero is placed between each data-word) and then filtered using filters related to the decomposition filters. The two resulting streams are simply added together to form the low-pass result of the previous level of processing. This can be combined with the high- pass result in a similar fashion to produce further levels, the process continuing until the original data-stream is reconstructed. This process is shown in figure 3

   Fig.3. The Inverse DWT filtering process.

   Lossy:

   Vol. 1 Issue 9, November- 2012

   Discards components of the signal that are

   Fig.4. 2-D DWT for image

   Fig.5.One- level 3D DWT structure

2. IMAGE COMPRESSION

   1. What is an image?

      An image (from Latin imago) or picture is an artifact, usually 2-Dimentional,that has a similar appearance to some object or person.

   2. What is an image compression?

      Image compression is minimizing the size in bytes of data without degrading the quality of the image to an acceptable level.

   3. Types of compressions:

   There are two types of compressions

   Lossless:

   Digitally identical to the original image. Only achieve a modest amount of compression. Lossless compression involve with compressing data, when decompressed data will an exact replica of the original data. This is the case when binary data such as executable are compressed.

   known to be redundant. Signal is therefore changed from input. Lossy compression is again divided into two types based on the human perception of identifying the loss in image afte the compression and decompression is done.

3. LIFTING SCHEME

   Lifting scheme of DWT has been recognized as a faster and efficient approach. The standard wavelet compression techniques, even if loss-less in principle, do not construct exactly the original image because of the rounding of the floating point wavelet coefficients to integers caused by the coding. The use of the lifting scheme allows to generate truly loss-less non- linear integer-to-integer wavelet transforms. (9,7)DWT-lossy transformation filter coefficients

   	Irrational value	Rational value
   	-1.5861343	-3/2
   	-0.0529801…	-1/16
   	0.88281107…	4/5
   	0.44350685	15/32
   	1.14960439	42/5

   The lifting scheme: split, predict, update and scale phases

   Fig.6. lifting scheme

   The wavelet lifting scheme is a method for decomposing wavelet transforms into a set of stages.

   The lifting scheme consists of 3 steps. They are:

   Split step:

   Its divides the input data into odd and even elements.

   Predict step:

   frequency components. This

   Vporlo. 1cIesssuse 9, cNaonvembbere- 2012

   It predicts the odd elements from the even elements. The even samples are multiplied by the time domain equivalent and are added to the odd samples.

   Update step:

   This step replace the even elements with an average. The updated odd samples are multiplied by the time domain equivalent and are added to the even samples.

   The lifting scheme is new approach to construct so called second generation wavelets i.e. wavelets which are not necessarily translations and dilations of one function. Lifting scheme allows for an in place computation. Another feature of lifting scheme is that all constructions are derived in the spatial domain. This is in contrast to the traditional approach, which relies heavily on the frequency domain.

   Fig.7. lifting scheme second generation

4. DISCRETE WAVELET TRANSFORM

1. One dimensional DWT :

   Any signal is first applied to a pair of low- pass and high-pass filters. Then down sampling (i.e., neglecting the alternate coefficients) is applied to these filtered coefficients. The filter pair (h, g) which is used for decomposition is called analysis filter-bank and the filter pair which is used for reconstruction of the signal is called synthesis filter bank.(g`, h`).The output of the low pass filter after down sampling contains low frequency components of the signal which is approximate part of the original signal and the output of the high pass filter after down sampling contains the high frequency components which are called details (i.e., highly textured parts like edges) of the original signal.

   This approximate part can still be further decomposed into low frequency and high

   continued successively to the required number of levels. This process is called multi level decomposition, shown in Figure 8

   Fig.8. One dimensional two level wavelet decomposition

   In reconstruction process, these approximate and detail coefficients are first up- sampled and then applied to low-pass and high- pass reconstruction filters. These filtered coefficients are then added to get the reconstructed version of the original image. This process can be extended to multi level reconstruction i.e., the approximate coefficients to this block may have been formed from pairs of approximate and detail coefficients. Shown in Figure 9

   Fig.9. One dimensional inverse wavelet transforms

2. Two-Dimensional DWT :

   One dimensional DWT can be easily extended to two dimensions which can be used for the transformation of two dimensional images. A two dimensional digital image which can be represented by a 2-D array X [m,n] with m rows and n columns, where m, n are positive integers. First, a one dimensional DWT is performed on rows to get low frequency L and high frequency H components of the image. Then, once again a one dimensional DWT is performed column wise on this intermediate result to form the final DWT coefficients LL, HL, LH, HH. These are called sub-bands.

   The LL sub-band can be further decomposed into four sub-bands by following the

   above procedure. This process can continue to the required number of levels. This process is called multi level decomposition. A three level decomposition of the given digital image is as shown. High pass and low pass filters are used to decompose the image first row-wise and then column wise. Similarly, the inverse DWT is applied which is just opposite to the forward DWT to get back the reconstructed image, shown in Figure 10

   Fig.10. Row-column computation of 2-D DWT

3. PROPOSED 3D-DWT ARCHITECTURE:

Conventional 3D-DWT is inefficient since it requires to access all the image frames on the same time axis, and thereby requires significant amount of memory space to perform DWT. The concept of group of frames (GOF) which is similar to the group of pictures in MPEG is introduced to overcome the drawbacks associated with conventional 3D-DWT; unfortunately this approach has its limitations from compression efficiency perspective.

Fig.11. 3D-DWT architecture

Vol. 1 Issue 9, November- 2012

The proposed architecture being introduced is

based on two layered system elements and addresses this frame access issue. Figure 11 highlights the proposed architecture comprising the PE-odd (processing element – odd) layer and the PE-even (processing element even) layer. The approach employs stacked chip architecture, and thereby alleviates the frame access bottleneck. The architecture permits accesses to all frames on the same time axis, thus providing better data compression efficiency.

V. Applications:

Medical application Signal de-noising Data compression Image processing

Results:

Fig.12 Simulation Result of DWT-7 Block Both High and Low pass

Fig13 .Simulation Result of DWT (TOP MODULE) Block with both High and Low pass

References:

Vol. 1 Issue 9, November- 2012

Fig.20 3-DWT Schematic with Basic inputs and Outputs

Conclusion:

The applications of 3-D wavelet based coding are opening new vistas in video and other multidimensional signal compression and processing. The prominent needs in these diversified application areas are efficient 3-D- DWT engines with good computing power which draws the attention of the dedicated VLSI architectures as the best possible solution. Though the researches of 2-D-DWT architectures are progressing quite fast, fewer approaches are reported in the literatures designing their 3-D counterpart.

This paper has presented a lifting based 3-D-DWT architecture with running transform, possibly the rst of its kind. Themain avors of the design are minimized storage requirement and memory referencing, low latency and power consumption and increased throughput, which become evident when they are compared with those of existing ones. Having single adder in its critical path, the mapped processor achieves a high speed of 321 MHz, offering large computing potentials which opens up new vista for real-time video processing applications. Compared to the original 3-D-DWT transform, successful application of motion compensations before temporal trans-form has been reported in the literature [2] as a good alternative for predictive coding. It is worth mentioning that the present design is fully scalable to those future modications and can be accepted as an introductory step toward those future 3-D wavelet computing machines.

1. I. Daubechies and W. Sweldens, Factoring wavelet transforms into lifting steps, J. Fourier Anal. ppl., vol. 4, no. 3, pp. 247-269, 1998.

2. S. Barua, J.E. Carletta, K.A. Kootteri, and

   A.E. Bell, An efficient architecture for lifting- based two- dimensional discrete wavelet transforms, VLSI J. Integration, vol. 38, no.3, pp. 341-352, Jan. 2005.

3. G. Kuzmanow, B. Zafarifar, P. Shrestha, and

   S. Vassiliadis, Reconfigurable DWT unit based on lifting, in proc. Program Res. Integer. Syst. Circuits, veldhoven, the Netherlands, Nov. 2002, pp. 325-333.

4. L. Luo, S. Li, Z. Zhuang, and Y.-Q. Zhang, Motion compensated lifting wavelet and its application in video coding, in Proc. IEEE Int. Conf. Multimedia Expo, Tokyo, Japan, 2001, pp. 365368.

5. A. Skodras, C. Christopoulos, and T. Ebrahimi, The JPEG 2000 stillimage compression standard, IEEE Signal Process. Mag., vol. 18,no. 5, pp. 3658, Sep. 2001.

6. J.-R. Ohm, M. van der Schaar, and J. W. Woods, Interframe waveletcoding: Motion picture representation for universal scalability, J. SignalProcess. Image Commun., vol. 19, no. 9, pp. 877908, Oct. 2004.

7. G. Menegaz and J.-P. Thiran, Lossy to lossless object-based coding of 3-D MRI data, IEEE Trans. Image Process., vol. 11, no. 9, pp. 10531061, Sep. 2002.

8. J. E. Fowler and J. T. Rucker, 3-D wavelet- based compression of hyperspectral imagery, in Hyperspectral Data Exploitation: Theory

and Applications, C.-I. Chang, Ed. Hoboken, NJ: Wiley, 2007, ch. 14, pp. 379407.

[9 ] L. R. C. Suzuki, J. R. Reid, T. J. Burns, G. B. Lamont, and S. K. Rogers, Parallel computation of 3-D wavelets, in Proc. Scalable High- Performance Computing Conf., May 1994, pp. 454461.

1. E. Moyano, P. Gonzalez, L. Orozco- Barbosa, F. J. Quiles, P. J. Garcia, and A. Garrido, 3-D wavelet compression by message passing on a Myrinet cluster, in Proc. Can. Conf. Electr. Comput. Eng., vol. 2. 2001, pp. 10051010.

2. W. Badawy, G. Zhang, M. Talley, M. Weeks, and M. Bayoumi, Low power architecture of running 3-D wavelet transform for medical imaging application, in Proc. IEEE Workshop Signal Process. Syst., Taiwan, 1999, pp. 6574.