=Paper=
{{Paper
|id=Vol-1584/paper9
|storemode=property
|title=Extended Pixel Representation for Image Segmentation
|pdfUrl=https://ceur-ws.org/Vol-1584/paper9.pdf
|volume=Vol-1584
|authors=Deeptha Girish,Vineeta Singh,Anca Ralescu
|dblpUrl=https://dblp.org/rec/conf/maics/GirishSR16
}}
==Extended Pixel Representation for Image Segmentation==
https://ceur-ws.org/Vol-1584/paper9.pdf
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