Help about RLE


Run Length Encoding

Column by Column Encoding

The compressor scans the bitmap row by row from left to right looking for runs of pixels.

Column by Column Encoding

The compressor scans the bitmap column by column looking for runs of pixels.

Zig Zag Encoding

This encoding method employs a zig-zag technque. Suppose that the rows of a 4 X 4 bitmap are numbered 0, 1, 2, 3 from top to bottom, and that the columns are numbered 0, 1, 2, 3 from left to right. Then the zig-zag technique will scan the pixels of a 4 X 4 bitmap in the following fashion (row, column):

(0,0); (0,1); (1,0); (2,0);
(1,1); (0,2); (0,3); (1,2);
(2,1); (3,0); (3,1); (2,2);
(1,3); (2,3); (3,2); (3,3).

Hilbert Curve Encoding

This encoding method recursively divides the bitmap into square grids of size 2x2, 4x4, or any other power of 2; and follows the same pattern throughout the file until the last pixel is reached. For example, the 8 X 8 bitmap will be scanned in the following manner (row, column):

(0,0); (0,1); (1,1); (1,0);(2,0); (3,0); (3,1); (2,1);
(2,2); (3,2); (3,3); (2,3);(1,3); (1,2); (0,2); (0,3);
(0,4); (1,4); (1,5); (0,5);(0,6); (0,7); (1,7); (1,6);
(2,6); (2,7); (3,7); (3,6);(3,5); (2,5); (2,4); (3,4);
(4,4); (5,4); (5,5); (4,5);(4,6); (4,7); (5,7); (5,6);
(6,6); (6,7); (7,7); (7,6);(7,5); (6,5); (6,4); (7,4);
(7,3); (7,2); (6,2); (6,3);(5,3); (4,3); (4,2); (5,2);
(5,1); (4,1); (4,0); (5,0);(6,0); (6,1); (7,1); (7,0);

Sierpinski Curve Encoding

The Sierpinski Curve consists of four open curves linked together by line segments located in the outer corners. These four parts are ninety degree rotations of the same curve. Assume, that there are four basic curves: A, B, C, and D. The basic construction rule of the Sierpinski curve is S: A\B/C\D/, and the recursion rules are:

A: A \ B - - D / A
B: B / D | | A \ B
C: C \ D - - B / C
D: D / A | | C \ D

For more information about the algorithms, see "Data Compression" by D. Salomon, Springer Verlag, 1998.


E-mail comments or suggestions about RLE to khuri@cs.sjsu.edu or joy.mathcs.sjsu.edu