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

151–160 of 303 posts

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

#151

Post by j-pb »

formerly_proven wrote: post #82
j-pb wrote: post #45

Earlier quoted context omitted.

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) Though a blocked iteration order should perform better due to better locality.

Thanks for the pointer!

If anybody else want to know how this works:

https://stackoverflow.com/questions/30539347/2d-morton-code-...

https://en.wikipedia.org/wiki/Carry-less_product

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

#152

Post by sltkr »

flohofwoe wrote: post #87
sltkr wrote: post #85

Earlier quoted context omitted.

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. Jus…

> In general, STB-style headers simplify C/C++ build system shenanigans.

Too vague. How is it better, concretely?

> E.g. one benefit is that you can configure the implementation via preprocessor defines without the defines leaking into the build system

That's not a benefit. How is this:

   #define LIB_IMPLEMENTATION
   #define LIB_KNOB 123
   #include "lib.h"
Any better than the two-file version:

   #define LIB_KNOB 123
   #include "lib.c"
?

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

I'm not sure what this means. Can you give an example? Is this being used in the above library?

> PS: but also see: https://github.com/nothings/stb#why-single-file-headers

OK, that only offers this explanation:

> Why not two files, one a header and one an implementation? The difference between 10 files and 9 files is not a big deal, but the difference between 2 files and 1 file is a big deal. You don't need to zip or tar the files up, you don't have to remember to attach two files, etc.

This is kind of nonsense to me. The difference between 2 files and 1 file is barely relevant, and doesn't weigh against the awkwardness of having no clear distinction between declarations and definitions, and having to pull in definitions by setting a magic preprocessor header.

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

#153

Post by kaetemi »

sam0x17 wrote: post #141
kaetemi wrote: post #121

Earlier quoted context omitted.

Because your pixels need to transform from the image color profile to the display color profile. By default this all falls back to sRGB, which is not the "ground truth pixel value" you may be assuming it is.

Right, which begs the question why on earth would there be more than one image color profile. The image color profile should just be implied and the same everywhere.

For correct editing operations, and correct display. Sadly, it's not pedantry, it's reality.

The 0.5 value is not half the brightness of 1.0 in sRGB. It merely means half the power output to your CRT.

If you want correct editing operations, you need to work in linear RGB.

It gets more fun. What is white? The color of your backlight? The color of white paper under your particular desk light?

And what is black? Is it pure darkness, or the black ink of your printer? Does your printer represent pure black, or dark gray?

We're stuck with images stored in the display profile of old CRTs by default, because that was the most practical option at the time.

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

#154

Post by nightcracker »

minus7 wrote: post #76
orlp wrote: post #15

Earlier quoted context omitted.

When I download that PNG file it is 10785 KB. If I re-encode it using FLIF 0.4 (to my knowledge still the best off-the-shelf lossless image compression) it is 7368 KB. That's 57% of the size of qoi, quite a lot smaller. You pay for it in encode/decode time though.

FLIF has been superseded[1] by JPEG XL, which, in my very limited testing, performed better (speed and compression-wise; libjxl) than FLIF. Interesting though that FLIF 0.4 was released 3 days ago. I haven't checked out that new release (and won't), but the previous one wasn't great code and was a pain to use (ended up using its CLI instead of the lib). We ended up going back to PNG because of interoperability and sp…

Yes, I am aware it has been 'superseded' but in my experience for lossless compression it's still usually better.

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

#155

Post by olaulaja »

tda wrote: post #28
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

Based on some quick* testing using z-order instead of going row by row ends up taking 1-10% less space. Most images were on the lower end but I didn't run into any taking more space.

* Swapping to z-order requires about 5 lines of changes if you ignore all the little edge cases like non power-of-two image sizes. Images used in testing may or may not be representative of anything.

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

#156

Post by BlueTemplar »

superjan wrote: post #137
sbrki wrote: post #75

Very nice. Regarding the comments about complexity of existing formats - I agree, with the exception of PNG. In terms of complexity, QOI is very similar to PNG filtering phases, i.e. when you strip primary compression phase (Huffman coding) from PNG. Also, I admire how the author combined a lot of common and cool tricks into QOI: - Block tags form a sort of a prefix code, making it easy to differentiate block types w…

Traditional compression research usually prioritized compression ratio, so more images would fit on your floppy disks and were faster to download over 28.8k modems. It usually means increased complexity. Png has it’s own story as it’s #1 design goal was to avoid techniques that were patented at the time. So they combined a simple set of prepasses with zip/gzip compression. There were better techniques known at the ti…

The most important is probably the difference between lossy and lossless compression...

(The GP-mentioned Bink is lossy ! Then he also for some reason uses a picture tending towards photo realistic which does NOT play well with lossless !)

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

#157

Post by javajosh »

Very cool - I hope browsers support this soon!

Funny meta comment: when I read "offering a 20x-50x speedup in compression and 3x-4x speedup in decompression" I caught myself reacting with disappointment to the "only" 3x-4x speed up. This is funny because 3x improvement is enormous; it's just small compared to 30x. There's a lesson somewhere in there about sharing stats together to achieve an emotional effect.

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

#158

Post by bno1 »

bob1029 wrote: post #135

This is very impressive work. One thing I did recognize after my last trip into the rabbit hole - JPEG can be the fastest format by orders of magnitude if you are using an appropriate encoder. The project mentions 20x-50x speedups over PNG which are commendable, but once you throw LibJpegTurbo into the mix (it does use SIMD), you will find a substantially different equation on your hands. I can do 1080p 4:4:4 JPEG en…

Jpeg is not losses though

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

#159

Post by sam0x17 »

kaetemi wrote: post #153
sam0x17 wrote: post #141

Earlier quoted context omitted.

Right, which begs the question why on earth would there be more than one image color profile. The image color profile should just be implied and the same everywhere.

For correct editing operations, and correct display. Sadly, it's not pedantry, it's reality. The 0.5 value is not half the brightness of 1.0 in sRGB. It merely means half the power output to your CRT. If you want correct editing operations, you need to work in linear RGB. It gets more fun. What is white? The color of your backlight? The color of white paper under your particular desk light? And what is black? Is it p…

> We're stuck with images stored in the display profile of old CRTs by default, because that was the most practical option at the time.

The analogue in photography is photographs lose color clarity and fade as they age. Why should I care if this is the case in images as display technology evolves when this is already a problem with every physical medium?

> For correct editing operations, and correct display. Sadly, it's not pedantry, it's reality.

I've been designing images and graphics for the web and sometimes for print off and on as a regular part of my various job functions since ~2009 and I have yet to see a situation where a color profile on an image isn't a huge pain and something that needs to be stripped away to get seemingly correct results.

Back to my point, I still don't see the value of having a color profile applied to an image. Images exist in the ether as platonic ideals, and we try to approximate them with our various display technologies. Why complicate the matter by also having multiple "flavors" of the platonic ideal itself? When I say (255, 0, 0), I expect the display to show me its best approximation of red. When I say (255, 255, 255), I expect the display to show me something as close to white as possible (and at the brightest possible setting). When I say (0, 0, 0), I expect the display to show me something that looks as close to black as possible. It's up to the display technology to decide whether this means just turn off that pixel on the screen or disengage the backlight or do whatever, but at the end of the day it's just trying to approximate black.

This is complicated enough, why do I need an image that will look good on only one kind of display and will have it's greens look pink on other displays. Isn't having a color profile for the display enough?

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

#160

Post by jameshart »

zosoworld wrote: post #25

I'm wondering how scalable would this be for hyperspectral images, with 25 channels for example. I'm guessing it's just repeating the processing for RGB channels but for 25?

Very much the kind of expert group design-by-committee type of requirement that this simple compression scheme was designed not to handle.

Since this scheme works primarily on exact cross-channel pixel matches, no. No it won’t work well for 25 channel images.

Which is a good thing. Most people are not trying to encode 25 channel hyperspectral data and if they are they can use their own format designed well for that purpose (or a committee-derived format that handles it adequately).

Or they can split the 25 channels across 7 4 channel images and encode them using this.

Post reply on HN