Abstract
The success of compressive sensing (CS) implies that an image can be compressed directly into acquisition with the measurement number over the whole image less than pixel number of the image. In this paper, we extend the existing CS by including the prior knowledge of Kcluster values available for the pixels or wavelet coefficients of an image. In order to model such prior knowledge, we propose in this paper Kclustervalued CS approach for imaging, by incorporating the Kmeans algorithm in CoSaMP recovery algorithm. One significant advantage of the proposed approach, rather than the conventional CS, is the capability of reducing measurement numbers required for the accurate image reconstruction. Finally, the performance of conventional CS and Kclustervalued CS is evaluated using some natural images and background subtraction images.
Keywords:
compressive sensing; Kmeans algorithm; modelbased method1 Introduction
Image compression is currently an active research area, as it offers the promise of making the storage or transmission of images more efficient. The aim of image compression [1] is to reduce the data size of image and then make the image stored or transmitted in an efficient form. In image compression, we may transform the image into an appropriate basis and only store or transmit the important expansion coefficients [2]. Since such coefficients are normally sparse (only few coefficients are nonzero) or compressible (decaying rapidly according to power law), the compression (e.g., image compression in JEPG2000 [3]) can be achieved via storing and transmitting the nonzero coefficients.
For example, assume that we have acquired an image signal x ∈ ℝ^{N }with N pixels. Through DCT or wavelet transform, image x may be represented in terms of sets of coefficients via a basis expansion: x = Ψα, where Ψ is an N × N basis matrix. Therefore, x may be represented by sparse coefficients
A Compressive sensing
Most recently compressive sensing (CS), as a sampling method in image compression, has been proposed [57], in order to compress the sparse/compressible signals x directly into acquisition during the sensing procedure. In CS, given M × N random measurement matrix Φ, we are able to achieve Mdimensional measurement values y via inner product:
where each entry y_{s }of y represents the value measured by measurement vector ϕ_{s }that is sth row of Φ. It has been proved [6] that image can be robustly recovered from M = O(S log(N/S)) measurements. In practice, M = 4S measurements are required for precise recovery as reported in [4], and therefore, compression can be reached by sensing and storing M measurements y. It has been proved that the signal can be recovered by seeking the sparest x with the solution of convex program [8]:
Equation 2 can be solved by a linear program within polynomial time [9]. For reducing the computational time, some other approaches have been proposed in the spirit of either greedy algorithms or combinatorial algorithms.
These include orthogonal matching pursuit (OMP) [10], StOMP [11], subspace pursuit [12] and CoSaMP [13].
It is attractive that CS is also applicable to images with sparse or compressible coefficients in the transform domain since y can be written as y = ΦΨx, in which ΦΨ can be seen as M × N measurement matrix. In the sequel, without generality loss we shall focus on the images, sparse or compressible in the pixel domain. However, in our experiments of Section 4, we shall also consider the images, compressible in wavelet domain.
B Basic idea
Beyond CS, most recently, various extensions of CS have been proposed. CS, at heart, utilizes the prior knowledge of the sparsity of signal to compress the signal. Actually, some signals, such as digital images, have some prior knowledge other than sparsity. For example, we know that the nonzero coefficients of images usually cluster together, and a modelbased CS was thus proposed in [1416] to integrate the prior knowledge of signal structure in CS for reducing the amount of measurements required for the recovery of images. However, to our best knowledge, all the stateoftheart modelbased CS approaches only concentrate on the prior knowledge of the locations of nonzero value pixels in digital images and assume that all the N pixel values of a digital image ∈ ℝ^{N}. For example, [17] proposed (S, C)modelbased CS for reconstructing the Ssparse signal with the prior knowledge of block sparsity model in which there are at most C clusters with respect to the locations of nonzero coefficients of the signal. This approach is applicable to some practical problems such as MIMO channel equalization. However, in some other applications, the values of the sparse signal rather than nonzerovalued locations cluster together. Therefore, in this paper, we consider sparse signals with the prior knowledge of Kclustervalued coefficients, either in the canonical (pixel) domain or in the wavelet domain.
As a matter of fact, it has been shown [18] that for the most digital images, the intensities of each pixel are usually the subspace^{a }of [0, 255]. The motivation of this paper is thereby to extend the modelbased CS theory to include such prior knowledge. Then, we propose a reconstruction approach based on Kclustervalued intensities for CS (called Kclustervalued CS) to incorporate Kmeans algorithm in CS for recovering the images using only K clusters of nonzero intensity values, {μ_{1}, μ_{2},..., μ_{K}} ⊆ [1, 255]. Once the measurement number M is less than required 4S for image compression with CS, there may exist several unreasonable solutions to the estimation of target image. However, during the reconstruction procedure, the proposed Kclustervalued CS avoids the possibility of intensity values being assigned beyond K clusters: {μ_{1}, μ_{2},..., μ_{K}}, and it thus may be capable of discarding those unreasonable solutions. So, Kclustervalued CS is possible to reduce the number of measurements M required for robust image recovery. Note that in a gray image even we set cluster number K to be 255 at limit, Kclustervalued CS can still avoid the recovered intensity values of each pixel to be greater than 255 or less than 0 in conventional CS. Since our proposed Kclustervalued CS is an extension of modelbased CS, we shall briefly review the modelbased CS in the following section.
For instance, when we apply CS in compressing the binary image, the measurement number M may be reduced with the prior knowledge that only one cluster of nonzero intensity values is available for reconstructing image. As illustrated in Figure 1, CS recovery algorithm, even with insufficient measurements, is able to refuse the solution not supported by the prior knowledge of only binary values being available for image intensities. Consequently, Kclustervalued CS is possible to reduce the measurement number for precise reconstruction of the target image. Since our proposed Kclustervalued CS is an extension of modelbased CS, we shall briefly review the modelbased CS in the following section.
Figure 1. (a) The original 96 × 128 binary image, (b) the reconstructed image using CS with the prior knowledge that only one cluster of nonzero intensity values exist, and (c) the reconstructed image without any prior knowledge. (d) The reconstruction results of 1clusterintensitybased CS, after aligning 96 × 128 pixels of the image to be a vector with 12,288 entries, and (e) the reconstructing results of conventional CS, after aligning 96×128 pixels of the image to be a vector with 12,288 entries. The sparsity S in this image is 1,592, and measurement number M here is 3S, which is smaller than 4S [4] required for the accurate recovery of image in conventional CS.
2 Overview of modelbased CS
Modelbased CS [14] incorporates some other prior knowledge rather than the sparsity or compressibility of signal in CS. It is intuitive that the restriction of such an additive prior knowledge may decrease the redundancy of measurements in CS, and the reduction in measurement number M of CS may therefore be possible.
In order to introduce the modelbased CS, let us first consider the modelbased restricted isometry property (RIP). Here, we define structured S sparsity model
• An M × N matrix Φ has the
It has been proved [19] that if
where c is a positive constant, then Φ has
Next, we define
Then, the prior knowledge can be encoded in algorithm
It has also been proved in [14] that error bound of modelbased CoSaMP is
for
In a word, on the basis of prior knowledge encoded in advance, the modelbased CS is capable of reducing the measurement numbers without increasing any error bound.
3 Kclustervalued CS
In this section, we provide the detail of the proposed approach on the basis of modelbased
CS. It is intuitive that a digital image is comprised of the pixels with several clusters
(at most 256) of the intensities, rather than all possible values used for estimating
the image/signal in conventional CS or modelbased CS [14]. So, structured S sparsity model
The Kmeans algorithm [20] ensures that the clusters of data with the same or similar values can be identified
in the same data set. So, Kmeans algorithm can be applied to the algorithm of Equation 7 using at most K = 255 clusters of nonzero intensities to reconstruct the target image at each iteration
of recovery algorithm in CS. However, in practice, since most digital images have
less than 255 clusters of nonzero intensities (the statistical analysis will be presented
in the last part of this section), K is normally set to be less than 255 for image reconstruction. Even though K is the rough estimation of real cluster numbers, Kmeans algorithm still works in modelbased CS due to the fact that the goal of Kmeans algorithm is to minimize
As assumed above,
Given each nonzero
For the purpose of minimizing J, we may apply an iterative procedure involving two successive optimizations. The
first optimization deals with minimizing J with respect to
1. Maximization: Since Equation 8 is a linear function of r_{nk}, this optimization can be easily solved by setting r_{nk }to be 1 once k makes
2. Expectation: In this stage, r_{nk }has been fixed such that Equation 8 can be minimized with respect to
So, Equation 8 can be solved by
The above two stages are then repeated until reaching at convergence. However, it
may converge to a local minimization rather than global minimization. Therefore, a
good initialization procedure can reduce the oscillations and improve the performance
of the proposed approach. Fortunately, we have the prior knowledge that for an image,
After these iterative two stages, the values of each
Table 1. Summary of the Kclustervalued CoSaMP algorithm
At each iteration, not only the measurement residual but also EM is applied for estimating the target signal. Since there are only a few clusters of intensity values for the target image, it is able to reduce the error caused by assigning unreasonable estimated values (e.g., more than 255 clusters) to each pixel at each iteration. Although the estimation error of the image may influence the clustering accuracy at each iteration, the minimization of Equation 8 also makes such influence minimal and the proposed approach converges after a few iterations. The computational time reported in section 4 also reveals that the robust of clustering.
Then, we have to answer how to confirm cluster number K for Kclustervalued CS. Here, we first consider the images sparse in pixel domain, and we statistically tested on 1,000 images from Caltech 101 and Berkeley Segmentation Database to obtain the optimal cluster numbers of pixel intensities for Kmeans in each image, which make the PSNR greater than 20 dB (since the acceptable value for the quality of lossy image compression is above 20 dB [21]). The statistical results are shown in Figure 2. As seen from this figure, more than 85% cluster numbers of intensities range below 10, and thus 10 may be chosen as an optimal cluster number for images sparse in pixel domain.
Figure 2. The number of images along with their optimal cluster numbers of intensities for Kmean algorithm. Note that the cluster number is chosen to be optimal one once it makes the accuracy of Kmean algorithm greater than 20 dB.
However, the images are hardly sparse in pixel domain. Therefore, we need to consider clustering wavelet coefficients of images. Toward the optimal cluster number of wavelet coefficients, we also statistically tested on the same 1,000 images as above with the following procedure: (1) obtain the wavelet coefficients of each image, and set wavelet coefficients less than 20 to be 0; (2) reconstruct the image with nonzero wavelet coefficients by nonK means algorithm and compute the PSNR of reconstructed image; (3) reconstruct the image by K means algorithm with increasing number of clusters of nonzero wavelet coefficients, and once the cluster number makes the difference in the PSNRs between images reconstructed by nonK means and Kmeans algorithms less than 2 dB, we output this cluster number as optimal one. The statistical results are then demonstrated in Figure 3. From this figure, we may confirm that clustering is a reliable prior in the wavelet transform for images, and 40 is an optimal cluster number for wavelet coefficients.
Figure 3. The number of images along with their optimal cluster numbers of wavelet coefficients for Kmean algorithm.
4 Experimental results
In this section, experiments were performed for validating the proposed Kclustervalued CS. For comparison, we also applied the conventional CS to exactly
the same images. In all the experiments, we utilized random Gaussian matrix as the
measurement matrix Φ on the images. For conventional CS and Kclustervalued CS, the maximum iteration numbers of CoSaMP were both set to be 30.
Besides, the iterations can also be halted once
A One experiment in detail
First of all, a lunar image (Figure 4a) was tested on conventional CS. Then, the reconstructed image is shown in Figure
4b using the recovery methods of CoSaMP, with M = 3S = 5217 random Gaussian measurements, where S = 1739 indicates the nonzero intensity values of the lunar image. Note that the measurement
number M is approximately
Figure 4. (a) The original lunar gray image (resolution: 128 × 128) with S = 1,739 nonzero values. The random Gaussian measurement number of CS over this image is M = 3S = 5,217 measurements, which is
From the viewpoint of computational time, as can been seen from Figure 4, Kclustervalued CS runs faster than conventional CS when cluster number K is small (e.g., K = 2, 5 and 10). It may be due to the fast convergence of Kclustervalued CoSaMP caused by more accurate recovery result at each iteration.
Next, we shall compare the recovery error of conventional and Kclustervalued CSs in terms of peak signaltonoise ratio (PSNR). PSNR refers to the ratio between the maximum possible power of a signal and the power of corrupting noise that affects the fidelity of its representation. Since many signals have very wide dynamic ranges, PSNR is normally expressed in terms of the logarithmic decibel scale. In our experiments, PSNR, as a measure of quality of lossy image compression, is defined by:
where N is the number of pixels at each image and 255 is the dynamic range of intensities
of the image. x and
Then, we run Monte Carlo (50 times) simulation on computing the PSNR of image reconstruction via conventional and Kclustervalued CSs. The results can be seen in Figure 5. Figure 5a shows the impact of measurement number M on the performance of Kclustervalued and conventional CSs for the target image displayed in Figure 4. Since the acceptable value for the quality of lossy image compression is above 20 dB [21], Figure 5a reveals that the proposed Kclustervalued CS approach reaches at tolerable recovery result when M = 3S, while the conventional CS fails^{c}. Also, it can be further seen that even when the measurement number is sufficient (M = 4S), the performance of Kclustervalued CS is superior to conventional one. Figure 5b further shows the performance of Kclustervalued CS given different cluster number K. We can observe that Kclustervalued CS works well with different cluster numbers and that the more cluster number we choose, the better Kclustervalued CS will perform in most cases.
Figure 5. (a) The reconstruction error of Figure 4 measured by PSNR. In this figure, the PSNR (vertical axis) is shown along with various measurement number and the values at the horizontal axis indicate how many times of sparsity level S. (b) The results of PSNR output by Kclustervalued CS with various cluster numbers K. The measurement number M here is set to be 3S.
B More experiments in general
In this subsection, we evaluated our proposed approach on three different images sets: (1) the image set chosen from Caltech 101 database contains five images, sparse in pixel domain; (2) the natural image set contains four images, sparse or compressible in wavelet domain; (3) background subtracted color image set.
For the first image set, since we have concluded in the above section that 10 can be seen as an optimal cluster number of intensities for the images sparse in pixel domain, we set K of Kclustervalued CS to be 10. In addition, all the measurement numbers used for compressing these images were chosen to be 3S, which is less than the least measurement number 4S required for successful reconstruction in conventional CS [4]. Then, the reconstruction results are presented in Figure 6, and these results show the better performance of Kclustervalued CS for compressing images that are sparse in standard domain.
Figure 6. (a) The original gray images. The measurement numbers of both conventional and Kclustervalued CS over these images are M = 3S, where S is the sparse level. (b) The reconstructed images using conventional CoSaMP recovery method. (c) The images reconstructed by Kclustervalued CoSaMP. Note that cluster number K was chosen to be 10 for all these images.
With the second image set, we have evaluated the promise of the proposed CS approach on compressing the images in wavelet domain. Here, as aforementioned in Section 3, we chose the cluster number of wavelet coefficients for Kclustervalued CS to be 40 as concluded in the above section. In order to obtain the more accurate results, the measurement numbers here were all set to be 3.5S, where S is the number of largest S wavelet coefficients used for image reconstruction. Then, the input and output images are shown in Figure 7, and the PSNRs of the reconstructed images in this figure are further demonstrated in Table 2. Again, Kclustervalued CS offers the better performance in compressing images, sparse in wavelet domain.
Figure 7. (a) The original gray images measured by CS with wavelet sparsity basis. The measurement numbers of both conventional and Kclustervalued CS over these images are M = 3.5S, where S is the number of compressible wavelet coefficients greater than threshold 20. (b) The reconstructed images using the conventional CoSaMP recovery method. (c) The images reconstructed by Kclustervalued (wavelet coefficients) CoSaMP. Note that cluster number K was chosen to be 40 for all these images.
Table 2. The PSNRs of reconstructed images of Figure 7
The Kclustersvalued CS is also applicable to background subtracted images. Here, we tested the proposed Kclustersvalued CS and conventional CS on the third image set with two background subtraction images from [16]. According to [16], these images are obtained by selecting at random two frames of video sequence and subtracting them in a pixelwise fashion. For each image, we set the cluster number K to be 10 as well. Then, we performed Kclustersvalued CoSaMP and conventional CoSaMP under M = 3S Gaussian random measurements. The recovery results are shown in Figure 8. We may see from this figure that Kclustervalued CS outperforms conventional one and that Kclustervalued CS is also capable of recovering background subtracted images with insufficient measurements (e.g., 3S measurements).
Figure 8. (a) Two original background subtraction images. The recovery results are shown in (b) for conventional CS and (c) for Kclustervalued CS, using M = 3S random Gaussian measurements for each image. Note that cluster number K was 10 for Kclustervalued CS.
5 Conclusions
In this paper, in order to compress the image, we have aimed to propose an advanced modelbased CS, named Kclustervalued CS, which utilizes Kmeans algorithm as the model for CS. In contrast to conventional CS, the proposed Kclustervalued CS incorporates the prior knowledge that only K clusters values of intensities are available for all the pixels of an image. In this paper, we also investigated cluster number K as prior knowledge. Such prior knowledge goes beyond the simple sparsity/compressibility of CS and therefore has the advantage in using fewer measurements than conventional CS for accurate image reconstruction. This way, Kclustervalued CS is applicable to other Kclustervalued signals (e.g., binary digital signals) besides the images. Also, it is applicable to other modelbased CS by considering all the prior knowledge together. Moreover, the experiments were performed and presented to validate the proposed approach.
Endnotes
^{a}This is the usual case since an image is normally comprised of a few categories of
objects with limited color intensities as exploited in computer vision community.
^{b}The K clusters can also be applied in color image by extending each gray value
Competing interests
The authors declare that they have no competing interests.
Acknowledgements
This work was partially supported by China National Basic Research Program (973) under Grant number 2007CB310600 and partially supported by NSFC 30971689.
References

M Petrou, C Petrou, Image Processing: The Fundamentals, 2nd edn. (Wiley, Amsterdam, 2010)

S Mallat, A Wavelet Tour of Signal Processing (Academic Press, New York, 1999)

D Taubman, M Marcellin, JPEG 2000: Image Compression Fundamentals, Standards and Practice, 1st edn. (Kluwer Academic, Dordrecht, 2001)

E Candès, M Wakin, An introduction to compressive sampling. IEEE Signal Process Mag 25(2), 21–30 (2008)

E Candès, J Romberg, T Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans Inf Theory 52(02), 489–509 (2006)

E Candès, T Tao, Nearoptimal signal recovery from random projections: Universal encoding strategies? IEEE Trans Inf Theory 52(12), 5406–5425 (2006)

D Donoho, Compressed sensing. IEEE Trans Inf Theory 52(4), 1289–1306 (2006)

E Candès, J Romberg, T Tao, Stable signal recovery from incomplete and inaccurate measurements. Commun Pure Appl Math 59(8), 1207–1223 (2006). Publisher Full Text

S Boyd, L Vandenberghe, Convex Optimization (Cambridge University Press, Cambridge, 2004)

J Tropp, A Gilbert, Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans Inf Theory 53(12), 267–288 (2007)

DL Donoho, Y Tsaig, I Drori, J luc Starck, Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit. Tech Rep, 1–39 (2006)

W Dai, O Milenkovic, Subspace pursuit for compressive sensing signal reconstruction. IEEE Trans Inf Theory 55(5), 267–288 (2009)

D Needell, J Tropp, Cosamp: iterative signal recovery from incomplete and inaccurate samples. Appl Comput Harmon Anal 26(3), 301–321 (2009). Publisher Full Text

R Baraniuk, V Cevher, M Duarte, C Hegde, Modelbased compressive sensing. IEEE Trans Inf Theory 56(4), 1982–2001 (2010)

Y Eldar, P Kuppinger, H Bolcskei, Compressed sensing of blocksparse signals: uncertainty relations and efficient recovery. in IEEE Trans Signal Process (2009)

V Cevher, M Duarte, C Hegde, R Baraniuk, Sparse signal recovery using markov random fields. Proceedings of NIPS (2008)

V Cevher, P Indyk, H Chinmay, R Baraniuk, Recovery of clustered sparse signals from compressive measurements. Proceedings of Sampta09 (2009)

CM Bishop, Pattern Recognition and Machine Learning, 1st edn. (Springer, New York, 2006)

T Blumensath, M Davies, Sampling theorems for signals from the union of finitedimensional linear subspaces. IEEE Trans Inf Theory 55(4), 1872–1882 (2008)

SP Lloyd, Least squares quantization in pcm. IEEE Trans Inf Theory 28(2), 129–136 (1982). Publisher Full Text

N Thomos, N Boulgouris, M Strintzis, Optimized transmission of jpeg2000 streams over wireless channels. IEEE Trans Image Process 15(1), 54–67 (2006). PubMed Abstract