Ähnlichste Farbe aus vielen finden

Sebastian Pizer

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

Athar

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.

padreigh

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

Siassei

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

Athar

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).

padreigh

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      151

als 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.

Sebastian Pizer

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.

Google: hsv farbraum
Google: lab farbraum

Athar

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.

volkard

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      151
als 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)

Athar schrieb:

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.

Ich glaub ich hab nicht verstanden was du willst. Du willst zu jedem Pxiel die ähnlichen finden und nicht nur die ähnlichen zu einer Farbe?

Siassei

Servus,

willst du evtl. zwei Bilder auf ähnlichkeit prüfen? Und noch mals, vergiss RGB und HSV. Für einen Vergleich mit aktzeptablen Ergebnisse musst du zu Lab, LCh oder einen vergleichbaren Farbsystem gehen.

Zu deinen Laufzeitproblemen:
Falls du keinen Algorithmus findest (welche Sprache benutzt du eigentlich?) der die vorgegebenen Zeit einhält, kannst du dir ja gedanken um die parallele Ausführung machen. Wenn ich dich richtig verstanden habe, benutzt du ein Bild und suchst dort x-mal nach einer Farbe.
Derartige Aufgaben lassen sich sehr schön mit OpenCL erledigen. Je nach Rechner kannst du dann das ganze auf der CPU oder GraKa laufen lassen. Auf beiden wirst du eine Beschleunigung erfahren, sofern du mit C, C++, Java, .NET oder ähnliches programmierst.
Ob OpenCL bereits mit Fortran-Operationen mithalten kann, weiß ich leider nicht. Ich besitze keinen High-End Fortran-Compiler. Die sind echt teuer und ihr Geld wert

Gruß,
Thomas