Color Sorting In PHP

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.

class Color {
    public $red = 0;
    public $green = 0;
    public $blue = 0;

    public function __construct($red, $green, $blue)
    {
        $this->red = $red;
        $this->green = $green;
        $this->blue = $blue;
    }
}

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.

$colors = [];

for ($i = 0; $i < 750; $i++) {
  $red = ceil(mt_rand(0, 255));
  $green = ceil(mt_rand(0, 255));
  $blue = ceil(mt_rand(0, 255));

  $colors[] = new Color($red, $blue, $green);
}

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.

function renderColors($colors, $sortedBy) {
    $color_width = 1;

    $width = count($colors) * $color_width;
    $height = 50;

    $im = imagecreatetruecolor($width, $height);
    $background_color = imagecolorallocate($im, 255, 255, 255);

    $x = 0;

    foreach ($colors as $colorObject) {
      $color = imagecolorallocate($im, $colorObject->red, $colorObject->green, $colorObject->blue);
      imagefilledrectangle($im, $x, 0, $x + $color_width,$height, $color);

      $x = $x + $color_width;
    }

    imagepng($im, 'colors-' . $sortedBy . '.png');
    imagedestroy($im);
}

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'.

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.

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

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.

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

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.

usort($colors, function ($a, $b) {
      $aValue['red'] = str_pad(dechex($a->red), 2, '0', STR_PAD_LEFT);
      $aValue['green'] = str_pad(dechex($a->green), 2, '0', STR_PAD_LEFT);
      $aValue['blue'] = str_pad(dechex($a->blue), 2, '0', STR_PAD_LEFT);

      $bValue['red'] = str_pad(dechex($b->red), 2, '0', STR_PAD_LEFT);
      $bValue['green'] = str_pad(dechex($b->green), 2, '0', STR_PAD_LEFT);
      $bValue['blue'] = str_pad(dechex($b->blue), 2, '0', STR_PAD_LEFT);

      $aValue = implode($aValue);
      $bValue = implode($bValue);

      return $aValue <=> $bValue;
});

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

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.

function calculateLightness($color) {
  $red = $color->red / 255;
  $green = $color->green / 255;
  $blue = $color->blue / 255;

  $chroma_min = min($red, $green, $blue);
  $chroma_max = max($red, $green, $blue);

  return ($chroma_max + $chroma_min) / 2;
}

usort($colors, function ($a, $b) {
  return calculateLightness($a) <=> calculateLightness($b);
});

This produces the following sorted colors.

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.

function calculateLuminance($color) {
  return (0.2126 * $color->red) + (0.7152 * $color->green) + (0.0722 * $color->blue);
}

usort($colors, function ($a, $b) {
  return calculateLuminance($a) <=> calculateLuminance($b);
});

This produces the following sorted colors.

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.

function rgbTohsv($color) {
  $red = $color->red / 255;
  $green = $color->green / 255;
  $blue = $color->blue / 255;

  $min = min($red, $green, $blue);
  $max = max($red, $green, $blue);

  switch ($max) {
    case 0:
      // If the max value is 0.
      $hue = 0;
      $saturation = 0;
      $value = 0;
      break;
    case $min:
      // If the maximum and minimum values are the same.
      $hue = 0;
      $saturation = 0;
      $value = round($max, 4);
      break;
    default:
      $delta = $max - $min;
      if ($red == $max) {
        $hue = 0 + ($green - $blue) / $delta;
      } elseif ($green == $max) {
        $hue = 2 + ($blue - $red) / $delta;
      } else {
        $hue = 4 + ($red - $green) / $delta;
      }
      $hue *= 60;
      if ($hue < 0) {
        $hue += 360;
      }
      $saturation = $delta / $max;
      $value = round($max, 4);
  }

  return ['hue' => $hue, 'saturation' => $saturation, 'value' => $value];
}

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

usort($colors, function ($a, $b) {
  $hsv1 = rgbTohsv($a);
  $hsv2 = rgbTohsv($b);

  return ($hsv1['hue'] + $hsv1['saturation'] + $hsv1['value']) <=> ($hsv2['hue'] + $hsv2['saturation'] + $hsv2['value']);
});

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

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.

function calcualteHue($color) {
  $red = $color->red / 255;
  $green = $color->green / 255;
  $blue = $color->blue / 255;

  $min = min($red, $green, $blue);
  $max = max($red, $green, $blue);

  switch ($max) {
      case 0:
          // If the max value is 0.
          $hue = 0;
          break;
      case $min:
          // If the maximum and minimum values are the same.
          $hue = 0;
          break;
      default:
          $delta = $max - $min;
          if ($red == $max) {
              $hue = 0 + ($green - $blue) / $delta;
          } elseif ($green == $max) {
              $hue = 2 + ($blue - $red) / $delta;
          } else {
              $hue = 4 + ($red - $green) / $delta;
          }
          $hue *= 60;
          if ($hue < 0) {
              $hue += 360;
          }
  }
  return $hue;
}

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

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

This produces the following sorted color image.

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.

// Set up the ranges array.
$ranges = [];

foreach ($colors as $color) {
  // Get the hue.
  $hue = calcualteHue($color);

  // Simplify the hue to create 12 segments.
  $simplifiedHue = floor($hue / 30);

  if (!isset($ranges[$simplifiedHue])) {
    // Add the simplified hue to the ranges array if it doesn't exist.
    $ranges[$simplifiedHue] = [];
  }

  // Add the color to the correct segment.
  $ranges[$simplifiedHue][] = $color;
}

// Sort the ranges by their keys (the simplified hue).
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.

$newColors = [];
foreach ($ranges as $id => $colorRange) {
  usort($colorRange, function ($a, $b) {
     return ($a->red + $a->green + $a->blue) <=> ($b->red + $b->green + $b->blue);
  });
  $newColors = array_merge($newColors, $colorRange);
}

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

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.