QOI: Lossless Image Compression in O(n) Time • Hacker News Board

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

#251

Post by gnramires » Thu, Nov 25, 2021, 1:32 AM UTC

h4kor wrote: post #74

ur-whale wrote: post #38

Earlier quoted context omitted.

> This bit made me laugh out loud :D Yeah, it's funny, until you actually go read the MPEG spec. documentation. Then any and all inklings of laughter will very quickly evaporate.

What does it say about these bits? I'm currently tinkering around with mp3s and wondered how many "useless" bits are in each frame. I wonder if they are ever used to trace distributors of pirated music, similar to yellow dots in printers.

He might be referring to the hundreds of pages (and very complicated implementations, usually of encoders) video formats have.

People think of technology as a straight line moving forward. But it's perhaps better to imagine like species in nature. It's just everything getting bigger. The smallest ant or bacteria evolves to better adapt to its niche, as the largest elephant or whale will develop adaptations (sometimes getting physically larger, depending on the environmental changes). The rule is that many scales have a role or niche. I think technology is similar.

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

#252

Post by [deleted] » Thu, Nov 25, 2021, 1:53 AM UTC

Const-me wrote: post #218

jiggawatts wrote: post #20

Earlier quoted context omitted.

I suspect SIMD would help with the encoding. The lookup table is small enough to fit into 8 AVX2 registers, so instead of hashing, you could use direct lookup, which would improve compression ratio further (a little bit).

> The lookup table is small enough to fit into 8 AVX2 registers Indeed. > so instead of hashing, you could use direct lookup However, I don’t think that part gonna work. See the code using that table: https://github.com/phoboslab/qoi/blob/master/qoi.h#L324-L328 SIMD registers aren’t indexable (at least not on AMD64), the register needs to be known to the compiler. Lanes within each register aren’t indexable either. T…

[deleted]

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

#253

Post by Dylan16807 » Thu, Nov 25, 2021, 2:10 AM UTC

BlueTemplar wrote: post #248

Dylan16807 wrote: post #241

Earlier quoted context omitted.

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…

> without using "bytes representing 105" (aka imaginary colors)

I think you misunderstood my point.

I'm saying it doesn't matter if certain byte sequences are invalid and don't correlate to real colors.

Imagine you're encoding two digit numbers into bytes. It's not bijective but that's fine, no correct two-digit math will give you an invalid byte.

Or imagine you're encoding numbers into bytes the way UTF-8 works. It's not bijective to all sequences of bytes but that's fine. No correct manipulation will give you a sequence that can't decode.

If you're trying to do incorrect math, you've already lost, and no color space will help. For example, overflowing your red channel in sRGB could turn your eggshell into a cyan.

> and trying to stay percepetually uniform

Where did that come from?

Zero encodings will be perceptually uniform, therefore being non-uniform isn't a disqualifier.

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

#254

Post by 10000truths » Thu, Nov 25, 2021, 2:18 AM UTC

hn_acc_2 wrote: post #223

phkahler wrote: post #95

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

The difference will be painfully clear once you try to walk a junior developer through installing and linking new files to a large project in Visual Studio, vs "copy this .h file here and include it". Whether or not a "good build system" should handle it, the fact that single-file libraries are much preferred these days should demonstrate most people don't have such a build system

So much of the C/C++ ecosystem revolves around knowing your build tools that, for most intents and purposes, it should honestly be considered an integral part of the languages. If I ever teach an introductory C/C++ course, I would dedicate at least 1/4 of my time to explaining:

* What a translation unit is, and how compiling a translation unit to an object file works

* What a linker is, and how the linker combines object files into a library/executable

* What make/autotools/cmake are, and how they work

* What FHS is, and how it standardizes the lib/bin/include paths that C/C++ build tools read from/install to

And so on. Any C/C++ course that goes beyond a “Hello world” program without explaining these concepts in detail does its students a disservice.

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

#255

Post by WoodenChair » Thu, Nov 25, 2021, 2:20 AM UTC

a_e_k wrote: post #224

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…

> But what shocks me is how did absolutely no-one apply such a naive RLE in the 30 years of internet image formats? Off the top of my head, both PCX [0] and TGA [1] use similarly naive RLE as their compression method. And while they also offer fancier compression methods, BMP [2], TIFF [3], and OpenEXR [4] all offer RLE modes as well. [0] https://en.wikipedia.org/wiki/PCX [1] https://en.wikipedia.org/wiki/Truevision_…

Just to add to this list, even MacPaint used RLE on a per-scan line basis. I recently wrote about decoding MacPaint files[0]. So, replying to the gp post, yes it is in a sense reinventing the wheel. But sometimes the wheel needs to get reinvented because you have a new vehicle that could use a different type. And I would say the original poster felt he needed part of the modern wheel without the tire, so he had to go back to earlier wheel designs in a modern context. Okay, I've stretched the analogy too far!

[0] http://www.observationalhazard.com/2021/09/building-retro-di...

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

#256

Post by Dylan16807 » Thu, Nov 25, 2021, 2:36 AM UTC

BlueTemplar wrote: post #245

Dylan16807 wrote: post #213

Earlier quoted context omitted.

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

What are you comparing it with?

If you compare Rec.2020 with 10 bits per channel and sRGB at 9.5 bits per channel, both of them using the same peak brightness, you should see similar amounts of banding on both.

Increasing the maximum brightness can require a lot of extra bits to keep things smooth, but that's a separate thing from which colors are possible.

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

#257

Post by littlestymaar » Thu, Nov 25, 2021, 2:43 AM UTC

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…

As you mention, our brain adapts pretty easily to varying lighting conditions in the real world, and that could also work on a screen[1], but the ambiant context is what matters: if you look at an image “A” in your said “undefined color space” after having spent quite some times looking at sRGB images for a while, then your image “A” would look absolutely horrible until your brain starts to adapt, like when you put sunglasses on or off for instance. The big difference being: with sunglasses, we have no choice but wait for our brain to adapt, but on a computer all the user would do is close the image.

[1]: even though for some reason I don't know, it works much less well: if you try and take pictures with the wrong white balance setting, the picture will look like shit no matter how long you look at it.

As a side note,

> [1]https://medium.com/swlh/magenta-the-color-that-doesnt-exist-...

This article is pretty terrible, as her author mixes everything up.

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

#258

Post by NL807 » Thu, Nov 25, 2021, 2:48 AM UTC

sam0x17 wrote: post #115

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…

I've never understood the need for color profiles on images themselves. On monitors and displays, sure, those vary, but why allow people to specify a color profile on an image, thus making images no longer a ground truth for pixel value? It seems like the main use case is dealing with images that already have color profiles. What is the point?

Simple question: what is the "ground truth"?

If you author an image on Display A and save its colours, then how does Display B know to render colours correctly that looks consistently with Display A?

You have two options:

1.) Tag Display A's colour space into the image, then convert colours to match Display B's colour space when rendering;

2.) Convert colour data from Display A colour space into a generic colour space (like sRGB, Display P3, ACEScg, etc) and embed that in to the image, then convert colours to match Display B's colour space when rendering.

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

#259

Post by phire » Thu, Nov 25, 2021, 3:44 AM UTC

zenogais wrote: post #164

st_goliath wrote: post #110

Out of curiosity, I modified the benchmark program to simply toss the pixel data into lz4/lz4hc for comparison (patch file: https://paste.debian.net/1220663/ ). I'm actually quite impressed how the resulting size is a little bit smaller than lz4hc (actually not even that far away from libpng), while the encoding speed is quite close to lz4, despite seemingly not having as many hacks and tweaks under the hood to get t…

Like the author said this is completely unoptimized. The natural next step in optimization might be to profile and then SIMD optimize the slow bits in compression and decompression. This would likely produce a significant speedup and may even bridge the gap with lz4.

The algorithm is extremely resistant to SIMD optimizations.

Every pixel uses a different encoding, 95% of the encodings rely on the value of the previous pixel, or the accumulated state of all previously processed pixels. The number of bytes per pixel and pixels per byte swing wildly.

SIMD optimization would basically require redesigning it from scratch.

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

#260

Post by phire » Thu, Nov 25, 2021, 5:51 AM UTC

HanClinto wrote: post #243

chrisdew wrote: post #43

Earlier quoted context omitted.

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.

Suggests the DIFF16 delta-color mode is responsible for quite a bit of the savings. Maybe it would be worth experimenting the exact encoding.

One idea would be to start a predicted color (calculate the delta of the previous two pixels, apply that, then specify a delta to that). Another would be to encode the delta in YUV or some other color space, and then experiment with the best balance of bits between those channels.

Perhaps it would be better to steal bits from RUN16 instead, I somewhat doubt it's usefulness.