Sorting a list of colors in one dimension?

Question

I would like to sort a one-dimensional list of colors so that colors that a typical human would perceive as "like" each other are near each other.

Obviously this is a difficult or perhaps impossible problem to get "perfectly", since colors are typically described with three dimensions, but that doesn't mean that there aren't some sorting methods that look obviously more natural than others.

For example, sorting by RGB doesn't work very well, as it will sort in the following order, for example:

(1) R=254 G=0 B=0 (2) R=254 G=255 B=0 (3) R=255 G=0 B=0 (4) R=255 G=255 B=0

That is, it will alternate those colors red, yellow, red, yellow, with the two "reds" being essentially imperceivably different than each other, and the two yellows also being imperceivably different from each other.

But sorting by HLS works much better, generally speaking, and I think HSL even better than that; with either, the reds will be next to each other, and the yellows will be next to each other.

But HLS/HSL has some problems, too; things that people would perceive as "black" could be split far apart from each other, as could things that people would perceive as "white".

Again, I understand that I pretty much have to accept that there will be some splits like this; I'm just wondering if anyone has found a better way than HLS/HSL. And I'm aware that "better" is somewhat arbitrary; I mean "more natural to a typical human".

For example, a vague thought I've had, but have not yet tried, is perhaps "L is the most important thing if it is very high or very low", but otherwise it is the least important. Has anyone tried this? Has it worked well? What specifically did you decide "very low" and "very high" meant? And so on. Or has anyone found anything else that would improve upon HSL?

I should also note that I am aware that I can define a space-filling curve through the cube of colors, and order them one-dimensionally as they would be encountered while travelling along that curve. That would eliminate perceived discontinuities. However, it's not really what I want; I want decent overall large-scale groupings more than I want perfect small-scale groupings.

Thanks in advance for any help.

Answer 1

If you want to sort a list of colors in one dimension you first have to decide by what metrics you are going to sort them. The most sense to me is the perceived brightness (related question).

I have came across 4 algorithms to sort colors by brightness and compared them. Here is the result.

I generated colors in cycle where only about every 400th color was used. Each color is represented by 2x2 pixels, colors are sorted from darkest to lightest (left to right, top to bottom).

1st picture - Luminance (relative)

0.2126 * R + 0.7152 * G + 0.0722 * B

2nd picture - http://www.w3.org/TR/AERT#color-contrast

0.299 * R + 0.587 * G + 0.114 * B

3rd picture - HSP Color Model

sqrt(0.299 * R^2 + 0.587 * G^2 + 0.114 * B^2)

4td picture - WCAG 2.0 SC 1.4.3 relative luminance and contrast ratio formula

Pattern can be sometimes spotted on 1st and 2nd picture depending on the number of colors in one row. I never spotted any pattern on picture from 3rd or 4th algorithm.

If i had to choose i would go with algorithm number 3 since its much easier to implement and its about 33% faster than the 4th

Answer 2

You cannot do this without reducing the 3 color dimensions to a single measurement. There are many (infinite) ways of reducing this information, but it is not mathematically possible to do this in a way that ensures that two data points near each other on the reduced continuum will also be near each other in all three of their component color values. As a result, any formula of this type will potentially end up grouping dissimilar colors.

As you mentioned in your question, one way to sort of do this would be to fit a complex curve through the three-dimensional color space occupied by the data points you're trying to sort, and then reduce each data point to its nearest location on the curve and then to that point's distance along the curve. This would work, but in each case it would be a solution custom-tailored to a particular set of data points (rather than a generally applicable solution). It would also be relatively expensive (maybe), and simply wouldn't work on a data set that was not nicely distributed in a curved-line sort of way.

A simpler alternative (that would not work perfectly) would be to choose two "endpoint" colors, preferably on opposite sides of the color wheel. So, for example, you could choose Red as one endpoint color and Blue as the other. You would then convert each color data point to a value on a scale from 0 to 1, where a color that is highly Reddish would get a score near 0 and a color that is highly Bluish would get a score near 1. A score of .5 would indicate a color that either has no Red or Blue in it (a.k.a. Green) or else has equal amounts of Red and Blue (a.k.a. Purple). This approach isn't perfect, but it's the best you can do with this problem.

Answer 3

There are several standard techniques for reducing multiple dimensions to a single dimension with some notion of "proximity".

I think you should in particular check out the z-order transform.

You can implement a quick version of this by interleaving the bits of your three colour components, and sorting the colours based on this transformed value.

The following Java code should help you get started:

    public static int zValue(int r, int g, int b) {
            return split(r) + (split(g)<<1) + (split(b)<<2);
    }

    public static int split(int a) {
            // split out the lowest 10 bits to lowest 30 bits
            a=(a|(a<<12))&00014000377;
            a=(a|(a<<8)) &00014170017;
            a=(a|(a<<4)) &00303030303;
            a=(a|(a<<2)) &01111111111;
            return a;
    }