Image Segmentation: K-Means and EM AlgorithmsChris VutsinasAbstractIn this paper, two algorithms for image segmentation are studied. K-means and an Expectation Maximization algorithm are each considered for their speed, complexity, and utility. Implementation of each algorithm is then discussed. Finally, the experimental results of each algorithm are presented and discussed.IntroductionBoth of the algorithms under consideration date back originally over 30 years. A K-Means algorithm was introduced by name in 1967 [1] while an EM algorithm was somewhat formalized ten years later in 1977 [2]. The dates attached to these algorithms can be somewhat confusing since the EM algorithm can be considered a generalized K-Means algorithm. It is safe to assume that both algorithms existed previously without formalization or a complete explanation of the theory involved. In order to understand how to implement each algorithm, the class notes and Wikipedia [3,4] were relied on heavily. In addition, a few of the papers found in the references section were of limited assistance.The K-Means algorithm and the EM algorithm can both be used to find natural clusters within given data based upon varying input parameters. Clusters can be formed for images based on pixel intensity, color, texture, location, or some combination of these. For both algorithms the starting locations of the partitions used are very important and can make the difference between an optimal and a non-optimal solution since both are susceptible to termination when achieving a local maximum as opposed to the global maximum.K-Means can be thought of as an algorithm relying on hard assignment of information to a given set of partitions. At every pass of the algorithm, each data value is assigned to the nearest partition based upon some similarity parameter such as Euclidean distance of intensity. The partitions are then recalculated based on these hard assignments. With each successive pass, a data value can switch partitions, thus altering the values of the partitions at every pass. K-Means algorithms typically converge to a solution very quickly as opposed to other clustering algorithms.Expectation-Maximization on the other hand relies on soft assignment of data to a given set of partitions. Every data value is associated with every partition through a system of weights based upon how strongly the data value should be associated with a particular partition. EM algorithms rely very heavily on the assumption that the initial partition values are close to the natural clustersof the given data. MethodologyTwo K-Means algorithms have been implemented. The first clusters the pixel information from an input image based on the RGB color of each pixel, and the second clusters based on pixel intensity. The algorithm begins with the creation of initial partitions for the data. The clustering based on pixel color will be considered first.In order to try to improve the runtime and results of the algorithm, partitions which are equally spaced were chosen. Initially, eight partitions were chosen. The partitions represented red, green,blue, white, black, yellow, magenta, and cyan or the corners of the “color cube”. With the initialpartitions chosen, the algorithm can begin. Every pixel in the input image is compared against the initial partitions and the nearest partition is chosen and recorded. Then, the mean in terms of RGB color of all pixels within a given partition is determined. This mean is then used as the new value for the given partition. If a partition has no pixels associated with it, it remains unchanged. In some implementations, a partition with no pixels associated with it would be removed; however, these partitions are simply ignored in this implementation. Once the new partition values have been determined, the algorithm returns to assigning each pixel to the nearest partition. The algorithm continues until pixels are no longer changing which partition they are associated with or, as is the case here, until none of the partition values changes by more than a set small amount. In order to gather more results, the initial partitions used were varied by addingand removing partitions.In a nearly identical setup, a second K-Means implementation was made using the grayscale intensity of each pixel rather than the RGB color to partition the image. The starting partitions were chosen as equally spaced values from 0 to 255. The number of partitions used, as in the color segmenting setup, was varied in order to increase the number of results available and to study the effects of varying this parameter.The EM algorithm is very similar in setup to the K-Means algorithm. Similarly, the first step is tochoose the input partitions. For this case, the same initial partitions as used in the color segmentation with K-Means were used in order to make the comparison of results more meaningful. Here, RGB color was again chosen as the comparison parameter. The EM cycle begins with an Expectation step which is defined by the following equation:This equation states that the expectations or weight for pixel z with respect to partition j equals the probability that x is pixel xi given that µ is partition µi divided by the sum over all partitions k of the same previously described probability. This leads to the lower expression for the weights. The sigma squared seen in the second expression represents the covariance of the pixel data. Once the E step has been performed and every pixel has a weight or expectation for each partition, the M step or maximization step begins. This step is defined by the following equation:This equation states that the partition value j is changed to the weighted average of the pixel values where the weights are the weights from the E step for this particular partition. This EM knxxnijiee1)(21)(212222knnijiijxxpxxpzE1)|()|(][miiijjxzEm1][1cycle is repeated for each new set of partitions until, as in the K-Means algorithm, the partition values no longer change by a significant amount.Experimental ResultsK-Means:Parameter: RGB Color Original K = 2 K = 8 K = 11 K = 14 K = 15Parameter: Grayscale Intensity