GIF compression is an older format, and so it is relatively simple to understand. In order to save disk space, fewer colors are stored. So GIFs have a limited palette of colors, and each pixel references one of those colors. The fewer the colors, the smaller the file. These colors are often assigned through dithering which is basically like digital stippling. It's also akin to halftones. So if I have a halftone GIF that only uses black and white, then I only need two colors in my palette, so even with a detailed moving pattern I am able to get decently small file sizes. That's not why I started doing the halftones, but it just wound up being a perfect fit for animating them! I made the GIF below when Tumblr still had a 1 Mb upload limit, but I was able to squeeze this large resolution and relatively long loop under that by halftoning each of the red, green, and blue channels, effectively making a palette with 8 total colors (red, yellow, green, cyan, blue, magenta, black, white).
Tumblr is one of the few social media sites that actually allows you to upload and display GIF files in their native format. You can see all the GIFs I've made by visiting my Tumblr page or you can check out my gallery of favorites on this site.
Most other sites (if they even allow direct upload) immediately convert the GIF to a video format and display the video file. For a lot of everyday GIFs this results in a smaller file with little noticeable visual difference which is why they do it. But it absolutely wreaks havoc with my halftones. And the reason is because modern compression techniques are far more sophisticated than using a limited palette, paradoxically making them inept for my special case. It's kind of like my halftones are the compression already, so trying to compress it further is just putting two compression techniques at odds with each other. Instagram has been a great place to post my still images but they don't allow direct GIF uploads so to post one of my loops there it is actually compressed as video twice (once on my end to create a video file for upload and once on their end when they reprocess that video) which absolutely destroys my halftones. Below, a crop of the original is on the left and a crop of the same region from an Instagram upload is on the right. Ouch.
But why? The underlying idea of modern compression revolves around the fact that most images and videos are made of gradients. A sky, a cheek, a shadow, etc. A lot of times gradients look really grainy with dithering, which inspired people to look for other ways to save space. Joseph Fourier is a mathematician who proved in the 1800's that any signal can be expressed as a sum of waves, and a picture file is a visual signal. One of my favorite mathematical concepts is the fraction 1/f, which basically implies that in most signals, the average amplitude of a constituent wave will be inversely related to the frequency. In other words, there is one big mountain peak and lots of little boulders. An image can be interpreted in terms of frequency and amplitude via a Fourier Transform. Below, the image on the left has it's Fourier spectrum on the right. To interpret this image, the distance from the center determines the frequency and the brightness determines the amplitude (and the angle determines the direction). As you can see, in the center where the frequency is small the amplitude is brighter and as the frequency increases towards the edge the amplitude generally decreases and it's darker.
A Fourier Transform takes an image into the frequency domain where it is no longer directly represented by pixel values, but rather as a sum of waves (which are themselves now stored in the pixels). Every pixel represents a single wave that repeats across the entire image. The waves all add together to form the image and for any given picture there are many waves that don't contribute much at all to how the image looks. For example, a high pass filter removes any waves past a certain frequency and often a significant number of waves can be eliminated entirely without making a noticeable difference, since they have small amplitudes due to the 1/f property. Below you can see on the right that all of the waves past a certain distance from the center have been eliminated, but the image on the left still looks pretty much the same, just slightly blurry.
Therefore, it can take less memory to store the waves of an image than it does to store the image itself. Throwing away extraneous waves is one of the basic concepts behind common compression techniques like JPEG and MP4, although they might not use exactly a Fourier Transform and they use additional tricks like treating the images as blocks and quantization and other stuff. The point is that these techniques work amazingly well in most situations. But there are exceptions! Way back when Joseph Fourier was first studying his famous equations, he wanted to prove that any signal could be represented as the sum of waves, even a step function that jumps vertically from one value to another. It is proven to work, but it takes an infinite number of waves to perfectly cancel out and make a sharp corner. For a sharp edge in a compressed image you can see this limitation in the form of ringing known as Gibb's phenomenon. Below on the left is the original halftone saved as a PNG file which is lossless. Each pixel is just on or off, so there are no gray values. On the right is the same halftone that I saved with JPEG compression at medium-high quality. The extra gray pixels in the JPEG are the result of waves which have not been cancelled out because not enough waves are used in total. Not only does the JPEG file have the ringing artifact, but the file size is also around 5x larger. The PNG file can index the colors like a GIF does, but the JPEG has to store the waves which for this example is much more expensive and still is not any where near enough.
For video compression, the problem is even worse because it involves not just spatial but also temporal gradients - pixels gradually changing in space as well as gradually changing in time. The pixels in my GIFs not only have hard edges to their side but are also constantly abruptly changing from one frame to the next. For a GIF file that is no problem, but for typical video it can really degrade and is especially true of most streaming platforms.
What do you think? Was this article interesting? Let me know in the comments below.
18 October, 2022
Karl BlueHippo
That was a neat read. I too have had difficulty uploading pieces intentionally made with under 256 colors to instagram and I understood a lot of these concepts before reading this, but this is well put and explains a lot! Dither me this, Batman.