Monday, July 7, 2014

Reducing the Number of Colors (Part I)

In my last post I discussed a way to reduce the number of colors in grayscale image. So the natural step was to proceed to a color image. Let's start with a nice color image.

The color image is just a collection of a red, a green and a blue image.

The Ignorant Approach

The first thing I tried, just to see what would happen, was to try the algorithm I made for the grayscale image. That means repeating the process for the individual channels and later merging the result.
That works, but it doesn't give the result I am really looking for.

For some colors this approach works. The sky is a nice color blue, some bright yellow accents on the plane come out as I wanted, but some color like on the right wing seem wrong.
What the program found were 6,6 and 7 peaks for the color channels. That means that if a certain value of blue is very dominant that value will be picked. But the area that belongs to that color might not be purely blue.

Similar But Different

Here's an example of 6 colors with the same maximum blue value of 255, but with different red and green values.

Square with different RGB values, but the same blue value.

You can imagine that one of these colors is not found as a dominant. If a certain color is found it has to give rise to a peak in he histogram of all three colors.

The picture above is an example in two color dimensions, the x-axis representing green and the y-axis blue. The dots are both colors that occur in some image. But perhaps the one in the top is found in way more pixels then the one in the bottom. In the end the green value which is the same for both colors will be found probably. But the blue value of the lowest color might not be found. Every pixel with a color close to that bottom color will be assigned a green value that is correct, but the new blue value could be miles off.

3D RGB Space

For me the problem was beginning look a bit clearer, also a bit more difficult. When you look at all the colors that occur in an image there are thousands. Some are quite similar, like all those colors blue in the sky of our example image. Let's see what all these colors look like in the 3D RGB space.

3D RGB Space of the Spitfire image

What I have drawn here is all the pixels in the image placed in the RGB space. Easily understandable points are (0,0,0) which is black in the front and (255,255,255) as white in the back. Along the diagonal axis are all the gray colors. Off diagonal RGB values are the other colors, and you can see some groups, and a lot of empty space. What you can't see how many identical RGB points there are, and how many of are all alone.
That is why I made the same image but here I changed the size of the circles to show how many pixels have that color.

We are looking at it from a different angle, but it shows one thing; there are a lot of blue pixels.

That's about as far as I've come right now. What I intend to do next is to find the regions of this image where a lot colors are found close together (like that blue area in the top). So this is similar to finding a peak in 1D histogram, but than more like finding a 3D peak (a blob with the highest density).
I am still thinking of what the best approach is going to be for this. 

Stay tuned!

Tuesday, July 1, 2014

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.