I'm looking for an efficent algorithm that can be controlled by a 8 bit micro. This alghorithm should be fast, with a high (if possible) compression and optimized for bi-level imges (that after the decompression should be displayed by an LCD). Any idea? Thanks
RLE. Or LZW if you can afford it.
bi-level means what ? If this is black and white, run length coding is one obvious candidate. Next step is a dictionary-table type compression.
-jg
You could use modified Huffman (MH) coding; as used by fax machines. For each scanline, perform run-length encoding (RLE) of black and white "runs" of pixels, followed by Huffman coding of the run lengths. The Huffman codes and corresponding white and black run lengths are given in RFC-0804:
This type of compression is used in some TIFF file.
T.4 and T.6 fax also support compression modes (MR and MMR) that look at more than one scanline of pixels, but this is more complex and takes more memory.
I thought LZW was out of patent now?
I suspect you're thinking of the wrong kind of "to be able to afford something". I guess Lewin was talking about technical affordability. LZW may be too CPU-heavy for the OP's (vaguely) specified micro.
Is LZW unpacking CPU-heavy? Guy is not going to pack on the MCU - just unpack. and this is just copying strings. It's even cheaper than any Hoffman - no need to work with variable size bitstrings.
C.
In a word, yes. Other LZs, and Huffman, are much easier to unpack.
-- Chuck F (cbfalconer at maineline dot net) Try the download section.
Yes, sorry - that's exactly what I meant.
I think, Run-length encoding (RLE) will be good for your requirement w.r.t image compression .
Karthik Balaguru
Yes. And a noticeable memory hog, too, compared to the address space of your typical 8-bitter.
The speed difference between a 16 MHz 286 and a 25-MHz 386 on LZW decompression (GIF images), way back when, was quite impressive. Doing that job on an 8-bitter feels painful just thinking about it.
I do seem to recall (though age has somewhat withered my memory) that the lookup table was large but all the strings were already in the decompressed data, if still held in memory. Tricky, certainly. I wonder if nibble compression would be better on an 8-bitter.
Those were the days.
Bill
LZW (or, what I know as LZW) uses a table of bounded size to store the symbols. Essentially, each entry is a symbol and a link pointer. What makes it tricky is that you need to read quantities which are not bytes. The 286 does not have instructions for that, but your controller may have them. The 386 may also benefit from its SHRD and BT instructions.
I would start with LZ77. LZ77 uncompression does not need *any* extra memory (except that which receives the output) and can be implemented as a screenful of assembler code on almost any piece of silicon.
Stefan
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.