Hi Nuke. Sorry for the necro, but the thread sounds really interesting. I'm working on a similar problem here, because of bandwith problems (stream R8G8B8 image data to an Arduino via serial/bluetooth and display it on a LED matrix with >500 LEDs and >20fps). I need to use simple algorithms, because I'm currently using an ATMega 328P (8bit, 16MHz), but might switch to the much more powerful Arduino Due if needed. So far I tried lossless (I don't really want to go lossy) compression using static huffman, but obviously the compression ratio for images is not stellar... My next approach is splitting the image into RGB color planes an doing a delta compression of color values using a variable number of bits. Atm I'm also able to hold the complete frame buffer in RAM, so I'll also try a simple delta-frame encoding of the RGB planes (only current vs. last frame), then do the color value delta encoding. About your probem: Have you considered doing an extra entropy encoding step (adaptive/static huffman, LZO or LZSS with heatshrink) after your image encoding? That might improve your compression ratio a bit. Why not check which block encoding would generate the smallerst error when being decoded?
