A de-texturing and spatially constrained K-means approach for image segmentation
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)
- et al.
Unsupervised segmentation of natural images via lossy data compression
Comput. Vision and Image Understanding
(2008) Signal Processing, Image Processing and Pattern Recognition
(1990)- Berkhin, P., 2002. Survey of Clustering Data Mining Techniques. Technical Report, Accrue Software, San Jose,...
- et al.
Comparison and optimization of methods of color image quantization
IEEE Trans. Image Process.
(1997) - et al.
Mean shift: A robust approach toward feature space analysis
IEEE Trans. Pattern Anal. Machine Intell.
(2002) - et al.
Unsupervised segmentation of color-texture regions in images and video
IEEE Trans. Pattern Anal. Machine Intell.
(2001) - 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...
- et al.
Ctex – An adaptive unsupervised segmentation algorithm on color-texture coherence
IEEE Trans. Image Process.
(2008) - et al.
Color texture segmentation based on the modal energy of deformable surfaces
IEEE Trans. Image Process.
(2009)