Graph cut optimization: Difference between revisions

Revision as of 16:06, 13 January 2019

Latest revision as of 02:10, 25 June 2025

(31 intermediate revisions by 19 users not shown)

Line 1:

{{short description|Combinatorial optimization method for a family of functions of discrete variables}}

'''Graph cut optimization''' is a [[combinatorial optimization]] method applicable to a family of cost[[function functions(mathematics)|function]]s of [[Continuous or discrete variablesvariable|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 suchwith thatpositive the variables of the function are represented by nodes in the network, and for each possible cut the value of the flow equals the value of the function when each variable assumes a binary value depending on the belonging of its representing node to the source or sink component after the cut, then it is possible to find the [[global optimum]] ofweights such function in [[polynomial time]] by computing a minimum cut of the graph.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 cost of <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_functionBoolean 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" />

== Representability ==

A [[pseudo-Boolean function]] <math>f: \{0, 1\}^n \to \mathbb{R}</math> is said to be ''representable'' if there exists a graph <math>G = (V, E)</math> with non-negative weights and with source and sink nodes <math>s</math> and <math>t</math> respectively, and there existexists a set of nodes <math>V_0 = \{v_1, \dots, v_n\} \subset V - \{s, t\}</math> such that, for each tuple of values <math>(x_1, \dots, x_n) \in \{0, 1\}^n</math> assigned to the variables, <math>f(x_1, \dots, x_n)</math> equals (up to a constant) the value of the flow determined by a minimum [[cut (graph theory)|cut]] <math>C = (S, T)</math> of the graph <math>G</math> such that <math>v_i \in S</math> if <math>x_i = 0</math> and <math>v_i \in T</math> if <math>x_i = 1</math>.<ref name="what" />

It is possible to classify pseudo-Boolean functions according to their order, determined by the maximum number of variables contributing to each single term. All first order functions, where each term depends fromupon at most one variable, are always representable. Quadratic functions

:<math> f(\mathbf{x}) = w_0 + \sum_i w_i(x_i) + \sum_{i < j} w_{ij}(x_i, x_j) . </math>

Line 25 ⟶ 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 64 ⟶ 68:

- p x_i x_j x_k

</math>

[[File:Graph cut ternary.svg|thumb|upright=2|Example of a graph representing the ternary term <math>p x_i x_j x_k</math> when <math>p > 0</math> (left) and when <math>p < 0</math> (right).]]

Line 86 ⟶ 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-FulkersonFord–Fulkerson algorithm|Ford-FulkersonFord–Fulkerson]], [[Edmonds–Karp algorithm|Edmonds-Karp]], and [[Boykov-KolmogorovBoykov–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 wherewere 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 109 ⟶ 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 121 ⟶ 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>

In both cases, the optimization problem in the innermost loop can be solved exactly and efficiently with a graph cut. Both algorithms terminate certainly in a finite number of iterations of the outer loop, and in practice such number is small, with most of the improvement happening at the first iteration. The algorithms can generate different solutions depending ofon the initial guess, but in practice they are robust with respect to initialisation, and starting with a point where all variables are assigned to the same random value is usually sufficient to produce good quality results.<ref name="fast" />

The solution generated by such algorithms is not necessarily a global optimum, but it has strong guarantees of optimality. If <math>S(x_i, x_j)</math> is a [[metric (mathematics)|metric]] and <math>\mathbf{x}</math> is a solution generated by the <math>\alpha</math>-expansion algorithm, or if <math>S(x_i, x_j)</math> is a [[semimetric]] and <math>\mathbf{x}</math> is a solution generated by the <math>\alpha\beta</math>-swap algorithm, then <math>f(\mathbf{x})</math> lies within a known and constant factor from the global minimum <math>f(\mathbf{x}^*)</math>:<ref name="fast" />

Line 134 ⟶ 137:

{{see also|Quadratic pseudo-Boolean optimization}}

Generally speaking, the problem of optimizing a non-submodular pseudo-Boolean function is [[NP-hard]] and cannot be solved in polynomial time with a simple graph cut. The simplest approach is to approximate the function with a similar but submodular one, for instance truncating all non-submodular terms or replacing them with similar submodular expressions. Such approach is generally sub-optimal, and it produces acceptable results only if the number of non-submodular terms is relatively small. <ref name="review" />

In case of quadratic non-submodular functions, it is possible to compute in polynomial time a partial solution using algorithms such as [[QPBO]].<ref name="review" /> Higher-order functions can be reduced in polynomial time to a quadratic form that can be optimised with QPBO.<ref name="elc" />

Line 143 ⟶ 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 163 ⟶ 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|pages=1222–1239|issue=11|publisher=IEEE|last1=Boykov|first1=Yuri|last2=Veksler|first2=Olga|last3=Zabih|first3=Ramin|pages=1222-1239}}

* {{cite conferencejournal|title=EnergyFast approximate energy minimization via graph cuts: Settling what is possible|conferenceyear=2001|journal=IEEE Computer Society ConferenceTransactions on ComputerPattern VisionAnalysis and PatternMachine RecognitionIntelligence|yearvolume=200523|volumeissue=211|last1=FreedmanBoykov|first1=DanielYuri|last2=DrineasVeksler|first2=PetrosOlga|last3=Zabih|first3=Ramin|pages=939-9461222–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-flowmaximum–flow problem|year=1988|journal=Journal of the ACM (JACM)|volume=35|pages=921–940|issue=4|publisher=ACM|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}}

* {{cite conference|first=Hiroshi|last=Ishikawa|title=Segment-basedHigher–Order stereoClique matchingReduction usingWithout graphAuxiliary cutsVariables|conference=Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition|year=20042014|volumepublisher=1IEEE|last1pages=Hong1362–1369|first1url=Li|last2=Chen|first2=George|pages=74https://www.cv-foundation.org/openaccess/content_cvpr_2014/papers/Ishikawa_Higher-81Order_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|publisher=IEEE|year=2009|pages=1645-16561645–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}}

* {{cite techreportconference|title=GraphVisual cutscorrespondence forusing minimizingenergy robustminimization higherand ordermutual potentialsinformation|year=2008|institutionconference=OxfordProceedings Brookesof Universitythe Ninth IEEE International Conference on Computer Vision|year=2003|last1=KohliKim|first1=PushmeetJunhwan|last2=LadickyKolmogorov|first2=LuborVladimir|last3=TorrZabih|first3=PHSRamin|pages=1-91033–1040|doi=10.1109/ICCV.2003.1238463}}

* {{cite tech 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|publisher=IEEE|pages=1274-1279}}

* {{cite journal|first1=Vladimir|last1=Kolmogorov|first2=RaminCarsten|last2=ZabinRother|title=WhatMinimizing energyNonsubmodular functionsFunctions: canA be minimized via graph cuts?Review|journal=IEEE transactionsTransactions on patternPattern analysisAnalysis and machineMachine intelligenceIntelligence|volume=2629|number=27|publisheryear=IEEE2007|yearpages=20041274–1279|pagesdoi=10.1109/tpami.2007.1031|pmid=17496384|s2cid=1645-165615319364}}

* {{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=264264–268|url=http://cim.mcgill.ca/~lombaert/graphcuts-268denoising-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|publisher=IEEE|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}}

* {{cite journalconference|title=Non-rigidGrabcut: imageInteractive registrationforeground ofextraction brainusing magneticiterated resonancegraph imagescuts|conference=ACM usingtransactions graph-cutson graphics|year=2011|journal=Pattern Recognition2004|volume=44|pages=2450–2467|issue=10-11|publisher=Elsevier23|last1=SoRother|first1=Ronald WKCarsten|last2=TangKolmogorov|first2=Tommy WHVladimir|last3=ChungBlake|first3=Albert CSAndrew|pages=2450309–314|url=http://pages.cs.wisc.edu/~dyer/cs534-fall11/papers/grabcut-2467rother.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=916916–924|url=https://link.springer.com/content/pdf/10.1007/978-9243-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=11–8|url=http://web2py.iiit.ac.in/publications/default/download/inproceedings.pdf.ac87b6f5-8826a-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 193 ⟶ 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]]