> It losslessy compresses images to a similar size of PNG
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.
In the other direction, you can target a subset of PNG to get less optimized images but with QOI-like encode and decode speed: https://github.com/richgel999/fpng
What command are you using? I find `ect --strict -9` to be extremely fast, much better than oxipng or zopfli. `-9` provides the maximum compression level built in to the program; you could use the advanced options like `--allfilters-b` but I've found that this produces negligible additional compression (similar to zopfli's advanced modes) and mostly just go with `-9`.
As I said in the OP, optimizing the seven test images provided by the QOI webpage took only a few seconds.
You're contradicting yourself. Either you have used `--allfilters-b --pal_sort=120 --mt-deflate=$(nproc)` and the quoted text in my previous post is true, or you haven't, and then the quote is false.
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.
The PNG format basically boils down to "encode pixel values as the difference to previous pixels to make it more compressible, compress with deflate, add metadata". Zipping it won't improve on that.
If you're willing to break compatibility anyways you could however improve PNG by substituting a better compression algorithm like zstd or lzma.
This is not true at all. PNG uses the DEFLATE algorithm which is a perfectly general algorithm for compressing data, it's not just a matter of encoding pixel differences. That's the real reason it doesn't make sense to zip a PNG - the internal data in the image is literally already zipped (the zip format uses DEFLATE).
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 apologize to wongarsu - I'm mildly dyslexic, and I missed the part of their comment where they mentioned that PNG uses DEFLATE, and leaving out that part totally changes the meaning of the comment. Their comment makes total sense after I happened to reread it.
but adding .zip extension doesn't make it friendly as an image format. I would never ever ever ever want to put <img src="imagename.zip"> into code any where. So if you're making a new image type that doesn't fit in a known image container, then create a new MIME type.
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!
Unfortunately not everything compresses well with QOI. I have considered using it for our company but then did some tests with real images from real (noisy, low-res) cameras. The result is that in many cases QOI did not offer much compression at all over just storing all the raw bytes and in some cases it even increased the size.
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.
I think the point in the design space makes more sense for game textures than sensor input. When you consider the encoding primitives, it'll only do well on images which have a mix of (a) limited palette, (b) blocks of constant color and (c) smooth gradients.
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.
I haven't evaluated this personally but the (close to?) lossless raw sensor image compression from Dotphoton [1] seems like an interesting approach for getting around the issue of sensor noise in image compression. However the implementation details are disappointly vague, as it's a proprietary product.
Awesome! Also, a PSA about the next image format for the web: JPEG XL (.jxl) - should be on everyone's radar. Already supported by browsers (behind a feature flag). Has lossy and lossless mode.
> lossless JXL can be faster and compress better than QOI
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.
There is a video on Youtube explaining some image formats. At the end of the video, QOI is mentioned as well. Check this out
https://youtu.be/EFUYNoFRHQI
So it only compresses to the size of PNG, but it's faster to decode? I could see this being useful for something like training sets for AI, if loading is fast enough you could avoid saving raw pixel arrays.
QOI is not on the pareto frontier for compression [1], it is however extremely simple and is a nice introduction to data compression for anyone wanting to learn about the field.
Very unrelated and I really hope my admitted ignorance won’t be unwelcome, but I was quite curious and… let’s just say I’ve never been so curious about something written in C, much less written any myself.
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?
> 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?
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].
Good question. I've taken a look at the final revision of the spec ([1]) and it seems that parallelizing a QOI decoder may be non-trivial, because of back references. More over, it's possible to come up with QOI-encoded images which would see no speedup from any concurrent decoding (for example, if every single pixel refers to the previous).
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).
Compression is fundamentally not suitable for GPGPU, because if it can be parallelized then it's not compressed well enough. That's why codec acceleration all uses ASICs.
Of course in some situations you don't care about compression efficiency that much.
This doesn't seem correct? All the compression algorithms I have some amount of understanding of (that being JPEG and H.264; not a ton, but fairly widespread) have some concept of mostly-independently-compressed blocks. You also see in practice that many compression tools can use multiple threads.
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.
I wrote the multithreaded H.264 decoder in ffmpeg.
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.
That is a strange statement, most machine learning boils down to compression in essence (OK it is lossy, but any image quantisation is also lossy). E.g. autoencoders are compression algorithms: take the model as a dictionary and the latent space weights as compressed representation. For most algorithms you are right though. Particularly it is worth the effort to put things in to Asics as the "wiring" normally stays stable and you do not need the flexibility of gpgpus . Still also there is nothing that keeps you from using them e.g. for efficient parallel decoding.
I think it's axiomatically true and ML models get a pass on being inefficient because people are so busy being impressed by their magic tricks.
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.
Totally agree, tgeneral compression that requires the dictionary to be transmitted on every message is not the best use case (if there even is any). Minimal description length is actually a nice information theoretical measure to describe power of ML models to compress. However I have also seen tons of theoretical proof that probably there is no optimal compression method ( I looked at grammar vs entropy coding some time ago) hence there is probably no optimal hardware in general. In the end it depends on your assumption about the the data (quality, structure, size, chunking,...) you want to compress.
You realize that you can do such a format with HTML? And ‘print’ to PDF if you wish?
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
The global decoder table is maintained by a standards organization. For every occupied index, it contains a piece of WebAssembly code that decodes the data and produces an image and metadata. Advantage: no more dealing with various image formats and installing decoders libs; there is just 1 format that can be tuned to specific uses and it will be available hundreds of years into the future. The WebAssembly code can be hand-optimized into native code (or even hardware) for frequently used decoders. The only downside is that you might occasionally need to access the central code repository over the internet to download a decoder.
Cynically speaking, what you describe is more or less "take any file, prepend four magic bytes". The "index into global decoder table" is exactly what magic bytes are for in the first place. In other words, you're basically describing the thinnest possible container format.
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.
> Cynically speaking, what you describe is more or less "take any file, prepend four magic bytes".
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.
Applied a bit more surgically, this is actually a pretty good idea. Take for example PNG: the header for the actual image data contains a one-byte field titled "compression method" with only one valid value: 0 for deflate. The idea at the time was probably that deflate is great, but something better might come along. Now almost three decades later we have plenty of better compression algorithms, but still all PNGs are deflate, because anyone who sets that header field to anything other than 0 breaks compatibility with every other PNG implementation that already exists.
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).
If that is your taste, you should definitely take a look at zpaq [1] which uses an embedded bytecode with a not-too-long specification [2]. It is tuned for compression algorithms but any general algorithm can be programed; for example there is a project that turns zpaq into (slower) Brotli [3].
IIUC he is saying that there will be a 64-bit index into a global standards-maintained table, and the decoder is downloaded from said table. Not that the decoder is actually included with the image. The decoder itself would probably eventually be cached if not shipped with browsers by default.
Essentially good compression needs prediction. Here the previous pixels are used but it seems only from the row. Given that this is a linear decompression (not a progressive) it would help a lot to instead of looking just at the row, also look at the above row where the other previously seen neighbor pixels are. With something like arithmetic coding and only the previously seen neighbor pixels as prediction contexts with some tweaking one can quickly get better compression than PNG offers. Doing this in a short C implementation is left to the reader ;)
This format (or something similar) may work for my project. I’ve designed a set of low color images for a retro TRS-80 computer I own and would like to write a slot machine app for. With its low processing power and my self-imposed requirement to write it in the BASIC language I would have used as a kid, the machine doesn’t have a lot of processing power or memory to do decompression stuff. Some of the concepts here seem simple enough to implement. I can probably reduce it even farther since I have less colors.
It could have an application in remote desktop scenarios, but it would suffer when high entropy images are on screen, like photos in a web browser - the variance in output size for a fixed input may not be ideal.
It would be hugely helped by being able to look at the previous frame.
No. This is a very simple and reasonably efficient image format. It is notable for its simplicity and straightforward implementation, as well as its speed compared with png.
Video compression is typically not about "take each frame, and make it as small as possible". Video compression revolves around cleverly making use of deltas and segmenting the image so that you can reuse as much data as possible from previous frames/keyframes.
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.
I didn't read the spec, but I assume that if a single-picture format doesn't have the concept of making use of reference pictures (so previous or future frames), it's leaving _a lot_ of compression potential on the table.
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.
I'm no expert on this but I assume because it would be all keyframes? I.e. the format doesn't support encoding transitions from frame to frame. But I guess decent video support could be possible if you define video as pixel perfect animation, i.e. Animated GIF. These would of course not compete with traditional video.
Video is massive. Uncompressed 1080p video at 60fps is 1Gb per second, compared to ~5mbps for compressed video. QOI is great for pictures where 3-5x compression is about as good as you can do, but video compression is about getting close to 500x compression.
They hiked with torches, and one of them had a laptop named “Wolf’s lair”. Sure, they could be nazis or something, but those things do not exactly prove that.
Point is, no matter how suspicios you think that would look, I would not go as far as declaring it “Nazi dog whistling”.
Laptop called "Wolf's Lair"? Hiking at night with burning torches? Hmm, you're right... while it's no cast-iron proof, they could definitely be nazis or something.
I wouldn’t call anything “dog whistling” unless it was confirmed that this was its purpose. Otherwise, every single black metal band would be guilty of something or other. Intention matters.
> You are also missing some other “suspicious” facts.
Those two things I listed were the only two things asserted by the links provided. I would guess that actual nazis would perhaps show more signs, especially with so many people eager to find something, anything, to pin on them.
I mean, no? Black metal is about death, satanism, and the dark coldness of the grave. It’s entirely overt. I’m sure a few BM bands do engage in all kinds of signaling, but talking as an ex BM enthusiast, the nazi/fascist stuff is coming out of other genres. Power metal, death mean, eg., and there it is a minority as well.
Yes, that is exactly my point. BM might have elements in common with other, more questionable, factions, but this does not make BM’s style into “signaling”. Likewise, mere torches by themselves, is not necessarily signaling. I mean, nazis at one point thought that torches were cool, for normal human reasons. Might not normal people also think that torches are cool, for the same, normal human reasons?
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.
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.