Zitat von DFYX
Ich konnts mir bis jetzt leider nicht wirklich anschaun, weil mein Rechner schon daran scheitert, auch nur ein ausreichend großes Bild mit deinem Programm zu laden. So in Richtung Avatargröße geht, aber da kriegt man sehr schnell hässliche Ergebnisse.
...
Ahja, beim Laden muss er die unwichtigsten Linien natürlich genauso berechnen. Ich kann aber zumindest einen Vorher-Nachher-Vergleich zur Verfügung stellen:
Vorher -
Nachher
(Keine Ahnung, warum ich gerade das Bild nehme - wie ich's mich gefragt habe, war ich schon halb fertig. <__<')
Um das Ganze effizienter zu machen wäre es auch möglich, eine Funktion einzubauen, die das Bild gleich um eine vorgegebene Anzahl an Pixeln verkleinert, das wäre zumindest etwas schneller.
Zitat von Freierfall
ich probiers erst gar ned aus, mein rechner ist schon bei deinem knäckebrot ääh mnadelbrot dingen in die knie gegangen
...
Daei war das noch das Schnellste! o_O'
Irgendwie scheine ich echt ein Problem mit der Performance meiner Programme zu haben, aber vielleicht hilft meine diessemestrige Vorlesung "Effiziente Programme" ja was. ^^''
Zitat
der algorythmus würd mich aber auch intressieren, und auch eine performance optimierte version von dem dingen
...
Eine performanceoptimierte Version lasse ich jetzt mal als Fleißaufgabe im Raum stehen, da ich - zumindest atm - echt keine Idee habe, was man da noch drehen könnte. <__< Bzw. höchstens eine sehr vage Idee, nämlich die, dass man die geringgewichtigsten Wege nach dem Verkleinern irgendwie von denen vorm Verkleinern ableiten können müsste. Aber ganz so einfach klappt das leider nicht, da müsste man einige Überlegungen anstellen, damit das zumindest halbwegs optimal bleibt.
Aber der Algorithmus ist ebenso simpel wie hardwarefressend:
Wenn ein neues Bild geladen wird (und halt leider auch, wenn das Bild verkleinert wird, da sich dann halt doch einiges ändert) wird erstmal von jedem Pixel das "Gewicht" bestimmt, also wie wichtig er für das Bild ist (computeWeights(), welches für jeden Pixel computeWeight() aufruft). Dies passiert, in dem jeweils die Differenz zwischen den R-, G- und B-Anteilen zu allen vier umliegenden Pixeln addiert wird. Bei den Pixeln am Rand (die ja keine vier angrenzenden haben) wird zusätzlich noch eine Normierung durchgeführt.
Dann kommt das Hardwarefressende: sowohl für die horizontale Richtung, als auch für die vertikale, muss der Weg mit dem geringsten Gesamtgewicht gefunden werden (computeLeastImportant***alLine()). (Ich erklär's hier für den horizontalen Weg.) Um den geringgewichtigsten Weg zu ein und demselben Pixel nicht mehrmals zu berechnen, wird dabei jeweils eine Spalte (also gleiche x-Koordinaten) berechnet. Der geringgewichtigste Weg zu einem Pixel der aktuellen Spalte berechnen sich dann aus dem Gewicht des Wegs zu demjenigen der drei vorigen Pixel (also (x-1, y-1), (x-1, y) und (x-1, y+1)), dessen Weg das geringste Gewicht hat, plus dem Gewicht des aktuellen Pixels. Die Wege werden dabei als verlinkte Listen gespeichert, und da die Wege zu den beiden unteren der vorigen Pixel noch für den nächsten Pixel der Spalte gebraucht werden, muss diese Liste praktisch jedes Mal geklont werden (außer wenn der geringgewichtigste Weg der zum obersten vorigen Pixel (x-1, y-1) ist) - Performance ade!
Wenn man in der letzten Spalte angekommen ist wird dann der Weg mit dem geringsten Gewicht gespeichert. Damit wäre dann das Bild zumindest schon erfolgreich geladen (kein Wunder, wenn da viele PCs schon aufgeben).
Wenn dann tatsächlich das Bild um einen Pixel niedriger werden soll, wird dieser geringgewichtichtigste Weg Spalte für Spalte abgegangen und jeweils der Pixel rausgenommen, der in diesem Weg liegt. Da das Bild aber Array-mäßig gespeichert wird, damit auf die Pixel schnell per Index zugegriffen werden kann, dauert das auch nicht gerade kurz, da alle unter diesem Pixel liegenden Pixel nach oben verschoben werden müssen. Eine kleine Optimierung dabei ist, dass je nach der Position des ersten Pixels entweder die über oder die unter dem aktuellen Pixel liegenden Pixel verschoben werden, aber das bringt wohl nur in Extremfällen mehr als ein paar Prozent.
Das entstehende Bild wird dann vertikal um einen Pixel gekürzt und zurückgegeben, und natürlich die Gewichte und unwichtigsten Wege neu berechnet.
@ DFYX: Setz' deine Ideen halt auch mal um, dann können wir ja schauen, ob's bloß meine Unfähigkeit oder doch die Schwierigkeit des Problems war. ^^''
Zitieren