Ähnlichste Farbe aus vielen finden
-
Moin,
ich habe viele Farben (RGB 24 bit) und möchte aus diesen diejenige finden, die einer bestimmten Farbe am ähnlichsten ist (und anschließend aus der Liste entfernen). Die Vergleichsfarbe ändert sich ständig und das ganze sollte möglichst schnell sein.
Im Moment sortiere ich die Farben anhand ihrer Helligkeit (eig. (R+G+B)/3) und suche dann beginnend bei der Helligkeit der Vergleichsfarbe links und rechts davon. Aufhören kann ich erst, wenn links und rechts garantiert keine ähnlicheren Farben als die ähnlichste bisher gefundene Farbe sein können.
Das ist aber leider recht langsam und die Laufzeit erhöht sich quadratisch mit der Anzahl der Farben (22s für 2.3 MPixel und ~15 min. für 11 MP).
Hat jemand eine schlauere Idee zu einer Datenstruktur, die mir eine schnelle Suche nach der ähnlichsten Farbe erlauben würde?
Ich habe schon einen ähnlichen Ansatz mit einer dreidimensionalen Struktur versucht, aber damit gewinnt man nicht viel... zwar habe ich nun weniger Farben in einer Subliste, aber dafür muss ich (links und rechts)³ suchen.Bitte nachfragen, falls mein Vorhaben noch nicht klargeworden ist.
-
Ich weiß zwar nicht, wie man dein Problem am besten löst, vor allem da die Ähnlichkeit zweier Farben wohl etwas subjektiv sein wird. Aber ich würde die Werte vorher nicht sortieren, es sei denn, das Vergleichen auf Ähnlichkeit wäre deutlich teurer als das Sortieren, was ich mir allerdings nur schwer vorstellen kann.
Wie machst du es denn bisher?
-
vielleicht hilft das: http://de.wikipedia.org/wiki/Delta_E
Das Problem an deiner Methode ist, dass rgb(255,255,0) und rgb(1,255,255) als ähnlich angesehen werden
-
Michael E. schrieb:
Ich weiß zwar nicht, wie man dein Problem am besten löst, vor allem da die Ähnlichkeit zweier Farben wohl etwas subjektiv sein wird. Aber ich würde die Werte vorher nicht sortieren, es sei denn, das Vergleichen auf Ähnlichkeit wäre deutlich teurer als das Sortieren, was ich mir allerdings nur schwer vorstellen kann.
Nein, das nicht. Aber ich muss noch erwähnen, dass sehr viele Suchvorgänge hintereinander durchgeführt werden (meist so viele, wie die Gesamtanzahl der Farben beträgt).
Vergleichsweise dazu geht das (einmalige) Sortieren recht schnell.Michael E. schrieb:
Wie machst du es denn bisher?
Die Ähnlichkeit (bzw. Differenz) zweier Farben bestimme ich mit |R1-R2| + |G1-G2| + |B1-B2|. Das ist als Ähnlichkeitskriterium auch durchaus brauchbar.
zwutz schrieb:
vielleicht hilft das: http://de.wikipedia.org/wiki/Delta_E
Diese Methode wäre auch denkbar, ist vermutlich aber wegen den Quadraten noch etwas rechenaufwändiger.
zwutz schrieb:
Das Problem an deiner Methode ist, dass rgb(255,255,0) und rgb(1,255,255) als ähnlich angesehen werden
Nicht direkt, da ich die nicht den Index der Farbe als Farbdifferenz verwende, sondern die obige Methode (|R1-R2|+...) verwende.
Aber ja, im Grunde liegt hier die Schwäche meines Ansatzes: rgb(255,255,0) und rgb(1,255,255) haben die gleiche Helligkeit und liegen deswegen in der sortierten Liste nah beieinander. Deswegen muss ich meist einen größeren Bereich der Liste durchsuchen, bis ich garantiert die ähnlichste Farbe gefunden habe.
-
Athar schrieb:
ich habe viele Farben (RGB 24 bit) und möchte aus diesen diejenige finden, die einer bestimmten Farbe am ähnlichsten ist (und anschließend aus der Liste entfernen). Die Vergleichsfarbe ändert sich ständig und das ganze sollte möglichst schnell sein.
Klingt nach dem "nearest neighbour"-problem.
Athar schrieb:
Hat jemand eine schlauere Idee zu einer Datenstruktur, die mir eine schnelle Suche nach der ähnlichsten Farbe erlauben würde?
Mit 'nem KD-Tree kannst du den "nearest neighbour" in logarithmischer Zeit finden. Dabei steigst Du den vielversprechendsten Pfad zuerst hinab und brichst ab, falls die Bounding-Box des aktuellen Knotens weiter vom Suchpunkt entfernt ist, als die bisher beste Lösung.
Das könnte man vielleicht noch mit einer Abwandlung Deiner Idee kombinieren. Die Farben -- als 3D Punktewolke aufgefasst -- kann man so rotieren, dass in der "X-Komponente" der Punkte die meiste Information drin steckt (muss nicht unbedingt die "Helligkeit" sein). Das hilft vielleicht auch nochmal, weil der Raum durch den KD-Baum ja in Achsen-parallelen Quadern partitioniert wird. Eine solche Abbildung ergibt sich aus den Eigenvektoren der Kovarianzmatrix der Rot/Grün/Blau-Komponenten, siehe "principal component analysis" bei Wikipedia.
SP
-
Sebastian Pizer schrieb:
Klingt nach dem "nearest neighbour"-problem.
Stimmt, das war das Stichwort, das mir gefehlt hat.
Sebastian Pizer schrieb:
Mit 'nem KD-Tree kannst du den "nearest neighbour" in logarithmischer Zeit finden. Dabei steigst Du den vielversprechendsten Pfad zuerst hinab und brichst ab, falls die Bounding-Box des aktuellen Knotens weiter vom Suchpunkt entfernt ist, als die bisher beste Lösung.
Das könnte man vielleicht noch mit einer Abwandlung Deiner Idee kombinieren. Die Farben -- als 3D Punktewolke aufgefasst -- kann man so rotieren, dass in der "X-Komponente" der Punkte die meiste Information drin steckt (muss nicht unbedingt die "Helligkeit" sein). Das hilft vielleicht auch nochmal, weil der Raum durch den KD-Baum ja in Achsen-parallelen Quadern partitioniert wird. Eine solche Abbildung ergibt sich aus den Eigenvektoren der Kovarianzmatrix der Rot/Grün/Blau-Komponenten, siehe "principal component analysis" bei Wikipedia.
Danke für den Tipp, das scheint ein vielversprechender Ansatz zu sein. Ich werde mich mal in Ruhe in KD-Trees einlesen.
-
Ich weiss ja nicht ob ich dein Problem korrekt verstanden habe, aber warum machst du nicht eine Bild-Farbraum-Transformation in einen geeigneteren Farbraum?
Transformier das ganze in den HSV Raum und gib dir für H und S kleine "deltas", alle H's die in dem Delta sind werden dann vereinigt...
http://de.wikipedia.org/wiki/HSV-Farbraum
Anderer Ansatz: du reduzierst die Farben, such mal nach Bildverarbeitungsalgos dafür, zB Floyd-Steinberg-Algorithmus
oder etwas was in Richtung Histogramm/Normalisation/Gleichverteilung geht ...
-
Konvertieren in HSV und dann nach H sortieren
-
i²e schrieb:
Konvertieren in HSV und dann nach H sortieren
Der HSV-Farbraum ist verlockend, aber dennoch nicht ganz korrekt
Die Aufgabe ist bei weitem nicht so trivial wie von vielen hier angenommen. Sie verlangt nach einem hohem Wissenstand, was die Wahrnehmung von Farben angeht. Die CIE untersuchte in dem vergangenen Jahrundert das ganze und definiert einen Standard (siehe DIN und ISO).
Mit den dort gesammelten Wissensstand lässt sich diese Aufgabe bewältigen.Am Ende ist es eine Frage der Genauigkeit. Die Abstände im sRGB-System geben nicht unbedingt den Unterschied der wahrgenommenen Farbe wieder. Gleiches gilt für HSV und Co.
CIE-Lab sollte hier abhilfe schaffen.
-
ok, einfach nach einem wert sortieren ist zu einfach und geht auch bei lab nicht.
-
am einfachsten wäre es wahrscheinlich die vergleichsfarbe im raum zu plazieren und dann die länge des vectors zu den anderen farben im bild zu brechenen. die rechenzeit sollte immerhin linear und nicht quadratisch sein.
-
kann den link zu den bilden nicht posten, das forum ist schon wieder im arsch
-
Kann sein, dass ich auf dem Schlauch stehe, aber hilft mir die Konvertierung nach HSV oder Lab bei der Suche wirklich weiter? Zwar ist in beiden Fällen die Helligkeit, nach der ich sortiere, bereits eine Farbkomponente.
Aber ist es letztendlich nicht dasselbe in Grün? Ich habe immer noch drei Komponenten, anhand der sich zwei Farben unterscheiden können. Vorher RGB, jetzt HSV oder Lab.
Und nachdem ich alle Farben mit gleichem L- bzw. V-Wert wie die gesuchte Farbe durchgegangen bin, muss ich immer noch Farben mit ähnlicher Helligkeit durchsuchen. Könnte ja sein, dass ich dort eine Farbe mit gleichem Farbton und geringem Helligkeitsunterschied finde und dass ich bisher unter den Farben mit gleicher Helligkeit nur eine mit großem Farbtonunterschied gefunden habe.i²e schrieb:
am einfachsten wäre es wahrscheinlich die vergleichsfarbe im raum zu plazieren und dann die länge des vectors zu den anderen farben im bild zu brechenen. die rechenzeit sollte immerhin linear und nicht quadratisch sein.
Die Suche an sich ist ja bereits linear. Die 22 Sekunden werden für 2.3 Millionen Suchvorgänge in jeweils 2.3-i Millionen Farben benötigt (-i weil die gefundene Farbe danach aus der Liste entfernt wird).
-
HSV hat gegenüber RGB den Vorteil das nach FARBE und nicht nach HELLIGKEIT sortiert ist.
Damit musst du einen wesentlich kleineren Bereich der Liste absuchen:Sortierst du nach Helligkeit liegen
(255,255,1) (255,1,255) (1,255,255)(128,255,129) (170,100,141)
alle nebeneinander in der Liste ... sind aber völlig verschiedene Farben.Ein Beispiel (GIMP sei dank für die Wertekonversion):
HSV RGB PERS.FARBEINDRUCK (R+B+G)/3 <- Division überflüssig Sortierung nach (R+B+G)/3 238,61,50 50,53,128 dunkelblaugrau 116 2,61,50 128,53,50 bräunlichrot 116 118,61,50 53,128,50 dunkelgrün 116 240,61,100 100,100,255 mittelhellblau 151 120,61,100 100,255,100 leuchtgrün 151 0,61,100 255,100,100 hellrot 151 Sortierung nach HSV 2,61,50 128,53,50 bräunlichrot 116 0,61,100 255,100,100 hellrot 151 118,61,50 53,128,50 dunkelgrün 116 120,61,100 100,255,100 leuchtgrün 151 238,61,50 50,53,128 dunkelblaugrau 116 240,61,100 100,100,255 mittelhellblau 151als Sortierindex kannst du einfach die zusammengesetzte hex des Farbwertes nehmen. CIE LAB ist besser was den "subjektiven" Farbeindruck angeht, aber HSV sollte um Längen besser sein als Helligkeitsbasiert
Kombinierst du das mit kdTree könnte das flott werden.
-
padreigh schrieb:
HSV hat gegenüber RGB den Vorteil das nach FARBE und nicht nach HELLIGKEIT sortiert ist.
Es sind immer noch drei Komponenten. Das Konvertieren in andere Farbräume mag Sinn machen oder auch nicht. Das kommt auf die Anwendung an. Im Endeffekt hat man irgend eine 3D-Punktewolke und man will möglichst schnell einen Punkt aus der Wolke finden, der einem anderen gegebenen Punkt -- nach einer zu definierenden Metrik -- am nächsten ist. Mit einer Datenstruktur wie dem K-D-Baum ist das möglich.
Bzgl Dithering habe ich da schon einiges ausprobiert. Bei gegebener Farbpalette und 24Bit Farben je Pixel eines Bilds habe ich für jeden Pixel jeweils den nächsten Nachbar (in der Farbpalette) im YUV-Farbraum mit einer gewichteten 2-Norm als Metrik gesucht (Helligkeit höher gewichtet als Chrominanz) und das mit Floyd-Steinberg-Dithering im linearen RGB-Farbraum kombiniert. Das sah in den meisten Fällen sehr gut aus und weniger "krisselig" als bei den Standardverfahren. Die Gewichtung führte dazu, dass "Mischfarben" nicht aus Hell/Dunkel sondern eher aus komplementären Farbtönen dargestellt wurden. Das ist von Vorteil, da unser Auge eine höhere räumliche Auflösung beim Helligkeitsanteil und eine niedrigere räumliche Auflösung beim Chrominanzanteil hat.
-
Also, du hast doch ein Bild und willst da drin alle Pixel finden die eine ähnliche Farbe wie eine Vergleichsfarbe haben. Richtig?
HSV und LAB sehen in Raum so aus:
Link geht wieder nicht
Ähnliche Farben haben einen kleinen Abstand im Raum. Du musst also nur den Abstand von allen Farben zu der Vergleichsfarbe berechnen und dir nur die kleinsten merken.
-
-
Mithilfe der psadbw-Instruktion habe ich die bisherige Implementation auf 7s für 2.3 Mio. Farben und 222s für 11 Mio. verbessern können. 4s und 83s wenn ich den Farbraum auf 21 Bit verkleinere.
Für die Implementation eines passenden Baumes habe ich STANN ausprobiert, damit liegen die Zeiten zweier Testprogramme mit jew. 2.3/11 Mio Farben bei 1.7s und 10s. Das ist sehr gut, aber darin enthalten ist noch nicht das Entfernen der gefundenen Farbe nach jeder Suche, denn das scheint STANN nicht zu unterstützen.
Da muss ich weiter nach einer Alternative suchen oder notfalls das ganze selbst implementieren.i²e schrieb:
Also, du hast doch ein Bild und willst da drin alle Pixel finden die eine ähnliche Farbe wie eine Vergleichsfarbe haben. Richtig?
Ja, aber eigentlich nur eine Farbe pro Suchvorgang. Beim nächsten habe ich bereits wieder eine ganz andere Vergleichsfarbe.
i²e schrieb:
Ähnliche Farben haben einen kleinen Abstand im Raum. Du musst also nur den Abstand von allen Farben zu der Vergleichsfarbe berechnen und dir nur die kleinsten merken.
Ja, schon. Das gilt aber auch im RGB-Farbraum. Die Abstände im Lab-Farbraum entsprechen zwar eher der menschlichen Farbähnlichkeitswahrnehmung, aber im RGB-Raum klappt das prinzipiell auch schon recht gut.
Das Problem ist, wenn ich mehrere Millionen Mal für jeweils mehrere Millionen Farbpaare den Abstand im Raum berechnen muss, wird's zeitlich eng. Im Grunde mache ich das bereits, nur dass ich nicht jedes Mal alle Farben betrachte.
-
Nur eine vage Idee. Keine Ahnung, ob sie klappen wird.
Wenn man in jeder Farbe die Zeiger auf die Nachbarfarben speichert, müßte man im 3D-Raum von einer beliebigen Startfarbe aus relativ geradlinig zur besten Farbe laufen können. Gibt es überhaupt lokale Täler? Und man ist sicher, daß man angekommen ist, wenn die Farbe besser ist alle alle Nachbarn. Angenommen, die 11Mio Farben wären gleichverteilt, wäre das ein Würfel von 222Farben Kantenlänge.
Also quasi der schwarze Graph auf http://de.wikipedia.org/w/index.php?title=Datei:Thiessen-Polygon.svg&filetimestamp=20091115230256 nur in 3D.
Angenommen, man kann in so einem Graphen einigermaßen performant suchen, wäre das auch der Ansatzpunkt, um ihn schnell zu bauen. Man fängt mit 2 Farben an. Dann fügt man ein, indem man für die neue Farbe die beste Farbe sucht und die neue wird zwischen der besten und deren Nachbarn eingekettet.
Und falls dann noch funktioniert, eine Farbe herauszuwerfen...
Wahrscheinlich ist ein Baum noch viel schneller.
-
padreigh schrieb:
HSV hat gegenüber RGB den Vorteil das nach FARBE und nicht nach HELLIGKEIT sortiert ist.
Damit musst du einen wesentlich kleineren Bereich der Liste absuchen:Sortierst du nach Helligkeit liegen
(255,255,1) (255,1,255) (1,255,255)(128,255,129) (170,100,141)
alle nebeneinander in der Liste ... sind aber völlig verschiedene Farben.Ein Beispiel (GIMP sei dank für die Wertekonversion):
HSV RGB PERS.FARBEINDRUCK (R+B+G)/3 <- Division überflüssig Sortierung nach (R+B+G)/3 238,61,50 50,53,128 dunkelblaugrau 116 2,61,50 128,53,50 bräunlichrot 116 118,61,50 53,128,50 dunkelgrün 116 240,61,100 100,100,255 mittelhellblau 151 120,61,100 100,255,100 leuchtgrün 151 0,61,100 255,100,100 hellrot 151 Sortierung nach HSV 2,61,50 128,53,50 bräunlichrot 116 0,61,100 255,100,100 hellrot 151 118,61,50 53,128,50 dunkelgrün 116 120,61,100 100,255,100 leuchtgrün 151 238,61,50 50,53,128 dunkelblaugrau 116 240,61,100 100,100,255 mittelhellblau 151als Sortierindex kannst du einfach die zusammengesetzte hex des Farbwertes nehmen. CIE LAB ist besser was den "subjektiven" Farbeindruck angeht, aber HSV sollte um Längen besser sein als Helligkeitsbasiert
Kombinierst du das mit kdTree könnte das flott werden.Warum vergleichst du im RGB-Farbraum auch die Helligkeit? Das geht im HSV Farbraum natürlich einfacher, weil du nur die Differenz einer Komponente brauchst. Das ist aber nicht gefragt.
Du musst die Unterschiede jeder einzelnen Farbkomponente aufaddieren, dann klappt's auch mit dem Nachbarn:
abs(Farbe1.R - Farbe2.R) + abs(Farbe1.G - Farbe2.G) + abs(Farbe1.B - Farbe2.B)
