Databases Reference
In-Depth Information
Arithmetic Coding
Many bi-level images have a lot of local structure. Consider a digitized page of text. In large
portions of the image we will encounter white pixels with a probability approaching 1. In other
parts of the image, there will be a high probability of encountering a black pixel. We can make
a reasonable guess of the situation for a particular pixel by looking at values of the pixels in
the neighborhood of the pixel being encoded. For example, if the pixels in the neighborhood
of the pixel being encoded are mostly white, then there is a high probability that the pixel to
be encoded is also white. On the other hand, if most of the pixels in the neighborhood are
black, there is a high probability that the pixel being encoded is also black. Each case gives us
a skewed probability—a situation ideally suited for arithmetic coding. If we treat each case
separately, using a different arithmetic coder for each of the two situations, we should be able
to obtain improvement over the case where we use the same arithmetic coder for all pixels.
Consider the following example.
Suppose the probability of encountering a black pixel is 0.2 and the probability of encoun-
tering a white pixel is 0.8. The entropy for this source is given by
H
=−
0
.
2log
2
0
.
2
−
0
.
8log
2
0
.
8
=
0
.
722
.
(11)
If we use a single arithmetic coder to encode this source, we will get an average bit rate close
to 0.722 bits per pixel. Now suppose, based on the neighborhood of the pixels, that we can
divide the pixels into two sets, one comprising 80% of the pixels and the other 20%. In the first
set, the probability of encountering a white pixel is 0.95, and in the second set the probability
of encountering a black pixel is 0.7. The entropy of these sets is 0.286 and 0.881, respectively.
If we used two different arithmetic coders for the two sets with frequency tables matched to
the probabilities, we would get rates close to 0.286 bits per pixel about 80% of the time and
close to 0.881 bits per pixel about 20% of the time. The average rate would be about 0.405
bits per pixel, which is almost half the rate required if we used a single arithmetic coder. If we
used only those pixels in the neighborhood that had already been transmitted to the receiver to
make our decision about which arithmetic coder to use, the decoder could keep track of which
encoder was used to encode a particular pixel.
As we have mentioned before, the arithmetic coding approach is particularly amenable to
the use of multiple coders. All coders use the same computational machinery, with each coder
using a different set of probabilities. The JBIG algorithm makes full use of this feature of
arithmetic coding. Instead of checking to see if most of the pixels in the neighborhood are
white or black, the JBIG encoder uses the pattern of pixels in the neighborhood, or
context
,
to decide which set of probabilities to use in encoding a particular pixel. If the neighborhood
consists of 10 pixels with each pixel capable of taking on two different values, the number of
possible patterns is 1024. The JBIG coder uses 1024 to 4096 coders, depending on whether a
low- or high-resolution layer is being encoded.
For the low-resolution layer, the JBIG encoder uses one of the two different neighborhoods
shown in Figure
7.12
. The pixel to be coded is marked
X
,whilethepixelstobeusedfor
templates are marked
A
or
O
.The
A
and
O
pixels are previously encoded pixels and are
available to both the encoder and decoder. The
A
pixel can be thought of as a floating member
of the neighborhood. Its placement is dependent on the input being encoded. Suppose the
image has vertical lines 30 pixels apart. The
A
pixel would be placed 30 pixels to the left of
