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.
  1. 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.
  2. 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".
  3. 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

  1. J. Bernasconi, "Low autocorrelation binary sequences: statistical mechanics and configuration space analysis", Journal de Physique 48 (1987), 559-567
  2. D. Everett, "Periodic digital sequences with pseudonoise properties", G.E.C. Journal, 33, No.3, (1966), 115-126.
  3. F. Hartung, M. Kutter, "Multimedia Watermarking Techniques", Proc. IEEE, 87, 7, July 1999, 1079-1107.
  4. G. Langelaar, R. Lagendijk, J. Biemond, "Removing Spatial Spread Spectrum Watermarks by Non-linear Filtering (EUSIPCO'98), 8-11 Sept 1998, Rhodes, Greece.
  5. F.J. MacWilliams and N.J.A. Sloane, "Pseudo-random sequences and arrays", Proc. IEEE 64 (1976), 1715-1729.
  6. 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.
  7. F.A.P. Petticolas, R.J. Anderson, M.G. Kuhn, "Information Hiding-A Survey", IEEE Proceedings, 87, 7, July 1999, 1063-1077
  8. M.R. Schroeder, "Number Theory in Science and Communication", Third Edition, Springer (1997)
  9. I.D. Svalbe, A.Z. Tirkel, R.G. van Schyndel, "Discrete Angle Watermark Encoding and Recovery ", ICPR Barcelona 2000.
  10. 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.
  11. 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.
  12. 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.