Color Image Segmentation: From the View of Projective Clustering

Color Image Segmentation: From the View of Projective Clustering

Song Gao (The University of Alabama at Birmingham, USA), Chengcui Zhang (The University of Alabama at Birmingham, USA) and Wei-Bang Chen (Virginia State University, USA)
DOI: 10.4018/jmdem.2012070104


An intuitive way of color image segmentation is through clustering in which each pixel in an image is treated as a data point in the feature space. A feature space is effective if it can provide high distinguishability among objects in images. Typically, in the preprocessing phase, various modalities or feature spaces are considered, such as color, texture, intensity, and spatial information. Feature selection or reduction can also be understood as transforming the original feature space into a more distinguishable space (or subspaces) for distinguishing different content in an image. Most clustering-based image segmentation algorithms work in the full feature space while considering the tradeoff between efficiency and effectiveness. The authors’ observation indicates that often time objects in images can be simply detected by applying clustering algorithms in subspaces. In this paper, they propose an image segmentation framework, named Hill-Climbing based Projective Clustering (HCPC), which utilizes EPCH (an efficient projective clustering technique by histogram construction) as the core framework and Hill-Climbing K-means (HC) for dense region detection, and thereby being able to distinguish image contents within subspaces of a given feature space. Moreover, a new feature space, named HSVrVgVb, is also explored which is derived from Hue, Saturation, and Value (HSV) color space. The scalability of the proposed algorithm is linear to the dimensionality of the feature space, and our segmentation results outperform that of HC and other projective clustering-based algorithms.
Article Preview

1. Introduction

Image segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze (Shapiro & Stockman, 2011). Pixels within a segment have high coherence with respect to certain features, such as color, texture, intensity, and spatial information, while pixels from different segments have significant difference in the same feature space or subspace of the space. Image segmentation has been widely applied in a wide spectrum of applications. For example, in the medical field, digital images of histological slides can be used to classify skin biopsies as either melanoma or nevi (Osborne, Gao, Chen, Andea & Zhang, 2011). Image segmentation as the first step is performed to recognize different tissues in the slide. Another example is the Content-based Image Retrieval (CBIR). Users can submit a query based on an uploaded image, or further filter the results, which are returned by the keywords searching, according to their contents. Image segmentation partitions an image into more meaningful contents as “visual keywords” to allow for more powerful queries.

Clustering (Everitt, 2012; Jain, Murty & Flynn, 1999) provides a good way for image segmentation since pixels within the same segment share some common characteristics. The most well-known and classical partitioning algorithm is K-means (Han & Kamber, 2005; MacKay, 2003). Given a set of data points X = (X1, X2,…, Xn), where each data point is a d-dimensional vector. The goal of K-means is to partition the n data points into K groups (Kn) G = (G1, G2, …, GK) so as to minimize the within-cluster sum of squares (criterion function), namely , where mi is the mean of cluster Gi. First, it randomly selects K data points as the initial means or centers of K clusters. Then, the rest of data points are assigned to the most similar clusters, based on a similarity measure (e.g., Euclidean distance) between data points and cluster means. The new mean (center) of each cluster is updated based on assigned data points to the cluster. This process iterates until the criterion function converges or is smaller than a threshold. Most clustering algorithms in image segmentation domain work on the full feature space including single or multiple modalities. Spectral clustering (Ng, Jordan, & Weiss, 2001; Shi & Malik, 2000) starts from transforming the original data matrix into the eigenvectors of matrix, and then detects k well-separated clusters on the surface of the k-sphere. Hill-climbing K-means algorithm (HC) (Ohashi, Aghbari & Makinouchi, 2003) initially discretizes the full feature space (e.g., LUV or HSV color space) in order to find the local maxima by using the hill-climbing technique (Russell & Norvig, 2003). Each local maximum is treated as one of the initial cluster seeds which are the input for the later K-means clustering. On one hand, HC can automatically determine the number of clusters, and effectively generate the segmentation result. On the other hand, HC is a global method, so it cannot find clusters that are best represented in subspaces as shown in Figure 1.

Figure 1.

Optimal segmentation results from certain subspace of HSV by using HC algorithm

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing