Image Compression

with Run-Length Encoding Algorithm

6 min readJul 25, 2021

Image Compression

Data compression is very important part of our digital world where we have many files of huge size, as we have better and bigger quality of data, specially images. Now smartphones have better quality camera and the picture taken from those takes more storage “with more complex pixel combinations, more storage is taken”. There are different compression algorithms like JPEG and PNG but my task here is to explain about Lossless Compression using Run Length Encoding. The term lossless means there should not be any loss of data.

Now a question arises what is an Image ?

Image is a combination of pixels in the digital world. Just like 2-D plane, Image also have plane and it only have positive coordinates. Here i will be using Python to do image operations on a dummy image .

Run length encoding

It is a data compression algorithm that helps us encode large runs of repeating items by only sending one item from the run and a counter showing how many times this item is repeated. Unfortunately this technique is useless when trying to compress natural language texts, because they don’t have long runs of repeating elements. In the other hand RLE is useful when it comes to image compression, because images happen to have long runs pixels with identical colour.

we can compress consecutive pixels by only replacing each run with one pixel from it and a counter showing how many items it contains.

In this case we can save only counters for pixels that are repeated more than once. Such the input stream “aaaabbaba” will be compressed as “[4]a[2]baba”.

Lossy RLE is a very suitable algorithm when it comes to images, because in most of the cases large images do appear to have big spaces of identical pixel colours, i.e. when the half of the picture is the blue sky. By using lossy compression we can skip very short runs.

First we’ve to say how long will be the shortest run that we will keep in the compression. For instance if 3 is the shortest run, then runs of 2 consecutive elements will be skipped.

*From this pic we see that we can lose some information that is invisible to the eye.*

One of the most important thing is how to merge short runs. For instance the following three runs have to be blended into one colour run.

We can choose the middle colour (option #1) or not, but this will always depend on the picture and it will be effective in some cases and ineffective in other.

Implementation

Preliminary Tasks: Importing Dependencies & Defining a helper function.

I created a dummy image of shape 100 by 100

Here i have imported libraries as:

1 NumPy for array operations.

2 Matplotlib to view our image.

3 OpenCV, read and write image.

4 Sys for getting array size.

Some Experiments :

Now checking image which have more storage ,a blank or random

It shows that both of these files have same size. But if we see the file created on our folder, then the random image is taking 10.2KB while zero image is taking 214B. this is happening because OpenCV is using some compression algorithm to compress as much as possible and it becomes easier to compress an image which have least details or less complex, less varying pixel combination.

Let’s find size of our file from code

we get 214 and 10180 There is huge difference of the size taken by two same sized image. Let’s get into the RLE now.

RLE (Run length Encoding)

Let’s take an example, image [1 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0] have 16 pixels and it is binary. Now using RLE, we do something like below.
At the beginning, current pointer is first value i.e. 1. Now compressed image [11]. Which means that 1 has repeated 1 times consecutively.
Next, value is 0. Again it is repeated one times, hence compressed image is [11 01]. Which means, 1 is repeated one times then 0 is repeated one times.
Next, value is 1. Now 1 is repeated three times. Hence compressed image is [11 01 13].
Similarly, next compressed image is, [11 01 13 03].
Similarly, final is, [11 01 13 03 12 01 12 03]
Finally RLE([1 0 1 1 1 0 0 0 1 1 0 1 1 0 0 0])=>[11 01 13 03 12 01 12 03]

Our image had 16 values now it is compressed under only 8 values.

Now to decompress it,

Initial value is 11, which means 1 repeated one times. Image is [1].
Next value is 01. Similarly, image is [1 0].
Next value is 13. Similarly, image is [1 0 1 1 1].
And so on.

“Encoding function for this image“.

The function used for encoding can be described as:

1)Either convert image into Binary or use it as it is.

2)Then convert image into flat, i.e 1d vector & scan from left to right.

3)If previous value is same as current then count the run else append (value, run) on encoded. And also check the run length, i.e. if it becomes 2**bits - 1 then append it. If it exceeds that value, then our values will be rounded off to 8 bit range later.

Decode Function:

— →The decode function is simpler than encoding. Just perform repetition for values by run numbers and reshape it back.

→Now we save it as npz, npz.npy, tif and png format then find out which extension will compress most.

Let’s see how are encoded array looks like : show(earr)

From above example, it shows that when saving RLE as NumPy compressed, it will take 15128 and 14992but when saving the encoded array as png image, it takes 2088 Bytes. But using TIFF format, it takes 1532. And also the decoding can be done easily.

Now we will use “NON-BINARY FORMAT OF AN IMAGE “.