# Chapter 5 - nsF5 and Wet Paper Coding: The Project's Core Algorithm (Week 6) > [🌐 中文版](https://yukinoshita-lin.github.io/nsf5-steganography/zh/content/ch05.html) > **Try it |** Goals: explain why shrinkage damages efficiency; understand wet paper coding as "wet positions untouched, solve on dry positions"; walk through the complete nsF5 flow in ns5_core.py. Two real-computed figures (Fig. 5-1 / Fig. 5-2) are included. ## 5.1 First, the Problem: F5's Shrinkage F5 modifies JPEG quantized coefficients by decrement: each time a coefficient's absolute value drops by 1, its LSB parity flips. But a coefficient with absolute value 1 (e.g. +1, −1) becoming 0 upon decrement. To JPEG, a 0 coefficient is an "absent frequency band", unsuitable as a carrier, so F5 abandons the block and looks elsewhere - that is **shrinkage**. - Shrinkage makes the **actual capacity** lower than the theory: blocks are wasted, the message needs more positions; - Shrinkage makes the **embedding efficiency** lower than α(p): more modifications are needed to compensate; - Shrinkage also leaves a detectable statistical feature: more coefficients are changed to 0, and the histogram looks abnormal. The project makes a clever analogy in the spatial (pixel) domain: subtract 128 from a pixel to get a "signed value" xv = pixel − 128, so pixels with |xv|≤1 (127, 128, 129) are the "dangerous" positions where decrement would hit near zero. The shrinkage problem of matrix embedding in JPEG becomes, in the pixel domain, the same problem as "127/128/129 must not be ordinary modification targets". ## 5.2 Wet Paper Coding: Mark the Wet First, Then Solve **Wet Paper Coding** is a framework by Fridrich et al. that answers: if some positions of a carrier are "untouchable" (like paper soaked wet - writing on them is invisible), can we complete embedding using only the remaining "dry" positions? Yes - and without the two parties needing to agree in advance which positions are wet, as long as the algorithm can reconstruct the same wet/dry partition from the image content itself. That is exactly what the project does: 1. For each block, find the positions that would become zero/dangerous on decrement and mark them wet; 2. The real problem: find a modification vector e on the **dry** positions such that flipping them makes the block's syndrome equal the target m; 3. That is, solve H[:,dry] · y = d, where d = s⊕m is the desired syndrome change; 4. The project solves in the order "single dry column hit → two dry columns XOR hit → GF(2) Gaussian elimination fallback", changing as little as possible; 5. The solution y is a 0/1 vector: y=1 positions are the dry positions actually to decrement. ![Fig. 5-1 wet/dry partition](../assets/nsf5_wet_dry.png) *Fig. 5-1 (real computation: ① a p=3 block; pixels 127/128/129 are judged **wet**(red) because "|xv|≤1, decrement would hit toward 0", the rest are **dry**(green); ② mapping pixel−128 to the signed coefficient xv - the closer to 0, the more dangerous)* > **Reading the figure |** The first step is always "**mark the wet first**": exclude positions that would become illegal (0 coefficient / hit zero) after decrement. Then embedding only happens at safe positions - that is exactly why nsF5 does not shrink and does not retry. > **Tip |** Why does "marking wet first" remove shrinkage? Because shrinkage comes from "only discovering it became 0 halfway through". nsF5 excludes all zero-colliding positions up front and solves only on safe dry points, so every block can embed successfully - no retries, no extra 0 coefficients. ## 5.3 Reading the Project: nsF5Pixel._embed() In `src/ns5_core.py`, the `nsF5Pixel` class inherits from `MatrixEmbedding` and only overrides `_embed()`. Reading it line by line shows the full nsF5 decision tree: *nsF5Pixel._embed() decision tree (pseudocode, logic identical to the source)* ```text xv = c[pos].astype(np.int16) - 128 # pixel -> signed coefficient s = syndrome(H, (xv & 1).astype(np.uint8)) if s == m: continue # syndrome already matched tc = hit_column(H, s ^ m) # most "direct" candidate position if abs(xv[tc]) > 1: # decrement won't hit zero -> change directly c[pos[tc]] -= sign(xv[tc]) # step toward 128 else: # candidate position is wet dry = [k for k in range(n) if abs(xv[k]) > 1] e = solve_wet_paper(H, dry, d) # solve only on dry points if e: decrement all hit dry points per e else: fallback flip target LSB (ensure decodability) ``` ## 5.4 The Three Solver Functions | **Function** | **Role** | **Key point** | | --- | --- | --- | | solve_wet_paper(H, dry_cols, target) | find a sparse solution among dry columns | weight 1 → weight 2 → Gaussian fallback | | gauss_solve_GF2(cols, b) | GF(2) Gaussian elimination | free variables set to 0 to reduce changes | | permute_index(total, seed) | deterministic pseudo-random permutation | splitmix64 + Fisher–Yates, C++-accelerable | ### 5.4.1 A Computable GF(2) Example (p=3, enough dry columns) Let p=3. Column j of `build_hamming(3)` is the 3-bit expansion of the binary number j (low bit on top), written $h_1,\dots,h_7$: $$ H=\begin{bmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}, \qquad h_1=\begin{smallmatrix}1\\0\\0\end{smallmatrix}, h_2=\begin{smallmatrix}0\\1\\0\end{smallmatrix}, h_3=\begin{smallmatrix}1\\1\\0\end{smallmatrix}, h_4=\begin{smallmatrix}0\\0\\1\end{smallmatrix}, h_5=\begin{smallmatrix}1\\0\\1\end{smallmatrix}, h_6=\begin{smallmatrix}0\\1\\1\end{smallmatrix}, h_7=\begin{smallmatrix}1\\1\\1\end{smallmatrix} $$ Assume pixels 1, 2, 3 of the block are wet (`|xv|≤1`, i.e. 127/128/129), so the dry columns are $\{4,5,6,7\}$. Suppose the desired syndrome difference is $d = s\oplus m = (1,1,0)^\top$. ![Fig. 5-2 wet paper solving](../assets/nsf5_solve.png) *Fig. 5-2 (real computation: ① H matrix - wet columns (pink boxes) excluded, dry columns (green boxes) usable, thick green = matched columns; ② the desired syndrome difference d; ③ the solution - find as few dry columns as possible whose XOR equals d. Here no single column hits; the 2-column hit h₄⊕h₇ = d, so columns 4 and 7 are changed)* > **Reading the figure |** > - **Single-column hit**: see if any dry column equals d (here none); > - **2-column hit**: see if two dry columns XOR to d (here h₄⊕h₇=[0,0,1]⊕[1,1,1]=[1,1,0]=d, hit); > - If neither works, use **GF(2) Gaussian elimination** as fallback. Key: solve only on "dry" points; wet points are never touched. **Step 1, single-column hit:** check whether any dry column equals $d=(1,1,0)^\top$: $h_4=(0,0,1)^\top$, $h_5=(1,0,1)^\top$, $h_6=(0,1,1)^\top$, $h_7=(1,1,1)^\top$. None equals $(1,1,0)^\top$ → no single hit. **Step 2, two-column XOR:** find two dry columns XORing to $d$. For example $h_5\oplus h_6 = (1,0,1)^\top\oplus(0,1,1)^\top=(1,1,0)^\top = d$ ✔. **Hit!** So only these two dry positions (their coefficients) are changed, no Gaussian needed. (The code finds the first matching pair in random order and may actually take h₄⊕h₇, which is equivalent to h₅⊕h₆; both satisfy `syndrome(H,e)=d`.) ### 5.4.2 When Is Gaussian Needed? - When Dry Columns Span All of GF(2)ᵖ The dry columns $\{4,5,6,7\}$ above are 4 in number and span all of GF(2)³, so most $d$ can be handled by a single or double hit. But if there are too few dry columns, or they are linearly dependent, the span shrinks. Example: only dry columns $\{4,5\}$ (more wet points). They and their pairwise XORs cover only 4 syndromes: $(0,0,0)$, $h_5=(1,0,1)^\top$, $h_6=(0,1,1)^\top$, $h_5\oplus h_6=(1,1,0)^\top$. If $d=(0,0,1)^\top$, none of these covers it - **no solution**. Why? GF(2) Gaussian elimination packs the dry columns into $A=[h_5\;h_6]$, a $3\times2$ matrix of rank at most 2 < p=3, so it **cannot span 3 dimensions**. A solution exists only if $d\in\mathrm{span}(A)$; $d=(0,0,1)^\top\notin\mathrm{span}\{(1,0,1)^\top,(0,1,1)^\top\}$, so `gauss_solve_GF2` returns `None` and `solve_wet_paper` returns `None`. **This is the mathematical essence of "not enough dry points": rank < p ⇒ some message bits cannot be realized.** > **Solvability criterion |** To embed any p-bit message on dry points, the number of dry columns usually needs to be ≥ p and those columns must span all of GF(2)ᵖ. That is why wet paper coding needs enough dry points (in nsF5 dry points are almost always sufficient; in extreme cases the code falls back to flipping the target bit to guarantee decodability). ### 5.4.3 Setting Free Variables to 0 = Change as Little as Possible Solving $A\,y=d$ generally has infinitely many solutions (when columns exceed the rank). `gauss_solve_GF2` sets **free variables to 0**, equivalent to "changing only the necessary dry columns", thereby **reducing the number of changed pixels** - which both raises embedding efficiency and lightens the statistical trace. > **Back to the code |** Open lines 145-215 of `src/ns5_core.py` and read against the 5.4 table. Read the function comments first, then verify with `test_wet_paper_needed()` in `src/test_core.py`: it forces pixels to 127/128/129 to create wet points and still completes an embed/decode roundtrip. ## 5.5 Verification: Efficiency and Roundtrip *Run the core self-tests + compare the two methods* ```bash python src/test_core.py ``` ```python # compare modified-pixel counts for matrix vs nsF5: import sys; sys.path.insert(0, "src") import numpy as np; from ns5_core import embed_string img = np.random.default_rng(0).integers(0, 256, (64, 64), np.uint8) for method in ("matrix", "nsF5"): stego, rep, nb = embed_string(img, "Hello nsF5!", method=method, p=3) print(method, "changed", rep["cover_changed"], "pixels / capacity", nb) ``` On the same random image and same message, matrix and nsF5 do not necessarily differ in change count - because nsF5's protected range (127/128/129) rarely triggers on random images. The real difference appears on an image dense with "dangerous pixels": nsF5 still embeds without shrinkage, while matrix may repeatedly fail. > **Try it |** Replace `img` with an image that is entirely 127/128/129, then compare the two methods' success count and change count - you directly feel the value of wet paper coding. ## 5.6 Summary and Self-Check - Shrinkage = decrement hitting zero and discarding a block, harming capacity, efficiency, and statistical safety (Fig. 5-1's "danger zone"); - Wet paper coding marks untouchable positions as wet up front and solves the syndrome equation only on dry points (Fig. 5-2); - nsF5 = matrix embedding + wet paper coding, no shrinkage, no retry; - The project simulates JPEG coefficients in the pixel domain with xv = pixel−128, treating |xv|≤1 as wet. > **Think about it |** Why does wet paper coding not need a pre-agreed set of wet positions? How does the decoder know which pixels cannot carry message bits? Hint: the decoder only reads LSBs to compute the syndrome - it never needs to know who was bypassed during embedding. One layer deeper: if a block has too many wet points and the dry ones do not span all of GF(2)ᵖ, what happens? (Combine with the rank argument in 5.4.2.)