3 ms·
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
by 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 agohttps://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 agoAfter 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 agoCPUs 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 agoThanks 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 agoI 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 agoHilbert 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 agoI 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.
- mzs 5y agoDo you have a link to discussions about QOI on twitter?
- j-pb 5y agohttps://twitter.com/WAHa_06x36/status/1463456861978599426?s=20 https://twitter.com/WAHa_06x36/status/1463456861978599426?s=...
- olaulaja 5y agoBased 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.