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!