1. F3

嵌入域是JPEG的量化DCT系数，为了避免直接采用LSBR带来的值对接近现象，在嵌入方法上它采取了以下措施

关键点：

• 当需要修改时，绝对值降低 $1$，所以绝对值为 $1$ 的系数也会被使用
• 当绝对值为 $1$ 的系数修改为0时，由于提取算法不能区分这个 $0$ 值的产生方式，所有嵌入算法需要继续嵌入，直到找到一个偶数或者将一个奇数的绝对值修改为非零偶数

优劣：

• 改动抵御了 $\chi^2$ 攻击。
• 使得偶数的数量增加，由于产生成 $0$ 时还需要继续嵌入，直到找到一个偶数或者将一个奇数的绝对值修改为非零偶数，会相对于一般的变动额外增加偶数。

2. F4

在F3上进行修改

关键点：

• F4针对不同符号、不同奇偶性的系统采用了不同的嵌入与消息表示方法，避免了偶数增加现象。负偶数、正奇数代表比特1，负奇数、正偶数代表比特0。

优劣：

• 维持了单调性和梯度递减性
• 保证了对称性

3. 纠错码

以 $(7,4)$ 纠错码为例，$n=7,k=4$。

• 有生成矩阵 $G_{k\times n}$，校检矩阵 $H_{(n-k)\times n}$，其符合 $GH^\mathrm{T}=0$。
• 设信息组 $m=(m_1\cdots m_k)^\mathrm{T}$，则产生的码字为$C=G^\mathrm{T}m$，且 $HC=0$。
• 在译码时，$(7,4)$ 纠错码具有纠错 $1$ 位的能力，设得到的码字为 $r$ ，$S=Hr=H(C+e)=0+He=He$

标准阵码表：

4. 矩阵编码

其负载为每 $n$ 个比特嵌入 $n-k$ 个比特。利用纠错码的思想使传递的消息在最小的代价下修改为 $Hr$。 假设嵌入的前 $n$ 个比特为 $m$，$Hm$ 将计算出校检子 $C$，$C$ 有 $2^{n-k}$ 种情况，当 $C$ 与消息 $S$ 不同时，通过纠错码的思想，可以在 $m$ 上修改最小的比特使得 $Hm$ 的结果为目标嵌入消息 $S$。

在《Matrix Embedding For Large Payloads》论文中描述了两种矩阵编码的算法，一种基于Random Linear Codes，另外一种基于 Simplex Codes 。

Random Linear Codes

• 在该码下在隐写时可以达到最高的嵌入效率，但是缺乏一种快速的信息嵌入方法。
• 对于嵌入慢这个特性，主要是由于基于矩阵编码的思想，需要修改 cover 中原来的信息比特 $m$，使得 $Hr$ 的结果为目标嵌入消息 $S$，但是在随机线性码的情况下，只能遍历所有符合要求的修改方式，才能找到代价最小的修改方式使 $m$ 修改为 $r$。(具体分析待补充)

$Algorithm 1:$ 在 $N$ 个元素的载体中嵌入 $M$ 个比特使用随机线性码

• (1) 为了在$N$ 个元素中嵌入 $M$ 个比特，首先需要找到一个 $n$，其符合 $a_n\ge M/N>a_{n-1}$
• (2) 读取载体接下来的 $n$ 个比特 $x$，并且获取接下来的 $n-k$ 个消息比特 $m$
• (3) 找到任意的码字 $e$ 其满足 $He = m -Hx$
• (4) 枚举出所有 $2^k$ 种有效码字，找到与 $e$ 最接近的有效码字 $c(e)$
• (5) [嵌入过程] 将 $x$ 修改为 $x+e-c(e)$ 完成嵌入
• (6) 如果消息比特还没有提取完，跳转至步骤 $1$ 继续嵌入，否则嵌入完成
• (7) [提取过程] 每次从载体中提出 $n$ 个比特 $x$，计算 $Hx$ 从而不断顺序提取出信息

Simplex Codes

• 基于该码的矩阵编码负载率稍微低于 Random Linear Codes，但在计算复杂度上其为 $O(n\log n)$。

$Algorithm 2:$ 在 $N$ 个元素的载体中嵌入 $M$ 个比特使用随机单纯码

• (1) 为了在$N$ 个元素中嵌入 $M$ 个比特，首先需要找到一个 $q$，其符合 $(2^q-q-1)/(2^q-1)\ge M/N>(2^{q-1}-q)/(2^{q-1}-1)$
• (2) 读取载体接下来的 $2^q-1$ 个比特 $x$，并且获取接下来的 $2^q-1-q$ 个消息比特 $m$
• (3) 找到所有的码字 $e$ 其满足 $He = m - Hx$，可以使用高斯消元
• (4) 令 $\hat e = (0,e_1,…,e_{2^q-1})$，计算 $E=1-2\hat eH_{2^q}$，使用阿达马变换。
• (5) $E_{i_0} = \max \lbrace E_1,…,E_{2^q}\rbrace$，$u =i_0-1$ 的二进制展开式子
• (6) 最近的码字 $e = c(e) =\sum_{i=1}^q u_i v_i^t$，$v_i$ 是生成式 $G$ 的第 $i$ 行
• (7) [嵌入过程] 将 $x$ 修改为 $x+e-c(e)$ 完成嵌入
• (8) 如果消息比特还没有提取完，跳转至步骤 $1$ 继续嵌入，否则嵌入完成
• (9) [提取过程] 每次从载体中提出 $n$ 个比特 $x$，计算 $Hx$ 从而不断顺序提取出信息

5. F5

F5实现了基于海明码的矩阵编码隐写在一个分组上最多修改一次，基本修改方法基于F4。

F5 方法在 JPEG 图片上的大致嵌入过程如下：

1. 开始 JPEG 压缩，在系数量化后进行嵌入
2. 基于密钥和系数数量生成固定序列在子空间中置乱系数位置从而进行加密
3. 根据载体的容量和秘密消息的长度确定参数$k$
4. 计算码字的长度 $n = 2^k − 1$
5. 使用 $(1, n, k)$ 矩阵编码嵌入秘密消息
   (a) 用 $n$ 个非零系数填充缓冲区
   (b) 散列这个缓冲区，生成一个具有 $k$ 位的散列值。
   (c) 将消息的下 $k$ 位与散列值进行异或计算
   (d) 如果总和为 $0$，则缓冲区保持不变。否则总和是缓冲区的索引 $1…n$，其对应的位置进行相应修改，同F4修改策略
   (e) 如过生成零，调整缓冲区（通过再读取一个非零系数来消除 0，即从相同的系数开始重复步骤 5(a)。如果没有生成零，前进到实际缓冲区后面的新系数。如果仍有消息数据，则继续执行步骤 6(a)
6. 继续 JPEG 压缩（霍夫曼编码等）

现将F5方法具体的比特嵌入部分转化为一般步骤进行描述：

$Algorithm 3:$ 在 $N$ 个元素的载体中嵌入 $M$ 个比特基于F5方法

• (1) 为了在$N$ 个元素中嵌入 $M$ 个比特，首先需要找到合适的 $n,k$，其满足 $2^k=n-1,(n-k)/n\ge M/N$
• (2) 读取载体接下来的 $n$ 个比特 $x=x_1…x_n$，并且获取接下来的 $n-k$ 个消息比特 $m$
• (3) 令$\hat x =1x_1\oplus2x_2\oplus \cdots \oplus nx_n$，计算 $p =\hat x \oplus m $
• (4) [嵌入过程] 若 $p$ 为0，则无需修改，否则将 $x$ 的第 $p$ 个比特 $x_p$ 修改为 $\lnot {x_p}$
• (5) 如果消息比特还没有提取完，跳转至步骤 $1$ 继续嵌入，否则嵌入完成
• (6) [提取过程] 每次从载体中提出 $n$ 个比特 $x$，计算 $m =1x_1\oplus2x_2\oplus \cdots \oplus nx_n$ 从而不断顺序提取出信息

6. MME

扰动计算

修改的矩阵编码方法基于 F5 方法。虽然F5方法保证了嵌入时每 $n$ 个比特最多修改一次，但是更细致的角度考虑，修改多次的扰动并不一定大，下面进行解释。

• 设 $C$ 和 $C’$ 分别为 DCT 系数取整前后的值， $R$ 为取整造成的误差，则有 $C=(c_1,c_2,\cdots,c_l), C’=(c_1’,c_2’,\cdots,c_l’), R=C’-C=(r_1,r_2,\cdots,r_l),r_i\in (-0.5,0.5)$

• 在F5方法下所有的操作都只可能将 $C’$ 加减 $1$，则扰动可能为 $1\pm\mid r_i\mid$，显然 $1+r_i$ 有可能大于 $2-r_j-r_k$

在MME方法中，与F5嵌入的方式稍有不同其有四种不同的分布及处理情况，变化策略如图:

将需要对一个系数的 $LSB(c_i)$ 进行修改时，可以得出对不同情况下造成的实际扰动如下($c_i$ 与 $p$ 点的距离)：

相对扰动 $s_i$ 如下($c_i$ 与 $p$ 点的距离减去$c_i$ 与 $c_i’$ 点的距离)

修改方法

1. 同F5方法，在嵌入时候求得 $\hat x =1x_1\oplus2x_2\oplus \cdots \oplus nx_n$，再计算 $p =\hat x \oplus m $，便可以找到需要修改的位置，通过修改该位置，便可以成功潜入消息。
2. 但是通过在前面的分析，修改一个位置虽然次数最少，但是造成的扰动不一定最少。由此，或许可以修改多个位置达到和修改该特定位置达到同样的嵌入效果，并能使得扰动更小。
3. 由于该位置是异或计算得出，显然可以由其它位置异或得到，比如$7=1\oplus6=2\oplus5=1\oplus2\oplus4$等。即实际使用该方法时，可以限制取值的数量，随后遍历每一种情况从而达到最低扰动下的修改修改方案。

下面给出MME比特嵌入部分转化为一般步骤进行描述：

$Algorithm 4:$ 在 $N$ 个元素的载体中嵌入 $M$ 个比特基于F5方法

• (1) 为了在$N$ 个元素中嵌入 $M$ 个比特，首先需要找到合适的 $n,k$，其满足 $2^k=n-1,(n-k)/n\ge M/N$，并选取最大修改次数 $C$
• (2) 读取载体接下来的 $n$ 个比特 $x=x_1…x_n$，并且获取接下来的 $n-k$ 个消息比特 $m$
• (3) 计算出每个比特的修改扰动代价$S=\lbrace s_1,s_2,\cdots,s_n \rbrace$
• (3) 令$\hat x =1x_1\oplus2x_2\oplus \cdots \oplus nx_n$，计算 $p =\hat x \oplus m $
• (4) 当 $p$ 不为0时，找出所有从 $n$ 个位置中选取 $t(t<=C)$个不同的位置，且其编号异或和恰好等于 $p$ 的情况，计算每种情况的扰动值 $s$，找到扰动值最小的位置编号集合 $P=\lbrace p_0,p_1,…,p_k\rbrace$
• (5) [嵌入过程] 若 $p$ 为0，则无需修改，否则将 $x$ 所有在 $P$ 集合中的位置的比特 $x_{p_i}$ 修改为 $\lnot {x_{p_i}}$
• (6) 如果消息比特还没有提取完，跳转至步骤 $1$ 继续嵌入，否则嵌入完成
• (7) [提取过程] 每次从载体中提出 $n$ 个比特 $x$，计算 $m =1x_1\oplus2x_2\oplus \cdots \oplus nx_n$，从而不断顺序提取出信息