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

There are two approaches you could take. The simple approach is to distil each colour into a single value, and the list of values can then be sorted. The complex approach would depend on all of the colours you have to sort; perhaps it would be an iterative solution that repeatedly shuffles the colours around trying to minimise the "energy" of the entire sequence.

My guess is that you want something simple and fast that looks "nice enough" (rather than trying to figure out the "optimum" aesthetic colour sort), so the simple approach is enough for you.

I'd say HSL is the way to go. Something like

sortValue = L * 5 + S * 2 + H

assuming that H, S and L are each in the range [0, 1].

Answer 2

Here's an idea I came up with after a couple of minutes' thought. It might be crap, or it might not even work at all, but I'll spit it out anyway.

Define a distance function on the space of colours, d(x, y) (where the inputs x and y are colours and the output is perhaps a floating-point number). The distance function you choose may not be terribly important. It might be the sum of the squares of the differences in R, G and B components, say, or it might be a polynomial in the differences in H, L and S components (with the components differently weighted according to how important you feel they are).

Then you calculate the "distance" of each colour in your list from each other, which effectively gives you a graph. Next you calculate the minimum spanning tree of your graph. Then you identify the longest path (with no backtracking) that exists in your MST. The endpoints of this path will be the endpoints of the final list. Next you try to "flatten" the tree into a line by bringing points in the "branches" off your path into the path itself.

Hmm. This might not work all that well if your MST ends up in the shape of a near-loop in colour space. But maybe any approach would have that problem.

Answer 3

 A. R=254 G=0 B=0
 B. R=254 G=255 B=0
 C. R=255 G=0 B=0
 D. R=255 G=255 B=0

You need to look at the difference between the neighbouring colours.

The diff between A and B is 0 + 255 + 0 = 255. The diff between A and C is 1 + 0 + 0 = 1.

The diff between A and B is greater than A and C so A is closer to C so swap B and C.

 A. R=254 G=0 B=0 
 C. R=255 G=0 B=0
 B. R=254 G=255 B=0
 D. R=255 G=255 B=0

The diff between C and B is 1 + 255 + 0 = 256. The diff between C and D is 0 + 255 + 0 = 255.

The diff between C and B is greater than C and D so C is closer to D so swap B and D.

A. R=254 G=0 B=0 
C. R=255 G=0 B=0
D. R=255 G=255 B=0
B. R=254 G=255 B=0

Treat it like a bubble sort. This is not a perfect algorythm by any stretch and there are probably better ways to approach this but this might be a kick in the right direction.

Also...

You'd need some funky way of comparing across your subject.

Answer 4

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 5

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;
    }