Efficient Image Transmission over WVSNs Using Two-Measurement Matrix Based CS with Enhanced OMP

Abstract

WVSN is a collective network of motes containing visual sensors. The nodes in the network are capable of acquiring, compressing, and transmitting successive images to the sink. To increase the lifetime of such network, it is essential to reduce the amount of dataflow across the network without losing the integrity. This paper proposes a CS-based image transmission system to reduce the number of measurements required to represent the image. It utilizes a two-measurement matrix-based CS. TMM with CS leads to 2.8% to 6.7% and 0.67% to 7.9% reduction in the number of measurements compared to one MM-based CS while using DCT and binary DCT, respectively. Similarly, TMM with NUS CS leads to 5% to 40% (DCT) and 1.4% to 20% (binDCT) reduction in the number of measurements than one-measurement matrix-based NUS CS. An Enhanced Orthogonal Matching Pursuit algorithm is also proposed, which produces nearly 2% to 26% better recovery rate with the same number of measurements than the conventional OMP algorithm. Reduced measurements and better recovery rate achieved will enhance the lifetime of the WVSN, with considerable image quality. Rate distortion analysis of the proposed methodology is also done.

1. Introduction

WVSNs are networks of wirelessly interconnected devices equipped with camera, enabling the retrieval of video and audio streams, still images, and scalar sensor data. They have tiny visual sensor nodes called camera nodes as shown in Figure 1, which integrate the image sensor, embedded processor, and wireless transceiver [1]. WVSNs have large volume of data to be processed and stored which increases the complexity of the system. With the advancement in the image sensor technology, WVSNs can be used for more complex multimedia applications like border surveillance using visual monitoring, tracking rare animal species, controlling the vehicle traffic on highways, and railways and environmental monitoring [1–3]. However, they are energized by small batteries with a short span of lifetime. Replacing or recharging of the battery is also extremely difficult. With reduced lifetime of the batteries image transfer application in WVSNs has the limitations such as reduced bandwidth, reduced on board memory, and limited computational capability. Hence, it is essential to aim at diminishing the amount of data to be processed and the level of computations involved.

Figure 1

Visual sensor network architecture [1].

WVSNs are in need of a compression process with acceptable compression rate, low computational complexity, low power consumption, and low dynamic memory usage to reduce the number of bits used for representing the image, which will also reduce the communication cost of the bits to be sent to the destination. Conventional image compression algorithms convert high-resolution images into a relatively small bit streams, in effect converting a large digital data set into a substantially smaller one. Eventually, data compression can be built directly into the acquisition process using CS. CS is used to recover a sparse signal from a less number of linear measurements. An image which is compressible in some basis can also be reconstructed perfectly from a small number of linear measurements [4].

The three inherent inefficiencies of traditional image compression techniques are as follows:

(i)

initial number of samples “p” may be large even if the desired number of samples “b” is small;

(ii)

set of all “p” transform coefficients must be computed even though we need only “b” of them;

(iii)

locations of the “b” transform coefficients must be encoded.

CS overcomes these inefficiencies by directly acquiring a compressed signal representation without going through the intermediate stage of acquiring “p” samples [4, 5].

Consider a real valued, finite length, one-dimensional signal $X \in R^{N}$ . Using the $N \times N$ basis matrix $ψ = [ψ_{1} | ψ_{2} | \dots | ψ_{N}]$ with the vectors ${ψ_{i}}$ as columns, a signal X can be expressed as

\begin{matrix} X = \sum_{i = 1}^{N} S_{i} ψ_{i} = ψ S, \end{matrix}

(1)

where X is $N \times 1$ column vector with coefficients $X_{i}$ , $i = 1,2 \dots N$ and S is vector of coefficients representing X in ψ basis. The process of measurement in CS [5] can be defined as

\begin{matrix} y = ϕ X = ϕ ψ S = Θ S, \end{matrix}

(2)

where ϕ is an $M \times N$ random matrix, $Θ = ϕ ψ$ , X is a $N \times 1$ sparse coefficient input vector, and y is a $M \times 1$ measurement vector. It is assumed that $M < N$ . The number of measurements depends upon the sparsity and incoherence [6, 7]. Low coherence between measurement basis ϕ and representation basis ψ results in a less number of measurements. The number of measurements M, for perfect reconstruction of a z-sparse N-dimension signal [6] is given by

\begin{matrix} M \geq α \cdot z \cdot \log (\frac{N}{z}), \end{matrix}

(3)

where α is some positive constant affecting the probability of recovery. Signal X could be recovered exactly by solving the minimum l1-norm optimization problem. The reconstruction process is formulated as

\begin{matrix} \hat{S} = \min_{S} {∥ S ∥}_{ℓ_{1}} subject to y = Θ S, X = ψ \hat{S} . \end{matrix}

(4)

This methodology can be made in-built during the acquisition process itself. Hardware realization is available in [8]. Since it is still in research, CS-based compression is proposed expecting the availability of hardware in the near future. The whole image is taken as the input and analysed how better it could have been captured with CS as in [5].

CS requires the choice of the measurement matrix (MM), recovery algorithm, and the sparsity basis. It reduces the data in hand on the initial stage itself, which will surely reduce the computational complexity and storage requirement burdens evolving in the WVSNs scenario. This motivated us to propose a scheme combining the CS and WVSNs to get better efficiency for the image transmission applications. The proposed scheme provides better recovery rate and acceptable image quality with much reduced number of measurements.

The rest of the paper is organized as follows. Section 2 provides the brief review of the related work. Section 3 discusses the system model that is proposed in detail. Section 4 presents the performance evaluation based on the number of measurements, percentage of recovery, Peak Signal to Noise Ratio (PSNR), and Bpp, and Section 5 gives the conclusion.

2. Related Work

Romberg [5] proposed a compressive imaging technique using both DCT and Noiselet coefficients. The algorithm is applied for the entire image; the measurement includes the DCT elements taken after zigzag ordering used in JPEG and random Noiselet measurements. It provides better image quality, but the random locations of the Noiselet coefficients have to be conveyed to the receiving end for proper recovery. The recovery is done using optimization technique by reducing the total variation. It is time consuming and very complex.

Sermwuthisarn et al. [9] divided the image into blocks and used Haar wavelets as sparse basis. The measurements are taken using Noiselet MM. Though the block based processing provides low memory and low-computing time, the sparsity varies from block to block so the MM size also changes. So, the details of the MM have to be sent along with the measurements which will also increase the energy consumption in case of WVSNs. Tsaig and Donoho [10] explored that CS can be applied in a different way in image recovery. CS is applied to measure only fine scale properties of the signal, while ordinary linear measurement and reconstruction were used to obtain the coarse-scale properties of the signal. It provided better image quality.

Zhou et al. [11] proposed NUS of CS. The image is divided into blocks, DCT transformed, zigzag ordered, and then classified as important and nonimportant coefficients. Important coefficients are transmitted as such and the CS measurements are taken over the nonimportant coefficients. Though it provides better quality with reduced measurements, it has increased complexity and MM changes from block to block further increasing the burden. Alternatively, a methodology using TMM by identifying the blocks to be low-frequency content block or high-frequency content block based on the number of nonzero elements is proposed. This is the extended version of the one proposed in [12] and is utilized in both CS and NUS measurement strategies, enabling efficient implementation in WVSNs. The measurements are taken using binDCT also, which reduces the energy consumption of the entire process, whereas in [12], only DCT is used. EOMP recovery algorithm is used in this paper to get better recovery rate while in [12] OMP is used. This reduces the number of measurements and the complexity.

CS enables the recovery of the sparse signals from a relatively small number of linear measurements. This requires the incoherent nature of the MM with the sparsity basis. There are many existing contributions that model and propose the MM generation. Candès et al. [6] used Gaussian random matrix which has inherent restricted Isometry property. Candès and Romberg [7] utilized the nonbinary orthogonal transform matrices as MM. They have fast transform algorithms, for example, Scrambled Fourier (SF) matrix. But these matrices have non binary element, which is a major drawback, hence the hardware implementation will be difficult in these cases and multiplication is done to take the measurements. Multiplications in the on-board processors of the mote will consume much energy. Sparse matrices generated from block diagonal matrices, Scrambled Block Hadamard (SBH) [13], and Binary measurement matrices [13, 14] are available in the literature, but they are computationally complex to be implemented in WVSNs. As an alternative, we have taken a binary sparse matrix with uniform distribution. Hence, the measurement process involves only additions.

Recovering the sparse signals from reduced number of measurements is an NP-hard problem. The two major algorithmic approaches to sparse recovery are based on L1-minimization and iterative methods (Matching Pursuits). The optimization techniques use either convex or linear programming to solve the L1 problem in it. But their implementation is very much time consuming and very complex [15]. The greedy algorithms use the correlation between the signal and the columns of the MM as a measure to find the elements with nonzero coefficients. There are several such algorithms [16–22] in the literature. In this paper, we concentrated on the matching pursuit algorithms due to its simple and fast implementation. Tropp and Gilbert [16] proposed the OMP algorithm in which the sparse signal is recovered by choosing a strong correlated column of the MM in each iteration and the contribution of chosen column is subtracted from the measurements. The original signal is recovered after z (sparsity level) number of iterations. Its advantage is fastness and transparency. But OMP has weaker guarantees of exact recovery. Needell and Vershynin [17] suggested ROMP, where z biggest columns of the MM are chosen and are regularized with the maximal energy concept. It terminates in at most $2 z$ iterations. The disadvantage is that finding the least squares solution in each iteration is tedious with more number of columns being included in the support set. Baby and Pillai [22] proposed ordered OMP, an improvement to OMP. The wrongly detected columns in the support set are removed by comparing the projection coefficients and are scaled down to avoid the reentry. It achieves exact recovery at a smaller number of measurements when compared to OMP. Our work is to decrease the number of measurements for exact recovery with reduced complexity. Hence, we propose the EOMP algorithm for recovery with two column entries into the support set in each iteration, with wrong column detection and its suppression. The elements of the support set are checked to get rid of duplications in the successive iterations. It provides exact recovery at very lesser measurements. The performance of the proposed algorithm is evaluated and compared with the OMP [16], ROMP [17], and OOMP [22].

Haupt et al. [23] have done a decentralized compression of networked data using CS. Yu et al. [24] have used CS to remove the redundancy in spatially neighbouring measurements, in the Vehicular Sensor Network (VSN). CS provides accurate reconstruction and less communication load for surveillance and urban monitoring applications. Mamaghanian et al. [25] have utilized CS for low-complexity energy-efficient ECG compression. The lifetime of the network is increased in all CS-based WSN applications [23–25].

Hence, this paper proposes an image transmission methodology using CS in WVSNs to prolong its lifetime. BinDCT [26, 27] is suggested for the transformation of the image in NUS strategy (hybrid CS). This will reduce the power consumption of the on board processor in the WSN mote. Measurements are taken using TMM procedure with binary valued MM to reduce the number of measurements required for the recovery of an image with acceptable quality. Encoding is done using the JPEG Huffman table. Reconstruction algorithm is improved to provide better performance. It gives exact recovery at very much less number of measurements. This reduces the number of measurements transmitted from the source to the destination. This paper mainly aims at the reduction of the number of measurements and to provide better recovery rate. This will increase the lifetime of the network, the foremost requirement in the real time applications.

3. Proposed System Model

The proposed CS-based compression algorithm for the WVSN is shown in Figure 2. The processes shown in the transmitter section will take part in the visual sensor nodes and the recovery as in the receiver section will be done at the powerful information collecting node called sink.

Figure 2

Proposed system model.

The captured input image is divided into a block of size $s \times s$ and spatially transformed using binDCT. DCT is chosen since it has high energy compaction property. Block size is chosen as $s = 8$ , so that it reduces the blocking artefacts and blurring effect in the reproduced image. It also considerably reduces the memory requirement for MM storage essential to take the CS measurements. The measurement matrix size is $M \times 64 (M \times s^{2})$ . The further increase in the block size will drastically increase the size of MM and its storage requirement. Hence, we fixed the block size to be 8.

Binary DCT is applied on the blocks to get the transformed image and to sparsify the image in NUS strategy. The conventional floating point method of computing DCT is very exhaustive. The floating point method computes the DCT using multiplications and additions. The energy consumed for multiplications is generally high when compared to additions or shifting operations. As we have a limited power supply at the source node, it is important to utilize it effectively. On this regard, we use the concept of binDCT to replace the floating point DCT. Using binDCT, the forward and the inverse transforms are implemented using only binary shift and addition operations. The energy consumed via this method would be far less than the conventional method. There are several families of such multiplierless binDCT computations. The configuration employed in this work is that of C1-Chen's factorization [26]. Comparison of the operations involved in the conventional method and binDCT method is listed in Table 1.

Table 1

Comparison of DCT methods used for 8 × 8 matrix.

Type	No. of multiplications	No. of additions	No. of shifts
Floating Point DCT	1024	896	—
Integer DCT Chen-C1	—	672	368

The transformed image is converted into a column vector (x). To sparsify “x”, only D% of “x” is kept and other elements are made to be zero. Choice of the D is made based on the quality requirement of the reconstructed image. The measurement procedure is described in detail in Section 3. The measurements are encoded using the conventional JPEG Huffman table [28]. The coded data is transmitted to the sink. At the sink, the received data is decoded and then the recovery is done through the proposed EOMP algorithm briefed in Section 4. It enables the reconstruction of the image with much reduced measurements compared to the conventional algorithms [7, 16, 22]. The reconstructed column vector is converted into a matrix of size 8 × 8 and inverse binDCT is applied. Then, the blocks are arranged properly to get back the reconstructed image. The procedure is also repeated with DCT transformation. Here, two-level compression is done to get better compression rate as follows.

(i)

The required measurements to represent the image are reduced by CS.

(ii)

The redundancy in the measurements is removed by encoding it using the standard JPEG Huffman table.

The entire process is formulated to reduce the computational complexity, the amount of data to be processed and transmitted, and the storage requirements (memory). The main reduction in the processing data is achieved due to the CS-based TMM techniques and EOMP algorithm.

3.1. Two-Measurement Matrix-Based CS

When an image is divided into blocks of small size, the frequency component in each block will not be the same. A block with smooth variations in the gray level contains only few large amplitude DCT coefficients. It is called as the low frequency component of the image. A block with sharp variations in the gray level contains more large amplitude DCT coefficients. It is called as the high frequency component of the image. This is shown in the cameraman image in Figure 3. The block 1 is one of the low frequency content blocks and it has only one large amplitude DCT coefficient. The block 2 is one of the high frequency content blocks and it has approximately 28 large amplitude DCT coefficients.

Figure 3

Example of low-frequency and high-frequency blocks.

If same-sized MM is used to measure both low-and high-frequency content blocks, it results in a large number of measurements. The proposed method uses two measurement matrices with different sizes. The MM with large number of rows is used to measure the high frequency content blocks and the MM with less number of rows is used to measure the low frequency content blocks, thereby reducing the total number of measurements. Based on the application (e.g., object detection) the number of measurements can be further reduced by sacrificing the quality of the image. In WVSNs, bandwidth is a constraint, which is solved by the proposed method, which produces less number of measurements. The procedure for the TMM allocation is summarised in Algorithm 1. This variation leads to reduction in measurements since the nature of the image is exploited to take measurements.

Algorithm 1

For each block in a image

(1) Convert to a column vector x of size $64 \times 1$ .

(2) Quantize: $x_{q} = x / 2^{n}$ , $n = 1,2, 3 \dots$

(3) Find the number of nonzero elements $N_{nz}$

(4) Compare $N_{nz}$ with a pre-fixed threshold (T) and set the

sparsity level

SL = $\begin{matrix} S_{h} if N_{nz} > T \\ S_{l} if N_{nz} < T \end{matrix}$

(5) Sparsify $x_{q}$ to have SL nonzero elements.

(6) Generate $ϕ$ (MM) of size $(SL \cdot \log (64)) \times 64$

(7) Take linear measurements, $y = ϕ x_{q}$

3.2. Two-Measurement Matrix-Based Nonuniform Sampling CS

In nonuniform sampling-based CS, transformed coefficients in each block are separated into important and unimportant component [11]. Important components are the first few elements taken after zigzag ordering the block. They are transmitted as such, whereas the remaining unimportant components undergo CS measurement. If same measurement matrix is used to measure the unimportant component of all blocks of an image (i.e., the unimportant component of low-frequency content blocks and high-frequency content blocks are weighted equally), it results in a large number of measurements. The proposed method uses two measurement matrices in nonuniform sampling-based CS as shown in Figure 4.

Figure 4

Flow chart of the proposed two measurement matrix-based nonuniform sampling CS.

The measurement matrix with large number of rows is used to measure the unimportant component of high frequency content blocks ( $ϕ_{1}$ ) and the measurement matrix with less number of rows is used to measure the unimportant component of low frequency content blocks ( $ϕ_{2}$ ), thereby reducing the total number of measurements. The size of important component of all blocks is kept as constant.

The important component is transmitted to the receiver directly along with CS measurements of unimportant component. The measurement matrices are assumed to be known to the transmitter and receiver. One extra bit (side information) per block is transmitted to inform the receiver which measurement matrix is being used for that block. The unimportant component is estimated at the receiver by using EOMP algorithm. Then important component is concatenated with it. Then, the resultant single column vector is rezigzag ordered to form a matrix. Then, inverse transformation is applied to this matrix to get the estimated block. These blocks are rearranged to form the estimated image. Both DCT and binDCT transforms are applied for analysis.

3.3. Recovery Enhanced OMP

The proposed recovery algorithm is a modification of the OMP [16]. Though there are several recovery algorithms [18–21], OMP is very popular due to its low computation cost and its ease of implementation. The main idea of the OMP is to pick the highly correlated column with the received signal. The index of the same is also accumulated in a counter $Λ$ consecutively. Signal estimate is found using the least squares solution with the available column set. The contribution of the support set is removed from the residue to maintain orthogonality between the residual and the support set. Hence, the algorithm discovers new column in each iteration. This column usually corresponds to the largest coefficient of the sparse signal. But at some instances, OMP fails to pick up the correlated columns correctly. So, it needs more measurements to ensure exact recovery. Algorithm 2 explains the procedure involved in OMP.

Algorithm 2: OMP [16].

Input:

(i) An $M \times N$ measurement matrix $ϕ$ .

(ii) An M-dimensional measurement vector y.

(iii) The sparsity level z of the ideal signal.

Procedure:

Step 1. $r_{0} = y$ , $Λ_{0} = 0$ and the iteration counter $t = 1$ .

Step 2. Find the index $λ_{t}$ that solves the easy optimization

problem.

$λ_{t} = {arg max}_{j = 1,2 \dots N} | 〈 r_{t - 1}, φ_{j} 〉 |$

Step 3. Augment the index set $Λ_{t} = Λ_{t - 1} \cup {λ_{t}}$ and

the matrix of chosen atoms. $ϕ_{t} = [ϕ_{t - 1} φ_{λ_{t}} ⌋$

Step 4. Solve the least-square problem to obtain a new signal

estimate.

$g_{t} = {arg min}_{g} {∥ ϕ_{t} g - y ∥}_{2}$

Step 5. Calculate the new approximation of the data and the

new residual.

$a_{t} = ϕ_{t} g_{t}$ , $r_{t} = y - a_{t}$

Step 6. Increment t and return to Step 2 if $t < z$ .

Step 7. The estimate $\hat{X}$ for the ideal signal has non-zero

indices at the components listed in $Λ_{z}$ . The value of the

estimate $\hat{X}$ in component $λ_{j}$ equals the jth component of $g_{t}$ .

In this paper, the falsely selected columns are identified in each iteration and are removed from the support set. The approximation coefficients as in step 4 can also be found by $g_{t} = {(ϕ_{t}^{T} ϕ_{t})}^{- 1} ϕ_{t}^{T} y$ . It is the projection of y on to the subspace spanned by the columns in $ϕ_{t}$ . The projection coefficients are used to check whether a column in the present support set is falsely detected or not. To check the false detection, two parameters are included as follows:

(i)

acceptance range, $ε < 1$ ,

(ii)

suppression factor, $α < 1$ .

In every iteration, EOMP compares the projection coefficients with that obtained in the previous iteration. A column in the present support set is declared as wrongly detected if its present projection coefficient falls below ε times, its value in the previous iteration. If any column fails this test, that is, if its coefficient gets smaller, then that column will be removed from the support set. Furthermore, that column is scaled down by α so that the column is given less importance in the coming iterations. Algorithm 3 explains the EOMP algorithm.

Algorithm 3: EOMP.

Input:

(i) An $M \times N$ measurement matrix ϕ

(ii) An M-dimensional measurement vector y

(iii) The sparsity level z of the ideal signal and the sparsity basis.

(iv) Acceptance Range, $ε$ and suppression factor, $α$

Procedure:

Step 1. Find $λ_{1} = {arg max}_{j = 1,2, . ., N} | 〈 y, φ_{j} 〉 |$ , $Λ_{1} = {λ_{1}}$ , $π = ⌊ φ_{λ_{_{1}}} ⌋$ , $g_{1} = {(π_{t}^{T} π_{t})}^{- 1} π_{t}^{T} y$ , residual,

$r_{1} = y - π g_{1}$

Step 2. iteration counter $t = 2$ , $k = 1$ . Set values for $ε$ and $α$ .

While $k \leq z$ , do

Step 3. Find $| 〈 r_{t - 1}, φ_{j} 〉 | j = 1,2, \dots, N$ . Take two maximum correlated indexes $λ_{t} = {λ_{h 1} λ_{h 2}}$

Step 4. Augment the index set $Λ_{t} = Λ_{t - 1} \cup {λ_{t}}$ and the sub-matrix of chosen atoms $ϕ_{t} = [ϕ_{t - 1} φ_{λ_{t}} ⌋$

where $ϕ_{0}$ is an empty matrix. /Two element entry/

Step 5. If there is any duplications in the index set, remove it by emptying the corresponding index.

Remove the atom in the sub-matrix also. /Duplication removal/

Step 6. Find a new signal estimate: $g_{t} = {arg min}_{g} {∥ ϕ_{t} g - y ∥}_{2}$

Step 7. For $i = 1,2, \dots, z$ , if $| g_{t} (t - i) | \leq ε | g_{t - 1} (t - i) |$ for some $i = j$ , then /Wrong index detect /

(a) $Λ_{t} = Λ_{t} - {Λ_{t} (j)}$ , $ϕ_{t} = ϕ_{t} - {ϕ_{t} (j)}$ , /Wrong index removal/

(b) $g_{t} = {arg min}_{g} {∥ ϕ_{t} g - y ∥}_{2}$ /Residue updating/

Step 8. Update the residue vector: $a_{t} = ϕ_{t} g_{t}$ , $r_{t} = y - a_{t}$

Step 9. Increment t, k and end while

In the proposed algorithm after calculating the first estimate, two highly correlated columns are included in the index set. If there is any duplication, it will be removed. Then, the current estimate is compared with the previous estimate, if it is up to the expected significant level, then the column identification is correct, if not the columns are taken as false identifications. The false columns will be removed from the submatrix, their contribution is subtracted from the residual. They are also suppressed by a factor of α. The algorithm tries to find the best approximation for the estimated input vector rather than relying on the highly correlated values.

Acceptance range (ε): it is used to find the wrongly detected columns, as their entry will reduce the projection coefficient values. If the current estimate value is less than ε times the previous estimate at one or more locations, then those entries are assumed to be wrong and are removed from the support set.

Suppression factor (α): this factor is used to suppress the wrongly detected columns from again entering into the support set. It enables easy convergence towards the correct support set.

To get better result, the accurate choice of the above mentioned factors is essential. It depends on the sparsity and size of the input vector. The values adopted for the image transmission are explained in Section 4.

4. Performance Evaluation

The proposed CS-based image transmission is implemented using EOMP algorithm and TMM technique. Performance metrics like percentage of recovery and PSNR are calculated and compared with OMP, ROMP, and OOMP. The proposed EOMP has better performance with the same level of complexity. The entire transmission algorithm is compared with the single measurement matrix method using OMP. The proposed technique requires less number of measurements to ensure the same level of PSNR than the existing one. The entire simulation is done using Matlab (R2011a). The data set $D (z, M, N)$ , having an ensemble of random matrices ϕ of size $M \times N$ and an ensemble of z sparse vectors is considered. The length of the data vector (N) is fixed as 64, since the block size of 8 is chosen in the processing of the image. Sparsity and the measurements are varied and the results are analysed.

4.1. Recovery Enhanced OMP

The working of the EOMP mainly depends on the choice of the parameters ε and α. The effect of suppression factor is analyzed first. Sparsity is fixed as 4 and acceptable range ε is taken as 0.5 and the α value is changed from 0.05 to 0.95; the corresponding percentage of recovery is plotted in Figure 5. For each value of α the number of measurements is varied from 0 to 64. Percentage of recovery is averaged over 1024 independent trials of the data set $D (z, M, N)$ . From Figure 5, it is evident that variation in α did not affect the percentage of recovery. The change is less than 1% for all the cases; hence, all the curves are overlapped. So, α value can be chosen independently from the range 0.05 to 0.95 as it has not much influence on the percentage of recovery.

Figure 5

Percentage of recovery for α varied from 0.05 to 0.95 with $z = 4$ , $ε = 0.5$ , $N = 64$ .

The percentage of success for a fixed measurement remains almost the same for the entire range of variation of the α and hence α can have any value between 0.05 and 0.95 as shown in Figure 6. The same is checked for different sparsity levels also.

Figure 6

98% of recovery for α variation from 0.05 to 0.95 with $N = 64$ .

The effect of the acceptance range is studied with $α = 0.7$ , $N = 64$ and the sparsity takes the following values $z = 2$ , 6, 10. The acceptance range is varied from 0.05 to 0.95 for all the individual cases. The percentage of recovery is calculated and is averaged over 1024 independent trials and is shown in Figure 7. The black, red, brown, green, and magenta curves correspond to $ε = 0.75$ , 0.8, 0.85, 0.9, and 0.95, respectively. For $ε = 0.05$ to 0.7, the curve is plotted in blue color. In Figure 7(a), the response for $ε = 0.05$ to 0.7 does not have much variation in terms of the percentage of recovery. So, the lines get overlapped and are visible as a single line, whereas the percentage recovery starts decreasing when the ε value is increased beyond 0.7. With the increase in ε, the checking limit for the column to be identified as wrong detection is tightened. Hence, correct columns can also be identified as the wrongly detected ones, this leads to the performance degradation for the values of $ε > 0.7$ . This holds good for the varying values of the sparsity also, which is shown in Figures 7(b) and 7(c).

Figure 7

Percentage of recovery of EOMP for ε varying from 0.05 to 0.95.

In all the cases, system becomes unstable or has degraded performance for $ε > 0.7$ . Hence, we omitted the range above 0.7 for ε. In the range of 0.05 to 0.65, any value can be chosen since there is no drastic degradation in the performance when $z = 2$ , but when sparsity increases, $ε = 0.65$ and 0.6 has nearly 2 to 4% reduction in the percentage of recovery. Hence, we suggest the value of ε to be chosen in the range 0.05 to 0.55. The performance has also been tested for the varying values of sparsity, the above mentioned range worked well. In this paper, it is fixed as $ε = 0.5$ for the forth coming analyses.

Comparison between EOMP and OMP is shown in Figure 8. The EOMP is simulated with $ε = 0.5$ , $α = 0.7$ , and $N = 64$ . The graph is drawn for $z = 2$ , 4, and 6. EOMP has better percentage of recovery when compared to OMP. With 30 measurements and sparsity $z = 6$ , EOMP achieves 96% recovery, whereas OMP achieves only 70% recovery.

Figure 8

Comparison of OMP and EOMP.

The performance of EOMP is also compared with regularized OMP (ROMP) and ordered OMP (OOMP). The EOMP is simulated with $ε = 0.5$ , $α = 0.7$ , and $N = 64$ . In Figure 9, the comparison is done for $z = 4$ and $z = 6$ . It is evident that EOMP outperforms ROMP and OOMP. The algorithm performed well for the other sparsity levels and different lengths of the input vector also. To check the working of the recovery algorithm for image applications, the blocks (8 × 8) are converted to column vectors with specified sparsity. Then, measurements are taken using the random binary matrix. The data is recovered with OMP, ROMP, OOMP, and EOMP, PSNR of the recovered images is tabulated as in Table 2. The PSNR value is averaged over 10 independent trials. The test images used are taken from the image database available in [29, 30]. The recovery is done for different sample rates.

Table 2

Comparison of PSNR (dB) for different recovery algorithm.

Image	Bridge			Cameraman			Gold hill			Bird
Sample rate	20%	30%	40%	20%	30%	40%	20%	30%	40%	20%	30%	40%
OMP	15.22	21.61	24.11	15.4	20.87	23.9	16.88	23.74	26.6	18.5	28.11	31.87
ROMP	15.43	21.37	24.04	15.41	20.98	24	16.93	23.28	26.38	17.91	26.5	31.65
OOMP	15.72	21.25	23.96	15.8	21.22	23.59	16.59	23.56	26.28	18.25	25.63	30.99
EOMP	18.31	22.34	24.93	17.53	21.85	24.69	20.16	25.1	27.41	20.29	29.2	33.39

Bold values indicate the better PSNR in each case.

Figure 9

(a) Comparison of recovery algorithms for sparsity, $z = 4$ , and (b) comparison of recovery algorithms for sparsity, $z = 6$ .

From Table 2, it is clear that EOMP has 1 dB to 3 dB increase in PSNR on an average. The images recovered by OMP, ROMP, OOMP, and EOMP with the sample rate of 30% are shown in Figure 10 for Bridge, Cameraman, Goldhill, and Bird images.

Figure 10

From top to bottom images are recovered by (a) OMP, (b) ROMP, (c) OOMP, and (d) EOMP (sample rate: 30%).

4.2. Two-Measurement Matrix-Based CS

Performance analysis for the proposed model with only CS measurements is analyzed. The image blocks are sparsified with fixed sparsity level (z) irrespective of the nature of the block in the image. The number of measurements required and PSNR are tabulated in Table 3. Then, using Algorithm 1 as described in Section 3, based on the nature of the image, sparsity level is varied for each block. The decision is made based on the number of nonzero levels in each block. In this paper, the threshold is fixed as $T = 55$ . Using Algorithm 1 and the number of non-zero levels in each block, sparsity level is fixed as $S_{l}$ or $S_{h}$ .

Table 3

Comparison of single MM CS and two MM CS.

Image	Single MM CS			Two MM CS
	Sparsity level per block (z)	Total number of measurements	PSNR(dB)	Sparsity level		Total number of measurements	PSNR (dB)
	Sparsity level per block (z)	Total number of measurements	PSNR(dB)	$S_{l}$	$S_{h}$	Total number of measurements	PSNR (dB)
Lena $256 \times 256$	3	12288	25.4	2	3	10884	25.2
	6	25600	28.6	4	6	24768	28.6
	10	43008	31.4	7	10	38445	31.4
	13	55246	33.1	10	13	51084	33.1

Cameraman $256 \times 256$	3	12288	23.6	2	3	10372	23.6
	6	25600	26.3	4	6	21768	26.3
	10	43008	28.9	7	10	36781	28.8
	13	55246	30.5	10	13	49548	30.4

Cameraman $128 \times 128$	3	3072	21.9	2	3	2632	21.5
	6	6400	24.8	4	6	5520	24.5
	10	10752	27.3	7	10	9322	27.2
	13	13824	28.8	10	13	12504	28.7

Baboon $64 \times 64$	3	768	25.2	2	3	764	25.1
	6	1600	27.7	4	6	1592	27.7
	10	2688	29.9	7	10	2454	29.6
	13	3456	31.3	10	13	3240	31.0

The measurements are taken such that the PSNR in both cases are approximately the same. It indicates that there is nearly 4.2%, 6.7%, 6.2%, 2.8%, and 3.2%, 7.9%, 3.8%, 0.67% reduction in measurements on an average, while using TMM-based CS with DCT and binDCT, respectively. The values given are for Lena (256 × 256), cameraman (256 × 256), cameraman (128 × 128), and Baboon (64 × 64). Using CS alone for the measurements provides acceptable quality image with reduced measurements. The hardware realization of the same would be easier. The results given in Table 3 are for no quantization case. With quantization, further reduction in the measurements can be achieved. Hence, use of EOMP and TMM-based CS has provided a considerable reduction in the measurements. The methodology is checked for the images of different dimensions and found to be advantageous over the block based CS (single MM CS).

4.3. Two-Measurement Matrix-Based Nonuniform Sampling (NUS) CS

The use of TMM-based NUS strategy produces the same range of PSNR with much reduced measurements when compared to the original NUS strategy [11]. The number of coefficients in important component (NIC) is kept constant and the number of CS measurements is varied, the NM and PSNR obtained with binDCT are given in Table 4.

Table 4

PSNR for single MM NUS CS.

Image	NM	PNM (%)	PSNR (dB)	NIC	SM
Lena ( $512 \times 512$ )	81920	31.3	33.31	4	4
	151552	57.8	36.12	4	8
	217088	82.8	38.24	4	12

Gold hill ( $256 \times 256$ )	20480	31.3	28.52	4	4
	37888	57.8	30.38	4	8
	54272	82.8	31.93	4	12

Cameraman ( $128 \times 128$ )	5120	31.3	25.18	4	4
	9472	57.8	27.56	4	8
	13568	82.8	29.35	4	12

Table 5 shows the simulation results of the proposed two-measurement matrix-based nonuniform sampling CS using binDCT. Here also, the NIC is kept as constant for all blocks. The sparsity level of unimportant component is kept as 2 for all low frequency content blocks because it has few large amplitude coefficients. The sparsity of unimportant component of high-frequency content blocks is varied and the results for Lena, Gold hill, and Cameraman images are shown. TMM-based NUS CS produces the same PSNR of one-measurement matrix-based NUS CS at 5% to 40% and 1.4 to 20% reduction in number of measurements while using DCT and binDCT, respectively. This reduction in number of measurements leads to saving in bandwidth and energy, enabling its use in WVSNs.

Table 5

PSNR for TMM-based NUS CS.

Image	NM	PNM (%)	PSNR (dB)	NIC	ML	MH
Lena ( $512 \times 512$ )	66848	25.5	33.24	4	2	4
	137627	52.5	36.05	4	2	8
	194251	74.1	38.08	4	2	12

Gold hill ( $256 \times 256$ )	19624	29.9	28.51	4	2	4
	35963	54.8	30.37	4	2	8
	51115	77.9	31.91	4	2	12

Cameraman ( $128 \times 128$ )	4496	27.4	25.18	4	2	4
	7447	45.4	27.57	4	2	8
	10370	63.2	29.33	4	2	12

The comparison of one-measurement matrix-based NUS CS and proposed TMM-based NUS CS for Clock (256 × 256) image is shown in Figure 11. From the graph, it is clearly visible that the proposed method needs much less measurements than one-measurement matrix-based nonuniform sampling CS to achieve the same PSNR.

Figure 11

Comparison between the TMM and one MM NUS CS method (Clock (256 × 256)).

The rate distortion curve for the TMM-based NUS CS and NUS CS is shown in Figure 12. The curve is obtained by varying the quantization step size from 2 to 64 with fixed values of $NIC = 4$ , $ML = 2$ and $MH = 4$ for TMM-based NUS CS and $NIC = 4$ , $SM = 4$ for the NUS CS. The results in the graph is for the cameraman image (256 × 256). The proposed strategy produces a reconstructed image of PSNR 25.86 dB at 0.54 bpp from 14368 measurements with the quantization size of 32. The proposed strategy is better than the existing NUS CS at low bit rates.

Figure 12

Rate distortion curve for TMM-based NUS method and the NUS CS (Cameraman (256 × 256)).

PSNR obtained at the bit rate of 0.5 bpp is acceptable; hence, we fixed the quantization size to be 64 and varied the number of elements taken from important and unimportant components to get better compression ratio. The results are shown in Figure 13. The x-axis shows the varying values of NIC, ML, and MH. The bit rate and PSNR are shown correspondingly.

Figure 13

Bit rate and PSNR for varying measurements in TMM-based NUS.

With the quantization step size of 64, a maximum of 44% compression is achieved. Further increased compression ratio can be achieved with the degradation in the image quality.

5. Conclusion

In this paper, TMM-based sampling strategy is used with CS-only and NUS-based CS techniques with DCT and binDCT as sparsity basis. In both cases, it is showed that the use of TMM reduced the required number of measurements considerably. We also proposed an enhanced version of the OMP. From the analysis of the percentage of recovery it is inferred that the EOMP produces the exact recovery of the sparse signal with very much reduced measurements. And also with this reduced measurements, the image quality is maintained in the acceptable level. Hence, the low bit rate transmission of the images in WVSNs is enabled.

Use of CS will reduce the complexity in hardware realizations in near future. The proposed methodology can be integrated in the WVSN node to reduce the energy requirement to send the image. Our approach will reduce the communication energy with reduced measurements. Hence, the lifetime of the network will be increased with the proposed methodology. Our future work will focus on the design of encoding technique to reduce the bit rate optimally for the WVSN scenario. Another interesting extension will be the energy analysis of the entire system model.

Footnotes

Notations

Conflict of Interests

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

References

Soro

Heinzelman

A survey of visual sensor networks

Advances in Multimedia 2009 2009 21

2-s2.0-68949132673

10.1155/2009/640386

640386

Akyildiz

I. F.

Melodia

Chowdhury

K. R.

A survey on wireless multimedia sensor networks

Computer Networks 2007 51 4 921 960

2-s2.0-33845708421

10.1016/j.comnet.2006.10.002

Almalkawi

I. T.

Zapata

M. G.

al-Karaki

J. N.

Morillo-Pozo

Wireless multimedia sensor networks: current trends and future directions

Sensors 2010 10 7 6662 6717

2-s2.0-77957126868

10.3390/s100706662

Donoho

D. L.

Compressed sensing

IEEE Transactions on Information Theory 2006 52 4 1289 1306

2-s2.0-33645712892

10.1109/TIT.2006.871582

Romberg

Imaging via compressive sampling: Introduction to compressive sampling and recovery via convex programming

IEEE Signal Processing Magazine 2008 25 2 14 20

2-s2.0-41949092175

10.1109/MSP.2007.914729

Candès

E. J.

Romberg

J. K.

Tao

Stable signal recovery from incomplete and inaccurate measurements

Communications on Pure and Applied Mathematics 2006 59 8 1207 1223

2-s2.0-33745604236

10.1002/cpa.20124

Candès

Romberg

Sparsity and incoherence in compressive sampling

Inverse Problems 2007 23 969 985

2-s2.0-34249687049

10.1088/0266-5611/23/3/008

Duarte

M. F.

Davenport

M. A.

Takbar

Laska

J. N.

Sun

Kelly

K. F.

Baraniuk

R. G.

Single-pixel imaging via compressive sampling: Building simpler, smaller, and less-expensive digital cameras

IEEE Signal Processing Magazine 2008 25 2 83 91

2-s2.0-41949104024

10.1109/MSP.2007.914730

Sermwuthisarn

Auethavekiat

Patanavijit

A fast image recovery using compressive sensing technique with block based orthogonal matching pursuit

Proceedings of the International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS '09)

December 2009

212 215

2-s2.0-77949901316

10.1109/ISPACS.2009.5383863

10.

Tsaig

Donoho

D. L.

Extensions of compressed sensing

Signal Processing 2006 86 3 549 571

2-s2.0-30844433547

10.1016/j.sigpro.2005.05.029

11.

Zhou

Xiong

Mao

Gong

Compressed sensing of images using nonuniform sampling

Proceedings of the 4th International Conference on Intelligent Computation Technology and Automation (ICICTA '11)

March 2011

483 486

2-s2.0-79955987142

10.1109/ICICTA.2011.405

12.

Jalbin

Hemalatha

Radha

Two Measurement Matrix Based Nonuniform Sampling for Wireless Sensor Networks

Proceedings of the 3rd International Conference on Computing Communication & Networking Technologies

2012

Coimbatore, India

13.

Gan

Tran

T. D.

Fast compressive imaging using scrambled block hadamard ensemble

Proceedings of the European Signal Processing Conference

2008

14.

Ogawa

Haseyama

The simplest measurement matrix for compressed sensing of natural images

Proceedings of the 17th IEEE International Conference on Image Processing (ICIP '10)

September 2010

Hong Kong, China

4301 4304

2-s2.0-78651079293

10.1109/ICIP.2010.5651800

15.

Foucart

A note on guaranteed sparse recovery via ℓ1-minimization

Applied and Computational Harmonic Analysis 2010 29 1 97 103

2-s2.0-77955281521

10.1016/j.acha.2009.10.004

16.

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

2-s2.0-64649083745

10.1109/TIT.2007.909108

17.

Needell

Vershynin

Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit

Foundations of Computational Mathematics 2009 9 3 317 334

2-s2.0-64749092799

10.1007/s10208-008-9031-3

18.

Mallat

S. G.

Zhang

Matching pursuits with time-frequency dictionaries

IEEE Transactions on Signal Processing 1993 41 12 3397 3415

2-s2.0-0027842081

10.1109/78.258082

19.

Donoho

D. L.

Tsaig

Drori

Starck

J.-L.

Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit

IEEE Transactions on Information Theory 2012 58 2 1094 1121

2-s2.0-84856938223

10.1109/TIT.2011.2173241

20.

Blumensath

Davies

M. E.

Gradient pursuits

IEEE Transactions on Signal Processing 2008 56 6 2370 2382

2-s2.0-44849136723

10.1109/TSP.2007.916124

21.

Blumensath

Davies

M. E.

Stagewise weak gradient pursuits

IEEE Transactions on Signal Processing 2009 57 11 4333 4346

2-s2.0-70350489674

10.1109/TSP.2009.2025088

22.

Baby

Pillai

S. R. B.

Ordered Orthogonal Matching Pursuit

Proceedings of the National Conference on Communications

2012

Kharagpur, India

23.

Haupt

Bajwa

W. U.

Rabbat

Nowak

Compressed sensing for networked data: a different approach to decentralized compression

IEEE Signal Processing Magazine 2008 25 2 92 101

2-s2.0-41949106208

10.1109/MSP.2007.914732

24.

Liu

Zhu

Feng

Zhang

Rashvand

H. F.

V. O. K.

Efficient sampling and compressive sensing for urban monitoring vehicular sensor networks

IET Wireless Sensor Systems 2012 2 3 214 221

25.

Mamaghanian

Khaled

Atienza

Vandergheynst

Compressed sensing for real-time energy-efficient ECG compression on wireless body sensor nodes

IEEE Transactions on Biomedical Engineering 2011 58 9 2456 2466

2-s2.0-80052049053

10.1109/TBME.2011.2156795

26.

Liang

Tran

T. D.

Fast multiplierless approximations of the DCT with the lifting scheme

IEEE Transactions on Signal Processing 2001 49 12 3032 3044

2-s2.0-0035673741

10.1109/78.969511

27.

Tran

T. D.

BinDCT: fast multiplierless approximation of the DCT

IEEE Signal Processing Letters 2000 7 6 141 144

2-s2.0-0033726834

10.1109/97.844633

28.

Wallace

G. K.

The JPEG still picture compression standard

Communications of the ACM 1991 34 4 30 44

2-s2.0-0026142897

10.1145/103085.103089

29.

The USC-SIPI Image Database

University of Southern California, http://sipi.usc.edu/database/

30.

Image repository

The University of Waterloo, http://links.uwaterloo.ca