Numerical Linear Algebra Methods For Image Restoration Problems

In signal and image processing, one wants to recover a faithful representation of anoriginal scene from blurred noisy image data. This process can be transformed mathe-matically into solving a linear system with a blurring matrix. This dissertation will studynumerical linear algebra based high-performance regularized algorithms for large-scale,structured linear systems in image restoration problems. Particularly, the blurring matrixhas different special structures under different boundary conditions, i.e., block Toeplitzwith Toeplitz blocks under Dirichlet boundary conditions or block Toeplitz-plus-Hankelwith Toeplitz-plus-Hankel blocks under Neumann boundary conditions. In this case, itis important and necessary to analysis the special structures of these matrices and theirinverse matrices and moreover, to design fast and stable algorithms for structured matrixcomputations. This dissertation consists eight chapters with six main parts.Ensuring monotonicity of perturbed triangular M-matrices is important in many ap-plications. Based on special properties of triangular M-matrices, Part I in this dissertationprovides sufficient and necessary conditions for maximum allowable of a single perturba-tion and higher rank perturbations. The key techniques include explicit formulas for theinverse of partitioned matrices and the use of Cramer’s rule. Perturbed Toeplitz tridiago-nal M-matrices are considered as a special case. The utility of these results is shown byconsidering an application: ensuring a nonnegative solution of a discrete analogue of anintegro-differential population model.Using a circulant matrix to approximate a given Toeplitz matrix, Part II in the dis-sertation studies scale parameter and fast Fourier transform based algorithms, scaling andrevised scaling Bini’s algorithms for fast inversion of triangular Toeplitz matrices. Inparticular, comparing with the original Bini’s algorithm, the scaling one improves theaccuracy of the numerical solution without additional computational cost.According to the inverse formula for Toeplitz matrices given by Lv and Huang, anapproximate inverse preconditioner is proposed for symmetric positive definite, but ill-conditioned, Toeplitz systems with multiple right-hand sides in Part III. The constructionof the preconditioner is of low computational cost, requires only the entries of Toeplitzmatrices and does not require explicit knowledge of the generating function f of Toeplitz matrices. Its convergence is proved. Numerical results are given to illustrate the efficiencyof the proposed inverse preconditioner.Enforcing anti-reflective boundary conditions, a truncated spectral decompositionpreconditioner is proposed for image restoration problems in Part IV. The preconditioneris based on the spectral decomposition of the blurring matrix with anti-reflective boundaryconditions. It clusters the large eigenvalues around one, but leaves the small eigenvaluesalone as well. Hence, conjugate gradient type methods, when applied to solving thesepreconditioned systems, converge very fast. Numerical examples are given to demonstratethe effectiveness of the proposed preconditioner.Shifting reflective boundary conditions are proposed in Part V for preserving the con-tinuity at the boundaries and therefore reducing ringing effects in the restored image. AKronecker product approximation of the corresponding blurring matrix is then provided,regardless of symmetry requirement of the PSF. The efficiency of the approximation in anSVD-based regularization method is demonstrated by several numerical examples.Iterative regularization algorithms, such as the conjugate gradient algorithm for leastsquares problems (CGLS) and the modified residual norm steepest descent (MRNSD)algorithm, are popular tools for solving large-scale linear systems arising from imagerestoration problems. These algorithms, however, are hindered by a semi-convergencebehavior, in that the quality of the computed solution first increases and then decreases.Two soft-thresholding based iterative algorithms for image deblurring are proposed inPart VI. They combine CGLS and MRNSD with a denoising technique such as soft-thresholding on the residual vector at each iteration, respectively. The convergence ofMRNSD and soft-thresholding based algorithm is proved. Numerical results show that theproposed algorithms overcome the semi-convergence behavior and the deblurring resultsare slightly better than those of CGLS and MRNSD with their optimal iterations.