CS 766: Computer VisionHomework #2Image Segmentation using Mean ShiftDue: Tuesday, October 17, 2006General Information• This homework is based on the mean shift segmentation algorithm; papers describing this method are in~cs766-1/public/html/fall06/hw/hw2/papers/• Provided MATLAB functions are in~cs766-1/public/html/fall06/hw/hw2/code/• Provided test data (images and pts.mat) are in~cs766-1/public/html/fall06/hw/hw2/data/• Do not print out your MATLAB code listing. Please submit your code to the hw2 handin directory.Mean Shift ClusteringThe Mean Shift algorithm clusters an n-dimensional data set (i.e., each data point is described by a feature vectorof n va lues) by associating each point with a peak of the data set’s probability density. For each point, Mean Shiftcomputes its associated peak by first defining a spherical window at the data point of radius r and computing themean of the points that lie within the window. The algor ithm then shifts the window to the mea n and rep e ats untilconvergence, i.e., until the shift is less than a threshold (e.g., 0.01). At each iteratio n the window will shift to amore densely populated portion of the data set until a peak is rea ched, where the data is equally distributed in thewindow. Implement the peak searching processes as the functionfunction peak = findpeak(data,idx,r)where data is an n × p matrix containing p data points, each point is defined by an n-dimensional column vector offeature values; idx is the co lumn index of the data point for which we wish to compute its assoc iated density peak;and r is the search window ra dius.Implement the meanshift function, which calls findpeak for each point and then assigns a label to ea ch pointaccording to its peak. This function should have the syntax:function [labels,peaks] = meanshift(data,r)where labels is a 1 × p vector that has an entry for each data point of data storing its asso c iated cluster label, andpeaks is an n × p matrix storing the density peaks found using meanshift for each data point. Peaks should becompared after each call to findpeak and similar peaks should be merged. For your implementation, consider twopeaks to be the same if the distance be tween them is ≤ r/2. Also, if the peak asso c iated with a data point is foundto already exist in peaks, then for simplicity its computed peak is discarded and it is given the label of the alreadyexisting peak in peaks.1Speeding up the AlgorithmAs described so far, the Mean Shift algorithm is too slow to be used for image segmentation where each pixel is adata point. Therefore, you should incorpora te the following two speedups into your implementation. Upon finding apeak, the first speedup will be to associate each data point that is at a distance ≤ r fr om the pea k with the clusterdefined by that peak. This speedup is known as the “basin of attraction” and is based on the intuition that pointsthat are within one window size distance from the peak will, with high probability, co nverge to that peak.The second speedup is based on a similar principle, where points that are within a distance of r/c of the searchpath are associated with the converged peak, where c is some constant value. Use c = 4 for this assignment.Incorporate both of the above speedups into your implementa tio n of meanshift. To realize the second speedupyou will need to modify findpeak as follows:function [peak,cpts] = findpeakopt(data,idx,r)where cpts is a vector storing a 1 for each point that is within a distance r/4 from the path, and a 0 otherwise .Since MATLAB is optimized for matrix operations, not loops, try to avoid using loops in your functions wheneverpossible. Instead, use matrix manipulation. For example, if you want to select all points that have been labeled ”1,”instead of writing a for loop you could write:found = find(labels == 1);currdata = data(:,found);which uses the find command to return the indexes of the elements o f labels that match the Boolean expression,which in this case is ”== 1”. Then data(:,found) selects tho se columns whose indexes are listed in the vectorfound.Here’s another MATLAB hint: say you are trying to find points in a matrix A that are closer than r to the pointof index idx in A. You can do it with a for loop this way:for i=1:size(A,2)R(i)=norm(A(:,i)-A(:,idx));endfind(R<r)But this is way too slow in MATLAB. The following is much faster:n = size(A,2)find(r>sqrt(sum((A - repmat(A(:,idx),1,n)).^2,1)))Debug and test your algorithm, both with and without the two speedups, using the prov ided dataset pts.matwhich contains a se t of 3D points that belong to two 3D Gaussian distributions. Compute results using r = 1, 2,and 4 and plot each result sepa rately using the provided function plot3Dclusters.Image SegmentationNext, build upon your implementation so that it can be used to perform ima ge segmentation. To do so, implementthe functionfunction segIm = meanshiftSegment(im,r)where im is an input image or, more generally, an image feature matrix, and r is the parameter associated with theMean Shift algorithm. The output segmented image is then constructed using the cluster labels and peak values .That is, the output image is constr ucted by assigning a different color va lue (fr om the peak value) to each label andcoloring pixe ls in the output image accordingly.Note that Mean Shift clusters use the Euclidean distance metric. Unfortunately, Euclidea n distance in RGB colorspace does not correlate well to perceived difference in color by people. For e xample, in the green portio n of thesp e c trum large distances are perceived as the same color, whereas in the blue part of the spectrum a small distance2may represent a large change in perceived color (see Figures 6.13 and 6.14 of Forsy th and Ponce). For this reason youshould use the non-linear LUV color space. In this space Euclidean distance better models the perceived differencein color. In meanshiftSegment clus ter the image data in LUV c olor space by first converting the RGB color vectorsto LUV using the provide d MATLAB function rgb2luv. Then convert the resulting cluster centers back to RGBusing the provided MATLAB function luv2rgb.ExperimentsSegment the images sunset.bmp and terrain.bmp using r = 5 and 10. Given an input image file, you’ll need toread the image into MATLAB and then convert it into the matrix form required by data. If the feature vector issimply the 3 LUV color values at a pixel, then you’ll have to create a 3 ×