2022-03-28

[public] 14.1K views, 19.9K likes, dislikes audio only

Reducible

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.2/png-1.2.pdf

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

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/chapter08.html

A deep dive into all the details of DEFLATE: https://www.youtube.com/watch?v=oi2lMBBjQ8s&ab_channel=BillBird

Initial blog post introducing QOI: https://phoboslab.org/log/2021/11/qoi-fast-lossless-image-compression

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

QOI Specification: https://qoiformat.org/qoi-specification.pdf

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: https://www.patreon.com/reducible

Twitter: https://twitter.com/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