What about encoding/decoding the image in two or more passes? Make a tiny dictionary of 8x8 or smaller blocks (all off, all on, dithered, etc) and what doesn't fit, RLE/LZW/etc the leftover blocks/pixels. As for the image you are using, I know that pure on/off pixels makes it harder to convert, but I'm not quite sure what it is supposed to be. I see the text and the map of the USA (I think) but otherwise there seems to be a lot of noise. Maybe cleaning it up a little would help with the image compression?

Since I assume the images intended will not be made strictly for the Dodo you could optimize a color dithering algorithm to output data easier to compress with any algoritm you choose (or vice versa), images designed specifically for the Dodo will be tougher but having an algorithm in mind when making the image can give savings too.

Good luck in your fight against entropy !

b&w pictures are some of the hardest to compress and #Recursive Range Reduction (3R) HW&SW CODEC is not adapted for this task. Look at the fax algorithms, I think they use arithmetic coding or range coding.

Thanks! I am well aware of bitonal image compression. At work I have implemented both CCITT and JBIG2 decoders. CCITT is the fax encoding, and it is basically Huffman with some additional tricks where it can take in the difference between the previous line of data. 

JBIG2 uses arithmetic encoding on top of some higher order constructs for glyphs and halftoning.  

The image I am trying to compress will be based on a threshold of foreground vs. background and should result in some pretty good runs of non changing data. That is how I generated the 1kb challenge image. I am not going to simply dither the image. A dithered image will suffer much worse compression.

I am going to try just a simple run length encoding first to see where I am at, but I think all I have room to code is at best some sort of simple huffman scheme. Hopefully I don't need to go down the route of arithmetic encoding, although I guess that would be impressive!

Thanks for the overview of your options :-)

i'd favor arith because it might give you a better result for a not-so-larger code...

Any chance of a modifier LZW (a bit like in GIF but with a different alphabet) ?

Oh and since there are only 2 tones, you just has to encode the run length (in huffman ?), am I right ?

Why can' t I reply to your last comment??

Anyway,

Actually, LZW is a great idea. I might actually try that first!

Yeah, 2 tones requires just the run length to be encoded.

you can't reply because HaD limit the depth of threads to 3, just reply to the parent post.

For the LZW, try using 2 contexts, one for white pixels and one for black ?

On second thought, it's probably not a good idea... But I tried to code a LZW once and whe I "got the trick", I understood why it was used so much. It's an easy algorithm once the data layout is figured out :-)

In your case, you can create an escape code for codes > 7 bits, saying "continue and don't change the length" for very long runs. This lets you code 128px-long runs and keep a symbol density that is close to the original pixel size...

For highly dithered pictures, I wonder about the performance of LZW, though. The original algo combines an existing sequence with a new symbol, but can't combine 2 existing sequences, making it quite under-efficient. This enhancement is not hard to do but will make a huge difference in your case.