Abstract
Separable reversible watermarking enables two encoders to separately embed a payload in a cover, and the original cover can be reconstructed by cooperation. It is required to limit the embedding distortion for the two encoders so that the marked content will not be seriously degraded, whereas both encoders expect to embed a sufficient payload. It motivates us to present a two-encoder game related to rate-distortion optimization of reversible watermarking. We investigate non-cooperative game and cooperative game in a parameterized perspective, which provides good generalization. We find the equilibrium strategies for both encoders under constraints. We extend the game to a multistage win-or-lose case, where both encoders want to win the game. We model the game on a rooted tree with unbounded branching and identify the winner once the initial state is given.
Introduction: The Two-Encoder Challenge
Reversible Watermarking (RW), or Reversible Data Hiding, is a specialized technique designed for high-integrity environments like medical imaging or military communications. Unlike standard watermarking, RW allows for the perfect, bit-for-bit reconstruction of the original cover content after the payload has been extracted.
While most research focuses on a single encoder, real-world scenarios often involve multiple parties needing to embed data into the same digital asset. This paper investigates the two-encoder problem, where Alice embeds a payload first, followed by Bob. This setup creates a "resource conflict": both encoders compete for the "smooth" regions of the image, which provide the best rate-distortion performance. Furthermore, Bob's subsequent modifications act as noise for Alice, requiring her to use robust, error-correcting strategies that inherently reduce her capacity.
Modeling Strategic Interaction
The authors model the cover as a collection of binary sequences, using information entropy to quantify "smoothness." The interaction is analyzed through two primary game-theoretic frameworks:
- Non-cooperative Game: Alice and Bob act independently. Alice must anticipate Bob's potential modifications, treating his embedding process as a noisy channel. The goal is to identify a Nash Equilibrium, where neither player can improve their payload (payoff) by unilaterally changing their strategy.
- Cooperative Game: Alice and Bob coordinate their efforts. This can involve Shared Keys, where they share exact modification positions (effectively a single-logic multi-layer system), or Independent Keys, where they cooperate on high-level goals without sharing low-level implementation details.
Equilibrium and Payoff Analysis
The core of the research lies in finding stable equilibrium strategies. The authors derived explicit payoff equations for Alice ($A_i$) and Bob ($B_i$) based on their chosen strategy parameters. A key finding is that these payoff functions are strictly monotone relative to distortion. Consequently, in a constrained environment, the equilibrium strategies always lie on the boundary of the allowable distortion ($p_{max}$).
In non-cooperative settings, a "second-player advantage" often emerges. Because Alice embeds first, she bears the "cost" of ensuring robustness against Bob's future changes. Bob, acting on the already-modified cover, can often optimize his strategy more effectively to achieve a higher relative payoff.
Key Insights and Results
- Smoothness as a Finite Resource: Smooth areas are formalized as a precious resource. Competition effectively increases the "cost" (distortion) of using these areas.
- Algorithmic Efficiency: For complex covers, the authors demonstrate that equilibria can be found efficiently using binary search or gradient descent, thanks to the monotonicity and concavity of the distortion functions.
- Cooperation Simplifies Optimization: When players share keys, the complex strategic balancing of the non-cooperative game collapses into a standard linear programming problem, solvable via the Simplex algorithm.
- Multistage Extension: The game is extended to a win-or-lose scenario modeled on a rooted tree, allowing for the identification of a winner based on initial states.
Limitations and Future Directions
While providing a robust theoretical foundation, the study currently relies on an additive distortion model, which may not fully account for the Human Visual System's (HVS) masking effects. Additionally, the focus on binary sequences, while generalizable to LSB planes, needs further extension to spatial domain techniques like Histogram Shifting. Future work could also expand the model to "N-player" games or include active adversaries attempting to remove the watermarks.
Summary updated