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

281–290 of 303 posts

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

#281

Post by dr_zoidberg »

kortex wrote: post #190
zcw100 wrote: post #144

Earlier quoted context omitted.

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"

I'm in the computer vision space and have looked into the effect of color spaces and encodings. People had basically exactly the epiphany you described. For example, there are several color models which try to be more lighting-invariant or (racially) color blind (this is a very similar problem, humans are all more or less "orange" hue-wise due to melanin's spectrum). TSL is one such space, there are others. https://e…

Quick question, from the context and how the wikipedia article was written I assumed TSL was fairly new, however looking at the dates of the published papers it all seems be late 90's early 2000's. Is this still in use somehow? I've never heard of it before, even though I've dabbled a bit in image processing from time to time in my line of work.

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

#282

Post by spider-mario »

sam0x17 wrote: post #159
kaetemi wrote: post #153

Earlier quoted context omitted.

For correct editing operations, and correct display. Sadly, it's not pedantry, it's reality. The 0.5 value is not half the brightness of 1.0 in sRGB. It merely means half the power output to your CRT. If you want correct editing operations, you need to work in linear RGB. It gets more fun. What is white? The color of your backlight? The color of white paper under your particular desk light? And what is black? Is it p…

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

> This is complicated enough, why do I need an image that will look good on only one kind of display and will have it's greens look pink on other displays.

That is precisely what attaching a profile to the image is supposed to avoid. It indicates what (255, 0, 0) in that image actually means. Then you convert that to the display profile to get the triplet that you must send to the display to actually get something that looks like it.

> Isn't having a color profile for the display enough?

What would you do with just one profile?

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

#283

Post by sitkack »

phire wrote: post #259
zenogais wrote: post #164

Earlier quoted context omitted.

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.

SIMD only gets you up to the width that your hardware platform supports and every SIMD program has to be rewritten for the new width.

Two other immediate avenues are multithreading, which think could be quite effective for this algorithm or GLSL, of that I have no opinion.

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

#285

Post by Animats »

account42 wrote: post #276
Animats wrote: post #217

Lossless avoids all those issues around human perception. Also, if you're storing game assets, some of what you're storing as images is not really imagery. It may be normals or height fields, which lossy image compression messes up. The code is interesting, in that it iterates over the output array, not the input. This helps prevent write buffer overflows. It has read buffer overflows, though. You can craft a compres…

Where do you see a read buffer overflow?

That would be telling.

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

#286

Post by em3rgent0rdr »

dylan604 wrote: post #237
em3rgent0rdr wrote: post #232

Earlier quoted context omitted.

well nobody can control what will happen to a file's content either if you want to be pedantic. If are worried about dumb users renaming it...I think most users know to not change things after a '.', so could just put the colorspace code there. And then could put another '.QOI' to end the filename. If want to keep cruft out of the file itself, then putting it in the filename works.

you're talking apples and kumquats. changing the name of the file (metadata in and of itself) does not affect the file at all. changing the contents of the file will have affects on the file. some changes might not negatively affect the file (like adding metadata when none was present) if the format allows for it. you can know the file will no longer be the same by running a hash on it. name changes will not affect t…

the color scheme is not "crucial information". It is just meta-data. It could be contained in the file, or in the filename, or outside the file in a separate metadata file.

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

#287

Post by Rounin »

By the way, this image format can match PNG in terms of size if combined with another form of lossless compression, so if we allow for that extra complexity, something like QOI + Zstandard could possibly compete with PNG in terms of both size and speed.

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

#288

Post by t0rakka »

kasper93 wrote: post #170

Neat work. Though I wouldn't be myself if I didn't have few nitpicks ;) - You are mixing lossy and lossless compression in your rant. And you are mixing containers with formats. Thing about lossy compression is that it is by design stupidly slow and complex to produce smallest possible results which has best perceived quality. Compress once and trade time for both image and compression quality. Lossless is not that b…

I wrote a small test bench for my own uses as wanted to compare with different codecs and see how "raw compression" would work, how would QOI+ZSTD combination work and so on.

Here's example output..

  image: 1502 x 1800 ( 10560 KB )
  ----------------------------------------------
           encode(ms)  decode(ms)   size(KB)    
  ----------------------------------------------
  qoi:          31.2        21.6       2452  
  qoi+zstd:     46.7        19.3       1832  
  zstd:         47.4         8.7       2742  
  lz4:          14.1         3.0       4108  
  png:          92.4        18.0       2795  
  zpng:         24.1        13.3       1394  
  jpg:           2.7         1.8        517

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

#289

Post by williamaadams »

hackerfactor1 wrote: post #240

There are a lot of better-than-JPEG and better-than-PNG solutions out there. Speed: If the benchmarks are correct, then this is exceptional, especially considering that the file size is only slightly larger than PNG. I can think of a couple of ways they could reduce the file size by probably around 10%-20% without sacrificing speed, but this is good enough to get attention. The biggest speed loss for PNG comes from z…

I came all the back from my Thanksgiving slumber just to say; really?

I love this library, and have made a C++ friendly version of the same.

What you get for a few hundred lines of code far outweighs any of the shortcomings it might have. It's a great starting point. If someone wants to make a full on format, they'll probably be better off just using the new JPEG XL, rather than trying to shape this thing.

It's a good exploration of what can be done with run-length encoding.

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

#290

Post by sitkack »

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…

Any possibility you could repost the patch? Was it pulled because of a bug?
Post reply on HN