Databases Reference
In-Depth Information
form of coding is called
embedded coding
. In order to enhance this aspect of the algorithm,
we can also sort the subordinate list at the end of each pass using information available to both
encoder and decoder. This increases the likelihood of larger coefficients being encoded first,
thus providing for a greater reduction in the reconstruction error.
Finally, in the example we determined the number of bits used by assuming fixed-length
encoding. In practice, arithmetic coding is used, providing a further reduction in rate.
16.4 Set Partitioning in Hierarchical Trees
The SPIHT (Set Partitioning in Hierarchical Trees) algorithm is a generalization of the EZW
algorithm and was proposed by Amir Said andWilliamPearlman [
216
]. Recall that in EZWwe
transmit a lot of information for little cost when we declare an entire subtree to be insignificant
and represent all the coefficients in it with a zerotree root label
zr
. The SPIHT algorithm uses a
partitioning of the trees (which in SPIHT are called
spatial orientation trees
) in a manner that
tends to keep insignificant coefficients together in larger subsets. The partitioning decisions
are binary decisions that are transmitted to the decoder, providing a significance map encoding
that is more efficient than EZW. In fact, the efficiency of the significance map encoding in
SPIHT is such that arithmetic coding of the binary decisions provides very little gain. The
thresholds used for checking significance are powers of two, so in essence the SPIHT algorithm
sends the binary representation of the integer value of the wavelet coefficients. As in EZW, the
significance map encoding, or set partitioning and ordering step, is followed by a refinement
step in which the representations of the significant coefficients are refined.
Let's briefly describe the algorithm and then look at some examples of its operation.
However, before we do that we need to get familiar with some notation. The data structure
used by the SPIHT algorithm is similar to that used by the EZW algorithm—although not
the same. The wavelet coefficients are again divided into trees originating from the lowest
resolution band (Band I in our case). The coefficients are grouped into 2
2 arrays that, except
for the coefficients in Band I, are offsprings of a coefficient of a lower resolution band. The
coefficients in the lowest resolution band are also divided into 2
×
2 arrays. However, unlike
the EZW case, all but one of them are root nodes. The coefficient in the top-left corner of the
array does not have any offsprings. The data structure is shown pictorially in Figure
16.11
for
a seven-band decomposition.
The trees are further partitioned into four types of sets, which are sets of coordinates of the
coefficients:
×
O
(
i
,
j
)
This is the set of coordinates of the offsprings of thewavelet coefficient at location
(
i
,
j
)
. As each node can either have four offsprings or none, the size of
O
(
i
,
j
)
is either
zero or four. For example, in Figure
16.11
the set
O
(
0
,
1
)
consists of the coordinates of
the coefficients
b
1
,
b
2
,
b
3
, and
b
4
.
D
(
.D -
scendants include the offsprings, the offsprings of the offsprings, and so on. For ex-
ample, in Figure
16.11
the set
i
,
j
)
This is the set of all descendants of the coefficient at location
(
i
,
j
)
D
(
0
,
1
)
consists of the coordinates of the coefficients
b
1
,...,
b
4
,
b
11
,...,
b
14
,...,
b
44
. Because the number of offsprings can either be zero
