Graph cuts in computer vision: Difference between revisions

Revision as of 03:34, 15 November 2017

Revision as of 01:07, 20 February 2018

Line 65:

Graph cuts methods have become popular alternatives to the level set-based approaches for optimizing the ___location of a contour (see<ref>Leo Grady and Christopher Alvino (2009), "[http://www.cns.bu.edu/~lgrady/grady2009combinatorial.pdf The Piecewise Smooth Mumford-Shah Functional on an Arbitrary Graph]", IEEE Trans. on Image Processing, pp. 2547–2561</ref> for an extensive comparison). However, graph cut approaches have been criticized in the literature for several issues:

* Metrication artifacts: When an image is represented by a 4-connected lattice, graph cuts methods can exhibit unwanted "blockiness" artifacts. Various methods have been proposed for addressing this issue, such as using additional edges<ref>Yuri Boykov and Vladimir Kolmogorov (2003), "Computing Geodesics and Minimal Surfaces via Graph Cuts", Proc. of ICCV</ref> or by formulating the max-flow problem in continuous space.<ref>Ben Appleton and Hugues Talbot (2006), "Globally Minimal Surfaces by Continuous Maximal Flows", IEEE Trans. on Pattern Analysis and Machine Intelligence, pp. 106–118</ref>

* Shrinking bias: Since graph cuts finds a minimum cut, the algorithm can be biased toward producing a small contour.<ref>Ali Kemal Sinop and Leo Grady, "[http://www.cns.bu.edu/~lgrady/sinop2007linf.pdf A Seeded Image Segmentation Framework Unifying Graph Cuts and Random Walker Which Yields A New Algorithm]", Proc. of ICCV, 2007</ref> For example, the algorithm is not well-suited for segmentation of thin objects like blood vessels (see<ref>Vladimir Kolmogorov and Yuri Boykov (2005), "What Metrics Can Be Approximated by Geo-Cuts, or Global Optimization of Length/Area and Flux", Proc. of ICCV pp. 564–571</ref> for a proposed fix).

* Multiple labels: Graph cuts is only able to find a global optimum for binary labeling (i.e., two labels) problems, such as foreground/background image segmentation. Extensions have been proposed that can find approximate solutions for multilabel graph cuts problems.<ref name="boykov2001fast" />

* Memory: the memory usage of graph cuts increase quickly as the image size increase. As an illustration, the Boykov-Kolmogorov max-flow algorithm v2.2 allocates <math>24n+14m</math> bytes (<math>n</math> and <math>m</math> are respectively the number of nodes and edges in the graph). Nevertheless, some amount of work has been recently done in this direction for reducing the graphs before the maximum-flow computation.<ref>Nicolas Lermé, François Malgouyres and Lucas Létocart (2010), "[http://lipn.fr/~lerme/docs/reducing_graphs_in_graph_cut_segmentation.pdf Reducing graphs in graph cut segmentation]", Proc. of ICIP, pp. 3045–3048</ref><ref>Herve Lombaert, Yiyong Sun, Leo Grady, Chenyang Xu (2005), "[http://step.polymtl.ca/~rv101/bandedgraphcuts.pdf A Multilevel Banded Graph Cuts Method for Fast Image Segmentation]", Proc. of ICCV, pp. 259–265</ref><ref>Yin Li, Jian Sun, Chi-Keung Tang, and Heung-Yeung Shum (2004), "[http://research.microsoft.com/pubs/69040/lazysnapping_siggraph04.pdf Lazy Snapping]", ACM Transactions on Graphics, pp. 303–308</ref>