What is the fastest available color quantization algorithm for Android?

Question

I'm using the NeuQuant quantization algorithm (https://code.google.com/p/android-gif-project/source/browse/trunk/GIFproject1/src/com/ui/NeuQuant.java?r=5) to reduce a jpeg to a 256-color image but it's very slow (~1 second for a 320x240 image, ~3 seconds for a 640x480). Even with multiple threads I can't get processing time to a decent level (ideally in the 100ms per image range).

Does anyone know a faster algorithm to reduce the color palette of an image to 256 colors?

Answer 1

Extracting 256 colors is somewhat of an edge case, but you should have a look at Median Cut Quantization. Here is an implementation : github link
Another option is octree.
You should really bench both solutions though and look for ways to improve them.

Additionally, running the algorithm through a RenderScript might allow you to speed it up a lot.