QOI – The Quite OK Image Format
qoiformat.org
qoiformat.org
It's worth pointing out that in cases where PNG is still the most reasonable format to use, compression gains are frequently left on the table. I frequently see 20-30% additional compression with tools like ect ("efficient compression tool"), oxipng, and zopflipng, and that's starting with images that are already pretty well compressed (using the strongest settings available from traditional PNG libraries). In other words, even PNG compresses better than PNG. :-)
Case in point: I downloaded the sample images in the zip on the page and recompressed them with ect. It took only a few seconds, but 4 of the 7 sample images could be further compressed by more than 33%! After compressing them as much as I could achieve, the resulting PNG images were only 77% the size of the QOI images. Compression gains of 23% are nothing to sneeze at when it comes to lossless compression.
Of course, that's not to say that something like QOI wouldn't be useful. Even if it wasn't, I do love seeing tiny but effective implementations of algorithms like this - well done.
If you're willing to break compatibility anyways you could however improve PNG by substituting a better compression algorithm like zstd or lzma.
You are however correct that zstd would be a better algorithm than DEFLATE to be the basis of a modern image format - however, that sort of misses the point as well because there are modern techniques for encoding images losslessly that are much better than general data compression can achieve. JPEG-XL has a lossless mode that is "about 35% smaller than PNG" according to their website. That's almost certainly more than you would get out of switching to zstd, or even LZMA.
I noticed this takes hours with ect. pngout ranks in second place with respectable results, but is fifty to hundred times faster.
As I said in the OP, optimizing the seven test images provided by the QOI webpage took only a few seconds.
Yes, this is technically not 100% true, it's just 99.9% true. Previous tests have found those additional options to provide negligible improvement in compression. Very rarely do I get even 1% more compression out of enabling all of them compared to ect's highest built-in compression level (`-9`).
Basically what I'm getting at is that ect seems to hit the point of diminishing returns much quicker than anything I've personally tested. I'm curious if you have found a tool that achieves the same or better compression more quickly, that's why I asked.
I particularly like the four 2-bit tags that allow you to encode: runs of a previously seen pixel, or a color Delta (big or small), or a previously seen pixel.
Plus, the simple hash function of previously seen pixels (inner product of rgba and the first four odd primes) based on their color values, into a 64 slot array, it's just really nice.
It's so refreshing to see one page specification. it just comes across as really elegant. Almost a work of art and has a certain aesthetic to it that I really like. It'll be cool to see more people creatively inventing standards. It's a worthwhile pursuit not because you think okay we're going to create a standard that's going to take over some other standard...nor a proliferation. But a file format a specification is a valid sort of medium of creative expression and output. It's a valid creative product I think. So it's just really really cool to see this!
QOI – The “Quite OK Image Format” for fast, lossless image compression - https://news.ycombinator.com/item?id=29661498 - Dec 2021 (103 comments)
The QOI File Format Specification - https://news.ycombinator.com/item?id=29625084 - Dec 2021 (54 comments)
QOI: Lossless Image Compression in O(n) Time - https://news.ycombinator.com/item?id=29328750 - Nov 2021 (293 comments)
The sample images that come with the download look well selected. I encourage everyone to try it on real data and see for themselves. Personally I was quite underwhelmed by the format and we are sticking with PNG for the time being.
But these won't compress well _losslessly_ in principle, would they?
Or did you manage to find a format that did in fact work well?
PNG should not be able to compress noisy images well, because noise removes patterning. JPEG obviously can, but exactly because it is lossy.
Reencoding JPGs may not be too bad because of the way DCT creates little blocks of gradients and chroma subsampling reducing local color entropy, but ISTM it'll do best on images generated by humans with drawing tools.
The decode speed is another big point in favour of usage in games.
https://cloudinary.com/blog/time_for_next_gen_codecs_to_deth...
There are also special-case trimmed-down PNG encoders that are in the same league as QOI in terms of compression and simplicity.
It should be noted that it "can be", not it always is. The implementation in question [1] is currently experimental and not what you get from cjxl. In any case it is worth noting that QOI inspired both FPNG and FJXL.
[1] https://github.com/libjxl/libjxl/tree/main/experimental/fast...
[1] See:
https://www.lucaversari.it/FJXL_and_FPNGE.pdf
https://github.com/libjxl/libjxl/tree/main/experimental/fast...
I glanced at the possibly relevant .c files and none were 300 SLOC or even LOC. That left only the .h file. I had no idea you could even provide implementation in .h files. I mean in hindsight that seems perfectly cromulent, if maybe still questionably intuitive.
Is this common practice? I’ve been assuming header files are used for unimplemented type definitions similar to TypeScript .d.ts files. Is this wildly wrong to assume?
For small libraries, yes
They make a great deal of sense for libraries used mainly in small programs or small parts of big programs.
By traditional reckoning, you’re almost correct, but this is an exception.
Unlike many other languages (including TypeScript AFAIK), C and C++ compilers are defined to process a self-contained piece of text (the “compilation unit”), which must declare the type of everything it uses from the outside; those are then linked together into an executable with external references bound by name, with the types blindly assumed to be correct. (The linker works at the assembly level, not the C level, the types are already gone.) The usual workaround is to have the preprocessor, which puts together said piece of text[1], pull in the declarations from a common source, the “headers”, just plain insert the declaration text into the source file. Thus the headers play a similar role to .d.ts files, but the toolchain does not impose any convention on how things are arranged in files, unlike in TypeScript, Go, or Java.
There are two downsides for this: first, the declarations go through the compiler once for every source file that uses them, yielding slower compiles; second, if you want to consume a library in source form you’ll have to marry the build system for the library with the build system for your consumer. (The “build system” is the conceptual thing that knows how to set up the header search paths, which files to compile, and how to link or otherwise package the results into build artifacts.)
An alternative to this traditional organization is the “header-only library”; it mostly eliminates the second downside at the cost of exacerbating the first.
- In the C++ world, the dumb linker model I described above is something of a lie: a lot of C++ things (vtables, inline functions, template instances, etc.) do not actually have a well-defined compilation unit they belong to (“vague linkage”), so in the simplest approach the compiler generates a definition for every compilation unit and the linker has to (know enough to be able to) throw away all of these except one. (You see where the notoriously long C++ compile times come from.) A header-only library then just bites the bullet, defines everything inline, and has the linker sort them out. These have become fairly common over the last decade. (This does not help the compile times.)
- In the C or C-ish-C++ gamedev world, there’s a practical need to get prototypes or good-enough preliminary versions out the door quickly, so the library that is easiest to integrate across as much build systems as possible has an advantage. A different variety of header-only libraries has gained traction there. These have the header contain both declarations and implementation, but the implementation is guarded by a preprocessor macro; the user of the library defines that macro in a single compilation unit that they designate as owning that implementation. (This has worse “tree-shaking” characteristics than a well-organized static library, but if the library isn’t large that’s probably not a big deal, and in any case many common libraries, such as libjpeg and libtiff, are not well organized in this sense.)
The QOI reference implementation comes from the second tradition and is probably influenced by the popular stb libraries[2].
[1] Actually a token stream.
On the other hand, a parallel QOI encoder is relatively straightforward and will only have about 4*N bytes of compression penalty per image, where N is the number of threads, which is a trivial cost, if we talk about megapixel-scale images (as opposed to tiny icons).
Of course in some situations you don't care about compression efficiency that much.
In particular, using ML models for compression would get a free advantage because they're often several GBs where a traditional codec is KBs, so they can hide data in there, but most people wouldn't think of that as being part of the compressed message size.
But they could have very differently shaped dependency trees, especially if you somehow managed to not run an entropy coder as the last step of compression.
From a theoretical perspective, compressing something is largely a search problem; you're searching through a space of possible representations in order to find the smallest one. Search problems can often be parallelized.
Any concept of "independently compressed blocks" is a compromise because you could've made them depend on each other and made the entropy coder more efficient. But I was talking about GPGPU, which is completely unsuitable for it either way.
I intend to create an AVX2 based decoder but I had absolutely no time to work on side projects in the past three months.
You might also want to take a look at this streaming encoder if you want to encode large files with a tiny memory footprint : https://github.com/MKCG/php-qoi/blob/main/src/FFI/lib/qoi.c
Truly my bafflement is infinite as to why people keep dragging in PDF when all they make is a bunch of text with maybe a few images or tables. My guess is, those people just hate and wish constant suffering upon everyone who doesn't have a 14" portrait-oriented screen nor has to fumble with paper.
Asking for PDF is also bitterly ironic in the context of QOI.
byte 0-3: magic code
byte 3-10: 64-bit index into global decoder table
byte 11-...: compressed data
You glossed over the most difficult part of the specification.
Whether you provide the file format encoding/decoding as wasm or C reference implementation is not going to matter much in practice outside the web sphere, imo. You may argue that having a standard of wasm implementations is innovative, but if you're inside something browser-like, that's more or less the same as "just pull in something.js to decode this".
I don't think "download a new decoder from the internet occasionally" is as small of a problem as you make it out to be - in this case, an application could just as easily pull an update of itself to support a new file format directly. And you still get the essentially the same inertia as now for adoption of new formats because someone somewhere might not be able to update decoders.
Then there's also the issue of "how many copies of all those wasm blobs are you gonna have around on your system if every application uses this format". Which means you're now re-inventing system libraries in js/wasm. Talk about javascript eating the world...
But, optimistically speaking, your proposal could make speed of iteration in image file formats faster by streamlining adoption of new formats. Which could be a good thing.
I was wondering if someone would notice that ;) What it amounts to is basically a package manager for image formats.
But it's the idea that matters here, not the implementation. If we want our data to be readable in 100 years from now, we better base it on some highly standard common format. That format could be WebAssembly.
[1] http://mattmahoney.net/dc/zpaq.html
If instead PNG was implemented as a definition of the metadata format, the "filter" stuff for making pixels more compressible, and a compression field that references a webassembly implementation of the compression method then libraries could still use their own optimized implementation for compression methods they know, but fall back to downloading the webassembly version for any method they don't know natively. You would have perfect backwards compatibility and could evolve the file format as technology advances.
The advantage of webassembly in that context is of course that it's trivial to sandbox, and the snippets don't need access to anything but their input.
You find someone to pollute the "global decoder table" and you can introduce all sorts of fun problems, many of which turn into "I can't replicate it here (because I cached a working decoder, or the malicious decoder is only shipped to specific clients)"
TBH, I don't think we want external entity injection and Turing-complete languages in our image formats.
You also create a bunch of permanent assumptions in any of the encoders. Today, the "image data" it expects to return might be, say, an uncompressed 48-bit RGBA bitmap. What if the next generation of image formats can do more or different? Say, volumetric image formats for VR or holographic systems? You'd need a way to signal what you're getting in the metadata, which would then have to be open-ended enough to satisfy future needs, AND reliably enforced. (I'm imagining decoders that don't bother explicitly specifying all the return format properties, because in CURRENT_YEAR, only one type made sense).
Meanwhile, people are using WebAssembly and Javascript all the time, from untrusted sources.
You can of course just have a sequence of individually compressed frames, just as you can do with PNG, TARGA, or JPEG, but these are not usually the ways you would want to distribute the video due to the huge sizes.
2D image compression is missing a dimension. Much of the savings to be had in a video compression algorithm are going to be based upon the similarity between frames (ie. across time) rather than within a given frame. Therefore, an algorithm that is designed only for the 2D image is not going to deliver the goods when applied to video. An example would be animated GIF. It's terrible.
It would be hugely helped by being able to look at the previous frame.
If the description "QOI is simple. The reference en-/decoder fits in about 300 lines of C." is correct, then at the very least they share the same goals, so the "nothing" might be an exaggeration.