# Reversible Watermarking Techniques An Overview and a Classification.pdf

##
Reversible Watermarking Techniq…

上传者：
hiyyt
2011-12-26
评分*1*
评论*0*
下载*29*次
收藏*10*人
阅读量*706*
暂无简介
简介
举报
**简介：**本文档为《Reversible Watermarking Techniques An Overview and a Classificationpdf》，可适用于专题技术领域，主题内容包含HindawiPublishingCorporationEURASIPJournalonInformationSecurityVolume,Arti符等。

Hindawi Publishing Corporation
EURASIP Journal on Information Security
Volume 2010, Article ID 134546, 19 pages
doi:10.1155/2010/134546
Review Article
Reversible Watermarking Techniques:
An Overview and a Classification
Roberto Caldelli, Francesco Filippini, and Rudy Becarelli
MICC, University of Florence, Viale Morgagni 65, 50134 Florence, Italy
Correspondence should be addressed to Roberto Caldelli, roberto.caldelli@unifi.it
Received 23 December 2009; Accepted 17 May 2010
Academic Editor: Jiwu W. Huang
Copyright 2010 Roberto Caldelli et al. This is an open access article distributed under the Creative Commons Attribution
License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly
cited.
An overview of reversible watermarking techniques appeared in literature during the last five years approximately is presented
in this paper. In addition to this a general classification of algorithms on the basis of their characteristics and of the embedding
domain is given in order to provide a structured presentation simply accessible for an interested reader. Algorithms are set in a
category and discussed trying to supply themain information regarding embedding and decoding procedures. Basic considerations
on achieved results are made as well.
1. Introduction
Digital watermarking techniques have been indicated so far
as a possible solution when, in a specific application scenario
(authentication, copyright protection, fingerprinting, etc.),
there is the need to embed an informative message in a
digital document in an imperceptible way. Such a goal
is basically achieved by performing a slight modification
to the original data trying to, at the same time, satisfy
other bindings such as capacity and robustness. What is
important to highlight, beyond the way all these issues are
achieved, it is that this “slight modification” is irreversible:
the watermarked content is diﬀerent from the original
one. This means that any successive assertion, usage, and
evaluation must happen on a, though weakly, corrupted
version, if original data have not been stored and are not
readily available. It is now clear that in dependence of
the application scenario, this cannot always be acceptable.
Usually when dealing with sensitive imagery such as deep
space exploration, military investigation, and recognition,
and medical diagnosis, the end-user cannot tolerate to risk
to get a distorted information from what he is watching
at. One example above all: a radiologist who is checking
a radiographic image to establish if a certain pathology is
present or not. It cannot be accepted that his diagnosis is
wrong both, firstly, to safeguard the patient’s health and,
secondly, to protect the work of the radiologist himself.
In such cases, irreversible watermarking algorithms clearly
appear not to be feasible; due to this strict requirement,
another category of watermarking techniques have been
introduced in literature which are catalogued as reversible,
where, with this term, it is to be intended that the original
content, other than the watermark signal, is recovered from
the watermarked document such that any evaluation can
be performed on the unmodified data. Thus doing, the
watermarking process is zero-impact but allows, at the same
time, to convey an informative message.
Reversible watermarking techniques are also named as
invertible or lossless and were born to be applied mainly in
scenarios where the authenticity of a digital image has to
be granted and the original content is peremptorily needed
at the decoding side. It is important to point out that,
initially, a high perceptual quality of the watermarked image
was not a requirement due to the fact that the original
one was recoverable and simple problems of overflow and
underflow caused by the watermarking process were not
taken into account too. Successively also, this aspect has been
considered as basic to permit to the end user to operate on
the watermarked image and to possibly decide to resort to
the uncorrupted version in a second time if needed.
2 EURASIP Journal on Information Security
Semi-fragile
Robust
Fragile
Reversible
Figure 1: Categorization of reversible watermarking techniques.
Reversible algorithms can be subdivided into two main
categories, as evidenced in Figure 1: fragile and semifragile.
Most of the developed techniques belong to the family of
fragile that means that the inserted watermark disappears
when amodification has occurred to the watermarked image,
thus revealing that data integrity has been compromised.
An inferior number, in percentage, are grouped in the
second category of semi-fragile where with this term it is
intended that the watermark is able to survive to a possible
unintentional process the image may undergo, for instance,
a slight JPEG compression.
Such feature could be interesting in applications where
a certain degree of lossy compression has to be tolerated;
that is, the image has to be declared as authentic even if
slightly compressed. Within this last category can also be
included a restricted set of techniques that can be defined as
robust which are able to cope with intentional attacks such as
filtering, partial cropping, JPEG compression with relatively
low quality factors, and so on.
The rationale behind this paper is to provide an overview,
as complete as possible, and a classification of reversible
watermarking techniques, while trying to focus on their
main features in a manner to provide to the readers basic
information to understand if a certain algorithm matches
with what they were looking for. In particular, our attention
has been dedicated to papers appeared approximately from
years 2004-2005 till 2008-2009; in fact, due to the huge
amount of works in this field, we have decided to restrict
our watch to the last important techniques. Anyway we
could not forget some “old” techniques that are consid-
ered as reference throughout the paper, such as [1–3],
though they are not discussed in detail. The paper tries
to categorize these techniques according to the classifi-
cation pictured in Figure 1 and by adding an interesting
distinction regarding the embedding domain they work on:
spatial domain (pixel) or transformed domain (DFT, DWT,
etc.).
The paper is structured as follows: in Section 2, fragile
algorithms are introduced and subdivided into two sub-
classes on the basis of the adopted domain; in Section 3,
techniques which provide features of semi-fragileness and/or
robustness are presented and classified again according to the
watermarking domain. Section 4 concludes the paper.
2. Fragile Algorithms
Fragile algorithms cover the majority of the published
works in the field of reversible. With the term fragile a
watermarking technique which embeds a code in an image
that is not readable anymore if the content is altered.
Consequently the original data are not recoverable too.
2.1. Spatial Domain. This subsection is dedicated to present
some of the main works implementing fragile reversible
watermarking by operating in the spatial domain.
One of the most important works in such a field has
been presented by Tian [4, 5]. It presents a high-capacity,
high visual quality, and reversible data embedding method
for grayscale digital images. This method calculates the
diﬀerence of neighboring pixel values and then selects some
of such diﬀerences to perform a diﬀerence expansion (DE).
In such diﬀerent values, a payload B made by the following
parts will be embedded:
(i) a JBIG compressed location map,
(ii) the original LSB values, and
(iii) the net authentication payload which contains an
image hash.
To embed the payload, the procedure starts to define two
amounts, the average l and the diﬀerence h (see (1)).
Given a pair of pixel values (x, y) in a grayscale image,
with x, y Z, 0 x, y 255,
l =
x + y
2
h = x y, (1)
and given l and h, the inverse transform can be respectively
computed according to(2)
x = l +
h + 1
2
; y = l
h
2
. (2)
The method defines diﬀerent kinds of pixel couples
according to the characteristics of the corresponding h
and behaves slightly diﬀerent for each of them during
embedding. Two are the main categories: changeable and
expandable diﬀerences, let us see below for their definitions,
respectively.
Definition 1. For a grayscale-valued pair (x, y) a diﬀerence
number h is changeable if
2
h
2
+ b
min(2(255 l), 2l + 1). (3)
Definition 2. For a grayscale-valued pair (x, y) a diﬀerence
number h is expandable if
|2 h + b| min(2(255 l), 2l + 1). (4)
This is imposed to prevent overflow/underflow problems
for the watermarked pixels (x′, y′).
To embed a bit b = (0, 1) of the payload, it is necessary
to modify the amount h obtaining h′ which is called DE
EURASIP Journal on Information Security 3
Table 1: Payload size versus PSNR of Lena image.
Payload Size (bits) 39566 63676 84066 101089 120619 141493 175984 222042 260018 377869 516794
Bit Rate (bpp) 0.1509 0.2429 0.3207 0.3856 0.4601 0.5398 0.6713 0.8470 0.9919 1.4415 1.9714
PSNR (dB) 44.20 42.86 41.55 40.06 37.66 36.15 34.80 32.54 29.43 23.99 16.47
(Diﬀerence Expansion) according to (5) for expandable
diﬀerences
h′ = 2 h + b, b = LSB(h′), (5)
and (6) for changeable ones
h′ = 2
h
2
+ b, b = LSB(h′), (6)
by replacing h with h′ within (2), the watermarked pixel
values x′ and y′ are got. The basic feature which distinguishes
expandable diﬀerences from changeable ones is that the first
ones can carry a bit without asking for saving the original
LSB. That yields to a reduced total payload B. A location
map takes into account of the diverse disjoint categories of
diﬀerences.
To extract the embedded data and recover the original
values, the decoder uses the same pattern adopted during
embedding and applies (1) to each pair. Then two sets of
diﬀerences are created: C for changeable h and NC for not
changeable h. By taking all LSBs of diﬀerences belonging to
C set, a bit stream B is created. Firstly, the location map is
recovered and used together with B to restore the original h
values; secondly, by using (2) the original image is obtained,
lastly, the embedded payload (the remaining part of B) is
used for authentication check by resorting to the embedded
hash.
Tian applies the algorithm to “Lena” (512 512), 8 bpp
grayscale image. The experimental results are shown in
Table 1, where the embedded payload size, the corresponding
bitrate, and PSNRs of the watermarked image are listed.
As DE increases, the watermark has the eﬀect similar to
mild sharpening in the mid tone regions. Applying the DE
method on “Lena,” the experimental results show that the
capacity versus distortion is better in comparison with the G-
LSB method proposed in [2], and the RS method proposed
in [1].
The previous method has been taken and extended by
Alattar in [6]. Instead of using diﬀerence expansion applied
to pairs of pixels to embed one bit, in this case diﬀerence
expansion is computed on spatial and cross-spectral triplets
of pixels in order to increase hiding capacity; the algorithm
embeds two bits in each triplet. With the term triplet a
1 3 vector containing the pixel values of a colored image
is intended; in particular, there are two kinds of triplets.
(i) Spatial Triplet: three pixel values of the image chosen
from the same color component within the image
according to a predetermined order.
(ii) Cross-spectral Triplet: three pixel values of the image
chosen from diﬀerent color components (RGB).
The forward transform for the triplet t = (u0,u1,u2) is
defined as
v0 =
u0 +wu1 + u2
N
,
v1 = u2 u1,
v2 = u0 u1,
(7)
where N and w are constant. For spatial triplets, N = 3 and
w = 1, while in cross-spectral triplets, N = 4 and w = 2.
On the other side, the inverse transform, f 1(), for the
transformed triplets t′ = (v0, v1, v2) is defined as
u1 = v0
v1 + v2
N
,
u0 = v2 + u1,
u2 = v1 + u1.
(8)
The value v1 and v2 are considered for watermarking
according to (9)
v′1 = 2 v1 + b1,
v′2 = 2 v2 + b2,
(9)
for all the expandable triplets, where expandable means that
(v′1 + v
′
2) satisfies a limitation similarly to what has been
proposed in the previous paper to avoid overflow/underflow.
In case of only changeable triplets, v′1 = 2 v1/2 + b1 (v′2
changes correspondingly), but the same bound for the sum
of these two amounts has to be verified again.
According to the above definition, the algorithm classifies
the triplets in the following groups.
(1) S1: contains all expandable triplets whose v1 T1 and
v2 T2 (T1, T2 predefined threshold).
(2) S2: contains all changeable triplets that are not in S1.
(3) S3: contains the not changeable triplets.
(4) S4 = S1 S2 contains all changeable triplets
In the embedding process, the triplets are transformed using
(7) and then divided into S1, S2 and S3. S1, and S2 are
transformed in Sw1 and S
w
2 (watermarked) and the pixel
values of the original image I(i, j, k) are replaced with the
corresponding watermarked triplets in Sw1 and S
w
2 to produce
the watermarked image Iw(i, j, and k). The algorithm uses
a binary JBIG compressed location map M, to identify the
location of the triplets in S1, S2, and S3 which becomes part
of the payload together with the LSB of changeable triplets.
In the reading and restoring process, the system simply
follows the inverse steps of the encoding phase. Alattar
4 EURASIP Journal on Information Security
Table 2: Embedded payload size versus PSNR for colored images.
Lena Baboon Fruits
Payload (bits) PSNR (dB) Payload (bits) PSNR (dB) Payload (bits) PSNR (dB)
305,194 35.80 115,050 30.14 299,302 35.36
420,956 34.28 187,248 28.54 497,034 33.00
516,364 33.12 256,334 27.20 582,758 32.45
660,618 31.44 320,070 26.10 737,066 31.14
755,096 30.28 408,840 24.73 824,760 30.06
837,768 29.10 505,150 23.34 853,846 29.49
941,420 27.01 656,456 21.20 888,850 28.52
Table 3: Comparison results between Tian’s and Alattar’s algorithm.
Gray-scale Lena Gray-scale Barbara
Tian’s Alg. Alattar’s Alg. Tian’s Alg. Alattar’s Alg.
PSNR (dB) Payload (bits) Payload (bits) PSNR (dB) Payload (bits) Payload (bits)
29.4 260.018 298.872 23.6 247.629 279.756
32.5 222.042 236.318 31.2 159.000 202.120
34.8 175.984 189.468 32.8 138.621 187.288
36.2 141.493 131.588 34.1 120.997 167.986
37.7 120.619 107.416 37.4 81.219 108.608
40.1 101.089 49.588 40.2 60.577 45.500
41.6 84.066 19.108 42.8 39.941 19.384
w
h
Quad q = (u0,u1,u2,u3)
Figure 2: Quads configuration in an image.
tested the algorithm with three 512 512 RGB images, Lena,
Baboon, and Fruits. The algorithm is applied recursively to
columns and rows of each color component. The watermark
is generated by a random binary sequence and T1 = T2 in all
experiments. In Table 2, PSNRs of the watermarked images
are shown. In general, the quality level is about 27 dB with a
bitrate of 3.5 bits/colored pixel. In Table 3, it is reported also
the performance comparison in terms of capacity between
the Tian’s algorithm and this one, by using grayscale images
Lena and Barbara.
From the results of Table 3, the algorithm proposed
outperforms the Tian’s technique at lower PSNRs. At higher
PSNRs instead, the Tian’smethod outperforms the proposed.
Alattar proposed in [7] an extension of such a technique,
to hide triplets of bits in the diﬀerence expansion of quads of
adjacent pixels. With the term quads a 14 vector containing
the pixel values (2 2 adjacent pixel values) from diﬀerent
locations within the same color component of the image is
intended (see Figure 2).
The diﬀerence expansion transform, f (), for the quad
q = (u0,u1,u2,u3) is defined as in (10)
v0 =
a0u0 + a1u1 + a2u2 + a3u3
a0 + a1 + a2 + a3
,
v1 = u1 u0,
v2 = u2 u1,
v3 = u3 u2.
(10)
The inverse diﬀerence expansion transform, f 1(), for
the transformed quad q′ = (v0, v1, v2, v3) is correspondingly
defined as in (11)
u0 = v0
(a1+a2+a3)v1+(a2+a3)v2+a3v3
a0 + a1 + a2 + a3
,
u1 = v1 + u0,
u2 = v2 + u1,
u3 = v3 + u2.
(11)
Similarly to the approach previously adopted, quads
are categorized in expandable or changeable and diﬀerently
treated during watermarking; then they are grouped as
follows.
(1) S1: contains all expandable quads whose v1 T1,
v2 T2, v3 T3 with v1, v2, v3 transformed values
and T1,T2, and T3 predefined threshold.
(2) S2: contains all changeable quads that are not in S1.
(3) S3: contains the rest of quads (not changeable).
(4) S4: contains all changeable quads (S4 = S1 S2).
EURASIP Journal on Information Security 5
In the embedding process the quads are transformed by using
(10) and then divided into the sets S1, S2, and S3. S1 and S2 are
modified in Sw1 and S
w
2 (the watermarked versions) and the
pixel values of the original image I(i, j, and k) are replaced
with the corresponding watermarked quads in Sw1 and S
w
2
to produce the watermarked image Iw(i, j, k). Watermark
extraction and restoring process proceeds inversely as usual.
In the presented experimental results, the algorithm is
applied to each color component of three 512 512 RGB
images, Baboon, Lena, and Fruits setting T1 = T2 = T3
in all experiments. The embedding capacity depends on the
nature of the image itself. In this case, the images with a
lot of low frequencies contents and high correlation, like
Lena and Fruits, produce more expandable triplets with
lower distortion than high frequency images such as Baboon.
In particular with Fruits, the algorithm is able to embed
867 kbits with a PSNR 33.59 dB, but with only 321 kbits
image quality increases at 43.58 dB. It is interesting to verify
that with Baboon the algorithm is able to embed 802 kbits
or 148 kbits achieving a PSNR of 24.73 dB and of 36.6 dB,
respectively.
The proposed method is compared with Tian’s algo-
rithm, using grayscale images, Lena and Barbara. At PSNR
higher than 35 dB, quad-based technique outperforms Tian,
while at lower PSNR Tian outperforms (marginally) the
proposed techniques. The quad-based algorithm is also com-
pared with [2] method using grayscale images like Lena and
Barbara. Also, in this case the proposed method outperforms
Celik [2] at almost all PSNRs. The proposed algorithm is
also compared with the previous work of Alattar described
in [6]. The results reveal that the achievable payload size for
the quad-based algorithm is about 300,000 bits higher than
for the spatial triplets-based algorithm at the same PSNR;
furthermore, the PSNR is about 5 dB higher for the quad-
based algorithm than for the spatial triplet-based algorithm
at the same payload size.
Finally, in [8], Alattar has proposed a further gener-
alization of his algorithm, by using diﬀerence expansion
of vectors composed by adjacent pixels. This new method
increases the hiding capacity and the computation eﬃciency
and allows to embed into the image several bits, in every
vector, in a single pass. A vector is defined as u =
(u0,u1, . . . ,uN1), where N is the number of pixel values
chosen from N diﬀerent locations within the same color
component, taken, according to a secret key, from a pixel set
of a b size.
In this case, the forward diﬀerence expansion transform,
f (), for the vector u = (u0,u1, . . . ,uN1) is defined as
v0 =
N1
i=0 aiuiN1
i=0 ai
,
v1 = u1 u0,
...
vN1 = uN1 u0,
(12)
where ai is a constant integer, 1 a h, 1 b w and
a + b /= 2, (w and h are the image width and height, resp.)
The inverse diﬀerence expansion transform, f 1(), for
the transformed vector v = (v0, v1, . . . , vN1), is defined as
u0 = v0
N1
i=1 aiviN1
i=0 ai
,
u1 = v1 + u0,
...
uN1 = vN1 + u0.
(13)
Similarly to what was done before, the vector u =
(u0,u1, . . . ,uN1) can be defined expandable if, for all
(b1, b2, . . . , bN1) 0, 1, v = f (u) can be modified to
produce v = (v0, v1, . . . , vN1) without causing overflow and