This paper presents a new approach for the segmentation of color-textured images, which is based on a novel, perceptually adapted K-means algorithm and a multidimensional multistep region growing technique. The method consists of several steps. Perceptually adapted K-means clustering algorithm is performed to determine the N reference colors of the desired region. Texture features are computed using the energy of some low order statistical moments Then, an N-dimensional multi-step region growing procedure controlled by texture is performed with the automatically extracted seeds by computing, for each new pixel in the image, its perceptual distance to the reference colors, that is, computing the CIEDE 2000 color distance in the L*a*b* color space to the colors that compound the multicolored texture, rather than Euclidean distance in a non-uniform color space. The method has an adaptive structure due to the growth tolerance parameter that changes with a step size that depends on the mean of the variance for each reference color of the actual grown region. Contrast is also introduced to decide which value of this tolerance parameter is taken, choosing the one that provides the region with the highest mean contrast in relation to the background. Using these tools, a set of 80 natural images is considered. To validate the segmentation results obtained, a comparison with state-of-the-art color-texture based algorithms has been completed. The proposed technique outperformed the published ones achieving a Recall value of 0.757 and a Precision value of 0.812.