Bitmap auf 8bit mittels vorhandener Palette

[Brainstalker]

Hallo,

ich habe eine Serie von Bitmaps, die alle die gleiche Palette benutzen, also 256 Farben. Jetzt möchte ich ein Bitmap hinzufügen, d.h. die Farben des Bitmaps sollen an die vorhandene Palette angepasst werden. Die Bitmaps die hinzugefügt werden, können jede mögliche Farbtiefe haben.
Mein erster Gedanke war, jedes Pixel des neuen Bitmaps mit den Farben der Palette zu vergleichen und mir dann ein Array des Bitmaps mit den Indizes anzulegen. Das funktioniert auch wunderbar, aber wird die Farbe in der Palette nicht gefunden werden mir die Bereiche weiß (meine default Farbe) angezeigt. Ist ja auch logisch bei einem Bitmap mit 24bit werden eher wenig Farben in der Palette gefunden.

Hat jemand einen Tipp für mich, wie ich in der Palette die Farbe finde, welche am nähsten an der zu suchenden Pixelfarbe liegt? Ich weiß wie ich Bitmaps in der Farbe reduzieren und eine Palette anlegen kann, aber eben nicht wie ich mit einer vorhandenen Palette vorgehe.

Gruß

[Medium]

Das einfachste ist es, Farben als 3-dimensionalen Vektor aufzufassen. Die kleinste Länge der Differenz zweier Farben gibt dann die am nächsten liegende an. Dann muss man sich nur noch für ein Farbmodell entscheiden, in dem dies die besten Ergebnisse liefert. RGB ist da meine ich schon garnicht SO schlecht, ich könnte mir aber auch gut HSV bzw. HSL für diesen Zweck vorstellen.

Edit: Ich glaube der L*a*b*-Farbraum wäre geradezu ideal dafür, allerdings auch nicht mehr ganz so trivial.
Edit2: Auch dieser Artikel dürfte für dich recht interessant sein.

[Brainstalker]

Ok Vektorrechnung sollte nicht das Problem sein. Hatte in der Uni erst letztes Semester Lineare Algebra.
Wie mache ich das am besten, sollte ich da dann von Nullvektor aus gehen und dann die differenz der beiden Vektoren ausrechnen? Und kann ich da einfach übers Skalarprodukt gehen?

Mir reicht auf jeden Fall erst mal der RGB Farbraum. Sicherlich wäre es besser über HSL zu gehen, da man dort die Helligkeit einbeziehen kann, aber mir erstmal nicht so wichtig. Werd ich vielleicht als zweite Implementation später hinzufügen. Dann könnte man auch beide vergleichen.
Der L*a*b*-Farbraum hört sich sehr interessant an. Den werd ich zwar hierfür nicht einsetzen, aber ich glaub da werde ich mich auf jeden Fall mal einarbeiten. Für andere Projekte.


Ich hab leider für die nächste Zeit kein Delphi, und mache das alles erstmal theoretisch. Meine erste Überlegung sieht folgendermaßen aus, wie gesagt nicht getestet.

Delphi-Quellcode:

TRGB = record
  r: byte;
  g: byte;
  b: byte;
end;

TPalette = array[0..255] of TRGB;



function Skalar(const aVector: TRGB): integer;
begin
  result := aVector.r * aVector.r
         + aVector.g * aVector.g
         + aVector.b * aVector.b;
end;


function GetNearestColor(const aColor: TRGB): integer;
var
   ind, smallest, diff: integer;
begin
  ind := 0;
  smallest := High(Palette);
  
  for i := 0 to High(Palette) do         // Palette mit 256 Einträgen
  begin
    diff := Skalar(aColor) - Skalar(Palette[i]);
    if diff < 0 then diff := diff * (-1);
    
    if diff < smallest then
    begin
      ind := i;
      smallest := diff;
    end;
  end;
  
  result := ind;
end;

[Medium]

Das Skalarprodukt kommt mit rein beim Quadrieren, die Differenz der Skalarprodukte hat aber nicht wirklich viel aussagekraft. (255, 0, 0) würde dann zum Beispiel identisch mit (0, 0, 255) sein.
In Pseudocode eher so:

Delphi-Quellcode:

type
  TRGBColor = class
  public
    r, g, b: Integer;
    constructor Create(ar, ag, ab: Integer);
  end;
var
  color1, color2, colorDiff: TRGBColor;
  distance: Double;
begin
  colorDiff := TRGBColor.Create(color2.r-color1.r, color2.g-color1.g, color2.b-color1.b);
  distance := sqrt(colorDiff.r*colorDiff.r + colorDiff.g*colorDiff.g + colorDiff.b*colorDiff.b);
.
.
end;

Geometrisch interpretiert hast du einen Farbwürfel, und ermittelst mit der Differenz den Vektor von color1 zu color2. Je kürzer der ist, desto - wortwörtlich - näher sind die Farben beieinander.

[Brainstalker]

Ja logo... Macht natürlich wenig Sinn. Hab auch gerade gemerkt das ich völligen murks geschrieben hab. Natürlich müssen die Vektoren erst von einander subtrahiert werden und dann der Betrag des resultierenden Vektors gebildet werden. Also quasi die Wurzel aus dem Skalar des Resultierenden.
Kaum das Semester hinter mir, schon bring ich alles durcheinander.

Für das HSV Modell müsste man aber andere Überlegungen anstellen, denn das Modell bildet ja kein Würfel.
Mal sehen, werd ich mir mal morgen Gedanken machen.

[Medium]

Zitat von Brainstalker:

Für das HSV Modell müsste man aber andere Überlegungen anstellen, denn das Modell bildet ja kein Würfel.

Stimmt, da müsste man sich für Hue etwas ausdenken, da dieser Wert ja ein Winkel ist. Für Sättigung und Helligkeit müsste man mit dem 2D-Abstand ganz gut hin kommen, beim Winkel theoretisch auch, nur dass man die 360°-0°-Grenze irgendwie verhackstücken müsste.
Oder hmm, das ginge doch fast einfach:

Delphi-Quellcode:

type 
  THSVColor = class 
  public 
    h, s, v: Integer; 
    constructor Create(ah, as, av: Integer); 
  end; 
var 
  color1, color2, colorDiff: TRGBColor; 
  distance: Double; 
begin 
  colorDiff := TRGBColor.Create(color2.h-color1.h, color2.s-color1.s, color2.v-color1.v); 
  if colorDiff.h < 0 then
    colorDiff.h := (2*pi)-colorDiff.h;
  distance := sqrt(colorDiff.h*colorDiff.h + colorDiff.s*colorDiff.s + colorDiff.v*colorDiff.v); 
. 
. 
end;

Allerdings hat man letztlich dann keinen "kartesischen" Abstand mehr, und es könnte evtl. Sinn machen die einzelnen Komponenten zueinander zu gewichten. So dass Sättigung evtl. nur zur Hälfte eingeht, Hue aber 1,5x so stark. Fertig bestimmte optimale Werte gibt's da glaub ich nicht, aber mit ein wenig Rumprobieren sollte sich was überzeugendes anstellen lassen.

[Brainstalker]

Ich hab heute auch mal ein bisschen drüber nachgedacht. Und mit ein bisschen Googeln hab ich auch ne Seite gefunden wo das RGB System als Würfel und das HSV als Kegel dargestellt war. Die Farbsättigung und der Farbton sind auf dem Kreis aufgetragen. Da könnte man ja theoretisch mit 2D Vektoren arbeiten. Hab noch ein Bild angehängt, wo ich mal meine Gedanken aufgeschrieben habe. Ob das dann alles richtig ist, sei mal dahin gestellt.

Wenn wir den Einheitskreis betrachten, müsste ja folgendes gelten:

x := [0..1] Sättigung
y := [0°..360°) Farbton

Farben f1, f2 = [x*cosy, x*siny] <---- Vektor

|f1-f2| = sqrt(fx²+fy²)

Fragt sich dann nur wie man den Value Wert mit einbringt. Habs übers Dreieck versucht (siehe Zeichnung), aber naja bin da noch nicht so weit gekommen. Vielleicht ist das ja auch ein völlig falscher Ansatz.

[himitsu]

Man könnte auch mal einen einfachen Weg versuchen.

- Man erstelle das 8-Bit-Bitmap, samt der Farbtabelle
- und kopiere (.Draw) einfach das gewünschte Bild da hinein.

[Brainstalker]

Ok hab nicht dazu gesagt, das ich kein Bitmap benutze, mache das sozusagen on the fly mit den "raw" Daten. Aber ich könnte ja auch mal schauen wie das mit der Geschwindigkeit aussieht, wenn ich es mit einem Bitmap mache.

Ich hätte also auch gern einen Weg die Farbe zu finden ohne ein Bitmap zu benutzen. Kann ich später dann auch für andere Dinge gebrauchen. Vielleicht kannst du ja aber auch ein bisschen Beispielcode posten, für andere die sich vielleicht für das Thema interessieren. Ich hab ja im Moment kein Delphi, kann also kein produktiven Code beisteuern.

Aber schonmal soweit vielen Dank an euch beide für die Hilfe.

[Medium]

Die wirklich wesentliche Frage, die es zu aller erst zu klären gälte, ist ja: Ab welchem Helligkeitsunterschied ist der wahrgenommene Fehler schlimmer als ein alternativer Farbunterschied, bzw. alle 3 Kombis aus H, S und V zueinander betrachtet.
Ich könnte mir schon vorstellen, dass eine einfache Vektorlänge auch im Kegel noch sinnvolle Ergebnisse liefert. Also H und S als Polarkoordinaten interpretieren, in Kartesische umrechnen, und dann wie auch bei RGB die Differenz bilden und Länge als Maß nehmen. Falls dabei zu oft arg falsche Farben, Helligkeiten oder Sättigungen auftreten, die entsprechende Komponente mit einem Multiplikator versehen. Dann ist das zwar keine geometrisch einwandfreie Sache mehr, aber führt ggf. zu gefälligeren Bildern. Das Ziel ist das Ziel