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

221–230 of 303 posts

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

#221

Post by a_e_k »

user-the-name wrote: post #99
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…

Hilbert curves are not that much more complex. Maybe ten or so lines of code. Interleaving bits is already a pretty complicated operations if you don't have builtins for it.

I agree that de-interleaving is fairly complicated, but interleaving can be done fairly easily with a lookup from a table for each dimension and then combining them: xbits[x] | ybits[y] | channelbits[c].

The nice thing about this is that just by changing the tables, you can get things like z-curve, tiles, row-major, or column-major pixel orders (or even combinations), plus swizzled, interleaved, or planar layouts for the color channels.

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

#222

Post by romwell »

mlhales wrote: post #117
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?

A color space and color profile are not the same. The point is knowing what a byte represents in a byte array. Is it red, hu, saturation, alpha, brightness etc?

The format in question specifies this though.

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

#223

Post by hn_acc_2 »

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…

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

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

#224

Post by a_e_k »

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_TGA

[2] https://en.wikipedia.org/wiki/BMP_file_format

[3] https://en.wikipedia.org/wiki/TIFF

[4] https://en.wikipedia.org/wiki/OpenEXR

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

#225

Post by a_e_k » 

    QOI_DIFF16 {
        u8 tag  :  3;   // b110
        u8 dr   :  5;   // 5-bit   red channel difference: -15..16
        u8 dg   :  4;   // 4-bit green channel difference:  -7.. 8
        u8 db   :  4;   // 4-bit  blue channel difference:  -7.. 8
    }
I'd think that the extra bit ought to be given to green, since that tracks most closely with luminance. That would make this somewhat analogous to the RGB565 layout for 16-bit pixels (https://en.wikipedia.org/wiki/High_color#16-bit_high_color).

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

#226

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.

I really like this.

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

#227

Post by barrkel »

akx wrote: post #89
barrkel wrote: post #66

Earlier quoted context omitted.

I rather wonder if things like this are used to encode a proof of intent. If something is marked as copyrighted, it may be trivial to remove the mark, but at least you had to remove the mark, and that's evidence of intent rather than ignorance.

Or a piece of software in your toolchain has been unaware of the bit and inadvertently stripped it. Is that evidence of intent still?

I'm not arguing in favour of it, I'm hypothesizing why it might be added.

Your toolchain should set the bit last thing before distribution, I'd expect.

If you're talking about a toolchain on the consumption side after distribution, well, consumers shouldn't be modifying content, is what I'd expect the position to be. No derivative works and all that.

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

#228

Post by kortex »

Dylan16807 wrote: post #214
kortex wrote: post #184

Earlier quoted context omitted.

CIE XYZ has imaginary colors, though. I guess when I said "no color space is complete" I meant "no color space is faithfully bijective to nominative human visual sensory response." Because such a thing is basically impossible (or insanely nonlinear and unwieldy). Also these color systems all or almost all assume a "norminal" (to steal a word from Everyday Astronaut, normal+nominal) average human vision system. If you…

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 probably fine if your image is static and you never manipulate it. As soon as you manipulate values of your image in your color space, you run the risk of falling outside the color domain.

But really to unpack this whole thread, my essential point is that color spaces are about engineering tradeoffs. sRGB can't reproduce many colors. CIE 1931 represents all color but has imaginary colors.

Ergo, I contend there is no "complete" color space.

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

#229

Post by Const-me »

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.

Videogames don't need color spaces, but they have different compression formats on GPUs, like S3TC, BC7, or ASTC. These things save not just storage, also VRAM bandwidth.

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

#230

Post by injinj »

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…

I believe libpng default zlib compression level is 6. libpng may use CRC (or adler) checksums, which account for around 30% of the decode time. In my experience with zlib, the higher compression levels have faster decode times. My reasoning at the time was (early '00s) that higher compression tends to code longer runs of copying of the dictionary. More time in the copy loop rather than the input and decode loop.
Post reply on HN