Keywords

1 Introduction

The discrete wavelet transform (DWT) represents the signal in dynamic sub-band decomposition. Generation of the DWT in a wavelet packet allows sub-band analysis without the constraint of dynamic decomposition. The discrete wavelet packet transform (DWPT) performs an adaptive decomposition of frequency axis. The specific decomposition will be selected according to an optimization criterion

The DWT, based on time-scale representation, provides efficient multi-resolution sub-band decomposition of signals. It has become a powerful tool for signal processing and finds numerous applications in various fields such as audio compression, pattern recognition, texture discrimination, computer graphics. Specifically, the two-dimensional DWT and its counterpart two-dimensional inverse DWT (IDWT) play a significant role in many image/video coding applications. The fundamental idea behind wavelets is to analyze according to scale. Indeed, some researchers in the wavelet field feel that, by using wavelets, one is adopting a perspective in processing data. Wavelets are functions that satisfy certain mathematical requirements and are used in representing data or other functions. When Joseph Fourier discovered that he could superpose sinus and cosines to represent other functions. However, in wavelet analysis, the scale that one use to look at data plays a special role. Wavelet algorithms process data at different scales or resolutions [1]. Fourier Transform (FT) with its fast algorithms (FFT) is an important tool for analysis and processing of many natural signals. FT has certain limitations to characterize many natural signals, which are non-stationary (e.g. speech). Though a time varying, overlapping window based FT namely short time FT (STFT) is well known for speech processing applications, a time-scale based Wavelet Transform is a powerful mathematical tool for non-stationary signals.

Wavelet Transform uses a set of damped oscillating functions known as wavelet basis. WT in its continuous (analog) form is represented as continuous wavelet transform (CWT). CWT with various deterministic or non-deterministic basis is a more effective representation of signals for analysis as well as characterization. CWT is powerful in singularity detection. A discrete and fast implementation of CWT (generally with real-valued basis) is known as the standard DWT. With standard DWT, signal has a same data size in transform domain, and therefore, it is a non-redundant transform. A very important property was multi-resolution analysis (MRA) that allows DWT to view and process [2].

The 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 compressed image manipulation, region of interest coding. 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.

The main feature of the lifting-based DWT scheme is to break up the high-pass and low-pass filters into a sequence of upper and lower triangular matrices and convert the filter implementation into banded matrix multiplications. Such a scheme has several advantages, including “in-place” computation of the DWT, integer-to-integer wavelet transform (IWT), symmetric forward and inverse transform. Therefore, it comes as no surprise that lifting has been chosen in the upcoming.

2 Methods Used in this Paper

2.1 Lifting Scheme of DFT

The basic principle of the lifting scheme is to factorize the poly-phase matrix of a wavelet filter into a sequence of alternating upper and lower triangular matrices and a diagonal matrix. This leads to the wavelet implementation by means of banded matrix multiplications.

Let \( \bar{h}(z) \) and \( \bar{g}(z) \) be the low-pass and high-pass analysis filters, and let h(z) and g(z) be the low-pass and high-pass synthesis filters. The corresponding poly-phase matrices are defined as [3]

$$\bar{P}(z) \left[\begin{array}{cc}\bar{h}_e (z) & \bar{h}_o(z)\\ \bar{g}_e(z) & \bar{g}_o(z)\end{array}\right] P(z) \left[\begin{array}{cc}{h}_e (z) & {h}_o(z)\\ {g}_e(z) & {g}_o(z)\end{array}\right]$$
(2.1)

If \( \left( {\bar{h},\bar{g}} \right) \) is a complementary filters pair, then it can always be factored into lifting steps as

$$\bar{P}_1(z)\left[\begin{array}{cc}K & 0\\ 0 & 1/K\end{array}\right]_{i=1}^{m} \left[\begin{array}{cc}1 & S_i(z)\\ 0 & 1\end{array}\right]\left[\begin{array}{cc}1 & 0\\ \bar{t}_i(z) & 1\end{array}\right]$$
(2.2)
$$\bar{P}_1(z)\left[\begin{array}{cc}K & 0\\ 0 & 1/K\end{array}\right]_{i=1}^{m} \left[\begin{array}{cc}1 & 0\\ \bar{t}_i(z) & 1\end{array}\right]\left[\begin{array}{cc}1 & \bar{S}_i(z)\\ 0 & 1\end{array}\right]$$
(2.3)

where K is a constant. The two types of lifting schemes are shown in Fig. 1 Scheme 1 P 1(z) which corresponds to the factorization consisting of three steps:

Fig. 1
figure 1

Lifting schemes. a Scheme1. b Scheme2

Full size image
  1. 1.

    Predict step, where the even samples are multiplied by the time domain equivalent of t(z) and are added to the odd samples.

  2. 2.

    Update step, where updated odd samples are multiplied by the time domain equivalent of s(z) and are added to the even samples.

  3. 3.

    Scaling step, where the even samples are multiplied by 1/k and odd samples by k.

The IDWT is obtained by traversing in the reverse direction, changing the factor K to 1/K, K factor to i/K, and reversing the signs of coefficients in t(z) and s(z).

In Scheme 2 which corresponds to the \( \bar{P} _{2} (z) \) factorization, the odd samples are calculated in the first step, and the even samples are calculated in the second step. The inverse is obtained by traversing in the reverse direction [4]. The discrete wavelet transform applies several filters separately to the same signal. In contrast to that, for the lifting scheme, the signal is divided like a zipper. Then, a series of convolution accumulate operations across the divided signals are applied.

The basic idea of lifting is the following: If a pair of filters (h, g) is complementary, that is, it allows for perfect reconstruction, then for every filters, the pair (h′, g) with \( h^{\prime } (z) = h(z) + s(z^{ 2} ).g(z) \) allows for perfect reconstruction too. Of course, this is also true for every pair (h, g′) of the form \( g^{\prime } (z) = g(z) + t\left( {z^{ 2} } \right).h(z). \) The converse is also true: If the filter banks (h, g) and (h′, g) allow for perfect reconstruction, then there is a unique filters with \( h^{\prime } (z) = h(z) + s\left( {z^{ 2} } \right).g(z). \) Each such transform of the filter bank (or the respective operation in a wavelet transform) is called a lifting step. A sequence of lifting steps consists of alternating lifts, that is, once the low pass is fixed and the high pass is changed in the next step, the high pass is fixed and the low pass is changed. Successive steps of the same direction can be merged [3].

2.2 Discrete Wavelet Transform of One-Level DWT

The DWT [6–8] is usually computed through convolution and sub-sampling with a couple of filters to produce an approximation signal L (low pass filter result) and a detail signal H (high-pass filter result). For two-dimensional signals, there exist separable wavelets for which the computation can be decomposed into horizontal processing (on the rows) followed by vertical processing (on the columns), using the same One-dimensional filters. Figure 2 shows a one-level decomposition. Subsequent levels are obtained by iterating on the low-pass signal LL [14].

Fig. 2
figure 2

One-level separable wavelet decomposition

Full size image

2.2.1 One-Dimensional DWT and IDWT Architecture

The multi-resolution DWT and IDWT can be viewed as cascades of several two-channel analysis and synthesis filter banks, respectively. The analysis and synthesis filter banks are shown in Fig. 3, where H(z) and G(z) are the analysis low-pass and high-pass filters. For perfect reconstruction, the synthesis low-pass and high-pass filters can be defined \( \tilde{H}(z) = G( - z)\,\tilde{G}(z) = - H( - z) \) [5]. Many very large scale integration (VLSI) architectures have been proposed to implement DWT and IDWT, and they can be categorized into three categories, including the convolution-, lifting-, and B-spline-based architectures.

Fig. 3
figure 3

Two-channel filter bank for DWT and IDWT. a Analysis filter bank for forward DWT. b Synthesis filter ban k for inverse DWT

Full size image

2.3 Two-Dimensional DWT and IDWT

A three-level two-dimensional IDWT computation-schedule scheme for the proposed architecture shown in Fig. 5 

Fig. 4
figure 4

Three-level computation-schedule scheme

Full size image
Fig. 5
figure 5

Two channel filter bank at level 3

Full size image

3 Experimental Analysis

Discrete wavelet transform is [9–11] used for the implementation of the image so that the image is compressed. And the inverse wavelet transform is used to get the original signal. The compression level is 3. Here, we used orthogonal filter. The input image is compressed by level 3. The below figure shows the compressed level (Fig. 6).

Fig. 6
figure 6

The conversion of the image by using DWT and IDWT

Full size image

The Fig. 7 shows the initial tree of the image. The initial tree divides the input signal into the high-pass and low-pass signal. The branch of the high pass and low pass again divides high pass and low pass. The sub-branch also continues up to the ending of the coefficients.

Fig. 7
figure 7

Initial tree of image

Full size image

The Fig. 8 shows the compression levels of the image. The compression level 3 is used.

Fig. 8
figure 8

Wavelet tree of image

Full size image

The Fig. 9 shows the best level tree of the image. By using best level, we can get at maximum of original image. Here, the compression level 1 is used.

Fig. 9
figure 9

Best level tree of image

Full size image

The Fig. 10 shows the original image and the compressed image. The number coefficients recovered is 99.74.

Fig. 10
figure 10

Original and compressed image

Full size image

The Fig. 11 shows the original image and the de-noised image. The stored absolute coefficients and histogram of the de-noised image.

Fig. 11
figure 11

De-noised image

Full size image

The Fig. 12 shows the histogram of the image. The standard deviation is 2.537, median absolute deviation is 0.943, and the mean absolute deviation is 1.642.

Fig. 12
figure 12

Histogram of the image

Full size image

The Fig. 13 shows the conversion of color image into gray scale image

Fig. 13
figure 13

Transmission of image by using DWT and IDWT

Full size image

Matlab is used to obtain the pixel values for the original image shown in Fig. 15. The size of the image is found to be of 128 × 128 pixels. A set of 4 × 4 pixels of the original image shown in Fig. 14 were given as test inputs. The original image input pixels, lifting-based DWT outputs/IDWT inputs and IDWT outputs are as shown in Table 1.

Fig. 14
figure 14

Original image

Full size image
Table 1 Test Results of lifting-based DWT and IDWT
Full size table

Referring to Table 1, it can be seen that the original pixels values at the input of DWT and the pixel values at the output of IDWT are same. Using IDWT output values, the original image can be reconstructed.

4 Conclusions

The color image is converted into the grayscale image. The image is compressed. The image is compressed by 3 levels by using discrete wavelet transform and the compressed image is recovered by using inverse discrete wavelet transform. The original image is recovered. The peak signal-to-noise ratio is 55.62 and mean square error is 0.178. Number of coefficients recovered is 99.94 %. Standard deviation is 2.537. Median absolute deviation is 0.943. Mean absolute deviation is 1.642.