This paper proposes a methodology that incorporates principles from cluster analysis and graph representation to achieve efficient image segmentation results. More specifically, a feature-based, inter-region dissimilarity relation is considered here in order to determine the dissimilarity matrix in a graph-based segmentation scheme. The calculation of the dissimilarity function between adjacent elementary image regions is based on the proximity of each region's feature vector to the main clusters that are formed by the image samples in the feature space. In contrast to typical segmentation approaches of the literature, the global feature space information is included in the spatial graph representation that was derived from the initial Watershed partitioning. A region grouping process is applied next to form the final segmentation results. The proposed approach was also compared to approaches that use feature-based, or spatial information exclusively, to indicate its effectiveness.