Recent studies have revealed that the performance of the FCM and K-means is completely related to the distance measures. However, the literature does not provide evidence that the distance used for data-clustering is useful for image segmentation. Therefore, a comparative study of the performance of diferent distance measures applied to image segmentation, using the mentioned clustering methods is proposed in this work. The selection of the distance measures was based on a literature study of their benefits. As a consequence, the selected distances to be tested are Euclidean, Manhattan, Canberra, and Spearman. Since our principal goal is to compare the efectiveness of the distance, the experiment had been evaluated according to two centroids selected by the user. According to primary results, the best-rated distance employed for image segmentation is the Canberra distance.
bership function is suitable for real-world applications where boundaries between clusters are
not well-defined [
Some works have explored the distance eficiency of the methods as K-means [
The rest of the paper is divided as follows: Section 2 describes the most relevant related works. The methodology used in this work is described in Section 3. Experimental results are presented and discussed in Section 4. Finally, Section 5 deals with the concluding remarks.
In the last years, clustering algorithms have been explored in several fields including but not limited to computer sciences, medicine, economics, social sciences, and earth sciences [10, 11]. Some applications of clustering algorithms in computer sciences domain include image segmentation such as: brain tumor identification [12], mammography image segmentation [13], satellite image retrieval [14], among others.
Since the main goal of this work is to evaluate the influence of distance measures on the
efectiveness achieved by K-means [
From a data mining perspective, authors in [17] use K means method to evaluate the overall performance of Euclidean, Chebyshev, Minkowski, and Manhattan, demonstrating that, Euclidean distance outperforms when a cluster center is selected randomly.
The distances measures used in clustering algorithms are summarized in Table 1.
An efective choice of a distance measure to express the distance between data and centroids is one important feature of clustering algorithms. Thus, the distances widely used in clustering algorithms, such as Euclidean, Manhattan, Canberra, and Chebyshev are selected and compared in this work for segmentation tasks.
The proposed methodology for evaluating the performance of the Euclidean, Manhattan, Canberra, and Chebyshev distances in clustering algorithms applied to image segmentation is schematized in Figure 1. First, the process reads an RGB image. Second, the RGB input image
Distances Advantages
[18] distinct or well separated from each other.
Euclidean 1.- The distance within two objects is not [19, 20] afected by the addition of new objects to the analysis, which may be outliers.
[21] is less sensitive to noise.
[22]
Disadvantages 1. This algorithm does not work well for categorical data, it is applicable only when the meaning is defined. 2. Algorithm fails for the non-linear data set. 1.- The distances can be greatly afected by diferences in scale among the dimensions from which the distances are computed. 2.- If one of the input attributes has a relatively large range, then it can overcome the other attributes 1.-This distance does not deal in a deterministic way when the dataset is high level 2.- The one disadvantage is that it depends upon the rotation of the coordinate system.
both coordinates are near to zero.
[23] to decide the distances between data sets.
centers are near, they will not be optimal.
Cosine [23] 1.- It produces a simple measure that can be used to diferentiate between similar texts, rank order them by similarity, or use the scores as a dependent variable in a regression model 1.- It is unable to provide information on the magnitude of the diferences. 2.- It is also invariant to scaling 3.- Cosine is not invariant to shifts. is converted to HSV color space. In this step, a graphical user interface is displayed to allow the user to select the color pixels that represent the object of interest (airplanes and animals) and the background. The pixels selected refer to the centroids that will be used in the clustering algorithms. Third, a multidimensional matrix is built to merge the tuple pixels positions with the color model matrices. Fourth, K-means of FCM is applied to the multidimensional matrix using the evaluated distance measures. To segment the object of interest in the case of K-means, it classifies each pixel as foreground if the distance from the pixel to the foreground centroid is less than the distance from the pixel to the background centroid. Otherwise, the pixel is classiifed as a background. It is worth mentioning that the centroids are selected by the user. On The other hand, FCM although it is a similar process it counts with a variable called: the degree of belonging which is linked inversely to the distance from the pixel to the foreground centroid. Finally, the influence of the evaluated distance measures on the overall performance achieved by K-means and FCM methods is determined in terms of accuracy metrics.
Humans perceive colors in screens as a combination of 3 primary colors R (red), G(green), and (blue). The laws of colorimetry state that any color can be derived by the combination of these three primary colors being the combination unique. From RGB other color, representations can be derived such as HSV. Selections of the best color space are one of the challenging tasks in image segmentation [24]. We take RGB into account because it is the most commonly used model for television systems, monitors, cameras, and smartphones. All these devices display color images by modulating the intensity of the three primary colors (red, green, and blue). In spite of RGB being widely used, it is not the most suitable color model for image segmentation purposes.
On the other hand, HSV is one of the color models used in an attempt to use ones closer to how humans perceive color. HSV has three components: hue (H), saturation (S), and value (V). H represents the "color", S is the dominance of that color ranging from unsaturated (shades of gray) to fully saturated (no white component), and V is the brightness. In recent years, HSV color space has gained the ability to support applications in noisy color image segmentation [25]. Also as it is stated in [26], HSV color space can recognize color with high intensities, making it easier to distinguish the objects of interest from the background. Therefore, HSVbased features are used in this work to explored the segmentation clustering algorithms as FCM or K-means.
The distance function is computed for each pixel represented by the vectors and .
• Euclidean: The euclidean distance is most commonly used [9], also it derives from
Pythagorean Theorem. This is influenced by greater units of measure and this vary with
the scale of each variable [
( , ) =
− )2
√
∑(
=0
( , ) = ∑ |(
• Manhattan: This distance stand out by calculating the absolute diferences between
coordinates of a pair of objects[9], also it is less noise sensitive [
( , ) = |( 3.3. Clustering Algorithms • Fuzzy C-Means [9]: Classical approaches result in strict partitions where each data function: point can only belong to one cluster. FCM clustering allows data points to belong to more than one cluster [28]. Each cluster is associated with a function that indicates the degree of each data point of belonging to an specific cluster. FCM performs the clustering by iterative searching for a set of fuzzy clusters and their associated centers. On this algorithm the user specify the number of clusters present in the set of data to be grouped. Then FCM partition the data into clusters by minimizing the objective =1 =1 ( , ) = ∑ ∑( )
‖ − ‖2 , 1 ≤ ≤ ∞ where { } =1
the parameter that we will compare using distances previously mentioned) from the data are the centroids of the cluster and ‖.‖ is an inner-product norm (this is to the − ℎ cluster center.
The FCM algorithm starts with random initial cluster centers and, at every iteration, it finds the fuzzy membership of each data point to every cluster using the following equation: and updating the centroids with: =
1 ∑ =1( ‖ − ‖
‖ − ‖ ) 2−1 =
∑ =1
∑ =1
⋅ (1) (2) (3) Algorithm 1 Pseudo-code of FCM Algorithm. Adapted from [29].
8: 9: 1: Fix , 2 < < ; , (e.g.,
= 0.001); 4: Choose any norm distance; 3: Fix maxIterations, (e.g., maxIterations = 100); 7: for = 1 to maxIterations do 5: Fix , 1 < <
∞, (e.g., = 2); 6: Randomly initialize 0 = 1, 2, … , cluster centers;
Update the membership matrix U using Eq. 2; Calculate the new cluster centers using Eq. 3; Calculate the new objective function using Eq. 1; − −1) < then The pseudo-code of the FCM is shown in Algorithm 1.
This technique is an unsupervised method, which means that no tagged data is needed.
Therefore when applying it in image segmentation, it is very useful because we only
need the image to the segment as the input data. On the other hand, due to FCM uses
the inner-product norm to find the nearest pixels, the sensitivity to noise is reduced. This
method is often used in pattern recognition and segmentation of images.
• K-means [
Non-hierarchical methods are characterized by two main steps. First, it assigns a cluster
to each datum, and then clusters are recalculated from data assigned to them.
Nonhierarchical methods clusters according to two criteria: distance or similarity.
Particularly, K-means works with distance criteria [
The algorithm solves a minimization problem, where the function to be minimized is the sum of the quadratic distances of each object to the centroid of its cluster, as the next equation shows: =1 ∈ ( ) = ∑ ∑ ∥ − ∥2 where is the number of clusters with their corresponding centroid and is the set of data whose elements are the objects represented by vectors, where each of its elements represents a characteristic or attribute. Then, to update the centroids we use the following equation: ( +1) = ‖ 1 ( ) ‖ ∑ ∈
( ) Algorithm 2 Pseudo-code of K-Means Algorithm. Adapted from [30] 1: input: (number of clusters), 2: (a set of lift ratios); 3: output: a set of clusters; 4: Arbitrarily choose objects from as the initial cluster centers; 5: repeat 6: 1. Based on the mean value of the objects, assign or reassign each 7: object to the cluster. 8: 2. Calculate the mean value of the objects for each cluster; and 9: update the cluster means. 10: until no change;
The pseudo-code of K-means method is shown in Algorithm 2.
This method is very efective in producing tighter clusters than hierarchical clustering when the clusters are globular.
Sensitivity ( /( + )), Specificity (( /( + )), and Accuracy (( + )/( + + + )) metrics were computed to determine how the diferent distance measures influence on the performance achieved by clustering algorithms to correctly distinguish pixels of object of interest from background ones. The parameters , , , and are obtained from the confusion matrix, and refer to the foreground pixels correctly classified as foreground, background pixels correctly classified as background, foreground pixels erroneously classified as background, and background pixels erroneously classified as foreground, respectively. Thus, sensitivity quantifies the ratio of pixels correctly classified as foreground over the total foreground pixels. Specificity quantifies the ratio of pixels correctly classified as a background over the total background pixels, and Accuracy quantifies the ratio of pixels correctly classified.
To test the proposed methodology, software routines were implemented in Python 3 using libraries like Numpy, Sys, Opencv, and plplot. Experiments were performed in Ubuntu 18.04 with kernel 4.18 installed in a laptop with an AMD processor with two cores running at 1.6 Ghz.
For experimental purposes, FCM and K-means use two centroids and one iteration. Particularly, FCM uses a fuzzier value of 1.5 based on the experimental setup introduced in [31].
This work uses a subset of 10 images from the Berkeley image dataset [32]. This dataset contains 500 natural images in format jpg along with their corresponding ground-truth (images correctly segmented). Each image of the subset contains one object of interest such as a swan, a plane, and a wildebeest in external environments with a resolution of 481 × 321.
All of the software routines implemented for testing purposes is available online at the
Experimental results depicted in the Tables 2 and 3 clearly exhibit that Canberra distance leads to less noise and pixels erroneously classified as foreground and background pixels in the majority of evaluated images. In contrast, in terms of accuracy, Canberra distance is higher by a value of 93.5%, in both FCM and K means implementations. However, based on Table 4, the greater maximum values of sensitivity values are reached by FCM with Manhattan distance by a 74.3%, meanwhile, K-mean outperforms when it uses Spearman one by a 74.2%. The other metrics perform that their maximum value is achieved in Canberra distance for both methods, FCM and K means.
Table 4 presents a comparison between averaged values between FCM and K-means. The column "dif" is the diference between the average, and the column "best" represents the method with the higher average value. Results presented in Figures 2, and 4 show that Canberra distance reaches the highest average value of accuracy and specificity. The performance was better at images where the object of interest contrasted with the background or was in a similar area. Besides, there was a background with a width color spectrum, so that some parts of it were identified as objects of interest.
This work explores the combination of RGB and HSV color spaces for segmentation, however, the segmentation is still a challenging task when the background and foreground are characterized by similar color values. The manual selection of the centroids manually achieves better outcomes than automatic selection approaches.
The eficiency of the clustering algorithms, using diferent distance measures has been evaluated with the accuracy, sensitivity, and specificity metrics. According to the results, the Canberra distance gives the best accuracy and specificity. Furthermore, the best sensitivity was achieved by the Manhattan distance applied in FCM, follow by the Spearman distance in Kmeans.
A limitation of the proposed implementation is that the number and values of clusters to be segmented out should be selected manually. In order to improve the utility, the proposed implementation should be facilitated with mechanisms that could adaptively determine the appropriate number of clusters to be segmented out. This is an important issue for future work.
The authors thank the valuable support given by the SDAS Research Group (www.sdas-group. com) and the head of the group Diego Pelufo. [9] A. B. Amina Dik, 1Abdelaziz El moujahid, A. Ettouhami, Weighted distances for fuzzy clustering, Applied Mathematical Sciences 8 (2014) 147 – 156. [10] S. Khanmohammadi, N. Adibeig, S. Shanehbandy, An improved overlapping k-means clustering method for medical applications, Expert Systems with Applications 67 (2017) 12–18. [11] S. Barak, T. Mokfi, Evaluation and selection of clustering methods using a hybrid group mcdm, Expert Systems with Applications 138 (2019) 112817. [12] P. K. Mishro, S. Agrawal, R. Panda, A. Abraham, A novel type-2 fuzzy c-means clustering for brain mr image segmentation, IEEE Transactions on Cybernetics (2020) 1–12. [13] S. Tyagi, S. Malhotra, D. Kumar, V. S. Verma, A. Bhardwaj, Mammographic image segmentation with modified fcm based clustering algorithm, AIP Conference Proceedings 2214 (2020) 020028. URL: https://aip.scitation.org/doi/abs/10.1063/5.0003604. doi:10.1063/5. 0003604. [14] P. Kavitha, P. V. Saraswathi, Segmentation for content based satellite image retrieval using fuzzy clustering, International Journal of Advanced Science and Technology 29 (2020). [15] R. Loohach, K. Garg, Efect of distance functions on simple k-means clustering algorithm,
International Journal of Computer Applications 49 (2012) 7–9. doi:10.5120/7629-0698. [16] D. Bora, D. Gupta, Efect of diferent distance measures on the performance of k-means algorithm: An experimental study in matlab, arXiv 5 (2014). [17] M. K. Arzoo, A. Prof, K. Rathod, K-means algorithm with diferent distance metrics in spatial data mining with uses of netbeans ide 8. 2, Int. Res. J. Eng. Technol 4 (2017) 2363– 2368. [18] A. Singh, A. Yadav, A. Rana, K-means with three diferent distance metrics, International
Journal of Computer Applications 67 (2013). [19] A. Román y Zubeldia, Implementación de pruebas para una hipótesis sobre la aplicación de distancia euclidiana para realizar agrupamientos en espacios multidimensionales, 2018. [20] M. Bora, D. Jyoti, D. Gupta, A. Kumar, Efect of diferent distance measures on the performance of k-means algorithm: an experimental study in matlab, arXiv preprint arXiv:1405.7471 (2014). [21] Y. Oike, M. Ikeda, K. Asada, A high-speed and low-voltage associative co-processor with exact hamming/manhattan-distance estimation using word-parallel and hierarchical search architecture, IEEE Journal of Solid-State Circuits 39 (2004) 1383–1387. [22] D. Androutsos, K. Plataniotiss, A. N. Venetsanopoulos, Distance measures for color image retrieval, in: Proceedings 1998 International Conference on Image Processing. ICIP98 (Cat. No. 98CB36269), volume 2, IEEE, 1998, pp. 770–774. [23] V. Kumar, J. K. Chhabra, D. Kumar, Performance evaluation of distance metrics in the clustering algorithms, INFOCOMP 13 (2014) 38–52. [24] H.-D. Cheng, X. H. Jiang, Y. Sun, J. Wang, Color image segmentation: advances and prospects, Pattern recognition 34 (2001) 2259–2281. [25] D. Bora, A. Gupta, F. Khan, Comparing the performance of l*a*b* and hsv color spaces with respect to color image segmentation, arXiv (2015). [26] S. Sural, G. Qian, S. Pramanik, Segmentation and histogram generation using the hsv color space for image retrieval, in: Proceedings. International Conference on Image Processing, volume 2, IEEE, 2002, pp. II–II. [27] D. Kaur, A comparative study of various distance measures for software fault prediction, arXiv preprint arXiv:1411.7474 (2014). [28] J. C. Dunn, A fuzzy relative of the isodata process and its use in detecting compact wellseparated clusters, Journal of Cybernetics 3: 32-57 (1973). [29] O. Moh’d Alia, R. Mandava, M. E. Aziz, A hybrid harmony search algorithm for mri brain segmentation, Evolutionary Intelligence 4 (2011) 31–49. [30] P.-Y. Zhou, K. C. Chan, A model-based multivariate time series clustering algorithm, in: Pacific-Asia Conference on Knowledge Discovery and Data Mining, Springer, 2014, pp. 805–817. [31] K.-L. Wu, Analysis of parameter selections for fuzzy c-means, Pattern Recognition 45 (2012) 407–415. [32] P. Arbelaez, M. Maire, C. Fowlkes, J. Malik, Contour detection and hierarchical image segmentation, IEEE Trans. Pattern Anal. Mach. Intell. 33 (2011) 898–916. URL: http://dx. doi.org/10.1109/TPAMI.2010.161. doi:10.1109/TPAMI.2010.161.