9 ms·
The QOI File Format Specification
- Aissen 5y agoThe experiment that led to this file format (QOI: Lossless Image Compression in O(n) Time) was discussed on HN: https://news.ycombinator.com/item?id=29328750 https://news.ycombinator.com/item?id=29328750
- choeger 5y agoThis is going to be super useful for educational purposes. I'd really like to see more file formats like this. There's already a bunch of minimal programming languages and even some operating systems. It's great value for learning stuff when you can implement a quite OK version of something in dozens of hours or less.
- ape4 5y agoI like how simple it is. Of course, getting a new format adopted is pretty difficult.
- formerly_proven 5y agoThis is very nice. If I had to nitpick something, I'd say choosing all-big-endian is kinda odd in 2021 but it's probably not a biggy even for something like this.
- thechao 5y agoSupport for 16/32b and fp-formats would've been nice -- the compressor is actually orthogonal to the bit width of the channels. Custom fp-compression usually just unvolves moving the sign bit into the LSB, and delta encoding the mantissa separately from the exponent -- although the latter isn't as important.
- adgjlsfhk1 5y agoThis was my initial thought, but given how the format is designed, you would pretty much have to make a whole new set of tags for 16 or 32 bit images.
- thechao 5y agoYeah... seems like a small family would be in the right vein. I'm immediately drawn to a block format, but that'd probably double the complexity.
- phoboslab 5y agoWell, it's easier to read in a hex editor and seemed like the right thing to do for a "wire format". The only places where it matters is the header's width/height and order of RGB(A) data. Storing RGBA as ABGR is not a great choice, imho. If you want to be endian independent, you have to read one byte at a time anyway (or swap).
- mgaunard 5y agowhy are channels interleaved at all if speed of decompression was the goal?
- user-the-name 5y agoBecause almost everywhere you would use data will expect it as interleaved. Separating the channels would require a second pass to re-interleave the data.
- wheybags 5y agoStoring rgba as abgr is a terrible choice, but are you sure they're actually doing that?
- phoboslab 5y agoSorry, I see how my previous comment was misleading. To clarify: No, QOI is not doing that. QOI stores RGBA as R,G,B,A because it is big endian. Little endian would imply that RGBA is stored as A,B,G,R. Which was my argument against using LE for a file format.
- Taywee 5y agoI don't believe it would imply that, because those are independent elements. RGBA would still be stored as R, G, B, A unless you're considering each pixel as a single 32-bit integer. A C structure for the colors would even live in memory in the order you expect. Just like a string is still stored byte-by-byte even in little-endian contexts. LE vs BE would only affect multi-byte integers and floats, not arrays or structures of single-byte elements.
- MisterTea 5y agoHonestly no one should worry about endianess in 2021.
- gpvos 5y agoThe bytes in the compressed data aren't going to be aligned to 2-, 4- or 8-byte offsets, so the overhead is going to be nonexistent or negligible.
- IshKebab 5y agoThis is pretty cool. Though... > all data is now encoded as big-endian. Why? If the goal is to be fast and simple then surely little endian would make more sense given that basically all processors are little endian. Big endian just means you need to swap everything twice. Edit: Seems like I'm not the only person that thought this was a super weird choice: https://github.com/phoboslab/qoi/issues/36 https://github.com/phoboslab/qoi/issues/36 The reasoning is: > The file format for QOI will not change anymore.
- mahkoh 5y agoLooking at the spec, the only multi-byte data are the width/height in the header. So only two 4-byte swaps per file.
- politician 5y agoThe link contains a link to the discussion on QOI v2, https://github.com/nigeltao/qoi2-bikeshed/issues https://github.com/nigeltao/qoi2-bikeshed/issues.
- Zababa 5y agoI think refusing a 5% speedup to ensure that the format will not change fits really well with the goals of the project.
- Zababa 5y agoThere is, I think, one thing missing: a comprehensive test suite that checks all the possible edge cases. Edit: as you can see below, the benchmark also checks for correctness so you can disregard this.
- phoboslab 5y agoWhat exactly do you mean with "edge cases"? For what it's worth, the decoder has been fuzzed[1] and the benchmark suite[2] with 2800 images en-/ and decodes without losing any pixels, as checked by qoibench[3]. [1] https://github.com/phoboslab/qoi/blob/master/qoifuzz.c https://github.com/phoboslab/qoi/blob/master/qoifuzz.c [2] https://qoiformat.org/benchmark/ https://qoiformat.org/benchmark/ [3] https://github.com/phoboslab/qoi/blob/master/qoibench.c#L440-L445 https://github.com/phoboslab/qoi/blob/master/qoibench.c#L440...
- Zababa 5y agoOh, I didn't realize that the benchmark also checked for correctness.
- robalni 5y agoWhen looking at the benchmark result and image size, it seems like this format is good at images that have horizontal structures or where the same color is repeated often. It's not good at vertical structures, including images with enlarged pixels (where one row is identical to the one above). I think the main reason for that is that PNG has a filter pass that can look at the row of pixels above, while this format only looks to the left. Example of image with vertical gradients: https://qoiformat.org/benchmark/images/icon_512/apps-preferences-desktop-locale.png https://qoiformat.org/benchmark/images/icon_512/apps-prefere... - qoi compresses to 186kb and libpng to 25kb Example of image with horizontal structure and repeated colors: https://qoiformat.org/benchmark/images/textures_pk/mod_walldetail1.png https://qoiformat.org/benchmark/images/textures_pk/mod_walld... - qoi compresses to 21kb and libpng to 33kb
- adgjlsfhk1 5y agoOne thing worth noting is that QOI can be pretty easily wrapped with something else to change pixel traversal order. If you want higher compression, I'd recommend wrapping QOI with ZSTD (or similar) compression on the output, and something to change the pixel traversal order on the input.
- Akronymus 5y ago> and something to change the pixel traversal order on the input. I could see a variety of space filling curves working for that.
- ape4 5y agoSince its simple and there have been vulnerabilities in other image readers... a mathematically proven reader might be a nice thing to sell it.
- fleabitdev 5y agoI've dealt with image decoding for a game engine before. The images in question were large pixel-art texture atlases, stored as PNG files and loaded at startup. Their slow decoding speed caught me by surprise, given that the file format is 25 years old! The reason turned out to be that Deflate's design makes it very hard to parallelise or SIMD-accelerate. Even the best available decoders are basically forced to process a byte at a time, in a straight line from start to finish, which obviously isn't a good match for modern CPUs. The 3x to 4x decompression speedup here is nice, but I can't help but feel a little sad about how poorly this format is taking advantage of available compute resources. (The ultimate dream would be a format which is so parallel-friendly that you can just send the binary blob to the GPU and decompress it in a compute shader!) Even a rule like "each row is compressed separately, with a table of row lengths at the beginning of the file" might have been enough - this would have made compression ratios slightly worse, but complexity wouldn't have suffered too much. With only six different chunk types, we could perhaps imagine a branchless decoder where each row's decoding state is stored in its own SIMD lane, and the results for several rows are all emitted at the same time...
- wongarsu 5y agoApple apparently ships a PNG encoder that completely flushes the deflate stream every now and then, giving you additional offsets where you can start decompressing without dependencies on previous data. The offsets are then saved as a separate chunk in the PNG. Decoders aware of this can parallelize decoding using these offsets, everyone else can read it as normal. The proper solution would of course be to use something more modern than deflate, the PNG format even has a metadata field that specifies the used compression algorithm. But anything but deflate wouldn't be backwards compatible, so nobody seems to use that option.
- gpvos 5y agoThe Apple encoder only splits the PNG in the middle.[0] This was linked from a recent HN post about a hack that exploits this to have PNGs that display differently in some situations on Apple machines.[1] [0] https://www.hackerfactor.com/blog/index.php?/archives/895-Connecting-the-iDOTs.html https://www.hackerfactor.com/blog/index.php?/archives/895-Co... [1] https://news.ycombinator.com/item?id=29573792 https://news.ycombinator.com/item?id=29573792
- jonsneyers 5y agoSee also: https://twitter.com/jonsneyers/status/1472959101416226823?t=w0l2OhcPhg487IrO5OnX1w&s=19 https://twitter.com/jonsneyers/status/1472959101416226823?t=... On my laptop, QOI encodes a test corpus at about 78 MP/s to a density of about 8.0 bits per pixel. Fast png encoding with fpng is 71 MP/s and reaches about 7.8 bpp. Fast lossless jxl encoding can be done at 162 MP/s (single-core, faster with more cores) and reaches about 6.8 bpp. It can also be decoded in parallel, unlike QOI and PNG. It doesn't have a single-page spec though :)
- adgjlsfhk1 5y agoNote that the reference QOI implementation is not speed focused. Some of the other ones are almost twice as fast.
- pcwalton 5y agoNeat, this is impressive! The first thing that comes to mind is that it's not very amenable to parallel encoding or decoding, even less so than PNG. The fact that QOI_OP_INDEX could reach arbitrarily far back basically eliminates parallel decompression. But I guess the simplest workaround for that would be to just break up your images into tiles that are each decoded in parallel. You could imagine a simple wrapper format that specifies how to reconstruct a larger image out of such tiles, which would be amenable to parallelism (albeit still not easily implementable on GPU, though I guess you could wring a little bit of parallelism out of it from by using one GPU SIMD lane per RGBA channel). Of course, it's entirely possible that your decompression goes so fast it doesn't matter that it's sequential and you're bottlenecked on I/O in any reasonable use case…
- ErikCorry 5y agoI experimented with adding this to the embedded system Toit. I wrote up the experience here https://medium.com/@erik_68861/trying-out-the-quite-ok-image-format-in-toit-98e8db914573 https://medium.com/@erik_68861/trying-out-the-quite-ok-image... and also used it for this little demo on a 2 inch screen: https://twitter.com/erikcorry/status/1470023885026467848 https://twitter.com/erikcorry/status/1470023885026467848 It was pretty good, but in the end I don't think I'll be making it part of the graphics system. I would really like a bit of random access into the image without having to divide it up into multiple tiles. And the spec took a direction that didn't really suit me - i wanted to use it for Gui-like textures which have slabs of colours and anti-aliased edges with varying alpha. In the final version of the spec there's no way to code "the alpha changed, but the color is the same". without spending 5 bytes on a single pixel. Previously that took 2 bytes. So I'm still looking for a format with: * Very small amount of decode state (GIF's 16k is probably too much - PNG's 32k is certainly too much). * Fast decode (these embedded chips are not as fast as desktops). * Alpha channel (not just on-off like GIF) * A bit of random access like the parallel PNG, but hopefully less bolted-on.
- FullyFunctional 5y agoAll these points are spot on, but I want to reorder the priority. I cannot believe that a format is introduced in this millennium that doesn't have a single thought to aiding parallel access/decode. The single-thread focus will not age well; even low-end µProcessors are going multicore today, and going forward that will only accellerate.
- kevingadd 5y agoEven ignoring parallelism, images increasingly need to go straight to the GPU, so improving the performance of access on-GPU (I.E. using a GPU compressed texture format) can have a bigger positive impact on the user experience than making the file on disk smaller. Adopting Basis to compress your images could in practice be much better than adopting QOI, and it should be benchmarked against options like that along with PNG or JPEG.
- modeless 5y ago
- CodesInChaos 5y agoThe end marker feels awkward: * It shouldn't be necessary, since having encoded all pixels already implies you're at the end. * It complicates the encoding/decoding of the indexing operation.
- edflsafoiewq 5y agoIt doesn't really complicate the encoder. Any real encoder would never emit 7 OP_INDEX to the same index, it would use a RLE instead.
- louisstow 5y agoCan someone explain how it's lossless if there's a chance of hash collisions in the index?
- ErikCorry 5y agoThe encoder can always generate the code for a literal pixel if the required colour is not found in the index.
- adgjlsfhk1 5y agoTLDR is hash collisions are an explicit part of the format. Encode and Decode are both specified to use the same hash function, so the hash collisions will all cancel out.
- shdon 5y agoI honestly quite like this. Was looking for a quick way to store and transmit some small images both with and without alpha information without having to bring in a relatively large dependency like libpng and still have a modicum of compression. Having the whole thing in a single file without any external dependencies is quite cool. I especially appreciate that the spec is concise (yet clear) enough to fit on a single page and I was able to code a full encoder/decoder that generated bit-for-bit identical results to the reference implementation in just over an hour just by reading that spec.