Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

QOI: Lossless Image Compression in O(n) Time

phoboslab.org

Post reply on HN
Print view View original

91–100 of 303 posts

Re: QOI: Lossless Image Compression in O(n) Time

#91

Post by phkahler »

j-pb wrote: post #45
tda wrote: post #28

Earlier 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…

I added Z-order curve to a ray tracer many years ago. Rather than using nested loops over X and Y pixel coordinates I used a single loop and de-interleaved the count to get X and Y. My thought was that this would increase the cache hit rate due to the locality of the pixels. It worked and the speedup was on the order of 10 percent. Because images are rarely power of 2 or even the same in both dimensions I opted to make a list of 32x32 blocks and rendered the blocks in Z-order as well as the pixels within (which still helped vs just tiling).

Locality is a good thing to exploit.

Re: QOI: Lossless Image Compression in O(n) Time

#92

Post by phoboslab »

nightcracker wrote: post #31

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 } 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.

I should probably fix that. Is there a clever way to unpack a 5bit signed int other than treating it as unsigned and subtracting 16?

Re: QOI: Lossless Image Compression in O(n) Time

#93

Post by phoboslab »

carrolldunham wrote: post #59

Could a hash collision make it inexact? so not guaranteed lossless?

No, the encoder checks if the color at the hashed value really matches before storing the QOI_INDEX. There's probably better ways to hash it, but this just seemed "good enough".

Re: QOI: Lossless Image Compression in O(n) Time

#94

Post by adgjlsfhk1 »

phoboslab wrote: post #92
nightcracker wrote: post #31

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 } 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.

I should probably fix that. Is there a clever way to unpack a 5bit signed int other than treating it as unsigned and subtracting 16?

That seems easiest.

Re: QOI: Lossless Image Compression in O(n) Time

#95

Post by phkahler »

CornCobs wrote: post #36
pantulis wrote: post #10

This 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

>> 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

I find that odd. How is that significantly better than dropping 2 files into a project and #including the header? A good build system should just compile all the C or C++ files in a given place, so nothing needs to be changed other than dropping the files in and #include where called from.

Re: QOI: Lossless Image Compression in O(n) Time

#97

Post by fabrixxm »

jiggawatts wrote: post #23

I 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…

It has data size in header: https://github.com/phoboslab/qoi/blob/master/qoi.h#L77-L82 Just put exif info after data :P

Re: QOI: Lossless Image Compression in O(n) Time

#98

Post by lmm »

sltkr wrote: post #85
flohofwoe wrote: post #29

Earlier 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…

> 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?

C doesn't have a packaging format or dependency manager, so having to keep track of two files would be pretty cumbersome.

Re: QOI: Lossless Image Compression in O(n) Time

#99

Post by user-the-name »

j-pb wrote: post #45
tda wrote: post #28

Earlier 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…

Hilbert curves are not that much more complex. Maybe ten or so lines of code. Interleaving bits is already a pretty complicated operations if you don't have builtins for it.
Post reply on HN