Deeptha Girish et al. MAICS 2016 pp. 63–67 Extended Pixel Representation for Image Segmentation Deeptha Girish, Vineeta Singh, Anca Ralescu EECS Department University of of Cincinnati Cincinnati, OH 45221-0030, USA girishde@mail.uc.edu, singhvi@mail.uc.edu, anca.ralescu@uc.edu Abstract in N dimensions into K clusters so that the within-cluster sum of squares distances is minimized. Thus, distance is We explore the use of extended pixel representation an important factor. One of the major difficulties of image for color based image segmentation using the K-means clustering algorithm. Various extended pixel represen- segmentation is to differentiate two similar regions which tations have been implemented in this paper and their actually belong to different segments. This is because the results have been compared. By extending the repre- existing features and the standard distances used to measure sentation of pixels an image is mapped to a higher di- the dissimilarity do not capture the small differences very mensional space. Unlike other approaches, where data well. Increasing the sensitivity to small differences is the is mapped into an implicit features space of higher di- motivation for using the extended pixel representation. mension (kernel methods), in the approach considered Image data is displayed on a computer as a bitmap which here, the higher dimensions are defined explicitly. Pre- is a rectangular arrangement of pixels. The number of bits liminary experimental results which illustrate the pro- used to represent individual pixel has increased over the posed approach are promising. recent years, as computers have become more powerful. Todays computer systems often use a 24 bit color system. Introduction The most common color system in use is the RGB space Image segmentation is a key processes in image analysis. (Red, Green and Blue). 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 Selecting the right color space for segmentation can segmentation is to divide the image into non overlapping be very important. Different parts of the image get high- areas such that all pixels in one segment have similar lighted better in different color spaces. It is also dependent features. This representation makes the image more mean- on the purpose of the segmentation. To simplify this choice ingful and makes its analysis and understanding easier. of color space, it is better to know in advance the features For example, in medical images each color represents a that represent maximum variation. This can be done by particular stain that is essentially a protein binder that finding the coefficient of variation for each of the features binds to a certain type of molecule. Therefore the dif- of different color spaces. For a given data set, the coefficient ferent clusters obtained after segmenting such an image of variation, defined as the ratio of standard deviation to according to color can help us identify different biological the mean, represents the variability within the data set with components in that image. This can help us to do further respect to the mean. When selecting features/dimensions, it analysis like finding meta data about each of the struc- then makes sense to to take into consideration the coefficient tures, finding one structures relative position to the other etc. of variation, more precisely, to select the features that have the highest variability. In selecting a color space, it is usual One way to achieve this is to cluster similar pixels to adopt one (e.g., RGB, HSV) space. This study departs into one cluster. Therefore, what defines similarity and how from this policy by selecting more than one color spaces, it is calculated becomes very important. A lot of research which further helps in better differentiate between pixels. 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 Related Work Rucklidge), (Gualtieri et al.(1992)Gualtieri, Le Moigne, and The idea of extended pixel representation has been used Packer). It is important that the measure we use captures previously to detect and repair halo in images (Ohshima the slightest difference in pixels. This plays an essential et al.(2006)Ohshima, Ralescu, Hirota, and Ralescu), role in segmentation. K-means (MacQueen et al.(1967)) is a to calculate the degree of difference between pixels popular algorithm that works well for image segmentation. in color images in order to identify the halo region. The aim of the K-means algorithm as stated by Hartigan The extended pixel representation used in (Ohshima ET. al. (Hartigan and Wong(1979)) is to divide M points et al.(2006)Ohshima, Ralescu, Hirota, and Ralescu) is 63 Deeptha Girish et al. MAICS 2016 pp. 63–67 Table 1: The original and extended color spaces Table 2: Euclidean distance (ED) and Manhattan distance Original Extended (MD) for two fixed pixels in the original and extended color Color Space Color Space spaces, and the percentage of change due to the extended (R G B) (R G B RG RG GB GB BR BR ) representation. (H S V ) (H S V HS HS SV SV V S V S ) Pixel Representation ED MD (Y Cb Cr) (Y Cb Cr Y Cb Y Cb CbCr CbCr CrY CrY ) (R G B) 54.08 75.00 (R G B) (R G B RG RG GB GB BR BR 80.47 ) 175.40 (H S V ) (R G B H S V Y Cb Cr) % of change 48.78 133.86 (Y Cb Cr) (H S V ) 5.00 5.13 (H S V HS HS SV SV V S V S ) 8.59 15.17 % of change 71.69 195.62 described next. Given a pixel p in the image I, its ex- (Y Cb Cr) 29.15 32.81 tended pixel representation of p, is the real-valued vector (Y Cb Cr Y Cb Y Cb CbCr CbCr CrY CrY ) 48.24 92.10 (R, G, B, RG , RG , GB , GB , BR , BR ) where RGB are % of change 65.52 180.72 pixel values in the RGB color space, and XY and XY are (R G B H S V Y Cb Cr) 61.64 112.94 the polar coordinates in the two dimensional color space, % of change with respect to average dis- 109.58 200.00 (X, Y ), with X, Y R, G, B, X = Y . This representation tances for the original color spaces 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. Obviously, all distances in the extended space should The same extended pixel representation can be imple- be larger than those in the original space, because adding mented in other color spaces as well, as our experimental more features to the pixel representation in effects adds results for HSV , which uses H for Hue, synonymous to positive quantities to each of the distances considered and color, S for Saturation, the colorfulness of a color relative therefore this experiment merely confirms that theoretical to its own brightness, and V for Value which refers to the fact. lightness or darkness of a color. It is known that for most images, HSV color space is more suitable for segmentation Sensitivity of the distance in the original and and we show that the extended pixel representation for extended space when the pixel changes HSV improves the results even for this color space. The A second small experiment was run as follows. Starting with Y CbCr space uses Y for Luminance, the brightness of two pixels p, and p , ED and MD were computed just as in light, C for Chrominance, the color information of the the previous section. Then p2 was altered slightly, to obtain signal, which is stored as two color-difference components p , and the same distances were computed for p and p , and (Cb and Cr). Table 1 shows the features for each color space compared with those computed for p and p . Tables 3 and 4 used in the experiments. show the results. Current Approach Table 3: Changes in the Euclidean Distance (ED) when To illustrate the effect of the extended pixel representation, the pixel p changes to p . RGB pixel values are p = we consider two experiments as follows. (10, 100, 150), p = (25, 120, 135), p = (30, 125, 130). Pixel Representation (p1 , p ) (p1 , p ) diff % Sensitivity of distance to the extended space Two pixels which are almost of the same color and having (R G B) 29.15 37.75 29.48 very similar R, G and B values are selected and their cor- (R G B RG RG GB GB BR BR ) 54.77 71.24 30.06 responding values in each of the extended pixel represen- (H S V ) 15.00 20 33.29 tations considered are calculated, using both the Euclidean (H S V HS HS SV SV VS VS ) 25.89 34.52 33.32 distance and Manhattan distance. It is seen that the extended (Y Cb Cr) 19.22 24.74 28.68 pixel representations are more sensitive to the dissimilarity (Y Cb Cr Y Cb Y Cb CbCr CbCr CrY CrY ) 38.40 49.43 28.70 between the pixels irrespective of the distance measure used. (R G B H S V Y Cb Cr) 38.01 49.36 29.88 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 val- ues into different clusters. Experiments and Results Table 2 shows the results for computing the distance Segmentation using the k-means algorithm was imple- between the two fixed pixels, in three standard color spaces, mented for three different images. Each image is in a dif- their extensions, and in an extended representation based on ferent color space. Segmentation using K-means was done three color spaces. on these images using the standard pixel representation and the extended pixel representation. The Euclidean distance 64 Deeptha Girish et al. MAICS 2016 pp. 63–67 The idea of representing each pixel with more information Table 4: Changes in the Manhattan Distance (ED) when proved to be successful for image segmentation. It was the pixel p changes to p . RGB pixel values are p = observed that extended pixel representation can more (10, 100, 150), p = (25, 120, 135), p = (30, 125, 130). effectively distinguish similar pixels. Although in the Pixel Representation (p1 , p ) (p1 , p ) diff % second experiment, it was seen that the percentage change of the euclidean distance between the extended pixel (R G B) 50 65 30 representation and the standard pixel representation when (R G B RG RG GB GB BR BR ) 120.3 155.4 29.17 p was changed to p is very small, the effect turns out to (H S V ) 15.15 20.22 33.39 be significant in the clustering step.With the same number (H S V HS HS SV SV VS VS ) 45.11 60.16 33.36 of clusters and the same distance measure used, the mean (Y Cb Cr) 27.40 35.82 30.73 square of the segmentation done using the extended pixel (Y Cb Cr Y Cb Y Cb CbCr CbCr CrY CrY ) 82.13 106.1 29.22 representation is lower for all images. (R G B H S V Y Cb Cr) 92.55 121.0 30.77 The promising experimental results of this idea en- courages exploration of other extended pixel representations between pixels (in original color space and extended space) in the future. It will be interesting to include texture was used. For every image, the number of clusters was de- information like edges or frequency domain information cided visually. The same number of clusters was used for all as part of the pixel representation. Tailoring the extended the extended pixel representations. The mean square error, pixel representations for the task in hand and automatic equation (1) and the signal to noise ratio, equation (2) are learning of the most important features and optimal number calculated. of features to represent a pixel for a particular task is an M N important idea to be considered for future work. 1 M SE(r, t) = [t(n, m) r(n, m)]2 (1) M ⇥ N n=1 m=1 References JA Gualtieri, J Le Moigne, and CV Packer. Distance be- M N 2 m=1 n=1 [r(n, m)] tween images. In Frontiers of Massively Parallel Computa- Snr(t, r) = 10 log10 M N tion, 1992., Fourth Symposium on the, pages 216–223. IEEE, m=1 n=1 [r(n, m) t(n, m)]2 1992. (2) John A Hartigan and Manchek A Wong. Algorithm AS 136: where r(n, m) represents the original image and t(n, m) A k-means clustering algorithm. Journal of the Royal Sta- represents the segmented image, both of size [N, M ]. tistical Society. Series C (Applied Statistics), 28(1):100–108, 1979. Table 5 shows the results of the segmentation and M SE Daniel P Huttenlocher, Gregory A Klanderman, and and Snr for each of these segmentations. Inspecting Table William J Rucklidge. Comparing images using the Hausdorff 5 it is observed that for all images, even though the distance distance. Pattern Analysis and Machine Intelligence, IEEE measure and the number of clusters were same, the mean Transactions on, 15(9):850–863, 1993. square error was lower and correspondingly signal to noise James MacQueen et al. Some methods for classification ratio was higher when the extended pixel representation and analysis of multivariate observations. In Proceedings of was used. It can be seen that the results look very similar the fifth Berkeley symposium on mathematical statistics and to the original image because the clusters are colored with probability, volume 1, pages 281–297. Oakland, CA, USA., 1967. the mean color of all the pixels in that cluster. It can also be observed that the difference in results when the extended Chihiro Ohshima, Anca Ralescu, Kaoru Hirota, and Dan Ralescu. Processing of halo region around a light source pixel representation is used is higher for images of low in color images of night scenes. In Proc. of the Conference contrast. The extended pixel representation also performs IPMU, volume 6, pages 2–7, 2006. better for pictures with high texture content. Liwei Wang, Yan Zhang, and Jufu Feng. On the Euclidean distance of images. Pattern Analysis and Machine Intelli- The smaller changes in color values of the pixels are gence, IEEE Transactions on, 27(8):1334–1339, 2005. separated and recognized better in extended pixel rep- resentations. 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. 65 Deeptha Girish et al. MAICS 2016 pp. 63–67 Table 5: Results on segmentation of six images, using each of the three color spaces separately (2nd row), extended pixel representation (3rd row), and all three color spaces (4th row). Bold font indicates the smallest MSE. ` c) Original Image a) Original Image b) Original Image a) RGB b) HSV c) YCbCr Snr=35.3260db Snr=54.8959db Snr=55.8133db MSE=0.0050 MSE = 0.0035 MSE=0.0031 a) RGBURG TRG UGB TGB UBR TBR b) HSVUHS THS USV TSV UVH TVH c) YCbCrUYCb TYCb UCbCr TCbCr UCrY TCrY Snr=39.3334db Snr=56.1241db Snr=58.8801db MSE=0.0033 MSE=0.0026 MSE=0.0015 a) RGB HSV YCbCr b) RGB HSV YCbCr c) RGB HSV YCbCr Snr=37.4722db Snr=57.064db Snr=35.4811db MSE=0.0173 MSE=0.0021 MSE=0.0173 66 Deeptha Girish et al. MAICS 2016 pp. 63–67 d) Original Image e) Original Image f) Original Image d) RGB e) HSV f) YCbCr Snr=47.4465db Snr=44.0748db Snr=54.3042db MSE=0.0014 MSE=0.0062 MSE=0.00075 d) RGBURG TRG UGB TGB UBR TBR e) HSVUHS THS USV TSV UVH TVH f) YCbCrUYCb TYCb UCbCr TCbCr UCrY TCrY Snr=49.2535db Snr=47.3483db Snr=54.9753db MSE=0.0012 MSE=0.0044 MSE=0.0007 d) RGB HSV YCbCr e) RGB HSV YCbCr e) RGB HSV YCbCr Snr=48.1598db Snr=26.9429db Snr=32.4912db MSE=0.0013 MSE=0.0038 MSE=0.0037 67