2017 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom)

and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData)

Towards A Hybrid Approach of K-means and

Density-Based Spatial Clustering of Applications
with Noise for Image Segmentation
Chun Guan Kevin Kam Fung Yuen Qi Chen
Department of Computer Science Department of Computer Science Department of Computer Science
University of Liverpool and Software Engineering and Software Engineering
Liverpool, UK Xi’an Jiaotong-Liverpool University Xi’an Jiaotong-Liverpool University
Department of Computer Science Suzhou, China Suzhou, China
and Software Engineering [email protected] [email protected]
Xi’an Jiaotong-Liverpool University
Suzhou, China
[email protected]

Abstract— Image segmentation is the process to divide a digital K-means algorithm is then adopted to cluster the pixels into a
image into a number of regions for further analysis in the area of number of small clusters whilst the centroid of each cluster is to
computer vision. Color images can be segmented by applying group the data points with similar aggregated features values.
various clustering algorithms such as DBSCAN, which can The clusters centroids produced by K-means are further
identify the arbitrary shaped clusters. The drawback of DBSCAN clustered by DBSCAN. The image segmentation results are
is the high computational complexity whilst the sizes of image finally provided by fusing the results of K-means and DBSCAN.
datasets are normally very large. This paper proposes a hybrid To demonstrate the usability of the proposed method, four
method of K-means and DBSCAN (Kmeans-DBSCAN) for image images selected from Berkeley Segmentation Dataset and
segmentation. K-means is the common partition-based clustering
Benchmark (BSDB) [10] were used in the experiment.
approach to reduce the size of image dataset. Four benchmarking
image segmentation cases are used for evaluating the usability of This paper is organized as following. Section II presents
proposed Kmeans-DBSCAN method. Kmeans-DBSCAN in details. Section III presents the
experimental design and the results. Section IV concludes this
Keywords—Image Segmentation; Computer Vision; Clustering study.
Analysis; K-means; DBSCAN.
II.
KMEANS-DBSCAN
I.
INTRODUCTION
The proposed Kmeans-DBSCAN approach consists of four
Image segmentation is an important topic in the field of stages. An image is preprocessed as a data matrix. The data
computer vision. The representation of images can be simplified matrix is divided to a number of small clusters by K-means. The
by segmenting a digital image into multiple regions for further clusters are then merged by DBSCAN taking the corresponding
analysis [1]. The pixels of an image can be clustered as regions centroids as inputs. Finally the results of K-means and DBSCAN
with respect to their color similarities and spatial relationships are fused to produce the segmentation results.
[1-3].
A.
Image Dataset Preprocessing
Density-based clustering methods can be applied for image
segmentation due to their ability to discover arbitrary shaped An RGB color image can be represented as a 3-D raw dataset
clusters [4-6]. Density-Based Spatial Clustering of Applications by using the image reading functions such as readJPEG()
with Noise (DBSCAN) [7] is the widely used density-based provided by R package jpeg [9]. The 3-D raw dataset is a color
clustering method. The main disadvantage of DBSCAN is the matrix consisting of three additive primary color (Red, Green
high time-complexity. As the size of an image dataset is and Blue) values of each pixel. In the preprocessing stage, the
normally very large, it is hard to be directly processed by raw 3-D image dataset is reconstructed as a 2-D data matrix by
DBSCAN. combining the primary color and spatial information. The ith
pixel is represented by the vector (Xi, Yi, Ri, Gi, Bi) where Xi, Yi
K-means [8] has been applied for image segmentation [1, 2] are the spatial values computed by Eqs. (1-2) and (Ri, Gi, Bi) is
by clustering the pixels with respect to their color similarities. the color vector from the raw image dataset.
As K-means was designed for centroid-based cases, it can not be
used to detect the arbitrary shaped regions in an image. 1+i \x
Xi = (1)
In this paper, a hybrid approach, Kmeans-DBSCAN is x
proposed by combining K-means and DBSCAN for image
segmentation. For the image preprocessing, the color and spatial i mod y
Yi =
information for all the pixels are represented in a 2-D data matrix. y (2)

978-1-5386-3066-2/17 $31.00 © 2017 IEEE 396

DOI 10.1109/iThings-GreenCom-CPSCom-SmartData.2017.65
where x and y are the numbers of pixels in the x and y axes of Density-Based Spatial Clustering of Applications with Noise
the image respectively; \ is integer division. (DBSCAN) was firstly proposed in [7]. DBSCAN can find the
arbitrary shaped clusters by detecting the high-density hyper-
B.
Pixels Clustering by K-means spheres and merging the close hyper-spheres into clusters.
The general procedure of K-means for grouping the pixels DBSCAN requires two parameters as input, the radius of hyper-
into clusters are presented in Algorithm 1. The MacQueen K- spheres (ε) and the minimum number of points in each hyper-
means [8] has been applied in the proposed KMEANS- sphere (Minpts).
DBSCAN approach. A number of cluster centroids are
randomly initialized and then every point is assigned to the The DBSCAN steps for clustering the centroids produced by
nearest centroid. The mean value of data points assigned to new K-means are given in Algorithm 2. K number of cluster
cluster is computed. The loop should be executed until the centroids produced by K-means constructs the matrix P where
centroids of clusters converge. The similarities of pixels are each vector pj represents a centroid (Algorithm 1). The
computed as Euclidean distance by Eq. (3). clustering pattern S is a vector where each element sj is a cluster
identifier (identifier 0 indicates the noise cluster). Sid represents
2 2 2 2 2
the value of cluster identifier. Cidj indicates the status of the jth
dii ′ = ( X i − X i ′ ) + (Yi − Yi ′ ) + (Ri − Ri ′ ) + (Gi − Gi ′ ) + (Bi − Bi ′ )
(3) centroid which is processed or not. The function regionQuery(p,
) returns p and all the neighborhoods of p within the radius .
Algorithm 1: K-means The function id (p') returns the index of p' in P. The algorithm
for merging clusters are described as Algorithm 3.
Input: Image data matrix D, the number of clusters K;
Output: a set of clusters C and clusters centroids P;
Algorithm 3: mergeCluster
1.
Randomly choose K pixels from D as the initial cluster
centroid s; Input: s; NeighborPts, Sid, , MinPts
2.
Assign each pixel to the closest cluster on the basis the 1.
s= Sid
similarities between the pixels computed by (3); 2.
for each p' in NeighborPts
3.
Update each cluster centroid as the mean value of the j' = id (p')
pixels in the cluster;
if Cidj' == unseen
4.
Repeat steps 2 and 3 until the centroids stop changing;
Cidj' = seen
NeighborPts' = regionQuery(p', )
C.
Centroids Clustering by DBSCAN
if sizeof(NeighborPts') >= MinPts
Algorithm 2: DBSCAN NeighborPts = NeighborPts joined with
NeighborPts'
Input: a set of centroids, P; radius of hyper-spheres, ; the
minimum number of points, Minpts. if sj'== 0 or Null
Output: Clustering pattern S. sj' = Sid
1.
Sid=0
D.
Clustering Results Fusion
2.
For j=1 to K The results of K-means and DBSCAN are fused to produce
if Cidj == seen the image segmentation results by visualization. Each cluster
centroid is assigned with a clustering identifier after DBSCAN,
j= j+1 and then the clustering identifier is assigned to all the pixels in
Cidj=seen cluster generated by the K-means. According to clustering
identifiers, new figure for segmentation is visualized.
NeighborPtsj = regionQuery(pj, )
III.
APPLICATION
if sizeof(NeighborPtsj) < MinPts
Four images shown in Figure 1 are selected from Berkeley
sj=0 // mark c as noise Segmentation Dataset and Benchmark (BSDB) [10] to evaluate
else the usability of proposed Kmeans-DBSCAN for image
segmentation. The proposed method is implemented by R
Sid = Sid +1 language with packages stats [11] and fpc [12]. The processing
details and results of the four images are presented as follows.
mergeCluster(sj, NeighborPtsj, Sid,
, MinPts)
A.
Image Dataset Preprocessing
3.
Return S.
Each image has 481 pixels in x-axis and 321 pixels in y-axis,
and thus it has 154401 pixels in total. The raw image datasets

397
have 2 space dimensions matrix and each element for the matrix using Kmeans-DBSCAN, the input size of DBSCAN is reduced
is the 3 dimensions color values (R, G, B). For the example of to 50 or 100 vectors in the experiments, as the segmentation
Image 3063, the color values of the first pixel are 0.3451, 0.4627 results are reasonable in Figures 4-5.
and 0.6667 in the raw image dataset. In the 2-D data matrix, the
first two attributes values are computed as IV.
CONCLUSION
(1\481+1)/481=0.0021 and (1mod321)/321=0.0.0031. The This paper proposes Kmeans-DBSCAN, a hybrid approach
attribute values of the first 4 pixels in Image 3063 are shown in of K-means and DBSCAN, for image segmentation. Since the
Table I. high computational complexity of DBSCAN and the large size
of image datasets, K-means is applied to reduce the size of image
TABLE I.
A SAMPLE OF PREPROCESSED IMAGE 3063 DATA MATRIX datasets in proposed approach. Four images selected from
Pixel ID Xi Yi Ri Gi Bi benchmarking datasets are used for evaluating the usability of
the proposed method. The results of proposed method are more
1 0.0021 0.0031 0.3451 0.4627 0.6667
reasonable than either DBSCAN or K-means segmentation
2 0.0021 0.0063 0.3686 0.4784 0.6745 results. The further study will extend the structure of the
3 0.0021 0.0093 0.4039 0.4980 0.6862 proposed method with more experiments.
4 0.0021 0.0125 0.4392 0.5216 0.6902

B.
Pixels Clustering by K-means ACKNOWLEDGMENT

The parameter settings of four sets of experiments are shown The research work reported in this paper is partially
in Table II. For each image, two tests are performed by setting supported by Research Grants from National Natural Science
K as 50 and 100 respectively and the results are shown in Figures Foundation of China (Project Number 61503306) and Natural
2-3. By inspection of the segmentation results in Figures 2-3, K- Science Foundation of Jiangsu Province (Project Number
means cannot solely detect the arbitrary shapes in the images, BK20150377), China.
whilst the same color at the same area in an image is forced to
be divided into small centroid-based clusters due to the Xi and Yi
values. The next step by DBSCAN is to solve this problem. REFERENCES
C.
Centroids Clustering by DBSCAN [1]
P. F. Felzenszwalb and D. P. Huttenlocher, “Efficient graph-based image
segmentation,” International journal of computer vision, vol.59(2), pp.
The settings for DBSCAN parameter pair, (, Minpts), are 167-181, 2004.
shown in Table II. In these cases, each set of centroids produced [2]
A. K. Jain and P. J. Flynn, “Image segmentation using clustering”. IEEE
cluster patterns S of two parts and few centroids are detected as Press, 1996.
noise by DBSCAN. [3]
K. S. Chuang, H. L. Tzeng, S. Chen, J. Wu and T. J. Chen, “Fuzzy c-
means clustering with spatial information for image segmentation,”
TABLE II.
PARAMETER SETTINGS FOR KMEANS-DBSCAN computerized medical imaging and graphics, vol. 30(1), pp. 9-15, 2006.
[4]
M. E. Celebi, Y. A. Aslandogan and P. R. Bergstresser, “Mining
Image ID K (, Minpts) biomedical images with density-based clustering,” In Information
Technology: Coding and Computing International Conference on IEEE,
50 (0.40, 2) vol. 1, pp. 163-168, 2005.
3063
100 (0.25, 3) [5]
J. Shen, X. Hao, Z. Liang, Y. Liu, W. Wang and L. Shao, “Real-Time
Superpixel Segmentation by DBSCAN Clustering Algorithm.,” IEEE
50 (0.35, 3) Transactions on Image Processing, vol. 25(12), pp. 5933-5942, 2016.
3096
100 (0.35, 5) [6]
Q. Ye, W. Gao and W. Zeng, “Color image segmentation using density-
50 (0.31, 2) based clustering,” In Multimedia and Expo, 2003. ICME'03. Proceedings.
12003 2003 International Conference on IEEE, vol. 2, pp. II-401, 2003.
100 (0.31, 4) [7]
M. Ester, H. P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm
50 (0.33, 3) for discovering clusters in large spatial databases with noise.” In Kdd, Vol.
135069 96, No. 34, pp. 226-231, 1996.
100 (0.31, 5)
[8]
J. Macqueen, “Some Methods for Classification and Analysis of
D.
Clustering Results Fusion Multivariate Observations,” In Proceedings of the fifth Berkeley
symposium on mathematical statistics and probability, vol 1, pp.281-297,
The image segmentation results of Kmeans-DBSCAN by 1967.

fusing the clustering results produced in steps B and C are [9]
Urbanek, S, “jpeg: Read and write JPEG images,” R package version 0.1–
visualized in Figures 4-5. 8, 2014.
[10]
D. Martin, C. Fowlkes, D. Tal, and J. Malik, “The berkeley segmentation
E.
Discussions dataset and benchmark,” University of California, Berkeley, http://www.
Several important findings are reported by follows. Firstly, cs. berkeley. edu/projects/vision/grouping/segbench, 2007.
K-means cannot solely and directly be used for image [11]
R. C. Team and C. Worldwide, “The R stats package. R Foundation for
Statistical Computing,” Vienna, Austria: Available from: http://www. R-
segmentation by the input of raw data sets. The results can be project.org, 2002.
inspected in Figure 6. Secondly, since the input data matrix has
[12]
C. Hennig, “fpc: Flexible procedures for clustering,” R package version
154401 vectors of 5 attributes, it will take hours to directly 2-1, 2014.
process it by DBSCAN without reasonable results. Finally, by

398
 (a) Image 3063 (b) Image 3069 (c) Image 12003 (d) Image 135069

Fig. 1.
Orginal Images.

(a) Image 3063 (b) Image 3069 (c) Image 12003 (d) Image 135069

Fig. 2.
Segmentation results of K-means by setting K as 50.

(a) Image 3063 (b) Image 3069 (c) Image 12003 (d) Image 135069

Fig. 3.
Segmentation results of K-means by setting K as 100.

(a) Image 3063 (b) Image 3069 (c) Image 12003 (d) Image 135069

Fig. 4.
Segmentation results of Kmeans-DBSCAN by setting K as 50, DBSCAN Parameter pairs as: (a) (0.40, 2); (b) (0.35, 3); (c) (0.31, 2); (d) (0.33, 3).

(a) Image 3063 (b) Image 3069 (c) Image 12003 (d) Image 135069

Fig. 5.
Segmentation results of Kmeans-DBSCAN by setting K as 100, DBSCAN Parameter pairs as: (a) (0.25, 3); (b) (0.35, 5); (c) (0.31, 4); (d) (0.33, 5).

(a) Image 3063 (b) Image 3069 (c) Image 12003 (d) Image 135069

Fig. 6.
Segmentation results of K-means by setting K as 2.

399