A set theoretic framework for watermarking and its application to semifragile tamper detection

We introduce a set theoretic framework for watermarking. Multiple requirements, such as watermark embedding strength, imperceptibility, robustness to benign signal processing, and fragility under malicious attacks are described as constraint sets and a watermarked image is determined as a feasible solution satisfying these constraints. We illustrate that several constraints can be formulated as convex sets and develop a watermarking algorithm based on the method of projections onto convex sets. The framework allows flexible incorporation of different constraints, including embedding strength requirements for multiple watermarks that share the same spatial context and different imperceptibility requirements based on frequency-weighted error and local texture perceptual models. We illustrate the effectiveness of the framework by designing a hierarchical semifragile watermark that is tolerant to mild compression, allows tamper localization, and is fragile under aggressive compression. Using a quad-tree representation, a spatial resolution hierarchy is established on the image and a watermark is embedded corresponding to each node of the hierarchy. The spatial hierarchy of watermarks provides a graceful tradeoff between robustness and localization under mild JPEG compression, where watermarks at coarser levels demonstrate progressively higher immunity to JPEG compression. Under aggressive compression, watermarks at all hierarchy levels vanish, indicating a lack of trust in the image data. The constraints implicitly partition watermark power in the resolution hierarchy as well as among image regions based on robustness and invisibility requirements. Experimental results illustrate the flexibility and effectiveness of the method.