Character compression per image depth

An image is a two-dimensional array of colored pixels, in this case 200 rows pf 320 pixels (320x200), today typically a 2-dimensional pixel array. Color indexing is the concept of replacing the 24-bit pixels with an 8-bit pointer to a color palette, thus reducing the memory required to represent the image. Character compression is the concept of replacing the pixel matrix with a matrix of references to a palette of 8x8 cells. Fewer bits per pixel results in poorer quality, but higher probability of finding similar 8x8 cells, and therefore a smaller image. More bits per pixel results in higher quality, but less probability of finding similar 8x8 cells, and therefore a larger image. The technique does not work well on photographic images. I use these original images:

1-bit (2 colors)

2-bit (4 colors)

3-bit (8 colors)

4-bit (16 colors)

5-bit (32 colors)

8-bit (256 colors)

In total, a 320x200 (64000) pixels image (8000 bytes) consist of 40x25 (1000) characters. On a blank image, only one of them are unique and needs to be stored. If the image contains just one set pixel, then the image contains two unique characters. One blank and one containing the pixel. Using character compression, the one pixel image requires 2000 bytes for the character index (1000 entries of 2 bytes each), 8 bytes for the empty character and 8 bytes for the character with a pixel. 2016 bytes in total, instead of the 8000 bytes that is required to store a 1-bit 320x200 pixel image.

The first (1-bit) image in this example contains 716 of 1000 unique characters and the 2000-byte index, meaning that the compressed images requires 716x8 + 2000 bytes (7728 bytes). Here is one example of matchig characters:

And here are all the matches highlighted:

By reducing the size of the character, you increase the likelihood to find duplicated character, but you increase the size of the character registry.

The probability of finding duplicate characters decrease when more colors are added (the 8-bit version of the image does not contain any duplicated characters) so a strategy for achieving better compression would be to allow a certain degree of mismatch. If two characters are similar to a certain degree, they can be treated as same. If the threshold for treating two characters as similar is too high, no compression will be achieved. If the threshold is too low, the image will look a bit off.

Uncompressed, the 8-bit image consumes one byte per pixel (not counting the color table of 256 colors). The pixel data requires 64000 (320x200) bytes and the color table requires 768 (256x3) bytes. If we use character compression to reduce the number of unique 8x8 pixel cells from 1000 to 500, the table (1000 entries, 2000 bytes) and 500 unique characters (32000 bytes) and the color palette (768 bytes), we would have reduced the memory required from 64768 bytes to 34768 bytes. However, the uncompressed image might be slightly distorted.

If I only look at average color of the character, these 429 cells are similar enough to be interchanged with another character:

Here is the compressed version of the image. The original 8-bit image consists of a color palette (768 bytes) and a pixel array of 64000 bytes. The compressed version consists of the same color palette, a 2000 byte character index and 571 characters, each requiring 64 bytes (36544 bytes).

Of course, the compression level should be slightly lowered for a perfect result, but there are lots of other measures that can be taken. Similarity can be defined in a more sophisticated way than a close average brightness and hue. For photographic images: The threshold for equality could be higher when the detail level is high (in this case, in the center of the image) and lower when the detail level is low. But for pixeled images, top-down-left-right-scanning is good enough. As a conclusion, this is the same image with a slightly lower compression level, still with room for the previous mentioned possible improvements:

A slightly lower compression level increases the output quality significantly, but I am convinced that a more intelligent compression engine will do an even better job.