Digital (Image) Watermarking Mostly taken from "Watermarking Techniques used in Medical Images: a Survey", Mousavi, Naghsh, and Abu-Bakar, Journal of Digital Imaging 27:714-729, 2004 Introduction Watermark can be visible or not. Watermark is used for - proving provenance (image is signed by the watermark) - tracing image propagation (each image has different watermark ... who distributed it illegally?) Watermarking is like steganography, but purpose of watermarking is not to convey a covert message. Types of watermarks - fragile - watermark is easily destroyed by modifying the image - useful for proving provenance or data integrity - semi-fragile: - watermark survives some attacks - robust: - watermark survives strong attacks Other watermark property - reversible: - original image can be exactly recovered Taxonomy of data security [01-taxonomy.png] Lifetime of a watermark [02-lifetime_of_a_watermark.png] Note that the extracted watermark might not be exactly the same as the original, so there may be a degree of confidence (< 100%) that it matches. Attacks to remove watermarks Image is changed, which may (accidentally?) remove the watermark signal processing types compression colour/intensity changes noise addition, or de-noising convolutions: frequency filtering or blurring re-scanning geometric types cropping column/row removal transformations: rotate/scale/translate Spatial methods watermark is embedded directly into pixels not very robust high capacity - LSB method (least significant bit) - replace all least-significant bits with a repeated watermark - good against geometric attacks (cropping, row/col removal, transformations) - bad against signal processing attacks - LBP method (local binary pattern) - break image into blocks; replace middle pixel in the block with average of block *plus* watermark bit. Extracting computes block average and the difference between that and the middle bit. - good against intensity changes - bad against convolutions - Histogram modification - "Reversible Data Hiding", Ni, Shi, Ansari, and Su, IEEE Transactions on Circuits and Systems for Video Technology 16(3):354-362, 2006 Embedding: 1. Build histogram. Find pixel value p_max with maximum h(p_max). Find pixel value p_min > p_max with minimum h(p_min). (Assume only one such pair; can extend to more pairs.) 2. Store all coordinates of pixels with value p_min. Call this the "overhead". These coordinates will be lost in the next step and must be encoded with the watermark. 3. Add 1 to all pixels in [p_max+1,p_min-1]. They go to [p_max+2,p_min]), overwriting the pixels of value p_min, which have their coordinates recorded. Now there are no pixels with value p_max+1. 4. Scan pixels in some order. When pixel of value p_max is found, add 0 or 1 to it depending on the next bit in the watermark. Include the "overhead" in this stream of bits. In the resulting image, pixels of value p_max correspond to zeros, while pixels of value p_max+1 correspond to ones. [03-reversible-histo-before.png] [04-reversible-histo-after.png] Extraction: Since you embedded the watermark, you *know* p_max and p_min. These are not stored in the image. 1. Scan pixels in same order. p_max -> 0 and p_max+1 -> 1 in extracted watermark and "overhead". 2. Scan pixels again. Subtract 1 from each pixel value in (p_max,p_min]. 3. Set all pixels with coordinates in "overhead" to p_min. - can be modified to use multiple pairs of (p_max,p_min) for more information hiding. - this is pretty fragile ... better used for authentication or steganography Transform methods watermark is embedded in coefficients in transformed domain (e.g. FT, DCT, DWT, ...) not very robust high capacity Fourier transform - embed in phase coefficients, since it's hard to remove without degrading the image. But this adds some distortion - embed in magnitude coefficients. Less distortion but easier to remove. Magnitude is immune to translation and cropping. "Robust watermarking method in DFT domain for effective management of medical imaging", Cedillo-Hernandez, Garcia-Ugalde, Nakano-Miyatake, and Perez-Meana, Signal, Image and Video Processing, 9(5):1163-1178, 2015 1. Apply FT. Pick coefficients in a mid-range of frequencies. (Modifications to low frequencies would be more apparant, while modifications to high frequencies would be lost in compression.) Choose alpha = minimum change in magnitude that would cause watermark to be lost. 2. In the +u,+v quadrant, within the mid-range of frequencies, assign one coefficient to each bit of the watermark.. 3. For the i^th bit of the watermark, look at the magnitudes M(u_i,v_i) and M(-u_i,v_i). Let d_i = M(u_i,v_i) - M(-u_i,v_i). If i^th bit is 0, ensure that M(u_i,v_i) - M(-u_i,v_i) <= -alpha: If that's not already the case, set M'( u_i,v_i) <- M( u_i,v_i) - 0.5(alpha+d_i) M'(-u_i,v_i) <- M(-u_i,v_i) + 0.5(alpha+d_i) Then d'_i = M'(u_i,v_i) - M'(-u_i,v_i) = (M( u_i,v_i) - 0.5(alpha+d_i)) - (M(-u_i,v_i) + 0.5(alpha+d_i)) = (M( u_i,v_i) - M(-u_i,v_i)) - (0.5(alpha+d_i) + 0.5(alpha+d_i)) = d_i - (alpha+d_i) = -alpha If i^th bit is 1, ensure that M'(u_i,v_i) - M'(-u_i,v_i) >= +alpha: If necessary, add 0.5(alpha-d_i) to M(u_i,v_i) and subtract 0.5(alpha-d_i) from M(-u_i,v_i). Then (similar to above) d'_i = +alpha. Then the sign of the difference, M(u_i,v_i) - M(-u_i,v_i), indicates whether the i^th bit is 0 (sign < 0) or 1 (sign > 0). Changes to the magnitudes by up to alpha won't change the signs. Immune to translation, cropping, and some degree of smoothing.