Color Sorting In PHP

9th June 2018

Sorting colors is the sort of thing that you never really think about until you need to do it. Sorting a bunch of items by their color is useful in a number of applications, but the simplest is just to display items to the user in a more controlled manner. As it happens sorting with colors is a much more complex topic than I originally thought and required digging into quite a bit more maths than I expected.

Incidentally, there is a whole world of color maths that I didn't know existed until I started looking into this. It was worth learning about though.

Setting Up

To start with, I created a little Color class so that I could have a standard way of storing a color. This just takes the red, green and blue values for a color and allows a simple way of accessing those values.

  1. class Color {
  2. public $red = 0;
  3. public $green = 0;
  4. public $blue = 0;
  5.  
  6. public function __construct($red, $green, $blue)
  7. {
  8. $this->red = $red;
  9. $this->green = $green;
  10. $this->blue = $blue;
  11. }
  12. }

Next, I created an array and filled it with a number of Color objects. This is the basis of the sorting that I will do for the rest of this post.

  1. $colors = [];
  2.  
  3. for ($i = 0; $i < 750; $i++) {
  4. $red = ceil(mt_rand(0, 255));
  5. $green = ceil(mt_rand(0, 255));
  6. $blue = ceil(mt_rand(0, 255));
  7.  
  8. $colors[] = new Color($red, $blue, $green);
  9. }

Before we get into sorting these Color objects I needed some way of displaying them. Rather than just print out the RBG values of the object it's important to actually see the colors that have been created. Otherwise it's a little difficult to actually see if the color sorting has worked. The easiest way to do this is to use the built in PHP image creation functions to generate an image. The following function takes the array of Color objects created in the above example and generates an image where each color is represented by a 1 pixel wide band. The second parameter is the type of sort we are using.

  1. function renderColors($colors, $sortedBy) {
  2. $color_width = 1;
  3.  
  4. $width = count($colors) * $color_width;
  5. $height = 50;
  6.  
  7. $im = imagecreatetruecolor($width, $height);
  8. $background_color = imagecolorallocate($im, 255, 255, 255);
  9.  
  10. $x = 0;
  11.  
  12. foreach ($colors as $colorObject) {
  13. $color = imagecolorallocate($im, $colorObject->red, $colorObject->green, $colorObject->blue);
  14. imagefilledrectangle($im, $x, 0, $x + $color_width,$height, $color);
  15.  
  16. $x = $x + $color_width;
  17. }
  18.  
  19. imagepng($im, 'colors-' . $sortedBy . '.png');
  20. }

The first thing to do is look at an unsorted color array, this can be printed out using.

renderColors($colors, 'none');

This generates the following image containing random colors in a file called 'colors-none.png'.

Random colors.

Now we have a way of rendering the colors we can start looking at sorting them.

RGB Sorting

Perhaps the easiest thing to sort by is the raw RGB value. This can be done by adding together the three different components of red, green and blue to get a single number that can be compared with other colors.

  1. usort($colors, function ($a, $b) {
  2. return ($a->red + $a->green + $a->blue) <=> ($b->red + $b->green + $b->blue);
  3. });

At face value this feels like it should work correctly as the darker and lighter colours will be grouped together. Indeed, this type of sorting does work if we are sorting grey or monochrome values as the difference between the colors does not cause overlaps. Here are a couple of examples of sorting just using grey and monochrome colors.

Grey colors sorted by RGB.Red colors sorted by RGB.

With the random collection of colors the end result or sorting by RGB is very messy.

Colors sorted by RGB

The colors are clearly sorted though. The darker colors are pushed towards the bottom and the lighter colors are pushed towards the top. There is still a long way to go though.

Hex Sorting

A slightly different approach is to sort by the hex value. This is a value that is quite commonly used throughout web development so I wanted to see what sort of result it gave.

  1. usort($colors, function ($a, $b) {
  2. $aValue['red'] = str_pad(dechex($a->red), 2, '0', STR_PAD_LEFT);
  3. $aValue['green'] = str_pad(dechex($a->green), 2, '0', STR_PAD_LEFT);
  4. $aValue['blue'] = str_pad(dechex($a->blue), 2, '0', STR_PAD_LEFT);
  5.  
  6. $bValue['red'] = str_pad(dechex($b->red), 2, '0', STR_PAD_LEFT);
  7. $bValue['green'] = str_pad(dechex($b->green), 2, '0', STR_PAD_LEFT);
  8. $bValue['blue'] = str_pad(dechex($b->blue), 2, '0', STR_PAD_LEFT);
  9.  
  10. $aValue = implode($aValue);
  11. $bValue = implode($bValue);
  12.  
  13. return $aValue <=> $bValue;
  14. });

Unfortunately, this type of color sort produces a terrible result with blues/green colors pushed lower and red colors pushed higher.

Colors sorted by Hex

This is more of a side effect of the ordering of the colors in the hex value than a representation of the actual color involved.

Lightness Sorting

Instead of going for sorting by basic values I though of looking at other values that the color has. The first thing I looked at was lightness. Lightness is brightness relative to the brightness of a similarly illuminated white. This is worked out by looking at the minimum and maximum color values.

  1. function calculateLightness($color) {
  2. $red = $color->red / 255;
  3. $green = $color->green / 255;
  4. $blue = $color->blue / 255;
  5.  
  6. $chroma_min = min($red, $green, $blue);
  7. $chroma_max = max($red, $green, $blue);
  8.  
  9. return ($chroma_max + $chroma_min) / 2;
  10. }
  11.  
  12. usort($colors, function ($a, $b) {
  13. return calculateLightness($a) <=> calculateLightness($b);
  14. });

This produces the following sorted colors.

Colors sorted by Lightness

This is clearly sorted by lightness with lighter colors getting push towards one end, but the colors look mixed up.

Luminance Sorting

Luminance describes the perceived lightness of a color, rather than the measured lightness. There are a couple of different standards available to work out luminance, but the one we are going for here is photometric/digital ITU BT.709. This is calculated using

(0.2126 x R) + (0.7152 x G) + (0.0722 x B)

To sort by luminance we use the following code.

  1. function calculateLuminance($color) {
  2. return (0.2126 * $color->red) + (0.7152 * $color->green) + (0.0722 * $color->blue);
  3. }
  4.  
  5. usort($colors, function ($a, $b) {
  6. return calculateLuminance($a) <=> calculateLuminance($b);
  7. });

This produces the following sorted colors.

Colors sorted by Luminance.

This is similar to the lightness sorting, but obviously has a different bias to the colors being sorted.

HSV Sorting

Rather than relying on the RGB colors to sort I wondered how the sort would look if I converted the RGB to a different color space. HSV or hue, saturation, value color space is defined in a way what is closer to how humans perceive colors. The hue is a value between 0 and 360 (i.e. degrees on a circle) and denotes the actual color. The saturation is the amount of grey in the color that ranges from 0 to 100 percent, where 0 denotes being fully grey and 100 being the full primary color. The value (or brightness) is a measurement of the darkness of the color between 0 and 100 percent, where 0 is fully black and 100 reveals the most color. Saturation and value are normally stored as a value between 0 and 1 in computer science.

Here is a function that converts our RGB color to a HSV. It just returns an associative array containing the three values.

  1. function rgbTohsv($color) {
  2. $red = $color->red / 255;
  3. $green = $color->green / 255;
  4. $blue = $color->blue / 255;
  5.  
  6. $min = min($red, $green, $blue);
  7. $max = max($red, $green, $blue);
  8.  
  9. switch ($max) {
  10. case 0:
  11. // If the max value is 0.
  12. $hue = 0;
  13. $saturation = 0;
  14. $value = 0;
  15. break;
  16. case $min:
  17. // If the maximum and minimum values are the same.
  18. $hue = 0;
  19. $saturation = 0;
  20. $value = round($max, 4);
  21. break;
  22. default:
  23. $delta = $max - $min;
  24. if ($red == $max) {
  25. $hue = 0 + ($green - $blue) / $delta;
  26. } elseif ($green == $max) {
  27. $hue = 2 + ($blue - $red) / $delta;
  28. } else {
  29. $hue = 4 + ($red - $green) / $delta;
  30. }
  31. $hue *= 60;
  32. if ($hue < 0) {
  33. $hue += 360;
  34. }
  35. $saturation = $delta / $max;
  36. $value = round($max, 4);
  37. }
  38.  
  39. return ['hue' => $hue, 'saturation' => $saturation, 'value' => $value];
  40. }

This function can be used to sort the color array in the following way.

  1. usort($colors, function ($a, $b) {
  2. $hsv1 = rgbTohsv($a);
  3. $hsv2 = rgbTohsv($b);
  4.  
  5. return ($hsv1['hue'] + $hsv1['saturation'] + $hsv1['value']) <=> ($hsv2['hue'] + $hsv2['saturation'] + $hsv2['value']);
  6. });

This produces the following color band, which is actually pretty close so what we want.

Colors sorted by HSV

There is a little bit of noise in here caused by lighter colors being dotted throughout, but it's close.

Hue Sorting

Because the saturation and value amounts in the HSV sort are quite small we can probably ignore them and get a similar result. So here is a function that just works out the hue of a RGB color.

  1. function calcualteHue($color) {
  2. $red = $color->red / 255;
  3. $green = $color->green / 255;
  4. $blue = $color->blue / 255;
  5.  
  6. $min = min($red, $green, $blue);
  7. $max = max($red, $green, $blue);
  8.  
  9. switch ($max) {
  10. case 0:
  11. // If the max value is 0.
  12. $hue = 0;
  13. break;
  14. case $min:
  15. // If the maximum and minimum values are the same.
  16. $hue = 0;
  17. break;
  18. default:
  19. $delta = $max - $min;
  20. if ($red == $max) {
  21. $hue = 0 + ($green - $blue) / $delta;
  22. } elseif ($green == $max) {
  23. $hue = 2 + ($blue - $red) / $delta;
  24. } else {
  25. $hue = 4 + ($red - $green) / $delta;
  26. }
  27. $hue *= 60;
  28. if ($hue < 0) {
  29. $hue += 360;
  30. }
  31. }
  32. return $hue;
  33. }

Sorting the colors by the function we use the following function.

  1. usort($colors, function ($a, $b) {
  2. return calcualteHue($a) <=> calcualteHue($b);
  3. });

This produces the following sorted color image.

Colors sorted by Hue

This is very close to the full HSV sort and doesn't require us to also work out the saturation and value amounts. It's still far from perfect though.

Divide And Conquer Hue Sorting

We are quite close with the hue sort, but it still needs something extra to allow better sorting. A better approach is to split apart the colors into their separate hues and then sort each hue separately. There are roughly 6 colors available in the hue values (Red, Yellow, Green, Cyan, Blue, Magenta) so by doubling this we can split the hue into 12 separate segments by dividing the hue by 30.

  1. // Set up the ranges array.
  2. $ranges = [];
  3.  
  4. foreach ($colors as $color) {
  5. // Get the hue.
  6. $hue = calcualteHue($color);
  7.  
  8. // Simplify the hue to create 12 segments.
  9. $simplifiedHue = floor($hue / 30);
  10.  
  11. if (!isset($ranges[$simplifiedHue])) {
  12. // Add the simplified hue to the ranges array if it doesn't exist.
  13. $ranges[$simplifiedHue] = [];
  14. }
  15.  
  16. // Add the color to the correct segment.
  17. $ranges[$simplifiedHue][] = $color;
  18. }
  19.  
  20. // Sort the ranges by their keys (the simplified hue).
  21. ksort($ranges);

With this in place we have an approximate ranged of colors that belong to a particular hue. Because RGB sorting is actually pretty good with monochrome sorting we can then sort each item in the range of colors by their RGB values.

  1. $newColors = [];
  2. foreach ($ranges as $id => $colorRange) {
  3. usort($colorRange, function ($a, $b) {
  4. return ($a->red + $a->green + $a->blue) <=> ($b->red + $b->green + $b->blue);
  5. });
  6. $newColors = array_merge($newColors, $colorRange);
  7. }

After rending the $newColors array of colors we get the following image

Colors sorted by Hue then RGB.

This is about as close as we can get using this random color data, but it's still a little bit messy due to the grey colors failing to be sorted correctly. Some of these segments do look a little off, but that's due to the random colors we are using to sort with.

Impossible?

I have tried to sort in a few different ways here, but each time I've gotten close there is always something causing the colors to look a little messy.

Some of you (especially if you have seen this problem before) might have spotted by now that this is actually impossible. The issue is that trying to sort color information containing multi-dimensional data into a 2 dimensional plane means that some of the data will inherently be missed out during the sort. That's why you never see a color picker in a linear, 2 dimensional line in any application or website. You actually tend to see HSV cubes where you select the color and then change the saturation.

I will probably write a follow up post on this subject, exploring the issue of sorting colors into a 3 dimensional grid.

If you are interested in getting all the code seen in this post in a single class then take a look at the Color class that I created for a website evolution engine I've been working on for a while. That Color class allows you to create the object using RGB, hex or even HSV and then work out the color geometry from there.

Comments

Permalink

Great analysis! I'm currently deciding how I want to sort color values and am glad to see solutions and to avoid spending a huge amount of time doing this as a result of you writing this article. Thanks much!

Chris (Tue, 08/14/2018 - 13:38)

Permalink

Hi :)

Sorting colors by pure RGB you can forget. How should a computer think

about FFCCFF ? is it now more red or more blue ?

Pure rainbow colors have just TWO RGB values,

Sub spectral_dan_bruton()
    Dim N, M, MM, i, j As Long
    Dim GAMMA, SSS As Double
    Dim R, G, B As Double
    Dim CV() As Double
    Dim out As String
    Dim CRG As Long
    out = "<table>"

    M = 400
    MM = M
    N = 1
    
    GAMMA = 1
    
    
    For WL = 380 To 780 Step 0.05 'wellenlänge
       
        'c WaveLength = WL
        'c
        R = 0
        G = 0
        B = 0
        
        
        For j = 0 To N - 1 'intensität
        
            If ((WL >= 380#) And (WL <= 440#)) Then
            
                R = -1# * (WL - 440#) / (440# - 380#)
                G = 0#
                B = 1#
                CRG = 0
            End If
            If ((WL >= 440#) And (WL <= 490#)) Then
                R = 0#
                G = (WL - 440#) / (490# - 440#)
                B = 1#
                CRG = 1
            End If
            If ((WL >= 490#) And (WL <= 510#)) Then
                R = 0#
                G = 1#
                B = -1# * (WL - 510#) / (510# - 490#)
                CRG = 2
            End If
            If ((WL >= 510#) And (WL <= 580#)) Then
                R = (WL - 510#) / (580# - 510#)
                G = 1#
                B = 0#
                CRG = 3
            End If
            If ((WL >= 580#) And (WL <= 645#)) Then
                R = 1#
                G = -1# * (WL - 645#) / (645# - 580#)
                B = 0#
                CRG = 4
            End If
            If ((WL >= 645#) And (WL <= 780#)) Then
                R = 1#
                G = 0#
                B = 0#
                CRG = 5
            End If

            '      LET THE INTENSITY SSS FALL OFF NEAR THE VISION LIMITS

            SSS = 1#
            If (WL < 420#) Then
                SSS = 0.3 + 0.7 * (WL - 380#) / (420# - 380#)
            End If
         
         
            If (WL > 700#) Then
                SSS = 0.3 + 0.7 * (780# - WL) / (780# - 700#)
            End If
            'c      GAMMA ADJUST AND WRITE IMAGE TO AN ARRAY
            SSS = 1#
            R = (SSS * R) ^ GAMMA
            G = (SSS * G) ^ GAMMA
            B = (SSS * B) ^ GAMMA
            
            
            R = Fix(R * 255)
            G = Fix(G * 255)
            B = Fix(B * 255)
            
            HR = Hex(R)
            HG = Hex(G)
            HB = Hex(B)
            If Len(HR) = 1 Then HR = "0" & HR
            If Len(HG) = 1 Then HG = "0" & HG
            If Len(HB) = 1 Then HB = "0" & HB
    
            CO = "#" & HR & HG & HB
            '    Debug.Print L, CO, r, g, b
            If CO <> oco Then
                out = out & "<tr>"
                out = out & "<td>" & l & "</td>"
                out = out & "<td class='td' style='background:" & CO & "'>&nbsp " & D2S(R) & "," & D2S(G) & "," & D2S(B) & " </td>"
                out = out & "</tr>"
                oco = CO
                WL = round_to_grid(WL, 0.05)
                RGBWL.Add HR & HG & HB, WL
                WLRGB.Add Trim(str(WL)), HR & HG & HB
                RGBCRG.Add HR & HG & HB, D2S(CRG)
                c = c + 1
            End If
            
            'Debug.Print WL, Fix(CV(I, J, 0) * 255), Fix(CV(I, J, 1) * 255), Fix(CV(I, J, 2) * 255)
        Next
       
    Next
    
    out = out & "</table>"
    Call filewrite("r:\spectral_mod.html", out)
    Debug.Print c
End Sub

So in fact dan just plays with the wavelength. Nice rainbow but NO mixed colors.

BTW you can create such a rainbow far more simple. ;)

But how bout the idea to use this rainbow an compare colors by a color distance = ?

Sub RGBdist(r1, g1, b1, r2, g2, b2)
     R = r1 - r2
     G = g1 - g2
     B = b1 - b2
     DIST = Sqr(2 * R * R + 4 * G + G + 3 * B * B)
End Sub

And this is really the most simplest equatation to do that ;)

Well it turns out, that even this approach with a few tunings give much better Results then just RGB or HSV Sorting

There are a few better color distance formulas out 

DIN 99 D

CIE2000

just to name two.

as testcase i use the LCARS colors - yeah im oldfashioned i love startrek :D 

Sub LCARSCOL()
    Dim rgb As String
    Dim dict As New DICTIONARY_VBA
    dict.RemoveAll
    
    BASE = "FF CC 99 66 33 00"
    Dim RES(215) As String
    Dim c() As String
    Dim ARR(215) As Double
    Dim YIQ(215) As Double
    Dim HSV(215) As String
    
    Dim RD As Double
    Dim GD As Double
    Dim BD As Double
    Dim R As Long
    Dim G As Long
    Dim B As Long
    
    Dim h As Long
    Dim s As Long
    Dim v As Long
    Dim hue As Double
    
    Dim SAT As Double
    Dim value As Double
    c = Split(BASE)
    'yiq sort
    For i = 0 To UBound(c)
        For j = 0 To UBound(c)
            For k = 0 To UBound(c)
                rgb = "#" & c(i) & c(j) & c(k)
                RES(N) = rgb
                R = CLng("&H" & c(i))
                G = CLng("&H" & c(j))
                B = CLng("&H" & c(k))
                
                RD = CLng("&H" & c(i))
                GD = CLng("&H" & c(j))
                BD = CLng("&H" & c(k))
                YIQ(N) = ((RD * 299) + (GD * 587) + (BD * 114)) / 1000
                '  HSV(n) = RGBtoHSV(RD, GD, BD, HUE, SAT, VALUE)
                HSV(N) = RGB_to_HSV(R, G, B, h, s, v)
                ARR(N) = h + 0.000001 * N
                Debug.Print hue, SAT, value, h, s, v
                dict.Add D2S(ARR(N)), N
                LCARS.Add c(i) & c(j) & c(k), c(i) & c(j) & c(k)
                N = N + 1
            Next
        Next
    Next
    
    QuickSort2 ARR
    
    For i = 0 To UBound(ARR)
    Debug.Print ARR(i)
    Next
    Dim out As String
    out = "<table>"
    
    For i = 0 To UBound(ARR)
        k = val(dict.ITEM(D2S(ARR(i))))
        out = out & "<tr><td>" & i & "<td></td><td class='td' style='background:" & RES(k) & "'>&nbsp " & RES(k) & "&nbsp" & "<td>" & HSV(k) & "</td>" & " </td></tr>"
    Next
    out = out & "</table>"
    Call filewrite("r:\lcars.html", out)
End Sub

 

"Sorry" for the VBA but my PHP times are over :)

Runs fine in excel or VB6 and dumps out html tables which can be viewed with chrome.

Have some fun with the things

Best regards Thomas

 

 

 

 

 

 

rexxitall (Fri, 09/07/2018 - 21:26)

Permalink

Thanks for this comment Thomas. I did read it all at the time but didn't respond.

I did actually look into color distance a little, but ended up not going ahead with it. I can't remember why, but I don't think it gave me any decent results. I might try with your example math and see what sort of results I get.

philipnorton42 (Thu, 01/03/2019 - 12:27)

Add new comment

The content of this field is kept private and will not be shown publicly.