0

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?
Raze
  • 2,175
  • 14
  • 30
  • see https://en.wikipedia.org/wiki/Color_difference Note: all methods fails for very different colours, but let's hope that with 256 (maybe also 32) colours you will not get much different colours. Do you mean Hue or colour? – Giacomo Catenazzi Aug 04 '20 at 12:25
  • 1
    You might want to google `octree color quantization algorithm`. I've used it in the past with success, but that was so long ago I hardly remember anything about it (hence not posted as an answer). – 500 - Internal Server Error Aug 04 '20 at 12:26
  • @500-InternalServerError It seems to me that octree quantization algorithm is about generating the palette. In my case, I already have the palette. I'm trying to figure out the best way to fit incoming colour to a match in the palette. – Raze Aug 04 '20 at 13:23

1 Answers1

0

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.

  • Thanks. A little approximation error is fine. But I understand that the way human eye perceives color, there could be huge differences in approximation of certain colours, where a very bright yellow might be perceived as yellow by us, but the choice of algorithm might choose white instead. At this point I'm just evaluating my options. More importantly, I want to know how to select a palette colour for an incoming colour efficiently. I'm looking for some sort of binning algorithm. – Raze Aug 04 '20 at 17:06
  • 1
    @Raze: kD-tree. You were not asking that in your post. –  Aug 04 '20 at 17:07
  • thanks. I have edited the first question to be more clear. – Raze Aug 05 '20 at 08:22