Hallo allerseits,

ich versuche ein kleines Programm zu schreiben, dass mit ein Bild aus mehreren kleinen Bildern zusammensetzt. Das funktioniert auch schon ziemlich gut, wie man am angehängten Balrog sehen kann.

Derzeit sieht es so aus, dass ich von allen kleinen Bildern die Durchshcnitts-RGB-Farbwerte abspeicher und mir dann das Bild rauspick, dessen RGB-Werte am besten zu den RGB-Werten des Teilausschnitts des großen Bildes passen.

An sich funktioniert das ja auch, nur hat mein Programm derzeit den großen Nachteil, dass es sehr langsam läuft, da es (wie bei einer eifnachen Liste) alle kleinen Bilder durchgehen muss, um das passendste Bild zu finden. Je größer die "Bilderdatenbank" ist, desto länger braucht das Programm.

In der Schule hatten wir mal Binärbäume durchgenommen, mit denen liese sich so ein Suchvorgang ja erheblich verbessern, nur hab ich das Problem, dass ich eben drei Werte habe, die ich vergleichen muss. Damit ich so einen Binärbaum kriegen kann, müsste ich also die rgb farben irgendwie in eine richtige Reihenfolge bringen, so dass ähnliche Farben nebeneinander liegen.

Frage nun: Wie kann ich das machen? (bzw. kann man doch einen Binärbaum machen mit drei zu vergleichenden werten?)

Hallo,

das geht am Problem vorbei: um Ähnlichkeit zu prüfen, braucht man eine Abstandsfunktion (Mathe Abteilung Topologie), aus einer einfachen Zahl für die Farbe lässt sich aber keine Ähnlichkeit von Farben herauslesen, egal wie diese Zahl gebildet wird (da die Helligkeit ja dazugehört, jedenfalls für deine Zwecke, braucht man mindestens 2 Zahlen).

Analog zum 3D-Raum wäre eine sinnvolle Abstandsformel D = Wurzel(R1^2 - R2^2) + Wurzel(G1^2 - G2^2) + Wurzel(B1^2 - B2^2) , eben der vektorielle Abstand. Um das Rechnen mit Quadraten und Wurzeln zu vermeiden, könnte man notfalls stark vereinfacht als Abstand nehmen MAX ( ABS(R1-R2), ABS(G1-G2), ABS(B1-B2) ), das ergibt auch noch ähnliche Farben.

Gruss Reinhard

Moderiert von Christian S.: Zitat des kompletten vorhergehenden Beitrags entfernt

@Reinhard: das weiß er selber, darum geht es ja

Hm... also ich würde einen Würfel probieren.
Also ein array[0..255,0..255,0.255] of Pointer. Diese Pointer zeigen auf deine Bilder. Das ganze wird am Anfang einmal per FillChar auf 0/nil gesetzt, dann die Bildverweise geschrieben. Jetzt könntest du ausgehend von der gesuchten Farbe die Umgebung der Koordinaten absuchen (3 for-Schleifen bis +/- Toleranz) bis du ein nicht-nil-Feld hast. Reduziert die Überprüfungen auf eine Hand voll, und wächst auch mit mehr Bildern nicht mehr...
Ist allerdings nur hypothetisch, ich versuch mich mal an nem PoC...

EDIT: vergiss es, das wären 65MB Pointer. Muss nicht sein

Wieviele Bilder hast du jetzt eigentlich?

Ich hab allerdings aus deinem anderen Post gesehen, dass du Canvas.Pixels benutzt. Nimm erstmal Scanline, das dürfte auch schon was bringen.

Mit Binary Trees könnte das eng werden. Die müssten dann genauso mehrdimensional werden, was dann genauso zu durchsuchen ist wie der Cube. Würde ich mal behaupten

Jede Farbe ist ja ein Punkt im RGB-Würfel. Aus deinen kleinen Bildern ermittelst du ja scheinbar am Anfang für dei DB einen RGB-Wert, also einen Punkt in diesem Würfel. Anschließend ermittelst du die Durchschnittsfarbe in deinem großen Bild für einen Teil und suchst den nächsten Punkt im Würfel, für den du ein Bild hast.

Im 2-dimensionalen macht man sowas sehr effizient mit Voronoi-Diagrammen, wobei ich auch da mit keiner direkten Implementierung dienen kann. Ob und wenn ja wie man das auf 3D ausweiten kann, weiß ich nicht. Könnte aber recht kompliziert werden

Eine Idee, weiß nicht ob's dir wirklich weiterhilft:

Speicher deine Farbwerte nicht als RGB, sondern als HSL, und teil dann die Suche in drei auf, d.h. suche im ersten Schritt nach kleinen Bildern mit benachbarten H-Werten, in diesen dann nach passenden S-Werten und nimm dann das mit dem nächsten L-Wert. Kann auch sein, dass eine andere Reihenfolge bessere Ergebnisse liefert. Jedenfalls kannst du dann vermutlich für die Einzelsuchen die Binärbäume anwenden.
Aber wie gesagt, is' mir grad so eingefallen, vielleicht ist's auch kompletter Mist.

Hmm, danke erstmal für die ganzen Antworten.

Das mit den drei Binärbäumen klappt denk ich nicht, da man ja den zweiten Binärbaum irgendwie erstellen muss, und da gehören ja nur die Sachen rein, die schon einen passenden R Wert haben. Diese Möglichkeit fällt also weg.

Was sich sehr interessant anhört ist der RGB-Würfel. Auf diese Vorstellung von RGB-Werten bin ich noch gar nicht gekommen. Problem hierbei (wenn man nicht die 255^3 Pointer haben will) wäre ja aber, den nächsten Punkt zu finden. Könnte man das ganze so optimieren, das man den RGB-Würfel in kleinere Würfel einteilt und dann nur die Abstände in dem kleinen Würfel überprüft? Wäre das sinnvoll oder überseh ich da was? Wie ich die Datenstruktur dann Aufbau, ist aber ne andere Frage


@Martok: Im Moment hab ich 670 Bilder und die Optimierung mit Scanline ist auch schon in Arbeit.

@Reinhard Kern: Das mit dem helligkeitswert ist mir auch schon aufgefallen, mein Balrog ist etwas dunkler als der Originale. Das Problem hab ich aber auf die Zukunft verschoben.

Jann1k hat folgendes geschrieben:

Hmm, danke erstmal für die ganzen Antworten. Das mit den drei Binärbäumen klappt denk ich nicht, da man ja den zweiten Binärbaum irgendwie erstellen muss, und da gehören ja nur die Sachen rein, die schon einen passenden R Wert haben. Diese Möglichkeit fällt also weg. ....

Hallo,

nicht dass das die Problematik grundsätzlich lösen würde, aber das 3D-Problem RGB lässt sich ausnahmsweise auf 2D reduzieren, weil ja alle Farbmodelle im Farbdreieck darstellbar sind - m.a.W. man kann mit der ins Farbdreieck transformierten Farbe rechnen und hat dann nur noch 2 Koordinaten. Immerhin.

Zum grundsätzlichen Problem: ich glaube (ist lange her, dass ich Topologie gemacht habe), dass es keine Abbildung von der Ebene (2D) auf eine Kurve (1D) gibt, bei der die Nachbarschaftsbeziehungen erhalten bleiben. Man kann zwar Kurven konstruieren, die die Ebene ausfüllen, aber dann sind auf der Ebene benachbarte Punkte auf der Kurve NICHT mehr (alle) benachbart. Eine solche Abbildung wäre aber Voraussetzung und Grundlage für eine einfache Binärsuche.

Ich lasse mich aber gern von einem besseren Mathematiker korrigieren - wer kennt sich da aus?

Andrerseits: du sprichst von 670 Bildern, also musst du im Brute Force Verfahren 670mal den Farbabstand zu deinem Pixel berechnen, das macht ein PC doch mit links. Ausserdem kannst du ja schon mal vorsortieren in rote Bilder, grüne Bilder usw.

Gruss Reinhard

Moderiert von Christian S.: Tripel-Post entfernt, der Editbutton ist eins weiter rechts ;-)

Hm jo. Da stimme ich Reinhard mal zu: 670 Bilder sind locker drin. Ich dachte schon du hast ein paar tausend

Du berechnest doch alle Farben nur einmal, und vergleichst dann nur noch. Am besten die Pixelfarbe noch in ne lokale Variable cachen (oder eben Scanline, dann brauchste das auch nicht mehr), und schon sinds nur noch 670 mal entfernungen berechnen. Lass die Wurzel noch weg, du vergleichst ja eh nur, und dann müsste das extrem schnell sein.

Oh. Moment. Du musst das ja für jedes Pixel machen.

Also anders. Beim Adventsrätsel hatte ich nachher mit einer vorberechneten Entfernungstabelle gearbeitet. Da standen die Entfernungen von jedem Punkt zu jedem Punkt drin (array[a,b]=distance(coord[a],coord[b])). Eventuell kriegt man sowas auch hin.

Oder du sortierst nach H,S,V (in der Wichtung), implementierst eine Skiplist/einen BTree auf H, und suchst dann das beste S für dieses H, und davon nochmal das beste S. Müsste auch gehen.

Wie immer: keine Garantie auf Speicherbedarf

Farbwürfel, jetzt Farbdreieck, langsam wirds richtig interessant, das Dreieck würd ich jetzt gerne realisieren. Versteh ich das richtig, dass jede Ecke des Dreiecks für eine Farbe (RGB) steht. Nur wie stellt man dann fest, wo eine Farbe (200,155,100) ist oder wie krieg ich aus den koordianten den punkt?

Jann1k hat folgendes geschrieben:

Farbwürfel, jetzt Farbdreieck, langsam wirds richtig interessant, das Dreieck würd ich jetzt gerne realisieren. Versteh ich das richtig, dass jede Ecke des Dreiecks für eine Farbe (RGB) steht. Nur wie stellt man dann fest, wo eine Farbe (200,155,100) ist oder wie krieg ich aus den koordianten den punkt?

Hallo Jann1k,

sorry, den Vorschlag Farbdreieck muss ich leider zurückziehen, bevor es jemand anders tut, ich hatte da ein Theorie-Defizit. Das Farbdreieck ist zwar grundlegend, weil es alle für den Menschen sichtbaren Farben erfasst und damit viel mehr als RGB, aber es enthält nicht die Helligkeit; die Farbe wird duch x und y im Farbdreieck bestimmt, aber die Helligkeit muss man sich dazu senkrecht vorstellen. Also doch 3D, es ist nichts gewonnen, denn für die Rasterung eines Bildes ist die Helligkeit wesentlich. Grundlagen gibts hier:

www.gm.fh-koeln.de/~.../Theorie/CIELab.html

Immerhin ist die Helligkeit vom Farbeindruck unabhängig, das böte folgenden Ansatzpunkt: sortiere die Bilder nach Helligkeit und suche die passende Farbe nur in der Umgebung der passenden Helligkeit, das reduziert die Anzahl der Berechnungen erheblich, vor allem bei vielen Bildern. Ich denke, je mehr Bilder du hast, desto eher findest du ein passendes, d.h. egal wie viele Bilder du hast, die Anzahl, die du für eine bestimmte Qualität durchsuchen musst, bleibt etwa konstant. Also suche das Bild mit der am besten passenden Helligkeit und untersuche in der nach Helligkeit sortierten Liste +- n Bilder. n bestimmt die Qualität, da wirst du finden, dass diese mit n immer langsamer zunimmt und dass sich also ab einem bestimmten n der Aufwand nicht mehr lohnt. Ich würde das n als Parameter eingeben.

Gruss Reinhard