Submission Format. Electronic submission on Canvas is mandatory. Submit a zip file containing:
• a pdf file with the source code (excluding libraries), the resulting images and a brief explanation of the implementation.
• the code,
• the output images.
Problem 1: k-means Segmentation. (35 points) Apply k-means segmentation on white-tower.png with k=10, according to slide 43 of Week 7. The distance function should only consider the RGB color channels and ignore pixel coordinates. Randomly pick 10 RGB triplets from the existing pixels as initial seeds and run to convergence.
After k-means has converged, represent each cluster with the average RGB value of its members, creating an image as in slide 51 of Week 7.
Problem 2: SLIC. (65 points) Apply the SLIC algorithm to wt slic.png. See slide 79 in Week 7, but implement the following steps:
1. Divide the image in blocks of 50×50 pixels and initialize a centroid at the center of each block.
1
2. Compute the magnitude of the gradient in each of the RGB channels and use the square rootof the sum of squares of the three magnitudes as the combined gradient magnitude. Move the centroids to the position with the smallest gradient magnitude in 3×3 windows centered on the initial centroids.
3. Apply k-means in the 5D space of x,y,R,G,B. Use the Euclidean distance in this space, but divide x and y by 2.
4. Optionally: only compare pixels to centroids within a distance of 100 pixels (twice the blocksize) during the updates.
5. After convergence, display the output image as in slide 79: color pixels that touch twodifferent clusters black and the remaining pixels by the average RGB value of their cluster.
Requirements and notes.
• You are allowed to use image reading and writing functions, as well as plotting functions, but you are not allowed to use filtering, edge detection or other image processing functions. You can convert the images to a different format for reading them.
• The complexity of k-means is linear with respect to the number of pixels and k. Start developing on small images with small values of k.
2
