Graph cut optimization: Difference between revisions

Revision as of 00:17, 7 May 2021

Latest revision as of 02:10, 25 June 2025

(7 intermediate revisions by 7 users not shown)

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}}

Line 174 ⟶ 181:

* {{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}}

Line 181 ⟶ 188:

* {{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]]