6 ms·
QOIR: A fast, simple, lossless image file format
- kevmo314 4y ago> For example, if you have a relatively wimpy camera that streams out a 160×120 grayscale image, it might be fun to see how far you can push something like combining: I'm typically not one for self-promo but I did this with video and you can get 90% compression with exactly those three basic steps. RGB -> YUV420, delta encoding, then basically-upgraded-RLE. You can find the guide here: https://github.com/kevmo314/codec-from-scratch https://github.com/kevmo314/codec-from-scratch
- deleted 4y ago[deleted]
- vanderZwan 4y agoNice! The caveat being that this assumes we have little to no shot noise I guess? Since that is where lossy codecs typically beat lossless.
- kevmo314 4y agoYep adding noise would mess up the deltas which would reduce the efficiency. This can be mitigated with a quantizer, which I was hoping to write about next. I suspect it's possible to achieve 99% lossy compression without getting too complex to be understandable in the toy codec with a couple more of these similar techniques.
- graderjs 4y agoThanks! I just forked it. Do you know if Apache-2.0 code can be included into a closed source project?
- askiiart 4y ago[choosealicense](https://choosealicense.com/licenses/apache-2.0/ https://choosealicense.com/licenses/apache-2.0/)
- 8n4vidtmkvmk 4y agoI've been having a problem recently.. apparently every modern image format has a max of either 16K or 64K width or height. I generated a PNG with stable diffusion that was about 70K pixels tall and 2GB. never figured out how to compress it. jpg, webp and avif wouldn't accept it.
- adgjlsfhk1 4y agojpeg-xl should do it. It was specifically designed to make sure it can support crazy resolutions and number of channels.
- adgjlsfhk1 4y agoIt is also crazy to me that so many image formats have such small size caps. I understand not wanting to use extra space for small images, but I can't think of any reason to have a maximum image size smaller than your maximum hard drive size. You probably don't want to unconditionally store 8 bytes for width and height, but you could pretty easily make it only use 1 byte for small images and for anything big, you won't miss the extra 6 bytes.
- gyan 4y agoIt may have to do with limitations of allocating memory chunks on 32-bit machines when these formats were originally designed. The decoder allocates a contiguous buffer that can hold the whole image.
- chungy 4y agoWebP is recent enough that it shouldn't have even been a real concern. 16383×16383 even in 2010 was an absurdly small size. I've had PNGs and JPEGs with larger dimensions for longer than WebP has even existed.
- gfxgirl 4y agoMy guess the limits are because, WebP is based on WebM (video) I agree those limits are too small.
- gamegoblin 4y agoQOIR is an extension of QOI, discussed here: https://news.ycombinator.com/item?id=29328750 https://news.ycombinator.com/item?id=29328750
- kieckerjan 4y agoFor me the golden nugget in this piece is the Morris principle: "Code tends to be extended to its level of incomprehensibility."
- p0nce 4y agoAlso extended QOI to make QOIX, a triple codec that can also encode 10-bit and 1 and 2-channels images. So you could say it's 3x the complexity. https://github.com/AuburnSounds/gamut https://github.com/AuburnSounds/gamut
- vanderZwan 4y agoI'm wondering if anybody has tried adding PNG filters on top of QOI[0]. I have an idea of how to do it, and it should be fairly easy to build on top of a QOI encoder/decoder, but didn't get around to trying it out myself. Per the QOI spec it already has the "SUB" filter built in, in the form of QOI_OP_DIFF. Which is great, because that leaves exactly four PNG filters instead of five (meaning they only need two bits to store): NONE, UP, AVERAGE and PAETH. Here's how to add the filters: on a per-line basis, create a transformed line for each filter (so the original pixels, plus UP, AVERAGE and PAETH transformations). Then see how each of the arrays would compress, then pick the best one by treating it as if it was the original pixel input. In a separate array we keep track of which filter we picked for each line. When we've done this for the entire image, we basically have a plain QOI image but if we decompress it the output would show each line in its new transformation. To recover the original image we just have to reverse these transformations bottom-to-top. So we just have to append that array where we kept track of the filters we picked for each line, four picks per byte. Since we know the height of the image we don't need to mark the end of this stream. The added size overhead is effectively one byte per four lines. I expect speed overhead would be roughly 4x for encoding (since we brute-force try four transformations), and something very tiny for decoding (since all we need to do in the end is one single in-place pass over all pixels to undo the transformations). Also, because SUB is covered by QOI_OP_DIFF, this approach would implicitly support mixing each of these per-line filters with SUB, so it would be possible to have SUB+UP, SUB+AVERAGE and SUB+PAETH, and it would be on a per-pixel basis. Might be beneficial in some cases. [0] https://www.w3.org/TR/PNG-Filters.html https://www.w3.org/TR/PNG-Filters.html [1] https://qoiformat.org/qoi-specification.pdf https://qoiformat.org/qoi-specification.pdf
- p0nce 4y agoI'm not sure why your whole scanline would need a predictor that is top pixel, left pixel, or average. Shouldn't this be for 16 or 32 pixel max? The most popular QOI modification has been to take the average of top and left decoded pixels as predictor. I've tried to put more bits into selecting 4 possible pixels as predictors (for a single pixel), but it doesn't work that well because the previously encoded colors are already in the table. Predictor+diff encoding weren't as successful as one would expect, probably because there pixels are processed one by one. One design principle of QOI is to read input once to encode, so not sure if people would want to try 4x the scanline.
- andrewla 4y agoInterestingly they offer a "lossy" mode, which is something I've been thinking about a lot recently. In reality, the decoding of all image formats (that I'm aware of) is completely lossless (i.e. deterministic), even for jpeg. The encoding is where the lossy decisions are made. So it should be totally possible to take a lossless format, and ask the question -- how to minimally change the image to produce an image that compresses better? There are png pre-processors, like pngquant, that are somewhat lossy, but I wonder how far this can go -- the heuristics that pngquant uses, for example, are based on image processing heuristics, but it seems like it should be equally possible to use characteristics of the very specific compression systems used in a slightly more generic way. For LZ-based systems, I wonder if there is some more generic way of approaching this. Running it forwards, and saying "what is the cheapest prediction of the next byte given our table so far" is interesting, but running it backwards is also interesting, to say "what is the byte that will increase our hit rate as we move forward in the image". I played with this a little bit, trying to get farbfeld + bzip2 to produce lossy image compressions, but bzip2 is too complex to easily work with in this fashion. It seems like png has some possibilities here (to optimize against its filters) and QOI (and QOIR) seem to have good possibilities here because of the simplicity of their heuristics.
- skandau 4y agoThere is qoirsk, an improvement version of qoir. Please visit github.com/skandau/qoirsk