Fast Solvers for Toeplitz Systems with Applications to Image Restoration

This dissertation, "Fast Solvers for Toeplitz Systems With Applications to Image Restoration" by Youwei, Wen, 文有為, was obtained from The University of Hong Kong (Pokfulam, Hong Kong) and is being sold pursuant to Creative Commons: Attribution 3.0 Hong Kong License. The content of this dissertation has not been altered in any way. We have altered the formatting in order to facilitate the ease of printing and reading of the dissertation. All rights not granted by the above license are retained by the author. Abstract: Abstract of thesis entitled FAST SOLVERS FOR TOEPLITZ SYSTEMS WITH APPLICATIONS TO IMAGE RESTORATION submitted by WEN You-Wei for the degree of Doctor of Philosophy at The University of Hong Kong in July 2006 Many applications in numerical mathematics and image processing require solv- inglinearsystemsofequationswhosecoecientmatricesarelargeandhaveToeplitz- like structure. Iterative solution techniques based on projection processes onto Krylov subspaces are used to solve such systems. The convergence rate can be speeded up when a suitable preconditioner is employed. The main goal of this the- sis is to construct preconditioners for Toeplitz-like systems, and to develop ecient algorithms for image reconstructions and restorations. The inverse of a Toeplitz matrix can be written as a sum of products of lower- triangular and upper-triangular Toeplitz matrices. It was shown in this thesis that Toeplitz matrix inversion formulae are numerically forward stable if the Toeplitz matrix is nonsingular and well-conditioned. Based on the inversion formula, block diagonal, Schur complement and inverse-free preconditioners for Toeplitz matrices were proposed and studied. The spectra of the preconditioned matrices were an- alyzed to show that the preconditioned iterative method can converge very fast. Numerical results show that the number of iterations required for the convergence oftheproposedpreconditioners islessthanthatof thewell-knowncirculantprecon-ditioners, where these two preconditioning methods have the same computational cost per iteration. In this thesis, two image processing applications are studied, namely, high- resolution imaging reconstruction problems and image restoration problems. In the reconstruction of high-resolution image from low-resolution images, the key is- sue is that the warping process should be introduced to register the observed low resolutionimageswiththeperturbationofdisplacementerrorsintotheregulargrid. Fromtheconstructionofthewarpingmatrix, amathematicalmodelwasformulated into a Toeplitz-like least squares problem. Therefore, the high-resolution image can be reconstructed eciently by solving this Toeplitz-like least squares problem. In a general image restoration problem, it is necessary to use debluring and denoising techniques to handle blurred and noisy images. A combined method of this kind was proposed and developed, and is called a Corrected Inverse-Denoising FiltER(CIDER)method. SinceblurringmatricesareusuallyToeplitz-likematrices, thedeblurringstepcanthereforebesolvedeciently. Adenoisingstepisalsoapplied to correct the errors in the deblurred image. Experimental results show that the signal-to-noise ratio obtained by CIDER is greater than those of other existing methods in a comparison study. DOI: 10.5353/th_b3688280 Subjects: Image reconstruction Toeplitz matrices Algorithms