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

171–180 of 303 posts

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

#171

Post by mmastrac »

dahart wrote: post #148

This is pretty neat! The compression rates and encode/decode rates are impressive for such a simple rule set. > SIMD acceleration for QOI would also be cool but (from my very limited knowledge about some SIMD instructions on ARM), the format doesn't seem to be well suited for it. Maybe someone with a bit more experience can shed some light? I don’t know about SIMD encoding, but for decoding at least, the core problem…

Wouldn't it make sense to transcode to a GPU-specific lossless, compressed format for rendering?

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

#172

Post by wizzwizz4 »

sltkr wrote: post #152
flohofwoe wrote: post #87

Earlier quoted context omitted.

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…

> The difference between 2 files and 1 file is barely relevant,

To you. To me doing Rust stuff, it's been quite helpful to have single-file C programs; it makes it a lot easier to compile and link things.

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

#173

Post by superjan »

BlueTemplar wrote: post #156
superjan wrote: post #137

Earlier quoted context omitted.

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

Yeah there’s a difference in techniques used for lossy vs lossless. But my point was that in compression research, runtime performance was much less important than compression performance, that was no different for lossy compression.

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

#174

Post by wizzwizz4 »

adgjlsfhk1 wrote: post #94
phoboslab wrote: post #92

Earlier quoted context omitted.

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.

Especially since your compiler will make it a super magical optimised version.

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

#175

Post by MauranKilom »

ball_of_lint wrote: post #161
sltkr wrote: post #53

Earlier quoted context omitted.

> Because of this hash the algorythm seems to do something else than first described though. Instead of "a running array of the 64 pixels it previously encountered", it's actually the previous 64 pixel _values_ previously encountered, which allows for much bigger jumpback. It's somewhere in between. Because these values are hashed into single slots, assuming that hash codes are random, the probability that a value is…

In an image with very limited colors you would have long runs of the same color and it would compress well from just the run-length encoding alone. Also, it's non-obvious that older values will be less useful. Going through the pixels in order like this doesn't preserve locality well, so older values may actually be closer to a given pixel than more recent ones.

> In an image with very limited colors you would have long runs of the same color and it would compress well from just the run-length encoding alone.

...unless those images are dithered. Which may be a relatively common thing to do in small color spaces!

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

#176

Post by contravariant »

demute wrote: post #131
kortex wrote: post #122

Earlier quoted context omitted.

No single color space is complete. Each has trade-offs. I would actually say that color profiles help get closer to ground truth, that is, rendering intent.

CIE XYZ is complete.

If you agree with their model of human vision anyway.

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

#177

Post by SavantIdiot »

What I like about this approach is that it requires zero differential calculus. People forgot that Radix2 DCTs come from a century's worth of advanced math in the S domain. This approach is applied-computer-science based, I can get my head around that a lot better than a Laplace/Z transform.

But what shocks me is how did absolutely no-one apply such a naive RLE in the 30 years of internet image formats?

Is this a case of "man reinvents wheel again because why do research" or is this exceptional?

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

#178

Post by cornstalks »

sam0x17 wrote: post #159
kaetemi wrote: post #153

Earlier quoted context omitted.

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, i…

> When I say (255, 0, 0), I expect the display to show me its best approximation of red.

Which red? There isn't a single, true "red". And different materials produce different reds (my work's Sony BVM-X300's reddest red is going to look way different than your monitor's red). Not all displays use only RGB color primaries, too. For example, at Dolby's office in San Francisco they have a projector in their theater that uses 5 (IIRC) color primaries, not 3. 6-primary projectors exist. And other non-RGB displays.

> When I say (255, 255, 255), I expect the display to show me something as close to white as possible

Which white? D50? D55? D60? D65? D67? Something else? And yes, these different white points (and many others) are actually used in practice.

> (and at the brightest possible setting).

100 nits looks way, way different than 4,000 nits. Some monitors can do 10,000 nits.

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

Which black? This might sound dumb, because we can agree that there is an objective "absolute black" (i.e. zero photons). But when an artist creates an image, the monitor they use has some version of black. If you don't account for that, the image may be distorted. Blacks can be crushed, for example.

An absolute color space exists. It's called XYZ. We could use it. Some image formats support it.

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

#179

Post by sltkr »

flohofwoe wrote: post #169
sltkr wrote: post #152

Earlier quoted context omitted.

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

> Any better than the two-file version: > #define LIB_KNOB 123 > #include "lib.c" See, now you have 3 files, the .h/.c file pair of the library, and your own implementation source file with the configuration which includes a .c file. How is this better than having two files? > Too vague. How is it better, concretely? I can only assume from that question that you haven't had the "pleasure" to work much with C/C++ buil…

> See, now you have 3 files, the .h/.c file pair of the library, and your own implementation source file with the configuration which includes a .c file.

The third source file is what the library authors suggested; I'd just create a seperate Makefile target for the implementation, which is then linked into the binary. (Yes, that's an extra target, but that costs very little and allows you to avoid unnecessary rebuilds.)

Why don't you give me a concrete counterexample where the single-header-setup makes things simpler? If it's so obviously beneficial it shouldn't be so hard to come up with a concrete example.

> #define IMPLEMENTATION > #include "base_library.h" > #include "extension_library.h"

Thanks for explaining, but that doesn't really motivate having a single file, since you could just as easily do:

  #include "base_library.c"
  #include "extension_library.c"
And you've saved a line (and removed the need for obscure preprocessor macros).

> ... without having to add a separate 'private but actually public API'.

Personally, I'd say this is exactly the right way to model this, but even if you disagree: it sounds like this simplifies things mainly for the library/extension authors, and not the library users, because if the extension author forward-declares the implementation details they depend on, there is no additional file to manage for the users either.

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

#180

Post by formerly_proven »

sam0x17 wrote: post #159
kaetemi wrote: post #153

Earlier quoted context omitted.

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, i…

You're assigning a color profile to the image in your model - the color profile of the display. Hence no color conversion needed, as source and target match.

What "red" and "green" are has changed quite dramatically with different display technologies. A display designed to meet Rec.2020 can show colors that other displays literally cannot produce and the deviation between the primaries is so big that everything looks like garbage if you don't do a color space conversion. Take some sRGB content and display it on a DCI P3 display. Looks like shit. Humans look like crabs.

> On monitors and displays, sure, those vary, but why allow people to specify a color profile on an image

The sole reason why we have device profiles defining device color spaces is so that we can convert from the image's color space to the device's color space. If images don't have a profile assigned to them, you don't need a device profile.

So you either have both image and device profile, or neither. Just one doesn't make sense.

Post reply on HN