RGB to closest predefined color

Question

Edit:

With the answer given I made this function

function grabclosestcolor($r, $g, $b){
    $colors = array(array(124,12,12),array(7,7,11),array(110,224,219),array(123,123,123),array(124,177,74),array(130,86,53),array(77,77,77),array(164,124,68),array(204,196,132),array(164,148,147),array(163,123,67),array(26,122,26), array(195,195,50),array(193,193,193),array(255,248,73),array(243,243,243));
    $differencearray = array();
    foreach ($colors as $value) {
        $difference = sqrt(pow($r-$value[0],2)+pow($g-$value[1],2)+pow($b-$value[2],2));
        array_push($differencearray, $difference);
        $smallest = min($differencearray);
        $key = array_search($smallest, $differencearray);
        return $colors[$key];
        }
    }

---

My goal is this. I grab a picture and loop through each pixel and grab its x,y, and rgb.

Instead of just grabbing the rgb, I have a predefined array and I'm looking for the closest match from the color I grabbed to the predefined array. The goal here is to only use colors from the predefined array. Here is my array of colors.

$colors = array(array(124,12,12),array(7,7,11),array(110,224,219),array(123,123,123),array(124,177,74),array(130,86,53),array(77,77,77),array(164,124,68),array(204,196,132),array(164,148,147),array(163,123,67),array(26,122,26), array(195,195,50),array(193,193,193),array(255,248,73),array(243,243,243));

and here is my existing code that loops through it all.

$int = imagesx($im) - 1;
$int2 = imagesy($im) - 1;
$start2 = 0;
do{
    $start = 0;
    do{
        $rgb = imagecolorat($im, $start, $start2);
        $r = ($rgb >> 16) & 0xFF;
        $g = ($rgb >> 8) & 0xFF;
        $b = $rgb & 0xFF;
        $value = rgb2hex($r,$g,$b).":$start:$start2";
        array_push($colorsofimage, $value);
    } while($int > $start++);
} while($int2 > $start2++);

rgb2hex is a User Defined Function, but what I want to accomplish is to change that function with the function to grab the closest color.

$colorsofimage contains an array of each pixels info with hex:x:y what i want it to be is rgb2hex(NEWFUNCTION($r,$g,$b)); So that the new hex is the 1 out of the predefined array.

I hope you understood, because I have no clue how to do it because I don't know the algorithm of a color.

Answer 1

You have to calculate the distance to each color, and pick the smallest.

There are a few ways to do this. A simple method would be to calculate the distance would be:

sqrt((r-r1)^2+(g-g1)^2+(b-b1)^2)

A better method might be to incorporate the weighted values to calculate a distance, for instance the values used when converting RGB->YUV:

Y = 0.299 * R + 0.587 * G + 0.114 * B

in that case you would use

sqrt(((r - r1) * .299)^2 + ((g - g1) * .587)^2 + ((b - b1) * .114)^2)

Of course, since you don't need the exact distances, just a comparison, you can and probably should just skip the square root, making the last calculation:

((r - r1) * .299)^2 + ((g - g1) * .587)^2 + ((b - b1) * .114)^2

Answer 2

The RGB colour-space is simply a cube. In 24-bit colour each side has a length of 256, allowing values from 0 to 255. In order to find the closest colour in within this cube, you need a distance function. The simplest and most intuitive is the Euclidean distance: if you have colour (r1, g1, b1) and another colour (r2, g2, b2) the distance would be sqrt((r2-r1)^2 + (g2-g1)^2 + (b2-b1)^2).

The challenge for you is then to find the best match across all the values in your predefined array. I suggest that you start simply by iterating over all your values and check the distance for each in turn. Note that for this purpose you do not need to perform the sqrt, simply comparing on the sum of the squares would be sufficient, and would have the benefit of being all based in integer maths. My PHP isn't great, but roughly you would do:

function dist($col1,$col2) {
  $delta_r = $col1[0] - $col2[0];
  $delta_g = $col1[1] - $col2[1];
  $delta_b = $col1[2] - $col2[2];
  return $delta_r * $delta_r + $delta_g * $delta_g + $delta_b * $delta_b;
} 

$closest=$colors[0];
$mindist=dist($rgb,$colors[0]);
$ncolors=sizeof($colors);
for($i = 1; $i < $ncolors; ++$i)
{
    $currdist = dist($rgb,$colors[$i]);
    if($currdist<$mindist) {
      $mindist=$currdist;
      $closest=$colors[$i];
    }
}

There are more complicated distance functions (for instance, taking better account of psychovisual interpretation of colour differences (look into Delta E) but I suspect this is more than you need.

Answer 3

Since this question is displayed in the top ten of goolge search results, here is a more complex function I wrote some years ago, which produced better results than the existing PHP functions.

/*
 * Die Funktion gibt den Array-Schlüssel der Farbe ($palette),
 * die am ehesten der Farbe $givenColor entspricht.
 * 
 * Returns the index of the palette-color which is most similar
 * to $givenColor.
 * 
 * $givenColor und die Einträge in $palette können entweder
 * Strings im Format (#)rrggbb
 * (z. B. "ff0000", "4da4f3" oder auch "#b5d7f3")
 * oder Arrays mit je einem Wert für Rot, Grün und Blau 
 * (z. B. $givenColor = array( 0xff, 0x00, 0x00 ) )
 * sein.
 * 
 * $givenColor and the colors in $palette should be either
 * formatted as (#)rrggbb
 * (e. g. "ff0000", "4da4f3" or "#b5d7f3")
 * or arrays with values for red, green and blue
 * (e. g. $givenColor = array( 0xff, 0x00, 0x00 ) )
 *
 * Referenzen/References:
 * function rgb2lab
 *   - http://www.f4.fhtw-berlin.de/~barthel/ImageJ/ColorInspector//HTMLHilfe/farbraumJava.htm
 *   - http://www.brucelindbloom.com/index.html?Eqn_RGB_to_XYZ.html
 *   - http://www.brucelindbloom.com/index.html?Eqn_XYZ_to_Lab.html
 *
 * function deltaE
 *   - http://www.brucelindbloom.com/index.html?Eqn_DeltaE_CMC.html
 */
function getNearestColor( $givenColor,
                          $palette = array('blue' => '0000ff','red' => 'ff0000','green' => '00ff00','yellow' => 'ffff00','black' => '000000','white' => 'ffffff','orange' => 'ff8800','purple' => 'ff00ff', 'teal' => '00ffff')
  )
{
  if(!function_exists('rgb2lab'))
  {
    function rgb2lab($rgb) {
      $eps = 216/24389; $k = 24389/27;
      // reference white D50
      $xr = 0.964221; $yr = 1.0; $zr = 0.825211;
      // reference white D65
      #$xr = 0.95047; $yr = 1.0; $zr = 1.08883;

      // RGB to XYZ
      $rgb[0] = $rgb[0]/255; //R 0..1
      $rgb[1] = $rgb[1]/255; //G 0..1
      $rgb[2] = $rgb[2]/255; //B 0..1

      // assuming sRGB (D65)
      $rgb[0] = ($rgb[0] <= 0.04045)?($rgb[0]/12.92):pow(($rgb[0]+0.055)/1.055,2.4);
      $rgb[1] = ($rgb[1] <= 0.04045)?($rgb[1]/12.92):pow(($rgb[1]+0.055)/1.055,2.4);
      $rgb[2] = ($rgb[2] <= 0.04045)?($rgb[2]/12.92):pow(($rgb[2]+0.055)/1.055,2.4);

      // sRGB D50
      $x =  0.4360747*$rgb[0] + 0.3850649*$rgb[1] + 0.1430804*$rgb[2];
      $y =  0.2225045*$rgb[0] + 0.7168786*$rgb[1] + 0.0606169*$rgb[2];
      $z =  0.0139322*$rgb[0] + 0.0971045*$rgb[1] + 0.7141733*$rgb[2];
      // sRGB D65
      /*$x =  0.412453*$rgb[0] + 0.357580*$rgb[1] + 0.180423*$rgb[2];
      $y =  0.212671*$rgb[0] + 0.715160*$rgb[1] + 0.072169*$rgb[2];
      $z =  0.019334*$rgb[0] + 0.119193*$rgb[1] + 0.950227*$rgb[2];*/

      // XYZ to Lab
      $xr = $x/$xr; $yr = $y/$yr; $zr = $z/$zr;

      $fx = ($xr > $eps)?pow($xr, 1/3):($fx = ($k * $xr + 16) / 116); $fy = ($yr > $eps)?pow($yr, 1/3):($fy = ($k * $yr + 16) / 116); $fz = ($zr > $eps)?pow($zr, 1/3):($fz = ($k * $zr + 16) / 116);

      $lab = array();
      $lab[] = round(( 116 * $fy ) - 16); $lab[] = round(500*($fx-$fy)); $lab[] = round(200*($fy-$fz));      
      return $lab;
    } // function rgb2lab
  }

  if(!function_exists('deltaE'))
  {
    function deltaE($lab1, $lab2)
    {
      // CMC 1:1
      $l = 1; $c = 1;

      $c1 = sqrt($lab1[1]*$lab1[1]+$lab1[2]*$lab1[2]); $c2 = sqrt($lab2[1]*$lab2[1]+$lab2[2]*$lab2[2]);

      $h1 = (((180000000/M_PI) * atan2($lab1[1],$lab1[2]) + 360000000) % 360000000)/1000000;

      $t = (164 <= $h1 AND $h1 <= 345)?(0.56 + abs(0.2 * cos($h1+168))):(0.36 + abs(0.4 * cos($h1+35)));
      $f = sqrt(pow($c1,4)/(pow($c1,4) + 1900));

      $sl = ($lab1[0] < 16)?(0.511):((0.040975*$lab1[0])/(1 + 0.01765*$lab1[0]));
      $sc = (0.0638 * $c1)/(1 + 0.0131 * $c1) + 0.638;
      $sh = $sc * ($f * $t + 1 -$f);

      return sqrt( pow(($lab1[0]-$lab2[0])/($l * $sl),2) + pow(($c1-$c2)/($c * $sc),2) + pow(sqrt(($lab1[1]-$lab2[1])*($lab1[1]-$lab2[1]) + ($lab1[2]-$lab2[2])*($lab1[2]-$lab2[2]) + ($c1-$c2)*($c1-$c2))/$sh,2) );
    } // function deltaE
  }

  if(!function_exists('colorDistance'))
  {
    function colorDistance($lab1,$lab2)
    {
      return sqrt(($lab1[0]-$lab2[0])*($lab1[0]-$lab2[0])+($lab1[1]-$lab2[1])*($lab1[1]-$lab2[1])+($lab1[2]-$lab2[2])*($lab1[2]-$lab2[2]));
    }
  }

  if(!function_exists('str2rgb'))
  {
    function str2rgb($str)
    {
      $str = preg_replace('~[^0-9a-f]~','',$str);
      $rgb = str_split($str,2);
      for($i=0;$i<3;$i++)
        $rgb[$i] = intval($rgb[$i],16);

      return $rgb;
    } // function str2rgb
  }

  // split into RGB, if not already done
  $givenColorRGB = is_array($givenColor)?$givenColor:str2rgb($givenColor);
  $min = 0xffff;
  $return = NULL;

  foreach($palette as $key => $color)
  {
    // split into RGB
    $color = is_array($color)?$color:str2rgb($color);
    // deltaE
    #if($min >= ($deltaE = deltaE(rgb2lab($color),rgb2lab($givenColorRGB))))
    // euclidean distance
    if($min >= ($deltaE = colorDistance(rgb2lab($color),rgb2lab($givenColorRGB))))
    {
      $min = $deltaE;
      $return = $key;
    }
  }

  return $return;
}

Answer 4

Calculate the distance from the input color to all possible candidates of your palette, and then pick the one with the smallest distance as the one to replace it with.

Distance can be defined in any way you like; Euclidean distance seems workable for RGB cubes, cylinders or HSL/HSV cones.

Answer 5

There is no point in taking the square root. Finding the shortest distance is the same as finding the shortest squared distance. sqrt is an expensive operation, so just skip it.

Whether it really matters, of course, depends of how often your program will make this calculation, but it's still pointless to have it.