Pixel packing

Pixel packing is a method which allows pixels to be stored in an optimal way: for a monochrome image there are, by definition, only two colours, a point of the image can thus be coded in only one bit to gain memory space.

RLE Compression

The RLE compression method (Run Length Encoding, sometimes written as RLC for Run Length Coding) is used by many image formats (BMP, PCX, TIFF). It is based on the repetition of consecutive elements.

The basic principle consists in coding a first element by giving the number of repetitions of a value and then the value to be repeated. Thus, according to this principle, chain “AAAAAHHHHHHHHHHHHHH” when compressed yields “5A14H”. The compression gain is thus (19-5) /19, that is, approximately 73.7% On the other hand, for the chain “CORRECTLY”, where there is little character repetition, the result of the compression is “1C1O2R1E1C1T1L1Y”, thus compression proves to be very expensive here, with a negative compression gain of (9-16)/9 that is, -78%!

Actually, RLE compression is governed by particular rules which allow compression to be carried out when necessary and the chain to be left as it is when compression causes a waste. These rules are the following:

• If three or more elements are repeated consecutively, the RLE compression method is used
• If not, a control character (00) is inserted, followed by the number of elements of the non-compressed chain and then the latter
• • If the number of elements of the chain is odd, the control character (00) is added on the end
• • Finally, specific control characters were defined in order to code:
  • an end of line (00 01)
  • the end of the image (00 00)
  • a pointer displacement over the image of XX columns and YY rows in the reading direction (00 02 XX YY).

Thus, RLE compression makes no sense except for data with many consecutive repeated elements, in particular images with large uniform areas. This method however has the advantage of not being very difficult to implement. There are alternatives in which the image is encoded by blocks of pixels, in rows, or even in zigzag.

Last update on Thursday October 16, 2008 02:43:16 PM.This document entitled « RLE Compression  » from Kioskea (en.kioskea.net) is made available under the Creative Commons license. You can copy, modify copies of this page, under the conditions stipulated by the licence, as this note appears clearly.