29
$\begingroup$

I can't seem to be able to sort colors by their hue and perceptual brightness correctly. Here's my current solution, but it's not right; there are all these dark bands:

c = RandomColor[RGBColor[_, _, _], 500];
o1 = SortBy[c, ColorConvert[#, "HSB"][[1]] &];
o2 = SortBy[c, ColorConvert[#, "LAB"][[2]] &];
Image[#, ImageSize -> 400] & /@ {Table[o1, {100}], Table[o2, {100}]}

my attempt to sort colors

I want to find a way to achieve color sorting that minimizes these bands and smooths the transition along the gradient, something similar to the clustering histograms Theo Gray used in the Disney app.

clustering histograms

$\endgroup$
  • $\begingroup$ Both your solutions are right. The dark and light bands are to be expected. The first sorts by hue, regardless of brightness, and it does exactly that; the brightness is not taken into account in the sort. The same happens for your a* sort. $\endgroup$ – DumpsterDoofus Jul 5 '15 at 21:29
  • 1
    $\begingroup$ I guess what I'm asking for is a clustering that minimizes those discontinuities. $\endgroup$ – M.R. Jul 5 '15 at 21:35
  • $\begingroup$ Interesting. That reduces it to a traveling salesman problem, where the distance metric is CIELAB, rather than Euclidean. I'll see what I can do. $\endgroup$ – DumpsterDoofus Jul 5 '15 at 21:40
  • 11
    $\begingroup$ Unfortunately this idea runs into a basic problem: You can’t sort colors. Because the human eye has three distinct color sensors (red, green, and blue), color is fundamentally a three-dimensional quantity, and there is no linear ordering that brings together “similar” colors. If you sort first by amount of red, for example, then you may bring together wildly different hues and brightnesses. If you sort by hue, then you bring together wildly different degrees of saturation and brightness, and so on. There’s just no way to do it. -- the article you cite $\endgroup$ – Mr.Wizard Jul 5 '15 at 21:54
  • 2
    $\begingroup$ The article also describes how Mr. Gray created the histograms you like, so you could try doing that. $\endgroup$ – Rahul Jul 6 '15 at 3:27
34
$\begingroup$

If you're looking for a way to sort the colors in such a way as to make them seem the least discontinuous, then one way to think of it is that each color is a point in a space endowed with a distance metric (either the CIELAB 1976 or the CIELAB2000 perceptual metrics), and you are trying to find a shortest tour that visits each point. We can do that with ColorDistance and FindShortestTour:

c = RandomColor[500];
ord2000 = 
  FindShortestTour[c, 
    DistanceFunction -> (ColorDistance[#1, #2, 
        DistanceFunction -> "CIE2000"] &)][[2]];
ord76 = FindShortestTour[c, DistanceFunction -> ColorDistance][[2]];
Image[Table[c[[ord2000]], {100}]]
Image[Table[c[[ord76]], {100}]]

Giving the following two results:

enter image description here enter image description here

To my eye, it looks like the CIE2000 metric does a slightly better job than the older 1976 variant.

As Mr. Wizard points out, "sorting" colors is sort of like "sorting" random points in a space with more than one dimension: there's no general way to do it that makes sense, since you're trying to impose a linear order on something which has more than one dimension. So the best you can do is find a shortest tour.

$\endgroup$
15
$\begingroup$

Just for fun, how does a 3D Hilbert curve sample the 3D colourspace of RGB? and can it be used to sort colours?

HilbertCurve3D[n] generates a 3D Hilbert curve of order n. The code is by Michael Trott from page 93 of The Mathematica Guidebook for Programming.

HilbertCurve3D[n_Integer?Positive] :=
   Module[{axiom = "X", recursion = "X" -> {"t", "c", "X", "F", "t", "c", "X", "F",
           "X", "q", "F", "t", "d", "d", "X", "F", "X", "w", "F", "p", "d",
           "d", "X", "F", "X", "q", "F", "d", "X", "q", "d"},
           r = {0, 0, 0}, m = IdentityMatrix[3]},
          Prepend[ DeleteCases[ Which[ (*the movements*)
             # == "F", r = r + (First /@ m),
             # == "B", r = r - (First /@ m);,
             # == "w", m = m.{{0, 0, 1}, {0, 1, 0}, {-1, 0, 0}};,
             # == "t", m = m.{{0, 0, -1}, {0, 1, 0}, {1, 0, 0}};,
             # == "p", m = m.{{0, -1, 0}, {1, 0, 0}, {0, 0, 1}};,
             # == "q", m = m.{{0, 1, 0}, {-1, 0, 0}, {0, 0, 1}};,
             # == "c", m = m.{{1, 0, 0}, {0, 0, 1}, {0, -1, 0}};,
             # == "d", m = m.{{1, 0, 0}, {0, 0, -1}, {0, 1, 0}};,
             True, Null] & /@ Flatten[Nest[# /. recursion &,
                                 Characters[axiom], n]], Null], {0, 0, 0}]]

HilberCurve3D[n] returns all points with integer coordinates within a cube spanning $\{0,0,0\}$ to $(2^n-1)*\{1,1,1\}$. Normalize by dividing by $2^n-1$ so that all coordinates range between 0 and 1. The number of samples in HilbertCurve3D[n] is $2^{3n}$.

The following code finds points on the Hilbert curve nearest the random colours, and sorts the colours based on the point position along the curve.

Block[{randomColours, rgbList, n = 3, hcurve, nearestFunction, 
       nearestHilbertIndex, sortedColours},

       (* make random colours *)
       randomColours = RandomColor[RGBColor[_, _, _], 500];

       (* create triples of rgb values, ranging 0 to 1 *)
       rgbList = Apply[List, randomColours, 1];

       (* normalized 3D Hilbert curve ranging 0 to 1 *)
       hcurve = HilbertCurve3D[n]/(2^n-1.);

       (* form nearest function for Hilbert curve *)
       nearestFunction = Nearest[hcurve -> Automatic];

       (* find index of Hilbert point nearest each random colour *)
       nearestHilbertIndex = Flatten[nearestFunction[rgbList], 1];

       (* sort random colours *)
       sortedColours = SortBy[
          Transpose[{randomColours, nearestHilbertIndex}], Last][[All, 1]];

       (* display random and sorted colours *)
       {Image[Table[randomColours, {100}], ImageSize -> 400], 
        Image[Table[sortedColours, {100}], ImageSize -> 400]} // Column
]

random colours

sorted colours

$\endgroup$
  • 4
    $\begingroup$ Since you're going down this route: you could also try sorting the colors in Morton order. $\endgroup$ – J. M. is away Jul 6 '15 at 21:15
  • 3
    $\begingroup$ BTW, you could use Ordering[] to rearrange the colors instead of going through the trouble of making an array for SortBy[]: randomColours[[Ordering[nearestHilbertIndex]]]. $\endgroup$ – J. M. is away Jul 7 '15 at 11:45
  • 1
    $\begingroup$ @J.M. Palm to forehead. Thank you for your consistently valuable comments on many of the questions here. $\endgroup$ – KennyColnago Jul 7 '15 at 18:04
11
$\begingroup$

I've decided to follow through on my suggestion in a comment to Kenny's answer to use Morton ordering (a.k.a. Z-ordering) of the colors in RGB space.

Here's a short routine to generate the n-th iterate of a d-dimensional Z-curve:

Morton[d_Integer, n_Integer] :=
   Array[FromDigits[BitGet[#1, d Range[n - 1, 0, -1] + #2], 2] &,
         {2^(n d), d}, {0, 0}]/(2^n - 1)

Let's generate a few random colors:

(* for reproducibility *)
cols = BlockRandom[SeedRandom[42, Method -> "Legacy"]; RandomReal[1, {500, 3}]];
Graphics[Raster[{cols}, {{0, 0}, {1, 1/8}}]]

random colors

Now, we proceed in a manner similar to Kenny's take, but using Morton ordering:

nf3 = Nearest[Morton[3, 3] -> Automatic];
idx = Flatten[nf3 /@ cols];
Graphics[Raster[{cols[[Ordering[idx]]]}, {{0, 0}, {1, 1/8}}]]

Morton-sorted colors

Nice banding, it looks. Whether this will suit OP's needs is an entirely different question...

$\endgroup$
  • 1
    $\begingroup$ Other possibilities, apart from the use of a different space-filling curve, would be to consider the Morton or Hilbert ordering in a different colorspace, like XYZ. $\endgroup$ – J. M. is away Jul 12 '15 at 13:09
7
$\begingroup$

I will use FeatureSpacePlot to do this.Plot their in feature space

colors = RandomColor[100];

This is original order

fea = FeatureSpacePlot[colors]

Sort it by DimensionReduce

Row[Keys[Sort[<|
    Thread[Cases[fea, _RGBColor, Infinity] -> 
      Flatten[DimensionReduce[
        Cases[fea, Text[___, x_List, _] :> x, Infinity], 1]]]|>]]]

$\endgroup$
  • $\begingroup$ Might be better to use DimensionReduce[] directly, since that's what FeatureSpacePlot[] uses internally: ord = Flatten[DimensionReduce[colors, 1, Method -> "TSNE", PerformanceGoal -> "Quality"]]; Row[colors[[Ordering[ord]]]] $\endgroup$ – J. M. is away Sep 5 '17 at 0:45
  • $\begingroup$ @J.M. Thanks.That's better than me. $\endgroup$ – yode Sep 5 '17 at 1:54
  • 1
    $\begingroup$ @yode J. M.'s shortcut doesn't preserve the color orderings! $\endgroup$ – user5601 Mar 6 '18 at 20:58
  • $\begingroup$ This thread is top of DuckDuckGo search for "color sort". Mathematics is a good way to evenly sort colors. nCol is a new color format at W3Schools.com. Sine calculations dominating this thread skew all primaries (i've tried dozens of dozens of models), that skew is toxic. So dump it! Yode citation '1]]]' indicates need for tangent analysis. Thanks yode! Using the nCol color block, namely RYGCBM. nCol ⱭN, w%, b%, e.g., C0,0%,0%, so where sum = w% + b%, then Ɑ[100((1+∑)/((1+∑)cos) + Ntan)] If it is not asking too much, please test nCOL sc $\endgroup$ – mark stewart Feb 23 at 22:23

protected by Community Feb 23 at 22:59

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.