The paper is concerned with the development of an unsupervised segmentation algorithm for multispectral images. Due to the high dimensionality of these images, the underlining motivation of this work is on how to build up a robust unsupervised segmentation algorithm with acceptable computational complexity. After an initial approximate segmentation using the EM algorithm, a cost function associated to each pixel is proposed. This function includes a term that measures how close the pixel at hand is to the region's distribution centroids, and another term that measures the local homogeneity in the pixel's neighborhood. In addition, an edge progression technique is used to re-label pixels optimally. Extensive experiments have been carried out on many multispectral images and quantitative results have shown the efficiency of the approach.