Color image segmentation plays an important role in the computer vision and image processing area. In this paper, we propose a novel color image segmentation algorithm in consideration of human visual sensitivity for color pattern variations by generalizing K-means clustering. Human visual system has different color perception sensitivity according to the spatial color pattern variation. To reflect this effect, we define the CCM (Color Complexity Measure) by calculating the absolute deviation with Gaussian weighting within the local mask and assign weight value to each color vector using the CCM values. Weighted color vectors are used in K-Means algorithm and the shape and the center position of each cluster is formed according to the color distribution in the image. We adaptively determine optimal K value, which is the number of cluster, by using the statistics of the color complexity measure that implies the complexity of the color image. The experimental results show that proposed algorithm segments the color image preserving significant features while removing unimportant details.