Reducing the number of colors in an image

OK first all, one of my most favorite astronaut pictures showing Anna Lee Fischer. To me it looks it's from a movie or something, it's just that cool.

Anna Lee Fischer

Long story short, I was wondering if I could reduce the number of colors (the grays) in this picture. Just for fun and exercise. I could try an image/photo editor, but it's always more fun to do it yourself right.

I went to work in Matlab and to just show you the end result first (before all long boring programming details). Tadaa!

Only 5 grays left

How it's done

The main idea I had was finding the colors that are most dominant. We therefore look at the histogram of the image as shown below. Values run from 0 to 255 on the x-axis and the y-axis represents the number of occurrences of a certain gray value in the image.

Something I find strange are the very regular holes in the histogram where a certain gray value apparently never occurs. Apart from that it's not a smooth line, there are about 5 local maxima visible. 

How do we find those?

Finding the peaks

I first removed the holes by using the average of the gray values around it. After that I applied a Gaussian smoothing. Before I tell you about how I find the peaks I'll first show the result of smoothing and finding the peaks.

You can see that the line is now very smooth and there are small red lines to show where the peaks are found. I find it a very satisfactory result. It may seem like the first and last line are just a bit off, but that is only because the steps are integers and the lines are placed on the integers. So i.e. to me and you the peak should be at 18.7, but it is found at 19.

The short explanation of how the peaks are found is this. I let the program walk along the line until it reaches the top. That means the next position has a lower value instead of a higher value. After that we continue to find the valley, so look for a position where the next element is higher instead of lower. And we go back to finding the next peak. I'm only interesting in the peaks of course. I don't tell the program how many peaks there are, just to stop when it's at the end of the histogram. 

Changing the colors 

To create the new image I take the value of every pixel in the original image and look to which peak value it is closest. Then it is changed to that peak value with a preference to the lowest/darkest value. The original image was pretty noisy so you can see this in the end result. 

When you use this method you have no control over how many colors the end result will have. This can be an advantage or a disadvantage depending on your needs. But I like it that we don't put in any previous knowledge and the program itself finds the most dominant values.

I guess this whole process or parts of it has a name, but it was still nice to built myself from scratch.

I'll try how the program works with color images, which will need some adjustments.