In [1], image segmentation is treated as a graph-partitioning problem. It proposes a novel global criterion, called normalized cut, for segmenting the graph. The normalized cut criterion measures both the total dissimilarity between the different groups as well as the total similarity within the groups. It suggests that when constructing the weight matrix of graph, we can choose certain percent of points of the graph with little effect on the result of segmentations. In my paper, I attempt to explain this phenomenon in theory and improve on the method of graph partitioning.

References.

[1] Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation.

Footnotes:

¹ Joint work with Prof. Zheyue ZHANG.