Algorithmus für nächstgelegene Farbe

[Hopsel]

Hi Gunnar!

Ich finde schwarz und grau aber ähnlicher als schwarz und rot.

Ich sehe, ihr versteht zumindest schon mal mein Problem. =)

Tatsächlich scheint dieses Problem gar nicht so trivial lösbar zu sein, wie ich hoffte.

Ich habe das Problem nun auf die Delta-E-Funktion des Color Measurement Committees heruntergebrochen.

Folgende PHP-Funktion gibt mir zu einer gegebenen Farbe im RGB-Format und einer Palette mit Farben ebenfalls im RGB-Format die Palettenfarbe aus, die am ehesten der gegegeben Farbe entspricht:

/*  
 * Die Funktion gibt den Array-Schlüssel der Farbe ($palette),  
 * die am ehesten der Farbe $givenColor entspricht.  
 *  
 * $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.  
 *  
 *  
 * Referenzen:  
 * 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' => '43aafd',  
                            'red' => 'fe6256',  
                            'green' => '64b949',  
                            'yellow' => 'fcf357',  
                            'black' => '656565',  
                            'white' => 'fdfdfd',  
                            'orange' => 'fea800',  
                            'purple' => '9773fe'  
                          )  
  )  
{  
  if(!function_exists('rgb2lab'))  
  {  
    function rgb2lab($rgb) {  
      $eps = 216/24389;  
      $k = 24389/27;  
  
      $xr = 0.964221;  // reference white D50  
      $yr = 1.0;  
      $zr = 0.825211;  
  
      // 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)  
      if ($rgb[0] <= 0.04045)  
        $rgb[0] = $rgb[0]/12.92;  
      else  
        $rgb[0] = pow(($rgb[0]+0.055)/1.055,2.4);  
  
      if ($rgb[1] <= 0.04045)  
        $rgb[1] = $rgb[1]/12.92;  
      else  
        $rgb[1] = pow(($rgb[1]+0.055)/1.055,2.4);  
  
      if ($rgb[2] <= 0.04045)  
        $rgb[2] = $rgb[2]/12.92;  
      else  
        $rgb[2] = 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];  
  
      // 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 = atan2($lab1[1],$lab1[2]);  
      $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);  
  
      $deltaE = 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)  
      );  
  
      return $deltaE;  
    } // function deltaE  
  }  
  
  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  
  }  
  
  // in die RGB-Werte zerlegen, wenn nicht schon geschehen  
  $givenColorRGB = is_array($givenColorRGB)?$givenColorRGB:str2rgb($givenColor);  
  $min = 0xffff;  
  $return = NULL;  
  
  foreach($palette as $key => $color)  
  {  
    // Farbe in die RGB-Werte zerlegen  
    $color = is_array($color)?$color:str2rgb($color);  
  
    if($min >= ($deltaE = deltaE(rgb2lab($color),rgb2lab($givenColorRGB))))  
    {  
      $min = $deltaE;  
      $return = $key;  
    }  
  }  
  
  return $return;  
}

Ein Aufruf mit der Farbe Gelb gibt mir erwartungsgemäß "yellow" zurück:
echo getNearestColor('#ffff00');

Die Palette kann man über den zweiten Parameter anpassen.
Der Vorgabewert basiert übrigens auf den Farben der Standardmarkierer, die von den statischen Karten von Googlemaps verwendet werden.

Geholfen haben mir folgende Internetseiten:
http://www.f4.fhtw-berlin.de/~barthel/ImageJ/ColorInspector/HTMLHilfe
(Die Funktion rgb2lab ist vom Java-Code dieser Seite einfach in PHP-Code üebrsetzt worden.)

http://www.brucelindbloom.com/index.html?Eqn_RGB_to_XYZ.html
http://www.brucelindbloom.com/index.html?Eqn_XYZ_to_Lab.html
http://www.brucelindbloom.com/index.html?Eqn_DeltaE_CMC.html

Ich hoffe, dieser Beitrag kann anderen Leuten später weiterhelfen und ein bisschen Arbeit ersparen. =)

MfG H☼psel