Unsupervised Image Segmentation Using Expectation-Maximization Algorithm

In this post, I would like to post my work related to Unsupervised Image Segmentation Using Clustering Algorithms like K-means clustering and Expectation-Maximization Algorithm. The Expectation-Maximization Algorithm is also commonly known as EM algorithm.

The EM algorithm for image segmentation works on the basis of maximum likelihood parameter estimation. Th important difference between K-means and EM algorithm is about assigning

fractional membership of any given point to the clusters.

I will discuss the general procedures of these algorithms.  Matlab is used as the tool.

K-means Clustering Algorithm:

Step 1: Initialize the centroids with k random intensities

Step 2: Repeat until the algorithm has converged:

             • Cluster the points based on the distance of their intensities from the centroid intensities

             • Compute the new centroid for each of the clusters

EM Algorithm:

Given Data X = {x(1), ..., x(N )}, where x(k) ∈ n

Step 1: Introduce hidden or latent variables Z such that ln p(X|Z, Θ) has an analytically tractable form.

Then construct complete data model p(X, Z|Θ) = p(X|Z, Θ)p(Z|Θ)

Step 2: Initialize parameter guess Θ(0)

Step 3: Repeat for t = 1, 2, 3 . . .

E step: Compute

Q(Θ, Θ(t) ) = E(Z|X,Θ(t)) [ln p(X, Z|Θ)];

M step: Choose

Θ(t+1) = arg max Q(Θ, Θ(t) )

Stop |Θ(t+1) − Θ(t) | ≤ , where is some consequence criteria

Output Final Parameter estimation Θ

The Image Segmentation procedure using EM algorithm is shown below. 

Unsupervised EM Algorithm for Image Segmentation: 

Goal: Estimate Θ and number of segmentation

Input: Image vector X = { x[1], x[2], . . . , x[N^2] }^T

Step 1: Set initial minimum message length Lmin = +∞

Step 2: for m = Mmax : −1 : Mmin

Initialize θ(0) = θk-means

Update by EM θm = θEM

Compute L(θ, x) 

if L(θ, x) ≤ Lmin , then

Lmin = L(θ, x); θ = θm ; Mbest = m

end if

end for

Output Estiamted parameter θ and number of segmentation Mbest

Results:

Peppers Image

City Image