Databases Reference
In-Depth Information
T A B L E 13 . 4
Bit allocation map for an 8
×
8 transform.
8
7
5
3
1
1
0
0
7
5
3
2
1
0
0
0
4
3
2
1
1
0
0
0
3
3
2
1
1
0
0
0
2
1
1
1
0
0
0
0
1
1
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Defining
M
1
M
2
γ
=
1
(σ
θ
k
)
(59)
k
=
and assuming that
α
k
is a constant
α
for all
k
, we obtain the reconstruction error variance for
the
k
th quantizer to be
2
r
k
2
−
2
R
σ
=
αγ
Note that the expression of the reconstruction error variance is independent of
k
. That is, each
of the quantizers in this idealized situation, where the reconstruction error variance is given
by Equation (
52
) with
α
k
=
α
and rates
R
k
are allowed to be nonintegers, contributes equally
to the total reconstruction error variance! We can use this insight to develop a recursive bit
allocation algorithm. Notice from Equation (
52
) that an increase in one bit for the value of
R
k
will result in a reduction by half in the standard deviation of the reconstruction error
σ
r
k
.
Combining these two insights, we obtain the following recursive bit allocation algorithm.
1.
Compute
σ
r
k
for each coefficient. As the number of bits allocated to each coefficient is
zero, initially,
σ
r
k
=
σ
θ
k
.
2.
Set
R
k
=
0 for all
k
, and set
R
b
=
MR
, where
R
b
is the total number of bits available
for distribution.
3.
Sort the standard deviations
{
σ
r
k
}
. Suppose
σ
r
l
is the maximum.
4.
Increment
R
l
by 1, and divide
σ
r
l
by 2.
5.
Decrement
R
b
by 1. If
R
b
=
0, then stop; otherwise, go to Step 3.
If we follow this procedure, we end up allocating more bits to the coefficients with higher
variance. Furthermore, we tend to equalize the amount of distortion contributed by each
coefficient.
This form of bit allocation is called
zonal sampling
. The reason for this name can be seen
from the example of a bit allocation map for the 8
8 DCT of an image shown in Table
13.4
.
Notice that there is a zone of coefficients that roughly comprises the right lower diagonal of the
bit map that has been assigned zero bits. In other words, these coefficients are to be discarded.
The advantage to this approach is its simplicity. Once the bit allocation has been obtained,
every coefficient at a particular location is always quantized using the same number of bits.
The disadvantage is that, because the bit allocations are performed based on average value,
variations that occur on the local level are not reconstructed properly. For example, consider
×
