Low-rank and Sparse Structures in Computational Imaging: Analysis and Algorithms

Open Access
- Author:
- Li, Yuelong
- Graduate Program:
- Electrical Engineering
- Degree:
- Doctor of Philosophy
- Document Type:
- Dissertation
- Date of Defense:
- August 28, 2018
- Committee Members:
- Vishal Monga, Dissertation Advisor/Co-Advisor
Vishal Monga, Committee Chair/Co-Chair
William E. Higgins, Committee Member
David J. Miller, Committee Member
Sean Brennan, Outside Member
Jesse Barlow, Committee Member - Keywords:
- High dynamic range imaging
Computational Imaging
Image alignment and stitching
Optimization
Statistical Estimation
Low-rank and Sparsity - Abstract:
- Computational imaging is a broad area that focuses on developing computational approaches to enhance image formation procedures and overcome certain limitations of common imaging devices, such as limited dynamic range, spatial resolution, spectral resolution, view angles, etc. With advances in computational resources as well as semiconductors and materials, computational imaging problems continue to be actively researched in both industry and academia. Some works focus on improving the physical capabilities of the hardware (e.g.\ sensors) and developing advanced devices; however, such devices are usually of high cost and sometimes impractical for many applications. For economic purposes, other works seek for algorithms that only require the use of conventional devices, and usually the critical step is in solving an inverse problem. Model-based inversion is frequently used to enhance the image formation process, which has received great popularity in the past two decades. A limitation of these techniques is that precise physical models are rarely available. In this thesis, we exploit the potential for low-rank and sparse structures in computational imaging. In particular, we look to complement model-based inversion methods by posing additional structures on images and videos. Typical approaches lie in three categories: working directly on images and videos themselves, on certain parts and components of them, or on transformed versions of them. We formulate the problem based on prior knowledge about such structures, and develop tractable optimization algorithms to obtain efficient and high-quality solutions. More specifically, we study the following problems: high dynamic range imaging, high dynamic range video synthesis and panoramic image alignment and stitching. For high dynamic range imaging, the major difficulty is on how to model object motions and eliminate the consequent ghosting artifacts. In our work, we model the static backgrounds as a low-rank matrix, and the dynamic foregrounds as a sparse matrix. Furthermore, we integrate spatial contiguity constraints on the dynamic foregrounds. We provide experimental evidence on the ability of this model in detecting moving objects (ghost regions), and subsequently in generating ghosting-artifact-free synthesized images. For high dynamic range video synthesis, the key open challenge is on motion estimation under presence of poorly-exposed pixels. To address this challenge, we move to a statistical viewpoint, and discover that the aforementioned model and several other relevant works are actually specific instances of a general maximum a posterior estimation framework. We then specialize this framework and reduce it to a concrete optimization problem whose solution gives an estimate of the background and foreground. We estimate the background part using rank minimization, and the foreground part using a multiscale adaptive kernel regression approach that implicitly captures motion information. In this way we overcome the difficulty in establishing exact correspondences between different frames. Finally, we propose a novel panoramic image alignment algorithm under a pixel-based framework to achieve higher alignment accuracy. We apply rank-1 and sparse decomposition on the transformed images, and develop efficient minimization algorithms to solve the associated challenging non-convex optimization problem. The solution gives the transformation parameters and hence the aligned images. We carry out rigorous theoretical analysis regarding convergence, optimality and complexity of the respective optimization problems.