Image denoising with variational methods via graph cuts

Abstract

Graph cut methods have evolved to a well-investigated and acknowledged method in computer vision. They have successfully been applied to a great variety of applications such as medical image processing, image restoration and segmentation, and many more. Many problems in computer vision arise from the need of determining the maximum a posteriori estimate in a stochastic Markov random field model, which in fact is equivalent to minimizing some energy function. These energies incorporate on the one hand the deviation from observed data and on the other hand the smoothness characteristics of the solution.<br />For a certain type of energy functions, graph cuts provide a novel way to exactly infer the maximum a posteriori estimate by computing a minimum cut. The energies are modeled as flow networks and due to the important max-flow-min-cut theorem the minimum cut can be found efficiently by computing the maximum flow. However, as soon as such energy function increases in complexity, either by extending the range of labels (multilabel problem) or by adding complex interaction potentials, the problem of inferring the exact MAP estimate becomes NP-hard. Especially the subject of image denoising, which is the reconstruction of an image that has been degraded by noise, has received extensive attention from the image analysis community. Several continuous regularization methods for denoising have been proposed. In the course of this work we investigate the applicability of graph cut methods and approximations for image denoising. In particular, we study discrete forms of first-order regularization models. Moreover, on the basis of test images which were artificially degraded by (e.g. Gaussian) noise we conduct a series of experiments with known graph constructions and show that even complex energy functions can be approximated with sufficient quality.