next up previous
Next: Lossless Compression Algorithms (Pattern Up: Lossless Compression Algorithms (Repetitive Previous: Simple Repetition Suppresion

Run-length Encoding

This encoding method is frequently applied to images (or pixels in a scan line). It is a small compression component used in JPEG compression (Section 7.6).

In this instance, sequences of image elements $X_{1},X_{2},\ldots,X_{n}$ are mapped to pairs $(c_{1},l_{1}),(c_{2},l_{2}),\ldots,(c_{n},l_{n})$ where ci represent image intensity or colour and li the length of the ith run of pixels (Not dissimilar to zero length supression above).

For example:

Original Sequence:

111122233333311112222

can be encoded as:

(1,4),(2,3),(3,6),(1,4),(2,4)

The savings are dependent on the data. In the worst case (Random Noise) encoding is more heavy than original file: 2*integer rather 1* integer if data is represented as integers.



Dave Marshall
10/4/2001