FAST K-MEANS COLOR IMAGE CLUSTERING WITH NORMALIZED DISTANCE VALUES

Abstract

Image segmentation is an intermediate image processing stage in which the pixels of the image are grouped into clusters such that the data resulted from this stage is more meaningful for the next stage. Many clustering methods are used widely to segment the images. For this purpose, most clustering methods use the features of the image pixels. While some clustering method consider the local features of images by taking into account the neighborhood system of the pixels, some consider the global features of images. The algorithm of the K-means clustering method, that is easy to understand and simple to put into practice, performs by considering the global features of the entire image. In this algorithm, the number of cluster is given by users initially as an input value. For the segmentation process, if the distribution of the pixels over a histogram is used, the algorithm runs faster. The values in the histogram must be discrete in a certain range. In this paper, we use the Euclidean distance between the color values of the pixels and the mean color values of the entire image for taking advantage of the every color values of the pixels. To obtain a histogram that consists of discrete values, we normalize the distance value in a specific range and round the values to the nearest integers for discretization. We tested the versions of K-means with the gray-level histogram and the distance value histogram on an urban image dataset getting from ISPRS WG III/4 2D Semantic Labeling dataset. Comparing the two histograms, the distance value histogram proposed in this paper is better than the gray-level histogram. 

Keywords

• Clustering,Histogram,Image segmentation,K-means

Normalize Edilmiş Uzaklık Değerleri ile Hızlı K-ortalama Renkli Görüntü Segmentasyonu

Öz

Görüntü segmentasyonu, görüntü piksellerinin kümelere gruplandığı orta seviye bir görüntü işleme aşamasıdır. Öyle ki, bu şamadan elde edilen veri daha sonraki aşamalar için önceki veriye göre daha anlamlı hale gelmiş olur. Birçok kümeleme metodu, görüntü segmentasyonu amacıyla yaygın bir şekilde kullanılmaktadır. Bu amaçla, çoğu kümeleme metodu görüntü piksellerinin özelliklerini kullanmaktadır. Bazı kümeleme metotları piksellerin komşuluk sistemini kullanarak görüntünün yerel özelliklerini ele alırken, bazıları da görüntünün genel özelliklerini ele almaktadır. Anlaşılması kolay ve uygulaması basit olan K-ortalama algoritması, bütün görüntünün özelliklerini ele alarak segmentasyon yapmaktadır. Bu algoritmada, küme sayısı başlangıç giriş değeri olarak kullanıcı tarafından verilmektedir. Bu segmentasyon işlemi için, eğer piksellerin bir histogram üzerindeki dağılımı kullanılırsa algoritma daha hızlı çalışmaktadır. Bu histogram üzerindeki değerler belirli bir aralıkta ve ayrık olmak zorundadır. Bu çalışmada, piksellerin her bir renk değerinden faydalanmak için piksellerin renk değerleri ile görüntünün ortalama renk değerleri arasındaki Öklit uzaklığı kullanılmıştır. Ayrık değerlerden oluşan bir histogram elde etmek için, uzaklık değerlerini belirli değer aralığında normalize ettik ve bu değerleri ayrıklaştırmak için en yakınındaki tamsayıya yuvarladık. Bu K-means metodu, ISPRS WG III/4 2D Semantic Labeling veri setinden alınan kentsel görüntüler üzerinde gri seviye değerlerinin ve uzaklık mesafesi değerlerinin histogramları ile test edilmiştir. İki histogram karşılaştırıldığında, uzaklık değeri histogramı gri seviye değer histogramından daha iyi sonuç vermiştir.

Anahtar Kelimeler

• Kümeleme,Histogram,Görüntü segmentasyonu,K-ortalama

Kaynakça

1. de Amorim, R.C., Makarenkov, V., 2016, "Applying Subclustering and Lp Distance in Weighted K-Means with Distributed Centroids", Neurocomputing, Vol. 173, pp. 700–707.
2. Axelsson, P., 2000, "DEM Generation from Laser Scanner Data Using adaptive TIN Models", International Archives of Photogrammetry and Remote Sensing, Vol. 33(Part B4), pp.110–117.
3. Cheng, H.D., Jiang, X. H., Sun, Y., Wang, J., 2001, "Color Image Segmentation: Advances and Prospects", Pattern Recognition, Vol. 34(12), pp.2259–2281.
4. Dai, S., Lu, K., Dong, J., Zhang, Y., Chen, Y., 2015, "A Novel Approach of Lung Segmentation on chest CT Images using Graph Cuts", Neurocomputing, Vol. 168, pp.799–807.
5. Felzenszwalb, P.F., Huttenlocher, D.P., 2004, "Efficient Graph-Based Image Segmentation", International Journal of Computer Vision, Vol. 59(2), pp.167–181.
6. Gingles, C., Celebi, M.E., 2014, "Histogram-Based Method for Effective Initialization of the K-Means Clustering Algorithm", The Twenty-Seventh International Flairs Conference In FLAIRS Conference, Florida, 21-23 May 2014.
7. Gonzalez, R.C., Woods, R.E., 2007, Digital Image Processing (3rd Edition), Pearson International Edition.
8. Jain, A.K., 2010, "Data Clustering: 50 Years Beyond K-means", Pattern Recognition Letters, Vol. 31(8), pp.651–666.

9. Jain, A.K., Dubes, R.C., 1988, Algorithms for Clustering Data, Prentice Hall, 355, p.320.
10. Jain, A.K., Murty, M.N., Flynn, P.J., 1999, "Data Clustering: a Review", ACM Computing Surveys, Vol. 31(3), pp.264–323.
11. Labeling, S., Vaihingen, B., 2016, Use of the Stair Vision Library within the ISPRS Use of the Stair Vision Library within the ISPRS 2D,
12. Likas, A., Vlassis, N., J. Verbeek, J., 2003, "The Global k-means Clustering Algorithm", Pattern Recognition, Vol. 36(2), pp.451–461.
13. Lin, C.-H., Chen, C. C., Lee, H. L., Liao, J. R., 2014, "Fast K-means Algorithm Based on a Level Histogram for Image Retrieval", Expert Systems with Applications, Vol. 41(7), pp.3276–3283.
14. Lloyd, S.P., 1982, "Least Squares Quantization in PCM", IEEE Transactions on Information Theory, Vol. 28(2), pp.129–137.
15. Mignotte, M., 2008, "Segmentation by Fusion of Histogram-Based K-means Clusters in Different Color Spaces", IEEE Transactions on Image Processing, Vol. 17(5), pp.780–787.
16. Peng, B., Zhang, L., Zhang, D., 2013, "A survey of Graph Theoretical Approaches to Image Segmentation", Pattern Recognition, Vol. 46(3), pp.1020–1038.
17. Punjab, P., Punjab, P., 2012, "Performance Analysis of Segmentation Techniques", International Journal of Computer Applications, Vol. 45(23), pp.18–23.
18. Rupali, N., Shweta, J., 2014, "Color Image Segmentation With K Means", Saiom publications, Vol. 1(5), pp.389–397. Available at: Saglam, A., Baykan, N.A., 2017, "Sequential Image Segmentation Based on Minimum Spanning Tree Representation", Pattern Recognition Letters, Vol. 87, pp.155–162.
19. Tian, M., Yang, Q., Maier, A., Schasiepen, I., Maass, N., Elter, M., 2013, "Automatic Histogram-Based Initialization of K-means Clustering in CT". In Bildverarbeitung für die Medizin 2013, Springer Berlin Heidelberg, pp. 277–282.