Finding the colour that matches one from a given palette

Question

I have a palette of colours, that's either 32 or 256. Then I have a stream of incoming colours (in RGB). I want to find out which colour in the palette the incoming colour matches most closely with. I believe this sort of algorithm is used in many image editing software.

So far, I came up with the following:

1. For each incoming colour, find the colour in the palette with the least distance, by finding out the distance from each colour in the palette.
2. For finding the distance, one of the following approaches:
   1. Sum of squares of differences of R, G and B values ((R1-R2)² + (G1-G2)² + (B1-B2)²)
   2. Convert the colour to HSV, use a weighted average of H, S and V values as the distance indicator. Something like 3 ✕ (H1-H2)² + 2 ✕ (S1-S2)² + (V1-V2)²
   3. Distance in YCbCr

I am looking for two things in particular.

1. Is there a better way than to check the distance with each colour in the palette? I'm looking for some sort of binning algorithm to find the right colour from the palette.
2. If sticking with checking the distance with each item in the palette, are there andy standard formulae which are considered standard?

Answer 1

As often, the answer depends on why exactly you want to do that.

If the goal is to minimize the numerical approximation error, the sums of squared difference (or the maximum of the absolute differences) can do.

I would abstain from and arbitrary formula such a a weighted sum of differences in some colorimetric space, which have no precise justification and are hard to interpret.

If you want to keep the image as similar as possible to the original for a human eye, you can use a "perceptually uniform" metric, such as CIELAB ΔE*. Anyway, in my personal opinion, such metrics are overly sophisticated and bring little benefit. You will only see differences for colors that are distant from the colors in your palette, if at all.