This paper proposes a new enhancement and efficient approach for diminution of iterations in K-Means algorithm. Also a quantized color and gray scale histograms are used for HSV color environments to reduce the process of image segmentation. As an apposed to traditional K-Means technique, in the suggested approach the initial centroids are automatically designated by an effective set of relations. Thus, pixel clustering process is only necessary to be done once after discovering all the centroids. Experimental results show that the new enhanced proposed approach gives better outcome in terms of speed and the results got from this research is closer to human visual perception from the colors.