How PNG Works: Compromising Speed for Quality

Chapters:
0:00 Introduction
1:35 Exploiting redundancy
2:09 Huffman Codes
4:22 Run Length Encoding
5:23 Lempel-Ziv Schemes (LZSS)
13:50 Transforming the problem
14:36 Filtering
17:46 How PNG Picks Filters
18:58 Heuristics for Filtering
21:06 PNG Encoding/Decoding
23:04 The Compromise: PNG Is Slow
23:31 Quite OK Image (QOI) Format
28:26 Benchmark Results
29:27 Final Thoughts
30:36 Brilliant Sponsorship

Developed in the mid 1990's, the PNG encoding standard for images is now the most used image format on the web. One aspect that makes PNG quite attractive for users is image quality is perfectly preserved as a result of lossless compression. In this video, we dive into how exactly PNG is able to compress images so well, while also retaining all the information in the image.

One thing we discover during this journey is how slow PNG is in practice. Towards the end, we discuss a relatively new image format called QOI that is somewhat comparable to PNG, but 20-50x faster. But what's perhaps the most remarkable aspect of QOI is how a simple set of rules lead to surprisingly good compression on a variety of images.

Animations created jointly by Nipun Ramakrishnan and Jesús Rascón.

*Minor error in QOI section: QOI_DIFF_SMALL should have a tag of 01 not 10 (QOI_DIFF_MED has the tag 10.*

References:

This video wouldn't be possible without the open source library manim created by 3blue1brown and maintained by Manim Community.

Music in this video comes from Jesús Rascón, Aaskash Gandhi, and Myuu.

Socials:

Big thanks to the community of Patreons that support this channel. Special thanks to the following Patreons:
Andreas
Adam Dřínek
Burt Humburg
Matt Q
Winston Durand
Andjela Arsic
Mutual Information
Richard Wells
Sebastian Gamboa
Zac Landis

[WilliamDye-willdye]

Congrats to the coder for coming up with QOI. In a world increasingly filled with code created by large teams, it's great to know there's still room for a lone outsider to wander in a come up with a cool hack.

[Cubinator]

Came to see the PNG stuff, but was totally blown away by the QOI stuff. Such a simple algorithm! Very impressive! Can't wait for Gimp and Web support for this format.

[wulfshade]

One thing to note about QOI is that because it is so simple and byte aligned it can be further compressed by other, general purpose compressors.
Basically, the same image might give you a 5mb PNG and 6mb QOI, but chucking them bove into a ZIP, the PNG stays 5mb while the QOI further shrinks to 4mb.
Though it will lose a lot of its speed advantage.

[Imperial_Squid]

Making a QOI encoder/decoder sounds like a fantastic introductory project for people learning to code, it's simple but gets down into the bytes, the logic is simple but incredibly effective and it shows how the field of comp sci is never "done" despite so many of the algorithms we learn about being decades old! Fabulous video about a great topic!!

[fraetor]

Interestingly you can actually get almost twice the performance of QOI with PNG while getting slightly smaller files with a speed specialised encoder such as fpng or fpnge, and still be decodable by all existing PNG decoders. fpnge was written by a single person in a weekend back in January 2022.
The real benefit of QOI is that it is a very easy to understand image format, which makes it a useful teaching resource for how effective simple techniques can actually be quite effective, but there are better things for production use.

[JeffreyLWhitledge]

From your description of QOI, I would say that its good compression ratios compared to PNG is probably because QOI recognizes that there is a correlation in the amount of change in the three color channels from pixel to pixel. PNG treats each color channel independently, which throws away a lot of exploitable redundancy. That is QOI better handles changes in brightness within a similar hue, something that is fairly common in photographic images.

[electronics-girl]

Probably one of the reasons QOI wasn't invented sooner is because it only handles 24-bit truecolor images. Back in the '90s when PNG was developed, it was far more common for images to be indexed color, so PNG needed to handle indexed color images well. Basically, PNG was designed to do many things well, but QOI only needs to do one thing well, so of course it can be simpler.

[DaVince]

I like how QOI is _almost_ PNG + 1.
P + 1 = Q
N + 1 = O
G + 2 = I

[emftechEE]

I was just watching your JPEG video as motivation for my Digital Signal Processing Class, and you publish this… thank you for your effort in visualizing these wonderful concepts, we needed someone with the visuals of 3Blue1Brown in the Engineering space, you and Zach Star are very inspiring to us aspiring engineers!

[kodirovsshik]

As a person who has previously implemented a PNG decoder, I was expecting this video to be just a small memory refresher on the format, but MAN I WAS WRONG
Got a refresh on Huffman coding, run length encoding, got an intuition about paeth predictor filter, found out how filters are picked and discovered a new amazing image format that I'm now willing to implement as an exercise

Never know what to expect, thank you for a great video!

[PaulFisher]

QOI is really neat! Given the amount of effort that has been spent on PNG and making encoding and decoding “fast enough” I’m not sure if something like QOI would ever dethrone it for general use (even WebP is having trouble gaining traction), I could certainly see it being very useful in more CPU-bound situations, like video game rendering. Since you absolutely have a 16ms deadline if you want to hit 60 fps, both the simplicity and (almost as importantly) the consistency of QOI decoding could be huge. In those situations, it’s usually the worst case scenario that counts. For instance, if you had an algorithm that was 20% faster on average but on 0.1% of cases took 3× as long, you probably would not want to use that. The worst-case cost of uncompressing a QOI image is probably closer proportionally to its average case than with PNG, where things can get quite a bit more complex.

[kleinesfilmroellchen]

This is an amazing video. QOI is so cool, but what this video really told me is how PNG compression works. A good format nonetheless. Lossless compression is absolutely fascinating.

PS: You've pushed me to continue my FLAC video series. It feels like I'm copying you even though I started with it before I knew your channel. Either way, you're a huge inspiration!

[Vaaaaadim]

The performance of the QOI algorithm seems quite compelling. I think I'd be willing to sacrifice some space savings for having compression/decompression that much faster.

[gblargg]

19:25 I like how you described the mapping in a way someone from mathematics would understand, rather than just saying that the value is treated as a signed byte.

[mynameisaustenful]

Nicely done 👍 this format reminds me of Grant and 3b1b...
You discuss the subject with precision while respecting the nuances and the accompanied animations help further cement the concepts - this is genuinely well executed

[RokeJulianLockhart.souq]

I did not understand any of this except some basic relevant vocabulary, but I compliment the narrator for his perfect speed and conciseness, and the animator for the simplicity and attractiveness of the animation.

[SianaGearz]

Check out fpng which was written in competiton to QOI. It uses the standard PNG format, but makes some concessions to make encoding and decoding similarly fast and achieve competitive compression. It basically reduces PNG to 24- or 32-bit mode, UP filter only, static Huffman, no lookback, only RLE.

[Video-Game-OST-HQ]

I wrote a texture-compression tool called LSDxt (name will have to change since it is not just for DXT files anymore) which is used internally at Square Enix, Cisco, Deep Silver Dambuster Studios, Apple, and possibly other places.
I will add QOI support in the next update, which won’t be long now. I’ve been waiting on PowerVR to fix a threading issue inside one of their libraries, but in order to just get a release out I think I will just warn the user of what isn’t working until they finally release a patch.
That will give QOI some exposure and it will mean that several of the big companies will have access to it (both convert-to and convert-from).

[LordHonkInc]

I'm a digital artist, so for the longest time I've relied on png as a (comparatively) simple and widely supported lossless format, and the hobbyist coder in me who has on more than one occasion tried to write image handling code from scratch (e.g. loading a jpeg without an external library) can appreciate the simplicity of this algorithm. I hope QOI gets more mainstream in the future, I'd be more than happy to provide my final product images in this format.

Now if you'll excuse me, I wanna see if I can make this into a Krita plugin :3

[milanstevic]

Well... wow... After checking out QOI I can't really tell why I actually never tried that. I was neck-deep in all kinds of RLE formats in the 90's, doing all kinds of things. But legit compressed formats all looked rather intimidating and I think everybody just guessed something as simple as that was simply too good to be true. Palletized images were one thing, but to consider a 32-bit true-color image easily compressible like that, you had to have a lot of time and patience. What I remember the most is that the disk space was incredibly precious, and there was no reliable internet access to make an image database (though once MP3s and JPEGs kicked in, we all had a folder or two with plenty of music and pretty pictures), only to commit to writing a proper codec with a decent benchmark.