2-D Run-Length Encoding#
Transferring images via e.g. a serial port from / to a display requires a lot of traffic to be sent over the communication port. To increase speed and decrease the number of bytes to be sent a compression algorithm is mandatory. Standard compression algorithms require a lot of computing effort (in terms of processing power and memory space required) which cannot be afforded by low power embedded systems.
Besides that a scan line based algorithm is preferred to be used enabling the controller to not need to analyze the complete image before compressing it. Speed of compression / decompression is also a very important issue.
Run-length encoding#
Run-length encoding is a very simple and fast algorithm to compress single scan lines, especially if the screen does not contain pictures but graphic images used to e.g. control a machine. Run-length encoding is made up of control sequences telling how many repetitions of a single color value will follow.
The disadvantage of simple run-length encoding is that every scan line is compressed separately thus resulting in rather weak performance (in terms of compression rate) especially when processing graphic images. As these images often contain partial identical scan lines following each other a 2D run-length encoding algorithm was developed.
Details of implementation#
Control sequences#
Control sequences are normally made up by a single byte where the 2 most significant bits indicate the type of repetition and the 6 least significant bits specify the repeat count (a value of 0 specifies a repetition of 1).
Bit 7 (HORZ_REPETITION_FLAG) set only: indicates a (horizontal) repetition of a single color value
Bit 6 (VERT_REPETITION_FLAG) set only: indicates a (vertical) repetition of the same part of the previous scan line
Bit 7 + Bit 6 both set: indicates the start of a 2-byte control sequence where the first byte contains a “repetition increase” ((count + 1) times 64) , specified in bit 0 … bit 5), followed by a second byte containing the type-of-repetition information (horizontal or vertical repetition) and the number of remaining repetitions.
Bit 7 + Bit 6 both cleared: indicates a count of uncompressed data run
Color format used by examples following below#
We support 16 bit images only, format is 5 red, 6 green and 5 blue bits.
So the hex value for red is 0xF800, for green it’s 0x07E0 and blue has the value 0x001F. Full white is 0xFFFF and full black is 0x0000.
The least significant byte of a color word is sent first.
Example 1#
The above image is a 20 x 2 pixel sized image where the first scan line contains one red, green and blue pixel followed by 17 white pixels.
So the first scan line has the following representation:
0x02 3 uncompressed pixels following:
0x00 0xF8 red pixel
0xE0 0x07 green pixel
0x1F 0x00 blue pixel
0x90 indicates a (horizontal) repetition (bit 7 set) of 17 pixel ...
0xFF 0xFF ... with white color
The second scan line has 8 identical pixels (compared with the previous scan line) followed by 12 black pixels, so the hex representation is as follows:
0x47 number of identical (bit 6 set) pixels is 8 (vertical repetition)
Note: no argument needed in this case
0x8B indicates a horizontal repetition (bit 7 set) of 12 pixel ...
0x00 0x00 .. with black color
Example 2#
Example 2 shows how the “repetition increase” sequence is used.
Scan line #1 contains a 68 pixel wide gray scale area followed by a 100 pixel wide blue area. Scan line #2 has a 150 pixel wide area with the same contents as scan line #1 followed by a 18 pixel wide red area. The complete image has a size of 168 x 2 pixels.
Scan line #1:
0xC0 "repetition increase" (bit 7 + 6 set) of 1 x 64
0x03 68 uncompressed pixels (bit 6 + 7 not set) follow: 64 (see above) + 3 + 1
0xFF 0xFF pixel #0: white color
: color word-values for pixel #1 ... pixel # 66
0x00 0x00 pixel #67: black color
0xC0 "repetition increase" (bit 7 + 6 set) of 1 x 64
0xA3 indicates a horizontal repetition (bit 7 set) of 64 (see above) + 35 + 1 = 100 pixels ...
0x1F 0x00 ... with blue color
Scan line #2:
0xC1 "repetition increase" (bit 7 + 6 set) of 2 x 64
0x55 bit 6 indicates vertical repetition, count is 2 x 64 (see above) + 21 + 1 = 150 pixels
0x91 indicates a horizontal repetition (bit 7 set) of 18 pixels ...
0x00 0xF8 ... with red color
Sample Source Code#
This sample code shows how to read and write compressed screen contents using 2D Run-Length Encoding.