Graph cut optimization: Difference between revisions

Revision as of 19:30, 13 January 2019

Revision as of 17:35, 14 January 2019

Line 86:

== 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-KarpEdmonds–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>.

Line 165:

</references>

* {{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|publisher=IEEE|last1=Boykov|first1=Yuri|last2=Veksler|first2=Olga|last3=Zabih|first3=Ramin|pages=1222-12391222–1239}}

* {{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-946939–946}}

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

* {{cite conference|first=Hiroshi|last=Ishikawa|title=Higher-OrderHigher–Order Clique Reduction Without Auxiliary Variables|conference=IEEE Conference on Computer Vision and Pattern Recognition|year=2014|publisher=IEEE|pages=1362-13691362–1369}}

* {{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-8174–81}}

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

* {{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-10401033–1040}}

* {{cite techreport|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-91–9}}

* {{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-12791274–1279}}

* {{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|publisher=IEEE|year=2004|pages=1645-16561645–1656}}

* {{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-268264–268}}

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

* {{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-314309–314}}

* {{cite journal|title=Non-rigid image registration of brain magnetic resonance images using graph-cuts|year=2011|journal=Pattern Recognition|volume=44|issue=10-1110–11|publisher=Elsevier|last1=So|first1=Ronald WK|last2=Tang|first2=Tommy WH|last3=Chung|first3=Albert CS|pages=2450-24672450–2467}}

* {{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-924916–924}}

* {{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-81–8}}

== Notes ==