Previous Page: Simple Compression

Compression Using Run Length Encoding

1

Remember all the numbers it took to encode this image into numbers? If you remember your homework, you remember it was a whole lot of numbers. Your instructor certainly remembers how many numbers it was from grading your homework! There must be a way to reduce the amount of numbers it takes to describe this bitmap.

Lots of those pixels are the same color. Couldn’t we just write down that all the pixels from 1,1 to 1,10 are all 0,0,0 and 2,1 to 2,4 are 0,0,0 and 5,5 and 2,6 are 255,255,255, etc.? If we grouped regions of pixels like this, it should reduce the size of our encoded data significantly. If used to compress each of our sequence of images, it would reduce our overall movie size by the same factor.

What we’ve just described is a method of image compression called run-length encoding because we are encoding a run of pixels of a certain length. Run-length encoding (RLE) is a type of compression called lossless because when you decode the data you get the exact same image back and nothing has been lost in the compression process. RLE can be used will all sorts of data files, not just image files because in reality images and other data are encoded into binary numbers which only consist of strings of 1s and 0s. The likelihood of finding runs of the same character are very high.

2
3
A standard Targa image of our Space Invader which comes out to 75KB
A Targa with RLE compression applied and it’s only 47KB

Run-length encoding is a very common and very effective method of lossless compression.

Next Page: Other Still Image Compression Methods