Investigation of Measures for Grouping by Graph Partitioning

Abstract

Grouping by graph partitioning is an effective engine for perceptual organization. This graph partitioning process, mainly motivated by computational efficiency considerations, is usually implemented as recursive bi-partitioning, where at each step the graph is broken into two parts based on a partitioning measure. We study four such measures, namely, the minimum cut, average cut, Shi-Malik normalized cut, and a variation of the Shi-Malik normalized cut. Using probabilistic analysis we show that the minimization of the average cut and the normalized cut measure, using recursive bi-partitioning will, on an average, result in the correct segmentation. The minimum cut and the variation of the normalized cut will, on an average, not result in the correct segmentation and we can precisely express the conditions. Based on a rigorous empirical evaluation, we also show that, in practice, the quality of the groups generated using minimum, average or normalized cuts are statistically equivalent for object recognition, i.e. the best, the mean, and the variation of the qualities are statistically equivalent. We also find that for certain image classes, such as aerial and scenes with man-made objects in man-made surroundings, the performance of grouping by partitioning is the worst, irrespective of the cut measure.