Many vision tasks can be formulated as partitioning an adjacency graph through optimizing a Bayesian posterior probability p defined on the partition-space. In this paper two approaches are proposed to generalize the Swendsen-Wang cut algorithm [A. Barbu and S.C. Zhu 2003] for sampling p. The first method is called multigrid SW-cut which runs SW-cut within a sequence of local "attentional" windows and thus simulates conditional probabilities of p in the partition space. The second method is called multi-level SW-cut which projects the adjacency graph into a hierarchical representation with each vertex in the high level graph corresponding to a sub-graph at the low level, and runs SW-cut at each level. Thus it simulates conditional probabilities of p at the higher level. Both methods are shown to observe the detailed balance equation and thus provide flexibilities in sampling the posterior probability p. We demonstrate the algorithms in image and motion segmentation with three levels (see Fig.1), and compare the speed improvement of the proposed methods.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Multigrid and multi-level Swendsen-Wang cuts for hierarchic graph partition


    Beteiligte:
    Barbu, A. (Autor:in) / Song-Chun Zhu, (Autor:in)


    Erscheinungsdatum :

    2004-01-01


    Format / Umfang :

    650655 byte





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



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

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


    Graph partition by Swendsen-Wang cuts

    Barbu, / Zhu, | IEEE | 2003


    Graph Partition by Swendsen-Wang Cuts

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


    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