This question is not directly related to this paper.
From the image segmentation and scene understanding point of view, norm in the cost function used here will probably correspond to euclidean distances in some feature space. Has there been any work to accomodate the importance of clusters representing some semantically meaningful objects? E.g. an image segment representing a person may consist of features which are not necesarily close to each other but together they form a meaningful cluster.