Graph cuts in computer vision: Difference between revisions

Revision as of 13:20, 8 April 2007

Revision as of 03:53, 9 April 2007

Line 1:

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

In the Bayesian statistical context of smoothing noisy, or corrupted, images, Greig, Porteous and Seheult showed how the maximum a posteriori estimate of a binary image can be obtained ''exactly'' by maximising the flow through an associated image network, involving the introduction of a ''source'' and ''sink''. The problem was therefore converted into a NP hard problem which could be solved using known efficient algorithms.

Prior to this result ''approximate'', although more general 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. See the references below.

Although the general <math>k</math>-colour problem remains unsolved for <math>k > 2,</math> the approach of Greig, Porteous and Seheult has turned out to have wide applicability in general computer vision problems. Their approach is often applied iteratively to a sequence of binary images, usually yielding near optimal solutions. See the article by Funka-Lea at al, as referenced below, for a recent application.

Although the general k-colour problem remains unsolved for k > 2, the approach of Greig, Porteous and Seheult has turned out to have wide applicability in general computer vision problems. Their approach is often applied iteratively to a sequence of binary images, usually yielding near optimal solutions. See the article by Funka-Lea at al, as referenced below, for a recent application.

== References ==

Line 16 ⟶ 12:

*D. Geman and S. Geman (1984), ''Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images'', IEEE Trans. Pattn Anal. Mach. Intell., '''6''', 721 - 741.

*D.M. Greig, B.T. Porteous and A.H. Seheult (1989), ''Exact maximum a posteriori estimation for binary images'', Journal of the Royal Statistical Society Series B, '''51''', 271 - 279.

[[Category: Bayesian statistics]]