Abstract
Compressive Sensing (CS) is an emerging technology which can encode a signal into a small number of incoherent linear measurements and reconstruct the entire signal from relatively few measurements. Different from former coding scheme which distortion mainly comes from quantizer, distortion and bit rate are related to quantization and compressive sampling in the compressive sensing based image coding schemes. Moreover, the total number of bits is often constrained in the practical application. Therefore under the given bit rate how to balance the number of measurements and quantization step size to minimization the distortion is a great challenge. In this paper, a fast Lagrange multiplier solving method is proposed for the compressive sensing based image coding scheme. Then using the solved Lagrange multiplier, the optimal number of measurements and quantization step size are determined based on the rate-distortion criteria. Experimental results show that the proposed algorithm improves objective and subjective performances substantially.
![](https://cdn.statically.io/img/media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11265-015-1087-0/MediaObjects/11265_2015_1087_Fig1_HTML.gif)
![](https://cdn.statically.io/img/media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11265-015-1087-0/MediaObjects/11265_2015_1087_Fig2_HTML.gif)
![](https://cdn.statically.io/img/media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11265-015-1087-0/MediaObjects/11265_2015_1087_Fig3_HTML.gif)
![](https://cdn.statically.io/img/media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11265-015-1087-0/MediaObjects/11265_2015_1087_Fig4_HTML.gif)
![](https://cdn.statically.io/img/media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11265-015-1087-0/MediaObjects/11265_2015_1087_Fig5_HTML.gif)
![](https://cdn.statically.io/img/media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11265-015-1087-0/MediaObjects/11265_2015_1087_Fig6_HTML.gif)
![](https://cdn.statically.io/img/media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11265-015-1087-0/MediaObjects/11265_2015_1087_Fig7_HTML.gif)
![](https://cdn.statically.io/img/media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11265-015-1087-0/MediaObjects/11265_2015_1087_Fig8_HTML.gif)
![](https://cdn.statically.io/img/media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11265-015-1087-0/MediaObjects/11265_2015_1087_Fig9_HTML.gif)
![](https://cdn.statically.io/img/media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11265-015-1087-0/MediaObjects/11265_2015_1087_Fig10_HTML.gif)
![](https://cdn.statically.io/img/media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs11265-015-1087-0/MediaObjects/11265_2015_1087_Fig11_HTML.gif)
Similar content being viewed by others
References
Donoho, D. (2006). Compressive sensing. IEEE Trans. on Inform Theory, 52(4), 1289–1306.
Cand’es, E., Romberg, J., & Tao, T. (2006). Robust uncertainty principles, exact signal reconstruction from highly incomplete frequency information. IEEE Trans. on Inform Theory, 52(2), 489–509.
Wu, X. L. & Zhang, X. J. (2009). Model-guided adaptive recovery of compressive sensing, in Proc. Data Compression Conf. (DCC), pp. 123–132.
Goyal, V. K., Fletcher, A. K., & Rangan, S. (2008). Compressive sensing and lossy compression. IEEE Signal Processing Magazine, 25(2), 48–52.
Wu, S-H, Peng, W-H, Chiang, T (2010). Bit-plane compressive sensing with bayesian decoding for lossy compression, 28th Picture Coding Symposium, pp. 606–609.
Wen, J., Chen, Z., Han, Y., Villasenor, J. D., & Yang, S. (2010). A compressive sensing image compression algorithm using quantized DCT and noiselet information, In Proc. Acoustics, Speech and Signal Process.Conf. (ICASSP), pp. 1294–1296.
Deng, C.W., Lin, W. S., Lee, B. S. & Lau, C. T. (2010). Robust image compression based upon compressive sensing, in Proc. IEEE Int. Conf. Multimed. and Expo. (ICME), pp. 462–467.
Deng, C., Lin, W., & Lee, B.-S. (2012). Robust image coding based upon compressive sensing. IEEE Trans. on Multimed., 14(2), 278–290.
Chen, H.-W., Kang, L.-W., & Lu, C.-S. (2010). Dynamic measurement rate allocation for distributed compressive video sensing. Proceedings of SPIE, 7744, 774401–774410.
Haixiao, L., Bin, S., Fang, T., Hao, Q., & Joint Sampling Rate and Bit-Depth Optimization in Compressive Video Sampling. (2014). IEEE Trans. on Multimed, 16(6), 1549–1562.
Lam, E., & Goodman, J. (2000). A mathematical analysis of the DCT coefficient distributions for images. IEEE Trans. on Image Process., 9(10), 1661–1666.
Huang, J. & Mumford, D. (1999). Statistics of natural images and models, in Comput. Vision and Pattern Recognition, IEEE Comput. Society Conf., pp. 1543–547.
Candes, E., & Wakin, M. (2008). An introduction to compressive sampling. IEEE signal process. magazine, 25(2), 21–30.
Baranuik, R. (2007). Compressive sensing. IEEE signal process. Magazine, 24(4), 118–124.
Cand’es, E. J., & Romberg, J. (2007). Sparsity and incoherence in compressive sampling. Inverse Problems, 23(3), 969–985.
Do, T. T., Gan, L., Nguyen, N. & Tran, T. D. (2008). Sparsity adaptive matching pursuit algorithm for practical compressed sensing, Asilomar Conf. on Signals, Syst., and Comput. pp. 581–587.
Laska, J. N., & Baraniuk, R. G. (2012). Regime change: Bit-depth versus measurement-rate in compressive sensing. IEEE Transactions on Signal Processing, 60(7), 3496–3505.
Candes, E. & Romberg, J. (2006). Encoding the lp ball from limited measurements, Proceedings of the Data Compression Conference (DCC), pp. 1–10.
Stutz, T., & Uhl, A. (2012). Efficient and rate-distortion optimal wavelet packet basis selection in JPEG2000. IEEE Trans. on Multimed, 14(2), 264–277.
Jiang, W. (2009). A novel algorithm of solving the optimal slope on rate-distortion curve for the given rate budget. Journal of Donghua University (English Edition), 26(3), 259–263.
Fan, Y., Wang, J., & Sun, J. (2012). Multiple description image coding based on delta-sigma quantization with rate-distortion optimization. IEEE Trans. on image process, 21(9), 4304–4309.
Chen, Z., & Dapeng, W. (2012). Rate-distortion optimized cross-layer rate control in wireless video communication. IEEE Trans. on CSVT, 22(3), 352–365.
Jiaying, L., Yongjin, C., Zongming, G., & Kuo, C.-C. J. (2010). Bit allocation for spatial scalability coding of H.264/SVC with dependent rate-distortion analysis. IEEE Trans. on CSVT, 22(7), 967–981.
Schulz, A., Velho, L., da Silva, E. A. B. (2009). On the empirical rate-distortion performance of compressive sensing, in Proc. Image Process. Conf., pp. 3049–3042.
Boufounos, P., & Baraniuk, R. (2008). Quantization of sparse representations. IEEE Trans. On Inform. Theory, 52(2), 489–509.
Jacques, L., Hammond, D. K. & Fadili, M. J. (2009). Dequantized compressive sensing with nongaussian constraints, IEEE Int.Conf. on Image Process. (ICIP), pp. 1465–1468.
Wang, L., Wu, X., & Shi, G. (2012). Binned progressive quantization for compressive sensing, IEEE Trans. Compression actions On Image Process., pp. 2980–2990.
Press, W. K., Flannery, B. P., Teukolsky, S. A., et al. (1988). Numerical recipes in C: The art of scientific computing. Cambridge: Cambridge Univ. Press.
Ramchandran, K., & Vetterli, M. (1993). Best wavelet packet bases in a rate-distortion sense. IEEE Trans. on Image Processing, 2(2), 160–175.
Pronzato, L., Wynn, H. P., & Zhigljavsky, A. A. (1999). Finite sample behaviour of an ergodically fast line-search algorithm. Comput. Optim. and Appl, 14(3), 1475–86.
Wei, J., Jia, W., & Jun, S. (2005). Rate-distortion based quantisation level adjustment for H.264. Electronics Letters, 41(16), 29–30.
Deng, C.W., Lin, W. S., Lee, B. S. & Lau, C. T. (2010). Robust image compression based upon compressive sensing, in Proc. IEEE Int. Conf. Multimed. and Expo. (ICME),, pp. 462–467.
Venkatraman D., & Makur, A. (2009). A compressive sensing approach to object-based surveillance video coding, in Proc. IEEE Int. Conf. Acoustics, Speech. Signal Process. (ICASSP), pp. 3513–3516.
Acknowledgments
This work is supported by National Natural Science Foundation of China (NSFC, 61401269, 61371125, 61202369), Natural Science Foundation of Shanghai (14ZR1417400), Shanghai Technology Innovation Project (10110502200, 11510500900), Innovation Program of Shanghai Municipal Education Commission (12ZZ176,13YZ105), Project of Science and Technology Commission of Shanghai Municipality (10PJ1404500), Leading Academic Discipline Project of Shanghai Municipal Education Commission (J51303).
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
The biased Lagrange cost J B (λ) is defined as follows
Then following results can be concluded:
-
1.
J B (λ) is the convex function of λ.
$$ \begin{array}{l}{J}_B\left({\lambda}_3\right)={\lambda}_3{R}_c-{J}^{*}\left(\lambda \right)\\ {}\begin{array}{cc}\hfill \hfill & \hfill \hfill \end{array}={\lambda}_3{R}_c-\underset{s\in S}{ \min}\left\{D(s)+\left[\theta {\lambda}_1+\left(1-\theta \right){\lambda}_2\right]R(s)\right\}\\ {}\begin{array}{cc}\hfill \begin{array}{cc}\hfill \hfill & \hfill \hfill \end{array}\hfill & \hfill \begin{array}{l}\le \theta \underset{s\in S}{ \min}\left\{\left[{\lambda}_1{R}_c-D(s)-{\lambda}_1R(s)\right]+\left(1-\theta \right)\underset{s\in S}{ \min}\left[{\lambda}_2{R}_c-D(s)-{\lambda}_2R(s)\right]\right\}\\ {}=\theta {J}_B{\left(\lambda \right)}_1+\left(1-\theta \right){J}_B\left({\lambda}_2\right)\end{array}\hfill \end{array}\end{array} $$(26)where λ 3 = θλ 1 + (1 − θ)λ 2, 0 ≤ θ ≤ 1.
-
2.
λ * and s*(λ *) that minimize J B (λ) are the optimal slope and optimal operating point for the given budget constraint.
Suppose λ ' is the slope of the convex hull face which “straddles” the budget constraint line on the R-D plane. For λ < λ ', invoking the lower rate operating point s '
$$ \begin{array}{l}\left.\left.{J}_B\left(\lambda \right)-{J}_B\left(\lambda \hbox{'}\right)=\underset{s\in S}{ \min}\left\{\left[\lambda {R}_c-\left(D(s)+\lambda R(s)\right)\right]-\left[\lambda \hbox{'}{R}_c-\left(D(s)+\lambda \hbox{'}R\left(s\hbox{'}\right)\right)\right]\right\}\right]\right\}\\ {}\begin{array}{cc}\hfill \begin{array}{cc}\hfill \begin{array}{ccc}\hfill \begin{array}{cc}\hfill \hfill & \hfill \hfill \end{array}\hfill & \hfill \hfill & \hfill \hfill \end{array}\hfill & \hfill \begin{array}{l}\ge \left[\lambda {R}_c-\left(D\left(s\hbox{'}\right)+\lambda R\left(s\hbox{'}\right)\right)\right]-\left[\lambda \hbox{'}{R}_c-\left(D\left(s\hbox{'}\right)+\lambda \hbox{'}R\left(s\hbox{'}\right)\right)\right]\\ {}\ge \left(\lambda -\lambda \hbox{'}\right)\left({R}_c-R\left(s\hbox{'}\right)\right)\ge 0\end{array}\hfill \end{array}\hfill & \hfill \hfill \end{array}\end{array} $$(27)Similarly, for λ > λ ', invoking the higher rate operating point s ' ', it can be got
$$ {J}_B\left(\lambda \right)-{J}_B\left(\lambda \hbox{'}\right)\ge \left(\lambda -\lambda \hbox{'}\right)\left({R}_c-R\left(s\hbox{'}\hbox{'}\right)\right)\ge 0 $$(28)Therefore, for all positive values of λ, J B (λ ') < J B (λ) is satisfied. It is proved that the optimal slope for the bit budget R c is the point minimizing the biased cost J B (λ).
Rights and permissions
About this article
Cite this article
Jiang, W., Yang, J. The Rate-Distortion Optimized Compressive Sensing for Image Coding. J Sign Process Syst 86, 85–97 (2017). https://doi.org/10.1007/s11265-015-1087-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11265-015-1087-0