A Journal of Software Engineering and Applications, 2012, 5, 134-139
doi:10.4236/jsea.2012.512b026 Published Online December 2012 (http://www.scirp.org/journal/jsea)
A Distributed Compressed Sensing for Ima ges Based on
Block Measu rements Data Fusion
Huaixin Chen, Jie Liu
Key Lab. of Information Processing, Southwest China Institute of Electronics Technology, Chengdu, P.R. Chi na .
Received 2012
ABSTRACT
Compressed sensing (CS) is a new technique for simultaneous data sampling and compression. In this paper, we pro-
pose a novel method called distributed compressed sensing for image using block measurements data fusion. Firstly,
original image is di vided into s mall blocks and each block is sampled independently using the same measure ment oper-
ator, to obtain the s maller enco ded sparser coe fficie nts and stored mea su rements matrix and its vectors. Secondly, orig-
inal image is reconstructed using the block measurements fusion and recovery transform. Finally, several numerical
experiments demonstrate that our met hod has a mu ch lo wer data storage a nd calculatio n cost as well a s high qualit y of
rec onstructio n when compared with other exist ing sc hemes. We believe it is of great pr actical potentials in the networ k
communication as well as pattern recognition domain.
Keywords: Distributed CS for I mag e; Information Fusion; Pattern recognition; Network Co mmunica tion
1. Introduction
With the development of the optical technology, the im-
age we got from the digital camera often has above 10
million pixels, the real world becomes clearer in the
electronic world, simultaneously, it becomes harder to
store and tra nsmit the se imag es. In c onve nti ona l i magi ng
syst ems, natural images are often first sampled into the
digital format at a higher rate and then compressed
through the JPEG or the JPEG 2000 [1] co d e for efficient
storage purpose. However, this approach is not applica-
ble for low-power, low resolution imaging devices such
as a sensor network with limit e d computation capabilities.
Fortunately, the compressed sensing theory (CS) [2-5]
which is proposed by Donoho and Candes, who shows
that under certain conditions, a signal can be precisely
reconstructed from only a small set of measurements.
Recently, CS has attracted considerab le attentions in areas
of applied mathematics, computer science, and electrical
engineering due to its excellent performance.
Compressed sensing acquisition of data might have an
important impact for the design of imaging devices
where data acquisition is expensive. Duarte et al. [6] de-
tail a single pixel camera that acquires random projec-
tions from the visual scene through a digital micro-mirror
array. The Block diagram of a single pixel camera has
showed in Figure 1. A similar acquisition strategy can
be used in MRI imaging to reduce the acquisition time
and increase the spatial resolution.
In addition, Bloc k-based CS for image is proposed
[7], block measurement is more advantageous for real-
time applications as the encoder does not need to send
the sampled data until the whole image is measured, and
the possibility of explo iting block CS is motivated b y t he
great success of block DCT coding systems which are
widely used in the JPE G and the MPEG standards.
In this paper, we present a novel distributed CS me-
thod which uses block measurements data fusion to re-
construct original images. The main advantage is to de-
crease the storage of encoder and huge bytes of data traffic,
and to need smaller calculate cost than that Block-based
Figure 1. Block diagram of a single-pixel camera

A distributed compressed sensing for images based on block measurements data fusion
135
CS resto red fro m a set of sub-measurement recovery and
jo int s ub -image. Therefore, our proposed method is mo re
advantageous in many important and emerging applica-
tions, e.g., the sensor network system or network com-
munication.
2. Background
2.1. Compressed Sensi ng
CS builds upon the fundamental fact that we can
represent many signals usi ng only a few non -zero coeffi-
cients in a suitable basis or dictionary. Based on CS
theoretic requireme n t that signal is assumed to be ap-
proximately sparse, we suppose that the transform coef-
ficients in the orthogonal basis Ψ of an
N
dimensional
vector
X
are sparse , the signal
X
can be represented as
[8]:
= Ψ Xa
(1)
where
a
is an
N
dimensional sparse coefficients vector,
it has o nly
K
non-zero coefficients. In order to take com-
pressed sensing measurements, we let
Φ
denote an
M
by
N
matrix with M×N. The measurement ma-
trix
Φ
should be uncorrelated with the transform ma-
trix
Ψ
.
M
measurements are obtaine d b y a linear system:
= == ΦΦΨ Φ Y Xaa
(2)
Where, sensing matrix
RMN× = ∈ Φ ΦΨ
,an
n-dimensional Euclidean signal vector space is denoted
by Rn . If the sensing matrix satisfies the Restricted Iso-
metry Property (RIP) [9,10], the sparse coefficients vec-
tor can be re constructe d as sol ving the fo llowin g minim-
al l0 norm optimization problem:
0
argmin||||. .st= = ， Φ aa aY
(3)
After obtained the sparse coefficients vector
a
, we
can exactl y reco nstruc t the original signal
X
as follow:
= Ψ Xa
(4)
Essentially, the optimization problem (3) is an NP-
hard problem; usually we must convert the minimal l0
norm optimization problem into the l1 norm or l2 nor m to
solve the sub optimization problem.
The methods we often used to solve the l1 norm opti-
mization problem are orthogonal matching pursuit [11],
iterative hard thresholding [12], gradient pursuits [13],
convex optimization [14], non-convex minimization [15]
and so on.
2.2. The block-base d CS with unit e d sub-images
The CS theoretic breaks the limit of Nyquist sampling
rate, it can compress the data at the same of sampling,
but the qua ntity o f the CS measurement matrix’s column
and row equal to the dimension of the signal and mea-
surements vector, respectively. In processing the high-
resolution optical image, it still need to store the enorm-
ous measurement matrix and measurements vector,
which takes a lot of time to reconstruct original image
thro ugh so lving t he optimization problem.
The block-based CS is proposed [16] to break the
bottleneck of the enormous data quantity image trans-
mitted by band-limited communication network, which
divides origina l image with huge gigabyte s of pixe ls into
many sub-images, which is projected and quantized in
the encoder, block-by-block measurements decoded and
reconstruction of subspace, finally, it make a recovery
the original image from joint sub-images, as showed in
Figure 2.
In Figure 2, firstly the block-based CS divides the
original big image into many small sub-image, next it
gets every sub-image ’s measur ements of compre ssed cod-
ing. Every sub-images has been a cquisition from block
measurements of CS processing. Finally, original image
is restored using joint reconstructed sub-images in a
block-by-block manner. Since each block is processed
independently in the block-based CS, Block-based mea-
surement is more advantageous for realtime applications
because the encoder does not need to send the sampled
data until the whole image is measured, the initial solu-
tion can be easily obtained and the reconstr uction proc ess
can be substantially speeded up. However, the approach
still need to store a large of data for measureme nts and
sub-images, and there are complex calculate cost for un-
ion sub-images to recover original im ag e.
3. Distributed CS Based on Block
Measurments Fusion
In the block CS, it ignores the strong cor r ela tio n of the
sub-images, which employed to reconstruct origina l im-
age by union them. For the sake of mining the correlation
among the sub-images and reducing the data storage as
well as calculatio n cost, we present a novel method of
distributed CS for image based on block measurements
fusion, wh ose processing is shown in Figure 3.
Being different from Block-based CS, the proposed
method in this paper doesn’t reconstruct original image
from a set of the recovery sub-images separatel y, but
restored original sub-image’s block measurement matrix
and its measurement vectors a t firstly, and reco nstruction
Divided into sub
images
Quantization
and denotation
encoding
CS projection
Original image
Denotation
decoding Sub images joint
CS
reconstruction
Compression
image
Reconstruction
image
Encoder
Decoder

A distributed compressed sensing for images based on block measurements data fusion
136
Figure 2. The diagram of block-base d CS by joint sub-i mages .
Divided into sub
images
Quantization
and denotation
encoding
CS projection
Original image
Denotation
decoding CS
reconstruction
Block
measurements
fuion
Compression
image
Compression
image Reconstruction image
Encoder
Decoder
Figure 3: The diagram of distribution CS based on block
meas ureme nts fusion.
original image though to synthesis measurement matrix
and its measurement vectors using data fusion, so as to
reduces the storage in the decoder and reduce the calcu-
lations from united s ub-images. The associated algorith m
is given in the next section detailedl y.
3.1. Synthese’s measurements matrix and its
vectors
In the decompressed of distribution CS, we get every
compressed measurements blocks of n column by n
column or m row by m row. Let
n
dimensional vec-
tor
x
denote one column of the original image. We can
obtain the measurements of
x
by
y =Ax
,
R
m
∈y
,
where m is a number of measurement vector,
R
mn×
∈A
is
th e measure me nt ma tr ix. This process sho ws in figure 4.
In [17], the authors indicate that if the measurement
matrix is random gauss matrix, the sensing matrix can
satisfy the RIP with hi gh prob ability. The theoretic a nal-
ysis and experimental r esults show that all of the differ-
ent measurement matrixes perform excellently and we
can’t find which one is bette r than ot hers. So we empl oy
the ra ndo m Gaus s matrix wit h the normal distrib utio n as
the mea s ure ment matrix of CS.
Suppose the column of image divided into
u
seg-
ments(or blocks), denoted by
12
, ,...,
u
xx x
, the number
of every segment are
12
,,..., u nn n
,respectively. In a cast
of overlap segment with the neighbors, therefore,
12
...
u
nnn n+>++
. In other case of no overlap seg-
ment ，
12
...
u
nnn n+=++
. Every segment’s com-
presse d measurements
i
y
can obtain as follow:
; 1,2,...,
i ii
iu = =y Ax
(5)
Where,
R
ii
mn
i
×
∈A
is the i-th segment’s measure-
ment matrix, that is a block measurement matrix,
i
m
is
the number of it s compressed measurements.
3.2. Fusion algorithm
The reconstruction op timization problem in CS is:
1
min|||| ,. .st = Ψ fy Af
. which indicates that to
reconstruct the sparse coefficients
f
of vector
x
, we
must know the measurement matrix
A
, measurements
vector
y
, and the sparse matrix
Ψ
. Because the matrix
Ψ
doesn’t be used in the encoder, so we just need to
synthesis the measurement matrix A and measurements
of vector y of original image
x
from every sub-block
measurements.
The reconstructed
A
and
y
satis f y the equation as
follow:
11 12
1
'' '
12 1
[ ,,...,]
[ :,1::,1:,...,
:,1:1][ ,,...,]
[,...,][ ,,...,]
u
u
nn nn
n-n +:n
=
=
=
=
+
12
2
2
( )()
()
+，
，
u
u
u
y Ax
A. xxx
AA
A.x xx
AAA .xxx
(6)
Then we obtain:
'' '
12
() ()()(),...,
uu
j j,:j,:j,:=++
12
+yA xAxAx
(7)
Where,
1,2,...,jm=
.
Using the equatio n (7), we know that every en-
try
(),= 1,2,...,jj my
of
y
, contains all entrie s’ informa-
tion of
x
.The measurements are obtained through mul-
tiplying measurement matrix by vector, so the every en-
try of
A
correlates with
i
A
.
As the case of no overlap segments,
...nn nn += ++
12 u
,
every entry
( ),1,2,...,
ii
kk m=y
of
i
y
is obtained
thro ugh multi plying o ne whol e ro w of me asure me nt ma-
trix b y vector
i
x
, so the r ows of sub-measurement matrix
just can be operated linearly and must treat the whole
row as an entry. From the equation
(6),
( )=()j j,:y Ax
and
12
...
u
nnnn+=++
, the row
number of all the sub-measurement matrix should be
extended to
m
, and then fused the b lock matrix to recon-
struct the whole measurement matrix A, which shows in
figure 5.

A distributed compressed sensing for images based on block measurements data fusion
137
Figure 4. The projection of CS
Figure 5: The fusion of block measurement’s data mat rix.
The next work is to expand the
ii
mn×
matrix
i
A
to
the
i
mn×
matrix
i'A
. In the section 3.1, we let the
meas ure ment matri x b e ra ndom Gauss matrix, so that the
reconstruction whole matrix should also be random
Gauss matrix satisfied the RIP.
From the applied probability, if
() ~N(0,1)
i
p,qA
,
and
()~N(0,1)
k
w,tA
, let
()+()
ik
ap,q bw,t=SA A
,
where a and b are constant.
So that we can obtain:
22
~ N(0,)ab+S
.
The encoder with high confidence nearly loses data
so to bring error. By contrast, the low confidence ones
should always happen, so we endue the
sub-measurement matrix with different power val-
ue
1/ pw,1,2,...,
k
ku=
, a high power is set to the matri x
with a high confidence and vice versa, which can im-
prove performance the reconstruction of image.
For the convenience of denotation,
,ASSi C
de-
notes that let the i-th row of
A
be the value of
C
, so
the measurement matrix’s fusion formula can be
represented as:
11
22
1 1111()()
1
2 2222()()
() ()
= ,{ [((),:)+((),:)]/pw| ,
[((),:)+((),:)]/pw| ,...,
[((),:)+((),:)]/pw| }
uu
m
ji ki
i
ji ki
u uuuuji ki
ji ki
ji ki
ji ki
i
≠
=
≠
≠
∑
AASS AA
AA
AA
(8)
Where, for the different
i
, at least the value of
()
p
ji
or
( ),1,2,...,
p
kip u=
should be changed.
By the equation (8),
= y Ax
and
i ii
= y Ax
, we can
obtain the measurements’ vector fusion formula as
follow:
=1
1
( )=[(())+(())]
pw
u
vv vv
vv
iji ki
∑
y yy
(9)
Where,
1,2,...,im=
; the relation of
()
v
ji
and
()
v
ki
is same as equal(8).
4. Experimental Results
The proposed distr ib uted CS based-on block mea-
surements fusion(BMF-DCS) sampling and reconstruc-
tion algorithms were i mpleme nted using Matlab software
with version 7.8.0 in PC Computer . For making a nice
comparison, we refer to the resulting impleme ntatio ns as
the Block CS for image based-on sub-images joint
(SIJ-BCS) . In the numerical experiments, we choose
three images Dock , Mountain and Cameraman for the
experimental object, those test image is of 256×256
pixels and its measurement ratio is 0.6. To evaluate di-
rectional transforms for CS reconstruction, we deploy the
DCT matrix is as sparse matrix within both the SIJ-BCS
framework and proposed BMF-DCS in this paper, and
the or thogo na l ma tchi ng p ursui t rec ons truc tin g algorithm
is applied to solve the optimizatio n p r oblem.
Fig.6- Fig.8 illustrate s the several example visual re-
sults. The numerical experiments demonstrate that both
the SIJ-BCS and BMF-BCS can reconstruct the original
image with similar good visual qualities for Dock,
Mountain and Cameraman. Howeve r, We note that the
rec onst ruc ti o n i ma ges from BMF-BCS are smoother than
that from SIJ-BCS. That is ,the reconstructed images by
the SIJ-BCS method have many noises in the edges and
blurred picture , but the reconstructed images using the
BMF-BCS method is of smooth in the edges.
Figure 6. Reconstru ction of D ock image. (a) Ori ginal i mage;
(b) SIJ-BCS reconstruction; (c) BMF-DCS r econst ructi on.

A distributed compressed sensing for images based on block measurements data fusion
138
Figure 7: Reconstruction of Mountain image. (a) Original
image; (b) SIJ-BCS reconstruction; (c) BM F-DCS r eco nstruc-
tion.
Figure 8: Reconstruction of Cameraman image. (a) Orig inal
image; (b) SIJ-BCS reconstruction; (c) BMF-DCS
reconstruction.
To e valuate the performance of reconstruction by qu-
alitatively, We emp loy the processing time of recon-
struction image in the decoder (TOD) as the calculate
cost, and use the number of data that stored in the de-
coder (NDD) to be represent the storage quantity, a nd the
power signal-to-noise ratio(PSNR) is used for evaluation
of the con s t ruction qua lit y. Here, the PSNR i s give n by:
11
22
max 00
PSNR10
log{/[( ,)(,)]}
MN
xy
M Nfxyxy
−−
= =
= ×
×× −
∑∑ gf
(10)
Table 1 tabulates the TOD, PSNR and NDD results
of both our algorithms (MBF-BCS) and SIJ-BCS recon-
struction algorithms on three 256×256 pixels natural
images Dock, Mountain and Cameraman.
Fro m t ab le 1, we can see that, for the complex image
Dock and Cameraman with symmetric al sparsity, these
two methods perform similarly, the BMF-BCS recon-
struction PSN R is higher than the SIJ-BCS only by 1dB.
For the si mple ima ge M o unt ai n wit h asymmetric sparsity,
the PSNR of BMF-BCS yields about 4.5 dB improve-
ments.
Additionally, The SI J-BCS metho d’s processing time
of the decoder reaches more than 100 times the BMF-
BCS methods, this result indicates that the BMF-BCS
largely reduces the calculate cost of the decoder. In some
sense, we can use some cheap equipments to achieve the
work that achieved by the dear equipment before. The
last column of Table 1, value of NDD shows that near
half a mount of processing data by the BMF-BCS method
is that by t he SIJ-BCS method in the decod er, it imply
our method can also reduce the cost of the equipment .
As for image block CS method based on sub images
joint, it ignores the correlations among the sub-images ,
whose reconstructing original images in manner of unit-
ed them .Therefore, the block CS method can only re-
construct the sparser images with high prec ision and the
less sp arse r sub -ima ges wit h lo w pre cisio ns. Bu t t he ne w
method proposed in this paper can reconstruct the whole
image with high precision because of the fault-tolerant
data fusio n used in the decod er to mine the correlation of
the s ub-images.
5. Conclusion
In this paper, we propose a novel distributed CS method
based-on block measurements fus i on in which we use the
block measurement matrix and its vectors fusion to syn-
thesis the whole measurements, then to reconstruct the
ori ginal i ma ges, t hat need no joint sub -ima ge. T he s ever-
al numerical experimental results show our algo r ithm can
reconstruct the original image with a high precision, and
largely reduce the storage and calculation cost for image
reconstruction in the decoder. Compared with
Table 1. Comparisons of reconstruction TOD, PSNR and
NDD measured by different methods.
TOD/s PSNR/dB NDD
Dock SIJ-BCS 4.336 17.25 65536
BMF-BCS
0.031
18.34
39321
Mounta in
SIJ-BCS
4.255
32.26
65536
BMF-BCS
0.026
36.72
39321
Camera-man
SIJ-BCS
4.628
21.57
65536
BMF-BCS
0.028
22.35
39321

A distributed compressed sensing for images based on block measurements data fusion
139
exist ing sche mes, the proposed new o ne contains a much
lower data storage and a much lower calculation cost as
well a s high q uality of i mage re construc tion. W e think it
is of practical potentials in the network communication
as well as realtime object recognition domain.
REFERENCES
[1] Varma,K.Bell.A.JPEG2000-choices and tradeoffs for en-
coders[J].Signal Processing Magazine, IEEE Nov.2004
Volu me ：21,Issue:6:70-75.
[2] DONOHO David L. Compressed Sensing[J]．IEEE Trans
Inform Theory,2006,52:1289-1306．
[3] CAN DÉS E, ROMBERG J, TAO T. Robust Uncertainty
Principles: Exact Signal Reconstruction from Highly In-
complete Frequency Information[J]. IEEE Transactions on
Information Theory,2006, 52( 2) : 489 -509.
[4] BARANIUK R, CEVHER V, DUARTE M, et al. Mod-
el-based Compressive Sensing[J].IEEE Trans. Inform.
ThEory,2010, 56(4):1982-2001.
[5] Baron, D., Wakin, M.B., Duarte, M.F. Sarvotham,S., Ba-
raniuk, R.G. Distributed compressed sensing.(2005)
Availabl e at http://www.dsp.rice.edu/cs.
[6] M. Duarte, M. Davenport, D. Takhar, J. Laska, T. Sun, K.
Kelly, and R. Baraniuk, “Single-pixel imaging via com-
pressive sa mpling, ” IEEE S ignal P rocessing M agazine, vol .
2, no. 25, p p. 83 –91, 2008.
[7] Sungkwang Mun, James E. Fo wl e r . Block Compressed
Sensing of images using directional transforms. Proceed-
ings of the International Conference on Image Processing,
2009, 30 21-3024.
[8] Baraniuk R. Compressive sensing[ J] . IEEE Signal
Processing Magazine, 2007, 24(4): 118-121
[9] BOURGAIN J, DILWORTH S, FORD K., et al. Explicit
Constructions of Rip Matrices and Related Problems[J].
Duke Math. J,2011,159:145-185.
[10] M. Davenport ,M. Wakin. Analysis of orthogonal matching
pursuit using the restricted isometry property. IEEE Trans
Inform Theory, 2010,56(9):4395-4401.
[11] M. Davenport ,M. Wakin. Analysis of orthogonal matching
pursuit using the restricted isometry property. IEEE Trans
Inform Theory, 2010,56(9):4395-4401.
[12] T. Blumensath , M. Davies. Iterative hard thresholding for
compressive sensing.Appl Comput Harmo n Ana l ,2009,
27(3):265-274.
[13] T. Blumensath and M. Davies. Gradient pursuits. IEEE
Trans. Signal Processing, 2008,56(6):2370-2382.
[14] E. Candes, B. Recht. Exact matrix completion via convex
optimization. Found Comput Math, 2009,9(6):717-772.
[15] Chartrand R．Exact reconstruction of sparse signals via
non-convex minimization[J].IEEE Signal Processing Let-
ters,2007,14(10),707- 710．
[16] Gan L.Block compressed sensing of natural im-
ages[C]//Proc Int Conf on Digital Signal Processing, Car-
diff, UK, 2007．
[17] Yaakov Tsaig, David L.Donoho. Extensions of Com-
pressed Sensing. Signal Processing, 86(2006) 549-571.