Lesson 2

The input to the problem is an undirected graph \(G(V,E)\), where the vertices represent pixels and two pixels are connected by an edge if we consider them neighbors (most likely we assume a rectangular grid here, but that's not important now). We also assume that each pixel \(i\) is assigned two non-negative numbers—\(b_{i}\) and \(f_{i}\). The formal meaning of these numbers will become clear very soon, but informally: the higher \(b_{i}\) (\(f_{i}\)), the more we want to assign this pixel to the background (respectively, foreground). Finally, we assume that for each pair of neighboring pixels \(\{i,j\}\) a non-negative number \(p_{ij}\) is given—a penalty for placing these pixels in different parts during segmentation. (In practice, some of these values may come from the user—for example, they may highlight a part of the image containing the foreground. The remaining values can be set to zero.)

In a modern computer vision pipeline, these numbers do not have to be chosen by hand. A neural network may estimate how likely each pixel is to belong to the foreground or background, and may also estimate which neighboring pixels should probably stay together. This is a typical interaction between machine learning and discrete optimization.

We are required to find a partition of the set of pixels into two parts \((B,F)\) that maximizes the following value: \[q(B,F)=\sum_{i \in B}b_{i}+\sum_{i \in F}f_{i} - \sum_{\substack{\{i,j\} \in E\\|B \cap \{i,j\}|=1}}p_{ij}\ .\]