📊 statistics

ADD for Multi-Bit Image Watermarking

This paper introduces ADD (Add, Dot, Decode), a theoretically grounded multi-bit image watermarking method that achieves superior robustness, capacity, and computational efficiency compared to state-of-the-art approaches by linearly combining learned watermarks with images and decoding via inner products.

Original authors: An Luo, Jie Ding

Published 2026-04-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: An Luo, Jie Ding

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are an artist painting a beautiful masterpiece. You finish it, but you're worried someone might steal it, claim it's theirs, or worse, use AI to make a fake copy and spread it as real news. You need a way to prove, "This is mine," without ruining the painting or making it look weird.

This is the problem of Image Watermarking.

For a long time, the solutions were like trying to hide a secret message by scratching tiny dots into the canvas. They were either too easy to erase (if you compressed the image or changed the brightness) or they could only carry a tiny note like "Yes, this is watermarked." They couldn't carry a full ID card, a timestamp, or a fingerprint.

Enter ADD (Add, Dot, Decode), a new method proposed by researchers An Luo and Jie Ding. Think of ADD not as scratching the canvas, but as teaching the image a secret handshake that only the owner knows.

Here is how it works, broken down into simple steps:

1. The Setup: The "Ghost" Signal

Imagine you have a special, invisible ink. But instead of just one color, you have a whole set of 48 different "ghost signals" (these are the bits of your message).

The Goal: You want to embed a 48-bit code (like a long password) into the image.
The Old Way: Old methods tried to hide this code by messing with the pixels in complex ways, like trying to weave a secret pattern into a tapestry. It was slow and fragile.
The ADD Way: ADD is much simpler. It treats the image like a blank canvas and the message like a set of instructions. It learns a specific "ghost signal" for each bit of the message.

2. The Training: Learning the "Ghost"

Before you can use the watermark, the computer has to learn what these ghost signals look like.

The Analogy: Imagine you are training a dog to sit. You don't just tell it to sit; you show it thousands of pictures of dogs and say, "When you see a dog, do this specific movement."
What ADD does: It looks at thousands of real photos. It asks, "If I add a tiny bit of 'Signal A' to this photo, can I still find 'Signal A' later even if someone smudges the photo, turns it sideways, or shrinks it?"
The Magic Trick: The math behind ADD ensures these signals are orthogonal. In everyday language, think of them as directions that don't interfere with each other. If you push a box North, it doesn't move East. ADD learns signals that push the image in directions that the image itself doesn't naturally go. This means the image doesn't look changed to the human eye, but the "ghost" is there, waiting to be found.

3. Embedding: The "Add" Step

Once the computer has learned these 48 ghost signals, embedding the watermark is incredibly fast.

The Action: You take your image and simply add the ghost signals to it, weighted by your secret message (0s and 1s).
The Result: The image looks exactly the same to you. It's like adding a whisper to a shout; the shout (the image) is still the loudest thing, but the whisper (the watermark) is there.

4. Decoding: The "Dot" Step

Now, imagine someone steals your image, crops it, compresses it, or rotates it. They try to destroy the watermark. How do you prove it's yours?

The Old Way: You might need to run a heavy, slow computer program to try and reverse-engineer the damage.
The ADD Way: You use a Dot Product.
- The Analogy: Imagine you have a flashlight with a very specific pattern of light (your learned ghost signal). You shine it on the image.
- If the image has your watermark, the light will bounce back brightly in a specific direction.
- If the image is fake or unwatermarked, the light just scatters.
- Because the signals are so distinct, you can just do a quick math check (a "dot product") to see if the signal is there. It's like checking a fingerprint against a database instantly.

Why is ADD a Game-Changer?

It's Super Strong (Resilient): Even if someone tries to blur, crop, or rotate the image, the "ghost signals" are so well-placed that they survive. In tests, ADD got 99.4% accuracy in reading the message even after the image was messed up. Other methods dropped to around 60-80%.
It's Super Fast: Because it's just simple addition and multiplication (no heavy neural networks running during the check), it is 7.4 times faster at decoding than the current best methods. It's the difference between waiting for a slow train and taking a bullet train.
It Carries More Info: It can hold a 48-bit message (enough for a user ID, a timestamp, and a signature) without breaking the image quality.
It's Theoretically Sound: The researchers didn't just guess this works; they proved mathematically that because images live in a "low-dimensional" space (they have patterns), these ghost signals can hide in the "empty space" where the image doesn't naturally go, making them invisible to us but obvious to the math.

The Bottom Line

ADD is like giving every image a super-fast, unbreakable, invisible ID card.

Old methods were like writing a secret note in invisible ink that fades if you look at it too hard.
ADD is like stamping the image with a laser that only your specific scanner can read, and it works even if the image gets crumpled in a pocket.

This technology is crucial for the future of the internet. As AI creates more realistic images, we need a way to know: Who made this? Is it real? Is it fake? ADD provides a fast, reliable, and mathematically proven way to answer those questions.

1. Problem Formulation

The paper addresses the critical challenge of multi-bit image watermarking in the era of generative AI. As high-fidelity image generation becomes ubiquitous, there is an urgent need to verify authenticity and trace provenance (e.g., identifying the user or model that generated an image).

Goal: Embed a $K$ $K$ -bit message ( $m \in \{-1, 1\}^K$ $m \in {- 1, 1}^{K}$ ) into an image $x$ $x$ to create a watermarked image $\tilde{x}$ $\tilde{x}$ such that:
1. Quality: $\tilde{x}$ remains visually indistinguishable from $x$ .
2. Identifiability: A verifier can detect if an image is watermarked and decode the embedded message.
3. Resilience: The message must survive common distortions (compression, rotation, noise, cropping).
Limitations of Existing Methods: Current approaches (both traditional frequency-domain and deep learning-based) often suffer from:
- Low capacity (typically $\le 32$ bits).
- Poor resilience to distortions.
- Lack of theoretical justification for why they work.
- High computational costs for embedding and decoding.

2. Methodology: ADD (Add, Dot, Decode)

The authors propose ADD, a method that simplifies the watermarking process into three distinct stages: Add (embedding), Dot (inner product computation), and Decode (sign extraction).

A. Core Mechanism

Embedding (Add): The watermark is added linearly to the image.
$\tilde{x} = x + \sum_{k=1}^{K} m_k w_k$
Where $w_1, \dots, w_K$ are learned watermark vectors corresponding to the $K$ bits of the message.
Decoding (Dot & Decode): To recover the message from a potentially distorted image $\tilde{x}'$ , the verifier computes the inner product between the image and each learned watermark vector:
$\Gamma_k = \langle w_k, \tilde{x}' \rangle$
The $k$ -th bit is decoded as $\hat{m}_k = \text{sign}(\Gamma_k)$ .
Detection: A test statistic $S = \sum_{k=1}^K |\Gamma_k|$ is used to determine if an image is watermarked (rejecting the null hypothesis $H_0$ if $S$ exceeds a threshold). If a dictionary of known messages $\mathcal{D}$ is available, a maximum likelihood approach ( $\max_{m \in \mathcal{D}} \langle m, \Gamma \rangle$ ) is used for improved performance.

B. Training Objective

The watermark vectors $w_{1:K}$ are learned via a training objective that balances three goals:

Identifiability: Uses a margin-based loss (e.g., hinge or logistic loss) to ensure the inner product $\langle w_k, \tilde{x}' \rangle$ has the correct sign corresponding to $m_k$ .
Resilience: The training simulates distortions by applying random distortion operators $A$ (e.g., JPEG, rotation) to the watermarked image before computing the loss.
Quality: A regularization term $\beta \sum \|w_k\|^2$ penalizes the magnitude of the watermark to preserve image quality.

Implementation Detail: Instead of optimizing in high-dimensional pixel space, ADD learns a low-dimensional mapping. A frozen feature extractor $\psi$ extracts features from the image, and trainable maps $g_k$ generate the watermark $w_k = g_k(\psi(x))$ . The final deployed watermark is the dataset-level average of these generated vectors.

3. Theoretical Analysis

The paper provides a rigorous theoretical foundation explaining why ADD works, based on the assumption that natural images lie near a low-dimensional subspace with Gaussian noise.

Geometric Structure: The training objective forces the learned watermarks to be orthogonal to the low-dimensional image subspace ( $U$ $U$ ) and mutually orthogonal to each other.
- $w_k \in U^\perp$ (Orthogonal to image content).
- $\langle w_k, w_j \rangle = 0$ for $k \neq j$ .
Statistical Guarantees:
- Under the null hypothesis (unwatermarked image), the inner products $\Gamma_k$ follow a Gaussian distribution centered at 0.
- Under the alternative hypothesis (watermarked), $\Gamma_k$ follows a Gaussian distribution centered at $\mu m_k$ .
- The authors prove that the Generalized Likelihood Ratio Test (GLRT) derived from this structure yields the optimal detection and decoding rules (sign function and sum of absolute values).
- They establish convergence results showing that as the training sample size $n \to \infty$ , the finite-sample watermark properties converge to the ideal population properties.

4. Key Results

Experiments were conducted on the MS-COCO dataset with a challenging 48-bit message capacity.

A. Performance vs. State-of-the-Art (SOTA)

Decoding Accuracy: ADD achieves 100% decoding accuracy on undistorted images and maintains ~99.4% average accuracy across various distortions (JPEG, rotation, noise, etc.).
- Comparison: SOTA methods (HiDDeN, SSL, DwtDct) dropped significantly under distortions, with an average accuracy drop of ~14% compared to ADD's drop of at most 2%.
Image Quality: ADD maintains a PSNR of 32.36 dB, comparable to or slightly better than deep learning baselines (HiDDeN: 32.88 dB, SSL: 33.09 dB) while offering superior robustness.
Detection: ADD achieves the highest Area Under the ROC Curve (AUROC), reaching 99.6% with a message dictionary and 98.8% without one.

B. Computational Efficiency

ADD offers massive speed improvements due to its simplicity (linear addition and dot products vs. neural network inference):

Embedding: 2 $\times$ faster than the fastest existing method (HiDDeN).
Decoding: 7.4 $\times$ faster than the fastest existing method.
- ADD Decoding: 0.19 ms/image vs. HiDDeN: 1.41 ms/image.

C. Generalizability

A watermark trained solely on MS-COCO generalized effectively to ImageNet, CIFAR-10, and CIFAR-100 without retraining, maintaining >99% bit accuracy and high AUROC.

5. Significance and Contributions

High-Capacity Robustness: ADD successfully handles 48-bit messages with near-perfect accuracy under severe distortions, a regime where previous methods fail.
Theoretical Rigor: It is one of the first multi-bit watermarking methods to provide a complete theoretical analysis linking the learning objective to geometric orthogonality and statistical hypothesis testing.
Computational Efficiency: By avoiding complex neural encoders/decoders at inference time, ADD enables real-time, scalable watermarking suitable for high-throughput applications.
Practical Deployment: The method supports both dictionary-free detection (for unknown sources) and dictionary-based detection (for specific user attribution), making it versatile for different use cases (e.g., model providers vs. individual artists).

In summary, ADD represents a paradigm shift in image watermarking, moving from complex, black-box neural networks to a simple, theoretically grounded, and highly efficient linear framework that excels in both robustness and speed.