A Graph Cut Algorithm for Generalized Image Deconvolution

Abstract

The goal of deconvolution is to recover an image x from its convolution with a known blurring function. This is equivalent to inverting the linear system y = Hx. In this paper, we consider the generalized problem where the system matrix H is an arbitrary nonnegative matrix. Linear inverse problems can be solved by adding a regularization term to impose spatial smoothness. To avoid oversmoothing, the regularization term must preserve discontinuities; this results in a particularly challenging energy minimization problem. Where H is diagonal, as occurs in image denoising, the energy function can be solved by techniques such as graph cuts, which have proven to be very effective for problems in early vision. When H is nondiagonal, however, the data cost for a pixel to have a intensity depends on the hypothesized intensities of nearby pixels, so existing graph cut methods cannot be applied. This paper shows how to use graph cuts to obtain a discontinuity preserving solution to a linear inverse system with an arbitrary non-negative system matrix. We use a dynamically chosen approximation to the energy which can he minimized by graph cuts; minimizing this approximation also decreases the original energy. Experimental results are shown for MRI reconstruction from Fourier data