Databases Reference
In-Depth Information
We have encoded twelve bits, and the sequence of bits generated by the encoder until this point
is 00111. In other words we have a coding rate of 5/12 bits/pixel, which is less than half the
coding rate we would have achieved had we used a single
Cum_Count
table. At this point if
we wish to terminate the encoding we would have to incur the overhead of transmitting the
bits in the lower limit. The six bits of the lower limit would be a significant overhead for this
toy sequence. However, in practice, when the input sequence is much longer than twelve, the
six-bit overhead would be negligible. We leave the decoding of this sequence as an exercise
for the reader.
Furthermore, the simple nature of the coder allows for approximations that result in simple
and fast implementations. We will look at three applications of the binary coder including the
QM coder used in the JBIG standard for encoding bilevel images and the M (or modulo) coder,
which is a part of the coder CABAC used in the H.264 video coding standard.
Before we describe the particular implementations, let us take a general view of binary
arithmetic coding. In our description of arithmetic coding, we updated the tag interval by
updating the endpoints of the interval,
u
(
n
)
and
l
(
n
)
. We could just as well have kept track of
one endpoint and the size of the interval. This is the approach adopted in many of the binary
coders, which track the lower end of the tag interval
l
(
n
)
and the size of the interval
A
(
n
)
, where
A
(
n
)
=
u
(
n
)
−
l
(
n
)
(58)
The tag for a sequence is the binary representation of
l
(
n
)
.
We can obtain the update equation for
A
(
n
)
by subtracting Equation (
9
) from Equation (
10
)
and substituting
A
(
n
)
for
u
(
n
)
−
l
(
n
)
.
A
(
n
)
=
A
(
n
−
1
)
(
F
X
(
x
n
)
−
F
X
(
x
n
−
1
))
(59)
A
(
n
−
1
)
P
=
(
x
n
)
(60)
Substituting
A
(
n
)
for
u
(
n
)
−
l
(
n
)
in Equation (
9
), we get the update equation for
l
(
n
)
:
l
(
n
)
=
l
(
n
−
1
)
+
A
(
n
−
1
)
F
X
(
x
n
−
1
)
(61)
Instead of dealing directly with the 0s and 1s put out by the source, many of the binary
coders map them into a More Probable Symbol (MPS) and Less Probable Symbol (LPS). If
0 represents black pixels and 1 represents white pixels, then in a mostly black image, 0 will
be the MPS, whereas in an image with mostly white regions 1 will be the MPS. Denoting the
probability of occurrence of the LPS for the context
C
by
q
c
and mapping the MPS to the lower
subinterval, the occurrence of an MPS symbol results in the update equations
l
(
n
)
=
l
(
n
−
1
)
(62)
A
(
n
)
=
A
(
n
−
1
)
(
1
−
q
c
)
(63)
while the occurrence of an LPS symbol results in the update equations
l
(
n
)
=
l
(
n
−
1
)
+
A
(
n
−
1
)
(
1
−
q
c
)
(64)
A
(
n
)
=
A
(
n
−
1
)
q
c
(65)
