💻 computer science

TRACE: Structure-Aware Character Encoding for Robust and Generalizable Document Watermarking

TRACE is a structure-aware document watermarking framework that leverages diffusion models to embed data through localized character encoding, achieving superior robustness, generalizability across languages and fonts, and significant performance gains over state-of-the-art methods.

Original authors: Jiale Meng, Jie Zhang, Runyi Hu, Zhe-Ming Lu, Tianwei Zhang, Yiming Li

Published 2026-03-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jiale Meng, Jie Zhang, Runyi Hu, Zhe-Ming Lu, Tianwei Zhang, Yiming Li

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 have a very important document, like a contract or a secret letter. You want to prove it's yours if someone tries to steal it or forge it. But here's the catch: you can't change the words (that would ruin the contract), and you can't write a giant "PROPERTY OF ME" in red ink (that would look suspicious).

This is the problem TRACE solves. It's a new way to hide a secret digital fingerprint inside a document without anyone noticing.

Here is how it works, explained through a simple story and some analogies.

The Problem: The "Bad" Ways to Hide Secrets

Before TRACE, people tried to hide secrets in documents in two main ways, and both had big flaws:

The "Pixel Painter" (Image-based): Imagine trying to hide a secret by slightly changing the shade of black ink on a few pixels of a letter.
- The Flaw: If you print the document and scan it back in, the printer and scanner act like a noisy photocopier. They blur the edges and add "dust" (noise). This tiny change in pixel shade gets wiped out, and your secret disappears.
The "Font Swapper" (Font-based): Imagine having a secret dictionary where the letter "A" has 50 different versions. To send a secret, you swap the normal "A" for a specific "A" from your dictionary.
- The Flaw: This only works if you have a dictionary for every possible font and handwriting style. If you encounter a weird, artistic font or someone's messy handwriting, your dictionary is useless. It's like trying to unlock a door with a key that only fits one specific lock.

The Solution: TRACE (The "Skeleton Shifter")

The authors of TRACE realized that letters aren't just blobs of ink; they have a skeleton. Think of a letter like a stick figure made of bones (strokes) and joints (endpoints and corners).

TRACE doesn't paint pixels or swap whole fonts. Instead, it gently nudges the joints of the stick figure.

The Analogy: The "Puppet Master"

Imagine the letter "A" is a puppet made of sticks.

Finding the Handle: TRACE looks at the puppet and finds the perfect "joint" to grab (like the top tip of the "A"). It calls this the Handle Point.
Deciding the Move: Based on whether it wants to send a "0" or a "1," it decides to move that joint slightly up, down, left, or right.
The Magic Move (Diffusion): This is where the cool tech comes in. TRACE uses an AI (called a Diffusion Model) that acts like a super-smart puppet master. It doesn't just drag the joint; it redraws the whole arm of the puppet so that the joint moves to the new spot, but the rest of the arm looks perfectly natural. It's like a cartoonist redrawing a frame so smoothly that the eye doesn't notice the character moved an inch.

How It Works in 3 Simple Steps

1. The Scout (Adaptive Initialization)
Before doing anything, TRACE scans the document. It uses a smart algorithm to find the best "joint" to move. It asks: "If I move this point, will the letter still look like the same letter? Will it survive being printed and scanned?" It picks the strongest, most stable joint to be the handle.

2. The Artist (Guided Diffusion)
Once the joint is picked, the AI steps in. It uses a technique called DragDiffusion. Imagine you are dragging a point on a digital drawing, and the AI instantly fills in the rest of the line to make it look natural.

If the secret bit is 0, it moves the joint a tiny bit closer to a neighbor point.
If the secret bit is 1, it moves it a tiny bit further away.
The AI ensures the letter doesn't look "broken" or "weird" during this move.

3. The Editor (Masked Replacement)
Sometimes, when the AI redraws the line, it might accidentally change a tiny bit of the background or a nearby curve. TRACE has a safety net. It takes the original document and pastes the new secret part right over it, like a surgeon stitching a tiny patch. This ensures that everything outside the secret move looks exactly like the original.

Why Is TRACE a Superhero?

It's Invisible: Because it only moves the "bones" of the letter slightly, the letter looks exactly the same to the human eye. Even if you zoom in, it's hard to tell.
It's Tough (Robust): This is the magic part. If you print the document, scan it, or take a photo of it with your phone, the "noise" (blur, dust, ink spread) might mess up the pixels. But the structure (the skeleton) stays the same. The joint is still slightly closer or further away than before. The secret survives the "cross-media" journey.
It's Universal: It doesn't need a dictionary of fonts. It looks at the structure of any letter, whether it's a fancy script, a messy handwriting, or a weird math symbol. It figures out the skeleton on the fly.

The Result

In tests, TRACE was able to hide secrets in documents that survived being printed, scanned, and photographed, with 99% accuracy in retrieving the secret. Meanwhile, older methods failed miserably or left obvious visual clues.

In a nutshell: TRACE is like a master forger who can slightly bend the spine of a letter to hide a message, knowing that no matter how much the paper gets crumpled or copied, that bent spine will always tell the story.

1. Problem Statement

Document watermarking is critical for tracing the provenance of digital and physical documents (e.g., contracts, official papers) and preventing misuse. However, existing methods face a "trilemma" where they struggle to simultaneously achieve robustness, generalizability, and imperceptibility:

Image-based methods: Embed data by altering pixel ratios (black/white). They are highly vulnerable to noise introduced during cross-media transmission (printing, scanning, photographing), leading to extraction errors.
Font-based methods: Rely on pre-defined codebooks of character variants. While robust to noise, they lack generalizability because codebooks cannot cover every possible font, language, handwriting style, or artistic typography without extensive manual training.
Format/Linguistic methods: Alter spacing or text semantics, which often compromises document integrity or has low embedding capacity.

The Core Challenge: Design a method that embeds data into documents such that it survives cross-media attacks (print-scan), works across diverse fonts/languages (including handwritten and artistic styles) without pre-training, and remains visually imperceptible.

2. Methodology: TRACE Framework

The authors propose TRACE (Structure-Aware Character Encoding), a framework that leverages Diffusion Models (specifically DragDiffusion) to embed data by subtly modifying the skeletal structure of characters rather than their pixel values or font variants.

The process consists of three main stages:

A. Adaptive Diffusion Initialization (ADI)

Before embedding, the system identifies optimal points to manipulate within a character's skeleton (endpoints and junction points).

Keypoint Detection: Extracts endpoints and junction points from the character skeleton.
Movement Probability Evaluator (MPE): An algorithm that automatically selects the best Handle Point ( $P_h$ ) and a Reference Point ( $P_r$ ). It scores points based on connectivity rules (e.g., ensuring the handle point is on a distinct stroke from the reference) to maximize the probability of successful extraction while maintaining visual consistency.
Target Point Estimation (TPE): Determines the Target Point ( $P_t$ ) based on the bit to be embedded (0 or 1).
- To embed 0: The distance between $P_h$ and $P_r$ is adjusted to be $\leq T_{embed}$ .
- To embed 1: The distance is adjusted to be $> T_{embed}$ .
- The movement direction is calculated using vector analysis of the stroke to ensure the character's identity is preserved.
Mask Drawing Module (MDM): Defines a local editing region (mask) around the handle and target points to confine the diffusion process.

B. Guided Diffusion Encoding (GDE)

The system uses a fine-tuned DragDiffusion model to move the handle point ( $P_h$ ) to the target point ( $P_t$ ).

LoRA Fine-tuning: The UNet is fine-tuned with Low-Rank Adaptation (LoRA) to better capture the original image's features, ensuring identity preservation.
Latent Optimization: The model iteratively moves the point using motion supervision.
Local Consistency Loss ( $L_{lc}$ ): A specialized loss function is introduced to minimize feature alterations in the masked region outside the immediate movement path, ensuring the rest of the character remains unchanged.

C. Masked Region Replacement (MRR)

To further enhance imperceptibility, the content within the mask of the original image is replaced with the corresponding content from the generated (edited) image. This step ensures that any unintended artifacts generated by the diffusion process outside the specific structural modification are reverted to the original, preserving the character's natural appearance.

D. Extraction

Extraction is blind (does not require the original image). The system detects the character skeleton, identifies the handle and reference points using the same MPE logic, and measures the distance $\Delta(P_h, P_r)$ . If the distance exceeds the threshold $T_{embed}$ , the bit is '1'; otherwise, it is '0'.

3. Key Contributions

Structure-Aware Paradigm: Shifts from pixel manipulation or font substitution to character structure encoding. By treating characters as skeletons of keypoints and lines, the method achieves inherent resistance to noise (as structure is more stable than pixel ratios).
Generalizability without Pre-training: Unlike font-based methods, TRACE does not require a pre-defined codebook or training on specific fonts. It dynamically generates encoded characters for any font, language (English, Chinese, Korean, Arabic, etc.), or style (handwritten, artistic) using the diffusion model.
Robustness and Imperceptibility Balance: Introduces MRR and $L_{lc}$ loss to solve the issue of diffusion models altering non-target regions, achieving high PSNR/SSIM while maintaining high extraction accuracy under attacks.
Comprehensive Evaluation: Demonstrates superior performance across multiple languages, font sizes, and cross-media scenarios (screenshots, print-scan, print-camera).

4. Experimental Results

The authors evaluated TRACE against state-of-the-art baselines (AutoStegaFont, Stegastamp, IHA) on English and Chinese fonts, as well as handwritten and artistic styles.

Robustness (Extraction Accuracy):
- Print-Scan: TRACE achieved 95–100% accuracy across various fonts, significantly outperforming AutoStegaFont (which dropped to ~60–70% in some cases).
- Print-Camera: Maintained >90% accuracy even at varying angles and distances, whereas baselines struggled.
- Adaptive Attacks: Resisted "structure morphing" attacks (elastic deformations) with >96% accuracy.
Imperceptibility (Visual Quality):
- PSNR: Achieved >32 dB (up to 41 dB for artistic fonts), representing a >5 dB improvement over baselines.
- SSIM: Consistently above 0.99, indicating near-perfect structural similarity to the original.
- Visuals: Residual images (difference between original and watermarked) were almost completely black, whereas baselines showed visible edge artifacts.
Generalizability: Successfully embedded watermarks in diverse scripts (Japanese, Russian, Arabic) and mathematical formulas without retraining.

5. Significance

TRACE represents a significant advancement in document security by solving the long-standing trade-off between robustness and generalizability.

Practical Application: It is suitable for real-world scenarios involving diverse document types (legal contracts, artistic typography, handwritten notes) where content cannot be altered (ruling out linguistic methods) and pre-training is impractical.
Security: It provides a reliable mechanism for copyright protection and leakage attribution, even after the document has been printed, scanned, or photographed.
Technical Innovation: It successfully adapts generative diffusion models (typically used for image editing) for the specific, constrained task of robust data hiding in text, introducing novel mechanisms (MPE, TPE, MRR) to ensure stability and stealth.

In conclusion, TRACE offers a unified, robust, and invisible solution for document watermarking that bridges the gap between digital and physical document security.