Tutorial # 9

```Tutorial # 9
Nov. 21, 2013
1
Segmentation
Isolating a region/regions of interest in an image
Useful for:






2
Collect more meaningful data from an image
Easier analysis
Locate objects
Locate boundaries
K-means clustering
Unsupervised clustering algorithm



Classifies input data points into K classes based on their inherent
distance to each other
Points are clustered around centroids/means
∀ = 1 …
Which are obtained by minimizing:

=
−
2
=1
Where there are K clusters  ,  = 1, 2 …  and  is the centroid of all
points
Ref:
http://www.ics.uci.edu/~dramanan/teaching/ics273a_winter08/projects/avim
_report.pdf
3
Example – 1 Channel
Given a gray scale image, use K-means to segment the
image. Choose K = 2 (Cluster A and Cluster B)

4
1
5
3
2
6
2
5
5
1
1.) Calculate the histogram
3.5
3
2.5
2
Frequency
1.5
1
0.5
0
0
5
1
2
3
Intensity
4
5
6
2.) Initialize centroids
Randomly initialize centroids
= 1
= 3

3.5
3
2.5
2
Frequency
1.5
1
0.5
0
0
6

1
2
3
4
Intensity
5
6
3) Cluster intensities based on distance
1
2
3
5
6
Distance
with
0
1
4
16
25
Distance
with
4
1
0
4
9
Note: Points with intensity 2 can be classified as either, but our algorithm
chooses the first cluster.
7
4.) Recalculate centroids
New centroids

2 = 1.5
2 = 4.8
2
3.5
3
2.5
2
Frequency
1.5
1
0.5
0
0
8
1
2
2
3
4
Intensity
5
6
5.) Recluster intensities using new centroids
1
2
3
5
6
Distance
with 2
0.25
0.25
2.25
12.25
20.25
Distance
with 2
14.44
7.84
3.24
0.04
1.44
We have a new clustering!
Recalculate the centroid.
9

New centroids
3 = 1.8
3 = 5.25
3
3.5
3
2.5
2
Frequency
1.5
1
0.5
0
0
10
1
2
2
3
4
Intensity
5
6
1
2
3
5
6
Distance
with 3
0.64
0.04
1.44
10.24
17.64
Distance
with 3
18.063
10.56
5.063
0.63
0.56
Recalculate the means and we find:
3 = 4
3 = 4
This means we can stop and we have our final
clusters
11
Final Clustering/Segmentation
A
B
A
A
B
A
B
B
A
This answer would change if we chose K = 3. Also, the number of iterations
would change depending on the starting centroids.
12
Real example
13
Real example
14
Number of Clusters: K = 1
15
Number of Clusters: K = 3
16
Actual Segmentation
Cluster 1
17
Cluster 2
Cluster 3
Similar intensities
18
Number of Clusters: K = 5
Oversegmentation
– K is too high
19
What about colour segmentation?



Different regions of interest may have the same intensity
but different colours
Can use the colour information of an image to improve
segmentation
Let’s focus only on the colour and remove the intensity
by converting to a different colour space:



20
HSI (Hue Saturation Intensity)
YCbCr (Luma, Blue difference, Red difference)
L*a*b* (Lightness, a* - colour that falls on the red-green axis,
b* - colour that falls on the blue-yellow axis)
Using L*a*b* space


Our K-means problem becomes a 2D problem
Our centroid will now have two variables, one defining
the intensity of the a* channel and one defining the b*
channel
21
http://www.mathworks.com/help/releases/R201
3b/stats/kmeans.gif
K=1
22
K=3
K=5
Cluster 1
23
Cluster 2
Cluster 3
```