Watermarking at Point of
Origin
A.Z.Tirkel
Scientific Technology
P.O.Box 3032
Dendy Brighton 3186, Australia
+61-3-95922206
tirkel@c031.aone.net.au
|
T.E.Hall
Department of Mathematics and Statistics
Monash University
P.O.Box 28M Victoria 3800, Australia
+61-3-99054412
tom.hall@sci.monash.edu.au
|
ABSTRACT
We describe a proposed scheme for watermarking images or video at the
camera. This addresses the issue of image security between the point of
origin and the point of distribution. The scheme is expected to find application
in the security industry, where proof of tampering is important and in
commercial photography, where breach of copyright is important.
Keywords
watermark, correlation, array, polynomial.
1. INTRODUCTION
Digital image watermarking is a new technique, whose relative importance
has escalated due to the proliferation of the Internet. Since our group
at Monash introduced the concept of the digital watermark [10] in 1993,
significant improvements in the technology have occurred, as reviewed in
[3], [7].
Almost all these techniques involve the insertion of the watermark into
image data, which is assumed to exist in digital memory. Most of the issues
relating to the watermark robustness and extraction relate to its transmission
from one computer to another. This leaves the image vulnerable between
point of origin and the computer where such a watermark is inserted.
This paper proposes a dedicated spatial pseudonoise watermark to protect
data from digital still and video cameras between the point of origin and
the point of distribution. Watermark recovery is achieved by performing
a correlation of the watermarked image with the watermark template. In
this scheme, there is no original image (unwatermarked) except its estimate
via the process of removing the watermark. This watermark can be compatible
with the acquisition hardware of standard CCD cameras and can be inserted
at the analogue/digital converter stage. Its implementation in an Electrically
Programmable Logic Device (EPLD) is straightforward.
The above watermark can coexist with the standard watermarks used for
protecting images through the communication channel, at the distribution
stage of the process. The latter are usually implemented in a transform
domain and are optimized for robustness against compression and geometrical
distortions: rotation, scale manipulations, cropping, shear etc. Compression
standards are evolving, so that this "distribution" watermark requires
flexibility. It seems impractical to use one watermark to perform these
seemingly incompatible functions. Different compression methods (and consequent
distribution watermarks) also impact on the effectiveness of the watermark
to resolve proof of piracy or proof of tampering issues. For example, fractal
compression is radically different in concept and application to Discrete
Cosine Transform based compression and so are the watermarking schemes
for these two cases. Robustness of one scheme to attacks based on the other
method has yet to be resolved.
In this paper we describe a point of origin watermark scheme. The motive
for this scheme is discussed in Section 2, where its application to commercial
photography and the surveillance industry is described. Section 3 presents
a novel spatial pseudonoise watermark construction method, which is capable
of providing individual watermark patterns for each image. Watermark assignment
is a two-part process. The first part is based on a generic address as
provided by a "smart" card for a photographer, or a video camera serial
number. The second part is an individual sequence number, uniquely identifying
the order of the image in the collection of that photographer or camera.
Section 4 addresses implementation issues, whilst Section 5 describes the
robustness of the scheme against cryptographic attack.
2 WATERMARK AT POINT OF ORIGIN
2.1 Proof of Piracy
In the case of commercial photography, a watermark at the point of origin
can resolve conflicts pertaining to piracy of the image. Consider a situation
where A claims that his/her image IA has been pirated by B on
the basis that B’s image, IB, contains A’s watermark WA
and therefore B’s image is a copy. B may have similar claims based on watermark
WB. Tests involving detection of each watermark, supervised
by an independent authority can be interpreted by consulting a result table,
such as Table 1. Detection of A or B’s watermark in each of the two images
are translated into who is a pirate. An inconclusive test is denoted by
#, whilst ? refers to an inconclusive or tentative result. Note that there
is no recourse to the "original" i.e. unwatermarked image, nor is this
a proof that A or B can rightfully claim that "original".
Table 1. Result table without "original"
Test |
WB IA |
WB IA |
# |
WA IB |
BOTH |
B |
B? |
WA IB |
A |
NEITHER |
? |
# |
A? |
? |
? |
In schemes where an original is required for detection or recovery, the
table becomes complicated, because then there are four objects to be tested
with uncertainties as to which are watermarked. This is in spite of the
fact that each claimant can produce a self-consistent method of extracting
his or her watermark.
Clearly, the former method is more effective. However, successful detection
or recovery of a watermark, without recourse to the "original", places
more restriction on the design of the watermark, especially in terms of
its cross-correlation with the image and with other watermarks. It is desirable
to implement such a scheme by applying the watermark from a SIMM card inserted
into a digital camera, in a similar manner to that in cellular telephones.
Figure 1. Watermark via SIMM card in the camera
2.2 Proof of Tampering
The security industry has recently implemented video surveillance on an
unparalleled scale. Typically, huge numbers of video frames are acquired
by cameras and multiplexed into a common storage data bank. In order to
ensure that such data becomes admissible evidence in a court of law, some
quantitative proof of integrity is required. This involves proof of tampering
with an individual frame, or with the sequencing of frames, or synchronization
with the sound track. Typically, tampering with a frame should be established
on the basis of upper and lower thresholds. A combination of digital signature
(fragile) with a correlative pseudonoise watermark can achieve this objective.
Sequencing and synchronization issues can be addressed if each frame is
assigned a unique watermark, with low cross-correlation with all others.
The scheme presented in this paper provides such a construction.
3. WATERMARK CONSTRUCTION
The original method of spatial watermark construction [10], involved sequences
developed for spread spectrum communications. Since then, it has become
clear that, despite many common features, watermarking requirements are
different, principally because:
(a) Images and video are multidimensional
This results in causal relationships between pixels in more than one
dimension. Multidimensional arrays have been constructed and analyzed [5]
and applied to coded aperture optics and structured light, but there, a
single array is sufficient.
(b) The image data is not embedded on a (sinusoidal) carrier
This makes it difficult to embed watermarks based on roots of unity,
as is done by phase modulation in communications. Our group has recently
been able to demonstrate two schemes that achieve this, for colour and
greyscale images, by constructing angles in abstract spaces [11]. An analysis
of such methods is presented in [9].
(c) The pixels are quantized and image polarity is usually known
Therefore correlation is meaningful for integer pixel offsets only
and coherent statistics are involved. Hence correlation should be considered
as a signed quantity. This contrasts with spread spectrum communications
and results in different criteria for acceptance of arrays suitable for
watermarking. It also has implications when more than one watermark is
involved, with watermarks and correlations adding arithmetically.
3.1 Watermark Properties
For watermarking schemes relying on correlative recovery, the most important
requirement of the watermark is that it should be imperceptible but still
yield an unambiguous autocorrelation peak. Ambiguities can arise due to
cross-correlation with the image, autocorrelation sidelobes and cross-correlation
between different watermarks. The effects of the cross-correlation with
the image can be reduced by non-linear (e.g. median) filtering before correlation
[4], or by Laplace filtering. These techniques rely on the different spatial
structure of the image and a pseudonoise sequence or array. The cross-correlation
between different watermarks can be reduced by orthogonalizing filters
[6]. However, such filters result in a small family of watermarks, whose
autocorrelation peaks are degraded. Cross-correlation with the image affects
filter design and stability. Both techniques are useful adjuncts to good
watermark design. Therefore, the authors have focused on the search for
large families of watermarks with good auto and cross-correlation. An added
benefit of such a design is that multiple watermarks can be embedded in
the same image in order to increase information capacity, enhance robustness,
or decrease visibility in low contrast regions of the image. There are
many other, more flexible requirements of watermarks for video and still
images, such as image size, aspect ratio, robustness against geometrical
distortions, compression and cryptographic attack. These features are reviewed
in [3], [7].
3.2 Array Constructions
The search for arrays with good auto and cross-correlation has been
carried out by computers as an exhaustive search and assisted search by
stimulated annealing [1]. The problem is theoretically difficult and these
methods are haphazard. By contrast, sequences with good correlation properties
have been studied extensively, [2], [8] and have found applications in
radar and spread spectrum communications. We have used these sequences
to generate arrays and volumes. An array is formed from a collection of
various cyclic shifts of a suitable sequence, which form columns (rows)
of the construction. Although it is possible to involve more than one sequence
to form such an array, our constructions are based on one sequence only.
When the sequence length is a prime p and the number of shifts is
also p, several orderly arrangements of column shifts yield arrays
with constrained auto and cross-correlation.
-
Exponential. The shifts are powers of a primitive root of Zp.
This ensures good autocorrelation, but so far the families of such arrays
with good cross-correlation are small.
-
Logarithmic. The shifts are based on the number-theoretic index
function (discrete logarithm) based on a primitive root of Zp.
This is similar to the generalized Legendre sequence defined over roots
of unity, but unlike its sequence counterpart, the family of such arrays
with good cross-correlation is small. The construction is cryptographically
"strong", since the inversion of the discrete logarithm is a "difficult
problem".
-
Polynomial. This construction assigns cyclic shifts based on polynomials
of degree n with coefficients chosen from Zp.
This is similar to the construction of sequences over roots of unity by
primitive or irreducible polynomials. For typical images, p can
be several hundred. The choice of coefficients is a combinatorial exercise.
Such a construction yields huge families of arrays with good auto and cross-correlation.
The authors have therefore investigated p x p arrays formed
by the polynomial shift algorithm.
The constraint of prime length and square aspect are restrictive, so
the search for other arrays is ongoing. Composite lengths are possible
for l=pm-1 where a logarithmic shift assignment (Zech logarithm)
results in arrays with good autocorrelation. The size of the families with
good cross-correlation is unknown, but expected to be small. The square
format can be modified slightly by puncturing or appending columns.
Sequences over prime lengths have been studied and a large number of
them are available. Typically, they are constructed over roots of unity
(special case: binary). We have used maximal length sequences, Legendre
sequences and generalized chirp sequences. Roots of unity can be employed
to construct watermarks for color and greyscale images [9], [11].
3.3 Polynomial Construction Array Properties
Here we present the properties of arrays constructed by using a shift polynomial
of the form:

is the cyclic shift (expressed modulo p) of the column whose index
(label) is x. For illustration purposes, consider p to be
509, compatible with an image of size 512 x 512. Consider n=50.
3.3.1 Autocorrelation
The autocorrelation is the list of dot products of a matrix with its (cyclically)
shifted versions. A vertical shift (in the column direction) of
results in an addition of
to a0.
A horizontal shift by
results in a transformation of x to x+
in the shift equation. The shifted matrix is described by the modified
shift polynomial:

The autocorrelation of the array is determined by the number of matching
columns i.e. the columns with the same shift in identical locations in
the shifted and unshifted matrices. These columns contribute
p to
the correlation, whilst all other columns contribute –1 (for standard
pseudonoise columns). The number of matching columns is determined by the
number of solutions to:

This corresponds to the number of roots of a polynomial of degree at
most n-1 and thus the maximum number of such solutions is n-1,
so that the maximum off-peak autocorrelation is:

Therefore, the maximum off-peak autocorrelation value normalized to
the peak of p2 is (n-2)/p, which is less than
10% for the example chosen. The actual correlation values range from –p
(no matching columns) to the maximum, in increments of p+1, but
the number of occurrences is constrained by the matrix balance (sum of
all entries). The location of each correlation value (function of shift
parameters
and
)
is determined by the shift polynomial.
3.3.2 Cross-correlation
Consider two matrices A and B, which are not shifts of each other, generated
by two different shift polynomials:
and
. As in the argument
of 3.3.1, the number of matching columns is determined by the number
of solutions to:

This corresponds to the number of roots to a polynomial of degree at
most n and thus the maximum number of such solutions is n,
so that the maximum cross-correlation is:

This is also less than 10% of the peak auto-correlation.
3.3.3 Family Size
The number of polynomials of degree n is (p-1)pn.
Each matrix is available in p2 shifts. Hence, the total
number of non-equivalent matrices generated by polynomials of degree n,
is (p-1)pn-2. For the example chosen, this exceeds 4
x 10132 (far in excess of the number of all images
and video likely to be produced).
3.3.4 Information Capacity
Each p x p matrix can be present in
p2
shifts. Therefore, it is possible to store 2log2
(p)
binary bits in such an array. This is almost 18 bits for the example
chosen. Where more information capacity is required, watermarks can be added together and still recovered [12].
This results in a degraded auto and cross-correlation and greater modification to the image.
The statistics
appear to be Gaussian, i.e. watermarks add like noise. For a sum of q
watermarks, the information capacity is multiplied by q, whilst
the standard deviation in the correlations
is multiplied by
.
3.3.5 Balance
The good correlation properties of the arrays depend on the off-peak sequence
correlation being low. Therefore, the seed column must be near balanced
(Legendre, FZC, m-sequence) and so are the arrays. Hence, when used as
a watermark, our arrays have a minimal impact on the image mean.
3.3.6 Robustness against cryptographic attack
The low contrast regions of the image are the most vulnerable to such attack,
since portions of the array may be available to the attacker. For our arrays,
accurate knowledge of the shifts of at least n columns (from a total
of p) columns is required to determine the shift polynomial. Should
this be insufficient protection, addition of several watermarks offers
cryptographic confusion. The use of cryptographically strong columns (such
as GMW sequences) can enhance security in the column direction.
4. IMPLEMENTATION
We envisage the arrays described in section 3 being implemented in hardware
at the Analog/Digital conversion stage of the digital (CCD) still or video
camera.
4.1 Watermark Construction
For still cameras, the array construction could proceed as illustrated
in section 3. Video cameras require 3D arrays, with time (frame index)
forming the third dimension. p x p x p arrays can
be constructed by employing polynomial shifts in the column and frame indices.
This could be achieved by a product of polynomials in the two variables,
a direct extension of the theory outlined in Section 3. Investigation of
shift expressions involving polynomials in multiple variables is ongoing.
The physical construction of the watermark requires computation of the
shift variable
using modulo
p arithmetic and the cyclic rotation of a stored sequence.
Information can be stored in the watermark by using a cyclic 2-dimensional
shift of the array as the watermark.
4.2 Watermark Assignment
Although the potential number of matrices provided by this construction
is inexhaustible, systematic assignment of shift polynomials which result
in distinct matrices is non-trivial. A scheme that enables assignment of
a 10 digit (decimal) PIN, a 10 digit camera Serial Number
and individual image assignments exceeding 1030 will
be presented.
4.3 Camera Interface
The column-based construction of our matrices is commensurate with CCD
readout. This limits the watermark to spatial domain. The embedding could
be performed by existing DSP or microprocessor hardware, or implemented
via an EPLD. The memory requirement is minimal: n shift polynomial
coefficients and the parent sequence (p terms). For shift register
sequences, only the register coefficients are required, reducing memory
space to a total of order n+log2(p). A card reader needs
to be installed in the camera, unless a smart card is to be employed. In
that case, the watermark generation could be performed within the card,
whose output could be an analog voltage. Such external implementation requires
camera clock and row/column sync etc to be communicated between the card
and the camera.
4.4 Computer Interface
The watermark described in this paper is designed to protect the image
between acquisition and distribution. It may be incompatible with or interfere
with the watermark(s) involved at the distribution stage. Therefore, it
may be desirable to combine the insertion of the new watermark with the
removal of the previous one. This is likely to be essential where lossy
compression is involved. Such compression may be applied successively and
the results may not be commutative (e.g. DCT based JPEG and fractal compression).
Watermarks designed to cope with such issues need to be involved.
5. REFERENCES
-
J. Bernasconi, "Low autocorrelation binary sequences: statistical mechanics
and configuration space analysis", Journal de Physique 48 (1987), 559-567
-
D. Everett, "Periodic digital sequences with pseudonoise properties", G.E.C.
Journal, 33, No.3, (1966), 115-126.
-
F. Hartung, M. Kutter, "Multimedia Watermarking Techniques", Proc. IEEE,
87, 7, July 1999, 1079-1107.
-
G. Langelaar, R. Lagendijk, J. Biemond, "Removing Spatial Spread Spectrum
Watermarks by Non-linear Filtering (EUSIPCO'98), 8-11 Sept 1998, Rhodes,
Greece.
-
F.J. MacWilliams and N.J.A. Sloane, "Pseudo-random sequences and arrays",
Proc. IEEE 64 (1976), 1715-1729.
-
K. Ohue, "A Generation Method of Periodic Orthogonal Numerical Sequences
with Small Maximum Amplitude for any Period", IEICE Trans, Fundamentals,
E80-A, 10, (1997), 2016-2021.
-
F.A.P. Petticolas, R.J. Anderson, M.G. Kuhn, "Information Hiding-A Survey",
IEEE Proceedings, 87, 7, July 1999, 1063-1077
-
M.R. Schroeder, "Number Theory in Science and Communication", Third Edition,
Springer (1997)
-
I.D. Svalbe, A.Z. Tirkel, R.G. van Schyndel, "Discrete Angle Watermark
Encoding and Recovery ", ICPR Barcelona 2000.
-
A.Z. Tirkel, G.A. Rankin, R.M. van Schyndel, W.J. Ho, N.R.A. Mee, and C.F.
Osborne, "Electronic water mark", Proceedings of DICTA-93, Macquarie University,
Sydney, December 1993, 666-673.
-
R. van Schyndel, A.Z. Tirkel, I.D. Svalbe, "A Multiplicative Color Watermark",
IEEE-EURASIP Workshop on Non-Linear Signal and Imaging Processing, Antalya,
Turkey, 1999, 336-340.
-
R. van Schyndel, A.Z. Tirkel, I.D. Svalbe, T.E. Hall, C.F. Osborne, "Algebraic
Construction of a New Class of Quasi-Orthogonal Arrays in Steganography",
SPIE Electronic Imaging 1999, San Jose, USA, 354-364.