K-means for Segmentation

Aseem suggested a simple experiment: Running K-means on rgb values of pixels. The initial segmentation outcome was promising. Two major problems that were apparent in the output was as follows:

1- Boundary pixels may be assigned to wrong clusters due to anti-aliasing.
2- Two elements with the same color would fall into one cluster.

Boundary clean-up

I tried a few techniques to fix the first problem. I ended up doing the following that gave the best result:

1- Before running k-means to determine cluster centers, I excluded edge pixels from k-means to make sure they do not form a separate cluster.
2- For the pixels that fall close to a segment boundary, I perform a soft assignment process. The output end up having a clean boundary matt.

Here are the results after cleaning boundary matt:

https://dl.dropboxusercontent.com/u/20022261/reports/segmentation_using_kmeans.html

Second level of segmentation 

In images that are segmented using only colors, seperate design elements tend to fall into the same cluster because they have the same color. We discussed two approaches to fix this problem:

1- Add certain features to RGB features to improve k-means clustering. One could hope that improved features would help improve clusters that k-means would generate. We discussed Stroke Width Transform, Texture features (LBP and local image statistics) and spatial features. We also discussed a metric learning process based on stochastic gradient descent to learn weights for features.

2- Separate disjoint elements of one cluster and join them up according to their appearance. We thought it is reasonable to process text elements separately using specialized features that could include Stroke Width Transform.

We decided to investigate the second idea first. I began implementing a basic version of Stroke Width transform that fits our application.