Graph cuts in computer vision: Difference between revisions

Revision as of 02:54, 22 June 2007

Revision as of 15:44, 5 July 2007

Line 1:

The theory of [[Cut (graph theory)|graph cuts]] was first applied in [[computer vision]] in the paper by Greig, Porteous and Seheult of Durham University, UK.

In the [[Bayesian]] statistical context of [[smoothing]] noisy (or corrupted) images, Greig, Porteous and Seheult showed how the [[MAP estimate|maximum a posteriori estimate]] of a [[binary image]] can be obtained ''exactly'' by maximising the [[Network flow|flow]] through an associated image network, involving the introduction of a ''source'' and ''sink''. The problem was therefore shown to be aefficiently non-[[NP hard]] problem which could be solved using known [[Polynomial time|efficient]] [[algorithms]]solvable.

Prior to this result, ''approximate'' techniques such as [[simulated annealing]] (as proposed by the Geman brothers), or iterated conditional modes (a type of [[greedy algorithm]] as suggested by Julian Besag) were used to solve these types of problems.