0 引言

信息隐藏^[1-2]主要是以数字媒体作为掩护，数字隐写技术旨在以诸如图像、音频、视频或者文本^[3]等数字媒体作为载体，把机密数据隐藏到数字媒体中。在利用无失真图像作载体的情况下，隐藏的数据不会改变载体的视觉效果，而且也不会改变载体的存储大小和格式，因而使用安全性高的数字隐写算法隐写图像能够在开放的网络环境中安全传输，不会泄露隐藏的秘密信息。为了更好地提高信息隐藏的安全性，如今隐写术经常与密码学结合或者针对隐写分析^[4]提出有效的隐写方法以达到较高的安全性，同时隐写术和密码学的结合与隐写分析也是当前信息安全^[5-7]比较关注的话题。

最简单且经典的隐写算法是最低有效位(Least Significant Bit, LSB)替换，该方法由于存在统计不对称的缺点，很容易被检测出隐藏的信息^[8]。这是因为LSB替换仅存在2m和2m+1之间的转换，破坏了图像最低有效位均匀随机分布的结构。同时仅仅存在2m和2m+1之间的转换，而没有2m和2m-1之间的转换，导致了成对灰度值的像素数趋于相等的现象。避免LSB替换算法带来的统计异常问题的最简单的方法是LSB匹配算法^[9]：当嵌入的比特与像素值的最低有效位不等时采取随机±1，相等时不作改变。最后载体中数值+1与－1的两种情况等概率出现，统计不对称也就不复存在。

在LSB的基础上，Chan等^[10]在2004年提出了改进的LSB算法，即最佳像素调整过程(Optimal Pixel Adjustment Process, OPAP)，在替换最低有效位数相同时，OPAP本身不会增加隐藏容量，而是在LSB替换的基础上去减少失真，但是随着替换r位的数量增加，图像表现的失真会变大。2006年，由Mielikainen^[11]提出的像素对匹配(Pair Pixel Matching, PPM)方法，主要是通过像素对为嵌入单元隐藏二进制信息，其思想是嵌入的单元不再是像素点而是像素组。同一年，Zhang等^[12]提出了利用修改方向(Exploiting Modification Direction, EMD)算法，在保证图像的感知度的前提下，EMD使用了N进制系统。在此基础上Chao等^[13]于2009年提出了钻石编码(Diamond Encoding, DE)的编码机制，以k值的大小控制编码。该方法在选择较小k值时能够达到较小的失真，提高了图像的视觉质量，但是过大的k值会影响图像质量。在2012年，Hong等^[14]提出了自适应像素对匹配(Adaptive Pixel Pair Matching, APPM)隐写算法，该算法与DE算法相比扩充了进制编码系统，信息的编码不再受限于k值的选择。根据图像的特征，先后出现了基于图像边缘像素的信息隐藏算法^[15-16]。因为鉴别图像边缘像素点的变化不容易，且图像边缘承载大量信息难以检测，所以在边缘区域隐藏秘密信息是一个较好的选择^[17]，使得图像隐写从秘密信息编码邻域转换到选择图像像素点进行嵌入的邻域。

代数多重网格的概念是Brandt等^[18]提出的。最早，代数多重网格组元的构造仅仅依靠问题方程的系数矩阵，根据系数矩阵内部结构的分析进行优化迭代，为求解偏微分方程提供了一个比较迅速的解决方案。因为代数多重网格方法只跟矩阵内部结构有关，所以将其应用于图像去噪、图像分割等，但主要还是通过求解图像邻域中的偏微分方程来处理相关应用^[19-20]。代数多重网格方法能描述矩阵的内部结构，因此可用来提取图像的内部特性，通过代数多重网格方法将图像分成粗网格和细网格两部分，进行图像融合、特征检测以及清晰度评价^[21-22]。

目前大部分算法是以图像的像素组作为一个单元进行嵌入，诸如PPM、EMD、DE与APPM等算法，近几年出现了基于图像特征进行嵌入的隐写算法，比较典型的如Islam等^[23]在2014年提出的Canny边缘检测的自适应隐写算法。代数多重网格方法能反映图像的特性，提取的粗网格能反映图像中变化剧烈的区域，而细网格反映图像中变化平缓的区域。因此将代数多重网格方法用于图像像素点的选取，本文提出了结合代数多重网格的钻石编码隐写算法。该算法使用代数多重网格将图像分成两个部分分别嵌入不同比率的秘密信息，其中区域特征变化大的点嵌入率大，而特征变化小的点嵌入率小，因此该方法能在保持相同嵌入容量的基础上提高安全性。

1 理论基础 1.1 钻石编码

钻石编码结合了PPM与EMD两个算法的特点，前者以两个像素点为单位进行数据隐藏，后者对具体的秘密信息编码。钻石编码最重要的部分是它的编码，也就是邻近位置的设置。假设待嵌入秘密信息像素对为(p, q)，钻石编码模型中的像素对为(a, b)，编码模型获取函数为S_k(p, q)，模型计算式如下：

$ {S_k}\left( {p, q} \right) = \left\{ {\left( {a, b} \right)|\left| {a-p} \right| + \left| {b-q} \right| \leqslant k} \right\} $

(1)

根据k值的变化，编码模型S_k的个数也在变化，其个数计算式为l=2k²+2k+1，每一个模型S_k均对应着一个模型顺序编排D_k。信息隐藏必须要能还原原始信息，钻石编码是通过钻石特征值(Diamond Characteristic Value, DCV)^[7]来嵌入信息，同样也根据DCV来还原信息。DCV的计算式如下：

$ DCV = f(p, q) = \left( {\left( {2k + 1} \right) \times p + q} \right)od l $

(2)

设编码的秘密信息为s_t，嵌入信息的时候，通过对s_t与DCV之差进行模l运算得到d_t，在D_k中查找值等于d_t的对应位置，再在S_k中查找对应位置的(p±n, q±m)序列值，以达到秘密信息的嵌入。距离的计算式如下：

$ {d_t} = \left( {{s_t}-f\left( {p, q} \right)} \right)od l $

(3)

1.2 代数多重网格

AMG方法的目标是求解离散域Γ₀上的问题:

$ {\boldsymbol{AU}} = {\boldsymbol{F}}; {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{j = 1}^n {{a_i}_j{u_j}} = {f_i}(i = 1, 2, ..., n) $

(4)

其中：A=(a_ij)_n*n，U=(u₁, u₂, …, u_n)^T，F=(f₁, f₂, …, f_n)^T。AMG方法将离散域Γ_m分为粗网格C_m+1和细网格F_m+1，粗网格的选择方法具有一定的规则^[24]，并且Γ_m=C_m+1+F_m+1=C_m+1+Γ_m+1。在Γ_m上，可以得到较小的代数方程组:

$ {\boldsymbol{AU}} = {\boldsymbol{F}}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{j = 1}^n {{a_i}_j{u_j}} = {f_i}(i = 1, 2, ..., n) $

(5)

其中：m=1, 2, …, M; n=n₁>n₂>…>n_M; A¹=A，U¹=U，F¹=F。

AMG方法具体思路是先在网格Γ_m上作松弛迭代，然后将误差投影到粗一层的网格Γ_m+1上，在粗网格上又作松弛迭代，继续平滑相应的高频部分。依此类推，直到最粗的一层网格Γ_m。在Γ_m上用直接法求解A^mU^m=F^m，然后用插值算子将所求得的误差返回到细网格，用以修正原有结果，直到最细的一层网格Γ₀。图 1是代数多重网格的大致流程。

AMG算法主要有两个部分：预处理与迭代循环。预处理是从描述问题的方程组的系数矩阵构造出AMG的五个分量：网格点集Γ_m，插值算子Ο_m+1^m，限制算子Ο_m^m+1，粗网格算子C_m+1以及光滑算子S_m。

1) 粗网格序列Γ^m，也就是未知数μ_j^m(1≤j≤n_m)的集合，是已知矩阵有关的有向图节点的虚构网络；定义最细网格Γ₀，构造网格序列满足Γ_n⊂Γ_n-1⊂…⊂Γ_k⊂…⊂Γ₀。

2)S_m，S(Γ^m)在Γ_m上的光滑算子。

3) 限制算子Ο_m^m+1，S(Γ^m)→S(Γ^m+1)。

4) 插值算子Ο_m+1^m，S(Γ^m+1)→S(Γ^m)。

5) 粗网格算子C_m+1，系数矩阵序列。

其中限制算子与插值算子满足以下条件：

Ο_m^m+1=(Ο_m+1^m)^T

C_m+1=Ο_m^m+1C_mΟ_m+1^m

图 2是通过代数多重网格后的Lena图，白色代表粗网格，黑色代表细网格。

1.3 隐写指标

一个隐写系统两个重要指标是感知度与安全性，本文采用峰值信噪比(Peak Signal to Noise Ratio, PSNR)与图像结构相似性(Structural Similarity Index, SSIM)^[25]来评价隐写的感知度，使用Markov链模型安全评估指标评价安全性。

PSNR是衡量图像感知失真度的常用指标之一，通过载密图像与原始图像相同位置的像素值计算获得PSNR值。如果获得的PSNR值在38 dB以上，人眼一般不能有效地察觉载密图像与原始图像的区别^[26]。对安全性而言，Sullivan等^[27]提出了采用Markov链(Markov Chain, MC)模型的安全性检测指标。通过对图像按列或者行的形式扫描得到数据链X，Sullivan等^[27]提出数据链中当前像素点的值x_t仅与其在链中的前一个像素点值x_t－1有关，x_t和x_t－1的关系为P(x_t|x_t－1, x_t－2, …, x₁)=P(x_t|x_t－1)。设图像像素值为i与j，E为i变化到j集合，记为〈i, j〉∈E，也就是记录所有像素值从i变到j出现的次数就可以得到载体图像MC模型的经验矩阵。设原始图像为C，载密图像为S，定义原始图像与载密图像对应的经验矩阵分别为M^C与M^S，m^C与m^S分别是对应经验矩阵的元素，则原始图像与载密图像统计分布的距离测度定义为：

$ D({{\boldsymbol{M}}^{\boldsymbol{C}}},{{\boldsymbol{M}}^{\boldsymbol{S}}}) = \sum\limits_{\left\langle {i,j} \right\rangle \in \boldsymbol{E}} {\left[ {m_{ij}^C\lg \left( {\frac{{m_{ij}^C}}{{\sum\limits_j {m_{ij}^C} }}\frac{{\sum\limits_j {m_{ij}^S} }}{{m_{ij}^S}}} \right)} \right]} $

(6)

2 本文算法

首先通过AMG方法把图像分成两类像素点，粗网格部分的像素值能够承载的改变量较大，细网格部分的像素值则相反。因此在粗网格部分嵌入信息较多，细网格部分嵌入较少。为了减少载密图像的失真度，本文选择k为1与2进行编码嵌入，过程如图 3所示。

2.1 嵌入过程

通过图像粗细网格特征像素点的提取，得到粗网格和细网格的像素点序列，把秘密信息按一定的比例分成两个部分以钻石编码的方式分别嵌入到提取的像素点中。其中选择一幅大小为m×n的彩色图像I，通过某种加密机制得到的秘密信息二进制流为S。嵌入过程主要步骤如下：

步骤一  用AMG方法提取粗细网格像素点。首先调用AMG方法，选择图像R、G、B的其中一个通道作为基准，保持这个通道像素值不变，把图像I的其他两个通道像素值分成粗网格和细网格两类，分别是P_C与P_F，粗网格特征的像素点用1表示，细网格特征的像素点用0表示，得到网格化的灰度图像。由0与1在图像中的不同位置得到粗网格像素点组成的序列为c₁c₂…c_n，则P_C=c₁c₂…c_n，细网格像素点组成的序列为f₁f₂…f_n，则P_F=f₁f₂…f_n。

步骤二  钻石编码k值选择与信息编码。k值的选择按照细网格不大于粗网格的原则进行，即k_C≥k_F，其中k_F为细网格中选择的k值，k_C为粗网格中选择的k值。如果$\left\lfloor {{L_C} \times {{\log }_{\text{2}}}(2k_C^2 + 2{k_C} + 1)/2} \right\rfloor \geqslant \left| {\boldsymbol{S}} \right| $，只需要嵌入粗网格像素，细网格像素不改变。如果$\left\lfloor {{L_C} \times {{\log }_2}(2k_C^2 + 2{k_C} + 1)/2} \right\rfloor < \left| {\boldsymbol{S}} \right| $，那么需要把S切成两部分，首先保证粗网格像素的嵌入，进而对细网格像素进行嵌入处理。根据选择的k值用公式l=2k²+2k+1计算出N元进制系统的长度，然后按照N元进制系统的长度进行编码，在编码时需要对二进制流S进行切片，最后得到编码信息序列S_N，在$ \left\lfloor {{L_C} \times {{\log }_2}(2k_C^2 + 2{k_C} + 1)/2} \right\rfloor < \left| {\boldsymbol{S}} \right|$情况下，通过不同的N元进制系统的长度获得粗网格与细网格编码序列分别为S_N^C与S_N^F，编码后的每一位数值需要一个像素对进行嵌入。由以上的规则最后把整个S_N嵌入像素对中。要保证秘密信息完全嵌入，需要满足以下条件:

$ \begin{gathered} \left\lfloor {\frac{{{L_C} \times {{\log }_2}(2k_C^2 + 2{k_C} + 1)}}{2}} \right\rfloor + \hfill \\ \left\lfloor {\frac{{{L_F} \times {{\log }_2}(2k_F^2 + 2{k_F} + 1)}}{2}} \right\rfloor \geqslant \left| {\boldsymbol{S}} \right| \hfill \\ \end{gathered} $

其中：L_C与L_F分别是粗网格与细网格像素点的个数；|S|为二进制序列长度。

步骤三  S_N编码序列、k_C和|S_N^C|、k_F和|S_N^F|的嵌入。根据文献[7]，信息的嵌入首先需要计算出待嵌入像素对的钻石特征值，可通过式(2) 获得。DCV的计算依赖于N元进制系统的长度l，粗细网格的l根据选择的k值计算。然后用待嵌入的一位编码序列通过式(3) 计算与DCV的距离d_t，再根据d_t确定其在D_k的位置，每一个钻石编码模型S_k对应着一个距离模式D_k，通过这个过程嵌入S_N的所有编码序列。最后把k_C和|S_N^C|以及k_F和|S_N^F|嵌入到粗细网格像素点特殊位置，如此完成整个嵌入过程。

假设嵌入参数k=2，像素对的值为(158, 156)，则l=13，x=158，y=156，通过式(2) 计算DCV: f(158, 156)=(158×5+156) mod 13=10。现在将13进制的秘密信息s_t=8₍₁₃₎嵌入像素对中，首先用式(3) 计算距离得到d_t=(8－10) mod 13=11，然后用d_t的值参照S₂模型进行改变像素对的值，当k=2时编码模型S₂与距离模式D₂如图 4所示，最后嵌入信息的像素对变为(158, 154)。

步骤四  嵌入溢出处理过程。在改变像素对值时可能出现上下溢出的情况，假设未嵌入信息的像素对为(x, y)，通过钻石编码嵌入信息溢出的像素对为(x′, y′)，则溢出处理如下：

x′=x′+l, y′=y′+l; x′, y′ < 0

x′=x′－l, y′=y′－l; x′, y′>255

通过步骤一到四，完成秘密信息流S嵌入图像I得到载密图I′。在嵌入秘密信息的同时也嵌入k_C和|S_N^C|、k_F和|S_N^F|，以保证信息能够提取。

2.2 提取过程

提取粗细网格像素点，用钻石编码的特征公式提取编码的信息序列，再由编码序列与加密密钥还原秘密信息二进制流。提取过程的主要步骤如下：

步骤一  AMG方法提取粗细网格像素点。此步骤和嵌入过程大体一致，由保持不变的通道像素点用AMG把其余两个通道像素分成两类，分别提取两个通道对应粗细网格位置的像素值。

步骤二  提取k_C和|S_N^C|、k_F和|S_N^F|。在粗细网格特定位置提取k_C和|S_N^C|与k_F和|S_N^F|，用长度|S_N^C|与|S_N^F|计算嵌入信息的像素点个数为2|S_N^C|与2|S_N^F|，最后得到粗细网格嵌入秘密信息的两类像素点分别是P′_C与P′_F。

步骤三  秘密信息的提取。把获取的两类像素点P′_C与P′_F按顺序重新组合成像素对，然后利用DCV公式进行信息的提取。设承载秘密信息的像素对为(x′, y′)，那么获得秘密信息s=f(x′, y′)=((2k+1)x′+y′)mod l，l=2k²+2k+1，其中粗细网格中的k值由步骤二获得。通过DCV公式获取的序列分成两部分，粗网格部分为S_N^C，细网格部分为S_N^F，再根据粗细网格不同的l值，也就是l进制系统与二进制的转换，把S_N^C与S_N^F还原成二进制流，分别得到S^C与S^F，最后二进制序列为S=S^C+S^F。根据得到的二进制序列，通过加密的密码机制解密还原秘密信息。

在嵌入过程中得到嵌入机密信息的像素对为(158, 154)，k值与l同嵌入过程的选择相同，提取的时候需要通过嵌入机密信息的像素中提取，然后通过式(2) 计算DCV：f(158, 154)=(158×5+154) mod 13=8，得到的13进制8₍₁₃₎即为嵌入过程中嵌入的s_t，也就提取出了机密信息。

3 实验结果及分析 3.1 图像感知度分析

通过峰值信噪比与图像结构相似性对隐写图像感知方面的分析，首先采用USC-SIPI标准图库^[28]中的Lena图在1 bpp(bit /pixel)的情况下进行图像感知度实验，也就是AMG结合DE隐写算法的感知度实验，本文简称AMGDE。在保证图像质量的情况下，AMGDE方法与DE方法中的k值都取1或者2，根据k_C≥k_F的条件，则AMGDE方法嵌入可以分成三种情况：k_C=1, k_F=1，用AMGDE11表示；k_C=2, k_F=1，用AMGDE21表示；k_C=2, k_F=2，用AMGDE22表示。DE方法分成两种情况：k=1时，用DE1表示；k=2，用DE2表示。最后得到隐写图像感知度实验结果如图 5所示。

由图 5可知，三种隐写方案都具有较高的PSNR，视觉上无法感知其中隐藏了信息，人眼能够察觉两幅图像变化的PSNR值为38 dB。

为了进一步验证算法在感知度方面的优势，选取了USC-SIPI中的10张图像在1 bpp嵌入率下，得到LSB替换(Least Significant Bit Replacement, LSBR)、随机LSB匹配(Least Significant Bit Matching, LSBM)、钻石编码(DE)、自适应的Canny边缘检测隐写算法(CANNYLSB)与AMGDE方法的SSIM值实验结果，如表 1所示。

从表 1中可以看出，当嵌入过程中的k值选择与原钻石编码k值相同时，AMGDE方法的SSIM值与DE方法完全一致，而AMGDE21的SSIM值正好介于AMGDE11与AMGDE22之间。同时与CANNYLSB相比，AMGDE方法的三种方案的SSIM值很明显大于CANNYLSB，由于CANNYLSB隐藏信息时替换最低有效的低两位二进制，因此CANNYLSB隐写算法更加适合小容量的嵌入^[23]。

3.2 图像安全性分析

本文采用式(6) 即一阶Markov安全测度值来评价隐写算法的安全性，该值越小安全性越高^[26]。采用图库为UCID.V2^[29]中的1 338张图像，将本文算法实验结果与LSBR、LSBM、DE与CANNYLSB进行比较。对每一张图片都进行多种方法嵌入，计算各种方法的安全指标值，统计AMGDE方法优于其他方法的图片个数占整个图库的比例进行结果比较。假设AMGDE方法优于其他方法图片数目为P_c，整个图库的图片数目用P_t表示，那么R=P_c/P_t×100%即为AMGDE方法优于其他方法的图片数目占整个图库的百分比。

根据文献[13]，因为钻石编码随着k值的增大，在同等嵌入率的情况下，整个图像像素值需要改变的个数减少，然而像素值的改变量增大，于是载密图像的安全性提高，但图像的感知度变差。所以，AMGDE11与DE2相比，同等嵌入率下，DE2改变原图像像素值的个数肯定小于AMGDE11，AMGDE21除去粗网格像素嵌入方式与DE2相同外，在细网格部分，DE2像素值改变个数也肯定小于AMGDE21，同理DE2像素值改变的个数也小于AMGDE21，也就是AMGDE11与AMGDE21安全性上都低于DE2。故AMGDE11与AMGDE21作比较实验时，只针对LSB、DE1、CANNYLSB作比较，而AMGDE22针对LSB、DE1、DE2、CANNYLSB作比较，统计AMGDE11、AMGDE21、AMGDE2优于其他比较方法的图片个数占整个图库的比例，在一阶Markov安全测度统计情况下，结果比较分别如表 2~4所示。

由表 2~4可知，在嵌入率较大的情况下，表中AMGDE方法优于其他方法的比例可以达到75%以上，也就是AMGDE方法的整体安全性较好。在嵌入率为0.2 bpp时，AMGDE21比AMGDE11的比例出现较大的增加。在AMGDE21方法中，粗网格中的嵌入率比细网格中的嵌入率高，说明在粗网格嵌入时能更好地抵制隐写分析，提高安全性。嵌入率为0.2 bpp时，嵌入的信息都在粗网格中，所以AMGDE21与AMGDE22中得到的结果都相同。在嵌入率为0.8 bpp和1.0 bpp时，AMGDE22相比对应的DE2方法，在一阶Markov安全测度统计情况下其比率超过了75%。与自适应边缘检测算法CANNYLSB相比，本文提出的三种方案在1 338张图下的隐写效果优于CANNYLSB算法，由于CANNYLSB是根据嵌入的秘密信息长度来确定边缘检测像素点的，因此每次边缘检测的像素点是随机分布的，嵌入率的增加使一阶Markov安全指标值的变化有一些突变，但整体优越效果明显，特别是AMGDE22的时候安全指标值稳定性较好，也说明AMGDE在大容量时优点较为明显。

从理论上来看，当嵌入率较小的时候，AMGDE方法嵌入点较为分散，嵌入点相互之间没有邻域关系，因此被检测出来的概率较高，而其他方法都是顺序嵌入，嵌入点之间存在邻域关系，所以被检测出来的概率较低。随着嵌入率提高，AMGDE方法嵌入点之间存在较多邻域关系，但是粗网格中对应点灰度变化较大，细网格中对应点灰度变化较小，因此在粗网格中检测出的概率大大降低，所以整个检测率降低。

为了更深入地分析，针对USC-SIPI标准图库中的Baboon与Yacht图像在不同嵌入率下进行一阶Markov安全指标值分析，得到安全指标随嵌入率变化的结果如图 6所示。

从图 6中可以看出，AMGDE方法在嵌入率线性增加的时候能保持比较稳定的变化，也可进一步验证AMGDE方法在大容量信息嵌入的优越性。

4 结语

结合AMG方法的钻石编码方法从一定程度上提高了原始钻石编码的安全性。AMG方法能根据图像的特征在不同区域嵌入不同比率的秘密信息，能保证在感知度和图像安全性较高的同时提高图像的嵌入容量。本文方法的PSNR都高于38 dB，视觉上无法发现载密图像是否嵌入了秘密信息，同时其SSIM与DE保持一致。从安全性上来看，AMGDE方法更适合于大容量秘密信息的嵌入。因此根据图像特征来进行秘密信息的嵌入是一种提高嵌入容量的有效方法，后续研究将对图像区域进行细化，根据机密信息获取AMG的不同层次进行更为细致的嵌入容量分配，进一步提高承载机密图像的嵌入容量和安全性。