Content deleted Content added
Link no longer valid, removed. |
→History: Added connection of graph cuts to other popular image segmentation algorithms |
||
Line 7:
Although the general <math>k</math>[[Graph coloring|-colour problem]] remains unsolved for <math>k > 2,</math> the approach of Greig, Porteous and Seheult<ref name="D.M. Greig, B.T 1989"/> has turned out<ref>Y. Boykov, O. Veksler and R. Zabih (1998), "[http://www.cs.cornell.edu/~rdz/Papers/BVZ-cvpr98.pdf Markov Random Fields with Efficient Approximations]", ''International Conference on Computer Vision and Pattern Recognition (CVPR)''.</ref><ref name="boykov2001fast">Y. Boykov, O. Veksler and R. Zabih (2001), "[http://www.cs.cornell.edu/~rdz/Papers/BVZ-pami01-final.pdf Fast approximate energy minimisation via graph cuts]", ''IEEE Transactions on Pattern Analysis and Machine Intelligence'', '''29''', 1222–1239.</ref> to have wide applicability in general computer vision problems. Greig, Porteous and Seheult approaches are often applied iteratively to a sequence of binary problems, usually yielding near optimal solutions.
In 2011, C. Couprie et al. <ref>Camille Couprie, Leo Grady, Laurent Najman and Hugues Talbot, “Power Watersheds: A Unifying Graph-Based Optimization Framework”, IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 33, No. 7, pp. 1384-1399, July 2011 http://leogrady.net/wp-content/uploads/2017/01/couprie2011power.pdf</ref> proposed a general image segmentation framework, called the "Power Watershed", that minimized a real-valued indicator function from [0,1] over a graph, constrained by user seeds (or unary terms) set to 0 or 1, in which the minimization of the indicator function over the graph is optimized with respect to an exponent <math>p</math>. When <math>p=1</math>, the Power Watershed is optimized by graph cuts, when <math>p=0</math> the Power Watershed is optimized by shortest paths, <math>p=2</math> is optimized by the [[Random walker algorithm]] and <math>p=\infty</math> is optimized by the [[Watershed (image processing)]] algorithm. In this way, the Power Watershed may be viewed as a generalization of graph cuts that provides a straightforward connection with other energy optimization segmentation/clustering algorithms.
==Binary segmentation of images==
| |||