Visit https://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: https://www.w3.org/TR/PNG/#9Filters and http://www.libpng.org/pub/png/spec/1....

A nice interactive guide to LZSS: https://go-compression.github.io/algo...

A definitive guide to all the details we didn't have time to talk about with respect to PNG: http://www.libpng.org/pub/png/book/ch...

A deep dive into all the details of DEFLATE:    • Data Compression (Summer 2020) - Lect...  

Initial blog post introducing QOI: https://phoboslab.org/log/2021/11/qoi...

Data on Image File Format Usage across Websites: https://w3techs.com/technologies/over...

QOI Specification: https://qoiformat.org/qoi-specificati...

QOI Source Code/Benchmark Results https://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]. https://www.manim.community/

Here is link to the repository that contains the code used to generate the animations in this video: https://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