Cryptography Reference
In-Depth Information
11.2.1 Previous VQ-Based Watermarking Algorithms
Vector Quantization
Vector quantization (VQ) has become an attractive block-based encoding
method for image compression in the last two decades. It can achieve a high
compression ratio. In environments such as image archival and one-to-many
communications, the simplicity of the decoder makes VQ very e
cient. In
brief, VQ can be defined as a mapping from k-dimensional Euclidean space
R
k
i =0, 1,,N−1. That is generally called
a codebook, where c
i
is a codeword and N is the codebook size. VQ first
generates a representative codebook from a number of training vectors using,
for example, the iterative clustering algorithm [22]. It is often referred to as
the generalized Lloyd algorithm (GLA). In VQ, the image to be encoded is
first decomposed into vectors and then sequentially encoded vector by vector.
In the encoding phase, each k-dimensional input vector x =(x
1
,x
2
,,x
k
)is
compared with the codewords in the codebook C =c
0
, c
1
,, c
N−1
. This
is done to find the best matching codeword c
i
=(c
i1
,c
i2
,,c
ik
) satisfying
the following condition:
into a finite subset C =c
i
d (x, c
i
) =
min
0≤j≤N−1
d (x, c
j
).
(11.1)
That is, the distance between x and c
i
is the smallest, where d (x, c
j
)isthe
distortion caused by representing the input vector x by the codeword c
j
. This
is often measured by the squared Euclidean distance. That is,
k
(x
l
−c
jl
)
2
.
d (x, c
j
)=
(11.2)
l=1
The index i of the best matching codeword assigned to the input vector x
is transmitted over the channel to the decoder. The decoder has the same
codebook as the encoder. In the decoding phase, for each index i, the decoder
performs a table look-up operation to obtain c
i
. This is then used to recon-
struct the input vector x. Compression is achieved by transmitting or storing
the index of a codeword rather than the codeword itself. The compression ra-
tio is determined by the codebook size and the dimension of the input vectors.
The overall distortion is dependent on the codebook size and the selection of
codewords.
Watermarking Algorithms Based on Codebook Partition
The main idea of this kind of VQ-based digital watermarking scheme [15, 16,
17, 18] is to carry secret copyright information by codeword indices. The aim
of the codebook partition is to classify the neighboring codewords into the
same cluster. Given a threshold D>0, we denote by S =S
1
,S
2
,,S
M
,
which is a
standard partition
of the codebook C =c
0
, c
1
,, c
N−1
for the
threshold D,ifS satisfies the following four conditions:
