page_title: Maximum flow problem
section_title: Image segmentation
hierarchical_section_title: Maximum flow problem / Real world applications / Image segmentation
caption_attribution_description: English: Image used as an example
context_page_description: In optimization theory, maximum flow problems involve finding a feasible flow through a flow network that obtains the maximum possible flow rate.
  The maximum flow problem can be seen as a special case of more complex network flow problems, such as the circulation problem. The maximum value of an s-t flow is equal to the minimum capacity of an s-t cut in the network, as stated in the max-flow min-cut theorem.
context_section_description: In their book, Kleinberg and Tardos present an algorithm for segmenting an image. They present an algorithm to find the background and the foreground in an image. More precisely, the algorithm takes a bitmap as an input modelled as follows: aᵢ ≥ 0 is the likelihood that pixel i belongs to the foreground, bᵢ ≥ 0 in the likelihood that pixel i belongs to the background, and pᵢⱼ is the penalty if two adjacent pixels i and j are placed one in the foreground and the other in the background. The goal is to find a partition (A, B) of the set of pixels that maximize the following quantity
  ,
  Indeed, for pixels in A (considered as the foreground), we gain aᵢ; for all pixels in B (considered as the background), we gain bᵢ. On the border, between two adjacent pixels i and j, we loose pᵢⱼ. It is equivalent to minimize the quantity
  because 
  We now construct the network whose nodes are the pixel, plus a source and a sink, see Figure on the right. We connect the source to pixel i by an edge of weight aᵢ.  We connect the pixel i to the sink by an edge of weight bᵢ. We connect pixel i to pixel j with weight pᵢⱼ. Now, it remains to compute a minimum cut in that network (or equivalently a maximum flow). The last figure shows a minimum cut.
caption: Source image of size 8x8.
exif: {}