Databases Reference
In-Depth Information
16.5.5 Tier I Coding
Block Coding
The EBCOT algorithm is a bitplane coder that independently encodes the bitplanes of the
coefficients in a code-block in multiple passes. Each code-block is first divided into subblocks.
For each bitplane the subblocks that contain any coefficients that are significant at that level
are deemed to be significant subblocks. A coefficient
c
ij
is said to be significant at level
n
if
c
ij
2
n
. If we denote the significance of a subblock
B
i
at level
n
by
n
σ
(
B
i
)
, then
n
σ
1 if there is a coefficient
c
ij
in the block with a magnitude greater than or equal to
2
n
, otherwise
(
B
i
)
=
n
0. These significance values are encoded using a quad-tree structure.
The subblocks are identified with leaf nodes. Four neighboring subblocks are viewed as
offsprings of an internal node that corresponds to the union of the four subblocks. These
are, in turn, organized into sets of 2
σ
(
B
i
)
=
2
quads
, and so on. A node in this tree is said to be
significant at level
n
if any of its descendants are significant at that level. The significant values
of the nodes starting from the root node are encoded using an MQ coder with equiprobable
contexts. The significance values that can be inferred from previously encoded significance
values are not encoded. For example, if the significance value of the parent code is 0 then the
significance values of all of the descendants are also going to be zero and, therefore, are not
encoded. Similarly, if a node of the tree has been encoded as significant at a higher level then it
is clearly significant at the lower level and, therefore, does not need to be encoded. Finally, if a
quad is declared to be significant and three of its descendants have been coded as insignificant,
then the fourth descendant is clearly significant and, therefore, the significance value for this
descendant does not need to be encoded.
Each bitplane is encoded in three passes, namely, the
significance propagation pass
,the
magnitude refinement pass
, and the
cleanup pass
. In each pass the coefficients are encoded
using either a
zero-coding
mode or a
run-length
mode. The first time a coefficient becomes
significant, the encoder encodes its sign using a predictive coding approach. The results of the
passes are encoded using an MQ coder (described in Chapter 4) with 18 different contexts.
Nine of these contexts are used in the zero-coding mode, five are used for sign coding, three are
used for magnitude refinement, and one is used for run-length coding. Each bit in a bitplane
is encoded only once.
In the significance propagation pass, only the zero-coding mode is used. The nine zero-
coding contexts are obtained by looking at the significance value of the two horizontal, two
vertical, and four diagonal neighbors of the coefficient being encoded. The rule for context
determination is shown in Table
16.3
. Only coefficients with known significant neighbors are
encoded in this pass. The idea is that neighbors of coefficients that were declared significant
in previous bitplanes are most likely to become significant in subsequent bitplanes. Each
coefficient with significant neighbors is encoded as either significant or insignificant in the
appropriate context as determined by the rule in Table
16.3
. If the coefficient is encoded as
significant the significance status of the coefficient is followed by the sign of the bit. The sign
is encoded as a prediction residual. The prediction for the sign is generated using the sign of
the two horizontal and the two vertical neighbors. The sign of the two horizontal neighbors
and the two vertical neighbors are each encoded into a single value
s
x
(where
x
is either
h
for
×
