Previous | ToC | Next Labs: Error Correction and Compression. Part 2. Math Alive

## Horizontal Differencing and Averaging

The basic principle is very simple. Imagine taking out just one horizontal line from the black and white image. The gray levels for the pixels in this line form a sequence of numbers between 0 and 255. In this sequence many values are very close to their neighbors - sudden jumps only occur if there was a sudden transition there in brightness (say from a light object to a dark wall) in the image. So a piece of this sequence could look like:

45 45 46 46 47 48 53 101 104 105 106 106 107 106 106 106.

If you are given any 2 numbers a and b then you completely characterize them by giving their average s = (a+b)/2 and their difference d = a-b. (Because a = s+d/2, b = s-d/2). The averages and differences for successive pairs in our sequence are:

 s: d: 45 46 47.5 77 104.5 106 106.5 106 0 0 -1 -48 -1 0 1 0

The sequence of differences has many more really small entries than large entries, and such sequences are easy to compress. Moreover, we can now easily make a small change to the d-sequence that would make it even more compressible. For instance, if we replace in the d-sequence every entry that is a 0 or 1 or -1 by 0:

 d': 0 0 0 -48 0 0 0 0
then this d'-sequence is highly compressible.

If we now recompute the original sequence (rounding off if necessary, so that we get integers) by a' = s+d'/2 , b' = s-d'/2, then we get:

45 45 46 46 47 47 53 101 104 104 106 106 106 106 106 106

which is very close to the original.