ImageResizer (Java)

[drunken monkey]

Ich habe gerade diesen Link entdeckt: Dynamic Resizing of images
Das ist irgendwie eine ziemlich coole Methode Bilder zu verkleinern/vergrößern. Ich bin mal gespannt, ob sich das durchsetzt

...

Hat mich wirklich beeindruckt, die Demo, daher habe ich mich selbst mal an einer Implementierung der Idee versucht und das Ergebnis will ich euch natürlich nicht vorenthalten:

Runterladen, ausprobieren, staunen!

Das "staunen" bezieht sich einerseits darauf, wie wenig man dem Bild (für die richtige Sorte von Bilde zumindest) tatsächlich die Verkleinerung anmerkt, aber viel eher darauf, wie sehr ich den augenscheinlichsten Kritikpunkt der Wortzähl-Applikation übernommen habe: ein mittelgroßes Bild um einen Pixel verschmälern braucht auf recht modernen PCs etwa eine Minute. Entweder haben die bei ihrer Demo ganz schön geWizardOfOzt oder eine ganze Serverfarm alleine für das Programm benutzt, oder ihr Algorithmus ist deutlich besser als meiner. Dass ich mal wieder bei Java geblieben bin dürfte die Sache auch nicht verbessert haben.
Also dynamisch ist das auf keinen Fall, aber die Ergebnisse können sich imo trotzdem sehen lassen.

Probiert's halt mal aus, und wer will, kann sich ja auch mal den Algorithmus zum Berechnen der unwichtigsten Linie (computeLeastImportantXYZalLine()) ansehen und zu optimieren versuchen, der frisst mit Abstand am meisten Rechenzeit. (Und darin wohl die Tatsache, dass andauernd Line-Objekte geklont werden müssen.) Ich bin allerdings echt auf nichts besseres gekommen, selbst der jetzige stellt schon die dritte Version dar, hinter der schon einiges an Überlegung steckt.
Die Option zur Vergrößerung des Bildes habe ich btw weggelassen, da sie a) das Ganze verkompliziert hätte und mir b) auch lang nicht so wirkungsvoll vorkommt wie die Verkleinerung.
Oh, und die GUI-Klasse zur Demonstration ist nicht kommentiert, da hat mich schon wieder langsam die Lust verlassen.


PS: Falls Interesse besteht könnte ich wahrscheinlich auch ein kurzes Tutorial über den allgemeinen Algorithmus schreiben. Das Blöde wäre halt, dass damit potenziell alle Lesenden zu hardwarefresserprogrammierenden Monstern erzogen würden. x__X

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

Eine grobe Erklärung, wie dein Algorithmus aussieht, wäre aber trotzdem ganz nett. Ich hab selber schon ein paar Ideen.

[FF]

ich probiers erst gar ned aus, mein rechner ist schon bei deinem knäckebrot ääh mnadelbrot dingen in die knie gegangen

der algorythmus würd mich aber auch intressieren, und auch eine performance optimierte version von dem dingen

[drunken monkey]

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.

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. ^^''

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. ^^''

[Jesus_666]

Dem Programm fehlt ein Statusbalken, der anzeigt, was es gerade tut. Dann würde man sich auch nicht wundern, warum das Bild nicht geladen wird...

[drunken monkey]

Dem Programm fehlt ein Statusbalken, der anzeigt, was es gerade tut. Dann würde man sich auch nicht wundern, warum das Bild nicht geladen wird...

...

Gute Idee!
Allerdings habe ich das gerade versucht, aber ziemliche Probleme gehabt, Swing dazu zu bringen, den angezeigten Text zu korregieren, bevor die Aktion abgeschlossen ist. Mittels repaint() kann man das nur in die EventQueue einreihen, aber die wird erst abgearbeitet, sobald nichts anderes mehr läuft. Und wenn man's mit update() macht (was man nicht soll), kommt plötzlich eine Exception beim Erstellen des Bilds.

Aber falls jemand weiß, wie man das machen könnte, kann's derjenige ja einbauen. Als Starthilfe kann man das hier verwenden, einfach alle Vorkommnisse von "// Repaint status label" ersetzen.

[Jesus_666]

Mein erster Gedanke wäre da Multithreading - du läßt das Bild in einem separaten Thread durchrechnen, der sich dann irgendwann zurückmeldet. Wenn du Anzeige- und Berechnungslogik voneinander trennst können sie sich nicht (ganz so leicht) gegenseitig auf die Füße treten.

[DFYX]

Schlagt mich, wenn es falsch ist, aber iirc legt Swing eh einen eigenen Thread für sich an. Daran kanns also eher nicht liegen.

[Jesus_666]

Schlagt mich, wenn es falsch ist, aber iirc legt Swing eh einen eigenen Thread für sich an. Daran kanns also eher nicht liegen.

...

Bringt aber nicht viel, wenn man seine interne Logik an Funktionen wie redraw() knüpft. Ich bin nicht der große Swing-Experte, aber an sich sollte es machbar sein, daß das Programm irgendeine Berechnung völlig unabhängig vom aktuellen Zustand des UI durchführt.

[drunken monkey]

Mein erster Gedanke wäre da Multithreading - du läßt das Bild in einem separaten Thread durchrechnen, der sich dann irgendwann zurückmeldet. Wenn du Anzeige- und Berechnungslogik voneinander trennst können sie sich nicht (ganz so leicht) gegenseitig auf die Füße treten.

...

OK, verstehe was du meinst. Vielleicht versuche ich das ja demnächst mal, müsste man aber einiges ändern...

Edit: Habe es jetzt probiert, aber das Problem bleibt bestehen. Anscheinend sind BufferedImages nicht thread-safe. :-/ Oder ich hab' was falsch gemacht, mit Threads arbeite ich zu selten. <__<
Jedenfalls kommt jetzt jedes Mal, wenn ich jetzt das Bild verkleinern will, eine Exception von Zeile 315/334/369/388, besagend, dass der image type 0 unbekannt ist. Wie man sich leicht an den entsprechenden Stellen vergewissern kann, kann das Problem kaum in normaler Weise entstehen. Entsteht anscheinend bloß, wenn man vom falschen Thread in Swingkomponenten rumpfuschen will.

Falls jemand meinen Versuch begutachten will: hier bitte.