imagecompressionrun-length-encoding

Run-length compression on an RGB image

Suppose I have an RGB image with 3 bit color depth as displayed below. My uncompressed image size would therefore be width * height * color depth in my case 200 * 200 * 3 = 120000 bits.

What would be the image size if I use run-length compression? Let's suppose the length is stored using 1 byte.

Run-length example image

This is how I tried solving it, but I'm not sure if my solution is correct:

20 * (1 + 3) + 160 * (1 + 3 + 1 + 3 + 1 + 3) + 20 * (1 + 3) = 2080 bits.

Compression ratio would therefore be uncompressed / compressed = ratio in my case 120000 / 2080 = 57.69.

Solution

  • You are on the right track but although you have said your RLE counter will be one byte you have only allocated it one bit. s/1 +/8 +/ fixes that problem:

    "What would be the image size if I use run-length compression? Let's suppose the length is stored using 1 byte."

    20 * (8 + 3) + 160 * (8 + 3 + 8 + 3 + 8 + 3) + 20 * (8 + 3) = 5720 bits

    There is another minor glitch in that you also need to be able to recognize when the bitstream is a colour index and when it is a counter. There are two common ways to do this. The most obvious is to prefix colour indexes with a 0 bit so 0rgb and counters with a 1 bit 1bbbbbbbb which then gives

    20 * (9 + 4) + 160 * (9 + 4 + 9 + 4 + 9 + 4) + 20 * (9 + 4) = 6760 bits

    The other method which wins or breaks even for images with 4 or fewer colours is to use two copies of the colour index itself to escape in a counter. So for your test image and 8 colour palette that gives

    20* (8 + 6) + 160 * (8 + 6 + 8 + 6 + 8 + 6) + 20 * (8 + 6) = 7280 bits

    Assuming 24bit rgb palette colours to be stored you also need 24 bits for each distinct colour in the image and another 3 bits for a counter to say how many are used. Real image headers have a lot more info in them.

    Wikipedia has a nice article on RLE

    Compression ratios somewhere between 16.5 and 20 for your sample image.

    BTW your sample image only has two distinct colours used and so could be encoded 1 bit per pixel. (and then escaping in a counter by repeating a colour works rather well)