This project proposes an improved version of lifting based 3-D Discrete Wavelet Transform VLSI architecture, which is a powerful image compression algorithm. This architecture based on lifting scheme greatly minimizes the storage requirement compared to previous architectures. The main features of this scheme are breaking up highpass and lowpass filters into a sequence of triangular matrices and convert the filter implementation into banded matrix multiplications. The proposed architecture has been modeled using Verilog HDL and its functionality is verified using Modelsim.
I. INTRODUCTION
DWT is one of the powerful signal processing technique based on time scale representation and best known for its results in compression techniques. Image and audio compression, pattern recognition, texture discrimination etc. are some of its application fields. These techniques are used to obtain the time scale representation of a signal in DWT i.e., by passing it through filters with different cutoff frequencies at different scales.
Types of compressions:
Lossless compression: It uses compression algorithms to achieve a moderate amount of compression and the reconstructed image will be exactly similar to the original.. ZIP file format, UNIX tool GZIP are some of the applications where it is used.
Lossy compression: It is a method where the image retrieved after compressing and decompressing the data cannot be used to reconstruct the exact image but is "close enough" to the original image. Streaming media and telephony are some of its applications.
DWT filtering process
In DWT filtering process two data streams are produced at each level by filtering the input data streams using two related filters. Since the output should have same data-words as original it is subsampled by 2. The output of the lowpass filter is again passed through the same filters until no additional filtering can occur. Subscript values indicate the "level" of output. [1
Frequency information from the data is extracted by filtering process depending on filter characteristics.
DWT Architecture:
DWT is mostly used in the image coding because of the fact that it supports properties like region of interest coding, image transmission both in quality and resolution, ease of compressed image manipulation etc. By breaking the highpass and lowpass filters into a set of alternating upper and lower triangular matrices and a diagonal matrix sequence, lifting based DWT converts the filter implementation into banded matrix multiplication..
II THEORETICAL IMPLEMENTATION
Since the DWT constitutes a pair of filtering operations, a unified representation of the poly-phase matrix can be introduced as follows [2]
C:\Users\welcome\Desktop\Unt.png
Where h(z) -highpass filter transfer function
g(z) --lowpass filter transfer functions
suffixes 'e' and 'o' correspond to even and odd terms respectively. Thus, the transform is symbolized with equation[5]
With λ(z) and γ(z) signifying the filtered lowpass and highpass parts of the input x(z).
The lifting scheme factorizes the poly phase representation to a cascade of triangular matrices and a scaling matrix. For example the common daubechies (9, 7) can be represented as [6]
The related algebraic equations are
C:\Users\welcome\Desktop\U.png
Where α=-1.586134342,
β=0.05298011854,
γ=0.8829110762
δ=0.4435068522
ζ=1.149604398
III. PROPOSED MODEL
Decomposition:
Fig2. One dimensional two level wavelet decomposition
The above figure shows simple one-dimensional wavelet decomposition. The signal is first applied to a pair of low and highpass filters and then down sampling is applied to these down coefficients. The lowpass filter output after down sampling contains low frequency components which are the approximate part of the original signal and the highpass filter output contains high frequency components which is the detailed part of the original signal.
The approximate part will be further decomposed into low and high frequency components and this process continuous successively to required number of levels.
Reconstruction:
In this process the filtered coefficients obtained by passing the up sampled approximate and detailed coefficients through low and highpass reconstruction filters are added to get the reconstructed version of the original image. This process can be extended to multi-level reconstruction as shown in the fig 3 .The approximate coefficients to this block may be formed from pairs of approximate and detailed coefficients.
Fig3. One dimensional inverse wavelet transform
3-D Discrete Wavelet Transform:
Fig.4 shows a 3-D DWT comprises of 3 1-D DWT's along the 3-axes. Designing filters that perform a convolution of input pixels is the most important part of DWT. [3]
Fig 4. 3D-Discrete Wavelet Transform [3]
Lifting Scheme:
The lifting scheme uses the correlation in the data to remove redundancy.[3,4]
In the first phase (split phase), data splits into odd and even samples. Assumption of the smoothness of the data, we predict that the odd samples value is closely related to the neighboring even samples so that N even samples are used to predict the value of the neighboring odd sample( prediction phase).
The odd sample is replaced by the difference between odd and even samples. The odd samples calculated have a smaller average compared to the original one until the signal is highly correlated and can be represented with fewer bits which completes the transformation of odd half.
For even half transformation, same prediction step is applied on the even half as well. Since even half is a sub-sampled version of the original signal, some of its properties which we wish to preserve are lost. In the third step (update phase) the even samples will be updated using newly calculated odd samples.
. These three steps are repeatedly applied on the even samples until all samples are transformed.
Fig5 The lifting scheme showing split, predicts, update and scale phases [3]
Rationalization of Filter Coefficients:
The lifting coefficients obtained for the bi-orthogonal 9/7 wavelet transformation are irrational numbers. The direct irrational coefficient implementation requires lot of hardware resources and the processing time at the
cost of slight improvement in the compression performance. Hence it is suggested that they should be optimally rationalized without much affecting the compression performance.
Table 1 shows the irrational and approximated rational counterpart for 9/7 filter which When applied to image coding, give out a performance that is almost same as that of irrationalized filter coefficient implementation, while the computational complexity is reduced remarkably.
C:\Users\welcome\Desktop\tbl.png
Table1. Showing irrational and rational values
The heart of 3-D DWT implementation is designing of 1-D processor. The different lifting coefficients can be easily obtained for Daubechies 9/7 filter by factorization of poly phase matrix. Fig 6 shows the 9/7 lifting scheme which is the direct implementation of Fig 5. The number of transformed coefficients is same as original coefficients because of subsampling. These transformed coefficients 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 will be implemented in 4 lifting steps which require the hardware implementation of following equations.
C:\Users\welcome\Desktop\eqns.png
x[n] is the data to be filtered and detail coefficients x5[n] and approximation coefficients x6[n] are the outputs.The lifting step coefficients scaling coefficients 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-coordinate processor gives the final output as the eight subsets of original image which are then stored in memory in binary file format.
.
3-D (9, 7) Discrete Wavelet Transform:
Basically 1-D (9, 7) DWT block diagram is developed based on the equations. The registers in the top half will operate in even clock where as the ones in bottom half work in odd clock.
The input pixels arrive serially row-wise at one pixel per clock cycle and it will get split into even and odd. So after the manipulation with the lifting coefficients 'a', 'b', 'c' and'd' is done, the lowpass and highpass coefficients will be given out. Hence for every pair of pixel values, one highpass and one lowpass coefficients will be given as output respectively.
The highpass and lowpass coefficients of the taken image will be identified and separated which will be stored in buffers for further calculations.
Fig 6. Computation of Basic (9,7) DWT Block[5]
Simulation:
The initial block of the design is that the DWT block which is mainly used for the transformation of the image. In this process, the image will be transformed into high and low. The snapshots of the simulation results were directly taken in to consideration and discussed.
The input which is 16 bit gets divided into into odd samples and even samples gets 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 reads up to sixteen clock cycles after that the data read according to the lifting scheme. The output data consists of highpass elements and lowpass elements. This is the 1-D DWT. The 2-D DWT is the output of 1-D DWT is again divided into LL, LH and HH, HL. The 3-D discrete wavelet transform is that the output of 2-D DWT again divided into LLL, LLH, LHL, LHH, HLL, HLH, HHL, and HHH. The output is verified in the Modelism.
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 Lowpass 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 Lowpass Coefficients will be achieved from the addition process of multiplied output and the odd pixel value.
Again this Lowpass 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 Highpass 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 Lowpass Coefficients of the image.
Now these lowpass coefficients and the highpass coefficients were taken as the input for the further process. Hence for the DWT-2 process, lowpass coefficients will be taken as the inputs and will do the process in order to calculate the lowpass and highpass coefficients from the transformed coefficients of DWT-1. In DWT-2, the same process as in DWT-1 will be carried out. Hence the simulated waveform is shown in the figure 4.2. Similarly the highpass coefficients from the DWT-1 block were taken as input to the DWT-3 block and hence further transformed lowpass and highpass coefficients will be obtained. Similarly the process is continued for DWT-4, DWT-5, DWT-6, and DWT-7.
Fig 7. Simulation Result of DWT-1 Block
Fig 8. Simulation Result of DWT-2
Fig 9 .Simulation Result of DWT-3 Block
Fig 10. Simulation Result of DWT-4 Block
Fig 11 Simulation Result of DWT-5 Block
Fig 12 Simulation Result of DWT-6 Block
Fig 13 Simulation Result of DWT-7 Block
Fig 14 Simulation Result of 3D-DWT(TOP MODULE)
Conclusion:
3-D (9, 7) Discrete Wavelet Transform based on lifting scheme which gives lossless processing has been developed. This work ensures that the image pixel values given to the DWT process gives the highpass and lowpass coefficients of the input image. The simulation results of DWT were verified with the appropriate test cases
Future scope:
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.
