Image Segmentation using Network Flow

In the image segmentation problem, the input is an image, and we would like to partition it into background and foreground. The MAXFLOW algorithm can be used to solve the segmentation problem in polynomial time by converting the image into a graph. The input is a bitmap on a grid where every grid node represents a pixel. We convert this grid into a directed graph G, by interpreting every edge of the grid as two directed edges.  Specifically, the input for out problem is as follows:

• A bitmap of size N × N, with an associated directed graph G = (V, E).
• For every pixel i, we have a value fi ≥ 0, which is an estimate of the likelihood of this pixel to be in the foreground (i.e., the larger fi is the more probable that it is in the foreground). The pixel intensity can be used to estimate fi, e.g. assuming that foreground pixels have a higher intensity than background pixels, brighter pixels have a higher probability of belonging to the foreground.
• For every pixel i, we have (similarly) an estimate bi of the likelihood of pixel i to be in the background

.  • For every two adjacent pixels i and j we have a separation penalty pij , which is the “price” of separating i from j. This quantity is defined only for adjacent pixels in the bitmap. The separation penalty is higher when i and j have similar intensities.

• We introduce two new vertices s (foreground) and t (background) and an edge connecting each pixel with s and t as shown in the example below.
• The optimal segmentation can be found by finding the minimum s-t cut.

Goal: implement a software solution that takes as input an image and outputs the segmentation of the image into foreground and background pixels.