Modeling and Optimization in Compressive Sensing and Sparse Coding Applications


Student thesis: Doctoral Thesis

View graph of relations


  • Yu ZHOU

Related Research Unit(s)


Awarding Institution
Award date19 Jan 2017


In the past decade, the emerging techniques of compressive sensing (CS) and sparse coding (SC) have been widely applied in the fields of signal processing, wireless communication and medical imaging. The core of these applications is to develop an efficient recover algorithm and a compact sparse representation for signals. The quality of the recovered or sparsely represented signal can be measured by several key criteria, including the measurement error (ME), reconstruction error or representation error (RE) and the sparsity. Various regularization based methods are proposed to enhance the capability of sparse representation and more problem-specific recover algorithms are developed to solve the ill-posed CS recover problem. However, most of these methods focus on the optimization of the well-posed problem but ignore the exploration and modeling of the relationship among these key criteria.

It is expected that modeling is helpful to provide more insightful views about the problem, which tries to interpret the problem from different angles. So, in this thesis, we focus on both the modeling and optimization of CS and SC in 1-D signal and image reconstruction problem. In addition, one typical SC based application, single image superresolution (SISR) is investigated. Experimental results demonstrate that through appropriate modeling and optimization, the quality of the reconstructed signals is superior to that of the conventional optimization methods by testing both on the benchmark and real-world database. In particular, we will present five aspects of works in this thesis.

At first, dictionary learning (DL) based block compressive sensing (BCS) image reconstruction, which aims to obtain both good sparse representation and reconstructed image with high accuracy, is investigated. It is found that the recovered sub-block and the sparse coefficients are no longer simply bridged by linear function, especially when independent measurement noise exists. In addition, the major task in BCS focuses on optimizing the recovered sub-block. To accurately address the intrinsically mutual influences between the two tasks and stress the importance of major task, DL based BCS is formulated as a bi-level optimization problem in which the upper level is to approximate the reconstructed sub-block by minimizing the CS measurement error (ME) and the lower level is to optimize the sparse coefficients represented by locally learned dictionary by minimizing the sparsity of the image sub-block. Experimental results demonstrate that the proposed bi-level modeling and optimization method is effective and achieves higher performance on numerical and visual results than some state-of-the-art single-level optimization BCS recover methods.

Secondly, we investigate the 1-D CS signal reconstruction under the noisy environment, which can be regarded as a problem of locating the nonzero entries of the signal. In order to reduce the impact of the measurement noise and better locate the nonzero entries, we proposed a two-phase algorithm which works in a coarse-to-refine manner. The tradeoff between the ME and the sparsity is utilized, so in phase 1, a decomposition based multi-objective evolutionary algorithm, MOEA/D, is applied to generate a group of robust solutions. To remove the interruption of noise, the statistical features with respect to each entry among these solutions are extracted and an initial set of nonzero entries are determined by clustering technique. In phase 2, a forward-based selection method is proposed to further update this set and locate the nonzero entries more precisely based on these features. At last, the magnitudes of the reconstructed signal are obtained by the method of least squares. Experimental results on benchmark signals as well as randomly-generated signals demonstrate that our proposed method outperforms several state-of-the-art CS recover methods, achieving higher recover accuracy and maintaining smaller sparsity.

In addition, we consider the problem of estimating the sparsity for image with noise. We propose an adaptive sparsity estimation model which consists of an offline training phase and online estimation phase. In the offline training, for each training patch, MOEA/D is applied to obtain a group of Pareto solutions and determine a sparsity range by formulating SC as a multiobjective problem. By processing a reduced number of representative training patches, all the sparsity ranges are stored in a lookup table (LUT) for reuse. In the online estimation phase, for a query patch, its sparsity range is set to that of the most similar training patch. And the corresponding sparse representation vector can be obtained by a sparsity-restricted greedy algorithm (SRGA) constrained by this range. Thus, the sparsity is adaptively determined by this sparse representation vector within this range. By comparing with the state-of-the-art greedy algorithms with fixed sparsity, experimental studies on benchmark dataset demonstrate the efficacy of our proposed method.

Also, as one of the most representative application of SC, single image superresolution (SISR) is researched. In this work, we focus on using multiple dictionaries to sparsely represent the pair of low resolution and high resolution patches, namely multi-dictionary based SISR (MDSISR). As the computational cost of MDSISR is very heavy and usually time-consuming and resource-intensive, we proposed a complexity reduction method via the phase congruency (PC) map, based on which the available LR image patches are divided into important patches and unimportant patches. Then, the corresponding important HR patches are reconstructed by multiple dictionary method and the unimportant ones by single dictionary. The finalized reconstructed HR image is obtained by averaging the overlapped region between the adjacent patches. Experimental results show that the proposed method can not only obtain competitive results but also can reduce the computational complexity in the reconstruction process compared with conventional MDSISR.

Last but not the least, for MDSISR, we propose a patch based evaluator to classify the LR patches into three categories: significant, less-significant and smooth based on the complexity of the contents. By incorporating the PC based patch evaluator (PCPE), a flexible MDSISR framework is proposed, which further reduces the computational cost in the reconstruction process. In this framework, multiple dictionaries are only applied to scale up the significant patches to maintain high reconstruction accuracy. Also, two simpler baseline approaches are used to reconstruct the less-significant and smooth patches, respectively. Experimental studies on benchmark database demonstrate that the proposed method can achieve competitive PSNR, SSIM, and FSIM with some state-of-the-art SISR approaches. Besides, it can reduce the computational cost in conventional MDSISR significantly without much degradation in visual and numerical results.