$3. . , v
.. «A 2:.
«than. . «w? fink,
flfir‘rmln
in .2 .
(32:?

:n.

. 1.1 a
furl
{hula - .1

3 _,.
.% . “ragga.
.- 2‘
9!.

.1
31a 5.5%?(3. AI...
:rz: €15, Jii. 32m... . :5
1 ~ 3 \I‘r rifi‘r {Cr
a £9.91. 1.1. .a .fikmvnuh
15.11.. 3...! . he; a"
.11.»:

3
Luna».
91.3.er
vi 5h
..
..

2‘. x...
5‘57...
Ii

 

. ‘ ”Mu Antfiufii ufiws

.: f .6! ..l.. 1..

 

 

 

&Dfl

 

 

This is to certify that the
dissertation entitled

IMAGE WATERMARKING IN THE TIME-FREQUENCY
DOMAIN

presented by

MAHMOOD ALAYA AL-KHASSAWENEH

has been accepted towards fulfillment
of the requirements for the

Doctoral degree in Electrical and
Computer Engineering

 

 

 

Major Professor’s Signature

oS/H/o}

 

Date

MSU is an affinnative-action, equal-opportunity employer

—«-»-.-t—.—--.-._.-------—--.--._.—

_.-.-.-.-.-.—.— —~.-A—.-.--»—-

- —..—.—.--—-—-—-.—.-¢--—-.- -

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/07 p:/CIRC/Date0ue.indd-p.1

IMAGE WATERMARKING IN THE TIME-FREQUEN CY
DOMAIN

By

Mahmood Alaya Al-khassaweneh

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY
Electrical and Computer Engineering

2007

ABSTRACT

IMAGE WATERMARKIN G IN THE TIME-FREQUEN CY DOMAIN
By
Mahmood Alaya Al-khassaweneh

With the fast development of the internet and multimedia tools in the past decade,
the access and the unauthorized reproduction of digital data has become easier and
widespread. The ease of access to digital data brings with itself the challenge of
content protection. One way to address this problem is through digital watermark-
ing, which has become an important tool in copyright protection applications. The
watermarking algorithms proposed so far, focus on time or frequency domain rep-
resentations of the image. There have been only a few attempts to utilize the joint
time-frequency (spatial-spectral) characteristics of an image for watermarking. These
time-frequency domain watermarking attempts were mainly focused on detecting the
watermark rather than extracting it and did not provide a theoretical framework for
the performance analysis of the watermarking algorithms.

In this dissertation, we introduce three new image watermarking schemes in the
joint time-frequency domain to address these issues in image watermarking. The first
two methods embed the watermark in the time-frequency domain of the image us-
ing Wigner distribution. Two different methods for embedding the watermark in the
Wigner distribution are introduced; the Time-Wigner method where the watermark
is embedded directly into the Wigner distribution of the image, and the Wigner-
Wigner method where the Wigner distribution of the watermark is embedded in the
Wigner distribution of the image. The performance of the embedding algorithms and
the corresponding watermark detectors are analyzed. It is shown that embedding in

the time—frequency domain is equivalent to a non-linear embedding function in the

spatial domain. The third watermarking approach in the time—frequency domain uses
the local autocorrelation function of the image. The local autocorrelation function
for a subset of pixels chosen from the image is computed and the watermark is em-
bedded in the selected locations of the autocorrelation function. A blind detection
algorithm is derived and its performance is quantified by deriving the probability of
error. The proposed algorithm is shown to be transparent and robust under attacks.
A comparison of the proposed methods with a discrete wavelet transform (DWT) do—
main based or/ and spread spectrum (SS) methods is illustrated through simulations.
The detailed analysis of the proposed time-frequency watermarking algorithms shows
that looking at this joint domain improves watermarking capacity and robustness

compared to existing methods.

To my wife and beloved parents

iv

ACKNOWLEDGMENTS

First and foremost, I would like to express my sincere thankfulness to my parents
Alaya and Jamilah Al-khassaweneh for their unconditional support, love, and caring
which helped me with the journey of life and graduate studies with humility and
honesty. I am also grateful to my wife Esraa Al-Sharoa for her encouragement, advice
and patience. Her support kept me working hard to achieve this. I would also like
to thank my little son Ahmad, who kept me awake all night studying. I would also
like to express my gratitude to all my brothers, sisters, and my family in-law for their
sincere wishes and encouragement. Especial thanks to my brother Mazin khasawneh,
his wife Manar, and their daughter Leen for the help, guidance, and being the best
friends.

This dissertation would not have been possible without the able guidance and valu-
able comments and inputs from my advisor Dr. Selin Aviyente. Dr. Selin Aviyente
gave me a break from my mundane life as a programmer and software engineer into
the challenging and interesting world of science and engineering. I am grateful for
her intellectual and financial support, inspiration, freedom of work, invaluable advice
and the trust that gave me the confidence to make the right decisions throughout
my graduate studies. My advisor, Dr. Selin Aviyente is not only great visionary
scientist with renowned reputation, but she is also very kind and gentle individual I
have known. In addition, I am very grateful to my committee members: Dr. Huyder
Radha, Dr. John Deller, and Dr. Anil Jain for their guidance and for teaching me

many useful courses in electrical and computer engineering.

TABLE OF CONTENTS

LIST OF TABLES ................................. ix

LIST OF FIGURES ................................ x
CHAPTER 1

Introduction ..................................... 1

1.1 General Scheme .............................. 2

1.2 Visible and Invisible Watermarks .................... 3

1.3 Applications ................................ 5

1.4 Requirements ............................... 6

1.5 Domains used for Image Watermarking ................. 7

1.6 Performance Measures .......................... 10
CHAPTER 2

Watermarking in the Time-Frequency Domain .................. 12

2.1 Background On Time-Frequency Distributions ............. 13

2.2 Previous Work on Image Watermarking in the Time-Frequency Domain 16

2.3 Contributions of this Dissertation .................... 18
CHAPTER 3

The Time-Wigner Watermarking Method .................... 20

3.1 Watermark Embedding .......................... 21

3.2 Error Introduced in the Inversion Process ................ 25

3.3 Watermark Detection for the Gaussian Case .............. 28

3.4 Watermark Detection for the Binary Watermark Sequence Case . . . 31

3.5 Simulation Results and Comparison ................... 34

3.5.1 The Choice of the Watermark Length .............. 36

3.5.2 Additive White Gaussian Noise (AWGN) ............ 37

3.5.3 Median Filtering ......................... 38

3.5.4 Rotation .............................. 40

3.5.5 JPEG Compression ........................ 41

3.5.6 Comparison between the Time-Wigner and the Spread Spec-

trum Methods ........................... 42

3.6 Discussion ................................. 56

3.7 Summary ................................. 57

vi

CHAPTER 4
The Wigner-Wigner Watermarking Method ...................

4.1

Watermark embedding ..........................

4.2 Error Introduced in the Inversion Process ................

4.3 Watermark Detection for the Gaussian Case ..............
4.4 Watermark Detection for the Binary Watermark Sequence Case

4.5 Simulation Results and Comparison ...................

4.5.1 The Performance under AWGN, Median Filtering, Rotation,

and JPEG Compression .....................

4.5.2 Comparison between the Wigner-Wigner and the Wavelet

Methods ..............................

4.6 Discussion .................................

4.7 Summary .................................

CHAPTER 5

Watermarking in the autocorrelation domain ...................

5.1 Background ................................

5.2 Watermark Embedding ..........................

5.3
5.4
5.5

5.6
5.7

Watermark Extraction ..........................
Analysis of the Algorithm under Attacks ................

Simulation Results and Comparison ...................
5.5.1 Comparison between Autocorelation, Wavelet, and Spread

Spectrum Methods ........................
5.5.2 Results for the Binary Logo Case ................

Discussion .................................

Summary .................................

CHAPTER 6
A Comparative Study of The Three Proposed Time-Frequency Watermarking

Methods .......................................

6.1

6.2

Comparison between the Three Time-Frequency Domain Watermark-
ing Methods ................................
6.1.1 Computational Complexity ....................
6.1.2 Capacity ..............................
6.1.3 Non-Blind and Blind Detection .................
6.1.4 Robustness ............................

Techniques for Performance Improvement ................
6.2.1 Pseudo-random Watermark Generator .............

vii

60
61
64
68
70
71

73
79
80

82
83
85
89
92
94

97
102

105
107

109

109
112
112
113
113

116
116

6.2.2 Reference Watermark ....................... 118

CHAPTER 7

Conclusions and Future Work ........................... 121
7.1 Summary of the Dissertation ....................... 121
7.2 I‘Mture Work ................................ 122

APPENDICES ................................... 124
A2 Detector derivation for the Time-Wigner method ........... 125
A3 Detector derivation for the the Wigner-Wigner method ........ 127

BIBLIOGRAPHY ................................. 132

viii

Table 1.1
Table 3.1

Table 3.2

Table 4.1

Table 4.2

Table 5.1

Table 5.2

Table 6.1

Table 6.2

LIST OF TABLES

Summary of some well-known watermarking algorithms ......

The average Normalized Mean Square Error introduced by the ap-
proximation of the Wigner distribution in Time-Wigner method. .

Average bit error rate in detecting the watermark under different
attacks using 100 different images. .................

The average Normalized Mean Square Error introduced by the ap-

proximation of the Wigner distribution in Wigner-Wigner method.

Average bit error rate in detecting the watermark under different
attacks using 100 different images. .................

Average bit error rate in detecting the watermark under different
attacks using 100 different images. .................

Bit error rate in detecting the watermark under different attacks
for different values of c. .......................

A comparison between the Wigner-based methods and the auto-
correlation method ...........................

Bit error rate in detecting the watermark with and with out using
pseudo-random watermark generator ................

ix

64

72

95

96

116

118

Figure 1.1
Figure 3.1

Figure 3.2

Figure 3.3
Figure 3.4
Figure 3.5
Figure 3.6
Figure 3.7

Figure 3.8
Figure 3.9

Figure 3.10

Figure 3.11
Figure 3.12

Figure 3.13

Figure 3.14
Figure 3.15

Figure 3.16

Figure 3.17

LIST OF FIGURES

A general watermarking scheme. ..................
The block diagram for the watermark embedding in the Time-
Wigner method .............................
The average histogram for the difference of the two Wigner distri-
butions in the Time-Wigner method. ................
PSN R versus number of bits. ....................
The ROC curves for different watermark lengths. .........

The original Lena512 image ......................
The watermarked Lena512 image with PSNR=62dB. .......

The normalized correlation detector response for the Time-
Wigner method applied to Lena512 image under AWGN with
different PSNRs, a. PSNR=48.13dB,b. PSNR=28.13dB, c.
PSNR=14.15dB, d. PSNR=8.13dB ..................

The watermarked image degraded by AWGN (PSNR=14.15dB). .

The probability of false alarm versus the threshold under AWGN
with PSNR=28.18dB. ........................

The normalized correlation detector response for the Time—Wigner
method applied to Lena512 image under median filtering with dif-
ferent filter sizes, a. size=3 x 3,b. size=5 x 5, c. size=7 x 7, d.
size=16 x 16. .............................

The watermarked image degraded by median filter of size 9 x 9. .

The probability of false alarm versus the threshold under median
filtering with filter size=4 x 4 .....................

The normalized correlation detector response for the Time-Wigner
method applied to Lena5l2 image under rotation with different
angles, a. degree=1°,b. degree=3°, c. degree=5°, d. degree=7°. .

The watermarked image degraded by rotation of 7° .........

The probability of false alarm versus the threshold under rotation
of 3°. .................................

The normalized correlation detector response for the Time-Wigner
method applied to Lena5l2 image under JPEG compression with
different compression ratios, a. CR=2,b. CR=8, c. CR=20, d.
CR=37. ................................

The watermarked image degraded by JPEG compression with
CR=37. ................................

22

27
37
38
39
40

41
42

47
48

49

50

Figure 3.18

Figure 3.19

Figure 3.20

Figure 3.21

Figure 4.1

Figure 4.2

Figure 4.3
Figure 4.4
Figure 4.5

Figure 4.6

Figure 4.7

Figure 4.8

Figure 5.1

Figure 5.2

Figure 5.3
Figure 5.4

Figure 5.5

Figure 5.6

The probability of false alarm versus the threshold under JPEG
compression with CR=20. ......................

Comparison between spread spectrum and Time-Wigner methods
under AWGN ..............................

Comparison between spread spectrum and T ime-Wigner methods
under Median Filtering.

Comparison between spread spectrum and Time-Wigner methods
under JPEG compression. ......................

The block diagram for the watermark embedding in the Wigner-
Wigner method .............................

The average histogram for the difference of the two Wigner distri-
butions in the Wigner-Wigner method ................

PSNR versus number of bits.
The watermarked Lena512 image with PSNR=80.2dB. ......

The normalized correlation detector response for the
Wigner-Wigner method applied to Lena5l2 image under, a.
AWGN=14.5dB,b. Median Filtering size=7 x 7, c. Rotations 1°,
d. JPEG CR=20 ............................

Comparison between the DWT and Wigner-Wigner methods under
AWGN.

Comparison between the DWT and Wigner-Wigner methods under
Median Filtering ............................

Comparison between the DWT and W igner—Wigner methods under
JPEG compression ...........................

The block diagram for the embedding algorithm for the autocorre-
lation method.

oooooooooooooooooooo

oooooooooooooooooooooooooooooooo

The block diagram for the watermark extraction algorithm for the
autocorrelation method.

The watermarked image with PSNR=44.5dB using c = 0.2 .....

Comparison between SS, DWT, and Autocorrelation methods un-
der AWGN.

Comparison between SS, DWT, and Autocorrelation methods un-
der Median Filtering ..........................

IIIIIIIIIIIIIIIIIIIIIIIIIIIIII

Comparison between SS, DWT, and Autocorrelation methods un-
der JPEG compression.

OOOOOOOOOOOOOOOOOOOOOOO

xi

52

53

54

55

66

67
73
74

75

77

78

86

91
97

99

100

Figure 5.7

Figure 5.8

Figure 5.9

Figure 6.1

Figure 6.2

Figure 6.3

Figure 6.4

The extracted logo under different attacks a- AWGN
(PSNR=22.11dB), b— JPEG (CR=7.7), c- Rotation (7 degrees),
and d— Median filtering (5 x 5). ...................

The extracted logo after subsequent attacks of 1- AWGN
(PSNR=28.13dB), 2- JPEG (CR=5), 3— Rotation (3 degrees), and
4- Median filtering (3 x 3) .......................

Comparison in computing the probability of error from the simu-
lations and the analytical results in equation (5.27) .........

The normalized correlation detector response for the autocorrela-
tion method with two embedded watermarks under AWGN with

PSNR=22.1dB .............................

Comparison between Time—Wigner (TW), Wigner-Wigner (WW),
and autocorrelation (AC) methods in terms of PSN R versus num-
ber of watermark bits ........................

Comparison between Time-Wigner (TW), Wigner-Wigner (WW),
and autocorrelation (AC) methods under AWGN attack .....

Comparison between using and not using the reference watermark
for the Wigner-Wigner method under AWGN ............

xii

103

104

106

111

115

120

CHAPTER 1

INTRODUCTION

The digital information revolution has brought profound changes in our lives. Along
the many advantages, this revolution has also generated new challenges and new
opportunities for innovation [1, 2]. The availability of powerful software and new
devices, such as digital camera and camcorder, high quality scanners and printers,
digital voice recorder, MP3 player and PDA, have reached consumers worldwide and
enable them to create, manipulate, and enjoy the multimedia data.

Internet and wireless network offer an easy way to deliver and exchange informa-
tion. The security and fair use of the multimedia data, as well as the fast delivery of
multimedia content to a variety of end users/devices are important, yet challenging
issues. This ease of access to digital data brings with itself the challenge of content
protection. Some common attacks on digital data include illegal access to the trans-
mitted data, data content modification, and production and re-transmission of illegal
copies. The solutions to these problems will not only contribute to our understanding
of this fast moving complex technology, but will also offer new economic opportuni-
ties to be explored. Watermarking and encryption techniques were developed in order
to provide copyright protection for digital data. Encryption protects the data from
piracy attacks during transmission and once the data is received and decrypted, it is
no longer protected. On the other hand, watermarking embeds a secret watermark
into the original data in a way such that it is always present [3].

Although the concept of watermarking (information hiding) has been mentioned
thousands years ago [4], it did not see the light and the attention from researchers
except in the past two decades. Research on watermarking has made considerable

progress in recent years and attracted attention from both academia and industry.

Techniques have been proposed for a variety of applications, including ownership
protection, authentication, access control, and annotation [5]. Watermarking is also
found useful as a general tool to send side information in multimedia communication
for achieving additional functionalities or enhancing performance. Imperceptibility,
robustness against moderate processing such as compression, and the ability to hide
many hits are the basic but rather conflicting requirements for many data hiding
applications. Several watermarking techniques have been proposed for different mul-
timedia data, like image, video and audio signals [6, 7, 8, 9, 10, 11]. Each data
type has it is own characteristics and is treated uniquely when it is watermarked
[12, 13, 14, 15, 16]. The focus of this dissertation is on image watermarking.

This chapter is organized as follows. In Section 1.1, the different stages in a general
watermarking scheme are discussed. Types, applications, and requirements for the
watermark are discussed in Sections 1.2 through 1.4. While Section 1.5 talks about
the domains used for watermarking, Section 1.6 summarizes the major measures used

to evaluate the performance of a given watermarking algorithm.

1 . 1 General Scheme

A general watermarking scheme is illustrated in Figure 1.1. The main components
in any watermarking scheme are the encoder and the decoder. The encoder embeds
the watermark, to, inside the original image, I , using an embedding function, E, to

produce the watermarked image, f. Mathematically this can be represented by,

i: E(I,w), (1.1)

where the embedding function, E, can operate in the spatial domain or some trans-
form domain and can have additive or multiplicative form. On the other hand, the

decoder, D, tries to extract or detect the original watermark from the watermarked

image, which is possibly corrupted by attacks,

a = D(i,1), (1.2)

where the decoder may or may not use the original image for detecting or extracting
the watermark. Depending on the nature of the embedder and the way the watermark
is inserted, the watermark may be extracted in the exact form or may be detected.

Detecting the watermark can verify the ownership, while extracting it can prove the

ownership.

1.2 Visible and Invisible Watermarks

Watermarking techniques can be classified in terms of perceptibility into two groups,
perceptible and imperceptible hiding. In perceptible watermarks, a visually mean-
ingful message, such as a logo, is embedded inside the image, which is essentially
an image editing or synthesis problem. The visible watermarks explicitly exhibit the
copyright, ownership information, or access control policies so as to discourage the
misuse of the watermarked images [17, 18]. For example, semitransparent logos are
commonly added to the preview images accessible via World Wide Web by copyright
holders. In [17], a visible watermarking technique is proposed by modifying the lumi-
nance of the original image according to a binary or ternary watermark pattern. The
same amount of modification is applied to the local luminance to give a consistent
perceptual contrast [19]. In addition, the modification is modulated by a random
generated sequence to make it difficult to systematically remove the visible marks via
an automated algorithm.

In most copyright and digital rights managements applications invisible water-
marks are preferred [20, 21, 22]. Invisible watermarks are used for content and author

identification in order to be able to determine the origin of an image. They can also

AWGN JPEG Original
Watermark lm ge

 

 

Extracted
Original watermark
Image _ Encoder Decoder ___._.

 

 

 

 

 

 

 

Key Rotation Filtering Key

Figure 1.1. A general watermarking scheme.

be used in unauthorized cepies detection either to prove ownership or to identify a
customer. The invisible scheme does not intend to forbid any access to an image but
its purpose is to be able to tell if a specified image has been used without the owner’s
formal consent or if the image has been altered in any way. This approach is the one
that has received the most attention in the past couple of years and it is also the

focus of this dissertation [23, 24, 25].

1.3 Applications

Although the original motivation for watermarking was copyright protection, it has

since then been used in different applications. Some common applications of water-

marking include [26, 27]:

1. COpyright protection: For copyright protection, a watermark indicating owner-
ship is embedded in the original image. The watermark, which is known only to
the copyright holder/ owner, should survive common processing and intentional
attacks so that the owner can show the presence of this watermark in case of
dispute to demonstrate the ownership of that particular image. In this applica-
tion, the goal is watermark detection rather than extraction. The probability
of detection should be high and the algorithm should have a low false alarm

rate. The total the number of bits that can be embedded are not necessarily

high [28].

2. Fingerprinting: In fingerprinting, the hidden data (watermark) is used to trace
the originator or the recipients of the image. For example, different watermarks
are embedded in different copies of the image before distributing to a number
of recipients. The robustness against obliterating and the ability to convey a

non-trivial number of bits are required [29].

3. Authentication: A watermark is embedded in the image, and is used later
to determine whether the original image is tampered or not. The robustness
against removing the watermark or making it undetectable is not a concern as
there is no such incentive from the attacker’s point of view. However, forging
a valid authentication watermark in an unauthorized or tampered image must

be prevented [30].

4. Annotation: In annotation, the goal is to embed a large number of bits inside

the original image. Although the robustness against intentional attack is not
required, some degree of robustness against common processing attacks are
desirable. The original host image, preferably, should not be used to extract

the watermark in this application [31].

1 .4 Requirements

Most watermarking algorithms try to satisfy the following main requirements [32, 33,

34] :

1. Perceptual Transparency: The characteristics of the Human Visual System

(HVS) are used to assure that the watermark is not visible. Basically, per-
ceptual transparency means that a watermarked image should look identical
to the original one, which means one should not notice any degradation in the

perceived quality. Transparency is a basic requirement of digital watermarking.

. Robustness: The watermark should be detected by an authorized user after the

image has undergone attacks such as additive white Gaussian noise (AWGN),
compression, filtering, etc. Ideally, the amount of image distortion necessary to
remove the watermark should degrade the desired image quality to the point of

becoming commercially valueless.

. Capacity: A watermarking system must allow for a useful amount of information

to be embedded into the image. Depending on the application, the amount of

data can vary from a single bit to multiple bits [35].

. Computational complexity: The watermark system should not be computation-

ally complex especially for applications where real-time embedding is desired.
Moreover, reducing the number of computations means low cost in designing

the hardware for the watermarking algorithm.

Therefore, the general goal of watermarking is to produce a modified data that

looks exactly the same as the original data but still contains the watermark that could

be used for copyright authentication.

1.5 Domains used for Image Watermarking

The two most common methods used for watermarking digital images are the spatial
and the spectral domain methods [36, 37, 38, 39]. The spatial domain methods
choose regions of the image according to texture, edges or a random partitioning and
embed the watermark in the selected regions [40, 41, 42, 43, 44, 45, 46]. Although the
watermarked image is identical to the original one, it is not in general robust to the
basic image processing attacks [47, 48, 49]. The spectral domain methods transform
the image into the spectral domain using transform methods such as Discrete Cosine
Transform (DCT), Discrete Fourier Transform (DFT), Discrete Wavelet Transform
(DWT), Fourier Mellin Transform and then mark it in the transform domain [50,
51, 52, 53, 54]. In this case, the watermark is inserted in the perceptually significant
parts of the image so that it is robust.

Transform domain methods have several advantages over the spatial domain meth-
ods [54]. First, they are more robust, since the watermark is inserted in the percep-
tually significant parts of the image, which corresponds to the mid-frequency range.
This range can be easily found in the transform domain [55, 56]. Second, they resist
the compression attacks. Since most compression techniques operate in the frequency
domain, it is easier to develop a watermarking scheme in the transform domain that
overcomes possible compression. Third, some transform domain algorithms are ro-
bust against specific geometric transformations such as DFT which is robust to most
affine transformations [57].

Spread spectrum is a common technique used for watermarking in both the spatial

and the transform domains [58, 59, 60, 61, 62]. The idea is to spread the watermark

over certain pixels of the image. As an example, in [63], where the watermark is
embedded in the DCT domain of the image, the authors assume the watermark to be
an independent and identically distributed Gaussian random vector that is impercep-
tibly inserted in a spread-spectrum-like fashion into the perceptually most significant
spectral components of the data. It has been shown that the watermark is robust
to signal processing operations such as lossy compression, filtering, digital-analog
and analog-digital conversion, requantization, and common geometric transforma-
tions such as cropping, scaling, translation, and rotation. Since the introduction of
the original spread spectrum approach, many developments have been made on the
method described in [63] such as using different transform domains to embed the wa-
termark, and the introduction of blind watermark detection algorithms [64, 65, 66].
In [65], the authors propose a multi-bit watermarking algorithm which is based on
the idea of spreading the watermark bit over many pixels of the original image us-
ing code-division multiplexing. The proposed method has a deterministic watermark
embedding scheme that assures total embedding efficiency. Unlike [63], where the
watermark is spread out in the DCT domain, the watermark in [65] is embedded
in the spatial image domain. Many spread spectrum algorithms have the following
limitations [67]:

1. Spread spectrum, in general, allows the detection of the watermark rather than

extraction.

2. If the energy of the watermark is reduced because of fading-like distortions, it

will lead to unreliable detection of the watermark [69].

3. Most of the spread spectrum techniques do not take into account the non-

stationarity of the original image or the attack interference.

An example for using the DWT domain for watermarking is in [68]. In [68], the

authors embed the watermark by quantizing certain DWT coefficients in different

subbands. The watermark is extracted without the need of the original image. An-
other well-known watermarking method in the transform domain is [52]. In [52], the
authors present a watermarking algorithm in the wavelet domain. The watermark
is masked according to the characteristics of the human visual system (HVS), where
masking is accomplished pixel by pixel by taking into account the texture and the
luminance content of all the image subbands. The watermark consists of a pseudoran-
dom sequence which is adaptively added to the largest detail bands. The watermark
is detected by computing the correlation between the watermarked coefficients and
the watermarking sequence without refereing to the original image.

Although transform domain algorithms have more advantages in providing ro-
bustness, sometimes it is difficult to satisfy imperceptibility constraints in the spatial
domain simultaneously with the spectral domain constraints. In order to take full ad-
vantage of both the spatial and the spectral domains, researchers have started looking
at the joint time-frequency representation of the image, which gives a more compre-
hensive representation of the image compared to looking at each domain individually
[70, 71, 72, 73, 74]. This approach also provides flexibility in the amount of data that
can be hidden inside an image. The use of joint time—frequency domain is the focus
of this dissertation. Table 1.1 summarizes some well-known watermarking algorithms

in literature.

Table 1.1. Summary of some well-known watermarking algorithms

 

 

 

 

 

 

 

 

 

 

Method Domain Multi-bit Blind
Barni, etc. [52] Transform (DWT) Yes Yes
Cox, etc. [63] Transform (DCT) Yes No
Mayer, etc. [65] Spatial Yes No
Kundur, etc. [68] Transform (DWT) Yes Yes
Stankovic, etc. [70] Time-frequency (Wigner) No No

 

 

1 .6 Performance Measures

In order to evaluate a watermarking algorithm, certain sets of measures should be met.
Although, there are no agreed-upon sets, most work in the watermarking literature

use the following measures for performance evaluation [75]:

1. Imperceptibility: For invisible watermarking method, the watermark should be
imperceptible and the human eye should not be able to distinguish between the
watermarked and the original images. This measure is subjective, and thus is

not always a reliable way of evaluating the watermarking algorithm.

2. Peak Signal to Noise Ratio (PSNR): This measure is related to imperceptibility,
where having higher PSNR means higher imperceptibility. This quantitative

measure is given for an N x N image by,

2
PSNR(dB) = 1010g10 25° 2 , (1.3)

.151? 2 (Kay) - 1(x,y))
xly

 

where f (1:, y) and [(33, y) are the watermarked and the original images, respec-

tively. For a good watermarking algorithm, the PSN R value should be above

30dB.

3. Correlation Coefficient: This is a measure between the extracted and the origi-
nal watermark, where higher correlation value means the extracted watermark

is the one of interest. This measure is mathematically given by,

Z w(y)'u3(y)
(10,222) = y .
V2 102(31) 217220;)
31 y

 

 

10

where, w and ti) are the original and extracted watermarks, respectively.

. Probability of Error: This measure is used to study the probability of detecting
a false watermark and assume that it is the correct one, i.e., probability of false
alarm, PFAv and detecting the correct watermark and assume that it is the

false one, i.e., probability of miss, PM. The probability of error in terms of

PF A and PM is given by,

Pe =P0PFA +P1(PM)- (1-5)
where, p0 and p1 are the a priori probabilities.

. Other Performance Measures: There are other performance measures which are
application dependent. For example, complexity is an issue if the watermarking
is done in real time, while it is not an issue for applications where the embedding
can take place offline. Alternatively, the time needed for the watermarking

algorithm is another issue, especially if the algorithm is to be implemented by

hardware.

The rest of this dissertation is organized as follows. Chapter 2 gives some back-

ground on time—frequency distributions and summarizes previous watermarking meth-

ods in the time-frequency domain. Chapters 3 through 5, introduce the Time-Wigner

method, the Wigner-Wigner method, and the autocorrelation method, respectively.

The derivation and the analysis for the embedding and the detection/extraction al-

gorithms are given for each method. Moreover, simulation results to evaluate the

performance of the proposed algorithms and comparisons with existing methods are

provided. Chapter 6 gives a detailed comparison of the three methods proposed in

this dissertation and offers techniques for performance improvement. Finally, Chapter

7 concludes this dissertation with a summary of contributions and future work.

11

CHAPTER 2

WATERMARKING IN THE TIME-FREQUEN CY DOMAIN

Time-frequency distributions are well-known signal representation tools that have
been used in a variety of applications including signal detection, classification, and
analysis [76]. Despite their widespread use in analyzing non-stationary signals, their
application to the signal watermarking problem has been limited until recently. Al-
though time—frequency analysis identifies the time at which various signal frequencies
are present, the difficulty of implementing and understanding these distributions,
limited their usage especially in the case of image watermarking, for which the time-
frequency distribution is a four dimensional distribution. Despite these challenges,
the representation of the energy of the signal simultaneously in time and frequency
makes time-frequency distributions a strong candidate for the watermarking problem.

In this chapter, we give a brief background on time-frequency distributions in
general and on Wigner distribution in particular. The main properties of Wigner
distribution are discussed in detail. After a brief introduction to time-frequency dis-
tributions provided in Section 2.1, we summarize some of the recent work in the area
of watermarking in the joint time-frequency domain and discuss the major properties
of these methods in Section 2.2. Finally, Section 2.3 summarizes the contributions of

this dissertation to watermarking in the joint time-frequency domain literature.

12

2.1 Background On Time-Frequency Distributions

Time-frequency distributions are bilinear transforms of a signal that represent the
energy distribution over time and frequency [77, 78]. The need for a combined time-
frequency representation stemmed from the inadequacy of the individual time domain
and frequency domain analysis to fully describe the nature of non-stationary signals.
A time-frequency distribution of a signal provides information about how the spec-
tral content of the signal evolves with time, thus providing an ideal tool to dissect,
analyze, and interpret non-stationary signals. This is performed by mapping a one
dimensional signal in the time domain, into a two dimensional time-frequency rep-
resentation of the signal. A variety of methods for obtaining the energy density of
a function, simultaneously in the time and the frequency have been devised, most
notably the short time Fourier transform and the Wigner distribution. The general

class of bilinear time-frequency distributions, named Cohen’s class of distributions

[76], are defined as,

C(t,w) = 4—i2—///3*(t -— ér)s(t + ér)¢(6,T)ej(_0t—Tw+wt)dtdrd0, (2.1)

where ¢(6, 7') is a two dimensional function called the kernel. The kernel determines

the distribution and its properities.

Among many time-frequency distributions, Wigner distribution has received the
most attention in the watermarking literature. Wigner distribution is a well-known
member of the Cohen’s class of distributions, for which ¢(6,T) = 1. For a one-

dimensional continuous time signal, 3(t), Wigner distribution is defined as,

W(t,w) = -21—W/OO s (t + g) 8* (t — %) e—jWTdT, (2.2)

13

where T is the time lag variable. Equation (2.2) suggests that to find the Wigner
distribution at a particular time, we sum the sequence obtained from the product
of the signal at a past time, 7', with the signal at a future time, 7'. This product,

3 (t + 5) 3* (t — 5), is called the autocorrelation function and it will be discussed in

detail in Chapter 5.

This definition can be extended to the discrete-time domain. For a one-

dimensional discrete time signal, 3(n), of length N, the Wigner distribution is,

WD(n,w) = 2 Z s(n + m)s*(n — mks—3'27””, (2.3)

m=—oo

where n and w = 27rk/N are the time and the frequency variables respectively.
Wigner distribution has many properties that make it a good choice for water-
marking applications. First, it satisfies the frequency and the time marginals which

makes it a valid energy distribution. The time and frequency marginals are given by,

Z womb) = |s(n)|2, (2.4)

and

Z WD(n, w) = [S(w)|2, (2.5)

respectively. Second, it is invertible, i.e. the signal can be retrieved from its Wigner

distribution up to a phase constant as:

5(t) = 55:76; 1:141 (30.)) ejtwdw. (2.6)

For real and positive valued discrete time signals, the signal can be retrieved from its

14

Wigner distribution as,

 

3(n) = \[Z WD(n,w). (2.7)

Equation (2.7) implies that for a positive real—valued signal, the original signal
can be retrieved from its Wigner distribution by taking the square root of the inverse
Fourier transform of the Wigner distribution evaluated at m = 0. Finally, the Wigner
distribution of a real signal is even symmetric. These properties will simplify the
embedding and detection algorithms in image watermarking.

The invertibility property in equation (2.7), which is valid for images, is not valid
for general signals, where the signal is not necessarily positive or real-valued. Many
algorithms have been proposed for synthesizing a time signal from a given Wigner
distribution. In [79, 80], the signal is computed for even and odd indices separately
through performing the eigen-decomposition of the autocorrelation matrix. In [81, 82],
the signal is synthesized using a set of basis functions. The authors in [81, 82], for-
mulate the synthesis problem as approximating a two—dimensional function. This
two-dimensional function is formulated as a product of two one-dimensional func-
tions using two least square procedures. The first procedure involves expressing a
time-frequency function as a bilinear combination of the basis auto and cross-Wigner
functions. The least squares approximation leads to an eigenvalue-eigenvector decom-
position of a symmetric matrix. The second procedure involves the approximation of
a pre—computed matrix as an outer product of two vectors. In [83], the synthesis is
accomplished by using a reference signal known a priori or found iteratively. The most
recent method for synthesizing the signal given its Wigner distribution was developed
in [84] by finding the discrete-time signal whose Wigner distribution best matches a
specified time-frequency distribution in the sense of the least mean squared error.

The effectiveness of Wigner distribution in signal analysis has inspired researchers

to adapt this distribution to image processing. Wigner distribution has been extended

15

to two-dimensional signals such as images in [85] as,

WD(n1,n2, ’61, k2) =

N N
—1 -1
2 7 -47r
— ' . k -l- , k
E E 3(n1+m1,n2+m2)s*(n1—m1,n2 -m2)e JNWI 1 7772 2).
N
m1=—-2-m2=--2—
(2.8)

This extension yields a four-dimensional representation which makes it difficult to
interpret the resulting distribution and increases the computational complexity. For
an N x N image this creates N 4 watermarkable points. However, due the computa-
tional complexity and the difficulty of interpreting these points, in this dissertation,
we find the Wigner distribution for a subset of pixels of the image using equation
(2.3). For an N x N image, the one-dimensional Wigner distribution creates N3
watermarkable points. Although there is a reduction in the number of watermark-
able cells by a factor of N, the distribution in equation (2.3) is easier to implement
and visualize, less computationally complex, and still provides N 3 watermarkable

cells which is higher than the N 2 cells, which are available in the individual time or

frequency domains.

2.2 Previous Work on Image Watermarking in the Time-Frequency Do-
main

The idea of watermarking in the joint time-frequency domain has attracted some

attention in recent years. Most of the recent work has concentrated on using the

Wigner distribution as the signal transform before embedding the watermark. Many

researchers use equation (2.3) to find the Wigner distribution of an image by scanning

it row by row or choosing a subset of pixels from the original image. For example, in

[70], the authors used a two-dimensional chirp signal with a variable spatial frequency

16

as the watermark. The watermark is characterized by a linear frequency change and
can be detected by using two-dimensional (2-D) time—frequency distributions. The
projections of the 2—D Wigner distribution and the 2-D RadonWigner distribution
are used in the watermark detection process. Although the authors were able to
detect the watermark efficiently under most attacks, there was no discussion on the
extraction of the watermark and there was no theoretical analysis of the performance
of the method. Moreover, the algorithm did not discuss the potential for multi-bit
watermarking.

In [71], the Wigner distribution is used for watermark embedding. The watermark
is embedded in a subset of the transformed cells in the Wigner domain. These cells
are selected such that the watermark will survive the JPEG compression. Since
the resultant watermarked distribution is not a valid Wigner distribution, the time
signal that has the closest distribution in the mean square error sense is found [82].
Although this algorithm detects the presence of the watermark under J PEG attacks,
no experimental results for other types of attacks are reported. Moreover, the error
in detecting the watermark was not studied and the extraction of the watermark was
not discussed.

In [73], a fragile image watermarking method using Wigner distribution is pre-
sented. The watermark is an FM modulated signal which is embedded in the diagonal
elements of the image. The particular features of this signal in the time-frequency
domain are used to identify the watermark. The Wigner distribution is used to ex-
tract the watermark. Since the focus of this method was fragile watermarking, no
study on the robustness of the proposed algorithm has been done.

Time-frequency distributions have also been used for audio watermarking. The
authors in [74], present a non-blind, robust watermarking scheme for audio signals.
The watermarking algorithm is based on the Singular Value Decomposition (SVD) of

the spectrogram of the signal. The SVD of the spectrogram is modified adaptively

17

according to the watermark message.

In this dissertation, we introduce three new methods for embedding the watermark
into the image using the Wigner distribution. For simplicity, we assume that we have
an N x N image and a watermark sequence of length N. The first method, T ime-
Wigner method, embeds the watermark directly into the Wigner distribution of the
image, while the second one, Wigner-Wigner method, embeds the Wigner distribution
of the watermark into the Wigner distribution of the image. The third method makes
use of the autocorrelation domain, which is related to the Wigner distribution through

a Fourier transform, and uses it for watermark embedding.

2.3 Contributions of this Dissertation

In this dissertation, we introduce three new image watermarking methods in the
joint time-frequency domain. Unlike the previous work in the time-frequency do-
main, a complete mathematical analysis is provided for both embedding and detec—
tion/extraction stages. The proposed methods put no constraints on the character-
istics of the watermark such as parameterizing it as a linear chirp as in previous
work. Moreover, we introduce a multi-bit watermarking algorithm which is suitable
for hiding larger amounts of data. We also compare the proposed joint time-frequency
watermarking algorithms with the current time and frequency domain methods.

The first class of algorithms will develop two new watermarking methods that
combine the spatial and the spectral domains, for both embedding and detection.
The first method consists of embedding the watermark directly in the Wigner distri-
bution of the image, the Time-Wigner method, while the second method consists of
transforming the watermark into the Wigner domain and then embedding it into the
Wigner distribution of the image, the Wigner-Wigner method. The corresponding
detection algorithms are also derived [86, 87].

We also introduce a new image watermarking method that is equivalent to wa-

18

termarking in the Wigner domain. The watermark is embedded in the local auto-
correlation domain. The autocorrelation function is related to the Wigner distribu-
tion through a Fourier transform and has no aliasing and inversion problems. The
time-varying autocorrelation function for randomly chosen pixels is found and the
watermark is embedded such that the modified autocorrelation is still a valid auto-
correlation function. This will ensure the invertibility of the autocorrelation function
and will enable us to extract the embedded watermark bits [88].

In the following chapters, we discuss each method in detail. The embedding and
detection /extraction algorithms are derived, the simulation results are provided, and
a comparison with existing time and / or frequency based watermarking methods are

carried out for each proposed method.

19

CHAPTER 3

THE TIME-WIGN ER WATERMARKING METHOD

In this chapter, the Time-Wigner method which embeds the watermark sequence
directly into the Wigner distribution of the image is introduced. The idea of embed-
ding the watermark in the transform domain is a common idea used with Discrete
Cosine Transform (DCT), Discrete Fourier Transform (DFT) and Discrete Wavelet
'Iiansform (DWT) domains [55, 68]. However, spreading the watermark in the joint
time-frequency domain is a very recent idea and not much work has been done in this
area. Similar to embedding the watermark in the transform domain, i.e. DCT, DFT,
and DWT, the proposed method can be thought of as spreading the sequence in the
joint-time frequency domain.

In the proposed method, the Wigner distribution for a subset of pixels chosen from
the original image is computed. The watermark, which could be either a Gaussian
distributed sequence or a binary sequence, is embedded inside the Wigner distribution
of the chosen pixels such that the watermarked distribution is as close as possible to
a valid Wigner distribution. The embedding algorithm is simplified to a non-linear
function in time which makes the embedding less computationally complex.

Two detection algorithms for the Gaussian and the binary watermark cases are
derived and their performances are quantified through an analysis of the probability
of error. In addition, the performance of the Time-Wigner method is compared with
the well-known spread spectrum method [63] to demonstrate the robustness and the
potential of the proposed method.

This chapter is organized as follows. Section 3.1 gives a detailed analysis of the
watermarking embedding algorithm in the Wigner domain. It shows that watermark-

ing in the Wigner domain is equivalent to a non-linear embedding function in the time

20

domain. Section 3.2 studies the error introduced in the inversion of the watermarked
distribution from the time—frequency domain to the time domain and gives more in-
sight about the choice of the weighting matrix. In Section 3.3, the performance of
the proposed Time-Wigner method for the Gaussian distributed watermark case is
analyzed. Both the probability of detection and the probability of miss are derived
for detecting the watermark. On the other hand, Section 3.4 deals with the binary
watermark sequence case. The probability of error in detecting the watermark is de-
rived. Section 3.5 provides simulation results to demonstrate the performance of the
proposed method under attacks. A comparison between the Time-Wigner method
and spread spectrum watermarking method is given. Discussion about the proposed
Time—Wigner method is given in Section 3.6. Finally, Section 3.7 summarizes the

major contributions of this chapter.

3.1 Watermark Embedding

In the Time-Wigner method, the watermark is embedded directly into the Wigner
distribution of the image. Figure 3.1 shows a block diagram for the proposed water-
mark embedding algorithm. The embedding algorithm has three main stages. The
first stage transforms a subset of pixels of length L chosen randomly from the host im-
age into the Wigner domain to produce L2 watermarkable cells. In the second stage,
the watermark is embedded inside the resulting Wigner distribution. The cells in the
joint time-frequency domain, where the watermark is embedded are chosen such that
the resultant watermarked distribution is close to a valid Wigner distribution. The
third stage involves computing the inverse Wigner transform for the watermarked
distribution.

In the proposed method, we assume the size of the host image to be N x N and
the watermark to be L S N. Moreover, for simplicity and other reasons discussed in

the embedding algorithm, we choose L = N unless otherwise stated.

21

Orbit“ Imus PM

 

Wigner

 

Find the

 

distribution

 

 

 

mftrix a

 

 

 

 

 

 

 

Figure 3.1. The block diagram for the watermark embedding in the Time-Wigner

method.

 

Encoder

 

 

 

 

Watermark, w

 

Inverse

Wigner

 

 

Watermarked Image

The corresponding embedding algorithm can be summarized as follows.

1. Transform a subset of pixels of length N at least, P(y), chosen randomly from

the image, I (:L', y), to the time—frequency domain using the Wigner distribution,

WDPUL Wy) = 2 Z P(y + m)P(y _ ,m)e-j2wym7
m

where my is the vertical frequency variable and WDp(y,wy) is the Wigner

distribution of the subset of pixels P(y).

22

(3.1)

The pixels, P(y), can be chosen randomly to provide more security to the
algorithm, or by edge detection algorithms to improve the robustness. In this
section, we choose P(y) randomly and the key that contains the locations of

the chosen cells is sent as a side information to be used in the decoding stage.

. Embed the watermark w inside the Wigner distribution WDp(y, my),

WDP(y,wy) = WDp<y,wy> + Apry.wy)w<y>, (3.2)

where A p(y, rug) is a time—frequency dependent weighting matrix that is related
to WDp(y, wy), and and A p(y, wy)w(y) is an element by element multiplication

for every column of Ap(y,wy) and w(y).

The length of P(y) is set to N, which will produce Ap(y,wy) of size N x N.
The multiplication in A p(y,wy)w(y) means that every frequency in A p(y,wy)
is multiplied by same weight determined by the watermark, w(y). This explains
why we choose the watermark length to be N. In the case where the watermark

length is less than N, we can append zeros to the watermark to get a watermark
sequence of length N.
The weighting matrix, A p(y,wy), is chosen such the the watermarked distri-

bution is very close to a valid Wigner distribution. The specifics of how the

weighting matrix is chosen will be explained in detail in Section 3.2.

. Find the watermarked image by taking the inverse transform assuming equation

(3.2) corresponds to a valid Wigner distribution,

 

Pry) = \/Z W‘Dpwy). (3.3)

will

23

Equation (3.3) can be simplified as follows,

 

at) = J2: WDpwy).

“y

 

= Z (WDpwy) + Anyway».
“’9

\l; (2m 2 PM + m)P<n - mafia/m + Ape. wy)w(y)),
= V221”: "+m>P )(n_m)§:. j2wym+ZAM (My) w<y>

 

m “’11 wy

 

Pmn(— m)6( (2)m +wZAP( y, wy)w(y),

ll
[\3
M
:9
Z
+
3

 

13(31) (3-4)

H
"U
A”
a:
3’]
:5
"U
’13
E
<2
.J

This simplification reduces the embedding function to a non-linear function in the
spatial domain, which is dependent on the weighting matrix, A p(y,wy). Equation
(3.4) was derived with the assumption that the watermarked distribution is a valid

Wigner distribution. However there is an error introduced in the inversion process,
E = VVDPWaWy) _ WDP(yiwy)7 (35)

where, WDp(y,wy) is the Wigner distribution of 1°(y) and WDP(y,wy) is the wa-
termarked Wigner distribution. This error is saved as a key and sent to the receiver

for more accurate watermark extraction.

In the next section, we study this error in more detail and look into its role in

determining the weighting matrix.

24

3.2 Error Introduced in the Inversion Process

The simplification of the embedding function in Section 3.1 was carried out with
the assumption that the watermarked distribution is a valid Wigner distribution.
However, this assumption is hard to satisfy and an error is introduced in the inversion
process. This section gives some insight about this error and its effect on the choice
of the weighting matrix, A p(y, wy).

To study the effect of the approximation in equation (3.4), we look at how different
the Wigner distributions of the signal in equation (3.3) is from the Wigner distribution
in equation (3.2). Let Ap(y, wy) = C-WDp(y,wy), where C is a constant and let the
Wigner distribution of P(y) be W—D_p(y,wy). Ideally, Wp(y,wy) and WDp(y,wy)
should be identical. However, an error E, is introduced by equation (3.3) in the

inversion process,

E = —WDp(y,wy) — WDp(y,wy). . (3.6)

In the proposed embedding method, the error E is saved as a key and used for
watermark extraction.

To study this error, we compute the Normalized Mean Square Error (NMSE)

between WDp(y,wy) and WDp(y,wy),

N N __ . 2
fig 2: 2 (WWW — WDptz‘.j>)

_ 1 3'
NMSE— N N . (3.7)

ZZWDi2<tj>

z .7

 

Table 3.1 shows the average NMSE for different images over all time-frequency
points. The NMSE is computed from the error introduced in the inversion of the

Wigner distribution for different images. The results suggest that the approximation

25

used for the inversion of the Wigner distribution is valid and introduces a small

amount of error.

Table 3.1. The average Normalized Mean Square Error introduced by the approxi-
mation of the Wigner distribution in Time-Wigner method.

 

 

 

 

 

 

Image NMSE Standard deviation (sd)
Lena 3.21 x 10—8 4.92 x 10—10
Barbara 3.07 x 10—8 4.98 x 10—10
Camera Man 2.93 x 10—8 7.64 x 10‘“11
Peppers 3.11 x 10-8 4.78 x 10—10

 

 

 

 

Further, we can study the time-frequency locations where the error is concentrated

by finding the difference between the two Wigner distributions,
WDD = WDp(y,wy) — WDp(y,wy). (3.8)

At each time point, i.e. for every column in WDD(y,wy), we find the histogram
of the maximum differences in equation (3.8) over frequency. Figure 3.2 shows that
the maximum error is concentrated around the low frequencies. Since the error is
concentrated in the low frequencies, the weighting matrix, A p (y,wy), can be chosen
such that the watermark is embedded in the middle frequency range, which is less
affected by this approximation error. The corresponding weighting matrix is,

WDPWrwy)

max(WDP(y,wy))’ L01 5 [Lay] S “’2

APfyawy) O( i (39)

0, elsewhere

where cal and (.02 are the normalized frequencies that can be determined empirically
with typical values of (.01 = (I; and tag = 11);. However, since the error is available as side

information at the receiver, the condition in equation (3.9) can be relaxed and the the

26

time-frequency points with the largest values are chosen for watermark embedding.

 

150 r r r r

# of times occured
8

8

 

 

 

Frequency

Figure 3.2. The average histogram for the difference of the two Wigner distributions
in the Time-Wigner method.

In the following two sections, we derive the probability of error in detecting the
watermark for two different cases. In Section 3.3, the performance of the detector for

the Gaussian watermark case is given, whereas in Section 3.4, the performance of the

detector for the binary watermark case is discussed.

27

3.3 Watermark Detection for the Gaussian Case

For copyright protection applications, it is important to detect the existence of the
watermark, and not necessarily extract the actual watermark, even after the water-
marked image is attacked [75, 89]. For these applications, the probability of error
in detecting the correct watermark is used as a measure to study the performance of
the detection algorithm. Moreover, copyright applications usually have access to the
original image and blind watermarking is not that crucial. Thus, in this dissertation,
we assume that we have access to the original image, or at least to the pixels used
for watermarking.

In this section, we will study the performance of the Time-Wigner watermarking
method for a Gaussian distributed watermark sequence. We define two hypotheses:
H1, the hypothesis that the embedded watermark exists and H0, the hypothesis that
there is no watermark embedded or that the embedded watermark is not the one that
the detector is testing for. Since we have access to the original image, we can extract
a function that depends on the watermark by squaring equation (3.4) and subtracting

the square of the image from it,

A

Z Apfyrwy) we) = P29) — P29). (3.10)
“’9

The extracted function is compared with a series of possible watermarks to determine

which watermark has been embedded,

H1

< ZAP(yaw?/) w(y),w(y)> > 77, (3-11)
wy <
H0

where < 931, 2:2 > is the inner product of 3:1 and .732, w(y) is the embedded watermark

28

sequence with variance 0%, 712(3)) is any other watermark sequence with variance 0%

and 77 is the threshold used to detect the watermark.

By defining the probability of false alarm as PF A and the probability of detection

as PD, the probability of error P8 is written as,
Pa = POPFA +P1(1— PD), (312}

where p0 and p1 are the a priori probabilities for H0 and H1, respectively.

For the case that the a priori probabilities of H0 and H1 are %,

Pe=-21—P(ZAp(y)w(y)w (y)>77 +— %P ZApty) ugh/Kn), (3-13)

where Ap(y) =ZyAp(y,wy).

In order to wfind the threshold 17 that minimizes P6, the distribution of
Z A p )and the distribution of 2A p )wy( )1I1(y) should be derived. The

full derivation lS given in the appendix.

Let,

= Z Ap(y)w2(y)- (3.14)
y

The mean and the variance of this random variable are given by,

11,. =012Ap(y), (3.15)
031-— - 2014: AP (3.16)
Let,
72 = Z Ap(y)w(y)w(y)- (3.17)
y

29

The mean and the variance of 22, assuming 11) and ti) are independent, are given by,

022— — (€02 :AQPQ). (3.19)
3!

For large N, the probability density functions (pdfs) of 21 and Z2, using the central

limit theorem [90], are assumed to be Gaussian,
le(z ZN) N(#21r021), (3.20)

f22(z ZN) I‘M/122,022) (3'21)

In order to find the minimum probability of error detector, we differentiate Pe with

respect to 77,
6P6

= .22
877 o, <3 >

which yields,
fz1(77) - fz2(77) = 0- (3-23)
Substituting the pdfs of zl and .22 in equation (3.22) and taking the natural log yields,

2
2 2 , [ZAPM ZApty)
—— — —— + — A 1 —— :0.
[40:03 l" 20% ’7 4 g 1"” “ «a.

(3.24)

 

 

 

The threshold, that minimizes the probability of error, is given by,

30

 

2 2 2 243(4)

2 2 “1‘02 2 y

0 0 Ap(-y) —1:l: 1+——— 1—4ln( )

1 22,: 0% 7501 (241109))?
9

\ . .

2 2

 

 

 

 

 

77 =
(3.25)

The threshold derived in equation (3.25) is image dependent. This dependency
on the image is reflected through the time-frequency weighting matrix, qu(y,wy).
Therefore, the time—frequency distribution of the image is taken into account when

choosing the appropriate threshold.

3.4 Watermark Detection for the Binary Watermark Sequence Case

The watermarking algorithm that embeds a Gaussian watermark detects the existence
of a specific identification watermark in the multimedia content. It usually serves as
an evidence of ownership. On the other hand, the multi-bit watermarking system
extracts the embedded watermark and it is usually used for data hiding or ownership
declaration. Thus, binary watermarks are preferable over the Gaussian ones in these
applications.

In this section, we assume the watermark to be a binary randomly generated
sequence of length N. For the Time-Wigner method, we can extract the watermark

from equation (3.2) as,

u“) = WDPf'yrwy) _ WDPfery) — E(9rwy)
(y) ( Ap(y,wy) ) , (3.26)

31

which can be written as,

P25) — P29) — 2 En. Wy)
("’y

if) : , (3.27)
(y) E APR/My)
w?!

 

where 113(y) is the extracted watermark after possible attacks and E (y, ray) is the error
key.
We assume the attack, 71(y), to be Gaussian and independent from the watermark

and ti)(y) consists of {—1, 1}. We can write the extracted watermark as,

10(9) = w(y) + ”(9), (3-28)
The detection rule will be,
H1
. >
('w(y), 10(9)) 77, (3.29)
<
H0

where, 121(3)) 2 w(y) + 71(y) if the watermark is embedded, and 222(y) = n(y) if no
watermark is embedded.

The probability of false alarm can be written as,

PFA = P (2(9) > 77)- (3.30)

where,

Z w(y)n('y)
z<y> = y .
\/Z 102(11): ”2(9)
y y

 

(3.31)

 

32

For simplicity, we assume the mean of n(y) to be zero. Thus, the expected value
for n2(y) is 0%. Assuming the length of the watermark is large and using the weak

law of large numbers (WLLN), we can use the following approximations,

2712(3)): 0,2,N. (3.32)
9

Moreover, since w2(y) = 1, we can write 2113(3)) = N. Thus, we can rewrite
y

2(9),

Z “((9)7100

~ 31
2(y) ~ onN . (3.33)

 

For large N we can assume z(y) to have a Gaussian distribution with mean and

variance given by,

and
2 _ 1
(72(3)) — N’ (3.35)
Thus, the probability of false alarm can be written as,
PFA = Q (tr/N) , (3.36)
1 +00 t2
where Q(y) = 7—27 3] exp (— (7)) dt.
Similarly, to find the probability of miss, we consider,
2 “((3)1900
(3.37)

 

 

2(9) = y ,
[[2 win) 2132(9)
31 y

33

By noting that Z u')2(y) 2 N(1 + 072,) using the WLLN, we can find the mean

3!
and the variance for 2(y) to be,

“2(9) = N, (3.38)

and
f = No.2,, (3.39)

Thus, the probability of miss is given by,

 

Ple—QCI/j—ng). (3.40)

The probability of error for correct extraction can then be written as,

Pe=%(Q ("m)+1—Q(,n/1:v:,))’ (3.41)

where, p0 and p1 are assumed to be equal. The probability of error in detecting the

 

correct watermark depends on the watermark length, N, the attack variance, 0%, and
the threshold, 77. The parameters N and r) are user defined, and should be chosen in

a way that reduces the probability of error.

3.5 Simulation Results and Comparison

This section provides simulation results to demonstrate the performance of the pro-
posed method for the binary watermark case. Similar simulations can be carried out
for the Gaussian watermark case. Although the Time—Wigner method has been ap-
plied to a large number of natural gray—scale images [91], in this section we give a
detailed performance analysis for the 512 x 512 Lena image and a randomly generated
binary watermark of length 256. The performance measures discussed in Section 1.6

are used to evaluate the performance of the proposed method.

34

The capacity of the embedding algorithm has been studied, where different wa-
termarks with different lengths have been embedded and the corresponding PSNRS
between the watermarked and the original image are computed. The probability of
false alarm derived in Section 3.4 is compared with the experimental results for differ—
ent attacks. The proposed method is tested under different attacks including Additive
White Gaussian Noise (AWGN), median filtering, rotation, and JPEG compression
with different compression ratios (CBS). The well-known Discrete Cosine Transform
(DCT) method by Cox et al. [63] has been implemented for comparison.

The proposed watermark embedding algorithm has been applied to a large number
of images. Table 3.2 shows the average bit error rates (BERs) under different attacks.
Since the performance of the algorithm does not vary much with the choice of the
image (as can be seen in Table 3.2), in the rest of this section we focus on the

performance of the algorithm for the Lena image.

Table 3.2. Average bit error rate in detecting the watermark under different attacks
using 100 different images.

 

Attack BER
AWGN (PSNR=48.13db) 0.0059i0.0021
AWGN (PSNR=36.0db) 0.0094i0.0045
AWGN(PSNR=14.15db) 0.0432:l:0.0121

 

 

 

 

 

 

 

 

 

 

 

 

JPEG (CR=1.7) 0.0078i0.0034
JPEG (CR=7.7) 0.0125i0.0085
JPEG (CR=20) 0.0134i0.0087
MF (3 x 3) 0.0016i0.0013
MF (5 x 5) 00041400022
MF (7 x 7) 0.0066:t0.0024

 

35

3.5.1 The Choice of the Watermark Length
In order to determine how many hits to embed in the host image, we calculated the
Peak Signal to Noise Ratio (PSNR) between the host and the watermarked images
for different watermark lengths. Figure 3.3 shows that even when we embed a large
number of bits, such as 2048 bits, the PSNR values remain in the 50dB range. The
PSNR values vary from 100dB for the case of 16 bits to 54dB for the 2048 hits case.

Moreover, to study the performance of the detector derived in Section 3.4 for
different watermark lengths, we find the ROC curves for different values of N. For
different watermark lengths, N, the probability of false detection and the probability
of false alarm in the presence of no attack are found for different thresholds. Figure
3.4 shows that larger watermark lengths provide better ROC curves. In fact, for
watermarks of length greater than 128, the ROC curve starts to approach the ideal.By
looking back to equations (3.36) and (3.40), we can see that increasing N will increase
the probability of detection, 1 — PM, and decrease the probability of false alarm,
PFA: for a given threshold, 77 and a fixed on. Thus, increasing N will produce less
probability of error, which agrees with the experimental results in Figure 3.4.

In the following simulations, we select the length of the watermark to be 256 for
a targeted PSNR of 62dB. Figure 3.5 shows the original Lena image, while Figure
3.6 shows the watermarked Lena image. It is clear that there is no visual difference
between the original and the watermarked images which satisfies the invisibility of the
watermark. As mentioned earlier, the proposed Time-Wigner method has been tested
under different types of attacks including additive white Gaussian noise (AWGN),
median filtering, rotation, and JPEG compression. In the following subsections, we

discuss each attack in detail.

36

PSNR versus number of bits
100 l l l l l

 

I

PSNR (dB)

55- ‘

 

 

l l l

500 1000 1500 2000 2500
Number of bits

 

Figure 3.3. PSNR versus number of bits.

3.5.2 Additive White Gaussian Noise (AWGN)

An additive white Gaussian noise with different noise levels was added into the water-
marked image. The extracted watermark was correlated with 100 randomly generated
watermarks at the receiver. The correlation detector has the highest value at the wa-
termark number 50 which corresponds to the actual embedded watermark as shown
in Figure 3.7. Figure 3.8 shows the attacked watermarked image under AWGN with
PSNR=14.15dB. The extracted watermark produces the highest correlation even un-

der this amount of distortion.

37

 

 

I

0.9

 

I

0.7

I

0.6

 

 

PD

 

.0
01
r

,0
A
l

.o
(A)
r

.0
N
r

_O
A
1

 

 

 

)-

-1 0 1 2 3 4 5 6
PFA x 10-4

Figure 3.4. The ROC curves for different watermark lengths.

Moreover, the correctness of equation (3.36), PF A = Q (Th/N), was validated
through simulation. Figure 3.9 compares the probability of false alarm computed from
the analytic expression and the simulation results under AWGN with PSNR=28.18dB.
The graph shows that the analytical and the experimental curves are very close to
each other, which validates the assumptions in Section 3.4.

3.5.3 Median Filtering

The second type of attack applied to the watermarked image is the median filtering.

A median filter of size F x F is applied to the watermarked image. The correlation

38

Origlnal Lena Image

 

Figure 3.5. The original Lena512 image.

detector results for median filtering attack are shown in Figure 3.10. The desired
watermark is detected even when the watermarked image is degraded significantly
with median filter of size 16 x 16. Choosing the pixels to be watermarked randomly
improve the robustness of the proposed method under median filtering, since the
median filtering attack with small filter size will most likely produce pixels with
values close to the watermarked pixels before attack. Thus, the Wigner distribution
of the attacked pixels and the pixels before the attack will be very close to each other

and this will lead to an accurate extraction of the watermark. This robustness stays

39

Watermarked Lena Image PSNR=40dB

 

Figure 3.6. The watermarked Lena512 image with PSNR=62dB.

till the median filtering attack start changing the selected pixels by big values. Figure
3.11 shows the degraded watermarked image for 9 X 9 median filtering, while Figure
3.12 validates again the correctness of equation (3.36) for median filtering.

3.5.4 Rotation

Rotation attack with different rotation angles is also applied to the watermarked
image. The watermarked image is rotated counter clock-wise using the bilinear in-
terpolation method. The proposed Time—Wigner method successfully detects the

embedded watermark even under large rotation angles, i.e 7°, as seen in Figure 3.13.

40

PSNR=48.13dB PSNR=28.13dB

 

 

—L
A

 

 

 

 

 

 

 

 

 

 

 

 

E E

g 0.8 :8 0.8

iéos 520.6

0 0

30.4 50.4

$0.2 E02

8 4014044 a . . -

20 40 60 80 100 20 40 60 80 100
b
PSNR=14.15dB PSNR=8.13dB

E E ' ' '

.3 0.8 g 0.8

E 0.6 “E; 0.6

E 3: : 0.4

g - A A g 0.2

5 0th W 5 o

o -0.2 o _02

 

 

 

20 40 60 80 100

20 40 60 80 100
c d

Figure 3.7. The normalized correlation detector response for the Time—Wigner method
applied to Lena512 image under AWGN with different PSNRs, a. PSNR=48.13dB,b.
PSNR=28.13dB, c. PSNR=14.15dB, d. PSNR=8.13dB.

Equation (3.36) was verified for rotation attack as shown in Figure 3.15.

3.5.5 JPEG Compression

One of the most important attacks that an image watermarking algorithm should
survive is the JPEG compression. The watermarked image was compressed with
JPEG at different compression ratios. Similar to other attacks, the detection of the

watermark was accurate even at high compression ratios, as shown in Figure 3.16.

41

Watermarked Image under AWGN with PSNR=14.15dB

.‘ ‘1‘

 

   

Figure 3.8. The watermarked image degraded by AWGN (PSNR=14.15dB).

Figure 3.17 shows the attacked image having visible blocking artifacts and yet the

algorithm is still able to detect the watermark. Again, equation (3.36) was verified

for JPEG attack as shown in Figure 3.18

3.5.6 Comparison between the Time-Wigner and the Spread Spectrum
Methods

For the comparison with the DCT method proposed by Cox [63], a watermark se-

quence of length 256 is embedded in the 256 highest magnitude coefficients in the

(DCT) of the Lena image. Figure 3.19 through Figure 3.21 show the correlation

42

Probability of False Alarm versus the threshold under AWGN (PSNR=28.12)

l I l l T

0.5-. '

 

I

0.45 - r

I
..+_
l

0.4

0.35 ‘

T
+

T

0.3 I ‘

PFA

I

0.2 + «

I

0.15 _

I

0.05 r -. -
+++

 

 

[ llllllllll
[Ill

0 ‘ r l
0 0.05 0.1 0.15 0.2 0.25 0.3
Threshold

 

Figure 3.9. The probability of false alarm versus the threshold under AWGN with
PSNR=28.18dB.

detector response for both methods under AWGN, median filtering and JPEG com-
pression respectively. The proposed Time-Wigner method performs better than the
DCT method under all attacks. Both, the Time—Wigner and DCT methods perform
well under AWGN. In the median filtering case, the proposed method has higher cor-
relation coefficients under all filter sizes. The DCT method embeds the watermark
in the largest magnitude DCT coefficients of the host image, which requires the use

of small weighting coefficients to provide an invisible watermark. Thus, the strength

43

Median filtering 3x3 Median filtering 5x5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

‘5 ‘5
E 0.8 E08

8 0-6 80.6
0 04 0
5 - .5 0.4
“ 0.2 “
% WM %0.2

t 0 t

o o 0
0 -02 . . 0 . .

I 20 40 60 80 100 20 40 60 80 100
a b
Median filtering 7x7 Median filtering 16x16

18 ‘ 75

$0.8 E 0.8

§O.6 g 0.6

c 0.4 c 0.4

.9 .9

E 0.2 1.3 0.2

g 2

o 0 8 0

0 - O _ ‘ 1

20 40 60 80 100 20 40 60 80 100
c d

Figure 3.10. The normalized correlation detector response for the Time-Wigner
method applied to Lena512 image under median filtering with different filter sizes, a.
size=3 x 3,b. size=5 x 5, c. size=7 X 7, d. size=16 x 16.

of the watermark will be low and any distortion in the image will affect the detection
of the watermark. The choice of the weighting matrix along with the use of the error
key improve the robustness and hence the detection of the watermark in the proposed

Time-Wigner method.

44

Watermarked Image under Median Filtering. Size = 9 x 9

 

Figure 3.11. The watermarked image degraded by median filter of size 9 X 9.

45

Probability of False Alarm versus the threshold under Median filtering 4x4

1 T i l T

0.5" ‘

 

0.45 r ' ‘

0.4 ~

0.05 -

 

 

 

 

o . ‘ . . * ' i l i
0 0.05 0.1 0.15 0.2 0.25
Threshold

Figure 3.12. The probability of false alarm versus the threshold under median filtering
with filter size=4 x 4.

46

Rotation=1 degree Rotation=3 degree

 

—b

 

_L

 

 

 

 

 

 

 

 

 

    

 

 

 

 

 

 

 

1% T8

'6 0.8 :g 0.8

E t

8 0.6 o 0-6

O O

.8 0.4 .5 M

g 0.2 (E? 0.2

8 000011th001108 ° . .

20 40 60 80 100 20 40 60 80 100
a b
Rotation=5 degree Rotation=7 degree

E 0.8 g 0_3

(:3! 0.6 33> 0.6

c 0.4 c 0.4

.9 .9

E 0.2 E 02

° 9

5 0w 1M 5 0

0 -02 . . . - 0 -0.2 .

20 40 60 80 100 20 40 60 80 100
c d

Figure 3.13. The normalized correlation detector response for the Time—Wigner
method applied to Lena512 image under rotation with different angles, a.
degree=1°,b. degree=3°, c. degree=5°, d. degree=7°.

47

Watermarked image rotated by 7 degrees

 

Figure 3.14. The watermarked image degraded by rotation of 7°.

48

Probability of False Alarm versus the threshold under Rotation (3 degrees)

F l l l l

0.5+ ‘

 

0.45 r ' r

0.4- +

0.05 -

 

 

 

 

o . ‘ r i r
0 0.05 0.1 0.15 .2 0.25
Threshold

Figure 3.15. The probability of false alarm versus the threshold under rotation of 3°.

49

JPEG CR=2 JPEG CR=8

 

 

—.L
—L

 

  

 

 

 

 

 

 

 

 

 

 

 

 

 

75? a

._ OJ

9 0.8 5 0.8

if, E

o 0.6 g 0.6

0 o

'3 0.4 S 0.4

E 0.2 E 0.2

g 010W ll Wk 9; 0

0 ll ll 8

20 40 6O 80 100 20 40 60 80 100
a b
JPEG CR=20 JPEG CR=37

is: ‘ r.

E 0.8 g 0.8

§00 (93’ 0-6

c 0.4 c 0.4

2 .9

$0.2 g 0.2

i: t 0

o 0 o

o o

20 40 60 80 100 20 40 60 80 100
c d

Figure 3.16. The normalized correlation detector response for the Time-Wigner
method applied to Lena512 image under JPEG compression with different compres-
sion ratios, a. CR=2,b. CR=8, c. CR=20, d. CR=37.

50

Watermarked Image under JPEG with CR=37

 

Figure 3.17. The watermarked image degraded by JPEG compression with CR=37.

51

Probability of False Alarm versus the threshold under JPEG with CR=20

l l l l l

0.5"? _

 

0.45 - a

0.05

 

 

 

 

o 1 r i
0 0.05 0.1 0.15 .2 0.25 0.3
Threshold

Figure 3.18. The probability of false alarm versus the threshold under JPEG com-
pression with CR=20.

52

AWGN comparison: Time-Wigner method

 

 

 

0.95 - + 88 -

mAr-rw-

 

 

0.9 '

 

0.85 -

0.8 -

0.75 *

Correlation Coefficient

0.7 r

0.65 -

 

 

 

0' l l l

10 15 20 25 30 35 4o 45
PSNR (dB)

1 l J

Figure 3.19. Comparison between spread spectrum and Time-Wigner methods under
AWGN.

53

Comparison under Median Filtering: Time Wigner method

 

p
(D
I

I
If],
‘1

'r
'1
5,,
It] I-
‘i
'I
a,"
a,"
r,[

 

9
co
I

 

 

p
N
I

 

Correlation Coefficient
.0 .0 .O 0
o.) 4:- 01 'c)
l 1

5:
N
l

l

 

 

l l l l L I I

Filter Size

Figure 3.20. Comparison between spread spectrum and Time-Wigner methods under
Median Filtering.

54

Comparison under JPEG

 

p
(o
I

 

_O
on
I

 

 

 

Correlation Coefficient
5: p
O) N
I I

9
(TI
I

O
A
I

 

 

 

i i l l

l

0 5 10 15 20 25 30 35
Compression ratio

)—

Figure 321. Comparison between spread spectrum and Time-Wigner methods under
JPEG compression.

55

3.6 Discussion

The main attribute of the Time-Wigner method, is the fact that it could be imple-
mented in the time domain directly. This is due to the fact that the time-frequency

domain embedding function can be simplified to non-linear function in time,

 

P<y)= P2<y)+ ZAPUJawy) we). (3.42)
“’3!

This simplified function uses the time-frequency characteristics of the image through
the weighting matrix A p(y, Lay).

For many watermarking applications, the embedding process can be done off line,
so the time required to embed the watermark does not matter. This means that
whether we use the non—simplified or the simplified version of the embedding function
will not have any effect on the transmitter (encoder). The difference appears when
we detect/extract the watermark. If we use the non-simplified function in the time-
frequency domain, we need to find the Wigner distribution of the image, or of the
subset of pixels from the image used for watermarking, which requires a lot of online
computations. On the other hand, if we use the simplified function, the Wigner
distribution is not needed to detect the watermark and thus we reduce the number
of computations.

The Time-Wigner method has the flexibility of embedding a Gaussian or binary
watermark. Depending on the application, one can choose whether to embed a
Gaussian or binary watermark sequence. The simulation results provided in Sec-
tion 3.5 are for the binary sequence case. Similar simulations can be carried out for

the Gaussian case. In this case, equation (3.25), which is dependent on 77, is used for

56

watermark detection,

 

 

 

 

 

 

 

 

l l ZA2(y)
2 2 Zaf‘ag
0102;2‘1PW) -1:l: 1+? 1-4ln(\/§:‘1)(:y:Ap(y))
_ l - ll
77: 20%—0’% .

(3.43)

For the special case when of = 0% = 02. The threshold, 7), reduces to,

 

j

l 2.4;. (y) '
= 02 A ' —1 + 2— 4111 . (3.44)
77 2 PW) \ C} 2)(ZyAP(3/))2

The special case for the threshold derived for the Gaussian watermark case, in

 

 

 

 

 

 

equation (3.44), assumes that a? 75 0% is sufficient to distinguish between the true
watermark and the false one at the receiver. Since the watermark is a Gaussian
random variable with zero mean, it is distinguished through its variance. So, if
two Gaussian random variables have two different variances, then these two random
variables are not identical. in other words, the detector will not falsely detect the
watermark if of 75 03, because it will recognize that the detected watermark is the
false one and ignore it. The main confusion occurs when 0% = 0% and using equation
(3.44) will enable the detection of the watermark. The detection of the watermark

is dependent on the right choice for n. For example, equation (3.44) determines the

value for 17 that provides the minimum probability of error, P8.

3.7 Summary

In this chapter, we proposed a new image watermarking method in the Wigner do-

main. The proposed Time—Wigner method in the time-frequency domain was sim-

57

plified to a non-linear function in the time domain. The simplified function uses the
time—frequency characteristics of the image through the weighting matrix A p(y, wy).
This simplification is based on the assumption that the watermarked distribution is
a valid Wigner distribution. However, this is not always true and an error is intro-
duced by the inversion process. The introduced error is analyzed and found to be
concentrated in the low frequency range. This error is saved as a key and used for
watermark extraction / detection at the receiver.

Two detection algorithms are derived. The first one assumes the watermark to
be a Gaussian sequence, while the second one assumes the watermark to be a bi-
nary sequence. Depending on the application, one can choose whether to embed a
Gaussian or a binary watermark sequence. Gaussian watermarks are suitable for ap-
plications where detecting the watermark is the main (goal, like broadcast monitoring
and owner identification. On the other hand, binary watermarks are used, in addition
to the previous applications, in covert communication. In covert communication, the
watermark is a secret message which contains some information for a specific usage,
i.e military.

To evaluate the performance of the proposed Time-Wigner method, a binary wa-
termark sequence is embedded inside Lena image. The robustness of the proposed
algorithm under attacks is shown through extensive simulations. The watermark is
successfully detected, even under severe distortions. Moreover, a comparison between
the Time-Wigner and the DCT methods is carried out. The DCT method is chosen
because of its robustness and the similarities it has with the Time-Wigner method
in terms of the way the watermark is spread over the image. In general, the pro-
posed Time—Wigner method performs better than the DCT method under all attacks
discussed in this chapter. In addition, Time-Wigner method has more flexibility in
choosing the number of bits to be embedded and still retain high PSNR values. Al-

though Time—Wigner and DCT methods use non-blind algorithms for detecting the

58

watermark, the prOposed Time-Wigner method requires only the subset of pixels used
for watermark embedding to detect the watermark, P(y), while the DCT requires the

whole image at the receiver.

59

CHAPTER 4

THE WIGNER—WIGNER WATERMARKING METHOD

In the previous chapter, the Time-Wigner method was shown to have high robustness.
However, once the Wigner distribution of the image is found, the watermark may be
detected / extracted using an estimation attack. In order to provide more security to
the Time-Wigner method, we propose and evaluate a novel time-frequency water-
marking algorithm using Wigner distribution. Unlike the Time—Wigner method, in
this chapter the Wigner distribution of the watermark is embedded inside the Wigner
distribution of a subset of pixels, P(y), chosen from the image, [(31, y). This method,
the Wigner-Wigner, can be considered as an improved version of the Time-Wigner
method to increase the security of the watermark. Embedding the Wigner distribu-
tion of the watermark inside the Wigner distribution of the image makes the water-
mark more secure, since extracting or detecting the watermark involves evaluating
the Wigner distribution for both P(y) and the watermark.

Similar to Chapter 3, two detection algorithms for the Gaussian and binary wa-
termark cases are derived. In addition, we compare the performance of the proposed
method with a similar watermarking algorithm in the multiresolution domain in [67],
to demonstrate the robustness and the potential of the proposed method.

This chapter is organized as follows. Section 4.1 gives a detailed analysis of the
watermarking embedding algorithm in the Wigner domain. It shows that the Wigner-
Wigner watermarking method in the time-frequency domain is equivalent to a non-
linear embedding function in the time domain. In Section 4.2, the error introduced in
the inversion of the watermarked distribution from the time-frequency domain to the
time domain, and the choice of the weighting matrix are discussed. Sections 4.3 and

4.4, analyze the performance of the proposed Wigner-Wigner method for the Gaussian

60

distributed watermark case and the binary watermark case, respectively. Section 4.5
provides simulation results to demonstrate the performance of the proposed method
under attacks. A comparison between the Wigner-Wigner method and a DWT-based
watermarking method is given. While Section 4.6 discusses some key points in the

proposed algorithm, Section 4.7 summarizes the major contributions of this chapter.

4.1 Watermark embedding

In the Wigner-Wigner method, the Wigner distribution of the watermark is embedded
into the Wigner distribution of the image. The block diagram for this method is given
in Figure 4.1. The embedding algorithm in the Wigner-Wigner method has four main
stages. Similar to the Time-Wigner method, the first stage transforms a subset of
the pixels of the image to the Wigner domain. In the second stage, the watermark is
transformed to the Wigner domain. In the third stage, the Wigner distribution of the
watermark is embedded inside the Wigner distribution of the chosen subset. The last
stage involves finding the inverse Wigner transform for the watermarked distribution.

Similar to the Time-Wigner method, we assume the size of the host image to
be N x N and the watermark to be L S N. Moreover, for simplicity, we choose
L = N unless otherwise stated. The watermark embedding algorithm can then be

summarized as follows:

1. Transform a subset of pixels, P(y), chosen randomly from the image, I (:12, y),

to the time-frequency domain using Wigner distribution,
WDp(y.wy) = 22 My + m)P<y — m)e*~'"2wym. (4.1)
m

The pixels, P (y), are chosen randomly and the key that contains the locations of

the chosen cells is sent as a side information to be used for watermark detection.
2. Transform the watermark sequence, 10, to the time-frequency domain using

61

Wigner distribution,

WDw(y, coy) = 2 Z w(y + m)w*(y — m)e_j2w3/m. (4.2)

3. Embed the Wigner distribution of the watermark sequence inside the Wigner

distribution of P(y),
WDP(y: My) : WDP(yi Wy) + AP(y1wy)® WDw (ya 013/): (4'3)

where A p(y,wy) G) WDw(y,wy) is an element by element multiplication. The
weighting matrix, A p(y, rug), is again chosen such the the watermarked distri-
bution is very close to a valid Wigner distribution. Unlike the Time-Wigner
method in this case, the Wigner distribution of the watermark is spread out on
the whole time-frequency plane. The specifics of how the weighting matrix is

chosen will be explained in detail in Section 4.2.

4. Obtain the watermarked image by taking the inverse transform assuming equa-

tion (4.3) is still a valid Wigner distribution,

 

it» = ZWDP(3/awy)- (4.4)
will

The embedding algorithm described in equation (4.4) can be simplified as follows,

62

 

Ply) = Z ”(me wy),

 

 

“)3!
= Z (WDp(y,wy) + Ap(y,wy)wpw(y,wy)),
”I!
= \/2 Z P(n + m)P(n — m)(5(2m) + Z AP(3/awy) * “12(9),
m “’31

 

= p2(y)+ ZAp(y,wy) Way),

\ wy

P(y) = P2(y)+ ZAp(y,Wy) *w2(y), (4-5)

N am

where * corresponds to convolution. Similar to the Time-Wigner method, the simplifi-

 

cation reduces 15(y) to a non-linear function of the image and the watermark sequence
in the spatial domain. The time-frequency dependence of the embedding function is
through the time-frequency dependent weighting matrix A p(y,wy). Equation (4.5)

assumes the watermarked distribution is a valid Wigner distribution. However, there

is an error introduced in the inversion process,
E = WDply,wy> — WDp<y, rug), (4.6)

where, WDp(y,wy) is the Wigner distribution of 15(y) and WDp(y,wy) is the wa-
termarked Wigner distribution. This error is saved as a key and sent to the receiver

for more accurate watermark extraction.

63

4.2 Error Introduced in the Inversion Process

Similar to the Time-Wigner method, the inversion of the watermarked distribution
assumes that the distribution in equation (4.3) is a valid Wigner distribution. How-
ever, as we have shown in the Time-Wigner method, this is usually not true, and an
error is introduced in the inversion process. In this section, we study the effect of
this approximation by looking at how different the Wigner distribution of the signal
in equation (4.4) is from the Wigner distribution in equation (4.3).

Let Ap(y,wy) = C - WDP(y,wy), where C is a weighting constant and let the
Wigner distribution of P(y) be Wp(y,wy). Ideally, Wp(y,wy) and WDp(y,wy)
should be identical. However, an error E, which again is kept as a key, is introduced by
equation (4.4) in the inversion process. In order to quantify this error, E, we compute
the Normalized Mean Square Error (N MSE) between pr, toy) and WDp(y, any).

Table 4.1 shows the average N MSE for different images over all time-frequency
points. The NMSE is computed from the error introduced in the inversion of the
Wigner distribution for different images. Similar to the results of the Time-Wigner
method, the error introduced in the inversion process in the Wigner-Wigner method
is small, which validates the approximation used for the inversion of the Wigner

distribution.

Table 4.1. The average Normalized Mean Square Error introduced by the approxi-
mation of the Wigner distribution in Wigner-Wigner method.

 

 

 

 

 

 

Image NMSE Standard deviation (sd)
Lena 3.11 x 10—8 5.02 x 10-10
Barbara 3.02 x 10-8 4.92 x 10‘W
Camera Man 2.99 x 10"8 8.21 x 10—11
Peppers 2.99 x 10‘8 4.67 x 10—10

 

 

 

 

64

In order to study the time-frequency locations where the error is concentrated, we

find the difference between the two Wigner distributions,

 

WDD = WDp(y,wy) — WDp(y,wy). (4.7)

At each time point, i.e. for every column in WD D (y, wy), we find the histogram of
the maximum differences in equation (4.7) over frequency. Figure 4.2 shows that the
maximum error is concentrated, once again and similar to the Time-Wigner method,
around the low frequencies. It is also clear that since the Wigner-Wigner method
spreads the watermark throughout the image, the error is more spread out compared
to the Time-Wigner method. Since the error is concentrated in the low frequencies,
we will choose the weighting matrix such that the watermark is embedded in the

middle frequency range, which is less affected by this approximation error. The

corresponding weighting matrix is,

WDP (yrwy)

mazz:(WDP(y,wy))’ “J1 S lwyl S “’2

Ap(y,wy) 0c (4.8)

0, elsewhere

where wl and tag are the normalized frequencies that can be determined empirically

with typical values of wl 2: (15 and wg = %.

65

WWWW)

 

Find the

 

 

 

 

 

Inverse wmnnarlred
Wigner image

 

Wigner
Won

 

 

 

Waterma’ur

Figure 4.1. The block diagram for the watermark embedding in the Wigner-Wigner
method.

66

 

120 r r r r

# of times occured

 

 

 

Frequency

Figure 4.2. The average histogram for the difference of the two Wigner distributions
in the Wigner-Wigner method.

67

4.3 Watermark Detection for the Gaussian Case

In this section, we derive the probability of error in detecting a Gaussian distributed
watermark. Similar to Section 3.3, we can detect the watermark in the Wigner-Wigner

method using a correlation function derived from equation (4.5) by subtracting the

square of the original P(y),

(Ape) =1 win/We» > n, (4.9)

where AME/l * 242(4) = 152(4) — 1%).
Since convolution in time corresponds to multiplication in frequency, and in order

to simplify the derivation we rewrite equation (4.9) as,
H1

<C<n>r1(n).Y2(n>> : n. (410)

HO

where C(n), Y1(n) and Y2(n) correspond to the Fourier transforms of A p(y), 202(3))

and 252(3)), respectively.

To find the minimum probability of error detector. Let,
2, = Z (Joni/12m). (4.11)
n
The mean and the variance of zl are given by,

p2, = N031 [2 2 C(72) + NC(0)] , (4.12)

68

031 = 8N208 [2(0291 )+ NC2(0 0.)] (4.13)
Readers should refer to the appendix for full derivation. Let,
22 = ; C(n)Y1(n)Y2(n). (4.14)
The mean and the variance of this random variable are given by,
#22 = N2afa§C(0), (4.15)

022- — 4N204102 4[ZC2() )(0+NC2(0.) (4.16)

 

Using the central limit theorem, the pdfs of 21 and 22 are assumed to be Gaussian,
f21(2) N N(#211021)- (4.17)

fz2 (Z) ’V N(#22,0z2)- (4.18)

Since C' (n) is the Fourier transform of A p(y), the following relationships hold,

= 2141991),
31
2001) = NAPUJ),
20201.) = NZA§3(y). (4.19)
n 9

Solving for 17 using the above facts and the assumption, from equation (4.8), that

69

 

y 9
20.2 2
1\r2ZAP(y)a‘11 [(71- — ) :1: 72 (j- — 1)]
N y 02 2 (4.20)
204
‘72

The threshold in equation (4.20), similar to the Time—Wigner method, depends on
the weighting matrix A p(y, wy). Thus, the spatial and the spectral characteristics of

the image are taken into account when choosing the appropriate threshold.

4.4 Watermark Detection for the Binary Watermark Sequence Case

The simplified embedding function in equation (4.5) shows that the square of the
watermark is used for the embedding, which in the case of a binary sequence of
{—1, 1} makes the extraction of the watermark impossible because the sign will be
lost through the square operation. Therefore, in the Wigner-Wigner method, pre-
processing and post-processing steps are introduced to account for this ambiguity.
The pre-processing shifts bit —1 to 0, so the embedded watermark is a sequence of

{0,1} instead of {—1,1}. Equation (4.5) can then be written as,

 

P(9)= P2(y)+ ZAP(3/awy) *w(9), (4-21)
Q49

2(9) = w(y)-

At the receiver, the extracted watermark is post-processed by converting every bit

since to

0 to -1. Once the extracted watermark is found with the post-processing step, the

same procedure described for Time-Wigner watermark extraction can be applied to

70

find the probabilities of false alarm and miss, where the extracted watermarked is,
113(9) = w(y) + 71(9) (422)

Similar to the Time-Wigner method, the probability of error for correct extraction

is,

Pe=%(Q (77W)+1_Q(:7/1—V::))’ (4.23)

where 77 is a pre—defined threshold and 0,2, is the attack variance.

 

4.5 Simulation Results and Comparison

In this section, we provide simulation results to demonstrate the performance of
the proposed embedding algorithm and the use of reference watermark. The wavelet-
based method in [67], has been implemented for performance comparison. In [67], the
authors propose a DWT based watermarking algorithm based on quantizing certain
DWT coefficients at each level. The DWT method embeds the watermark in the
wavelet domain of the image, which reveals the characteristics of the image at different
scales. Similarly, the Wigner—Wigner method embeds the watermark in the time-
frequency domain, which reveals the characteristics of the image at different frequency
components at different times.

In order to determine how many bits we can embed inside an image and keep a high
PSNR at the same time, different watermarks with different lengths are embedded
inside the host image. Figure 4.3 shows the PSNR values for different watermark
lengths. The PSNR values are in 70dB range even for large watermark lengths, i.e.
2048.

The proposed watermark embedding algorithm has been applied to a large number

of images [91]. Table 4.2 shows the average bit error rates (BERs) under different

71

attacks. Since the performance of the algorithm does not vary much with the choice
of the image (as can be seen in Table 4.2), in the rest of this section we focus on the

performance of the algorithm for the Lena image.

Table 4.2. Average bit error rate in detecting the watermark under different attacks
using 100 different images.

 

Attack BER
AWGN (PSNR=48.13db) 00065400031
AWGN (PSNR=36.0db) 00091400056
AWGN(PSNR=14.15db) 01821400425

 

 

 

 

 

 

 

 

 

 

 

 

JPEG (CR=1.7) 00075400031
JPEG (CR=7.7) 00151400061
JPEG (CR=20) 00514400134
MF (3 x 3) 00182400101
MF (5 x 5) 00415400121
MF (7 x 7) 00574400210

 

A binary watermark of length 256 is embedded into the Lena image resulting in
a PSNR of 80.2dB. The watermarked image in Figure 4.4 has no visible differences

from the original image, which satisfies the imperceptibility condition.

4.5.1 The Performance under AWGN, Median Filtering, Rotation, and
JPEG Compression
The performance of the Wigner-Wigner method is demonstrated under similar at-
tacks as in the Time-Wigner case, i.e. AWGN, median filtering, rotation, and JPEG
attacks. The extracted watermark was correlated with 100 randomly generated wa-
termarks at the receiver. The performance of the correlation detector is similar to
the Time-Wigner method, where the extracted watermark has the highest correlation,
when it is correlated with the true watermark, among all possible watermarks at the

receiver. The correlation detector response for sample attacks is shown in Figure 4.5.

72

PSNR versus number of bits

 

 

 

105» -
100 -> 4
95- .
a
3
a: - .
z 90
(I)
(L
85 - 4
80- -
75- -

 

200 400 600 800 1000 1200 1400 1600 1800 2000
Number of bits

Figure 4.3. PSNR versus number of bits.

4.5.2 Comparison between the Wigner-Wigner and the Wavelet Methods

For the comparison with the DWT method proposed by Kundur [67], a binary wa-
termark sequence of length 256 is embedded. Figure 4.6 through Figure 4.8 show
the correlation detector response for both methods under AWGN, median filtering,
and .1 PEG compression respectively. The proposed Wigner-Wigner method performs
better than the DWT method under all attacks. The DWT-based method embeds the
watermark in every DWT level, where some of these levels are less robust to attacks.

Moreover, the Wigner-Wigner method embeds the Wigner of the watermark inside

73

Watermarked Lena Image PSNR=80.2dB

 

Figure 4.4. The watermarked Lena512 image with PSNR=80.2dB.

the Wigner distribution of the image, while the DWT embeds the binary watermark
itself in the DWT domain, which gives more security to the Wigner-Wigner method.
The use of the error key in extracting/ detecting the watermark in the Wigner-Wigner
method improves the robustness of the proposed algorithm. In addition, the DWT-
based method sends more side information in order to extract the watermark. The
locations of all modified coefficients in every level at each scale of the DWT should be
available at the receiver. This large amount of side information is a drawback for the

DWT-based method. Although both methods have the ability of embedding binary

74

AWGN Median Filtering

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

‘5' 75
ii 0.64 1 "*5 0.6'
8 . 8
S S 0.4
E :5 0.2 -
“5’ “5’ o (WM/[[0110
o o
0 . . . . 0 -o.2 . . . . 4
20 40 60 80 100 20 40 60 80 100
a b
Rotation JPEG
g . . - ‘5' 1 . . .
:0; 0.6’ 3506'
E E 0.2’ 1
g 2
° 3 00104104141171]
0 A A . L o . n n
20 40 60 80 100 20 40 60 80 100
c 11

Figure 4.5. The normalized correlation detector response for the Wigner—Wigner
method applied to Lena512 image under, a. AWGN=14.5dB,b. Median Filtering
size=7 x 7, c. Rotations 1°, d. JPEG CR=20.

watermark sequences, the Wigner-Wigner method has the advantage of embedding

Gaussian sequences as well, which makes it suitable for more applications.

75

AWGN comparison: Vlfigner-lMgner method
1 r r ’fl—T’.

 

-L

 

.0
(D
r
\
\

-+-wwq

_O
G)
I

\

 

 

I’ I 'O'DWT

p
N
I

\
\

 

o p
0'! a:
5

s
‘I

s

s

s

o
h

x
C

Correlation Coefficient

 

 

o 10 20 30 4o 50
PSNR (dB)

 

Figure 4.6. Comparison between the DWT and Wigner-Wigner methods under
AWGN.

76

Comparison under Median Filtering: Wigner-Wigner method

 

 

 

 

 

 

 

 

1$.~l I l I l l l
\ ~~‘*~
0.9-\ ‘~.~
\ ‘+..
0.3- \ ."-l- -
\ ‘~.~ ]
«H _ \ §
507 \ f
€06 ‘
g ' ‘\ -e-0wr
'fi \
50.4' G
t \ -+-ww
0 s
00.3' \
x
- s
0.2 \
x
0.1- \O--
---e.-.-
0 l l l l l I l
1 2 3 4 5 6 7 8 9
FillerSize

Figure 4.7. Comparison between the DWT and Wigner—Wigner methods under Me-
dian Filtering.

77

Comparison under JPEG: Wrgner-Wigner method

 

 

 

 

 

 

 

 

1“. I I I I I I I
\ ‘~.
09~° f‘u '°'DWT~
' \ ~~~
~§ -+-ww
03 ‘, *~..~ -
\ ~~~~~~
507 \ ‘~0
.9 \
0
EO.6~ \
8 \
0 _ \
.5 0.5 ‘
$04 A ~
L \
8 \
O.3~ ‘ ~
\
\
0.2" ‘
\
01- ‘s
. °---.-
0 1 1 1 1 1 1-."'II1_
0 5 10 15 20 25 30 35
Compression ratio

Figure 4.8. Comparison between the DWT and Wigner-Wigner methods under J PEG
compression.

78

4.6 Discussion

The proposed Wigner-Wigner watermarking method, which is an extension of the
Time-Wigner method, embeds the Wigner distribution of the watermark inside the
image. Therefore, the Wigner-Wigner method uses the time—frequency characteristics
for both the image and the watermark, while the Time-Wigner method uses the time-
frequency information only for the image. Similar to the Time-Wigner method, the
time-frequency domain embedding algorithm in the Wigner—Wigner method is sim—

plified to a non-linear function in time that depends on the square of the watermark,

 

Pry) = P20) + 24.00.44,) 4 242(4). (4.24)
”I!
The simplified function can be used for watermark embedding, instead of the time-
frequency domain function, to reduce the number of computations.
The Winer-Wigner method has also the ability of embedding both Gaussian and

binary watermark sequences. In this case, the threshold that is used to detect the

szAp(;r/)oi1 [( —1)i\/2(?%—1)]
9 ‘72

77 z . (4.25)
1 4)
‘72

The threshold in equation (4.25) shows that the Wigner-Wigner method depends on

watermark is,

[\3
HM

0'

to
q
q“; NM

N 2, which makes it more dependent on the length of the subset, P(y), compared
to the Time—Wigner method. Moreover, finding the threshold and implementing the
detector in the Time-Wigner method is simpler because of the convolution operation
in the Wigner-Wigner method, which makes the detection more complicated as we

need to find the Fourier transforms for A p(y), 1122(3)) and 1212(y).

79

4.7 Summary

In this chapter, we introduced a novel watermarking algorithm based on embedding
the Wigner distribution of the watermark inside the Wigner distribution of the signal.
The embedding algorithm in the time-frequency domain is simplified to a non-linear

function in time that depends on the square of the watermark,

 

Pry): P2<y)+ ZApry,wy> W20). (4.26)
“’3!

This square operation makes the extraction of the binary watermark impossible,
since the sign is lost. Thus, we proposed a pre—processing and post-processing op-
erations, where the binary sequence of {—1, 1} is shifted to {0,1} at the embedder,
and the received watermark is converted back to {—1, 1} at the receiver. This sim-
plification, similar to the Time-Wigner method, is based on the assumption that the
watermarked distribution is a valid Wigner distribution. However, since this is hard
to satisfy, an error is introduced by the inversion process. The introduced error is
analyzed and found to be concentrated in the low frequency range. This error is saved
as a key and used for watermark extraction/ detection at the receiver.

In this chapter, similar to the previous chapter, two detection algorithms are
derived for the Gaussian and the binary watermarks cases, respectively. The per-
formance of the proposed Wigner—Wigner method is evaluated through embedding
a binary watermark sequence. The correct detection of the embedded watermark is
validated after attacks.

The proposed watermarking method is compared with a well-known DWT—based
method. Although the watermark sequence in the DWT is repeatedly embedded in
every scale of the DWT of the image, our proposed method, which embeds the water-
mark just once, outperforms the DWT method in all attacks. The proposed method

reduces redundancy in the algorithm and provides higher accuracy and security at

80

the expense of increased computational complexity.

81

CHAPTER 5

WATERMARKING IN THE AUTOCORRELATION DOMAIN

The major challenge for watermarking in the Wigner domain discussed in Chapters
3 and 4, is that once the Wigner distribution is watermarked, it is no longer a valid
distribution and the time signal, 3(71), can be recovered using the approximation in
equation (2.6). This approximation introduces some error in detecting or extracting
the watermark. This error is sent as a key to add robustness to the detection of the
watermark. Therefore, one of the biggest shortcomings of the Wigner-based methods
is that the original image and an extra key that contains the error in inverting the
Wigner distribution are needed for watermark detection. Another shortcoming of the
Wigner-based watermarking methods is that the computation of the weighting matrix
in the Wigner-based method makes it unsuitable for real-time applications, where the
watermark is required to be embedded in a very short period of time. The non-blind
detection algorithm is another disadvantage for the Wigner-based methods. These
constraints limit the use of the Wigner—based method in certain applications such as
real-time verification systems.

In this chapter, we introduce a new image watermarking method that is equivalent
to watermarking in the Wigner domain without the limitations mentioned above.
Unlike the Wigner-based methods, the proposed method can embed only a binary
watermark sequences. The binary watermark is embedded in the local autocorrelation
domain, which is related to the Wigner distribution through a Fourier transform
and has no aliasng and invertibility problems. The pixels to be watermarked are
chosen randomly from the original image. This ensures the security of the embedded
watermark. The time-varying autocorrelation function for the chosen pixels is found

and the watermark is embedded such that the modified autocorrelation is still a valid

82

autocorrelation function. This will ensure the invertibility of the autocorrelation
function and will enable us to extract the embedded watermark bits. The robustness
of the proposed autocorrelation based watermarking method under different attacks
such as rotation, filtering, AWGN, and J PEG compression is evaluated by computing
the probability of error.

This chapter is organized as follows. Section 5.1 gives a brief introduction on the
autocorrelation function. Section 5.2 introduces the embedding algorithm, whereas
Section 5.3 introduces the extraction algorithm. In Section 5.4, the analysis of the
proposed method under attacks is provided. Simulation results and comparison with
other well-known methods are demonstrated in Section 5.5. Some final remarks and

discussion are given in Section 5.6. Finally, Section 5.7, summarizes the main points

of this chapter.

5.1 Background

The use of autocorrelation function for watermarking has been previously mentioned
in literature [92, 93]. The autocorrelation function used in these papers is the regular
autocorrelation function which represents the well-known correlation based detector,
that has a peak when the extracted watermark is correlated with the original one.
Unlike this autocorrelation function, the autocorrelation function used for watermark-
ing in this chapter represents a time-varying function that is related to the Wigner
distribution through an inverse Fourier transform.

It is obvious from equation (2.3),
m .
wow, 02) = 2 Z s(n + m)s*(n — m)e-J2W, (5.1)
m=—oo

that the Wigner distribution is the Fourier transform of a time-varying autocorrela-

tion function 7(m, n) = s(n + m)s*(n — m). The autocorrelation function has some

83

properties that make it a good choice for watermarking applications. First, for real
and positive-valued discrete time signals, such as images, the signal can be retrieved

from its autocorrelation function as 3(71.) = 4/r(n,0). Second, the autocorrelation

function of a real signal is symmetric. These properties simplify the embedding and
detection algorithms in image watermarking.

Since Wigner distribution is the Fourier transform of every other row of the auto-
correlation matrix, embedding the watermark in the Wigner distribution is equivalent
to embedding it in the autocorrelation domain. The autocorrelation function for a

discrete-time signal of length M can be written as:

7‘(m, n) = 3(n + m)s*(n — m), (5.2)

where m = [:2M], :éli + 2, ..., [%’I—], n = 1, ..., M and [9:] is the largest integer less
than or equal to :r.

The autocorrelation written in matrix form for the signal 3(n) =

{81 32 33 84 85} is:

0 0 3135 0 0
0 8183 8284 8385 0

74772,"): 3% 3% 5% .32 3% - (5-3)

 

0 .3133 8284 8385 0

 

 

0 0 8185 0 0]

The symmetry of r(m, n) and the invertibility, 3(n) = ‘/r(0, n), are clear from the

above example. Since 7(m, n) is symmetric, we consider only the positive indices,

84

22222
31 32 83 54 35

74072:"): 0 8183 8284 8335 0

 

 

_ 0 O 31.95 0 0 J

The proposed method modifies the non—zero elements of 7+(m,n) for m > O.
r(0,n) is not modified directly to preserve the visual quality of the watermarked
image. For a signal of length M, we have ELLE—Mil watermarkable points. For

the example given in equation (5.3), the number of watermarkable locations in the

autocorrelation function will be 4, which correspond to 3133, 3234, 3335 and 3155.

5.2 Watermark Embedding

For simplicity, we consider an N x N image and a binary watermark sequence 11) of
length L consisting of {~1,1}. The embedding algorithm which is illustrated in Figure

5.1, can be summarized as follows:

1. Choose randomly a subset of pixels from the original image. This subset should
have at least 2\/L+1 points from the image to ensure that we have L watermark-
able cells by the relationship given in the previous section. In this dissertation,
we choose 2L + 1 points, 8(7).) = {31, 32, ..., 82 L +1}, which give L2 watermark-
able cells. This will provide a degree of freedom in choosing the locations to
insert the L watermark bits in the next step. A key K 3 containing the locations

of the selected pixels is stored.

2. Compute the autocorrelation function r+(m,n) for s(n) and choose the wa-
termarkable locations according to a randomly generated key Kr. The key,
Kr, should choose L distinct locations among-the L2 non-zero points in the

autocorrelation function with the exception of the row at m = 0.

3. Since every coefficient in 7+(m,n) is a product of two points of the original

85

 

 

 

 

 

 

 

 

 

 

Original Image
Image [Autocorrelation ll Kr
ode“
Kn
[ Waterrnerked
image
Encoder .___..

 

 

 

 

 

Watennerk
1 Generation

1

Watermark. w

 

 

 

 

Figure 5.1. The block diagram for the embedding algorithm for the autocorrelation
method.

signal s(n), we can write:

1"+(M) = 37+j—13j—1'+11 (5.5)
where 7' = 1,2, ...,L +1 and j = 1,2, ...,2L +1.
4. Fix min(s,-+j_1, sj_,'+1) and modify max(s,-+j_1,sj_i+1). We keep the pixel

with minimum value unmodified since any small change in a small valued pixel

86

will cause a perceptible distortion in the watermarked image. Also, modify-

ing large values will provide more robustness against attacks. The embedding

process can be written as,

max(§,'+j_1,.§j_i+1) -'= max(s,-+j_1, Sj—i+1)(1 '1' (Hall), (5'6)

where a) is the weighting coefficient of the 1th bit for l = 1, 2, 3, ..., L. The value

of max(s,-+j_1, sj_,+1) before modification is stored in a key, K p.

5. Modify all locations in r+(n,m) that contain max(s,+j_1, sj_,-+1) with the

new value of max(.§,-+j_1, 3j—i+1)-
6. Repeat steps (3 — 5) for every watermark bit.
7. Obtain the watermarked signal 8(71) by taking the square root of 7+(0, n).

The weighting coefficient at is derived such that the max(§,-+j_1, éj—Hl) remains

greater than min(s,-+j_1, sj_,~+1). This ensures that the watermark extraction is

possible. The weighting coefficients are derived as follows:

 

 

 

max(si+j—lr Sj—z'+1)(1 + Orwr) 2 min(31'+j—1:3j—z'+1)- (5-7)
min 3- -_ ,s-_'
011012 (2+3 1 ] 2+1) _1. (5.8)
max(37'+j—113j—i+1)
If 11), = 1 then,
min 8- -_ ,s-_-
012 ( 1+3 1 ] 2+1) _1. (5.9)
maxf$i+j—1,8j—z'+1)
If to, = —1 then,
min(s- -_ ,s-_-
01131— 2+] 1 J 1+1) (5.10)

maX(84+j—1rSj—i+1)'
In order to satisfy both equations (5.9) and (5.10), we choose at = c(1 —

min(si+j_1,sj_i+1)
> 0; where 0 S c S 1 is a constant. Usin this relationshi ,
max(sz'+j—1a3j—z'+1)) g P

87

the weighting coefficient for each watermark bit is adapted based on the particular
pixel value, and the strength of the watermark can be adjusted by choosing c.
As a numerical example to illustrate the embedding process, let 3(71) =

{100, 128,110, 99, 95}, w = {1,—1,1} and c = 0.2. The autocorrelation function
for 3(n) is,

[10000 16384 12100 9801 9025
r+(m.n)= 0 110001267210450 0 . (5.11)

 

 

0 0 9500 0 O ]

Let K,» contain the locations for 5133,3234,33s5. For I = 1, wl = 1. Since

53 = 110 > 31 = 100, we embed 101 into 33. The results for embedding the first bit

are,

Kr = 3133,

041 = 0.018,

823 = 33(1+ 071101) =112,
KP, = 110,

s(n) = {100, 128, 112, 99, 95}.

(5.12)

88

For the second bit, I = 2,

1112 = -1,
Kr = 3234,
042 = 0.045,

8A2 = 82(1+ 02102) = 122.2,

3(n) = {100,122.2,112,99,95}.

(5.13)
For the final bit, we get,
1103 = 1,
Kr = S385,
073 = 0.030,
8A3 = S3(1+ 03103) = 115.4,
Km 2 112,
5(n) = {100, 122.2, 115.4, 99, 95}.
(5.14)

5.3 Watermark Extraction

In order to study the performance of the detector, probability of error will be derived.

In this dissertation, we assume that we have access to the keys K 3, Kp and Kr at

the receiver. The semi-blind extraction algorithm can be implemented by performing

the same steps in the embedding algorithm in the reverse order.

The extraction algorithm, as shown in Figure 5.2, can be summarized as follows:

89

1. Extract the watermarked pixels, 8(71), using the key K 3.
2. Compute the autocorrelation function r+ (m, n) for §(n).

3. Using K r, determine the modified locations in the autocorrelation function.

4. Find max(.§,-+j_1, éj-Hl) for r+(z',j) where 2' and j are determined from Kr
and then use the last stored value for max(s,-+j_1, sj_,-+1) in Kp to find the

sign of 0'le and determine the value of 10) according to,

max g. ._ ,§._.
(2+3 1 ] 2+1) _1). (5.15)

10 = sgn(a w ) = sgn
l l l (max(si+j—laSj—z'+1)

which can be written as,

max(§i+j—la§j—i+1) _1 > 0 (516)
maX(55+j—1,8j—4+1)

5. Replace max(.§,-+j_1, éj—i-i-l) With max(s,-+j_1, Sj—i+l)'

6. Repeat steps (3-5) for the next watermark bit. The embedded watermark se-

quence is extracted in the reverse order, 761 for l = L, L - 1, ..., 1.

As a numerical illustration of the extraction algorithm, we continue with the
example given in the previous section. As we mentioned earlier, the watermark is

extracted in the reverse order. Therefore, in the first run we extract the first bit of

the watermark sequence,

90

AWGN JPEG

 

 

Watermark
inverse- mm

 

 

 

 

 

 

 

€
25
3‘

Rotation Filtering

Figure 5.2. The block diagram for the watermark extraction algorithm for the auto-

correlation method.

Kr = 8335,

3(71) = {100,122.2, 115.4, 99, 95},
. 115.4

1123 —sgn (—112 — 1) — 1,

323 = K173 = 112,

s(n) = {10012221129095}.
(5.17)

91

The output for the second run is,

Kr = 3254,

801) = {100, 122.2, 112,99, 95},

122.2
‘ = — 1 = .—1
1112 sgn( 128 ) ,

8,2 =3 K192 : 128,

 

3(n) = {100,128,112,99,95}.

(5.18)
Finally for the first watermark bit,
Kr = 8133,
s(n) = {100,128,112, 99,95},
112

7 = _ _ 1 = 1

ul sgn (110 ) ,

5(n) = {100, 128, 110, 99,95}.
(5.19)

The above example shows that we can extract the watermark and get the original

signal without any error assuming that there is no corruption in the received image.

The following section analyzes the effect of the attacks the image may undergo through

on the recovery of the watermark.

5.4 Analysis of the Algorithm under Attacks

In the Wigner-based methods, the extraction algorithm for the binary watermark

case allows us to extract the whole watermark sequence at once. Therefore, we are

92

able to model any attack on the watermarked image as additive noise. However, in
the autocorrelation method, the watermark is extracted bit by bit in reverse order.-
This method of extraction, allows us to model the attack as additive noise on each
watermark bit and thus we can find the probability of error in extracting every wa-
termark bit. As mentioned in [95], we can model the attacks on the watermarked
image as additive white gaussian noise 71),, which is uncorrelated with the pixel value.

For each pixel in the watermarked sequence 8],, the pixel value after an attack can

be written as,

5k = 5k + nk. (5.20)
Therefore, the detection rule in equation (5.16) is modified as:

51:1

17.) >
w, + 0. (5.21)
almax(3-i+j—173j—i+1) <

 

_1_ (max(§z'+j—1a§j—z’+1) __1
0‘1 max(sz'+j—113j—i+1) '
The probability of error P6,, assuming equal a prior probabilities for {-1,1}, for

where w) =

the 1th watermark bit can be derived as,

[anr > almax(32'+j—113j—i+l))+ PW < —armaX(Si+j—1-3j—z'+1))]
(5.22)

Fe

er—I

l =

The variance of noise is estimated using the robust median estimator in the discrete
wavelet domain given by [96]:
Median( Y, )

(in, = 0.6745 ~ ,le E subband HHl. (5.23)

 

 

 

93

The mean fin, of n, can be estimated by subtracting the mean of the original image
from the mean of the received image. By plugging in the expression for a) from

Section 5.2, we get

max(s,-+j—1,Sj—i+l) ‘ min(si+j-1’Sj—2+1) — (inf) (5 24)

P61 : Q (C 6741

where Q(y) = fi 2004130 g» dt.

From equation (5.24) it is seen that as 0 increases, the watermark strength in-
creases and P6, decreases as expected. It is also observed that as the difference
between max(s,-+j_1,sj_,-+1) and min(s,-+j_1,sj_,-+1) increases, the probability
of error will decrease. This suggests that if we embed the watermark into elements
of the autocorrelation matrix that correspond to the correlation of pixels that have
a large absolute difference, the algorithm will be more robust against attacks. More—
over, equation (5.24) gives the error for every watermark bit, so for a watermark of
length L we can find the bit error rate (BER).

It should be noted that the model in equation (5.20) is not always realistic. For
example, in some cases the attack ”k is actually correlated to the signal and cannot
be modeled as additive white Gaussian noise. Thus, equation (5.24) will not be valid

for all attacks.

5.5 Simulation Results and Comparison

In this section, we demonstrate the performance of the proposed method through
various simulations with different attacks. We also, compare the proposed method
with spread spectrum method [63] and the DWT method [68]. The reason to choose
these two methods is because of the similarity between the proposed method and the
methods in [63, 68]. In [63], the watermark is embedded in the DCT domain and is

spread out through the whole image, similarly, the proposed method embeds the wa—

94

termark in the autocorrelation domain and the watermark is also spread out through
the whole image. On the other hand, the method in [68] embeds the watermark in
the DWT domain repeatedly in different scales. The proposed method, is similar
in the way it embeds every watermark bit repeatedly in all locations of 7+(n,m)
that contain max(s,-+j_1, sj_,-+1). We also show the performance of the proposed
method in embedding and extracting logos when the watermarked image undergoes
distortion.

The watermark embedding algorithm in the autocorrelation domain has been ap-
plied to a large number of images [91] using c = 0.2 and L = 256. Table 5.1 shows
the average bit error rates (BERs) under different attacks. Since the performance of
the algorithm does not vary much with the choice of the image (as can be seen in

Table 5.1), in the rest of this section we focus on the performance of the algorithm

for the Lena image.

Table 5.1. Average bit error rate in detecting the watermark under different attacks
using 100 different images.

 

c 0.2
AWGN (PSNR=48.13db) 0.0075:i:0.0051
AWGN (PSNR=36.0db) 0.0421:l:0.0063
AWGN(PSNR=14.15db) 0.1572i0.0098

 

 

 

 

 

 

 

 

 

 

 

 

JPEG (CR=1.7) 00215400076
JPEG (CR=7.7) 00842400153
JPEG (CR=20) 01421400213
MF (3 x 3) 01041400211
MF (5 x 5) 01105400134
MF (7 x 7) 01254400242

 

The autocorrelation method, unlike the Wigner-based methods, allows us to ex-

tract one bit of the watermark at a time. Therefore, we will report the results in

95

terms of the average bit error rates (BERs).

The watermarked Lena image is similar to the original one with no visible differ-
ences with PSNR=44.5dB. Figure 5.3 shows the watermarked image using c = 0.2.
The algorithm has been tested under different attacks and for different embedding
parameters. We ran the algorithm 100 times by generating different watermark se-
quences. The average bit error rates with their standard deviations are reported.
Table 5.2 shows the effect of the choice of c on the robustness of the proposed algo-
rithm under additive white gaussian noise ’AWGN’, JPEG compression, and median

filtering ’MF’. The algorithm maintains a low (BER) even for low J PEG compression

ratio.

Table 5.2. Bit error rate in detecting the watermark under different attacks for

different values of c.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

c 0.05 0.1 0.2
AWGN(PSNR=48.1dB) 00340.01 0.024001 00140.01
AWGN(PSNR=36.1dB) 0.094001 0.054002 0.044001
AWGN(PSNR=28.1dB) 0.114001 0.094002 00540.01
AWGN(PSNR=142dB) 01440.03 01340.03 01540.02
AWGN(PSNR=8.1dB) 01740.03 0.154003 0.154003

JPEG(CR=1.7%) 0.044001 00340.01 0.024001
JPEG(CR=7.7%) 01240.02 01040.02 0.084002
JPEG(CR=20%) 01640.02 01440.03 01440.02
JPEG(CR=37%) 01840.02 0.164001 0.16:l:0.03
MF(3x3) 0.114001 01040.03 0.104002
MF(5x5) 0.124002 0.124002 01140.01
MF(7><7) 01340.02 01240.01 01240.01

 

96

 

Watermarked Image PSNR=44.5dB

 

Figure 5.3. The watermarked image with PSNR=44.5dB using c = 0.2.

5.5.1 Comparison between Autocorelation, Wavelet, and Spread Spec-
trum Methods

The proposed algorithm is also compared with a well-known watermarking algorithm

based on the Discrete Wavelet Transform (DWT) introduced by Kundur and Hatzi-

nakos [68]. In their work, the authors propose a DWT based watermarking algorithm

based on quantizing certain DWT coefficients at each level. For comparison, we em-

bed the same watermark sequences. As another comparison, we compare the proposed

method with the well-known spread spectrum watermarking [63]. In this method, the

97

watermark is embedded into the highest magnitude DCT coefficients of the image.
The watermark is extracted by comparing the DCT coefficients of the watermarked
image and the original image. In [68, 63], the authors try to detect the watermark,

so in this comparison, we use a correlation based detector to detect the watermark,

(19(9). 227(9)) 77, (5.25)

where, w, and, 113, are the original and the extracted watermarks, respectively.

In all three methods, the extracted watermark is correlated with the true wa-
termark and the correlation value is reported for different attacks. For the sake of
this comparison, a binary watermark of length 256 is embedded in all methods. The
results indicate that our method outperforms the DWT method and has better, but
close, performance with the spread spectrum method for the tested attacks as shown
in Figure 5.4 through Figure 5.6. The DCT method embeds the watermark in the
largest magnitude DCT coefficients of the host image, which requires the use of small
weighting coefficients to provide an invisible watermark. Thus, the strength of the
watermark will be low and any distortion in the image will affect the detection of
the watermark. On the other hand, the DWT method is based on quantizing certain
DWT coefficients at each level. This quantization introduces some error in the ex-
traction process. Embedding the watermark in the pixels with the largest values in
the autocorrelation domain, explain the close performance of the proposed method

with the DCT method.

98

Figure 5.4. Comparison between SS, DWT, and Autocorrelation methods under

AWGN.

AWGN comparison: Autocorrelation method

 

 

 

 

 

 

 

 

 

 

I ’1’
I ’ ’

0.9"

0.87
5 07*
'1} ' +88
11:
8 o
o ' -->-'AC
S
:5 0.5- ’1
g 04 ’

. 1 I
0 I

0.3” I

,0
0.2% I
0.1 l l l l l l l l
10 15 20 25 30 35 40 45
PSNR (dB)

99

50

Comparison under Median Filtering: Autocorrelation method

 

 

 

 

 

Correlation Coefficient
N co 4x on '0) K1

5:
A
I

 

 

 

 

Filter Size

Figure 5.5. Comparison between SS, DWT, and Autocorrelation methods under
Median Filtering.

100

Comparison under JPEG: Autocorrelation method

1 I I I I I I I

 

5::
N

P
O)

 

9
(’1

Correlation Coefficient
.0
A

.0
(A)
I

 

 

 

SD
M

 

_o
_L

 

 

l l l l

10 15 20 25 30 35
Compression ratio

1 l

O
01

Figure 5.6. Comparison between SS, DWT, and Autocorrelation methods under
JPEG compression.

101

5.5.2 Results for the Binary Logo Case

We have also embedded a logo image as the watermark inside the image. The logos,
serve as a quick check for signaling and locating tampering. The decision on whether
an image is altered or not, can be made automatically by comparing the extracted
pattern with the original one, if available, or by human testing based on visualizing
the extracted pattern. The latter case uses a reasonable assumption that the human
can distinguish a ’meaningful’ pattern from a random one. Figure 5.7 shows the
extracted logo under different attacks. It is clear that we are able to extract the
watermark even when the image goes through different distortions. Moreover, to test
the performance of the proposed method when the watermarked image goes under
multiple attacks, we applied the AWGN (PSNR=28.13dB), JPEG (CR=5), rotation
(3°), and filtering (3 x 3) attacks in sequence to the watermarked image. Although
the image went through multiple attacks, the extracted logo is still recognizable as

shown in Figure 5.8 and has a correlation value of 0.8 with the original logo.

102

  
   

.uF

I

95:3. -.'- - ~ ‘. ama-

.' '

 

 
 
 

 

'.-a..I'a<..:-;--s=~4- ==

':,'H:.
I> I].

        

.‘fi'fir'f‘é":fl-"fl: -

H'-
w—-
_
-_ '
.-
'h
4.
_,-.
Q |.
.-
.475:

Figure 5.7. The extracted logo under different attacks a- AWGN (PSNR=22.11dB),
b- JPEG (CR=7.7), c- Rotation (7 degrees), and d- Median filtering (5 x 5).

103

The extracted logo under multiple attacks

 

Figure 5.8. The extracted logo after subsequent attacks of 1- AWGN
(PSNR=28.13dB), 2- JPEG (CR=5), 3- Rotation (3 degrees), and 4- Median filtering
(3 x 3).

104

5.6 Discussion

In this chapter, we proposed a watermarking algorithm in the autocorrelation domain.
This method, unlike the Wigner-based methods, can embed only multi-bit watermark.
The embedding algorithm embeds one bit of the watermark at a time. Therefore, at
the receiver, we extract the individual watermark bits. This way of embedding and

extraction allows us to model the attack as additive noise on each pixel value of the

image,

3k = 5}, + 71),. (5.26)

Therefore, we derived the probability of error in detecting every watermark bit,

(5.27)

,

maX(84+j—1,3j—z'+1) - min(si+j—lrSj-i+1)_ 1171,)

P61 = Q (C 5‘77.)

where Q(y) = -—1—— +fooex (— (t2)) dt
7% 2 7 '

y
The probability of error in extracting the watermark in equation (5.27) can be

used to improve the performance of the proposed algorithm. If P3, is greater than
a predefined threshold, an error occurred in extracting the lth watermark bit and

therefore, the bit should be reversed,

w, = 112)
where 117, is the complement of 7.0,. However, improving the performance this way

depends on the accuracy of the noise model, since not all attacks can be modeled

105

as additive noise. For example, AWGN can be modeled as an additive noise, while

JPEG compression is not well approximated by additive noise. This is illustrated in

Figure 5.9.

AWGN

0.4Kn ., r r r r 1 fl
» _ —E1—Simulation results
~O~ Analytical results .

 

 

 

 

 

I

0.1

Probability of error
0
N

K-LJ

 

l l l

0 l 1 4 l L
5 10 15 20 25 30 35 40 45

 

 

 

 

 

 

0
PSNR(dB)
JPEG Compression
g 01- ~
«5 0.08 - -
g 006- -
g . o , O
8 0'04 b 0
d: 0.02 - . _
0 1 2 3 4 5
Compression Ratio

Figure 5.9. Comparison in computing the probability of error from the simulations
and the analytical results in equation (5.27).

106

5.7 Summary

In this chapter, we presented a new robust watermarking algorithm based on the
local autocorrelation function. The autocorrelation function is modified such that the
watermarked function is still a valid autocorrelation function. A semi-blind detection
algorithm is derived and its performance is quantified by deriving the probability
of error. The proposed autocorrelation based watermarking algorithm is shown to
be robust and provides high capacity. The number of bits that can be embedded
for an M x M image is M, which is around 33421488 bits for an image of
size 512 x 512. This does not mean that we can embed this large number of bits
without degrading the visual appearance of the watermarked image, but it enables
us to embed a large number of bits that can be suitable for any application and at
the same time keep a high PSN R for the watermarked image.

In addition to the ability to embed large amount of data, the algorithm is shown to
have reasonable computational complexity and high watermark security. The compu-
tational complexity of the proposed embedding algorithm is of order 0(M2). Thus,
the autocorrelation method can be used in real-time applications. In terms of security,
the semi-blind extraction algorithm makes it more secure compared to Wigner-based
methods, because some keys and side information, not the original image, are needed
for watermark extraction. This side information can be reduced or eliminated which
in turn will increase the security of the algorithm. For example, instead of generating
Kr randomly, we can choose the first successive L non-zero points in the autocorre—
lation function 7+(m, 77.). Moreover, we can choose a row from the image and use it
for watermark embedding, to get rid of the K p key.

The comparison with the well-known spread spectrum and DWT-based methods
shows the superior performance of the proposed method. The proposed method uses

semi-blind detection algorithm to detect the watermark, while the SS and DWT

107

methods need the original image for watermark detection. The semi-blind detection

algorithm makes the proposed algorithm suitable for a wide class of applications.

108

CHAPTER 6

A COMPARATIVE STUDY OF THE THREE PROPOSED
TIME-FREQUEN CY WATERMARKIN G METHODS

In this chapter, we provide a quantitative comparison of the three time-frequency
based image watermarking algorithms proposed in this dissertation. Moreover, we
introduce techniques to improve the performance of the proposed methods. In Section
6.1, a comparison between the three proposed methods will be carried out based
on computational complexity, watermarking capacity, detection / extraction type, and

robustness. In Section 6.2, techniques to improve the performance of the proposed

methods are introduced.

6.1 Comparison between the Three Time-Frequency Domain Water-

marking Methods

In Chapters 3 through 5, we have introduced three different methods. For each
method, we gave a complete mathematical analysis at the encoder and the decoder.
Moreover, comparisons with competitive well-known methods in other transform do-
mains have been carried out. In this section, we compare the three proposed methods
in terms of computational complexity, capacity, and robustness. Before we proceed
with this comparison, we like to emphasize that the Wigner-based methods have the
ability to embed Gaussian and binary watermark sequences, unlike the autocorre-
lation method which embeds a binary watermark. Although the simulation results
provided for the Wigner-based methods are for the binary watermark case, similar
simulations can be carried out for the Gaussian watermark case. The binary wa-
termarks are preferable over the Gaussian ones in many applications including data
hiding and ownership declaration. Thus, we focused on embedding binary watermarks

throughout this dissertation. For the rest of this chapter, we assume the watermark

109

is a binary sequence of length M, and the image is of size M x M unless otherwise
stated.

We also like to emphasize that in some applications, it is desirable to embed more
than one watermark, where each watermark has a different purpose. For example, the
first watermark may reveal the name of the image owner and the second watermark
reveals the date of creating that image. A good watermarking algorithm should be
able to detect both watermarks, even when the watermarked image goes under dif-
ferent attacks. As an example on using the proposed algorithms to embed multiple
watermarks, we embedded two binary watermarks each of length 512 bits inside the
lena image using the autocorrelation method. Figure 6.1 shows the correlation func-
tion under AWGN (PSNR=22.1dB). The maximum correlation occurs at sequence

100 and sequence 150, which correspond to the first and the second watermarks,

respectively.

110

 

AWGN (PSNR=22.1dB)

I I I l I I l I I

 

0.8 - 7

IO
0)
I

 

Correlation Coefficient
O
A

F)
N

 

 

O

 

 

-0.2
1 1 r 1 1 4L ML

20 40 60 80 100 120 140 160 180 200

Figure 6.1. The normalized correlation detector response for the autocorrelation
method with two embedded watermarks under AWGN with PSNR=22.1dB.

111

6.1.1 Computational Complexity

We have shown that the Wigner-based methods reduces the embedding algorithms
to a non-linear functions in the time domain. However, these non-linear functions
are dependent on the weighting matrix which is dependent on the Wigner distrib-
ution of the chosen pixels, P(y). Thus, the most computationally complex part in
the Wigner-based methods is finding the weighting matrix. To compute the weight-
ing matrix, we need to perform 0(M2) multiplications to find the autocorrelation
function for the input pixels. Moreover, we need M 2log(M 2) multiplications to find
the Fourier transform of the resultant autocorrelation function in order to compute
the Wigner distribution for P(y). Thus, we need M 2 + M 2log(M 2) computations to
find the weighting matrix for the Wigner-based methods, i.e. 0(M2log(M2)). On
the other hand, the autocorrelation method embeds the watermark in the autocorre-
lation domain, which has a computational complexity of 0(M2). The computation
of the Wigner distribution makes the Wigner-based methods more computationally
complex compared to the autocorrelation method. This computational complexity

limits the use of the Wigner-based methods to limited applications.

6.1.2 Capacity
In terms of the capacity, the simplified embedding functions for the Time-Wigner and

the Wigner-Wigner methods are,

 

 

Pry): P2ry)+ 24100.4.) wry). (6.1)
toy
and
1E’04): P2(y)+ 2419056941) *wzty). (62)
“’31

112

respectively. From the simplified functions, the maximum number of bits that can
be embedded inside P(y) are M, if the length of P(y) is M. Therefore, for an
image of size M x M, we have the capacity to embed up to M 2 bits, since we
can choose P(y) to be the whole image, i.e. of length M 2. The autocorrelation
method, on the other hand, has a capacity of embedding 441443.118 bits. Although
the number of watermarkable cells is high in all of the three methods, not all of the
watermarkable cells are used for watermarking. The constraint of having a high PSN R
value limits the number of embedded bits. Figure 6.2 shows the PSNR values for
different watermark lengths using the three proposed method. The Wigner-Wigner
method provides higher PSNR values, since embedding one bit of the watermark
sequence in the autocorrelation method will result in changing many pixels form
the original sequence, P(y). Moreover, the Time-Wigner method requires the same
watermark to be embedded into every column of the Wigner distribution of P(y),

which lowers the PSN R value.
6.1.3 Non-Blind and Blind Detection

As discussed in Chapters 3 and 4, both Wigner-based methods require the original
image or at least the original chosen pixels, P(y), for watermark detection / extraction.
On the other hand, the autocorrelation method does not need the original data for
watermark extraction. The semi-blind detection algorithm for the autocorrelation

method makes it more useful for a wide range of practical applications.

6.1.4 Robustness

In terms of robustness, the proposed methods are shown to be robust against different
types of image processing attacks and perform better than some of the most well-
known watermarking methods. In this subsection, we compare the performance of the
proposed time-frequency methods with each other under attacks. In order to provide

a fair comparison, we do not use the reference watermark technique in the Wigner-

113

PSNR versus number of bits

 

 

 

 

 

 

 

 

 

-A-Tw
'-fl- AC -
~o~ww
’0',
20",, q
A "'0' ......
m 4...,
o “'11....0
g A 0 MW,
% \A‘
n- 60. " ~~~‘.--- A .
I. . ------‘--_--*
50_ I. .
II
\
40’ '\ -
1‘.
30- . . .""."';°'"1"-'.-'-n-1n-.....
200 400 600 800 1000 1200 1400 1600 1800 2000
Numberofbits

Figure 6.2. Comparison between Time-Wigner (TW), Wigner-Wigner (WW), and
autocorrelation (AC) methods in terms of PSN R versus number of watermark bits

Wigner method. A binary watermark sequence of length 256 is embedded inside the
Lena image. The performance measure used is the correlation coefficient between the
extracted and the original watermark. Figure 6.3 shows a sample result under AWGN
attack. The figure shows that the proposed Time-Wigner method outperforms the
other two methods. This is expected, since the watermark in the autocorrelation
method is embedded in a recursive way. This way of embedding will cause any

error in detecting the watermark bit to affect the detection of the neighboring bits.

114

Moreover, the embedded watermark in the Wigner-Wigner method is {0, 1}, while it
is {—1, 1} in the Time-Wigner method. Thus, distortions on the watermarked image

in the Wigner-Wigner case will affect the extraction of the watermark more than in

the Time-Wigner case.

 

 

 

 

 

 

Comparison under AWGN
7 r r T I....1rrr] '-,_'£..|’1|Fifiw
““,r|‘A “" l
09- ”1,1 >“" ’ -
ANN] ’ I‘ I
1 I
0.8” ’1" I -
‘3 \’\ ’ l-V'AC
H \ ’ ’
c . ‘ .
,9 0J“- .~',.IV’ I -
,3 {3‘ I "lh"TVV
: I
80. , .
g I’ ...ww
.2 0.5- I -
.9 I
0 I
504- , -
O I
I
(13- , .
I
I
(12- I -
I
I

 

 

 

0.1? 1 1 1 1 1 1 1 1
10 15 20 25 30 35 40 45

PSNR

Figure 6.3. Comparison between Time-Wigner (TW), Wigner-Wigner (WW), and
autocorrelation (AC) methods under AWGN attack

As a summary for this section, Table 6.1 summarizes the main comparisons, be-

tween the Wigner-based and the autocorrelation methods. It is important to mention

115

that due the high computational complexity of the proposed algorithms, their usage

may be limited to certain applications like copyright protection and data hiding.

Table 6.1. A comparison between the Wigner-based methods and the autocorrelation
method.

 

Wigner-Based Autocorrelation

_ 2
Capacity M 2 MAL-

 

 

 

 

 

 

 

Multi-bit Yes Yes
Blind N on-blind Semi-blind
Computationally complex O(leog(M)) O( M 2)

 

 

6.2 Techniques for Performance Improvement

In this section, we discuss some techniques that can be used to improve the perfor-
mance of the proposed methods. This includes the use of the the pseudo-random

watermark generator and the reference watermark discussed in Chapter 4.

6.2.1 Pseudo-random Watermark Generator

In order to provide more secure and robust watermarks, the watermark can be gen-
erated using a pseudo-random generator. This idea has been used in [97] and has
been applied to other multi-bit watermarking algorithms. The original watermark

sequence w of length N is spread out to generate another sequence W of length M

according to,

N
W = sgn a Z 11),- ~15]- . (6.3,)
i=1

where 15,- is a pseudo—random sequence of length M and a is a gain factor that

determines the watermark magnitude.

The set P of N reference marks is constructed such that the pseudo-random

116

sequences are orthogonal to each other.

P: {p1,P2,...,PN}, (6.4)

13,: [P,-1,Pj2,...,P,-M], (6.5)

where P], 6 {-1,1}.

The initial state of the random sequence generator should be known by the em-
bedder and the detector in order to produce the same P. After W is created, it is
embedded instead of w and at the receiver we recover W of length M. In order to re-

construct the original watermark sequence, a binary decision is made on the decision

variable D k

1 M a
Dk = M Z W.- - P1... (6.6)
i=1
10k = sgn(Dk). (6.7)

Generating the watermark this way will increase the security of the embedding
algorithm, since the created watermark, W, rather than the original watermark is
embedded in the host data. Moreover, it will increase the robustness of the water-
marking algorithm, since the initial state of the random sequence generator is known
at the receiver which carries some side information about the original watermark.

In order to illustrate the effect of using the pseudo-random watermark generator,
we apply this generator to the autocorrelation method and compare the output with
the output obtained by embedding the watermark directly. The watermark is a binary
sequence of length 256 and c = 0.2. Table 6.2 shows that using the pseudo-random
watermark generator reduces the bit error rate to zero. This improved efficiency,
however, comes at the expense of using the extra seed key, which is transmitted to

the receiver. The results in Table 6.2 agree with the results for the method proposed

117

in [97]. In [97], the authors embed a multi-bit watermark inside an image using a

deterministic embedding scheme that ensures total embedding efficiency, i.e. zero bit

error rate.

Table 6.2. Bit error rate in detecting the watermark with and with out using
pseudo-random watermark generator

 

Generator No Yes
AWGN (PSNR=48.1db) 0.01 0.00
AWGN (PSNR=28.1db) 0.05 0.00
JPEG (CR=1.7) 0.02 0.00
JPEG(CR=7.7) 0.08 0.00
MF (3 x 3) 0.10 0.00

MF (5 x 5) 0.11 0.00

 

 

 

 

 

 

 

 

 

 

 

6.2.2 Reference Watermark

In order to increase the robustness of the proposed watermarking algorithms, we
may use a reference watermark. The reference watermark, which is assumed to be
known at the receiver, and the desired watermark are embedded in an orthogonal
way, which means that they are not embedded in 'the same pixels. The bit error
rate for the reference watermark is expected to be equal to the bit error rate for the
desired watermark. The following equation is used to determine if an error occurred

in the 1th bit of the reference watermark,

BE(z’) = 411.0) ea 427(4), (6.8)

where wr and '11“)? are the original and extracted reference watermarks respectively
and GB is the exclusive X—OR operator. If BE (2) equals 1 then an error occurred at

the 2th otherwise the extracted bit is correct.

118

If more than one reference watermark is used, a majority rule can be used to deter-

mine if an error has occurred at the 7th bit. For the case of R reference watermarks,

this can be written as,
R
Majority(z') = Z w,,,(r) 49 41,),(4) , (6.9)
k

where if Majority(z') = 1, the 1th bit of the extracted desired watermark is shifted.
Deciding the use of reference watermark is dependent on the targeted PN SR value
and the number of watermark bits. For example, if the number of watermark bits is
large and the targeted PSN R is high, using reference watermark is not recommended.
On the other hand, if the goal is to provide more accurate detection/ extraction, the
use of reference watermark is desirable. Therefore, the use of the reference water-
mark in the Wigner-Wigner method is justified, because the square operation in the

simplified function,

 

P(y)= P2(y)+ 24190114017) “92(9). (610)
wy

makes the watermark less robust and harder to extract. Therefore, we can use the
reference watermark to add more robustness to the Wigner-Wigner method. To
compare the results between using and not using the reference watermark, we test
the Wigner-Wigner method under the two cases for different attacks. Figure 6.4
shows the simulation results for the AWGN attack. The results, as expected, show

the superior performance of using the reference watermark.

119

Comparison between uisng and not using the reference watermark under AWGN

1 r r r 1 r r _ _ 1.. - 31"“;
a 4|" ' - - —I5'"""'"""

0.9 ' , fl ’ "\ ..

I ,‘ '->-' No reference

 

 

.CD
CD
I

\

I )I - + - Reference .

p
N

 

 

 

_-_
IT
\
l

Correlation Coefficient

$3 $3 .0
A 01 O)

I I

s

s
x
J l

5:
(A)
1

1

 

 

 

’.
01$! 1 1 1 1 1 1 1

10 15 20 25 30 35 4o 45
PSNR (dB)

Figure 6.4. Comparison between using and not using the reference watermark for the
Wigner—Wigner method under AWGN.

120

CHAPTER 7

CONCLUSIONS AND FUTURE WORK

7.1 Summary of the Dissertation

In this dissertation, three new watermarking algorithms based on the time—frequency
representation of the image has been introduced. It has been shown that for positive
and real signals, the signal can be retrieved from its Wigner distribution without any
error. This realization inspired the implementation of two time-frequency watermark
embedding methods; one uses the time-frequency distribution of the image, the Time-
Wigner method, and the other uses the time-frequency information for both the image
and the watermark, the Wigner-Wigner method. For both methods, under special
conditions as described in this dissertation, the embedding algorithm in the joint
domain can be simplified to a non-linear embedding function in the time domain
as long as the modified distribution is still a valid Wigner distribution. This result
reduces the computational complexity of embedding and detecting the watermark.
A non-blind correlation based detector is derived using the non-linear embedding
function and the probability of error is found in the case of Gaussian and binary
watermark sequences. The proposed algorithms are shown to be transparent and
robust under attacks through experiments.

The third method introduces a robust watermarking algorithm based on the 10-
cal autocorrelation function. The autocorrelation function is modified such that the
watermarked function is still a valid autocorrelation function. A semi-blind detection
algorithm is derived and its performance is quantified by deriving the probability
of error. The proposed algorithm is shown to be transparent and robust under at-
tacks. The proposed algorithm performs better than conventional transform domain

algorithms as illustrated through our comparison with a DWT based method and a

121

spread spectrum method.

All of the proposed methods have the ability to embed multi-bit watermarks. Each
of the proposed methods has a different advantage. The Time-Wigner method is the
best in terms of the perceptibility and PSNR values. The Wigner-Wigner method
should be used when the robustness is the main concern as it has superior performance
with the use of the reference watermark. The autocorrelation method has the highest
capacity and is semi-blind. Therefore, it should be used when the data to be hidden

is large. These variations make the proposed methods applicable to a wide range of

watermarking applications.

7 .2 Future Work

The proposed Wigner-based methods assume the watermarked distribution to be a
valid Wigner distribution. However, this is not always true and an error is intro-
duced in the inversion process. Therefore, we used the error between the Wigner of
the watermarked pixels and the watermarked distribution as a key and send it as a
side information to the receiver. This error key added robustness to the proposed
algorithms. Watermarking the Wigner distribution in a way that keeps it as a valid
Wigner distribution, would be a possible extension of this work and will save us from
sending the extra error key. Moreover, in the Wigner-based methods, due to the
computational complexity and the difficulty of implementing the Wigner distribution
for the image, which is a two dimensional signal, we randomly choose a subset of
pixels from the image and do the watermarking on the Wigner distribution of this
subset, which is a one dimensional vector. However, finding the Wigner distribution
of the whole image or some blocks from the image, may reveal new characteristics and
information about the image which can improve the watermarking in this domain.
The proposed watermarking methods have been applied to gray-scale images.

Future research may modify the methods to make them suitable for other types of

122

 

media, i.e. video and audio. For example, the fact that a video is a sequence of images,
suggests that the algorithms should be applicable for this media type. However, in
audio signals, where there are some negative and positive values, the implementation
is not that trivial. The proposed algorithms use the fact that positive real-valued
signals can be synthesized from their Wigner distributions without any error. This
fact does not apply in the audio case and other methods for finding the inverse of
the Wigner distribution for signals which are not necessarily positive or real-valued,
should be used. In [84], the authors established an algorithm for synthesizing the
signal from its Wigner distribution by finding the discrete-time signal whose Wigner
distribution best matches a specified time-frequency distribution in the sense of the
least mean squared error. One may apply the proposed Wigner-based methods on
the audio signals and use the algorithm developed in [84] to find the inverse of the

watermarked distribution.

123

APPENDICES

124

In this appendix, we give the derivation for the detection statistics for the two
algorithms, i.e. 21 and 22 in (3.14) and (4.11) for the Time-Wigner method, and
in (3.17) and (4.14) for the Wigner-Wigner method. We assume that w and 1f) are

independent Gaussian random variables with zero means and variances of a? and 03,

respectively.

A.2 Detector derivation for the Time-Wigner method

 

Let,
z1= ZApty)w2(y) (AI)
.9
The mean of 21 is,
42, = 42 24144). (A2)
9
The variance of 21 is,
03, = E [22] — 4.2., (A 3)
where,
=14 “24.014412102421442 <4 )
y 1
:13 241201444 +E Z)Ap(4 Apr4)w 2(4)w2 (4)
9 gm
=30 4: AP(y)+a4 224,44) ()(44P) (.44)
y #9

where we have used the fact that E [w4(y)] = Bai4 for a normal random variable with

125

 

zero mean [98]. Noting that,

2
1431:0111 (241913))“, ,
=U§ZA2.(4) )+UIZZAP()A ),

y y #9

the variance of 21 is given by,

031— — 2014ZAP(

Similarly for,

24 = Z Ap<4)wr4)414).

5’

It is apparent that 22 has zero mean,
#22 = 07

and the variance of 22 is,

032 — E [23‘] ,
= E Z Z AP(4)44(4414414414414),
y 17
= E 24241442144214)

 

- 0102 22241901)-

(A6)

(A-7)

(4.9)

where the independence of w and 7.0 is used in simplifying the first equality to the

second one.

126

A.3 Detector derivation for the the Wigner-Wigner method

In this method Y1(k), Y2(k) and C(k) are the Fourier transforms of w2(m), 1122(m)

and A p(y) respectively. Therefore,

N-l -27rmk
Y1(k) = Z w2(m)e_J—7V_, (A.10)
m=0
and N 1
_ -27rmk
Y2(k) = Z w2(m)e‘J’N—. (A.11)
m=0

Since w(m) and 10(m) are independent random variables, w2 (m) and 1212(m) are
independent too. Therefore, Y1(k) and Y2(k) are independent. For large N, Y1(k)

and Y2(k) can be assumed to be Gaussians using the central limit theorem. The mean

of Y1(k) is,
N_1 _ ~27rmk
”Y1(k)— E Z w2(m e 3 ,
m=0
N_1 o21rmk
= E [w2(m)] Z e_J N ,
m=0
= Nafauc), (A.12)
N_1 -27rmk
where Z 6.] N =N6(k).
m=0

127

In order to find the variance of Y1(k), we need to find E [Y12(k)],

.27rk(m—Th)

E [Y12(k)] = E [22w2(m>w2<m>e‘J—N— ,

 

_ .27rk(m—7”n
= E [Zw4(m)+z Z w2(m)zfj2(7h)e 3‘77 ,
k

m filaém _

.27m m—r‘n}
= 3011N +011 [2 Z e—J ( ] , (A.13)

m rhaém

where

Z Z e_j27rklm—rhl = 2:X:e_j27rk§m—fn) — N,
7%

(JV—1) -27rkl
= Z (N — |l|)e—’T — N,
—(N-1)
(JV—1) -27rkl
= —2N + 2N26(k) — Z NIB—3T,
-(N—1)
(N’l) 2m

 

=—2N 2N26k —2
+ () 20: lcos( N )

_ 2
= —2N + 2N26(k) — 2 [35V— + 556(k)] ,

= —N + N26(k).

wherel=m—fiz

Therefore,

E [Y12(k)] = [2N + N26(k:)] 0‘11,

128

(A.14)

(A.15)

and the variance of Y1(k) is given by,
2 _ 4

Following the same procedure the mean and the variance for Y2(k) are given by,

“Y2(k) = N036“), (A.17)
0%,200 = 2N03. (A.18)
For,
21 = Z agar/1209) (A.19)
k

The mean is,

#2, = E [Z moi/12m] ,
k
= 2 COM [143(k)],
k

= Z C(k) [2N + N26(k)] 0‘11 = 2N0;1 2 00¢) + Nzofcm), (A20)
k k

129

and the variance can be obtained by computing E [2%] as follows,

E[22]=E 220000 (151/2)1(k) ,

=EZC2 (k)(k)C+ZZC (le) Y2(1}),

’6 k fcaék .

 

= :02 (k) [12N2+ +(12N3 + 11(4))5(1:)]851 + E W:[Z) 2( CU»: C(k)Y12( (kY) Y2(k) ,

k 12¢k j

:02: ([)12N2 + (12N3 + N4)5(k)] 5213+
k
C(k

C(()2N + 512505)) (2N + N25(ic)()4.21)

0332

k £79k
where we have used the fact that E [Y14(k)] = [12N2 + (12N3 + N4)6(k)] a? for a
gaussian random variable with non-zero mean [98].
By noting that,
1121:: 02(k)k+)[41v2(+(4N3 + N4)6(k)]8 01 +

08: Z C(k)C (k)(2N + N25(k)) (2N + N25(ic)), (A22)
k kyék

the variance of 21 is given by,

031 = E [zfl — 1131 = 8N20§ [; C2(n) + NCz(0)] . (A23)
Similarly for,
22 = Z C(k)Y1(k)Y2(k). (A24)

k

130

The mean is,

44.22 = E [Z C(kwmkwmj ,
k

= 1x12525312 [Z C(k)6(k) ,
k

 

 

l
= N20%0’%C(0). (A25)
and,

E[z 2:] [2:0 (k)Y1(k)Y2(k)Y2(k ) ,
= E 202(k)Y12(k) )+ Z Z C(k1fi(/3)Y2(k)Y2(l§) ,

k k kaék _
= E WE?) 02(k)Y12(k)Y22(k) ,

k l

= Z 02(k) (2N + N26(k))2 5152. (A 26)
k

where the independency of Y1(k) and Y2(k) is used to simplify the second equality.

The variance of 22 is given by,

532 = 411(2an3 [E]; C2(n) + NC2(0)] . (A27)

131

BIBLIOGRAPHY

[1] I. J. Cox, M. L. Miller, and J. A. Bloom, Digital Watermarking, Academic Press,
2002.

[2] N. F. Johnson, Z. Duric, and S. Jajodia, Information Hiding: Steganography
and Watermarking- Attacks and Countermeasures, Kluwer Academic Publishers,

2000.

[3] G. C. Langelaar, I. Setyawan, and R. L. Lagendijk, “Watermarking Digital Im-
age and Video Data: A State of-the-art Overview,” IEEE Signal Processing
Magazine, vol. 36, no. 9, pp. 20-46, Sep. 2000.

[4] F.A.P. Petitcolas, R.J. Anderson, M.G. Kuhn, “Information Hiding-A Survey,”
Proceedings of IEEE special issue on Protection of Multimedia Content, vol. 87,

pp. 1062-1078, July. 1999.

[5] F. Hartung, M. Kutter, “Multimedia Watermarking Techniques,” Proceedings of
IEEE special issue on Protection of Multimedia Content, vol. 87, pp. 1079-1107,
July. 1999.

[6] A. Gurijala, and J. R. Deller, “Detector Design for Parametric Speech Water—
marking,” IEEE International Conference on Multimedia and Expo, vol. 1, pp.
251-255, July 2005.

[7] L. Wen-Nung, and C. Li—Chun, “Robust and High-quality Time-domain Audio
Watermarking Based on Low-frequency Amplitude Modification,” IEEE Trans-
actions on Multimedia, vol. 8, pp. 46- 59, Feb. 2006.

[8] L. Wei, X. Xiangyang, and L. Peizhong, “Localized Audio Watermarking Tech—
nique Robust Against Time-scale Modification,” IEEE Transactions on Multi-
media, vol. 8, pp. 60- 69, Feb. 2006.

[9] S. Jiande, and L. Ju, “A Temporal Desynchronization Resilient Video Water-
marking Scheme Based on Independent Component Analysis,” IEEE Interna-
tional Conference on Image Processing, vol. 1, pp. 265-268, Sep. 2005.

[10] K. Su, D. Kundur, and D. Hatzinakos, “Statistical Invisibility for Collusion-
resistant Digital Video Watermarking,” IEEE Transactions on Multimedia, vol.
1, pp. 43—51, Feb. 2005.

132

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

G. Doerr, and J. Dugelay, “Security Pitfalls of Frame-by-frame Approaches to
Video Watermarking,” IEEE Transactions on Signal Processing, vol. 52, pp.
2955-2964, Oct. 2004.

E. Praun, H. Hoppe, A. Finkelstein, “Robust Mesh Watermarking,” Proceedings
of Computer Graphic, vol. 1, pp. 49-56, Aug. 1999.

J. Cox, M. L. Miller, and J. A. Bloom, “Watermarking Applications and their
Properties,” Proceedings of International Conference on Information Technology:
Coding and Computing 2000, vol. 2729, pp. 6—10, March. 2000.

S. Craver, M. Wu, and B. Liu, “What can we Reasonably Expect from Water-
mark?,” Proceedings of IEEE Workshop on Applications of Signal Processing to
Audio and Acoustics, vol. 1, pp. 223—226, Oct. 2001.

F. Huang, Habib M. Hosseini, H. C. Chua, and Y.L. Guan, “Watermarking
of Streaming Video for Finger-Printing Applications,” Proceedings of the IEEE
International Symposium on Circuits and Systems, vol. 2, pp. 452-455, May 2002.

L. D. Strycker, P. Termont, J. Vandewege, J. Haitsma, A. A. C. M. Kalker,
M. Maes, and G. Depovere, “Implementation of a Real-Time Digital Watermark-
ing Process for Broadcast Monitoring on a 'Drimedia Processor,” IEEE Proceed-
ings of Vision, Image and Signal Processing, vol. 147, pp. 371-376, 2000.

G.W. Braudaway, K.A. Magerlein, F. Mintzer: “Protecting Publicly-Available
Images With A Visible Image Watermark,” SPIE Conference on Optical Security
and Counterfeit Deterrence Techniques, vol. 2659, pp. 126-133, Feb. 1996.

J. Meng, S-F. Chang, “Embedding Visible Video Watermarks in the Compressed
Domain,” IEEE International Conference on Image Processing, vol. 1, pp. 474 -
477, Oct. 1998

A.K. Jain, Fundamentals of Digital Image Processing, Prentice Hall, 1989.

G. W. Braudaway, K. A. Magerlein, and F. Mintzer, “Protecting Publically
Available Images with aVisible Image Watermark,” Proceedings of SPIE, Optical
Security and Counterfeit Deterrence Techniques, vol. 2659, pp. 126-133, July
1996.

W. W. Ping, and N. Memon, “Secret and Public Key Image Watermarking
Schemes for Iimage Authentication and Ownership Verification,” IEEE Trans-
actions on Image Processing, vol. 10, pp. 1593-1601, Oct. 2001.

133

 

 

 

[22] K. Gopalakrishnan, N. Memon, and P. L. Vora, “Protocols for Watermark Veri-
fication,” IEEE Transactions on Multimedia, vol. 8, pp. 66-70, Oct. 2001.

[23] C. Chin-Chen, and C. Chi-Yien, “An Enhanced Buyer Seller Watermarking Pro-
tocol,” International Conference on Communication Technology Proceedings, vol.

2, pp. 1779- 1783, April 2003.

[24] Y. Lim, C. Xu, and D. D. Feng, “Web Based Image Authentication using Invisible
Fragile Watermark,” Proceedings of the Pan-Sydney Area Workshop on Visual
information Processing, vol. 11, pp. 31-34, 2001.

[25] S. Katzenbeisser, and F. A. Petitcolas, Information Hiding Techniques for
Steganography and Digital Watermarking, Artech House, Inc, 2000.

[26] J. M. Acken, “How Watermarking adds Value to Digital Contents,” Communi-
cations of the ACM, vol. 41, pp. 75-77, July 1998.

[27] J. Zhao, E. Koch, and C. Luo, “In Bussniess Today and Tomorrow,” Communi-
cations of the ACM, vol. 41, pp. 67-72, July 1998.

[28] S. Wang, and Y. Lin, “Wavelet Tree Quantization for Copyright Protection Wa-
termarking,” IEEE Transactions on Image Processing, vol. 13, pp. 154 - 165, Feb

2004.

[29] A. Jain, and L. Hong, and R. Bolle, “On-Line Fingerprint Verification,” IEEE
Transactions on Pattern Analysis and Machine Intelligence, vol. 19, pp. 302-314,
April 1997.

[30] C. Fei, D. Kundur, and R. Kwong, “Analysis and Design of Secure Watermark-
based Authentication Systems,” IEEE Transactions on Information Forensics
and Security, vol. 1, pp. 43-55, March 2006.

[31] S. Ravi, A. Agarwal, and S. Ganesan, “Frequency Domain Real Time Digital
Image Watermarking,” IEEE International Conference on Electro Information
Technology, vol. 1, pp. 1-6, May 2005.

[32] I.J. Cox, M.L. Miller, J.M.G. Linnartz, T. Kalker, “A Review of Watermark-
ing Principles and Practices,” IEEE Digital Signal Processing for Multimedia
Systems, vol. 1, pp. 461-482, 1999.

[33] M. Kutter, F. Hartung, “Introduction to Watermarking Techniques,” Informa-
tion Techniques for Steganography and Digital Watermarking, vol. 1, pp. 97-119,
Dec. 1999.

134

[34] P. Meerwald, A. Uhl, “Watermark Security via Wavelet Filter Parameterization,”
International Conference on Image Processing, vol. 3, pp. 1027-1030, 2001.

[35] S. Voloshynovskiy, O. Koval, M. Kivanc Mihcak and T. Pun, “The Edge Process
Model and Its Application to Information Hiding Capacity Analysis”, IEEE
Transactions on Signal Processing, vol. 54, pp. 1813-1825, May 2006.

[36] H. S. Bassali, J. Chhugani, S. Agarwal, A. Aggarwal, and P. Dubey, “Compres-
sion Tolerant Watermarking for Image Verification,” IEEE International Con-

ference on Image Processing, vol. 1, pp. 430-433, Sep. 2000.

[37] P. Meerwald, A. Uhl, “A Survey of Wavelet-Domain Watermarking Algorithms,”
Proceedings of SPIE, Electronic Imaging, Security and Watermarking of Multi-
media Contents, vol. 4314, pp. 505-516, Jan. 2001

[38] AH. Tewfik, “Digital Watermarking,” IEEE Signal Processing Magazine, vol.
17, pp 17-88, Sep. 2000.

[39] J. Dugelay, S. Roche, “A Survey of Current Watermarking Techniques,” In-
formation Techniques for Steganography and Digital Watermarking, vol. 1, pp.
121-145, Dec. 1999.

[40] O. Bruyndonckx, J. J. Quisquater, and B. Macq, “Spatial Method for Copyright
Labeling of Digital Images,” Proceedings of IEEE Workshop on Nonlinear Signal
and Image Processing, vol. 1, pp. 456—459, June 1995.

[41] J. R. Hernandez, M. Amado, and F. P rez Gonzalez, “DCT-Domain Water-
marking Techniques For Still Images: Detector Performance Analysis and a New
Structure,” IEEE Transactions on Image Processing, vol. 9, pp. 55-68, Jan. 2000.

[42] T. Holotyak, J. Fridrich and S. Voloshynovskiy, “Blind Statistical Steganalysis
of Additive Steganography Using Wavelet Higher Order Statistics,” Conference
on Communications and Multimedia Security, vol. 2578, pp. 273-274, Sep. 2005.

[43] A. Nikolaidis, and I. Pitas, “Asymptotically Optimal Detection for Additive
Watermarking in the DCT and DWT Domains,” IEEE Transactions on Image
Processing, vol. 12, pp. 563-571, May 2003.

[44] F. Y. Shih, and S. Y. T. Wu, “ Combinational Image Watermarking in the Spatial
and Hequency Domains,” Pattern Recognition, vol. 36, pp.969-975, April 2003.

135

 

 

 

[45]

[46]

[47}

[48]

[49]

[50]

[51]

[52]

[53]

[54]

P. Yang Zhao Campisi, and D. Kundur, “Dual Domain Watermarking for Au-
thentication and Compression of Cultural Heritage Images,” IEEE Transactions
on Image Processing, vol. 13, pp. 430-448, March 2004.

W. Dietl, P. Meerwald, and A. Uhl, “Protection of Wavelet-based Watermarking
Systems using Filter Parametrization,” ACM Signal Processing, vol. 83, pp. 2095-
2116, Oct. 2003.

R. Bangaleea and H. C. S Rughooputh, “Performance Improvement of Spread
Spectrum Spatial-Domain Watermarking Scheme through Diversity and Attack
Characterisation,” IEEE AFRICON, Africon Conference in Africa, vol. 1, pp.
293—298, Oct. 2002.

D. P. Mukherjee, S. Maitra, and S. T. Acton, “Spatial Domain Digital Water-
marking of Multimedia Objects for Buyer Authentication,” IEEE Transactions
on Multimedia, vol. 6, pp. 1-15, Feb. 2004.

N .F. Johnson, S.C. Katezenbeisser, “A Survey of Steganographic Techniques,”
Information Techniques for Steganography and Digital Watermarking, pp. 43-75,
Dec. 1999.

M. Barni, F. Bartolini, A. De Rosa, and A. Piva, “Capacity of the Watermark
Channel: How Many Bits can be Hidden within a Digital Image?,” Proceedings
of SPIE, vol. 3657, pp. 437-448, Jan. 1999.

M. Barni, F. Bartolini, A. De Rosa, and A. Piva, “A DWT-based Technique for
Spatio—frequency Masking of Digital Signatures,” Proceedings of International
Conference on Security and Watermarking of Multimedia Contents, vol. 3657,
pp. 31-39, Jan. 1999.

M. Barni, F. Bartolini, and A. Piva, “ Improved Wavelet-based Watermarking
through Pixel-wise Masking,” IEEE Transactions on Image Processing, vol. 10,
pp. 783H791, May. 2001.

J. J. K. O’Ruanaidh and T. Pun, “Rotation, Scale and Translation Invariant Dig-
ital Image Watermarking,” IEEE Signal Processing: Special Issue on Copyright
Protection and Control, vol. 66, pp. 303—317, May 1998.

S. Pereira, S. Voloshynoskiy, and T. Pun, “Optimal Transform Domain Wa-
termark Embedding via Linear Programming,” IEEE Transactions on Signal
Processing, vol. 81, no. 6, pp. 1251-1260, June 2001.

136

[55]

[56]

[57]

[58}

[59]

[60]

[61]

[62]

[63]

[64]

[65]

I. J. Cox, J. Kilian, T. Leighton, and T. Shamoon, “Secure Spread Spectrum
Watermarking for Images, Audio and Video,” Proceedings of International Con-
ference on Image Processing, vol. 3, pp. 243~246, Sep. 1996.

Ching-Yung Lin, Min Wu, Jeffrey A. Bloom, Ingemar J. Cox, Matt L. Miller,
and Yui Man Lui, “Rotation, Scale, and Translation Resilient Watermarking for
Images,” IEEE Transactions on Image Processing, vol. 10, pp. 767—782, May

2001.

S. Pereira and T. Pun, “Fast Robust Template Matching for Affine Resistant Wa-
termarks,” Lecture Notes in Computer Science: Third International Workshop
on Information Hiding, vol. 1768, pp. 199-210, 1999.

H. S. Malvar, and D. A. F. Florencio, “Improved Spread Spectrum: A New Mod-
ulation technique for Robust Watermarking,” IEEE Transactions Signal Process-
ing, vol. 51, pp. 898-905, April 2003.

A. Briassouli, and P. Moulin, “Detection-theoretic Analysis of Warping Attacks
in Spread-spectrum Watermarking,” Proceedings of Acoustics, Speech, and Signal
Processing, vol. 3, pp. 53-6, April 2003.

L. Hua, and J. E. Fowler, “A Performance Analysis of Spread-spectrum Water-
marking Based on Redundant Transforms,” IEEE International Conference on
Multimedia and Expo, vol. 2, pp. 553-556, 2002.

W. C. Chu, “DCT-based Image Watermarking using Subsampling,” IEEE Trans-
actions on Multimedia, vol. 5, pp. 34- 38, March 2003.

M. A. Suhail, and M. S. Obaidat, “Digital Watermarking-based DCT and JPEG
Model,” IEEE Transactions on Instrumentation and Measurement, vol. 52, pp.
1640-1647, Oct. 2003.

I. J. Cox, J. Killian, T. Leighton, and T. Shamoon, “Secure Spread Spectrum
Watermarking for Multimedia,” IEEE Transactions on Image Processing, vol. 6,
pp. 1673-1687, 1997.

J. Cox, M. L. Miller, and A. L. Mckellips, “Informed Embedding: Exploiting Im-
age and Detector Information During Watermark Insertion,” IEEE International

Conference on Image Processing, vol. 3, pp. 1-4, 2000.

J. Mayer and R. A. Silva, “Efficient Informed Embedding of Multi-bit Water-
mark,” International Conference on Acoustic, Speech and Signal Processing, vol.
3, pp. 389-392, 2004.

137

[66] J. Mayer, A. V. Silverio, and J. C. M. Bermudez, “On the Design of Pattern
Sequences for Spread Spectrum Image Watermarking,” Telecommunication Sym-

posium, 2002.

[67] D. Kundur, Multiresolution Digital Watermarking: Algorithms and Implications
for Multimedia Signals, PhD dissertation, 1999.

[68] D. Kundur and D. Hatzinakos, “Digital Watermarking using Multiresolution
Wavelet Decomposition,” in Proceedings of IEEE International Conference on
Acoustic, Speech and Signal Processing, vol. 5, pp. 2969—2972, 1998.

[69] P. G. F likkema, “Spread-Spectrum Techniques for Wireless Communication,”
IEEE Signal Processing Magazine, vol. 14, pp. 26-36, May 1997.

[70] S. Stankovic, I. Djurovic, and I. Pitas, “Watermarking in the Space/Spatial-
frequency Domain using Two-dimensional Radon-Wigner Distribution,” IEEE
Transactions on Image Processing, vol. 10, pp. 650-658, Apr. 2001.

[71] B. G. Mobasseri, “Digital Watermarking in the Joint Time-frequency Domain,”
in IEEE International Conference on Image Processing, vol. 3, pp. 481—484, 2002.

[72] S. Erkucuk, S. Krishnan, and M. Zeytinoglu, “Robust Audio Watermarking using
a Chirp Based Technique,” in IEEE International Conference on Multimedia and

Expo, vol. 2, pp. 513—516, July 2003.

[73] B. Barkat and F. Sattar, “A New Time-frequency Based Private Fragile Water-
marking Scheme for Image Authentication,” in IEEE International Symposium

on Signal Processing and Applications, vol. 2, pp. 363—366, 2003.

[74] H. zer, B. Sankur, and N. Memon, “An SVD-based Audio Watermarking Tech-
nique”, International Multimedia Conference, Proceedings of the 7th workshop

on Multimedia and security, vol. 1, pp. 51—56, 2005.

[75] Y. Steinberg and N. Merhav, “Identification in the Presence of Side Information
with Application to Watermarking,” IEEE Transactions on Information Theory,
vol. 47, pp. 1410—1422, May 2001.

[76] L. Cohen, T ime-Frequency Analysis, Prentice Hall, New Jersey, 1995.
[77] http: / / www.wavelet.org/ tutorial / tf.htm.

[78] http:/ / www.cbi.dongnocchi . it / glossary / TimeFrequency. html.

138

[79] G. F. Boudreaux-Bartels and T. W. Parks, “Signal Estimation using Modi-
fied Wigner Distribuiton,” Proceedings of International Conference on Acoustics,
Speech, and Signal Processing, vol. 22, pp. 3.1-3.4, March 1984.

[80] G. F. Boudreaux-Bartels and T. W. Parks, “Time-varying Filtering and Signal
Estimation using Wigner Distribution Synthesis Techniques,” IEEE Transac-
tions on Acoustics, Speech, and Signal Processing , vol. 34, pp. 442-451, June

1986.
[81] K. B. Yu and S. Cheng, “Signal Synthesis from Wigner Distribution,” Proceedings

of International Conference on Acoustics, Speech, and Signal Processing, vol. 1,
pp. 1037-1040, March 1985.

[82] B. V. K. Kumar, C. P. Neuman, and K. J. Devos, “Discrete Wigner Synthesis,”
IEEE Transactions on Signal Processing, vol. 11, pp. 277-304, 1986.

[83] T. J. McHale and G. F. Boudreaux-Bartels, “An Algorithm for Synthesizing Sig-
nals from Partial Time-frequency Models using the Cross Wigner Distribution,”
IEEE Transactions on Signal Processing, vol. 41, pp. 1986—1990, May 1993.

[84] S. Rao Nelatury, B. G. Mobasseri, “Synthesis of Discrete-Time Discrete—
Frequency Wigner Distribution”, IEEE Signal Processing Letters, vol. 10, pp.

221-224, 2003.

[85] G. Cristobal, C. Gonzalo, and J. Bescos, “Image Filtering and Analysis Through
the Wigner Distribution function,” in Advances in Electronics and Electron
physics, W. Hawkes, Ed., pp. 309—397. Academic Press, 1991.

[86] M. Al—khassaweneh and S. Aviyente, “Robust Watermarking on the Joint
Spatial-spectral Domain,” Proceedings of IEEE Digital Signal Processing Work-
shop, vol. 1, pp. 297—301, 2004.

[87] M. Al-khassaweneh and S. Aviyente, “A time-frequency Inspired Robust Im-
age Watermarking,” IEEE Conference Record of the Thirty-Eighth Asilomar
Conference on Signals, Systems and Computers, vol. 1, pp. 392—396, 2004.

[88] M. Al—khassaweneh and S. Aviyente, “Image Watermarking in the Autocorrela-
tion Domain,” Proceedings of the 4th ACM international workshop on Contents

protection and security, vol. 1, pp. 53—58, Oct. 2006.

[89] M. Zeng and B. Liu, “A Statistical Watermark Detection Technique without
using Original Images for Resolving Rightful Ownerships of Digital Images,”
IEEE Transcations on Image Processing, vol. 6, pp. 1534—1548, Nov. 1999.

139

[90] A. Papoulis, Probability, Random Variables, and Stochastic Processes, McGraw-
Hill, New York, 1991.

[91] “http://hlab.phys.rug.nl/imlib/index.html,” .

[92] C. H. Lee and H. K. Lee, “Improved Autocorrelation Function Based Water-
marking with Side lnformation,” Journal of Electronic Imaging, vol. 14, pp.
0130121—01301213, Mar. 2005.

[93] P. Dong and N .P. Galatsanos, “Geometric Robust Watermarking through Wa-
termark Pattern Shaping,” in Proceedings of International Conference on Image

processing, vol. 1, pp. 493—496, Sep. 2003.

[94] C. K. Chui, Wavelets: A Tutorial in Theory and Applications, Academic Press,
California, 1992.

[95] D. Kundur and D. Hatzinakos, “Toward Robust Logo Watermarking using Mul-
tiresolution Image Fusion Principles,” IEEE Transactions on Multimedia, vol. 6,

pp.185—198,2004.

[96] G. Chang, B. Yu, and M. Vetterli, “Adaptive Wavelet Thresholding for Image
Denoising and Compression,” IEEE Transactions on Image Processing, vol. 9,
pp. 1532—1546, Sept. 2000.

[97] J. Mayer and R. A. Silva, “Efficient Informed Embedding of Multi-bit Water-
mark,” in Proceedings of IEEE International Conference on Acoustics,Speech
and Signal Processing, vol. 3, pp. 389—392, 2004.

[98] M. Evans, N. Hastings, and B. Peacock, Statistical Distributions, Wiley, New
York, 2000.

140

   

1“1111111111111[1],]I