Elsevier

Pattern Recognition Letters

Volume 32, Issue 2, 15 January 2011, Pages 359-367
Pattern Recognition Letters

A de-texturing and spatially constrained K-means approach for image segmentation

https://doi.org/10.1016/j.patrec.2010.09.016Get rights and content

Abstract

This paper presents a new and simple segmentation method based on the K-means clustering procedure and a two-step process. The first step relies on an original de-texturing procedure which aims at converting the input natural textured color image into a color image, without texture, that will be easier to segment. Once, this de-textured (color) image is estimated, a final segmentation is achieved by a spatially-constrained K-means segmentation. These spatial constraints help the iterative K-means labeling process to succeed in finding an accurate segmentation by taking into account the inherent spatial relationships and the presence of pre-estimated homogeneous textural regions in the input image. This procedure has been successfully applied on the Berkeley image database. The experiments reported in this paper demonstrate that the proposed method is efficient (in terms of visual evaluation and quantitative performance measures) and performs competitively compared to the best existing state-of-the-art segmentation methods recently proposed in the literature.

Research highlights

► An efficient segmentation procedure based on the K-means. ► The clustering is done on a de-textured image. ► Some spatial constraints are added to this procedure. ► Simple to implement and performs competitively.

Introduction

Image segmentation is an important pre-processing step which consists in dividing the image scene into spatially coherent regions sharing similar attributes. This preliminary low-level vision task has been widely studied in the last decades since it is of critical importance in many image understanding algorithms, computer vision and graphics applications. Presently, the problem of finding a fast, simple and automatic method, able to efficiently segment a color textured image remains open.

Due to their simplicity and efficiency, clustering approaches were one of the first techniques used for the segmentation of (textured) natural images (Banks, 1990). After the selection and the extraction of the image features (usually based on color and/or texture and computed on (possibly) overlapping small windows centered around the pixel to be classified), the feature samples, handled as vectors, are grouped together in compact but well-separated clusters corresponding to each class of the image. The set of connected pixels belonging to each estimated class thus defined the different regions of the scene. The method known as K-means (or Lloyd’s algorithm) (Lloyd, 1982) (and its fuzzy version called fuzzy C-means) are some of the most commonly used techniques in the clustering-based segmentation field, and more generally, “by far, the most popular clustering algorithm used in industrial applications and machine learning” (Berkhin, 2002).

Nevertheless, despite its popularity for general clustering, K-means suffers from three major shortcomings for the difficult problem of the unsupervised segmentation of textured color image;

  • (1)

    First, this clustering utilizes an iterative procedure that converges monotonically to a local minima. This convergence to a bad local solution may be due either (or both) to a bad initialization (i.e., a bad choice of the initial cluster centers) or to the complexity or to the high-dimensional of the dataset (such as the high dimensional feature descriptors required to characterize different color textures).

  • (2)

    Such clustering method only involves a partitioning in the feature space without (at all) considering spatial constraints. This considerably reduces the efficiency of this algorithm for the image segmentation issue. Since spatial relationships are essential attributes of any image, spatial constraints should be necessarily taken into account to achieve an efficient noise robust image segmentation.

  • (3)

    Finally, the K-means assumes, often wrongly, the presence of spherical clusters with equal volumes (or equivalently, the shapes of each feature distribution associated to each class are assumed to be Gaussian with identical variance).

In this paper, we propose an original and simple segmentation strategy based on the K-means procedure that remedies these above-enumerated problems. First, in order to apply the K-means clustering algorithm in a reduced dimension space, in which the search of well-separated clusters can converge faster to a better local minima (related to a more accurate segmentation map), we propose, in a first step, to simplify the input color textured image into a color image without texture. Thanks to this pre-processing step (that we will call in the following a de-texturing procedure) the difficult textured image segmentation problem (which necessarily should use a set of high dimensional texture feature descriptors) is reduced to solving a (noisy) color image segmentation which is drastically less complex than a color textured image segmentation problem.

In our application, this de-texturing procedure is simply based on a simple combination of several K-means segmentations applied on the input image expressed by different color spaces and using, as input multidimensional feature descriptor, the set of values of the re-quantized color histogram estimated around the pixel to be classified. Once, a de-textured (color) image is estimated, the final segmentation is simply achieved by a spatially-constrained K-means segmentation using, as simple cues, a feature vector with the set of color values contained around the pixel to be classified. The spatial constraint allows to take into account the inherent spatial relationships of any image and helps the iterative K-means labeling process to succeed in finding an optimal solution, i.e., an accurate segmentation map.

The remainder of this paper is organized as follows: Section 2 describes the proposed model i.e., the so-called de-texturing procedure and the spatially constrained K-means segmentation model. Finally, Section 3 presents a set of experimental results and comparisons with existing segmentation techniques.

Section snippets

De-texturing procedure

This de-texturing approach (described in Algorithm 2) is a three-step process as follows:

  • (1)

    The first step is simply based on a K-means segmentation of the input image using the Manhattan distance (L1 norm) and as simple cues (i.e., as input multidimensional feature descriptor) the set of values of the re-quantized color histogram, with equidistant binning, estimated around each pixel to be classified. In our application, this local histogram is equally re-quantized (for each of the three color

Set up

In all the experiments, in order to promote diversity in the K-means segmentation results or in the different estimated edge maps (and also to somewhat increase the accuracy around the boundaries between distinct texture regions, after the averaging process), we have considered ten (Ns = 10) different color spaces (each color channel has been normalized between 0 and 255), namely RGB, HSV, YIQ, XYZ, LAB, LUV, I1I2I3, H1H2H3, YCbCr, TSL, (Martinkauppi et al., 2001, Banks, 1990, Braquelaire and

Conclusion

In this paper, we have presented an original, simple and efficient segmentation procedure based on the K-means procedure. The proposed method overcomes the inherent problems of this simple automatic clustering procedure using spherical distributions on the difficult problem of the textured color image segmentation. First, the clustering is done on a simplified (de-textured image), on which the search of well-separated clusters is easier. Besides, some spatial constraints help the iterative K

References (20)

  • A.Y. Yang et al.

    Unsupervised segmentation of natural images via lossy data compression

    Comput. Vision and Image Understanding

    (2008)
  • S. Banks

    Signal Processing, Image Processing and Pattern Recognition

    (1990)
  • Berkhin, P., 2002. Survey of Clustering Data Mining Techniques. Technical Report, Accrue Software, San Jose,...
  • J.-P. Braquelaire et al.

    Comparison and optimization of methods of color image quantization

    IEEE Trans. Image Process.

    (1997)
  • D. Comaniciu et al.

    Mean shift: A robust approach toward feature space analysis

    IEEE Trans. Pattern Anal. Machine Intell.

    (2002)
  • Y. Deng et al.

    Unsupervised segmentation of color-texture regions in images and video

    IEEE Trans. Pattern Anal. Machine Intell.

    (2001)
  • P. Felzenszwalb et al.

    Efficient graph-based image segmentation

    Internat. J. Comput. Vision

    (2004)
  • Freixenet, J., Munoz, X., Raba, D., Marti, J., Cufi, X., 2002. Yet another survey on image segmentation: Region and...
  • D.E. Ilea et al.

    Ctex – An adaptive unsupervised segmentation algorithm on color-texture coherence

    IEEE Trans. Image Process.

    (2008)
  • M. Krinidis et al.

    Color texture segmentation based on the modal energy of deformable surfaces

    IEEE Trans. Image Process.

    (2009)
There are more references available in the full text version of this article.

Cited by (0)

View full text