k-means segmentation algorithm" /> k-means segmentation algorithm" /> k-means segmentation algorithm" />
 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.

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.

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:
 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, 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. 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. Table 1: Number of clusters used in each algorithm for each respective images Table 2: Comparison of algorithms in terms of mean $Q$-value and standard deviation ($Q$-value, $σ$) Table 3: Comparison of algorithms in terms of mean RMSE and standard deviation (RMSE, $σ$) Table 4: Comparison of algorithms in terms of mean computation time and standard deviation (time (s), $σ$) 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 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 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. 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. Table 9: Comparison of proposed algorithm with clustering image segmentation algorithm in terms of MSE, Time, and $Q$ for two MRI images 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. 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