YOGA - A Handmade Lossless
Image Compression Format

YOGA is a lossless raster graphics file format written in C++ as a single header file, made solely by me in 2023. I decided to make it as an exercise for to learn how compression and decompression works, with the express goal of being fast while keeping a similar compression ratio compared to PNG.

The results are quite impressive. YOGA is on average 5-10x faster when encoding and about 1.2-2x faster decoding than LIBPNG while keeping a similar compression ratio. Where YOGA shines is compression of larger, detailed images with realistic lighting like photographs and renders where it's not only faster but also creates about 30% smaller images. It performs much more poorly on small images like icons and flat-shaded art however. All of the data and more can be found in the results section.

When I was researching the topic I found it difficult to find clear and concise explanations of how to implement compression and decompression algorithms in a practical way. While there's plenty of resources available on how e.g. Huffman coding works on a theoretical level there's not as much freely available material for programmers who want to make something useful out of it. For that reason I decided to write this article about the steps I took to provide the material I wish I would've had when making it.

Before we begin, it's incredibly useful to know as much as possible about the data we want to compress. Uncompressed images come in a variety of colour depths, typically 4-12 bits of colour data in 1-4 channels, with each channel value together in memory as a "pixel". Images using floating point values do exist, but they're usually reserved for image editing, rendering or specific purposes like HDR photography.

Since memory is 1-dimensional, image data stored there is too. Most image formats store pixels in rows, typically starting from the top (others do it in blocks, chunks). Some image formats like BMP allow negative heights to tell the image reader that the rows are stores from the bottom up.

YOGA is limited to a maximum of 8 bits per colour channel and 4 channels total, but thanks to the compression technique we're using we get the implementation of lower colour depths and fewer channels for free! The width and height will be stored in int32's which is still enough to support a terapixel-sized image but we will limit the total size to 2 GiB for a compressed image since all the functions are single-threaded and it would make more sense to combine multiple images on different threads if you need larger images.

A common approach to compress images is by converting the red, green and blue colours (RGB) to a different colour space and discarding information that the human eye is less sensitive to, called chroma subsampling. There are however several colour transformations that translate back to RGB exactly, keeping the compression lossless, while still allowing the data to be more compressible by reducing randomness.

To write the library we will begin with a colourfully diverse image known as kodim23 from the Kodak Lossless True Colour Image Suite. The single line of black pixels at the bottom has been removed but it's otherwise unedited.

Our first task is to read the PNG image, but for this we will use a library such as stb_image, lodepng, libpng etc. Whichever one we choose we write the data to a struct like this:

Once the image is loaded we can convert it to a more compressible format. The one that will be discussed here is YCoCg-R. This colour model separate the brightness (Y) of each pixel into an 8-bit unsigned channel and the colour data into two 9-bit signed channels; chroma orange (Co) and chroma green (Cg). (This is where the name "YOGA" comes from, since we're adding an alpha A channel to this). The conversion is losslessly reversible and can be done quickly with the following simple operations:

With YCoCgR_To_RGB we can generate the entire colour space for each value of Y. Since we are masking the values the pattern repeats for combinations of YCoCg that couldn't be generated by RGB_To_YCoCgR.

Another reason why we pick YCoCg-R is because it has a very fast conversion that can be done with simple integer math. The fact that we end up with more bits than RGB is okay because the final result is still likely have a lot less entropy and be better compressed. To verify this there is a method that scales linearly with the image size to analyse the total entropy of the image. Let's start by separating the RBG into its component channels into a struct like this:

Next we create a struct to gather occurrence statistics for each possible value of the colours into an array that will allow us to plot them.

You can still make out a lot of details for each colour channel as they also encode the colour brightness. This can be seen in the chart as a wide spectrum with low peaks which clues us in on a high entropy. Now let's compare it to the YCoCg-R channels:

Nearly all the contrast is preserved in the brightness channel and if we compare the Y chart with the RGB chart it almost looks like a superposition of the RGB values. The CoCg channels are a lot less uniform, with high peaks and low valleys. The contrast that does remain in CoCg is located in sharp colour transitions like the yellow and blue feathers of the left parrot.

Another thing noticeable about the data in all channels is that in the general case the difference in colour between two adjacent pixels is low. By storing the value difference Δ between pixels in sequence, i.e. the velocity of change, we can most likely reduce the entropy of the data and improve compression rates. If we do that for the original RGB and the converted YCoCg-R data and plot it logarithmically we get these two charts:

The first thing we notice is that we now have very clear and defined peaks around zero, rapidly decreasing towards the edges. We can also clearly see that the average value distribution in ΔCo and ΔCg is significantly smaller than their RGB counterparts while the ΔY channel is about the same.

Thanks to this analysis, we can see that ΔYCoCg-R is a good choice to compress this specific image. But for other images or even other data types like audio or joint animation transforms it might be more beneficial to represent the data as a second-order difference, a.k.a. the acceleration of change. Perhaps the data benefits more from another method like dictionary encoding or even keeping the data in its raw format. If we could quantify the compressibility of the data in different representations, we could choose from any number of implementations for any given input. That's where entropy analysis comes in!

Before we continue, we should define what entropy actually is. Entropy is a measure of how disordered a system is, and in our case it's a measure of the likelyhood that we can successfully predict the next value in a fixed data set. For example, if all the values in our set are the same, there is no entropy because we can successfully guess the value for every position without fail. If all the values are completely random then the entropy is at its maximum since every guess has the same chance of being correct as a dice-roll.

Note that the entropy value of an image isn't related to the quality of it. It also doesn't affect the uncompressed size of the image in any way.

For a data set with known possible values (e.g. 0 to 255) we can calculate a normalised value for entropy H. This is done by first calculating the information value I of an event E, defined as I(E) = -log(P(E)). The probability of an event P(E) gives the information 1 when it is entirely expected. For example when tossing a coin with a 50% chance of either heads or tails, each toss is given by P(E) = 1/2. Because there's two possible values for the coin, the logarithmic base is log₂ and as we can see -log₂(1/2) = 1. Similarly for a perfect six sided die we get -log₆(1/6) = 1. For a 256-sided die we get log₂₅₆(1/256) = 1 etc. and now you see where we're going with this. Due to the "change of base" formula we can also rewrite log₂₅₆(x) = log₂(x)/8.

If we want to measure the given information G of a possible event E_n we take the information value for that event multiplied by the probability of that event: G(E_n) = I(E_n)*P(E_n). To calculate the total amount of entropy H we sum up the given information of each possible event H = Sum_n(G(E_n)). For a perfect coin we get H = 1/2 + 1/2 = 1, the coin is maximally entropic!

If we instead imagine an uneven coin with probabilities of 0.6 and 0.4 (the sum of all probabilities should also equal one) we instead find
H = -log₂(0.6)*0.6 + (-log₂(0.4)*0.4) = 0.97
meaning the coin isn't completely entropic. Similarly for a 99% heads 1% tails coin we find an entropy value of 0.08 and as expected H approaches zero the less random the set of probabilities is.

Let's analyse it for a single value in a single channel. In the image there are 768 * 511 = 392448 pixels and the number of pixels with the value 123 in the red channel is 1768. Therefore the given information of finding a red pixel with that value can be found like this:

Repeat that for all values that red can take (0-255) and sum them and we find the entropy value H for the red channel to be 0.933! Let's now take a look at all of the representations of the image data we've talked about so far:

In this chart we can see that the RGB channels all have a pretty high entropy, similar to Y, while CoCg are markedly lower with an average reduction in entropy of 10%. We also see that by converting the data to be the difference from the last pixel we get a drastic average reduction of nearly 42% but ΔYCoCg-R still finishes well on top with a 55% average reduction. We could repeat this analysis for other colour models or data representations we'd like to support and pick the one that gives the lowest entropy value, but among these representations we can be confident that we've chosen the lowest one.

In any single channel we can infer that the pixels that are close to each other are statistically likely to be the same or nearly the same colour. Think of it like "repeat the previous value once again", or twice, or a thousand times. This is especially true after representing the colour as the difference in value from the previous. When we represent the data as copies or variations of previous data for a set length we call this "runlength encoding" or "RLE".

Here the concept of a "colour value" can be blurred. For example we can consider a repeat value as a new colour value 256. If we repeat it twice that can also be a new value 257. Since the channel value doesn't represent the colour directly anymore we will start calling them codes instead and we call this method "fixed-code" (FC) RLE.

However we immediately see the problem if we would have a unique code when there's many variations of lengths for the repetitions. For large images there might even be more unique codes for RLE than there are colours! Instead we can use a single code as a mark to do a repetition followed by a count. This is called "fixed-length" (FL) RLE.

The issue with fixed-length is of course that you have to tack the count on afterwards and we might end up with more bits in the end than we saved. We have to again analyse our data to optimise the number of codes we dedicate to FC and FL. We do that quite simply by going through each pixel value and comparing it to the last. We can already store the result of this analysis in the data to speed up encoding later.

In the graph above we can see that most of the duplicate runs here are very short. In fact out of 70040 duplicate runs, 57% (40141) of them only run for a single pixel and 81% runs once or twice. Comparatively there is only two instances of 39 duplicate runs in the Co channel.

We also note that it takes a minimum of 6 bits to represent the value 39 plus the code for FL RLE. But we could also use the codes for 20 and 19 or even 10, 10 and 19 and choose the smallest combination of codes. It's not immediately clear what the optimal choice is here because we don't yet know how long the codes might be, but what is clear is that since the 39 duplicate run only happens twice, it literally doesn't matter which encoding we pick for it.

Let's now imagine a different scenario and take this image of my dog. We run it through the same program and plot the alpha channel:

Compared to the previous example this data is very noisy and can take 441 possible values, for that reason it's probably best to use FL RLE here. In practice however, it's usually better to use some kind of mix of both.

At this point we start to make some assumptions about our data, because it's too expensive to analyse every possible permutation to find the most optimal compression settings. Because we have to store the meaning of every code in the file later, we want to limit the number of them. For that reason, say that if we find more than 31 RLE values we add a FL RLE, everything else will be a FC RLE. That now means that the 32nd code, the FL code, can start from the lowest value it needs to represent!

We can develop this further to squeeze out some extra bits when compressing, but it's highly dependent on the source data and most likely not worth it for images.

After we've reduced the entropy in the data as much as possible it's time to pick a compression algorithm to encode it. For this purpose we will use Huffman coding to build a binary tree representation of the data using the occurrence counts. Such a tree is a type of multiply linked list a.k.a. a binary tree, where traversal is done by choosing one of two possible paths from the root. Each entry in the list is called a node and each link can either be a branch to another node or it can be the value represented by the code (also known as a "leaf").

In the image above we can see the possible node constructs to encode the letters A, B, C, D and E in a theoretical tree. In this example we could encode the letter A as a single bit 0b1. From there it follows that the codes for B, C, D and E are 0b110, 0b010, 0b100 and 0b000 respectively. Note that for any given code that isn't A the first bit must be zero since if it wasn't the decoder couldn't tell the difference between an A and a path through the tree. If you are unfamiliar with Huffman coding I can recommend this primer by Tom Scott.

A Huffman tree is constructed starting at the lowest weighted end towards the root, weight in our example meaning number of occurances. In each step we are finding the possible step that gives the lowest total weight sum of the tree until all the values are included. The process of creating the tree is therefore as follows:

For the case where we have full knowledge of the value set and probability distribution we are guaranteed that each code is given the optimal bit length representation for compression. To store these codes and code-lengths we can add them to our previously-made struct

We will also write a TFLI_YOGA_Node struct that will easily allow us to represent the data as a binary tree. Here we will have a TFLI_YOGA_Node for each side as well as the combined_weight which is the sum of the occurrences of the values in the node including all of the child nodes. The simplest approach to create the codes later would be by reading the tree from each end back to the root so we store the parent as well. Lastly it could be a good idea to include which index in the TFLI_YOGA_Occurrences array an end value is referring to if we haven't sorted it back to value order yet when writing the codes.

With all that said we write this:

Assuming we have at least two values in the channel, we create the first node. As the list is sorted by occurrences they are easy to find at the end of the list and as we continue we'll step backwards until we reach the root index.

I'm calling this a NEW node as we're creating a free-standing node with two ends. The two other types are called TIE to tie two free nodes together and to BUILD an end/branch combination.

After we construct the first node we need to find if a NEW, TIE or BUILD node yields the smallest occurrence sum for the tree. Note that depending on the number of free standing nodes or list entries left not every combination will be possible.

We construct the TIE and BUILD like this:

This process is repeated until we run out of value entries and free standing nodes. The last consideration to mention is that when sums are equal the priority order is NEW, TIE and BUILD in that order.

Once the entire tree is constructed we generate the codes with a simple loop finding each end and stepping backwards until we reach the root.

There's several methods to decode a bit-stream. The simplest method would be to simply traverse the tree bit-by-bit and it's not a bad option as it only requires as much memory as the tree needs and performs reasonably well, but we can do better.

The fastest method is using a lookup-table (LUT) but there is two significant problems with this method. First we need to read or generate this table and store it somewhere. Second we need to ensure we don't stall the CPU by reading from slow memory. The fastest memory accessible by the CPU is the L1 cache and it varies in size but by far the most common size in modern CPUs is at least 32 KiB.

We don't want to store a large LUT in the file itself as it could take up the large part of the file size. At the same time generating it might take more time than it's worth. Reading from a large LUT could also involve so many cache-misses that the performance benefit of using it is almost if not entirely void. The solution therefore is to limit the size and use bit-traversal as an alternative for long codes.

Huffman codes are binary and come only in powers of two so if we keep within the assumed minimum L1 cache size while leaving some headroom we are left with subdividing either 16 KiB for the 1, 2 and 4 channel case or 24 KiB for the 3 channel case. Since we're at liberty to choose the table size we can dynamically scale it down for small images and for larger images it will represent a very small part of the total size (less than 1% for a 2.5 MiB file for the full 24 KiB case).

Using this information we can optimise the use of the table. The largest table size case is 16 KiB for a single channel meaning the longest code we would need to assign to a table is 14 bits long which is representable by 4 bits in the lookup value. We also know each value is represented by a maximum of 9 bits for the Co and Cg channels totalling 13 bits. Depending on what type of data we're encoding we might want to use a 32-bit integer for our LUT to ensure that we have enough room for runlength counts and node indices as we will see we only need 16-bit integers here leaving 3 bits for other purposes.

Firstly we only have data encoded as either YCoCg-R or runlengths, so we assign one bit for this purpose. Secondly we have exactly two processes for reading the data; the LUT and the nodes, so the second bit is assigned for that. The remaining bit we don't have a specific use for at this time, so we will add it to the value bits totalling 10 meaning we can use runlength counts up to 1024 repetitions.

Note however that when we are reading from the nodes we can use the full remaining 15 bits for the offset as we know the bit-length of the table and we know we need to read at minimum another bit to find the right side of the node to read from, meaning we don't need to know if the value is a direct value or a runlength until we reach the end. Given all that, this is how the values in the LUT will be formatted:

Most of the node data we needed to create our codes is useless when decoding so this struct can also be simplified. We only need to know if the node data is a branch or end value and we need to know that value. The value again can be either the colour data or runlength so the node struct and format are made like this:

To give a practical example of how this process works let's imagine we already have the YOGA file ready for decoding. we would grab the int16_t* lookup_table for the channel and try to decode a bit stream:

We find that table_value = -32704 = 0b1000'0000'0100'0000, so this indicates that we should jump to the node at offset 64

Now all that's left to do is repeat until we find the final value

If instead the value would have been read directly from the table we would decode it like this

We've finally gone over everything needed to write the file so all that's left is doing the work. The YOGA header is defined like this:

Most of these are self-explanatory and we won't go into them further but you might wonder why we only have a single TFLI_YOGA_File_Node* pointer instead of one per channel. The reason is that we will only be storing the parts of the tree that doesn't fit into the LUT, basically pruning the tree into multiple smaller ones for which we store the offset.

To start writing the LUT and nodes we need to know which list entries have codes that exceed the LUT in length, a process as simple as this is enough with our limited value range

Since every code is unique we can safely write to the table without doing any collision checks. Entries that fit into the table can be much shorter so for these we need to write duplicates into the table. For example say that we have a 4-bit code 0b1001 and we're writing it into a 6-bit wide table. When reading the bit-stream we're reading 6 bits for the lookup so for a 4-bit code we need to get the same result for every variation, i.e. 0b00'1001, 0b01'1001, 0b10'1001, 0b11'1001. The code for this could look something like this:

In the case that the length and width are the same we simply write the value into position instead. That leaves the codes that are too long for the table and since we already have the list of them we can find what entry points we need to write to the table. With the number of exceeded code lengths we're dealing with we don't need to bother with anything more complicated than filling in values into an array with a simple loop:

If we didn't already incorporate the runlength list into the colour value list we can do that here. The runlength flag value is part of the colour value list and has a code with a length that serves as the base of the runlength codes. We can combine these and do the same as with the colour values but in the rare case that the runlength flag code is too long for the table we need to find it among the written codes and write the entire runlength tree from that point.

We've already written flags into the channel data to make encoding straight forward so we start by making a buffer to hold the codes we want to encode. Ideally we want to get the full pixel data at once to avoid writing to the same memory multiple times so the code for each channel will follow eachother. Additionally we are assuming that no code for any value is longer than 32 bits.

If we have a runlength active we can simply skip writing and reading the colour value as we'll keep track of it when decoding. Otherwise we check for flags and write the correct code into the buffer

Once we've found the code we can add it to the buffer without no gaps using some pointer and bit arithmetic

After the codes for each channel have been put into the buffer we can finally write them to the file. The simplest option is to just write single bytes in order, shifting them if necessary and then filling in the remaining bits if there are any.

Because we know the image size before decoding we don't need any signal to stop at the end, but we don't necessarily want to end the file at the last possible byte either. If we want to load bits into a buffer using a certain size integer we can pad the file with some zeroes at the end.

We've finally gotten to the point where we can try to debug the encoded image and see if everything is working correctly. It is a good idea to start trying to decode the image even right after the first transformation to YCoCg-R as it will help with finding bugs and errors. After each added transformation (delta, runlength etc.) we add support to decode and we can try to verify these steps with a suite of test images to try to find edge-cases.

We're using a 64-bit system to decode the bit-stream so we create and fill a 64-bit buffer.

We will ensure to always have more or equal to 32 bits of data in the buffer. This way we can read the bit stream without worrying about the amount of bits left in a particular code assuming the longest code is no more than 32 bits.

In the section Implementing a look-up table we talked about the specific implementation for reading the bit-stream and every other transformation is just the same transformation in reverse. If we read a runlength value we just reuse the same value for that channel. To undo the delta transformation we keep track of the last value we found and add the decoded value. Lastly we do the YCoCg-R to RGB conversion and we're done.

We can compare the size and speed of our code to other file formats and libraries to get an objective metric of how well we've done. We will do this by comparing file size as well as encoding and decoding speed of the QOI test suite. Measuring the file size is easy enough, but we are at the mercy of the operating system when measuring the time it takes to encode and decode.

To start, we have to simply hope that the OS doesn't decide to suddenly interrupt our execution thread. Since we're not using multiple threads this shouldn't be a big issue and with enough data this factor will be minimised.

Secondly we give each library the best possible chance by reading and writing to or from memory that is already loaded with data and available. For STB Image and QOI this requires overriding their memory call macros but for STB Image Write specifically there wasn't an obvious way to do this without rewriting the library. Perhaps this is why it's performing so bad at web screenshots as those images are much larger than typical images and it probably runs into a bunch of realloc calls that requires memory to be copied.

Finally we are also relying on the OS to provide us with an accurate timer. In the benchmark source you can see that both the time and the cycle count is tracked. The cycle counts are not presented here but can be used to double check if the times seem accurate, which they are.

With all of that said, the tables show the data as measured while the graphs are presented as relative to YOGA. This is simply done to make it easier to tell the difference, for example a time value of 5 means that the library performed 5x slower than YOGA, while values below 1 indicate it being faster. All libraries use the default settings.

Here we can see that YOGA is much faster than libpng and STBI in every circumstance except small images, on average almost 7 times faster than libpng. Without looking into the implementation, there is probably more analysis of the data before compression starts and less analysis during compression, which is creating this discrepancy. QOI is blowing all other libraries out of the park though, being a factor of 5-100 times faster, almost as fast as just writing bitmap data directly.

Decoding data is much more uniform in its result between the libraries, as is expected since they all work on decoding a stream of bits using data from the header. Still YOGA is about the same if not faster in nearly every case compared to libpng and STBI, being on average 20-25% faster, but QOI is still the clear winner in terms of speed.

Perhaps the most important statistic when it comes to compression is the compression ratio. Size matters and unfortunately STBI web doesn't even fit on the graph, towering above at a ratio of 4.73 times larger than YOGA. Overall YOGA and libpng have a very similar size, with YOGA being just a fraction smaller in some practical cases like photos and textures. Overall libpng still wins overall and if you change the compression ratio to be 9 instead of the default 6 it might also be smaller for those situations.

YOGA is definitely the most complex and difficult software I have tried to write to-date. To start, I only spent about 10 hours learning theory in the same way as most computer science students would be learning it. But after that, I had to spend over 100 hours programming a working prototype before I could even export an entire file, because the compression required so many steps to get to the point where you can start decompressing it again. Then it was the nightmare of debugging the almost 3000 lines of code where every line can have a profound impact on the result. Unless you have a special interest, compression is not really a rabbit hole I would recommend but it has taught me a lot, not only about compression but also shipping code and designing an API. Creating this article about it has also been interesting albeit a lot of work on its own.

There are things I would consider to improve, especially to improve the performance of the small icons. YOGA also doesn't do any multicolour analysis at all, nor does it check if YCgCo actually makes the image more compressible. This probably explains partly why it does so well at textures and photos but not icons, for example. Another thing I've been thinking about is subdividing the image into chunks to better optimise the compression of that chunk, but that would take a complete rewrite of the library and is not something I'm interested in developing at the moment.

So for the foreseeable future I am satisfied with the performance of it and I will use it for my own projects moving forward with the satisfaction of knowing I made it completely on my own. If you have read all of this, thank you and let me know if you have any feedback!