Graph cut optimization: Difference between revisions

Revision as of 01:38, 14 March 2024

Revision as of 00:26, 4 May 2024

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 185 ⟶ 192:

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