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

141–150 of 303 posts

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

#141

Post by sam0x17 »

kaetemi wrote: post #121
sam0x17 wrote: post #115

Earlier quoted context omitted.

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?

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.

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

#142

Post by Sharlin »

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.

What does "255" mean? If you just take it to mean "max saturation that your display can output" then it's going to be perceived as a different color depending on the viewer's display. That is undesirable. And due to historical reasons (the capabilities of CRT monitors) the meaning of "max saturation" was de facto standardized to what we now call sRGB. If you want to encode a greater range of colors than sRGB then you need to be able to say that hey, this "255" is more saturated than what sRGB considers "255" and should not be displayed on sRGB without conversion.

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

#143

Post by dahart »

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?

The point is to use bits effectively and not waste them, by accounting for what usually happens on most displays and in our eyes & brains. If we don’t account for it, then (for example) a 1-bit difference between two bright colors means something very different from a 1-bit difference between two dark colors.

So what is “ground truth” exactly? We need to know what units we’re talking about; is it lumens, or “tristimulus” values (what we want our eyes to see), or LCD monitor voltages, or something else? First we have to agree on what ground truth means.

A big reason for common formats like PNG and JPEG to need color profiles is because 8 bits per channel is not enough color resolution unless you store the colors non-linearly. 8 bits is barely enough (or some would say almost enough) to represent low-dynamic-range images on TVs and monitors even when you have the colors gamma encoded or use a perceptual color space.

The problem with storing “ground truth” values for pixels in 8-bits-per-channel formats is that many experts would probably say this implies a linear color space. And a linear color space encoded in 8 bits leaves noticeable gaps between colors, such that you can see color banding if you try to render a smooth gradient. You lose up to 2 bits of color precision in some regions, notably the dark colors.

So, in order to not have color banding, we correct the colors before storing them by trying to make the colors have even steps between any 1-bit change in the spectrum. The color profile is just a record of what was done to correct the colors, so someone else can un-correct them as needed.

You might think we could do away with color profiles for high-dynamic-range images, but the non-linearity of our vision and our displays means that linear encodings are still inefficient with their bits even if you have 32 bits per channel.

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

#144

Post by zcw100 »

cyber_kinetist wrote: post #47
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 think the author's intending to use this only as a data packing format (ex. for app/game development) and not a general-purpose exchange format. If all you want to do is pack image/texture data for your game then I totally get why they assume RGBA8 storage and leave out metadata such as color space information.

I wonder if color profiles will be important to images used for AI. Right now, as far as I can tell, people generally ignore details like that but I wonder if someday people are going to say, "oh wait, we've been completely ignoring color profiles. We could have been using that" or "we didn't realize how ignoring that messed things up"

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

#145

Post by AlotOfReading »

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.

Because display technology can't reproduce the full set of colors we see and and moreover, we have a finite number of bits to encode the value of any pixel. A color space/profile is both a target for display manufacturers to produce and a way of standardizing the trade off between bit depth and quantization error.

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

#146

Post by adgjlsfhk1 »

lstamour wrote: post #139
demute wrote: post #131

Earlier quoted context omitted.

CIE XYZ is complete.

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…

8 bit just objectively isn't enough for hdr. 8 bits is few enough that you can pretty easily see banding on a simple color gradient in sdr. Dithering helps a lot, but once you get to HDR 10 bits is pretty much the minimum.

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

#147

Post by adgjlsfhk1 »

benlivengood wrote: post #109

I wonder if the author tried making pixel diffs capable of using lookback. They'd be one byte longer but would possibly happen a lot more often than full pixel values. It's also reminiscent of the delta blocks from MPEG. If anything I would trade the 5-bit run for delta-from-lookup on a whim (the cases where the ratio between short runs vs. exact lookback is extreme seems like it might only happen for pinstripe patte…

The hard part here is figuring out which pixel to diff to. You would almost certainly have to look at all 64 pixels which would be a lot slower. That said, you can probably get noticably better compression from it.

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

#148

Post by dahart »

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 is to make some unit of the image (pixels, scanlines, blocks, etc) independently addressable (readable). The current format is complicated due to pixels of different sizes; there’s no way to know where data for pixel 1000 starts without reading all preceding 999 pixels. You could build a prefix-sum array of pixel indices, but that will fully undermine your compression.

One question might be how well does QOI work on independent scan lines or blocks? Is the compression still pretty good if the look-back window is limited in size and restarts every once in a while?

To make a GPU capable format, the very first thing you would probably need to do is separate the tag bits from all the other data, so a thread could identify the pixel type by direct lookup into the tag buffer. It then needs to know where to go to find the remaining data, so you’d probably need at least one byte of data that could be used to reliably locate the rest of the data. I don’t see an easy way to make this happen for separate pixels, but it might not be bad if the image is encoded in blocks or scanlines.

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

#149

Post by junon »

jiggawatts wrote: post #20
junon wrote: post #3

To answer the author's question: No, SIMD would not help with this. This is neat. I wonder if the author would be willing to write a Kaitai Struct definition for it. Something else interesting: QOI is 1,2,2 letters off from PNG. I'm quite certain this is an accident but it's interesting nonetheless.

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

Yes encoding might benefit of course, I was more considering decoding speed I suppose.

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

#150

Post by gfody »

SkeuomorphicBee wrote: post #63

Really cool encoding, it is a bit incredible that such simple rules can archive such good results. It is so interesting that if the image have few colors, method #2 alone (An index into a previously seen pixel) encodes the whole image into an indexed colour space (with the hash table becoming the pallet). Ive seen already some comments recommending adding some vertical locality by tiling, Hilbert order, or Z order. I…

having done my own experiments with indexed pallets I suspect method #2 is responsible for most of the compression here. most photographs only have half a million distinct colors and it drops considerably as you focus in on an area. if you're willing to relax the single-pass requirement, partitioning the whole image by pallet similarly to how one encodes high-color images into multi-framed gifs can yield surprisingly good compression.
Post reply on HN