An Efficient Architecture for Lifting Based 3D-Discrete Wavelet Transform

An Efficient Architecture for Lifting Based 3D-Discrete Wavelet Transform

Karunakar Pothuganti,

Assistant Professor,

Dept. Of Electrical Engineering, samara university, Ethiopia.

Anusha chitneni Assistant professor, Department Of E.C.E, SICET, Hyderabad, India

Vikram Angala Assistant professor, Department Of E.C.E

SCITS, Karimnagar, India

Abstract

The digital data can be transformed using Discrete Wavelet Transform (DWT). The Discrete Wavelet Transform (DWT) was based on time-scale representation, which provides efficient multi-resolution. The lifting based scheme (9, 7) (Here 9 Low Pass filter coefficients and the 7 High Pass filter coefficients) filter give lossy mode of information. The lifting based DWT are lower computational complexity and reduced memory requirements. Since Conventional convolution based DWT is area and power hungry which can be overcome by using the lifting based scheme. The discrete wavelet transform (DWT) is being increasingly used for image coding. This is due to the fact that DWT supports features like progressive image transmission (by quality, by resolution), ease of transformed image manipulation, region of interest coding, etc. DWT has traditionally been implemented by convolution. Such an implementation demands both a large number of computations and a large storage features that are not desirable for either high-speed or low-power applications. Recently, a lifting-based scheme that often requires far fewer computations has been proposed for the DWT.

In this paper, the design of Lossy 3-D DWT (Discrete Wavelet Transform) using Lifting Scheme Architecture will be modelled using the Verilog and its functionality were verified using the Modelsim tool and can be synthesized using the Xilinx tool.

1. Introduction

   The wavelet transform is computed separately for different segments of the time-domain signal at different frequencies. Multi-resolution analysis analyzes the signal at different frequencies giving different resolutions. Multi- resolution analysis is designed to give good time resolution and poor frequency resolution at high frequencies and good frequency resolution and poor time resolution at low frequencies. Good for signal having high frequency components for short durations and low frequency components for long duration, e.g. Images and video frames.

   1. Difference between Continuous Wavelet Transform and Discrete Wavelet Transform

      Wavelet transforms are classified into discrete wavelet transforms (DWTs) and continuous wavelet transforms (CWTs). Both DWT and CWT are continuous-time (analogue) transforms. They can be used to represent continuous-time (analogue) signals. CWTs operate over every possible scale and translation whereas DWTs use a specific subset of scale and translation values or representation grid.

      The word wavelet is due to Morlet and Grossmann in the early 1980s. They used the French word ondelette, meaning "small wave". Soon it was transferred to English by translating "onde" into "wave", giving "wavelet".

      The Wavelet transform is in fact an infinite set of various transforms, depending on the merit function used for its computation. This is the main reason, why we can hear the term "wavelet transforms" in very different situations and applications. Orthogonal wavelets are used to develop the discrete wavelet transform Non orthogonal wavelets are used to develop the continuous wavelet transform There are more wavelet types and transforms, but those two are most widely used and can serve as examples of two main types of the wavelet transform:

      Those are redundant and non-redundant ones.

      • The discrete wavelet transform returns a data vector of the same length as the input is. Usually, even in this vector many data are almost zero. This corresponds to the fact that it decomposes into a set of wavelets (functions) that are orthogonal to its translations and scaling. Therefore we decompose such a signal to a same or lower number of the wavelet coefficient spectrum as is the number of signal data points. Such a wavelet spectrum is very good for signal processing and compression, for example, as we get no redundant information here.

      • The continuous wavelet transform in contrary returns an array one dimension larger than the input data. For a 1D data we obtain an image of the time-frequency plane. We can easily see the signal frequencies evolution during the duration of the signal and compare the spectrum with other signals spectra. As here is used the non-orthogonal set of wavelets, data are correlated highly, so big redundancy is seen here. This helps to see the results in a more humane form.

   2. Area of Application

      • Medical application

      • Signal denoising

      • Data compression

      • Image processing

2. 3D DISCRETE WAVELETRANSFORM

   1. 3D DISCRETE WAVELETRANSFORM

      The 3D DWT can be considered as a combination of three 1D DWT in the x, y and z directions, as shown in Figure 1. The preliminary work in the DWT processor design is to build 1D DWT modules, which are composed of high-pass and low-pass filters that perform a convolution of filter coefficients and input pixels. After a one-level of 3D discrete wavelet transform, the volume of image is decomposed into HHH, HHL, HLH, HLL, LHH, LHL, LLH and LLL signals as shown in the Figure1.

      Figure 1.one level 3D-discrete wavelets transform structure

   2. Lifting Scheme

      The basic idea behind the lifting scheme is very simple; try to use the correlation in the data to remove redundancy [4, 5]. First split the data into two sets (split phase) i.e., odd samples and even samples as shown in Figure 2.

      Figure 2. The lifting scheme: Split, predict, update and scale

      Figure 3. 1-D lifting scheme of daubechies 9/7 for forward wavelet DWT.

      Because of the assumed smoothness of the data, we predict that the odd samples have a value that is closely related to their neighboring even samples. We use N even samples to predict the value of a neighboring odd value (predict phase). With a good prediction method, the chance is high that the original odd sample is in the same range as its prediction. We calculate the difference between the odd sample and its prediction and replace the odd sample with this difference. As long as the signal is highly correlated, the newly calculated odd samples will be on the average smaller than the original one and can be represented with fewer bits. The odd half of the signal is now transformed. To transform the other half, we will have to apply the predict step on the even half as well. Because the even half is merely a sub-sampled version of the original signal, it has lost some properties that we might want to preserve. In case of images we would like to keep the intensity (mean of the samples) constant throughout different levels. The third step (update phase) updates the even samples using the newly calculated odd samples such that the desired property is preserved. Now the circle is round and we can move to the next level. We apply these three Steps repeatedly on the even samples and transform each time half of the even samples, until all samples are transformed

      Figure 4. 3D DWT Architecture

      .

   3. Rationalization of Filter Coefficients

   As already stated lifting scheme is one of the most efficient algorithms for the implementation of discrete wavelet transform. But one of the major shortcomings with this scheme is that the lifting coefficients obtained for the implementation of bi orthogonal 9/7 wavelet transformation are irrational numbers [7, 8]. Hence the direct irrational coefficient implementation requires lot of hardware resources and the processing time at the cost of slight improvement in the compression performance. On the other hand, lower precision in filter coefficients results in smaller and faster hardware at the cost of compression performance. In addition to this rationalization also determines

   other critical hardware properties such as throughput and power consumption. Hence it is suggested that they should be optimally rationalized without much affecting the compression performance

   Table 1. Irrational and rational lifting coefficients for 9/7 wavelet transform.

   	Irrational value	Rational value
   	-1.58613443420.	-3/2
   	-0.0529801185.	-1/16
   	0.8828110755.	4/5
   	0.4435068520	15/32
   	1.1496043988.	42/5

   Table 1 shows the irrational and approximated rational counterpart for 9/7 filter which are considered as a very good alternative to irrational coeffcients. When these coeffcients are applied to image coding, the compression performance is almost same as that of irrationalized filter coefficient implementation, while the computational complexity is reduced remarkably. The heart of 3-D DWT implementation is designing of 1-D processor which is clearly elaborated in Fig.4 The different lifting coeffcients can be easily obtained for Daubechies 9/7 filter by factorization of poly phase matrix. Figure 3 shows the implementation of 9/7 lifting scheme. This figure is direct implementation of Fig. 2 for the required scheme. When the signal passes through various steps, it is split into three separate one dimensional transforms, the high pass component (HHH) and a low pass component (LLL). Because of sub sampling the total number of transformed coeffcients is same as that of original one. These transformed coeffcients are then processed by x coordinate Processor, which have the same architecture as that of y and z-processor, to complete 3-D transformation. The bi-orthogonal 9/7 wavelet can be implemented as four lifting steps followed by scaling requires that the following equations be implemented in hardware.

   x1[2n+1] x[2n+1]+{ x[2n]+x[2n+2]}..(1)

   x2 [2n] x[2n]+{ x1 [2n+1]+ x1 [2n-1]}.(2) x3[2n+1] x1 [2n+1]+{ x3[2n]+ x3[2n+2]}(3)

   x4[2n] x2 [2n]+{ x3[2n+1]+ x3[2n-1]}.(4) x5[2n+1] 1/{ x3[2n+1]}(5) x6[2n] { x4[2n]}(6)

   The original data to be filtered is denoted by x[n] and the 1-D DWT outputs are the detail coefficients x5[n] and approximation coefficients x6[n]. The lifting step coefficients ,, and and scaling coefficient are constants given by Table 1. The above equations are implemented on Verilog to obtain the coefficients x5[n] and x6[n]. These coefficients correspond to H and L respectively. Now these coefficients are passed through the 1-D processor 3 times. Where, z-co-ordinate processor gives the final output as the eight subsets of original image as shown in

   Figure 1. These coefficients are then stored in external memory in the form of binary file. For the multiple level of decomposition this binary file can be invoked iteratively to obtain further sublevels.

3. Result and Discussion

   The DWT process and the developed architecture for the required functionality were discussed in the previous chapters. Now this chapter deals with the simulation and synthesis results of the DWT process. Here Modelsim tool is used in order to simulate the design and checks the functionality of the design. Once the functional verification is done, the design will be taken to the Xilinx tool for Synthesis process and the net list generation.

   The Appropriate test cases have been identified in order to test this modelled DWT process architecture. Based on the identified values, the simulation results which describes the operation of the process has been achieved. This proves that the modelled design works properly as per its functionality.

   1. Simulation Results

      The test bench is developed in order to test the modeled design. This developed test bench will automatically force the inputs and will make the operations of algorithm to perform.

   2. DWT Block

      The initial block of the design is that the Discrete Wavelet Transform (DWT) block which is mainly used for the transformation of the image. In this process, the image will be transformed and hence the high pass coefficients and the low pass coefficients were generated. Since the operation of this DWT block has been discussed in the previous chapter, here the snapshots of the simulation results were directly taken in to consideration and discussed.

      The input is 16 bits each input bit width is vary because of the multiplier. The DWT consists of registers and adders. Whenever the input is send, the data divided into even data and odd data. The even data and odd data is stored in the temporary registers. When the reset is high the temporary register value consists of zero whenever the reset is low the input data split into the even data and odd data. The input data read up to sixteen clock cycles after that the data read according to the lifting scheme. The output data consists of low pass and high pass elements. This is the 1-D discrete wavelet transform. The 2-D discrete wavelet transform is that the low pass and the high pass again divided into LL, LH and HH, HL. The 3-D discrete wavelet transform is that the low pass and the high pass

      again divided into LLL, LLH, LHL, LHH, HLL, HLH, HHL, and HHH. The output is verified in the Modelsim.

      For this DWT block, the clock and reset were the primary inputs. The pixel values of the image, that is, the input data will be given to this block and hence these values will be split in to even and odd pixel values. In the design, this even and odd were taken as a array which will store its pixel values in it and once all the input pixel values over, then load will be made high which represents that the system is ready for the further process.

      Once the load signal is set to high, then the each value from the even and odd array will be taken and used for the Low Pass Coefficients generation process. Hence each value will be given to the adder and in turn given to the multiplication process with the filter coefficients. Finally the Low Pass Coefficients will be achieved from the addition process of multiplied output and the odd pixel value.

      Again this Low Pass Coefficient will be taken and it will be multiplied with the filter coefficients. The resultant will be added with the even pixel value which gives the High Pass Coefficient. Hence all the values from even and odd array will be taken and then above said process will be carried out in order to achieve the High and Low Pass Coefficients of the image.

      Figure 5. Simulation Result of DWT-1 Block with Both High and Low Pass Coefficients

   3. Synthesis Result

      The developed DWT is simulated and verified their functionality. Once the functional verification is done, the RTL model is taken to the synthesis process using the Xilinx ISE tool. In synthesis process, the RTL model will be converted to the gate level net list mapped to a specific technology library. The design of DWT is synthesized and its results were analyzed as follows.

      Figure 6. synthesize report

4. Conclusion & Future scope

   1. Conclusion

      Basically the medical images need more accuracy without loosing of information. The Discrete Wavelet Transform (DWT) was based on time-scale epresentation, which provides efficient multi-resolution. The lifting based scheme (9, 7) (The high pass filter has five taps and the low pass filter has three taps) filter give lossless mode of information. A more efficient approach to lossless whose coefficients are exactly represented by finite precision numbers allows for truly lossless encoding.

      The discrete wavelet transform (DWT) is being increasingly used for image coding. This is due to the fact that DWT supports features like progressive image transmission (by quality, by resolution), ease of transformed image manipulation, region of interest coding, etc. DWT has traditionally been implemented by convolution. Such an implementation demands both a large number of computations and a large storage features that are not desirable for either high-speed or low power applications. Recently, a lifting-based scheme that often requires far fewer computations has been proposed for the DWT.

      This work ensures that the image pixel values given to the DWT process which gives the high pass and low pass coefficients of the input image. The simulation results of DWT were verified with the appropriate test cases. Once the functional verification is done.

   2. Future scope of the Work

      As future work,

      • This work can be extended in order to increase the accuracy by increasing the level of transformations.

        • This can be used as a part of the block in the full fledged application, i.e., by using these DWT, the applications can be developed such as compression, watermarking, etc

REFERENCES

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

2. Daubechies, I., \Ten lectures on wavelets," SIAM, Philadelphia, 1992.

3. Jiang, R. M. and D. Crookes, \FPGA implementation of 3D discrete wavelet Transform for real-time medical imaging,"

   ECCTD, 519{522, August 2007

4. Daubechies, I. and W. Sweldens, \Factoring wavelet transforms into lifting steps," Journal of Fourier Analysis and Applications, Vol. 4, No. 3, page No. 247 to 269, 1998.

5. . Sweldens, W., \The lifting scheme: A construction of second generation wavelets,"SIAM Journal on Mathematical Analysis,

   Vol. 29, No. 2, 511{546, March 1998

6. Spiliotopoulos, V., N. D. Zervas, C. E. Androulidakis, G. Anagnostopoulos, and S. Theoharis,\Quantizing the 9/7 daubechies lters coeffcients for 2D DWT VLSI Implementions,"

   DigitalSignal Processing, Vol. 1, 227{231, 2002

7. Xiong, C., S. Zheng, J. Tian, and J. Liu, \The improved lifting scheme and novel Recongurable VLSI architecture for the 5/3 and 9/7 wavelet lters," ICCCAS, Vol. 2, 728{732, June 2004.

8. 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.

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