Compress black & white pixel data on an 8-bit microprocessor
https://stackoverflow.com/questions/7117903
-
01-01-2021 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
I need to compress the data of a 102x64 pixel black and white LCD screen using an 8-bit microprocessor. The data is coming in as a stream as shown below:
unsigned char data[8][102] =
{
{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x38, 0x28, 0xfe, 0x82, 0xba, 0xba, 0x82, 0xba, 0xba, 0x82, 0xba, 0xba, 0x82, 0xfe, 0x00,
0x00, 0x38, 0x44, 0x44, 0x38, 0x00, 0x40, 0x4c, 0x50, 0x60, 0x00, 0x28, 0x00, 0x40, 0x7c, 0x00,
0x4c, 0x54, 0x54, 0x24, 0x00, 0x00 },
{0x00, 0x20, 0x20, 0x20, 0x3f, 0x3f, 0x20, 0x20, 0x20, 0x00, 0x6f, 0x6f, 0x00, 0x0f, 0x0f, 0x08,
0x08, 0x0f, 0x0f, 0x08, 0x08, 0x0f, 0x07, 0x00, 0x07, 0x0f, 0x0a, 0x0a, 0x0e, 0x06, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
{0x00, 0x00, 0x00, 0x00, 0xc0, 0xcf, 0x0e, 0x0d, 0x0d, 0x0d, 0xce, 0xcf, 0x0d, 0xcd, 0xcd, 0x0d,
0x0c, 0xcf, 0xc0, 0x00, 0x00, 0xc0, 0xc2, 0x02, 0x83, 0xc0, 0x40, 0x40, 0x41, 0x42, 0x02, 0x02,
0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x03, 0x00, 0x00, 0x01, 0x02, 0x02,
0x02, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
{0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0x07, 0xfb, 0xfb, 0xfb, 0x07, 0xff, 0xff, 0xfb, 0xc7, 0x3f,
0xff, 0xff, 0x00, 0x84, 0x00, 0x00, 0x04, 0x04, 0xfc, 0x04, 0x04, 0x00, 0x04, 0x0c, 0x14, 0x24,
0xc4, 0x00, 0x00, 0x84, 0x00, 0x00, 0x30, 0x50, 0x90, 0x10, 0xfc, 0x10, 0x00, 0xf8, 0x04, 0x04,
0x04, 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
{0x00, 0x3f, 0x3f, 0x20, 0x20, 0x30, 0x1f, 0x0f, 0x00, 0x01, 0x0b, 0x0a, 0x0a, 0x0f, 0x07, 0x00,
0x08, 0x3f, 0x3f, 0x08, 0x08, 0x00, 0x07, 0x0f, 0x0a, 0x0a, 0x0e, 0x06, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
{0x00, 0xc0, 0xc0, 0x40, 0x40, 0xc0, 0x81, 0x02, 0x02, 0x82, 0xc1, 0x40, 0x42, 0xc2, 0xc3, 0x00,
0x00, 0xc0, 0xc0, 0x40, 0x40, 0x00, 0x81, 0xc2, 0x42, 0x42, 0x41, 0x40, 0x02, 0x02, 0x03, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x02, 0x02, 0x02, 0x01, 0x00, 0x01, 0x02, 0x02, 0x02,
0x01, 0x00, 0x01, 0x02, 0x02, 0x02, 0x01, 0x00, 0x01, 0x02, 0x02, 0x02, 0x01, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xf8, 0x04, 0x04, 0x04, 0xf8, 0x00, 0x04, 0x04, 0xfc, 0x04,
0x04, 0x00, 0x00, 0x04, 0x00, 0x00, 0xf8, 0x04, 0x04, 0x04, 0xf8, 0x00, 0x04, 0x04, 0xfc, 0x04,
0x04, 0x00, 0x00, 0x04, 0x00, 0x00, 0x04, 0x0c, 0x14, 0x24, 0xc4, 0x00, 0xf8, 0x04, 0x04, 0x04,
0xf8, 0x00, 0xf8, 0x04, 0x04, 0x04, 0xf8, 0x00, 0xf8, 0x04, 0x04, 0x04, 0xf8, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },
{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
0x00, 0x00, 0x00, 0x00, 0x00, 0x00 }
};
However I'm unable to fit it completely into the microprocessor's RAM. I can only access it in 51 or less byte chunks.
For those who are curious - the data will produce the following image:
I like to transfer the data using a slow serial interface. It takes way too much time to send the data as is. My goal is to double the speed by shrinking the data by a factor of 2. A normal zip compression will achieve factor 2.46 by compressing the 816 byte to 332 bytes.
My first idea was to shrink the data by grouping the byte that do have the same value in a sequence. For instance the data {0x20, 0x20, 0x20, 0x3f, 0x3f, 0x20, 0x20, 0x20} will be compressed from 8 byte to 6 byte into this {{0x20, 0x03}, {0x3f, 0x02}, {0x20, 0x03}}.
Is there a method that works better for black & white pixel data and the limited recourses that a 8-bit microprocessor provides?
Solution 3
I created a test using the RLE method (which was really easy to implement) and compressed a similar image from 816 to 446 byte (factor 1.82) - which is more than I expected from such a simple method.
OTHER TIPS
Fax machines use a combination of Huffman compression for lines, and then the following few lines only encode the differences from the last complete line.
It's the same principle as video compression: you compress one full frame, and then compress the differences for the next few frames (that's not 100% accurate, of course).
It should help the compression, but the code becomes a bit more complex.
I'd start with Huffman compression, as the image is definitely not random and should compress nicely. I don't think fax machines have a huge amount of memory so it might be possible to squeeze it in.
I don't know much about compression, but for something that's even more effective than RLE, specifically designed for a LCD, I'd perhaps consider something like this (inventing this algorithm as I write) :
{tag, x coord, y coord, data, data, data, ..., tag, x coord, ... and so on.
This is based on the idea that everything on the LCD is blank by default, and you just fill in the data. So it removes the need of storing a lot of 0x00. Instead, the value 0x00 can be used as a tag to describe where a new data segment begins and ends.
It would look like this:
uint8_t data[N] = {0x00, 0x05, 0x01, 0xFF, 0xFF, 0x00, 0x01, 0x02, 0xAA, 0xBB, 0xCC };
This will print the data FFFF at location (5,1) to (6,1) on the LCD, and then the data AABBCC at location (1,2) to (3,2). A wrap-around at end of line could easily be implemented. 0x00 may appear as one of the coordinates but never as data.
If you consider a huffman compression you can try a pre-processing like delta code or a move-to-the-front of the data. A delta code records the difference from the next byte and a mtf swaps the data using a dictionary. It can improve the compression rate of a statistial compressor. If a huffman is to expensive you may look into a golomb code. Mtf is used in bzip2 before a BWT transformation.
