E-M Algorithm
The idea behind the Expectation Maximization (EM) algorithm is to find the optimal parameters that maximize the expectation of the probability of a pixel belonging to any class. The model used is a mixture of Gaussians. The number of Gaussians or classes is fixed and is a known parameter in this problem.
To begin, let us define the feature vector. This vector contains characteristics that describe the group of pixels that we want to identify.
Feature vector: x = [x, y, hue, saturation]t . The features are the pixel coordinates (x and y) and its color (hue and saturation).
To calculate the probability of a pixel given that it belongs to a certain class k with parameters θk (αk, μk and Σk) we use the following Probability Density Function (PDF):
The total probability for a pixel is the sum of the probabilities that it belongs to each class (mixture model).
Where αk is the probability that the pixel belongs to a class k, and Θ is the parameter space {θ1, …, θK}.
The EM algorithm is an iterative calculation of the expectation of the missing data (in this case the class to which each pixel belongs to) and the model parameters at that expectation value. This iteration is done until the parameters stop changing by less than a threshold ε.
The steps would be:
1.- Initialize the model parameters θk(0)
2.- Calculate the expectation of our missing data Ekn(i+1) using the current values of the model parameters θk(i).
3.- Calculate the mew model parameters θk(i+1) with the new estimate of the missing data αk(i+1).
4.- Calculate the maximum relative error ε = MAX((θk(i+1) - θk(i))/θk(i)) and compare it with the threshold. If it is greater go to step 2, else end.
The expectation of the missing data is calculated using:
The new model parameters are calculated with the following formulas:
Issues
A problem that is not evident at first is how to calculate the feature distance from the mean. The algebraic distance is fine for the pixel coordinates but is not so for hue. Hue is a periodic value like an angle. When calculating the distance for this feature one has to make sure the value falls inside the range [0 - 359].