New Edge-Directed Interpolation Based-Lifting DWT and MSPIHT Algorithm for Image Compression

Show more

Received 2 April 2016; accepted 11 April 2016; published 18 July 2016

1. Introduction

Today multimedia applications heavily rely on image data’s in which needs efficient image compression technique is necessary. There are two different solutions when we speak about image compression, lossy and lossless image compression. Currently large varieties of image compression techniques exist. Some of the transform coding techniques are utilizing discrete cosine transform (DCT), Discrete Wavelet Transform (DWT), KL Transform (KLT), and predictive coding techniques. Image compression is the key enabling technique in multimedia applications; it has wide and important applications in day to live. The two important techniques are DWT and SPIHT; these are got more and more important image compression because of its high PSNR value with better compression ratio and good quality of image reconstruction. As a lossy image compression algorithm, discrete cosine transform (DCT) is the most mature compression algorithm. Under the condition of large image compression ratio will produce large image artifacts and edge effects. Wavelet transform gives the better solution for this problem.

Discrete wavelet transform (DWT) is one of the famous techniques for image compression [2] - [6] . Traditional DWT lifting scheme is usually applied in horizontal and vertical directions, but it fails to provide efficient representation of geometric characteristics of an image. It is subband coding technique which distributes energies. DWT alone cannot represent geometrical characteristics of image. To overcome these problems, a lot of new techniques have been employed. Some of the techniques are curvelets [9] , contourlets [10] , bandelets [11] [12] and wedgelets [14] . But all these have high computational cost and their filter designs are complex and also they are not impressed to use image compression particularly.

Adaptive wavelet transform is carried over in the early work, the image partitioned into small blocks then apply reversible resampling filter to each blocks and edges are sheared. The conventional method of 2D-DWT is applied to sheared blocks these provide vanishing moments along the edges [13] . This problem can be efficiently handled another technique called directionlets with simple filter design. But anyhow both of these methods have some limitations. Because the above said two methods are handling images with small blocks which was produced again the blocking artifacts in the reconstruction of an image. To overcome these limitations by using bandelets technique proposed in [11] [12] , the directional correlation in the detailed wavelet coefficients removed by using conventional DWT after bandeletization procedure is followed. After the block wise operations are carried over in the wavelet domain, the approximate coefficient is same as conventional DWT, the blocking artifacts neither observed. In this approach also the problem still cannot be solved. The conventional DWT has been applied before doing bandeletization because post processing technique still based on wavelet transform. Another important technique called lifting scheme is well suited to overcome the above said problems. This method ensures better reconstruction. Lots of research was carried by many authors based on directional approaches with lifting scheme. Another method proposed in [18] lifting based separable directional based wavelet transform. Most of the method employed conventional DWT as a base failed to produce significant improvement.

In this paper we first propose new edge-directed interpolation-based lifting DWT. The proposed method differs from other lifting based DWT. It provide more efficient with less computation cost and along with MSPIHT algorithm for image compression. NEDI algorithm is the interpolation method to preserve the geometric characteristics such as edges and lines in an image. In our approach we concentrate to get more energy compaction by introducing interpolation method, lots of interpolation methods are there, we have chosen NEDI because it preserves the edge which is degraded normally while doing compression. Then we use Lifting DWT scheme instead of conventional DWT, the first work is NEDI with Lifting scheme is proposed. The second work is NEDI with Lifting DWT applied to modified SPIHT algorithm for image compression. The New Edge Directed Interpolation with Lifting DWT is discussed in Section 2. The SPIHT algorithm for image compression and MSPIHT algorithm for image compression is presented in Section 3. The simulation results and analysis are reports in Section 4. The conclusions are drawn finally in Section 5.

2. New Edge Directed Interpolation-Based Lifting DWT

The reconstruction of geometric characteristics of image such as edges and lines are important whenever doing image compression in multimedia applications. The interpolation methods are more suitable for preserving the edges and lines particularly. Lot of interpolation methods is available; some of the interpolation methods are listed here including the two traditional methods. The traditional methods are bilinear and bi-cubic interpolation.

There are four edge-directed interpolation methods. These are the methods which includes new edge directed interpolation (NEDI), edge-guided image interpolation (EGII), iterative curvature based interpolation (ICBI) and directional cubic convolution interpolation (DCCI). In this paper new edge directed interpolation (NEDI) is applied to get good quality of image [1] . NEDI algorithm is based on geometric duality between Low resolutions (LR) and High Resolutions (HR) image. To obtain HR local covariance coefficients from its LR counterpart, let us assume that the LR image P_{x}_{,y} of size M × N comes directly from size of 2M × 2N. i.e.,. Here apply the new algorithm NEDI then interpolate the interlacing lattice from the lattice. The fourth order linear interpolation formula:

(1)

Figure 1 shows the four nearest neighbors. The natural image source is assumed to be a design of locally stationary Gaussian process. The optimal MMSE linear interpolation coefficients are given by classical Wiener filtering theory [21] as

(2)

where (0 ≤ k, l ≤ 3) and, (0 ≤ k ≤ 3) are the local covariance of HR. For example r_{0} defined by as shown in Figure 1. This is the missing pixel and interpolate. Normally one question arises is it possible to get HR image covariance from LR image resolution. But it can be estimate HR covariance from LR covariance which characterizes relationship between covariance and resolution. The first step starts with edge model in one dimensional case. The sampling distance at LR and HR are represented by 2a and a. The relationship between normalized covariance and the sampling distance y is defined by stationary Gaussian process:

(3)

The equation S(a) = S(2a)^{1/4} links the covariance of HR to LR. For simplicity S(a) is replaced by S(2a) when the sampling distance a goes to 0. Successfully acquiring the knowledge of HR covariance for 2D images, the orientation is the important factor. Geometric regularity is one of the important fundamental properties of edges [19] . This orientation related property directly affects the visual quality around the edges.

The sufficient information of local covariance is used to determine orientation. But estimate the orientation from local covariance which has the limitation discussed earlier methods. Based on geometric duality, the HR covariance from its LR has estimated. Geometric duality is nothing but the relationship between HR covariance and LR covariance couple their pair of pixels at different resolution but same orientation. When interpolate the interlacing lattice from the HR covariance, and LR covariance of geometric

Figure 1. Geometric duality when interpolating from.

duality as shown in Figure 1. Estimation of local covariance for 2D signals, geometric duality facilitates the estimation of orientation is not necessary. Figure 2 shows the similar geometric duality, when interpolating the interlacing lattice from the lattice. Both Figure1 and Figure 2 are isomorphic. The scaling and rotation factor are 2^{1/2} and π/4. The HR and LR covariance are being related, the existing covariance estimation and covariance based adaptation methods linked together. By using classical covariance method [21] the LR covariance is estimated by,

(4)

where is the data vector containing the N × N pixels inside in the local window. C is a 4 × N^{2} data matrix. The k^{th} column vector is the four nearest neighbors of x_{k} along the diagonal direction. Therefore according to the Equations (2) and (4), we have

(5)

Therefore the interpolated value obtained by substituting (5) in (1).

The NEDI algorithm depends on covariance based adaptation method. The main drawback of this method is high computational complexity. It requires more number of multiplications (nearly 1300) when we select the min size of local window (size N = 8). The complexity is increased order of two compared to linear interpolation method, if we apply covariance based adaptation method to all pixels. Instead of that apply hybrid approach: the covariance based adaptation method is applied only to edge pixels, and bilinear interpolation method has been applied for non-edge pixels. Now the complexity is reduced because the edge pixels are less percentage that only has the benefit of covariance based adaptation method.

Figure 2. Geometric duality when interpolating from.

3. SPIHT Algorithm

Multimedia applications the image compression plays vital role. For the past few years lots of wavelet based image compression algorithms have been developed. Among those SPIHT is the more familiar wavelet based image compression algorithm [8] . It provides excellent performance in terms of PSNR and image quality while reconstruction. It is based on progressive transmission and spatial scalability. But it has limitation of inefficient coefficient partitioning method. It requires large memory to store their lists. The repetitive scanning procedure in the SPIHT algorithm, which reduces the speed of the coding procedure. Here a little bit modification of SPIHT algorithm is carried over to reduce the limitations of the traditional SPIHT algorithm. The modification reduces bits redundancy and scanning redundancy which can reduces the coefficients re-ordering.

3.1. SPIHT Image Compression

Three different lists are used to store significant information of wavelet coefficients. Three lists are list of insignificant set (LIS), list of insignificant pixels (LIP) and list of significant pixel (LIP). The first step of SPIHT algorithm combines wavelet coefficients of a node and its successor nodes into one set called LIS. Travels along LIS of each node are partitioned into four different subsets. Each subset is tested for significant state. The testing of set significant is carried over by the function using the following formula [15] - [17] :

(6)

where C_{x,y} is the coefficient value for (x, y) position in the wavelet domain. The ρ stands for the set of coefficients and S_{n}(ρ) is used for significant state of set ρ at bit plane n. The coefficient value in the set is less than the threshold value, and then set is insignificant. Hence a bit is emitted. This is the reason, SPIHT algorithm use minimum bits for wavelet coefficients.

3.2. Modified SPIHT Algorithm

The traditional SPIHT algorithm needs more storage space to store their three lists and which has more number of scanning process of their coefficients. Many authors have proposed modifications in the SPIHT algorithm. One of the modifications proposed in [20] is to increase the speed of the algorithm by not using the lists. Here the modification in SPIHT algorithm is made for image compression to reduce the number of bits and scanning redundancies. There are two type sets used for scanning wavelet coefficients of a node with a threshold value which decides the wavelet coefficients significant or insignificant. By using modified SPIHT algorithm reduces the output one bit less than the traditional SPIHT [7] . The modification is based on whether the threshold value is too small or big. The traditional SPIHT need 4 bits output to determine the important of child node. This value is taken to decide the threshold value is greater than or less than 4. If the threshold is too small almost the O-set is not used.

The traditional SPIHT is used whenever the threshold is smaller. While the threshold value is large the O-set replaces four grandchildren nodes of the following scan, and it can reduce the bits. While scanning D-set, there are duplicate scanning because of modification reduces the unnecessary scans. While scanning D-set the important coefficients is found, it should determine whether it is direct child node. Whether it is positive, it can be determined by returned value in the following rules which improves the scanning efficiency. These are the steps of the LIS scanning procedure of the modified SPIHT algorithm which is given in the flowchart in Figure 3. The MSPIHT algorithm initially set the threshold value is a maximum value of coefficient, then set child node as a root node. Its start from LIS and check if it’s a type-D set, then the coefficient value is important, send output ‘1’ for each coefficient. Further its continuation is based on the threshold value. In the same time if it’s a type-L and checks these coefficients and further continuation is as said earlier. And then another set called type-O is introduced to reduce the bits and scanning redundancies and check for the importance which is given in the flowchart. The procedure continues until the LIS value is empty. The modified algorithm performs LIS scanning for one time and deal three different sets. Repeat the steps update the threshold n = n − 1 until n = 0.

4. Simulation Results

In this part, we first discuss the performance of new edge directed interpolation (NEDI) with other

Figure 3. Flowchart of MSPIHT algorithm.

non-interpolation methods and the performance of modified SPIHT algorithm for image compression.

4.1. Experiment I: Performance of NEDI Algorithm with Lifting DWT

NEDI algorithm is mainly used for preserving edges and lines to made good quality of image. So we concentrated NEDI along with Lifting DWT to improve energy level. Our simulation results got improved while performing Lifting scheme with NEDI, its energy level 1.07% higher than 5/3 wavelet and 0.94% higher than the traditional DWT. Table 1 shows the percentage of subband energies of whole image. The comparative analysis of subband energies of traditional DWT, 5/3 wavelet and NEDI with Lifting DWT was listed in Table 1.

The energy is more concentrated in the low frequency ranges by using NEDI based lifting DWT. Among those NEDI with Lifting DWT performs better subband energies in the low frequency images, so subsequent coding process in image compression is well effective. The NEDI method preserves the edge information to get good visual quality of image. There are three methods such as traditional DWT decomposition, 5/3 wavelet decomposition and NEDI with Lifting DWT decomposition were taken for analysis. Figure 4 shows the first level of decomposition Lena image for traditional DWT Decomposition, 5/3 Wavelet and NEDI with Lifting DWT.

4.2. Experiment II: Performance of SPIHT Algorithm

The SPIHT is well standard algorithm in the field of image compression. In Table 2 the traditional SPIHT algorithm results are taken from the reference [8] for comparative analysis. Then we have implemented traditional SPIHT without Arithmetic coding. Our simulation results are listed in Table 2. Before applying the MSPIHT algorithm for image compression, we have got the higher energy compaction by using NEDI with lifting DWT from the experiment I which is applied in modified SPIHT algorithm by introducing another set called type-O in the SPIHT algorithm, to preserve the geometric characteristics of images which are normally blurred when we are doing image compression. Table 2 shows the experimental results of traditional SPIHT, traditional SPIHT (without arithmetic coding) and the proposed MSPIHT (without arithmetic coding) method. In Figure 4 Shows the Experimental results of reconstructed Lena image by applying Traditional DWT decomposition with SPIHT algorithm, 5/3 Wavelet decomposition with SPIHT and NEDI with Lifting DWT decomposition with MSPIHT. The proposed method has almost the same PSNR value with traditional method, but the modification of SPIHT algorithm which reduces bits and scanning redundancies. The proposed method in Figure 5(d) shows the edges are preserved. The experimental results of PSNR (dB) values of traditional and proposed method are shown in Figure 6. The minimum MSE values are graphically represented in Figure 7.

Table 1. Percentage of subband energy of whole image.

(a) (b) (c)

Figure 4. First Level of Wavelet Decomposition of Lena Image (a) Traditional DWT Decomposition (b) 5/3 Wavelet Decomposition (c) NEDI with Lifting DWT Decomposition.

Table 2. Comparison between traditional and Proposed SPIHT (PSNR in dB).

(a) (b)(c) (d)

Figure 5. Reconstructed Lena Image (a) Origional Image (b) Traditional DWT (c) 5/3 Wavelet Decomposition (d) NEDI with Lifting DWT Decomposition.

4.3. Experiment III: Performance of MSPIHT Algorithm with NEDI

Table 3 shows the experimental results of different standard images of the proposed MSPIHT method. The standard images were taken for experiments which are having higher geometric characteristics. The interpolation algorithm is mainly used to preserve the geometric characteristics of an image. The different standard images were taken for analysis and there PSNR (dB) values are computed for bit rate 0.9 bpp. The experimental results of different standard images were graphically represented in Figure 8. The experimental results show that NEDI along with MSPIHT image compression gives better performance particularly at edges.

Figure 6. Comparison of PSNR (dB) values of traditional SPIHT and proposed MSPIHT algorithm.

Figure 7.Comparison of mean square error (MSE) values of traditional and proposed MSPIHT algorithm PSNR.

5. Conclusions

Image compression plays important role in multimedia applications. DWT and SPIHT are widely used techniques. The paper mainly focused on the wavelet image coding compression. Our work is focused on the following aspects.

1) The first work of this paper is based on new edge directed interpolation method with lifting DWT scheme. In this method NEDI algorithm combined with lifting DWT. The geometric information of an image is preserved by the interpolation method. The experiment results proved that NEDI with lifting DWT has better energy levels than the conventional lifting scheme. The image visual quality is good.

Table 3. PSNR (dB) values of standard images using proposed MSPIHT method.

Figure 8. PSNR (dB) values of different standard image of proposed MSPIHT algorithm.

2) The second work of this paper is MSPIHT algorithm for image compression. The modification reduces the bit and scanning redundancies compared with traditional method. The experimental results in Table 2 showed that the algorithm reduces bits and run time without compromising the quality of image and thus the PSNR value is improved.

Future Work

The methods employed in this paper 1) NEDI algorithm is preferred for preserving edge information but it has limitation of time consuming which will be overcome by fast edge directed interpolation. 2) The SPIHT algorithm implemented in this paper without arithmetic coding stage, the future work can include MSPIHT algorithm with AC which will improve the PSNR value further. 3) To improve more picture quality and to reduce computational complexity, Lifting DWT with Fast edge directed algorithm can be implemented in future.

References

[1] Li, X. and Orchard, M.T. (2001) New Edge-Directed Interpolation. IEEE Transactions on Image Processing, 10, 1521- 1527.

http://dx.doi.org/10.1109/83.951537

[2] Grgic, S., Grgic, M. and Zovko-Cihlar, B. (2001) Performance Analysis of Image Compression Using Wavelets. IEEE Transactions on Industrial Electronics, 48, 682-695.

http://dx.doi.org/10.1109/41.925596

[3] Chen, N., Wan, W. and Xiao, H.D. (2010) Robust Audio Hashing Based on Discrete Wavelet Transform and Nonnegative Matrix Factorization. IET Communications, 4, 1722-1731.

http://dx.doi.org/10.1049/iet-com.2009.0749

[4] Antonini, M., Barland, M., Mathieu, P. and Daubechies, I. (1992) Image Coding Using the Wavelet Transform. IEEE Transaction on Image Processing, 1, 205-220.

http://dx.doi.org/10.1109/83.136597

[5] Hilton, M.L., Jawerth, B.O. and Sengupta, A. (1994) Compressing Still and Moving Images with Wavelets. Multimedia systems, 2, 218-227.

http://dx.doi.org/10.1007/BF01215399

[6] Taubman, D. and Marcellin, M.W. (2002) JPEG 2000 Image Compression: Fundamentals, Standards and Practice. Kluwer, Dordrecht.

http://dx.doi.org/10.1007/978-1-4615-0799-4

[7] Fang, Z.J., Xiong, N.X., Yang, L.T., Sun, X.M. and Yang, Y. (2011) Interpolation-Based Direction-Adaptive Lifting DWT and Modified SPIHT for Image Compression in Multimedia Communications. IEEE Systems Journal, 5, 584- 593.

[8] Said, A. and Pearlman, W.A. (1996) A New, Fast and Efficient Image Codec Based on Set Portioning in Hierarchical Trees. IEEE Transactions on Circuits Systems Video Technology, 6, 243-250.

http://dx.doi.org/10.1109/76.499834

[9] Cands, E.J. and Donoho, D.L. (1999) Curvelets a Surprisingly Effective Non Adaptive Representation for Objects with Edges. In: Curve and Surface Fitting: Saint-Malo, University Press, Nashville, TN, 105-120.

[10] Do, M.N. and Vetterli, M. (2005) The Contourlet Transform: An Efficient Directional Multiresolution Image Representation. IEEE Transactions on Image Processing, 14, 2091-2106.

http://dx.doi.org/10.1109/TIP.2005.859376

[11] Pennec, E.L. and Mallat, S. (2005) Sparse Geometric Image Representation with Bandeletes. IEEE Transactions on Image Processing, 14, 423-438.

http://dx.doi.org/10.1109/TIP.2005.843753

[12] Peyre, G. and Mallat, S. (2005) Surface Compression with Geometric Bandelets. ACM Transactions on Graphics, 24, 601-608.

http://dx.doi.org/10.1145/1073204.1073236

[13] Taubman, D. and Zakhor, A. (1995) Orientation Adaptive Subband Coding of Images. IEEE Transactions on Image Processing, 3, 421-437.

http://dx.doi.org/10.1109/83.298396

[14] Donoho, D.L. (1999) Wedgelets: Nearly Minimax Estimation of Edges. The Annals of Statistics, 27, 859-897.

http://dx.doi.org/10.1214/aos/1018031261

[15] Liu, K., Belyaey, E. and Guo, J. (2012) VLSI Architecture of Arithmetic Coder Used in SPIHT. IEEE Transactions on Very Large Scale Integration Systems, 20, 697-710.

http://dx.doi.org/10.1109/TVLSI.2011.2109068

[16] Chopra, G. and Pal, A.K. (2011) An Improved Image Compression Algorithm Using Binary Space Partition Scheme and Geometric Wavelets. IEEE Transactions on Image Processing, 20, 270-275.

http://dx.doi.org/10.1109/TIP.2010.2056378

[17] Wang, Z. and Bovik, A.C. (2011) Embedded Foveation Image Coding IEEE Transactions on Image Processing, 10, 1397-1410.

[18] Ding, W., Feng, W. and Li, S. (2004) Lifting-Based Wavelet Transform with Directionally Spatial Prediction. Proceeding of Picture Coding Symposium, San Francisco, 483-488.

[19] Mallat, S.G. (1998) A Wavelet Tour of Signal Processing. Academic, New York.

[20] Wheller, F.W. and Pearlman, W.A. (2000) SPIHT Image Compression without Lists Proceedings of IEEE International Conference on Acoustic Signal Processing, Istanbul, Vol. 4, 2047-2050.

http://dx.doi.org/10.1109/icassp.2000.859236

[21] Jayant, N. and Noll, P. (1984) Digital Coding of Waveforms: Principles and Applications to Speech and Video. Prentice-Hall, Englewood Cliffs, NJ.