Blind image deconvolution via Hankel based method for computing the GCD of polynomials

In this paper we present an algorithm, that is based on computing approximate greatest common divisors (GCD) of polynomials, for solving the problem of blind image deconvolution. Specifically, we design a specialized algorithm for computing the GCD of bivariate polynomials corresponding to z-transforms of blurred images to recover the original image. The new algorithm is based on the fast GCD algorithm for univariate polynomials in which the successive transformation matrices are upper triangular Toeplitz matrices. The complexity of our algorithm is O(n2log(n)) where the size of blurred images is n×n. All algorithms have been implemented in Matlab and experimental results with synthetically blurred images are included to illustrate the effectiveness of our approach.