Compressed Sensing Based Apple Image Measurement Matrix Selection

Abstract

The purpose of this paper is to design a measurement matrix of apple image based on compressed sensing to realize low cost sampling apple image. Compressed sensing based apple image sampling method makes a breakthrough to the limitation of the Nyquist sampling theorem. By investigating the matrix measurement signal, the method can project a higher dimensional signal to a low-dimensional space for data compression and reconstruct the original image using less observed values. But this method requires that the measurement matrix and sparse transformation base satisfy the conditions of RIP or incoherence. Real time acquiring and transmitting apple image has great importance for monitoring the growth of fruit trees and efficiently picking apple. This paper firstly chooses sym5 wavelet base as apple image sparse transformation base, and then it uses Gaussian random matrices, Bernoulli random matrices, Partial Orthogonal random matrices, Partial Hadamard matrices, and Toeplitz matrices to measure apple images, respectively. Using the same measure quantity, we select the matrix that has best reconstruction effect as the apple image measurement matrix. The reconstruction PSNR values and runtime were used to compare and contrast the simulation results. According to the experiment results, this paper selects Partial Orthogonal random matrices as apple image measurement matrix.

1. Introduction

Conventional approaches to sample signal or images include four steps: sampling, compression, transmission, and decompression. In order to reduce the cost of sensor acquisition, transmission, and storage, a large number of researchers focus on data compressing and dimension reduction and so forth. But prior studies require users to first obtain the original data and store it and then compress and transmit the data. This process brings a great burden to the sensor. In practical applications, it is hard to satisfy the demand of collecting data in real time. On the contrary, if we use “sampling and compression” technology and obtain the compressed signal directly, it will enormously reduce the time and store space demand of acquisition data. Random matrix is common and easy to analyze. The process of the signal acquisition can be projected to dimension reduction, which can greatly realize data compression. Thereby CS has gathered widespread attention from researchers. For example, Toeplitz matrix and circulant matrix were applied to the linear dynamic systems [1–4]. The block diagonal matrix was applied to the distributed sensor system [5] and the initial forecast linear systems [6]. These random matrices acquire good effects in practice.

Compressed sensing is a new sampling theory proposed in recent years; this theory makes a breakthrough on the limitation of the Nyquist sampling theorem. It has been proven that using a rate which is lower than the Nyquist rate to sample the signal and reconstruct the data is feasible. Data acquisition methods based on this theory use “sampling and compression” technology and obtain the compressed signal directly. CS requires the number of samples to be far less than conventional signal processing and these samples can recover the original signal exactly. This reduces the cost of the signal's acquisition and transmission. CS brings a revolutionary breakthrough for information acquisition and processing technology. Currently, CS is applied in many fields, especially image processing. A number of results have developed based on CS theory. For example, Rice University professor Duarte and his colleagues developed a single-pixel [7], compressive sensing camera which was based on CS theory. This design included a new camera structure and is the most famous proof of concept model for CS.

Based on “sampling and compression” technology, we acquire signal by projecting the high dimension signal to the low dimension space using measurement matrix. Measurement matrix is designed according to the characteristics of the signal. The measurement matrix and the sparse base must satisfy the restricted isometry property (RIP) conditions, which can reconstruct the original signal. Toeplitz matrix and circulant matrix have been applied in the channel estimation and synthetic aperture radar and so forth [2, 8–12]. Bajwa et al. study some matrix elements that obey Bernoulli distribution system in the literature, and follow-up studies argue that the matrix element is bounded random matrix or distributed Gaussian random matrix; in this case, these matrices can meet RIP conditions of the 2k-sparse vector quantity on time domain [2, 10].

As the apple is one of China's most important fruit species, the refined management of apple's growing process is important to improve the yield, which means that the efficiency of apple image information system is of great importance. In this paper, we introduce the compressed sensing theory to the apple image acquisition process and improve both the speed and efficiency effectively. In the process of apple's growth, a lot of apples images need to be acquired and transferred to monitor the growth status of apple, pest control, and the robots movements. This paper researches on using Gaussian random matrices, Bernoulli random matrices, Partial Orthogonal random matrices, Partial Hadamard matrices, and Toeplitz matrix to measure the apple image. With the same quantity condition, we select the best construction matrix as the apple image measurement matrix. The apple image measurement matrix is applied to the apple's manufacturing operations process and overcomes the traditional method limit. It can reduce the cost of data acquisition and transmission. Thus it has very important practical significance.

The main contributions of this paper are as follows: we give the first trial to apply the image acquisition to the apple growing process. We use “sampling and compression” technology and obtain the compressed signal directly, and it can enormously reduce the time and store space demand of acquisition data. By conducting experiments on real life images, we figure out the best measurement matrix and demonstrate the effectiveness and efficiency of our methods.

2. Materials and Methods

2.1. Theory of Compressed Sensing

Compressed sensing can sample and compress signals at the same time. It can obtain the compressed signal directly, which includes three core problems: sparse representation of a signal, the measurement matrix, and the reconstruction algorithm [13]. The theoretical framework is shown in Figure 1.

Figure 1

Signal processing framework based on compressed sensing.

CS relies on two principles: sparsity and incoherence. During signal conversation process, signal is represented by several big coefficients and leave out the rest of the coefficient which is not distortion of the signal. The most practical signals (such as voice and video signal) can have sparse representation in some transform domain. A sparse representation of the signal is to change the original signal through a mathematical transformation, after which the signal is projected onto the orthogonal transformation basis. If most of the transform coefficients have an absolute value of zero, we call it a sparse signal after the transformation. If the value of most of the transform coefficients is small and few large coefficients can capture the main information about the object, we call it an approximation sparse signal.

$X = [X_{1}, X_{2}, X_{3}, \dots, X_{n}]$ is a one-dimensional discrete signal of length N which represents a sparse form of the original signal in a transform basis; that is,

\begin{matrix} X = Ψ α . \end{matrix}

(1)

In this expression, the coefficient $a_{i} = [x, ψ_{i}]$ ; the coefficient vector is $a = Ψ^{T} X$ ; the number of α's nonzero coefficients is k. The transfer matrix $Ψ = [ψ_{1}, ψ_{2}, ψ_{3}, \dots, ψ_{n}]$ is the basis of the orthogonal transformation. It is more flexible in choosing them according to the characteristics of the original signal. The typical frequently used sparse transformation bases are Fourier basis, DCT basis, wavelet basis (wavelet domain), and so forth.

After the sparse transformation of the original signal, it is different from the traditional Nyquist sampling theorem; compressed sensing samples a signal through designing the measurement matrix Φ. Φ can make high-dimensional signals projected onto a low-dimensional space to realize the compression of data. Finally, with the measurement vector in the low-dimensional projection domain, we can reconstruct the original signal nearly lossless as a linear equation. Consider

\begin{matrix} y = Φ X . \end{matrix}

(2)

In the formula above, y represents linear measurement of the sparse signal X, $y \in R^{M}$ is an M dimensional vector, and $X \in R^{N}$ is the unknown signal which needs to be reconstructed. Then, plugging (1) into (2),

\begin{matrix} y = Φ Ψ α . \end{matrix}

(3)

Φ is called the measurement matrix: $Φ \in R^{M \times N} (M ≪ N)$ ; M is the set of measurement times in the process of compressed sensing theory; and N is the length of the signal. Measured value of the unknown signal X under the measurement matrix Φ is y. The measured value y is the compressed representation of X.

The coherence between the measurement matrix Φ and the representation basis Ψ is

\begin{matrix} μ (Φ, Ψ) = \sqrt{x} \underset{1 \leq k, j \leq n}{m a x} |〈φ_{k}, ψ_{j}〉|, μ (Φ, Ψ) \in [1, \sqrt{n}] . \end{matrix}

(4)

The coherence measures the largest correlation between any two elements of Φ and Ψ which contain correlated elements [14]; the coherence μ is large. Otherwise, it is small.

Signal reconstruction refers to the process in which we get a sparse signal with length N or the original discrete signal X again [15] through obtaining the measurement vector y by M times. The measurement matrix and sparse transformation base satisfy the conditions of RIP or incoherence. We can reconstruct the original signal X accurately or approximate it precisely by solving the problem of optimal $L_{0}$ norm. X meets the type shown below:

\begin{matrix} X = a r g m i n {‖X‖}_{0} \\ s.t. y = Φ X . \end{matrix}

(5)

Solving the above equation is an NP-hard problem. Fortunately, prior work in compressed sensing has provided us with numerically feasible alternatives to this NP-hard problem. According to the theory of functional analysis and convex optimization, one major approach is that we can solve the $L_{0}$ problem approximately through the $L_{1}$ norm [16, 17].

Common reconstruction algorithms include the interior-point method [18], Gradient Projection for Sparse Reconstruction (GPSR) [19], Homotopy algorithm [20], MP algorithm [21], Basis Pursuit (BP) algorithm [22], and Orthogonal Matching Pursuit algorithm. The interior-point algorithm is slow but generates very precise reconstructions. GPRS exhibits rapid computational speed and reconstruction results are generally better. Homotopy algorithm is more practical for small-scale problems.

MP algorithm reconstruction is fast, but the reconstruction result is bad. BP algorithm suffers from slow reconstruction speed, but the results are better. OMP algorithm uses selection criteria in the matching pursuit. In the rebuild process, every iteration gets an atom that belongs to support set of F from x. By orthogonalization of the selected atoms collection, we ensure the optimality of the iteration and reduce the number of iterations. In this paper, we have chosen the OMP algorithm for apple image reconstruction.

2.2. Selection on Measurement Matrix

Another premise of compressed sensing theory is incoherence. Incoherence belongs to the sensor model. The measurement matrix Φ and sparse base Ψ are multiplied to calculate the sensing matrix. In order to reconstruct the sparse signal, Candes and Tao proved that Φ must satisfy the isometry property (RIP) conditions. For any K-sparse signal and constant, it satisfies

\begin{matrix} (1 - δ_{k}) {‖c‖}_{2}^{2} \leq {‖Φ_{T} c‖}_{2}^{2} \leq (1 + δ_{k}) {‖c‖}_{2}^{2}, \forall c \in R^{|T|} . \end{matrix}

(6)

$T \subset \{1, \dots, N\}, | T | \leq K$ ; $Φ_{T}$ is a child of the matrix composed of the related column indicated by the index T with the size of $K \times |T|$ . The matrix Φ then satisfies the restricted isometry property. The limited isometric property defines an important equidistant constant $δ_{k}$ ; it indicates that as long as $δ_{k}$ is not close to 1, it can approximately promise the Euclidean distance of the constant S-order sparse signal. This ensures the uniqueness of the reconstructed signal.

Designing the measurement matrix should satisfy the following conditions: transformation matrix should satisfy RIP conditions, or the measurement matrix and transformation matrix should meet incoherence. The previous researches prove that Gaussian random matrices, partial random Fourier matrix, Partial Hadamard matrix, Toeplitz matrix, Partial Orthogonal random matrices, Bernoulli random matrix, and so forth are feasible solutions. This paper selects the Gaussian random matrices, Bernoulli random matrices, Partial Orthogonal random matrices, Partial Hadamard matrices, and Toeplitz matrices on the apple image measurement.

(1) Gaussian Random Measurement Matrix. The probability density function of random variable X is

\begin{matrix} f (x) = \frac{1}{\sqrt{2 π} σ} e^{- {(x - μ)}^{2} / 2 σ^{2}}, - \infty < x < \infty, \end{matrix}

(7)

where μ,

σ (σ > 0)

are called parameters of normal distribution or Gaussian distribution. X is denoted by

X ~ N (μ, σ^{2})

. For Gaussian distribution, we have

E (X) = μ

, and

D (X) = σ^{2}

The elements $x_{i, j}$ of Gaussian random matrices Φ are independent random variables, which obey the Gaussian distribution with the mean of 0 and the square deviation of $1 / n$ , namely, $x_{i, j} ~ N (0, 1 / n)$ .

(2) Bernoulli Random Measurement Matrices. Bernoulli distribution is a discrete probability distribution; when the Bernoulli trial succeeds, it results in Bernoulli random variable as a value A. Otherwise, it results in Bernoulli random variable as non-A. Bernoulli random matrices are the elements of the matrix Φ with the same probability with $1 / \sqrt{n}$ or $- 1 / \sqrt{n}$ .

(3) Partial Orthogonal Random Matrices. If N order square A meets $A^{T} A = E$ , A is called orthogonal matrix; the sufficient and necessary conditions of the N order square matrix A are the fact that A column vector is standard orthogonal vector group.

The method of constructing Partial Orthogonal measurement is illustrated as follows. We first generate $N * N$ dimension orthogonal matrix T, and then we randomly select M rows from T, construct the $M * N$ matrix, and then unite the N columns to get the measurement matrix.

(4) Partial Hadamard Matrices. Hadamard matrix is orthogonal square matrix composed by elements of +1 and 1. The method of constructing Partial Hadamard matrix is illustrated as follows. We first generate Hadamard matrix $N * N$ , and then we, from the generated matrix, randomly select M row vector and generate $M * N$ Hadamard random measurement matrix.

(5) Toeplitz Matrix. Toeplitz matrix is also known as diagonal-constant matrix, elements of line parallel to main diagonal line are the same. The method of constructing Toeplitz random measurement is illustrated as follows. First, we generate a random vector and then the random vector with related functions to generate the corresponding Toeplitz matrices; second, we select the first M rows of the Toeplitz constructed as $M * N$ Toeplitz random measurement matrix.

3. Results and Discussion

This paper chooses an apple image represented by $256 * 256$ RGB pixels. We use sym5 wavelet bases to represent the original apple image sparsely with random Gaussian measurement matrix ( $X ~ N (μ, σ^{2})$ ), Bernoulli random matrices ( $X ~ B (n, p)$ ), Partial Orthogonal random matrices, and Partial Hadamard matrices, and Toeplitz matrices are then used for observational measuring of the signal. Finally, the apple image is reconstructed by the OMP algorithm. The reconstructed PSNR values and runtime were used to compare and contrast the simulation results. The quality of the 5 reconstructed apple images is measured using PSNR. Figures 2–5 show time and PSNR scatter diagrams for 5 different measurement matrices used to reconstruct the apple image when the sampling point M takes different values.

Figure 2

Reconstruction time and PSNR values of 5 different measurement matrices with $M = 150$ .

Figure 3

Reconstruction time and PSNR values of 5 different measurement matrices with $M = 160$ .

Figure 4

Reconstruction time and PSNR values of 5 different measurement matrices with $M = 170$ .

Figure 5

Reconstruction time and PSNR values of 5 different measurement matrices with $M = 180$ .

In this experiment, we vary the number of sampling pixels, for example, $M = 150$ , $M = 160$ , $M = 170$ , $M = 180$ , use sym5 wavelet base as sparse transformation base, sample with five different measurement matrices and reconstruct images through OMP algorithm. The experiment verified that the colorized apple image constructed by the partial orthogonal random matrices with a sym5 wavelet base had a higher quality.

Figures 6–9 compare the restored apple image by the CS reconstruction algorithm with the Toeplitz matrix and the Orthogonal matrix with the original apple image when the sampling point M assumes different values.

Figure 6

Original image, Toeplitz matrix reconstruction image and partial orthogonal matrix reconstruction image with $M = 150$ .

Figure 7

Original image, Toeplitz matrix reconstruction image and partial orthogonal matrix reconstruction image with $M = 160$ .

Figure 8

Original image, Toeplitz matrix reconstruction image and partial orthogonal matrix reconstruction image with $M = 170$ .

Figure 9

Original image, Toeplitz matrix reconstruction image and partial orthogonal matrix reconstruction image with $M = 180$ .

The above results show the reconstruction precision of the Orthogonal measurement matrix and the Toeplitz measurement matrix. Under the condition of same sampling points, the quality of reconstruction image with the Orthogonal measurement matrix is much better than that of the reconstruction image with Toeplitz measurement matrix.

In this paper, we choose the sampling points from 150 to 180. If we use too many points, that is, more than 180 points, the significance of using sampling methods is minimized. While if we use too few points, that is, less than 150 points, the effectiveness of our methods decline. Hence, between the tradeoff of effectiveness and complexity, we choose the sampling points from 150 and 180.

Since PSNR is mostly commonly used to measure the quality of reconstruction images, we choose the PSNR score as measurement metric. SSIM is also a quality reconstruction metric, but it is more complicated to compute for which the formula involves a value for each pixel. We conduct experiments using SSIM metric and it demonstrates the superiority of our method, but it takes too much space in the paper; we do not list the details of the SSIM results.

4. Conclusion

This paper uses sym5 wavelet base as apple image sparse transformation base, and then it uses Gaussian random matrices, Bernoulli random matrices, Partial Orthogonal random matrices, Partial Hadamard matrices, and Toeplitz matrices to measure apple image, respectively. Using the same measure quantity, we select the matrix that has best reconstruction effect as the apple image measurement matrix. According to the experiment results, this paper selects Partial Orthogonal random matrices as apple image measurement matrix. This measurement matrix is used for the data processing of apple image; it can better realize image data compression and greatly reduced apple image sampling and transport cost, which has important application significance in the process of apple production operation.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The authors would like to thank Wanlin Gao for helpful comments and pointers. This work was supported by National Key Technology R&D Program of China during the 12th Five-Year Plan Period (Grant no.: 2012BAD35B02).

References

Rauhut

Circulant and Toeplitz matrices in compressed sensing

http://arxiv.org/abs/0902.4394

Haupt

Bajwa

W. U.

Raz

Nowak

Toeplitz compressed sensing matrices with applications to sparse channel estimation

IEEE Transactions on Information Theory 2010 56 11 5862 5875

10.1109/tit.2010.2070191

MR2808938

2-s2.0-77956563404

Romberg

Compressive sensing by random convolution

SIAM Journal on Imaging Sciences 2009 2 4 1098 1128

10.1137/08072975x

MR2559161

Sanandaji

B. M.

Vincent

T. L.

Wakin

M. B.

Concentration of measure inequalities for compressive Toeplitz matrices with applications to detection and system identification

Proceedings of the 49th IEEE Conference on Decision and Control (CDC ′10)

December 2010

2922 2929

10.1109/cdc.2010.5717107

2-s2.0-79953134952

Park

J. Y.

Yap

H. L.

Rozell

C. J.

Wakin

M. B.

Concentration of measure for block diagonal matrices with applications to compressive signal processing

IEEE Transactions on Signal Processing 2011 59 12 5859 5875

10.1109/TSP.2011.2166546

MR2907885

2-s2.0-81455136681

Wakin

M. B.

Sanandaji

B. M.

Vincent

T. L.

On the observability of linear systems from random, compressive measurements

Proceedings of the 49th IEEE Conference on Decision and Control (CDC ′10)

December 2010

4447 4454

10.1109/cdc.2010.5718068

2-s2.0-79953146495

Duarte

M. F.

Davenport

M. A.

Takhar

Laska

Sun

Kelly

K. F.

Baraniuk

R. G.

Single-Pixel imaging via compressive sampling

IEEE Signal Processing Magazine 2008 25 2 83 91

10.1109/msp.2007.914730

Rauhut

Circulant and Toeplitz matrices in compressed sensing

Proceedings of the Signal Processing with Adaptive Sparse Structured Representations (SPARS ′09)

April 2009

Saint Malo, France

Romberg

Compressive sensing by random convolution

SIAM Journal on Imaging Sciences 2009 2 4 1098 1128

10.1137/08072975X

MR2559161

ZBL1176.94017

10.

Bajwa

W. U.

Haupt

Raz

Nowak

Compressed channel sensing

Proceedings of the 42nd Annual Conference on Information Sciences and Systems (CISS ′08)

March 2008

5 10

10.1109/ciss.2008.4558485

2-s2.0-51849127524

11.

Tropp

J. A.

Wakin

M. B.

Duarte

M. F.

Baron

Baraniuk

R. G.

Random filters for compressive sampling and reconstruction

Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP ′06)

May 2006

872 875

2-s2.0-33947632909

12.

Bajwa

W. U.

Haupt

J. D.

Raz

G. M.

Wright

S. J.

Nowak

R. D.

Toeplitz-structured compressed sensing matrices

Proceedings of the IEEE/SP 14th Workshop on Statistical Signal Processing (SSP ′07)

August 2007

Madison, Wis, USA

IEEE

294 298

10.1109/ssp.2007.4301266

2-s2.0-41949102240

13.

Tropp

J. A.

Gilbert

A. C.

Signal recovery from random measurements via orthogonal matching pursuit

IEEE Transactions on Information Theory 2007 53 12 4655 4666

10.1109/tit.2007.909108

MR2446929

2-s2.0-64649083745

14.

Candès

E. J.

Wakin

M. B.

An introduction to compressive sampling

IEEE Signal Processing Magazine 2008 25 2 21 30

10.1109/MSP.2007.914731

15.

Gao

Voice signal compression and reconstruction method based on the theory of the compressive sensing

Proceedings of the 11th National Conference on Man-Machine Voice Communication

2011

16.

Drori

Donoho

D. L.

Solution of l₁ minimization problems by LARS/homotopy methods

Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP ′06)

May 2006

Toulouse, France

IEEE

10.1109/ICASSP.2006.1660734

2-s2.0-33947646302

17.

Garrigues

P. J.

Ghaoui

L. E.

An homotopy algorithm for Lasso with online observations

Proceedings of the Annual Conference on Neural Information Processing Systems

December 2008

Vancouver, Canada

18.

Kim

S.-J.

Koh

Lustig

Boyd

Gorinevsky

An interior-point method for large-scale

l_{1}

-regularized least squares

IEEE Journal of Selected Topics in Signal Processing 2007 1 4 606 617

10.1109/JSTSP.2007.910971

19.

Figueiredo

M. A. T.

Nowak

R. D.

Wright

S. J.

Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems

IEEE Journal on Selected Topics in Signal Processing 2007 1 4 586 598

10.1109/jstsp.2007.910281

2-s2.0-39449126969

20.

Donoho

D. L.

Tsaig

Fast solution of

l_{1}

-norm minimization problems when the solution may be sparse

2008

Stanford, Calif, USA

Department of Statistics, Stanford University

21.

T. T.

Gan

Nguyen

Tran

T. D.

Sparsity adaptive matching pursuit algorithm for practical compressed sensing

Proceedings of the 42nd Asilomar Conference on Signals, Systems and Computers

October 2008

Pacific Grove, Calif, USA

581 587

10.1109/acssc.2008.5074472

2-s2.0-70349694266

22.

Chen

S. S.

Donoho

D. L.

Saunders

M. A.

Atomic decomposition by basis pursuit

SIAM Journal on Scientific Computing 1998 20 1 33 61

10.1137/s1064827596304010

MR1639094

2-s2.0-0032131292