How PNG Works: Compromising Speed for Quality

Visit brilliant.org/Reducible/ to get started learning STEM for free, and the first 200 people will get 20% off their annual premium subscription.
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:
PNG Specification: www.w3.org/TR/PNG/#9Filters and www.libpng.org/pub/png/spec/1....
A nice interactive guide to LZSS: go-compression.github.io/algo...
A definitive guide to all the details we didn't have time to talk about with respect to PNG: www.libpng.org/pub/png/book/ch...
A deep dive into all the details of DEFLATE: • Data Compression (Summ...
Initial blog post introducing QOI: phoboslab.org/log/2021/11/qoi...
Data on Image File Format Usage across Websites: w3techs.com/technologies/over...
QOI Specification: qoiformat.org/qoi-specificati...
QOI Source Code/Benchmark Results qoiformat.org/:
This video wouldn't be possible without the open source library manim created by 3blue1brown and maintained by Manim Community.
The Manim Community Developers. (2022). Manim - Mathematical Animation Framework (Version v0.11.0) [Computer software]. www.manim.community/
Here is link to the repository that contains the code used to generate the animations in this video: github.com/nipunramk/Reducible
Music in this video comes from Jesús Rascón, Aaskash Gandhi, and Myuu.
Socials:
Patreon: / reducible
Twitter: / reducible20
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.

[@MrRussianComrad]

Yes, indeed, very inspiring!

[@wpyoga]

It's called quantity over quality. So many coders come and go, but few are good coders. Code has been commoditized, so you see all these large teams working on large software packages, while the requirements could have been solved by a small elite team working closely together. Cue the "elitist" comments...

[@masternobody1896]

genius

[@roboticbrain2027]

A couple of issues with QOI: 1. After Reading the whole spec it seems to perform absolutely awful for alpha gradients since it has to encode a whole raw pixel for any change in alpha value. 2. As far as I can tell it basically reinvents or at least gets inspiration from YUV color space by favoring greens and using differences to it... I've seen something like that before but can't exactly remember where. (Possibly in patent encumbered graphics card stuff) 3. A big part of PNG is P for portability! 4. QOI is not much of an usable image format since it only covers compression. The PNG spec specifies several different chunk types with metadata and can even handle animations, so obviously it has to be bigger in scale. 5. When it comes to media compression it is a well accepted fact that encoding takes longer than decoding since in most cases you view a file more often than create it. So the benefits of faster encoding are only marginal. In conclusion: QOI is just a reimagination of several pre existing ideas with mostly academic value and possibly for custom self-contained projects not needing to interact with other software.

[@WilliamDye-willdye]

@@roboticbrain2027 I disagree in particular with point 5. There's a lot more encoding going on now, often on battery-powered machines. Encoding speed is a big win these days. As for item 4, extra features can be added by simply forking PNG, or maybe extending PNG to support QOI compression. If your point is that it's not fair to call PNG excessively long when PNG has to cover a lot more functionality, then I agree. It's not an apples-to-apples comparison. Even so, I'm very glad that QOI is concise. Regarding alpha-channel handling, thank you for bringing up that issue. It's worth investigating, and I completely missed it. Still, if there is a problem, I doubt if it can't be fixed. Same with point 3 and the others. I just don't see any show-stoppers here. QOI still stands as a cool hack. The fact that it covers old ground only adds to the coolness, because it emerged with noteworthy improvements. I say we move ahead with it. The world is producing a lot more media, with even more on the way. Better encoding is needed more than ever.

[@Cubinator73]

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.

[@vdinh143]

I'm blown away by how similar it is to just Assembly languages: A header for the operation type and a body for the operands. Uses the best of every world 🤣

[@nordern1]

Honestly, I don't see web support happening. The main metric of the web is size, and PNG is still smaller, and the decoding time is still small enough to not matter. And encoding typically only happens once. This type of format specifically makes sense for something like textures, or internal compression

[@code_explorations]

@@nordern1 Decoding happens a lot, though. It could make web pages feel snappier.

[@nordern1]

@@code_explorations yes, it happens a lot. But it's not faster enough for it to actually matter. We are currently transitioning to webp, which seems to decode about half as quickly as PNG. But it's smaller, so it's worth it, and I never noticed a difference. And when you have hundreds of images on a page, those are probably going to be jpeg thumbnails anyways

[@N00byEdge]

@@code_explorations The difference in download speed is many magnitudes larger than the decoding one sadly. But it would still be cool if browsers could view them, even if websites don't use them by default. Given the large difference in encoding speed however, there might be a use case for them with dynamically generated image content.

[@wulfshade5703]

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.

[@Reducible]

Yeah, a few people who have experimented with it have found that QOI + zip compression often performs better than PNG by itself. I'd like to see more comprehensive data on it though to really make thorough conclusions, but I suspect this will be a consistent finding since the compression method of QOI is distinctly different from zip file (LZSS + huffman coding) approaches. But alas, as you mentioned, you lose the simplicity and speed. Really cool to think about though!

[@defenestrated23]

Use the zstandard compression library instead of zip (which is basically DEFLATE). It's crazy fast.

[@vylbird8014]

And as web servers commonly use DEFLATE transparently on the connection anyway, that happens. But still, QOI isn't going to match WebP in most cases. There aren't that many niches when CPU time is more of a concern than storage or transmission time.

[@DiThi]

@@defenestrated23 Deflate uses Huffman coding, zstd uses something else better than Huffman, which is one of the reasons for its speed I think.

[@DiThi]

Trough lz4 or zstd it should be possible to beat PNG in both size and speed simultaneously.

[@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.

[@qwertystop]

Is there a reason QOI couldn't work with indexed-color images or reduced color spaces? Or at least the same algorithm with a different bit alignment. Mode 11 (run-length or direct uncompressed representation) both work fine, mode 00 (lookback) works with a different hash algorithm based on the new bit count, and mode 10 and 01 (delta) similarly seem like they ought to work fine with paletted images as long as the palette is sorted (so that shading and other gradients have a small delta in palette space) and the necessary adjustments for altered bit-count are made.

[@ukyoize]

@@qwertystop Well, QOI's index is 4 times smaller than PNG's

[@doodlebug1820]

This 100% matches what I'm seeing. I am working on a QOI version of an image that has limited colors and uses a lot of dithering. This was common in the 80s/90s. The QOI file is about 6 times bigger than the PNG file for the exact same data. QOI winds up encoding each dithered pixel as an "index" byte, which means it is "compressing" it to 1 byte per pixel. But the pixels in video ram are basically 1 byte each anyways, so if i consider that i could just copy bytes directly from Video RAM to disk and vice versa, as my base case, then QOI basically has zero compression on those dithered sections. It only is compressing the Run (RLE) sections, so if I just copied the video RAM bytes directly to disk it would only be about 30% bigger than the QOI file. on a 90s Dialup internet modem PNG, GIF, JPEG, would be the choice not QOI.

[@DaVince21]

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

[@inerlogic]

it's PNG+1 with a checksum.. P+1=Q, N+1=O, G+1=H, 1+1+1=1, add the checksum to the H, H+1=I

[@jellomochas]

@@inerlogic 1 + 1 + 1 = 3

[@inerlogic]

@@jellomochas not in binary

[@totheknee]

@@inerlogic 1 + 1 + 1 = 3 no matter what base is chosen. We would normally write 3 decimal as 11 binary, but it's still a _three_ and most definitely not a _one._

[@nozome-jin]

@@totheknee He means (1+1+1) % 2 = 1. In this case 2 is chosen as the base. Of course because it's binary.

[@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.

[@gblargg]

And its short encoding of small changes in levels handles noise in a solid-color area of a photograph, or a slight gradient, well.

[@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.

[@Pystro]

Now I want to see those faster encoders included in the comparison... (as well as the QOI+Zip comination)

[@dlol.]

theoretically someone could also make speed improvements to QOI we'll just have to see what happens since its so new

[@n00blamer]

@@dlol. QOI is really difficult to make concurrent because of the way the previous-color-with-this-hash works. At least for PNG the deflate/inflate can be segmented by splitting the image into multiple IDATs (done that, linear speed increase as function of nr. of committed threads/cores). In this kind of scenario the PNG runs circles around QOI.

[@n00blamer]

@@Pystro QOI+ZIP isn't worth it as the deflate is taking most of the encoding time and at that point the PNGs filtering system is more efficient as a compressor. QOI+ZSTD is more competitive but still net loss, at least unless the image is tiled or segmented some how so that some parallel action is possible (I have tiled QOI prototype at specific URL but this channel sanitizes comments with links so whatever).

[@circuit10]

@@n00blamer Could you not split the image into strips and encode them in parallel? Then you would lose some compression but you could parallelise it

[@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!!

[@jgtb0pl]

Mom, I know what I'm gonna do today

[@KiraleosAkis]

This sounds like a terrible project for people learning to code. Can you recall what it was when you first learned how to code either through uni or on your personal time? Nothing made sense, computers were still black magic and you had 0 clue of what a program is let alone knowing file formats, let alone image file formats, let alone compression techniques. I don't disagree that learning the lowest level stuff is very important and paramount to becoming a good developer, but I just don't think that this particular project is quite right for a beginner.

[@Imperial_Squid]

@@KiraleosAkis I never said it should be your first project, chill my guy. I mean it's good when learning about bytes and stuff like that, obviously you'd do the standard stuff learning loops and ifs, that kinda thing first. And not all programmers learn in the same route, if you get on really well with low level code this would be great, if you're more network/high level/software dev/whatever then you'd prefer a different route. But I think this kinda thing is absolutely achievable for someone with a few months experience behind them

[@totheknee]

It also might show how the object oriented fad is harmful compared to simple, performant code. My guess is that QOI would run 1/2 as fast with OOP nonsense, in addition to being harder to understand and maintain.

[@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!

[@Supreme_Lobster]

I second this!

[@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!

[@harriehausenman8623]

Same for me. Nice tickling of the neurons.

[@canesvenatici9588]

That's cool, I still don't understand tho. After filtering, how does the PNG decoder knows the difference between say positif 255 and negative 1?

[@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.

[@Reducible]

Yeah, totally agree! As simple as QOI is, I highly doubt it will ever replace something that's so entrenched as PNG. And yeah, that's a great point of worst case scenarios. I work professionally in an area that interfaces a lot with video codecs and one of the important aspects in decoder performance is the worst case thresholds for when we have to drop frames. There are expectations in modern media (e.g KZbin playback) to be able to render 2x speed playbacks and variable playback rates, so ms of performance on the decoding side can be the difference between having something that is totally unwatchable and something smooth. The aspect that makes modern video codecs so fast is the operations can be nicely accelerated on the GPU. In order for QOI to really mature, that aspect of the equation also needs to be figured out. On first look, it doesn't seem obvious if GPU's would even be able to handle it well due to the dependency on previous pixels and run-lengths. But honestly, haven't put much thought into it :)

[@notnullnotvoid]

@@idoben-yair429 The type of compression that GPUs use for real-time rendering is quite different. It's lossy by necessity, and packs each tile of 4x4 (or 6x6 or 8x8) pixels into a set amount of space, so the GPU can get to each tile in a single random access. But yeah, a simple enough lossless format split into large-ish tiles could probably be decompressed on the GPU. LZW, the compression scheme used by GIF, has been shown to be parallelizeable on the GPU (although the GIF format itself isn't ideal since it isn't byte-aligned). Between this, vp8/webp, and the kraken decompression hardware in the PS5, it's an interesting time for compression.

[@JobvanderZwan]

I think most people would default to comparing compression algorithms to each other, but what I think a lot of people don't realize is that most of the time the CPU is data-starved and waiting for disk or memory, to the point where if you have right type of data a compression algorithm like LZ4 for on-the-fly decompression/compression on the CPU can be faster to use than uncompressed data when loading/storing values from/to RAM. So it's not even about saving disk space or memory at that point (although of course it's also a little bit about that), under the right circumstances it's genuinely faster to use compressed data than to use uncompressed data. I wouldn't be surprised if QOI is the kind of fast compression algorithm that beats uncompressed images for speed, and will find use as such.

[@notnullnotvoid]

@@JobvanderZwan That's a great point - as the ratio of bandwidth to processor speed changes, the fastest compression algorithm also changes. With much faster internet and hard drives these days, and CPUs that aren't getting any faster on average (because of decreasing form factor and power limits), lighter compression is more appropriate than ever.

[@terohannula30]

GameMaker has adopted QOI now, it also includes option to further try compress with B2Z. So you have option to use PNG, QOI or QOI+B2Z. These choices are useful and can be chosen per texture page.

[@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.

[@jursamaj]

I mean, sure, but any mathematics person getting into computer programming needs to learn what signed bytes are anyway. And probably should learn it early, before getting into such an esoteric topic as image compression.

[@gblargg]

@@jursamaj I think plenty of people watching don't plan on getting into computer science. These things are interesting as more abstract mathematical problems.

[@angeldude101]

Except their explanation is closer to how it's usually explained to programmers (as just mapping a range of values to a different range) rather than explaining the actual mathematics behind it in the form of modular arithmetic. Bytes aren't ordered on a number line, but rather on a number wheel. When working with it though, most situation require cutting the wheel somewhere to straighten it into a number line. The two most common choices are between -1 and 0, and the diametrically opposite point, which correspond to unsigned and signed numbers respectively. When folded back into a wheel, two seemingly different points between the two lines can end up as the same point on the number wheel, just with different labels. There are also connections with division rounding (since modulus/remainder is a part of division, and while the modulus is normally positive with a quotient rounded down, rounding it instead to the nearest value, ties up, the signed remainder obtained would be the same value as a signed integer) and p-adic integers (as sign-extension and 0-extension can be seen as heuristics to guess what the digits that got truncated off should've been), but that's enough for now. Not once did I mention bits or bytes. Everything here can be done even in decimal, or any other base with some fixed number of digits. (The decimal equivalent? Anything with a leading 5 to higher would be negative, and could be extended with a string of infinite 9s.)

[@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!

[@Reducible]

FLAC has a lot of incredible ideas involved -- absolutely think it would make some great content, so please do continue covering it! I took a brief look at some of the work you did and I think you might be only coverage of FLAC I've seen on KZbin (at least to my knowledge), so that's super cool!

[@kleinesfilmroellchen]

@@Reducible Thank you so much! The second video is already in the works and has some juicy lossless compression stuff in it :^)

[@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.

[@killpidone]

Depends on the application, for web browser I'd think size is overall better focus as transmission over the internet is going to take much longer than decompression

[@ETXAlienRobot201]

@@killpidone if the difference was super significant, sure. want to complain about size, check-out unity bundles! *shudder* also, for size, unfortunately, JPEG out-performs PNG quite often. also, i assume QOI doesn't actually use the general-purpose compressors, so MAYBE those can squeeze some more off? either way, seems pretty worth it! web formats are actually full of bloat and complexity, this is the REAL reason google chrome is the most popular browser, particularly the complexity

[@milanstevic8424]

@@ETXAlienRobot201 you don't actually compare a lossless format with a lossy one. I mean, hear me out, yes, practically it kind of makes sense -- after all even 32-bit floating point math does work to a tolerable margin of error for most applications, right? but let me tell you, it's not just the OCD -- it's the error accumulation that's the real issue. lossy formats will accumulate the bias with every edit. this doesn't happen with floating point math in general, given that any RAM data is volatile anyway, but will readily happen with a file being in use for years. the ground truth will be lost over time, and maintaining that the original data must be preserved as ground truth would heavily disrupt the way these algorithms work. in short, such error accumulation is unacceptable for many purposes outside the casual read-only usage, therefore lossy formats should really be used only as the end product, not as an intermediate archival format. from this perspective, comparing the two is really like comparing apples to oranges. that said, I doubt QOI would significantly benefit from any general purpose compressors (maybe only in fringe cases), but it would quickly (exponentially) lose its edge in processing time.

[@milanstevic8424]

@@killpidone if we were still in the mid 90's I'd agree with you, but that particular constraint is long gone. at least on these orders of magnitude. however, with the digital photography in mind (which is a subset of digital graphics in general) I'd argue JPEG was and still is a better choice, as it was made to handle that particular domain quite well, and no lossless format will beat it any time soon if we're exclusively talking about web browsing.

[@killpidone]

@@milanstevic8424 you don't live in a rural area

[@RokeJulianLockhart.s13ouq]

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.

[@akirachisaka9997]

Do you want to one day talk about redundancy? Like how a QR code can be partially damaged yet still be read? Basically, I’m always wondering what are efficient ways to introduce data redundancy.

[@rosuav]

3blue1brown has a really good vid on how a very small amount of redundancy can be used for error correction - check out Hamming codes. Unsurprisingly, that vid also uses manim :)

[@akirachisaka9997]

@@rosuav Yeah, I've seen 3b1b's series on error correction. That's what got me interested in this topic!

[@AraliciaMoran]

An interesting point on that subject : PNG includes CRC hashes, which makes it able to detect if an error occurred in part of its file, and in which part the error is present. Can't do error correction tho.

[@davidlloyd1526]

While interesting, the trouble is that PNG and JPEG are "good enough". There are lots of image formats that are better than both... but none gained traction. We're in a similar situation with video (h264). A video on "what happens when things are good enough?" would be interesting in itself...

[@Cornyfisch]

I think that AV1 is a really strong alternative to H.264, it is even implemented in hardware by the new Intel Arc GPUs

[@SomeRandomPiggo]

@@Cornyfisch i've messed around with it for the past month or so and in some cases svt-av1's preset 8 can be faster than h264 and look way better!

[@bit1345]

For the layman yes. Anyone actually making shit knows which file formats they need. A customer asked me which file they needed to buy, i wanted a vector so I said get the .eps version. If something new comes by that works way better coders, web designers, digital artists, and others will use it.

[@AraliciaMoran]

@Revotry People don't like change is really true, but maybe in more and different ways that you meant. Many people don't care much about the file format itself; they do care about the workflow and the tools they use. Someone whose been using Photoshop (as an example) for years usually won't want to have to switch to another editor, use an external plugin, or run an external tool simply to be able to use webp; that's cumbersome, and unless its mission-critical, not really worth the extra time when you can just hit a button to export in png. (Webp export is now native to photoshop, but has been only for a few months; we'll probably see it being used a lot more) And that kind of inertia is present not only at the end user level, but also at the tool maker level; the fact that Photoshop can natively export to webp only since february while a third-party plugin has been existing for the past three years is proof of that. And even if your tools allow you to export to a newer format, it's sometime still not a good idea, due to how(or where) this image with be used. For example, Wordpress, which is behind many website, allow the upload of webp images as of mid-2021, but still forbid the upload of svg images, requiring the installation of third party plugins to be able to do that. Which means that if you give your unique designs to a client as a svg export, they might not be able to use them as intended. As a result, unless you are actively trying to give the best results you can, and know exactly in which context the image will be used, defaulting to older format might simply be the better, if not only, option.

[@bagamax]

I remember TIFF-ZIP was good enough before PNG, and TIFF-RLE was good enough before TIFF-ZIP. TIFF-ZIP is very niche now and TIFF-RLE can be considered dead at all. Good enough is not an end of a story, it's just some pause sligtly longer than usual.

[@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

[@davidrich27]

I wanna say that I saw somewhere that 3B1B made his animation library freely available, so maybe he used that?

[@CrushedAsian255]

@@davidrich27yeah I think he’s using the manim library

[@milanstevic8424]

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.

[@grn1]

From reading other comments I've learned that QOI only works for 24-bit tru-color images while PNG works with various other formats which were far more common in the 90's. PNG also has color corrections and as you mentioned computing power was far cheaper than storage.

[@aloysiuskurnia7643]

When I see the QOI algorithm I scream to my head "there is NO WAY an algorithm this 'primitive' can compress stuff to the level of PNG", but the data says otherwise Probably this mindset is why QOI is not found sooner

[@aa01blue38]

Lol, imagine being a software engineer who worked on PNG for more than a decade and you see one random guy make something almost as good and 50x faster

[@jamesmnguyen]

@@aa01blue38 Probably with a few tweaks, Just as good but 10x faster.

[@SviatoslavDamaschin]

Well, less complex = less computational power, no?

[@xavierrodriguez2463]

yeah this really feels like a format that would've been invented in the late 80s, and if it was, I'm sure we'd be using it today.

[@AnglosArentHuman]

@@aa01blue38 PNG was designed to work under completely different circumstances to the modern computational landscape. Their reaction is probably along the lines of "bloody finally" rather than "damn I feel dumb".

[@isle_of_violets]

this channel is amazing because every time i think "eugh hes saying its too complex to explain in this video" he then just says "so lets get into it" and it makes me happy every time

[@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

[@terohannula30]

GameMaker has adopted QOI, and currently allows you store texture pages as either PNG, QOI or QOI+ZIP, which is nice as some pages might be faster&smaller in one format, and some page in another.

[@gamechannel1271]

Game maker pretty irrelevant nowadays

[@FaultyTwo]

lmao. QOI is an acronym for "Quite OK Image". Truly living up to its name.

[@sadhlife]

Your overall video quality has gone way, way up since the dynamic array days. I'm really proud, my dude.

[@finndriver1063]

Love this video, as well as QOI which I stumbled on a little while ago! I've started recommending QOI en/decoders to people as an intermediate self-contained programming project. If you're not bored of image stuff, I'd love to see a video on TinyVG (like QOI but for SVG), or the newish, badly-named JPEG XL, which looks set to maybe dethrone JPEG in browsers, and is a FOSS standard for once. Farbfeld is also interesting, but perhaps more for philosophy rather than technology. A miniseries on the different technical details of competing methods would make my year. Other examples might be comparisons of lossy audio (mp3, Vorbis, Speex, Opus (Opus is crazy)), or static document formats (DjVu, PDF, XPS).

[@TommyLikeTom]

I love how excited you got when you mentioned that the length can be greater than the offset at 11:13

[@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.

[@suseJattackIsBack]

Fun fact: QOI is pronounced just as koi, the fish, is: /koi/. The battle for the best performing compression algorithm is only obscured by the pronunciation of their name.

[@MichaelPuterbaugh]

I want to pronounce it /kwa/ like the French word "quoi". We learned nothing from GIF, did we?

[@harriehausenman8623]

@@MichaelPuterbaugh Prilliant 🤣

[@harriehausenman8623]

This insight is way less funny that we should have to admint 😉

[@grn1]

@@MichaelPuterbaugh It's pronounced GIF.

[@nyuh]

I personally, encountered QOI for the first time on discord. Somebody asked to test their QOI iimage converter. Tried to look into how QOI works, but I couldn't quite wrap my head around it. Nice to find a thing that finally explains it clearly :)

[@setharnold9764]

I can stare at paeth and avg and wonder how the heck those are reversible, or look at qoi and wonder if I could get that done in an afternoon. Pretty crazy. Thanks for the introduction.

[@MatthewFearnley]

Hi. I believe Avg and Paeth are reversible because (like the other filters) they’re calculated from past values that are already known by the decoder. So the difference is just that you’re just adding a number to a calculated value, rather than a directly known value.

[@mohad12211]

great video! I always like in-depth videos about compression, please consider explaining video/audio compression in the future!

[@cjjuszczak]

fantastic video, eloquent, concise, beautifully told, and a joy to listen, and watch :)

[@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).

[@harriehausenman8623]

OMG. You did it again! Absolutely fantastic video and the examples are just brilliantly designed. Thank you so much.

[@konpet4248]

Yo, I'm currently implementing PNG decompression, while also getting ready for compression. After all the pain I had to go through with DEFLATE (which I can compress and decompress now), seeing the simplicity of QOI hurt me quite a bit. And seeing them just waste 6 bits for the uncompressed pixels just for byte allignment, while DEFLATE just completely ignores the concept of bytes, made it hurt even more Thanks for this video though, you explained it really well, like I expected coming from your other videos. Keep it up!

[@Icelink256]

A number of years back, I was tasked with compressing fullscreen 2bpp images, for a console game. My approach was based on a sprite drawing technique, that was a hardware feature in the MSX2 homecomputer. (Called the OR color, which allowed two overlapping 1-bit sprites, to produce more colors than would normally be allowed.) My method was to split the bitplanes of the image, and delta-encode each half separately. Apparently, the developers of Pokémon came to the exact same solution, so I'd unintentionally re-invented the wheel! :P

[@caros6924]

I have to say, this is a really fantastic video. I'm studying on image signals, ur video helps me understand too much! thanks.

[@masondaub9201]

I made a PNG reader/writer library in C as a personal project. The PNG specification is truly a monster, and it took forever for me to read through and understand it and get a working project. The colour types, CRCs, compression and filtering together make it quite complex and it took me weeks to get it working, and that's with using zlib instead of making a custom deflate compressor. I wish I had these videos when I did that.

[@bagamax]

I had no idea that my scepticizm on replacing nice old working PNG with something that compresses worse might be blown away with a single page of spec. This compresses not an image, this compresses developement complexity. And it is amazing!

[@bluebukkitdev8069]

Thanks so much for putting this video together. So many animations, such excellent explanations.

[@ace4x3]

This is a great video! It feels really good when I can, more or less, follow through what is being told in the video :)

[@LeeSmith-cf1vo]

I have recently been working on my own image compression format. So far it has marginally better lossless compression than png and takes about the same time to do so. The lossy version barely does any better, but there is plenty more tricks to add yet. Not ready to share it yet but if it turns out to get good results I will certainly do so. BTW it supports transparency and I have only a single test image so far (photo) - plenty still to be done. Oh and the "lossless" mode may be technically incorrect, I'm not sure if there might be imperceptible rounding errors in there - need to check that.

[@LeeSmith-cf1vo]

The biggest weak spot is going to be the decoding time, which is about the same as the encoding time. But the code is unoptimised JS, so I'm sure it can go way faster.

[@fluffycritter]

The QOI algorithm is pretty impressive in its simplicity. It reminds me of some of the experiments I did with lossless image compression back in the day, only it seems to get much better results! Most of my attempts were based on running the Haar wavelet transform which did a pretty good job and had the benefit of also making the image progressively-refinable as it downloaded (which was a big deal back in the 90s when I developed it, not so much today). To be fair to the PNG spec's size, a lot of that is because it does a thorough job of also explaining non-image chunks with various forms of metadata and the spec is intended to be quite extensible, and also being a W3C spec they have to have a lot of boilerplate and "legalese," which also makes it much more difficult to read. Also, I don't know how feasible this would be on PNG, but on a specialized ebook format I developed which also used the variational filter approach (inspired by PNG), the approach I took was to just compress each chunk of data with each possible filter and see which one compressed the best. The structure of the data did make it a lot more feasible though (as a single filter was always good across each data channel) and also it benefitted from being an offline, automatic process where it didn't really matter how long it took to happen.

[@turinhorse]

THIS WAS SUPER EXCELLENT. clear, detailed. perfect presentation. thank you.

[@alexyz9430]

holy shit, thank you so much for shedding light on QOI, truly blew my mind away!

[@psyboyo]

I didn't know this channel existed, this video is brilliant and so are the explanations, and qoi blew my mind. If used to stream video in the future... oh boy! ❤

[@portevent]

Wow, I didn't know you but I'm glad i came up to this channel. The animation quality is excellent, the explanation are great. There is a lot of work in it nice

[@0xbenedikt]

It would be interesting to add a deflate step to QOI. I wonder how well it can be compressed further.

[@AVX512]

Too OP

[@daxterapid]

A video on font rasterization or dithering might be neat, loving these image file videos though. Your content is fantastic!

[@Adityarm.08]

This was an amazing watch. Thank you.

[@injeolmi6]

this is incredible. Thank you so much for putting this together.

[@tomhartwig7194]

What an absolute beauty of a video. Thanks a lot! I've really enjoyed it!

[@matheuscosta5330]

what a piece of art this explanation is...

[@World_of_OSes]

When encoding a PNG in programs such as GIMP, there is a slider where you can choose how much compression to use and it is a trade-off between size and speed. What is this doing in the algorithm?

[@fweaks]

The biggest thing it's doing is probably adjusting the size of the windows. If it has to look further forward or backwards every time, that's going to take longer. But it's also going to give more potential findings.

[@zeddy675]

Great explanation, wonderful graphics! I remember having to implement a PNG encoder/decoder for a personal project back in the 90s and I had hard times on some specs. Managed to do it but would have taken less time with your video! GIF was much simpler and my PHP implementation of it has been widely used since the 90s, which is strange 🤪

[@firehawk128]

This reminds me of 3 blue 1 brown - it's great how you've visualized the algorithms working.

[@XaurielZ]

You do a really great job of breaking down complicated comp sci concepts so that even a humanities scrub like me with minimal math and tech experience can understand. Kudos!

[@ScottLahteine]

It really gets you thinking! For some images, reordering the pixels in (e.g.) a spiral might produce better compression, while others might do better if rotated 90°, etc. And, you can imagine combining QOI with a "progressive loading" technique - where you start out making big blocks of the dominant hues, then fill in the differences in stages, applying smaller and smaller pixels at each step. Such differential data ends up having longer runs perfect for QOI or basic RLE to digest. Then you just need to specify in the header which trick you used to get the best compression. Of course, a simplified heuristic would help in figuring out the most suitable approach for the given image.

[@AVX512]

Sounds like how Diffusion-based image compression would work

[@rasherbilbo452]

Beautifully presented.

[@thekilla1234]

"I have no idea what I'm doing." Spoken like a true computer scientist.

[@wispedits]

thanks, lots of effort put into this really well done!

[@RedStoneMatt]

Absolutely fantastic, very interesting and easy to understand

[@OtakuSanel]

encoding time for images is a moot point, you do it once and it's done. however the decoding time may be worth the lower compression ratio in certain applications.

[@danielbernalbrito4381]

Awesome video. Thank you!

[@usbhub95]

Great video, I would love to see more like it. I’m not particularly well versed in compression, but have always loved the topic. Particularly lossless compression.

[@ToyKeeper]

Have been following QOI with excitement. Originally meant for real-time lossless video on low-end hardware, it has become quite an interesting option for images too. I hope it'll become commonplace and universally supported soon.

[@TheOPtmal]

Honestly, this video made me appreciate PNG more than anything.

[@EpicGamer-ux1tu]

Great video. Thanks for sharing!

[@nadebal1]

THANK YOU IT WORKED. I AM SO HAPPY.

[@Rudxain]

And here I was believing HEIC/HEIF was the ultimate lossless compression format for raster graphics. Thank you for this valuable info!

[@0LoneTech]

HEIF will be up for discussion in another 20 years, when the patents run out. In the meantime we could consider AV1.

[@chr1st0pher]

This is so interesting. It seems to help explain why png sequences are not desirable for good playback speed in video applications (even tho decoding speed is not bad). It makes me wonder what the best lossless image format for performance playback would be. I’ve heard most people say exr which is usually what I use but not exactly sure which compression type is best. This video helped generally make more sense of that whole world

[@Xxnightwalk1]

I truly love your content, even though it always ends up burning my brain as I'm far from smart enough to do anything close to what you cover X) And that brings me to think, it would be nice to sometimes have some more "back to basics" kind of content, see how the simpler ideas and concepts get mixed together and end up creating the complex systems you cover I really liked the dynamic array videos for example

[@_schnelli4800]

Great video, really nice to see content I've learnt in uni actually being applied to something. I cannot help but feel PNG can be improved upon, LZSS and Huffman coding are great techniques but I don't feel the same about filtering. To my understanding filtering is trying to introduce redundancy and we need to make sure we are lossless while doing so. The filter has 5 different types and uses the best for each row, I think this is a bit simplistic and there may be better ways to look for and exploit patterns to further increase the redundancy.

[@hrrawr]

QOI's creator is my hero for fitting the specification onto a single page.

[@brainxyz]

Great Explanation!

[@sanderbos4243]

Excellent video!

[@ihebbendebba2978]

very good teacher and astounding animations. What a professional work

[@313usually]

Feel like I've watched a long story SF documentary movie. Hats off to your time and effort to make this great tutorial! Thanks. I saw little typos in QOI depiction of the video: the tag bit for QOI_OP_DIFF is b01 according to the official spec doc, not b10. (timeline 25:02 , 25:51 , and recapped frames of it.)

[@Pi7on]

I absolutely love the semplicity of QOI

[@deliveryman7001]

This is cool. Glad it appeared in my recommended, very interesting stuff.

[@BoffinBrain]

Great video with helpful visuals. Perhaps you can do a video on WEBP in the future, since I'm not familiar with that yet.

[@jboyengy]

I'm a lay person, and I recently learned a little bit about Hilbert Curves and then just randomly had this video recommended to me by KZbin (good video, btw! It did make this topic fairly easy to understand!). As I understand it, Hilbert Curves kinda "maintain locality" of data, so I was wondering if you followed a Hilbert Curve around an image while compressing it rather than going line by line, would that produce better results. I ask, because it seems like in images, pixels near one another seem like they'd be more repetitive than pixels further apart. This seems like something that would have already been tried, though.

[@MatthewFearnley]

Nice video! Around the 20:45 mark.. Probably the most popular open source encoder (libpng) does use the “average distance from 0” heuristic for choosing filters. But PNGOUT (closed source but freeware) reportedly uses an “entropy” heuristic. I think basically it takes the frequency ‘f’ of each byte value, sums up all the values of ‘f log f’, and (IIRC) chooses the lowest score. So a row of mostly 0’s would score well, but equally so would a row of, say, mostly 128’s. It was hard to say, because PNGOUT also used a better/slower LZSS compressor, but I think it generally chose more compressible filter combinations.

[@leozendo3500]

thank you for turning information into knowledge

[@maliciousfry]

Super interesting and very informative!

[@AceyTM]

Great video I'd love to see such explanations about video game texture format !

[@mazza420]

this is so cool! and you explained it so clearly! i kind of want to implement these algorithms now

[@LeBeautiful]

I understood PNG to a whole new level with this video. Fascinating..but QOI..god bless Dominic Szablewski!

[@rcmaniac25]

First, great explanation of PNG. Second, I actually came across QOI and this video a different way... my Prusa 3D printer put in their release notes that they were switching the preview images of 3D models from PNG to QOI and that older gcode (the format used to encode all the moves for the printer) might not have a working preview because they were encoded in PNG. While I see many of the comments indicate PNG can get smaller images then QOI, the reason for the switch was because the decoder uses less memory since 3D printers are embedded systems with limited ram and processing capabilities. Looking at their code, the whole thing is less then 400 lines of code. That includes white space, brackets, comments, and pretty-printing the code for easier readability. They also did an interesting change of turning the whole thing as a state machine. I don't know how they use it (the code is a detached git branch, so Github doesn't really index it for searchability), but given how the decoder is written, my mind wants to say they have a screen buffer, read the file's gcode byte by byte, and every time they get a pixel, they put it in the screen buffer and move on. The result is the whole decoder runs in 259 byte of ram (probably a bit more, or being pedantic and covering frame buffers and pointers and such, probably closer to 512 bytes). That is quite incredible for a image decoder. Meanwhile, a quick search for an embedded image decoder gives me PNGdec and says it runs on anything with at least 48K of ram. ~0.253K image decoder vs. 48K+ image decoder... and (again, by how I think they're using it) it being processed as I/O is read and being written direct into screen buffers... the amount of space and processing time that frees up is basically like the image decoder wasn't even there. And yet it gets near PNG compression... that's huge. It's amazing it came about a little over a year ago and this is the first I'm learning about it. Also fun note: if you read QOI's original blog post, he created it when trying to create an video format. While no basis, it would be quite huge to get something like H.264/H.265 or AV1/VP9 compression with reduced decompressor size, memory usage, or processing time... just a dream for the future...

[@_mathis]

While the advantage in encoding speeds likely matters less for most applications, one other advantage of an extremely simple format like QOI is almost trivially easy hardware encoding/decoding. Wouldn't surprise me if that makes it to SoCs soon, as we move more towards specialized hardware.

[@CoolAsFreya]

Finally makes sense why PNGs with more colors (like an image) take longer to save and are bigger than PNGs with less colors (like a logo)

[@eyalhamtsany9472]

Great video! I really learned a lot from it! Thank you for that. One correction, if I may: in the QOI description you have the same 2-bits TAG (of '1 0') for both QOI_DIFF_SMALL and QOI_DIFF_MED. I think this is incorrect.

[@jameswis4644]

Very impressive!

[@Patashu]

Never heard of QOI before, it's super cool!

[@TinchoX]

Fascinating!

[@_spartan11796]

Love the video!

[@AlexanderTzalumen]

I would be interested to see the performance of the decoder, this might be useful for video streams.

[@vinos1629]

u are the best channel on youtube at the moment

[@Meverynoob]

25:47 can someone explain why small diff and med diff are both using the tag 0b10? Doesn't make sense to me how a decoder would differentiate between the two.

[@Reducible]

Good catch. That is a typo -- updated the description with the correction. QOI_DIFF_SMALL should have a tag of 01, not 10.