Normalized cutswith soft must-link constraints for image segmentation and clustering

Segmentation and clustering are common pre-processing tasks in many image understanding and computer vision applications. In some of these applications, expert users can often provide knowledge about which pixels or regions in an image should be grouped together, guiding the clustering or segmentation process to yield more meaningful results than could be achieved by fully automatic algorithms. In this paper, we discuss a popular clustering algorithm, Normalized Cuts, and we show that with a simple modification, it can be generalized to incorporate expert knowledge in the form of soft must-link constraints that give partial information about how pixels or regions should be grouped. By illustrating how our proposed algorithm performs on the tasks of clustering synthetic data, segmenting real photographic images, and classifying regions in hyperspectral imagery, we show that incorporating expert knowledge can significantly improve results in many settings.