### Fast Approximate Energy Minimization via Graph Cuts

In *International Conference on Computer Vision*, vol. I, pp. 377-384,
Kerkyra, Greece, 1999.

**Test of Time award at ICCV 2011**

### Abstract

In this paper we address the problem of minimizing a large class of energy
functions that occur in early vision. The major restriction is that the
energy function's smoothness term must only involve pairs of pixels.
We propose two algorithms that use
graph cuts to compute a local minimum even when very large moves are allowed.
The first move we consider is an "ab"-swap: for a pair of labels
"a", "b", this move exchanges the labels between an arbitrary set of
pixels labeled "a" and another arbitrary set labeled "b". Our first
algorithm generates a labeling such that there is no swap move that decreases
the energy. The second move we consider is an "a"-expansion: for a label
"a", this move assigns an arbitrary set of pixels the label "a".
Our second algorithm, which requires the smoothness term to be a metric,
generates a labeling such that there is no expansion move that decreases the
energy. Moreover, this solution is within a known factor of the global
minimum. We experimentally demonstrate the effectiveness of our approach on
image restoration, stereo and motion.

##### WHOLE PAPER pdf file (278Kb)

##### JOURNAL VERSION: Check out PAMI'01.
This journal paper contains much more material/details. In particular,
PAMI'01 contains our proof that a local minimum
found by the "a"-expansion algorithm is within the factor of 2 from the global
minimum of the Potts energy.