A multigrid for image deblurring with Tikhonov regularization

In the resolution of certain image deblurring problems with given boundary conditions 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 with 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 neighbourhood 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. Copyright (c) 2005 John Wiley & Sons, Ltd.