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. 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. A finite-length signal x ∈ R^N 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 ∈ R^M (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: 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: 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 ₀ -minimization as following: where the l ₀ -norm ∥ θ ∥ ₀ is number of non-zero vector elements of θ . However, the l ₀ -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 ₁ -minimization, which is a convex optimization problem, as: Here, is the l ₁ -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] : 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. 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 ⁽ⁱ⁾ ∈ R^{B 2} where i is a block index, x ⁽ⁱ⁾ is a column vector with B ² elements, each of which is a pixel value inside the i -th B × B block. Then, blocks are compressively sampled into measurement domain as y_i = Փ_Bx ⁽ⁱ⁾ where y_i ∈ R^M_B is a column vector measurement and Փ_B is a M_B × B ² measurement matrix; in this case, subrate of a block is calculated as a ratio of M_B / B ² . The measurement matrix of a whole frame is a block-diagonal matrix as: 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] . 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. 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 ₀ (i.e., same original subrate for all blocks) Y = ( y ₁ , y ₂ ,... y_i ,...) is block-averaged as: where y_i is the measurement vector of a i -th block , and is a mean value of measurement vector y_i . Then is reshaped into a form of 2D image we can see a roughly estimated original image in a low resolution (i.e., still has good spatial correlation among blocks in measurement domain). Subsequently, the reshaped image is scaled up to original image size by a bicubic interpolation [16] 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: The bigger e_i 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: where s_i is an adaptively selected subrate for i -th block; s_m is the minimum subrate of block. s_m is firstly setup s_m = r × s ₀ , ( r is predefined parameter to determine how small the minimum subrate assigned for each block is, 0 < r < 1). The meaning of s_m is to guarantee that the subrate assigned for each block is not so small compared with s ₀ 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 ₀ such that: where L is the number of blocks in image . From (8) and (9): 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), s_m 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 ₀ while a complex block is assigned a higher subrate than s ₀ . Finally, since smooth blocks are assigned subrate lower than s ₀ , we only take required number of measurement B ² × s_i from y_i . Otherwise, those complex blocks are assigned with higher subrate than s ₀ , we have to sample more B ² × ( s_i - s ₀ ) measurements. 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 . 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. 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. 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 - 주관심분야 : 멀티미디어 영상압축, 영상인식, 신호처리