I am not familiar with image encodings, but isn’t the idea of complexity relative? For example getting rid of Hoffman encoding and byte aligning everything may be less complex for computers, but when making energy and area efficient hardware, we may not care that much about some of these things?
QOI: Lossless Image Compression in O(n) Time
81–90 of 303 posts
Re: QOI: Lossless Image Compression in O(n) Time
#82Earlier quoted context omitted.
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
After making the edit, I saw that someone made the same suggestion on twitter! Hilbert curves have slightly better locality than Z-curves, but Z-Curves are trivial to produce. If you have a N dimensional space over unsigned integers, then you can place each point on a one dimensional Z-Curve by interleaving their bits into a new integer. So for any point (X, Y) in the X-Y coordinates of an image the Z-Curve coordinat…
CPUs can do this quickly:
__m128i src = _mm_set_epi32(0, 0, x, y);
__m128i res = _mm_clmulepi64_si128(src, src, 0);
uint64_t zeorder = _mm_extract_epi32(res, 0) | (_mm_extract_epi32(res, 2) Re: QOI: Lossless Image Compression in O(n) Time
#83QOI_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.
Who knows? Maybe it's the result of a heuristic that achieves a slightly better compression ratio.
Re: QOI: Lossless Image Compression in O(n) Time
#84Earlier quoted context omitted.
This is patently so. Taken to absurd proportions, you can compress a specific rendition of the Mona Lisa with just one bit. 1 means Mona, and 0 is undefined behaviour.
Taking this a step further: 0 means that all subsequent bits contain an arbitrary PNG. Now your algorithm encodes any image, and still does Mona Lisa in one bit.
It's also almost as effective as PNG (plus one bit) for non-Mona Lisa images.
Re: QOI: Lossless Image Compression in O(n) Time
#85Earlier quoted context omitted.
There is a strong tradition of single-file C/C++ libraries [1] because it has been difficult to integrate larger C/C++ libraries into the codebase. [1] https://github.com/p-ranav/awesome-hpp
There's an important difference between STB-style 'single file libraries', and C++ 'stdlib-style' header-only-libraries: STB-style libraries put the implementation code into a separate section inside an "#ifdef IMPLEMENTATION" block, while most C++ header-only-libraries use inline code (and thus pay a higher compilation cost each time this header is included). STB-style libraries skip the implementation already in th…
So what's the compelling reason to ship these as a single source file, instead of using the more logical and standard solution of a single header and a single source file?
Unlike C++ header-only libraries, C libraries like this still need their implementation included exactly once.
I understand the benefits of keeping the implementation in a single source file (simplifies integrating in existing build systems, interprocedural optimizations, etc.) but combining the source and header files too makes them awkward to use, with little benefit beyond being able to claim "our implementation is only 1 file!" which is about as impressive as saying "our implementation is only 1 line!" if you've just deleted all the whitespace.
Re: QOI: Lossless Image Compression in O(n) Time
#86I know you don't like "design by committee" and overly complex formats. Also, the compression algorithm itself is somewhat independent of the "container format" that it's used with. However, if I may make a suggestion: If you do end up rolling your own container format for any reason, always include a way to store the colour space of the image! Treating RGB images as arrays of bytes without further tags is like treat…
Yes, also store the DPI. In general, allow arbitrary key-value pairs to be stored.
If you want any interop you'd better standardize some keys, allowing for extensions. Store those in key,len,data records and you have iff/ riff formats ... used by .avi and .wav formats.
Re: QOI: Lossless Image Compression in O(n) Time
#87Earlier quoted context omitted.
There's an important difference between STB-style 'single file libraries', and C++ 'stdlib-style' header-only-libraries: STB-style libraries put the implementation code into a separate section inside an "#ifdef IMPLEMENTATION" block, while most C++ header-only-libraries use inline code (and thus pay a higher compilation cost each time this header is included). STB-style libraries skip the implementation already in th…
So what's the compelling reason to ship these as a single source file, instead of using the more logical and standard solution of a single header and a single source file? Unlike C++ header-only libraries, C libraries like this still need their implementation included exactly once. I understand the benefits of keeping the implementation in a single source file (simplifies integrating in existing build systems, interp…
In general, STB-style headers simplify C/C++ build system shenanigans.
E.g. one benefit is that you can configure the implementation via preprocessor defines without the defines leaking into the build system. Just add the config defines in front of the implementation include.
It's also trivial to write "extension headers" which need to directly peek into the (otherwise private) implementation of the base library. Just include the extension header implementation after the base library implementation.
PS: but also see: https://github.com/nothings/stb#why-single-file-headers
Re: QOI: Lossless Image Compression in O(n) Time
#88Earlier quoted context omitted.
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.
This is patently so. Taken to absurd proportions, you can compress a specific rendition of the Mona Lisa with just one bit. 1 means Mona, and 0 is undefined behaviour.
Are we about to talk about Kolmolgorov complexity? you're damn right that we're about to talk about Kolmolgorov complexity! :)
Re: QOI: Lossless Image Compression in O(n) Time
#89>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.
Or a piece of software in your toolchain has been unaware of the bit and inadvertently stripped it.
Is that evidence of intent still?
Re: QOI: Lossless Image Compression in O(n) Time
#90Earlier 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
You could still stream the pixels, you'd just have to stream them in Z order. This may seem pedantic, but this applies to any mismatch between the order in which you store pixels and the order in which the format stores pixels. E.g. some file formats may be row-major, others column-major, some block-based (like JPEG) or a fancy interleaving scheme (like Adam7). Some might store the channels interleaved, others separa…
And formats like BMP are stored upside down...