Abstract
The Normalized Cut (NCut) objective function, widely
used in data clustering and image segmentation, quantifies
the cost of graph partitioning in a way that biases clusters
or segments that are balanced towards having lower values than unbalanced partitionings. However, this bias is so
strong that it avoids any singleton partitions, even when vertices are very weakly connected to the rest of the graph. Motivated by the Buhler-Hein family of balanced cut costs, we ¨
propose the family of Compassionately Conservative Balanced (CCB) Cut costs, which are indexed by a parameter
that can be used to strike a compromise between the desire to avoid too many singleton partitions and the notion
that all partitions should be balanced. We show that CCBCut minimization can be relaxed into an orthogonally constrained ?? -minimization problem that coincides with the
problem of computing Piecewise Flat Embeddings (PFE)
for one particular index value, and we present an algorithm
for solving the relaxed problem by iteratively minimizing a
sequence of reweighted Rayleigh quotients (IRRQ). Using
images from the BSDS500 database, we show that image
segmentation based on CCB-Cut minimization provides better accuracy with respect to ground truth and greater variability in region size than NCut-based image segmentation