Algorithmus für nächstgelegene Farbe

[Hopsel]

Hi alle!

Nehmen wir an ich habe eine Palette von mehreren Farben im RGB-Format.

Wie kann ich zu einer weiteren gegebenen Farbe herausfinden, welche Farbe aus der Palette am ehesten dieser gegebenen Farbe entspricht?

MfG H☼psel

[Der Martin]

Hallo,

Nehmen wir an ich habe eine Palette von mehreren Farben im RGB-Format.
Wie kann ich zu einer weiteren gegebenen Farbe herausfinden, welche Farbe aus der Palette am ehesten dieser gegebenen Farbe entspricht?

eigentlich müsste man bei einer solchen Aufgabenstellung die physiologische Farbwahrnehmung des menschlichen Auges berücksichtigen. Aber als stark vereinfachten Ansatz würde ich vorschlagen, den RGB-Farbraum tatsächlich als kartesisches Koordinatensystem zu betrachten, in dem sich der "Abstand" x zweier Farben über den Pythagoras ergibt:

x² = (R1-R2)² + (G1-G2)² + (B1-B2)²

In diesem Fall brauchst du aus einer gegebenen Menge an Farben "nur" diejenige auszuwählen, für die x am kleinsten ist.

So long,
 Martin

[Gunnar Bittersmann]

@@Der Martin:

nuqneH

Aber als stark vereinfachten Ansatz würde ich vorschlagen, den RGB-Farbraum tatsächlich als kartesisches Koordinatensystem zu betrachten, in dem sich der "Abstand" x zweier Farben über den Pythagoras ergibt:

Dieser Ansatz ist recht untauglich.

Bsp.: schwarz #000 = rgb(0, 0, 0) hätte zu grau #666 = rgb(102, 102, 102) einen Abstand von 102√3 ≈ 177, zu rot #900 = rgb(153, 0, 0) einen Abstand von 153.

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

Qapla'

[Tom]

Hello,

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

Dann frag da mal deinen Monochrom-Laserdrucker, was der dazu sagt :-P

Liebe Grüße aus dem schönen Oberharz

Tom vom Berg

[bleicher]

Grüße,

und mit mittelwerten gewichtete?

MFG
bleicher

[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

[Hopsel]

Hi Ingrid!

Eh ich´s vergesse...

Für Perl gibt es ein Implementation diverser hilfreicher Farbumwandlungsfunktionen:
Graphics::ColorObject

MfG H☼psel

[EisFuX]

(Hallo|Hi(ho)|Tag|Mahlzeit) Hopsel,

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:

Moment! Du wolltest eine PHP-Funktion?
Warum hast du das nicht gleich gesagt?

In PHP kämpft man doch nicht mit Algorithmen, sondern schaut, ob sich in der riesigen Menge an fertig eingebauten Funktionen was Passendes findet:

imageColorClosestHWB() berücksichtigt Farbton, Schwarz- und Weißwert einer Farbe.

imageColorClosest() ist die (wahrscheinlich weniger brauchbare) RGB-Variante.

Beide Funktionen benötigen eine Image-Resource. Die kann man sich speichersparend per imageCreate(1,1) erzeugen.
Die Zahl der Farben pro Palette ist zwar auf 256 beschränkt, dürfte aber für die meisten Anwendungen ausreichen.

MffG
EisFuX

[Hopsel]

Hi EisFuX!

Moment! Du wolltest eine PHP-Funktion?
Warum hast du das nicht gleich gesagt?

Eigentlich wollte ich einen Algorithmus bzw. Denkanstoß.

In PHP kämpft man doch nicht mit Algorithmen, sondern schaut, ob sich in der riesigen Menge an fertig eingebauten Funktionen was Passendes findet:

Tatsächlich kannte ich diese Funktionen noch nicht.

imageColorClosestHWB() berücksichtigt Farbton, Schwarz- und Weißwert einer Farbe.

Das tut sie aber leider nicht befriedigend. Meine Funktion gibt mir z. B. für den Rotwert #900 den mMn passenderen Farbton zurück.

Mir ist es wichtig, dass die Farbe weitestgehend erhalten bleibt. Das funktioniert mit meiner Funktion. Meistens... =)

Ich habe eine Vergleichsseite online gestellt, bei dem über den Get-Parameter eine Farbe übergeben werden kann: Vergleich zwischen getNearestColor() und imagecolorclosestHWB().

Wenn einmal die Funktion imageColorClosestLab() kommen sollte, bin ich gerne bereit, meine Funktion einzustampfen.

MfG H☼psel

[EisFuX]

(Hallo|Hi(ho)|Nabend) Hopsel,

»» imageColorClosestHWB() berücksichtigt Farbton, Schwarz- und Weißwert einer Farbe.
Das tut sie aber leider nicht befriedigend. Meine Funktion gibt mir z. B. für den Rotwert #900 den mMn passenderen Farbton zurück.

Mir ist es wichtig, dass die Farbe weitestgehend erhalten bleibt. Das funktioniert mit meiner Funktion. Meistens... =)

Ja, leuchtendes Rot berechnet die GD-Funktion anscheinend besser:
http://www.fuhrpark-software.de/spielwiese/color.php?color=ff0000

Ich habe eine Vergleichsseite online gestellt, bei dem über den Get-Parameter eine Farbe übergeben werden kann: Vergleich zwischen getNearestColor() und imagecolorclosestHWB().

Fehlte noch imageColorClosest(), oder liefert das so schlechte Ergebnisse?

Wenn einmal die Funktion imageColorClosestLab() kommen sollte, bin ich gerne bereit, meine Funktion einzustampfen.

Hehe, mir würde es schon genügen, wenn die GD-Funktionen unkastriert in PHP übernommen werden würden, oder wenn imageTTFBBox() richtig rechnen würde ... ;-)

MffG
EisFuX

[Længlich]

Da dika xalda hwa!

»» imageColorClosestHWB() berücksichtigt Farbton, Schwarz- und Weißwert einer Farbe.
Das tut sie aber leider nicht befriedigend. Meine Funktion gibt mir z. B. für den Rotwert #900 den mMn passenderen Farbton zurück.

Mir ist es wichtig, dass die Farbe weitestgehend erhalten bleibt. Das funktioniert mit meiner Funktion. Meistens... =)

Ein Gegenbeispiel: http://www.fuhrpark-software.de/spielwiese/color.php?color=97f
Da liegen IMHO beide ziemlich daneben (zumal die letzte der Palettenfarben wirklich sehr ähnlich ist). Vielleicht läßt sich die Formel ja irgendwie noch ein bißchen verfeinern.

Viele Grüße vom Længlich

[Hopsel]

Hi Længlich!

Danke für deine Anmerkung.

Ein Gegenbeispiel: http://www.fuhrpark-software.de/spielwiese/color.php?color=97f
Da liegen IMHO beide ziemlich daneben (zumal die letzte der Palettenfarben wirklich sehr ähnlich ist). Vielleicht läßt sich die Formel ja irgendwie noch ein bißchen verfeinern.

Ohje. Das ist ein Programmierfehler meinerseits. Ich verdoppele die Angaben im GET-Parameter anscheinend falsch. Mit 9977ff klappts.

MfG H☼psel

[Hopsel]

Hi Ingrid!

Ohje. Das ist ein Programmierfehler meinerseits. Ich verdoppele die Angaben im GET-Parameter anscheinend falsch.

Was red´ ich da. Ich verdoppele die Angaben gar nicht. Das Skript ist nur für sechsstellige hexadezimale RGB-Farbangaben gedacht.

Böser, böser Længlich! =)

MfG H☼psel

[Længlich]

Ciao!

»» Ohje. Das ist ein Programmierfehler meinerseits. Ich verdoppele die Angaben im GET-Parameter anscheinend falsch.
Was red´ ich da. Ich verdoppele die Angaben gar nicht. Das Skript ist nur für sechsstellige hexadezimale RGB-Farbangaben gedacht.

Ups, sorry. Deine frühere Aussage über den »Rotwert #900« (mit dem es zufälligerweise auch klappt) und die Tatsache, daß die Farbe auf der Seite wie gewünscht angezeigt wird, haben mich da wohl in die Irre geführt.

Böser, böser Længlich! =)

Jap, der böse User gibt oft unerwarteten Schrott ein! >:-)

Mit den sechsstelligen läuft Deine Funktion tatsächlich sehr gut, und auch erkennbar besser als die von PHP. Ich habe noch kein neues Gegenbeispiel. ;-)

Viele Grüße vom Længlich

[Hopsel]

Hi Længlich!

Böser, böser Længlich! =)
Jap, der böse User gibt oft unerwarteten Schrott ein! >:-)

... den ich jetzt aber abfange. =)
Zumindest sind drei- und sechsstellige Werte nun erlaubt. Bei anderen Werten ist die Ausgabe der Funktion(en) nicht definiert.

Mit den sechsstelligen läuft Deine Funktion tatsächlich sehr gut, und auch erkennbar besser als die von PHP. Ich habe noch kein neues Gegenbeispiel. ;-)

Das wirst du auch nicht finden. :-p

MfG H☼psel

[EisFuX]

(Hi|Nabend) Hopsel,

»» Mit den sechsstelligen läuft Deine Funktion tatsächlich sehr gut, und auch erkennbar besser als die von PHP. Ich habe noch kein neues Gegenbeispiel. ;-)
Das wirst du auch nicht finden. :-p

*räusper*
http://www.fuhrpark-software.de/spielwiese/color.php?color=5589ff

... oder bin ich farbenblind?

B.T.W.: Ich habe mich jetzt mehrmals dabei ertappt, wie ich die Zahl für den RGB-Wert mit vorangestelltem #-Zeichen eingeben wollte ... ;-)

MffG
EisFuX

--
[1] Es könnte sich auch um die K2000-Farbe "mauve" handeln.

[Hopsel]

Hi EisFuX!

»» Mit den sechsstelligen läuft Deine Funktion tatsächlich sehr gut, und auch erkennbar besser als die von PHP. Ich habe noch kein neues Gegenbeispiel. ;-)
Das wirst du auch nicht finden. :-p
*räusper*
http://www.fuhrpark-software.de/spielwiese/color.php?color=5589ff

... oder bin ich farbenblind?

Technisch gesehen ist das einwandfrei.
Ich habe mal eine euklidische Abstandsfunktion hinzugefügt, die allerdings ähnlich Werte liefert.
Das Problem was du ansprichst liegt einfach daran, dass das Palettenblau einen sehr hohen Grünanteil hat. Mit reineren Palettenfarben erzielst du subjektiv bessere Ergebnisse.

Du kannst ja gerne mal mit dem Code des Skripts experimentieren.

MfG H☼psel

[romy]

Hallo Længlich,hallo Hopsel,

Mit den sechsstelligen läuft Deine Funktion tatsächlich sehr gut, und auch erkennbar besser als die von PHP. Ich habe noch kein neues Gegenbeispiel. ;-)

Wie sieht es mit http://www.fuhrpark-software.de/spielwiese/color.php?color=99ffee aus. M.E. müsste blau ähnlicher sein, oder.

ciao
romy

[Hopsel]

Hi romy!

Wie sieht es mit http://www.fuhrpark-software.de/spielwiese/color.php?color=99ffee aus. M.E. müsste blau ähnlicher sein, oder.

Je länger ihr testet, desto unzufriedener werde ich. Bitte stellt sofort alle Testversuche ein. ;-)

Anscheinend ist die deltaE-Funktion doch nicht so gut geeignet. Genausowenig wie der euklidische Abstand der Lab-Werte.

Die deltaE-Funktion ist eigentlich zum bestimmen von minimalen Farbabweichungen - also zur Qualitätsmessung - gedacht. Werte über 5 sind dabei schon deutlich wahrnehmbar. In meinem Skript wird mit Werten weit über 300 gerechnet.

Ich werde mich mal noch ein wenig umschauen. Vielleicht finde ich ja was schönes.

MfG H☼psel

[romy]

Hallo Hopsel,

Je länger ihr testet, desto unzufriedener werde ich. Bitte stellt sofort alle Testversuche ein. ;-)

Ich bin mir nicht sicher, ob es wirklich schlecht ist, dass das Programm bei einem sehr hellen Blau, weiß erkennt? Unser Auge bleibt nun mal einfach bei der Farbe, das es erkennt. Kannst du mir in Worten kurz erklären, was dein Programm genau macht. Mir fehlt die Zeit und das Wissen um den Code richtig zu lesen.
Letztendlich ist es schwierig, denke ich, mit einem Algorithmus eine Wahrnehmung abzubilden, oder?

Ein weiters Beispiel: http://www.fuhrpark-software.de/spielwiese/color.php?color=667766 Du hast die Palette allerings angepasst, sehe ich.

Aber ich finde das sehr spannend, was du da machst.

ciao
romy

[Hopsel]

Hi Ingrid!

Die Zeile

$h1 = atan2($lab1[1],$lab1[2]);

muss wie folgt ersetzt werden:
$h1 = (((180000000/M_PI) * atan2($lab1[1],$lab1[2]) + 360000000) % 360000000)/1000000;

Grund: H1 muss im Gradmaß vorliegen, nicht im Bogenmaß.

Damit findet die Funktion auch die richtigen Farbwerte zuverlässiger.

MfG H☼psel

[Encoder]

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

Weiß nicht obs inzwischen schon durch die irgendwo gezeigte Funktion definiert ist. Falls nicht, könnte man ja auf das Modell Farbton-Sättigung-Helligkeit ausweichen und anhand ihm gewichten.
Eine Abweichung des Farbtons zählt dabei stärker als Ausschlusskriterium als eine Abweichung der Sättigung oder so irgendwie.

[Hopsel]

Hi Encoder!

Ich finde schwarz und grau aber ähnlicher als schwarz und rot.
Weiß nicht obs inzwischen schon durch die irgendwo gezeigte Funktion definiert ist.

Ja, ist mit drin. Es wird auf den Lab-Farbraum zurückgegriffen. Farben mit geringen a- und b-Anteilen können ziemlich sicher auf Graustufen abgebildet werden, vorausgesetzt, es befinden sich solche in der Palette.

MfG H☼psel

[Gunther]

Hi Hopsel!

Nehmen wir an ich habe eine Palette von mehreren Farben im RGB-Format.

Wie kann ich zu einer weiteren gegebenen Farbe herausfinden, welche Farbe aus der Palette am ehesten dieser gegebenen Farbe entspricht?

Vielleicht hilft dir die folgende Seite dabei, die für deine Zwecke "geeignetste" Methode zu finden?
http://www.brucelindbloom.com/index.html?Math.html

Gruß Gunther

[Hopsel]

Hi Gunther!

Vielleicht hilft dir die folgende Seite dabei, die für deine Zwecke "geeignetste" Methode zu finden?
http://www.brucelindbloom.com/index.html?Math.html

Ja, die Seite habe ich auch gefunden. Wirklich sehr hilfreich.
Die daraus entstandene Funktion hat aber richtig Mühe gemacht. =)

MfG H☼psel