The Rate-Distortion Optimized Compressive Sensing for Image Coding

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.

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).

Authors and Affiliations

1. School of Electronics and Information Engineering, Shanghai University of Electric Power, 35-702, No.2878 Gaoqing road, Pudong, Shanghai, 200090, China

   Wei Jiang & Junjie Yang

Corresponding author

Correspondence to Wei Jiang.

Appendix

The biased Lagrange cost J _B (λ) is defined as follows

Then following results can be concluded:

1. 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 λ ₃ = θλ ₁ + (1 − θ)λ ₂, 0 ≤ θ ≤ 1.

2. 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 (λ).

Reprints and permissions