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

Area of Science:

• Computer Vision
• Image Processing
• Machine Learning

Background:

• Normalized Cut (NCut) or Spectral Clustering (SC) uses volume constraints to prevent isolated segmentation, but this can be computationally challenging or undesirable.
• Existing methods may struggle with controlling isolated segmentation effectively.

Purpose of the Study:

• To introduce the K-way constrained Normalized Cut (K-way CNCut) for improved image segmentation.
• To establish a link between K-way CNCut and algebraic multigrid (AMG) methods for enhanced functionality.
• To develop an automatic image segmentation algorithm based on the proposed framework.

Main Methods:

• Formulated K-way CNCut as a minimum Cut problem with user-defined constraints or cluster representatives.
• Established a connection between K-way CNCut and the construction of optimal prolongation operators in energy minimizing AMG for normalized Graph Laplacian.
• Utilized multilevel coarsening algorithms from AMG to construct constraints for K-way CNCut, enabling automatic segmentation.

Main Results:

• Demonstrated that K-way CNCut can both discourage and encourage isolated segmentation based on constraint selection.
• Showcased the link to AMG, enabling the construction of constraints via multilevel coarsening for fully automatic segmentation.
• Numerical experiments showed K-way CNCut's effectiveness compared to state-of-the-art segmentation algorithms like SegNet and SAM.

Conclusions:

• K-way CNCut provides a flexible and powerful framework for image segmentation with controllable isolation.
• The discovered link with AMG facilitates automatic constraint generation and fully automatic segmentation.
• The proposed method shows significant potential for advancing image segmentation techniques.