Related pages on www.mikekohn.net: SSE Image Processing, GIF, TIFF, BMP/RLE, JPEG, AVI, kunzip, gif2avi, Ringtone Tools, yuv2rgb

BMP RLE (Run Length Encoding) Compression

RLE compression is probably one of the simplest compressions. This would be a great place for a beginner to start :). RLE4 and RLE8 are used in Microsoft's BMP format. If you've read enough of my webpages, you'll probably realize I'm not a very big fan of Microsoft, but I must admit the BMP format (unlike most Microsoft file formats) is actually not bad. The only real problems I have with BMP is it stores its images upside down (unless the height is negative) and things have to be aligned on 4 byte boundaries. Gross. But anyway, the way RLE encoding works is if you have an image that repeats a color multiple times, you can save disk space by storing repeated color information in the following way:

Let's say you had a 5x5 pixel image that looks like this (where R=red pixel, B=blue pixel, Y=yellow pixel):

RRRRR
BBBBB
BRYBR
RBRBR
YYYYY


In an uncomperessed BMP, you would store each color 1 byte at a time in a file. You'd store the BMP Header Information, a color palette, and then R,R,R,R,R, B,B,B,B,B, B,R,Y,B,R, R,B,R,B,R, Y,Y,Y,Y,Y.

This means the raw image data would take up 25 bytes. Note: I'm doing this right side up and not taking into account that data in BMP must be aligned. Also, note that storing a 3 color image in 8 bit is not ideal. Anyway, in RLE8 compression, the image data could be written as: 5,R, 5,B, 0,5,B,R,Y,B,R, 0,5,R,B,R,B,R, 5,Y.

Storing the data like this means: repeat R 5 times, repeat B 5 times, 0,5 means the next section is uncompressed for 5 bytes B,R,Y,B,R, 0,5 again means 5 bytes of uncompressed R,B,R,B,R, and then repeat Y 5 times. This brings the picture data section down to 20 bytes.

For an example of decompressing RLE8 and RLE4, take a look at the parse_bmp.c file of Ringtone Tools and for an example of compression (I forgot if I used RLE4 or RLE8 here) take a look at gif2avi from MandelServer.