Introduction

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.

Related Work

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

(R G B) (R G B RG RG GB GB BR BR ) (H S V ) (H S V HS HS SV SV V S V S ) (Y Cb Cr) (Y Cb Cr Y Cb Y Cb CbCr CbCr CrY CrY ) (R G B) (H S V ) (R G B H S V Y Cb Cr) (Y Cb Cr)

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.

Current Approach

To illustrate the effect of the extended pixel representation, we consider two experiments as follows.

Sensitivity of distance to the extended space

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. (10, 100, 150), p = (25, 120, 135), p = (30, 125, 130).

Pixel Representation

(p 1 , p 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.

MSE(r, t) = 1 M ⇥ N M n=1 N m=1 [t(n, m) r(n, m)] 2 (1) Snr(t, r) = 10 log 10 M m=1 N n=1 [r(n, m)] 2 M m=1 N n=1 [r(n, m) t(n, m)] 2

(2) where r(n, m) represents the original image and t(n, m) represents the segmented image, both of size [N, M ].

Table 5 shows the results of the segmentation and MSE and Snr for each of these segmentations. Inspecting Table 5 it is observed that for all images, even though the distance measure and the number of clusters were same, the mean square error was lower and correspondingly signal to noise ratio was higher when the extended pixel representation was used. It can be seen that the results look very similar to the original image because the clusters are colored with the mean color of all the pixels in that cluster. It can also be observed that the difference in results when the extended pixel representation is used is higher for images of low contrast. The extended pixel representation also performs better for pictures with high texture content.

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.

Conclusion

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.