Color segmentation

For one of my project I needed algorithm which tells customer how many colors will be needed to print their picture on t-shirt for example. The main problem is that you cannot use CMYK colors in my case (technology limit) but separate picture into several PANTONE colors.

This is orginal picture:

I've tried reduce picture to 10 colors with imagemagick quantize function (php)

quantizeImage( 10, Imagick::COLORSPACE_RGB, 0, false, false );

and counts percentill for each 10 colors. This method gives not satisfied results for me because some pictures have dominant color (background) and it is hard to choose right threshold which colors can be droped. Look at this picture:

and try to find an appropriate threshold. If we drop colors below 1% for example we will lost two blue colors which seems to be important. If we drop colors below 0.5% we will have several not important gray colors. So color quantization is not a good way to solve my problem.

I've been searching for another approaches and found term "color segmentation" or "image partitioning". Some segmentation code is in imagemagick, but it is terrible slow and it gives totally different colors. Mean shift algorythm looks promising but I did not find usable implementation (except of java imageJ program). Finally I found mean shift algorythm in C++ by Dorin Comaniciu and Peter Meer -

http://www.caip.rutgers.edu/~comanici/segm_images.html :

A general technique for the recovery of significant image features is presented. The technique is based on the mean shift algorithm, a simple nonparametric procedure for estimating density gradients. Drawbacks of the current methods (including robust clustering) are avoided.

Their code is very old and not compilable on modern Linux distributions so I've modified it and fix some bad memory referencing and fork that project onto http://code.google.com/p/colorsegmenter/. There is source code and binary.

This program will segment our test picture into several colors (undersegmentation):

which is very nice because you does not have to mess with thresholds etc.

This program has two another modes

oversegmentation:

quantization:

If you know another implementations or techiques, please share it in discussion or send me email festr2@gmail.com.