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

201–210 of 303 posts

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

#201

Post by dahart »

mmastrac wrote: post #171
dahart wrote: post #148

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…

Wouldn't it make sense to transcode to a GPU-specific lossless, compressed format for rendering?

Yes, totally. Depends on your use case, but there certainly could be good reasons to keep images in compressed form even GPU RAM. It’d be ideal if decode is both random-access and predictable amounts of work per pixel. This format checks the predictable work box, but would need a little design to make it random access.

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

#202

Post by jiggawatts »

junon wrote: post #149
jiggawatts wrote: post #20

Earlier quoted context omitted.

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.

There are some clever tricks that can be pulled with the latest instructions sets like AVX-512. The registers are huge and the instructions available are so varied that there are clever ways to use them in "off label" ways to implement lookup tables and bit-level parsers.

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

#203

Post by ErikCorry »

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…

I wonder how much worse the compression would be if you just had the last 64 colors, but didn't update when using the run length byte codes. Seems like it would be close to the same, and the decoder wouldn't need to hash the pixels.

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

#204

Post by em3rgent0rdr »

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…

That metadata could be stored in the filename to keep it out of the actual file.

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

#207

Post by makapuf »

kortex wrote: post #122
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?

No single color space is complete. Each has trade-offs. I would actually say that color profiles help get closer to ground truth, that is, rendering intent.

Using one given color profile is part of the trade-off.

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

#208

Post by bluedino »

rytill wrote: post #138
phkahler wrote: post #95

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

Why use two files instead of one?

What if you want to use the functions in other C files? What if you want to compile them all separately?

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

#209

Post by Trixter »

phoboslab wrote: post #16
Ono-Sendai wrote: post #13

Very cool. Typo: "I barely understand how Huffman Coding and DTC works" I guess you mean DCT? (discrete cosine transform) One other thought: To make it so that compression and decompression can be multithreaded, you might want to 'reset' the stream every N rows. (i.e. break any RLE runs, start from a colour literal). This would allow a bunch of threads to start at different places in the image, in parallel. There wou…

Thanks, fixed! I'll probably investigate "resetting" the stream to allow for multithreaded en-/decode when I try to roll this into a video codec.

Before you start rolling this into a video codec, please consult the sources of UT Codec, which has been state of the art in this space for many years. Or, at least, use UT Codec as a direct basis for comparison, to see if you are beating it in terms of compression/decompression speed.

Modern lossless video codecs don't care that much about saving space, since you're burning gigabytes per minute anyway; the key is that the compression and decompression are as transparent as possible, to reduce the bandwidth to/from the storage medium. A good lossless codec can be used to scrub through and edit on a video editor's timeline, so decomp performance is what's most important.

Also, any such lossless video codec is going to need more than 8 bits per component; most real-world footage coming off of phones and cameras is 10-bit Rec.2020. If it is too difficult to position QOI for real-world sources, you can certainly keep it 8-bit and market it as an animation codec or similar; just keep it in mind.

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

#210

Post by xiphias2 »

javajosh wrote: post #157

Very cool - I hope browsers support this soon! Funny meta comment: when I read " offering a 20x-50x speedup in compression and 3x-4x speedup in decompression " I caught myself reacting with disappointment to the "only" 3x-4x speed up. This is funny because 3x improvement is enormous; it's just small compared to 30x. There's a lesson somewhere in there about sharing stats together to achieve an emotional effect.

It's trivial to port this to JS / WebAssembly without losing speed (using bytearrays) ..it's a nice afternoon project actually
Post reply on HN