With 24 bit color you can create an array with an element for each of the 16 million colors and just build the histogram. Running k-means on that is going to be less efficient than just making the histogram buckets larger, e.g. 2x2x2 = 8 colors per bucket, or whatever. So yeh you should be able to do that in a few milliseconds I would have thought. For more speed look at using SIMD instructions.
I too have been playing with color quantization as an exercise so I won't like at your library as I've been trying to do it all on my own and don't want to see other approaches yet, but here he is not quantizing them so his is going to be faster. Also there really is a trade off in trying to reduce the number of pixels and then clustering versus just clustering on them all. How many times you loop and how much those loops costs isn't as cut and dry as I thought.
Here is a shameless plug for one of my color extracting library: https://github.com/jathu/UIImageColors/
It currently takes around ~0.3s on average to extract the colors. However, with my new PR (https://github.com/jathu/UIImageColors/pull/54), it takes around ~0.14s on average. IMO this is still slow, I would like to bring it below 0.1s.
I tried to optimize this with k-means to reduce total number of colors, but the result was slower and worse color choices. If anyone has methods to improve the performance, please make a PR.