3 ms·

Really cool encoding, it is a bit incredible that such simple rules can archive such good results. It is so interesting that if the image have few colors, meth

Really cool encoding, it is a bit incredible that such simple rules can archive such good results. It is so interesting that if the image have few colors, method #2 alone (An index into a previously seen pixel) encodes the whole image into an indexed colour space (with the hash table becoming the pallet). Ive seen already some comments recommending adding some vertical locality by tiling, Hilbert order, or Z order. I have yet another different vertical locality suggestion to try: While encoding/decoding keep a ring buffer the size of one full line of the image, storing each encoded/decoded bit there. Then add a variation of method #3 (The difference to the previous pixel) which instead encodes the difference to the pixel above the current (the last pixel from the ring buffer). Maybe, due to the limited "tag" space it would not be worth it to implement it for DIFF8, but only for DIFF16 (taking one bit from red to the additional tag bit) and DIFF24 (I'm not sure which bit I would steal there). Edit: Also, when thinking about video encoding in the future you may want to keep a ring buffer fitting the full last frame of video. And then temporal locality is probably even more important, so then you may want to change the tags to encode more commands relating to the pixel from the previous frame.

tda 5y ago
nice idea, I think it is somewhat more in line with the keep it simple option, as I e.g. have no idea what a hilbert curve for an arbitrary size rectangle looks like. And you still get compression for x and y directions (though no run length encoding the vertical, perhaps a further addition). I quite like this approach of defining a few compression methods, see which one works best, and apply that one. I used a similar strategy for time series compression where I would take a chunk of data, apply z few different compression algorithms on it (RLE, delta RLE, etc) and just keep which ever one was smallest. Of course here it is done on a per pixels basis, and I used arbitrary size chunks. The latter is trivial to parallelize. Same could be applied here though, split the image in half and compress both parts independently
gfody 5y ago
having done my own experiments with indexed pallets I suspect method #2 is responsible for most of the compression here. most photographs only have half a million distinct colors and it drops considerably as you focus in on an area. if you're willing to relax the single-pass requirement, partitioning the whole image by pallet similarly to how one encodes high-color images into multi-framed gifs can yield surprisingly good compression.

tda 5y ago

nice idea, I think it is somewhat more in line with the keep it simple option, as I e.g. have no idea what a hilbert curve for an arbitrary size rectangle looks like. And you still get compression for x and y directions (though no run length encoding the vertical, perhaps a further addition). I quite like this approach of defining a few compression methods, see which one works best, and apply that one. I used a similar strategy for time series compression where I would take a chunk of data, apply z few different compression algorithms on it (RLE, delta RLE, etc) and just keep which ever one was smallest. Of course here it is done on a per pixels basis, and I used arbitrary size chunks. The latter is trivial to parallelize. Same could be applied here though, split the image in half and compress both parts independently

gfody 5y ago

having done my own experiments with indexed pallets I suspect method #2 is responsible for most of the compression here. most photographs only have half a million distinct colors and it drops considerably as you focus in on an area. if you're willing to relax the single-pass requirement, partitioning the whole image by pallet similarly to how one encodes high-color images into multi-framed gifs can yield surprisingly good compression.