QOI_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
}
QOI: Lossless Image Compression in O(n) Time
31–40 of 303 posts
Re: QOI: Lossless Image Compression in O(n) Time
#32tl;dr: 00xxxxxx - copy (x+1)-th last EXPLICITLY ENCODED pixel (i.e. ignoring repeats) 010xxxxx - repeat the last pixel x+1 times 011xxxxx xxxxxxxx - repeat the last pixel x+33 times 10rrggbb - copy the last pixel and adjust RGB by (r-1, g-1, b-1) 110rrrrr ggggbbbb - copy the last pixel and adjust RGB by (r-15, g-7, b-7) 1110rrrr rgggggbb bbbaaaaa - copy the last pixel and adjust RGBA by (r-15, g-15, b-15, a-15) 1111R…
This is so neat. Reminds me the recent LZ4 post who manually hand tweaking the encoding one could still create a decent compression boosts after all these decades.
Re: QOI: Lossless Image Compression in O(n) Time
#33Waawh, one would think (certainly, I personally thought) that all the _simple_ compression algorithms would have been discovered and build by now...
Interesting I have the opposite view. From intuition I would think there is an unbounded set of simple compression algorithms. You can probably make much more effective simple compression algorithms by making basic assumptions about the type of image.
Re: QOI: Lossless Image Compression in O(n) Time
#34Earlier 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 or C++ stdlib headers are different than STB-style single-file-libraries though in that the implementation code is inline and needs to be parsed each time the header is included.
Re: QOI: Lossless Image Compression in O(n) Time
#35tl;dr: 00xxxxxx - copy (x+1)-th last EXPLICITLY ENCODED pixel (i.e. ignoring repeats) 010xxxxx - repeat the last pixel x+1 times 011xxxxx xxxxxxxx - repeat the last pixel x+33 times 10rrggbb - copy the last pixel and adjust RGB by (r-1, g-1, b-1) 110rrrrr ggggbbbb - copy the last pixel and adjust RGB by (r-15, g-7, b-7) 1110rrrr rgggggbb bbbaaaaa - copy the last pixel and adjust RGBA by (r-15, g-15, b-15, a-15) 1111R…
You might be able to do better compression by traversing the pixels in Hilbert [1] order or Z [2] order, to take into account vertical neighbours as well as horizontal. It might cost time or space though, as you couldn't stream the pixels through it anymore - you'd need them all in memory. [1] https://en.wikipedia.org/wiki/Hilbert_curve [2] https://en.wikipedia.org/wiki/Z-order_curve
I wonder if the pixel data were transformed to/from a different order, before and after the compression/decompression, if that would speed things up without introducing too much slowdown of its own?
Re: QOI: Lossless Image Compression in O(n) Time
#36This is as cool as it gets. I have a honest question about the source code, a lot of time since I coded anything meaningful in C, but I remember the header files did not have that much code on it, while here I see most of the code is in the header file. Why is this the case? Inline compilation? What are the advantages?
Single header libraries are hugely more ergonomic and easy to use. Just get the file, #include it and you're done! Most C libraries on GitHub prefer this mode of distribution now
Re: QOI: Lossless Image Compression in O(n) Time
#37Earlier quoted context omitted.
You might be able to do better compression by traversing the pixels in Hilbert [1] order or Z [2] order, to take into account vertical neighbours as well as horizontal. It might cost time or space though, as you couldn't stream the pixels through it anymore - you'd need them all in memory. [1] https://en.wikipedia.org/wiki/Hilbert_curve [2] https://en.wikipedia.org/wiki/Z-order_curve
The nice thing is if M >= B^2 (i.e., total memory is large enough to fit a square region of the image, where each row/column of the square fits a full block/page of memory), you can transform from row/column order to Hilbert/Z-order without needing to do more I/Os. So you can't do such a conversion in a streaming fashion, but there is no need to load all data in memory either.
See also: Intel's guide to looping over smaller chunks of 2D arrays for better cache utilization:
https://www.intel.com/content/www/us/en/developer/articles/t...
Re: QOI: Lossless Image Compression in O(n) Time
#38>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
> This bit made me laugh out loud :D
Yeah, it's funny, until you actually go read the MPEG spec. documentation.
Then any and all inklings of laughter will very quickly evaporate.
Re: QOI: Lossless Image Compression in O(n) Time
#39Wondering how well this does on noisy / grainy images since it relies so much on pixel similarity.
Re: QOI: Lossless Image Compression in O(n) Time
#40> To keep things O(n) when encoding, there's only one lookup into this array. The lookup position is determined by a “hash” of the rgba value (really just r^g^b^a). Is a bit imprecise. The algorithm would still be O(n) even with a linear search through the "seen pixel array", as it is bounded by 64 length and therefore a constant factor that gets eaten by the Big-O notation. Because of this hash the algorythm seems t…
I was about to post the same idea about a locality preserving pixel order. I was thinking about hilbert curves, never heard of z-curves. Would be nice to see if/how that affects the compression ratios. How surprising that a few simple principles can give quite a good image format
https://en.wikipedia.org/wiki/Z-order_curve
Related to this method, it's sometimes used for texture mapping on GPUs.