Description

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