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

241–250 of 303 posts

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

#241

Post by Dylan16807 »

kortex wrote: post #228
Dylan16807 wrote: post #214

Earlier quoted context omitted.

Why does it matter if it's bijective?

So GP's question was basically "why do we need color profile?" and the short answer is "to know what images should look like". In order to know what an image should look like, a "perfect" or "complete" representation, at minimum the real colors must be injective to the color space (every value has at most 1 color). You could argue that the color space needn't be injective (values that have no color), which is probabl…

Yes, it has to be injective from the real world to the file format. It doesn't have to be bijective.

> As soon as you manipulate values of your image in your color space, you run the risk of falling outside the color domain.

If your manipulation could go outside the domain, then your manipulation is incorrect. Like, if I have a number from 0 to 99 that I store in a byte, it's fine that a byte is not bijective to those numbers, and if I end up with a byte representing 105, then I did something wrong that corrupted my byte.

If I'm doing incorrect math, a bijective color space doesn't fix the problem, it just guarantees that I get an incorrect color out the other end instead of possibly getting an incorrect color or possibly getting an error value.

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

#242

Post by kaetemi »

romwell wrote: post #219
kaetemi wrote: post #163

Earlier quoted context omitted.

I get what you mean, but... the color profile of the image is the profile of the display where the image can be displayed without adjustment. Think of it as the display profile of the guy that sent you the image. The magic math transforms the image to your display profile. That means it will look exactly the same on both displays. If they both have a correct display profile. If your green is going pink, then either y…

>That means it will look exactly the same on both displays. If they both have a correct display profile We can continue believing that Santa exists, or we can accept that effectively nobody has correct color profiles, and doesn't care either. It's nice metadata you have there, would be a shame if I applied night mode to it at 6PM. > also, you can actually calibrate consumer hardware ...with professional hardware that…

You can get pretty close without expensive calibration gear, using consumer gear that has a reasonable factory sRGB calibration.

https://blog.kaetemi.be/2021/02/01/calibrating-an-inkjet-pri...

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

#243

Post by HanClinto »

chrisdew wrote: post #43
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…

The current encoding is complete, so no future extensions are possible. A fix would be to change: 110rrrrr ggggbbbb - copy the last pixel and adjust RGB by (r-15, g-7, b-7) to: 1100rrrr ggggbbbb - copy the last pixel and adjust RGB by (r-7, g-7, b-7) This leaves: 1101???? ... available for future extensions.

So I implemented this change and tested it out. Turns out, in my simple test suite, this actually changes the size of images. Not drastically. Often just a 5-10 kb difference (on a 500-600kb file), but that's still more than I expected for changing r-15 to r-7.

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

#244

Post by BlueTemplar »

kaetemi wrote: post #166
sam0x17 wrote: post #159

Earlier quoted context omitted.

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

The sRGB color #ffffff should never mean "the brightest white on this monitor", unless you're using an average CRT. Just imagine you're using an HDR display, where the brightest white is as bright as the sun.

Thankfully, "as bright as the sun" is waaaaaaay outside of what a monitor is capable of : SDR is (supposed to) top out at 10^2 cd/m^2, HDR10 at 10^3, Dolby Vision maxes out at 10^4 cd/m^2, but the midday sun is... ~10^9 !

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

#245

Post by BlueTemplar »

Dylan16807 wrote: post #213
lstamour wrote: post #139

Earlier quoted context omitted.

Isn’t that kind of like saying Real numbers are complete? Yes, it’s true, but we don’t have an infinite level of precision for each colour. So we have to, practically speaking, limit how many colours can be specified to some reasonable (and arbitrary) number, e.g. 10 million or 1 billion or more (in terms of number of colours in a colour space) and representation in digital bits. Also, since I conflated the two a bit…

> Isn’t that kind of like saying Real numbers are complete? It's more like saying the range from 0..2 is complete so don't use an encoding that caps out at 0.8 or 1.1 The difference between all visible colors and a more constrained color space is only a factor of two or three. Less than half a bit per channel.

How do you explain then that even 10 bits aren't enough for a colour space like Rec.2020, which doesn't even feature all colours ?

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

#246

Post by michael-ax »

phkahler wrote: post #95
CornCobs wrote: post #36

Earlier quoted context omitted.

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

its not 'significantly better'.

but also ask "why are the tables of content prefixing the contents of all my books?"

its taken ages, but with this model, c lib authoring has finally taken something that was a core strength of pascal: single-file modularity.

though in theory there's no difference between theory and practice, in practice, there is. and this kind of packaging makes a lot of sense for a lib like this.

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

#248

Post by BlueTemplar »

Dylan16807 wrote: post #241
kortex wrote: post #228

Earlier quoted context omitted.

So GP's question was basically "why do we need color profile?" and the short answer is "to know what images should look like". In order to know what an image should look like, a "perfect" or "complete" representation, at minimum the real colors must be injective to the color space (every value has at most 1 color). You could argue that the color space needn't be injective (values that have no color), which is probabl…

Yes, it has to be injective from the real world to the file format. It doesn't have to be bijective. > As soon as you manipulate values of your image in your color space, you run the risk of falling outside the color domain. If your manipulation could go outside the domain, then your manipulation is incorrect. Like, if I have a number from 0 to 99 that I store in a byte, it's fine that a byte is not bijective to thos…

The point is that the average human ""real" color space" has a very weird shape :

https://upload.wikimedia.org/wikipedia/commons/a/a9/Visible_...

Good luck representing that with only 3 channels, without using "bytes representing 105" (aka imaginary colors), and trying to stay percepetually uniform !

It gets even worse : the real color space is non-Euclidean : it stretches out, parallel lines drift further apart, etc.

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

#249

Post by michael-ax »

Trixter wrote: post #200
SavantIdiot wrote: post #177

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

RLE on runs of deltas is in very many compression schemes; it's a common technique (probably so common that many authors don't deem it worth mentioning). Lossless video codecs in particular (huffyuv, lagarith, utcodec, etc.) have had this going back 20 years at least.

definitely ubiquitous.

we applied rle encoding for time-series and triac control systems 43 years ago after getting some guidance from a mainframe guy - but since RLE is practical so that we even use it to give direction to people on the street, its probably so old that its even found its way into the way our genes are encoded. :D

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

#250

Post by [deleted] »

xiphias2 wrote: post #210
javajosh wrote: post #157

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.

It's trivial to port this to JS / WebAssembly without losing speed (using bytearrays) ..it's a nice afternoon project actually

[deleted]
Post reply on HN