The following are alrgorithms that MEP infterface implements: COX, XIE

Cox's DCT, additive, non-blind Image Watermarking Algorithm

This algorithm is considered a classical watermarking algorithm and was first introduced in the paper by:

[1] Ingemar J. Cox, Joe Kilian, Tom Leighton, and Talal G. Shamoon. In Proceedings of the IEEE International Conference on Image Processing, ICIP '97, volume 6, pages 1673 - 1687, Santa Barbara, California, USA, 1997.

Watermark generation, embedding and extraction will now be explained so if you don't enjoy math tune out now.

Watermark Generation:

The mark is a Gaussian sequence of pseudo-random real numbers and will be denoted X = x1, x2,….xn were n is length of watermark. The choice of the watermark length n determines to which degree the watermark is spread out. In most cases the larger the watermark the lesser the embedding strength needs to be. There is no one watermark length n that is suitable for all images therefore it is image specific.

Embedding Watermark

When embedding the watermark a series of coefficients are extracted from the images DCT domain. Let the image be denoted by P and the series of coefficients be C = c1, c2,….cn were n is length of watermark. The series of coefficients C are the largest (most significant) in the DCT domain. Before watermarking the image P it has to be subjected to a DCT transformational change. Extraction of significant coefficients can then take place. The watermark can then be embedded by altering the coefficients by the following formula:

(1) c_i' = c_i + a x_i

Where a can vary from 0 to 1 and is the embedding strength of the watermark. As noted in Cox's paper it may not be applicable to use a single scaling factor for all values of ci. It is possible to change the above formula to:

(2) c_i' = c_i + a_i x_i

Rules can then be set so that a_i is chosen so that watermark will not be perceptually noticeable. The first of the equations is implemented for Cox's algorithm. Because we are using a single scaling factor it is best to leave this at its default value of 0.5 for most pictures so that watermark will most likely not be noticeable. Figure 1 below illustrates the embedding algorithm just described.

Extraction and Comparison of Watermark

From equation (1) we can take the logarithm of original coefficients to get:

(3) c_i = c_i exp(a x_i)

From equation (3) an inverse embedding function can easily be found to be:

(4) x_i* = (c_i* - ci) / (a x_i)

Where c_i* are the extracted coefficients from the watermarked images DCT domain. From equation (4) we see that the original coefficients ci are needed therefore we need the original image. This is why Cox's algorithm is non-blind and needs the original image to extract the watermark. Now that we have the extracted watermark, X*, we can compare it to the original watermark with the following formula:

(5) d = [(X*) (X)] / [ |X*| |X|]

Value of d can range from 1 to -1. The closer the value is to 1 the better the watermark match is. For the purpose of our paper a correlation of .4 or better was deemed to be an acceptable match.


Xie's DWT, Quantization, Blind Image Watermarking Algorithm

This algorithm is the stronger of the two watermarking algorithms used and was first introduced in the paper by:

Liehua Xie and Gonzalo R. Arce.
Joint wavelet compression and authentication watermarking. In Proceedings of the IEEE International Conference on Image Processing, ICIP '98, Chicago, IL, USA, 1998.

Paper describes a blind watermarking algorithm for embedding watermark for authentication. The watermark algorithm is implemented in the Discrete Wavelet Transform, DWT. Xie and others also discuss implementation of SPIHT compression algorithms but we did not focus on this. Watermark generation, embedding and extraction will now be explained so if you don't enjoy math shut your eyes now.

Watermark Generation:

The watermark, X = x1, x2,….xn were n is length of watermark, is made up of binary values, xi Î {0,1} for i £ n.

Embedding the Watermark

First the image to be watermarked is decomposed to obtain a low-frequency approximation representation which is the LL component. The LL component is the top level of the pyramid of the wavelet transformed image. The LL component is where the watermark will be embedded. Sliding a non-overlapping 3x1 window over 3 coefficients, each time manipulating them, embeds the watermark. Let b1, b2, and b3 denote the coefficients of the 3x1 sliding window. The local sliding window variables are first sorted in ascending order b(1), b(2), and b(3). The range between b(1) and b(3) are then split into intervals according to:

(1) space = a [b(1) + b(3)] / 2

The median of the three coefficients are quantized to become a multiple of "space" to represent one bit of watermark data, xi. Therefore the region is divided into 2/a where the default value of a=0.05. Each region will have two boundaries denoted by lk and lk+1. All 1's are associated to all even boundaries and all 0's are associated with odd boundaries. The coefficient is manipulated to lie on the boundary representing the watermark bit xi. The manipulated coefficient is then updated in the subband component.

Extracting the Watermark

Since this is a blind algorithm the watermark is extracted without the original image. The median of the sliding window is determined and quantized to obtain a reconstruction point. The bit value is then determined from the associated reconstruction point which is assigned to xi* where X* is extracted watermark. The extracted watermark, X*, is then compared with that of the original watermark X.