# Chapter 4 - Matrix Embedding and F5: Change Less, Hide More (Week 5)

<!-- lang-switch -->
> [🌐 中文版](https://yukinoshita-lin.github.io/nsf5-steganography/zh/content/ch04.html)




> **Try it |** Goals: understand why "embedding efficiency" matters; hand-compute a p=3 Hamming syndrome embedding example; read the matrix-coding schematic and efficiency curves; know F5's "shrinkage" problem.

## 4.1 From "1 bit per pixel" to "p bits per change on average"

Naive LSB changes 0.5 pixels on average per stored bit - very inefficient. Suppose there were a code where each block of n pixels lets you store p bits by **changing at most 1 pixel**: changes drop dramatically. That idea is **Matrix Embedding**, and its math tool is the binary Hamming code.

Define embedding efficiency α = average bits carried per modification. The theoretical ceiling is p bits per change, α(p) = p·2ᵖ/(2ᵖ−1): ~2.67 at p=2, ~3.43 at p=3, ~4.27 at p=4, rising with p - but the block length n=2ᵖ−1 grows too.

> **Tip |** Why is larger p "better"? Because the Hamming code uses n=2ᵖ−1 positions to carry p message bits; the bigger p, the less "waste" of n relative to p, and the more info each change carries on average. The cost: bigger blocks, and the message is pickier about the carrier structure. Look at Fig. 4-1 to see "7 positions hold 3 bits, flipping just 1 pixel" directly.

## 4.2 Hamming in a Nutshell: Parity-Check Matrix and Syndrome

Let block length n=2ᵖ−1. Build a p×n **parity-check matrix H** whose n columns are exactly all non-zero vectors in GF(2)ᵖ: at p=3 the seven columns are binary 1..7. Write the n pixel LSBs of a block as a column vector x, and define the syndrome s = H·x (mod 2), a p-bit vector.

To embed p message bits m, we want to flip a few bits so the new syndrome equals m. Since every column of H is distinct, flipping bit j only turns the syndrome into s⊕Hⱼ - that is, **any needed syndrome change matches some column**.

1. Compute the current syndrome s = H·x;
2. If s == m, no change needed in the block;
3. Otherwise compute the difference d = s ⊕ m (a non-zero p-bit vector);
4. Find the column of H equal to d - call it column j;
5. Flip the LSB of pixel j; done (H·x′ = m).

![Fig. 4-1 matrix-coding syndrome schematic](../assets/f5_syndrome_demo.png)

*Fig. 4-1 (real computation: ① parity-check matrix H (p=3, n=7); the red box highlights the "target column"; ② this block's 7 pixel LSBs: x; ③ current syndrome s=H·x; ④ the 3 message bits to hide: m; ⑤ difference d=s⊕m. Since d equals H's column 1, only the 1st pixel's LSB is flipped to get ⑥ the new syndrome = m)*

**Read this figure and you have all of matrix coding**:
- **H has 7 columns, each a 3-bit binary** (for 1~7);
- **s = H·x**: XOR the columns where x is 1 to get the current syndrome;
- **To turn the syndrome into m**: just flip the pixel whose column equals d=s⊕m;
- Conclusion: **to hide 3 bits, most cases only need 1 pixel changed**.

## 4.3 A Worked p=3 Example

Let the 7 pixel LSBs of a block be x = [0,1,0,1,1,0,1]. Columns in binary order (low bit on top): H₁=[1,0,0], H₂=[0,1,0], H₃=[1,1,0], H₄=[0,0,1], and so on. First the syndrome: the 1-positions of x are columns 2,4,5,7; XOR them: H₂⊕H₄⊕H₅⊕H₇ = [0,1,0]⊕[0,0,1]⊕[1,0,1]⊕[1,1,1] = [0,0,1], so s=[0,0,1].

To embed m=[1,1,0]: d = s⊕m = [0,0,1]⊕[1,1,0] = [1,1,1]. H₇=[1,1,1], hits column 7, so flip the 7th pixel's LSB: x′=[0,1,0,1,1,0,0]. Recompute s′=H·x′=[1,1,0]=m, success.

**7 pixels carry 3 message bits, but on average only ~87.5% of blocks need a 1-bit change** - about 0.875 changes per block, i.e. per 3 bits about 0.875 changes, ~3.43 bits per change.

> **Try it |** `src/matrix_demo.py` turns this into a clickable visual panel (the "Matrix Coding Demo" tab in the GUI). Use `demo_step(p, x, m_bin)` to see the returned s, d, and the matched column, then verify H·x′ == m by hand.

## 4.4 Why Efficiency Matters: Capacity, Change Rate, and Detectability

"Hiding successfully" is not the skill; what matters is **for the same message, the fewer changes, the smaller the statistical trace, the harder to detect**. Let us plot the three quantities vs p with the real formulas - then you see the matrix-coding trade-off.

![Fig. 4-2 embedding efficiency](../assets/f5_efficiency.png)

*Fig. 4-2 (real computation: as p grows - ① capacity per pixel p/(2ᵖ−1) drops; ② average change rate (1−2⁻ᵖ)/(2ᵖ−1) drops sharply; ③ bits carried per change (embedding efficiency) p/(1−2⁻ᵖ) rises. Dashed lines are the naive-LSB baseline: capacity 1, change rate 0.5, efficiency 1)*

**Reading the figure**:
- **Change rate** (②) directly measures "trace": the larger p, the fewer pixels changed to hide the same message, the harder statistical detection catches it;
- **Efficiency** (③) measures "value per change": p=3 is ~3.43 bits/change, over 3x naive LSB;
- **Cost** (①): the larger p, the smaller per-pixel capacity; hiding the same message needs a larger carrier.

Put them on one "capacity vs change-rate" trade-off plot and the trade-off is obvious:

![Fig. 4-3 capacity-change-rate tradeoff](../assets/f5_tradeoff.png)

*Fig. 4-3 (real computation: blue line is matrix coding at different p (capacity on x-axis, change rate on y-axis); red dashed line is naive LSB. The whole matrix-coding curve sits much lower - **at the same change rate it hides more, or at the same capacity it changes less and leaves a smaller trace**. That is why nsF5 in Chapter 5 insists on matrix embedding)*

> **Tip |** Steganography performance is usually measured by two things: **capacity** (how much) and **distortion/change rate** (how detectable). Matrix embedding's meaning is to **raise capacity at the same distortion, or lower distortion at the same capacity**. This "change less = safer" idea runs through the nsF5 of Chapter 5 and the detection of Chapter 8.

## 4.5 F5: Matrix Embedding + JPEG Coefficient Decrement

F5 (Westfeld) is a JPEG steganographic scheme: it does matrix embedding on quantized DCT AC coefficients. Changing a "bit" is not an LSB flip but reducing the coefficient's **absolute value by 1** (e.g. +3→+2, −5→−4), which both flips the LSB parity and avoids obvious statistical anomalies.

The problem is "shrinkage": when a coefficient with absolute value 1 is decremented, it becomes 0. A 0 coefficient in JPEG decoding means "no such frequency component", so F5 treats it as no longer a legal carrier, drops the block, and retries later message bits. **Shrinkage** reduces the actual payload, lowers the achieved efficiency below the theory, and leaves a detectable statistical feature.

## 4.6 Back to the Project: MatrixEmbedding

> **Back to the code |** Open the `MatrixEmbedding` class in `src/ns5_core.py`: `_embed()` is literally the 4.2/4.3 steps - compute s, compare m, find the column, flip. Fig. 4-1/4-2/4-3 are the visualizations of the math behind that code.

*MatrixEmbedding._embed() core (real code excerpt)*

```python
xl = (c[pos] & 1).astype(np.uint8)     # take block LSBs
s  = syndrome(H, xl)                     # s = H·x
if np.array_equal(s, m): continue        # exactly matched, no change
d = (s ^ m).astype(np.uint8)             # difference
col = int(np.where(np.all(H == d[:, None], axis=0))[0][0])
c[pos[col]] ^= 1                         # flip the matched pixel
```

> **Back to the code |** `src/efficiency.py`'s `plot_code_family_and_efficiency()` also draws the code family and efficiency plot (saved to `output/efficiency.png`), cross-checkable with Fig. 4-2.

## 4.7 Summary and Self-Check

- Matrix embedding works in blocks: n positions carry p bits, at most 1 change (Fig. 4-1);
- Distinct H columns ⇒ any syndrome difference locates the unique pixel to flip;
- Embedding efficiency α=p·2ᵖ/(2ᵖ−1), rising with p but block length grows too (Fig. 4-2);
- **Capacity-change-rate trade-off**: the fewer changes, the harder to detect (Fig. 4-3) - the fundamental answer to "why matrix coding";
- F5 embeds by decrementing JPEG coefficients; shrinkage occurs when |coefficient|=1 becomes 0.

> **Think about it |** If F5 skips and retries on shrinkage, can the message still decode correctly? How does the decoder know which blocks were skipped? Do not worry if stuck - Chapter 5's nsF5 uses wet-paper coding to sidestep this entirely. One layer deeper: using Fig. 4-3, if I want to hide only 0.2 bit/pixel, how low can matrix coding push the change rate (versus naive LSB's ~0.1)? That directly sets how hard steganalytic detection is.