System and method for fast approximate energy minimization via graph cuts

摘要

Many tasks in computer vision involve assigning a label, such as disparity for depth of field data to every pixel. Energy minimization may be used to accomplish this labeling. The present invention provides an efficient way of minimizing energy functions in assigning labels to pixels. Two methods of using graph cuts to compute a local minimum are described. The first move is an alphabeta swap. For a pair of labels, alpha, beta, this move swaps the labels between an arbitrary set of pixels labeled a and another arbitrary set of pixels labeled beta. The first method generates a labeling such that there is no swap move that decreases the energy. The second move is the alpha-expansion. For a label alpha, this move assigns an arbitrary set of pixels with the label alpha.