Optimising circular avatars

Recently, Twitter jumped upon the circular avatar train. It's bad. The worst consequence is that it chops off cat ears, of course.

But ignoring the serious issues for a moment… hey, isn't it a waste of bandwidth? The avatar images in question are in fact still square, with the circle shape being cut out on the client (e.g. with border-radius). Caclulating the area of the unit circle (r = ½), we get a = πr² = π½² ≈ 0.7854, and if we subtract that from the area of the unit square, we get 1 - a ≈ 0.2146… so about 21.46% of the avatar image is being thrown away. How inefficient! Surely, this must cost Twitter millions.

Personally, I don't care about what makes imaginary Twitter investors miserable, because it's a really badly run company. However, reducing the bandwidth impact also sounds like a fun technical challenge to solve. So let's get to it!

The first thing to know about Twitter avatars is that they are almost always JPEGs. Twitter rather aggresively assumes that JPEG is a suitable image format for everything opaque, despite the fact that it is a fairly poor choice for certain categories of images. Normally I'd complain about this, but in this case it means that I only have to worry about one image format for this experiment, and it's one I find interesting (JPEG), rather than a glorified gzipped bitmap (PNG), so I'm actually happy!

The second thing to know is that JPEGs are divided into a grid of tiny squares known as “blocks”, typically 8×8 or 16×16 pixels in size, as part of the encoding process. Those blocks of pixels are then mathemagicked through the Discrete Cosine Transform into vectors of numbers by which you can multiply and sum sine waves to get back the orignal pixels, sort of. It's very fancy.

Why have I brought this up? Well, let's look at the most obvious way to remove the image data outside the circle, namely selecting the parts of the image outside the circle and replacing them with a flat colour, say black. For instance, let's take my current avatar, Takamachi Nanoha as depicted in Magical Girl Lyrical Nanoha A's:

If we open it up in the GNU Image Manipulation Program, make a circle selection, invert it, and fill in the area with black, we get this:

This worked out fine, right? Well, mostly. It's certainly smaller, at 29.3KiB versus the original's 32.4KiB. But I'm not quite happy with it.

For one thing, the fine detail of the sharp circular edge can potentially add more information to the image. While the flat areas of colour we create obviously contain almost no information at all, the blocks where the edge of the circle is might now be more detailed, and so take up more space in the JPEG and result in a file size that's not as small as we'd like.

For another thing, sharp edges like this don't usually look good in JPEGs, because of chroma subsampling, which essentially means that JPEGs store the brightness and colour of pixels at different resolutions since the human eye is bad at seeing colour but good at seeing brightness. When there's a sharp edge in a JPEG where the colour and brightness change at the same time, it creates an ugly fringing effect. It's normally quite subtle, but it's made worse here by our next point.

Browsers also create a problem here, because while you cut out one circle in the image editor, the browser will then cut out an ever-so-slightly different circle. That slight difference makes for a nasty fringe around the edge of the image. So while you wanted this:

What you actually get is this:

Note the ugly fringe around the edges, particularly at the bottom-right. That's the combined effect of JPEG's chroma subsampling muddying the edges, and the browser I was using cutting out a slightly different circle.

Finally, there's another vital issue with the obvious way of removing the image data outside the circle: it's boring! Anyone can use an image editor. But that's no fun. I have a more interesting solution.

So, remember how I mentioned earlier that JPEG divides images into blocks? Well, if we operate on a block level, rather than a pixel level, we can potentially solve all these issues! If we only remove whole blocks, chroma subsampling is no longer an issue, because it doesn't operate at block boundaries, only within blocks, so the edges stay clean. It also means that from the perspective of JPEG, there's no fine detail created that might increase the amount of data used by the blocks at the circle edges, because we're not changing the contents of blocks except to get rid of them. The problem of the browser cutting out a slightly different circle is mostly solved, too, because blocks are large enough that there'll be a few pixels around the edge of the circle that aren't removed, giving a little bit of breathing room with respect to where the circle is drawn. And most importantly, removing blocks is something I can write a program to do, so it's more interesting!

The first thing to do is to grab a copy of the JPEG specification. Unfortunately, it's a paid-for standard. But it just so happens that there's a copy on the W3C's website. I've no idea if they have permission to host it there, but that's not my problem!

The second thing to do is to write some bad C code based on that specification to parse our avatar JPEG file and blank out the blocks outside the circle. Luckily, I have extensive experience in writing bad C code.

So, I write some bad C code to parse a JPEG. It turns out JPEGs have a programmer-friendly internal structure! They're made up of “marker segments” that begin with a prefix (the “marker”) and 2-byte integer containing the length of the segment in bytes. Because each segment mentions its length at the beginning, it's trivial to skip over the segments we're not interested in. I do just that, and…

…well. It turns out that JPEG's elegant marker segment structure doesn't apply to the actual meat of the file, the actual image data. This is especially true for (the somehow non-oxymoronic concept of) interlaced progressive JPEGs like, say, Twitter avatars. So my naïve JPEG parser just blows up when it gets to that point. That could be fixed, but then there's the problem of trying to comprehend the terse, scattered and abstract specification's description of scan encoding. I could go through the full tedium of decoding the cryptic wonders of the spec, but I want to actually finish this blog post.

What is to be done, then? Well, there's actually a much easier way of implementing this: edit the image as a bitmap and simply black out the aforementioned whole 16×16 blocks. All that's needed is a simple image processing library.

But wait, you might ask, wouldn't loading the original JPEG, editing it, then exporting the result back to JPEG surely reduce its quality? JPEG is a lossy format, right?

You wouldn't be quite wrong. The JPEG encoding process discards various kinds of information. However, for a given quality setting, JPEG encoding is actually an idempotent operation! JPEG does not inherently degrade the quality of an image; encoding an image as a JPEG discards a certain level of fine detail, but if that fine detail has already been removed (by, say, a previous JPEG encoding pass), there is nothing to remove, and so further repeated JPEG encoding at the same or higher quality level will not reduce quality.

Therefore, some horrible PHP image manipulation code later, and we have our circular avatar with blacked-out blocks:

Not exactly beautiful, but it's small! At 28,205 bytes, this second attempt is smaller than the original 32,425-byte square avatar and the 29,310-byte clean black circle avatar from earlier. Okay, this isn't quite a fair contest, because this file lacks the colour profile data of the original avatar or the clean circle version… but even if we strip that data from both of those (magick in.jpg -strip -interlace JPEG -quality 85 out.jpg), they only come to 31,751 and 28,714 bytes respectively: the blacked-out-blocks approach is still more efficient!

But that's not all. As hoped, this approach does yield a clean edge when the browser cuts out the circle:

Success!

So, to conclude:

I hope you enjoyed reading this as much as I enjoyed writing it. I actually began this post on 2017-06-21, but JPEG specifications and more important concerns got in my way. I'm glad to have finally gotten it done. ^^