Segmentation of noisy or textured images remains challenging in both accuracy and computational efficiency. In this paper, we propose a new approach for segmentation of noisy or textured images that exist widely in real life. The proposed approach finds the mean values of different pixel classes more efficiently and accurately than the benchmark expectation maximization (EM) and K-means methods. With these mean values, the segmentation is achieved by clustering the pixels to its nearest mean. When too much noise is left for the presegmentation result or when textured objects are involved, we propose transforming the density distribution of labeled pixels into grayscale distribution by down-sampling the image with a bicubic function. An optimal threshold is automatically selected from the slope difference distribution of the histogram for the final segmentation. The extracted boundary is then refined by an energy minimization function with the detected edges when enough clear edges can be obtained. A large variety of images are used to validate the proposed approach, and the results verify its effectiveness in segmenting both noisy and textured images.