# Multiple Watermarking Algorithm Based on Spread Transform Dither Modulation

Xinchao Li, Ju Liu1, Jiande Sun, Xiaohui Yang, and Wei Liu Xinchao Li, Ju Liu,
Jiande Sun, and Xiaohui Yang are with the School of Information Science and
Engineering, Shandong University, Jinan, 250100, China (e-mail:
juliu@sdu.edu.cn).Ju Liu and Wei Liu are with the Hisense State Key Laboratory
of Digital Multi-Media Technology Co., Ltd, Qingdao, China. This work was
supported partially by the National Basic Research Program of China (973
Program, No.2009CB320905), the National Natural Science Foundation of China
(60872024), the Cultivation Fund of the Key Scientific and Technical
Innovation Project (708059), Education Ministry of China for funding, Nature
Science Foundation of Shandong Province (Q2008G03), Doctoral Program
Foundation of Institutions of Higher Education of China (200804221023).

###### Abstract

Multiple watermarking technique, embedding several watermarks in one carrier,
has enabled many interesting applications. In this study, a novel multiple
watermarking algorithm is proposed based on the spirit of spread transform
dither modulation (STDM). It can embed multiple watermarks into the same
region and the same transform domain of one image; meanwhile, the embedded
watermarks can be extracted independently and blindly in the detector without
any interference. Furthermore, to improve the fidelity of the watermarked
image, the properties of the dither modulation quantizer and the proposed
multiple watermarks embedding strategy are investigated, and two practical
optimization methods are proposed. Finally, to enhance the application
flexibility, an extension of the proposed algorithm is proposed which can
sequentially embeds different watermarks into one image during each stage of
its circulation. Compared with the pioneering multiple watermarking
algorithms, the proposed one owns more flexibility in practical application
and is more robust against distortion due to basic operations such as random
noise, JPEG compression and valumetric scaling.

###### Index Terms:

Multiple Watermarking, STDM, Constrained Quadratic Minimization, Sequential
Multiple Watermarking

##  I Introduction

In recent years, as the rapid development in the field of digital
watermarking, multiple watermarking algorithms which give the possibility of
embedding different watermarks in the same image, have received widespread
attention since the pioneering contribution [1], where the idea of embedding
multiple watermarks in the same image is initially presented.

Since then, multiple watermarking has enabled many interesting applications.
In [2], Mintzer and Braudaway suggest that the insertion of multiple
watermarks can be exploited to convey multiple sets of information. Sencar and
Memon [3] apply the selective detection of multiple embedded watermarks, which
can yield lower false-positive rates compared with embedding a single
watermark, to resist ambiguity attacks. Boato et al. [4] introduce a new
approach that allows the tracing and property sharing of image documents by
sequentially embedding multiple watermarks into the data. Giakoumaki et al.
[5] apply multiple watermarking algorithm to simultaneously addresses medical
data protection, archiving, and retrieval, as well as source and data
authentication.

Meanwhile, different watermarking techniques and strategies have been proposed
to achieve multiple watermarking. In [6], Sheppard et al. discuss three
methods to achieve multiple watermarking: rewatermarking, composite
watermarking and segmented watermarking. Rewatermarking embeds watermarks one
after another and the watermark signal could only be detected in the
corresponding watermarked image using the former watermarked signal as the
original image. The watermark embedded previously may be destroyed by the one
embedded later. Composite watermarking discusses the extension of single
watermarking algorithms to the case of multiple watermarking by introducing
orthogonal watermarks [7, 8]. Being similar to these, CDMA based schemes [9,
10] use the orthogonal codes to modulate the watermarks from different users
to derive the orthogonal watermarks. Unfortunately, they cannot guarantee the
robustness in the case of blind extraction. Segmented watermarking embeds
multiple watermarks into different segments of one image. Clearly, the number
of segments limits the number and size of watermarks to be embedded [11]. The
embedding pattern chosen for mapping watermarks to segments can greatly affect
the robustness of each watermark against cropping attack [12].

Other schemes embed different watermarks into different channels of the host
data, e.g., different levels of wavelet transform coefficients[5], or RGB of
the color image [13, 14]. In fact, the limited quantity of watermarks embedded
would somehow constrain their application area.

In this study, we focus on the techniques that can embed multiple watermarks
into the same area and the same transform domain of one image, meanwhile, the
embedded watermarks can be extracted independently and blindly in the detector
without any interference.

To this end, a novel multiple watermarking algorithm is proposed. It initially
extends the spread transform dither modulation (STDM), a single watermarking
algorithm, to the field of multiple watermarking. Moreover, through
investigating the properties of the dither modulation (DM) quantizer and the
proposed multiple watermarks embedding strategy, two optimization methods are
presented which can improve the fidelity of the watermarked image
significantly. Compared with the pioneering multiple watermarking algorithm
[15], it has considerable advantages, especially in robustness against Gauss
Noise, Salt&Pepper Noise, JPEG Compression and Valumetric Scaling. Finally,
some potential interesting applications are discussed and an application
extension of our algorithm is proposed to realize image history management by
sequentially embedded watermarks.

The reminder of this paper is organized as follows. In section II, we briefly
describe the main algorithm of spread transform dither modulation. In section
III, the proposed multiple watermarking algorithm is introduced. In section
IV, to improve the fidelity of the watermarked image, the properties of the
dither modulation quantizer and the embedding strategy of the proposed
algorithm are analyzed. In section V, two practical optimization methods are
presented. In section VI, the efficiency of the two optimization methods is
tested, meanwhile, the robustness of the proposed methods is assessed.
Finally, some potential interesting applications of the proposed algorithm and
the concluding remarks are summarized in section VII and VIII, respectively.

##  II Spread Transform Dither Modulation

As the proposed multiple watermarking algorithm is based on Spread Transform
Dither Modulation, a blind single watermarking algorithm belonging to the QIM
family, introduction beginning with the basic QIM is appropriate.

###  II-A Quantization Index Modulation

Fig. 1: Embedding one message bit, $m$, into one sample $x$ using original
QIM, where sets of circles and crosses represent $\Omega^{0}$ and
$\Omega^{1}$, respectively.

In the original QIM watermarking, a set of features extracted from the host
signal are quantized by means of a quantizer chosen from a pool of predefined
quantizers on the basis of the to-be-hidden message [16]. In the simplest
case, a set of uniform quantizers are used leading to lattice-based QIM
watermarking. As illustrated in Fig.1, the basic QIM uses two quantizers
$Q^{0}$ and $Q^{1}$ to implement the function, and each of them maps a value
to the nearest point belonging to a class of predefined discontinuous points,
one class ($\Omega^{0}$) represents bit 0 while the other ($\Omega^{1}$)
represents bit 1 [17]. The standard quantization operation with step-size
$\Delta$ is defined as

$\operatorname{Q}(x,\Delta)=\Delta\cdot\operatorname{round}(\frac{x}{\Delta})$
(1)

where the function round(.) denotes rounding a value to the nearest integer.

In the embedding procedure, according to the message bit $m$, $Q^{0}$ or
$Q^{1}$ is chosen to quantize the sample $x$ to the nearest quantization point
$y$. For example, $Q^{0}$ and $Q^{1}$ may be chosen in such way that $Q^{0}$
quantizes x to even integers and $Q^{1}$ quantizes x to odd integers. If we
wish to embed a 0 bit, then $Q^{0}$ is chosen, else $Q^{1}$.

In the detecting procedure, it is reasonable to assume the marked signal $y$
is corrupted by the attacker, resulting in a noisy signal $\tilde{y}$. The QIM
detector is a minimum-distance decoder, which finds the quantization point
closest to $\tilde{y}$ and outputs the estimated message bit $\tilde{m}$ [18].

$\tilde{m}=\operatorname*{argmin}\limits_{m\in\mathbf{0,1}}\operatorname{dist}(\tilde{y},\Omega^{m})$
(2)

where ${\mathop{\rm
dist}\nolimits}(\tilde{y},\Omega^{m})\buildrel\Delta\over{=}\mathop{\min}\limits_{s\in\Omega^{m}}\left|{\tilde{y}-s}\right|$.

###  II-B QIM-Dither Modulation

Dither modulation, proposed by Chen and Wornell [16], is an extension of the
original QIM. Compared with the original QIM, it uses the pseudo-random dither
signal, which can reduce quantization artifacts, to produce a perceptually
superior quantized signal. Meanwhile, through the dither procedure, the
quantization noise is independent from the host signal. The DM quantizer QDM
is as following

$y=\operatorname{QDM(x,\Delta,d^{m})}=\operatorname{Q}(x+d^{m},\Delta)-d^{m},m=0,1$
(3)

where $y$ is the marked signal of $x$ by DM quantizer, $d^{m}$ is the dither
signal corresponding to the message bit $m$.

$d^{1}=d^{0}-\operatorname{sign}(d^{0})\frac{\Delta}{2}$ (4)

where $d^{0}$ is a pseudo-random signal and is usually chosen with a uniform
distribution over $[-\Delta/2,\Delta/2]$.

In the detecting procedure, the detector firstly applies the QDM quantizer (3)
to produce two signals $S^{0}$ and $S^{1}$, by embedding “0” and “1” into the
received signal $\tilde{y}$ respectively.

$S^{m}=\operatorname{QDM}(\tilde{y},\Delta,d^{m})=\operatorname{Q}(\tilde{y}+d^{m},\Delta)-d^{m},m=0,1$
(5)

where $d^{m}$ must be exactly the same as which in the embedding procedure.
Note that the pseudo-random signal $d^{0}$ can be considered as a key to
improve the security of the system, and in what follows, this secret signal is
referenced as the dither factor, $df$.

The detected message bit is then estimated by judging which of these two
signals has the minimum Euclidean distance to the received signal $\tilde{y}$,
in the same manner as (2).

$\tilde{m}=\operatorname*{argmin}\limits_{m\in\mathbf{0,1}}\operatorname{dist}(\tilde{y},S^{m})$
(6)

###  II-C QIM-Spread Transform Dither Modulation

As an important extension of the original QIM, STDM applies the idea of
projection modulation. It utilizes the DM quantizer to modulate the projection
of the host vector along a given direction. This scheme combines the
effectiveness of QIM and robustness of spread-spectrum system, and provides
significant improvements compared with DM.

Fig. 2: Block diagram of spread transform dither modulation

To embed one message bit $m$, a host vector x, consisting of samples to be
embedded, is projected onto a random vector u to get the projection $x_{p}$.
Then, the projection $x_{p}$ is modulated according to the message bit $m$
using the DM quantizer (3). This procedure can be illustrated in Fig.2, and
the watermarked vector g is as follows,

${\bf{g}}={\bf{x}}+(\frac{{{\mathop{\rm QDM}\nolimits}({\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}}),\Delta,d^{m})-{\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}})}}{{\left\|{\bf{u}}\right\|_{2}}}){\bf{u}}$
(7)

where ${\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}})\buildrel\Delta\over{=}\frac{{\left\langle{{\bf{x}},{\bf{u}}}\right\rangle}}{{\left\|{\bf{u}}\right\|_{2}}}$,
$\left\langle{{\bf{x}},{\bf{u}}}\right\rangle$ is the inner product of x and
u, $\left\|{\;\cdot\;}\right\|_{2}$ denotes the $L^{2}$-norm operation.
$\Delta$ is the quantization step generated from a pseudo-random generator.

In the detecting procedure, the detector projects the received vector
${\bf{\tilde{g}}}$ onto the random vector u. And then, it utilizes the DM
detector to estimate the message bit $\tilde{m}$ from the projection, in the
same manner as (5) and (6). This can be expressed as follows,

$\tilde{m}=\mathop{\arg\min}\limits_{m\in\\{0,1\\}}{\mathop{\rm
dist}\nolimits}({\mathop{\rm
proj}\nolimits}({\bf{\tilde{g}}},{\bf{u}}),{\mathop{\rm
QDM}\nolimits}({\mathop{\rm
proj}\nolimits}({\bf{\tilde{g}}},{\bf{u}}),\Delta,d^{m})\;)$ (8)

Note that, the random vector u and the random positive real number $\Delta$
used in the STDM detector must be exactly the same as they are in the
embedder, and can be considered as two keys which are only known to the
embedder and detector, thereby improving the security of the system.

##  III Multiple Watermarking Algorithm

Based on the algorithms mentioned above, we extend the spread transform dither
modulation (STDM), a single watermarking algorithm, to the field of multiple
watermarking application. The proposed multiple watermarking algorithm, namely
STDM-Multiple Watermarking (STDM-MW), can embed multiple watermarks into the
same area and the same transform domain of one image, meanwhile, the embedded
watermarks can be extracted independently and blindly in the detector without
any interference.

###  III-A Fundamental Idea

As mentioned in section II, to embed a single message bit, $m$, STDM modulates
the projection of the host vector $\bf{x}$ along a given direction $\bf{u}$.
The modulated host vector $\bf{g}$ can be expressed as follows,

${\bf{g}}={\bf{x}}+k{\bf{u}}$ (9)

To detect the message bit, the detector projects the modulated vector $\bf{g}$
onto the given direction $\bf{u}$. And then, it utilizes the DM detector to
estimate the message bit from the projection. This detection mechanism induces
the vector $\bf{g}$ must be subject to

${\mathop{\rm proj}\nolimits}({\bf{g}},{\bf{u}})={\mathop{\rm
QDM}\nolimits}({\mathop{\rm proj}\nolimits}({\bf{x}},{\bf{u}}),\Delta,d^{m})$
(10)

Thus, the embedding procedure is actually to derive the scaling factor $k$
used in (9) to make the modulated vector $\bf{g}$ in the form of (10).
Substituting (9) into (10), the scaling factor $k$ can be given by

$k=\frac{{{\mathop{\rm QDM}\nolimits}({\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}}),\Delta,d^{m})-{\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}})}}{{\left\|{\bf{u}}\right\|_{2}}}$ (11)

Inspired by this, to embed multiple message bits, $m_{1}$, $m_{2}$,…, $m_{n}$,
into the same host vector $\bf{x}$, we can modulate the projection of the host
vector $\bf{x}$ along different given directions, $\bf{u}_{1}$,
$\bf{u}_{2}$,…, $\bf{u}_{n}$. The modulated host vector $\bf{g}$ can be
expressed as follows

$\;{\bf{g}}={\bf{x}}+{\bf{U}}{\bf{K}}$ (12)

where ${\bf{U}}=[{\bf{u}}_{1},{\bf{u}}_{2},...,{\bf{u}}_{n}]$,
${\bf{K}}=[k_{1},k_{2},...,k_{n}]^{T}$.

To detect the message bits, the modulated vector $\bf{g}$ is projected onto
the given directions, $\bf{u}_{1}$, $\bf{u}_{2}$,…, $\bf{u}_{n}$,
respectively. And then, the DM detector is used to estimate each message bit
from the corresponding projection. Thus, in the same manner as (10), the
modulated vector $\bf{g}$ must be subject to the following equation,

$\begin{array}[]{l}\left\\{\begin{array}[]{l}{\mathop{\rm
proj}\nolimits}({\bf{g}},{\bf{u}}_{1})={\mathop{\rm
QDM}\nolimits}({\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}}_{1}),\Delta_{1},d_{1}^{m_{1}})\\\
{\mathop{\rm proj}\nolimits}({\bf{g}},{\bf{u}}_{2})={\mathop{\rm
QDM}\nolimits}({\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}}_{2}),\Delta_{2},d_{2}^{m_{2}})\\\
.........\;.........\\\ {\mathop{\rm
proj}\nolimits}({\bf{g}},{\bf{u}}_{n})={\mathop{\rm
QDM}\nolimits}({\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}}_{n}),\Delta_{n},d_{n}^{m_{n}})\\\
\end{array}\right.\\\ \\\ \end{array}$ (13)

where $d_{j}^{m_{j}}$ is the dither signal in the direction ${\bf{u}_{j}}$
corresponding to the message bit $m_{j}$.

By substituting (12) into (13), n equations can be obtained. These are
expressed as follows in the matrix form,

${\bf{U}}_{\bf{I}}{\bf{K}}={\bf{QDMV}}-{\bf{P}}$ (14)

where

$\begin{array}[]{l}\;\;\;\;\;\;\;\;\;\;\;{\bf{U}}_{\bf{I}}=\Lambda_{U}{\bf{U}^{T}}{\bf{U}},\;\Lambda_{U}=[\frac{1}{{\left\|{{\bf{u}}_{1}}\right\|}},\frac{1}{{\left\|{{\bf{u}}_{2}}\right\|}},...,\frac{1}{{\left\|{{\bf{u}}_{n}}\right\|}}]\\\
\;\;\;\;\;\;\;\;\;\;\;{\bf{P}}=[{\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}}_{1}),{\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}}_{2}),...,{\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}}_{n})]^{T}\\\
\;\;\;\;\;\;\;\;\;\;\;{\bf{QDMV}}=[QDMV_{1},QDMV_{2},...,QDMV_{n}]^{T}\\\
\;\;\;\;\;\;\;\;\;\;\;QDMV_{j}={\mathop{\rm QDM}\nolimits}({\mathop{\rm
proj}\nolimits}({\bf{x}},{\bf{u}}_{j}),\Delta_{j},d_{j}^{m_{j}})\\\
\end{array}$

From (14), the scaling factor sequence $\bf{K}$ can be calculated by

${\bf{K}}={\bf{U}}_{{}_{\bf{I}}}^{{}^{-1}}({\bf{QDMV}}-{\bf{P}})$ (15)

Finally, according to (12), the watermarked host vector $\bf{g}$ which carries
$n$ message bits can be generated. Note that, to make (15) tenable, the length
of the host vector $\bf{x}$, namely $L$, must be no less than the number of
embedded message bits, $n$, i.e., $L\geq n$, (see Appendix A).

In the detecting procedure, we can apply the STDM detector (8) to estimate
every single bit $\widetilde{m}_{j}$ from the projection of the received
vector ${\bf{\tilde{g}}}$ along the corresponding direction ${\bf{u}}_{j}$,
independently. This can be expressed as follows,

$\begin{array}[]{l}\widetilde{m}_{j}=\mathop{\arg\min}\limits_{m_{j}\in\\{0,1\\}}{\mathop{\rm
dist}\nolimits}({\mathop{\rm
proj}\nolimits}({\bf{\tilde{g}}},{\bf{u}}_{j}),{\mathop{\rm
QDM}\nolimits}({\mathop{\rm
proj}\nolimits}({\bf{\tilde{g}}},{\bf{u}}_{j}),\Delta_{j},d_{j}^{m_{j}}),\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;j=1,2,...,n\end{array}$
(16)

###  III-B Detailed Implementation

As illustrated in Fig.3 and Fig.4, the proposed scheme, STDM-MW, consists of
two parts, the embedder (Fig.3) and the detector (Fig.4). In this scheme, each
user is given three secret keys, $STEP\\_KEY$, $U\\_KEY$ and $Dither\\_KEY$,
to implement watermark embedding and detecting. It is assumed that there are
$n$ users and the watermark sequence of the $j^{th}$ user is $\bf{w}_{j}$,
${\bf{w}_{j}}=[w_{j1},w_{j2},...,w_{jN}]$, with length $N$.

Fig. 3: Block diagram of STDM-Multiple Watermarking embedder

Fig. 4: Block diagram of STDM-Multiple Watermarking detector for the $j^{th}$
user

The embedding procedure is as follows,

(a) Divide the image into disjoint $8\times 8$ blocks of pixels, and perform
DCT transform to each block to gain its DCT coefficients. A part of these
coefficients will be selected to form a single vector, denoted as the host
vector ${\bf{x}}_{i}(i=1,2,...,N)$, ${\bf{x}}_{i}=[x_{1},x_{2},...,x_{L}]$,
with length L. As illustrated in Fig.5, each host vector ${\bf{x}}_{i}$ is
used to embed one bit sequence $[w_{1i},w_{2i},...,w_{ni}]$, the $j^{th}$
element of which is corresponding to the $j^{th}$ user’s $i^{th}$ bit.

(b) Use the secret keys, $STEP\\_KEY$, $U\\_KEY$ and $Dither\\_KEY$, of each
user to generate the step sizes $\Delta_{ji}$, the random projective vectors
${\bf{u}}_{ji}$ and the dither factors $df_{ji}$ for each host vector
${\bf{x}}_{i}$, respectively. According to the message bit $w_{ji}$, the final
dither signal $d_{ji}^{w_{ji}}$ can be generated using $df_{ji}$.

(c) Embed each bit sequence $[w_{1i},w_{2i},...,w_{ni}]$ by modulating each
host vector ${\bf{x}}_{i}$ into ${\bf{g}}_{i}$ using the method mentioned in
III-A , based on the parameters,
$[{\bf{u}}_{1i},{\bf{u}}_{2i},...,{\bf{u}}_{ni}]$,
$[d_{1i}^{w_{1i}},d_{2i}^{w_{2i}},...,d_{ni}^{w_{ni}}]$,
$[\Delta_{1i},\Delta_{2i},...,\Delta_{ni}]$, calculated in step (b). Finally,
transform the modified coefficients back to form the watermarked image.

Fig. 5: Parameters arrangement, the arrangement for projective vector
${\bf{u}}$, dither factor $df$ and step size $\Delta$ is the same as it is for
watermark $w$.

During the transmission, the watermarked image may sustain certain attacks,
intentional or unintentional, and become a distorted image at the receiver.
Each user can use his own secret keys to detect his own watermark
independently.

The detecting procedure of the $j^{th}$ user is as follows

(a) Form each host vector ${\bf{\tilde{g}}}_{i}$ of the received image in the
same manner as step (a) in the embedding procedure.

(b) use the secret keys, $STEP\\_KEY_{j}$, $U\\_KEY_{j}$ and
$Dither\\_KEY_{j}$, of the $j^{th}$ user to generate the step sizes
$[\Delta_{j1},\Delta_{j2},...,\Delta_{jN}]$, the random projective vectors
$[{\bf{u}}_{j1},{\bf{u}}_{j2},...,{\bf{u}}_{jN}]$ and the dither factors
$[df_{j1},df_{j2},...,df_{jN}]$, respectively.

(c) Use the STDM detector to detect every bit $\tilde{w}_{ji}$ from each host
vector ${\bf{\tilde{x}}}_{i}$, based on the parameters, ${\bf{u}}_{ji}$,
$df_{ji}$ and $\Delta_{ji}$.

Note that, with an eye to the robustness of STDM-MW against valumetric
scaling, the step-size $\Delta$ should be multiplied by the mean intensity of
the whole image.

##  IV Analysis of STDM-Multiple Watermarking

Through experiment, it is found that along with the increase of the number of
watermarks embedded, the quality of the images declines in vary degrees. To
address this issue, further analysis of the embedding strategy of STDM-
Multiple Watermarking is demanded.

As is widely known, in the case of Imperceptible $\&$ Robust watermarking,
owning the same robustness, the more imperceptible, the more effective the
algorithm is. In most cases, the imperceptibility of the watermark, in other
words the fidelity of the watermarked image, is measured in PSNR, which varies
inversely with the mean squared error, MSE. Referencing Appendix B, we have

$MSE\propto\left\|{\bf{C^{\prime}}-\bf{C}}\right\|_{2}$ (17)

where $\bf{C}$ and $\bf{C}^{\prime}$ are the DCT coefficient vectors of the
original image and the watermarked one.

Thus, under the PSNR measurement, the smaller the Euclidian distance between
the watermarked coefficient and the original one is, the higher the fidelity
of the watermarked image will be. According to this idea, to improve the
fidelity of the watermarked image, we need to produce the watermarked vector
that is closest to the host vector.

At the very beginning, as the embedding procedure of STDM-Multiple
Watermarking is based on Dither Modulation, it is appropriate to investigate
the DM quantizer in a deeper way.

###  IV-A Dither Modulation Based Single Watermarking

From section II-B, to embed one message bit $m$, the original DM quantizer,
QDM, quantizes the point $x$ to ($\Delta
round(\frac{{x+d^{m}}}{\Delta})-d^{m}$). However, ignoring the imperceptible
constraint (minimum Euclidian distance), we can quantize the point $x$ to any
point $b_{i}$, $b_{i}\in{\bf{B}}$.

${\bf{B}}=\\{b|b=\beta\Delta-d^{m},\;\beta\in Z\\}$ (18)

Definitely, any points in ${\bf{B}}$ have the same detection robustness
according to the DM detection mechanism, (5) and (6). In what follows, this
kind of points are defined as the DM quantization points of point $x$.

As illustrated in Fig.6, in the case of DM single watermarking, it is optimal
to use (3), which is equivalent to $\beta=round(\frac{{x+d^{m}}}{\Delta})$ in
(18), to choose the final quantization point, because the selected one is the
closest point to $x$ among all the DM quantization points of $x$,(i.e., points
in $B$).

Fig. 6: Utilizing DM to embed one message bit $m$ into point $x$, where the
set of circles represents quantization points in $B$, (assuming $d^{m}>0$).
Dotted-lines, $L=\\{l|l=((2\alpha+1)\frac{\Delta}{2}-d^{m},\;\alpha\in Z\\}$,
denote the median point between two adjacent quantization points.

Inspired by this idea, in the original STDM, as illustrated in Fig.7, we can
modulate the host vector $\bf{x}$ to any vector
(${\bf{g}}^{\prime\prime}$,${\bf{g}}^{\prime}$,${\bf{g}}$), whose projection
point is the DM quantization point of the host vector’s projection point $p$.

However, the imperceptible constraint must be considered. Referencing (9), the
Euclidian distance $dis\\_v$ between the watermarked vector $\bf{g}$ and the
host vector $\bf{x}$, is proportional to $k$, which is actually the distance
$dis\\_p$ between the host vector’s projection point $p$ and $p$’s DM
quantization point. This can be formulated as follows,

$dis\\_v=\left\|{{\bf{g}}-{\bf{x}}}\right\|_{2}=\left\|{{\bf{x}}+k{\bf{u}}-{\bf{x}}}\right\|_{2}=k\left\|{\bf{u}}\right\|_{2}=dis\\_p$
(19)

As DM quantizer (3) can generate the quantization point that is closest to the
original point, it can find the closest DM quantization point to the host
vector’s projection point, i.e., the DM quantizer can make $dis\\_p$ minimum.
Thus, it is optimal to use DM quantizer to modulate the host vector $\bf{x}$
to vector $\bf{g}$ by (7). In this way, the minimum $dis\\_v$ can be
guaranteed.

Fig. 7: Utilizing STDM to embed one message bit $m$ into one host vector
$\bf{x}$, where $\bf{u}$ is the projective vector and $\bf{g}$ is the
watermarked vector. The set of circles represents the DM quantization points
of the projection point $p$ of the host vector $\bf{x}$ along the direction
$\bf{u}$.

###  IV-B Embedding Strategy of STDM-Multiple Watermarking

As mentioned above, DM quantizer is optimal for STDM in the case of single
watermarking. Unfortunately, it seems that this strategy is not optimal in the
case of multiple watermarking.

As mentioned in III-A, in the case of multiple watermarking, if $n$ message
bits are embedded, the host vector $\bf{x}$ must be modulated along $n$ given
directions to form the watermarked vector $\bf{g}$. For each direction, the
projection of the watermarked vector $\bf{g}$ must be the closet DM
quantization point to the host vector $\bf{x}$’s projection point.

As illustrated in Fig.8, it is a simple example for two users, that is
embedding two bits into the host vector $\bf{x}$. To do this, host vector
$\bf{x}$ must be projected along the projective vectors $\bf{u}_{1}$ and
$\bf{u}_{2}$ to gain the projection points $p_{1}$ and $p_{2}$, respectively.
And then, points $p_{1}$ and $p_{2}$ are quantized into their closet DM
quantization points, $Q_{1}$ and $Q_{2}$, respectively. Finally, host vector
$\bf{x}$ is modulated into vector $\bf{G}_{1}$.

Fig. 8: Utilizing the original embedding strategy STDM-MW to embed two message
bits into one host vector $\bf{x}$, where $\bf{u}_{1}$ and $\bf{u}_{2}$ are
the two projective vectors denoting the quantization directions. $p_{1}$ and
$p_{2}$ are the projection points of $\bf{x}$ along $\bf{u}_{1}$ and
$\bf{u}_{2}$, respectively. The circles along $\bf{u}_{1}$ and $\bf{u}_{2}$
denote the DM quantization points, belonging to the point set ${\bf{B}}_{1}$
and ${\bf{B}}_{2}$,respectively.
${\bf{B}}_{j}=\\{b|b=\beta_{j}\Delta_{j}-d_{j}^{m_{j}},\;\beta_{j}\in Z\\}$.

However, this original embedding strategy, using the closest DM quantization
point as the final quantization point of the projection point, can not product
the closet watermarked vector to the host vector. Actually, vectors
$\bf{G}_{1}$, $\bf{G}_{2}$, $\bf{G}_{3}$ and $\bf{G}_{4}$ can all be selected
as the watermarked vector of the host vector $\bf{x}$ while owning the same
detection robustness. And, as shown in Fig.8, vector $\bf{G}_{1}$, the
original selected one, dose not have the minimum Euclidian distance to the
host vector $\bf{x}$ among the four alternative ones. In practice, vector
$\bf{G}_{2}$ is the closest one.

Thus, it is not optimal to use vector $\bf{G}_{1}$ to play as the watermarked
vector. More specifically, once the host vector $\bf{x}$ belongs to the
shadowed area in the parallelogram in Fig.8, it is not optimal to use the
original embedding strategy to select the quantization point along each
direction and generate the watermarked vector.

The original multiple watermarks embedding strategy (13) and (15) must be
rewritten as

$\left\\{\begin{array}[]{l}{\mathop{\rm
proj}\nolimits}({\bf{g}},{\bf{u}}_{1})=Qp_{1}\\\ {\mathop{\rm
proj}\nolimits}({\bf{g}},{\bf{u}}_{2})=Qp_{2}\\\ ...........\;..........\\\
{\mathop{\rm proj}\nolimits}({\bf{g}},{\bf{u}}_{n})=Qp_{n}\\\
\end{array}\right.$ (20)

${\bf{K}}={\bf{U}}_{{}_{\bf{I}}}^{{}^{-1}}({\bf{Qp}}-{\bf{P}})$ (21)

where $Qp_{j}$ denotes one DM quantization point in the j-th direction,

$\begin{array}[]{l}\;\;\;\;\;\;\;\;\;\;\;{\bf{Qp}}=[Qp_{1},Qp_{2},...,Qp_{n}]^{T},\\\
\;\;\;\;\;\;\;\;\;\;\;Qp_{j}\in{\bf{B}}_{j},{\bf{B}}_{j}=\\{b|b=\beta_{j}\Delta_{j}-d_{j}^{m_{j}},\beta_{j}\in{\rm
Z}\\}\\\ \end{array}$

Substituting (21) into (12), the watermarked vector can be given by

$\;{\bf{g}}={\bf{x}}+{\bf{U}}{\bf{U}}_{{}_{\bf{I}}}^{{}^{-1}}({\bf{Qp}}-{\bf{P}})$
(22)

As there are many DM quantization points in each direction, there are several
combinations to make $\bf{Qp}$. This will form a vector pool for $\bf{Qp}$,
namely $\bf{Qp\\_S}$. Vectors in $\bf{Qp\\_S}$ can all be chosen as $\bf{Qp}$
in (22), and correspondingly, a vector pool for the watermarked vector
${\bf{g}}$ is generated, namely g_S. The goal of our optimization procedure is
to find the closest one to the host vector ${\bf{x}}$ from this vector pool
$\bf{g\\_S}$, and finally use this vector to play as the optimized watermarked
vector.

##  V Optimization for STDM-Multiple Watermarking

As mentioned above, obviously, if all the candidate vectors in the pool
$\bf{g\\_S}$ are traversed, the one which is closest to the host vector will
be found ultimately. However, as the infinite size of $\bf{g\\_S}$, this
procedure is not practical. To address this issue, the optimization procedure
is divided into two cases, the special case and the general case.

###  V-A Special Case: Multiple Watermarking using Orthogonal Projective
Vectors

It has been observed that the goal of our optimization procedure is to find
the closet watermarked vector to the host vector, i.e., the Euclidian distance
between them is minimum. According to (22), the Euclidian distance, $dis\\_v$,
can be expressed as follows,

$\begin{array}[]{l}dis\\_v=\left\|{{\bf{g}}-{\bf{x}}}\right\|_{2}=\sqrt{({\bf{Qp}}-{\bf{P}})^{T}{\bf{U}}_{e}({\bf{Qp}}-{\bf{P}})}\end{array}$
(23)

where
${\bf{U}}_{e}=\Lambda_{U}^{-1}({\bf{U}}^{T}{\bf{U}})^{-1}\Lambda_{U}^{-1}$.

If the projective vectors $\bf{u_{1}}$,$\bf{u_{2}}$,…,$\bf{u_{n}}$ are
preprocessed by Gram-Schmidt orthogonalization, the matrix ${\bf{U}}_{e}$ will
be Identity matrix ${\bf{I}}_{n}$, and $dis\\_v$ is actually the Euclidian
distance between the vector of DM quantization points, $\bf{Qp}$, and the
vector of projection points, $\bf{P}$.

$dis\\_v=\left\|{{\bf{Qp}}-{\bf{P}}}\right\|_{2}=\sqrt{\sum\limits_{j}{({\bf{Qp}}(j)-{\bf{P}}(j))^{2}}}$
(24)

As QDM quantizer (3) can minimize each item in (24), the original embedding
strategy, using the closest DM quantization point as the final quantization
point of the projection point, is optimal in the case of multiple watermarking
using orthogonal projective vectors. Note that, in the following description,
this special case will be referred as STDM-MW-Uorth.

The simple example for this case is illustrated in Fig.9, if the host vector
$\bf{x}$ belongs to the rectangle area centered by ${\bf{G}}_{i}$ with width
$\Delta_{1}$ and height $\Delta_{2}$, it will be modulated to the vector
${\bf{G}}_{i}$. Obviously, ${\bf{G}}_{i}$ is the optimal watermarked vector
for ${\bf{x}}$.

Fig. 9: Embedding two message bits into one host vector $\bf{x}$ in the case
of $\bf{u_{1}}$ and $\bf{u_{2}}$ are orthogonal projective vectors, and
${\bf{G}}_{5}$ is the optimal watermarked vector for ${\bf{x}}$.

###  V-B General Case: Multiple Watermarking using Unorthogonal Projective
Vectors

In general, it is not realistic to expect the projective vectors
$\bf{u_{1}}$,$\bf{u_{2}}$,…,$\bf{u_{n}}$ are orthogonal with each other. Thus,
taking a tradeoff between PSNR and time efficiency, we propose two methods for
the general case to find the optimized watermarked vector which is much closer
to the host vector, namely STDM-MW-Poptim and STDM-MW-Qoptim.

####  V-B1 STDM-MW-Poptim

In STDM-MW-Poptim, along each direction, $t$ quantization points, which are
near the projection point of the host vector, are selected to form the point-
set for this direction. This can be expressed as follows

${\bf{H}}_{j}=\\{h|h=\Delta_{j}(floor(\frac{x}{{\Delta_{j}}})+k)-d_{j}^{m_{j}},\;\;k\in{\rm
Z}\\}$ (25)

where ${\bf{H}}_{j}$ denotes the point-set of the j-th direction.

And then, one point of each point-set is selected to form a vector
$\bf{PoQp}$. It can be used to substitute the vector $\bf{Qp}$ in (22), and
the watermarked vector can be calculated by

${\bf{g}}_{i}={\bf{x}}+{\bf{UU}}_{\bf{I}}^{-1}({\bf{PoQp}}_{i}-{\bf{P}}),\;\;i=1,2,...,F$
(26)

where, assuming there are $n$ bits to be embedded in one host vector, in other
words $n$ quantization directions are given for one host vector, thus there
are $F=t^{n}$ ways to choose one element from $n$ point-sets (of length $t$)
to form the vector $\bf{PoQp}$. And correspondingly, $F$ watermarked vectors
$\bf{g}$ are produced.

The final optimized watermarked vector ${\bf{g}}_{optim}$ is then given by
judging which of these watermarked vectors produced in (26) has the minimum
Euclidean distance to the host vector $\bf{x}$.

${\bf{g}}_{optim}=\mathop{\arg\min}\limits_{{\bf{g}}_{i},i\in\\{1,2,...,F\\}}dist({\bf{x}},{\bf{g}}_{i})$
(27)

More specifically, Fig.10 gives an optimization example for STDM-MW-Poptim,
which is the simple case of embedding two bits into one host vector. Three
quantization points are selected in each directions, thus $3^{2}$ watermarked
vectors ($G_{1}$,$G_{2}$,…,$G_{9}$) can be generated. The final optimized
watermarked vector is $G_{2}$, the one that is closest to the host vector
$\bf{x}$ among the nine candidate vectors.

Fig. 10: Utilizing STDM-MW-Poptim to embed two message bits into one host
vector $\bf{x}$, where $\bf{u}_{1}$ and $\bf{u}_{2}$ are the two projective
vectors denoting the quantization directions. $Q_{1}$, $Q_{2}$ and $Q_{3}$ are
the selected quantization points, corresponding to the search area $k=-1,0,1$
in (25). These points form ${\bf{H}}_{1}$, the point-set of direction
$\bf{u}_{1}$. $Q_{4}$, $Q_{5}$, $Q_{6}$ are the same ones.

####  V-B2 STDM-MW-Qoptim

It has been observed that the goal of our optimization procedure is to find
the optimal DM quantization point along each direction which makes the
Euclidian distance between the optimized watermarked vector and the host
vector is minimum. According to (23), the Euclidian distance, $dis\\_v$, can
be expressed as follows,

$dis\\_v=\sqrt{{\bf{A}}^{T}{\bf{U}}_{e}{\bf{A}}}$ (28)

where ${\bf{A}}=({\bf{Qp}}-{\bf{P}})$.

Thus, the optimization procedure can be formulated as a constrained quadratic
minimization problem that minimizes

$Y={\bf{A}}^{T}{\bf{U}}_{e}{\bf{A}}$ (29)

subject to the constraint in the form of

${\bf{A}}+{\bf{P}}\in{\bf{Qp\\_S}}$ (30)

To do the optimization, a part of elements in $\bf{Qp}$ are selected as the
fixed elements, each of which is generated from quantizing the projection
point using (3), that is, the closest DM quantization point to the projection
point. The other elements in $\bf{Qp}$ will be optimized to minimize $Y$ in
(29).

Assuming the elements to be optimized in $\bf{Qp}$ are
$Qp(o_{1})$,$Qp(o_{2})$,…,$Qp(o_{t})$ and the elements to be fixed are
$Qp(f_{1})$,$Qp(f_{2})$,…,$Qp(f_{r})$, thus, in (29), the corresponding
elements to be optimized and fixed in $\bf{A}$, ${\bf{A}}={\bf{Qp}}-{\bf{P}}$,
will be $A(o_{1})$,$A(o_{2})$,…,$A(o_{t})$ and
$A(f_{1})$,$A(f_{2})$,…,$A(f_{r})$. By differentiating $Y$ with respect to
each element to be optimized, and setting the derivatives to be zero, $t$
equations will be generated

$\frac{{\partial Y}}{{\partial A(o_{i})}}=0,\;i=1,2,...,t$ (31)

$\Rightarrow\;\sum\limits_{j=1}^{t}{{\bf{U}}_{eo_{i}o_{j}}A(o_{j})}=\sum\limits_{k=1}^{r}{{\bf{U}}_{eo_{i}f_{k}}A(f_{k})},\;i=1,2,...t$
(32)

Solving (32), $t$ optimized elements in $A$ are produced, consequently, the
optimized elements in $\bf{Qp}$ can be generated,
$Qp(o_{i})=A(o_{i})+P(o_{i})$. Unfortunately, each $Qp(o_{i})$ may not subject
to the constraint (30), in other words, $Qp(o_{i})$ dose not belong to the set
of quantization points of the $o_{i}$-th direction, set ${\bf{B}}_{o_{i}}$,
$\\{b|b=\beta_{o_{i}}\Delta_{o_{i}}-d_{o_{i}}^{m_{0_{i}}},\;\beta_{o_{i}}\in
Z\\}$. To satisfy this constraint, the final optimized $Qp(o_{i})$ can be
given by

$Qp(o_{i})=\mathop{\arg\min}\limits_{b_{j},b_{j}\in{\bf{B}}_{o_{i}}}dist(Qp(o_{i}),b_{j})$
(33)

Finally, vector $\bf{QoQp}$ is generated by assembling $Qp(o_{i})$ and
$Qp(o_{f})$, and it can be used to substitute the vector $\bf{Qp}$ in (22).
The watermarked vector can be calculated by

${\bf{g}}_{i}={\bf{x}}+{\bf{UU}}_{\bf{I}}^{-1}({\bf{QoQp}}_{i}-{\bf{P}}),\;\;i=1,2,...,F$
(34)

where, assuming there are $n$ bits to be embedded in one host vector, in other
words, there are $n$ given quantization directions for one host vector. Thus,
there are $F=\left(\begin{array}[]{l}r\\\ n\\\ \end{array}\right)$ ways to
choose $r$ elements from $\bf{Qp}$ (of length $n$) to play as the fixed
elements. $F$ vectors $\bf{QoQp}$ are generated, and correspondingly, $F$
watermarked vectors $\bf{g}$ are produced.

The final optimized watermarked vector ${\bf{g}}_{optim}$ is then given by
judging which of these watermarked vectors produced in (34) has the minimum
Euclidean distance to the host vector $\bf{x}$.

${\bf{g}}_{optim}=\mathop{\arg\min}\limits_{{\bf{g}}_{i},i\in\\{1,2,...,F\\}}dist({\bf{x}},{\bf{g}}_{i})$
(35)

More specifically, Fig.11 gives an optimization example for STDM-MW-Qoptim,
which is the simple case of embedding two bits into one host vector. Thus,
there are two elements in $\bf{Qp}$, $Qp(1)$ and $Qp(2)$, corresponding to the
projection directions $\bf{u_{1}}$ and $\bf{u_{2}}$. If $Qp(1)$ is fixed, then
$Qp(1)$ is equal to $Q_{2}$. Through (31), actually Path 1 in Fig.11, the
optimized point of $Qp(2)$ is $O_{2}$. Finally, according to (33), $O_{2}$ is
quantized to $Q_{4}$, and the corresponding watermarked vector is $G_{1}$.
Correspondingly, if $Qp(2)$ is fixed, Path 2 is used to optimize $Qp(1)$, and
$G_{2}$ is the corresponding watermarked vector. Comparing $G_{1}$ with
$G_{2}$, the final optimal watermarked vector is $G_{2}$, the one that is
closer to the host vector $\bf{x}$.

Fig. 11: Utilizing STDM-MW-Qoptim to embed two message bits into one host
vector $\bf{x}$.

##  VI Experimental Results and Analysis

To evaluate the performance of our proposed method, experiments are performed
on standard images with size $256\times 256$ as shown in Fig.12. And all the
experiment data illustrated in the following section are the averaged ones.

Fig. 12: Test images

More specifically, for all the proposed algorithms, to be analyzed in the
experiments, the $2^{nd}-8^{th}$ DCT coefficients, in zig-zag-scaned order, of
each $8\times 8$ block are used to form each host vector which is used to
embed several message bits in it. The projective vectors and quantization
steps are generated from the Gaussian distribution $\mathcal{N}(0,16)$ and
$\mathcal{N}(f_{g},4)$, respectively. $f_{g}$ is adjusted to ensure a given
image fidelity.

###  VI-A Experimental Test for the Efficiency of the Optimization Methods

As mentioned above, to optimize the proposed multiple watermarking algorithm,
two optimization methods, STDM-MW-Poptim and STDM-MW-Qoptim, are proposed to
realize image fidelity improvement. To test their performance, 5 watermarks,
with size $32\times 32$, are embedded into the standard image. Meanwhile, the
same quantization steps, dither signals and projective vectors are used for
the two methods to compare their performance in PSNR&CPU-time.

Fig. 13: PSNR Vs. CPU-time with different optimization parameters. The first
point denotes embedding without optimization, the rest points are
corresponding to the different search areas,
$k=(0,1),(0,1,2),(-1,0,1),(-1,0,1,2)$ in (25), for STDM-MW-Poptim and the
fixed numbers, $r=4,3,2,1$ in (32), for STDM-MW-Qoptim.

As illustrated in Fig.13, both of them have great performance in the
improvement of the fidelity of the watermarked image. The image fidelity is
promoted from 41dB to 44dB in PSNR, compared with the original embedding
strategy.

In STDM-MW-Poptim, along with the growth of the search area, it takes more
time to realize the optimization, whereas, gives less contribution to the
increase in PSNR. Taking a tradeoff between CPU-time and PSNR, $2^{nd}$ point,
search area $k=0,1$, is the optimal one for five users in STDM-MW-Poptim.

In STDM-MW-Qoptim, the CPU-time of $2^{nd}$&$5^{th}$ point and
$3^{rd}$&$4^{th}$ point are almost the same. This is mainly due to the fact
that the number of the watermarked vectors generated for one host vector, $F$
in (34), are the same, because $F=\left(\begin{array}[]{l}4\\\ 5\\\
\end{array}\right)=\left(\begin{array}[]{l}1\\\ 5\\\ \end{array}\right)$ for
$2^{nd}$&$5^{th}$ point, and $F=\left(\begin{array}[]{l}3\\\ 5\\\
\end{array}\right)=\left(\begin{array}[]{l}2\\\ 5\\\ \end{array}\right)$ for
$3^{rd}$&$4^{th}$ point. Taking a tradeoff between CPU-time and PSNR, $4^{th}$
point, fix number $r=2$, is the optimal one for five users in STDM-MW-Qoptim.

Comparing the two optimal points in the two methods, STDM-MW-Poptim has better
performance due to less CPU-time and higher PSNR.

Through experiments, for different numbers of users, it is found that $k=0,1$
and $r=floor(user\\_number/2)$ are the appropriate optimization parameters for
STDM-MW-Poptim and STDM-MW-Qoptim. And in what follows, these two parameters
are used to implement the optimization.

###  VI-B Experimental Test for the Proposed Methods in Robustness&PSNR

To test the impact of multiple watermarks embedding to the fidelity of the
image, different numbers of watermarks are embedded into the image using the
four proposed methods separately.

As illustrated in Fig.14, along with the increase of the number of watermarks
embedded, the quality of the images declines in vary degrees. STDM-MW-Uorth,
which uses Gram-Schmidt orthogonalization to preprocess the projective
vectors, has the superior image quality among these methods. This is mainly
due to STDM-MW-Uorth is optimal in the case of orthogonal projective vectors.
Unfortunately, in the general case that the projective vectors are not
orthogonal, STDM-MW-no-optim, the quality of the watermarked image declines
rapidly using the original embedding strategy without optimization. In
contrast, if optimization is applied, e.g., STDM-MW-Poptim, the situation will
be improved by a large scale, which is promoted by 1.03dB for 3 watermarks,
2.09dB for 4 watermarks, and 3.59dB for 5 watermarks.

Fig. 14: PSNR Vs. Number of watermarks

From another point of view, to evaluate the robustness of our proposed
multiple watermarking methods, the test images are embedded into 3 watermarks,
with size $32\times 32$, under the uniform fidelity, a fixed PSNR of 42 dB.
Meanwhile, four kinds of attacks, Gauss Noise, JPEG Compression, Salt&Pepper
Noise and Amplitude Scaling, are used to verify the performance of the
schemes.

As illustrated in Fig.15, we test four versions, STDM-MW-no-optim, STDM-MW-
Poptim, STDM-MW-Qoptim and STDM-MW-Uorth. And we use the average detection
score, measured in bit error rate (BER), to analyze the performance, and each
curve is the average BER of the three detected watermarks.

Fig. 15: BER vs. (a) Gaussian Noise, (b) JPEG, (c) Salt&Pepper Noise and (d)
Amplitude Scaling

As we expected, according to Fig.15.(d), all the proposed schemes do have good
performance in amplitude scaling. The rise of BER in scale $\beta\geq 1.2$ is
mainly due to the “cutoff distortion”, that is, some pixels of the image are
already quite huge and will be cut off to the maximum allowed value when there
is an scaling. In this case, the pixels will not scale linearly with the
scaling factor while the quantization step-sizes still scale linearly as
usual. Thus, experimental performance on bright images will have a worse
robustness in this scale.

With regard to other attacks, both STDM-MW-Poptim and STDM-MW-Qoptim have
better robustness against Gauss noise (Fig.15.(a)) and JPEG compression
(Fig.15.(b)) compared with STDM-MW-no-optim. This mainly due to the fact that
the optimization procedures can improve the fidelity of the watermarked image,
as shown in Fig.14, in other words, the embedding strength used in them could
be relatively increased while ensuring the given fidelity.

Although the STDM-MW-Uorth is the best performed one, it is not suitable for
the applications where independent detection is required, because all the
projective vectors of each users must be gained in the detector to perform
Gram-Schmidt orthogonalization before the detecting procedure. Thus,
referencing to section VI-A, STDM-MW-Poptim is the optimal one to play as the
multiple watermarks embedding strategy in the sense of higher robustness, less
CPU-time and for general applications.

Fig. 16: BER vs. (a) Gaussian Noise, (b) JPEG, (c) Salt&Pepper Noise and (d)
Amplitude Scaling

Fig. 17: Watermark show

###  VI-C Comparison with the Pioneering Multiple Watermarking Algorithms

To give an objective analysis of the performance of the proposed method, the
optimal one of our proposed schemes, STDM-MW-Poptim, is picked up to be
compared with the pioneering multiple watermarking algorithms, DA and IA-R in
[15]. Both of them can embed multiple watermarks into the same image area, and
each watermark can be detected independently, like ours. To correspond with
the original paper, the parameters used for them are identical, the keys K is
generated from Gaussian distribution $\mathcal{N}(0,16)$ and the first 10% of
the DCT AC coefficients are used to form the host vector, meanwhile, 3
watermarks are embedded into the standard images, the same as ours. Note that,
the mean of the keys D is modified to meet the uniform image fidelity, 42dB in
PSNR. The BER curves are illustrated in Fig.16, meanwhile, to show the
subjective visual effect, the detected watermarks corresponding to different
conditions are given in Fig.17.

As illustrated in Fig.16.(d), because DA and IA-R do not take the amplitude
scaling attack into account, they cannot resist the image process which scales
the amplitude of the pixels. In contrast, STDM-MW-Poptim has great advantage
in this field,

In robustness to random noise and JPEG Compression, Fig.16.(a)(b)(c), our
proposed scheme outperforms others significantly, especially in Salt&Pepper
Noise attack, the performance is almost improved by 70%. Such superior
performance is attributed to the exploitation of the great robustness of the
original STDM in single watermarking. In addition, the optimization strategy
can provide a significant improvement in image fidelity, in other words, the
embedding strength used in our scheme could be relatively increased while
ensuring the given fidelity.

##  VII Application Discussion and Extension

As mentioned above, the proposed multiple watermarking algorithm has the
feature that it can embed multiple watermarks into the same area and the same
transform domain of one image, meanwhile, the embedded watermarks can be
extracted independently and blindly in the detector without any interference.
To this end, it may own some potential interesting applications.

###  VII-A Coauthor Copyright Certification

In the field of copyright management, one common scenario is that a number of
authors who have co-designed an image need separate certification for each of
them. This can be fulfilled by the proposed algorithm, STDM-MW-Poptim, in
which the embedded watermarks (certifications for each author) can be
extracted independently and blindly in the detector. Every author can use
his/her own key set, $STEP\\_KEY$, $U\\_KEY$ and $Dither\\_KEY$, to extract
his/her own watermark, by which the copyright of each author can be
certificated independently.

###  VII-B Secret Related Area

A more interesting feature of STDM-MW-Poptim is that the detecting procedure
of each watermark is independent with each other. More importantly, the
receiver even dose not know how many watermarks are exactly embedded, i.e.,
one receiver cannot perceive the exist of other hidden information without the
notification from the embedder. This is due to the fact that in terms of each
receiver, the detecting procedure is exactly the same as STDM, which is deemed
as a single watermarking algorithm. This interesting feature would cause the
gloss to the receiver that the watermark he/she has extracted is the only
information hidden in the image, and this gloss may provide a key cover for
the protection of the true secret information.

###  VII-C Image History Management

In some applications such as medical image management, it is desirable to
acquire the history of a medical image from the patient through the various
laboratories and physicians, e.g., directly detecting from the image who is
the creator, who has access to the data after its creation. This can be
realized by sequentially embedding each user’s digital signature into the
image during each stage of its circulation.

Inspired by [19], we can utilize the special case of our proposed algorithm,
multiple watermarking using orthogonal projective vectors, STDM-MW-Uorth,
combined with STDM-MW-Poptim to fulfill this application.

As illustrated in Fig.18, if Q additional watermarks are desired to be
embedded into the watermarked image with P watermarks embedded, we must
guarantee that these additional watermarks must not interfere with the former
embedded watermarks. To realize this, we apply the idea of STDM-MW-Uorth,
using projective vectors that are orthogonal to the ones of the former
embedded watermarks.

Fig. 18: Sequential Multiple Watermarks Embedding

To embed Q additional watermarks simultaneously for the coming Q users, the
watermarked image with P watermarks embedded as well as a public key set (the
former users’ $U\\_KEY$) are needed. Then, the projective vector
${\bf{u}}_{i}$ produced by each new user will be preprocessed by Gram-Schmidt
orthogonalization.

${\bf{u}}^{orth}_{i}={\bf{u}}_{i}-\sum\limits_{j=1}^{P}{proj({\bf{u}}_{i},{\bf{k}}_{j})\cdot\frac{{{\bf{k}}_{j}}}{{\left\|{{\bf{k}}_{j}}\right\|_{2}}}\;\;,i=1,2,...,Q}$
(36)

Finally, based on these preprocessed projective vectors,
${\bf{u}}^{orth}_{1}$,${\bf{u}}^{orth}_{2}$,…,${\bf{u}}^{orth}_{Q}$, Q
additional watermarks can be simultaneously embedded into the watermarked
image using STDM-MW-Poptim without any interference.

One step further, if all the watermarks are desired to be embedded into the
image one by one, this case is equivalent to STDM-MW-Uorth.

In this way, we can embed multiple watermarks into the image sequentially to
realize image history management. Compared with [4], which is based on [20,
21], an additional management for the public key set is needed in our scheme.
Nevertheless, to detect the watermark, [4] must acquire the knowledge of the
content of the original embedded watermark to implement correlation detection
and can only judge whether there exists the given watermark. This feature may
somehow constrain its application area.

##  VIII Conclusions

In this paper, a novel multiple watermarking algorithm is presented which
initially extend the STDM, a single watermarking algorithm, to the field of
multiple watermarking application. It can embed multiple watermarks into the
same area and the same transform domain of one image; meanwhile, the embedded
watermarks can be extracted independently and blindly in the detector without
any interference. Moreover, through investigating the properties of the DM
quantizer and the proposed multiple watermarks embedding strategy, two
optimization methods are presented to improve the fidelity of the watermarked
image. Experimental results indicate that the optimization procedure can
significantly improve the quality of the watermarked image, meanwhile, the
more watermarks embedded the more quality improvements can be gained. Finally,
to enhance the application flexibility, an application extension of our
algorithm is proposed, which can sequentially embed multiple watermarks into
the image during each stage of its circulation, thereby realizing image
history management. In general, compared with the pioneering multiple
watermarking algorithms, the proposed scheme owns more flexibility in
practical application and is more robust against distortion due to basic
operations such as random noise, JPEG compression and valumetric scaling.

## Appendix A

Referencing (15), to make it tenable, the matrix ${\bf{U}}_{{}_{\bf{I}}}$ must
be reversible. As ${\bf{U}}_{{}_{\bf{I}}}$ is an n-by-n matrix, thus

$rank({\bf{U}}_{{}_{\bf{I}}})=n$

Referencing (14), ${\bf{U}}_{\bf{I}}=\Lambda_{U}{\bf{U}^{T}}{\bf{U}}$, thus

$rank({\bf{U}}_{\bf{I}})\leq\min\\{rank({\bf{U}}),rank\\{{\bf{U^{\prime}}}\\}\\}$

Consequently, we have $rank({\bf{U}})\geq n$, and reference (12), ${\bf{U}}$
is an L-by-n matrix, thus

$\left\\{\begin{array}[]{l}rank({\bf{U}})=n\\\ L\geq n\\\ \end{array}\right.$

where L denotes the length of the host vector ${\bf{x}}$.

## Appendix B

Consider $X$ and $X^{\prime}$ represent the original image and the watermarked
one in the space domain. And referencing the DCT transformation, we have

$Y=AXA^{\rm T},\;\;Y^{\prime}=AX^{\prime}A^{\rm T}$

where $Y$ and $Y^{\prime}$ are the coefficients in DCT domain.

Then, the MSE between the original image and the watermarked image can be
written by

$\begin{array}[]{l}MSE=\frac{1}{{mn}}\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{n}{[X(i,j)-X^{\prime}(i,j)]^{2}}}\\\
\;\;\;\;\;\;\;\;\;\;=\frac{1}{{mn}}\left\|{X-X^{\prime}}\right\|_{F}^{2}\\\
\;\;\;\;\;\;\;\;\;\;=\frac{1}{{mn}}\left\|{A^{\rm T}YA-A^{\rm
T}Y^{\prime}A}\right\|_{F}^{2}\\\
\;\;\;\;\;\;\;\;\;\;=\frac{1}{{mn}}\left\|{A^{\rm
T}(Y-Y^{\prime})A}\right\|_{F}^{2}\\\ \end{array}$

where $\left\|Q\right\|_{F}$ denotes the Frobenius norm of the matrix $Q$, in
view of
$\left\|Q\right\|_{F}\buildrel\Delta\over{=}(\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{n}{(Q(i,j))^{2})^{1/2}}}=(tr(Q^{T}Q))^{1/2}$,

$MSE=\frac{1}{{mn}}\times tr((A^{\rm T}(Y-Y^{\prime})A)^{T}(A^{\rm
T}(Y-Y^{\prime})A))\\\ $

Considering $A^{T}=A^{-1}$ in the DCT transformation, thus

$\begin{array}[]{l}MSE=\frac{1}{{mn}}\times tr(A^{\rm
T}(Y-Y^{\prime})^{T}(Y-Y^{\prime})A)\\\
\;\;\;\;\;\;\;\;\;\;=\frac{1}{{mn}}\times
tr((Y-Y^{\prime})^{T}(Y-Y^{\prime}))\\\
\;\;\;\;\;\;\;\;\;\;=\frac{1}{{mn}}\left\|{Y-Y^{\prime}}\right\|_{F}^{2}\end{array}$

When $Y$ and $Y^{\prime}$ are grouped into 1-dimension vectors, we have

$MSE=\frac{1}{{N}}\left\|{C-C^{\prime}}\right\|_{2}^{2}$

where $N=mn$, denotes the total number of the elements in the vector.

## References

  * [1] I. J. Cox, J. Kilian, T. Leighton, and T. Shamoon, “Secure spread spectrum watermarking for multimedia,” _IEEE Trans. Image Process._ , vol. 6, no. 12, pp. 1673–1687, Dec. 1997.
  * [2] F. Mintzer and G. W. Braudaway, “If one watermark is good, are more better?” _Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing._ , vol. 4, pp. 2067–2069, 1999.
  * [3] H. T. Sencar and N. Memon, “Combatting ambiguity attacks via selective detection of embedded watermarks,” _IEEE Trans. Information Forensics and Security._ , vol. 2, no. 4, pp. 664–682, 2007.
  * [4] G. Boato, F. G. B. D. Natale, and C. Fontanari, “Digital image tracing by sequential multiple watermarking,” _IEEE Trans. Multimedia._ , vol. 9, no. 4, pp. 677–686, 2007.
  * [5] A. Giakoumaki, S. Pavlopoulos, and D. Koutsouris, “Multiple image watermaking applied to health information management,” _IEEE Trans. Inf. Technol. Biomed._ , vol. 10, no. 4, pp. 722–732, Oct. 2006.
  * [6] N. P. Sheppard, R. Safavi-Naini, and P. Ogunbona, “On multiple watermarking,” in _Proceedings of the 2001 ACM workshop on Multimedia and security: new challenges_ , 2001, pp. 3–6.
  * [7] S. Stankovic, I. Djurovic, and I. Pitas, “Watermarking in the space/spatial-frequency domain using two-dimensional radon-wigner distribution,” _IEEE Trans. Image Process._ , vol. 10, no. 4, pp. 650–658, 2001.
  * [8] C.-T. Hsu and J.-L. Wu, “Hidden digital watermarks in images,” _IEEE Trans. Image Processing._ , vol. 8, no. 1, pp. 58–68, 1999.
  * [9] F. Zou, Z. Lu, and H. Ling, “A multiple watermarking algorithm based on cdma technique,” _Proc. 12th Ann. Int. Conf. ACM on Multimedia_ , pp. 424–427, 2004.
  * [10] D. Peng, J. Wang, S. Yang, S. Wang, and A. Liu, “Cdma based multiple-user digital watermarking,” _Proc. IEEE Int. Conf. IIH-MSP ’06_ , pp. 75–78, 2006\.
  * [11] J. Xiao and Y. Wang, “Multiple watermarking with side information,” in _Digital Watermarking_ , ser. Lecture Notes in Computer Science, 2009, vol. 5450, pp. 379–387.
  * [12] R. Scealy, R. Safavi-Naini, and N. Sheppard, “Performance measurement of watermark embedding patterns,” in _Digital Watermarking_ , ser. Lecture Notes in Computer Science, 2004, vol. 2939, pp. 265–266.
  * [13] A. Takahashi, R. Nishimura, and Y. Suzuki, “Multiple watermarks for stereo audio signals using phase-modulation techniques,” _IEEE Trans. Signal Processing._ , vol. 53, no. 2, pp. 806–815, 2005.
  * [14] S. Behnia, M. Teshnehlab, and P. Ayubi, “Multiple-watermarking scheme based on improved chaotic maps,” _Communications in Nonlinear Science and Numerical Simulation_ , vol. 15, no. 9, pp. 2469–2478, 2010.
  * [15] P. H. W. Wong, O. C. Au, and Y. M. Yeung, “A novel blind multiple watermarking technique for images,” _IEEE Trans. Circuits Syst. Video Technol._ , vol. 13, no. 8, pp. 813–830, 2003.
  * [16] B. Chen and G. Wornell, “Quantization index modulation: a class of provably good methods for digital watermarking and information embedding,” _IEEE Trans.Inf.Theory._ , vol. 47, no. 4, pp. 1423–1443, 2001.
  * [17] Q. Li and I. J. Cox, “Using perceptual models to improve fidelity and provide resistance to valumetric scaling for quantization index modulation watermarking,” _IEEE Trans.Inf.Forensics and Security._ , vol. 2, no. 2, pp. 127–139, 2007.
  * [18] P. Moulin and R. Koetter, “Data-hiding codes,” _IEEE Proceeding_ , vol. 93, no. 12, pp. 2083–2126, 2005.
  * [19] P. H. W. Wong, A. Chang, and O. C. Au, “A sequential multiple watermarks embedding technique,” _Proc. IEEE Int. Conf. ICASSP ’04_ , vol. 3, pp. 393–396, 2004.
  * [20] G. Boato, F. G. B. D. Natale, and C. Fontanari, “An improved asymmetric watermarking scheme suitable for copy protection,” _IEEE Trans. Signal Process._ , vol. 54, pp. 2833–2834, 2006.
  * [21] J. Tzeng, W.-L. Hwang, and I.-L. Chern, “An asymmetric subspace watermarking method for copyright protection,” _IEEE Trans. Signal Process._ , vol. 53, no. 2, pp. 784–792, 2005.