Sage Journals: Discover world-class research

Abstract

Block compressive sensing of image results in blocking artifacts and blurs when reconstructing images. To solve this problem, we propose an adaptive block compressive sensing framework using error between blocks. First, we divide image into several non-overlapped blocks and compute the errors between each block and its adjacent blocks. Then, the error between blocks is used to measure the structure complexity of each block, and the measurement rate of each block is adaptively determined based on the distribution of these errors. Finally, we reconstruct each block using a linear model. Experimental results show that the proposed adaptive block compressive sensing system improves the qualities of reconstructed images from both subjective and objective points of view when compared with image block compressive sensing system.

Keywords

Compressive sensing adaptive sampling error between blocks linear recovery

Introduction

The Nyquist sampling theorem requires to sample image signals with a high speed before image compression. The sampling rate must be at least as twice as the signal frequency in order to reconstruct signals accurately. At such a high sampling rate, sensed objects had to take a large number of sensors to sample the signal and then store it, which poses a great challenge to the sampling device. In recent years, compressed sensing (CS) has emerged with its capability of recovering an image without distortion at a sub-Nyquist sampling rate.^1–5 First, it uses a random measurement matrix Φ to project the sparse or compressible high-dimensional signal ( x ∈ R ^N) on an orthogonal basis to the low dimension space R ^M and obtains the measurement vector y = Φx ∈ R ^M. Then, the original signal is reconstructed with a high probability from a small number of projections by solving the optimization problem. CS combines sampling and compression, and according to the sparse degree of the image, it can recover the image signal from far fewer samples or measurements than required by Nyquist theorem.^6–8 However, for a massive-scale image, the heavy computing burden during the reconstruction process and the vast storage of the random measurement matrix can both lead to the excessive cost and time delay in random measurement. That makes CS impractical. In order to better encode and reconstruct image, many scholars have made unremitting efforts and found that block measurement of images can effectively weaken the deficiencies of the random CS measurement.^9–11

Under block compressive sensing (BCS) framework of images,¹² the sensed object is divided into n blocks of B×B in size, and each image block is measured independently using the same measurement matrix. It can reduce the storage capacity, so that the high-dimensional image acquisition can be effectively and easily achieved. However, due to different details of image blocks, the same sampling rate to measure and reconstruct each image block would cause a quality decline of block reconstruction or waste of resources. To overcome this defect, adaptive block compressive sensing (ABCS) is proposed by Zhang et al.¹³ and Canh et al.¹⁴ to adaptively allocate CS measurements on the basis of BCS, and to set the different measurement times for each block according to different feature details. ABCS can capture the image characteristics effectively and further improve the performance of BCS system. Zhang et al.¹³ use block variance to express the feature details of each block and adaptively measure the image based on the distribution of block variance. In the study by Canh et al.,¹⁴ the image edges are used as features and adaptively allocate the measurement times for each block according to varying edge. The above-mentioned works use some image features to reveal the block structure complexity, for example, block variance, edges. Although they can improve the reconstruction quality, these methods ignored the correlation between blocks. There are many blocking artifacts on reconstructed image, leading to a poor subjective quality. Therefore, an appropriate image feature, which is used to assess block structure complexity, has been a key to improving the performance of ABCS.

Based on ABCS framework, we propose an ABCS coding system which uses error between blocks to allocate measuring resources. The main contributions of our ABCS system are listed as follows:

We use the error between blocks to measure the block structure complexity, and according to this index, the CS measurements are adaptively allocated for image blocks.

We use a linear model to reconstruct each image block. Instead of using numerical iteration method, this model only performs several matrix-vector products.

By computing the error between each block and its adjacent blocks, we assign different sampling rates to each block. A higher measurement rate is assigned to blocks with larger error between blocks and lower one to blocks with smaller error. In order to avoid nonlinear iterative process, the proposed ABCS system performs linear reconstruction at decoder and reconstructs accurately image with a low computational complexity.

This article is organized as follows. Section “Introduction” is an introduction to CS and previous works; section “ABCS coding framework” describes ABCS coding framework; section “Proposed scheme” presents the proposed ABCS system using error between blocks; section “Experimental results” gives experiment results; and section “Conclusion” concludes this article.

ABCS coding framework

Image ABCS allocates sampling resources independently according to block characteristics. Details are as follows.

At the CS encoder, a natural scene is first captured by complementary metal-oxide semiconductor (CMOS) sensors as a full-sampling image x of N = R×C in size. Then, as shown in Figure 1, image x is divided into n blocks of B×B in size, and the image blocks are numbered from top to bottom and from left to right. Let x _i represent the ith (i=1, 2, 3, …, n; n=N/B²) block. Next, according to block features, we assign M_i (<<B²) measurement times to x _i and construct a corresponding random measurement matrix Φ _Bi. The elements of Φ _Bi obey Gaussian distribution with mean zero, and these elements are produced by a pseudorandom sequence, which was designed by Marsaglia and Tsang.¹⁵ Finally, the matrix-vector inner product is performed for x _i by Φ _Bi, and we obtain the block measurement vector y _i with the length M_B (<<B²)

y_{i} = Φ_{B i} x_{i}

(1)

in which the elements of M_i×B² Φ _Bi obey Gaussian distribution. To express the compression efficiency of each block, we define the measurement rate S_i as

S_{i} = \frac{M_{i}}{B^{2}}

(2)

After implementing CS sampling, all block measurement vectors are transmitted to decoder, and they are used to reconstruct the original image.

Figure 1.

Dividing an image into blocks.

At the CS decoder, ABCS system generally constructs the minimum l₂-l₁ norm reconstruction model as

{\hat{x}}_{i} = \arg min {‖ y_{i} - Φ_{B i} x_{i} ‖_{2}^{2} + λ {‖ Ψ_{B i} x_{i} ‖}_{1}}

(3)

in which||·||₂ and ||·||₁ are l₂ and l₁ norm, respectively; Ψ _Bi is the sparse-representation matrix of x _i, which can be generated by discrete cosine transform (DCT) or wavelet transformation; and λ is the fixed regularization factor. The model (3) is a convex optimization problem, and its solver is an important role in ABCS system. Many works are devoted to solve the model (3), for example, some classical algorithms: orthogonal matching pursuit (OMP)¹⁶ and iterative soft thresholding (IST).¹⁷ Recently, some advanced recovery algorithms^18–22 were proposed to improve the accuracy of solving the model (3), for example, Zhou et al.¹⁸ proposed a two-phase evolutionary approach to generate a robust solution of the model (3), Tan et al.¹⁹ added non-local sparsity and non-local low-rank regularization in the model (3) to improve the recovery accuracy, and Chang et al.²⁰ used two regularization terms multi-image non-local low-rank regularization and compensation-based adaptive total variation to raise the quality of reconstructed image.

Proposed scheme

Figure 2 presents the framework of the proposed ABCS scheme. At the CS encoder, after fully sampling image x , the error e_ij between block x _i and its surrounding blocks is calculated in turn. We take the maximum error value E_i as a reflection of structure complexity of x _i and adaptively allocate the measurement rate M_i for x _i according to E_i. The corresponding block measurement matrix Φ _Bi is generated for random CS measurement. At the CS decoder, a linear model is constructed to recover the image by matrix-vector product. The following describes in detail the adaptive measurement allocation and linear recovery.

Figure 2.

Proposed ABCS framework.

Error between blocks

This article uses error between blocks to reveal the structure complexity of each block. The calculation of error between blocks is shown in Figure 3. We select four neighboring blocks x _i○j (j = 1, 2, 3, 4) of the current block x _i and calculate the error values of x _i and its four neighborhood blocks as follows

e_{ij} = \frac{1}{B^{2}} ‖ x_{i} - x_{i \circ j} ‖_{2}

(4)

Figure 3.

Illustration of computing error between blocks.

The maximum error value of x _i○j is taken as the error E_i between blocks of x _i

E_{i} = max {e_{i 1}, e_{i 2}, e_{i 3}, e_{i 4}}

(5)

We calculate the error between blocks for x _i and normalize it by

w_{i} = \frac{E_{i}}{\sum_{i = 1}^{n} E_{i}}

(6)

According to w_i, we set measurement times of x _i. CS measurements should be allocated more for blocks whose error between blocks is larger and less for blocks which are otherwise. Since the error between blocks reflects block structures, it can be proportional to CS measurement times. Therefore, based on error between blocks, the adaptive measurement can ensure that each block has sufficient measurement resources. The above process has a light computational burden, its complexity is only O(N), so it cannot greatly raise the encoding costs.

Measurement allocation

According to w_i, we adaptively allocate measurement times for each block. First, we assign the initial measurement number M_0i to x _i as follows

M_{0 i} = c \cdot \frac{M}{n}

(7)

where M is the total measurement number of image and c is a parameter to control M_0i. Then, we calculate the measurement times of x _i as follows

M_{i} = round [(1 - c) \cdot w_{i} \cdot M + M_{0 i}]

(8)

where round[.] is rounding operator. Finally, in order to avoid that the measurement number exceeds the total number of pixels in image block, we set the upper limit of the measurement times as B² for each block, and the measurement number exceeding the upper limit is evenly distributed to other blocks.

Linear recovery

Traditional recovery algorithms solve the model (3) to reconstruct image blocks, and they have such a high computational complexity that it is difficult to reconstruct image blocks in a short time, so the proposed ABCS system adopts a linear recovery method. The idea of linear recovery is to construct a linear operator H , which is used to linearly project the measurement vector y _i into the estimation ${\hat{x}}_{i}$ of x _i. The criterion for selecting H is to minimize the residual e between the estimation ${\hat{x}}_{i}$ and the original block x _i. Suppose

{\hat{x}}_{i} = H \cdot y_{i}

(9)

The estimation residual e can be presented by

e_{i} = x_{i} - {\hat{x}}_{i}

(10)

The linear operator H is constructed by minimizing the mean square error of e as

H_{opt} = \arg min_{H} {\begin{matrix} R_{ee} = E (e_{i} {e_{i}}^{T}) \\ = E [(x_{i} - H y_{i}) {(x_{i} - H y_{i})}^{T}] \end{matrix}}

(11)

where E[.] is the expectation function. Make the gradient of R _ee (with respect to H ) equal to 0

H_{opt} = E [x_{i} {y_{i}}^{T}] E^{- 1} [y_{i} {y_{i}}^{T}]

(12)

Plug equation (1) into equation (12), and we get

H_{opt} = R_{xx} Φ_{B_{i}}^{T} ({Φ_{B}}_{i} R_{xx} Φ_{B_{i}}^{T})^{- 1}

(13)

where R _xx is the auto-correlation function of x _i, that is

R_{xx} = E [x_{i} x_{i}^{T}] = [\begin{matrix} E (x_{i 1} x_{i 1}) & E (x_{i 1} x_{i 2}) & \dots & E (x_{i 1} x_{i B^{2}}) \\ E (x_{i 2} x_{i 1}) & E (x_{i 2} x_{i 2}) & \dots & E (x_{i 2} x_{i B^{2}}) \\ ⋮ & ⋮ & ⋱ & ⋮ \\ E (x_{i B^{2}} x_{i 1}) & E (x_{i B^{2}} x_{i 2}) & \dots & E (x_{i B^{2}} x_{i B^{2}}) \end{matrix}]

(14)

The elements R_xx(i, j) in R _xx can be estimated as follows²³

R_{xx} (m, n) = E [x_{im} x_{in}] = ρ^{δ_{m, n}}

(15)

where δ_m,n is the chessboard distance²⁴ between x_im and x_im, ρ is the correlation coefficient, and we set it to 0.95 in general. According to H _opt, we can generate the estimation of original block by matrix-vector product. The image x is divided into n non-overlapping blocks, and a whole image is reconstructed by performing matrix-vector product for n times, so the linear recovery model has a low computational complexity.

Experimental results

The performance of ABCS system presented in this article is evaluated on a number of grayscale images of 512 × 512 in size including Lenna, Barbara, Peppers, Goldhill, and Mandrill. These test images include varying degrees of smoothness, edge, and texture detail. In all experiments, the block size B is set to 16, and the preset total measurement rate S (= M/N) between 0.1 and 0.5. The peak signal-to-noise ratio (PSNR)²⁵ is used to objectively evaluate the qualities of reconstructed images. The PSNR is computed by the following formula

PSNR = 10 \log_{10} (\frac{R \times C \times 255^{2}}{\sum_{i = 1}^{R} \sum_{j = 1}^{C} {| x_{i, j} - x_{i, j} |}^{2}})

(16)

in which R×C is the size of image, x_i,j is the pixel of original image, and ${\hat{x}}_{i, j}$ is the pixel of reconstructed image. We need to set the initial measurement times M_0i according to equation (7), in which M_0i is controlled by the parameter c, so the appropriate c value is first determined to ensure that the ABCS system presents itself with a good performance. After that, we compare our ABCS system with the BCS system proposed by Gan¹² and present their objective and subjective results. The BCS system uses OMP algorithm¹⁶ to reconstruct test images. All experiments are conducted under the following computer configuration: Intel(R) Core (TM) i7 @ 3.30 GHz CPU, 8GB, RAM, Microsoft Windows 7 64 bits, and MATLAB Version 7.6.0.324 (R2008a).

Threshold setting

We set the value of c to be between 0.05 and 0.5. Figure 4 shows the average PSNR curve on five test images as c value varies when the measurement rate S is, respectively, 0.1, 0.3, and 0.5. For the five images of different textures, the PSNR value has a significant upward trend when c is in the interval of [0.05, 0.30], indicating that our allocation scheme is ineffective when c is small. PSNR value shows a slow downward trend when c is in the interval of [0.30, 0.50], indicating that a large c value can degrade the reconstruction quality. When c is set to be 0.30, the average PSNR value on all test images is the highest at any measurement rate, so we set c to be 0.30 to get the better reconstruction quality.

Figure 4.

Average PSNR curve on the five test images as c value varies when the measurement rate S is (a) 0.1, (b) 0.3, and (c) 0.5, respectively.

Performance comparison

Table 1 shows the PSNR comparison of the proposed ABCS system and the BCS system at different measurement rates. Compared with the BCS system, the proposed ABCS system achieves a higher PSNR value at any measurement rate, for example, when S is set to be 0.1, 0.4, and 0.5, our system obtains an average PSNR gain of 0.47, 0.33, and 0.53 dB, respectively, which indicates that our system gets the better objective quality than BCS system. Table 2 shows the average reconstruction time on all test images at different measurement rates. It can be seen that our system has a low computational complexity, and it requires only 1.86 s on average to reconstruct a test image. Figure 5 shows the visual reconstruction qualities of reconstructed images by BCS and the proposed ABCS systems at S = 0.3. We can see that these reconstructed images by the BCS system are fuzzier than those reconstructed by our system, especially that some texture details cannot be well preserved, for example, for Mandrill reconstructed by BCS, severe blurs occur in the region of hairs, but our system generates the clear hair region. The proposed system provides the more pleasure visual results compared with BCS system. From the above, we can see that our system provides better objective and subjective qualities with a low computational complexity when compared with BCS system.

Table 1.

PSNR (in dB) comparison of the proposed ABCS system and the BCS system at the different measurement rates.

Image	Barnara	Goldhill	Lenna	Mandrill	Pepper	Avg.
S = 0.1
BCS	21.56	25.97	26.72	19.57	26.18	24.00
Proposed	21.78	26.30	27.41	19.76	26.79	24.47
ΔPSNR	0.22	0.33	0.69	0.19	0.61	0.47
S = 0.2
BCS	23.29	28.46	29.97	21.29	29.18	26.44
Proposed	23.46	28.69	30.53	21.51	29.57	26.75
ΔPSNR	0.17	0.23	0.56	0.22	0.39	0.31
S = 0.3
BCS	24.45	30.10	32.11	22.61	31.08	28.07
Proposed	24.68	30.40	32.67	22.91	31.36	28.40
ΔPSNR	0.23	0.30	0.56	0.30	0.26	0.33
S = 0.4
BCS	25.61	31.45	33.71	23.75	32.42	29.39
Proposed	25.91	31.94	34.40	24.23	32.80	29.86
ΔPSNR	0.30	0.49	0.69	0.48	0.38	0.47
S = 0.5
BCS	26.82	32.84	35.35	25.01	33.73	30.75
Proposed	27.24	33.40	36.04	25.62	34.11	31.28
ΔPSNR	0.42	0.56	0.69	0.61	0.38	0.53

PSNR: peak signal-to-noise ratio; ABCS: adaptive block compressive sensing; BCS: block compressive sensing; ΔPSNR: PSNR gain of the proposed system over BCS system.

Table 2.

Reconstruction time (in s) of the proposed ABCS system at any measurement rate.

S	0.1	0.2	0.3	0.4	0.5	Avg.
Time (in s)	0.94	1.28	1.73	2.33	3.04	1.86

ABCS: adaptive block compressive sensing.

Figure 5.

Visual qualities of reconstructed images by BCS and the proposed ABCS systems at S = 0.3. Left: reconstructed images by the proposed system; Middle: reconstructed images by the BCS system; Right: original images. (a) Lenna, (b) Barbara, (c) Peppers, (d) Goldhill, and (e) Mandrill.

Conclusion

In this article, we propose an ABCS system that adaptively measures each block according to error between blocks which is used to measure the structure complexity of each block. We set the measurement rate adaptively and reconstruct images using a linear model. The experimental results show that the proposed ABCS system provides better objective and subjective qualities when compared with BCS system.

The measurement vectors derived from our system must be quantized before transmission. However, we disregard this aspect, assuming that measurement vectors are densely quantized. In the future work, we will investigate the impact of quantization on the performance of ABCS system and propose an efficient quantization scheme to improve the practical utility of our system.

Footnotes

Handling Editor: Ioan Tudosa

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the National Natural Science Foundation of China, under Grants nos. 61501393 and 61601396; by the MOE (Ministry of Education in China) Project of Humanities and Social Sciences, under Grant no. 17YJCZH123; and by Nanhu Scholars Program for Young Scholars of XYNU.

ORCID iD

Ran Li

References

Donoho

. Compressed sensing. IEEE T Inform Theory 2006; 52(4): 1289–1306.

Candès

Romberg

Tao

. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE T Inform Theory 2006; 52(2): 489–509.

Candès

Tao

. Near-optimal signal recovery from random projections: universal encoding strategies. IEEE T Inform Theory 2006; 52(12): 5406–5425.

Candes

Romberg

. Quantitative robust uncertainty principles and optimally sparse decompositions. Found Comput Math 2006; 6(2): 227–254.

Candes

Tao

. Decoding by linear programming. IEEE T Inform Theory 2005; 51(12): 4203–4215.

Zhang

Yang

et al . A survey of sparse representation: algorithms and applications. IEEE Access 2017; 3: 490–530.

Becker

Bobin

Candes

. NESTA: a fast and accurate first-order method for sparse recovery. SIAM J Imaging Sci 2011; 4(1): 1–39.

Figueiredo

MAT

Nowak

Wrigh

. Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J Sel Top Signa 2008; 1(4): 586–597.

Mun

Fowler

. DPCM for quantized block-based compressed sensing of images. In: Proceedings of the 20th European signal processing conference, Bucharest, 27–31 August 2012, pp.1424–1428. New York: IEEE.

10.

Zhang

Zhao

Jiang

. Spatially directional predictive coding for block-based compressive sensing of natural images. In: Proceedings of the 20th IEEE international conference on image processing, Melbourne, VIC, Australia, 15–18 September 2013, pp.1021–1025. New York: IEEE.

11.

Mun

Fowler

. Block compressed sensing of images using directional transforms. In: Proceedings of the IEEE international conference on image processing, Cairo, Egypt, 7–10 November 2009, pp.2985–2988. New York: IEEE.

12.

Gan

. Block compressed sensing of natural images. In: Proceedings of international conference on digital signal processing, Cardiff, 1–4 July 2007, pp.403–406. New York: IEEE.

13.

Zhang

Xiang

Yin

et al . Adaptive compressed sensing for wireless image sensor networks. Multimed Tools Appl 2017; 76(3): 4227–4242.

14.

Canh

Dinh

Jeon

. Edge-preserving nonlocal weighting scheme for total variation based compressive sensing recovery. In: Proceedings of the IEEE international conference on multimedia and expo, Chengdu, China, 14–18 July 2014, pp.1–5. New York: IEEE.

15.

Marsaglia

Tsang

. The ziggurat method for generating random variables. J Stat Softw 2000; 5(8): 1–2.

16.

Tropp

Gilbert

. Signal recovery from random measurements via orthogonal matching pursuit. IEEE T Inform Theory 2008; 53(12): 4655–4666.

17.

Beck

Teboulle

. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J Imaging Sci 2009; 2(1): 183–202.

18.

Zhou

Kwong

Guo

et al . A two-phase evolutionary approach for compressive sensing reconstruction. IEEE T Cybernetics 2017; 47(9): 2651–2663.

19.

Tan

Hou

Chen

et al . Image compressive sensing reconstruction based on collaboration reduced rank preprocessing. Electron Lett 2017; 53(11): 717–718.

20.

Chang

Ding

PLK

. Compressive sensing reconstruction of correlated images using joint regularization. IEEE Signal Proc Let 2016; 23(4): 449–453.

21.

Song

Gao

Shen

et al . Compressed sensing image reconstruction using intra prediction. Neurocomputing 2015; 151: 1171–1179.

22.

Liu

Zhai

Zhou

et al . Compressive sampling-based image coding for resource-deficient visual communication. IEEE T Image Process 2016; 25(6): 2844–2855.

23.

Tran

. Context-based entropy coding of block transform coefficients for image compression. IEEE T Image Process 2002; 11(11): 1271–1283.

24.

Gonzalez

Woods

Eddins

. Digital image processing using MATLAB. Beijing, China: Publishing House of Electronics Industry, 2009.

25.

Khan

Muhammad

Irfan

et al . A novel magic LSB substitution method (M-LSB-SM) using multi-level encryption and achromatic component of an image. Multimed Tools Appl 2016; 75(22): 14867–14893.

Adaptive compressive sensing of images using error between blocks

Abstract

Keywords

Introduction

ABCS coding framework

Proposed scheme

Error between blocks

Measurement allocation

Linear recovery

Experimental results

Threshold setting

Performance comparison

Conclusion

Footnotes

Declaration of conflicting interests

Funding

ORCID iD

References