Unraveling Statistics Behind Floyd-Steinberg Dithering in R

justinkraaijenbrink
Apr 11 · 6 min read
Photo by Bud Helisson on Unsplash

un·rav·el (ŭn-răv’əl) v. un·rav·eled un·rav·el·ing un·rav·els ~ To clarify the elements of something mysterious or baffling

I has been a while since my first post, for which I chose to write about the relatively unfamiliar Floyd-Steinberg dithering algorithm. Most probably my post would have been read by more people had it been called How I used deep learning to become a successful investor or so… To receive at least some readers, I decided to make the dithering as practically oriented and accessible as possible, which seems to have worked! Viewer stats were far better than predicted, so may be my next post should be something Bayesian. Nevertheless, in my sincere enthusiasm to show you the elegance of the algorithm of Robert W. Floyd and Louis Steinberg, I did skip over some very interesting statistical details. Such a shame! In this article I truly hope to compensate for this deficiency by explaining something about permutations and how we can employ them to pick the optimal color palette. Let’s unravel!

Image dithering: a quick recap

To recapitulate, here is a super small summary of my previous post: we exploited the Floyd-Steinberg algorithm to create an attractive representation of Quokka Quinten, despite using a 3-bit color palette only. Graphically, it turned out to look like this:

Full vs. 3-bit vs. 3-bit dithered Quokka Quinten. How cool!

It is without doubt that the dithering algorithm provides a way to immensly improve on the plain 3-bit representation. Especially when looking superficially, the result is quite dazzling! However, taking a closer look reveals considerable artefacts and we can even see some green and red dots. A possible solution is to expand our color palette to for example 6-bit, which means being able to choose from 2⁶ = 64 colors. It should be no surprise that we substantially ameliorate the image, since we have eight times as much colors to our disposal. Since a picture says a thousands words, here is the story depicted graphically:

3-bit dithered vs. 6-bit dithered

It goes without saying that using increasingly extensive color palettes would yield increasingly pretty images as well, but it won’t surprise you that it comes at certain costs (e.g., computation times, data storage). Well, sounds like we have come across an interesting trade-off! One possible strategy is to just eyeball some images that are dithered using different-sized color palettes, look at their storage size and decide on the optimal number of colors to use. There certainly is a better — and most important: statistically more sound — way to tackle this problem. For this we exploit a basic understanding of three concepts: loss function, permutation and an objective criterion for ‘costs’ — the Gap statistic.

Composing a loss function

The first thing that pops up in mind when we talk about any optimization problem, is the notion of a loss function. One of the most well-known loss functions in machine learning is the Mean Squared Error (MSE) for regression problems and Cross Entropy for classification tasks. For the Floyd-Steinberg algorithm we need can’t use those existing functions, so we have to be a little bit more creative. Brace yourselves…

Let R be the set of row indicators of an image (except the first row) and C be the set of column indicators (except the first and last column). The diffused error eᵢⱼ for pixel xᵢⱼ can now be defined as

with 1(ij) indicator functions for either the rows (R) or columns (C) and cₖ a particular color from the K color palette. Now, with the diffused error eᵢⱼ made explicit, we define ĉₖᵢⱼ as the corresponding color to pixel xᵢⱼ that minimizes the Euclidean norm of eᵢⱼ. In formula:

If you don’t follow the math, don’t worry! So far, we only wrote down in a fancy way that ĉₖᵢⱼ is the nearest color in the color palette for pixel xᵢⱼ. This formalisation, together with the fact that we can use ĉₖᵢⱼ instead of cₖ in the formula for eᵢⱼ, yields our loss function:

with X representing the set of all pixels and Cₖ a K×3 matrix, where in each row one of the K color vectors is stored. In other words, the total loss is defined as the sum of squared errors!

Alright, let’s repose for now and let the math sink in… Time to turn our heads to a somewhat more digestable topic: permutation.

Permutation

In a global sense, permutations are (random) rearrangements of objects, and are widely used in statistics to perform for example significance tests. Now, within this specific image dithering context, we may assume Quokka Quinten to be a random rearrangement of pixels. This results in a rather noisy picture:

Permuted version of the Quokka Quinten image.

The reason that such a picture might be useful, is that it serves as another tool in formalizing the optimization as a statistically well-defined problem. Suppose we refer to this random collection of pixels as the null hypothesis (H₀). Under this assumption, our sparkling picture of Quinten is just as likely as all other N! permuted versions of the picture, with N the number of pixels. We can also apply the Floyd-Steinberg algorithm on a permuted picture under H₀ for any color palette of our choice and calculate the value of the loss function. By repeating this process hundreds of times and averaging the results, we obtain an estimate of the average loss-value, or as statisticians like to say: we get an estimate of the expected loss under H₀. Now we are really getting somewhere, so let’s complete our puzzle by putting the final missing piece in place!

The Gap statistic

Permutation allowed us to obtain an estimates of the expected loss under H₀ for the different color palettes. The crux of the matter lies in the comparison of this expected losses with the loss values for our observed picture of Quokka Quinten. It should be of no surprise that the loss values will decrease for larger K (remember, K was the number of colors in our palette), but this is not necessarily true for the difference between the expected loss and the observed loss. It is exactly this difference that defines the Gap statistic:

Choosing the optimal color palette

With this Gap statistic, the problem of choosing the optimal number of colors in our palette can be formulated as the value of K that maximizes this Gap statistic:

The only thing that is left is to visualize the results by plotting the loss values and Gap statistics against the number of colors in our palette. The picture below shows the idea. We clearly see the decreasing trend for the loss values (left pane), and a nonlinear curve for the Gap statistic. Apparently, the Floyd-Steinberg dithering algorithm represents structured pictures such as our Quokka Quinten far better than random rearrangements of the same pixels.

Pfieuw… It has been a though journey to a reformulate our problem such that we were able to choose the optimal number of colors. I sincerely hope it did not distract from the fascinating way in which we can put statistics to work and help us solve complicated problems!

Geek Culture

Proud to geek out.

Sign up for Geek Culture Hits

By Geek Culture

Subscribe to receive top 10 most read stories of Geek Culture — delivered straight into your inbox, once a week. Take a look.

By signing up, you will create a Medium account if you don’t already have one. Review our Privacy Policy for more information about our privacy practices.

Check your inbox
Medium sent you an email at to complete your subscription.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store