Cryptography Reference
In-Depth Information
11.2.2 Multistage VQ based Multipurpose Watermarking
Algorithm
Multistage Vector Quantization
The basic idea of multistage VQ is to divide the encoding task into successive
stages, where the first stage does a relatively crude quantization of the input
vector using a small codebook. A second stage quantizer then operates on
the error vector between the original and quantized first stage output. The
quantized error vector then provides a second approximation to the original
input vector which leads to a refined or a more accurate representation of the
input. A third stage quantizer may then be used to quantize the second stage
error to provide a further refinement.
In this chapter, we adopt a two-stage vector quantizer as illustrated in
Fig. 11.1. It is the simplest case and can be used to generate the gen-
eral multistage vector quantizer. The input vector x is quantized by the
initial or first stage vector quantizer denoted by VQ
1
whose codebook is
C
1
=
with size N
1
. The quantized approximation
x
1
is then subtracted from x producing the error vector e
2
. This error vec-
tor is then applied to a second vector quantizer VQ
2
whose codebook is
C
2
=
c
10
, c
11
,, c
1(N
1
−1)
with size N
2
yielding the quantized output e
2
.
The overall approximation x to the input x is formed by summing the first
and second approximations, x
1
and e
2
. The encoder for this VQ simply trans-
mits a pair of indices specifying the selected codewords for each stage. The
task of the decoder is to perform two table lookups to generate and then sum
the two codewords. In fact, the overall codeword or index is the concatenation
of codewords or indices chosen from each of two codebooks. That is, this is a
product code where the composition function g of the decoder is a summation
of the reproductions from the different two VQ decoders. Thus the equivalent
product codebook C can be generated from the Cartesian product C
1
c
20
, c
21
,, c
2(N
2
−1)
C
2
.
Compared to the full search VQ with the product codebook C, the two-stage
VQ can reduce the complexity from N = N
1
N
2
to N
1
+ N
2
.
+
E
+
E
2
2
X
+
+
ˆ
VQ
2
_
+
X
1
VQ
1
X
1
Fig. 11.1.
Two-stage VQ.
