Transcription
What we'll dive into in this video is an understanding of how PNG, one of the most commonly used image file formats, compresses images in a rather clever way such that the original image quality is perfectly preserved across all websites.
The two most commonly used image file formats are PNG and JPEG. One pretty common problem with JPEG is that some particular images can look noticeably off after compression, especially when these images have vector graphics or text. These artifacts are a result of JPEG purposely discarding information to save more space. PNG files, however, have no such problem.
One of the many themes in today's video will be about understanding PNG from the perspective of lossless compression. PNG is a really clever extension to core ideas used in a variety of text compression algorithms, specifically those found in zip files. But as ingenious as these ideas are, as we go through the algorithms, you'll notice how complex and slow they can be, especially when used on images.
Towards the end of the video, I'll also share with you an alternative to PNG that I'm almost certain most of you have never heard of. Discovered a few months ago, a new image format called QOI made the rounds in the developer community. Not only is it comparable to PNG, but it's also up to 50 times faster. There's a lot of exciting topics to cover, so let's begin.
[Music]
Imagine I gave you an image composed of red, green, and blue pixel values and asked you to compress the image into the fewest number of bits possible. A key constraint is that whatever compression method you use, it must be the case that there is a way to reverse it and get back the exact same image, same number of pixels, and each pixel corresponds one to one. How much you approach this problem?
Well, one big idea that's common in lossless compression is to exploit redundancy. Let's focus on a single channel of this image to keep things simple. In this particular channel, some pixel values are more common than others, and maybe we can take advantage of that by representing them with fewer bits than less frequent pixels.
The most common scheme to generate a set of codes where fewer bits are allocated to more frequent data is Huffman codes. For those of you who aren't familiar with Huffman codes, we can take each pixel independently and find the frequencies of the pixel within the image. We sort these frequencies in increasing order. We can build what's called a Huffman tree by taking the two least frequent pixels and then connecting them to a node with their sum. We put this back in our set and repeat the process until we get through all the values. At the end, this tree gives us the codes for each pixel value. Every time we go left in the tree, we add a zero to the code, and every time we go right, we add a one. The key idea here is that the most frequently used pixels are higher up in the tree, leading to a smaller bit representation. Our original image had four pixel values, so a standard bit representation of these values would have taken 2 bits per pixel. By using Huffman codes, we've now compressed our image to 1.89 bits per pixel.
[Music]
But note, these savings are slightly misleading because for us to actually get back the original image, a Huffman decoder has to know the codes we used. We need to store some version of this tree, which makes Huffman coding generally wasteful for smaller images. But for larger sets of data, Huffman coding can be a good choice. PNG, by the way, does use Huffman coding, but not exactly the way I described. We'll come back to this point a little bit later, so keep Huffman coding in the back of your mind and let's explore some other options.
One thing that's not so appealing about Huffman codes is they essentially treat pixels on an image as independent of each other. But in real images, redundancy also happens across sequences of pixels. For example, pixels neighboring each other are likely to be similar in value.
One simple compression scheme that takes advantage of repetitive neighboring pixels is run-length encoding. The basic premise of run-length encoding involves compressing a sequence of similar pixel values as the pixel value and the number of continuous occurrences of that value. In images where a lot of the pixels along the row have the same color, run-length encoding can be quite effective. But again, it's not too hard to define an image with a lot of repetitive data where run-length encoding doesn't really perform well. The aspect that makes this image more tricky to compress is that the redundancy happens across a sequence of two pixels. Run-length encoding doesn't handle that well.
When we start looking at repetition across sequences, there's a lot of powerful tools in the world of text compression that better handle it. If you think about text snippets in general, the redundancy will often occur as a result of using the same words or the same phrases. A class of algorithms that are better tailored to handling repetitions of sequences are Lempel-Ziv schemes, named after the two original authors of the first paper introducing the basic version of the idea. The algorithm used frequently in zip files and PNG is a more efficient version of the original author's scheme called LZSS, which is what we're going to focus on today.
The basic idea of LZSS involves back-referencing. On a high level, if I have some text and I see a sequence of characters that appeared earlier in the text, I could possibly save some space by referencing that earlier sequence instead of outputting the same sequence of characters. It's best understood with an example. Suppose we had the following set of texts that we want to compress.
There's a few important terms to be aware of when understanding LZSS. We must define a sliding window and a lookahead buffer, both of which are given a specific size. The lookahead buffer can be thought of as the characters LZSS tries to create a back-reference for. A natural question is, where does it look for a match of characters that I can reference later? That's where the search buffer comes in. The search buffer will be the difference between the sliding window size and the lookahead buffer size, and this is where LZSS will store processed characters to find a match.
At the start of the algorithm, the search buffer is empty. The sliding window encompasses the entire search buffer and the lookahead buffer. At the start of LZSS, we consider just the look-ahead characters. Since we haven't seen the first character, we'll just encode it as the character 'R'. Now that we've processed the character, we move it to the search buffer, which contains previously encoded characters. We go through the first few characters in a similar manner. Since we've never seen them before.
Now, where this gets interesting is when we reach the second instance of the character 'E'. The compressor looks for the largest string in the lookahead buffer that matches text in the current sliding window, and it finds a match for the character 'E'. So, the big idea in LZSS is we can encode this character as an offset and a length. The original 'E' was found two characters back, so that's our offset, and the length of the match is going to be one. We can now move the second instance of 'E' into the search buffer and proceed. We encode the letter 'T', the letter 'I', and then we hit our next interesting case. In our lookahead buffer, we have the character 'T', but the key aspect of this class of algorithms is it tries to find the longest string it can match with anything in our sliding window. Notice that the string 'TI' has been seen before, and that's the longest match. So we can output an offset of 2 and a length of 2. We then pass these two characters into the search buffer and continue encoding. We encode the letter 'V' as is, and then use a back-reference to the letter 'E'. The space is processed normally, and then we hit another 'R'. What's the longest match in the lookahead buffer? In this case, we can actually match four characters here. This allows us to output a back-reference with offset 11 and a length four. We then move these four characters into the search buffer, and one thing I want you to notice is we actually get rid of the four characters from the beginning to keep the sliding window length constant.
[Music]
The last couple of steps involves encoding the character 'A' as is, and finally the character 'T' as a back-reference. A final encoding is the following sequence of characters and offset-length pairs. Decoding this is not too tricky. We simply output characters as we see them, and anytime we encounter an offset-length pair, we go back into our current decoded string by the offset and output characters as defined by the length. We continue until we process all characters and offset-length pairs. Seeing this in action confirms that this entire scheme does not lose any information. The decoder can completely reconstruct the original data.
This is the core of LZSS, but there are a few important points worth emphasizing. In the world of compression, the devil really is in the details. The search buffer size and lookahead buffer size we chose has a direct impact on compression. A good way to see that is by taking a look at this step in our encoding. Because of how we define the sliding window, we can output a really nice back-reference of length 4. But suppose we decreased the search buffer size by 1. We're now a little unlucky and can't make a back-reference to the sequence because the character 'R' had just moved out of the search buffer.
In practice, LZSS as implemented by PNG and other zip file tools generally define a sliding window length of 32 kilobytes. We also define a lookahead buffer of 258 bytes. Another subtle detail that's important in LZSS involves the way it allows for defining offset-length pairs. Suppose we had the task of encoding the following set of characters with these defined parameters. How do you think LZSS will encode it? The actual answer may surprise you, and it's important enough to show.
We start by outputting the first five characters normally, and then in our lookahead buffer, we have the characters 'D', 'E', 'D', 'E'. How we identify matches in LZSS is by looking for the starting character in our search buffer. But a somewhat counter-intuitive feature is that the end of this match can actually be in the lookahead buffer. So, in this particular scenario, we can actually output an offset of 2 and a length of 4. It looks weird to have a length greater than the offset, but seeing how LZSS decodes it should convince you that this works perfectly fine. After we output our individual characters, we decode the back-reference by going back two characters and then copying over the next four characters. The first two characters copy over as we've seen before. Now, we still need two more characters, but hey, we have two characters right here. So we reference them and fill out the rest of the string. What basically happened here is we took the last four characters and generated a back-reference by using this particular set of characters, and there's nothing in LZSS that prevents you from doing that. In fact, there's a pretty cool byproduct of allowing such representations.
Take for example the following sequence of text where we just repeat a single character. LZSS will compress the sequence of text with the following representation. What's interesting about that? Well, it's essentially just run-length encoding. I think what's remarkably clever about LZSS is by designing the algorithm in this manner, we get run-length encoding for free.
A final caveat of LZSS is that in practice, the algorithm only emits a back-reference of length three or more. It turns out that more often than not, it takes more space to store offset-length pairs than it does to store two characters individually. So, in this earlier sequence, the actual LZSS encoding will only have one offset-length pair. All the other length one or two pairs end up being overkill.
Transitioning back into the world of images, PNG uses the same LZSS algorithm to take pixels from each RGB channel and represent them as a sequence of raw pixels and offset-length pairs. But there's actually more to it. In the world of text, we feel pretty comfortable with the idea that phrases and blocks of characters can be repeated. But suppose, for example, I gave you the following gradient image. Here, each pixel value is just slightly greater than its previous value. LZSS will do terrible on this image, and Huffman coding won't do much better either. So that's pretty depressing. We just spent all this time going through our two main weapons, and it only took a second for a simple example to break everything. Such is the life of engineers, right?
But at the same time, I think we intuitively feel that this image should be compressible. There is a predictable pattern here. The way PNG solves this problem involves a pre-processing step called filtering. When you have a problem that doesn't translate well to an existing approach, you have a choice to either create a new approach or transform the problem into a version that can be solved with existing solutions. PNG chooses to transform the problem in the filtering step by introducing redundancy.
In this particular image, the pattern is not too hard to see. The difference between every adjacent pixel is four. If we transform the row to store differences rather than the raw pixels, LZSS can perform significantly better. This is an example of one type of filter applied to the image. PNG goes further and defines five different types of filters. The most basic filter is simply "no filter," which is fairly self-explanatory. The filter we just showed earlier with differences between row-wise adjacent elements is an example of a "sub" filter. If we take this row and apply the "sub" filter, we get the following output.
You might notice immediately that there's some weird values that come out of this operation. For example, 134 minus 139 is equal to 251. An important point here is every filter actually operates on individual bytes, not necessarily pixels. In this example, since a pixel is 8 bits, they end up corresponding nicely. But in images where a pixel is not 8 bits, this can actually lead to quite a bit of confusion. PNG filters will always take the value from a mathematical operation on individual bytes and make sure it's in the range of representable 8-bit numbers before proceeding. This is usually done by taking the difference and applying a mod 256 operation. So, 134 minus 139 is negative 5, but taken mod 256, it's 251.
The next filter is the "up" filter. It's the same concept as the "sub" filter, but applied to the pixel immediately above the current pixel. "Up" filters work well when pixels are correlated to each other along the columns of an image. The fourth filter, called the "average" filter, is a combination of the "up" and "sub" filters. We subtract our current pixel by the average of the pixel immediately to the left and immediately above. Again, be wary that all operations are on single bytes, so anything negative will wrap around via the implicit mod operation.
The final filter PNG defines is the most intricate, and it's called the "path" filter. First, we calculate a base value equal to the sum of the corresponding bytes to the left and above minus the byte to the upper left. Then, we calculate the difference between this base value and the three pixels that we just dealt with: left, up, and upper left. We'll choose whatever pixel gives us the smallest difference. This "winner" pixel, in a sense, is the one we'll choose to finally subtract our original pixel from. The intuition here is that this process just calculates what was the best pixel to choose out of all three neighbors. Once we choose the best pixel, we perform the same operation as the other methods: subtract it from our original pixel and store that value.
In this example, we showed filtering on a grayscale image. When dealing with RGB images, these operations are done on each channel individually. This makes sure that we are not mixing up red, green, and blue values, which are probably less correlated. Also, because we are dealing with left, up, and upper left pixels, edge cases in a very literal sense do come in. What PNG filters do to gracefully handle this is to find any out-of-bounds pixel as zero.
An important question that may have crossed your mind is, how does PNG even figure out what filter to use? Well, there were a couple of initial findings that provided some guidance. In general, if you have a palette-based image using a smaller set of colors to save data, filtering usually won't create any additional redundancy. Also, remember filtering operates on individual bytes, so if the image has less than 8 bits per pixel, PNG found that "none" filters should only be used, since the overlap between pixels and a byte made it difficult to create any correlation. But on most other types of images, having some combination of filters was usually a good idea and led to better compression when taking account of how LZSS works.
But simply trying every combination is a ridiculous solution. On even a simple 240p resolution image, the number of possible filtering combinations is 5 to the power of 240. That number is more than the number of atoms in the universe. Unfortunately, you can't wait until the end of the universe to save a damn image, so we have to be smarter.
The way PNG solves this problem is by defining a heuristic to determine which filter is best for a particular row. It's called the "minimum sum of absolute differences." The actual calculation is not too difficult, but the steps involved can be confusing, so let's break it down. Suppose we take this particular row of our image and do a "sub" filter where we don't mod the final value by 256. In comparison, this particular row is a true "sub" filter after modding by 256.
Now, to calculate the sum of absolute difference metric, we're basically going to treat all values between 0 and 127 inclusive as is, and then any value greater than or equal to 128 will be remapped to a corresponding negative value, where 255 is mapped to negative 1 and 128 is mapped to negative 128. So, in our absolute sum of differences calculation, we perform this operation on the remapped filtered data. After summing the absolute value of each element in this remapped set of data, we get a score for the filter.
What PNG does to pick the best filter is perform this calculation on all five filters for each row and then pick the filter that has the minimum score. The overall intuition is that filters that map data such that the sum of absolute differences is closer to zero are more likely to have data that is actually repetitive. But truth be told, there's no real mathematical proof that this is the best heuristic to use. It turns out that no one really has found something that is as simple and performs better empirically, so this is still the heuristic that's used to this day. But who knows, maybe someone down the line will find a better method.
The advantage of using this particular heuristic is that PNG generally only has to test each filter five times on every row, which is much more tractable than a naive approach of trying all combinations of filters. On the decoding side, one nice property of these filters is that each operation is entirely reversible. No part of the filtering component loses any information.
So, putting this all together, PNG takes an uncompressed RGB image and then filters each channel of the image row-wise, picking a filter through heuristics. Then, PNG takes this filtered image and, on each channel, uses the LZSS algorithm to further compress the image. LZSS replaces previously seen sequences of filtered pixels with back-references. But there's one final step to PNG. After LZSS, we get a sequence of pixels and offset-length pairs. Since LZSS only emits back-references with length greater than or equal to three, there's still some individual pixel redundancy in the sequence that we can exploit. The last step of PNG involves taking this encoded LZSS sequence and performing a modified Huffman coding scheme to further exploit it. There are a lot of painstaking details on exactly how this is done on a sequence that contains both individual pixel values and offset-length pairs. It is surprisingly complicated.
The combination of LZSS and Huffman coding that PNG uses is often called the Deflate compression scheme. These steps essentially encompass the entire PNG file format. Every part of this approach either creates some redundancy or exploits it in a way that is perfectly reconstructible. With the fact that these methods perform better than other lossless image compression schemes, PNG is often the go-to file format when you need to retain all information.
But at the same time, if we look at the entire process from start to finish, it does feel rather complicated, right? I mean, we have all this filtering, which we actually have to do at least five times on each row, and then we have to perform LZSS, which is also computationally expensive. That's not even mentioning that this entire process has to go through Huffman coding, and trust me, that gets really complicated within the context of PNG. So, even though PNG is widely used, it is actually by far one of the slowest compression methods in practice. This is not usually a big deal, since decoding a PNG image is not too inefficient. But it does introduce an interesting question: Is there a compression scheme that's simpler and faster, yet still somewhat comparable to PNG?
And until about a few months ago, the answer would have been no. But then an image format called QOI was developed by an independent software engineer, Dominique Schrablski, and it turns out it's surprisingly close to PNG in compression ratios, but way faster. What I think is most notable about this scheme is how a simple set of rules for encoding end up making it extraordinarily fast, but also quite effective.
The best way to understand QOI is through an example image. QOI considers each channel in an image jointly in its encoding. So, let's split the image into its individual RGB values and then align them together. The speed of QOI comes from the fact that it processes every pixel just once throughout encoding. QOI will keep track of a reference to the previous pixel and the current pixel, which will continuously be updated based on the value of the previous pixel and the current pixel.
There are a couple of rules for encoding. The first rule is, if the current pixel is the same value as the previous pixel, QOI encodes it using a run-length encoding and will increment the run-length until it sees a different pixel. It encodes run-lengths in a single byte, with two bits reserved for the run-length tag. QOI will use special tags for all its encoding options to help the decoder losslessly reconstruct the original image. The other six bits encode the actual run-length value.
The second option involves storing the RGB value of the current pixel as a difference from the previous pixel. If the difference between the previously seen pixel value and the current pixel value is within a predefined constraint, we can store the current RGB pixel in a single byte of memory. Two bits will be reserved for the difference tag, and then the other six bits encode the actual difference on each channel.
QOI also has an option to encode larger differences in two bytes of memory. If the previous pixel and current pixel differences meet the following criteria, it is possible to encode the current pixel in two bytes using the following scheme. These rules may seem a bit arbitrary, but one key constraint that we're trying to maintain is having all the encoded bytes aligned. One aid in the simplicity of QOI is that the decoder can just read bytes one by one without ever having to worry about some pixels being encoded partially in one byte and then partially in another byte.
The fourth option involves encoding a pixel as an index of a previously seen pixel. As QOI processes pixels one by one, it'll store each pixel in an array. We determine the location to place the processed pixel by using a rather simple hash of the R, G, and B pixel values. So, when we encounter a new pixel, we do a simple check of the array to determine if it has been seen before, and if so, we store the index position in the array. QOI uses an array of size 64, which allows the index location to be stored in 6 bits.
And lastly, if run-length encoding is not possible, the pixel has never been encountered in our array, and the difference of a pixel is too large, we'll just store the RGB value as is in memory. Notice that we actually do take a little bit more space to store the RGB value directly because we need to notify the decoder of this choice. The hope here is that QOI will not have to output too many of these cases. And that's really the core logic. There are some minor details on bit representation and handling transparency, but it really doesn't get much simpler than this for a compression algorithm. I mean, the entire specification is just one page long. PNG specification, for comparison, is a true monster of a document.
When you run QOI on an image, the main task of the encoder is to determine the proper tag and data that it needs to generate for the decoder. This involves correctly updating the previous and current pixels and also keeping track of the index and updating it appropriately. The logic is not too complex. I really do believe you can code both an encoder and decoder without too much difficulty after reading through the spec. In fact, I highly recommend taking the time to do it as a fun exercise. It's a good way to understand how to represent compressed information.
On this particular image, after running QOI, we end up with a stream of 50 bytes. Considering the original image had 64 pixels with 3 bytes each for a total of 192 bytes, the compressed version of the image is only 26% of the original image. So, we know for sure that QOI is simpler than PNG.
But how does it actually hold up in terms of compression performance? Well, for the most part, PNG is better, but the difference between QOI and PNG is not as large as you would expect. There's a reference test suite of images with a variety of interesting features, and we actually ran the algorithm on the entire test suite to see the results. As you can tell, QOI is pretty close to PNG for a lot of these images, which is truly impressive.
And where QOI really shines is in its speed. The speed of QOI encoding, especially, is on the order of 20 to 50 times faster than PNG, mainly because QOI only has to process the pixel once, while PNG may have to process pixels several times in various stages. The decoding performance is also better than PNG, but the differences are not as drastic, since PNG decoding is generally a lot simpler than encoding.
Rather than debate which format is better, though, I really think what's cool about QOI is just the fact that this relatively simple and understandable idea was discovered so recently. The full PNG spec was developed in the mid-1990s, so the fact that something almost 30 years later came around and is even comparable to it is incredible. Dominique, the engineer who invented it, also claims that he is no expert in image formats and kind of just played around with ideas that were much simpler for the average person to understand. And I think there's a big lesson to take away from this. A lot of times on this channel, we like to go over algorithms and ideas that are really clever and complex, but sometimes solutions that are simple, or as Dominique describes them, "stupidly simple," should also be appreciated. After all, the biggest job of software engineers and computer scientists is to manage complexity. A lot of problems are really difficult and they simply need elaborate solutions, but along the way, it's easy to get lost in the complexity and design something that's perhaps a little too difficult and slow. As engineers, if we can get away with it, we should absolutely consider more simple and understandable solutions. I believe the story of QOI, when compared to PNG, is a great example of that.
In this video, we took our time diving into hands-on examples of both PNG and QOI to get a feel for how they work. One of the best ways to learn new and complex ideas is by playing around with them on your own, and a great tool for learning interactively is Brilliant, the sponsor for this video. From the basics of mathematics and algorithmic thinking to more complex ideas in deep learning and probability, Brilliant offers a variety of courses and learning paths for those interested in getting hands-on practice. Lately, I've been dabbling in their computer architecture course, which is an area that intersects fundamentally with byte representations that we talked about in this video. Visually seeing how the lower layer of computers represent information and store it in memory gave me some new perspectives on concepts I'd learned while in college. All the courses come with elegant interactive visualizations and a great set of practice problems to encourage mastery of the content.
You can get started for free by going to brilliant.org/reducible, which is linked in the description below. Brilliant is providing a special offer through this channel where the first 200 members to sign up get 20% off the annual subscription. It's a great way to learn more about the topics in these videos and also a good way to support this channel. Big thanks to Brilliant for sponsoring this video. Thanks for watching, and I'll see you all in the next one.