Graph cut optimization: Difference between revisions

Revision as of 14:01, 13 January 2019

Revision as of 14:06, 13 January 2019

Line 3:

Not all pseudo-Boolean functions can be represented by a flow network, and in the general case the global optimization problem is [[NP-hard]]. There exist sufficient conditions to characterise families of functions that can be optimised through graph cuts, such as [[Pseudo-Boolean_function#Submodularity|submodular quadratic functions]]. Graph cut optimization can be extended to functions of discrete variables with a finite number of values, that can be approached with iterative algorithms with strong optimality properties, computing one graph cut at each iteration.

Graph cut optimization is an important tool for inference over [[graphical models]] such as [[Markov random field]]s or [[conditional random field]]s, and it has important applications in [[computer vision]] problems such as [[image segmentation]],<ref name="peng" /><ref name="grabcut" /> [[image denoising|denoising]],<ref name="lombaert" /> [[image registration|registration]]<ref name="so" /><ref name="tang" /> and [[stereo cameras|stereo matching]].<ref name="kim" /><ref name="hong" />

== Representability ==