Analysis of Wavelet Compression and Seam Carving Using the Hausdorf Distance

Abstract

In this paper image quality of two types of compression methods, wavelet based and seam carving based are investigated. A metric is introduced to compare the image quality under wavelet and seam carving schemes. Meyer, Coiflet 2 and Jpeg2000 wavelet based methods are used as the wavelet based methods. Hausdorf distance based metric (HDM) is proposed and used for the comparison of the two compression methods instead of model based matching techniques and correspondence-based matching techniques, because there is no pairing of points in the two sets being compared. In addition entropy based metric (EM) or peak signal to noise ration based metric (PSNRM) cannot be used to compare the two schemes as the seam carving tends to deform the objects. The wavelet compressed images with different compression percentages were analyzed with HDM and EM and it was observed that HDM follows the EM/PSNRM for wavelet based compression methods. Then HDM is used to compare the wavelet and seam carved images for different compression percentages. The initial results showed that HDM is better metric for comparing wavelet based and seam carved images.

1. Introduction

The rapid growth of wireless communication systems has increased the demand for robust multimedia transmission with better quality, coverage, and more power and bandwidth efficiency. The restriction of the wireless communication channels like limited bandwidth increases the demand for more reliable and better quality multimedia communication systems, specifically to develop transmission techniques that do not consume more bandwidth while achieving better received image quality. One way of sending high-quality images through band limited wire/wireless communication channels can be achieved by applying the proper compression technique depending on the transmission capacity, type of the image and the download time of the file as the independent variables [1]-[3]. The proper compression technique can be identified as the selected method of compression and the respective compression percentage according to a metric.

The evaluation of lossy techniques is extreme difficult when describing the type and amount of degradation in reconstructed images. Due to the problems related with the subjective measures of image quality, there are lots of research has been done in order to develop a reliable quantitative measure.

The most commonly used metric for measuring compression is based on image quality which can be defined as signal to noise ratio (PSNR) or mean squared error (MSE) [18]. However, they often fail when evaluating the image quality with different compression techniques. Even more importantly, the metrics do not measure object shape or boundary variations such as edges due to the compression techniques.

There are prominent reviews of image quality metrics have been done during the last few decades. The research done by, Ahumada [4] provides a concise summary of perceptual metrics applied to image quality research. Jayant et al. [5] describe how perceptual characteristics have been applied to signal compression. The research work by Daly [6] provides a number of visual factors which should be integrated in a perceptual metric in order to evaluate image quality. According to Eskicioglu [7] have proved a number of quality metrics. The research done by S. Fernando and R. Wijesiriwardana [8] has showed how entropy can be used as a metric [EM] to evaluate loss of information due to compression techniques such as wavelet based methods and seam carving. However due to the image geometric complexities EM methods found to be difficult to use in seam carved method [8].

In this research the authors have introduced the Hausdorf distance metric [9] to assess the change of images due to compression techniques such as wavelet based method and seam carving by computing the amount of resemblance of shape of the objects.

Wavelet based methods and seam carving were used as compression schemes. Where Meyer, Coiflet2 [10], [11], and JPEG2000 [12] wavelets based compression methods were experimented together with an energy based seam carving method [13].

In order to select a proper method out of the methods used a metric is required and EM based metrics have been researched for the wavelet transformation based methods [14]-[17]. However when comparing seam carving method and wavelet methods a new metric is required as EM based metrics is not ideal for measuring the quality of the seam carved image as pixel coherence is preserved and only the shapes are distorted in a seam carved image. Moreover model based or correspondence based matching techniques cannot be used as the number of points being different on compressed images. Therefore we used Hausdorf distance based metric (HDM) [9] to compare the compressed images.

First part of this research we compare the wavelet based compression methods with EM and HDM and It was found out that they are comparable. Hence HDM can be used as a valid metric to measure the image distortion in wavelet based compressed images.

The second part of the research we used HDM to compare energy based seam carved images with different compression percentages and it was found that HDM is a good metric to compare the image distortion in seam carved images.

The third part of the research we have compared the Meyer, Coiflet 2, JPEG2000 and seam carved images based on HDM. The theory, method and the results are discussed in the following chapters.

2. Wavelet Based Image Compression

The rapid advancement in wavelet technology has led to advanced standards for image compression which is based on discrete wavelet transform (DWT). It has brought a new surge of interest in wavelets and also towards advancement and faster computational algorithms for storing and transmission of images

In this research two families of wavelets namely, Meyer and Coiflet 2 wavelets and JPEG2000 are used for the compression. The Equations (1) and (2) shows the Meyer scale and wavelet functions and JPEG2000 is based on defined two wavelet transformations namely CDF9/7 and CDF(5/3). Each layer of JPEG2000 adds coded information to improve the quality of the image [12].

(1)

(2)

2.1. Seam Carving

Seam carving is a technique targeting image compression and resizing based on detection of seams from the energy function of the image. The method aims at finding seams of minimum energy and manipulating the image by carving out these seams [13].

Effective resizing of images not only use geometric constraints, but consider the image content as well. Conventional image resizing consists of cropping or evenly down sampling that lead to loss of important features or distortion. Seam carving method enables us to remove pixels from uninteresting parts of the image while preserving important content. The cumulative energy function is defined by Equation (3).

(3)

And the backtracing in x direction can be represented mathematically as shown in Equation (4).

(4)

2.2. PSNR Based Metric

PSNR is used as a general metric to measure the quality of restoration of lossy or lossless compression of images. The signal denotes the original data, and the noise represents the error introduced by compression. However, a higher PSNR generally indicates that the reconstruction is of higher quality, in some cases it may not be true. The PSNR is defined as,

(5)

where,.

The, is the maximum possible pixel value of the image. I, J denotes the original and compressed images respectively.

2.3. Entropy Based Metric

The entropy can be used as a statistical measure of uncertainty to characterize the texture of an image [11]. If a random variable X takes on values in a set

and is defined by a probability distribution, then the entropy of the random variable can be written as,

(6)

2.4. Hausdorf Distance Based Metric

Hausdorf distance is a metric between two point sets [9]. Since this is applied to digital images the dimensions of the two point sets were restricted to two dimensions.

Let and denote two finite point sets. Then the Hausdorf distance is defined as,

where,

and is some underlying norm on the points of A and B.

The function is called the directed Hausdorf distance from A to B.

The Hausdorf distance is the maximum of and. Thus it measures the degree of mismatch between the two sets by measuring the distance of the point of that is farthest from any point of and vice versa.

3. Analysis

Different types of images are selected for the testing. The images are selected so that they will cover the common types of photographic images. The compression percentages of 35%, 50%, 70% and 90% are used for each type of image respectively and the entropy and Hausdorf distance were calculated by using MatLab™ built in functions. Figure 1 shows the 7 images used.

3.1. EM and HDM Results of Wavelets Based Compressed Images

The Figure 2 shows the plot of EM vs. the HDM at different percentage compression ratios. All three methods of wavelet transformations were used for the analysis.

At 35%, r value of 0.98 and p value of less than 5% are observed. At 70%, r value of 0.98 and p value of less than 5% is observed. At 90% r value of 0.7 and a p value less than 5% is observed. Between the EM and HDM values a linear relationship is observed at 35% to 90% percentage compressions. Also at higher compression percentages above 90% less r lower than 0.7 were observed.

Figure 1. Seven images used for testing.

Figure 2. EM vs HDM wavelet compression results.

3.2. EM and HDM Results of Seam Carving Based Compressed Images

The EM vs. HDM data of the seam carved images are shown in Figure 3. Poor linear relationship is observed between EM and HDM. This is expected as EM has limitations for the seam carved images.

3.3. HDM on Meyer and Coiflet 2 Wavelet Compression Schemes

Figure 4 shows the HDM on Meyer wavelet compressed images. The X axis is the Image number and the Y axis is the HD value.

It was observed that change of the HD values is significant after 70% of compression. For all 7 images increasing HD values are observed with the compression percentage.

Figure 5 shows the HDM on Coiflet 2 wavelet compressed images. The X axis is the Image number and the Y axis is the HD value. It was observed that that change of the HD values are significant after 70% of compression similar to the Meyer wavelet compressed images. For all 7 images tested increasing HD values are observed with the compression percentage.

Figure 3. EM vs HDM seam carving based compression.

Figure 4. HDM of Meyer wavelet compressed images.

Figure 5. HDM of Coiflet 2 wavelet compressed images.

The tabulated data are show in Table 1. Similar graph profiles were observed with the Coiflet 2. Figure 6 shows the Coiflet 2 vs. Meyer HD values. We have observed a linear relationship with an average slop of 1 and r value of 0.98 at a less than 5% p value. The r and slope values are given in Table 2.

Regression results of HD values of Meyer and Coiflet 2 based compressed images at different compression percentages.

3.4. HDM on JPEG 2000 Compressed and Seam Carved Images

Figure 7 shows the HDM on the JPEG2000 compressed images. Unlike the Meyer and Coiflet 2 methods. For all 7 images increasing HD values with the compression percentages are observed.

Figure 6. HDM of Coiflet 2 vs Meyer wavelets compressed images.

Figure 7. HDM of JPEG 2000 compressed images.

Table 1. HD values of seven images (Meyer and Coiflet 2 wavelets) with compression %.

Table 2. Regression results.

Figure 8 shows the HDM on the seam carved compressed images. For all seven images an increasing HD values with the compression percentages are observed.

The HD data of the JPEG2000 and seam carving schemes are shown in the Table 3.

Figure 9 shows seam caved HD values vs. JPEG2000 compressed HD values. It is observed that they both having proportional relationship for all images tested except few. However it was also observed that the nature of proportionality is depend on the image type and the compression percentage (Figure 9).

4. Discussion

The initial experimental data showed HDM can be used as a metric in different compression schemes specially to measure the quality of the seam carved images. However more testing is required with different image types to justify HDM as a Metric for comparing different compression schemes.

In addition seam carved images showed better image quality in identifying objects over 70% compression

Figure 8. HDM of seam carved images.

Figure 9. HDM of seam carved vs JPEG 2000 compressed.

Table 3. HD values of seven images (seam carved and JPEG 2000) with compression %.

percentages with respect to Meyer and Coiflet 2 wavelet based compression schemes. Moreover with images having textual data seam carved images preserved the information better than the Meyer or the Coiflet 2 schemes images at the same compression percentage (Figure 10). The images with large curved objects were severely distorted under the seam carved scheme (Figure 11) above 90% compression.

Comparing 90% compression of seam carving and JPEG2000, the JPEG2000 shows the entire image while seam carving has removed low energy plane areas while preserving high energy geometrical details (Figure 12).

The following table shows how the HDM varies based on two compression techniques.

Figure 10. Comparison of seam carved and Mayer wallet compressed image I_{2}.

Figure 11. Comparison of seam carved and Mayer wallet compressed image I_{3}.

Figure 12. Comparison of seam carved and JPEG2000 compressed image I_{4}.

In JPEG2000 at 90% the detail features which shows the geometry or shape of the buildings has considerably been removed while seam carving preserves the detail geometry and the hue of the high energy objects. Table 4 shows that there is not much difference (0.21%) in HDM for seam carving while JPEG2000 shows a considerable change (17.24%) of HDM from 70% to 90%. Table 5 also has similar results. Which is a good indication of HDM being a better metric than that of PSNRM that depend on the hue and the noise.

However images with comparatively close energies of the seams, the comparison of seam carved and JPEG2000 is reversed. In Figure 13, seam carving has removed seams from the objects thereby changing the geometry or shape of the object. However, the JPEG2000 removes detail geometry and hue contrast from the image while preserving overall image features.

Table 6 shows this shape or geometrical difference with HDM while the PSNRM is unable to measure this variation as PSNR is increased in seam carved image and decreased in JPEG2000 image without any coherence with the geometrical variation of the two images. In addition even though the HDM has increased in under the both schemes, the effect of lower HDM variation (25% in JPEG2000 compressed and 30% in seam carved) is an indication of better preservation of geometry in the JPEG2000 compressed images for images with lower seam energies.

Figure 14 shows the compression of images using seam carving at 70% and 90%. Here we can observe that when compression increases the seams from sky area has been removed dominantly. This affects the image geometry in a minimum level and thus the HDM values does not show considerable change. However, the

Table 4. HDM and PSNR of I_{4}.

Table 5. HDM and PSNR of seam carved Veg and I_{4}.

Table 6. HDM and PSNR of I_{1}.

Seam Carved 90% JPEG2000 90%

Figure 13. Comparison of seam carved and JPEG 2000 compressed image I_{1}.

PSNR shows a higher difference and can be seen from the Table 4.

Also in Table 7 and Table 8 it can be clearly seen that the PSNRM is not a good metric with the percentage compression as the variation of the values are inconsistence from image to image. This is another indication that HDM is a better metric than the PSNRM at higher compression percentages.

In Figure 15, the images I_{1} and I_{2} has less variation in energy seams. Therefore when compressing at 70% and 90% seams containing geometrical features (mainly edges representing the object shape) has removed. Thus resulting a considerable change in shape. Both JPEG2000 and seam carving method can preserve the textual data.

Further we observed that the I2 PSNR and I1 PSNR are inconsistent and HDM maintained its consistency.

JPEG2000 90% seam carved 90%

Figure 14. Comparison of seam carved and JPEG 2000 compressed images arc, I_{3}, Veg.

JPEG2000 90% Seam Carved 90%

Figure 15. Comparison of seam carved and JPEG 2000 compressed images I_{1}, I_{2}.

Table 7. HDM and PSNR of seam carved Arc and Train.

Table 8. HDM and PSNR of seam carved I_{1}, I_{2}.

Based on these results we can conclude that the HDM is a better metric for representing geometrical or shape changes due to image compression techniques at compression percentages above 70%.

Cite this paper

Fernando, S. and Wijesiriwardana, R. (2016) Analysis of Wavelet Compression and Seam Carving Using the Hausdorf Distance.*Journal of Computer and Communications*, **4**, 35-45. doi: 10.4236/jcc.2016.43006.

Fernando, S. and Wijesiriwardana, R. (2016) Analysis of Wavelet Compression and Seam Carving Using the Hausdorf Distance.

References

[1] Taylor, C. and Dey, S. (2001) Adaptive Image Compression for Wireless Multimedia Communication. ICC.

[2] Lee, D.-G. and Dey, S. (2002) Adaptive and Energy Efficient Wavelet Image Compression for Mobile Multimedia Data Services. ICC.

[3] Li, Z.N. and Drew, M.S. (2005) Fundamentals of Multimedia. Pearson Education, New Jersey.

[4] Ahumada, A.J. (1993) Computational Image Quality Metrics: A Review. SID Digest of Technical Papers, 24, 305-308.

[5] Jayant, N., Johnston, J. and Safranek, R. (1993) Signal Compression Based on Models of Human Perception. Proc. IEEE, 81, 1385-1421. http://dx.doi.org/10.1109/5.241504

[6] Daly, S. (1993) The Visible Differences Predictor: An Algorithm for the Assessment of Image Fidelity. In: Watson, A.B., Ed., Digital Images and Human Vision, MIT Press, Cambridge, MA, 179-206.

[7] Eskicioglu, A.M. and Fisher, P.S. (1993) A Survey of Quality Measures for Grey Scale Image Compression. In: Proc. NASA Space Earth Science Data Compression Workshop, 49-61.

[8] Fernando, S. and Wijesiriwardana, R. (2014) Selection of Wavelet Compression or Seam Carving Technique Based on Image Type. In: Proc. of Int. Conf. on Indu and Inf. Systems.

[9] Huttenlocher, D.P., Klanderman, G.A. and Rucklidge, W.J. (1993) Comparing Images Using Hausdorf Distance. IEEE Transactions on Pattern Recognition and Machine Intelligence, 15, No. 9.

[10] Goswami, J.C., Noble, B. and Chan, A.K. (1999) Fundamentals of Wavelets. John Wiley, New York.

[11] Gonzales, R.C., et al. (2009) Digital Image Processing Using MATLAB. 2nd Edition, Pearson Education.

[12] Skodras, A., Christopoulos, C. and Ebrahimi, T. (2001) The JPEG 2000 Still Image Compression Standard. IEEE Signal Processing Magazine. http://dx.doi.org/10.1109/79.952804

[13] Avidan, S. and Shamir, A. (2007) ACM Transactions on Graphics (TOG). Proceedings of ACM SIGGRAPH.

[14] Kabir, M. (2013) Image Compression Using Lifting Based Wavelet Transform Coupled with SPIHT Algorithm. In: Proceedings of the Int. Conf. on Informatics, Electronics and Vision. http://dx.doi.org/10.1109/iciev.2013.6572638

[15] Mallet, S.G. (1989) A Theory for Multiresolution Signal Decomposition: The Wavelet Representation. IEEE Trans. Pattern Annal. Machine Intell, 11, 674-693. http://dx.doi.org/10.1109/34.192463

[16] Chandler, D.M. and Hemami, S. (2002) Additivity Models for Suprathreshold Distortion in Quantized Wavelet Coded Images. Human Vision and Electronic Imaging Conference, San Jose, CA, USA, SPIE Vol. 4662, May, 105-118.
http://dx.doi.org/10.1117/12.469507

[17] Kumari, S. and Vijay, R. (2012) Image Quality Estimation by Entropy and Redundancy Calculation for Various Wavelet Families. International Journal of Computer Information Systems and Industrial Management Applications, 4, 27-34.

[18] Moivre, A. (2010) Image Quality Metrics: PSNR vs SSIM. Proceedings of the International Conference on Pattern Recognition.