Databases Reference
In-Depth Information
+
−
−
−
−
Y
2
−
Y
1
Y
3
Q
3
Q
1
X
−
Index
Index
−
F I GU R E 10 . 27
A three-stage vector quantizer.
10.7.4 Multistage Vector Quantization
Multistage vector quantization [
159
] is an approach that reduces both the encoding complexity
and the memory requirements for vector quantization, especially at high rates. In this approach,
the input is quantized in several stages. In the first stage, a low-rate vector quantizer is used to
generate a coarse approximation of the input. This coarse approximation, in the form of the
label of the output point of the vector quantizer, is transmitted to the receiver. The error between
the original input and the coarse representation is quantized by the second-stage quantizer, and
the label of the output point is transmitted to the receiver. In this manner, the input to the
n
th-stage vector quantizer is the difference between the original input and the reconstruction
obtained from the outputs of the preceding
n
1 stages. The difference between the input to
a quantizer and the reconstruction value is often called the
residual
, and the multistage vector
quantizers are also known as
residual vector quantizers
[
160
]. The reconstructed vector is the
sum of the output points of each of the stages. Suppose we have a three-stage vector quantizer,
with the three quantizers represented by
Q
1
,
−
Q
2
, and
Q
3
. Then for a given input
x
, we find
y
1
=
Q
1
(
x
)
y
2
=
Q
2
(
x
−
Q
1
(
x
))
y
3
=
Q
3
(
x
−
Q
1
(
x
)
−
Q
2
(
x
−
Q
1
(
x
)))
(11)
ˆ
The reconstruction
x
is given by
x
ˆ
=
y
1
+
y
2
+
y
3
(12)
This process is shown in Figure
10.27
.
If we have
K
stages, and the codebook size of the
n
th-stage vector quantizer is
L
n
, then
the effective size of the overall codebook is
L
1
×
L
2
× ··· ×
L
K
. However, we need to
store only
L
1
+
L
K
vectors, which is also the number of comparisons required.
Suppose we have a five-stage vector quantizer, each with a codebook size of 32, meaning that
we would have to store 160 codewords. This would provide an effective codebook size of
32
5
L
2
+···+
432. The computational savings are also of the same order.
This approach allows us to use vector quantization at much higher rates than we could
otherwise. However, at rates at which it is feasible to use LBG vector quantizers, the perfor-
mance of the multistage vector quantizers is generally lower than the LBG vector quantizers
[
136
]. The reason for this is that after the first few stages, much of the structure used by the
vector quantizer has been removed, and the vector quantization advantage that depends on this
structure is not available. Details on the design of residual vector quantizers can be found in
[
160
,
161
].
=
33
,
554
,
