QOI
lastmod 2021-11-26created 2021-11-261 edits
"Quite OK Image" - O(n) lossless image compression
Features
- Compresses RGB/RGBA to a size similar to PNG
- Compression is 20x-50x faster, decompression 3~4x faster
- Open-source, 300-line single-header C code
- Simple single-threaded implementation without SIMD
Technical details
- Encodes/decodes an image in a single pass
- Touches every pixel only once, and each pixel is encoded in one of 4 ways
- If it is the same as the immediately preceding pixel, increase the run-length of the preceding pixel; if different, pack the new pixel using one of the following 3 methods
- If it is the same as a previously processed pixel, the index of that pixel. For this, it keeps an array of the 64 most recent pixels
- If it does not differ much from the previous pixel, store the RGBA difference
- If the 3 methods above fail, store the pixel's RGBA value. Only the parts that differ from the preceding pixel are stored
Someone's comment
To put it with slight exaggeration, QOI is PNG with zlib removed, leaving only the filtering, and then improved.
The zlib/gzip/DEFLATE compression algorithm that PNG also uses is widely used, but it is so old that it is less efficient, and LZ77-style algorithms including zlib rely on the basic assumption that "among recent bytes, runs of identical consecutive bytes appear several times" (e.g., when the input is "to be or not to be", exploiting the fact that "to be" appears twice). But images are data for which this assumption does not hold well, so PNG effectively uses zlib only for entropy coding (an approach that compresses based on the probability of the next byte without any additional context), and uses simple filtering as a preprocessing step to make the data fed into zlib fit the assumption as much as possible, but it cannot really be called that efficient.
Modern lossless image formats improve on this in two main ways: one approach improves pixel prediction, which corresponds to PNG's filtering (greatly increasing the kinds of filtering, or applying different filtering to different parts of the image), and the other improves entropy coding, which corresponds to PNG's zlib. QOI's approach is similar, but it is distinctive in that, for simplicity, it does not use the pixels above the current position at all for pixel prediction, and that it gives up entropy coding and instead provides several empirically based difference (delta) codings. Especially because of the first characteristic, apart from compression/decompression performance, its compression ratio tends to be worse than even PNG's, which seems improvable by sacrificing a bit of simplicity.
See also
- png (zlib)
- FELICS - A lossless image compression algorithm that achieves 5x faster performance than the lossless JPEG codec with a similar compression ratio.
- ImageZero