An Image representation using Compressive Sensing and Arithmetic Coding

An Image representation using Compressive Sensing and Arithmetic Coding

• 1.
  ©2016, IJCERT AllRights Reserved DOI:10.22362/ijcert/2016/v3/i11/48908 Page | 573 Volume 3, Issue 11, November-2016, pp. 573-579 ISSN (O): 2349-7084 International Journal of Computer Engineering In Research Trends An Image representation using Compressive Sensing and Arithmetic Coding *Dr. Renuka Devi S M ECE Dept, GNITS, Hyderbad-500008 Abstract— The demand for graphics and multimedia communication over intenet is growing day by day. Generally the cod- ing efficiency achieved by CS measurements is below the widely used wavelet coding schemes (e.g., JPEG 2000). In the existing wavelet-based CS schemes, DWT is mainly applied for sparse representation and the correlation of DWT coefficients has not been fully exploited yet. To improve the coding efficiency, the statistics of DWT coefficients has been investigated. A novel CS-based image representation scheme has been proposed by considering the intra- and inter-similarity among DWT coefficients. Multi-scale DWT is first applied. The low- and high-frequency subbands of Multi-scale DWT are coded separately due to the fact that scaling coefficients capture most of the image energy. At the decoder side, two different recovery algo- rithms have been presented to exploit the correlation of scaling and wavelet coefficients well. In essence, the proposed CS- based coding method can be viewed as a hybrid compressed sensing schemes which gives better coding efficiency com- pared to other CS based coding methods. Index Terms-.Compressive sensing, Discrete wavelet tansform, Tree Structured wavelet CS, Basis Pursuit ——————————  —————————— 1. INTRODUCTION With the increasing demand for digital multi- media, there has been more and more interest in visual communication over Internet and wireless networks. Generally speaking, the amount of visual data is huge, while the bandwidth of transmission channels is limited. Thus, compression techniques are employed before data transmission. Discrete cosine transform (DCT) and Dis- crete Wavelet Transform (DWT) are two widely used transforms for image compression. The classic standard JPEG employs DCT to compact image energy, and thus a fraction of significant coefficients can approximate the original image. The JPEG 2000 is the most recent image compression standard, which is based on DWT and outperforms JPEG in general. Although the existing image coding schemes can provide excellent compression performance, they are high sensitivity to channel noise. One bit error or loss may cause severe error propagation and thus makes some of the bit stream that follows become meaningless. Therefore, error control or data protection is necessary in many situations. Multimedia content is typically with a large amount of data, and such a huge data volume is often grouped into a number of packets. If MDC approach has only two or three descriptions, each description would be still loaded into a lot of packets. In this scenario, packet loss in any single description can make the re- ceived packets from the description being useless, and thus the decoded image quality would be severely af- fected. The system proposes an alternative coding paradigm with a number of descriptions [4,5 6,10], based upon Compressive Sensing (CS).Two- dimensional Discrete Wavelet Transform (DWT) is ap- plied for sparse representation. Unlike the typical wave- let coders (e.g., JPEG 2000), DWT coefficients here are not directly encoded, but re-sampled towards equal importance of information instead. To achieve better coding efficiency separate encoding schemes are used for higher and lower bands. At the decoder side, by fully exploiting the intra-scale and inter-scale correla- tion of multiscale DWT, two different CS recovery algo- rithms are developed for the low-frequency subband and high-frequency subbands, respectively. The recov- ery quality only depends on the number of received CS measurements. The lower frequency subband coefficients con- tain most of the image energy. The coefficients values are most probably significant in low frequency sub- band. Based on the above analysis, the lowest subband coefficients are not sparse. Application of compressive sampling both for low and high frequency subbands is always not suitable. The existing image representation schemes Available online at: www.ijcert.org
• 2.
  Dr. Renuka DeviS M ," An Image representation using Compressive Sensing and Arithmetic Coding”, International Journal of Computer Engineering In Research Trends, 3(11):573-579,November-2016.DOI:10.22362/ijcert/2016/v3/i11/48908. ©2016, IJCERT All Rights Reserved DOI:10.22362/ijcert/2016/v3/i11/48908 Page | 574 based on compressive sensing does not fully utilize the statistical properties of multiscale DWT. Also the energy concentration in LL band makes it suitable for entropy coding rather than compressive sensing. A novel image representation scheme is proposed such that different encoding techniques are used for low and high frequen- cy subbands. The paper is organized as follows. Section 2 gives the introduction of CS theory.Section 3 deals with the proposed methodology of Image represenatation by hybrid CS i.e, CS with Arithmetic coding.Section 4 shows the experimental results by using two methods of recovery i.e., Basic persuit and TSW CS. 2. COMPRESSIVE SENSING As explained earlier, if f is a N×N signal sparse on some basis Ψ. If x is a K sparse representation of on the basis Ψ. Then compressive sensing states that by making M linear measurements f can be fully represent- ed as[1,2] ∑ The recovery of f can be done by solving a con- vex optimization problem as shown ‖ ̌‖ ‖ ̌‖ In CS scheme, the measurements are not values of x , but represents projections on to x. As mentioned earlier the necessary condition for sparse recovery is RIP (Restricted Isometry Property), where the sparsifying base Ψ and measurement matrix ф should be incoherent to each other. In [1,6, 7], the authors demonstrated that CS measurements have the democracy property if is gener- ated according to a Gaussian distribution. If democracy property is satisfied, each CS sample contributes a simi- lar amount of information of the original signal. Math- ematically, we say that is M-democratic if all the M×N sub-matrices obey UUP. Democratic property can be used for CS based image representation. By multiplying the unequally im- portant DWT coefficients with an i.i.d. random Gaussian matrix, the resultant CS measurements are with roughly equal importance and thus can be used for error control or data protection. 3. STATISTICAL PROPERTIES OF DWT 3.1 Error bounds for lower and higher bands Donoho [1, 2, 3, and 14] suggested a hybrid CS to measure wavelet coefficients in higher bands while using linear reconstruction for lower band. Natural images are complex representation of real world. It is hard to find out a basis, which results in exact sparse representation of the natural image. But the natural image in general is compressible. If an image x such that f(x) =Ψx, where Ψis an orthonormal basis. x is compressed by taking K largest coefficients into account represented as , then the difference |‖ ‖ || || Where R and p are constants and depends on fn(x), that is the nth largest coefficients in f ( x) and coef- ficients of f varies as 1< n < N , | f n(x) |< R. n-1/p. Based on the analysis on error bounds [8,9], the conclusion is CS is more suited for signals with fast re- covery and are sparser. So to leverage maximum sig- nal recovery and minimum error in presence of noise the image is divided into dense and sparse components. Multiscale DWT is used for this purpose. The lowest subband of DWT representation of the signals has most significant data. Fig 1: Decay rate of Low Frequency subband coefficients Fig 2: Decay rate of Wavelet coefficients Figures 1 & 2 shows the decay rate of scaling and wavelet coefficients respectively. Based on the above graphs, the decay rate of wavelet coefficients is
• 3.
  Dr. Renuka DeviS M ," An Image representation using Compressive Sensing and Arithmetic Coding”, International Journal of Computer Engineering In Research Trends, 3(11):573-579,November-2016.DOI:10.22362/ijcert/2016/v3/i11/48908. ©2016, IJCERT All Rights Reserved DOI:10.22362/ijcert/2016/v3/i11/48908 Page | 575 far higher than scaling coefficients. Hence we can con- clude that CS is more suited for wavelet coefficients and less suited for scaling coefficients. 3.2 Intra band statistics of LL band [14] Fig 3 represents the histogram of LL band coef- ficients for pirate image (size 128×128) after 3 levels 'Haar' DWT is applied. The coefficients of LL band comprises of significant data. Also some symbols of low band data occurs with high probability. To reduce this redundancy and increase coding efficiency, entrophy coding is considered to be better coding method for LL band. Fig 3 Histogram of Low frequency subband co- efficients So arithmetic coding is used as entropy coding technique for LL band. As the values of coefficients are highly correlated, taking differential data will result in significant efficiency of coding. Inter scale statistics of DWT In the proposed methodology, statistical properties of multiscale DWT, Wavelet coefficients results in parent children relationships. The wavelet coefficients at the coarsest scale serve as ‚root nodes‛ for the quad trees, with the finest scale of coefficients constituting the ‚leaf nodes‛. For most natural images the negligible wavelet coefficients tend to be clustered together; specifically, if a wavelet coefficient at a particular scale is negligible, then its children are also generally (but not always) neg- ligible. This leads to the concept of ‚zero trees‛ *19+ in which a tree or sub tree of wavelet coefficients are all collectively negligible. The structure in the wavelet coefficients is im- posed within a Bayesian prior, and the analysis yields a full posterior density function on the wavelet coeffi- cients. Consequently, in addition to estimating the un- derlying wavelet transform coefficients of the given image ‚error bars‛ are also provided, which provide a measure of confidence in the inversion. Such error bars are useful for at least two reasons: (i) When inference is performed subsequently, one may be able to place that inference within the context of the confidence in the CS inversion; (ii) typically one may not know a priori how many transform coefficients are important in a signal of inter- est, and therefore one will generally not know in ad- vance the proper number of CS measurements N – one may use the error bars on the inversion to infer when enough CS measurements have been performed to achieve a desired accuracy. Based on the above analysis below conclusions are made. a) Compressive sampling is used for sparse com- ponents where decay rate of coefficients is rapid. b) Compressive sampling is less suited for low fre- quency subband of DWT. c) The low frequency band coefficients are highly correlated and are significant with maximum probabil- ity. d) There is a parent children relationship that exists between scaling and wavelet coefficients, such that if a parent is insignificant then the children are most likely insignificant. 3.3 CS based lossy image compression Based on the statistical properties projected the proposed method used two different encoding algo- rithms for Low and High frequency subbands. Figure 4 represents the encoding scheme used for image repre- sentation scheme. Fig 4 : Encoder of Proposed System[14]. 3.4 Measurements Sampling of High frequency data In the proposed CS based MDC image coding instead of directly coding the DWT coefficients, they are re-sampled towards equal importance of information. In the proposed method, i.i.d. Gaussian is selected as CS measurement matrices. In this process high frequen- cy sub bands are re-sampled, such that the overall resampled information is of equal important for all
• 4.
  Dr. Renuka DeviS M ," An Image representation using Compressive Sensing and Arithmetic Coding”, International Journal of Computer Engineering In Research Trends, 3(11):573-579,November-2016.DOI:10.22362/ijcert/2016/v3/i11/48908. ©2016, IJCERT All Rights Reserved DOI:10.22362/ijcert/2016/v3/i11/48908 Page | 576 subbands. Once the wavelet coefficients are measured by random matrix, they are quantized using 16 bit for- mat. Encoding of Low frequency Information As low frequency subband contain most of the image energy, compressive sampling of the scaling co- efficients will not result in efficient scheme. The low frequency subband has highly correlated data, entropy coding results in best representation of data. The scaling coefficients are quantized in the first step. The quantized scaling coefficients are taken and Differential data is calculated from the quantized coefficients. As scaling coefficients are highly correlated data, calculating differential data will result in reducing maximum redundancy. The differential data is then given as input to a arithmetic coder. For a 16*16 LL band of 256 symbols (each of 16 bits), the resultant arithmetic coded output is just with 1552 bits for 'cameraman' image. As described, the scaling coefficients have quantization, differential data and arithmetic coding steps, before final bit stream is created. 3.5 Recovery Fig 5: Decoder of Proposed System[14] Fig 5. Shows the block diagram shows different stages of recovery of compressed image representation. Recovery of High band Coefficients The high band coefficients are recovered based on a Bayesian framework. The intra scale correlation of low and high bands is utilized as a prior information for a Bayesian learning. Based on the parent child relation- ship of inter band coefficients, a belief is propagated such that, if LL band parent of a particular set of wave- let coefficients is significant, then most likely the chil- dren coefficients are also significant. To solve the l1 optimization problem, along with available data, the inter scale dependencies are also utilized. Marcov Chain Monte Carlo (MCMC) method is used for recovery of Bayesian learning. Recovery of Low band Coefficients Scaling coefficients recovery is exact reverse process of encoding. In the 1st step, an arithmetic de- coder is used to retrieve differential coefficients. In the 2nd step, from the differential data, original data is re- produced. In the last step, inverse quantization is done. As the quantization is a lossy process, even after the inverse quantization some loss of data is present. After the quantization process, estimated scaling coefficients are available. Inverse Discrete Wavelet Transform (IDWT) The Wavelet coefficients and scaling coeffi- cients recovered in previous steps are combined and used as inputs to recover original image f by applying Inverse Discrete Wavelet Transform. 4. RESULTS AND DISCUSSION Since that the LL band coefficients are encoded using arithmetic coding where as the higher band coefficients are encoded using Compressive sens- ing. So the method is named as Arth-CS. The compari- sons methods are referred as TSW CS for Tree Struc- tured Wavelet CS and BP - Basis Pursuit for CS optimi- zation problem. For optimization problem primal dual al- gorithm is implemented for linear programming. SPGL 1.8 is used for implementation of Basis pursuit. Cameraman image of 512×512 size is taken as i/p to the experiments. For easier computation image is resized for 128×128 size. On the resized image 3 meth- ods are applied. Three level ‘haar’ wavelet is applied for decomposing the image. For TSW-CS and BP the meas- urements are taken based on bit budget and the meas- urements are quantized into signed 16 bit integer val- ues. Fig 6: Rate -Distortion Characteristics Figure 6. shows Rate -Distortion characteristics of the three different methods. Clearly Arth-CS method out performs other methods. TSW CS method the con-
• 5.
  Dr. Renuka DeviS M ," An Image representation using Compressive Sensing and Arithmetic Coding”, International Journal of Computer Engineering In Research Trends, 3(11):573-579,November-2016.DOI:10.22362/ijcert/2016/v3/i11/48908. ©2016, IJCERT All Rights Reserved DOI:10.22362/ijcert/2016/v3/i11/48908 Page | 577 ditions of implementation are as per the base paper, in which the low frequency band coefficients are also re- covered based on MCMC method. The subjective eval- uation for these images reveals that Arth- CS is more efficient than the other two methods. Fig 7 represents number of measurements against relative error. Fig 7: Measurements Vs Relative error Clearly Relative error is highest in BP and low- est in Arth-CS. Also the error decreases at the same rate as TSW CS. Fig 8. plots the computational time required to compress and recover back the image. In this, Arth- CS and TSW CS are compared as the methods are compari- tive. Fig 8: Measurements VS Computational time Clearly Arth- CS outperforms TSW CS in com- putational time. To get subjective evaluation on these 3 methods, 3 different techniques are applied for a range of images and with different measurements. Scaling coefficients are coded using DPCM fol- lowed by arithmetic coder. Based on the bit budget of scaling coefficients, proportionately extra measure- ments are taken for TSW CS and BP methods. For ex- ample, for pirate image of 128×128 size, 3 stages DWT is applied. 11000 measurements are taken for wavelet co- efficients. To represent 256 scaling coefficients 1763 bits are used in arithmetic coding. Proportionately a total of 11100 measurements are taken in TSW CS and BP methods. Above results are for Living room image. The original image is 512×512. It is resized to 128×128 and 3 level' haar ' wavelet is applied. 3 methods are compared against 0.83 bpp bit rate.The results can be compared more prominently in tabular format of table 6.1 Table 6.1: PSNR values for cameraman image No. Of measurements bpp PSNR (dB) Arth- CS TSW- CS BP Arth- CS TSW- CS BP 1 6000 6097 6097 0.744 29.76 29.26 25.85 2 7000 7097 7097 0.866 31.41 30.56 27.85 3 8000 8097 8097 0.988 32.71 32.5 29.54 4 9000 9097 9097 1.11 33.94 33.77 32.27 5 10000 10097 10097 1.22 35.39 34.88 34.13 6 11000 11097 11097 1.35 36.92 36.65 36.15 As shown in the table 6.2, 97 extra measurements are taken in TSW-CS and BP, since the LL band 256 coeffi- cients are coded by 1552 bits. This is equivalent to 97 measurements of 16 bit length. Table 6.2 represents bpp against relative reconstruction error for the three meth- ods for cameraman image. Table 6.2: Relative reconstruction error for different rates for cameraman Image S.No bpp Relative reconstruction error Arth-CS TSW-CS BP 1 0.744 0.0623 0.0661 0.0979 2 0.866 0.0516 0.056 0.0777 3 0.988 0.0447 0.049 0.064 4 1.11 0.0386 0.0393 0.047 5 1.22 0.0326 0.0346 0.0377 6 1.35 0.0273 0.0282 0.0298 The relative reconstruction error decreases as the bpp increases. In all the three methods Arth-CS has the least reconstruction error when compared to original image. Table 6.3: Computational time for different rates for cameraman image S.No bpp Computational time (Sec) Arth-CS TSW-CS 1 0.744 505 535
• 6.
  Dr. Renuka DeviS M ," An Image representation using Compressive Sensing and Arithmetic Coding”, International Journal of Computer Engineering In Research Trends, 3(11):573-579,November-2016.DOI:10.22362/ijcert/2016/v3/i11/48908. ©2016, IJCERT All Rights Reserved DOI:10.22362/ijcert/2016/v3/i11/48908 Page | 578 2 0.866 524 564 3 0.988 535 567 4 1.11 597 622 5 1.22 650 678 6 1.35 703 736 Computational time is compared only between Arth-CS and TSW-CS as they have comparable performance. Basis pursuit method takes relatively large computa- tional time for sparse recovery. As shown previously for subjective evaluation, for different images coded at different rates, Arth-CS has consistently performed well, against other two methods. Table 6.4: Bit rate-Distortion values for different images S. No. Image Name bpp PSNR (dB) Arth- CS TSW- CS BP 1 Lena 1.33 33.3209 33.19 32.54 2 Pirate 1.35 30.23 29.74 30.13 3 Woman Blonde 0.985 28.8 28.45 26.85 4 Peppers 1.11 30.3396 30.06 28.32 5 House 1.23 37.21 37.003 36.26 6 Living room 0.83 27.08 26.57 25.01 7 cameraman 1.35 36.92 36.65 36.15 Below table 6.5 shows relative error in 3 methods: Table 6.5 : Bit rate- Relative error values for different images S. No. Image Name Bpp Relative error Arth- CS TSW- CS BP 1 Lena 1.33 0.047 0.0423 0.0456 2 Pirate 1.35 0.0653 0.0687 0.066 3 Woman Blonde 0.985 0.0659 0.0686 0.0812 4 Peppers 1.11 0.0607 0.0626 0.0765 5 House 1.23 0.0238 0.0244 0.0266 6 Living room 0.83 0.088 0.0939 0.1123 7 cameraman 1.35 0.0273 0.0282 0.0299 Clearly Arth-CS method has a better recover quality as well as less computational time, for different images. 5. CONCLUSION There are a number of CS based MDC schemes used in literature for image compression and representation. CS based methods are cost effective and best suited for certain applications where available resources at remote area are scarce. It is generally believed that the coding effi- ciency achieved by CS measurements taking is below the widely used wavelet coding schemes (e.g., JPEG 2000). Based on the decay rates and statistical properties of multiscale DWT, DWT coefficients are categorized as sparse and non sparse components. The non sparse components of multiscale DWT are differently encoded by taking differential data and applying entropy cod- ing. CS measurements are directly taken for sparse components. This approach not only increased overall coding efficiency, but also improved the quality of re- covered image. For recovery of high band coefficients, parent child relationship existing between multiscale DWT is utilized as a Bayesian prior for fast recovery of wavelet coefficients. Experimental results show that the proposed CS based hybrid schemes has better R-D per- formance compared to relevant existing methods. REFERENCES [1] Donoho D.L., ‚Compressed sensing,‛ IEEE Transac- tions on Information Theory, vol. 52, pp. 1289–1306, 2006. [2] Cand`es E. J. and Wakin M. B. , ‚An introduction to compressive sampling,‛ IEEE Signal Processing Maga- zine, vol. 25, pp. 21–30, 2008. [3] Tropp, Joel A., and Stephen J. Wright. "Computational methods for sparse solution of linear inverse problems." Proceedings of the IEEE 98.6 (2010): 948-958. [4] Candès E., Romberg J. and Tao T., ‚Robust uncertainty principles: Exact signal reconstruction from highly in- complete frequency information,‛ IEEE Trans. Inform. Theory, vol. 52,no. 2, pp. 489–509, Feb. 2006. [5] J. A. Tropp and A. C. Gilbert, ‚Signal recovery from random measurements via orthogonal matching pur- suit,‛ IEEE Transactions on Information Theory, vol. 53, pp. 4655–4666, 2007. [6] D. L. Donoho, Y. Tsaig, I. Drori, and J.-L. Starck, ‚Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit,‛ March 2006, preprint. [7] B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani, ‚Least angle regression,‛ Annals of Statistics (with dis- cussion), vol. 32,pp. 407–499, 2004. [8] [Online]. Available: http://www.cs.ubc.ca/~mpf/spgl1/ [9] Deng C.W., Lin W. S., Lee B. S. and Lau C. T., ‚Robust image compression based upon compressive sensing,‛ in Proc. IEEE Int. Conf. Multimedia and Expo. (IC- ME’10), Jul. 2010, pp. 462–467. [10] Ji S. , Xue Y. , and Carin L., ‚Bayesian compressive sensing,‛ IEEE Transactions on Signal Processing, vol.
• 7.
  Dr. Renuka DeviS M ," An Image representation using Compressive Sensing and Arithmetic Coding”, International Journal of Computer Engineering In Research Trends, 3(11):573-579,November-2016.DOI:10.22362/ijcert/2016/v3/i11/48908. ©2016, IJCERT All Rights Reserved DOI:10.22362/ijcert/2016/v3/i11/48908 Page | 579 56, 2008, pp. 2346–2356. [11] Said A. and Pearlman W. A., ‚A new, fast, and efficient image codec based on set partitioning in hierarchical trees,‛ IEEE Transactions on Circuits and Systems for Video Technology, vol. 6, 1996, pp. 243–250. [12] Pavithra V, Renuka Devi SMand Ganapathy Reddy Ch , "A survey of robust image coding techniques", IJCA (0975-8887),Volume No 71, No 5,May 2013,pp. 41-51 [13] Pavithra V, Renuka Devi SM ‘An image representation scheme by hybrid compressive sensing’ IEEE Asia Pacif- ic Conference on Postgraduate Research in Microelectronics and Electronics (PrimeAsia), 19-21 December 2013