You're designing an interactive image segmentation tool that works as follows. You sta...

You're designing an interactive image segmentation tool that works as follows. You start with the image segmentation setup described in Section , with n pixels, a set of neighboring pairs, and parameters {aj, {bj, and {pij}. We will make two assumptions about this instance. First, we will suppose that each of the parameters {ai}, {bi}, and {pij} is a nonnegative integer between 0 and d, for some number d. Second, we will suppose that the neighbor relation among the pixels has the property that each pixel is a neighbor of at most four other pixels (so in the resulting graph, there are at most four edges out of each node).

You first perform an initial segmentation (A0, B0) so as to maximize the quantity q(A0, B0). Now, this might result in certain pixels being assigned to the background when the user knows that they ought to be in the foreground. So, when presented with the segmentation, the user has the option of mouse-clicking on a particular pixel v1, thereby bringing it to the foreground. But the tool should not simply bring this pixel into the foreground; rather, it should compute a segmentation (A1, B1) that maximizes the quantity q(A1, B1) subject to the condition that v1 is in the foreground. (In practice, this is useful for the following kind of operation: In segmenting a photo of a group of people, perhaps someone is holding a bag that has been accidentally labeled as part of the background. By clicking on a single pixel belonging to the bag, and recomputing an optimal segmentation subject to the new condition, the whole bag will often become part of the foreground.)

In fact, the system should allow the user to perform a sequence of such mouse-clicks v1, v2, ,vt; and after mouse-click vi, the system should produce a segmentation (Ai, Bi) that maximizes the quantity q(Ai, B) subject to the condition that all of v1, v2, … ,vt are in the foreground.

Give an algorithm that performs these operations so that the initial segmentation is computed within a constant factor of the time for a single maximum flow, and then the interaction with the user is handled in O(dn) time per mouse-click.

(Note: Solved Exercise  from this chapter is a useful primitive for doing this. Also, the symmetric operation of forcing a pixel to belong to the background can be handled by analogous means, but you do not have to work this out here.)