Color Quantization and other random musings...

Last time around, I was about to start up on the color quantization and I guess the most important part of this application... which would actually end up giving the final image a cartoonized look.

Now we had done a similar approach called K-means sorting in one of our assignments, which essentially did do the same thing, but had a couple of drawbacks. Firstly, the bin values had to be hardcoded and secondly, this method requires multiple iterations, which is bound to slow down the entire process. And there is no guarantee that even after a fixed number of iterations, the solution would converge and the final result would be the same as when random bin values would have been picked.

So the task in front of me was to come up with a fast yet flexible method, which would actually take color values for the bin from the image. I came across the 'Median Cut' method, which is supposed to be the one of the best methods for color quantization. The premise behind median cut algorithms is to have every entry in the color map represent the same number of pixels in the original image. In contrast to uniform sub-division (read Hardcoded b, these algorithms divide the color space based on the distribution of the original colors. The algo can be given as follows:

1. Find the smallest box which contains all the colors in the image.
2. Sort the enclosed colors along the longest axis of the box.
3. Split the box into 2 regions at median of the sorted list.
4. Repeat the above process until the original color space has been divided into n regions, where n is the number of bins.

I was under the impression that this process might not be too fast, but even on the CPU, the creation of the bins executes pretty fast!! Nice!!

So I did this step in 2 parts... the creation of the bins on the CPU and the actual quantization in a fragment shader, by passing the bins as a texture, thus reducing the number of registers used.

In the meantime, I decided to dabble once again on the edge detection front, since my current approach was just a hack, by tweaking one of the parameters of the bilateral filter. So I decided to use the Sobel filter again, but this time I decided to threshold the output, and this did work wonders to the output! So right now I have edges and no noise! Joy to the world!!

So finally, my program comes out to be a 3-pass thing...

1. First pass: input: image, output: bilaterally filtered image
2. Second pass: input: bilaterally filtered image, output: edge detected image
3. Third pass: input: edge detected image, output: color quantized image, rendered to the screen

Original Image

Bilateral filter

Edge Detection

Color Quantization

Currently, I have incorporated both videos and static images into the program, so I am getting outputs in both cases. But here are a few problems, which I hope to smooth out in the next few days:

1. The output video frame rate isn't the same as the input frame rate.
2. The number of bins at present has to be hardcoded since Cg doesn't allow variables in the for loop conditions.
3. In order to use larger number of bins, I have to use an advanced fragment profile like fp40. The others do not support this.

Also, I will have to take some time out to make the UI for this. I am thinking of using Qt for this purpose, although I haven't really used it ever. But if I don't try, I won't know!!

Until next time then!

Lots of updates!

All right! So there have been lots of updates since my last post.. and the following paragraphs will take you through those in brief...

First up I succeeded in porting the RGB to CIELab space and reverse conversion onto the GPU. That speeded up things quite a bit.

Next up was to develop the extended Bilateral Filter, which is essentially an edge preserving smoothening operator. The colors in the output image would be smoothed out but the edges would still be preserved, unlike , say, Gaussian blurring. The authors have given their formula for a simplified Bilateral Filter, and I started on implementing it in a fragment program. The special thing about a bilateral filter is that it acts on the geometric as well as photometric domain of an image thus giving a perceptually well defined smoothening of the image. They have given typical values of the 2 main variables affecting the output, the geometric deviation and the photometric deviation.



I discovered that I had to tweak certain parameters in order to get a nice output, and in the process of this tweaking, I did come across a nice little finding, which I will talk about, after the next section on edge detection.

So once the bilateral filter was working, the next step was to give the output of the previous step to the edge detection fragment program in order to get an image with the edges detected. Initially, I just wrote this as a single pass application with the bilateral filter code commented to test the edge detection. The authors have used a Difference-of-Gaussians edge detection approach, which takes the difference in perception when two different Gaussian filters are applied to the same image with 2 different deviations.

I didn't quite get this approach working, so I had to resort to the simpler and well documented Sobel filter approach. This method does have a drawback of introducing a significant amount of noise in the output image.

It was after this that I started on the multipass approach, in which the first pass consists of applying the Bilateral Filter to the image and writing the output to a texture, which would then be passed to the edge detection fragment program. After this the output of the edge detection would then be blended with the previous filter output to create the final output image. For this I used the glBlendFunc method of OpenGL. It has plenty of options, and I had to experiment with a few options before I got the right combination.



But because of the noise in the edge detected output, the final output image also had the noise, and the result wasn't impressive. So, I started experimenting with different approaches and in the process of this experimenting, I discovered that the Bilateral filter could also act as an edge detector!! There was a certain parameter, which when set to the right value resulted in a smoothed image with the edges detected! So what I got was 2 processes within the same process!


So now there doesn't seem to be any need for the edge detection fragment program, though there is still one important step remaining, that of quantizing the image. Hence I will have to check the output of that step in both cases, using the edge detection program and without it.

The next step in this process is the quantization of the image. There are a number of color quantization approaches documented, and I will have to see which of them suits real time implementation.