A Gradient Descent Approximation For Graph Cuts

Abstract. Graph cuts have become very popular in many areas of com-puter vision including segmentation, energy minimization, and 3D re-construction. Their ability to find optimal results efficiently and the convenience of usage are some of the factors of this popularity. How-ever, there are a few issues with graph cuts, such as inherent sequential nature of popular algorithms and the memory bloat in large scale prob-lems. In this paper, we introduce a novel method for the approximation of the graph cut optimization by posing the problem as a gradient de-scent formulation. The advantages of our method is the ability to work efficiently on large problems and the possibility of convenient implemen-tation on parallel architectures such as inexpensive Graphics Processing Units (GPUs). We have implemented the proposed method on the Nvidia 8800GTS GPU. The classical segmentation experiments on static images and video data showed the effectiveness of our method.