Looks like PCX on steroids
QOI: Lossless Image Compression in O(n) Time
61–70 of 303 posts
Re: QOI: Lossless Image Compression in O(n) Time
#62Looks nice!
Did you try fuzzing your implementation (e.g. with AFL++ or libfuzzer)? Codecs and especially decoders written in C that handle untrusted binary data are quite worthwhile targets for fuzzing.
Re: QOI: Lossless Image Compression in O(n) Time
#63Really cool encoding, it is a bit incredible that such simple rules can archive such good results.
It is so interesting that if the image have few colors, method #2 alone (An index into a previously seen pixel) encodes the whole image into an indexed colour space (with the hash table becoming the pallet).
Ive seen already some comments recommending adding some vertical locality by tiling, Hilbert order, or Z order. I have yet another different vertical locality suggestion to try:
While encoding/decoding keep a ring buffer the size of one full line of the image, storing each encoded/decoded bit there. Then add a variation of method #3 (The difference to the previous pixel) which instead encodes the difference to the pixel above the current (the last pixel from the ring buffer). Maybe, due to the limited "tag" space it would not be worth it to implement it for DIFF8, but only for DIFF16 (taking one bit from red to the additional tag bit) and DIFF24 (I'm not sure which bit I would steal there).
Edit: Also, when thinking about video encoding in the future you may want to keep a ring buffer fitting the full last frame of video. And then temporal locality is probably even more important, so then you may want to change the tags to encode more commands relating to the pixel from the previous frame.
Re: QOI: Lossless Image Compression in O(n) Time
#64Earlier quoted context omitted.
Thanks, fixed! I'll probably investigate "resetting" the stream to allow for multithreaded en-/decode when I try to roll this into a video codec.
Even better might be breaking it into tiles, so you get some vertical locality happening as well as horizontal. It would be interesting to know which strategy is used for each pixel. Have you tried making maps of that with four different colours? Particularly interesting would be how much the cache is used and also how often it replaces a colour that it could have used later. Maybe there's a better colour hash. BTW y…
I really like the trick of caching previously-seen pixels by value rather than position. Very nifty!
I was thinking this would combine well with progressive rendering (i.e. store pixels in mipmap-style order) so the cache is warmed up with spread of pixels across the image rather than just scanline order. That doesn’t make it parallelizable in the way tiling does, though, hmm.
Another tweak that would probably help is having the file specify a rotation (or even a full mapping table) for each component of the hash, so a clever encoder can pick values that minimise collisions. (A fast encoder can just use all-zeroes to get the same behaviour as before.)
Re: QOI: Lossless Image Compression in O(n) Time
#65Earlier quoted context omitted.
Packing the entire library in a header file is a somewhat recent and much welcome trend. See for example: https://github.com/nothings/stb https://github.com/nothings/single_file_libs
I wouldn't call it recent. Boost has been doing it since it was started in the late 1990s.
Boost did it because C++ template definitions must be in headers.
That seems unrelated to this idea that C code using it is equally reasonable. That's a developer choice.
Re: QOI: Lossless Image Compression in O(n) Time
#66>I can almost picture the meeting of the Moving Picture Experts Group where some random suit demanded there to be a way to indicate a video stream is copyrighted. And thus, the copyright bit flag made its way into the standard and successfully STOPPED MOVIE PIRACY BEFORE IT EVEN BEGAN. This bit made me laugh out loud :D
I rather wonder if things like this are used to encode a proof of intent.
If something is marked as copyrighted, it may be trivial to remove the mark, but at least you had to remove the mark, and that's evidence of intent rather than ignorance.
Re: QOI: Lossless Image Compression in O(n) Time
#67This is a great project, but personally I feel that there are lots of uses for uncompressed images (ie. random access, ready to render straight away), and lots of uses for well compressed lossless, but little use for 'slightly compressed' images. The normal argument for 'slightly compressed' images is that they can be decompressed with very few CPU cycles, but the reality is that with modern platforms lossless image…
“Slightly compressed” is heavily used in 3D graphics -- see ETC2, DXT, etc.
It’s useful because the size savings apply in memory, because decompression is so cheap it can be done on the fly.
It has to be lossy because you want a guaranteed fixed-rate compression ratio (eg 4x) and there’s no way to do that losslessly.
Re: QOI: Lossless Image Compression in O(n) Time
#68QOI_DIFF24 { u8 tag : 4; // b1110 u8 dr : 5; // 5-bit red channel difference: -15..16 u8 dg : 5; // 5-bit green channel difference: -15..16 u8 db : 5; // 5-bit blue channel difference: -15..16 u8 da : 5; // 5-bit alpha channel difference: -15..16 } It bothers me more than it should that the 5-bit signed differences aren't -16..15 matching two's complement but -15..16 instead.
Yes, this is baffling. Wonder if the format could still be amended to fix this?
Re: QOI: Lossless Image Compression in O(n) Time
#69this is so satisfying to see. kudos to developer!
Re: QOI: Lossless Image Compression in O(n) Time
#70Wondering how well this does on noisy / grainy images since it relies so much on pixel similarity.
Noisy but around recurring or slighly different pixels would achieve a 1:4 compression rate