Fast algorithms for total variation minimization with applications to image deconvolution and compressed sensing

[摘要] This thesis presents two fast algorithms for total variation based image restoration. As an important branch of imaging sciences, image restoration aims to recover the original images from the degraded observations or measurements and usually some kind of regularization techniques are required for numerical stability and reducing aliasing artifacts of the recovered images. As a non-smoothing regularization technique, total variation minimization has been widely used in many image restoration fields because it allows for discontinuities in the images but at the same time disfavors oscillations. Moreover, total variation minimization can exploit the spareness of the gradient of the recovered images in many fields such as medical imaging to reduce the aliasing artifacts of the recovered images. In spite of the outstanding performance of total variation minimization in modeling many natural images, it is still a great challenge to develop efficient algorithms for it because of the high nonlinearity of total variation. Many progresses have been made to develop efficient algorithms for total variation minimization but the existing algorithms are still far from satisfying in many fields. In this thesis, we present two fast algorithms for total variation minimization in two important applications: image deconvolution and image reconstruction in compressed sensing. In image deconvolution, we present a simple algorithmic framework for recovering images from blurry and noisy observations when a blurring point-spread function is given. This framework introduces an augmented variable and construct a new functional based on the original variable and the augmented variable. We alternatively minimize the new functional based on these two variables alternatively. Basically, our algorithm is an iterative procedure of alternately solving a pair of easy subproblems associated with an increasing sequence of penalty parameter values. The main computation at each iteration is three Fast Fourier Transforms (FFTs). For image reconstruction for compressed sensing, our new algorithm is a fixed point iteration algorithm that is based on two powerful algorithmic ideas: operator-splitting and graph-based algorithms. The operator-splitting technique allows us to solve one easy subproblem and a relatively hard subproblem in each fixed point iteration associated with an increasing sequence of penalty parameter values. The newly emerging graph-based algorithms efficiently generate solutions of the hard subproblem. For both algorithms, global convergence is well established and their practical performances are also demonstrated by several typical numerical experiments.

[发布机构] Rice University

[效力级别] Pure