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

161–170 of 303 posts

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

#161

Post by ball_of_lint »

sltkr wrote: post #53
j-pb wrote: post #6

> To keep things O(n) when encoding, there's only one lookup into this array. The lookup position is determined by a “hash” of the rgba value (really just r^g^b^a). Is a bit imprecise. The algorithm would still be O(n) even with a linear search through the "seen pixel array", as it is bounded by 64 length and therefore a constant factor that gets eaten by the Big-O notation. Because of this hash the algorythm seems t…

> Because of this hash the algorythm seems to do something else than first described though. Instead of "a running array of the 64 pixels it previously encountered", it's actually the previous 64 pixel _values_ previously encountered, which allows for much bigger jumpback. It's somewhere in between. Because these values are hashed into single slots, assuming that hash codes are random, the probability that a value is…

In an image with very limited colors you would have long runs of the same color and it would compress well from just the run-length encoding alone.

Also, it's non-obvious that older values will be less useful. Going through the pixels in order like this doesn't preserve locality well, so older values may actually be closer to a given pixel than more recent ones.

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

#162

Post by jameshart »

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.

Right - this thread of people asking for colorspaces, dpi data, arbitrary metadata collections… all are exhibiting precisely the ‘expert group’ committee mindset that this format is supposed to avoid.

If you want all that, there are formats galore that support it! The point is more: where are the formats for people who don’t need all that? Here is one. Please don’t try to ruin it.

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

#163

Post by kaetemi »

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…

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 your profiles are wrong, or your software is broken. Maybe it really is pink, and it just looks green for you, because you're ignoring color profiles.

But the fact is, most software is broken, and you should store images with the sRGB profile.

And also, you can actually calibrate consumer hardware, so that you can scan a photo, and reprint it. And the scan, display, and print will look exactly the same. (It's not the case by default, because consumer printers do what you do, stretch or fit the color space to the printer's. The Vivid and Natural profiles in the driver, respectively. This is a good default for documents, not for professional photography.)

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

#164

Post by zenogais »

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.

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

#165

Post by BlueTemplar »

giorgioz wrote: post #24

>I can almost picture the meeting of the Moving Picture Experts Group where some random suit demanded there to be a way to indicate a video stream is copyrighted. And thus, the copyright bit flag made its way into the standard and successfully STOPPED MOVIE PIRACY BEFORE IT EVEN BEGAN. This bit made me laugh out loud :D

Indeed, however remember the mandatory "What colour are your bits ?" :

https://ansuz.sooke.bc.ca/entry/23

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

#166

Post by kaetemi »

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…

The sRGB color #ffffff should never mean "the brightest white on this monitor", unless you're using an average CRT.

Just imagine you're using an HDR display, where the brightest white is as bright as the sun.

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

#167

Post by gfody »

haxiomic wrote: post #4

This is impressive, I was curious if it was just better on simpler images with many duplicate pixels but it's nice to see it working well with photography too e.g. https://phoboslab.org/files/qoibench/images/wallpaper/EwZDbL... decode ms encode ms decode mpps encode mpps size kb libpng: 148.4 3995.5 55.88 2.08 12223 stbi: 161.0 1858.3 51.50 4.46 19199 qoi: 60.8 95.6 136.49 86.78 12868 I'm interested if there's a stan…

  pngcrush -brute  10355kb
  cjxl -q 100 -e 9  8413kb

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

#168

Post by j-pb »

mzs wrote: post #123
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…

Do you have a link to discussions about QOI on twitter?

https://twitter.com/WAHa_06x36/status/1463456861978599426?s=...

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

#169

Post by flohofwoe »

sltkr wrote: post #152
flohofwoe wrote: post #87

Earlier quoted context omitted.

In general, STB-style headers simplify C/C++ build system shenanigans. E.g. one benefit is that you can configure the implementation via preprocessor defines without the defines leaking into the build system. Just add the config defines in front of the implementation include. It's also trivial to write "extension headers" which need to directly peek into the (otherwise private) implementation of the base library. Jus…

> In general, STB-style headers simplify C/C++ build system shenanigans. Too vague. How is it better, concretely? > E.g. one benefit is that you can configure the implementation via preprocessor defines without the defines leaking into the build system That's not a benefit. How is this: #define LIB_IMPLEMENTATION #define LIB_KNOB 123 #include "lib.h" Any better than the two-file version: #define LIB_KNOB 123 #include…

    > Any better than the two-file version:
    >    #define LIB_KNOB 123
    >    #include "lib.c"
See, now you have 3 files, the .h/.c file pair of the library, and your own implementation source file with the configuration which includes a .c file. How is this better than having two files?

> Too vague. How is it better, concretely?

I can only assume from that question that you haven't had the "pleasure" to work much with C/C++ build systems yet, at least when it comes to integrating 3rd party libraries.

Re. extension headers:

    #define IMPLEMENTATION
    #include "base_library.h"
    #include "extension_library.h"
Since the implementation of the base library is in the same compilation unit as the extension library, the extension library has direct access to the private implementation details of the base library without having to add a separate 'private but actually public API'.

> no clear distinction between declarations and definitions

STB-style libraries have this clear distinction, C++ style header-only libraries don't.

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

#170

Post by kasper93 »

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 bad, although your simple solution is well, simple :)

- I feel like the benchmark suite is lacking. For better overview you probably should include libpng results with max compression level and lowest compression level. Lossless modes of AVIF and WEBP would be nice. (also could throw similar project to yours like https://github.com/catid/Zpng) Not saying the benchmark is bad, but IMHO doesn't paint the full picture. From quick test I got significantly better compression on libpng, ofc in expense of time, but you didn't configure libpng for speed either. So we have some results, but they are not really representative imho.

- I understand it is pet project, but don't forget about importance of image metadata, like colorspace and so on.

- Also keep in mind that compression is easy at the beginning, but the tricky part is how to squeeze more.

EDIT: formatting...

Post reply on HN