Graph cut optimization: Difference between revisions

Revision as of 00:26, 4 May 2024

Latest revision as of 02:10, 25 June 2025

(2 intermediate revisions by 2 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 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}}