Path Based Pairwise Data Clustering with Application to Texture Segmentation
Most cost function based clustering or partitioning methods measure the compactness of groups of data. In contrast to this picture of a point source in feature space, some data sources are spread out on a low-dimensional manifold which is embedded in a high dimensional data space. This property is adequately captured by the criterion of connectedness which is approximated by graph theoretic partitioning methods. 
 
We propose in this paper a pairwise clustering cost function with a novel dissimilarity measure emphasizing connectedness in feature space rather than compactness. The connectedness criterion considers two objects as similar if there exists a mediating intra cluster path without an edge with large cost. The cost function is optimized in a multi-scale fashion. This new path based clustering concept is applied to segment textured images with strong texture gradients based on dissimilarities between image patches.