Graph cuts in computer vision: Difference between revisions

Revision as of 09:12, 4 July 2020

Revision as of 15:01, 19 August 2020

Line 71:

* 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://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6438&rep=rep1&type=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), "[http://pub.ist.ac.at/~vnk/papers/KB-ICCV05.pdf 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 increaseincreases quickly as the image size increaseincreases. 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] {{Webarchive|url=https://web.archive.org/web/20120327014313/http://lipn.fr/~lerme/docs/reducing_graphs_in_graph_cut_segmentation.pdf |date=2012-03-27 }}", 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>

== Algorithm ==