Wondering how well this does on noisy / grainy images since it relies so much on pixel similarity.
All lossless compression algos do badly on noisy images
QOI: Lossless Image Compression in O(n) Time
51–60 of 303 posts
Re: QOI: Lossless Image Compression in O(n) Time
#52Waawh, one would think (certainly, I personally thought) that all the _simple_ compression algorithms would have been discovered and build by now...
Interesting I have the opposite view. From intuition I would think there is an unbounded set of simple compression algorithms. You can probably make much more effective simple compression algorithms by making basic assumptions about the type of image.
This is patently so. Taken to absurd proportions, you can compress a specific rendition of the Mona Lisa with just one bit. 1 means Mona, and 0 is undefined behaviour.
Re: QOI: Lossless Image Compression in O(n) Time
#53> 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 still in the table after k intervening values is pow(63/64, k).
That means the table is unlikely to contain all 64 values, but it will also retain some older values. Since older values are less likely to be useful in the future the encoding performance is likely somewhat worse than if the algorithm used strictly the last 64 distinct values.
This means that the algorithm is a bit sensitive to hash collisions, which seem particularly likely for primary colors (i.e. with each of the components at value 0 or 255):
- Slot 0: black, ALL SHADES OF magenta (x ^ 0 ^ x = 0), yellow (etc.) and cyan.
- Slot 15: white (255 ^ 255 ^ 255 = 255), red (255 ^ 0 ^ 0 = 255), green (etc.), blue.
Re: QOI: Lossless Image Compression in O(n) Time
#54Earlier quoted context omitted.
The nice thing is if M >= B^2 (i.e., total memory is large enough to fit a square region of the image, where each row/column of the square fits a full block/page of memory), you can transform from row/column order to Hilbert/Z-order without needing to do more I/Os. So you can't do such a conversion in a streaming fashion, but there is no need to load all data in memory either.
See also: Intel's guide to looping over smaller chunks of 2D arrays for better cache utilization: https://www.intel.com/content/www/us/en/developer/articles/t...
Yeah, those images explain it pretty well. There is one slight difference, though.
Because the Hilbert/Z-order curves are defined recursively, algorithms for converting between the curve and row/column order are "cache-oblivious", in that they don't need to take an explicit block size. You write it once, and it performs well on any system regardless the CPU cache size and/or page size.
Re: QOI: Lossless Image Compression in O(n) Time
#55Earlier quoted context omitted.
Interesting I have the opposite view. From intuition I would think there is an unbounded set of simple compression algorithms. You can probably make much more effective simple compression algorithms by making basic assumptions about the type of image.
This is patently so. Taken to absurd proportions, you can compress a specific rendition of the Mona Lisa with just one bit. 1 means Mona, and 0 is undefined behaviour.
Taking this a step further: 0 means that all subsequent bits contain an arbitrary PNG. Now your algorithm encodes any image, and still does Mona Lisa in one bit.
Re: QOI: Lossless Image Compression in O(n) Time
#56Wondering how well this does on noisy / grainy images since it relies so much on pixel similarity.
[deleted]
Re: QOI: Lossless Image Compression in O(n) Time
#57Wondering how well this does on noisy / grainy images since it relies so much on pixel similarity.
Notably, pixel similarity along a particular order. If I understood correctly something like a vertical rainbow would compress significantly different than the same picture rotated.
Re: QOI: Lossless Image Compression in O(n) Time
#58tl;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…
> 00xxxxxx - copy (x+1)-th last EXPLICITLY ENCODED pixel (i.e. ignoring repeats)-
Not exactly. It's "copy the last pixel color for which (r^g^b^a)&63 == x".
Re: QOI: Lossless Image Compression in O(n) Time
#59Could a hash collision make it inexact? so not guaranteed lossless?
Re: QOI: Lossless Image Compression in O(n) Time
#60> 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…
Yeah, one should probably add a randomisations step for each channel for good measure.
With random byte->byte lookup tables those costs should be hidden by the cache.
so hash = HR[r] ^ HG[g] ^ HB[b] ^ HA[a].