Theory And Methods Of Non-convex Compressed Sensing Based On Overcomplete Dictionaries

Compressed sensing(CS) is a new and developing framework for signal acquisition and processing. The theoretical and technical research on CS have been making a significant impact on signal acquisition, analysis and processing. Nowadays, the CS application on real signals is capturing increasing research interests, which is characterized by 1) the more practical and complex signals than the signals with ideal sparse properties are gaining attentions; 2) the sparse representations based on structured and redundant dictionaries are paid more attention than that on orthogonal bases and frames; 3) the research interest in the CS application is exceeding that in the CS theory. Moreover, the estimation of efficient reconstruction algorithms for the structured reconstruction models, which are designed for the practical problems, is not only the keys to the generalization of the CS theory to applications, but also the hotspot of the CS research.This dissertation is devoted to the theory and methods of the non-convex CS based on overcomplete dictionaries, where the block strategy is adopted for the sampling and reconstruction of images; the Ridgelet overcomplete dictionaries are constructed for any image blocks; and the structured reconstruction models are established by exploiting the sparsity and structured sparsity on the dictionaries. For the CS reconstruction, which is essentially characterized by the non-convex 0l norm constrain, we proposed several reconstruction methods. They distinguished themselves by either evolutionary searching strategies or collaborative reconstruction strategies. By the experimental results, the methods are shown not only efficient but also promising for the non-convex inverse problems. The contributions of the dissertation include:(1) The two-stage reconstruction strategy of nature-inspired optimization algorithms is proposed, which adopts global search strategies. In the first reconstruction stage, we design a genetic algorithm for a class of image blocks to acquire the estimation of atomic combinations in all directions; and in the second reconstruction stage, we adopt a clonal selection algorithm to search better atomic combinations in the sub-dictionary resulted by the first stage for each image block further on scale and shift parameters. Moreover, we adopt novel and flexible heuristic evolutionary searching strategies for the non-convex reconstruction models. The experimental results show the efficiency and stability of the method. This work is a successful try of nature-inspired optimization methods on the non-convex reconstruction.(2) A collaborative CS reconstruction method is proposed to fasten the two-stage evolutionary reconstruction method, by replacing the global searching strategies by the iterative updating steps and the local search strategies of the greedy matching pursuit methods. The main idea of the collaborative reconstruction is to reconstruct an image block by the collaboration of a group of other blocks near to it or sharing similar structures to it. Therefore, more information is made use for individual blocks than their own measurements. The proposed reconstruction model is composed of two collaborative processes which are derived from the self-similarity properties of natural images. By the experimental results, the method is shown much faster than the two-stage evolutionary reconstruction method, and to outperform the classic matching pursuit method.(3) To achieve better estimation on the local structures of images and improve the available collaborative reconstruction method, we propose a geometric structure guided collaborative reconstruction method, where the geometric structured sparsity models are established according to the structural matching between the atoms and image blocks. Furthermore, the geometric structured sparsity models are made a hybrid use with the self-similarity property in the collaborative manners, which results various collaborative reconstruction strategies for the smooth, single-oriented and stochastic image blocks. By the experimental results, the method is shown to outperform the previously proposed collaborative reconstruction scheme in reconstruction accuracy and speed.(4) It is observed that the structured sparsity properties are resulted by the block strategy and the overcomplete dictionary. To make use of such properties and acquire the accurate estimation on the image and its local directional structures, it is proposed the non-convex image reconstruction with direction-guided dictionaries and evolutionary searching strategies, where the judgment rules are designed on the Ridgelet dictionary to identify an image block as one of the three types: smooth, single-oriented and multiple-oriented. Furthermore, the direction(s) of the oriented blocks are estimated, and the smaller sparse dictionaries are chosen from the Ridgelet dictionary for the smooth and single-oriented blocks. Based on the above, three evolutionary searching strategies are designed for the three types of blocks, which are adapted to the structures of the blocks. Specifically, the smooth blocks are estimated by the one-stage evolutionary reconstruction strategies constrained by the structured sparse priors; the oriented blocks are firstly estimated by the direction guided structured sparsity, and then refined in the other evolutionary stage. The experimental results show that the direction-guided evolutionary reconstruction method performs better than the two-stage evolutionary reconstruction method in speed and reconstruction accuracy. By this work, it is further shown the application potentials of the evolutionary methods on the practical reconstruction models with non-convex sparse priors and multiple complex structured constrains.