Graph cut optimization: Difference between revisions

Revision as of 16:16, 31 December 2019

Latest revision as of 02:10, 25 June 2025

(12 intermediate revisions by 11 users not shown)

Line 2:

'''Graph cut optimization''' is a [[combinatorial optimization]] method applicable to a family of [[function (mathematics)|function]]s of [[Continuous or discrete variable|discrete variable]]s, named after the concept of [[cut (graph theory)|cut]] in the theory of [[flow network]]s. Thanks to the [[max-flow min-cut theorem]], determining the [[minimum cut]] over a [[graph (discrete mathematics)|graph]] representing a flow network is equivalent to computing the [[maximum flow]] over the network. Given a [[pseudo-Boolean function]] <math>f</math>, if it is possible to construct a flow network with positive weights such that

* each cut <math>C</math> of the network can be mapped to an assignment of variables <math>\mathbf{x}</math> to <math>f</math> (and vice versa), and

* the flowcost throughof <math>C</math> equals <math>f(\mathbf{x})</math> (up to an additive constant)

then it is possible to find the [[global optimum]] of <math>f</math> in [[polynomial time]] by computing a minimum cut of the graph. The mapping between cuts and variable assignments is done by representing each variable with one node in the graph and, given a cut, each variable will have a value of 0 if the corresponding node belongs to the component connected to the source, or 1 if it belong to the component connected to the sink.

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 [[Graph cuts in computer vision|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" />. See also [[Graph cuts in computer vision]].

== Representability ==

Line 29:

== Graph construction ==

Graph construction for a representable function is simplified by the fact that the sum of two representable functions <math>f'</math> and <math>f''</math> is representable, and its graph <math>G = (V' \cup V'', E' \cup E'')</math> is the union of the graphs <math>G' = (V', E')</math> and <math>G'' = (V'', E'')</math> representing the two functions. Such theorem allows to build separate graphs representing each term and combine them to obtain a graph representing the [[entire function]].<ref name="what" />

The graph representing a quadratic function of <math>n</math> variables contains <math>n + 2</math> vertices, two of them representing the source and sink and the others representing the variables. When representing higher-order functions, the graph contains auxiliary nodes that allow to model higher-order interactions.

Line 89:

== Minimum cut ==

After building a graph representing a pseudo-Boolean function, it is possible to compute a minimum cut using one among the various algorithms developed for flow networks, such as [[Ford–Fulkerson algorithm|Ford–Fulkerson]], [[Edmonds–Karp algorithm|Edmonds–Karp]], and [[Boykov–Kolmogorov algorithm]]. The result is a partition of the graph in two connected components <math>S</math> and <math>T</math> such that <math>s \in S</math> and <math>t \in T</math>, and the function attains its global minimum when <math>x_i = 0</math> for each <math>i</math> such that the corresponding node <math>v_i \in

S</math>, and <math>x_i = 1</math> for each <math>i</math> such that the corresponding node <math>v_i \in T</math>.

Max-flow algorithms such as Boykov&ndash;Kolmogorov's are very efficient in practice for sequential computation, but they are difficult to parallelise, making them not suitable for [[distributed computing]] applications and preventing them from exploiting the potential of modern [[Central Processing Unit|CPU]]s. Parallel max-flow algorithms were developed, such as [[Push–relabel maximum flow algorithm|push-relabel]]<ref name="goldberg" /> and [[jump-flood algorithm|jump-flood]],<ref name="peng" /> that can also take advantage of hardware acceleration in [[GPGPU]] implementations.<ref name="cudacuts" /><ref name="peng" /><ref name="stich" />

== Functions of discrete variables with more than two values ==

Line 112:

'''foreach''' <math>\alpha \in \Lambda</math>:

<math>\mathbf{\hat{x}} := \arg \min_{\mathbf{y} \in \Alpha(\mathbf{x})} f(\mathbf{y})</math>

'''if''' <math>f(\mathbf{\hat{x}}) < f(\mathbf{x})</math>:

<math>\mathbf{x} = \mathbf{\hat{x}}</math>

<math>\text{exit} := 0</math>

Line 124:

'''foreach''' <math>(\alpha, \beta) \in \Lambda^2</math>:

<math>\mathbf{\hat{x}} := \arg \min_{\mathbf{y} \in \Alpha\Beta(\mathbf{x})} f(\mathbf{y})</math>

'''if''' <math>f(\mathbf{\hat{x}}) < f(\mathbf{x})</math>:

<math>\mathbf{x} = \mathbf{\hat{x}}</math>

<math>\text{exit} := 0</math>

Line 146:

Sufficient conditions analogous to submodularity were developed to characterise higher-order pseudo-Boolean functions that can be optimised in polynomial time,<ref name="freedman" /> and there exists algorithms analogous to <math>\alpha</math>-expansion and <math>\alpha\beta</math>-swap for some families of higher-order functions.<ref name="p3" /> The problem is NP-hard in the general case, and approximate methods were developed for fast optimization of functions that do not satisfy such conditions.<ref name="freedman" /><ref name="kohli" />

== Notes ==

<references group="note">

<ref name="annealing">Algorithms such as [[simulated annealing]] have strong theoretical convergence properties for some scheduling of the temperature to infinity. Such scheduling cannot be realised in practice.</ref>

<ref name="fn auxiliary node">Adding one node is necessary, graphs without auxiliary nodes can only represent binary interactions between variables.</ref>

</references>

== References ==

{{reflist|20em|refs=

<references>

<ref name="cudacuts">Vineet and Narayanan (2008).</ref>

<ref name="elc">Ishikawa (2014).</ref>

Line 166 ⟶ 172:

<ref name="tang">Tang and Chung (2007).</ref>

<ref name="what">Kolmogorov and Zabin (2004).</ref>

}}

</references>

==Bibliography==

* {{cite journal|title=Fast approximate energy minimization via graph cuts|year=2001|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=23|issue=11|last1=Boykov|first1=Yuri|last2=Veksler|first2=Olga|last3=Zabih|first3=Ramin|pages=1222–1239|doi=10.1109/34.969114|citeseerx=10.1.1.439.2071}}

* {{cite conference|title=Energy minimization via graph cuts: Settling what is possible|conference=IEEE Computer Society Conference on Computer Vision and Pattern Recognition|year=2005|volume=2|last1=Freedman|first1=Daniel|last2=Drineas|first2=Petros|pages=939–946|url=http://www.vision.cs.rpi.edu/publications/pdfs/freedman_cvpr05-cuts.pdf}}

* {{cite journal|title=A new approach to the maximum–flow problem|year=1988|journal=Journal of the ACM|volume=35|pages=921–940|issue=4|last1=Goldberg|first1=Andrew V|last2=Tarjan|first2=Robert E|url=http://akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/08/Goldberg88.pdf|doi=10.1145/48014.61051|s2cid=52152408}}

* {{cite conference|first=Hiroshi|last=Ishikawa|title=Higher–Order Clique Reduction Without Auxiliary Variables|conference=IEEE Conference on Computer Vision and Pattern Recognition|year=2014|publisher=IEEE|pages=1362–1369|url=https://www.cv-foundation.org/openaccess/content_cvpr_2014/papers/Ishikawa_Higher-Order_Clique_Reduction_2014_CVPR_paper.pdf}}

* {{cite conference|title=Segment-based stereo matching using graph cuts|conference=Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition|year=2004|volume=1|last1=Hong|first1=Li|last2=Chen|first2=George|pages=74–81|url=http://vc.cs.nthu.edu.tw/home/paper/codfiles/qyliu/201211290607/Segment-based%20Stereo%20Matching%20Using%20Graph%20Cuts.pdf}}

* {{cite journal|first1=Pushmeet|last1=Kohli|first2=M. Pawan|last2=Kumar|first3=Philip H.S.|last3=Torr|title=P³ & Beyond: Move Making Algorithms for Solving Higher Order Functions|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=31|number=9|year=2009|pages=1645–1656|url=http://www.robots.ox.ac.uk/~phst/Papers/2008/P3%20Journal/p3_pami.pdf|doi=10.1109/tpami.2008.217|pmid=19574624|s2cid=91470}}

* {{cite conference|title=Visual correspondence using energy minimization and mutual information|conference=Proceedings of the Ninth IEEE International Conference on Computer Vision|year=2003|last1=Kim|first1=Junhwan|last2=Kolmogorov|first2=Vladimir|last3=Zabih|first3=Ramin|pages=1033–1040|urldoi=http:10.1109//wwwICCV.academia.edu/download/30739536/1033_kim2003.pdf1238463}}

* {{cite techreporttech report|title=Graph cuts for minimizing robust higher order potentials|year=2008|institution=Oxford Brookes University|last1=Kohli|first1=Pushmeet|last2=Ladicky|first2=Lubor|last3=Torr|first3=PHS|pages=1–9|url=https://www.researchgate.net/profile/Pushmeet_Kohli/publication/228338783_Graph_cuts_for_minimizing_robust_higher_order_potentials/links/544a74be0cf2f10303a41de2/Graph-cuts-for-minimizing-robust-higher-order-potentials.pdf}}

* {{cite journal|first1=Vladimir|last1=Kolmogorov|first2=Carsten|last2=Rother|title=Minimizing Nonsubmodular Functions: A Review|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=29|number=7|year=2007|pages=1274–1279|doi=10.1109/tpami.2007.1031|pmid=17496384|s2cid=15319364}}

* {{cite journal|first1=Vladimir|last1=Kolmogorov|first2=Ramin|last2=Zabin|title=What energy functions can be minimized via graph cuts?|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=26|number=2|year=2004|pages=1645–1656|url=https://ecommons.cornell.edu/bitstream/handle/1813/5842/2001-1857.pdf?sequence=1|doi=10.1109/TPAMI.2004.1262177|pmid=15376891|hdl=1813/5842|hdl-access=free}}

* {{cite conference|title=Simultaneous image de-noising and registration using graph cuts: Application to corrupted medical images|conference=11th International Conference on Information Science, Signal Processing and their Applications|year=2012|last1=Lombaert|first1=Herve|last2=Cheriet|first2=Farida|pages=264–268|url=http://cim.mcgill.ca/~lombaert/graphcuts-denoising-registration.pdf}}

* {{cite journal|title=JF-Cut: a parallel graph cut approach for large-scale image and video|year=2015|journal=IEEE Transactions on Image Processing|volume=24|pages=655–666|issue=2|last1=Peng|first1=Yi|last2=Chen|first2=Li|last3=Ou-Yang|first3=Fang-Xin|last4=Chen|first4=Wei|last5=Yong|first5=Jun-Hai|bibcode=2015ITIP...24..655P|doi=10.1109/TIP.2014.2378060|pmid=25494510|s2cid=1665580}}

* {{cite conference|title=Grabcut: Interactive foreground extraction using iterated graph cuts|conference=ACM transactions on graphics|year=2004|volume=23|last1=Rother|first1=Carsten|last2=Kolmogorov|first2=Vladimir|last3=Blake|first3=Andrew|pages=309–314|url=http://pages.cs.wisc.edu/~dyer/cs534-fall11/papers/grabcut-rother.pdf}}

* {{cite journal|title=Non-rigid image registration of brain magnetic resonance images using graph-cuts|year=2011|journal=Pattern Recognition|volume=44|issue=10–11|last1=So|first1=Ronald WK|last2=Tang|first2=Tommy WH|last3=Chung|first3=Albert CS|pages=2450–2467|doi=10.1016/j.patcog.2011.04.008|bibcode=2011PatRe..44.2450S }}

* {{cite conference|title=Graph Cuts with CUDA|first1=Timo|last1=Stich|conference=GPU Technology Conference|year=2009|url=https://www.nvidia.com/content/gtc/documents/1060_gtc09.pdf}}

* {{cite conference|title=Non-rigid image registration using graph-cuts|conference=International Conference on Medical Image Computing and Computer-Assisted Intervention|year=2007|last1=Tang|first1=Tommy WH|last2=Chung|first2=Albert CS|pages=916–924|url=https://link.springer.com/content/pdf/10.1007/978-3-540-75757-3_111.pdf|doi=10.1007/978-3-540-75757-3_111|doi-access=free}}

* {{cite conference|title=CUDA cuts: Fast graph cuts on the GPU|conference=IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops|year=2008|last1=Vineet|first1=Vibhav|last2=Narayanan|first2=PJ|pages=1–8|url=http://web2py.iiit.ac.in/publications/default/download/inproceedings.pdf.ac87b6f5-826a-41d1-91cf-b19f2574ac66.pdf}}

== Notes ==

<references group="note">

<ref name="annealing">Algorithms such as [[simulated annealing]] have strong theoretical convergence properties for some scheduling of the temperature to infinity. Such scheduling cannot be realised in practice.</ref>

<ref name="fn auxiliary node">Adding one node is necessary, graphs without auxiliary nodes can only represent binary interactions between variables.</ref>

</references>

== External links ==

Line 196 ⟶ 197:

*[https://github.com/nsubtil/gco-v3.0 GCO], graph cut optimization library by Olga Veksler and Andrew Delong.

{{DEFAULTSORT:Graph cut optimization}}

[[Category:Combinatorial optimization]]

[[Category:Computer vision]]