Minimum cut

The motorcyclist is marked red, what surrounds them blue: the fence, the spectators, a car, the asphalt. The program has traced the outline of the motorcycle and the person, although it was shown only a few strokes. No neural network: the picture is turned into a graph where each pixel is linked to its neighbours, and the program has found the cheapest cut in it between red and blue. Draw yourself: add a stroke where the cut went wrong, and it is recomputed in tens of milliseconds. The “colour weight” slider changes what the cut pays for, and in the second photo the cut separates the sky from the mountains.

The white line is the border of the cut, and everything beyond it is dimmed. It runs where neighbouring pixels differ strongly: along the edge of the jacket, along the wheel, along the shadow under the motorcycle. This is neither chance nor a tuned setting: it is how the price that the cut minimises is built.

The idea

Labelling a picture as “object” and “background” is the same as cutting a graph. Add two vertices to the pixels: a source (the object) and a sink (the background). Link each pixel to them by edges whose price says how much the pixel resembles the object and the background, and to its four neighbours by an edge that is the dearer the more alike the neighbours are. Any cut between the source and the sink is a labelling: whatever stays with the source is the object. The price of the cut equals the “penalty” of the labelling: for pixels of the wrong colour and for a border between similar neighbours. The cheapest labelling is the minimum cut, and it is found by a maximum flow.

More strictly. Denote a pixel’s label L_p ∈ {object, background}. The penalty of a labelling is its energy

$$E(L) = \sum_{p} D_p(L_p) + \sum_{\{p, q\}} w_{pq}\,[L_p \ne L_q].$$

The first sum is for the data: D_p(object) is large if the colour of pixel p is rare under the red strokes, D_p(background) if it is rare under the blue ones. The second is for smoothness: for each pair of neighbours the labelling separated we pay w_pq, and w_pq is large for similar neighbours and small for dissimilar ones. Pixels under the strokes are glued to their end by edges of infinite price. There are 2 to the power of the number of pixels labellings; for a picture 320 pixels wide that is 2^64,960. There is no need to try them.

The energy can be more complex, but not every energy will do. Vladimir Kolmogorov and Ramin Zabih found out in 2004 which binary energies with pairwise terms reduce to a cut: those where the penalty for neighbours disagreeing is at least the penalty for agreeing, w(0, 1) + w(1, 0) ≥ w(0, 0) + w(1, 1). Such energies are called submodular. Ours is a special case: agreement costs zero, disagreement w_pq ≥ 0.

Colour against borders

The two terms pull in different directions. Smoothness likes short borders along sharp transitions; the data likes each pixel to go to whoever it resembles in colour. The listing below computes the cut of the same picture, shrunk to 120 pixels wide, at four colour weights. Without colour the cut gives the object 695 pixels: the person with the motorcycle. With weight 20 the object gets 2181 pixels, with 100, 3441: the dark trees in the corner and the dark bumper of the car stick to the motorcyclist. The motorcycle is green, the jacket black, and the trees dark green: a colour model from a few strokes honestly finds them alike.

In the second photo colour and borders agree: the sky differs from the mountains both in colour and by a sharp transition. The cut runs exactly along the ridge, even where there are no strokes, and hardly changes as the colour weight moves from zero to forty. Real object selection programs build a more complex colour model, a mixture of several normal distributions, and refine it in turn with the cut. This is how the GrabCut algorithm of Carsten Rother, Vladimir Kolmogorov and Andrew Blake (2004), available in OpenCV, works.

How to find the cut: two waves meeting

By the max-flow min-cut theorem, proved in the article on maximum flow, the price of the minimum cut equals the value of the maximum flow, and the cut itself is the border of the set of vertices reachable from the source along unsaturated edges. So a fast flow on a pixel grid is needed. The Edmonds–Karp algorithm from that article starts a breadth-first search from the source anew for each path and drowns on pictures: there are thousands of paths, and each search covers tens of thousands of pixels.

Yuri Boykov and Vladimir Kolmogorov did it differently (the first version in 2001, a detailed journal paper in 2004), and their way resembles bidirectional search. Two trees grow: one from the source, the other from the sink. The source tree captures a free neighbour if the edge to it is not yet full, the sink tree if the edge from the neighbour is not full. When the trees touch, a path is found: source, along a tree, the boundary edge, along the other tree, sink. Flow is sent along it, and some edges of the path fill up.

The key is what comes next. Edmonds–Karp would throw both trees away and start again. Here the trees live on: vertices whose edge to the parent has filled up become orphans, and each orphan looks for a new parent in its own tree, a neighbour that itself still holds on to the root and whose edge is not full. If it finds one, the tree is whole. If not, the orphan becomes free, and its children are orphaned too. Then the trees grow again. When there is nowhere to grow and the trees have not met, the flow is maximum, and the source tree is the object’s side.

On this piece of 160 pixels the trees needed 27 paths to run up against each other, and the maximum flow is 42. Note where the border went: along the edge of the helmet, where red turns into blue; the edges between neighbours are cheap there, and they were filled first.

A cut without a source and a sink

Often there are no ends: what is needed is the weakest spot of the whole graph, the smallest set of edges without which it falls apart into two parts, whichever they are. This is the global minimum cut. It can be found with flows too, by trying every vertex as the sink with the same source, but in 1993 David Karger proposed a way with no flows at all.

Take a random edge and contract it: its two ends merge into one vertex, the edges between them vanish (they would become loops), and the other edges are kept, even if they have become parallel. Repeat until two vertices remain. Each is a group of original vertices, and the edges between them are a cut. Here is how it looks on the network of flights between 21 airports: the weight of a link is the number of callsigns flying between two cities, and a random edge is taken in proportion to its weight.

The first run cut off Balkhash: only two callsigns fly to and from it. Press “2000 runs”: in 76% of cases the contractions end with a cut of weight 2, which is the minimum, and there are two such cuts, Balkhash and Usharal; in the remaining cases heavier cuts come out. Why so often at all? Because the edges of the minimum cut are few, and a random edge is most often taken from thick bundles like Almaty–Astana, which are safe to contract.

For 21 airports the bound is 0.48%, and in fact it is 76%: the theorem speaks of the worst graph, and the flight network is far from it. But even the worst case is not frightening. Repeat the runs independently T times and take the best cut. The probability that all T missed is at most (1 − p)^T ≤ e^−pT, where p = 2/(n(n − 1)). With T = n(n − 1)/2 · ln 100 this is less than 1%: for 21 airports, 968 runs. The result is a Monte Carlo algorithm: fast, but with a small probability of error that repetition can make as small as you like.

The theorem also yields an unexpected fact without any algorithm. The events “the run ended with cut C₁” and “… with cut C₂” for different minimum cuts are mutually exclusive, and each has probability at least 2/(n(n − 1)). The probabilities sum to at most one, so a graph has at most n(n − 1)/2 minimum cuts. A cycle of n vertices has exactly that many: any pair of edges.

Many runs are needed, and each costs O(m), about n²m log n in all. In 1996 Karger and Clifford Stein sped the scheme up: the first contractions are almost safe, so the graph is contracted to n/√2 vertices once, and after that two independent copies are run recursively. That gives O(n² log³ n). A deterministic way, without randomness, was given by Mechthild Stoer and Frank Wagner in 1997. It also contracts vertices, but chooses the pair not at random: in each phase the vertices are lined up in “maximum adjacency” order, each next one most strongly connected to those already chosen, and the cut “the last vertex against the rest” turns out to be minimal among cuts separating the last two. The time is O(nm + n² log n). The listing uses it to check Karger’s answer.

Code

The segmentation of the motorcyclist in full: strokes, a graph with prices, the Boykov–Kolmogorov algorithm on the pixel grid. The graph is not built explicitly: a pixel has four neighbours, and the capacity of the edge to the neighbour in direction d lies in cap[4p + d]. The edges to the source and sink are stored as one number tr[p]: the path “source → p → sink” is saturated at once by the smaller of the two prices, leaving only the difference. The program checks the theorem on itself: the price of the cut found equals the energy of the labelling, computed separately.

colour weight   cut = energy   object pixels   augmentations
            0           1079             695             423
           20          86895            2181            4228
           50         208895            3092            4257
          100         407370            3441            5085

The global cut of the flight network: the exact answer by the Stoer–Wagner algorithm and 2000 runs of random contractions. Each callsign is a separate edge of the multigraph, and a random callsign is chosen with equal probability, that is, a link in proportion to its weight. If a loop comes up, a callsign inside an already merged group, it is simply drawn again: the same as choosing a random edge among non-loops.

What it costs

There is no good bound for the Boykov–Kolmogorov flow, as said above. But a measurement on grids of the same picture shrunk to different widths shows the difference from Edmonds–Karp better than any bound. The axes are logarithmic.

On a picture 120 pixels wide Boykov–Kolmogorov in Go is 170 times faster, and the gap grows with size: the time of Edmonds–Karp grows faster than the square of the number of pixels, and that of Boykov–Kolmogorov not much faster than linearly. Edmonds–Karp traverses the whole graph anew for each path, while Boykov–Kolmogorov’s trees survive the paths, and most of the work is not repeated. In the browser the scene above computes the cut of a picture 320 pixels wide in tens of milliseconds, fast enough to recompute after every stroke.

Where it works

• Selecting objects in photos. The GrabCut algorithm, a rectangle around the object, correction strokes and a cut of the pixel graph, is in OpenCV as cv.grabCut.
• Medical images. A doctor marks a few points of an organ and of the background, and a cut of the three-dimensional voxel grid traces the whole organ: the same energy, only a voxel has six neighbours.
• Vision in general. Stereo, stitching panoramas along an invisible seam, denoising: labelling problems reduced to a chain of cuts. Yuri Boykov, Olga Veksler and Ramin Zabih showed in 2001 how to solve a multi-label problem by a sequence of binary cuts, and this became the standard.
• Network reliability. The global cut is the smallest number of links whose breaking divides a network: communication channels, pipelines, flights. In the network above it is just two links, and both lead to one airport.

History

In 1989 the statisticians D. M. Greig, B. T. Porteous and A. H. Seheult were working on restoring a binary image from a noisy one: finding the most probable picture under a model where neighbouring pixels tend to coincide. Such problems were then solved approximately, by annealing for instance. The authors noticed that the problem reduces to a minimum cut and solved it exactly. The paper came out in a journal of mathematical statistics, and computer vision researchers hardly noticed it for more than ten years.

In the late 1990s Yuri Boykov, Olga Veksler and Ramin Zabih brought cuts back into vision, for many labels and for real problems. In 2001 Boykov and Marie-Pierre Jolly demonstrated interactive segmentation with strokes, just as in the scene above. And in 2004 three works came out at once: the flow algorithm of Boykov and Kolmogorov, Kolmogorov and Zabih’s answer to the question of which energies can be minimised by a cut at all, and GrabCut by Rother, Kolmogorov and Blake.

The global cut was long sought with flows. In 1992 Hiroshi Nagamochi and Toshihide Ibaraki found a way without flows, based on “maximum adjacency order”, and Stoer and Wagner in 1997 brought it to a short algorithm with a simple proof. In between, in 1993, David Karger, then a graduate student, showed that random contractions find the cut with good probability, with an analysis half a page long. This algorithm became one of the standard first examples of randomised algorithms in textbooks.

Problems

In the first problem the cut cuts nothing in a picture: it chooses which articles of this catalogue to read for the sake of the problems, and infinite edges make it impossible to “solve a problem without reading the article”. In the second there is no source and sink, and the most weakly connected node is not always the weakest spot.