Common Image Compression Methods

1. Run-Length Encoding (RLE) Compression

The principle is to replace consecutive pixels with the same color value in a scan line with a count value and the color value of those pixels. For example: aaabccccccddeee can be replaced with 3a1b6c2d3e. RLE is highly effective for images with large areas of uniform color. Many specific run-length compression methods are derived from the RLE principle:

1.1 PCX Run-Length Compression

This algorithm essentially converts a bitmap format to a compressed format. For a byte Ch that appears once consecutively, if Ch > 0xc0, the compression adds 0xc1 before the byte; otherwise, it outputs Ch directly. For a byte Ch that appears N times consecutively, it is compressed into two bytes: 0xc0 + N and Ch. Thus, the maximum N can only be ff - c0 = 3fh (63 in decimal). If N exceeds 63, multiple compressions are required.

1.2 BI_RLE8 Compression

This compression method is used in the bitmap files of WINDOWS 3.0 and 3.1. The encoding is also based on two-byte units. The first byte specifies the number of repetitions of the color indicated by the second byte. For example, the code 0504 means displaying 5 consecutive pixels with a color value of 04 starting from the current position. When the second byte is zero, it has special meanings: 0 indicates the end of a line; 1 indicates the end of the image; 2 is an escape followed by two bytes, which represent the horizontal and vertical offsets of the next pixel relative to the current position. This method can compress images with a maximum of 8-bit (256-color) pixels.

1.3 BI_RLE4 Compression

This method is also used in WINDOWS 3.0/3.1 bitmap files. It is similar to BI_RLE8 encoding, with the only difference being that one byte in BI_RLE4 contains the colors of two pixels. Therefore, it can only compress images with no more than 16 colors, limiting its application scope.

1.4 Packbits Compression

This method is used for bitmap data compression on Apple's Macintosh computers and is employed in the TIFF specification. It is similar to BI_RLE8 compression. For example, 1c1c1c1c2132325648 is compressed into 831c2181325648. Clearly, the best-case scenario for this method is when 128 consecutive bytes are identical, which can be compressed into a single value 7f. This method is quite effective.

2. Huffman Coding Compression

Another common compression method, established in 1952 for text files. The basic principle is to replace frequently used data with shorter codes and rarely used data with longer codes, with each data item having a unique code. These codes are binary and vary in length. For example, an original data sequence ABACCDAA can be encoded as A(0), B(10), C(110), D(111), resulting in the compressed output 010011011011100. Generating Huffman codes requires two passes over the original data: the first pass precisely counts the frequency of each value, and the second pass builds the Huffman tree and encodes the data. Due to the need to construct and traverse a binary tree to generate codes, both compression and decompression are relatively slow. However, its simplicity and effectiveness make it widely used.

3. LZW Compression

LZW compression is more complex than most other compression techniques but offers higher efficiency. The basic principle is to encode each first-occurring string with a numerical value, which is then converted back to the original string during decompression. For example, the string "abccddeee" can be replaced with the value 0x100. Whenever this string appears, 0x100 is used instead, achieving compression. The correspondence between 0x100 and the string is dynamically generated during compression and is implicitly embedded in the compressed data. As decompression proceeds, this encoding table is gradually restored from the compressed data, with subsequent data generating more correspondences based on earlier data. This continues until the end of the compressed file. LZW is reversible, preserving all information.