"Rounding" colour values to the nearest of a small set of colours

Preamble

As a part of a project I'm working on I am trying to provide a convenient way to search for images in our system. We currently provide searching by various types of user added metadata (e.g. title, description, keywords) and by various metadata which we extract (e.g. EXIF, IPTC, XMP, etc). I would also like to add a 开发者_如何转开发"colour search" similar to what you can see in google's image search.

The project uses PHP and we can use the Imagemagick extension to segment and quantize the image and extract the most "significant" colours from the image; I'm not entirely certain of the results I'm getting here, but they seem reasonably accurate and certainly better than nothing.

The Problem

The bit that I'm having difficulty on is converting these significant colours into a set of representative colours, e.g. when you look at Google's image search there is a set of 12 colours there. I'd like to mathematically "round" my colour value to the nearest representative colour, so that I can index the image with the colours that I detect and then facet my search results that way.

Any suggestions?

---

The first step would be to define the colors you want to compare to.

The second step is to find the smallest distance from your color to one of the colors you chose in the previous step. In order to be able to measure that distance you need an Euclidian space in which to model colors.

Of course the simple choice would be the RGB space

And the distance between two colors C₁(r₁, g₁, b₁) and C₂(r₂, g₂, b₂) would be

sqrt( (r₁ - r₂)² + (g₁ - g₂)² + (b₁ - b₂)² ).

But if you need more precision it would be better to use the Hue-Chroma-Lightness bicone space, a derivative of the HSL cylinder.

In the RGB space things were straight forward as R, G and B where each on a separate axis. In HCL we need to compute the coordinates on each of the axis.

First of all we compute the chroma (which is a bit different from saturation) as:

Chroma = max(Red, Green, Blue) - min(Red, Green, Blue)

Then we normalize our H, C and L value so that H goes from 0 to 2 (to cover a circle if we multiply by PI and take radians as the unit), C goes from 0 to 1 (the radius of the trigonometric circle) and L goes from -1 (Black) to 1 (White).

Next we take z = L without any transformations as it is clear from the image that it goes along the vertical axis.

We can easily observe that for a color, Chroma is the distance from the z axis and Hue is the angle. So we get

x = C * cos(H*PI) and
y = C * sin(H*PI)

At this point x, y and z will all be in [-1, 1] and the distance between two colors will be, using the same formula as above,

sqrt( (x₁ - x₂)² + (y₁ - y₂)² + (z₁ - z₂)² ).

---

To get even more precision and find the closest color according to human color perception you could use the CIE-L*ab modeling space and compute the distance with one of these algorithms. The principles are the same as for the two cases presented above, only the algorithms are more complex.

---

Update (7 years later)

Finally xkcd featured a comic that I can use in this post!

https://xkcd.com/1882/

---

function getSimilarColors (color) {
    var base_colors=["660000","990000","cc0000","cc3333","ea4c88","993399","663399","333399","0066cc","0099cc","66cccc","77cc33","669900","336600","666600","999900","cccc33","ffff00","ffcc33","ff9900","ff6600","cc6633","996633","663300","000000","999999","cccccc","ffffff"];

    //Convert to RGB, then R, G, B
    var color_rgb = hex2rgb(color);
    var color_r = color_rgb.split(',')[0];
    var color_g = color_rgb.split(',')[1];
    var color_b = color_rgb.split(',')[2];

    //Create an emtyp array for the difference betwwen the colors
    var differenceArray=[];

    //Function to find the smallest value in an array
    Array.min = function( array ){
           return Math.min.apply( Math, array );
    };


    //Convert the HEX color in the array to RGB colors, split them up to R-G-B, then find out the difference between the "color" and the colors in the array
    $.each(base_colors, function(index, value) { 
        var base_color_rgb = hex2rgb(value);
        var base_colors_r = base_color_rgb.split(',')[0];
        var base_colors_g = base_color_rgb.split(',')[1];
        var base_colors_b = base_color_rgb.split(',')[2];

        //Add the difference to the differenceArray
        differenceArray.push(Math.sqrt((color_r-base_colors_r)*(color_r-base_colors_r)+(color_g-base_colors_g)*(color_g-base_colors_g)+(color_b-base_colors_b)*(color_b-base_colors_b)));
    });

    //Get the lowest number from the differenceArray
    var lowest = Array.min(differenceArray);

    //Get the index for that lowest number
    var index = differenceArray.indexOf(lowest);

    //Function to convert HEX to RGB
    function hex2rgb( colour ) {
        var r,g,b;
        if ( colour.charAt(0) == '#' ) {
            colour = colour.substr(1);
        }

        r = colour.charAt(0) + colour.charAt(1);
        g = colour.charAt(2) + colour.charAt(3);
        b = colour.charAt(4) + colour.charAt(5);

        r = parseInt( r,16 );
        g = parseInt( g,16 );
        b = parseInt( b ,16);
        return r+','+g+','+b;
    }

    //Return the HEX code
    return base_colors[index];
}

---

This is a rough idea only - you will need to tweak it to your own needs.

Basically, I thought that, as colors are recorded as RGB, either as a Hex string "#000000" to "#ffffff", or as an RGB set "rgb(0,0,0)" to "rgb(255,255,255)", and these are interchangeable/translateable, this is a simple mathematical rounding issue.

In the full range of colors there would be (16*16)*(16*16)*(16*16) = 256*256*256 = 16,777,216 possible colors.

Rounding colors to their closest single character Hex value reduces that to 16*16*16 = 4,096 possible colors. Still far too many, but getting closer.

Rounding colors to a single character value, but then limiting that further to being one of 4 (0,3,7,f) reduces it to 4*4*4 = 32. Close enough for me.

So, I built a very basic PHP function to try and achieve this:

function coloround( $incolor ){
  $inR = hexdec( $incolor{0}.$incolor{1} )+1;
  $inG = hexdec( $incolor{2}.$incolor{3} )+1;
  $inB = hexdec( $incolor{4}.$incolor{5} )+1;
 # Round from 256 values to 16
  $outR = round( $outR/16 );
  $outG = round( $outG/16 );
  $outB = round( $outB/16 );
 # Round from 16 to 4
  $outR = round( $outR/4 );
  $outG = round( $outG/4 );
  $outB = round( $outB/4 );
 # Translate to Hex
  $outR = dechex( max( 0 , $outR*4-1 ) );
  $outG = dechex( max( 0 , $outG*4-1 ) );
  $outB = dechex( max( 0 , $outB*4-1 ) );
 # Output
  echo sprintf( '<span style="background-color:#%s;padding:0 10px;"></span> &gt; <span style="background-color:#%s;padding:0 10px;"></span>%s has been rounded to %s<br>' ,
         $incolor , $outR.$outG.$outB ,
         $incolor , $outR.$outG.$outB );
}

This function, when passed a hex string, echos a sample of the original color and a sample of the abbreviated color.

This is just a basic proof-of-concept, as I do not know the format Imagemagick is returning the colors as, but you may be able to utilise this logic to create your own.

From those 32 colors then, you could group the similar (there would probably be about 8 shades of grey in there) and name the remainder to allow your users to search by them.

---

Depending on the number of colors you're looking for, why not try using bitwise operators (PHP's reference here, since you mentioned it in the question) to reduce the number of significant digits? You could round the RGB values before shifting to increase accuracy as well.