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

101–110 of 303 posts

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

#101

Post by gpvos »

wongarsu wrote: post #48

Is it just me, or is the compression algorithm not really less than the one in PNG? I will grant the author that if you don't need features like support for color spaces, different bit depths or interlacing you can skip the entire container format. But for reference this is the core part of png: For each scanline write one byte for the chosen filter method, then $width pixels. There are five filter types. In type 0,…

The 64-pixel lookback makes it a bit similar to LZ-style compression like Deflate, but the latter is not O(n) because it can recognize multi-pixel sequences. QOI is just a slightly beefed up run-length encoding.

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

#102

Post by WaitWaitWha »

I am going to be the fly in this ointment.

I appreciate the premise to develop this, and the science that comes with it.

I cannot tell if the author is writing in jest or serious when he is rude to the historical work that was done before him, yet relies on. It comes across as hubris with no floor to hold him up.

Today's genius is often questioned and found to be a fool of tomorrow, and a bit of grace goes a long way.

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

#103

Post by userbinator »

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…

I see it as a variant of LZ specialised to images, so its performance should not be too surprising. Running an uncompressed bitmap through a general-purpose compression algorithm tends to yield similar results to PNG.

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

#107

Post by mkl »

amelius wrote: post #73
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…

Yes, also store the DPI. In general, allow arbitrary key-value pairs to be stored.

> Yes, also store the DPI.

I don't think that's a good idea. Most images, like photos and screenshots, don't have physical dimensions. Some image tools like to put in bogus default DPI values that are guaranteed to be wrong, and it can be a bit of pain.

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

#108

Post by andrewla »

makapuf wrote: post #72

Would be interesting to try to use it as is but in a lossy way

Very much this -- it will unfortunately have a horizontal bias if done naively, but I've been exploring the space of doing lossy preprocessing to improve image compression, but the layered heuristics in png make this difficult. This format is simple enough that we have a number of approximation heuristics -- find the closest color in the last 64, use a smaller delta, or preserve one or two channel colors in the next pixel.

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

#109

Post by benlivengood »

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 patterns). I should probably implement the change and test it before posting...

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

#110

Post by st_goliath »

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 there. So the encoder is IMO doing amazingly well actually.

However, the decoding speed of liblz4 is off by roughly an order of magnitude. But again, liblz4 probably benefits from decades of tweaking & tuning to get there. It would be interesting how much performance could be gotten out of the qoi decoder.

Here are the totals I get for the "textures" benchmark samples:

          decode ms   encode ms   decode mpps   encode mpps   size kb
  libpng:       2.2        32.4         58.67          3.94       160
  stbi:         2.1        17.0         61.50          7.49       228
  qoi:          0.7         0.7        191.50        170.54       181
  lz4:          0.1         0.6       1226.06        206.40       258
  lz4hc:        0.1        70.9       1029.26          1.80       200
And for the "wallpaper" samples. The spreads seem to be a bit more in favor of qoi here:

          decode ms   encode ms   decode mpps   encode mpps   size kb
  libpng:     131.9      2287.1         66.63          3.84      8648
  stbi:       147.5      1177.1         59.55          7.46     12468
  qoi:         56.3        56.5        156.13        155.60      9981
  lz4:         14.3        53.1        614.53        165.50     18019
  lz4hc:       13.9      1901.7        630.94          4.62     12699
Post reply on HN