 | |
Apr 25, 2001
Error-Free Compression
Probability of each run length vector: hi = Li/Ni
where Li is length of individual vector and Ni is total
number of pixels in the image with graylevel Gi.
If there are J vectors defining the run sequences of value Ga, and
the probability for a vector Li
specifying a specific sequence length
Lai of Ga values is given by hai = NLai/J, then the entropy Ea for the
vectors specifying value Ga is Ea = -Σi
hai·lb(hai). A similar expression is obtained for K vectors specifying the value Gb:
Ea = -Σi hbi·lb(hbi).
Defining La = (Σi
Lai)/J then gives the entropy for the entire binary image using run
length coding as
Erl = (Ea + Eb)/(La
+ Lb).
An example image is:
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
In uncompressed form, this image takes 49 bits. To perform run length
encoding, first give the value and the length of all sequences in each row. With
one bit for value and three bits for length, this picture will require 36 bits
to represent. This represents a compression ratio of 1.36 : 1. A zig-zag scan
would further reduce the requirement to 30 bits, using 5 bits for the lengths.
Other approaches find the edges of objects and then encode the edges using
Fourier descriptors or 8-bit chain codes. The Fourier method can give errors
unless all the Fourier descriptors are used.
Predictive coding:
Assume that pixels are correlated and encode the differences between adjacent
pixels instead of the pixel values themselves. This requires some estimation
function fest(x,y), which can be compared to the original image f(x,y).
Subtracting fest(x,y) from f(x,y) gives an error function e(x,y)
which hopefully has much smaller values than the pixel values. One simple
estimation function (differential coding) is to assume that each pixel
has the same value as its predecessor:
fest(x,y) = f(x-1,y).
Sample image:
|
0 |
0 |
2 |
3 |
4 |
|
1 |
1 |
2 |
3 |
3 |
|
1 |
1 |
3 |
4 |
4 |
|
1 |
2 |
3 |
4 |
4 |
|
1 |
0 |
2 |
4 |
4 |
Straight binary coding of this image using 3-bit code will require 75 bits.
Application of the simple predictor described above, fest(x,y) = f(x-1,y),
going row by row, and specifying the initial value of each row, gives
0: 0, 2, 1, 1
1: 0, 1, 1, 0
1: 0, 2, 1, 0
1: 1, 1, 1, 0
1: -1, 2, 2, 0
Now using 2 bits for the difference graylevels and 3 bits to represent the
first graylevel in each row results in a total of 55 bits. The compression ratio
is 1.36 : 1. Zig-zag scanning will eliminate the need to give the initial row
values after the first row and allow longer sequences. Then only the initial
value and 24 difference values are required. Huffman coding makes the average
number of pits/pixel equal to 1.87. Adding three bits for the initial value
brings the total storage requirement to 48 bits for a compression ratio of 1.56
: 1.
Last modified on April 25, 2001
|
