We now consider a different variation of the image segmentation problem in Section. We wil...

We now consider a different variation of the image segmentation problem in Section. We will develop a solution to an image labeling problem, where the goal is to label each pixel with a rough estimate of its distance from the camera (rather than the simple foreground/background labeling used in the text). The possible labels for each pixel will be 0,1,2 …• ,M for some integer M.

Let G = (V, E) denote the graph whose nodes are pixels, and edges indicate neighboring pairs of pixels. A labeling of the pixels is a partition of V into sets A0, … A1, ,AM, where Ak is the set of pixels that is labeled with distance k for k = 0, ,M. We will seek a labeling of minimum cost; the cost will come from two types of terms. By analogy with the foreground/background segmentation problem, we will have an assignment cost: for each pixel i and label k, the cost ai,k is the cost of assigning label k to pixel i. Next, if two neighboring pixels (i, j) e E are assigned different labels, there will be a separation cost. In Section 7.10, we used a separation penalty pij. In our current problem, the separation cost will also depend on how far the two pixels are separated; specifically, it will be proportional to the difference in value between their two labels.

Thus the overall cost q' of a labeling is defined as follows:

The goal of this problem is to develop a polynomial-time algorithm that finds the optimal labeling given the graph G and the penalty parameters aitk and py. The algorithm will be based on constructing a flow network, and we will start you off on designing the algorithm by providing a portion of the construction.

The flow network will have a source s and a sink t. In addition, for each pixel i e V we will have nodes v^k in the flow network for k = 1, ...,M, as shown in Figure 1. (M = 5 in the example in the figure.)

For notational convenience, the nodes vt 0 and vlM+1 will refer to s and t, respectively, for any choice of i e V.

We now add edges (vitk, vikk+1) with capacity ai k for k = 0,... ,M; and edges (vitk+1, vlik) in the opposite direction with very large capacity L.We will refer to this collection of nodes and edges as the chain associated with pixel i.

Notice that if we make this very large capacity L large enough, then there will be no minimum cut (A, B) so that an edge of capacity L leaves the set A. (How large do we have to make it for this to happen?). Hence, for any minimum cut (A, B), and each pixel i, there will be exactly one low-capacity edge in the chain associated with i that leaves the set A. (You should check that if there were two such edges, then a large-capacity edge would also have to leave the set A.)

Finally, here's the question: Use the nodes and edges defined so far to complete the construction of a flow network with the property that a minimum-cost labeling can be efficiently computed from a minimum s-t cut. You should prove that your construction has the desired property, and show how to recover the minimum-cost labeling from the cut.

Figure 1 The set of nodes corresponding to a single pixel i in Exercise (shown together with the source s and sink t).