Computer Vision: Image Segmentation with k-Means and Mean Shift

 Image Segmentation is the process of dividing an image to segments such that each segment has meaning. Segmentation is to group together similar pixels, if they share similar semantics. We are going to look at a few computer vision algorithms for image segmentation, each based on a machine learning concept/method. 

We looked at one segmentation algorithm already earlier in the course. Active contour is having an approximate boundary around the object, and evolve (move) the contour to fit the exact object boundary. So far, we have looked at simpler images that has clearly a foreground and a background. 

How do we segment all the regions into manmade vs natural objects, and there is no one single segmentation. 

There are many theory about how people do segmentation. One principle say that we rely heavily on our past experiences to group things together, to segment out and extract objects from images. 

It's sometimes hard for computers to detect if an object is emerging or not. 

You can argue whether an image is really there or not. The process of grouping is quite subjective. Some people do shallow segmentation, others do finer segmentation. It's not easy to figure out how we are segmenting, a lot of the reason is because of ambiguity. 

Broadly we can think about segmentation in 2 ways:

1. We group pixels together that are semantically similar, we are grouping due to high-level similarity.

2. We group pixels together which look similar.

Top-down segmentation is easier for humans, but hard for computers.

We want to group pixels which look similar, which is the bottom-up segmentation.

2 pixels may look similar if they have the same brightness, color, similar texture, pixel position, etc. 

For each pixel, we represent each pixel as a vector of the features of pixels. If black and white, we can represent intensity. What about the the color. There would be 3 numbers in the feature vector, RGB, one for each color.   

We can represent each pixel with the red, green, and blue values, and each pixel can be represented as a 3D feature vector.  

The next thing we do is to take each of these vectors and represent them as points in the 3-dimensional space. 

Each point is represented by a point in 3d vector space as follows: 

Each point represents one pixel in an image, and the coordinates of a point represents the color of the corresponding pixel.

Given an image on the left, can you create a feature space? Because we don't know the location of said pixel; as a result, we need the coordinates. 

The distance between points can be represented as a function of the distance between the pixels.   The more similar the two pixels, the closer the corresponding points will be in the feature space, and vice versa. We can use distances to identify similar pixels in the image. We use clusters in feature space to group together similar pixels in the image. 

We need to define a notion of distance between 2 points. One definition that is used a lot is the simple Euclidean distance.

Let i and j be 2 pixels whose features are fi and fj. 

The intuition is similar pixels will be in clusters. By finding these clusters, we can segment the image, which is grouping similar images together, assigning one label to all the images in the cluster. 

So far, we only talked about similarity only in terms of color. It's possible for an object that have similar colors which are in similar areas of the image. You can have a feature vector that groups both colors and position. 

So how do we identify these clusters, to group together points that are close together?

Let's start with a simple example with a 2D vector space with the points in the space, sort of grouped together in 3 distinct vectors. Just to make things easier, suppose you told just to make 3 clusters. You want to assign a label to it so that points in the same cluster should be assigned a label. We need to assign the cluster labels to each of these points. We randomly pick points of labels to each space. There will be a red label, a green label, and a blue label, and we can think of these points as the centers of the points/color/whatever feature that is to be measured. 

Step 1 is to randomly generate centroids of the 3 clusters. 

Step 2 is to find the nearest cluster center for each of the data points. 

Step 3 is to recompute the mean location of the cluster, which is the average of all of the points in the cluster. These locations can now be thought of the new cluster centers. Now perform step 2 again, which the labels of the points no will get updated

Step 4 is to repeat steps 2 and 3 until convergence. 

We cannot guarantee that we can always find the certain cluster, but we can get something reasonable with high probability. 

Clustering:

1. Pick k points randomly as the initial centroids (m1, m2, ..., mk) of the k clusters in feature space.

2. For each pixel xj find nearest cluster mean mi to pixel feature fj and assign to cluster i

3. Recompute the mean 

We can split and image into different segment. All brown points are assigned to one segment, and the blue points corresponds to blue segments. Let's increase the number of the number of segments to 8. 

If there is an image like van Gogh, pixels with the same color is far apart, which makes it extremely hard to look for segments that are spatially compact.

We should define similarity not just in terms of color, but in terms of location as well. In general, feature vector should have more property, like if you include (k = 16, {R,G,B,x,y} - space)

Of course, the features are 5-dimensional now, especially if 2 points are close, meaning the corresponding pixels are of similar colors and similar location as well. This gives us more spatially proximate locations, using color, location, gradient, and texture, which records different kinds of color and segmentation. Below is a segmented image of still life. 

Overall, we've looked at K-Means clustering, and it's fairly intuitive and fast algorithm easy to implement as well, which requires specifying the number of clusters, and sensitive to initialization. These images are also not super robust to outliers.

One method was an idea called mean shift. Suppose we have a bunch of pixel features. Assume we just have a bunch of pixels and a mean space. We can see that certain regions of space which have a high density and other regions that are more sparse. We can represent a density distribution as a histogram, or 3D plot, and whichever location has a higher density of points gets a higher peak, or larger value.

The first picture shows the pixel feature distribution. The second picture shows the normalized density. 

In each location of the space, we have created a peak, and the height of the peak indicates the density features of the following distribution. 

Now this plot is a bunch of mountains and hills, and the next question is, "what does each hill represent?"

Each point represents a local maxima, but what is it a local maxima of? The height is the density of points and each points corresponds to many clusters, and the peak of the hill is the center of the cluster in feature space. 

Suppose which cluster a pixel in an image we want to determine is assigned to. How do we do it? We look at the pixel feature and what we do is to make the feature climb the steepest hill its neighborhood, climbing up in the strongest positive gradient. 

Once you have done this for every pixel, we will have a label for each pixel 

We have the intuition here on how mean shift works, and we will look into the details in a minute. 

How do we actually implement this? Give a feature space in an image (not the image, but the FEATURE) space where one dot correspond to a pixel feature.

Let's pick a sample pixel, and move the point to a region of high density of dots. We want to do this iteratively, and first look at the small local window around the point. We can compute a point by taking the average of all the dots within a window, taking a average, or even a weighted average, where the points closer to the center get a higher weight.

We shift a point to the mean location, and keep repeating this step until convergence. We climb the steepest hill in its local neighborhood. We find the centroid in a new window, and new location, and go up and down, in a low region for zero high-density.

We repeat this process for all the pixels until we reach a cluster center, and all the pixels that reach and converge to the same location is assigned the same label, meaning they belong to the same cluster. 

All the features at the same hill, will get the same label, and we want to get the same cluster for the hill. 

The means shift algorithm:

Given: Distribution of N pixels in the feature space.

Task: Find modes (clusters) of distribution.

Clustering.

1. Set mi = fi as initial mean for each pixel I

2. Repeat the following for each mean mi

    a. place window of size W around mi

    b. compute centroid m within the window. Set mi = m.

    c. stop if shift in mean mi is less than threshold ε. mi is the mode.

3. label all pixels with the same mode as belonging to the same cluster. 

There are many applications for this in computer vision and machine learning. 

One thing that will impact the final number of clusters is the window size. The windows might be the size of the feature space and all of the points will be assigned to the same cluster. The maximum density of points is the location where the height is the maximum, where the density is the maximum. 

The next question is how to pick the initial point. We look for the location of the feature itself. If there is no point within the circle, then the point itself can be a cluster center, and we can get as many clusters as the number of features, but that's not good.

Features only based on color will disregard the spatial locations of the pixels. We want to divide a thin strip into multiple clusters, depending on how to choose features, and what you really want your clustering algorithm to do. 

Here is K means vs mean shift, and mean shift is far right and K means is center.  

Here is another one. 

Mean shift does a reasonable job vs K-means.

Mean shift algorithms are simple but computationally very expensive. The question is, what is the unit? It's in a space of a feature vector, the feature space. So if your feature spaces is arguably go from 0 to 255, unit variable is heavily dependent on what your features are.

Mean shift finds an arbitrary number of clusters, with no initialization required. The clustering also depends on a certain window size W.  Both algorithms work outside and can be discontinued to be used. It doesn't have to depend on more features in the feature space and can be expensive and include something like HAAR.