Why Cartoons Compress Better Than Video in GIF

This article explains the mathematical framework behind GIF file size discrepancies, specifically contrasting flat cartoon art with real-world photographic footage. Claude Shannon’s Information Theory, particularly the concept of Shannon entropy, combined with the algorithmic behavior of Lempel-Ziv-Welch (LZW) dictionary coding, provides the formal mathematical model for why simplistic graphics achieve significantly higher compression ratios than complex, noisy video.

Shannon Entropy and Information Density

The foundational mathematical model governing this behavior is Claude Shannon’s Source Coding Theorem. Shannon defined the information entropy \(H(X)\) of a discrete random variable \(X\) (in this context, pixel color values in an image) using the formula:

\[H(X) = -\sum_{i=1}^{n} P(x_i) \log_2 P(x_i)\]

Where \(P(x_i)\) represents the probability of a specific color \(x_i\) occurring across the image. Shannon's theorem dictates that the minimum average number of bits required to encode a symbol without loss cannot be less than the entropy of the source.

In simple cartoon art, color distribution is heavily skewed. Large regions share identical, flat colors. A small subset of palette indices holds a probability \(P(x_i)\) approaching 1, while most other colors have a probability near 0. Consequently, the calculated entropy \(H(X)\) is extremely low, meaning very few bits are mathematically required to describe the state of any given pixel.

Conversely, real-world footage features analog gradients, continuous lighting shifts, and sensor noise. Even across visually "flat" surfaces, adjacent pixels vary subtly in value. The probability distribution \(P(x_i)\) across the 256 available GIF colors is relatively uniform. As \(P(x_i)\) flattens, Shannon entropy maximizes toward its upper bound:

\[H_{\max} = \log_2(N)\]

For an 8-bit palette (\(N = 256\)), maximum entropy is 8 bits per pixel. Because real footage exhibits high entropy, its theoretical compression limit is inherently restricted compared to the low-entropy cartoon.

Lempel-Ziv-Welch (LZW) String Redundancy

GIF relies on the LZW algorithm, a lossless, dictionary-based compression technique. Rather than storing individual pixels, LZW dynamically builds a codebook of repeating sequences encountered while scanning pixel rows sequentially.

The efficiency of LZW depends on the recurrence rate and length of matching substrings. Let a row of pixels be modeled as a sequence \(S = (s_1, s_2, \dots, s_m)\).

  1. Cartoon Art: A scan line across a cartoon character consists of long runs of uniform color indices (e.g., [5, 5, 5, 5, 5, ...]). LZW quickly registers short sequences and progressively builds code entries for exponential string lengths (5-5, 5-5-5, 5-5-5-5). Within a few scan lines, hundreds of pixels are represented by single, high-order dictionary keys.
  2. Real-World Footage: Photographic data rarely produces repeated pixel sequences of any substantial length due to thermal noise and continuous-tone transitions. The sequence looks disordered (e.g., [142, 143, 141, 145, ...]). The LZW dictionary fills with short, two-symbol phrases that rarely reoccur.

Once the GIF dictionary reaches its maximum size limit (4,096 entries or 12 bits per code), it must either stop adding strings or clear itself entirely. With real footage, the dictionary saturates almost instantly without yielding compression savings, often causing the output file to approach or exceed raw byte representation.

Markov Random Fields and Spatial Correlation

The spatial distribution of pixels can also be modeled using a first-order Markov chain, evaluating the transition probability \(P(X_t = c \mid X_{t-1} = c)\) between neighboring pixels.

In cartoon imagery, the probability that the next pixel is identical to the current pixel approaches 1 (\(P \approx 1\)). In photographic footage, that same transition probability drops sharply toward 0 due to natural micro-variations. The high conditional entropy in photographic footage breaks the sequential predictability that LZW requires, explaining why cartoons achieve dramatically smaller file sizes under identical GIF encoding constraints.