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

21–30 of 303 posts

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

#21

Post by mkl »

ur-whale wrote: post #14
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?

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.

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

#22

Post by EdSchouten »

mkl wrote: post #12
lifthrasiir wrote: post #8

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

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.

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

#23

Post by jiggawatts »

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 treating char* as "text" without specifying the code page. It could be UTF8. Or Latin-1. Or something else. You don't know. Other people don't know. There's often no way to tell.

Similarly with colour spaces: sRGB, Display P3, and Adobe RGB are just close enough to be easily confused, but end up looking subtly wrong if mixed up.

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

#24

Post by giorgioz »

>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

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

#26

Post by ChrisMarshallNY »

mkl wrote: post #21
ur-whale wrote: post #14

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

The original C++ templates used to be entirely contained in the headers. I assume that is no longer the case, but it has been a long time, since I wrote C++.

When I was writing template SDKs, the headers were pretty much the entirety of the library.

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

#27

Post by mkl »

phoboslab wrote: post #16
Ono-Sendai wrote: post #13

Very cool. Typo: "I barely understand how Huffman Coding and DTC works" I guess you mean DCT? (discrete cosine transform) One other thought: To make it so that compression and decompression can be multithreaded, you might want to 'reset' the stream every N rows. (i.e. break any RLE runs, start from a colour literal). This would allow a bunch of threads to start at different places in the image, in parallel. There wou…

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 you might want to change "(really just r^g^b^a)" to "(really just (r^g^b^a)%64)".

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

#28

Post by tda »

j-pb wrote: post #6

> 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

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

#29

Post by flohofwoe »

lifthrasiir wrote: post #11
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?

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 the preprocessor and compile the implementation only once for the whole project.

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

#30

Post by pedrocr »

These kinds of formats have been somewhat explored by camera makers for their raw formats. Since the computing resources in the cameras can be quite limited there are a few formats that try to occupy this space of simplicity with still some tricks for compression. Samsung's various SRW encodings remind me most of this:

https://github.com/pedrocr/rawloader/blob/a59bb78d156277781a...

Post reply on HN