So I have a small (8x8 pixel) image in 24-bit color. I want to be able to (quickly) generate a color-quantized version of the image that only has two colors.

One naive approach is to cluster a luma histogram of the image (1-dimensional clustering is easier than the 2D or 3D case). The chroma can be generated by averaging the pixels in each cluster. Unfortunately, this technique doesn't really work well if the the image has uniform luma.

Any ideas?


The approach I would use, and indeed have used, would be to

  1. run principal component analysis on your image data to generate "the" main axis
  2. Project your pixels onto that axis (i.e. compute the dot product of each colour value against the axis)
  3. Using the dot prods, sort the the colour values from smallest to largest and
  4. Find the "partitioning" point, i.e. that splits smaller values in one set, larger in the other, that minimises, say, the mean squared error. i.e. each partition is represented by the average of its members and you compute the total error.

This last step, i.e. finding the best partition, can be done in linear time by starting with the "least" item in partition "A", all the rest in partition "B", and progressively shifting the next smaller over from "B" to "A, one at a time. You just need to keep separate sums of the values and sums of squares of the values for each partition and then you can compute the total MSE relatively cheaply.

Note that the function should follow a quadratic curve so it (should) begin decreasing until it reaches the minimum. Once it starts increasing again you can stop the search.

A cheap way to find the principal axis is to first generate the 3x3 covariance matrix and then use the "repeated matrix vector multiplication" trick to find the principal eigenvector (i.e. the principal axis)

  • 1
    $\begingroup$ Hmm this seems promising; I'll try it out and see how it goes $\endgroup$ – AnimatedRNG Apr 5 '18 at 20:30
  • $\begingroup$ Alternatively, if you are after something that is quick to code (but not likely to be quite as good) another possible approach would be (a) find the average, (b) find the colour furthest from the average -call it X, (c) find the colour furthest from X, call it Y, then (d) run several iterations of k-means (en.wikipedia.org/wiki/K-means_clustering#Standard_algorithm) starting with X and Y as the initial reps. It might do the trick. $\endgroup$ – Simon F Apr 6 '18 at 8:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.