Lossless Image Compression Algorithms: Deep Dive into PNG, WebP & AVIF

The Mathematical Foundation of Lossless Compression

Lossless data compression operates by exploiting two forms of data redundancy:

• Spatial Redundancy: Adjacent pixels in an image frequently share identical or closely correlated color values. Converting absolute pixel values into relative difference residuals clusters the numerical data distribution.
• Statistical (Entropy) Redundancy: Not all byte symbols occur with equal probability. Entropy encoding algorithms (such as Huffman coding and Arithmetic coding) assign shorter bit sequences to frequently occurring symbols according to Shannon information theory:
  H(X) = - \sum_{i=1}^{n} P(x_i) \log_2 P(x_i)

PNG Architecture: Scanline Filtering & DEFLATE

Standard PNG operates in two distinct stages: Filtering followed by Compression.

The Five PNG Delta Filters

Directly feeding raw RGB byte streams into LZ77 produces poor compression because image gradients produce constantly shifting values. PNG evaluates each scanline independently, prefixing the row with a 1-byte filter selector:

• Filter 0 (None): Transmits raw byte unmodified.
• Filter 1 (Sub): Subtracts the byte to the left: $ ext{Filt}(x) = ext{Orig}(x) - ext{Orig}(x - bpp)$.
• Filter 2 (Up): Subtracts the byte immediately above in the preceding scanline.
• Filter 3 (Average): Subtracts the arithmetic mean of left and above pixels.
• Filter 4 (Paeth): Evaluates a linear function $p = a + b - c$ (where $a$ is left, $b$ is above, and $c$ is upper-left diagonal) and selects whichever neighbor is closest to $p$.

Filtered scanlines are then passed into the DEFLATE algorithm, which executes sliding-window LZ77 dictionary substitution followed by canonical Huffman tree coding.

WebP Lossless: The Four Modern Image Transforms

While PNG filters are limited to scanline heuristics, Lossless WebP (VP8L) applies four sophisticated spatial and color transforms before entropy coding:

1. Spatial Predictor Transform: Divides the image into $16 imes 16$ macro-blocks. For each block, it selects the optimal predictor from 14 spatial algorithms (such as TrueMotion, linear combinations, and gradient clamps) to model local textures.
2. Color (Cross-Color) Transform: In natural imagery, red and blue color channels correlate strongly with green. WebP decorrelates channels using linear transformations ($R' = R - g_r cdot G$ and $B' = B - g_b cdot G$), collapsing red and blue channel variances toward zero.
3. Color Indexing (Palette) Transform: If the image contains fewer than 256 unique colors, it automatically replaces 32-bit ARGB values with an 8-bit index array.
4. Color Cache Transform: Maintains an internal FIFO cache of recently encountered colors, allowing repeated colors to be represented by a single lightweight cache index.

AVIF Lossless: AV1 Identity Transform & Intra-Prediction

AVIF encapsulates intra-coded frames from the alliance-backed AV1 video codec. For lossless encoding, AVIF bypasses the lossy Discrete Cosine Transform (DCT) matrix by engaging Identity Transform Mode:

• Directional Intra-Prediction: AV1 models block interiors using 56 fine-grained angular prediction directions, projecting edge gradients diagonally across $4 imes 4$ to $64 imes 64$ coding units.
• Multi-Symbol Arithmetic Coding (D-Ary): Unlike Huffman coding (which requires integer bit lengths per symbol), arithmetic coding represents entire message streams as a single fractional number between 0.0 and 1.0, approaching the theoretical Shannon entropy limit within fractions of a percent.

Entropy Coding Mechanics & Huffman Tree Optimizations

In high-throughput web graphic pipelines, compressing the residual difference arrays requires optimal entropy tree construction. Standard PNG compressors often rely on fixed Huffman tables to reduce CPU encoding time; however, advanced optimizers (such as Zopfli and oxipng) iterate through thousands of candidate dynamic Huffman bit lengths. By calculating the exact minimum spanning cost of prefix code trees, dynamic optimization reduces final PNG archive payloads by an additional 5% to 15% without sacrificing lossless decodability.

Client Decoding Complexity & Mobile Battery Trade-Offs

While lossless WebP and AVIF deliver superior byte density over network pipes, engineering teams must evaluate client-side decompression overhead. PNG decoding is virtually instantaneous on modern devices because DEFLATE routines are implemented in highly optimized assembly (zlib-ng). Conversely, AVIF lossless decompression requires navigating complex AV1 intra-prediction trees and arithmetic context models, consuming measurably more CPU cycles and battery energy on low-power mobile hardware.

For high-frequency UI interactions where hundreds of raster assets are decoded simultaneously (such as infinite-scroll feeds or interactive design toolbars), WebP lossless provides the optimal sweet spot: achieving 25% smaller file sizes than PNG while decompressing up to four times faster than AV1 identity frames.