Databases Reference
In-Depth Information
Example16.4.1:
Let's use the same example we used for demonstrating the EZW algorithm:
26
6
13
10
−7
7
6
4
4 −4
4 −3
2 −2 −2 0
We will go through three passes at the encoder and generate the transmitted bitstream, then
decode this bitstream.
First Pass
The value for
n
in this case is 4. The three lists at the encoder are
LIP
:{
(
0
,
0
)
→
26
,(
0
,
1
)
→
6
,(
1
,
0
)
→−
7
,(
1
,
1
)
→
7
}
LIS
:{
(
0
,
1
)
D
,(
1
,
0
)
D
,(
1
,
1
)
D}
LSP
:{}
In the listing for the LIP, we have included the arrows to make it easier to follow the example.
Beginning our algorithm, we examine the contents of the LIP. The coefficient at location (0, 0)
is greater than 16. In other words, it is significant; therefore, we transmit a 1, thena0toindicate
the coefficient is positive and move the coordinate to the LSP. The next three coefficients are
all insignificant at this value of the threshold; therefore, we transmit a 0 for each coefficient
and leave them in the LIP. The next step is to examine the contents of the LIS. Looking at the
descendants of the coefficient at location (0, 1) (13, 10, 6, and 4), we see that none of them are
significant at this value of the threshold so we transmit a 0. Looking at the descendants of
c
10
and
c
11
, we can see that none of these are significant at this value of the threshold. Therefore,
we transmit a 0 for each set. As this is the first pass, there are no elements from the previous
pass in the LSP; therefore, we do not do anything in the refinement pass. We have transmitted
a total of 8 bits at the end of this pass (10000000), and the situation of the three lists is as
follows:
:{
(
,
)
→
,(
,
)
→−
,(
,
)
→
}
LIP
0
1
6
1
0
7
1
1
7
LIS
:{
(
0
,
1
)
D
,(
1
,
0
)
D
,(
1
,
1
)
D}
LSP
:{
(
0
,
0
)
→
26
}
Second Pass
For the second pass we decrement
n
by 1 to 3, which corresponds to a threshold
value of 8. Again, we begin our pass by examining the contents of the LIP. There are three
elements in the LIP. Each is insignificant at this threshold so we transmit three 0s. The next
step is to examine the contents of the LIS. The first element of the LIS is the set containing
the descendants of the coefficient at location (0, 1). Of this set, both 13 and 10 are significant
at this value of the threshold; in other words, the set
is significant. We signal this by
sending a 1 and examine the offsprings of
c
01
. The first offspring has a value of 13, which
D
(
0
,
1
)
