GIF Fun 5: Color Reduction

In the second installment of my GIF-related posts, I wrote about how one can preserve all the colors of an image when putting it into a GIF. In the end, it turned out that due to how most software handles displaying GIFs, no matter what we would do, keeping all colors would come with the downside of some long and not good-looking animation. This means that if people want to upload images for their GIF in my editor, then the amount of colors needs to be reduced to at least 256 so they fit into a single color table. How to achieve that is what today’s post is about.

Actually, there is already a function that reduces color in the editor; I implemented it alongside the rectangle and transparency methods that allow the preservation of all colors. This reduction function is an implementation of k-means, grouping colors in 3D space and then using only one color per group. It was an idea that worked out well enough for most images I tested it on, but still has its problems, namely efficiency and banding.

Median Cut: A Faster Reducer

k-means is rather expensive to calculate, and my implementation does not even make sure all generated groups are non-empty. Furthermore, the initial distribution of group centers impacts the outcome, meaning that there is one more variable to take care of, which I would rather not have to do. The current implementation uses either colors along the grey line or a kind of color spiral as initial points. While the results look not too bad, unused colors are a bit of a no-no because those could be used to preserve more detail, and the calculations take a while even with an optimization from a naive implementation. In order to right those wrongs, I eventually sat down and implemented Median Cut, which turned out to be quite simple and resulted in adequate color palettes in a much better runtime.

While k-means has to do all that grouping and regrouping for all colors by calculating a lot of distances, for Median Cut, things are way easier. Starting with a set of color bins, where at the start there is only one holding all colors, and a number of target bins, it does the following:

1. Select the bin with the largest amount of colors in it
2. Calculate which of the red, green, and blue channels has the highest spread (the difference between the smallest and largest value seen in that channel)
3. Sort the colors according to that channel
4. Put the upper half of colors into a new bin (the titular median cut)
5. Keep doing this until the amount of target bins is reached

The amount of colors in a bin is a very simple metric, and in theory, other selection criteria could be used, but it does a good enough job. One could also go by brightness spread, or something else, but keeping bin size in mind is probably good regardless of the chosen metric. Also because we can treat the bins as simple arrays, getting the amount of colors in them does not lead to any costly calculations. The spread per channel just needs to be calculated for the selected bin and can be done in a single loop, meaning it is cost-effective.

I chose to only have unique colors in the bins, meaning that if a color occurs multiple times in the image, it does not influence the bin selection process. This helps avoid creating a confused mapping at the end if one color appears in more than one bin. Using the amount of colors per bin as a metric also leads to the final bins having pretty equal sizes. There can be a bin with about twice the size as the rest, but as long as a bin amount is used that is a power of 2, there should not be any bigger problems. Because for GIFs the amount of colors we want and therefore the number of bins is at most 256, we actually end up having a linear runtime in the amount of (unique) colors of our image, which is pretty neat.

With Median Cut implemented, I had a better way to calculate ‘good’ colors for simple color reduction purposes. But still, there is a problem. Replacing the original colors with a palette created by median cut leads to banding, where the edges between two different colored areas are rather pronounced and often look bad.

There is nothing in Median Cut that concerns itself with preserving shades and at least some level of smoothness. Thankfully, there are ways to avoid that, so let’s look at them next.

Dithering

It is used quite spectacularly in the game Return of the Obra Dinn and, of course, is a staple method of using a reduced color palette and still keeping smooth shadows and gray tones.

Dithering is the de facto way to circumvent banding by using the power of halftones so that an image looks as if it has more detail than there actually could be in terms of pure colors. Today you will likely see dithering used for aesthetic reasons more than technical ones. I put off implementing it for a while even though it is not that hard™.

Dithering comes in many flavors; the more known ones are ordered dithering, where static matrices are used, leading to checkboard patterns (like Bayer dithering), using blue noise to break up such patterns a bit, or calculating quantization errors per pixel and diffusing them (like Floyd-Steinberg). A lot of material about dithering reduces the colors to pure black and white or, at best, some gray tone. Using more than just shades of gray makes things not that more complicated, but it requires a bit of care as we can no longer just rely on a singular value like luminance to pick a pixel’s color. And, as you will see further down, it was the way of how to choose a color that initially got me stuck when implementing dithering.

Dithering can make an image appear brighter than it is if the colors are quantized in normal RGB space. I do not think that it is that big of an issue, so I ignored any possible preprocessing to a space where luminosity could be used better. Furthermore, most dither approaches are really fast; faster even than Median Cut, so besides keeping banding at bay, they also provide a speed boost for color reduction.

Error Diffusion

Floyd-Steinberg is one of the many ways one can do dithering with error diffusion, where the difference between the original color and the quantized color is pushed onto yet-to-be-processed neighbors, leading to pretty neat results that avoid a checkerboard pattern. Which pixel gets how much of the error is dependent on the method used; not the whole error needs to get passed on, and in theory the range of how far out the error is propagated is not bounded. Floyd-Steinberg, Atkinson, Burkes, etc., are really just names for tables that tell us which pixel gets how much of the error; besides that, the basic procedure stays the same, so we can even come up with our own tables. For example, we can push a fraction of the error to the three pixels below the one we process and see what happens. This pyramid pattern is not particularly suited to keep strange artifacts and patterns from appearing, but it shows that we can indeed make our own tables.

To begin, I took a look at Wikipedia for Floyd-Steinberg and naively translated the pseudocode there into TypeScript. And the result was not great. At first I thought I had yucked up the implementation, but after looking around, it turns out that I had made a wrong assumption about the way I could select colors. What I had tried to do was to use a color palette created by median cut and select colors based on the minimal distance to those in the palette, but that did not work out like I had thought it would.

Choosing a color based on distance from a palette is not bad when it is a direct mapping without anything extra being done, but it is not the way to go for error diffusion. There are, for example, problems when the representative colors are not somewhat evenly spread; an error in one channel can blow out, leading to some nasty error propagation like you can see below.

Color Quantization

An easy way to do color quantization for dithering is to use evenly distributed values in each channel and then clamp the colors to them. If we want to have n+1 different values for a channel, we can use round (n * (channel_value / 255)) to first get a value in [0,n] and then multiply that by (255/n) before rounding the result to get the actual quantized channel value. Doing this for the red, green, and blue channels gives us the closest color that will not lead to large and hard-to-diffuse errors.

There is a problem with this clamping in that it gets harder to control the number of created colors. If we allow 6 values per channel, we have 216 possible colors that our pixel could get clamped to, but there is no guarantee that all of these colors will be used. Where Median Cut lets us say how many colors we want, for the clamping approach it is hard to set the amount of colors we end up with; we can only really set a maximum via how many values we allow per channel. The fewer values per channel we allow, the more grainy the image will look as the overall error rises, so we would like the value to be as high as possible to avoid that. This, of course, then conflicts with the fact that we can only use 256 colors for the whole image within a GIF, meaning we can either use the safe option of always using 6 values per channel for a total of 216 possible colors but maybe get slightly grainy results, or try to find an optimal value for our image by rerunning the dither multiple times and checking the number of unique colors each time. Because dithering leads to the perception of more colors than used anyway, 6 values per channel suffice in most cases, so we can go with that. Also, with only 216 colors being possible in general, there is the option for a general optimization in the future where the GIF ends up with only one global color table needed, as all images would share the same possible color palette. There seem to be more sophisticated ways to handle dithering and color selection, but I am not currently about to read an academic paper just to have ever so slightly better colors.

With a better color selection, the Floyd-Steinberg implementation also started producing good looking images.

Ordered Dithering

After Floyd-Steinberg worked, I went on to also implement basic Bayer dithering but did not care much about making it neat. Bayer dithering uses a static matrix that is repeatedly tiled over the input image and used to influence the color selection as an additional factor, shifting channel values ever so slightly around. In theory, Bayer matrices can be calculated for any size, but because it was not my focus, I opted to simply hard-code the three basic ones (2 by 2, 4 by 4, and 8 by 8).

The results tend to have a checkboard pattern, which is why error diffusion is often used for static images. However, ordered dithering is better suited for animations and can easily be parallelized because there is no possibility of the colors influencing each other. So if you were to use dithering in a game at runtime, ordered dithering would likely be the way to go.

A point of Bayer dithering, which I noticed only after implementation, is that because there is no error that can propagate, using a color palette made by Median Cut does not result in the same error that occurs with error diffusion. In practice, though, it still leads to very strange images as the shifts due to the matrix send colors to strange places. So why it may have its uses for some trippy images, for Bayer dithering, the color selection/quantization should be the same as for Floyd-Steinberg if images are to look normal.

Decisions Decisions

Just for dithering with error diffusion, there are tons of different tables and smaller things one can tweak as serpentine processing, where the algorithm handles each row in an alternating direction. Bayer matrices can, in theory, be as big as one wants them to be. And of course noise generation, which I so far have ignored, is its own beast with things to tweak and play with. All of that is even before there are more choices, like how many colors to use, how to quantize colors, using grayscale or not, and potential preprocessing of the image.

So if I were to use dithering in my editor, then there would be too many possibilities for any user to choose from. For now I opted to give two processing options for the image upload, alongside a checkbox for grayscale and one input for a maximum color amount. The standard option is error diffusion via Floyd-Steinberg, non-greyscale, and using 216 colors. And the other option is to use Median Cut with a default of 256 colors For the future, I plan on making a configuration for the editor where users can select and change what options are used overall, which would include swapping the used diffusion functions.

But for now it works well enough, so I will finish the UI parts and then leave it alone for a while.

And that is all for this post. Thank you for reading and see you next time.

• GIF