PNG: Universelle Bilder fürs Web

Deflate-Kompression

Für PNG wurde der Deflate/Inflate-Algorithmus von Philip Katz spezifiziert, den beispielsweise auch PKZIP verwendet. Deflate erkennt nur wiederkehrende, horizontale Muster. Dafür arbeiten aber die vorgeschalteten Filter mit Bildpunkten aus der darüber liegenden Bildzeile, so dass vertikale Bildmuster ebenfalls erkannt werden. Daher lässt sich eine bessere Komprimierung erzielen als bei GIF. Bei verschiedenen Mustern komprimiert der Deflate-Algorithmus somit besser als sein LZW-Pendant.

Nach der Deflate-Methode wird zunächst der LZ77-Algorithmus auf die zu komprimierenden Daten angewandt - allerdings ohne sortierte Hash-Tabellen. Es folgt die Kodierung nach der Huffmann-Methode (Entropie-Kodierung). Diese kommt auch in JPEG 2000 zum Einsatz - mehr über dieses Bildformat finden Sie hier.

Bei der Entropie-Kodierung werden die Zeichen nach ihrer Häufigkeit sortiert. Häufig vorkommende und lange Bitfolgen werden durch kurze Codes repräsentiert - und seltene Folgen durch längere.

Beim Aufbau des Huffman-Baums sortiert man die Werte zunächst nach Ihrer Häufigkeit. Dann weist man dem seltensten Wert die 0 zu und dem zweitseltensten Wert die 1 zu. Diese beiden fasst man zusammen, indem man die Häufigkeiten addiert und in die Liste der Häufigkeiten einsortiert. Im Folgenden verarbeitet man wieder die beiden seltensten Werte der Liste und fährt so fort, bis alle kodiert sind.