Agglomerative connectivity constrained clustering for image segmentation

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


We consider the problem of clustering under the constraint that data points in the same cluster are connected according to a pre-existed graph. This constraint can be efficiently addressed by an agglomerative clustering approach, which we exploit to construct a new fully automatic segmentation algorithm for color photographs. For image segmentation, if the pixel grid with eight neighbor connectivity is imposed as the graph, each group of pixels generated by this clustering method is ensured to be a geometrically connected region in the image, a desirable trait for many subsequent operations. To achieve scalability for images with large sizes, the segmentation algorithm combines the top-down k-means clustering with the bottom-up agglomerative clustering method. We also find that it is advantageous to conduct clustering at multiple stages through which the similarity measure is adjusted. Experimental results with comparison to other widely used and state-of-the-art segmentation methods show that the new algorithm achieves higher accuracy at much faster speed. A software package is provided for public access.

Original languageEnglish (US)
Pages (from-to)84-99
Number of pages16
JournalStatistical Analysis and Data Mining
Issue number1
StatePublished - Feb 2011

All Science Journal Classification (ASJC) codes

  • Analysis
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Agglomerative connectivity constrained clustering for image segmentation'. Together they form a unique fingerprint.

Cite this