Implementation of the regularized structured total least squares algorithms for blind image deblurring

The structured total least squares (STLS) problem has been introduced to handle problems involving structured matrices corrupted by noise. Often the problem is ill-posed. Recently, regularization has been proposed in the STLS framework to solve ill-posed blind deconvolution problems encountered in image deblurring when both the image and the blurring function have uncertainty. The kernel of the regularized STLS (RSTLS) problem is a least squares problem involving Block–Toeplitz–Toeplitz–Block matrices.In this paper an algorithm is described to solve this problem, based on a particular implementation of the generalized Schur Algorithm (GSA). It is shown that this new implementation improves the computational efficiency of the straightforward implementation of GSA from O(N2.5) to O(N2), where N is the number of pixels in the image.