Given an RGB value what would be the best way to find the closest match in the database?

Question

I have a rgb value and if it doesn't exist in the color table in my database I need to find the closest color. I was thinking of comparing all values and finding the difference(in red,green,and blue) then take the average. The lowest average deviation should be the closest color. There seems to me like there should be a better way. Any ideas?

Answer 1

Calculate both the average and the distance like this:

(r + g + b) / 3 = average
(r - average) + (g - average) + (b - average) = distance

This should give you a good idea of the closest value.

Answer 2

The following does exactly what you describe:

select (abs(my_R - t.r) + abs(my_G - t.g) + abs(my_B - t.b)) / 3 as difference, t.*
from RGBtable t
order by difference desc;

However, you might get better results with something that was non-linear. In the "take the averages" approach, if you goal color is (25, 25, 25) the color (45, 25, 25) would be closer than (35, 35, 35). However, I bet the second would actually look closer, since it would also be gray.

A few ideas come to mind: you could try squaring the differences before you average them. Or you could do something complicated with finding the color with the closest ratio between the different values. Finding the closest ratios would get you closest to the right hue, but won't account for saturation (if I'm remembering the terms right...)

Answer 3

Consider a color as a vector in 3-dimensional space, you can then easily compute the difference by using 3d pythagoras:

d = sqrt((r2-r1)^2 + (g2-g1)^2 + (b2-b1)^2)

However, note that due to colors being subject to interpretation by not-so-perfect eyes, you might want to adjust the colors to avoid them having the same importance.

For instance, using a typical weighted approach:

d = sqrt(((r2-r1)*0.3)^2 + ((g2-g1)*0.59)^2 + ((b2-b1)*0.11)^2)

Since eyes are most sensitive to green, and least sensitive to blue, two colors that differ only in the blue component must thus have a larger numeric difference to be considered "more different" than one that is the same numeric difference in the green component.

There's also various ways to optimize this calculation. For instance, since you're not really interested in the actual d value, you can dispense with the square root:

d =   ((r2-r1)*0.30)^2
    + ((g2-g1)*0.59)^2
    + ((b2-b1)*0.11)^2

Note here that in many C-syntax-based programming languages (like C#), ^ does not mean "raise to the power of", but rather "binary exclusive or".

So if this was C#, you would use Math.Pow to calculate that part, or just expand and do the multiplication.

Added: Judging by the page on Color difference on Wikipedia, there's various standards that try to handle perceptual differences. For instance, the one called CIE94 uses a different formula, in the L*C*h color space that looks like it's worth looking into, but it depends on how accurate you want it to be.

Answer 4

From looking at the Wikipedia page on Color difference, the idea is to treat RGB colours as points in three dimensions. The difference between two colours is the same as the distance between two points:

difference = sqrt((red1 - red2)^2 + (green1 - green2)^2 + (blue1 - blue2)^2)

Answer 5

Let the database do it for you:

select top 1
  c.r,
  c.b,
  c.g
from
  color c
order by
  (square(c.r - @r) + square(c.g - @g) + square(c.b - @b))

Where @r, @g, and @b are the r,g,b values of the color that you're searching for (SQL Server parameter syntax, since you didn't specify a database). Note that this is still going to have to do a table scan since the order by has a function call in it.

Note that the extra square root call isn't actually required since it's a monotonic function. Not that it would probably matter very much, but still.

Answer 6

One step better than average is nearest square root:

((delta red)^2 + (delta green)^2 + (delta blue)^2)^0.5

This minimizes the distance in 3D color space.

Since a root is strictly increasing, you can search for the maximum of the square instead. How you express this in SQL would depend on which RDBMS you're using.

Answer 7

The Euclidean distance difference = sqrt(sqr(red1 - red2) + sqr(green1 - green2) + sqr(blue1 - blue2)) is the standard way to determine the similarity of two colours.

However, if you have your colours in a simple list, then to find the nearest colour requires computing the distance from the new colour with every colour in the list. This is an O(n) operation.

The sqrt() is an expensive operation, and if you're just comparing two distances then you can simply omit the sqrt().

If you have a very large palette of colours, it is potentially quicker to organise the colours into a kd tree (or one of the alternatives) so as to reduce the number of diffreences that require computing.