We explore the use of extended pixel representation for color based image segmentation using the K-means clustering algorithm. Various extended pixel representations have been implemented in this paper and their results have been compared. By extending the representation of pixels an image is mapped to a higher dimensional space. Unlike other approaches, where data is mapped into an implicit features space of higher dimension (kernel methods), in the approach considered here, the higher dimensions are defined explicitly. Preliminary experimental results which illustrate the proposed approach are promising.
Image segmentation is a key processes in image analysis. This step is done irrespective of the goal of the analysis. It is one of the most critical tasks in this process. The aim of segmentation is to divide the image into non overlapping areas such that all pixels in one segment have similar features. This representation makes the image more meaningful and makes its analysis and understanding easier. For example, in medical images each color represents a particular stain that is essentially a protein binder that binds to a certain type of molecule. Therefore the different clusters obtained after segmenting such an image according to color can help us identify different biological components in that image. This can help us to do further analysis like finding meta data about each of the structures, finding one structures relative position to the other etc. One way to achieve this is to cluster similar pixels into one cluster. Therefore, what defines similarity and how it is calculated becomes very important. A lot of research has been done on finding similarity measures for images and videos (Wang et al.(2005)Wang, Zhang, and Feng), (Huttenlocher et al.(1993)Huttenlocher, Klanderman, and Rucklidge), (Gualtieri et al.(1992)Gualtieri, Le Moigne, and Packer). It is important that the measure we use captures the slightest difference in pixels. This plays an essential role in segmentation. K-means (MacQueen et al.(1967)) is a popular algorithm that works well for image segmentation. The aim of the K-means algorithm as stated by Hartigan ET. al. (Hartigan and Wong(1979)) is to divide M points in N dimensions into K clusters so that the within-cluster sum of squares distances is minimized. Thus, distance is an important factor. One of the major difficulties of image segmentation is to differentiate two similar regions which actually belong to different segments. This is because the existing features and the standard distances used to measure the dissimilarity do not capture the small differences very well. Increasing the sensitivity to small differences is the motivation for using the extended pixel representation. Image data is displayed on a computer as a bitmap which is a rectangular arrangement of pixels. The number of bits used to represent individual pixel has increased over the recent years, as computers have become more powerful. Todays computer systems often use a 24 bit color system. The most common color system in use is the RGB space (Red, Green and Blue).
Selecting the right color space for segmentation can be very important. Different parts of the image get highlighted better in different color spaces. It is also dependent on the purpose of the segmentation. To simplify this choice of color space, it is better to know in advance the features that represent maximum variation. This can be done by finding the coefficient of variation for each of the features of different color spaces. For a given data set, the coefficient of variation, defined as the ratio of standard deviation to the mean, represents the variability within the data set with respect to the mean. When selecting features/dimensions, it then makes sense to to take into consideration the coefficient of variation, more precisely, to select the features that have the highest variability. In selecting a color space, it is usual to adopt one (e.g., RGB, HSV) space. This study departs from this policy by selecting more than one color spaces, which further helps in better differentiate between pixels.
The idea of extended pixel representation has been used previously to detect and repair halo in images (Ohshima et al.(2006)Ohshima, Ralescu, Hirota, and Ralescu), to calculate the degree of difference between pixels in color images in order to identify the halo region. The extended pixel representation used in (Ohshima et al.(2006)Ohshima, Ralescu, Hirota, and Ralescu) is described next. Given a pixel p in the image I, its extended pixel representation of p, is the real-valued vector (R, G, B, RG, RG, GB , GB , BR, BR) where RGB are pixel values in the RGB color space, and XY and XY are the polar coordinates in the two dimensional color space, (X, Y ), with X, Y R, G, B, X = Y . This representation better support image segmentation because it captures the difference between pixels more accurately. In particular, it gives much better results for images with low contrast. The same extended pixel representation can be implemented in other color spaces as well, as our experimental results for HSV , which uses H for Hue, synonymous to color, S for Saturation, the colorfulness of a color relative to its own brightness, and V for Value which refers to the lightness or darkness of a color. It is known that for most images, HSV color space is more suitable for segmentation and we show that the extended pixel representation for HSV improves the results even for this color space. The Y CbCr space uses Y for Luminance, the brightness of light, C for Chrominance, the color information of the signal, which is stored as two color-difference components (Cb and Cr). Table 1 shows the features for each color space used in the experiments.
To illustrate the effect of the extended pixel representation, we consider two experiments as follows.
Two pixels which are almost of the same color and having very similar R, G and B values are selected and their corresponding values in each of the extended pixel representations considered are calculated, using both the Euclidean distance and Manhattan distance. It is seen that the extended pixel representations are more sensitive to the dissimilarity between the pixels irrespective of the distance measure used. This is the idea behind using extended pixel representation. Especially for tasks like segmentation, this is a very efficient way to separate two samples which have similar feature values into different clusters.
Table 2 shows the results for computing the distance between the two fixed pixels, in three standard color spaces, their extensions, and in an extended representation based on three color spaces.
HS HS SV SV V S V S ) (H S V ) (H S V % of change % of change (Y Cb Cr) 29.15 (Y Cb Cr Y Cb Y Cb CbCr CbCr CrY CrY ) 48.24 (R G B H S V Y Cb Cr) % of change with respect to average distances for the original color spaces Obviously, all distances in the extended space should be larger than those in the original space, because adding more features to the pixel representation in effects adds positive quantities to each of the distances considered and therefore this experiment merely confirms that theoretical fact.
A second small experiment was run as follows. Starting with two pixels p, and p , ED and MD were computed just as in the previous section. Then p2 was altered slightly, to obtain p , and the same distances were computed for p and p , and compared with those computed for p and p . Tables 3 and 4 show the results. between pixels (in original color space and extended space) was used. For every image, the number of clusters was decided visually. The same number of clusters was used for all the extended pixel representations. The mean square error, equation (1) and the signal to noise ratio, equation (2) are calculated.
M SE(r, t) =
1 M ⇥ N
M
N
The smaller changes in color values of the pixels are separated and recognized better in extended pixel representations. Irrespective of the color space used, the extended pixel representation gives lower mean squared error and higher signal to noise ratio than the standard pixel representation for all images. All pixels that are similar in color get clustered into one segment which might represent a particular structure in the image. Thus, this representation adds more meaning to the image.
The segmentation problem considered in this paper can be addressed by using the extended pixel representations.
The idea of representing each pixel with more information proved to be successful for image segmentation. It was observed that extended pixel representation can more effectively distinguish similar pixels. Although in the second experiment, it was seen that the percentage change of the euclidean distance between the extended pixel representation and the standard pixel representation when p was changed to p is very small, the effect turns out to be significant in the clustering step.With the same number of clusters and the same distance measure used, the mean square of the segmentation done using the extended pixel representation is lower for all images.
The promising experimental results of this idea encourages exploration of other extended pixel representations in the future. It will be interesting to include texture information like edges or frequency domain information as part of the pixel representation. Tailoring the extended pixel representations for the task in hand and automatic learning of the most important features and optimal number of features to represent a pixel for a particular task is an important idea to be considered for future work. a) RGB
Snr=35.3260db MSE=0.0050 b) HSV
Snr=54.8959db MSE = 0.0035
Snr=55.8133db MSE=0.0031 a) RGB RG RG GB GB BR BR b) HSV HS HS SV SV VH VH
Snr=39.3334db MSE=0.0033 Snr=56.1241db MSE=0.0026 Snr=58.8801db MSE=0.0015 a)
Snr=37.4722db MSE=0.0173
MSE=0.0021 c)
d) RGB
Snr=47.4465db MSE=0.0014 e) HSV
Snr=44.0748db MSE=0.0062
Snr=54.3042db MSE=0.00075 d) RGB RG RG GB GB BR BR e) HSV HS HS SV SV VH VH
Snr=49.2535db MSE=0.0012 Snr=47.3483db MSE=0.0044 Snr=54.9753db MSE=0.0007
MSE=0.0038