Max-flow Min-cut Graph Based Image Segmentation: Spring 2021
Summary
In this project, I formulated image segmentation as a max-flow, min-cut problem and developed a graph-cut based method of interactive image segmentation to segment the foreground and background from images. In this method, an image is first converted to a graph as shown in figure 1. Nodes represent pixels and the weights of the edges between nodes represent the similarity of two neighboring pixels. Meanwhile, the weights between the source, sink, and pixel-edges represent the probability that a pixel belongs to the foreground or background. Pixels selected by a user determine this probability, making this method of image segmentation interactive. With this representation of an image as a graph, we can segment the image by finding the minimum cut of its graph through well-established max-flow min-cut algorithms.
Figure 1: Graph Representation of an Image.
I evaluated the performance of the method using a subset of images from the Berkeley Segmentation Dataset, where minimal, moderate, and high numbers of pixels were manually pre-labeled. I found that the performance of the method depends on the probability and spatial distributions of the pixels in the foreground and background of an image and suggested ways to better improve the performance. Figure 2 shows the set of images used to evaluate the segmentation method, and figure 3 shows the IoU score of the method for each image and level of manual pre-labeling.
Figure 2: Subset of Images from the Berkeley Segmentation Dataset Used to Evaluate Performance.
Figure 3: IoU Scores of the Max-flow Min-cut Graph Based Image Segmentation for various images from the Berkeley Image Segmentation Dataset.