A Multigrid Algorithm for Maxflow and Min-Cut Problems with Applications to Multiphase Image Segmentation

Xue Cheng Tai, Liang Jian Deng*, Ke Yin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we propose a multiphase image segmentation method via solving the min-cut minimization problem under the multigrid method framework. At each level of the multigrid method for the min-cut problem, we first transfer it to the equivalent form, e.g., max-flow problem, then actually solve the dual of the max-flow problem. Particularly, a classical multigrid method is used to solve the sub-minimization problems. Several outer iterations are used for the multigrid method. The proposed idea can be used for general min-cut/max-flow minimization problems. We use multiphase image segmentation as an example in this work. Extensive experiments on simulated and real images demonstrate the efficiency and effectiveness of the proposed method.

Original languageEnglish
Article number101
JournalJournal of Scientific Computing
Volume87
Issue number3
DOIs
Publication statusPublished - May 2021

Scopus Subject Areas

  • Software
  • Theoretical Computer Science
  • Numerical Analysis
  • Engineering(all)
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Continuous min-cut and max-flow
  • Multigrid method
  • Multiphase image segmentation

Fingerprint

Dive into the research topics of 'A Multigrid Algorithm for Maxflow and Min-Cut Problems with Applications to Multiphase Image Segmentation'. Together they form a unique fingerprint.

Cite this