一元二次方程插值空间大容量可逆信息隐藏

咸雯雯，张芷瑜，孙旖涔，石 慧，黄 丹

（辽宁师范大学计算机与信息技术学院，辽宁大连 116029）

可逆信息隐藏自诞生之初，便得到学者们的广泛关注。该技术在嵌入秘密信息后可无损恢复秘密信息和载体图像，以往传统信息隐藏方法会导致原始信息丢失，无法适用于司法、医学、军事等［1-3］对原始载体信号要求较高的领域。

为了解决该问题，不少学者提出可逆信息隐藏方法，又称为可逆水印。目前，该算法主要包括无损数据压缩、直方图平移、差分扩展、图像插值等。然而，大部分图像插值的可逆信息隐藏算法存在图像质量差、嵌入率低、数据溢出现象尚待解决。

综上所述，本文提出一种一元二次方程与自适应梯度插值的可逆信息隐藏算法。该算法首先对原始图像I进行下采样；
然后利用图像插值算法生成插值图像C；
最后对插值图像C进行边缘梯度预测（Contrast-Guided Image Interpolation，CGI）将其分为重叠的3 × 3 块，依据边缘像素占比将块分为边缘块和非边缘块。对于非边缘块，采用一元二次方程插值空间算法，将块内相邻像素看作一元二次方程ax2+bx+c=0 的3 个系数a、b、c，建立以两根为参考值的期望插值模型；
针对边缘块，基于自适应梯度预测策略进行插值操作。经过上述一系列操作，将秘密信息S嵌入图像得到图像E，图1为算法流程图。

Fig.1 Flow chart of univariate quadratic equation interpolation space reversible information hiding algorithm图1 一元二次方程插值空间可逆信息隐藏算法流程

1.1 无损压缩算法

无损压缩算法通常首先选取图像的部分信息作为待压缩载体，再在压缩出的空间中存储秘密信息。Celik 等［4］提出一种LSB 压缩算法，基于预测条件熵编码将图像中未修改部分作为辅助信息以提升算法效率，但容易产生噪声使图像质量下降。Zhang 等［5］提出基于能力特征的压缩算法，利用能力特征优化当前嵌入以获得最优嵌入方式，但算法的隐藏容量有限。

1.2 直方图平移算法

直方图平移基于不同灰度值的统计特性完成信息隐藏。最早由Ni 等［6］提出基于直方图平移的可逆数据隐藏算法，根据载体图像直方图中的峰值点隐藏秘密信息，但该算法需要额外传送峰值或零点信息，且隐藏容量较小。Wang 等［7］提出两步嵌入法，显著提高算法性能。Xiong等［8］在直方图平移的基础上提出双层可逆嵌入算法，加强传统算法的不可感知性，提高嵌入容量。虽然上述算法均提升了图像的获取质量，但隐藏率仍然较低。

1.3 差分扩展算法

差分扩展算法是对像素差值法的扩展，该算法将比特信息扩展后设定差值最低有效位进行数据隐藏。Tian等［9］利用相邻像素间的相关性进行信息隐藏。Niu 等［10］在改进传统算法的基础上，利用采样像素点对非采样像素点进行预测，后采样像素点利用序列密码进行加密，非采样像素点利用Paillier 同态算法加密，最后在密文域上嵌入秘密信息，虽然该方法的安全性较高，但最高嵌入量仅为1.2bpp，应用局限性较大。

1.4 图像插值算法

近年来，Jung 等［11］提出的图像插值算法广泛应用于信息隐藏领域。该方法首先对输入图像进行下采样，再通过插值算法生成一幅与输入图像大小相同的插值图像，并且仅在插值图像的非基准像素中隐藏秘密信息。王继军［12］设计一种类似双线性插值原理的图像隐藏方法，将载体图像放大为原来的4 倍，放大图中有1/4 的插值点保留原始图像信息，其余插值点均可嵌入水印，相较于经典插值算法，生成的图像质量较好，但嵌入率仅为0.75bpp。

为此，Xiong 等［8］在上述算法的基础上进行改进，首先对载体图像进行分块，得到每个分块中4 个基准像素的最大值和最小值；
然后计算非基准像素与最大值、最小值差值的绝对值；
最后自适应选定差值，确定非基准像素能嵌入的最大水印位数。该算法相较于文献［12］的算法，在隐藏容量和图像质量嵌入率方面均有所提高，但图像峰值信噪比（Peak Signal-to-noise Ratio，PSNR）较低。熊祥光等［13］基于文献［8］提出一种改进的图像插值算法。该算法首先对插值图像进行重叠分块；
然后优先选择方差较小的分块；
最后自适应计算各非基准像素能隐藏的最大数据量。虽然解决了隐秘图像像素溢出的问题，提高隐藏容量及隐秘图像质量，但算法的运行效率较低。Hassan 等［3］提出基于图像插值的可逆信息隐藏算法。该算法利用增强邻居平均插值（Enhanced Neighbor Mean Interpolation，ENMI）和改进邻居平均插值（Improved Neighbor Mean Interpolation，MNMI）技术插值秘密数据，图像质量有所提高，但隐藏容量受限。

针对上述问题，本文提出一种基于一元二次方程与自适应梯度插值的可逆信息隐藏算法以解决嵌入容量小、图像质量差、数据溢出等问题。首先按照梯度预测的性质将插值图像块分为边缘块和非边缘块，优先选择方差较小的分块进行嵌入，然后运用一元二次方程插值算法和自适应梯度预测插值算法隐藏非边缘块和边缘块信息。

本文采用梯度预测算法将图像块划分为边缘块和非边缘块，以便利用像素本身性质解决图像插值问题，从而提高图像生成质量。

2.1 期望插值

传统图像插值方法首先对原始图像进行下采样操作；
然后利用相邻像素点间的相关性进行插值；
最终得到和原始图像相同尺寸的插值图像。图2 为期望插值计算示意图，“●”为原始图像I的像素点，称为基准像素；
“○”为由水平和竖直方向两个像素点确定的插值像素点；
“◎”为由对角线方向4 个像素点确定的插值像素点。其中，插值像素点为非基准像素，将单独处理图像右边界和下边界的像素点。

Fig.2 Schematic diagram of expected interpolation calculation图2 期望插值计算示意图

期望插值的计算过程如下：

（1）设输入原始图像I大小为m×n，对图像I进行下采样，生成图像O(m/2 ×n/2)。

式中，1 ≤i≤m/2，1 ≤j≤n/2。

（2）对图像O的非右边界和非下边界区域进行插值，生成非基准像素，得到插值图像。

（3）对图像O的右边界的像素点进行插值。

（4）对图像O的下边界的像素点进行插值。

（4）对于最右下角的像素点进行插值。

2.2 像素分类

基于梯度预测算法完成图像像素分类，将图像像素分为边缘像素和非边缘像素。首先计算图像C的像素点(i，j)在θ方向扩散后的梯度值Uθ：

式中，∇θ为方向导数，θ∈{0°，45°，90°，135°}，由此可得：

式中，*表示卷积运算，Sθ表示边缘检测算子对应的掩膜，4个方向的掩膜分别为：

数据保真项Ed(μθ)为：

数据平滑项Es(μθ)为：

像素点的能量函数为：

式中，λ=0.2。

根据式（12）-（14）可得：

将式（15）的积分函数转换为：

对E(μθ)求解最小值可得：

运用拉布拉斯算子∇2，即∇2μθ可表示为：

根据式（17）、式（18）化简可得：

由于式（19）存在两个连续的空间变量x、y，因此适用迭代方程进行求解。引入连续的时间变量参t后可得：

根据式（20）-（22）可得：

式中，n1代表迭代次数，一般为不超过10的正整数。

利用所得的4 个方向梯度值μ0、μ45、μ90、μ135对图像C的像素点进行类型判断。对于水平方向上的像素，若|μ0-μ90| ≥T，则此像素为边缘像素；
若|μ0-μ90|

2.3 图像块分类

插值图像C中边缘像素点的数量Z占所有像素点的比例D：

式中，0 ≤Z≤m×n。

根据图像边缘像素占比D可得图像分块划分参数d：

将插值图像C以步长为2 与3 × 3 分块进行不完全重叠操作，为了避免重复嵌入信息，每个分块选择3 个非基准像素点嵌入秘密信息，分别为第一行的插值、第一列插值和对角线插值，如图3所示。

Fig.3 Block diagram图3 分块示意图

由图3 可见，当分块边缘像素点占比大于d时，则为边缘像素块，反之则为非边缘像素块。

2.4 图像块方差排序

设分块左上角的基准像素点为C(i，j)，分别计算分块中非基准像素C(i，j+1)、C(i+1，j)、C(i+1，j+1)与最邻近差值最小的基准像素的差值bk(k∈{1，2，3})：

各分块对应的方差Vh为：

由于方差越小，图像越平滑，对图像的影响越小，图像质量越好。因此，首先对各分块按照方差Vh进行排序，然后优先选择方差最小的块进行信息隐藏。

由于图像插值会将原始图像先进行下采样操作，再进行插值，因此需要计算非基准像素与基准像素之间的差值以便于进行数据隐藏操作［14］。

3.1 一元二次方程插值算法

为了提高嵌入容量，针对非边缘像素块相对平滑的特点，本文将三相邻像素点作为一元二次方程ax2+bx+c=0 的系数a、b、c，根据方程的两个解与图像期望插值的最大差值嵌入秘密信息。

3.1.1 一元二次方程构造及性质

为了避免一元二次方程无解的情况，由于原始a、b、c均为像素灰度值（大于0），因此a取负数：

同时，为了提高图像插值的质量及系统安全性，按照水平、垂直、对角线等不同方向构造一元二次方程，如图4所示。

（1）对于水平像素点C(i，j+1)，选择水平方向上2 个领域像素值和对角线方向上1 个领域像素值作为一元二次方程的系数（见图4(b)）：

（2）对于竖直像素点C(i+1，j)，选择垂直方向上2 个领域像素值和对角线方向1 个领域像素值作为一元二次方程的系数（见图4(c)）：

Fig.4 Point selection distribution图4 构造一元二次方程

（3）对于对角线像素点C(i+1，j+1)，首先计算该像素点的梯度以此判断方向θ，从而选择不同像素点作为一元二次方程的系数。对角线像素点可由判断值g表示：

若g=|μ0|且g>0，则θ=0°，一元二次方程选择0°方向掩膜为1的像素点（见图4(d)）：

若g=|μ0|且g≤0，则θ=180°，一元二次方程选择180°方向掩膜为1的像素点（见图4(e)）：

若g=|μ45|且g>0，则θ=45°，一元二次方程选择45°方向掩膜为1的像素点（见图4(f)）：

若g=|μ45|且g≤0，则θ=225°，一元二次方程选择225°方向掩膜为1的像素点（见图4(g)）：

若g=|μ90|且g>0，则θ=90°，一元二次方程选择90°方向掩膜为1的像素点（见图4(h)）：

若g=|μ90|且g≤0，则θ=270°，一元二次方程选择270°方向掩膜为1的像素点（见图4(i)）：

若g=|μ135|且g>0，则θ=135°，一元二次方程选择135°方向掩膜为1的像素点（见图4(j)）：

若g=|μ135|且g<0，则θ=315°，一元二次方程选择315°方向掩膜为1的像素点（见图4(k)）：

一元二次方程ax2+bx+c=0的解为：

此外，为了保证结果的通用性，将x1、x2进行归一化，并将归一化结果映射到区间大小为0～255的像素值区间。

3.1.2 可嵌入位数

将期望插值（包括基准像素点）记为Goodk，一元二次方程得出的解记为默认为x1

若Goodk在x1、x2的绝对值取整的对称轴的右边，选取x1，反之选取x2。因此，一元二次方程起始值Gsk为：

期望插值Goodk与Gsk的差值goodk可嵌入区间，该区间大小为：

式中，k∈{1，2，3}。

可嵌入的位数为：

以水平C(i+1，j)、k=1 为例，当所选像素点为a=-111、b=107、c=109 时，能够将一元二次方程转化为抛物线与X 轴的交点，根为x1=-0.62、x2=1.5839，归一化映射像素值为x1=105、x2=139，可 得Good1=C(i，j+1)=108、good1=31、L1=4。根据上述信息，可在图中嵌入4bit的二进制秘密信息，如图5所示。

Fig.5 Example of a quadratic equation of one variable图5 一元二次方程示例

3.1.3 修正因子

当goodk+S=Goodk时，载密图像E的质量最理想，但由于秘密信息S的不确定性，会产生不同的结果。为此，引入修正因子T使Goodk-(goodk+S+T)趋近与0。其中，秘密信息S对应的二进制为ssi(i=1，2，3...)，插入的最大范围Smax为：

由式（46）可得嵌入秘密信息位数，但该式会造成goodk与Smax之间产生差值，影响图像的质量。因此，本文增加参数t1对该式进行调整：

同理，S与Smax也存在差值，引入阈值Lk′控制嵌入位数：

根据（48）-（50）修正参数t2：

最终调整参数为：

3.1.4 信息隐藏

一元二次方程的信息隐藏公式如下：

若隐藏秘密信息s=0，则t1=31 -15=16、Lk′=1、smax′=1、t2=16-2=14、T=30、Sk=139-0-30=109、Goodk-(goodk-s-T)=1。此时，算法对图像效果质量影响较小。

3.2 自适应梯度插值算法

该算法的目的在于尽量不破坏边缘像素块原有性质的同时，在边缘像素块中隐藏秘密信息，以提高图像质量。具体的，算法依据边缘像素点在各方向上的梯度值占比，自适应地计算可嵌入位数以嵌入秘密信息。

3.2.1 梯度预测

根据边缘像素块每个像素点在0°、45°、90°、135°方向上的预测梯度μ0、μ45、μ90、μ135，可得梯度占比Pθ，其中θ∈｛0o，45o，90o，135o｝：

其中，可溢出像素范围即为可嵌入区间goodk：

式中，k∈{1，2，3}，godk为可溢出值。

根据式（45）计算可嵌入位数，以第一个像素点为例，4个方向的预测梯度分别为：μ0=0.042 3、μ45=0.062 9、μ90=0.018 0、μ135=0.022 6，期望插值分别为Goodk=112、P0=0.408 6、P45=0.758 6、P90=0.140 9、P135=0.183 35，god1=168、good1=37、L1=56。因此，可嵌入秘密信息S二进制的位数为5。

3.2.2 信息隐藏

为了减少插入秘密信息S产生的各种差值对图像质量造成的影响，本文提出自适应梯度插值算法：

当隐藏秘密信息为s=13，即t1=56 -31=25、Lk′=4、S′max=16、t2=32 -16=16、T=41、Sk=168-13-41=114，可得Goodk-(goodk+s+T)=2。由此可见，载密图像值与期望插值几乎接近于0，图像质量存在一定程度提升。

4.1 载体图像恢复

在秘密信息隐藏过程中，所有基准像素点都未进行任何更改操作。可根据载秘图像E中保留的插值图像C的基准像素点，通过下采样操作无损恢复载体图像R。例如，对于8×8含密子块E，黑色像素为基准像素（见图6），其中最后一行/列黑色像素与倒数第二行/列黑色像素相同。因此，利用公式（57）恢复载体4×4 子块R，其中i、j∈{1，2，3，4}。

4.2 秘密信息提取

秘密信息提取算法是插值隐藏算法的逆过程。首先对恢复的载体图像R进行插值操作得到插值图像C；
然后计算插值图像各像素梯度值，将图像分成重叠的3 × 3 子块，依据边缘像素占比将其分为边缘块和非边缘块；
接下来计算各分块的方差，以选择待提取块；
最后将二进制秘密信息转化为十进制秘密信息S。

Fig.6 Recovery diagram of 8×8 block图6 8×8子块恢复图

（1）当分块属于非边缘像素块时，秘密信息S为：

（2）当分块属于边缘像素块时，秘密信息S为：

5.1 数据集

本文实验基于SIPI 基准数据集［17］，在Wimdows10 和MATLAB 2020b 平台进行仿真实验，将实验结果与现有算法进行性能比较，以进一步证明本文算法在嵌入率和图像质量方面的优势。

SIPI 数据集主要包括纹理、天线、杂项、序列四大类，共306 张图像，每种类型的图像大小各不相同，黑白图像为8 位/像素，彩色图像为24 位/像素，如图7 所示。为了避免实验的偶然性，本文选择不同大小的灰度和彩色图像进行实验。

Fig.7 Original carrier image图7 原始载体图像

5.2 透明性测试

图8 为以512×512 大小的标准灰度图像为例，嵌入随机生成的二值信号的载密图像。其中，图8 分别展示了Lk′=1 和满载时的图像效果，由此可见载密图像的不可感知性较好。

Fig.8 Secret image图8 载秘图像

5.3 嵌入容量与载秘图像质量

采用峰值信噪比（Peak Signal-to-Noise Ratio，PSNR）、嵌入率（Embedding Rate，ER）、结构相似性（Structural Similarity Index，SSIM）作为评价标准分析算法性能。

表1 为算法在Lk′=1、2、4 和满载时，载密图像的ER、PSNR、SSIM 值，整个隐藏信息过程无数据溢出，也无任何附加信息。

由此可见，Lk′的取值与嵌入容量、图像质量密切相关。当Lk′的取值越大时，平均嵌入率ER 越高，峰值信噪比PSNR 与结构相似性SSIM 越低，图像质量降低；
当Lk′的取值越小时，平均嵌入率ER 越低，峰值信噪比PSNR 与结构相似性SSIM 越高，图像质量越好。

总体而言，本文算法具有较大嵌入容量，满载时平均嵌入率ER 高达4.068 1bpp，载密图像在Lk′=1、2、4 的PSNR 与SSIM 值较高。

Table 1 Values of Er，PSNR and SSIM of secret image表1 载密图像ER、PSNR、SSIM值

5.4 性能比较

在相同实验条件下，将本文算法与以插值图像为载体图像的可逆信息隐藏算法进行比较，具体实验结果见表2、表3。

由表2 可知，本文算法容量最高，满载平均容量高达4.068 1bpp，相较于现有方法优势明显。当Lk′=1 时，算法的平均嵌入率与文献［12］的方法相同；
当Lk′=2 时，算法平均嵌入率高于文献［8］和文献［12］的方法；
当Lk′=4 时，算法的平均嵌入率高于文献［12］、文献［17］、文献［8］、文献［15］、文献［16］和文献［15］的方法。

由表3 可知，本文算法的图像质量较高，当Lk′=1、2时，算法的平均峰值信噪比分别为28.638 2dB 和28.613 4dB，均高于其他方法。当Lk′=4时，算法的平均峰值信噪比高达28.198 2dB，远远高于文献［19］、文献［18］、文献［8］、文献［15］、文献［16］和文献［15］的方法，略低于文献［12］的方法。

Table 2 Comparison of embedding rate ER between the proposed algorithm and other algorithms表2 本文算法与其他算法嵌入率ER比较

本文提出一种基于一元二次方程插值与自适应梯度预测插值可逆信息隐藏算法。该算法无任何附加信息、无数据溢出，仅以插值图像为载体，通过构造一元二次方程和自适应梯度预测模型，结合边缘像素和非边缘像素的自身的梯度性质实现图像插值和秘密信息嵌入。

Table 3 Comparison of PSNR between the proposed algorithm and other algorithms表3 本文算法与其他算法峰值信噪比PSNR比较

实验结果表明，该算法灵活性高、实用性强，在图像嵌入容量与隐秘图像质量方面相较于传统方法提升显著，并能够无损还原载体、准确提取秘密信息。下一步，将该模型运用于人工智能、模型水印等领域。