Ähnlichste Farbe aus vielen finden

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