Dithering mit PHP

1258040176Mein Cousin hat im Studium ein Java-Programm geschrieben, das beliebige Bilder auf 2 Farben reduziert: Weiß und Schwarz. Ich weiß, dass das eigentlich keine Farben sind, aber was solls…

Ich habe mir den Spaß gemacht und diesen Algorithmus („Floyd-Steinberg-Dithering“) in PHP implementiert. Dass die Ausführung mit PHP total langsam ist, ist klar. Aber darum ging es mir auch gar nicht.

Was ist Dithering?

Dithering beschreibt den Vorgang, bei dem ein Bild auf wenige Farben (hier weiß und schwarz) reduziert wird. Der Inhalt des Bildes ist nach dem Dithering immer noch erkennbar. Genau hier liegt die Schwierigkeit! Hier mal 2 Beispielbilder für euch:

(vorher)

frau
(nachher)

1258039329

Ich finde es sehr erstaunlich, wie man mit 2 Farben ein Bild doch so genau darstellen kann. Das ganze geht auch mit Rot und Grün:

1258040176

Man könnte hier eigentlich alle möglichen Farbkombinationen benutzen. Was ich auch gemacht habe, war 3 oder 4 Farben zu benutzen. Allerdings wird das Bild dann immer undeutlicher.

Der Algorithmus

Der Algorithmus sieht in PHP so aus:

 $image = imagecreatefromstring(file_get_contents($_FILES["picture"]["tmp_name"]));

 $info = getimagesize($_FILES["picture"]["tmp_name"]);

 $height = $info[1];
 $width  = $info[0];

 $white = imagecolorallocate($image, 255, 255, 255);
 $black = imagecolorallocate($image, 0, 0, 0);

 $red   = imagecolorallocate($image, 255, 0, 0);
 $green = imagecolorallocate($image, 0, 255, 0);

 for ($j = 0; $j < $height; $j++)
 {
 for ($i = 0; $i < $width; $i++)
 {
 // aktuellen Farbwert des Pixels speichern
 $prevVal = imagecolorat($image, $i, $j);

 // prüfen, ob Pixel auf weiß oder schwarz gesetzt wird
 if($prevVal < ($black + $white / 2))
 {
 imagesetpixel($image, $i, $j, $black);  //dunkler
 }
 else
 {
 imagesetpixel($image, $i, $j, $white);   //heller
 }

 // Fehlerberechnung
 $error = $prevVal - imagecolorat($image, $i, $j);

 // Fehlerpropagation und
 // Abfangen der letzten Zeile und Spalte
 if($i < $width - 1)
 {
 imagesetpixel($image, $i + 1, $j, imagecolorat($image, $i+1, $j) + (7 * $error / 16));
 }

 if($j < $height - 1)
 {
 imagesetpixel($image,$i, $j + 1, imagecolorat($image, $i, $j+1) + (5 * $error / 16));
 }

 if($i < $width - 1 && $j < $height -1)
 {
 imagesetpixel($image,$i + 1, $j + 1, imagecolorat($image, $i+1, $j+1) + (1 * $error / 16));
 }

 if($i > 0 && $j < $height - 1)
 {
 imagesetpixel($image,$i - 1, $j + 1, imagecolorat($image, $i-1, $j+1) + (3 * $error / 16));
 }
 }
 }

 header("Content-Type: image/jpeg");
 imagejpeg($image);

Dem aufmerksamen Programmierer fällt hier auf, dass ich einfach ungeprüft alle Dateien verarbeite. Es könnte sich genausogut um Schadsoftware handeln. Da ich dieses Skript nur zum Testen benutzt habe, habe ich auf sämtliche Sicherheitsvorkehrungen verzichetet. Im produktiven Einsatz muss sowas natürlich beachtet werden!

Funktionsweise

$white = imagecolorallocate($image, 255, 255, 255);
$black = imagecolorallocate($image, 0, 0, 0);

Als erstes werden die Farben Weiß und Schwarz „angelegt“.

for ($j = 0; $j < $height; $j++)
 {
 for ($i = 0; $i < $width; $i++)
 {
 // aktuellen Farbwert des Pixels speichern
 $prevVal = imagecolorat($image, $i, $j);

 // prüfen, ob Pixel auf weiß oder schwarz gesetzt wird
 if($prevVal < ($black + $white / 2))
 {
 imagesetpixel($image, $i, $j, $black);  //dunkler
 }
 else
 {
 imagesetpixel($image, $i, $j, $white);   //heller
 }

Danach wird das Bild in 2 verschachtelten for-Schleifen zeilenweiße durchlaufen. Bei jedem Pixel wird geprüft, ob er heller oder dunkler als „die Mitte zw. Weiß und Schwarz“ ist. Ist er Dunkler, wird der Pixel schwarz gefärbt. Andernfalls wird er weiß.

// Fehlerberechnung
$error = $prevVal - imagecolorat($image, $i, $j);

Jetzt wird die Abweichung von der Originalfarbe zur neuen Farbe (weiß/schwarz) berechnet.

// Fehlerpropagation und
 // Abfangen der letzten Zeile und Spalte
 if($i < $width - 1)
 {
 imagesetpixel($image, $i + 1, $j, imagecolorat($image, $i+1, $j) + (7 * $error / 16));
 }

 if($j < $height - 1)
 {
 imagesetpixel($image,$i, $j + 1, imagecolorat($image, $i, $j+1) + (5 * $error / 16));
 }

 if($i < $width - 1 && $j < $height -1)
 {
 imagesetpixel($image,$i + 1, $j + 1, imagecolorat($image, $i+1, $j+1) + (1 * $error / 16));
 }

 if($i > 0 && $j < $height - 1)
 {
 imagesetpixel($image,$i - 1, $j + 1, imagecolorat($image, $i-1, $j+1) + (3 * $error / 16));
 }

Um das Bild möglichst realistisch erscheinen zu lassen, wird diese Abweichung (auch Fehler genannt) an die umliegenden Pixel weitergegeben. Sie wird aber nicht 1:1 weitergegeben, sondern anteilig. Das heißt, dass nur ein Bruchteil der Abweichung auf die Originalfarbe der umliegenden Pixel aufaddiert wird. Diese Anteile hat der Erfinder des Dithering-Algorithmus selbst ermittelt und als die besten empfunden.

header(„Content-Type: image/jpeg“);
imagejpeg($image);

Wenn alle Pixel durchlaufen sind, wird das Bild nur noch als JPG ausgegeben.

Der Algorithmus ist also gar nicht so kompliziert wie man auf den ersten Blick denkt!

Anpassungen

Ich habe noch ein bisschen herumexperimentiert und festgestellt, dass das Bild feiner wird, wenn man die Grenze, an der entschieden wird, ob ein Pixel hell oder Dunkel wird, niedriger setzt. Ich habe also

// prüfen, ob Pixel auf weiß oder schwarz gesetzt wird
 if($prevVal < ($black + $white) / 2)

durch

// prüfen, ob Pixel auf weiß oder schwarz gesetzt wird
 if($prevVal < ($black + $white) / 3)

ersetzt. Das Bild sieht jetzt so aus:

1258041876

Man kann auch die Farben ändern. Wichtig ist aber, dass Weiß durch die Hellere Farbe und Schwarz durch die dunklere Farbe ersetzt wird. Anders geht es nicht!

Wenn man 3 oder mehr Farben benutzen möchte, muss man nur den Block verändern, an dem entschieden wird, welche Farbe gesetzt wird.

Ausführungsdauer

Auf meinem Testserver (800 Mhz, 386MB RAM) hat die Ausführung beim Beispielbild ca. 11 Sekunden gedauert. Da das Bild nicht wirklich sehr groß ist und das Skript trotzdem so lange gebraucht hat, kann man sagen, dass der Algorithmus insgesamt sehr langsam ist. Ob man das Dithering noch optimieren kann, weiß ich nicht.

Wer Dithering im Webbereich ernsthaft einsetzen möchte, sollte sowieso eine andere Sprache dazu verwenden. Java hat z.B. für das gleiche Bild nur ca. 1,5 Sekunden benötigt. Eine Implementierung in C oder C++ wäre wahrscheinlich noch schneller, da das direkt auf dem System läuft.

1 Star2 Stars3 Stars4 Stars5 Stars (Wurde noch nicht bewertet)
Loading...


12 Kommentare zu “Dithering mit PHP”

  1. Hey studiert dein Cousin zufällig in Freiburg?

    Dort läuft gerade ein Proseminar, das sich mit der Verarbeitung und Manipulation von solchen Fotos beschäftigt.

    MfG

    Simon

  2. Hi,

    mein Cousin studiert in Ulm Medieninformatik 😉

    MfG
    Simon

  3. Die Bilder sehen sehr interessant aus, wusste gar nicht, dass man solche Sachen auch per php realisieren kann. Was vielleicht noch gut ankommen würde wäre, wenn du das Script auf deinen Webserver klatschst und es per Link der Blogger-Community zur Verfügung stellst. Dem ein oder anderen sollte das sogar einen Backlink wert sein 😉
    .-= alte Kiehvoz´s last blog ..Auch Babys sprechen bereits in Dialekt =-.

  4. Hi,

    das wäre momentan zu viel Aufwand, da ich in dem Fall auch noch einige Sicherheitsprüfungen einbauen müsste. Vielleicht irgendwann mal 🙂

    MfG
    Simon

  5. Das geditherte Bild als JPEG zu speichern ist dann aber reichlich widersinnig.

    Erstens ist die DCT (Diskrete Cosinus-Transformation) im JPEG-Algorithmus überhaupt gar nicht geeignet, Bilder mit extremen Kontrasten und feinen Strukturen zu speichern, weil das Gibbssche Phänomen dann für deutliche Kompressionsartefakte (Blocking und Ringing) sorgt, das Ergebnis dann also wieder Zwischenstufen zwischen schwarz und weiß enthält.

    Zweitens ist das Dithering doch eigentlich dafür gedacht, Bilder mit einer Palette von geringem Umfang zu erzeugen, also sollte man das Bild dann auch in einem Format speichern, welches überhaupt Bilder mit kleiner Palette unterstützt: PNG beispielsweise. Dazu wäre es aber sicher sinnvoll, zwei Bild-Ressourcen zu verwenden: Einmal das Originalbild (imagecreatefromstring), und parallel das neue Bild mit den selben Dimensionen als Palette-Image erzeugt (imagecreate). Dann liest der Dither-Algorithmus immer Pixel aus dem Quell-Image und setzt Pixel in das Ziel-Image, und dieses wird dann mit seiner reduzierten Palette platzsparender als PNG gespeichert.

    (Ja, es gibt auch 1-bit-JPEGs; aber soweit ich weiß, unterstützt die GD-Bibliothek in PHP dieses „JBIG“-Format nicht, sondern nur Baseline-JPEG für 24-bit RGB.)

  6. @LigH: Du hast da wohl ziemlich viel Ahnung, ich hab das Skript oben als Laie geschrieben. Wärst Du evtl. daran interessiert, einen Gastartikel für net-developers.de zu diesem Thema (und vllt. noch mehr) zu schreiben?

    Ich bin mir sicher, dass sich einige dafür interessieren würden.

    PS.: So wie du das erklärst, wird mir klar, warum JPGs in diesem Fall schwachsinnig sind. Ehrlich gesagt habe ich damals gar nicht über das erforderliche Format nachgedacht, sondern aus Routine einfach JPG genommen.

    MfG
    Simon

  7. Tut mir leid, viel Zeit zum Schreiben habe ich nicht, und gerade zum Thema Multi-Level-Dithering (nicht nur zu zwei Farben, sondern zu einer ganzen Farbpalette) experimentiere ich noch; es gibt da für mich noch erhebliche Unklarbeiten.

    Beispielsweise wie ich das „Fehlerbild“ speichern soll, da die akkumulierten Fehlerwerte pro Pixel anscheinend auch jenseits von [0..255] liegen können, und deshalb Image-Ressourcen dafür wohl ungeeignet wären. Man kann ja die Farbe eines RGB-Pixels nicht einfach so als Ganzzahlwert verarbeiten, oder? Beim „Dithern auf Farbpalette“ müssen da doch R-, G- und B-Differenzen separat betrachtet werden. Vielleicht wäre eine Geringste-Differenz-Anpassung sogar in einem YUV- oder HSL-Farbraum günstiger…

    Wahrscheinlich wäre dann PHP sogar wenig geeignet, als interpretierte Skript-Sprache ist die Verarbeitung größerer Datenfelder ja doch mit viel RAM und Zeit verbunden, vor allem wenn fertige GD2-Funktionen dafür nicht mehr verwendet werden können.

    Außerdem können bereits eng konfigurierte virtuelle Webserver schon mal die Konvertierung mit „HTTP Error 500“ beenden, wenn größere Bilder und Zwischenpuffer an die Grenzen des Variablenspeichers geraten.

  8. Schade, dass das mit dem Gastartikel zeitlich nicht hinhaut.

    Deie Ausführungen sind interessant, auch wenn ich zugegebenermaßen stellenweise nicht 100%ig folgen kann.

    Deine Unklarheiten kann ich somit auch nicht beseitigen, aber ich denke, das war auch nicht deine Absicht 😉

    Darf ich fragen, ob du dich beruflich mit dem Thema auseinandersetzt oder privat? Studium?

  9. Wow, echt cool! Ich bin da noch ganz neu und finde es immer wieder spannend, was alles möglich ist -und bei euch sieht das immer so einfach aus 🙂

  10. Übung macht den Meister 🙂

  11. Hi
    I am working on this dithering images using PHP and I am new to this can I have the source code for the reference

  12. Hi,
    the code is in the article above. You should be able to see and copy it.

Hinterlasse einen Kommentar!

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.

»Informationen zum Artikel

Autor: Simon
Datum: 12.11.2009
Zeit: 17:54 Uhr
Kategorien: Codeschnipsel
Gelesen: 33396x heute: 2x

Kommentare: RSS 2.0.
Diesen Artikel kommentieren oder einen Trackback senden.

»Mehr zum Thema erfahren

Schlagwörter: , , , ,

»Meta