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 blockbased 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 blockwise 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 blockbased CS in both terms of objective (up to 3.29 dB gain) and subjective qualities.
I . Introduction
Nyquist/Shannon sampling theorem is the basis for signal acquisition in digital signal processing, which tells that a bandlimited 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 nonzero elements at a subNyquist sampling rate while still guaranteeing exact reconstruction with sufficient amount of measurements.
In CS for image/video, blockbased CS (BCS) scheme, where nonoverlapped 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 finitelength signal
x
∈
R^{N}
is called
k
sparse if it has at most
k
nonzero 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 subsampling 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
_{0}
minimization as following:
where the
l
_{0}
norm ∥
θ
∥
_{0}
is number of nonzero vector elements of
θ
. However, the
l
_{0}
minimization is a nonconvex 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:
Here,
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]
:
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. Blockbased Compressive Sensing
In CS for image/video processing, the blockbased CS (BCS) method has been proposed to reduce the complexity of system
[11

13]
. An input image is split into nonoverlapping blocks denoted by
x
^{(i)}
∈
R^{B}
^{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
y_{i}
=
Փ_{B}x
^{(i)}
where
y_{i}
∈
R^{MB}
is a column vector measurement and
Փ_{B}
is a
M_{B}
×
B
^{2}
measurement matrix; in this case, subrate of a block is calculated as a ratio of
M_{B}
/
B
^{2}
. The measurement matrix of a whole frame is a blockdiagonal 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 BCSSPL. An improvement of BCSSPL is also presented in
[12]
.
III . Rate allocation for blockbased 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.
부드럽고 복잡한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}
,...
y_{i}
,...) is blockaveraged 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:
측정 영역에서의 경계선 검출 (측정율 0.4에서 512x512 해상도 및 8x8 블록 크기를 갖는 Lena 영상) Fig. 2. Edge detection in measurement domain (512x512 Lena image with block size 8x8, subrate 0.4)
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:
제안하는 적응적 BCS 방법에 대한 블록 다이어그램 Fig. 3. Diagram of proposed adaptive BCS for image
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
_{0}
, (
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
_{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:
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 recalculated.
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}
×
s_{i}
from
y_{i}
. Otherwise, those complex blocks are assigned with higher subrate than
s
_{0}
, we have to sample more
B
^{2}
× (
s_{i}

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 nonoverlapped 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]
블록크기 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]
블록크기 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]
여러 CS 복원 방법에 대한 실험 결과 [SSIM index] Table 3. Experimental results with various CS recovery methods [SSIM index]
블록크기 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/0000000231599285
 주관심분야 : 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/0000000210074068
 주관심분야 : 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/0000000271416463
 주관심분야 : Compressive Sensing, Video Coding.
Chien Van Trinh
 2012년 8월：Hanoi University of Science and Technology (Vietnam)
 2012년 9월 ~ 2014년 8월：성균관대학교 전자전기컴퓨터공학과 석사
 ORCID : http://orcid.org/0000000246749055
 주관심분야 : Video Compression and Compressive Sensing.
박 영 현
 2011년 2월 : 성균관대학교 전자전기공학부 학사
 2011년 3월 ~ 현재 : 성균관대학교 전자전기컴퓨터공학과 석박통합과정
 ORCID : http://orcid.org/0000000247335049
 주관심분야 : Video Compression and Compressive Sensing.
전 병 우
 1985년 : 서울대학교 전자공학과 학사
 1987년 : 서울대학교 전자공학과 석사
 1992년 : Purdue Univ. School of Elec. 공학박사
 1993년 ~ 1997년 : 삼성전자 신호처리연구소 수석연구원
 1997년 ~ 현재 : 성균관대학교 정보통신대학 교수
 ORCID : http://orcid.org/0000000256502881
 주관심분야 : 멀티미디어 영상압축, 영상인식, 신호처리
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
Haibo Z
,
Xiuchang 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
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 timefrequency 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
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 Blockbased 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 blockbased 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 Skipmode 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.
,
BabaieZadeh 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/ietipr:20080080