A Journal of Software Engineering and Applications, 2012, 5, 134139 doi:10.4236/jsea.2012.512b026 Published Online December 2012 (http://www.scirp.org/journal/jsea) Copyright © 2012 SciRes. 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 . Email: chenhuaixin@sina.com 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 lowpower, low resolution imaging devices such as a sensor network with limit e d computation capabilities. Fortunately, the compressed sensing theory (CS) [25] 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 micromirror 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 kbased 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 Blockbased Figure 1. Block diagram of a singlepixel camera
A distributed compressed sensing for images based on block measurements data fusion Copyright © 2012 SciRes. JSEA CS resto red fro m a set of submeasurement 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 dimensional vector are sparse , the signal can be represented as [8]: (1) where is an dimensional sparse coefficients vector, it has o nly nonzero coefficients. In order to take com pressed sensing measurements, we let denote an by matrix with M×N. The measurement ma trix should be uncorrelated with the transform ma trix . measurements are obtaine d b y a linear system: (2) Where, sensing matrix ,an ndimensional 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 , we can exactl y reco nstruc t the original signal as follow: (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], nonconvex minimization [15] and so on. 2.2. The blockbase d CS with unit e d subimages 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 blockbased CS is proposed [16] to break the bottleneck of the enormous data quantity image trans mitted by bandlimited communication network, which divides origina l image with huge gigabyte s of pixe ls into many subimages, which is projected and quantized in the encoder, blockbyblock measurements decoded and reconstruction of subspace, finally, it make a recovery the original image from joint subimages, as showed in Figure 2. In Figure 2, firstly the blockbased CS divides the original big image into many small subimage, next it gets every subimage ’s measur ements of compre ssed cod ing. Every subimages has been a cquisition from block measurements of CS processing. Finally, original image is restored using joint reconstructed subimages in a blockbyblock manner. Since each block is processed independently in the blockbased CS, Blockbased 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 subimages, and there are complex calculate cost for un ion subimages 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 subimages, which employed to reconstruct origina l im age by union them. For the sake of mining the correlation among the subimages 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 Blockbased CS, the proposed method in this paper doesn’t reconstruct original image from a set of the recovery subimages separatel y, but restored original subimage’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 Copyright © 2012 SciRes. JSEA 136 Figure 2. The diagram of blockbase d CS by joint subi 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 ubimages. 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 dimensional vec tor denote one column of the original image. We can obtain the measurements of by , , where m is a number of measurement vector, 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 seg ments(or blocks), denoted by , the number of every segment are ,respectively. In a cast of overlap segment with the neighbors, therefore, . In other case of no overlap seg ment ， . Every segment’s com presse d measurements can obtain as follow: (5) Where, is the ith segment’s measure ment matrix, that is a block measurement matrix, is the number of it s compressed measurements. 3.2. Fusion algorithm The reconstruction op timization problem in CS is: . which indicates that to reconstruct the sparse coefficients of vector , we must know the measurement matrix , measurements vector , 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 from every subblock measurements. The reconstructed and satis f y the equation as follow: 11 12 1 '' ' 12 1 [ ,,...,] [ :,1::,1:,..., :,1:1][ ,,...,] [,...,][ ,,...,] u u nn nn nn +:n = = = = + 12 2 2 ( )() () +， ， u u u y Ax A. xxx AA A.x xx AAA .xxx (6) Then we obtain: '' ' 12 () ()()(),..., j j,:j,:j,:=++ 12 +yA xAxAx (7) Where, . Using the equatio n (7), we know that every en try of , contains all entrie s’ informa tion of .The measurements are obtained through mul tiplying measurement matrix by vector, so the every en try of correlates with . As the case of no overlap segments, , every entry of is obtained thro ugh multi plying o ne whol e ro w of me asure me nt ma trix b y vector , so the r ows of submeasurement matrix just can be operated linearly and must treat the whole row as an entry. From the equation (6), and , the row number of all the submeasurement matrix should be extended to , 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 Copyright © 2012 SciRes. JSEA Figure 4. The projection of CS Figure 5: The fusion of block measurement’s data mat rix. The next work is to expand the matrix to the matrix . 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 , and , let , where a and b are constant. So that we can obtain: . 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 submeasurement matrix with different power val ue , 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, de notes that let the ith row of be the value of , 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 , at least the value of or should be changed. By the equation (8), and , we can obtain the measurements’ vector fusion formula as follow: =1 1 ( )=[(())+(())] pw u vv vv vv iji ki ∑ y yy (9) Where, ; the relation of and is same as equal(8). 4. Experimental Results The proposed distr ib uted CS basedon block mea surements fusion(BMFDCS) 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 basedon subimages joint (SIJBCS) . 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 SIJBCS framework and proposed BMFDCS 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 SIJBCS and BMFBCS 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 BMFBCS are smoother than that from SIJBCS. That is ,the reconstructed images by the SIJBCS method have many noises in the edges and blurred picture , but the reconstructed images using the BMFBCS method is of smooth in the edges. Figure 6. Reconstru ction of D ock image. (a) Ori ginal i mage; (b) SIJBCS reconstruction; (c) BMFDCS r econst ructi on.
A distributed compressed sensing for images based on block measurements data fusion Copyright © 2012 SciRes. JSEA 138 Figure 7: Reconstruction of Mountain image. (a) Original image; (b) SIJBCS reconstruction; (c) BM FDCS r eco nstruc tion. Figure 8: Reconstruction of Cameraman image. (a) Orig inal image; (b) SIJBCS reconstruction; (c) BMFDCS 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 signaltonoise 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 (MBFBCS) and SIJBCS 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 BMFBCS recon struction PSN R is higher than the SIJBCS only by 1dB. For the si mple ima ge M o unt ai n wit h asymmetric sparsity, the PSNR of BMFBCS yields about 4.5 dB improve ments. Additionally, The SI JBCS metho d’s processing time of the decoder reaches more than 100 times the BMF BCS methods, this result indicates that the BMFBCS 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 BMFBCS method is that by t he SIJBCS 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 subimages , 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 faulttolerant data fusio n used in the decod er to mine the correlation of the s ubimages. 5. Conclusion In this paper, we propose a novel distributed CS method basedon 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 SIJBCS 4.336 17.25 65536 Mounta in Cameraman
A distributed compressed sensing for images based on block measurements data fusion Copyright © 2012 SciRes. JSEA 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.JPEG2000choices and tradeoffs for en coders[J].Signal Processing Magazine, IEEE Nov.2004 Volu me ：21,Issue:6:7075. [2] DONOHO David L. Compressed Sensing[J]．IEEE Trans Inform Theory,2006,52:12891306． [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 elbased Compressive Sensing[J].IEEE Trans. Inform. ThEory,2010, 56(4):19822001. [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, “Singlepixel 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 213024. [8] Baraniuk R. Compressive sensing[ J] . IEEE Signal Processing Magazine, 2007, 24(4): 118121 [9] BOURGAIN J, DILWORTH S, FORD K., et al. Explicit Constructions of Rip Matrices and Related Problems[J]. Duke Math. J,2011,159:145185. [10] M. Davenport ,M. Wakin. Analysis of orthogonal matching pursuit using the restricted isometry property. IEEE Trans Inform Theory, 2010,56(9):43954401. [11] M. Davenport ,M. Wakin. Analysis of orthogonal matching pursuit using the restricted isometry property. IEEE Trans Inform Theory, 2010,56(9):43954401. [12] T. Blumensath , M. Davies. Iterative hard thresholding for compressive sensing.Appl Comput Harmo n Ana l ,2009, 27(3):265274. [13] T. Blumensath and M. Davies. Gradient pursuits. IEEE Trans. Signal Processing, 2008,56(6):23702382. [14] E. Candes, B. Recht. Exact matrix completion via convex optimization. Found Comput Math, 2009,9(6):717772. [15] Chartrand R．Exact reconstruction of sparse signals via nonconvex 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) 549571.
