# A New Scalar Quantization Method for Digital Image Watermarking

Authors: Yevhen Zolotavkin; Martti Juhola
Journal: Journal of Electrical and Computer Engineering
 (2016)

---

## Abstract

A new technique utilizing Scalar Quantization is designed in this paper in order to be used for Digital Image Watermarking (DIW). Efficiency of the technique is measured in terms of distortions of the original image and robustness under different kinds of attacks, with particular focus on Additive White Gaussian Noise (AWGN) and Gain Attack (GA). The proposed technique performance is affirmed by comparing with state-of-the-art methods including Quantization Index Modulation (QIM), Distortion Compensated QIM (DC-QIM), and Rational Dither Modulation (RDM). Considerable improvements demonstrated by the method are due to a new form of distribution of quantized samples and a procedure that recovers a watermark after GA. In contrast to other known quantization methods, the detailed method here stipulates asymmetric distribution of quantized samples. This creates a distinctive feature and is expressed numerically by one of the proposed criteria. In addition, several realizations of quantization are considered and explained using a concept of Initial Data Loss (IDL) which helps to reduce watermarking distortions. The procedure for GA recovery exploits one of the two criteria of asymmetry. The accomplishments of the procedure are due to its simplicity, computational lightness, and sufficient precision of estimation of unknown gain factor.


---

## Body

## 1. Introduction

In modern communications, multimedia plays significant role. Ownership of multimedia data is important and needs to be protected [1]. As a part of nowadays popular multimedia content, digital images are an important class. A protection of digital rights of an owner is implemented by Digital Image Watermarking (DIW). A watermark that is inserted into an image has to be robust [2] as well as invisible [3].Among the popular and efficient techniques in DIW, Quantization Index Modulation (QIM) is widely used in blind watermarking where neither original media nor watermark is known to the receiver [4, 5]. One of the aspects of robustness of QIM is evaluated by attacking a watermarked image with Additive White Gaussian Noise (AWGN). Unfortunately, all the known on practice implementations of QIM are far from achieving the channel capacity limit that was first derived in [6].Several different QIM-related approaches are known. Some state-of-the-art realizations will be outlined briefly. According to QIM, intervals of equal lengthΔ are mapped on the real number line. The oldest known approach is to replace all the original coefficients inside every interval with one of the two endpoints of that interval. The selection of the endpoint depends on a bit of a watermark [7]. The main disadvantage is that for high intensity of noise and the capacity of the oldest QIM is much lower than the theoretical limit. In a more advanced realization of DC-QIM, coefficients from every original interval are mapped into two disjoint subintervals. The gap between the subintervals is controlled by parameter α, 0
≤
α
≤
1 [8]. Assuming that initial distribution inside original interval and target distributions in subintervals are uniform, the mapping in accordance to DC-QIM is optimal in terms of Mean Square Error (MSE) of quantization. In order to maximize capacity for a given MSE under AWGN of different intensity, parameters Δ, α have to be adjusted. Nevertheless, the limit defined in [6] is still well above the one achievable by DC-QIM.Not all the original coefficients in each interval need to be quantized. This idea has been explored by the authors of Forbidden Zone Data Hiding (FZDH) [9]. Another idea was proposed by the authors of Thresholded Constellation Modulation (TCM) that uses two different quantization rules to modify coefficients inside the original interval [10].Despite sufficient robustness of QIM under AWGN, the limitation is that synchronization is required in order to reconstruct intervals that are necessary to extract (or decode) a watermark. A type of distortion which scales all the watermarked coefficients is called Gain Attack (GA). The scaling factor might be close to 1 and cause very little visual distortion, but it is unknown to the receiver which causes asynchronous extraction. Retrieval of the watermark is usually complicated by AWGN that follows GA [11].Improvement of QIM performance under GA is the task of numerous known approaches [12]. Most of them can be classified into two groups where the main idea of the first group is to estimate the unknown factor [13] while the idea of the second is to quantize coefficients of a different kind that are invariant to scaling of original signal.The solution proposed in [11] contributes to robustness enhancement in case of GA and a constant offset attack followed by AWGN. A pilot signal is embedded for this purpose. Fourier analysis is used during extraction to estimate the gain factor and the offset. Another method of recovery after GA and AWGN is proposed in [14]. It uses information about dither sequence and applies Maximum Likelihood (ML) procedure to estimate the scaling factor.Watermarking that is invariant to GA demands more complex transform of original signal (e.g., nonlinear) to obtain coefficients. One of the most popular watermarking methods in that category is Rational Dither Modulation (RDM) [15]. For a particular coefficient, a ratio that depends on a norm of other coefficients is being quantized instead of a coefficient itself. In order to quantize the ratio, RDM utilizes the simplest QIM scheme. This implies that the performance of RDM under AWGN (without GA) is close to the simplest QIM. Among others recent blind watermarking methods robust to GA are, for example, detailed in [16–18].A new scalar QIM-based watermarking method is proposed in this paper. It provides high robustness under conditions of AWGN and GA. Among the new features of the method are IDL and a new form of distribution of quantized samples.The organization of the rest of the paper is as follows. Section2 explains the choice of the distribution of quantized samples and contains description of the procedure of recovery after GA. Concept of IDL and quantization model are described in Section 3 using formal logic approach. The aspects of analytic-based estimation of robustness under AWGN are discussed in Section 4. Next, Section 5 contains experimental results obtained under AWGN and GA. Discussion of the details of the experiment and comparison of the performance are given in Section 6. Section 7 concludes the paper. The list of the key variables and their meaning is given in Nomenclature section.


## 2. Distribution of Quantized Samples and Procedure for Recovery after GA

An asymmetric distribution of quantized samples is proposed and parametrized in this section. Asymmetry is the quality that can be easily expressed quantitatively. Under symmetric attack, like AWGN, such quantitative index remains sufficiently indicative. On the other hand, it can be affected by GA. Such semifragility is favorable for restoration of the right condition for decoding. The restoration is done by the procedure for recovery after GA which uses criterion of asymmetry. Compared to the known estimation procedures [14], the one proposed in this section depends on a single variable which is the unknown gain factor. This makes the technique simple and more precise.For encoding, in our case, asymmetric distribution requires substantially more variables for description compared to common QIM methods. Because of that, it is advisable to refer to Nomenclature section.


### 2.1. Distribution of Quantized Samples

SymbolΣ will be used to denote a random variable whose domain is the space of original coefficients of a host. A particular realization of Σ will be denoted as ς. We will further consider manipulation of original values ς that are in some kth interval of size Δ and its left endpoint is l
Δ
k. Such an interval is referred further as embedding interval. For any ς
∈
[
l
Δ
k
,
l
Δ
k
+
Δ
] we define x
=
ς
-
l
Δ
k and X will be used to denote a random variable which represents x. The value of Δ should be small enough so that the distribution of X can be considered uniform. A random variable that represents quantized coefficients inside kth interval is denoted as X
′ and its realization is denoted as x
′. Each pair of an original x and corresponding quantized x
′  belongs to the same kth embedding interval so that an absolute shift is never larger than Δ. Correspondingly, a random variable that represents quantized coefficients on the whole real number line is denoted as Σ
′ and its realization is denoted as ς
′.In order to provide efficient recovery after GA, we propose the following asymmetric distribution of quantized samplesx
′ inside kth embedding interval (Figure 1(a)):(1)
f
x
′
=
γ
0
+
η
1
f
0
x
′
,
if
x
′
∈
0
,
Δ
β
-
α
,
φ
1
+
ϑ
0
f
1
x
′
,
if
x
′
∈
Δ
β
,
Δ
,
0
,
otherwise
,where f
0
x
′ and f
1
(
x
′
) are two different kinds of truncated distributions defined as(2)
f
0
x
′
=
c
x
′
+
τ
,
if
x
′
∈
0
,
Δ
β
-
α
,
0
,
otherwise
,
(3)
f
1
x
′
=
g
,
if
x
′
∈
Δ
β
,
Δ
,
0
,
otherwise
.The other parameters are constrained in the following way: 0
≤
α
≤
β
≤
1, γ
0
+
ϑ
0
+
φ
1
+
η
1
=
1  (see Nomenclature section). The meaning of parameters γ
0, ϑ
0, φ
1, η
1 will be discussed later in Section 3. In Figure 1(b) we can see the distribution of the quantized coefficients outside kth embedding interval as well.Figure 1
Distribution of the quantized coefficients: (a) Insidekth embedding interval. (b) In five consecutive intervals.
(a)
(b)


### 2.2. Procedure for GA Recovery

It is assumed that under GA the original length of embedding intervalΔ is altered by unknown gain factor λ and the resulting length is Δ
~
=
λ
Δ. In addition to that, AWGN attack is applied. The procedure for GA recovery is the estimator whose result is based on a criterion having higher values for the right length Δ
~ of embedding interval. The uniqueness of the distribution of quantized samples is exploited by two different criteria C
1 and C
2. The procedure itself represents a brute force approach that substitutes guessed values Δ
~
′ of the length of embedding interval into a criterion. Guessed value of Δ
~
′ which maximizes it (C
1 or C
2) should be selected:(4)
Δ
~
′
′
=
arg
⁡
max
​
Δ
~
′
​
⁡
C
1,2
Δ
~
′
,where Δ
~
′
′ is the final output of the procedure. Some interval Δ
~
m
i
n
′
,
Δ
~
m
a
x
′ for guessed values Δ
~
′ should be defined in advance. For instance, Δ
~
m
i
n
′
=
0.9
Δ and Δ
~
m
a
x
′
=
1.1
Δ works well in most cases because the diapason of scaling factor λ is quite limited on practice.For each particular valueΔ
~
′, the index defined according to the criterion is calculated by projecting noisy quantized samples ς
n
′ on a single embedding interval:(5)
x
n
′
=
ς
n
′
mod
⁡
Δ
~
′
,
if
ς
n
′
-
l
Δ
k
Δ
~
′
mod
⁡
2
=
0
,
Δ
~
′
-
ς
n
′
mod
⁡
Δ
~
′
,
otherwise
.This is needed to reconstruct the distribution of quantized samples inside embedding interval.Two criteria are proposed for the assessment of the distribution of random variableX
n
′
∈
[
0
,
Δ
~
′
] (subscript “n” means affected by noise):(6)
C
1
Δ
~
′
=
median
X
n
′
Δ
~
′
-
0.5
,
C
2
Δ
~
′
=
μ
w
X
n
′
Δ
~
′
w
,
w
=
2
m
+
1
,
m
∈
N
.Here,μ
w is the wth central moment. Odd moments are zero for symmetric distributions, but for asymmetric distributions their values can be sufficiently large. If the assumption about Δ
~ is wrong, then the values of both criteria are low. In that case the distribution of X
n
′ is very close to uniform (which is symmetric). This is because of the effect caused by GA on calculation of x
n
′ in (5). Nevertheless, the distribution of X
n
′ demonstrates asymmetry in case Δ
~
′ is close to Δ
~. The explanation is that the distribution of quantized samples inside embedding interval (before GA is introduced) is indeed asymmetric. In spite of utilization of brute force optimization, the procedure is simple and the computational demand is low. On practice, the number of brute force steps is much smaller than the number of quantized elements. Therefore, the complexity is O
n in that case. For instance, for recovery with high accuracy it is enough to perform 103 brute force steps with values from the interval Δ
~
m
i
n
′
,
Δ
~
m
a
x
′.


## 2.1. Distribution of Quantized Samples

SymbolΣ will be used to denote a random variable whose domain is the space of original coefficients of a host. A particular realization of Σ will be denoted as ς. We will further consider manipulation of original values ς that are in some kth interval of size Δ and its left endpoint is l
Δ
k. Such an interval is referred further as embedding interval. For any ς
∈
[
l
Δ
k
,
l
Δ
k
+
Δ
] we define x
=
ς
-
l
Δ
k and X will be used to denote a random variable which represents x. The value of Δ should be small enough so that the distribution of X can be considered uniform. A random variable that represents quantized coefficients inside kth interval is denoted as X
′ and its realization is denoted as x
′. Each pair of an original x and corresponding quantized x
′  belongs to the same kth embedding interval so that an absolute shift is never larger than Δ. Correspondingly, a random variable that represents quantized coefficients on the whole real number line is denoted as Σ
′ and its realization is denoted as ς
′.In order to provide efficient recovery after GA, we propose the following asymmetric distribution of quantized samplesx
′ inside kth embedding interval (Figure 1(a)):(1)
f
x
′
=
γ
0
+
η
1
f
0
x
′
,
if
x
′
∈
0
,
Δ
β
-
α
,
φ
1
+
ϑ
0
f
1
x
′
,
if
x
′
∈
Δ
β
,
Δ
,
0
,
otherwise
,where f
0
x
′ and f
1
(
x
′
) are two different kinds of truncated distributions defined as(2)
f
0
x
′
=
c
x
′
+
τ
,
if
x
′
∈
0
,
Δ
β
-
α
,
0
,
otherwise
,
(3)
f
1
x
′
=
g
,
if
x
′
∈
Δ
β
,
Δ
,
0
,
otherwise
.The other parameters are constrained in the following way: 0
≤
α
≤
β
≤
1, γ
0
+
ϑ
0
+
φ
1
+
η
1
=
1  (see Nomenclature section). The meaning of parameters γ
0, ϑ
0, φ
1, η
1 will be discussed later in Section 3. In Figure 1(b) we can see the distribution of the quantized coefficients outside kth embedding interval as well.Figure 1
Distribution of the quantized coefficients: (a) Insidekth embedding interval. (b) In five consecutive intervals.
(a)
(b)


## 2.2. Procedure for GA Recovery

It is assumed that under GA the original length of embedding intervalΔ is altered by unknown gain factor λ and the resulting length is Δ
~
=
λ
Δ. In addition to that, AWGN attack is applied. The procedure for GA recovery is the estimator whose result is based on a criterion having higher values for the right length Δ
~ of embedding interval. The uniqueness of the distribution of quantized samples is exploited by two different criteria C
1 and C
2. The procedure itself represents a brute force approach that substitutes guessed values Δ
~
′ of the length of embedding interval into a criterion. Guessed value of Δ
~
′ which maximizes it (C
1 or C
2) should be selected:(4)
Δ
~
′
′
=
arg
⁡
max
​
Δ
~
′
​
⁡
C
1,2
Δ
~
′
,where Δ
~
′
′ is the final output of the procedure. Some interval Δ
~
m
i
n
′
,
Δ
~
m
a
x
′ for guessed values Δ
~
′ should be defined in advance. For instance, Δ
~
m
i
n
′
=
0.9
Δ and Δ
~
m
a
x
′
=
1.1
Δ works well in most cases because the diapason of scaling factor λ is quite limited on practice.For each particular valueΔ
~
′, the index defined according to the criterion is calculated by projecting noisy quantized samples ς
n
′ on a single embedding interval:(5)
x
n
′
=
ς
n
′
mod
⁡
Δ
~
′
,
if
ς
n
′
-
l
Δ
k
Δ
~
′
mod
⁡
2
=
0
,
Δ
~
′
-
ς
n
′
mod
⁡
Δ
~
′
,
otherwise
.This is needed to reconstruct the distribution of quantized samples inside embedding interval.Two criteria are proposed for the assessment of the distribution of random variableX
n
′
∈
[
0
,
Δ
~
′
] (subscript “n” means affected by noise):(6)
C
1
Δ
~
′
=
median
X
n
′
Δ
~
′
-
0.5
,
C
2
Δ
~
′
=
μ
w
X
n
′
Δ
~
′
w
,
w
=
2
m
+
1
,
m
∈
N
.Here,μ
w is the wth central moment. Odd moments are zero for symmetric distributions, but for asymmetric distributions their values can be sufficiently large. If the assumption about Δ
~ is wrong, then the values of both criteria are low. In that case the distribution of X
n
′ is very close to uniform (which is symmetric). This is because of the effect caused by GA on calculation of x
n
′ in (5). Nevertheless, the distribution of X
n
′ demonstrates asymmetry in case Δ
~
′ is close to Δ
~. The explanation is that the distribution of quantized samples inside embedding interval (before GA is introduced) is indeed asymmetric. In spite of utilization of brute force optimization, the procedure is simple and the computational demand is low. On practice, the number of brute force steps is much smaller than the number of quantized elements. Therefore, the complexity is O
n in that case. For instance, for recovery with high accuracy it is enough to perform 103 brute force steps with values from the interval Δ
~
m
i
n
′
,
Δ
~
m
a
x
′.


## 3. Quantization

A quantization model is introduced in this section. In order to represent it in a compact form, we combine all the quantization conditions in a single logical expression. Previously proposed distribution of quantized samples is assured. However, additional parameter of the quantization model implies different distribution of the samples associated with labels “0” and “1.”


### 3.1. Two Approaches for Quantization

Quantized samples are modified according to the model described in this subsection. A watermark bit is denoted asb. Each sample with value x inside kth embedding interval has index i
∈
N according to its order in the host sequence. During watermarking a bit is assigned to each index i. Different frameworks might be used for description of the quantization model. We will use first order predicate logic to describe our approach. This choice can be reasoned as follows. A closed-from expression has to be defined for quantization and it is important to show that the derived solution minimizes MSE between initial and target distribution. The kind of proposed target distribution is not common for QIM-based watermarking methods. Therefore, we find it necessary to explain in detail the process of derivation of quantization expression. Also, samples interpreting “0” should be quantized in a different way to samples interpreting “1.” Predicate logic is a suitable tool for description of embedding because logical construction can incorporate all the possible quantization conditions in a compact form.Two-place predicateE is to denote correspondence between some index and the value of coefficient. For example, E
i
x is true if a coefficient with order i has value x. We will further use notation of the set E which contains all the pairs (
x
,
i
) that provide true value of E
i
x. One-place predicate B is to denote bit value assigned to a coefficient with particular index. For instance, B
i is true if watermark bit b
=
1 is assigned to a coefficient with index i and ~B
i is true if b
=
0. Two-place predicates X
0 or X
1 will be used to define that some ith sample with value x has label “0” or “1,” respectively:(7)
X
0
i
x
≡
E
i
x
&
~
B
i
,
∀
i
∀
x
,
(8)
X
1
i
x
≡
E
i
x
&
B
i
,
∀
i
∀
x
.SetsX
0 and X
1 contain all the pairs (
x
,
i
) that provide true values of X
0
i
x and X
1
i
x, respectively. Initial PDFs of X inside X
0, X
1, and E are considered to be uniform: f
X
0
x
=
f
X
1
x
=
f
E
x
=
1
/
Δ (Figure 2).Figure 2
Scheme of labeling and distribution of original samples prior to quantization.Also, each coefficient is labeled either as IDL or non-IDL depending on its valuex and index i. Samples labeled as IDL are quantized in a different way which reduces the total embedding distortion. Both types of coefficients (IDL and non-IDL) are being modified during quantization. However, after quantization, interpretation of a bit of each IDL coefficient is incorrect. The purpose of quantization is to provide that all the non-IDL samples can be extracted correctly and the resulting distribution of all the samples is the one depicted in Figure 1(a). Parameters η
1 and ϑ
0 represent fractions of IDL for b
=
1 and b
=
0, respectively. Parameters φ
1 and γ
0 represent fractions of non-IDL samples for b
=
1 and b
=
0, respectively. The fraction of zeros in a watermark data is γ
0
+
ϑ
0 and fraction of ones is φ
1
+
η
1. It is required that γ
0
+
ϑ
0
+
φ
1
+
η
1
=
1.We define IDL and non-IDL samples using two-place predicatesI
D
L
0, I
D
L
1, N
I
D
L
0, and N
I
D
L
1 in the following way (Figure 2):(9)
I
D
L
0
i
x
≡
X
0
i
x
&
x
>
L
1
,
∀
i
∀
x
,
I
D
L
1
i
x
≡
X
1
i
x
&
x
<
L
2
,
∀
i
∀
x
,
N
I
D
L
0
i
x
≡
X
0
i
x
&
x
≤
L
1
,
∀
i
∀
x
,
N
I
D
L
1
i
x
≡
X
1
i
x
&
x
≥
L
2
,
∀
i
∀
x
,where L
1
=
Δ
γ
0
/
(
γ
0
+
ϑ
0
), L
2
=
Δ
η
1
/
(
φ
1
+
η
1
), and L
1
≥
L
2.SetsI
D
L
0, I
D
L
1, N
I
D
L
0, and N
I
D
L
1 will be used in order to specify all the coefficients that satisfy I
D
L
0, I
D
L
1, N
I
D
L
0, and N
I
D
L
1, respectively. Fractions γ
0, ϑ
0, φ
1, and η
1 can be expressed in terms of cardinalities of sets I
D
L
0, I
D
L
1, N
I
D
L
0, N
I
D
L
1
, and E. For example, I
D
L
0
/
E
=
ϑ
0.In this paper, two different quantization techniques are proposed. Since predicate logic is used to describe watermark embedding, a suitable logical construction should be able to distinguish between the techniques. According to our model, each kind of quantization can be represented by setting a corresponding logical value (“0” or “1”) for zero-place predicateΩ. Hence, Ω is used to define one out of two possible quantization techniques. For each kind of quantization, E is split on two subsets E
0 and E
1. For two-place predicates E
0 and E
1 formulas E
0
i
x and E
1
i
x are defined in the following way:(10)
E
0
i
x
≡
N
I
D
L
0
i
x
∨
I
D
L
1
i
x
&
Ω
∨
I
D
L
0
i
x
&
~
Ω
,
∀
i
∀
x
,
(11)
E
1
i
x
≡
E
i
x
&
~
E
0
i
x
,
∀
i
∀
x
.Using information about distribution insideI
D
L
0, I
D
L
1, N
I
D
L
0, and N
I
D
L
1 it is easy to derive distribution inside E
0 and E
1. Let us introduce variable ω
∈
{
0
,
1
} of natural numbers domain N (not a logical variable) which satisfies Ω
⊃
ω
=
1
&
~
Ω
⊃
ω
=
0. Common arithmetical operations can be performed with ω which makes it possible to express PDF f
E
0
x in the following compact form:(12)
f
E
0
x
=
γ
0
+
ϑ
0
f
X
0
x
+
ω
φ
1
+
η
1
f
X
1
x
D
N
0
,
if
x
≤
L
2
,
γ
0
+
ϑ
0
f
X
0
x
D
N
0
,
if
L
2
<
x
≤
L
1
,
1
-
ω
γ
0
+
ϑ
0
f
X
0
x
D
N
0
,
otherwise
,where D
N
0
=
ω
η
1
+
γ
0
+
1
-
ω
ϑ
0.Thereforef
E
1
x can be expressed as (Figures 3 and 4)(13)
f
E
1
x
=
f
E
x
-
D
N
0
f
E
0
x
1
-
D
N
0
.Figure 3
Scheme of redistribution of original samples during quantization,Ω is “true.”Figure 4
Scheme of redistribution of original samples during quantization,Ω is “false.”Elements of setsE
0 and E
1 are modified during quantization so that new sets E
0
′ and E
1
′ are obtained, respectively. Therefore, for successful quantization, we require the following formula F
1 to be true:(14)
F
1
≡
E
0
i
x
⊃
E
0
′
i
x
′
&
E
1
i
x
⊃
E
1
′
i
x
′
,
∀
i
∀
x
∃
x
′
.As a result of quantization, variablesX
E
0 and X
E
1 are modified in a way that the resulting X
E
0
′
′ and X
E
1
′
′ are distributed according to some desired distributions. For each kind of quantization (depending on the value of Ω), the pair of desired distributions is different. We propose the following distributions that can be expressed as (Figures 3 and 4)(15)
f
E
0
′
x
′
=
ω
f
0
x
′
+
1
-
ω
γ
0
f
0
x
′
+
ϑ
0
f
1
x
′
γ
0
+
ϑ
0
,
f
E
1
′
x
′
=
ω
f
1
x
′
+
1
-
ω
η
1
f
0
x
′
+
φ
1
f
1
x
′
φ
1
+
η
1
.It can be seen that, for any logical value of Ω, the distribution of X
′ inside E
0
∪
E
1 is the same and matches the distribution represented in Figure 1. It means that the efficiency of the procedure of GA recovery (proposed in the previous section) cannot be affected by the selection of Ω.In addition to the necessity of providing desired distribution of the quantized samples, we need to minimize quantization distortions. Both requirements can be expressed by two two-place predicatesU and V:(16)
E
0
′
i
x
′
≡
E
0
i
x
&
U
x
x
′
,
∀
i
∀
x
∀
x
′
,
E
1
′
i
x
′
≡
E
1
i
x
&
V
x
x
′
,
∀
i
∀
x
∀
x
′
.The idea of minimization of embedding distortions can be explained in the following example. Assuming two samplesx
i
,
x
j
∈
E
0, x
i
≤
x
j, we infer that quantization in a way in which x
i
′
≤
x
j
′ implies less distortion than in case when x
i
′
>
x
j
′. Let us sort elements in E
0 and E
0
′ in the dimension of x and x
′, respectively. Then, for some x
i (index i is an order in a host sequence) the number of elements in E
0 with x value less than x
i should be equal to the number of elements in E
0
′ that have x
′ value less than x
i
′. Integration should be used in case we switch from discrete distribution of samples in E
0 and E
0
′ to continuous one. Further, throughout the paper we assume that the constant of integration is zero for indefinite integrals. Hence, the truth values for both predicates U and V are defined as(17)
U
x
x
′
≡
∫
f
E
0
x
d
x
=
∫
f
E
0
′
x
′
d
x
′
,
∀
x
∀
x
′
,
(18)
V
x
x
′
≡
∫
f
E
1
x
d
x
=
∫
f
E
1
′
x
′
d
x
′
,
∀
x
∀
x
′
.Further, we introduce logical formula F
2
(19)
F
2
≡
∃
x
′
U
x
x
′
&
∃
x
′
V
x
x
′
,
∀
xand state that argument(20)
F
2
,
11
,
16
⊨
F
1is valid. The task of watermark embedding is to assure that the mentioned argument is sound. For that purpose, a procedure that makes F
2 true should be proposed.


### 3.2. Quantization Equations

Quantization equations and their solutions are needed to satisfy formulaF
2 during embedding. For this purpose, we will analyze conditions that enforce qualities of predicates U and V. Due to the large number of variables in the text we recommend to refer to Nomenclature section for clarity. We can rewrite elements of (17) in the following way:(21)
∫
f
E
0
x
d
x
=
min
⁡
x
,
L
2
ω
φ
1
+
η
1
+
x
γ
0
+
ϑ
0
Δ
D
N
0
,
if
x
≤
L
1
;
ω
+
1
-
ω
x
γ
0
+
ϑ
0
Δ
D
N
0
,
otherwise
,
∫
f
E
0
′
x
′
d
x
′
=
ω
+
γ
0
1
-
ω
γ
0
+
ϑ
0
∫
f
0
x
′
d
x
′
,
if
x
′
≤
Δ
β
;
ω
+
γ
0
1
-
ω
γ
0
+
ϑ
0
+
ϑ
0
1
-
ω
γ
0
+
ϑ
0
∫
f
1
x
′
d
x
′
+
∫
Δ
β
0
f
1
x
′
d
x
′
,
otherwise
.From (21) it is clear that(22)
∫
0
L
1
f
E
0
x
d
x
=
∫
0
Δ
β
-
α
f
E
0
′
x
′
d
x
′
=
ω
+
γ
0
1
-
ω
γ
0
+
ϑ
0
.The equation above means that the following is true:(23)
U
x
x
′
⊃
x
≤
L
1
&
x
′
≤
Δ
β
∨
x
>
L
1
&
x
′
>
Δ
β
,
∀
x
∀
x
′
.We introduce two two-place predicates U
1 and U
2:(24)
U
x
x
′
&
x
≤
L
1
&
x
′
≤
Δ
β
≡
U
1
x
x
′
&
U
x
x
′
&
x
>
L
1
&
x
′
>
Δ
β
≡
U
2
x
x
′
,
∀
x
∀
x
′
.According to (21) and (24) the following can be derived:(25)
U
1
x
x
′
≡
Υ
1
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
0.5
c
x
′
2
+
τ
x
′
,
∀
x
∀
x
′
,
U
2
x
x
′
≡
Υ
2
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
g
x
′
-
Δ
β
,
∀
x
∀
x
′
,where(26)
Υ
1
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
γ
0
+
ϑ
0
min
⁡
x
,
L
2
ω
φ
1
+
η
1
+
x
γ
0
+
ϑ
0
Δ
D
N
0
γ
0
+
ω
ϑ
0
,
Υ
2
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
x
γ
0
+
ϑ
0
2
-
γ
0
Δ
D
N
0
ϑ
0
Δ
D
N
0
.Now, let us analyze conditions that enforce quality of predicate V. Elements of (18) can be represented as(27)
∫
f
E
1
x
d
x
=
1
-
ω
x
φ
1
+
η
1
Δ
1
-
D
N
0
,
if
x
≤
L
2
;
max
⁡
x
-
L
1
,
0
ω
γ
0
+
ϑ
0
+
x
-
L
2
φ
1
+
η
1
Δ
1
-
D
N
0
,
otherwise
,
∫
f
E
1
′
x
′
d
x
′
=
1
-
ω
η
1
φ
1
+
η
1
∫
f
0
x
′
d
x
′
,
if
x
′
≤
Δ
β
;
1
-
ω
η
1
φ
1
+
η
1
+
ω
+
φ
1
1
-
ω
φ
1
+
η
1
∫
f
1
x
′
d
x
′
+
∫
Δ
β
0
f
1
x
′
d
x
′
,
otherwise
.We can see that according to (25)(28)
∫
0
L
2
f
E
1
x
d
x
=
∫
0
Δ
β
-
α
f
E
1
′
x
′
d
x
′
=
1
-
ω
η
1
φ
1
+
η
1
.This means that the following expression is true:(29)
V
x
x
′
⊃
x
≤
L
2
&
x
′
≤
Δ
β
∨
x
>
L
2
&
x
′
>
Δ
β
,
∀
x
∀
x
′
.Next, two two-place predicates V
1 and V
2 are defined as(30)
V
x
x
′
&
x
≤
L
2
&
x
′
≤
Δ
β
≡
V
1
x
x
′
&
V
x
x
′
&
x
>
L
2
&
x
′
>
Δ
β
≡
V
2
x
x
′
,
∀
x
∀
x
′
.According to (27) and (30) the following can be derived:(31)
V
1
x
x
′
≡
Υ
3
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
0.5
c
x
′
2
+
τ
x
′
,
∀
x
∀
x
′
,
V
2
x
x
′
≡
Υ
4
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
g
x
′
-
Δ
β
,
∀
x
∀
x
′
,where(32)
Υ
3
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
x
φ
1
+
η
1
2
η
1
Δ
1
-
D
N
0
,
Υ
4
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
φ
1
+
η
1
max
⁡
x
-
L
1
,
0
ω
γ
0
+
ϑ
0
+
x
-
L
2
φ
1
+
η
1
-
Δ
1
-
D
N
0
1
-
ω
η
1
Δ
1
-
D
N
0
φ
1
+
ω
η
1
.We can express U using U
1 and U
2 in the following way:(33)
U
x
x
′
≡
x
≤
L
1
⊃
U
1
x
x
′
&
x
>
L
1
⊃
U
2
x
x
′
,
∀
x
∀
x
′
.Also, we can express V using V
1 and V
2:(34)
V
x
x
′
≡
x
≤
L
2
⊃
V
1
x
x
′
&
x
>
L
2
⊃
V
2
x
x
′
,
∀
x
∀
x
′
.Further, utilizing property L
2
≤
L
1 we can obtain(35)
x
≤
L
2
⊃
∃
x
′
U
1
x
x
′
&
∃
x
′
V
1
x
x
′
,
∀
x
,
L
2
<
x
≤
L
1
⊃
∃
x
′
U
1
x
x
′
&
∃
x
′
V
2
x
x
′
,
∀
x
,
L
1
<
x
⊃
∃
x
′
U
2
x
x
′
&
∃
x
′
V
2
x
x
′
⊨
F
2
,
∀
x
.Here, each premise should be true. With the aim to provide this, equations in (25) and (31) should be solvable. It can be seen that the solutions are straightforward:(36)
x
U
1
,
V
1
′
=
τ
2
+
2
Υ
1,3
c
-
τ
c
,
(37)
x
U
2
,
V
2
′
=
Υ
2,4
+
g
Δ
β
g
,where, for example, in (36), x
U
1
,
V
1
′ denotes the values of x
′ that turn either U
1
x
x
′ or V
1
x
x
′ true for Υ
1
(
·
) or Υ
3
(
·
), respectively. The diagram of quantization is represented in Figure 5. Each ith original sample is chosen from array X on ith iteration. The corresponding bit of a watermark is chosen from array b. Vector θ contains parameters of the quantization. At the end of each iteration, quantized value of ith sample is written to array X
′.Figure 5
Quantization diagram for thekth embedding interval.


## 3.1. Two Approaches for Quantization

Quantized samples are modified according to the model described in this subsection. A watermark bit is denoted asb. Each sample with value x inside kth embedding interval has index i
∈
N according to its order in the host sequence. During watermarking a bit is assigned to each index i. Different frameworks might be used for description of the quantization model. We will use first order predicate logic to describe our approach. This choice can be reasoned as follows. A closed-from expression has to be defined for quantization and it is important to show that the derived solution minimizes MSE between initial and target distribution. The kind of proposed target distribution is not common for QIM-based watermarking methods. Therefore, we find it necessary to explain in detail the process of derivation of quantization expression. Also, samples interpreting “0” should be quantized in a different way to samples interpreting “1.” Predicate logic is a suitable tool for description of embedding because logical construction can incorporate all the possible quantization conditions in a compact form.Two-place predicateE is to denote correspondence between some index and the value of coefficient. For example, E
i
x is true if a coefficient with order i has value x. We will further use notation of the set E which contains all the pairs (
x
,
i
) that provide true value of E
i
x. One-place predicate B is to denote bit value assigned to a coefficient with particular index. For instance, B
i is true if watermark bit b
=
1 is assigned to a coefficient with index i and ~B
i is true if b
=
0. Two-place predicates X
0 or X
1 will be used to define that some ith sample with value x has label “0” or “1,” respectively:(7)
X
0
i
x
≡
E
i
x
&
~
B
i
,
∀
i
∀
x
,
(8)
X
1
i
x
≡
E
i
x
&
B
i
,
∀
i
∀
x
.SetsX
0 and X
1 contain all the pairs (
x
,
i
) that provide true values of X
0
i
x and X
1
i
x, respectively. Initial PDFs of X inside X
0, X
1, and E are considered to be uniform: f
X
0
x
=
f
X
1
x
=
f
E
x
=
1
/
Δ (Figure 2).Figure 2
Scheme of labeling and distribution of original samples prior to quantization.Also, each coefficient is labeled either as IDL or non-IDL depending on its valuex and index i. Samples labeled as IDL are quantized in a different way which reduces the total embedding distortion. Both types of coefficients (IDL and non-IDL) are being modified during quantization. However, after quantization, interpretation of a bit of each IDL coefficient is incorrect. The purpose of quantization is to provide that all the non-IDL samples can be extracted correctly and the resulting distribution of all the samples is the one depicted in Figure 1(a). Parameters η
1 and ϑ
0 represent fractions of IDL for b
=
1 and b
=
0, respectively. Parameters φ
1 and γ
0 represent fractions of non-IDL samples for b
=
1 and b
=
0, respectively. The fraction of zeros in a watermark data is γ
0
+
ϑ
0 and fraction of ones is φ
1
+
η
1. It is required that γ
0
+
ϑ
0
+
φ
1
+
η
1
=
1.We define IDL and non-IDL samples using two-place predicatesI
D
L
0, I
D
L
1, N
I
D
L
0, and N
I
D
L
1 in the following way (Figure 2):(9)
I
D
L
0
i
x
≡
X
0
i
x
&
x
>
L
1
,
∀
i
∀
x
,
I
D
L
1
i
x
≡
X
1
i
x
&
x
<
L
2
,
∀
i
∀
x
,
N
I
D
L
0
i
x
≡
X
0
i
x
&
x
≤
L
1
,
∀
i
∀
x
,
N
I
D
L
1
i
x
≡
X
1
i
x
&
x
≥
L
2
,
∀
i
∀
x
,where L
1
=
Δ
γ
0
/
(
γ
0
+
ϑ
0
), L
2
=
Δ
η
1
/
(
φ
1
+
η
1
), and L
1
≥
L
2.SetsI
D
L
0, I
D
L
1, N
I
D
L
0, and N
I
D
L
1 will be used in order to specify all the coefficients that satisfy I
D
L
0, I
D
L
1, N
I
D
L
0, and N
I
D
L
1, respectively. Fractions γ
0, ϑ
0, φ
1, and η
1 can be expressed in terms of cardinalities of sets I
D
L
0, I
D
L
1, N
I
D
L
0, N
I
D
L
1
, and E. For example, I
D
L
0
/
E
=
ϑ
0.In this paper, two different quantization techniques are proposed. Since predicate logic is used to describe watermark embedding, a suitable logical construction should be able to distinguish between the techniques. According to our model, each kind of quantization can be represented by setting a corresponding logical value (“0” or “1”) for zero-place predicateΩ. Hence, Ω is used to define one out of two possible quantization techniques. For each kind of quantization, E is split on two subsets E
0 and E
1. For two-place predicates E
0 and E
1 formulas E
0
i
x and E
1
i
x are defined in the following way:(10)
E
0
i
x
≡
N
I
D
L
0
i
x
∨
I
D
L
1
i
x
&
Ω
∨
I
D
L
0
i
x
&
~
Ω
,
∀
i
∀
x
,
(11)
E
1
i
x
≡
E
i
x
&
~
E
0
i
x
,
∀
i
∀
x
.Using information about distribution insideI
D
L
0, I
D
L
1, N
I
D
L
0, and N
I
D
L
1 it is easy to derive distribution inside E
0 and E
1. Let us introduce variable ω
∈
{
0
,
1
} of natural numbers domain N (not a logical variable) which satisfies Ω
⊃
ω
=
1
&
~
Ω
⊃
ω
=
0. Common arithmetical operations can be performed with ω which makes it possible to express PDF f
E
0
x in the following compact form:(12)
f
E
0
x
=
γ
0
+
ϑ
0
f
X
0
x
+
ω
φ
1
+
η
1
f
X
1
x
D
N
0
,
if
x
≤
L
2
,
γ
0
+
ϑ
0
f
X
0
x
D
N
0
,
if
L
2
<
x
≤
L
1
,
1
-
ω
γ
0
+
ϑ
0
f
X
0
x
D
N
0
,
otherwise
,where D
N
0
=
ω
η
1
+
γ
0
+
1
-
ω
ϑ
0.Thereforef
E
1
x can be expressed as (Figures 3 and 4)(13)
f
E
1
x
=
f
E
x
-
D
N
0
f
E
0
x
1
-
D
N
0
.Figure 3
Scheme of redistribution of original samples during quantization,Ω is “true.”Figure 4
Scheme of redistribution of original samples during quantization,Ω is “false.”Elements of setsE
0 and E
1 are modified during quantization so that new sets E
0
′ and E
1
′ are obtained, respectively. Therefore, for successful quantization, we require the following formula F
1 to be true:(14)
F
1
≡
E
0
i
x
⊃
E
0
′
i
x
′
&
E
1
i
x
⊃
E
1
′
i
x
′
,
∀
i
∀
x
∃
x
′
.As a result of quantization, variablesX
E
0 and X
E
1 are modified in a way that the resulting X
E
0
′
′ and X
E
1
′
′ are distributed according to some desired distributions. For each kind of quantization (depending on the value of Ω), the pair of desired distributions is different. We propose the following distributions that can be expressed as (Figures 3 and 4)(15)
f
E
0
′
x
′
=
ω
f
0
x
′
+
1
-
ω
γ
0
f
0
x
′
+
ϑ
0
f
1
x
′
γ
0
+
ϑ
0
,
f
E
1
′
x
′
=
ω
f
1
x
′
+
1
-
ω
η
1
f
0
x
′
+
φ
1
f
1
x
′
φ
1
+
η
1
.It can be seen that, for any logical value of Ω, the distribution of X
′ inside E
0
∪
E
1 is the same and matches the distribution represented in Figure 1. It means that the efficiency of the procedure of GA recovery (proposed in the previous section) cannot be affected by the selection of Ω.In addition to the necessity of providing desired distribution of the quantized samples, we need to minimize quantization distortions. Both requirements can be expressed by two two-place predicatesU and V:(16)
E
0
′
i
x
′
≡
E
0
i
x
&
U
x
x
′
,
∀
i
∀
x
∀
x
′
,
E
1
′
i
x
′
≡
E
1
i
x
&
V
x
x
′
,
∀
i
∀
x
∀
x
′
.The idea of minimization of embedding distortions can be explained in the following example. Assuming two samplesx
i
,
x
j
∈
E
0, x
i
≤
x
j, we infer that quantization in a way in which x
i
′
≤
x
j
′ implies less distortion than in case when x
i
′
>
x
j
′. Let us sort elements in E
0 and E
0
′ in the dimension of x and x
′, respectively. Then, for some x
i (index i is an order in a host sequence) the number of elements in E
0 with x value less than x
i should be equal to the number of elements in E
0
′ that have x
′ value less than x
i
′. Integration should be used in case we switch from discrete distribution of samples in E
0 and E
0
′ to continuous one. Further, throughout the paper we assume that the constant of integration is zero for indefinite integrals. Hence, the truth values for both predicates U and V are defined as(17)
U
x
x
′
≡
∫
f
E
0
x
d
x
=
∫
f
E
0
′
x
′
d
x
′
,
∀
x
∀
x
′
,
(18)
V
x
x
′
≡
∫
f
E
1
x
d
x
=
∫
f
E
1
′
x
′
d
x
′
,
∀
x
∀
x
′
.Further, we introduce logical formula F
2
(19)
F
2
≡
∃
x
′
U
x
x
′
&
∃
x
′
V
x
x
′
,
∀
xand state that argument(20)
F
2
,
11
,
16
⊨
F
1is valid. The task of watermark embedding is to assure that the mentioned argument is sound. For that purpose, a procedure that makes F
2 true should be proposed.


## 3.2. Quantization Equations

Quantization equations and their solutions are needed to satisfy formulaF
2 during embedding. For this purpose, we will analyze conditions that enforce qualities of predicates U and V. Due to the large number of variables in the text we recommend to refer to Nomenclature section for clarity. We can rewrite elements of (17) in the following way:(21)
∫
f
E
0
x
d
x
=
min
⁡
x
,
L
2
ω
φ
1
+
η
1
+
x
γ
0
+
ϑ
0
Δ
D
N
0
,
if
x
≤
L
1
;
ω
+
1
-
ω
x
γ
0
+
ϑ
0
Δ
D
N
0
,
otherwise
,
∫
f
E
0
′
x
′
d
x
′
=
ω
+
γ
0
1
-
ω
γ
0
+
ϑ
0
∫
f
0
x
′
d
x
′
,
if
x
′
≤
Δ
β
;
ω
+
γ
0
1
-
ω
γ
0
+
ϑ
0
+
ϑ
0
1
-
ω
γ
0
+
ϑ
0
∫
f
1
x
′
d
x
′
+
∫
Δ
β
0
f
1
x
′
d
x
′
,
otherwise
.From (21) it is clear that(22)
∫
0
L
1
f
E
0
x
d
x
=
∫
0
Δ
β
-
α
f
E
0
′
x
′
d
x
′
=
ω
+
γ
0
1
-
ω
γ
0
+
ϑ
0
.The equation above means that the following is true:(23)
U
x
x
′
⊃
x
≤
L
1
&
x
′
≤
Δ
β
∨
x
>
L
1
&
x
′
>
Δ
β
,
∀
x
∀
x
′
.We introduce two two-place predicates U
1 and U
2:(24)
U
x
x
′
&
x
≤
L
1
&
x
′
≤
Δ
β
≡
U
1
x
x
′
&
U
x
x
′
&
x
>
L
1
&
x
′
>
Δ
β
≡
U
2
x
x
′
,
∀
x
∀
x
′
.According to (21) and (24) the following can be derived:(25)
U
1
x
x
′
≡
Υ
1
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
0.5
c
x
′
2
+
τ
x
′
,
∀
x
∀
x
′
,
U
2
x
x
′
≡
Υ
2
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
g
x
′
-
Δ
β
,
∀
x
∀
x
′
,where(26)
Υ
1
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
γ
0
+
ϑ
0
min
⁡
x
,
L
2
ω
φ
1
+
η
1
+
x
γ
0
+
ϑ
0
Δ
D
N
0
γ
0
+
ω
ϑ
0
,
Υ
2
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
x
γ
0
+
ϑ
0
2
-
γ
0
Δ
D
N
0
ϑ
0
Δ
D
N
0
.Now, let us analyze conditions that enforce quality of predicate V. Elements of (18) can be represented as(27)
∫
f
E
1
x
d
x
=
1
-
ω
x
φ
1
+
η
1
Δ
1
-
D
N
0
,
if
x
≤
L
2
;
max
⁡
x
-
L
1
,
0
ω
γ
0
+
ϑ
0
+
x
-
L
2
φ
1
+
η
1
Δ
1
-
D
N
0
,
otherwise
,
∫
f
E
1
′
x
′
d
x
′
=
1
-
ω
η
1
φ
1
+
η
1
∫
f
0
x
′
d
x
′
,
if
x
′
≤
Δ
β
;
1
-
ω
η
1
φ
1
+
η
1
+
ω
+
φ
1
1
-
ω
φ
1
+
η
1
∫
f
1
x
′
d
x
′
+
∫
Δ
β
0
f
1
x
′
d
x
′
,
otherwise
.We can see that according to (25)(28)
∫
0
L
2
f
E
1
x
d
x
=
∫
0
Δ
β
-
α
f
E
1
′
x
′
d
x
′
=
1
-
ω
η
1
φ
1
+
η
1
.This means that the following expression is true:(29)
V
x
x
′
⊃
x
≤
L
2
&
x
′
≤
Δ
β
∨
x
>
L
2
&
x
′
>
Δ
β
,
∀
x
∀
x
′
.Next, two two-place predicates V
1 and V
2 are defined as(30)
V
x
x
′
&
x
≤
L
2
&
x
′
≤
Δ
β
≡
V
1
x
x
′
&
V
x
x
′
&
x
>
L
2
&
x
′
>
Δ
β
≡
V
2
x
x
′
,
∀
x
∀
x
′
.According to (27) and (30) the following can be derived:(31)
V
1
x
x
′
≡
Υ
3
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
0.5
c
x
′
2
+
τ
x
′
,
∀
x
∀
x
′
,
V
2
x
x
′
≡
Υ
4
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
g
x
′
-
Δ
β
,
∀
x
∀
x
′
,where(32)
Υ
3
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
x
φ
1
+
η
1
2
η
1
Δ
1
-
D
N
0
,
Υ
4
x
,
ω
,
γ
0
,
ϑ
0
,
φ
1
,
η
1
=
φ
1
+
η
1
max
⁡
x
-
L
1
,
0
ω
γ
0
+
ϑ
0
+
x
-
L
2
φ
1
+
η
1
-
Δ
1
-
D
N
0
1
-
ω
η
1
Δ
1
-
D
N
0
φ
1
+
ω
η
1
.We can express U using U
1 and U
2 in the following way:(33)
U
x
x
′
≡
x
≤
L
1
⊃
U
1
x
x
′
&
x
>
L
1
⊃
U
2
x
x
′
,
∀
x
∀
x
′
.Also, we can express V using V
1 and V
2:(34)
V
x
x
′
≡
x
≤
L
2
⊃
V
1
x
x
′
&
x
>
L
2
⊃
V
2
x
x
′
,
∀
x
∀
x
′
.Further, utilizing property L
2
≤
L
1 we can obtain(35)
x
≤
L
2
⊃
∃
x
′
U
1
x
x
′
&
∃
x
′
V
1
x
x
′
,
∀
x
,
L
2
<
x
≤
L
1
⊃
∃
x
′
U
1
x
x
′
&
∃
x
′
V
2
x
x
′
,
∀
x
,
L
1
<
x
⊃
∃
x
′
U
2
x
x
′
&
∃
x
′
V
2
x
x
′
⊨
F
2
,
∀
x
.Here, each premise should be true. With the aim to provide this, equations in (25) and (31) should be solvable. It can be seen that the solutions are straightforward:(36)
x
U
1
,
V
1
′
=
τ
2
+
2
Υ
1,3
c
-
τ
c
,
(37)
x
U
2
,
V
2
′
=
Υ
2,4
+
g
Δ
β
g
,where, for example, in (36), x
U
1
,
V
1
′ denotes the values of x
′ that turn either U
1
x
x
′ or V
1
x
x
′ true for Υ
1
(
·
) or Υ
3
(
·
), respectively. The diagram of quantization is represented in Figure 5. Each ith original sample is chosen from array X on ith iteration. The corresponding bit of a watermark is chosen from array b. Vector θ contains parameters of the quantization. At the end of each iteration, quantized value of ith sample is written to array X
′.Figure 5
Quantization diagram for thekth embedding interval.


## 4. Robustness under AWGN

In this section, we will analytically estimate the robustness of the proposed watermarking scheme under AWGN. Robustness is reflected by the term “extracted information” which denotes mutual information between embedded and detected messages. In contrast to channel capacity, the index of extracted information is practical but depends on the algorithm of detection. Also, throughout this section we assume that the original samples are distributed uniformly inside the quantization interval.The derivations for extracted information are less involved whenΩ is “false.” Therefore, only that condition is considered here. In order to estimate extracted information we first find error rates. The rates depend on the attack severity (represented by σ), Δ, and parameter set θ
=
{
γ
0
,
φ
1
,
η
1
,
ϑ
0
,
α
,
β
}. Moreover, we derive a stronger statement that information about Δ
/
σ and θ is sufficient to perform analytic estimation of error rates for our watermarking scheme. Finally, we will demonstrate how error rates can be expressed using W
N
R and θ.


### 4.1. Estimation of Error Rates

For our estimation, it is considered that, during watermark extraction, in each embedding interval samples that interpret “0” are separated from samples that interpret “1” using a threshold (e.g., hard decision region detector). The position of the threshold inith embedding interval is T
h
+
Δ
-
2
T
h
mod
⁡
(
i
-
k
,
2
) (dashed vertical lines in Figure 1(b)). Therefore, the whole real number line can be seen as a union of two domains:(38)
Z
=
⋃
m
=
-
∞
∞
2
Δ
m
+
l
Δ
k
-
Th
,
2
Δ
m
+
l
Δ
k
+
Th
,
(39)
O
=
⋃
m
=
-
∞
∞
2
Δ
m
+
l
Δ
k
+
Th
,
2
Δ
m
+
1
+
l
Δ
k
-
Th
.During extraction, all the elements in Z will be labeled “0” and all the elements in O will be labeled “1.”After noise is added, elements quantized inkth embedding interval might spread over its limits and other notations should be used. We notate sample values that are affected by noise as ς
n
′. Also, ς
n
′ belongs to some embedding interval and inside this interval we use x
n
′
=
ς
n
′
-
Δ
ς
n
′
/
Δ. Random variables Σ
n
′ and X
n
′ represent ς
n
′ and x
n
′, respectively (alternatively we use Σ
˙
′ and X
˙
′ to save space in lower subscript part). Therefore, two modified sets are obtained: E
0
′
→
A
W
G
N
Σ
˙
0
′; E
1
′
→
A
W
G
N
Σ
˙
1
′. For noise variance σ
2 we might, for instance, estimate the expected fraction for each of the noisy sets Σ
˙
0
′ and Σ
˙
1
′ in Z. Fractions of Σ
˙
0
′ and Σ
˙
1
′ that belong to O can be found in a trivial manner. In that way we obtain error rates for “0” and “1.”However, instead of appealing directly to setsΣ
˙
0
′ and Σ
˙
1
′, we use an indirect but computationally lighter approach. In case Ω is “false” we can conclude for the following distributions of quantized samples (not affected by AWGN yet) that(40)
f
E
ˇ
0
′
x
′
=
f
E
ˇ
1
′
x
′
=
f
0
x
′
,where(41)
E
ˇ
0
′
i
x
′
≡
E
0
′
i
x
′
&
x
′
≤
Δ
β
-
α
,
∀
i
∀
x
′
,
E
ˇ
1
′
i
x
′
≡
E
1
′
i
x
′
&
x
′
≤
Δ
β
-
α
,
∀
i
∀
x
′
.Also, we can conclude that the following distributions are also identical:(42)
f
E
^
0
′
x
′
=
f
E
^
1
′
x
′
=
f
1
x
′
,where(43)
E
^
0
′
i
x
′
≡
E
0
′
i
x
′
&
x
′
≥
Δ
β
,
∀
i
∀
x
′
,
E
^
1
′
i
x
′
≡
E
1
′
i
x
′
&
x
′
≥
Δ
β
,
∀
i
∀
x
′
.For any σ, (40) means that, for example, the fraction of elements from E
ˇ
0
′ that after AWGN appear in Z is equal to that of E
ˇ
1
′ and can be calculated using f
0
(
x
′
). This fraction will be denoted as F
ˇ
Z. The PDF of AWGN with variance σ
n
2 is denoted as f
N
ς
n
′
-
ς
′
,
0
,
σ
n using parameters ς
′
=
x
′
+
l
Δ
k and ς
n
′. Therefore(44)
F
ˇ
Z
=
∫
Z
∫
0
Δ
β
-
α
f
0
x
′
f
N
ς
n
′
-
x
′
-
l
Δ
k
,
0
,
σ
n
d
x
′
d
ς
n
′
.Fraction of elements from E
^
0
′ that after AWGN appear in Z will be denoted as F
^
Z:(45)
F
^
Z
=
∫
Z
∫
Δ
β
Δ
f
1
x
′
f
N
ς
n
′
-
x
′
-
l
Δ
k
,
0
,
σ
n
d
x
′
d
ς
n
′
.Error rates are calculated using F
ˇ
Z and F
^
Z:(46)
B
E
R
0
=
1
-
F
ˇ
Z
γ
0
γ
0
+
ϑ
0
+
1
-
F
^
Z
ϑ
0
γ
0
+
ϑ
0
,
B
E
R
1
=
F
ˇ
Z
η
1
φ
1
+
η
1
+
F
^
Z
φ
1
φ
1
+
η
1
.In order to demonstrate that error rates can be calculated based on Δ
/
σ, θ we analyze expression for F
ˇ
Z (expression for F
^
Z can be analyzed in a similar way). Function f
0
x
′ is present in (44). According to (2) it is defined using parameters c, τ. Parameters α, β are also present in (2) as well as in (44). Parameters α, β have clear constraints (the same is true about γ
0, ϑ
0, φ
1, η
1). It is possible to express c, τ using α, β, γ
0, ϑ
0, φ
1, η
1. In the realization of our method parameter τ is set as(47)
τ
=
γ
0
+
ϑ
0
Δ
γ
0
.Defining new parameter τ
´ as(48)
τ
´
=
τ
Δ
,it can be seen that τ
´
=
γ
0
+
ϑ
0
/
γ
0 does not depend on the choice of Δ.Using property of PDF, the following is obtained from (2):(49)
∫
0
β
-
α
Δ
f
0
x
′
d
x
′
=
c
β
-
α
2
Δ
2
2
+
τ
Δ
β
-
α
=
1
.It is easy to derive from (48) and (49) that(50)
c
Δ
2
=
2
1
-
τ
´
β
-
α
β
-
α
2
.According to (50), it is also obvious that parameter(51)
c
´
=
c
Δ
2is independent of Δ.One of the properties of PDF of AWGN is(52)
f
N
x
,
0
,
σ
n
=
1
σ
n
f
N
x
σ
n
,
0,1
.Therefore, we can rewrite (44) in the following manner:(53)
F
ˇ
Z
=
∫
Z
∫
0
Δ
β
-
α
f
0
x
′
f
N
ς
n
′
-
x
′
-
l
Δ
k
,
0
,
σ
n
d
x
′
d
ς
n
′
=
Δ
2
σ
n
∫
Z
-
l
Δ
k
/
Δ
∫
0
β
-
α
f
0
x
′
f
N
Δ
ς
n
′
-
l
Δ
k
-
x
′
Δ
σ
n
,
0,1
d
x
′
Δ
d
ς
n
′
-
l
Δ
k
Δ
.Now, it can be demonstrated that domain(54)
Z
´
=
Z
-
l
Δ
k
Δ
=
⋃
m
=
-
∞
∞
2
m
-
Th
Δ
,
2
m
+
Th
Δis independent of Δ if during extraction parameter(55)
T
h
´
=
Th
Δcan be set without information about Δ (e.g., T
h
´ may be set as T
h
´
=
β
-
0.5
α). Hence, (53) can be represented in the following way:(56)
F
ˇ
Z
=
∫
Z
´
∫
0
β
-
α
Δ
σ
n
c
´
x
′
Δ
+
τ
´
f
N
Δ
σ
n
ς
n
′
-
l
Δ
k
-
x
′
Δ
,
0,1
d
x
′
Δ
d
ς
n
′
-
l
Δ
k
Δ
.Here, for integration we consider ς
n
′
-
l
Δ
k
/
Δ
∈
Z
´ and x
′
/
Δ
∈
0
,
β
-
α, where both domains Z
´ and 0
,
β
-
α depend only on β
,
α. Except the terms ς
n
′
-
l
Δ
k
/
Δ and x
′
/
Δ, only Δ
/
σ
n, c
´
,
τ
´ appear under the integrals. Therefore, the result of integration, F
ˇ
Z, depends only on Δ
/
σ
n, θ.Further we will expressΔ
/
σ
n in terms of W
N
R and θ which confirms that B
E
R
0 and B
E
R
1 can be defined using only W
N
R and θ.


### 4.2. Estimation ofΔ
/
σ
n

MeasureW
N
R is widely used in watermarking. It expresses relation between watermark and noise energies and in AWGN case is(57)
WNR
=
10
log
10
⁡
D
σ
2
,where D is the energy of the watermark. Plot of robustness index in respect to W
N
R is one of the characteristics that are the most meaningful for practical implementation [4, 11]. Therefore it is important to be able to express error rates using W
N
R and the set of embedding parameters θ. For this purpose, we first express Δ
/
σ
n using W
N
R and θ.ParameterD in (57) can be seen as a distortion of a host signal, caused by the quantization. There are many different approaches that adequately assess quality degradation for digital images [19, 20]. Nevertheless, in this paper we are using simple and well-known distortion measure based on MSE between original and quantized samples [21]. We will define D and factor it in a form Δ
2
Q, where Q depends only on θ. It is assumed that original samples are distributed uniformly inside embedding interval. Distortion D is needed to obtain quantized sets E
ˇ
0
′, E
ˇ
1
′, E
^
0
′, and E
^
1
′. Therefore, further we will consider D as a sum of four kinds of distortion: D
=
D
ˇ
0
+
D
ˇ
1
+
D
^
0
+
D
^
1. Each of the distortion components is defined as follows:(58)
D
ˇ
0
=
γ
0
∫
0
Δ
β
-
α
f
0
x
′
x
′
-
Δ
γ
0
γ
0
+
ϑ
0
∫
0
x
′
f
0
x
′
d
x
′
2
d
x
′
,
D
ˇ
1
=
η
1
∫
0
Δ
β
-
α
f
0
x
′
x
′
-
Δ
η
1
η
1
+
φ
1
∫
0
x
′
f
0
x
′
d
x
′
2
d
x
′
,
D
^
0
=
ϑ
0
∫
β
Δ
Δ
f
1
x
′
x
′
-
Δ
ϑ
0
γ
0
+
ϑ
0
∫
β
Δ
x
′
f
1
x
′
d
x
′
+
Δ
γ
0
γ
0
+
ϑ
0
2
d
x
′
,
D
^
1
=
φ
1
∫
β
Δ
Δ
f
1
x
′
x
′
-
Δ
φ
1
η
1
+
φ
1
∫
β
Δ
x
′
f
1
x
′
d
x
′
+
Δ
η
1
η
1
+
φ
1
2
d
x
′
.It can be demonstrated that each of the distortion components can be factored usingΔ
2. For instance, considering D
ˇ
0 the next result can be obtained:(59)
D
ˇ
0
=
Δ
2
γ
0
∫
0
β
-
α
c
´
x
′
Δ
+
τ
´
x
′
Δ
-
ρ
ˇ
0
∫
0
x
′
/
Δ
c
´
x
′
Δ
+
τ
´
d
x
′
Δ
2
d
x
′
Δ
=
Δ
2
Q
ˇ
0
,where(60)
Q
ˇ
0
=
γ
0
β
-
α
3
c
´
3
ρ
ˇ
0
2
24
β
-
α
3
+
c
´
2
ρ
ˇ
0
5
τ
´
ρ
ˇ
0
-
4
20
β
-
α
2
+
c
´
1
-
τ
´
ρ
ˇ
0
1
-
2
τ
´
ρ
ˇ
0
4
β
-
α
+
τ
´
1
-
τ
´
ρ
ˇ
0
2
3
.Here(61)
ρ
ˇ
0
=
γ
0
γ
0
+
ϑ
0
.The rest of the distortion components can also be factored in a similar way, where(62)
Q
ˇ
1
=
η
1
β
-
α
3
c
´
3
ρ
ˇ
1
2
24
β
-
α
3
+
c
´
2
ρ
ˇ
1
5
τ
´
ρ
ˇ
1
-
4
20
β
-
α
2
+
c
´
1
-
τ
´
ρ
ˇ
1
1
-
2
τ
´
ρ
ˇ
1
4
β
-
α
+
τ
´
1
-
τ
´
ρ
ˇ
1
2
3
,
Q
^
0
=
ϑ
0
g
´
1
-
β
1
-
ρ
^
0
g
´
2
3
1
+
β
+
β
2
+
1
-
ρ
^
0
g
´
ρ
^
0
g
´
β
-
ρ
ˇ
0
1
+
β
+
ρ
^
0
g
´
β
-
ρ
ˇ
0
2
,
Q
^
1
=
φ
1
g
´
1
-
β
1
-
ρ
^
1
g
´
2
3
1
+
β
+
β
2
+
1
-
ρ
^
1
g
´
ρ
^
1
g
´
β
-
ρ
ˇ
1
1
+
β
+
ρ
^
1
g
´
β
-
ρ
ˇ
1
2
,
ρ
ˇ
1
=
η
1
η
1
+
φ
1
,
ρ
^
0
=
1
-
ρ
ˇ
0
=
ϑ
0
γ
0
+
ϑ
0
,
ρ
^
1
=
1
-
ρ
ˇ
1
=
φ
1
η
1
+
φ
1
.Factorization in the formD
=
Δ
2
Q can be done based on Q
=
Q
ˇ
0
+
Q
ˇ
1
+
Q
^
0
+
Q
^
1. Therefore, according to (57) Δ
/
σ can be expressed in the following way:(63)
Δ
σ
=
10
0.1
∗
W
N
R
Q
ˇ
0
+
Q
ˇ
1
+
Q
^
0
+
Q
^
1
.


## 4.1. Estimation of Error Rates

For our estimation, it is considered that, during watermark extraction, in each embedding interval samples that interpret “0” are separated from samples that interpret “1” using a threshold (e.g., hard decision region detector). The position of the threshold inith embedding interval is T
h
+
Δ
-
2
T
h
mod
⁡
(
i
-
k
,
2
) (dashed vertical lines in Figure 1(b)). Therefore, the whole real number line can be seen as a union of two domains:(38)
Z
=
⋃
m
=
-
∞
∞
2
Δ
m
+
l
Δ
k
-
Th
,
2
Δ
m
+
l
Δ
k
+
Th
,
(39)
O
=
⋃
m
=
-
∞
∞
2
Δ
m
+
l
Δ
k
+
Th
,
2
Δ
m
+
1
+
l
Δ
k
-
Th
.During extraction, all the elements in Z will be labeled “0” and all the elements in O will be labeled “1.”After noise is added, elements quantized inkth embedding interval might spread over its limits and other notations should be used. We notate sample values that are affected by noise as ς
n
′. Also, ς
n
′ belongs to some embedding interval and inside this interval we use x
n
′
=
ς
n
′
-
Δ
ς
n
′
/
Δ. Random variables Σ
n
′ and X
n
′ represent ς
n
′ and x
n
′, respectively (alternatively we use Σ
˙
′ and X
˙
′ to save space in lower subscript part). Therefore, two modified sets are obtained: E
0
′
→
A
W
G
N
Σ
˙
0
′; E
1
′
→
A
W
G
N
Σ
˙
1
′. For noise variance σ
2 we might, for instance, estimate the expected fraction for each of the noisy sets Σ
˙
0
′ and Σ
˙
1
′ in Z. Fractions of Σ
˙
0
′ and Σ
˙
1
′ that belong to O can be found in a trivial manner. In that way we obtain error rates for “0” and “1.”However, instead of appealing directly to setsΣ
˙
0
′ and Σ
˙
1
′, we use an indirect but computationally lighter approach. In case Ω is “false” we can conclude for the following distributions of quantized samples (not affected by AWGN yet) that(40)
f
E
ˇ
0
′
x
′
=
f
E
ˇ
1
′
x
′
=
f
0
x
′
,where(41)
E
ˇ
0
′
i
x
′
≡
E
0
′
i
x
′
&
x
′
≤
Δ
β
-
α
,
∀
i
∀
x
′
,
E
ˇ
1
′
i
x
′
≡
E
1
′
i
x
′
&
x
′
≤
Δ
β
-
α
,
∀
i
∀
x
′
.Also, we can conclude that the following distributions are also identical:(42)
f
E
^
0
′
x
′
=
f
E
^
1
′
x
′
=
f
1
x
′
,where(43)
E
^
0
′
i
x
′
≡
E
0
′
i
x
′
&
x
′
≥
Δ
β
,
∀
i
∀
x
′
,
E
^
1
′
i
x
′
≡
E
1
′
i
x
′
&
x
′
≥
Δ
β
,
∀
i
∀
x
′
.For any σ, (40) means that, for example, the fraction of elements from E
ˇ
0
′ that after AWGN appear in Z is equal to that of E
ˇ
1
′ and can be calculated using f
0
(
x
′
). This fraction will be denoted as F
ˇ
Z. The PDF of AWGN with variance σ
n
2 is denoted as f
N
ς
n
′
-
ς
′
,
0
,
σ
n using parameters ς
′
=
x
′
+
l
Δ
k and ς
n
′. Therefore(44)
F
ˇ
Z
=
∫
Z
∫
0
Δ
β
-
α
f
0
x
′
f
N
ς
n
′
-
x
′
-
l
Δ
k
,
0
,
σ
n
d
x
′
d
ς
n
′
.Fraction of elements from E
^
0
′ that after AWGN appear in Z will be denoted as F
^
Z:(45)
F
^
Z
=
∫
Z
∫
Δ
β
Δ
f
1
x
′
f
N
ς
n
′
-
x
′
-
l
Δ
k
,
0
,
σ
n
d
x
′
d
ς
n
′
.Error rates are calculated using F
ˇ
Z and F
^
Z:(46)
B
E
R
0
=
1
-
F
ˇ
Z
γ
0
γ
0
+
ϑ
0
+
1
-
F
^
Z
ϑ
0
γ
0
+
ϑ
0
,
B
E
R
1
=
F
ˇ
Z
η
1
φ
1
+
η
1
+
F
^
Z
φ
1
φ
1
+
η
1
.In order to demonstrate that error rates can be calculated based on Δ
/
σ, θ we analyze expression for F
ˇ
Z (expression for F
^
Z can be analyzed in a similar way). Function f
0
x
′ is present in (44). According to (2) it is defined using parameters c, τ. Parameters α, β are also present in (2) as well as in (44). Parameters α, β have clear constraints (the same is true about γ
0, ϑ
0, φ
1, η
1). It is possible to express c, τ using α, β, γ
0, ϑ
0, φ
1, η
1. In the realization of our method parameter τ is set as(47)
τ
=
γ
0
+
ϑ
0
Δ
γ
0
.Defining new parameter τ
´ as(48)
τ
´
=
τ
Δ
,it can be seen that τ
´
=
γ
0
+
ϑ
0
/
γ
0 does not depend on the choice of Δ.Using property of PDF, the following is obtained from (2):(49)
∫
0
β
-
α
Δ
f
0
x
′
d
x
′
=
c
β
-
α
2
Δ
2
2
+
τ
Δ
β
-
α
=
1
.It is easy to derive from (48) and (49) that(50)
c
Δ
2
=
2
1
-
τ
´
β
-
α
β
-
α
2
.According to (50), it is also obvious that parameter(51)
c
´
=
c
Δ
2is independent of Δ.One of the properties of PDF of AWGN is(52)
f
N
x
,
0
,
σ
n
=
1
σ
n
f
N
x
σ
n
,
0,1
.Therefore, we can rewrite (44) in the following manner:(53)
F
ˇ
Z
=
∫
Z
∫
0
Δ
β
-
α
f
0
x
′
f
N
ς
n
′
-
x
′
-
l
Δ
k
,
0
,
σ
n
d
x
′
d
ς
n
′
=
Δ
2
σ
n
∫
Z
-
l
Δ
k
/
Δ
∫
0
β
-
α
f
0
x
′
f
N
Δ
ς
n
′
-
l
Δ
k
-
x
′
Δ
σ
n
,
0,1
d
x
′
Δ
d
ς
n
′
-
l
Δ
k
Δ
.Now, it can be demonstrated that domain(54)
Z
´
=
Z
-
l
Δ
k
Δ
=
⋃
m
=
-
∞
∞
2
m
-
Th
Δ
,
2
m
+
Th
Δis independent of Δ if during extraction parameter(55)
T
h
´
=
Th
Δcan be set without information about Δ (e.g., T
h
´ may be set as T
h
´
=
β
-
0.5
α). Hence, (53) can be represented in the following way:(56)
F
ˇ
Z
=
∫
Z
´
∫
0
β
-
α
Δ
σ
n
c
´
x
′
Δ
+
τ
´
f
N
Δ
σ
n
ς
n
′
-
l
Δ
k
-
x
′
Δ
,
0,1
d
x
′
Δ
d
ς
n
′
-
l
Δ
k
Δ
.Here, for integration we consider ς
n
′
-
l
Δ
k
/
Δ
∈
Z
´ and x
′
/
Δ
∈
0
,
β
-
α, where both domains Z
´ and 0
,
β
-
α depend only on β
,
α. Except the terms ς
n
′
-
l
Δ
k
/
Δ and x
′
/
Δ, only Δ
/
σ
n, c
´
,
τ
´ appear under the integrals. Therefore, the result of integration, F
ˇ
Z, depends only on Δ
/
σ
n, θ.Further we will expressΔ
/
σ
n in terms of W
N
R and θ which confirms that B
E
R
0 and B
E
R
1 can be defined using only W
N
R and θ.


## 4.2. Estimation ofΔ
/
σ
n

MeasureW
N
R is widely used in watermarking. It expresses relation between watermark and noise energies and in AWGN case is(57)
WNR
=
10
log
10
⁡
D
σ
2
,where D is the energy of the watermark. Plot of robustness index in respect to W
N
R is one of the characteristics that are the most meaningful for practical implementation [4, 11]. Therefore it is important to be able to express error rates using W
N
R and the set of embedding parameters θ. For this purpose, we first express Δ
/
σ
n using W
N
R and θ.ParameterD in (57) can be seen as a distortion of a host signal, caused by the quantization. There are many different approaches that adequately assess quality degradation for digital images [19, 20]. Nevertheless, in this paper we are using simple and well-known distortion measure based on MSE between original and quantized samples [21]. We will define D and factor it in a form Δ
2
Q, where Q depends only on θ. It is assumed that original samples are distributed uniformly inside embedding interval. Distortion D is needed to obtain quantized sets E
ˇ
0
′, E
ˇ
1
′, E
^
0
′, and E
^
1
′. Therefore, further we will consider D as a sum of four kinds of distortion: D
=
D
ˇ
0
+
D
ˇ
1
+
D
^
0
+
D
^
1. Each of the distortion components is defined as follows:(58)
D
ˇ
0
=
γ
0
∫
0
Δ
β
-
α
f
0
x
′
x
′
-
Δ
γ
0
γ
0
+
ϑ
0
∫
0
x
′
f
0
x
′
d
x
′
2
d
x
′
,
D
ˇ
1
=
η
1
∫
0
Δ
β
-
α
f
0
x
′
x
′
-
Δ
η
1
η
1
+
φ
1
∫
0
x
′
f
0
x
′
d
x
′
2
d
x
′
,
D
^
0
=
ϑ
0
∫
β
Δ
Δ
f
1
x
′
x
′
-
Δ
ϑ
0
γ
0
+
ϑ
0
∫
β
Δ
x
′
f
1
x
′
d
x
′
+
Δ
γ
0
γ
0
+
ϑ
0
2
d
x
′
,
D
^
1
=
φ
1
∫
β
Δ
Δ
f
1
x
′
x
′
-
Δ
φ
1
η
1
+
φ
1
∫
β
Δ
x
′
f
1
x
′
d
x
′
+
Δ
η
1
η
1
+
φ
1
2
d
x
′
.It can be demonstrated that each of the distortion components can be factored usingΔ
2. For instance, considering D
ˇ
0 the next result can be obtained:(59)
D
ˇ
0
=
Δ
2
γ
0
∫
0
β
-
α
c
´
x
′
Δ
+
τ
´
x
′
Δ
-
ρ
ˇ
0
∫
0
x
′
/
Δ
c
´
x
′
Δ
+
τ
´
d
x
′
Δ
2
d
x
′
Δ
=
Δ
2
Q
ˇ
0
,where(60)
Q
ˇ
0
=
γ
0
β
-
α
3
c
´
3
ρ
ˇ
0
2
24
β
-
α
3
+
c
´
2
ρ
ˇ
0
5
τ
´
ρ
ˇ
0
-
4
20
β
-
α
2
+
c
´
1
-
τ
´
ρ
ˇ
0
1
-
2
τ
´
ρ
ˇ
0
4
β
-
α
+
τ
´
1
-
τ
´
ρ
ˇ
0
2
3
.Here(61)
ρ
ˇ
0
=
γ
0
γ
0
+
ϑ
0
.The rest of the distortion components can also be factored in a similar way, where(62)
Q
ˇ
1
=
η
1
β
-
α
3
c
´
3
ρ
ˇ
1
2
24
β
-
α
3
+
c
´
2
ρ
ˇ
1
5
τ
´
ρ
ˇ
1
-
4
20
β
-
α
2
+
c
´
1
-
τ
´
ρ
ˇ
1
1
-
2
τ
´
ρ
ˇ
1
4
β
-
α
+
τ
´
1
-
τ
´
ρ
ˇ
1
2
3
,
Q
^
0
=
ϑ
0
g
´
1
-
β
1
-
ρ
^
0
g
´
2
3
1
+
β
+
β
2
+
1
-
ρ
^
0
g
´
ρ
^
0
g
´
β
-
ρ
ˇ
0
1
+
β
+
ρ
^
0
g
´
β
-
ρ
ˇ
0
2
,
Q
^
1
=
φ
1
g
´
1
-
β
1
-
ρ
^
1
g
´
2
3
1
+
β
+
β
2
+
1
-
ρ
^
1
g
´
ρ
^
1
g
´
β
-
ρ
ˇ
1
1
+
β
+
ρ
^
1
g
´
β
-
ρ
ˇ
1
2
,
ρ
ˇ
1
=
η
1
η
1
+
φ
1
,
ρ
^
0
=
1
-
ρ
ˇ
0
=
ϑ
0
γ
0
+
ϑ
0
,
ρ
^
1
=
1
-
ρ
ˇ
1
=
φ
1
η
1
+
φ
1
.Factorization in the formD
=
Δ
2
Q can be done based on Q
=
Q
ˇ
0
+
Q
ˇ
1
+
Q
^
0
+
Q
^
1. Therefore, according to (57) Δ
/
σ can be expressed in the following way:(63)
Δ
σ
=
10
0.1
∗
W
N
R
Q
ˇ
0
+
Q
ˇ
1
+
Q
^
0
+
Q
^
1
.


## 5. Experimental Results

In this section, two different settings are considered for experiments. AWGN attack is investigated assuming the first kind of settings and GA attack is investigated assuming the second kind of settings. For the first type, the obtained results are compared with the results of QIM and DC-QIM. For the second type, the performance is compared with the results of RDM (DC-QIM was not considered here as it is vulnerable to GA). Here, in each type of experiment, the goal is to estimate the highest possible amount of extracted information of the method for a given intensity of attack. We explore optimization of embedding parameters. During watermark embedding, parametersγ
0
,
ϑ
0
,
φ
1
,
η
1, and Ω define sets E
0 and E
1. In addition to the mentioned parameters, c, τ, and g are needed to define E
0
′ and E
1
′. Extracted information is maximized over γ
0, ϑ
0, φ
1, η
1, Ω, c, τ, and g by brute force approach. With the aim to reduce computations, parameters η
1, ϑ
0, φ
1, and γ
0 are constrained according to our considerations.


### 5.1. Information Extracted under AWGN

During the experiment, parametersη
1
,
γ
0
,
ϑ
0, and φ
1 were constrained as η
1
+
γ
0
=
0.5, ϑ
0
+
φ
1
=
0.5. It can be explained by our intention to use a detector based on median thresholding inside embedding interval. Therefore, if one detects the watermark message right after embedding, the I
D
L fraction for “0” and “1” will be ϑ
0 and η
1, respectively. One of the advantages of median thresholding is that no additional information is needed for detection even though the distribution of quantized samples is asymmetric and controlled by many parameters. The parameter T
h for median-based (hard decision) detector is calculated using two steps: (a) for all ς
n
′ find x
n
′ according to (5); (b) calculate T
h
=
m
e
d
i
a
n
X
n
′.For other methods that were used for comparisons, the standard hard decision detector was used (with equal length of decision intervals for “0” and “1”).For the proposed watermarking methodI
D
L occurs only if the condition γ
0
+
φ
1
<
1 holds. In that case, different values of ω cause different robustness characteristics. However, IDL might not be suitable for some application in Digital Watermarking. For instance, in semifragile watermarking a fraction of lost data can be interpreted as the presence of an attack (which increases false positive rate). Therefore, condition γ
0
+
φ
1
=
1 has been investigated first.In Figure6, amount of extracted information toward WNR is plotted for the proposed method, DC-QIM and QIM [8]. During watermark extraction, the value of the normalized threshold was set to T
h
´
=
β
-
0.5
α.Figure 6
Analytic-based estimation of information extracted under AWGN without IDL.Error rates were calculated according to (46). However, only the integers from -
100
,
100 were used as a set for m in (38) instead of the whole set Z. The purpose of the limitation is to reduce computational complexity while still maintaining high fidelity of the result. Then, the maximized amount of extracted information C was calculated according to(64)
C
=
max
p
em
~
b
⁡
p
~
b
,
b
log
2
⁡
p
~
b
,
b
p
e
m
~
b
p
e
x
b
+
p
b
,
~
b
log
2
⁡
p
b
,
~
b
p
e
m
b
p
e
x
~
b
+
p
~
b
,
~
b
log
2
⁡
p
~
b
,
~
b
p
e
m
~
b
p
e
x
~
b
+
p
b
,
b
log
2
⁡
p
b
,
b
p
e
m
b
p
e
x
b
.Here, p
~
b
,
b denotes joint probability of embedding symbol ~
b and extracting symbol b; p
e
m
b and p
e
x
b denote probabilities of symbol b to be embedded and extracted, respectively. Using joint probabilities, we calculate probabilities of extracting a particular bit:(65)
p
e
x
b
=
p
~
b
,
b
+
p
b
,
b
,
p
e
x
~
b
=
p
b
,
~
b
+
p
~
b
,
~
b
.Joint probabilities can be expressed using p
e
m
· and error rates:(66)
p
~
b
,
b
=
p
e
m
~
b
B
E
R
0
,
p
b
,
~
b
=
p
e
m
b
B
E
R
1
,
p
~
b
,
~
b
=
p
e
m
~
b
1
-
B
E
R
0
,
p
b
,
b
=
p
e
m
b
1
-
B
E
R
1
.As it was mentioned earlier, embedding probabilities are(67)
p
e
m
~
b
=
γ
0
+
ϑ
0
,
p
e
m
b
=
η
1
+
φ
1
.From Figure 6 it can be seen that with no IDL the proposed method performs better than QIM for W
N
R
≤
9 dB and better than DC-QIM for WNR values less than −2 dB.While comparing the designed method with DC-QIM, explanation of a slightly better performance should be found in the new distribution of quantized samples and thresholding technique. Optimal solution for the problem of informed data hiding has been theorized by Costa [6], and every known practical answer, including DC-QIM, uses structured codebook which lacks certain desirable characteristics [11]. We believe that the minor advantage of the presented method is due to larger number of variables that were adjusted for embedding.In case IDL is acceptable (for a particular watermarking application), much better results are achievable for both “true” and “false”Ω under low WNRs (Figure 7). Obviously, the demonstrated superiority is due to IDL only. Additionally, it can be seen that “false” logical value of Ω provides slightly more beneficial outcome under AWGN compared to when Ω is “true.” As a reference, Costa Theoretical Limit (CTL) [6] is plotted in Figure 7:(68)
CTL
=
1
2
log
2
⁡
1
+
10
0.1
∗
W
N
R
.Figure 7
Analytic-based estimation of information extracted under AWGN with IDL.


### 5.2. Information Extracted under GA

In this subsection, we explore performance of the proposed quantization approach under GA. For comparison, RDM is chosen instead of DC-QIM as it is known to be vulnerable to GA. We describe conditions and the results of the simulations based on real images and assuming watermark embedding followed by GA.For the experimental evaluation, we used 92 natural grayscale images with resolution 512 × 512. Each image was split on 4 × 4 blocks and first singular values of Singular Value Decomposition (SVD) were quantized to embed a watermark [22]. The watermarking was arranged without IDL and γ
0
=
φ
1
=
0.5. Document to Watermark Ratio (DWR) was set to 28 dB, where(69)
DWR
=
10
log
10
⁡
σ
H
2
Dand σ
H
2 is the variance of the original coefficients. An example of original and watermarked diagnostic images is given in Figure 8.Figure 8
Common MRI imaging of a patient’s kidney: (a) original diagnostic image; (b) watermarked image.
(a)
(b)For some healthcare organizations, protection of personal data is a high priority task. On the other hand, diagnostic data might need to be shared between experts from other organizations. For that purpose, DIW is a suitable tool [23]. However, an important additional constraint is imposed in that case: an expert conclusion (diagnosis) should not be affected by watermarking. According to the judgements of collaborating group of medical imaging experts, the diagnostic statement for the watermarked image in Figure 8(b) is identical to the statement for the original one in Figure 8(a).For watermark embedding (encoding), a brute force optimization overα and β was repeated for each new value of σ. Obviously, this needs to be done only once as the optimal parameters can be stored. In addition to the concept of optimal parameters, we investigated efficiency of a constrained version of the proposed quantization approach, where α and β were constant and equal to 0.05 and 0.35, respectively. The common sense behind such a modification is that actual σ of AWGN might not be known on practice during watermark embedding (because the attack happens after embedding).For watermark extraction (hard decision decoding), these two steps are required: (1) apply GA recovery procedure; (2) define threshold. In accordance with the proposed procedure for GA recovery, criterionC
1 was used for the estimation of actual Δ during the experiment. The condition of GA was simulated by ignoring information about Δ value that was used for embedding. Hence, the value was estimated by the procedure of GA recovery. No information except initial guess interval with Δ
~
m
i
n
′
=
0.9
Δ, Δ
~
m
a
x
′
=
1.1
Δ was used for watermark extraction. In contrast to that, RDM does use the information about the exact value of quantization step. For RDM, the value of a given quantized coefficient was calculated using the information about the previous 100 coefficients.Two types of thresholding are possible and two types of extraction conditions exist. Under condition whenα and β are constants, no additional information needs to be transferred to the decoder. However, if α and β are optimized on encoder’s side, information about them might need to be sent. This is necessary if thresholding is established in the way that T
h
´
=
β
-
0.5
α (e.g., the threshold is in the middle of separating zone in quantization interval). Since the requirement for additional information seems impractical, we proposed median thresholding T
h
=
m
e
d
i
a
n
X
n
′ as well.For each method that took part in the experiment, the resulting amount of extracted information is plotted toward AWGN variance (Figure9).Figure 9
Information extracted under GA followed by AWGN.As it can be seen from Figure9, under both mentioned conditions of embedding, the proposed approach outperforms RDM. The advantage is more evident for larger AWGN variance.


## 5.1. Information Extracted under AWGN

During the experiment, parametersη
1
,
γ
0
,
ϑ
0, and φ
1 were constrained as η
1
+
γ
0
=
0.5, ϑ
0
+
φ
1
=
0.5. It can be explained by our intention to use a detector based on median thresholding inside embedding interval. Therefore, if one detects the watermark message right after embedding, the I
D
L fraction for “0” and “1” will be ϑ
0 and η
1, respectively. One of the advantages of median thresholding is that no additional information is needed for detection even though the distribution of quantized samples is asymmetric and controlled by many parameters. The parameter T
h for median-based (hard decision) detector is calculated using two steps: (a) for all ς
n
′ find x
n
′ according to (5); (b) calculate T
h
=
m
e
d
i
a
n
X
n
′.For other methods that were used for comparisons, the standard hard decision detector was used (with equal length of decision intervals for “0” and “1”).For the proposed watermarking methodI
D
L occurs only if the condition γ
0
+
φ
1
<
1 holds. In that case, different values of ω cause different robustness characteristics. However, IDL might not be suitable for some application in Digital Watermarking. For instance, in semifragile watermarking a fraction of lost data can be interpreted as the presence of an attack (which increases false positive rate). Therefore, condition γ
0
+
φ
1
=
1 has been investigated first.In Figure6, amount of extracted information toward WNR is plotted for the proposed method, DC-QIM and QIM [8]. During watermark extraction, the value of the normalized threshold was set to T
h
´
=
β
-
0.5
α.Figure 6
Analytic-based estimation of information extracted under AWGN without IDL.Error rates were calculated according to (46). However, only the integers from -
100
,
100 were used as a set for m in (38) instead of the whole set Z. The purpose of the limitation is to reduce computational complexity while still maintaining high fidelity of the result. Then, the maximized amount of extracted information C was calculated according to(64)
C
=
max
p
em
~
b
⁡
p
~
b
,
b
log
2
⁡
p
~
b
,
b
p
e
m
~
b
p
e
x
b
+
p
b
,
~
b
log
2
⁡
p
b
,
~
b
p
e
m
b
p
e
x
~
b
+
p
~
b
,
~
b
log
2
⁡
p
~
b
,
~
b
p
e
m
~
b
p
e
x
~
b
+
p
b
,
b
log
2
⁡
p
b
,
b
p
e
m
b
p
e
x
b
.Here, p
~
b
,
b denotes joint probability of embedding symbol ~
b and extracting symbol b; p
e
m
b and p
e
x
b denote probabilities of symbol b to be embedded and extracted, respectively. Using joint probabilities, we calculate probabilities of extracting a particular bit:(65)
p
e
x
b
=
p
~
b
,
b
+
p
b
,
b
,
p
e
x
~
b
=
p
b
,
~
b
+
p
~
b
,
~
b
.Joint probabilities can be expressed using p
e
m
· and error rates:(66)
p
~
b
,
b
=
p
e
m
~
b
B
E
R
0
,
p
b
,
~
b
=
p
e
m
b
B
E
R
1
,
p
~
b
,
~
b
=
p
e
m
~
b
1
-
B
E
R
0
,
p
b
,
b
=
p
e
m
b
1
-
B
E
R
1
.As it was mentioned earlier, embedding probabilities are(67)
p
e
m
~
b
=
γ
0
+
ϑ
0
,
p
e
m
b
=
η
1
+
φ
1
.From Figure 6 it can be seen that with no IDL the proposed method performs better than QIM for W
N
R
≤
9 dB and better than DC-QIM for WNR values less than −2 dB.While comparing the designed method with DC-QIM, explanation of a slightly better performance should be found in the new distribution of quantized samples and thresholding technique. Optimal solution for the problem of informed data hiding has been theorized by Costa [6], and every known practical answer, including DC-QIM, uses structured codebook which lacks certain desirable characteristics [11]. We believe that the minor advantage of the presented method is due to larger number of variables that were adjusted for embedding.In case IDL is acceptable (for a particular watermarking application), much better results are achievable for both “true” and “false”Ω under low WNRs (Figure 7). Obviously, the demonstrated superiority is due to IDL only. Additionally, it can be seen that “false” logical value of Ω provides slightly more beneficial outcome under AWGN compared to when Ω is “true.” As a reference, Costa Theoretical Limit (CTL) [6] is plotted in Figure 7:(68)
CTL
=
1
2
log
2
⁡
1
+
10
0.1
∗
W
N
R
.Figure 7
Analytic-based estimation of information extracted under AWGN with IDL.


## 5.2. Information Extracted under GA

In this subsection, we explore performance of the proposed quantization approach under GA. For comparison, RDM is chosen instead of DC-QIM as it is known to be vulnerable to GA. We describe conditions and the results of the simulations based on real images and assuming watermark embedding followed by GA.For the experimental evaluation, we used 92 natural grayscale images with resolution 512 × 512. Each image was split on 4 × 4 blocks and first singular values of Singular Value Decomposition (SVD) were quantized to embed a watermark [22]. The watermarking was arranged without IDL and γ
0
=
φ
1
=
0.5. Document to Watermark Ratio (DWR) was set to 28 dB, where(69)
DWR
=
10
log
10
⁡
σ
H
2
Dand σ
H
2 is the variance of the original coefficients. An example of original and watermarked diagnostic images is given in Figure 8.Figure 8
Common MRI imaging of a patient’s kidney: (a) original diagnostic image; (b) watermarked image.
(a)
(b)For some healthcare organizations, protection of personal data is a high priority task. On the other hand, diagnostic data might need to be shared between experts from other organizations. For that purpose, DIW is a suitable tool [23]. However, an important additional constraint is imposed in that case: an expert conclusion (diagnosis) should not be affected by watermarking. According to the judgements of collaborating group of medical imaging experts, the diagnostic statement for the watermarked image in Figure 8(b) is identical to the statement for the original one in Figure 8(a).For watermark embedding (encoding), a brute force optimization overα and β was repeated for each new value of σ. Obviously, this needs to be done only once as the optimal parameters can be stored. In addition to the concept of optimal parameters, we investigated efficiency of a constrained version of the proposed quantization approach, where α and β were constant and equal to 0.05 and 0.35, respectively. The common sense behind such a modification is that actual σ of AWGN might not be known on practice during watermark embedding (because the attack happens after embedding).For watermark extraction (hard decision decoding), these two steps are required: (1) apply GA recovery procedure; (2) define threshold. In accordance with the proposed procedure for GA recovery, criterionC
1 was used for the estimation of actual Δ during the experiment. The condition of GA was simulated by ignoring information about Δ value that was used for embedding. Hence, the value was estimated by the procedure of GA recovery. No information except initial guess interval with Δ
~
m
i
n
′
=
0.9
Δ, Δ
~
m
a
x
′
=
1.1
Δ was used for watermark extraction. In contrast to that, RDM does use the information about the exact value of quantization step. For RDM, the value of a given quantized coefficient was calculated using the information about the previous 100 coefficients.Two types of thresholding are possible and two types of extraction conditions exist. Under condition whenα and β are constants, no additional information needs to be transferred to the decoder. However, if α and β are optimized on encoder’s side, information about them might need to be sent. This is necessary if thresholding is established in the way that T
h
´
=
β
-
0.5
α (e.g., the threshold is in the middle of separating zone in quantization interval). Since the requirement for additional information seems impractical, we proposed median thresholding T
h
=
m
e
d
i
a
n
X
n
′ as well.For each method that took part in the experiment, the resulting amount of extracted information is plotted toward AWGN variance (Figure9).Figure 9
Information extracted under GA followed by AWGN.As it can be seen from Figure9, under both mentioned conditions of embedding, the proposed approach outperforms RDM. The advantage is more evident for larger AWGN variance.


## 6. Discussion

In the experimental section, robustness of the proposed quantization method was estimated under AWGN and GA. The proposed approach provides higher amount of extracted information compared to the other state-of-the-art reference methods, like DC-QIM and RDM. The reasons of its superiority will be discussed in more detail in this section.Asymmetric distribution of quantized samples and the proposed procedure for GA recovery is a successful combination that provides robustness under GA. Compared to other estimations of the scaling factor from the literature, the proposed estimation approach is light. For instance, in order to estimate the scaling factor, a model of a host is used in [14] which complicates estimation and reduces its precision. On the other hand, an approach different to estimation is exploited by RDM [15]. However, Distortion Compensation is not present in RDM. In contrast to that, the proposed quantization method has Distortion Compensation and outperforms RDM because AWGN is introduced (as a second stage of GA).The proposed quantization approach demonstrates higher robustness under AWGN compared to well-known DC-QIM. The advancement that causes such superiority is IDL. ParameterΩ was introduced in order to distinguish between two different ways of realization for IDL. Target distribution for all the samples in quantization interval remains the same for any logical value of Ω (which guarantees equally successful recovery from GA). Distributions are different if “ones” and “zeros” are considered separately. This influences the resulting performance. As it has been demonstrated by the experiment, modification of the quantization approach with “false” Ω performs slightly better. In general, usage of IDL is beneficial under low WNRs. The common sense here is that predicting the loss of some information (as a result of an attack) we might accept the scenario when a part of information is lost initially. Compared to DC-QIM, such quantization behavior enables redistribution of embedding distortion from samples that are likely to be misinterpreted to the other (non-IDL) samples that can be more robust.Unlike DC-QIM, the proposed quantization method has many parameters that need to be set up for watermark embedding. Some additional parameters might be needed depending on the technique for watermark extraction. For instance, the thresholding that depends onT
h
´
=
β
-
0.5
α may be applied, which requires parameters α, β to be communicated to the receiver.On the other hand, no parameters are needed for extraction if the proposed median thresholding is used (absolutely blind extraction). ParameterΔ can be estimated using procedure for GA recovery taking as input only rough interval Δ
~
m
i
n
′
,
Δ
~
m
a
x
′. This is an advantage compared to DC-QIM that always requires Δ to be known to the decoder.We do not consider any case with malicious attacks (that analyze and deliberately change the watermarked signal) as they are not the objectives of our paper. However in case a key is used to protect a watermark, it will also be needed for decoding.Lastly, we need to emphasize that the computational cost of our scheme is low. Optimization of embedding parameters conducted in Section5 is computationally heavy, but it needs to be done only once. The optimized parameters can be used for embedding then. The computational cost of embedding is comparable with that of DC-QIM (please, refer to the quantization diagram). For extraction, complexity of the proposed procedure of GA recovery is O
n.


## 7. Conclusions

A new scalar QIM-based watermarking method has been proposed in this paper. It provides higher robustness under AWGN and GA compared to other quantization methods. The benefits of the method are due to the introduced procedure of recovery after GA as well as new distribution of quantized samples with IDL.For the new distribution of quantized samples there is no symmetry inside embedding interval. The nonsymmetric distribution of quantized samples is exploited by the introduced procedure of recovery after GA. Two different criteria are proposed to be used within the procedure. During experiment it has been confirmed that the procedure is computationally light and efficient.In addition to the new kind of distribution of quantized samples, the proposed QIM-based method benefits from IDL. Utilization of IDL can reduce embedding distortions introduced to a host signal. This is done by letting some watermark bits to be interpreted incorrectly during embedding and before any attack occurs. A model that describes quantization process assumes that IDL can be implemented in two different ways depending on the logical value of parameterΩ. The proposed realization of IDL is beneficial for any Ω under highly intensive AWGN attack. However, “false” value of Ω provides slightly higher robustness compared to “true.”Considerable performance improvements are due to the abovementioned advancements. The amount of information extracted (using hard decision decoder) under AWGN is at the same or of a higher level compared to DC-QIM. Usage of IDL is the most advantageous under AWGN for WNRs close to −12 dB, where it performs up to 104 times better than DC-QIM. Under GA, the performance of the proposed method is up to 103 times higher than that of RDM. Finally, visual quality degradation caused by the proposed quantization method was also estimated in a subjective way by a group of medical imaging experts. It was confirmed that as a result of watermarking, important diagnostic characteristics did not change.



---

*Source: 9029745-2016-02-24.xml*