An adaptive random compressive partial sampling method with TV recovery

The recent development of compressive sensing (CS) theory (Candès et al. 2006; Donoho 2006; Eldar and Kutyniok 2012) has drawn much attention in signal processing community over the past few years. The basic principle of CS is that sparse or compressible signals can be recovered from very few measurements in comparison with traditional data acquisitions limited by Shannon–Nyquist sampling theorem. CS has an attractive advantage that the encoder is signal independent and computationally inexpensive at the cost of high complexity at the decoder. This is highly desirable to many applications where the data acquisition devices must be simple (e.g. inexpensive resource-deprived sensors) or long-term sampling process will harm the object being captured (e.g. X-ray imaging) (Eldar and Kutyniok 2012).

A signal ( x = { x_n}_{n=1}^N) of length N is said to be sparse in a basis space (varPsi ) = ( {psi _n }_{1leqslant n leqslant N}) if transform coefficients (langle x, psi _n rangle , 1le n le N ) are mostly zero, or nearly sparse in the space (varPsi ) if a dominant portion of these N coefficients are either zero or very close to zero. The sparsity of x in (varPsi ) is quantified by the number of significant (nonzero) coefficients K. The signal can be perfectly recovered from ( M = O(Klog (N/K))) observations with a high probability. Current CS recovery algorithms explore the prior knowledge that a natural image is sparse in some domains, such as DCT, wavelets, and total variation (TV) domain (Becker et al. 2011; Bioucas-Dias and Figueiredo 2007; Candes et al. 2006; Li et al. 2009; Rudin et al. 1992). The TV model was first proposed by Rudin et al. (1992) for image denoising and has been successfully used for image restoration. Recently, some TV solvers have been incorporated in the CS framework (Becker et al. 2011; Bioucas-Dias and Figueiredo 2007; Li et al. 2009; Lustig et al. 2007). Particularly, TV-based CS recovery methods achieve state-of-the-art results (Li et al. 2009). In this paper, we use TV-based CS recovery approach, which adopts the finite difference as the sparsifying operator.

The recovery performance of CS depends significantly on the measurements. The dominant cost in the sensing (measurement) process is the inner product between the sensing matrix and signal, which requires O(MN) operations for the mainstream CS. The random projection is not only time consuming but also costs a large number of memory particulary for large-scale data sensing. To sense signals under a resource-limited condition, we adopt a random element-wise operator to randomly sample M pixels of an image x with N pixels. The sensing strategy of our method, which can be regarded as an approximation of the identity operator, saves computer resources drastically. The random mask sensing can be useful in constructing 2D or 3D maps for military, environment, medicine, etc.

A natural property of CS is its ability to compactly encode the signal x without considering any specific features of x. Hence, an adaptive measurement learning, which captures the most important characteristics of a signal, could improve the CS recovery performance to a great extent. Some model-based or adaptive recovery algorithms (Wu et al. 2012; Soni and Haupt 2012, 2011) have been proposed, which greatly promoted the recovery performance over the traditional signal independent CS. For example, the model-guided adaptive recovery of compressive sensing (MARX) (Wu et al. 2012) improves the reconstruction quality of existing CS methods by 2–7 dB for some natural images. But relevant CS recovery algorithms are time consuming, which takes about 10 h for a (512 times 512) image. The time-consuming recovery process exists in most literature works and thus limits their use for large-scale data sensing. Consequently, block-based CS (Mun and Fowler 2009) and fast CS framework (Do et al. 2012) are introduced in recent years. The TV-based CS recovery algorithms are edge-reserving algorithms and much faster than other algorithms (Bioucas-Dias and Figueiredo 2007; Becker et al. 2011; Li et al. 2009; Lustig et al. 2007). Additionally, the structure random matrix (SRM) is highly relevant for large-scale and real-time compressive sensing as it has fast computation and supports block-based processing (Mun and Fowler 2009; Do et al. 2012). But these fast CS methods are not adaptive to signals. An adaptive sampling method (Yang et al. 2012) is proposed, but the forepart sampling is fixed. It is well known that edges are the critical and dominant information for nature images in computer vision, which contain not only the local statistics but also nonlocal ones of the images. In this paper, a new framework of adaptive-random sampling and recovery (ASR) algorithm is proposed to improve the rate-distortion performance of the image acquisition system, while maintaining a low complexity of the encoder.

The decoder is essentially the same as the traditional CS recovery algorithm except that a low-complexity sensing operator was incorporated (in the decoder). To the best of knowledge, this is the first time that edges of recovered images have been exploited in the adaptive image recovery, which is also our main contribution. Regarding completely random element-wise operation measurements, the measurements are independent and all the spatial pixels have the same chance to be measured. However, our adaptive sensing strategy provides the pixels located around edges more chance to be sensed than smooth regions of the image.

In the new method, we partially sample m pixels in total as the compressed m measurements. For convenience, we also name our method as compressive (partial) sampling or sensing although it is not the same as standard CS. The proposed framework is able to balance computational costs with reconstruction quality. In the new image acquisition-coding system, (m_text{r} (ll N)) random measurements (y = varPhi _text{r} circ f) of a 2D image f ((fin R^{sqrt{N} times sqrt{N}})) are measured first, where the ( varPhi _text{r}) is a (sqrt{N} times sqrt{N}) random matrix with 0/1 entries. The ( circ ) denotes the inner product operation element-wise. In other words, we randomly sense (m_text{r}) image pixels as the measurements. These measurements are quantized and sequentially transmitted to the decoder. Second, we recover a coarse image (hat{f}_1) from the ( m_text {r} ) measurements by the traditional TV-based recovery algorithm. The edge of f denoted by (m_text {a}), as the adaptive measurements, is predicted by (hat{f}_1). Third, the edge measurements are combined with the (m_r) random ones as updated (m = m_text {r} + m_text {a}) measurements to recover a refined image (hat{f}_2). Using the measurement-learning or measurement-updating concept, the double recovery procedure could improve the reconstruction performance significantly compared to completely M random measurements and other state-of-the-art CS methods.

The remainder of this paper is organized as follows. In the next section, we introduce the sensing strategy of the new ASR framework: a hybrid adaptive-random sampling is elaborated. The subsequent section presents the process of de-quantization by the CS decoder to solve a under-determined inverse problem of ASR, followed by which simulation results are reported. The final section concludes this paper.