11 Information Hiding for Spatial and Geographical Data
245
SVD(A) = UΣV
T , where U and V are orthogonal matrices (UU
T
= VV
T
= I, with
I the identity matrix) and Σ is a diagonal matrix, Σdiag(σ 1 , σ 2 , ...., σ M ), whose diagonal entries σ i (i = 1, . . . , M) are in decreasing order and they are called singular
values [12]. The singular values and their distribution vary with different images.
The image energy spreads over all the singular values in the presence of random texture, while only the first singular value dominates all the others in the presence of
smooth regions [25]. The rank of A is defined as the maximum number of linearly
independent columns or, alternatively, as the maximum number of linearly independent rows. An interesting property of the SVD of a matrix is that the rank of a matrix
is equal to the number of the non-zero singular values [12]. With r denoting the rank
of the matrix A, we have A = U r Σ r V
T
r , where U r and V r are obtained, respectively, by
picking the first r singular vectors of U and V, and Σ r is a diagonal matrix of order r
(r ≤ M), whose diagonal entries are σ 1 , σ 2 , ...., σ r . Applying this result to the matrix
representation of images, we have the remaining singular values σ i = 0, for i > r;
thus, these singular values do not contribute to the energy of the image. Then, the
SVD compression may be considered for lossless compression schemes. A higher
compression ratio is achieved by adaptive rank selection [11]: in some applications,
including Web publication or multimedia streaming, it is acceptable to compress the
original data with some loss according to the requirement that a percentage of the
original information is maintained in the compressed data. Thus, fewer ranks than
the rank r may be enough.
The SVD may be applied to the whole image or, alternatively, to small blocks
of it. In image processing, the analysis of many problems can be simplified substantially by working with block matrices [15]. Processing small blocks is suitable to
capture local variations that are addressable in a given block and may disappear at
a coarser level of representation, such as the whole image. Other advantages of the
block-oriented approach include reduced computation and parallel processing [15].
The use of SVD by blocks is suitable in our watermarking scheme, since we embed
the watermark in each block according to their rank and the magnitude of singular
values. Typical values for the block size are 4, 8, 16, 32, 64.
In the following, we develop a new watermarking system based on block-based
SVD compression. This is a novel approach with respect to previous solutions that
apply the SVD to the entire image, without considering how singular values vary
with different blocks of the same image. Also, embedding the watermark in the most
significant singular values of each block makes the watermarking system more robust
to possible attacks.
11.4.2 The Watermarking Embedding
We decided to embed the watermark in the most significant singular values of each
block to prevent possible removal attacks, including lossy compression. The model
of our watermarking system is discussed in the following. Let A
M×N be the matrix representation of the original image to be protected by watermarking. First, it
is divided into blocks H i (i = 1, . . . , B), whose size m × n is small enough to capture the local features. The watermark to be embedded into the ith block is represented by the non-zero entries of a diagonal matrix W k r i . The watermark is embedded
245
SVD(A) = UΣV
T , where U and V are orthogonal matrices (UU
T
= VV
T
= I, with
I the identity matrix) and Σ is a diagonal matrix, Σdiag(σ 1 , σ 2 , ...., σ M ), whose diagonal entries σ i (i = 1, . . . , M) are in decreasing order and they are called singular
values [12]. The singular values and their distribution vary with different images.
The image energy spreads over all the singular values in the presence of random texture, while only the first singular value dominates all the others in the presence of
smooth regions [25]. The rank of A is defined as the maximum number of linearly
independent columns or, alternatively, as the maximum number of linearly independent rows. An interesting property of the SVD of a matrix is that the rank of a matrix
is equal to the number of the non-zero singular values [12]. With r denoting the rank
of the matrix A, we have A = U r Σ r V
T
r , where U r and V r are obtained, respectively, by
picking the first r singular vectors of U and V, and Σ r is a diagonal matrix of order r
(r ≤ M), whose diagonal entries are σ 1 , σ 2 , ...., σ r . Applying this result to the matrix
representation of images, we have the remaining singular values σ i = 0, for i > r;
thus, these singular values do not contribute to the energy of the image. Then, the
SVD compression may be considered for lossless compression schemes. A higher
compression ratio is achieved by adaptive rank selection [11]: in some applications,
including Web publication or multimedia streaming, it is acceptable to compress the
original data with some loss according to the requirement that a percentage of the
original information is maintained in the compressed data. Thus, fewer ranks than
the rank r may be enough.
The SVD may be applied to the whole image or, alternatively, to small blocks
of it. In image processing, the analysis of many problems can be simplified substantially by working with block matrices [15]. Processing small blocks is suitable to
capture local variations that are addressable in a given block and may disappear at
a coarser level of representation, such as the whole image. Other advantages of the
block-oriented approach include reduced computation and parallel processing [15].
The use of SVD by blocks is suitable in our watermarking scheme, since we embed
the watermark in each block according to their rank and the magnitude of singular
values. Typical values for the block size are 4, 8, 16, 32, 64.
In the following, we develop a new watermarking system based on block-based
SVD compression. This is a novel approach with respect to previous solutions that
apply the SVD to the entire image, without considering how singular values vary
with different blocks of the same image. Also, embedding the watermark in the most
significant singular values of each block makes the watermarking system more robust
to possible attacks.
11.4.2 The Watermarking Embedding
We decided to embed the watermark in the most significant singular values of each
block to prevent possible removal attacks, including lossy compression. The model
of our watermarking system is discussed in the following. Let A
M×N be the matrix representation of the original image to be protected by watermarking. First, it
is divided into blocks H i (i = 1, . . . , B), whose size m × n is small enough to capture the local features. The watermark to be embedded into the ith block is represented by the non-zero entries of a diagonal matrix W k r i . The watermark is embedded