Metraipolis › archive › dc_a00e86dc70dc
Graph cut optimization — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Graph_cut_optimization
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-06T16:44:58.617Z
- SHA-256 of the archived text
e85c139d7e9f859c556ec4be7720ecb4d28fda4881bf8d753b826ac95c073b38- Stable URL of this page
https://metraipolis.com/documento/dc_a00e86dc70dc
How to cite
Graph cut optimization — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Graph_cut_optimization (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_a00e86dc70dc (Metraipolis archive dc_a00e86dc70dc, sha256 e85c139d7e9f859c556ec4be7720ecb4d28fda4881bf8d753b826ac95c073b38)
BibTeX
@misc{dca00e86dc70dc,
title = {Graph cut optimization — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Graph_cut_optimization},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_a00e86dc70dc; sha256 e85c139d7e9f859c556ec4be7720ecb4d28fda4881bf8d753b826ac95c073b38},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Graph_cut_optimization. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Graph cut optimization is a combinatorial optimization method applicable to a family of functions of discrete variables, named after the concept of cut in the theory of flow networks. Thanks to the max-flow min-cut theorem, determining the minimum cut over a graph representing a flow network is equivalent to computing the maximum flow over the network. Given a pseudo-Boolean function f {\displaystyle f} , if it is possible to construct a flow network with positive weights such that each cut C {\displaystyle C} of the network can be mapped to an assignment of variables x {\displaystyle \mathbf {x} } to f {\displaystyle f} (and vice versa), and the cost of C {\displaystyle C} equals f ( x ) {\displaystyle f(\mathbf {x} )} (up to an additive constant) then it is possible to find the global optimum of f {\displaystyle f} 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 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 fields or conditional random fields, and it has applications in computer vision problems such as image segmentation, denoising, registration and stereo matching.
Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; categoria «Computer vision»).
Fonte: Wikipedia in inglese, voce «Graph cut optimization» — https://en.wikipedia.org/wiki/Graph_cut_optimization
Wikidata Q60321144 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q60321144
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Graph_cut_optimization?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1373893701, consultata il 2026-10-06T15:18:49.074Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 66b682363fa17a7bc595b1d2fce22c6d45ee76f3878475b243d49e65312edde8