4 ms·

> 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

by j-pb 5y ago

> 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 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. By deterministically computing this array during execution it itself seems to act as a kind of compressed jumpback table, allowing for approximated arbitrary jumpback with just 6 bit. Quite impressive! Edit: I think there might be an interesting tweak that could increase the effectiveness of the hashing technique used. If one were to walk and store the pixels in a Z-Curve order, the runtime would stay the same but the locality of the color value pool, might be increased.

tda 5y ago
I was about to post the same idea about a locality preserving pixel order. I was thinking about hilbert curves, never heard of z-curves. Would be nice to see if/how that affects the compression ratios. How surprising that a few simple principles can give quite a good image format
- mkl 5y ago
  https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve Related to this method, it's sometimes used for texture mapping on GPUs.
- j-pb 5y ago
  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 coordinate is X_1,Y_1,X_2,Y_2... Which can be achieved with a bunch of bit shifts and masks, (or a bunch of wires if you happen to use it in an FPGA ^^')
  - formerly_proven 5y ago
    CPUs can do this quickly: __m128i src = _mm_set_epi32(0, 0, x, y); __m128i res = _mm_clmulepi64_si128(src, src, 0); uint64_t zeorder = _mm_extract_epi32(res, 0) | (_mm_extract_epi32(res, 2) << 1); Though a blocked iteration order should perform better due to better locality.
    - j-pb 5y ago
      Thanks for the pointer! If anybody else want to know how this works: https://stackoverflow.com/questions/30539347/2d-morton-code-encode-decode-64bits https://stackoverflow.com/questions/30539347/2d-morton-code-... https://en.wikipedia.org/wiki/Carry-less_product https://en.wikipedia.org/wiki/Carry-less_product
  - phkahler 5y ago
    I added Z-order curve to a ray tracer many years ago. Rather than using nested loops over X and Y pixel coordinates I used a single loop and de-interleaved the count to get X and Y. My thought was that this would increase the cache hit rate due to the locality of the pixels. It worked and the speedup was on the order of 10 percent. Because images are rarely power of 2 or even the same in both dimensions I opted to make a list of 32x32 blocks and rendered the blocks in Z-order as well as the pixels within (which still helped vs just tiling). Locality is a good thing to exploit.
  - user-the-name 5y ago
    Hilbert curves are not that much more complex. Maybe ten or so lines of code. Interleaving bits is already a pretty complicated operations if you don't have builtins for it.
    - a_e_k 5y ago
      I agree that de-interleaving is fairly complicated, but interleaving can be done fairly easily with a lookup from a table for each dimension and then combining them: xbits[x] | ybits[y] | channelbits[c]. The nice thing about this is that just by changing the tables, you can get things like z-curve, tiles, row-major, or column-major pixel orders (or even combinations), plus swizzled, interleaved, or planar layouts for the color channels.
- olaulaja 5y ago
  Based on some quick* testing using z-order instead of going row by row ends up taking 1-10% less space. Most images were on the lower end but I didn't run into any taking more space. * Swapping to z-order requires about 5 lines of changes if you ignore all the little edge cases like non power-of-two image sizes. Images used in testing may or may not be representative of anything.
sltkr 5y ago
> 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. Except black and white, these are unlikely to occur often in photographic images but could well occur in bitmaps with a handcrafted palette, or when the RGB values are converted from a system with a lower color space. For example, the 16 color CGA palette maps to just 3 different slots.
- j-pb 5y ago
  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].
- ball_of_lint 5y ago
  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.
  - MauranKilom 5y ago
    > 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. ...unless those images are dithered. Which may be a relatively common thing to do in small color spaces!
ErikCorry 5y ago
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.

by j-pb 5y ago

tda 5y ago

I was about to post the same idea about a locality preserving pixel order. I was thinking about hilbert curves, never heard of z-curves. Would be nice to see if/how that affects the compression ratios. How surprising that a few simple principles can give quite a good image format

mkl 5y ago
https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve Related to this method, it's sometimes used for texture mapping on GPUs.
j-pb 5y ago
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 coordinate is X_1,Y_1,X_2,Y_2... Which can be achieved with a bunch of bit shifts and masks, (or a bunch of wires if you happen to use it in an FPGA ^^')
- formerly_proven 5y ago
  CPUs can do this quickly: __m128i src = _mm_set_epi32(0, 0, x, y); __m128i res = _mm_clmulepi64_si128(src, src, 0); uint64_t zeorder = _mm_extract_epi32(res, 0) | (_mm_extract_epi32(res, 2) << 1); Though a blocked iteration order should perform better due to better locality.
  - j-pb 5y ago
    Thanks for the pointer! If anybody else want to know how this works: https://stackoverflow.com/questions/30539347/2d-morton-code-encode-decode-64bits https://stackoverflow.com/questions/30539347/2d-morton-code-... https://en.wikipedia.org/wiki/Carry-less_product https://en.wikipedia.org/wiki/Carry-less_product
- phkahler 5y ago
  I added Z-order curve to a ray tracer many years ago. Rather than using nested loops over X and Y pixel coordinates I used a single loop and de-interleaved the count to get X and Y. My thought was that this would increase the cache hit rate due to the locality of the pixels. It worked and the speedup was on the order of 10 percent. Because images are rarely power of 2 or even the same in both dimensions I opted to make a list of 32x32 blocks and rendered the blocks in Z-order as well as the pixels within (which still helped vs just tiling). Locality is a good thing to exploit.
- user-the-name 5y ago
  Hilbert curves are not that much more complex. Maybe ten or so lines of code. Interleaving bits is already a pretty complicated operations if you don't have builtins for it.
  - a_e_k 5y ago
    I agree that de-interleaving is fairly complicated, but interleaving can be done fairly easily with a lookup from a table for each dimension and then combining them: xbits[x] | ybits[y] | channelbits[c]. The nice thing about this is that just by changing the tables, you can get things like z-curve, tiles, row-major, or column-major pixel orders (or even combinations), plus swizzled, interleaved, or planar layouts for the color channels.
olaulaja 5y ago
Based on some quick* testing using z-order instead of going row by row ends up taking 1-10% less space. Most images were on the lower end but I didn't run into any taking more space. * Swapping to z-order requires about 5 lines of changes if you ignore all the little edge cases like non power-of-two image sizes. Images used in testing may or may not be representative of anything.

sltkr 5y ago

> 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. Except black and white, these are unlikely to occur often in photographic images but could well occur in bitmaps with a handcrafted palette, or when the RGB values are converted from a system with a lower color space. For example, the 16 color CGA palette maps to just 3 different slots.

j-pb 5y ago
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].
ball_of_lint 5y ago
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.
- MauranKilom 5y ago
  > 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. ...unless those images are dithered. Which may be a relatively common thing to do in small color spaces!

ErikCorry 5y ago

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.