- They base their work on Fast Approximate Energy Minimization via Graph Cuts which proposes 2 efficient algorithms to find the labelling corresponding to a local minimum of a general energy composed of a smoothness and data term. These algorithms are based on the $\alpha - \beta$ swap and $\alpha$ expansion moves, which they prove to be acceptable moves to go towards a minimum of this energy. These moves work by defining a graph with specific costs on the edges, and performing a single min-cut on the graph. This gives a new labelling of all data points, and a new move can be done, until convergence.
- They introduce a cost function linked with using each label, and they prove that they can have well-defined optimality bounds with a slightly modified version of the $\alpha - \beta$ swap and $\alpha$ expansion algorithms, where they simply reject the move if the total cost (combination of data, smoothness and label cost) increases.
- They observe that the label cost is mostly useful to prevent defining multiple labels for unconnected parts in the image that could share the same label, since nothing encourages that behavior otherwise. But in the case where only connected components of the graph should have the same label, the smoothness energy is enough to drive the number of labels down.
- They detail how this method can be used to fit a finite (and as small as possible) set of models with parameters to a potentially noisy dataset. They give the example of fitting an unknown numbers of lines to some points:
- First initialize with a large number of random lines
- Compute optimal labelling with $\alpha$ expansion (some labels may be dropped at this point)
- Re-estimate line parameter based on labelling, continue until convergence
- They relate their energy to K-means and GMM techniques, showing how they are similar under some conditions. They also show on toy examples how the techniques differ in result. One particular nice property of the method they propose is that it can select a minimum number of labels, where K-means and GMM fitting with Expectation Maximization (EM) will not, if they are initialized with too many labels.
- They give examples of applications to line, circle fitting, homography estimation.
- Also, code: https://vision.cs.uwaterloo.ca/code/
They introduce the possibility to penalize the number of labels in a segmentation where the goal is to fit an arbitrary number of parametric models to subsets of pixels of the same label in an image.