2.1.

Compressive Sensing

The core of compressive sensing is recovering the sparse vector $\mathbf{x}\in {\mathbb{R}}^n$ from a small number of linear measurements $\mathbf{y}=\mathrm{\Phi }\mathbf{x}$, where $\mathrm{\Phi }\in {\mathbb{R}}^{m\times n}$ is the measurement matrix ($m\ll n$). There are many solutions for the underdetermined linear system if $\mathbf{y}$ is in the range of $\mathrm{\Phi }$, and we are interested in finding the sparsest one among all the solutions. However, finding the sparsest solution is NP-hard. Therefore, instead of solving the NP-hard problem, people are looking into alternative approaches. Convex approaches are of great interest because there are lots of algorithms for solving these convex problems and it is easy to analyze the solutions of the convex problems. If $\mathbf{x}$ is sparse and $\mathrm{\Phi }$ satisfies some conditions such as the null space property,²³ the incoherence condition,²⁴ and the restricted isometry property,²⁵ the following problem is equivalent for finding the sparest solution:

When there is noise in the measurements, i.e., $\mathrm{\Phi }\mathbf{x}+\mathbf{n}=\mathbf{y}$ with $\mathbf{n}$ being the white Gaussian noise, we solve the following problem instead: where $\lambda$ is a parameter for balancing the data fitting term and the regularization term. In order to solve these convex ${\ell }_1$ problems, many algorithms are proposed.^26,27

Although the ${\ell }_1$ minimization is fully understood and stable with theoretical guarantee, the number of required measurements is still high, and the performance is not good in many applications with a small number of measurements. For example, radiologists want to reduce more projections and thus radiation than that required for ${\ell }_1$ minimization in computed tomography. For the difference between two frames in a video, we want to decrease the number of measurements further such that it can realize higher fps videos than current cameras can produce. In order to recover signals from even fewer measurements, nonconvex regularizations are applied, and a short review will be given in Sec. 2.2.

2.2.

Nonconvex Optimization Problems for Compressive Sensing

In this section, we review several nonconvex regularizations for compressive sensing and their corresponding algorithms. Denote $\mathbf{x}=(x_1,x_2,\dots ,x_n)\in {\mathbb{R}}^n$, the truth sparse signal as ${\mathbf{x}}_0$, and ${\mathbf{x}}^l$ as the $l$’th iteration.

The ${\ell }_p$ ($0\le p\le 1$) term is commonly used,²⁸ and it has ${\ell }_0$ and ${\ell }_1$ as special cases. Because of the nonconvexity, it recovers sparse signals with even fewer measurements than the convex counterpart, ${\ell }_1$. To solve the nonconvex problems, there are several approaches. We describe three of them on both the noise-free and noisy cases. First, two reweighted algorithms for the following noise-free case are presented:

The iteratively reweighted ${\ell }_1$ minimization (IRL1)²⁰ replaces the ${\ell }_p$ term using a weighted ${\ell }_1$ term with the weights depending on the previous iteration. The iteration is expressed as

For every iteration, a weighted ${\ell }_1$ minimization problem has to be solved and iterative algorithms are applied.

Similarly, the iteratively reweighted least squares^21,22 replace the ${\ell }_p$ term using a weighted least squares term with the weights depending on the previous iteration. The iteration is expressed as

In this case, there is an analytical solution for the weighted ${\ell }_2$ minimization problem, since it is equivalent to a least squares problem.

Except for these two reweighted algorithms for solving ${\ell }_p$ minimization problems, some algorithms for solving convex optimization problems are applied to solve nonconvex problems with general nonconvex regularizations.²⁹ One example is the forward–backward iteration. In each forward–backward iteration, for solving

where $r(\mathbf{x})$ is a nonconvex regularization term including ${\Vert \mathbf{x}\Vert }_p$ and the following mentioned nonconvex sorted ${\ell }_1$ as special cases, a proximal mapping of the nonconvex regularization term follows a gradient descent on the data fidelity term, i.e., However, for ${\ell }_p$ minimization, there are only analytical solutions when $p=0$, $1/2$, $2/3$, and 1.³⁰

The success of ${\ell }_p$ minimization and both iterative algorithms for solving ${\ell }_p$ minimization problems depicts that it is better to assign small weights for components with large absolute values and large weights for zero components and components with small absolute values. A nonconvex sorted ${\ell }_1$ that assigns weights based on the ranking of absolute values was developed by Huang et al.³¹ Let the coefficients ${\{{\omega }_i\}}_{i=1}^n$ be a nondecreasing sequence of nonnegative real numbers, i.e., $0\le {\omega }_1\le \cdots \le {\omega }_n\ne 0$. The nonconvex sorted ${\ell }_1$ regularization is defined as

where $|x_{[1]}|\ge \cdots \ge |x_{[n]}|$ are the absolute values of the components in $\mathbf{x}$ ranked in decreasing order. Two special cases of nonconvex sorted ${\ell }_1$ are 2-level ${\ell }_1$ with $w_1=w_2=\cdots =w_k=a_1<1=w_{k+1}=\cdots =w_n$ and iterative support detection (ISD) with $w_1=w_2=\cdots =w_k=0<1=w_{k+1}=\cdots =w_n$. In addition, Huang et al. suggested a way for adaptively changing the weights during the iteration instead of having a fixed set of weights for better performance. The proposed update rule is where $r$ controls the rate of decreasing ${\omega }_i$ from 1 to 0 and $K^l$ is the smallest $i$ such that $|x_{[i+1]}^l-x_{[i]}^l|>{\Vert x^l\Vert }_{\infty }/\beta$ with some positive $\beta$.³²

2.3.

Video Compressive Sampling

A video can be considered as a series of images, as shown in Fig. 2 (left), where the coordinate space $(x,y,t)$ consists both the spatial domain $(x,y)$ and the temporal domain $(t)$. Each frame could be realized as a static natural image that is redundant because natural images are intrinsically sparse in a specific domain.^24,33 Another redundancy happens between similar frames in the temporal domain. As shown in Fig. 3, more than 85% of the pixels have no significant changes. Therefore, difference coding³⁴ in MPEG and H.265 series reuses existing frames and updates only the pixels with significant changes.

As discussed in Sec. 1, the objective of compressive video sensing is to combine both compression and sampling procedures to achieve the signal compression in hardware. In our proposed compressive video sensing, there are two types of image frames: intraframes (I-frames in H.264 or reference frames) and interframes (P-frames in H.264), shown in Fig. 4. The compressive sampling is applied on both I-frames and P-frames, where P-frames are reconstructed by the difference between P-frames and their previous frames.

Since I-frames are considered as static images and the image compressive sampling has already been studied for single-pixel cameras,^7,35 a total variation algorithm³⁶ is applied to recover intraframes from the I-frame sampling. For the P-frames, because the difference between similar frames is sparse, a nonconvex regularization is adopted to reduce the number of samples and thus increase the compression ratio. We compare the performance of four different nonconvex regularizations numerically and choose the best in the experiment. The four regularizations are: ${\ell }_p$ with IRL1, ISD, 2-level, and the nonconvex sorted ${\ell }_1$ ($m$-level). In IRL1, the weights are updated by

For 2-level, we choose $a=0.6$. For $m$-level, we choose $\beta =7$ and $r=0.1$.

We compare the runtimes, root-mean-square error (RMSE), and the peak signal-to-noise ratio (PSNR) for these four algorithms on the difference between two consecutive frames ($64\times 64$) in Fig. 5. The difference between the left and the middle images in Fig. 5 is shown on the right. We choose the measurement matrices to be randomized Bernoulli matrices with $\pm 1$ entries. The sampling rate (the number of measurements/the number of pixels) is changed from 6% to 35%. The comparison result is shown in Fig. 6, where the $x$-axis represents the sampling rate. When the number of measurements is small, nonconvex algorithms are unstable because they can easily be trapped at stationary points and the strategy for adaptively updating weights may not work so well. Overall, $m$-level is the most efficient and effective algorithm among all these four algorithms. Therefore, we choose $m$-level in our experiments in Sec. 3.

Though nonconvex algorithms are able to recover sparse signals accurately from a small number of linear measurements, there is still error due to the hardware noise and the modeling error. For example, there is noise in the measurements and the algorithms cannot recover the sparse signals exactly. In Fig. 7, we show the exact difference image between two frames on the left and compare it with that recovered using the nonconvex sorted ${\ell }_1$ on the middle. It is noticed that there are many isolated pixels with small nonzero values in the recovered difference image, and these pixels are supposed to have zero values. In order to improve this, we develop a simple and effective method to remove these pixels and update only the pixels in the areas with significant changes.

We apply the Sobel operator with a pair of $3\times 3$ convolution masks on the recovered difference image to find the edges since the Sobel kernels compute the gradient with smoothing in both the horizontal and vertical directions. Then a threshold is selected to obtain a binary mask that indicates the pixels with large gradient values. However, it does not delineate the outline of the changing area of interest. Then the binary gradient mask is dilated using the vertical structuring element followed by the horizontal structuring element for a better outline. Because the mask shows only the edges of the difference image and the areas with significant changes are inside the edges, the whole areas with significant changes are obtained via filling the holes inside the edges using a flood fill operation via the MATLAB^® function “imfill.” This method keeps the most significant changes and removes error on the difference image so as to reduce the reconstruction error in P-frames. Figure 7(c) shows the performance of this postprocessing (denoising) procedure. The flow chart for this procedure is described in Fig. 8.

Due to the frame difference sensing mechanism, the reconstruction error accumulates because every time we reconstruct P-frames using the difference between two consecutive frames. The error in the first P-frame is accumulated to the second P-frame. Therefore, the reconstruction of the first P-frame after I-frames is very important, and an improvement on this frame also improves following P-frames. On the other hand, if the number of P-frames between two consecutive I-frames is small, we can compute the difference image between the P-frame and the previous I-frame instead to avoid the accumulated error from previous P-frames.

The next numerical experiment shows that we can apply the simple denoising procedure to improve the reconstruction results of the first P-frame and all the P-frames after that. In this numerical experiment, there are five P-frames after one I-frame. In Fig. 9, all five P-frames are plotted. The first row has five ground true frames (${\mathrm{P}}_{01}$ to ${\mathrm{P}}_{05}$). For the second and third rows, we show the reconstruction results using the difference image between two consecutive frames, and the reconstruction results using the difference image between P-frames and the I-frame are shown in the fourth and fifth rows. The reconstruction results using $m$-level without the denoising step are shown in the second row (${\mathrm{P}}_{11}$ to ${\mathrm{P}}_{15}$) and the fourth row (${\mathrm{P}}_{31}$ to ${\mathrm{P}}_{35}$). The reconstruction results with the denoising step are shown in the third row (${\mathrm{P}}_{21}$ to ${\mathrm{P}}_{25}$) and the fifth row (${\mathrm{P}}_{41}$ to ${\mathrm{P}}_{45}$). The PSNR and RMSE values are shown in Tables 1 and 2. From both tables, we can see that the PSNR value is decreasing and the RMSE value is increasing for the five P-frames, if the difference images between two consecutive frames are used and the denoising step improves all P-frames, especially the first P-frame. However, if all the P-frames are compared with the I-frame, the improvement of the denoising step is large for all five P-frames. This numerical experiment suggests that we may choose to compare P-frames with the previous I-frame instead of the previous frame because the error in the previous P-frames will be accumulated.

Table 1

PSNR values for the five reconstructed P-frames with four methods: difference images between two consecutive images without the denoising step (m-level); difference images between two consecutive images with the denoising step (denoising); difference images between P-frames and the I-frame without the denoising step (m-level*); and difference images between P-frames and the I-frame with the denoising step (denoising*).

Table 2

PSNR values for the five reconstructed P-frames with four methods: difference images between two consecutive images without the denoising step (m-level); difference images between two consecutive images with the denoising step (denoising); difference images between P-frames and the I-frame without the denoising step (m-level*); and difference images between P-frames and the I-frame with the denoising step (denoising*).

The whole algorithm for P-frames reconstruction is depicted in Table 3. The steps (a) to (c) show the nonconvex sorted ${\ell }_1$ calculation process, while steps (d) to (e) demonstrate the edge-detection denoising procedure to reduce the error in the compressive video sensing.

Table 3

P-frames reconstruction algorithm.