A Multigrid for image deblurring with Tikhonov regularization

Abstract. In the resolution of certain image deblurring problems with given boundary con-ditions we obtain two-level structured linear systems. In the case of shift-invariant point spread function with Dirichlet (zero) boundary conditions, the blurring matrices are block Toeplitz matrices with Toeplitz blocks. If the periodic boundary conditions are used, then the involved structures become block-circulant-circulant-blocks. Furthermore Gaussian-like point spread functions usually lead to numerically banded matrices which are ill-conditioned since they are associated to generating functions that vanish in a neighborhood of (pi, pi). We solve such systems by applying a multigrid method. The proposed technique shows an optimality property, i.e., its cost is of O(N) arithmetic operations (like matrix-vector product), where N is the size of the linear system. In the case of images affected by noise we use two Tikhonov regularization techniques to reduce the noise effects. Key words. Point spread function (PSF); Toeplitz and circulant matrices; ill-conditioning; multigrid methods; Tikhonov and Riley regularization. 1. INTRODUCTION. Basicall