Long-rank approximation and sparse recovery for visual data reconstruction

In recent years, a new theory in signal processing has emerged and is often known under the name of compressed sensing (CS). CS theory and its companions promise to be more effective than Shannon's sampling theory in the class of sparse signals. Inspired by its successes in various fields, in this dissertation we focused on solving several problems in visual data recovery, namely image/video inpainting, completion and concealment from two perspectives: sparse reconstruction with local coherent dictionary model and low-rank tensor approximation.;Our main contribution is to propose a framework that bases on tensor analysis, in particular low-rank tensor approximation technique, to exploit the spatial and temporal redundancy in visual data for recovery tasks. Our proposal is among the first works that successfully apply tensor analysis to image and video processing. More importantly, our novel contribution is to provide a practical work-flow that relies heavily on constructing low-rank data structures from visual data prior to applying low-rank-based algorithms. This aspect allows our framework to be applicable to real image and video data, and makes it stand out from other approaches.;Additionally, we propose a sparse model which bases on adaptive dictionaries to represent visual data. It allows us to employ new advancements in CS theory to attack visual data recovery problems from a new perspective. In this proposed model, a representing dictionary is fully adaptive to a single input signal, adding ultimate flexibility to signal representation and helping to achieve a sparser solution, which is desirable in various applications. This feature makes the proposed model unique comparing to other dictionary-based models that have been employed in image and video processing.;Finally, relying on the two proposed models, we have developed working algorithms for several recovery applications including visual data concealment, inpainting and completion. In various scenarios, our algorithms outperform some state-of-the-art methods. Especially, our methods are more robust when the corruptions in the visual data contain large contiguous areas. On the practical application side, we also propose a framework which facilitates the parallelization process of our algorithms. Furthermore, we develop a new parallel reduction algorithm, which is theoretically able to deliver optimum performance. Since reduction is such an essential process in any data processing algorithm, our approach is highly applicable to other applications beyond image processing.