Top 10 decomposition bases of each database
This chapter aims to present an efficient compression algorithm based on quincunx wavelet packet transform that can be applied on any image of size 128 × 128 or bigger. Therefore, a division process into sub-images of size 128 × 128 was applied on three gray-scale image databases, then pass each sub-image through the wavelet transform and a bit-level encoder, to finally compress the sub-image with respect to a fixed bit rate. The quality of the reconstructed image is evaluated using several parameters at a given bit rate. In order to improve the quality in sense of the evaluation quality, an exhaustive search has led to the best packet decomposition base. Two versions of the proposed compression scheme were performed; the optimal version is able to decrease the effect of block boundary artifacts (caused by the image division process) by 27.70 % considering a natural image. This optimal version of the compression scheme was compared with JPEG standard using the quality evaluation parameters and visual observation. As a result, the proposed compression scheme presents a competitive performance to JPEG standard; where the proposed scheme performs a peak signal to noise ratio of 0.88 dB over JPEG standard at a bit rate of 0.50 bpp for a satellite image.
- quincunx wavelet transform
- wavelet packet
- quality evaluation parameters
- reduction factor
- JPEG standard
Wavelet is defined as a small wave that can be the base of all physical phenomena; which means that a time and/or space variation of a phenomenon is a sum of multiple wavelets. As examples, the wavelet transform was applied on an electro-cardiogram (ECG) signal in order to extract the QRS complex  (time variation), on a video sequence in order to implement a hidden watermark  (time and space variation) and on a 2D image in order to reduce its size (compression) [3, 4] (space variation). In this chapter, one considers the application of the wavelet on 2D image compression.
An image is one of the most important sources of information; it provides a visual comprehension of a phenomenon. The image can take several natures as medical, natural, textural or satellite image, each nature is characterized by a proper amount of details. For a digital image, the size in bytes is as bigger as the amount of details; this applies the use of image compression process.
In other words, if one considers a gray-scale image of size , that means a bit rate of 8 bits per pixel () and a file size of bits (Kbytes). Compressing this image leads to reduce its file size (without changing the image size); for example, to reduce the file size by a factor of 10 (25.6 Kbytes), one have to consider a bit rate of .
Because of the conservation of all details in the image after decompression, the lossless1 compression algorithms, as Run Length Coding (RLE), Lempel-Ziv-Welch (LZW) and Huffman [5, 6], are by far the ideal methods. However, such a compression algorithms does not provide a significant reduction of image’s file size, and therefore the lossy2 compression algorithms may be more appropriate.
The most known lossy compression algorithm is the standard JPEG (Joint Photographic Experts Group) ; it is based, as lossy algorithm, on a discrete transform (Cosine Discrete Transform, DCT in this case). The Discrete Wavelet Transform (DWT) and Quincunx Wavelet transform (QWT) are two other discrete transforms that can be found in the literature [8, 9]; they apply a progressive transformation on the image followed by an encoding process (like Embedded Zerotree Wavelet, EZW or Set Partitioning In Hierarchical Trees, SPIHT ) to give the image a bit-level representation.
This chapter aims to propose a QWT-based compression algorithm that can be applied on any image of size or bigger. Therefore, the following structure is adopted: In Section 2, the discrete wavelet transform is introduced and the progressive presentation of an image is exposed. Section 3 is dedicated to the quincunx wavelet transform, the QWT extension to wavelet packet (PQWT) and the encoding process employing SPIHT algorithm. The PQWT-based compression algorithm is presented in Section 4, and the results and discussions in Section 5.
2. Discrete wavelet transform
As discrete sine and cosine, the DWT is used to represent a digital signal (as an image) with sum of projections over orthogonal functions; these functions are called “wavelet”. Several wavelets are described in the literature; among them, one can find dyadic Daubechies family (represented with scaling and wavelet functions in Figure 1 for four examples ).
In order to improve JPEG compression performances (in sense of evaluation parameters presented in Section 4), the researchers have proposed the JPEG 2000 compression algorithm based on a wavelet called CDF 9/7 (Cohen-Daubechies-Feauveau 9-tap/7-tap) [11, 12]. The scaling and wavelet functions, and decomposition and reconstruction low and high filters are shown in Figure 2.
2.2 Wavelet decomposition
As it is mentioned above, a wavelet applies a progressive transformation on the image. This process (called filter bank analysis) is realized by passing an image with coefficients , at time , through a decomposition low filter , a decomposition high filter and a decimation function (↓2). As a result of level 1 decomposition, one obtain an approximation image of coefficients and a detail image of coefficients . The same process is applied, at level , on the approximation to get an approximation and a detail . Figure 3 shows a wavelet 3-level decomposition.
2.3 Wavelet reconstruction
The reconstruction process (called filter bank synthesis) follows the inverse order of decomposition process, which means that, at level and time , an approximation and a detail are oversampled (↑2) and passed, respectively, through reconstruction low filter and reconstruction high filter to generate an approximation image of coefficients . Figure 4 shows a wavelet 3-level reconstruction.
A perfect reconstruction satisfies the following criteria:
where, is a normolised frequency, and () are, respectively, the Fourier transform of impulse responses and .
Figure 5 illustrates the result of applying CDF 9/7 3-level decomposition over gray-scale image ‘Lena’.
3. Quincunx wavelet transform
The decomposition and reconstruction processes using QWT remain the same as DWT; however, there are some differences:
The diamond McClellan transform  is applied to map a 1-D design onto the quincunx structure.
The decimation factor is for each direction.
The 2D quincunx refinement and wavelet filters are given respectively by:
where, is 2D pulse, is the discrete Fourier transform parameter and is filter order. All simulations in this chapter were performed considering .
The QWT 6-level decomposition of image ‘Lena’ is given in Figure 6.
3.2 Quincunx wavelet packet transform
The Wavelet Packet Transform (WP)  consists on generalizing the decomposition over all parts of the decomposed images (approximations and details) considering the following condition: a detail image is decomposed if its entropy decreases after decomposition. The literature has shown that this technique is more efficient on textural images.
Employing the packet transform on QWT (PQWT) implies that only dyadic parts of QWT decomposition are concerned, which means that the analysis time decreases.
Figure 7 shows the entropy-based PQWT 6-level decomposition of image ‘Lena’.
3.3 Set partitioning in hierarchical trees encoder
In order to compress an image employing wavelet-based transform, an encoding step is used to give a bit-level representation to the image. This chapter employs the SPIHT encoder as bit-level representation encoder. Figure 8 summarizes the relationship between decomposition levels. The authors of  had proposed a modified version of SPIHT for the wavelet packet transform; this version is adopted for the PQW transform.
4. Proposed QWT/PQWT-based compression algorithm
4.1 Compression scheme
The JPEG standard is based on dividing an image into sub-images of size , then applying the DC transform on each image. In the proposed approach, one adopts 8-level PQWT as transform algorithm and a size of for the dividing process. An example of dividing process is given in Figure 9.
The proposed compression scheme is summarized in Figure 10. It consists on applying, on each image () constituting the original image, the QW or PQW transform then the SPIHT algorithm with respect of a compression bit rate. The resulting bit streams are gathered to construct the compressed image.
In order to test the proposed compression algorithm, three gray-scale image databases were employed. The first database consists of 60 images (20 satellite images, 20 natural images and 20 medical images) of size , the second database consists of 114 textural images of size  and the third database consists of Shivang Patel 168 fingerprint images of size . Each image from databases is divided into sub-images of size (16 sub-images in case of image and 4 sub-images in case of image).
Considering packet quincunx wavelet transform, one has tested the 260 possible 8-level decompositions (called decomposition bases) on the sub-images, in order to select the optimal packet decomposition base (in sense of evaluation parameters). The performance of PQWT is compared with QWT and entropy-based PQWT decomposition base (called proper base).
4.2 Reconstruction scheme
The proposed reconstruction scheme is shown in Figure 11. The compressed image is divided into bit streams according to the number of sub-images. Each bit stream is decoded and transformed using Inverse QW or Inverse PQW transform, to finally obtain the reconstructed sub-image , (). All sub-images are then gathered to construct the reconstructed image.
4.3 Evaluation parameters of compressed image quality
Choosing a compression bit rate for gray-level image, leads to a degradation on the original image. This degradation can be measured using the evaluation parameters of compressed image quality. In this chapter, three evaluation parameters are adopted :
Peak Signal to Noise Ratio: the PSNR parameter is given by , where, is the Mean Square Error, is the original image, is the reconstructed image and designates the resolution of a gray-scale image.
Mean Structural SIMilarity index: the MSSIM index is the average over all local windows of the product of three functions as follow , where, , and are the luminance, contrast and structure comparison functions.
Visual Information Fidelity: the VIF parameter is a ratio of conditional mutual information measured over all decomposition parts of the image.
5. Results and discussion
The main purpose of this study is to establish a compression strategy using packet quincunx wavelet transform, whatever the type or the size of an image. Therefore, one has begun with applying on the 20 satellite images an exhaustive search among the 260 PQWT decomposition bases. To evaluate the compression quality employing PQWT (for a given bit rate), the relative errors (, and ) are used to distinguish between the different performance curves. These parameters are expressed as follow:
where, designates an evaluation parameter (PSNR, VIF or MSSIM) and is the average of over all database images. For a negative value of , the PQWT outperforms the QWT.
Figure 12 illustrates the best 17 decomposition bases that achieve minimum values of . Base 0 refers to QWT decomposition.
The second step consists on applying these 17 decomposition bases on the other databases, and then evaluates the compressed images quality using the relative errors given in Eq. (5). Table 1 shows for each database, the top 10 decomposition bases; and in green the five common decomposition bases between all databases.
|Base||Satellite images||Natural images||Medical images||Textural Images||Fingerprint images|
The evaluation curves in sense of relative error are shown in Figure 13. Each Figure compares the evaluation curves of the top 10 decomposition bases, in addition of the PQWT proper decomposition. It can be observed that the proper decomposition achieves fewer performances in case of satellite, textural and fingerprint images, where a visibility (VIF) average degradation of 8% is measured for fingerprint images. On the other hand, the proper decomposition curves are competitive in comparison with the other decomposition curves in case of natural and medical images, especially for at low bit rate values.
Considering the performance curves of fingerprint images (Figure 13.e), negative values of relative errors are observed at low bit rate region; which means that the chosen decomposition bases achieve better performance than base 0 (QWT).
Regarding the five common decomposition bases (marked in green in Table 1), the curves of Figure 13 show that the decomposition base 3 achieves slightly better performance; therefore, in the rest of the chapter, one adopts this decomposition base.
In order to illustrate the compression effect on the database images, one has chosen from each database the image that satisfies the minimum . The chosen images are given in Figure 14.
In Table 2, it is given the performance in sense of peak SNR of the five adopted images, for two values of bit rate (and ). These results show a tiny superiority of decomposition base 3 in comparison with base 0 and the proper decomposition; except for the medical image, where a difference of is observed between base 3 and base 0 at a bit rate of .
As observed in JPEG compression scheme, the image division into sub-images causes block boundary artifacts; these artifacts are visible at low bit rates values. This phenomenon is clearer for natural, medical and fingerprint image at a bit rate of .
To remedy to the problem of block boundary artifacts, one propose to add two processes to the compression scheme (as shown in Figure 15):
The two sub-images and overlap and have common pixels (an example of image division with overlapping is given in Figure 16),
Each sub-image is weighted by a 2D Gaussian window defined by the sub-image size and the minimum amplitude (as shown in Figure 17).
To avoid the pixel redundancy causes by the overlapping, the pixel may have value in case of two overlapped sub-image, and value in case of four overlapped sub-images. Therefore, as summarized in Figure 18, the total size of a sub-image may be expressed as follow:
In case of two overlaps, the size of the sub-image equals ,
In case of three overlaps, the size of the sub-image equals ,
In case of four overlaps, the size of the sub-image equals .
These new sub-image sizes permit to define a bit rate for each sub-image according to the number of overlaps. In other words, the bit rate of an overlapped sub-image equals:
where, denotes the bit rate without overlapping and is called the reduction factor of bit rate. The bit rate of the overall image is the average over sub-images bit rates.
In order to demonstrate the effect of the overlapping pixels () on bit rates, one has plotted in Figure 19 the reduction factor curves for . It is clear from these curves that a higher order of reduction factor leads to lower compression performance; therefore, a reduction factor threshold of has to be respected.
The proposed reconstruction scheme, given in Figure 20, divides the output of the inverse QWT or the inverse PQWT by the same 2D Gaussian windows define in the compression process. The reconstructed sub-images are overlapped with the same manner as the compression process, to construct the reconstructed image.
The evaluation curves in sense of PSNR and VIF parameters are shown in Figure 21. Each Figure compares the evaluation curves of the PQWT with decomposition base 3 and proper decomposition, in addition of the JPEG compression standard. It can be observed that:
in case of medical image (Figure 21.c), both schemes present slightly the same performance.
In Table 3, it is given the performance in sense of PSNR and VIF parameters of the five adopted images, at a bit rate of for textural image and for the others. To compare the performance of the proposed scheme (PQWT with and parameters), two other schemes are involved: the PQWT with and (referring to the first proposed scheme) and JPEG standard.
To fix and parameters of PQWT – base 3 and PQWT – proper decomposition, an exhaustive search (with respect of the reduction factor threshold) has been performed to get the maximal value of PSNR parameter. It can be observed in Table 3 that the and parameters differ from an image to another; therefore, these parameters have to be included in the compressed file, as well as the size of the overall image.
The obtained results show a tiny superiority of PQWT – base 3 in comparison with JPEG and PQWT – proper decomposition; except for natural and medical images, where the JPEG standard is slightly better.
Figure 22 compares the visual side of the five adopted compressed images, where details of size from original, PQWT – base 3 and JPEG images are magnified. From these figures, it can be observed that PQWT compressed images present lower block boundary artifacts effect in comparison with JPEG images (especially for satellite and textural images), and preserve the continuity of their detail shapes.
For a deep study of the block boundary artifacts effect between both proposed compression schemes employing PQWT – base 3, one have focused only on the overlapping regions in the five adopted images, where bands of 8 pixels per line and column around these regions are extracted in order to measure the effect of block boundary artifacts in sense of PSNR. By denoting and the measured PSNRs of the extracted regions employing, respectively, the first and second proposed schemes, the average block boundary artifacts effect is measured by
where, values of the bit rate () from up to are employed to evaluate the PSNRs.
In Table 4, the values of are given for the five adopted images. From these results, it can be concluded that, in comparison with the first compression scheme, the second proposed compression scheme presents a significant reduction of 27.70% and 22.87% of the effect of block boundary artifacts for, respectively, natural and medical images. However, a tiny reduction of for fingerprint image is observed, which means that further processing on sub-images boundaries is necessary for such an image using local 2D filters .
|Image||Satellite image||Natural image||Medical Image||Textural Image||Fingerprint image|
This chapter introduces an image compression scheme that employs quincunx wavelet decomposition improved by wavelet packet. This process permits to focus on both approximation and detail parts of the image decomposition.
Using the concept of image division into sub-images (employed in JPEG standard compression algorithm), the effect of block boundary artifacts has occurred especially at low range of compression bit rates. To overcome this problem, the sub-images are weighted by a 2D Gaussian window and overlapped with respect to the reduction factor of compression bit rate. This means that, in addition of the overall image size, two parameters have to be included in the compressed file: the minimum amplitude of 2D window and the number of overlapped pixels.
To present the proposed compression algorithm as a standard, its performances were compared, in sense of evaluation parameters, to those of JPEG standard. The main improvement was seen in the capacity of the proposed scheme to provide better image visual quality (detail shapes continuity). This means that, in the first hand, it can be possible to reduce the image file sizes without reducing the image visual quality, and increase the storage capacity in photographic devices in the other hand.
As a result, this compression technique permits to create benchmarks and databases with low capacity whatever its nature (satellite, medical, natural or textural image).
In this work, one have focused on gray-scale images in order to present the proposed compression scheme. It is necessary, in future works, to investigate its efficiency on video and color images compression.
Conflict of interest
The author declare that there is no conflict of interest.
Run Length Coding
Joint Photographic Experts Group
Cosine Discrete Transform
Discrete Wavelet Transform
Quincunx Wavelet transform
Embedded Zerotree Wavelet
Set Partitioning In Hierarchical Trees
Packet-based Quincunx Wavelet transform
Inverse Quincunx Wavelet Transform
Inverse Packet-based Quincunx Wavelet Transform
Peak Signal to Noise Ratio
Mean Structural SIMilarity index
Visual Information Fidelity
- The term “lossless” refers to the conservation of all details in the image after reconstruction, which means that the original and reconstructed images are identical.
- The term “lossy” refers to the loss of details in the image after reconstruction by quantification or truncation, which means that the original image differs from the reconstructed one.