PNG Compression

Lossless image compression format with support for transparency using the DEFLATE algorithm.

The Quest for a Better Image Format: The Birth of PNG

In the early days of the World Wide Web, the GIF format was king. It allowed for small file sizes for the simple graphics used on websites and brought the world the joy of simple animations. However, GIF had two significant drawbacks that spurred the internet community to search for a better alternative. First, it was limited to a palette of just 256 colors, making it unsuitable for high-quality photographic images. Second, the LZW compression algorithm it used was patented, and the patent holder began demanding licensing fees, creating legal uncertainty for software developers.

In response to this, a group of developers created a new, open standard designed to be a superior, patent-free replacement for GIF. They named it PNG, which officially stands for . PNG was designed from the ground up to be versatile, powerful, and, most importantly, completely lossless. It has since become the most widely used lossless image compression format on the internet, prized for its ability to handle graphics with sharp edges, text, and transparency with perfect fidelity.

The Heart of PNG: The DEFLATE Algorithm

Unlike JPEG, which uses a complex, multi-stage, lossy pipeline, PNG's compression power comes from a single, brilliant, and completely algorithm known as DEFLATE. The DEFLATE algorithm is not one single technique but a clever combination of two well-established compression methods applied in sequence. It is the same core algorithm used in popular file archiving formats like ZIP and GZIP, which speaks to its versatility and effectiveness.

Part 1: LZ77 - Finding Repetitive Patterns

The first stage of DEFLATE employs the , a powerful dictionary-based compression technique. It works by looking for repeated sequences of data within the image.

Imagine the algorithm reading through your image's pixel data byte by byte. It maintains a "sliding window" of recently seen data, which acts as a dynamic dictionary. As it reads new data, it constantly checks its dictionary to see if the current sequence of bytes has appeared before within the window.

  • If the sequence is new, the algorithm simply outputs it as a "literal" byte and adds it to its dictionary.
  • If the sequence has been seen before, the algorithm does something clever. Instead of outputting the sequence of bytes again, it outputs a much shorter reference, or a pointer. This pointer typically consists of two numbers:
    1. Distance: How far back in the dictionary to look to find the start of the matching sequence.
    2. Length: How many bytes to copy from that starting point.

For example, consider the sentence: "The slow brown fox jumps over the other slow brown dog." The LZ77 algorithm would process this as follows:

  1. It would output "The slow brown fox jumps over the other " as literals.
  2. When it reaches the second "slow brown ", it finds a match in its dictionary. Instead of writing out those 11 characters again, it outputs a pointer like (distance: 31, length: 11), which is much shorter.
  3. It then outputs "dog." as literals.

This technique is extremely effective for computer-generated graphics, which often contain large areas of identical color or repeating patterns.

Part 2: Huffman Coding - Efficiently Encoding the Result

The output of the LZ77 stage is a mix of literal bytes (for new data) and distance/length pointers (for repeated data). The second stage of DEFLATE takes this mixed stream and compresses it further using .

Huffman coding is a form of entropy coding. It works by analyzing the frequency of each symbol (be it a literal byte or a specific type of pointer) in the data stream. It then builds a custom codebook where:

  • Symbols that appear very frequently are assigned very short binary codes (e.g., just a few bits).
  • Symbols that appear infrequently are assigned longer binary codes.

By using fewer bits for the most common elements, the overall size of the data stream is reduced significantly. The combination of LZ77's pattern-finding ability and Huffman's statistical coding efficiency makes the DEFLATE algorithm incredibly powerful and versatile, forming the lossless core of the PNG format.

PNG's Secret Weapon: Pre-compression Filtering

While the DEFLATE algorithm is powerful, it works best on data with lots of repetition. Natural images, even those with large areas of seemingly solid color, often have subtle noise or gradients that break up long, perfect runs of identical bytes. To make the image data more "compressible" for the DEFLATE engine, PNG employs a crucial pre-processing step called filtering.

The PNG encoder processes the image one horizontal row of pixels at a time (a "scanline"). Before a scanline is compressed, it can be "filtered." This does not mean applying a visual effect like a blur. Instead, it is a reversible mathematical transformation that replaces the actual pixel values with smaller, more repetitive difference values. The idea is to encode the *change* from one pixel to the next, rather than the absolute value of the pixel itself. Since adjacent pixels in an image are often very similar, these differences are frequently small numbers or zeros, which are much easier for the DEFLATE algorithm to compress.

For each scanline, the PNG encoder can choose one of five filter types, selecting the one that it predicts will produce the most compressible result for that specific line. The type of filter used is then stored alongside the filtered data, so the decoder knows how to reverse the process. The filter types are:

  • Type 0: None - No filtering is applied. The scanline's raw pixel data is passed directly to the compressor.
  • Type 1: Sub - Each pixel's value is replaced by the difference between it and the value of the pixel immediately to its left. This is very effective for images with smooth horizontal gradients.
  • Type 2: Up - Each pixel's value is replaced by the difference between it and the value of the pixel directly above it in the previous scanline. This works well for images with vertical patterns.
  • Type 3: Average - Each pixel's value is replaced by the difference between it and the average of the pixels to its left and directly above. This is a good general-purpose filter that handles diagonal gradients well.
  • Type 4: Paeth - This is the most complex filter. It makes a prediction for the current pixel based on its three closest neighbors (left, above, and upper-left) and then chooses the neighbor that is closest to the predicted value. The pixel is then replaced by the difference between its actual value and the value of that chosen neighbor. It excels at handling complex, two-dimensional patterns.

This intelligent filtering step is a major reason why PNG is often much more efficient at compressing graphics and diagrams than older formats like GIF, which lack this sophisticated pre-processing stage.

PNG's Versatility: Color Modes and Transparency

PNG was designed to be highly flexible, capable of handling a wide variety of image types. It achieves this through support for multiple color modes and a groundbreaking approach to transparency.

Handling Color

PNG is not limited to a single color representation. It supports several modes to efficiently store different kinds of images:

  • Grayscale: For black-and-white images. Can use up to 16 bits per pixel for a vast range of gray tones.
  • Indexed Color: This mode is similar to GIF. It uses a palette of up to 256 colors. This is ideal for images with a limited number of colors to achieve a smaller file size than full color modes.
  • Truecolor: This is the most common mode for high-quality images. It stores full RGB color information, typically using 24 bits per pixel (8 bits for each of Red, Green, and Blue), allowing for over 16.7 million distinct colors.

Revolutionary Transparency: The Alpha Channel

Perhaps PNG's most significant advantage over GIF is its support for a full . While GIF offers only binary transparency (a pixel is either fully visible or fully invisible), PNG allows for variable levels of translucency.

When an alpha channel is present (in Grayscale or Truecolor modes), an extra 8 or 16 bits of data is stored for each pixel. This data does not represent color, but rather the pixel's level of opacity, on a scale from 0 (completely transparent) to 255 (completely opaque). This allows for sophisticated effects like smooth, anti-aliased edges, shadows that fade into the background, and glassy, translucent objects. This feature alone has made PNG the standard format for web graphics, logos, and icons that need to be overlaid seamlessly on different backgrounds.

    PNG Compression