<p>The approach I would use, and indeed have used, would be to</p>

<ol>
<li>run principal component analysis on your image data to generate "the" main axis</li>
<li>Project your pixels onto that axis (i.e. compute the dot product of each colour value against the axis)</li>
<li>Using the dot prods, sort the the colour values from smallest to largest and</li>
<li>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.</li>
</ol>

<p>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. </p>

<p>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.</p>

<p>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)</p>

CC BY-SA 3.0
2018-04-05T20:30:18.053Z
Hmm this seems promising; I'll try it out and see how it goes
AnimatedRNG
CC BY-SA 3.0
2018-04-06T08:46:26.440Z
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 (https://en.wikipedia.org/wiki/K-means_clustering#Standard_algorithm) starting with X and Y as the initial reps.  It might do the trick.
Simon F
CC BY-SA 3.0
2018-04-05T08:36:43.173Z
2018-04-06T08:35:13.163Z
2018-04-06T08:35:13.163Z
Simon F
<p>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. </p>

<p>One naive approach is to cluster a luma histogram of the image (1-dimensional clustering is <a href="https://stackoverflow.com/a/11516590/498680">easier</a> 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.</p>

<p>Any ideas?</p>

<algorithm><image-processing><color>
Quick 2-color quantization for small images
AnimatedRNG
# Quick 2-color quantization for small images

(Asked by: username_0 on 2018-04-04)

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](https://stackoverflow.com/a/11516590/498680) 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?

**Tags:** algorithm, image-processing, color


---

## 1 answers

### Answer by username_1 on 2018-04-05. Score: 1 | Accepted answer

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)

> **Comments:**
> **username_0**: Hmm this seems promising; I'll try it out and see how it goes  
> **username_1**: 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 (https://en.wikipedia.org/wiki/K-means_clustering#Standard_algorithm) starting with X and Y as the initial reps.  It might do the trick.  

---

