134
168
THS

 

’f‘a‘Fq-e

(90/30

lHHaHHHHZHLHHHHIHHHHHHH HlHHHlHlHH

301834 6001

 

LIBRARY :1

H M"mitten State‘,
Unl lvurlny

 

.
L—_¥ I

t'-

This is to certify that the

thesis entitled

ADAPTIVE WAVELET-DOMAIN DIGITAL IMAGE WATERMARKING: A

DETECTION-THEORETIC APPROACH

presented by

Keith J. Jones

has been accepted towards fulfillment
of the requirements for

fl 5 degree in E E

AU

Major professor

Date 2/6//??

0-7639 MS U is an Affirmative Action/Equal Opportunity Institution

 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE

DATE DUE

DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ma chleOS-p“

ADAPTIVE WAVELET-DOMAIN DIGITAL IMAGE WATERMARKING: A
DETECTION-THEORETIC APPROACH

BY

KEITH J. JONES

A THESIS
Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of
MASTER OF SCIENCE

DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING

1999

ABSTRACT

Adaptive Wavelet-Domain Digital Image Watermarking: A Detection-Theoretic
Approach

By

Keith J. Jones

The goal of digital watermarking is the ability to embed information into a file
so any attempts to remove the information would render the file useless to the
attacker. This technological tool is used for a variety of purposes including owner-
ship declaration, authentication, content control, and covert communications. The
basic engineering trade-offs involved when designing a digital watermark are with
the following three competing factors: information embedding rate, distortion of
the original file, and robustness due to intentional or unintentional attempts to
remove the watermark information. A general framework which addresses these
trade-offs is presented and an existing adaptive wavelet-domain scheme is further
deve10ped using hypothesis testing. A new adaptive wavelet domain watermark-
ing method is also proposed which is superior to the existing method, in real world

application.

For my beautiful wife, Andrea.

iii

ACKNOWLEDGEMENTS

I would like to acknowledge all the help from Dr. Robert Nowak, from the initial
ideas for the foundation of this thesis, to the proof reading of the final draft.
Without him, this would not have been possible.

iv

TABLE OF CONTENTS

1 INTRODUCTION

2 OVERVIEW OF EXISTING METHODS
2. 1 Spread Spectrum Approaches ....................
2.2 Quantization Approaches .......................
2.3 Adaptive Quantization Approaches .................

3 FORMULATION or ADAPTIVE WAVELET-BASED WATERMARK—
ING METHODS
3.1 The Wavelet Transform ........................
3.2 The Overview of an Existing Method ................
3.2.1 A Decision - Theoretic Approach ..............
3.3 The New Adaptive Watermarking Method .............
3.3.1 Comparison/Analysis .....................

4 APPLICATION
5 CONCLUDING REMARKS AND RECOMMENDATIONS

BIBLIOGRAPHY

4030303

14
19
24

28

36

39

4.1
4.2
4.3
4.4
4.5

LIST OF TABLES

The bit-error rates using J PEG compression of 90% .........
The bit-error rates using J PEG compression of 75% .........
The bit-error rates using J PEG compression of 60% .........
The bit-error rates using a low-pass filter with W, = 0.99.

The bit-error rates using a low-pass filter with W“ = 0.9. . . . . .

vi

34
34
34
35
35

2.1

3.1
3.2
3.3
3.4
3.5
3.6

4.1
4.1
4.2
4.3
4.4

LIST OF FIGURES

General watermark embedding model. ............... 7
The 2-D wavelet transform example. ................ 10
The quantization model. ....................... 12
The bit-error rate for p = 0.4 ..................... 24
The bit-error rate for p = 0 ..................... 25
The bit-error rate for p = —0.4 ................... 25
The bit—error rate for varying p values using the existing method

with the hypothesis test. ....................... 27
The host images. ........................... 30
The host images (can’t). ....................... 31
An example of watermarking methods. ............... 32
An example of JPEG attack, 60% compression. .......... 33
An example of low-pass filter attack, W” = 0.9. .......... 33

vii

CHAPTER 1
INTRODUCTION

Digital media provides an extraordinary medium to share information such as
audio, images, and video. Due to the ability to transmit digital media easily,
content providers find it advantageous to embed additional information in their
files. This introduction will provide a background about watermarking that will
be useful for the analysis of the specific algorithms.

There are many uses for digital watermarks. Some of them include:

1. Proof of ownership of a file can allow the owner to distribute their content in
a medium, such as the internet, where this file could be capied repeatedly.
The watermark, which contains the ownership information, may be the only

proof the owner will have to collect any necessary royalties.

2. File authentication would allow a person to receive a file and be reassured

it was produced and not tampered with in route to the receiving entity.

3. Using a watermark to control a file’s usage would allow the owner to place

restrictions such as the copy/no copy/copy once scheme for DVD disks.

4. Covert communications would allow for two entities the ability to transmit
information to each other secretly. The security in this application is high
because third parties would not know to look within a transmitted file for

the communication.

For further discussion on watermark usage, see [1].
For many of these applications to be successful, the embedding scheme must
be robust. A watermarking scheme is considered to be robust when removing or

altering (“attacking”) the watermark causes the host file (in which the watermark

is embedded) to be of little or no use. For example, if the host is an image, then
removing a “robust” watermark will drastically degrade the visual quality of the
image. There are two types of attacks against which a watermarking algorithm
must be robust: the unintentional attack and the intentional attack. Unintentional
attacks consist of any transformation that may be applied without the intent to
harm a watermark and still leave the visual quality of the image acceptable. Some

examples of unintentional attacks on images are:

l. Filtering.
2. Crapping.
3. Resizing.
4. Rotation.
5. Digital to analog, and analog to digital conversions.
6. Format conversions.
7. Compression.
8. Non linear transformations
9. Color manipulations.

10. Multiple watermarks.

11. Noise.

Intentional attacks are performed with the specific aim to remove the watermark
information. Intentional attacks on images include:

1. Collusion

2. Attack on the detector.

3. Attack on the encoder.

4. False watermark information representation.
5. Multiple watermarking.

6. Removal of sections of the image.

It is important to mention the existence of software packages to test the robustness
of watermarking methods. One such package, StirMark [2],[3],[4], automates many
of the attacks above. For further discussion on attack methods, see [1].

Watermarks can be used in nearly every file type. Some examples of file types
that can be watermarked are the following:

1. Test documents - ASCII or document processing programs.
2. Audio files - WAV and MP3.

3. Image files — GIF, JPEG, TIFF, PGM, and RAW.

4. Video files - AVI and MPG.

5. CAD files - watermark the textures applied to the object.

For the rest of this thesis, the concentration will be on gray-scale images that are
256 x 256 pixels.

Currently, there are two general types of watermarks used: visible watermarks
and invisible watermarks. A visible watermark provides a robust method but
may also degrade the visual usefulness of the file. This type of watermark usually
consists of a symbol, phrase, or trademark and appears in the image, visible to the
naked eye. An invisible watermark would try to alleviate any visual degradation
to the file, but its robustness is limited. This type of watermark is invisible to the
naked eye and requires a special detection algorithm to decode the watermark. An

invisible watermark usually consists of an ASCII phrase or a binary number. A
watermark causing little visible degradation and that is highly robust to a number
of “attacks”, or intentional attempts to remove it, is very desirable.

From an engineering perspective, the basic trade-offs involve the following

competing factors when designing a watermarking algorithm:
1. The amount of information embedded.

2. The degradation to the original image.

3. The robustness of the watermark against attacks.

The visible degradation stems from having to hide the information within
the digital image which degrades some of the visual quality. Since the human
visual system is not perfect, a small perturbation from the original image to
generate a watermarked image may not be detected by the human eye. Therefore
there is a range of perturbations the original image, also called the host image,
can endure during the watermarking process before the watermarked image is
considered inferior to the host in visual quality.

To make a watermark robust, a scheme would typically watermark a large
portion of the image and be highly redundant. Watermarking a large amount of
visual information could erode the visual quality of a watermarked image. Embed-
ding the watermark information redundantly will limit the amount of information
embedded. Hence, the trade-offs involved are readily apparent.

The work in this thesis improves upon an existing watermark embedding
method by formal hypothesis testing. In addition, a new digital watermark encod-
ing method is proposed that is practically superior to the existing method. The
new method increases the robustness while keeping the visual degradation of the

encoding phase and the amount of information encoded, a constant. The analysis

here also sheds light on several important features of the adaptive watermarking
methods.

CHAPTER 2
OVERVIEW OF EXISTING METHODS

2.1 Spread Spectrum Approaches

Many watermarks use an approach defined as spread spectrum embedding. The
approach adds pseudo-noise information to the host image to construct the water-
marked image. Least significant bit (LSB) method is one example of this approach.
The LSB method adds the information to the least significant bit of each pixel
value to represent the watermark. This approach is easily removed because the
attacker can subtract their pseudo-noise information signal from the watermarked
image and create a new watermark in the image. This process is known as the
IBM attack [5]. Since this method is easily attacked and removed, there is a need
to develop a more robust system. The following section pr0poses the next logical
step in such an approach.

2.2 Quantization Approaches

In [6], a generalized model of the quantization technique that addresses the trade-
offs among visual degradation, robustness, and amount of data embedded is pro-
posed. In this model, the host is represented by a vector 1: E R”, where R is
the real line. The host signal can be either the image itself or a transformation,
such as the Discrete Wavelet 'Ikansforrn (DWT), of the image. The data will be
embedded into 1: at a rate of R bits per host signal sample. Denote by m, the
integer chosen from a set {0, 1, 2, ..., 29"“ - 1}, as the information to be embed-
ded. s(z, m) is the quantized (watermarked) data indexed by m, defined as a
quantization index modulation function. Also define a noise vector, n, which can
be stochastic or determinant, signal dependent or independent, that represents an

 

 

x—b- s(X,m) S 3)] DEC —>m

m i n

 

 

 

 

 

 

Figure 2.1: General watermark embedding model.

attack on the watermark. In the case of no attack, the noise vector n, is ideally
zero. The decoder will calculate the estimate in of m from the attacked image y.
This completely general model can be observed in Fig. 2.1.

The authors of [6] further the approach by a coded dither modulation scheme in
which q[-] represents a given quantizer. This quantizer is used at shifted increments
to represent a dithered quantizer, parameterized by a dither vector d(m) for each

possible value of m, so that:

8(1; m) = alt + d("0] - d(m) (2-1)

The goal of this approach is to ensure that two dithered quantizers are the maxi-
mum possible distance from each other. As a simple example, q[] could be defined
as a uniform, scalar quantizer with step size A. See [6] for further explanation of
this example. Although this general model is useful, a watermarking method that

adapts to the host signal could provide more robustness.

2.3 Adaptive Quantization Approaches

Although the approach in the previous section provides a more robust scheme
to watermark images, it is possible to exploit characteristics of the human visual
system (HVS) to strengthen the robustness of the quantization method. The HV S

is unable to detect noise in areas of similar frequency patterns. This phenomenon
is known as frequency masking [1]. The HVS is also known to be unable to
detect the visibility of other features that are spatially close to them, and this is
known as spatial masking [1]. Together, a new type of masking, known as edge
masking, allows for a stronger signal to be hidden in the edge features at different
frequency levels and spatial locations within the image. Where edges are absent,
the watermark information will be less obtrusive. A watermarking scheme which
exploits edge masking is characterized as an adaptive method

In contrast to the dithered quantizer in the previous section, adaptive quantiz-
ers are signal dependent. Near edges of the host image, s(z, m) will watermark the
image harshly without noticeably degrading the visual quality of the image. Such
an adaptive quantizer will increase the robustness of the watermarking algorithm.

The methods pr0posed in the following chapters are all adaptive.

CHAPTER 3
FORMULATION OF ADAPTIVE WAVELET-BASED
WATERMARKING METHODS

3.1 The Wavelet Transform

The discrete wavelet transform (DWT) provides localization in frequency and
space. Because of this fact, the wavelet transform provides a much more suitable
domain to adaptively watermark information. Furthermore, the wavelet transform
is known to be sparse, and the edges of the image tend to be evident in the highest
absolute values of the wavelet coefficients [7] . This edge phenomenon can be seen
as the white pixels in Fig. 3.1(c). This feature is effective for exploiting the edge
masking prOperty when embedding a watermark. For further explanation of the
DWT, see [7].

The two-dimensional DWT (2DWT) can be efficiently computed using a filter
bank structure. The sub-image in the lower right corner of Fig. 3.1(b) is obtained
by applying a high-pass filter (H) to the rows and columns of the original im-
age and decimating in each direction. The sub-images H,H, (diagonal details)
L,H, (horizontal details) and H,L (vertical details) are composed of the wavelet
coefficients at the first scale. The sub-image in the upper-left corner represents
the scaling coefficients at the next scale and is obtained by reiterating the filter
bank on the previous scale’s L,L sub-image. Fig. 3.1 illustrates the process of

performing the two—dimensional wavelet transform on a test image.

3.2 The Overview of an Existing Method

One promising method using wavelet-domain adaptive watermark encoding was

pmposed in [8]. The embedding rate, defined in Section 2.2, is R = §. A value

 

 

 

 

 

 

 

 

 

L,L H,L
H,L
L,H H,H
L,H H,H
(a) The Original Image. (b) The 2—D wavelet trans-

form diagram.

 

(c) The 2—D wavelet transform
example.

Figure 3.1: The 2—D wavelet transform example.

10

of Q is chosen to represent a trade-off between robustness and visual degradation
of this algorithm. Q is chosen on a trial-and-error basis. It is desirable to choose
the lowest integer Q value that does not produce visual degradation to the host
image. Typically, values of 6 S Q 5 10 do not produce noticeable distortions.
The framework for the system pr0posed can be generalized into the following

algorithm for embedding a watermark:

1. Compute the DWT of the host image. Denote the wavelet coefficient image

saw.

2. For each scale, I, and each position (i, j) within I, perform the following

steps:

(a) There are three distinct sets of wavelet coefficients, corresponding to
the three orientations; vertical, horizontal, and diagonal. Take the
triple of coefficients at position (i, j) and scale l, and order them so

that:

wlfltfivj) < wMaarj) < whdsavj) (3'1)

where d; E {horizontal,vertical,diagonal}, each distinct. If

mm. (131') = mm... (131')

when k at m, then perturb the value of 101,4,(i, j) slightly so that the

algorithm may continue.

(b) Given Q, calculate the quantization step size with the following equa-

ll

i T [j

- T
,1) I

W
l

5‘

‘

d( 1.1)
3
Figure 3.2: The quantization model.

tion:

A = wl,d3 (i: :)Q-u;l,di (i: j) (32)

(c) To embed a watermark bit of value one, quantize w“, (i, j) to the near-
est quantization level with 1 written over it in Fig. 3.2. To embed a
watermark bit of value zero, quantize w“, (i, j) to the nearest quanti-

zation level with a 0 written over it in Fig. 3.2.
The decoding process is also formulated into an algorithm as follows:

1. Compute the DWT of the host image. Denote the wavelet coefficient image

”w.

2. For each scale, l, and each position (i, j) within I, perform the following
steps:

(a) There are three distinct sets of wavelet coefficients, corresponding to
the three orientations; vertical, horizontal, and diagonal. Take the
triple of coefficients at position (i, j) and scale I, and order them so

that:

101,416,” < 101,430,,” < 101,436,]? (3.3)

12

where d; e {horizontal,vertical,diagonal}, each distinct. If

101,4. (i, j) = whit... (it j)

when k 96 m, then perturb the value of wt,“ (1', j) slightly so that the

algorithm may continue.

(b) Given Q, calculate the quantization step size with the following equa-

tion:

_ WMLJ’) - 101.410.]?
A — 2Q _ l (3.4)
(c) Find the closest quantization level in Fig. 3.2 to the tow, value. If there
is a 0 over the line, a zero is decoded. If there is a 1 over the line, a

one is decoded.

Decoding the wavelet coefficient to the nearest quantization level in Fig. 3.2 is
equivalent to finding the maximum value of the following expression, with respect
to n, where the integer n e [0, 2Q - 1]:

 

PM. u) = - (101.420. 2') - w... (232') - ”w”, (’3 31,1"? ("j )) (3.5)

If the value of n that maximizes Eq. (3.5) is even, a zero is decoded. If the value of
n that maximizes Eq. (3.5) is add, a one is decoded. Eq. (3.5) is approximately the
log likelihood expression for the observed data after an additive attack, modeled
as an additive Gaussian White Noise (GWN). This decoder provides invariance for
affine transformations to a given wavelet triple representing the three directions

for the coordinates (i, j) in level I.

13

The value of Q used is also very important. 2Q - 1 denotes the number of
quantization levels in Fig. 3.2. For higher values of Q, the range is quantized
with higher resolution, while lower values of Q quantize coarsely. The value of
Q represents part of the engineering trade-off for the pr0posed system because
a lower value of Q will produce a watermark more robust and a higher level of
visual degradation. A higher value of Q will produce a system less robust, but
the watermarked image will bare a closer resemblance to the host image.

This watermarking scheme is adaptive because at areas with edge features, the
wavelet coefficients will be large. When there are large distances between to“,
and an...” the watermark perturbs the host image more aggressively compared to
the case when w“, and w“, are near each other. When to”, and w“. are near
each other, the edge feature is missing and the perturbation to the host image is
small.

3.2.1 A Decision - Theoretic Approach

The proposed method in Section 3.2 may not produce the n which minimizes the
probability of an error. Given a model of the attack process, the goal of this
chapter is to minimize the probability of error for the existing method by finding
the most likely encoded bit using the hypothesis test:

Ho : n is even, 0 encoded,

H1 : n is odd, 1 encoded.

First, the preliminaries must be established. Define a vector Y as the obser-
vations of the wavelet coefficient triple in a given image suspected of containing a

watermark:

14

”hit (’2 j)
Y = 91,4: (5’1) (3'6)

_ ”Ad: ('rj)

 

 

Define the vector W as the original watermarked wavelet coefficients before the
attack:

101,4, (5.1)

W = 101.425,.” (3'7)

 

 

_ "11,436,.” ..

This suspected image is assumed to have an attack, modeled as an additive Gaus-
sian noise, defined as the vector 5, with the covariance matrix 2y, given below,

and a zero mean vector.

1 p p
2y: p 1 p '02 (3.8)

 

 

hppld

Notice this is only one such choice for the covariance matrix, other more general
covariance structures will be pr0posed in Chapter 5. This particular covariance
matrix is chosen because it adds the next logical step of complexity beyond an
independent error model (diagonal covariances), allowing for possible correlation,
p, between the wavelet coefficient errors. This level of generality, as opposed to
an independent error model, is important since many attacks, e.g., JPEG, may

introduce correlated errors. The attack is modeled by:

15

P

”'9‘! ('a J)
ylpdz (is J)
_ ”M; (i: J)

 

 

p

Wm. (M) + 61

" wzmfid) + 6:

 

_ 101.4,“, j) + £3

Eirthermore, the log likelihood function is:

.W=_w—EWW$HY-MU)

 

(am

aim

A transformation from the three variable system in Eq. (3.9) can be made to

the two variable system in Eq. (3.11) without loss, since the wavelet coeflicient

differences alone contain the necessary decoding information.

51,1“: .1)
b136, J)

B:

-101
—110

 

Many statistical values can be evaluated:

t

whiz — what

5151.1“: J)]

E[b1,2(i:j)l =

wi,d;(5,j) - 101.4. (itj)

nt
2Q — 1
t

nt

20—1

 

 

F 91.41“,»
111,420: J)
_ ”his“: J) .

q

 

(3.11)

win
win
was

min

The derivation for the new transformed covariance matrix is given in Eq. (3.16)

16

through (3.27):

V3151) = EKG: " 502] (3-16)
=.- E[e§ — 25.21 + cf] (3.17)

= (1 — 2p +1)a2 (3.18)

= 2(1 - p)a’ (3.19)

vMU») = E[(€2 - 602] (33-20)
= Eh; - 2521:. + 8:] (3.21)

= (1 — 2p + 1)a2 (3.22)

= 2(1 — ma2 (3.23)

COVU’I: 52) = Elks - ‘61)(62 " 61)] (334)
= EIE362 — £152 — £361 + 61‘] (3.25)

= (p — p — p + 1)a’ (3.26)

= (1 — p)a2 (3.27)

These calculations lead to the form of the covariance matrix below:

In 21
b2 12

EB=COV

(1 - p)a2 (3.28)

The new covariance matrix has a structure which is invariant to the value of p.
Therefore, the overall probability of error is a function of p, but the detector struc-
ture (decision rule) will be indifferent. The performance analysis with different
values of p will be discussed in section 3.3.1. The position notation (i, j) and
the scale index I will be omitted where unnecessary to keep the equations simple

17

throughout the rest of this analysis. The new log likelihood equation is:

1'3 = —(B — E[B])'2§‘(B — E[B]) (3.29)

The hypothesis test involves the choice of whether 2, the bit initially encoded,
is zero or one. The minimum probability of error decision [9] is determined by the

likelihood ratio test (LRT) defined as:

H1
p(B|n,t,z = 1) >

<
p(B|n,t, z = 0) Ho

 

A(B) = 1 (3-30)

Several nuisance parameters prevent a direct calculation of this test. The

nuisance parameters are:
0 n e {0,2,4,6,8, ...,2Q - 2}|z = 0
o n E {1,3,5,7,8,...,2Q- 1}]z = l
o t 6 31*

The nuisance parameter n, providing the exact position of the bit encoded, and
t, the quantization distance, are not known. One approach to solve this problem
is the generalized likelihood ratio test (GLRT) where the nuisance parameters are
replaced by the maximum likelihood estimates (MLE) of their values. The GLRT
is defined as follows:

max p(Blnrtiz = 1) H1

 

~ n odd, t 6 32+ > 1
MB) — max p(B|n, t, z = 0) [$0 (331)
n even, t 6 92+

18

Computing the MLE for t and substituting it into the likelihood ratio test,
Eq. (3.30), nearly completes the GLRT and provides Eq. (3.32). The completion
of the GLRT involves searching for the n that maximizes Eq. (3.32) within the
range of [0, 2Q — 1]. Finally, if the maximizing n is even, then it is assumed a
zero was encoded; if it is odd then a one was encoded. Hence, this completes the

hypothesis test.

(b; + bln — ago)? (3.32)

mi“ 1°” (B'"’ t) = 2(p - l)(n + n2 + (1 — 2o)? — 21.0)

3.3 The New Adaptive Watermarking Method

Here a new method is preposed which is a variant / extension of the previous
method. The new method defines an information bit with two integers (m, n),
representing a zero if m and n are even, and a one if m and n are odd. Notice
the embedding rate, defined in Section 2.2, is also R = 3] for this method. A Q
value will be used which serves the same purpose as in the previous method. The
integer values of m and n are defined by:

(m) e l—(2Q- 1).2Q— 11x l-(2Q- 1).2Q— 1] (3.33)

The encoding process can be summarized in the following algorithm:

1. Compute the DWT of the host image. Denote the wavelet coefficient image

”w.

2. For each scale, I, and each position (i, j) within l, perform the following

steps:

19

(a) There are three orientations in the DWT image. Take the same coor-

dinates, (i, j), in l and order the wavelet coefficients so that:

lwl,dr(irj)| < lwl,d2(iaj)| < lwl,ds(irj)l (334)

where d). e {horizontal,vertical,diagonal}, each distinct. If

Iwz.d.(5:j)| = lwz,¢,.(i,j)|

when k 56 m, then it is possible to perturb the value of w“. (i, j) slightly

so that the algorithm may continue.

(b) The embedding process makes the following changes to the wavelet

coefficient triple:

1014.621.) = Ez—g’f—I’Jz (335)
w; ,4, (i, j) = W (3.36)

To embed a zero, (m, n) are both chosen to be even such that the
distance between the host, it), and new, 111’, wavelet coefficient values
are minimal. If a one is to be embedded, (m, n) are both chosen to be
odd such that the new, g, values are minimal distance from the host,

11/, corresponding wavelet coefficients.

The new method also has a similar decoding sequence to the previous method.

It is summarized as follows:

1. Compute the DWT of the image in question. Denote the wavelet coefficient

image as w.

20

2. For each scale, I, and each position (i, j) within I, perform the following

steps:

(a) There are three orientations in the DWT image. Take the same coor-

dinates, (i,j), in l and order the wavelet coefficients so that:

lwl,d1(irj)| < lwl,da(irj)| < lwlflsarjn (337)

where d), E {horizontal,vertical,diagonal}, each distinct. If

th.d.(5»j)| = lwz,4,.(i,j)l

when k 7‘ m, then it is possible to perturb the value of w“, (i, j) slightly

so that the algorithm may continue.

(b) Find the values of (m, n) which are both even or both odd that maxi-
mize the following equation:

- . man i 2
meme -(w:.a.(i.J)--—;¢'7‘3‘T‘-’-’) —

(101312011) - W)? (3-38)

This is equivalent to finding the m and n values which are both even
or odd and minimize the distance when compared to the w“, (i, j)

coefficient. Notice this is also in the form of a log likelihood expression.

We can derive a similar decision rule by following the more formal hypothesis

test as before. The hypotheses are defined as:

21

Ho : n, m are even, 0 encoded,

H1 : n,m are odd, 1 encoded.

To set up the decision rule, one must define more notation. Define a vector Y

as the observations of a suspect image according to Eq. (3.6) and (3.39).

[9131511)] < [MARIN < [“3136er (3'39)

Also define a vector W similar to Eq. (3.7) and denote this vector as the true value
of the wavelet coefficient triples before an attack. Again, an attack is modeled
using Eq. (3.9). The statistical properties of e are the same as that assumed in
the previous method using the covariance matrix in Eq. (3.8) and a zero mean
vector. Again, this choice of covariance matrix is only one of many, Chapter 5
will recommend more for future research. The expected values of the observation

Y are given below.

E[m,r(i.1’)l= 7%}? (3.40)
Elmsffijll = W (3.41)
E[yr,3(i,j)] = was,» (3.42)

Using a similar argument as the previous formal decision rule, in this case the

GLRT is given by:

22

 

max p(Wlmr n2 whilst z = 1) H1
- m,n odd, to“, 6 R > 1
A(W) - max P(Wlm: 7‘: whats: z = 0) [:0 (3.43)

m,n even, mu, 6 92

By finding the maximum likelihood estimate for w“, (i, j) and substituting it
into Eq. (3.10), the result nearly completes the GLRT and gives Eq. (3.55).

to = 111.4. (5.1) (3-44)
to = 111.42 (1': 1) (3-45)
33 = 31.4. (131') (3-46)
(1 = y§(m2 + n2 — 2mnp) (3.47)
b = 2y,y3(n - mp - m’p + mnp - 2nQ + 2me) (3.48)
c = y;(1 + m2 + 2mp - 4Q - 4me + 40') (3.49)
d = 11%” + (1 - 2Q)2 + n(2p - 4110)) (3-50)
e = -2w(p(1 + n - 2Q)(32 + are - 21120)) (3-51)
f = 41110710192 - 113 + yap - Map + 21/30 - 2112120)) (35-52)

9 = (-1 + p)(m2(1 + p) + n2(1+ p)+(1 + p)(1 - 262)”) (3-53)

h = (-1 + p)(—2mp(-1 + n + 262) + n(2p — 4pQ)) (3.54)

a+b+c+d+e+i (3.55)

113,973 1089(Wlm, n. while) = g + h

In a similar manner as before, we search over integer values (m, n) 6 [— (2Q —

1), 2Q - 1] x [—(2Q — 1), 2Q - 1)], both even or both odd, and find the pair that

23

 

    

0.45 .

New Method with the Hypothesis Test
0 New Method

- - - Existing Method with the Hypothesis Test
+ Existing Method

 

 

 

 

 

0.3'

03"

“Brande

V

0.2

0.15 '-

0.1-

0.05%

 

 

 

Figure 3.3: The bit-error rate for p = 0.4.

produces the maximum value of Eq. (3.55). If the maximizing (m, n) are both
even, a zero is assumed to be encoded. If they are odd, a one is assumed to be
encoded. Hence, this is the completion of the hypothesis test.

An important note is the value for p in the covariance matrix can be different
for each level of wavelet resolution, l, being decoded. This provides for greater
flexibility and better detection.

3.3.1 Comparison/Analysis

The performance simulation is structured such that the host wavelet triples are
independently Gaussian distributed. Each watermarking method will be applied
to these triples, separately, and attacked with the addition of Gaussian noise. Each
method will use the same host wavelet triple values to encode the watermark, the

same noises, and the same encoding bit values.

24

 

0.15 '-

0.“ -

 

 

 

U T U V

New Method with the Hypothesis Test

New Method -
Existing Method with the Hypothesis Te
Existing Method .

 

 

 

 

 

Figure 3.4: The bit.error rate for p = 0

 

0.15 -

ons-

 

U I l T

 

 

 

New Method with the Hypothesis Test
New Method

Existing Method with the Hypothesis Test
Existing Method ‘

 

 

 

 

 

Figure 3.5: The bit-error rate for p = -—0.4

25

The calculated results from the simulation for the bit-error rate represents a
situation when a watermarked image may be attacked by the addition of Gaussian
noise. This is an ideal scenario which fits the hypothesis test model perfectly.
Because the data and the noise are generated in this manner, a value of power
can be associated and will provide a measure of signal-to—noise ratio (SNR) for each
iteration. The purpose of this type of simulation is to plot several performance
curves for different values of the SNR.

The result of probability of bit-error rate versus signal-to—noise ratio for each
of the four decoders are depicted in Fig. 3.3, 3.4, and 3.5. The simulation used
a Q value of 10, performed 1000 repetitions for each SNR value, and the stated
p value. The Q value was chosen as 10 because this is the lowest value observed
that does not produce visual degradation.

Fig. 3.3 shows that the pr0posed method under-performing the existing method.
Fig. 3.4 and 3.5 shows the preposed method has superior performance to the ex-
isting method at higher SNR values. Therefore, one conclusion can be drawn
concerning the value of p: if the noise added is uncorrelated or slightly negatively
correlated, then the new method is superior.

Another conclusion is that the hypothesis test, Eq. (3.32), for the existing
method does not perform much better, or worse, than the ad hoc scheme, Eq. (3.5),
when different values of p are used to generate the correlated noise. This can
be explained with the following argument. If the range between w“, (i, j) and
w),¢,(i, j) is quantized with a large Q, the most likely values of y. ,4, (i, j) and
y; ,4,(i, j) are the values w; ,4, (i, j) and w),d,(i, j), respectively. That is, if a very
fine quantization step is used, then the maximization is essentially unconstrained
and produces the same results as the ad hoc method. Therefore, this argument

suggests Eq. (3.5) is actually the same maximization as Eq. (3.32) and the curves
are as expected.

26

 

 

 

 

 

 

 

. I U I I T l
as ' H
k '. ........ p - _0.4
\ . — o
0.45 - \ P " -
\ " ' ‘ p I +0.4
\ .,
b \ .’. a:
04 \
\ ° ,
\
0.35 P \ .1. d
\ -.
\
\
i 0.3 H- \ ..
\
\
IE 0.8 "' \ a
\
3 \ -.
02 - \ 1
\ .
\
0.15 - \ -
\
\ .
o ‘ \ \ ..' on
r x
\ \
00w - \ """ II
\ ........
0 l 1 1 1 T ““““
20 25 so 35 40 45 50
SNR

Figure 3.6: The bit-error rate for varying p values using the existing method with
the hypothesis test.

In contrast, the covariance structure presented in Eq. (3.28) makes the decision
rule for the existing method with the hypothesis test invariant to the choice of
p, but the performance is not. Fig. 3.6 compares the probability of detection for
different choices of p for the existing method. Notice the detector performance
is better with positive values of p as opposed to negative values. As the value of
p tends toward one, the covariance matrix becomes zero. Therefore, the overall
covariability becomes zero and the performance of the detector is maximum.

Conversely, the new method is dependent on p when using the hypothesis
test. When p is chosen as a good estimate of the added correlated noise, the
proposed detector based on a hypothesis test performs slightly better than the ad
hoc version. The increase in performance using the hypothesis test for the new

method is very slight, however.

27

CHAPTER 4
APPLICATION

It is desirable to test each watermark embedding method on a variety of real
images. Fig. 4.1 represents a typical assortment of test imsges because there
are solid objects (Fig. 4.1(a)), granular (Fig. 4.10)), and combinations of straight
edges (Fig. 4.1(c) and 4.1(d)). The other images represent different mixtures of
each. Furthermore, this subset is extensively used for testing and evaluations
purposes in the research community.

Fig. 4.2 displays an example image selected from the subset watermarked with
the existing method and the new method. An example of two attacks can be
viewed in Fig. 4.3 and 4.4 for both watermarking schemes. Each figure represents
an image with nearly zero visual degradation using J PEG compression of 60% and
low pass filtering using a third-order two-dimensional Butterworth filter [10] with
cutoff frequency W“ = 0.9. Various bit-error rates can be viewed in Tables 4.1
through 4.5. The value of p chosen for the tabular results varied, but was usually
slightly negative and constant across each wavelet resolution level, 1.

Tables 4.1 through 4.5 provide numerous values for the bit-error rates using
different strengths of the two attacks. The conclusion drawn from the tables is
obvious: the newly proposed method performs superior compared to the existing
method. In some instances, the new method performs nearly 30% better than the
existing method.

Due to the actual correlation value, p, due to these attacks tended to be
slightly negative, Fig. 3.3 through 3.5 strengthens the conclusion that the new
method performs better than the existing method. This correlation is the key
factor in determining the difference in the performance of the two methods.

The hypothesis test for the previous (existing) method performed the same

28

as the ad hoc detector in Eq. (3.5), therefore the argument regarding the rough
equivalence of the two decoders given in the last chapter is strengthened. The
hypothesis test for the new method seems to do better or worse depending on the
value of p chosen for the simulation. Since the purpose of this thesis is not to find
the Optimum value of p, it is important to note that an increase in performance
could be achieved with enough trial and error experiments to find the best estimate

of p for each instance of attack and level of wavelet resolution, I.

29

(b) Bridge

 

(6) Building (d) Camera

 

(e) n-uit

Figure 4.1: The host images.

30

 

0) River

Figure 4.1: The host images (con’t).

31

 

(c) New Method

Figure 4.2: An example of watermarking methods.

32

 

(a) Fig. 4.2(b) Attacked (b) Fig. 4.2(c) Attacked

Figure 4.3: An example of JPEG attack, 60% compression.

 

(a) Fig. 4.2(b) Attacked (b) Fig. 4.2(c) Attacked

Figure 4.4: An example of low-pass filter attack, Wfl = 0.9.

33

8
Eq. 3.32
.2360
.1
0.1
.221
.1662
0.2235
.1
.1
0.1

8
Eq. 3.55
1993

0.1
21
1
0.2029
1

0.0691
0.

 

Table 4.1: The bit-error rates using J PEG compression of 90%.

. 3.5

0.

0.1

1

0.2757
0.2868
0.3375
0.3022

.3449
0.2522

.2647

0.1 19

0.
0.

0.2831
0.2860

2235

0.2353
0.1

3.55
.31

0.

0.2772

0.2779
3081

0.

0.

0.1816

 

Table 4.2: The bit-error rates using JPEG compression of 75%.

 

 

 

 

 

 

 

 

 

 

 

 

Image P. Method 1 IT Method 1 P, Method 2 P. Method 2
Eq. (3.5) Eq. (3.32) Eq. (3.38) Eq. (3.55)

benz 0.3794 0.3794 0.3632 0.3691
bridge 0.3493 0.3485 0.3176 0.3243
building 0.3493 0.3500 0.2919 0.2956
camera 0.3654 0.3654 0.3434 0.3434
fruit 0.3750 0.3743 0.3221 0.3272
girl 0.4096 0.4110 0.3485 0.3515
318.88% 0.3544 0.3566 0.3287 0.3279
lenna 0.3471 0.3463 0.3044 0.3022
mandrill 0.3596 0.3588 0.3375 0.3390
river 0.3162 0.3184 0.3081 0.3132

 

 

 

 

 

Table 4.3: The bit-error rates using JPEG compression of 60%.

34

 

. 3.5

0.1956

0.1
0.1

0.1699
0.0838

0.0669
0.0801

0.1
.1
0
0.1691
.0831
0.
0.0669
0 1

35

3.55
0.1654

0.1331
0.1

0.1346
0.
0.
0.0500

 

Table 4.4: The bit-error rates using a low-pass filter with W,, = 0.99.

1

.3390
0.

0.3500

0.4368

 

Table 4.5: The bit-error rates using a low-pass filter with W" = 0.9.

CHAPTER 5
CONCLUDING REMARKS AND
RECOMMENDATIONS

There are some areas of this analysis where future research would be very bene-
ficial. One recommended tapic for future research is to classify attacks and char-
acterize each with an appropriate value of p for use with the statistical versions
of the new detectors.

Another recommended topic for future research is to derive a statistical model
for the methods using a different covariance matrix that encompasses more vari-

ables:

' 1
ade

2: d b f .a’ (5.1)

efc

 

 

In general, the decision rule will not be invariant to the choice of the covariance
parameters like it is in the existing method. More parameters used in the covari-
ance matrix may provide extra flexibility and better performance after a complete
classification of attacks is deveIOped. Fhrthermore, the methods discussed in this
thesis use a detector which treats different sets of wavelet coefficient triples inde-
pendently. Many attacks, in general, may not effect these triples independently
and a joint maximization of a likelihood ratio for all sets of wavelet triples could
be researched.

The last recommended tepic for future research is the examination of higher
embedding rates for the given watermarking methods. If the quantized values in
Fig. 3.2 were not modulus two, but rather modulus 2', then there is a possibility

36

of increasing the embedding rate to R = g. Note, due to the basic engineering

trade-ofis, this will decrease the other two competing factors.

37

 

BIBLIOGRAPHY

38

[1]

[2]

[3]

[4]

[5]

[6]

[7]

BIBLIOGRAPHY

M. D. Swanson, M. Kobayashi, A. H. Tewfik, “Multimedia Data—Embedding
and Watermarking Technologies,” Proceedings of the IEEE, Vol. 86, No. 6,
pp. 1064-1087, June 1998

Fabien A. P. Petitcolas, Ross J. Anderson, Markus G. Kuhn, “Attacks on
copyright marking systems”, in David Aucsmith (Ed), Information Hiding,
Second International Workshop, IH’98, Portland, Oregon, USA, April 15-17,
1998, Proceedings, LNCS 1525, Springer-Verlag, ISBN 3-540-65386-4, pp.
219-239

Fabien A. P. Petitcolas and Ross J. Anderson, “Evaluation of cepyright mark-
ing systems” To be presented at IEEE Multimedia Systems (ICMCS’99), 7—1 1
June 1999, Florence, Italy

Fabien A. P. Petitcolas. “Image Watermarking - StirMark” . [Online] Available
http: / / www.cl.cam.ac.uk/ users / fapp2 /steganography/

image.watermarking/stirmark/

R. B. Wolfgang, E. J. Delp, “A Watermarking Technique for Digital Imagery:
Further Studies,” Proc. of the Int. Conf. on Imaging Science, Systems, and
Technology, pp. 279-287, June 30 - July 3, 1997

B. Chen, G. W. Wornell, “An Information-Theoretic Approach To The De-
sign of Robust Digital Watermarking Systems,” Proc. of IEEE Int. Conf. on
Acoustics, Speech and Signal Processing, Vol. 4, pp. 2061-2064, March 1999

C. S. Burrus, R. A. Gopinath, H. Guo. “Introduction to Wavelets and Wavelet
'Ikansforms A Primer,” Prentice-Hall, Inc., New Jersey, 1998

39

[8] D. Kundur, D. Hatzinakos, “Digital Watermarking Using Multiresolution
Wavelet Decomposition,” Proc. of IEEE Int. Conf. on Acoustics, Speech and
Signal Processing, Vol.5, pp. 2969-2972, May 1998

[9] MD. Srinath, P.K. Rajasekaran, R. Viswanathan, “Introduction to Statisti-
cal Signal Processing with Applications,” Prentice Hall, Upper Saddle River,
New Jersey, 1996

[10] A. Ambardar, “Analog and Digital Signal Processing,” PWS Publishing Com-
pany, Boston, MA, 1995

40

 

 

"HHHHHHHHHH