Colour detection algorithm in PHP

Last weeks I’ve been working on colour detection algorithm so in this post I will share few ideas how to solve this problem.

First think we need to do is to choose the area where we will be checking colours. roi_sThis area is called ROI and usually it’s a rectangle located in the center of an image, covering 5/6 of it’s size. ROI is necessary because the most of images has relevant data located in the center (faces, logos, etc…), therefore colours on the edges won’t be important for us.

The next step is to decide the size of a detection mesh – distance between points where we will check image colour. Of course – the more points we check the better, but in case of big images algorithm can become very slow. Therefore we need to set up fixed number of points per image width / height. I decided to check 1/10th of width and 1/10th of image height.

OK, let’s retrieve pixel colour:

... open image ...
for ($x = $roi['x']['min']; $x <= $roi['x']['max']; $x += $pointDistance['x']) {
    for ($y = $roi['y']['min']; $y <= $roi['y']['max']; $y += $pointDistance['y']) {
        // get color vector of current pixel
        $colorVector = imageColorsForIndex($img, imageColorAt($img, $x, $y));
        ... do something with colour ...
    }
}

Colour detection algorithm

The next step is to decide whether we want to map pixel colours to a predefined palette or not. If not, there is nothing more you have to do than saving data of pixel colour acquired using above code. But if we want to map pixel colour to a palette, things getting more complicated. In my case I had a palette of 12 colours: [red, orange, yellow, green, turquoise, blue, purple, pink, white, gray, black, brown].

The hearth of image colour detection algorithm is finding the shortest distance between two colours; one from palette and another from image pixel.
This leads us to checking the shortest distance between two n-dimensional vectors in one of chosen colour space.
There are three main colour spaces:

  • RGB – red, green and blue
  • HSV / HSB – hue, saturation and value
  • LAB – lightness, a and b color-opponent dimensions based on XYZ color space coordinates

RGB

The easiest way is to compare colour vectors in RGB space – we will just need to solve Euclidean Vector Distance equation for each pixel and colour in our palette:

vector distance

As for most of images, this method will give good results but unfortunately – images containing pale colours like light brown/yellow/green/pink will be mismatched. This is because RGB colour space does not reflect the way how human eye sees colours. In RGB pale pink and brown are much more closer colours than pink and red (for human, obviously not).
Distance between colours will be as follows:

function colorDistance($a, $b) {
    return sqrt(pow($a['red'] - $b['red'], 2)
                + pow($a['green'] - $b['green'], 2)
                + pow($a['blue'] - $b['blue'], 2));
}

HSV

HSV_cone

Much more better results we can get using Hue-Saturation-Value color space. HSV space is a cone with colour wheel at the bottom.
In order to convert colours to HSV color space, we need to:

function rgbToHsv($rgb) {
    $h = 0;
    $s = 0;
    $v = 0;
    $r = $rgb[0] / 255;
    $g = $rgb[1] / 255;
    $b = $rgb[2] / 255;
    $max = max( $r, $g, $b );
    $min = min( $r, $g, $b );

    if ( $max === $min ) $h = 0;
    else if ( $max === $r ) $h = ( 60 * ($g - $b) / ( $max - $min ) + 360 ) % 360;
    else if ( $max === $g ) $h = 60 * ( $b - $r ) / ( $max - $min ) + 120;
    else if ( $max === $b ) $h = 60 * ( $r - $g ) / ( $max - $min ) + 240;

    if ( $max === 0 ) $s = 0;
    else $s = 1 - $min / $max;

    $v = $max;

    $hsv = array($h, $s * 100, $v * 100);
    return $hsv;
}

In HSV colour space brightest colours are on the bottom, darkest on the top of a cone. Pale colours are close to cone axis. Hue is a degree on a colour wheel with values from 0-360, therefore during counting distance between colours we need to “fold” one dimension to get the actual proper value.

function colorDistance($a, $b) {
    $hueDiff = 0;
    // folding "H" dimension
    if ($a[0] > $b[0]) {
        $hueDiff = min($a[0] - $b[0], $b[0] - $a[0] + 360);
    } else {
        $hueDiff = min($b[0] - $a[0], $a[0] - $b[0] + 360);
    }

    return sqrt(pow($hueDiff, 2)
                + pow($a[1] - $b[1], 2)
                + pow($a[2] - $b[2], 2));
}

That’s all! As a result of above code you’ll get shortest distance between two colours which help you to decide which colour from palette is the closest to colour of a pixel.

As far as I know, the best results with colour detection algorithm you can get using LAB colour space. Unfortunately, conversion between RGB and LAB colour space is much more complicated so I decided to write separate post about this topic.

Sources and useful links

http://www.emanueleferonato.com/2009/08/28/color-differences-algorithm/
http://stevehanov.ca/blog/index.php?id=116
http://en.wikipedia.org/wiki/Color_difference
http://homepages.inf.ed.ac.uk/rbf/PAPERS/iccv99.pdf
http://www.cs.cmu.edu/~har/visapp2006.pdf
http://research.cs.wisc.edu/vision/piximilar/
http://mattmueller.me/Piximilar/paper.pdf
http://mattmueller.me/blog/creating-piximilar-image-search-by-color