Reference

Graph Cuts

Treiber, Marco Alexander

2013

Overview

Energy functions consisting of a pixel-wise sum of data-driven energies as well as a sum of terms affected by two adjacent pixels (aiming at ensuring consistency for neighboring pixels) are quite common in computer vision. This kind of energy can be represented well by Markov Random Fields (MRFs). If we have to take a binary decision, e.g., in binary segmentation, where each pixel has to be labeled as “object” or “background,” the MRF can be supplemented by two additional nodes, each representing one of the two labels. The globally optimal solution of the resulting graph can be found by finding its minimum cut (where the sum of the weights of all severed edges is minimized) in polynomial time by maximum flow algorithms. Graph cuts can be extended to the multi-label case, where it is either possible to find the exact solution when the labels are linearly ordered or the solution is approximated by iteratively solving binary decisions. An instance of the max-flow algorithm, binary segmentation, as well as stereo matching and optical flow calculation, which can both be interpreted as multi-labeling tasks, is presented in this chapter. Normalized cuts seeking a spectral, i.e., eigenvalue solution, complete the chapter.

• Publisher: Springer London, Limited,Springer London
• Subject: Adjacent Pixel / Binary Segmentation / Image processing / Markov Random Field / Optimization / Spare Capacity / Stereo Match
• ISBN: 1447152824, 9781447152828