Design of Memory Efficient Architecture for Mul-tilevel Discrete Wavelet Transform

Design of Memory Efficient Architecture for Mul-tilevel Discrete Wavelet Transform

Ashley Alex

PG student, VLSI & Embedded Systems, ECE Department TKM Institute of Technology

Karuvelil P.O, Kollam, Kerala-691505, India

Abhila R Krishna

Assistant professor, ECE Department TKM Institute of Technology

Karuvelil P.O, Kollam, Kerala-691505, India

Abstract The discrete wavelet transform is one of the commonly used signal transformations. It does not change the information content present in the signal. The Wavelet Transform provides a time-frequency representation of the signal. The two dimensional Discrete Wavelet Transform is widely used for compressing the video and image. The high data rate transmission and storage have been used in portable devices and handheld devices. The image or video can be occupied more storage spaces in devices. Therefore the image can be decomposed into multilevel DWT to achieve the higher compression ratio. Memory complexity is the most important issue for efficient realisation of Discrete Wavelet Transform in VLSI system. The goal of this work is to suggest a memory efficient generic architecture for multilevel Discrete Wavelet Transform The Discrete Wavelet Transforms are com- puted concurrently to reduce the frame buffers and a parallel data access is applied in each Discrete Wavelet Transform level to reduce memory complexity of the overall structure. The design architecture is written using VHDL code and simulated using Xilinx ISE tools and ModelSim SE 6.5.

Keywords Discrete wavelet transform, PE, Lifting scheme, convolution algorithm

1. INTRODUCTION

   Discrete wavelet transform represents an important innovation in the area of signal processing and image process- ing. Wavelet Transform is a transformation technique which is used for the transformation into a suitable domain which are well localized in both time and frequency domains with the help of wavelets. Discrete wavelet transforms a discrete time signal into a discrete wavelet representation. One of the impor- tant features of the discrete wavelet transform is the multireso- lution analysis (MRA). It analyses the signal at different fre- quencies giving different resolution [3]. It is designed to give good time resolution and poor frequency resolution at high frequencies and good frequency resolution and poor time reso- lution at low frequencies. It is good for signals having high frequency components for short duration and low frequency components for long duration. The wavelet transform describes a multiresolution decomposition process in terms of expansion of an image into a set of wavelet basis function. In recent years, the wavelet transform emerged in the field of image or signal processing as an alternative to well known Fourier transform.

   In most digital signal processing applications, the fre- quency content of the signal is very important. The Fourier transform is probably the most important transform used to

   obtain the frequency spectrum of signal. But the Fourier trans- form does not tell at which time the frequency component oc- cur. To solve this problem, the wavelet transform was intro- duced which provides a better time frequency representation of the signal than any other transforms.

   In image processing applications, efficient storage and transmission of image is very much essential. The raw image contains a huge amount of redundant information, for efficient transmission and storage purpose this redundancy must be re- moved which is the ultimate aim of image compression. One of the important steps in image compressions is the transforma- tion of image into a suitable domain which has better localiza- tion in time and frequency domain. Discrete wavelet transform, of its excellent space frequency localization property has been extensively used as a transformation technique in most image compression system [4] [5]. DWT has been adopted by recent still image and video coding standards, JPEG2000 andMPEG-4, given its high performance for image and video compression showing superior results when compared to the traditionally used discrete cosine transform.

   Recently , the wavelet transform is being increasingly used not only in the field of image and signal processing appli- cations but also in many other different areas ranging from mathematics, physics, astronomy to statistics and economics.

   The report is organized as follows. Chapter 2 includes the literature survey of the project. It gives the basic idea of the discrete wavelet transform. It also specifies the one dimension- al, two dimensional, different level of wavelet decomposition. Chapter 3 presents the architecture. The simulation results are given in the Chapter 4. It includes the simulation result ob- tained from MATLAB and modelsim and finally Chapter 5 concludes this project and outlines the further researches fol- lowed by the references.

2. LITERATURE REVIEW.

1. Discrete Wavelet Transform

   The DWT is a multiresolution decomposition scheme for input digital signals. The source signal is firstly decom- posed into two frequency sub bands, low-frequency (low-pass) sub band, and high-frequency (high-pass) sub band. For the classical DWT, the forward decomposition of a signal is im-

   plemented by a low-pass digital filter H and a high-pass digital filter G. Both digital filters are derived using the scaling func- tion and the corresponding wavelet functions at different fre- quency scales. The system down samples the signal to half of the filtered results in the decomposition process. If four-tap and non-recursive FIR filter are considered, the transfer functions of H and G can be represented as follows:

   H(z) = h0 + pz-1 +pz-2 +pz-3 (1)

   G(z) = g0 +g1z-1 +g2z-2 + g3z-3 (2)

   One of the drawbacks of the DWT is that it doubles the memory requirements because it is implemented as a filter. The lifting scheme reduces the memory requirements and the num- ber of operations needed to perform the wavelet transform if compared with the usual filtering algorithm (also known as convolution algorithm). The order of this reduction depends on the type of wavelet transform [3], A special case of wavelet filter is the Daubechies 9/7 filter. This filter has been widely used in image compression, and it has been included in the JPEG2000 standard. Recently, a novel way of computing the wavelet transform is by trying to reduce the computational complexity for the wavelet filtering process, which is called Symmetric Mask-based Discrete Wavelet Transform (SMDWT). This algorithm computes the wavelet transform as a matrix convolution, using the four matrixes derived from the 2D-DWT of Daubechies 9/7 floating point lifting-based coeffi- cients. The 2D lifting-based Wavelet Transform (LDWT) scheme requires vertical and horizontal 1D LDWT calcula- tions, and each of the 1D LDWT requires four steps: splitting, prediction, updating, and scaling. Conversely, the four sub band 2D SMDWT can be yielded using four independent ma- trices of size 7 × 7, 7 × 9, 9 × 7, and 9× 9 for the Daube- chies 9/7 filter [8]. The interest in this algorithm is based on both the way it computes the DWT, unlike the traditional DWT and LDWT algorithms, it computes each sub band independ- ently through a four matrix convolution, and the theoretical low computation complexity.

2. One-dimensional DWT

   Nowadays, wavelet transform is intensively used in speech, image and video processing, and in signal processing in general because of its attractive characteristics to represent non-stationary signals in both frequency and time dmains.

   Figure 1 One Dimensional DWT

   Figure 1 shows a two-level 1D-DWT. Here the input image is filtered( both high pass and low pass) and then per- form down sampling which is used to reduce the number of samples and only the output of low pass filter is given as the input to the next transformation level[7]. The basic structure of a 1D-DWT is originally based on filter bank for sub-band de-

   composition where the number of cascaded units determines the level of transformation in the Discrete Wavelet Transform.

3. Two Dimensional DWT

   Two-dimensional (2-D) discrete wavelet transform (DWT) is widely used in image and video compression. The input image is required to be decomposed into multilevel DWT to achieve higher compression ratio. The multilevel 2-D DWT on the other hand, being highly computation-intensive and memory-intensive, is implemented in very large scale integra- tion (VLSI) system to meet the temporal requirement of real- time applications.

   Figure. 2 Two dimensional DWT

   Due to its ever increasing usage in high data-rate communication and storage, through portable and hand-held devices, VLSI implementation of 2-D DWT is subjected to a set of incompatible constraints, e.g., the silicon area and power consumption along with its minimum processing-speed for real-time computation. A separable 2D-DWT with N levels of transformation can be easily achieved by concatenation of 1D- DWT units, with the first stage processing N transformation levels on rows and the second one with N transformation levels on columns. Here the Figure 2 shows a two level 2-D discrete wavelet transform. Transformation is done both in row and column directions. The LL sub band of first level transforma- tion is given as the input to the second level transformation while all other sub bands are the detailed coefficients. Simi- larly the LLLL sub band is given as input to the next level.

4. Wavelet decomposition

   There are several ways wavelet transforms can decompose a signal into various sub bands. These include uniform decom- position, octave-band decomposition, and adaptive or wavelet-

   packet decomposition. Out of these, octave-band decomposi- tion is the most widely used.

   The procedure is as follows: wavelet has two functions wavelet and scaling function. They are such that there are half the frequencies between them. They act like a low pass filter and a high pass filter The decomposition of the signal into different frequency bands is simply obtained by successive high pass and low pass filtering of the time domain signal. This filter pair is called the analysis filter pair. First, the low pass filter is applied for each row of data, thereby getting the low frequency components of the row. But since the low pass filter is a half band filter, the output data contains frequencies only in the first half of the original frequency range. By Shannon's Sampling Theorem, they can be sub-sampled by two, so that the output data now contains only half the original number of samples. Now, the high pass filter is applied for the same row of data, and similarly the high pass components are separated.

5. Lifting based discrete wavelet transform

   The main feature of the lifting-based discrete wavelet transform scheme is to break up the high-pass and low-pass wavelet filters into a sequence of smaller filters that in turn can be converted into a sequence of upper and lower triangular matrices. The basic idea behind the lifting scheme is to use data correlation to remove the redundancy. In a grey scale im- age, each pixel value represents the photo intensity of its own spot in the image. The transformation is done by separating the low frequency pixels from its high frequency counterparts. This operation can be implemented in a number of ways. Some of the widely accepted techniques are level-by-level, block- based and line-based transformations.

   The lifting scheme is a popular method to compute DWT and is accepted as a JPEG2000 compliant technique. This method factorizes the wavelets into simple lifting steps and then performs the transformation. The lifting scheme has a number of advantages, for example less computational com- plexity, less memory requirements and in-place computation.

   The lifting algorithm can be computed in three main phases, namely: the split phase, the predict phase and the up- date phase [3], as illustrated in Figure 2.3

   SPLIT

   UPDATE

   PREDICT

   Figure 3 Lifting based DWT

   1. Split phase: In this Split phase, the data set is split into two subsets to separate the even samples from the odd ones.

   2. Predict phase: In the prediction stage, the main step is to eliminate redundancy left and give a more compact data representation. It generates the odd samples based on the even samples.

   3. Update phase: The third stage of the lifting scheme in- troduces the update phase. In this phase, it updates the pre- dicted values based on the even samples. This updated value represents the smooth coefficients and the predicted value represents the detailed coefficients.

Update phase U: si = 1/4 (di +di-1) + x2i (3)

Predict Phase P : di =-1/2(x2i +x2i+2 ) +x2i+1 (4)

III PROPOSED METHOD

Raw images contain a huge amount of redundant informa- tion. In order to efficiently store and transmit the useful infor- mation this redundancy can be removed, which is the ultimate aim of the image compression. Transformation of an image to a suitable domain is the first and most important step in an image compression. The discrete wavelet transform is the main trans- formation technique that has been used nowadays. The main goal of this work is to design an efficient architecture for multi- level discrete wavelet transform.

1. System architecture

   The proposed system is shown in fig 4. The system mainly consists of four main modules. The first is the external inter- face through which the host system can communicate by read- ing the input image as well as for writing the coefficient com- puted by the proposed system. The second is the row processor which is used to perform the row wise computation of the pixel data i.e. it performs the 1D-DWT along the rows of pixels data in the original image and store the intermediate coefficients in the memory bank. The third is the column processor which is used to perform the column wise computation of the row trans- formed coefficient. That is it performs the 1D-DWT along the columns. This 1D-DWT along the row and the 1D-DWT along the column which together performs the 2D-DWT of the image. Fourth one is the memory module, which is used to store the incoming pixel, row transformed coefficient as well as storing the column transformed coefficient or the one level 2D-DWT coefficient.

2. Row Processor

   Figure 4 DWT processor

   operation to be performed i.e. whether predict or update op- eration. After performing the row wise computation, the input data is replaced with row transformed coefficient thus saving the auxiliary memory required to store the intermediate coef- ficient. This possible because of the in place computation of the lifting based discrete wavelet transform since input data is no more required for further processing. Thus memory com- plexity of the system can be reduced.

3. Column Processor

   The operation of the column processor is almost same as that of the row processor. The main difference is the input to the column processor. In column processor the input is the row transformed coefficient. The row transformed coef- ficient is stored in the memory bank in column wise and then performs the operation.

4. MULTILEVEL DESIGN

Figure. 6 show the image after 1 level transformation. It is divided into four quadrants: LL1, HL1, LH1 and HH1. The information contained in the first quadrant (LL1) repre- sents the low frequency components (smooth coefficients) of the image. Only this quadrant of the trasformed coefficients is required for processing at the next level.

The row processor mainly consists of row logic ele- ment (RLE) which is used to perform the row wise computa- tion of the pixel data. The proposed system utilizes the lifting based approach to compute the discrete wavelet transform. Here the logic elements are designed in such a way that it can perform both predict and update operation. This predicts and update operation takes place in alternate clock cycles.

The equation (3) & (4) can be implemented without any multiplier, thereby reducing the complexity of the multi- plication operation. The multiplication operation is replaced by the shift right operation. This has been possible because the equation (3) & (4) require multiplication by ½ and ¼ respec- tively, which can be easily achieved by shifting the data to the right by one or two positions respectively. That is ½ can be achieved by shifting the bit to right by one and ¼ can be achieved by shifting the bit to right by two.

Figure 5 Processing element

The figure 5 shows the implementation of a generic processing element. Here the select signal determines which

Since the hardware resources required by the level 1 DWT processor presented earlier is very low , higher level DWT processors are designed using multiple instances of the level 1 processor operating in parallel. Each of the single-level proc- essors calculates and outputs the low frequency (LL) sub-band of the transformed coefficients generated at that level to the next level.

Figure 6 Row and column Transformation for first level DWT

1. SIMULATION RESULTS

   The design entry is modelled using VHDL in Xilinx ISE Design Suite 13.2 and the simulation of the design is per- formed using modelsim SE 6.5 from Xilinx ISE to validate the functionality of the design.

   1. Image pixel values obtained from MATLAB

      Here the pixel values of the corresponding image are gen- erated and stored in a text file with the help of MATLAB R2013b. The pixel values are obtained in a binary form for giving into the system

      Figure 7 Pixel values form matlab

   2. Reading the pixel values

      The pixel value of the desired image is taken and stored in a text file using the mat lab. From the text document, the pixel values are read serially using vhdl and are simulated.

   3. Logic element

   The below simulation result shows the logic element which is used for the row transformation and column transformation. Here the select signal denotes whether update or predict func- tion to be performed. If the select signal is 0, it performs pre- dict phase operation. if the select signal is 1, it performs up- date operation .

2. CONCLUSIONS

The project is intended to design an memory efficient architecture for multilevel two dimensional discrete wavelet transform. The architecture implements the lifting scheme with a single multiplier free processing element to perform both predict and update operations. The 2D coefficients from each level are passed directly to the next level for processing without the need for additional storage. Thus saving the memory complexity. Due to the in place computation based trans- form, there is no need of special memory to store the coef- ficients. The multilevel discrete wavelet transform helps to achieve the highest compression ratio. The lowest memory requirement makes the proposed system suitable for high performance image processing including streaming video for portable and power constrained wireless application. The system is developed using VHDL and simulated using Model Sim6.2 b design suit from Mentor Graphics.

Fig 7 Reading the pixel value

.

Fig 8 logic element

References

1. B. K. Mohanty and P. K. Meher, Memory-efficient modular VLSI architecture for high-throughput and low-latency imple- mentation of multilevel lifting 2-D DWT, IEEE Trans. Signal Process., vol. 59, no. 5, pp. 20722084, May 2013.

2. C. Cheng and K. K. Parhi(Jan. 2008) High-speed VLSI imple- mentation of 2-D discrete wavelet transform IEEE Trans. Signal Process., vol. 56, no. 1, pp. 393403,Jan 2008.

3. C.-T. Huang, P.-C. Tseng, and L.-G. Chen(Generic RAM-based architectures for 2-D discrete wavelet transform with line- based method IEEE Trans. Circuits Syst. Video Technol., vol. 15, no. 7, pp. 910920.

4. X. Tian, L. Wu, Y.-H. Tan, and J.-W. Tian, Efficient multi- input/multioutput VLSI architecture for 2-D lifting-based discrete wavelet transform, IEEE Trans. Comput., vol. 60, no. 8, pp. 12071211, Aug. 2011.

5. Z. Gao and C. Xiong, High-throughput implementation of lift- ing-based discrete wavelet transform using look-ahead pipelin- ing, SPIE, Opt. Eng., vol. 49, no. 10, 107003, pp. 17, Oct. 2011.

6. Y.-K. Lai, L.-F. Chen, and Y.-C. Shih, A high-performance and memory-efficient VLSI architecture with parallel scanning

   method for 2-D lifting-based discrete wavelet transform, IEEE Trans. Consum. Electron., vol. 55, no. 2, pp. 400407, May 2010.

7. Y.-K. Lai, L.-F. Chen, and Y.-C. Shih A high-performance and memory-efficient VLSI architecture with parallel scanning method for 2-D lifting-based discrete wavelet .

8. G. C. Jung, D. Y. Jin, S. M. Park; "An Efficient line VLSI Archi- tecture for 2-D Lifting DWT", The 47th IEEE International Midwest Symposium on Circuits and Systems.

9. M. Jeyaprakash; "FPGA Implementation of Discrete Wavelet Transform (DWT) for JPEG 2000", International Journal of Re- cent Trend in Engineering, Vol. 2, No. 6, November 2009.