Best algorithm for matching colours.

Question

I have an array of around 200 colours in RGB format. I want to write a program that takes any RGB colour and tries to match a colour from the array that is most "similar".

I need a good definition for "similar", which is as close as possible to human perception.

I also want to show some information about matching accuracy. For example black-white: 100% and for a similar colour with a slightly different hue: -4%.

Do I need to use neural networks? Is there an easier alternative?

Answer 1

Here is the complete code Python for finding the name of a colour given an arbitrary value in RGB.

import matplotlib.colors as mc
import numpy as np
from scipy.spatial import KDTree
import cv2


class ColorNamer:
    def __init__(self):
        self.clut = {}
        self.clut_list = []
        self.clut_tree = None

        for name in mc.XKCD_COLORS:
            rgb = mc.to_rgb(mc.XKCD_COLORS[name])
            lab = cv2.cvtColor(np.single([[rgb]]), cv2.COLOR_RGB2Lab)[0][0]
            self.clut[tuple(lab)] = name[5:]
        self.clut_list = list(self.clut.keys())
        self.clut_tree = KDTree(self.clut_list)


    def name(self, rgb):
        lab = tuple(cv2.cvtColor(np.single([[rgb]]), cv2.COLOR_RGB2Lab)[0][0])
        dist, point = self.clut_tree.query(lab, 1)
        idx = int(point)
        key = self.clut_list[idx]
        return self.clut[key]

if __name__ == '__main__':
    cn = ColorNamer()
    print(cn.name((.3211, .543, .633)))

Answer 2

I faced the same problem recently, and compared various algorithms I found online. At first I was hesitant to use CIELAB color space due to its complexity, but it's really not as bad as it looks at first. Here's all the code you'll need to compare two RGB values.

struct CIELAB {
    float L, a, b;
};

float gammaCorrect( float v )
{
    return 100.0f * (v <= 0.04045f ? v / 12.92f : powf( (v + 0.055f) / 1.055f, 2.4f ));
}

float nonlinearToLinear( float v )
{
    return v > 0.008856f ? cbrtf( v ) : 7.787f * v + 16.0f / 116.0f;
}

CIELAB RGBToCIELAB( int R, int G, int B )
{
    float red = gammaCorrect( R / 255.0f );
    float green = gammaCorrect( G / 255.0f );
    float blue = gammaCorrect( B / 255.0f );

    float xr = nonlinearToLinear( (red * 0.4124564f + green * 0.3575761f + blue * 0.1804375f) / 95.047f );
    float yr = nonlinearToLinear( (red * 0.2126729f + green * 0.7151522f + blue * 0.0721750f) / 100.000f );
    float zr = nonlinearToLinear( (red * 0.0193339f + green * 0.1191920f + blue * 0.9503041f) / 108.883f );

    return { 116.0f * yr - 16.0f, 500.0f * (xr - yr), 200.0f * (yr - zr) };
}

float similarity( int R0, int G0, int B0, int R1, int G1, int B1 )
{
    CIELAB lab0 = RGBToCIELAB( R0, G0, B0 );
    CIELAB lab1 = RGBToCIELAB( R1, G1, B1 );
    float dL = lab0.L - lab1.L;
    float da = lab0.a - lab1.a;
    float db = lab0.b - lab1.b;
    return dL*dL + da*da + db*db;
}

For the similarity() function, the lower the result the better the match. For improved efficiency, pre-convert your RGB color list into CIELAB space.

If a simpler algorithm is desired, Wikipedia's Color difference page has an algorithm that works pretty well. You can implement it using integer arithmetic, and if only comparing similarities you can skip the square-root computation.

int similarity( int R0, int G0, int B0, int R1, int G1, int B1 )
{
    int dr = R0 - R1;
    int dg = G0 - G1;
    int db = B0 - B1;
    int redsum = R0 + R1;
    return (1024 + redsum) * dr*dr + 2048 * dg*dg + (1534 - redsum) * db*db;
}

The computation will not exceed 32-bit signed integers.

I found this matching to be noticeably inferior to matching in CIELAB space, but the computation is trivial.

I also tried matching in HSV color space but did not get good results for some color pairs. For example, pure white and pure black (which are as different as can be) can have the same hue and saturation, so might match better than you'd like.

Answer 3

The fastest way I've achieved this is to add the colors to an octree and then, just as with quantization, you use each bit to guide you to the deepest child node. Once you can go no deeper, either you're at the deepest level (the lowest bit), in which case you've hit the exact color, or the next child node you need doesn't exist--at which point you just need the child with the bit that's closest to the bit you're searching for and that's your closest color. It's a heck of a lot faster than converting everything to HSL and back, or calculating every single Euclidean distance.

Here's my code on CodeProject: https://www.codeproject.com/tips/1046574/octtree-based-nearest-color-search

Answer 4

I was looking for the thing but having not found a lot answers around I decided to create this little library.

https://github.com/sebastienjouhans/c-sharp-colour-utilities

Answer 5

No, you do not need neural networks here! Simply consider an HSL color value a vector and define a weighted modulus function for the vector like this:

modulus = sqrt(a*H1*H1 + b*S1*S1 + c*L1*L1);

where a,b,c are weights you should decide based on your visual definition of what
creates a bigger difference in perceived color - a 1% change in Hue or a 1%
change in Saturation

I would suggest you use a = b = 0.5 and c = 1

Finally, find out the range your modulus would take and define similar colors to be those which have their moduli very close to each other (say 5%)

Answer 6

I'd also point out the least squares method, just as something slightly simpler. That is, you take the difference of a number, square it, then sum all these squared differences.

Answer 7

Convert all of the colors to the CIE Lab color space and compute the distance in that space

deltaE = sqrt(deltaL^2 + deltaA^2 + deltaB^2)

Colors with the lowest deltaE are the most perceptually similar to each other.