Report

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