Advanced
Rate Allocation for Block-based Compressive Sensing
Rate Allocation for Block-based Compressive Sensing
Journal of Broadcast Engineering. 2015. May, 20(3): 398-407
Copyright © 2015, The Korean Society of Broadcast Engineers
  • Received : March 16, 2015
  • Accepted : May 19, 2015
  • Published : May 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Quang Hong Nguyen
Khanh Quoc Dinh
Viet Anh Nguyena
Chien Van Trinh
영현 박
병우 전
bjeon@skku.edu

Abstract
Compressive sensing (CS) has drawn much interest as a novel sampling technique that enables sparse signal to be sampled under the Nyquitst/Shannon rate. By noting that the block-based CS can still keep spatial correlation in measurement domain, this paper proposes to adapt sampling rate of each block in frame according to its characteristic defined by edge information. Specifically, those blocks containing more edges are assigned more measurements utilizing block-wise correlation in measurement domain without knowledge about full sampling frame. For natural image, the proposed adaptive rate allocation shows considerable improvement compared with fixed subrate block-based CS in both terms of objective (up to 3.29 dB gain) and subjective qualities.
Keywords
I . Introduction
Nyquist/Shannon sampling theorem is the basis for signal acquisition in digital signal processing, which tells that a band-limited signal should be sensed at a rate of being at least twice of the signal bandwidth for perfect reconstruction. However, for high dimensional signal, according to huge amount of samples, the cost of sampling and encoding thereafter might be impractical for some applications having limited sampling/encoding resources, such as surveillance camera or satellite imaging. Alternatively, a new signal sampling technique named compressive sensing (CS) overcomes this problem by sensing a sparse signal containing very few non-zero elements at a sub-Nyquist sampling rate while still guaranteeing exact reconstruction with sufficient amount of measurements.
In CS for image/video, block-based CS (BCS) scheme, where non-overlapped blocks are sensed separately, requires much less memory for storing measurement matrix; as a result, it deems to be more practical. However, conventional BCS considers all blocks equally, i.e., all blocks are sampled at the same subrate, disregarding the fact that blocks in a frame with different sparsity level (due to their different contents) may need different number of measurements for reconstruction. The subrate is the ratio of sample numbers used with and without compressed sensing scheme, so it is a number between 0 and 1. For example, a subrate of 0.5 means that the number of sampled data is reduced by half by using compressed sensing scheme. Note that, a smooth block has more compressible representation in transform domain (e.g., Discrete Cosine Transform or Discrete Wavelet Transform) than a complex block having more edge, texture or detail; so that a smooth block needs fewer measurements than a complex block to achieve the same recovery precision.
In prior researches on adaptive CS of video [1 - 2] , the adaptive subrate of block is conveyed from decoder to encoder via a feedback channel. However the feedback channel may not be always available in practical situation, especially in real time application due to its potentially high delay. In other approaches [3 - 4] for image/video, the authors proposed to assign an adaptive subrate for a block based on its edge information under availability assumption of the original image (i.e., raw data that is fully sampled) for detecting edge pixels. Here, they somehow lose the advantages of CS (CS combines the sampling and compression into one step; hence, raw data is unavailable at encoder).
In this paper, we propose a method to adapt the subrate of block for image system. Subrate of each block is assigned according to its characteristic so that complex blocks are assigned more measurement data than smooth blocks without assuming availability of original image. Note that properly designed CS system should be able to preserve signal information pretty well from spatial domain to measurement domain. Under this assumption, we examine each block for its characteristic by performing edge detection in measurement domain with neither referring to raw data nor requiring feedback channel. The way we evaluate block's characteristic in measurement domain makes adaptive CS system become more simple and practical. Eventually, for image, the subrate assigned to each block is estimated proportionally to the number of edge pixels in the given block, i.e., the more edge pixels a block contains, the higher subrate the block is assigned to. Experimental results manifest superior improvement of the proposed method compared with conventional scheme of a fixed subrate BCS.
The remainder of this paper is organized as following: Section II introduces the related works. Section III presents the proposed method of adapting subrate of BCS based on edge information. Experimental results and analyses are shown in Section IV. Finally, Section V concludes the paper.
II . Related works
- 1. Compressive Sensing
A finite-length signal x RN is called k -sparse if it has at most k non-zero coefficients for some k N . Compressive sensing (CS) [5] is an emerging framework which can reduce the sampling cost; it is proved that a k -sparse signal x can be recovered from far fewer measurements y RM (i.e., M < N ) than the Nyquist/Shannon sampling rate where the measurement vector y is a linear projection of the signal x by a measurement (or sensing) matrix Փ as:
PPT Slide
Lager Image
The ratio of M / N is called the subrate (or, measurement rate), which represents how much sub-sampling is done since M < N . Note that, the measurement matrix Փ needs to satisfy the restricted isometry property (RIP) [6] . Matrix Փ satisfies RIP of oder- k if there exits a δk ∈(0,1) holding for all k -sparse vector x such that:
PPT Slide
Lager Image
In fact, most of the natural signals are not exactly sparse, but can be sparsely represented in a proper transform domain, or compressible in some transform domains. By assumption that the signal x , through a sparse transform with its kernel ψ , can be represented as x = ψ T θ , where θ is the transform coefficient of x , and the signal θ is sparse (or at least compressible); the sparse vector θ of the signal x can be recovered from the M measurements, y = Փx = ՓψTθ by l 0 -minimization as following:
PPT Slide
Lager Image
where the l 0 -norm ∥ θ 0 is number of non-zero vector elements of θ . However, the l 0 -minimization is a non-convex problem, which means potentially very difficult to solve, especially when the number of vector elements are large. Instead, CS solves (3) by l 1 -minimization, which is a convex optimization problem, as:
PPT Slide
Lager Image
Here,
PPT Slide
Lager Image
is the l 1 -norm of θ .
It is already known that CS can successfully recover a k -sparse signal under the condition that the number of acquired measurements M should satisfy [7] :
PPT Slide
Lager Image
There are many algorithms to solve the CS reconstruction problem; for example, Matching Pursuit [8] , Orthogonal Matching Pursuit [9] , Multiple Candidate Matching Pursuit [10] , SL0 [18] , or TVAL3 [19] algorithms.
- 2. Block-based Compressive Sensing
In CS for image/video processing, the block-based CS (BCS) method has been proposed to reduce the complexity of system [11 - 13] . An input image is split into non-overlapping blocks denoted by x (i) RB 2 where i is a block index, x (i) is a column vector with B 2 elements, each of which is a pixel value inside the i -th B × B block. Then, blocks are compressively sampled into measurement domain as yi = ՓBx (i) where yi RMB is a column vector measurement and ՓB is a MB × B 2 measurement matrix; in this case, subrate of a block is calculated as a ratio of MB / B 2 . The measurement matrix of a whole frame is a block-diagonal matrix as:
PPT Slide
Lager Image
For recovery, [11] suggests a procedure that combines projected Landweber iteration with smoothing in the form of Wiener filtering. The overall process of BCS sampling and SPL reconstruction are called BCS-SPL. An improvement of BCS-SPL is also presented in [12] .
III . Rate allocation for block-based compressive sensing
It is worth noting that BCS still keeps the block correlation in spatial domain also in measurement domain [13 - 15] . S. Mun et al. empirically confirmed the high correlation among measurements of BCS using Lena image, which showed average correlation even larger than 0.95 [13] .
Additionally, characteristic of natural image is changed from region to region. Some regions can be smooth, while others can be complex with many objects. As a result, the sparsity (or compressibility) of image is also changed with different regions. Fig. 1 shows us more clearly about this problem. From original Lena image, we extract two blocks with two different characteristics; the upper one locates in a smooth region and the lower one locates in a complex region with many edge information (see the edge image on the left side). And then, DCT transformation is applied for two those blocks. Obviously, the sorted in descending order of absolute DCT coefficients of upper one decrease much quickly than the lower one. That means the upper one (smooth block) is more compressible than the lower one (complex block). As a result, smooth block needs less measurements than complex block to achieve equally reconstructed performance.
PPT Slide
Lager Image
부드럽고 복잡한block에 대한 절대 DCT 계수의 내림차순 정렬 Fig. 1. Sorted descendance of absolute DCT coefficients of smooth and complex block.
Motivated by the correlation among BCS measurements, we detect edges in image using the measurement data only. That is, if the block measurement data of blocks at an initial subrate s 0 (i.e., same original subrate for all blocks) Y = ( y 1 , y 2 ,... yi ,...) is block-averaged as:
PPT Slide
Lager Image
where yi is the measurement vector of a i -th block , and
PPT Slide
Lager Image
is a mean value of measurement vector yi . Then
PPT Slide
Lager Image
is reshaped into a form of 2D image
PPT Slide
Lager Image
we can see a roughly estimated original image in a low resolution (i.e.,
PPT Slide
Lager Image
still has good spatial correlation among blocks in measurement domain). Subsequently, the reshaped image
PPT Slide
Lager Image
is scaled up to original image size by a bicubic interpolation [16]
PPT Slide
Lager Image
where up (*) is the bicubic interpolation operator. Interestingly, the interpolated image still clearly contains edges and boundaries of the original image, and therefore, a typical edge detection algorithm is expected to identify those edge pixels well.
Fig. 2 shows the whole process of edge detection in measurement domain. Clearly, the detected edge image shows edges quite well. Thus, it is possible to characterize blocks based on the edge information, for example, a smooth block will contain very few edge pixels while a complex block will contain many edge pixels. By this way, it is expected that the more complex (less compressible) the block is, the more edge pixels the block contains. Therefore, in this paper, we estimate the sparsity of i -th block proportionally with number of edge pixels in block as:
PPT Slide
Lager Image
PPT Slide
Lager Image
측정 영역에서의 경계선 검출 (측정율 0.4에서 512x512 해상도 및 8x8 블록 크기를 갖는 Lena 영상) Fig. 2. Edge detection in measurement domain (512x512 Lena image with block size 8x8, subrate 0.4)
The bigger ei means that block is less compressible. On the other hand, the number of required measurements for CS reconstruction depends much on the sparsity of block as shown in (5); hence, a sparser block needs fewer measurements [1] . Thus we should look for a way to sample each block with its proper subrate adaptively. In this paper, the rate allocation for each block is based on the edge image - blocks containing more edges (i.e., more complex) are sampled with a higher subrate than otherwise.
The whole proposed compressed sensing system is shown in Fig. 3 ; sparsity estimation is equivalent to edge detection process which determines the edge information in each block. The subrate of each block is assigned proportionally to spasity of block as following:
PPT Slide
Lager Image
PPT Slide
Lager Image
제안하는 적응적 BCS 방법에 대한 블록 다이어그램 Fig. 3. Diagram of proposed adaptive BCS for image
where si is an adaptively selected subrate for i -th block; sm is the minimum subrate of block. sm is firstly setup sm = r × s 0 , ( r is predefined parameter to determine how small the minimum subrate assigned for each block is, 0 < r < 1). The meaning of sm is to guarantee that the subrate assigned for each block is not so small compared with s 0 which can make unstably or inaccurately in reconstruction and we may not get the improvement. Parameter α is a control parameter (its value is calculated below)
The subrate of each block is adjusted so that the final subrate of whole image is not changed compared with s 0 such that:
PPT Slide
Lager Image
where L is the number of blocks in image . From (8) and (9):
PPT Slide
Lager Image
PPT Slide
Lager Image
The value of α in (11) is then substituted into (8) to calculate subrate of each block. However, if the assigned subrate for a block exceed 1 (which is nonsense in CS system since number of measurements is not higher than signal length), sm is adjusted by increasing r (note that r is still smaller than 1), and then subrate assigned for each block is re-calculated.
As a result, a smooth block may be assigned a smaller subrate than s 0 while a complex block is assigned a higher subrate than s 0 . Finally, since smooth blocks are assigned subrate lower than s 0 , we only take required number of measurement B 2 × si from yi . Otherwise, those complex blocks are assigned with higher subrate than s 0 , we have to sample more B 2 × ( si - s 0 ) measurements.
IV. Experimental results
In this section, performance of the proposed method is presented using four 512x512 gray natural images, namely, Lena, Barbara, Boat, and Cameraman. At encoder, the input image is split into small non-overlapped blocks and then mapped into measurement domain by an i.i.d. random Gaussian. In our experimental results, we tested three subrates 0.2, 0.4, 0.6 with two block sizes of 8x8 and 16x16. Performance of the proposed method is evacuated using three reconstructed algorithms: Iterative Support Detection (ISD) [17] , Smoothed L0 Norm (SL0) [18] , and total variation (TVAL3) [19] . For edge detection, Canny edge detection algorithm is used considering its good performance compared with other edge detection algorithms [20] . Additionally, value of 2/3 is assigned for the initiation of parameter r . More detail result of the experiments is shown in Table 1 , Table 2 , Table 3 and Fig. 4 .
블록크기 8x8에서의 여러 CS복원 방법에 대한 실험 결과 [PSNR in dB]Table 1. Experimental results with various CS recovery methods for block size of 8x8 [PSNR in dB]
PPT Slide
Lager Image
블록크기 8x8에서의 여러 CS복원 방법에 대한 실험 결과 [PSNR in dB] Table 1. Experimental results with various CS recovery methods for block size of 8x8 [PSNR in dB]
블록크기 16x16 에서의 여러 CS 복원 방법에 대한 실험 결과[PSNR in dB]Table 2. Experimental results with various CS recovery methods for block size of 16x16 [PSNR in dB]
PPT Slide
Lager Image
블록크기 16x16 에서의 여러 CS 복원 방법에 대한 실험 결과[PSNR in dB] Table 2. Experimental results with various CS recovery methods for block size of 16x16 [PSNR in dB]
여러 CS 복원 방법에 대한 실험 결과 [SSIM index]Table 3. Experimental results with various CS recovery methods [SSIM index]
PPT Slide
Lager Image
여러 CS 복원 방법에 대한 실험 결과 [SSIM index] Table 3. Experimental results with various CS recovery methods [SSIM index]
PPT Slide
Lager Image
블록크기 8x8 및 측정율 0.4에서 TVAL3 기반 복원 알고리즘을 통해 산출된 영상 간 화질 비교 Fig. 4. Visual quality comparison using TVAL3 CS recovery algorithm with block size 8x8. subrate 0.2
Table 1 shows performance of various CS recovery method with a block size of 8x8. Clearly, the proposed method gains remarkably compared with the case of fixed subrate BCS. Those images with much detail, like Barbara, show PSNR improvement of 0.64 dB to 1.42 dB. With smooth images, like Cameraman, the improvement is up to 3.29 dB (subrate 0.2 with ISD algorithm).
Additionally, Table 2 shows the performance of CS recovery with block size of 16x16. Obliviously, performance of the proposed method is better than the fixed subrate BCS; however, improvement of the proposed method with block size of 16x16 is lower than that with block size of 8x8. It is because the block size of 8x8 is better in keeping the block correlation and the spatial information is also preserved well in measurement domain than the block size of 16x16. The proposed adaptive subrate assignment for each block becomes more accurate leading to higher performance in CS recovery.
Moreover, Table 3 shows visual comparison between the fixed subrate BCS and the proposed method by SSIM index with block size 8x8; it is obvious that, in all cases, the proposed method presents better performance. For more clearly, Fig. 4 illustrates an example of cropped Lena image at subrate 0.2 and TVAL3 algorithm. Fig. 4 (c) shows better in visual quality (the fine detail becomes much clearer) compared with Fig. 4 (b), especially in some complex regions which contains much edge information (subrate for those blocks in this region is high) leading to good reconstructed block both in subjective and objective qualities.
V. Conclusion
In this paper, an adaptive rate allocation for BCS of images is proposed. The characteristic of block is defined based on edge detection and then subrate of each block is assigned commensurably to how many edge pixels it contains in the edge image - blocks containing more edges are assigned more measurement data than others. The experimental results showed remarkable improvement of the proposed method compared with the fixed subrate BCS.
BIO
Quang Hong Nguyen
- 2013년 8월 : Hanoi University of Science and Technology (Vietnam)
- 2013년 9월 ~ 현재 : 성균관대학교 전자전기컴퓨터공학과 석사과정
- ORCID : http://orcid.org/0000-0002-3159-9285
- 주관심분야 : Image/video coding and Compressive Sensing
Khanh Quoc Dinh
- 2010년 8월:Hanoi University of Science and Technology (Vietnam)
- 2012년 8월:성균관대학교 전자전기컴퓨터공학과 석사
- 2013년 9월 ~ 현재:성균관대학교 IT융합학과 박사과정
- ORCID : http://orcid.org/0000-0002-1007-4068
- 주관심분야 : Video Compression and Compressive Sensing.
Viet Anh Nguyen
- 2011년 8월:Hanoi University of Science and Technology (Vietnam)
- 2013년 8월:성균관대학교 전자전기컴퓨터공학과 석사
- 2013년 9월 ~ 2014년 12월:성균관대학교 전자전기컴퓨터공학과 박사과정
- ORCID : http://orcid.org/0000-0002-7141-6463
- 주관심분야 : Compressive Sensing, Video Coding.
Chien Van Trinh
- 2012년 8월:Hanoi University of Science and Technology (Vietnam)
- 2012년 9월 ~ 2014년 8월:성균관대학교 전자전기컴퓨터공학과 석사
- ORCID : http://orcid.org/0000-0002-4674-9055
- 주관심분야 : Video Compression and Compressive Sensing.
박 영 현
- 2011년 2월 : 성균관대학교 전자전기공학부 학사
- 2011년 3월 ~ 현재 : 성균관대학교 전자전기컴퓨터공학과 석박통합과정
- ORCID : http://orcid.org/0000-0002-4733-5049
- 주관심분야 : Video Compression and Compressive Sensing.
전 병 우
- 1985년 : 서울대학교 전자공학과 학사
- 1987년 : 서울대학교 전자공학과 석사
- 1992년 : Purdue Univ. School of Elec. 공학박사
- 1993년 ~ 1997년 : 삼성전자 신호처리연구소 수석연구원
- 1997년 ~ 현재 : 성균관대학교 정보통신대학 교수
- ORCID : http://orcid.org/0000-0002-5650-2881
- 주관심분야 : 멀티미디어 영상압축, 영상인식, 신호처리
References
Chen H. W. , Kang L. W. , Lu C. S. "Dynamic measurement rate allocation for distributed compressive video sensing," in Proc. SPIE Visual Communication and Image Processing July 2010 1 - 10
Nebot J. P. , Ma Y. , Huang T. “Distributed Video Coding Using Compressive Sampling,” in Proc. Picture Coding Symposium May 2009 1 - 4
Azghani M. , Aghagolzadeh A. , Aghagolzadeh M. “Compressed Video Sensing Using Adaptive Sampling Rate,” in Proceeding of International Symposium on Telecommunications Dec. 2010 710 - 714
Hai-bo Z , Xiu-chang Z. 2013 “Sampling Adaptive Block Compressed Sensing Reconstruction Algorithm for Images Based on Edge Detection,” The Journal of China Universities of Post sand Telecommunications 20 97 - 103
Baraniuk R. 2007 “Compressed sensing,” IEEE Signal Processing Magazine 24 118 - 121    DOI : 10.1109/MSP.2007.4286571
Candes E. , Tao T. 2005 “Decoding by linear programming,” IEEE Trans. Information Theory 51 4203 - 4215    DOI : 10.1109/TIT.2005.858979
Davenport M. A. , PhD. Thesis 2010 “Random Observation on Random Observation: Sparse Signal Acquisition and Processing,” Rice University PhD. Thesis
Marcia S. , Zhang Z. 1993 "Matching pursuits with time-frequency dictionaries," IEEE Trans. Signal Processing 41 3397 - 4415    DOI : 10.1109/78.258082
Tropp J. , Gilbert A. C. 2007 "Signal recovery from random measurement via orthogonal marching pursuit," IEEE Trans. Inform. Theory 53 4655 - 4666    DOI : 10.1109/TIT.2007.909108
Kwon S. , Shim B. 2012 "Multiple Candidate Matching Pursuit," Journal of Broadcasting Engineering 17 954 - 963    DOI : 10.5909/JBE.2012.17.6.954
Mun S. , Fowler J. E. "Block Compressive Sensing of Images Using Directional Transforms," in Proceedings of the International Conference of Image Processing Nov. 2009 3021 - 3024
Park Y. , Shim H. J. , Jeon B. 2014 "Convergence Complexity Reduction for Block-based Compressive Sensing Reconstruction," Journal of Broadcasting Engineering 19 240 - 249    DOI : 10.5909/JBE.2014.19.2.240
Mun S. , Fowler J. E. “DPCM for quantized block-based compressive sensing of image,” Proceedings of the 20th European Signal Processing Conference Aug. 2012 1424 - 1328
Dinh K. Q. , Shim H. J. , Jeon B. “Measurement Coding for Compressive Imaging Using a Structural Measurement Matrix,” in Proceeding of IEEE Int. Conf. on Image Proc. Sept. 2013 10 - 13
Nguyen Q. H. , Dinh K. Q. , Nguyen V. A. , Trinh C. V. 2014 "A Skip-mode Coding for Distributed Compressive Video Sensing," Journal of Broadcasting Engineering 19 257 - 267    DOI : 10.5909/JBE.2014.19.2.257
Keys R. G. 1981 “Cubic Convolution Interpolation for Digital Image Processing,” IEEE Trans. on Acoustics, Speech, and Signal Processing 29 1153 - 1160    DOI : 10.1109/TASSP.1981.1163711
Wang Y. , Yin W. 2010 “Sparse Signal Reconstruction via Iterative Support Detection,” SIAM Journal on Imaging Sciences 3 462 - 491    DOI : 10.1137/090772447
Mohimani G. H. , Babaie-Zadeh M. , Jutten C. 2009 “A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed L0 Norm,” IEEE Trans. on Signal Processing 57 289 - 301    DOI : 10.1109/TSP.2008.2007606
Li C. , PhD. Thesis 2011 "Compressive Sensing for 3D Data Processing, Tasks: Application, Models and Algorithms," Rice University PhD. Thesis
Maini R. , Aggarwal H. 2009 “Study and Comparison of Various Image Edge Detection Technique,” International Journal of Image Processing 3 1 - 12    DOI : 10.1049/iet-ipr:20080080