Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

Here are two examples of lossless image compression.

Run-length encoding

RLE (run-length encoding) replaces a sequence of pixels of the same color with the number of pixels in that sequence. Therefore, the image Figure 1 needs 9 bytes to be stored without any compression. By reading the image column after column, the bytes are:

(000255255255255128128).\begin{pmatrix} 0 & 0 & 0 & 255 & 255 & 255 & 255 & 128 & 128 \end{pmatrix}.
A 3 × 3 image.

Figure 1:A 3 × 3 image.

We see 3 pixels with intensity 0, 4 pixels with intensity 255, and 2 pixels with intensity 128. Thus the image is encoded in RLE with only 6 bytes:

(3042552128).\begin{pmatrix} 3 & 0 & 4 & 255 & 2 & 128 \end{pmatrix}.

In this example, the compression rate is 6/9 = 2/3.

In computers, BMP format is based on RLE compression.

Lempel-Ziv-Welch Algorithm

The LZW algorithm (Lempel-Ziv-Welch, 1984) is an improvement of the LZ78 algorithm (1978). It is used in format such as GIF or TIFF. In short, the principle is to build a dictionary where the “words” are groups of pixels and to assign a code to each group. The dictionary is built during the compression stage and depends on the image.

Basics of Image Processing
Compression
Basics of Image Processing
Lossy compression