Vision tasks, such as segmentation, grouping, recognition, can be formulated as graph partition problems. The recent literature witnessed two popular graph cut algorithms: the Ncut using spectral graph analysis and the minimum-cut using the maximum flow algorithm. We present a third major approach by generalizing the Swendsen-Wang method - a well celebrated algorithm in statistical mechanics. Our algorithm simulates ergodic, reversible Markov chain jumps in the space of graph partitions to sample a posterior probability. At each step, the algorithm splits, merges, or regroups a sizable subgraph, and achieves fast mixing at low temperature enabling a fast annealing procedure. Experiments show it converges in 2-30 seconds on a PC for image segmentation. This is 400 times faster than the single-site update Gibbs sampler, and 20-40 times faster than the DDMCMC algorithm. The algorithm can optimize over the number of models and works for general forms of posterior probabilities, so it is more general than the existing graph cut approaches.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Graph partition by Swendsen-Wang cuts


    Beteiligte:
    Barbu, (Autor:in) / Zhu, (Autor:in)


    Erscheinungsdatum :

    2003-01-01


    Format / Umfang :

    954712 byte




    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Graph Partition by Swendsen-Wang Cuts

    Barbu, A. / Zhu, S. / IEEE | British Library Conference Proceedings | 2003


    Multigrid and Multi-level Swendsen-Wang Cuts for Hierarchic Graph Partition

    Barbu, A. / Zhu, S.-C. / IEEE Computer Society | British Library Conference Proceedings | 2004



    Motion Estimation by Swendsen-Wang Cuts

    Barbu, A. / Yuille, A. / IEEE Computer Society | British Library Conference Proceedings | 2004


    Motion estimation by Swendsen-Wang Cuts

    Barbu, A. / Yuille, A. | IEEE | 2004