Graph Cut Image using MATLAB

Abstract:

In the paper we discuss an application of min-cut algorithms on graphs to a problem of a segmentation of images. Segmentation, as many problems in image processing, can be formulated as a minimization problem. Graph cuts can work as a powerful energy minimization tool producing globally optimal solutions. We concern on Ford-Fulkerson algorithm and its slight modification Edmonds-Karp algorithm for finding a maximal flow in a directed weighted graph. It holds that the maximal flow corresponds to a minimal cut, and the minimal cut leads to a semi-automatic segmentation of N-dimensional image obtained in a polynomial time. The image is considered as a graph for which we find the minimal cut. The segmentation of the image is then determined by this cut, partitioning the image into pixels of an object and pixels of a background. The user is expected to determine the typical pixels of the background and the object interactively.