An Efficient K-Way Constrained Normalized Cut and Its Connection to Algebraic Multigrid Method

Normalized Cut (NCut) or Spectral Clustering (SC) discourages the isolated segmentation that may result from the standard minimum Cut by adding a volume constraint. Such a volume constraint introduces a significant computational challenge or an undesirable effect when the isolated segmentation is desired. In this paper, we propose the $K$ -way constrained Normalized Cut ( $K$ -way CNCut). It is formulated as the minimum Cut with a priori chosen (either manually or automatically) constraints or representatives for the cluster. The role played by the constraints is to attract the strongly connected nodes to the relevant hosting constraints, thus it can both discourage or encourage the isolated segmentation, depending on the choice of constraints and nodes surrounding it. Most critically, in this paper, the $K$ -way CNCut is discovered to have a link with the construction of the optimal prolongation operator in the algebraic multigrid method (AMG), more precisely, the energy minimizing AMG in its most general setting, for the normalized Graph Laplacian. For the special case when a single constraint is given as a representative of a single cluster, it is shown to lead to the multiscale image segmentation. The importance of this link has been demonstrated as well. Among others, a set of constraints for the $K$ -way CNCut was shown to be constructed via the multilevel coarsening algorithm, which exists in the algebraic multigrid method, thereby the $K$ -way CNCut with manually chosen constraints, is made to be a fully automatic image segmentation algorithm. A number of numerical experiments are presented and compared with state-of-the-art classical and learning-based (both supervised and semi-supervised) image segmentation algorithms, which include SegNet and SAM to demonstrate the effectiveness of the proposed framework.