Editing Maximum flow problem (section)

=== Image segmentation ===
[[File:Maxflow imagesegmentation image.png|thumb|Source image of size 8x8.|alt=|left|110x110px]]
[[File:Maxflow imagesegmentation network.png|thumb|Network built from the bitmap. The source is on the left, the sink on the right. The darker an edge is, the bigger is its capacity. a<sub>i</sub> is high when the pixel is green, b<sub>i</sub> when the pixel is not green. The penalty p<sub>ij</sub> are all equal.<ref>{{Cite web|url=https://gitlab.com/francois.schwarzentruber/imagesegmentationwithmaxflow|title=Project imagesegmentationwithmaxflow, that contains the source code to produce these illustrations.|website=GitLab|language=en|url-status=dead|archive-url=https://web.archive.org/web/20191222173132/https://gitlab.com/francois.schwarzentruber/imagesegmentationwithmaxflow|archive-date=2019-12-22|access-date=2019-12-22}}</ref>]]
In their book, Kleinberg and Tardos present an algorithm for [[image segmentation|segmenting]] an image.<ref>{{Cite web|url=https://www.pearson.com/us/higher-education/program/Kleinberg-Algorithm-Design/PGM319216.html |title=Algorithm Design|website=pearson.com|language=en|access-date=2019-12-21}}</ref> 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<sub>i</sub>'' ≥ 0 is the likelihood that pixel ''i'' belongs to the foreground, ''b<sub>i</sub>'' ≥ 0 in the likelihood that pixel ''i'' belongs to the background, and ''p<sub>ij</sub>'' 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

:<math>q(A, B) = \sum_{i \in A} a_i + \sum_{i \in B} b_i - \sum_{\begin{matrix}i, j \text{ adjacent} \\ |A \cap \{i, j\}| = 1 \end{matrix}} p_{ij}</math>,

Indeed, for pixels in ''A'' (considered as the foreground), we gain ''a<sub>i</sub>''; for all pixels in ''B'' (considered as the background), we gain ''b<sub>i</sub>''. On the border, between two adjacent pixels ''i'' and ''j'', we loose ''p<sub>ij</sub>''. It is equivalent to minimize the quantity

:<math>q'(A, B) = \sum_{i \in A} b_i + \sum_{i \in B} a_i + \sum_{\begin{matrix}i, j \text{ adjacent} \\ |A \cap \{i, j\}| = 1 \end{matrix}} p_{ij}</math>

because

:<math>q(A, B) = \sum_{i \in A\cup B} a_i + \sum_{i \in A\cup B} b_i - q'(A, B).</math>

[[File:Maxflow imagesegmentation result.png|thumb|Minimum cut displayed on the network (triangles VS circles).]]

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<sub>i</sub>''.  We connect the pixel ''i'' to the sink by an edge of weight ''b<sub>i</sub>''. We connect pixel ''i'' to pixel ''j'' with weight ''p<sub>ij</sub>''. Now, it remains to compute a minimum cut in that network (or equivalently a maximum flow). The last figure shows a minimum cut.