In many 2D image restoration problems, such as image deblurring with Dirichlet boundary conditions, we deal with two-level linear systems whose coefficient matrix is a banded block Toeplitz matrix with banded Toeplitz blocks (BTTB). Usually, these matrices are ill-conditioned since they are associated to generating functions which vanish at (π, π) or in neighborhood of it. In this work, we solve such BTTB systems by applying an Algebraic Multi-Grid method (AMG). The technique we propose has an optimality property, i.e., its cost is of O(n1 • n2) arithmetic operations, where n1 x n2 is the size of the images. Unfortunately, in the case of images affected by noise, our AMG method does not provide satisfactory regularization effects. Therefore, we propose two Tikhonov-like techniques, based on a regularization parameter, which can be applied to AMG method in order to reduce the noise effects.
Serra-Capizzano recently introduced anti-reflecting boundary conditions (AR-BC) for blurring models: the idea seems promising both from the computational and approximation viewpoint. The key point is that, under certain symmetry conditions, the AR-BC matrices can be essentially simultaneously diagonalized by the (fast) sine transform DST I and, moreover, a C1 continuity at the border is guaranteed in the 1D case. Here we give more details for the 2D case and we perform extensive numerical simulations which illustrate that the AR-BC can be superior to Dirichlet, periodic and reflective BCs in certain applications.
We briefly describe a multigrid strategy for unilevel and two-level linear systems whose coefficient matrix An belongs either to the Toeplitz class or to the cosine algebra of type III and
such that An can be naturally associated, in the spectral sense, with a polynomial function f. The interest of the technique is due to its optimal cost of O(N) arithmetic operations, where N is the size of the algebraic problem. We remark that these structures arise in certain 2D image restoration problems or can be used as preconditioners
for more complicated image restoration problems.