information:filtering, stylistic:tone
Image segmentation

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.