k-means segmentation algorithm" /> k-means segmentation algorithm" /> k-means segmentation algorithm" />
Please wait a minute...
Computational Visual Media  2019, Vol. 05 Issue (04): 347-361    doi: 10.1007/s41095-019-0151-2
Research Article     
Evaluation of modified adaptive k-means segmentation algorithm
Taye Girma Debelee1,2,(✉), Friedhelm Schwenker1, Samuel Rahimeto2, Dereje Yohannes2
1Institute of Neural Information Processing, Ulm University, 89081Ulm, Germany; F. Schwenker, friedhelm.schwenker@uni-ulm.de.;
2Addis Ababa Science and Technology University, Addis Ababa, 120611, Ethiopia. E-mail: S. Rahimeto, samuelrahimeto@gmail.com; D. Yohannes, derejey@yahoo.com.
Download: PDF (13536 KB)      HTML  
Export: BibTeX | EndNote (RIS)      

Abstract  

Segmentation is the act of partitioning an image into different regions by creating boundaries between regions. k-means image segmentation is the simplest prevalent approach. However, the segmentation quality is contingent on the initial parameters (the cluster centers and their number). In this paper, a convolution-based modified adaptive k-means (MAKM) approach is proposed and evaluated using images collected from different sources (MATLAB, Berkeley image database, VOC2012, BGH, MIAS, and MRI).The evaluation shows that the proposed algorithm is superior to k-means++, fuzzy c-means, histogram-based k-means, and subtractive k-means algorithms in terms of image segmentation quality (Q-value), computational cost, and RMSE. The proposed algorithm was also compared to state-of-the-art learning-based methods in terms of IoU and MIoU; it achieved a higher MIoU value.



Key wordsclustering      modified adaptive k-means (MAKM)      segmentation      Q-value     
Received: 01 April 2019      Published: 13 March 2020
Corresponding Authors: Taye Girma Debelee   
Cite this article:

Taye Girma Debelee, Friedhelm Schwenker, Samuel Rahimeto, Dereje Yohannes. Evaluation of modified adaptive k-means segmentation algorithm. Computational Visual Media, 2019, 05(04): 347-361.

URL:

http://cvm.tsinghuajournals.com/10.1007/s41095-019-0151-2     OR     http://cvm.tsinghuajournals.com/Y2019/V05/I04/347

T?p, are computed using the histogram levels. Third, the dynamic window size is computed using an amplitude threshold for each image. This is followed by a 2D convolution operation. Finally, the mean of the convolution is set as the initial seed to generate other new seed values that can be used as the centers of clusters, which are then used to perform clustering.">
Fig. 1:  Flowchart of our convolution-based segmentation algorithm. First, histograms of the grayscale image of the original image are generated. Second, amplitude thresholds, <inline-formula><math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline" id="MA54"><mml:mrow><mml:mi>T</mml:mi><mml:mo>?</mml:mo><mml:mi>p</mml:mi></mml:mrow></math></inline-formula>, are computed using the histogram levels. Third, the dynamic window size is computed using an amplitude threshold for each image. This is followed by a 2D convolution operation. Finally, the mean of the convolution is set as the initial seed to generate other new seed values that can be used as the centers of clusters, which are then used to perform clustering.
Fig. 2:  MRI-labeled image segmented using various approaches.
Fig. 3:  Bag-labeled image segmented using various approaches.
Fig. 4:  Cameraman-labeled image segmented using various approaches.
Fig. 5:  Coins-labeled image segmented using various approaches.
Fig. 6:  Moon-labeled image segmented using various approaches.
ImageSizeK++HBKFCMSCAKMMAKM (proposed)
Experiment-1MRI128×128334233
Bag250×189334454
Cameraman256×256334344
Coins246×300334243
Moon537×358334244
Pout291×240334234
Glass181×282334533
Experiment-2AT3_1m4_01 (AT)480×640334155
Lena512×512334433
Valley321×481334544
Airplane321×481334244
Mountain321×481334243
Breast384×512334265
Table 1: Number of clusters used in each algorithm for each respective images
ImageSizeK++HBKFCMSCAKMMAKM (proposed)
MRI128×1280.40, 0.181.06, 0.600.87, 0.640.31, —0.21, 0.000.20, 0.00
Bag250×1890.44, 0.350.50, 0.430.39, 0.320.13, —0.07, 0.000.12, 0.00
Cameraman256×2560.39, 0.210.44, 0.280.48, 0.250.70, —0.02, 0.000.05, 0.00
Coins246×3000.26, 0.230.54, 0.370.42, 0.180.13, —0.13, 0.000.13, 0.00
Moon537×3580.25, 0.360.87, 0.570.60, 0.510.06, —0.01, 0.000.01, 0.00
Pout291×2400.28, 0.040.35, 0.140.40, 0.130.29, —0.20, 0.000.03, 0.00
Glass181×2820.55, 0.240.46, 0.410.44, 0.290.62, —0.15, 0.000.14, 0.00
Table 2: Comparison of algorithms in terms of mean Q-value and standard deviation (Q-value, σ)
ImageSizeK++HBKFCMSCAKMMAKM (proposed)
MRI128×1281.14, 0.001.14, 0.0040.88, 0.0060.91, —1.03, 0.001.03, 0.00
Bag250×1891.27, 0.0041.27, 0.011.13, 0.0011.36, —1.29, 0.000.90, 0.00
Cameraman256×2561.63, 0.0011.62, 0.0051.44, 0.011.63, —1.47, 0.001.10, 0.00
Coins246×3001.54, 0.0021.54, 0.011.47, 0.0041.50, —1.61, 0.001.31, 0.00
Moon537×3580.86, 0.0010.86, 0.0040.91, 0.0010.76, —0.88, 0.000.86, 0.00
Pout291×2401.81, 0.041.79, 0.021.91, 0.0051.77, —1.50, 0.001.48, 0.00
Glass181×2821.51, 0.001.51, 0.0011.62, 0.0051.77, —1.44, 0.001.37, 0.00
Table 3: Comparison of algorithms in terms of mean RMSE and standard deviation (RMSE, σ)
ImageSizeK++HBKFCMSCAKMMAKM (proposed)
MRI128×1280.01, 0.0050.02, 0.0060.02, 0.0095.00, 0.500.003, 0.0010.004, 0.001
Bag250×1890.08, 0.070.09, 0.030.06, 0.0233.70, 1.020.012, 0.0020.018, 0.011
Cameraman256×2560.04, 0.020.09, 0.0050.08, 0.0162.77, 1.250.0116, 0.0020.016, 0.004
Coins246×3000.09, 0.070.11, 0.0050.08, 0.0175.90, 1.160.015, 0.0040.022, 0.024
Moon537×3580.20, 0.110.26, 0.010.20, 0.0071025.01, 5.690.041, 0.0030.042, 0.005
Pout291×2400.02, 0.0080.09, 0.0050.06, 0.0174.03, 0.750.015, 0.0040.015, 0.004
Glass181×2820.02, 0.0060.07, 0.0040.05, 0.0239.44, 0.050.012, 0.0080.011, 0.004
Table 4: Comparison of algorithms in terms of mean computation time and standard deviation (time (s), σ)
ImageSizeK++HBKFCMSCMAKM (proposed)
AT3_1m4_01 (AT)480×6400.530.360.490.500.04
Lena (LE)512×5120.420.350.480.390.06
Valley (VA)321×4810.450.450.550.450.15
Airplane (AI)321×4810.400.290.360.410.10
Mountain (MT)321×4810.340.500.530.640.19
Breast384×5120.460.390.730.720.01
Table 5: Comparison of proposed algorithm with K++, HBK, FCM, and SC in terms of mean Q-value for AT, LE, VA, AI, MT, and Breast images
ImageSizeK++HBKFCMSCMAKM (proposed)
AT3_1m4_01 (AT)480×6400.830.830.820.740.69
Lena (LE)512×5121.001.001.101.120.84
Valley (VA)321×4811.231.231.201.421.06
Airplane (AI)321×4811.451.451.511.281.22
Mountain (MT)321×4810.950.950.880.780.72
Breast384×5120.560.580.590.500.56
Table 6: Comparison of proposed algorithm with K++, HBK, FCM, and SC in terms of mean RMSE for AT, LE, VA, AI, MT, and Breast images
ImageSizeK++HBKFCMSCMAKM (proposed)
AT3_1m4_01 (AT)480×6400.340.420.332846.450.14
Lena (LE)512×5120.210.340.272074.850.12
Valley (VA)321×4810.200.270.18693.660.06
Airplane (AI)321×4810.120.230.14648.500.05
Mountain (MT)321×4810.090.240.17658.370.07
Breast384×5120.100.200.171092.930.05
Table 7: Comparison of proposed algorithm with K++, HBK, FCM, and SC in terms of mean computation cost (s) for AT, LE, VA, AI, MT, and Breast images
Fig. 7:  Lena-labeled image segmented using various approaches.
ImageAlgorithmQTime (s)MAEEntropyPSNRPRF?1
DogAKM0.0420.1066.071.5347.2589.361.772.9
FCM0.4310.3453.221.8346.9886.992.289.5
k-means++0.2090.2482.761.9446.6484.899.591.6
Proposed0.0400.0523.891.7947.2890.380.485.1
PlaneAKM0.0310.0410.4071.5443.5595.089.692.2
FCM0.7430.2120.3021.7143.1191.298.794.8
k-means++1.000.1200.2521.6343.1694.296.695.4
Proposed0.0300.0360.3371.5843.5995.392.493.8
PlantAKM0.0120.0540.3311.6345.7871.181.776.0
FCM0.0410.28640.601.6445.730.01.30.0
k-means++0.6210.10743.301.6445.650.00.00.0
Proposed0.0110.0610.3321.6345.8472.182.877.2
PersonAKM0.0950.1112.721.9248.6783.688.886.1
FCM0.1390.5816.301.6247.7292.268.178.3
k-means++0.350.6514.091.7247.3492.972.881.6
Proposed0.0940.0505.112.0648.7184.999.991.8
Table 8: Comparison of proposed method with clustering algorithms in terms of Q, computation time, MAE, entropy, PSNR, precision (P), recall (R), and F-score (F?1) using VOC2012 dataset
Fig. 11:  Examples of annotated and extracted region with tumor for MRI image using proposed method.
ImageMethodMSETimeQ
MRI_1AKM0.670.030.009
FCM0.740.160.238
k-means++0.770.370.053
Proposed0.660.020.008
MRI_2AKM0.740.030.020
FCM0.850.161.585
k-means++0.910.301.492
Proposed0.730.020.019
Table 9: Comparison of proposed algorithm with clustering image segmentation algorithm in terms of MSE, Time, and Q for two MRI images
MethodMRI_1MRI_2MRIoU
AKM63.1958.1960.69
FCM79.2162.9371.07
k-means++77.9083.9680.93
Proposed64.2286.3375.28
Table 10: Comparison of proposed algorithm with clustering algorithm in terms of IoU and MIoU for two MRI images
Fig. 8:  Examples of annotated and extracted region with cancer for breast mammographic images from BGH and MIAS datasets using proposed method.
Fig. 9:  Annotated and respective segmentation result for dog from VOC2012 challenge datasets using proposed method.
Fig. 10: Annotated and respective segmentation result for plane and person from VOC2012 challenge datasets using proposed method.
Author(s), year, and citationMethodDogPlanePlantPersonMIoU
Long et al., 2015[5]FCN-8s71.876.845.273.966.92
Chen et al., 2016 [4]DeepLab68.77250.873.666.28
Chen et al., 2016 [4]DeepLab-Msc68.474.951.775.067.5
Dai et al., 2015 [6]MSRA-CFM69.175.750.467.565.68
Mostajabi et al., 2015 [7]TTI-Zoomout-1674.081.968.844.367.25
Chen et al., 2016 [4]DeepLab-CRF75.278.454.777.671.48
Chen et al., 2016 [4]DeepLab-MSc-CRF74.380.456.979.072.65
Chen et al., 2016 [4]DeepLab-CRF-7x778.983.960.380.675.93
Chen et al., 2016 [4]DeepLab-MSc-LargeFOV78.583.558.279.774.98
Chen et al., 2016 [4]DeepLab-MSc-CRF-LargeFOV79.084.459.780.875.98
Liu et al., 2015 [36]ParseNet Baseline73.182.651.978.671.58
Liu et al., 2015 [36]ParseNet77.184.152.678.273.0
Reproduced by Ref. [36]Hypercolumn72.168.752.672.966.58
Yu and Koltun, 2015 [8]Front-End Module73.182.256.679.172.75
ReproducedAKM57.485.661.3075.669.98
ReproducedFCM81.090.10.064.358.85
Reproducedk-means++84.591.20.068.961.15
Proposed methodMAKM74.088.1661.3285.077.12
Table 11: Related works from learning-based methods and clustering algorithms for comparison with proposed method in terms of IoU and MIoU for selected images from VOC2012 dataset
[1]   Zaitoun, N. M.; Aqel, M. J. Survey on image segmentation techniques. Procedia Computer Science Vol. 65, 797-806, 2015.
[2]   Jaglan, P.; Dass, R.; Duhan, M.A comparative analysis of various image segmentation techniques. In: Proceedings of the 2nd International Conference on Communication, Computing and Networking. Lecture Notes in Networks and Systems, Vol. 46. Krishna, C.; Dutta, M.; Kumar, R. Eds. Springer Singapore, 359-374, 2019.
[3]   Schwenker, F.; Trentin, E. Pattern classification and clustering: A review of partially supervised learning approaches. Pattern Recognition Letters Vol. 37, 4-14, 2014.
[4]   Chen, L.-C.; Yang, Y.; Wang, J.; Xu, W.; Yuille, A. L.Attention to scale: Scale-aware semantic image segmentation. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 3640-3649, 2016.
[5]   Long, J.; Shelhamer, E.; Darrell, T.Fully convolutional networks for semantic segmentation. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 3431-3440, 2015.
[6]   Dai, J.; He, K.; Sun, J.Convolutional feature masking for joint object and stuff segmentation. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 3992-4000, 2015.
[7]   Mostajabi, M.; Yadollahpour, P.; Shakhnarovich, G.Feedforward semantic segmentation with zoom-out features. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 3376-3385, 2015.
[8]   Yu, F.; Koltun, V. Multi-scale context aggregation by dilated convolutions. arXiv preprint arXiv:1511.07122, 2015.
[9]   Chen, L. C.; Papandreou, G.; Schroff, F.; Adam, H. Rethinking atrous convolution for semantic image segmentation. arXiv preprint arXiv:1706.05587, 2017.
[10]   Shi, P. F.; Fan, X. N.; Ni, J. J.; Wang, G. R. A detection and classification approach for underwater Dam cracks. Structural Health Monitoring: An International Journal Vol. 15, No. 5, 541-554, 2016.
[11]   Khanmohammadi, S.; Adibeig, N.; Shanehbandy, S. An improved overlapping k-means clustering method for medical applications. Expert Systems with Applications Vol. 67, 12-18, 2017.
[12]   Dhanachandra, N.; Manglem, K.; Chanu, Y. J. Image segmentation using k-means clustering algorithm and subtractive clustering algorithm. Procedia Computer Science Vol. 54, 764-771, 2015.
[13]   Fau?er, S.; Schwenker, F.Clustering large datasets with kernel methods. In: Proceedings of the 21st International Conference on Pattern Recognition, 501-504, 2012.
[14]   Razavi Zadegan, S. M.; Mirzaie, M.; Sadoughi, F. Ranked k-medoids: A fast and accurate rank-based partitioning algorithm for clustering large datasets. Knowledge-Based Systems Vol. 39, 133-143, 2013.
[15]   Dixit, A. Adaptive kmeans clustering for color and gray image. 2014. Available at .
[16]   Bezdek, J. C. Modified objective function algorithms. In: Pattern Recognition with Fuzzy Objective Function Algorithms. Advanced Applications in Pattern Recogni-tion. Springer Boston MA, 155-201, 1981.
[17]   Fau?er, S.; Schwenker, F.Parallelized kernel patch clustering. In: Artificial Neural Networks in Pattern Recognition. Lecture Notes in Computer Science, Vol. 5998. Schwenker, F.; El Gayar, N. Eds. Springer Berlin Heidelberg, 131-140, 2010.
[18]   Benaichouche, A. N.; Oulhadj, H.; Siarry, P. Improved spatial fuzzy c-means clustering for image segmentation using PSO initialization, Mahalanobis distance and post-segmentation correction. Digital Signal Processing Vol. 23, No. 5, 1390-1400, 2013.
[19]   Lei, T.; Jia, X. H.; Zhang, Y. N.; He, L. F.; Meng, H. Y.; Nandi, A. K. Significantly fast and robust fuzzy c-means clustering algorithm based on morphological reconstruction and membership filtering. IEEE Transactions on Fuzzy Systems Vol. 26, No. 5, 3027-3041, 2018.
[20]   Arthur, D.; Vassilvitskii, S.k-means++: The advantages of careful seeding. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, 1027-1035, 2007.
[21]   Zhang, Y.; Huang, D.; Ji, M.; Xie, F. D. Image segmentation using PSO and PCM with Mahalanobis distance. Expert Systems with Applications Vol. 38, No. 7, 9036-9040, 2011.
[22]   Purohit, P.; Joshi, R. A new efficient approach towards k-means clustering algorithm. International Journal of Computer Applications Vol. 65, No. 11, 7-10 2013.
[23]   Yedla, M.; Pathakota, S. R.; Srinivasa, T. M. Enhanced k-means clustering algorithm with improved initial center. International Journal of Science and Information Technologies Vol. 1, No. 2, 121-125, 2010.
[24]   Kü?ükkülahl?, E.; Erdo?mu? P.; Polat, K. Histogram-based automatic segmentation of images. Neural Computing and Applications Vol. 27, No. 5, 1445-1450, 2016.
[25]   Minaee, S.; Wang, Y.Screen content image segmentation using least absolute deviation fitting. In: Proceedings of the IEEE International Conference on Image Processing, 3295-3299, 2015.
[26]   Badrinarayanan, V.; Kendall, A.; Cipolla, R. SegNet: A deep convolutional encoder-decoder architecture for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 39, No. 12, 2481-2495, 2017.
[27]   Minaee, S.; Wang, Y. An ADMM approach to masked signal decomposition using subspace representation. IEEE Transactions on Image Processing Vol. 28, No. 7, 3192-3204, 2019.
[28]   Minaee, S.; Wang, Y. Screen content image segmenta-tion using robust regression and sparse decomposition. IEEE Journal on Emerging and Selected Topics in Circuits and Systems Vol. 6, No. 4, 573-584, 2016.
[29]   Martin, D.; Fowlkes, C.; Tal, D.; Malik, J.A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: Proceedings of the 8th IEEE International Conference on Computer Vision, 416-423, 2001.
[30]   Khan, Z.; Ni, J.; Fan, X.; Shi, P. An improved k-means clustering algorithm based on an adaptive initial parameter estimation procedure for image segmentation. International Journal of Innovative Computing, Information and Control Vol. 13, No. 5, 1509-1525, 2017.
[31]   Suckling, J. P. The mammographic image analysis society digital mammogram database exerpta medica. Digital Mammo 375-386, 1994.
[32]   Everingham, M.; Van Gool, L.; Williams, C. K. I.; Winn, J.; Zisserman, A. The Pascal visual object classes (VOC) challenge. International Journal of Computer Vision Vol. 88, No. 2, 303-338, 2010.
[33]   Saffor, R.; Ramli, A. R.; Ng, K-H. A comparative study of image compression between JPEG and wavelet. Malaysian Journal of Computer Science Vol. 14, No. 1, 39-45, 2001.
[34]   Gonzalez, R. C.; Woods, R. E. Digital Image Processing New York: Addison-Wesley, 1992.
[35]   Kamran, S. A.; Sabbir, A. S.Efficient yet deep convolutional neural networks for semantic segmenta-tion. In: Proceedings of the International Symposium on Advanced Intelligent Informatics, 123-130, 2018.
[36]   Liu, W.; Rabinovich, A.; Berg, A. C. Parsenet: Looking wider to see better. arXiv preprint arXiv:1506.04579, 2015.
[1] Liang Han, Pin Tao, Ralph R. Martin. Livestock detection in aerial images using a fully convolutional network[J]. Computational Visual Media, 2019, 5(2): 221-228.
[2] Salma Alqazzaz, Xianfang Sun, Xin Yang, Len Nokes. Automated brain tumor segmentation on multi-modal MR image using SegNet[J]. Computational Visual Media, 2019, 5(2): 209-219.
[3] Dawar Khan, Dong-Ming Yan, Fan Ding, Yixin Zhuang, Xiaopeng Zhang. Surface remeshing with robust user-guided segmentation[J]. Computational Visual Media, 2018, 4(2): 113-122.
[4] Takazumi Kikuchi, Yuki Endo, Yoshihiro Kanamori, Taisuke Hashimoto, Jun Mitani. Transferring pose and augmenting background for deep human-image parsing and its applications[J]. Computational Visual Media, 2018, 4(1): 43-54.
[5] Zhen Wei, Yao Sun, Junyu Lin, Si Liu. Learning adaptive receptive fields for deep image parsing networks[J]. Computational Visual Media, 2018, 04(03): 231-244.
[6] Rachele Bellini, Yanir Kleiman, Daniel Cohen-Or. Dance to the beat: Synchronizing motion to audio[J]. Computational Visual Media, 2018, 04(03): 197-208.
[7] Yixin Zhuang,Hang Dou,Nathan Carr,Tao Ju. Feature-aligned segmentation using correlation clustering[J]. Computational Visual Media, 2017, 3(2): 147-160.
[8] Sheng Yang,Jie Xu,Kang Chen,Hongbo Fu. View suggestion for interactive segmentation of indoor scenes[J]. Computational Visual Media, 2017, 3(2): 131-146.
[9] Xueting Liu,Chengze Li,Tien-Tsin Wong. Boundary-aware texture region segmentation from manga[J]. Computational Visual Media, 2017, 3(1): 61-71.
[10] Zhenyong Fu. Pairwise constraint propagation via low-rank matrix recovery[J]. Computational Visual Media, 2015, 1(3): 211-220.
[11] Hong Li,Wen Wu,Enhua Wu. Robust interactive image segmentation via graph-based manifold ranking[J]. Computational Visual Media, 2015, 1(3): 183-195.
[12] Xiangyu Mao,Xueting Liu,Tien-Tsin Wong,Xuemiao Xu. Region-based structure line detection for cartoons[J]. Computational Visual Media, 2015, 1(1): 69-78.