RLE Image Compression

RLE Image Compression
RLE is a natural candidate for compressing graphical data. A digital image consists of small dots called pixels. Each pixel can be either one bit, indicating a black or a white dot, or several bits, indicating one of several colors or shades of gray. We assume that the pixels are stored in an array called a bitmap in memory, so the bitmap is the input stream for the image. Pixels are normally arranged in the bitmap in scan lines, so the
first bitmap pixel is the dot at the top left corner of the image, and the last pixel is the one at the bottom right corner.
Compressing an image using RLE is based on the observation that if we select a pixel in the image at random, there is a good chance that its neighbors will have the same color . The compressor thus scans the bitmap row by row, looking for runs of pixels of the same color. If the bitmap starts, e.g., with 17 white pixels, followed by 1 black one, followed by 55 white ones, etc., then only the numbers 17, 1, 55,. . . need be written on the output stream.
The compressor assumes that the bitmap starts with white pixels. If this is not true, then the bitmap starts with zero white pixels, and the output stream should start with 0. The resolution of the bitmap should also be saved at the start of the output stream.
The size of the compressed stream depends on the complexity of the image. The more detail, the worse the compression. However, Figure 1.4 shows how scan lines go through a uniform area. A line enters through one point on the perimeter of the area and exits through another point, and these two points are not “used” by any other scan lines. It is now clear that the number of scan lines traversing a uniform area is roughly