ABSTRACT

To solve the problems of small embedding capacity and low security of image watermarking algorithm, a watermarking image can be decomposed into multiple shadow images with the secret sharing algorithm, and then the shadow images can be embedded into multiple carrier images by histogram shifting. This paper proposes a multi-image watermarking algorithm based on secret sharing and histogram shifting. In this algorithm, the watermarking image cannot be extracted by only one shadow image, and other shadow images must be used. Therefore, the algorithm security is improved. Meanwhile, the embedding capacity of image watermarking can be enlarged by increasing the number of carrier images. Algorithm analyses and experimental results show that the proposed algorithm is feasible.

Keywords:Image Watermarking, Secret Sharing, Histogram Shifting, Multiple Image Process

基于秘密分享和直方图平移的多图像水印算法

赵卓影^1,2，张佳志^1,2，张晓强^1,2*

¹中国矿业大学信息与控制工程学院，江苏 徐州

²徐州市人工智能与大数据重点实验室，江苏 徐州

收稿日期：2019年4月3日；录用日期：2019年4月14日；发布日期：2019年4月28日

摘 要

针对目前图像水印算法存在的嵌入容量小和安全性弱的问题，利用秘密分享方案将一幅水印图像分解成多幅影子图像，再通过直方图平移算法把影子图像分别嵌入到多幅载体图像中，从而提出了一种基于秘密分享和直方图平移的多图像水印算法。在该算法中，若仅有一幅影子图像将无法提取出水印图像，需要有其他影子图像，从而提高了图像水印算法的安全性。同时，通过增加载体图像的数量，可扩大图像水印算法的嵌入容量。算法分析和实验结果表明该算法的可行性。

关键词 :图像水印，秘密分享，直方图平移，多图像处理

Copyright © 2019 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

图像是网络信息的重要载体。据心理学家统计，人类约有70%的信息都来自视觉。拍摄设备的增加以及拍摄的便捷性使得图像在军事、医疗、气象、电子政务以及个人事务等领域得到了广泛的应用。人们的图像版权保护意识逐渐增强，图像水印是一种保护图像版权的技术。然而，黑客攻击能力的提升以及图像复制和传播的便捷，对图像水印技术提出了新挑战。

秘密分享方案 [1] [2] 是利用Shamir的 $\left(k,n\right)$ 门限秘密分享机制。它是将一份秘密信息分解成 $n$ 份影子信息，任何一份影子信息均无法独自恢复出秘密信息，只有把其中的任意 $k\left(k\le n\right)$ 份影子信息联合起来才能恢复出秘密信息。

对于基于直方图平移的可逆水印算法，高峰值点意味着较高的嵌入能力 [3] 。在直方图可逆水印技术中，利用峰值点和零值点对来修改载体图像的直方图。可嵌入到载体图像中的秘密位数等于与峰值点相关联的像素数。在覆盖图像块上应用模量算子后，利用载体图像的直方图来确定嵌入位置。使用模量算子的主要目的是增加载体图像直方图中的峰值点数，这增加了载体图像的嵌入能力，而含水印图像的失真度较低 [4] 。单幅图像水印算法仅有一幅载体图像，水印嵌入容量有限。多图像水印算法含有多幅载体图像，可明显扩大嵌入容量。目前，多图像水印技术越来越受到研究者们的关注 [5] 。

因此，将秘密分享方案和基于直方图平移的图像水印算法有机地结合，提出一种基于秘密分享和直方图平移的多图像水印算法。算法分析和实验结果表明：该算法是安全可靠的，且具有较大的嵌入容量。

2. 理论基础

2.1. 秘密分享方案

Shamir的 $\left(k,n\right)$ 门限秘密分享方案的基本思想是：首先，要把秘密S分割成 $n$ 份影子信息；其次，分别将 $n$ 份影子信息分发给 $n$ 个参与者进行保管；最后，任意 $k\left(k\le n\right)$ 份影子信息联合起来才能恢复出S。

基于拉格朗日插值多项式算法的秘密分享方案 [6] 描述如下。令 $k-1$ 次的拉格朗日多项式为：

$f\left(x\right)=m_0+m_{1}x+m_2{x}^2+\cdots +m_{k-1}{x}^{k-1}$， (1)

其中，k为整数且 $k\le n$，系数 $m_1,m_2,\cdots ,m_{k-1}$ 可根据情况任意选取 [7] 。

令水印图像为秘密S，则基于拉格朗日插值多项式算法的秘密分享方案可描述为：将一幅水印图像分解成n幅影子图像，任何一幅影子图像均无法独自恢复出水印图像，只有把其中的任意 $k\left(k\le n\right)$ 份影子联合起来才能恢复出水印图像。

2.2. 直方图平移算法

Ni等人提出了一种基于直方图平移的可逆水印算法 [8] ，其算法思想为：首先，绘出图像的灰度直方图，并找出其中的最大值点a和最小值点b，为方便讨论，不妨设 $a<b$ ；其次，将图像中所有在 $\left[a+1,b-1\right]$ 的灰度值加1，即将 $\left[a+1,b-1\right]$ 的直方图向右平移一位，从而像素值为 $a+1$ 的像素点的个数变为0；再次，在嵌入水印时，若水印值为1，则像素值为a的灰度值加1，即为 $a+1$ ；若水印值为0，则保持 $a$ 的像素值不变；最后，提取水印信息时，顺序扫描图像，若像素灰度值为a，则提取的水印信息为0；若像素灰度值为 $a+1$，则提取的水印信息为1 [9] 。若想恢复出原始宿主图像，只需把灰度值处在区间 $\left[a+1,b\right]$ 的灰度值减1即可。

3. 新多图像水印算法

3.1. 生成影子图像

设水印图像为 $W$，根据基于拉格朗日插值多项式算法的秘密分享方案，生成n幅影子图像步骤如下：

步骤1：令公式(1)中的 $m_0=w_{ij}$，其中 $w_{ij}\in W$ ；

步骤2：随机选取 $m_1,m_2,\cdots ,m_{k-1}$ 的值作为公式(1)的系数；

步骤3：选择 $W$ 上 $n$ 个不同的非零值 $x_1,x_2,\cdots ,x_n$，且将此 $n$ 个值公开，分别计算 $w_{ij}^1=f\left(x_1\right),w_{ij}^2=f\left(x_2\right),\cdots ,w_{ij}^n=f\left(x_n\right)$ ；

步骤4：对 $W$ 中的所有像素进行步骤1~步骤3的操作，即可得到n幅影子图像，即 $W^1=\left\{w_{ij}^1\right\},W^2=\left\{w_{ij}^2\right\},\cdots ,W^n=\left\{w_{ij}^n\right\}$。

3.2. 嵌入影子图像

设 $k\left(k\le n\right)$ 幅载体图像为 $I_{\text{1}},I_{\text{2}},\cdots ,I_k$，从 $n$ 幅影子图像中任选 $k$ 幅即 $W^1,W^2,\cdots ,W^k$ 作为水印信息，分别嵌入到 $k$ 幅载体图像中。根据秘密分享方案， $k$ 幅影子图像可以恢复出原水印图像。提出的多图像水印算法嵌入影子图像的详细步骤如下：

步骤1：绘制 $I_1$ 的直方图，找出其中的最大值点a，并在最大值点右侧寻找最小值点b [10] ；

步骤2：直方图平移。在像素值为 $\left[a,b\right]$ 内的像素点上嵌入影子信息，先顺序扫描图像，当扫描到的像素值为 $\left[a+1,b-1\right]$ 内的值时，将其值加上1，其他的像素值不变；

步骤3：嵌入影子。扫描载体图像，当扫描到的像素值为a时，在该像素点嵌入1位影子信息 $w_{ij}^1\in W^1$ 且 $w_{ij}^1\in \left\{0,1\right\}$。嵌入规则为：若嵌入的水印影子信息为0，则该点像素值不变；若嵌入的影子信息为1，则该点的像素值加1；

步骤4：类似地，将影子图像 $W^2,W^3,\cdots ,W^k$ 分别嵌入到 $I_2,I_3,\cdots ,I_k$，最终可得含水印图像为 $I_1^W,I_2^W,\cdots ,I_k^W$。

3.3. 提取影子图像及恢复载体图像

步骤1：提取影子图像。对含水印图像 $I_1^W$ 的像素值进行顺序扫描，若扫描到的像素值为a，则恢复的影子信息为“0”；若扫描到的像素值为 $a+1$，则恢复的影子信息为“1”，从而恢复出影子图像 $W^1$。类似地，可提取出含水印图像 $I_2^W,I_3^W,\cdots ,I_k^W$ 中的 $k-1$ 幅影子图像 $W^2,W^3,\cdots ,W^k$ ；

步骤2：将k组不同的值 $\left(x_1,w_{ij}^1\right),\left(x_2,w_{ij}^2\right),\cdots ,\left(x_k,w_{ij}^k\right)$ 分别代入公式(1)可得如下方程组，其中， $w_{ij}^1\in W^1,w_{ij}^{\text{2}}\in W^{\text{2}},\cdots ,w_{ij}^k\in W^k$，为影子图像 $\left(i,j\right)$ 位置的像素值，

$\begin{array}{l}{w}_{ij}^1\left(x_1\right)=m_0+m_1{x}_1+m_2{x}_1^2+\cdots +m_{k-1}{x}_1^{k-1}\mathrm{mod}255\\ w_{ij}^2\left(x_2\right)=m_0+m_1{x}_2+m_2{x}_2^2+\cdots +m_{k-1}{x}_2^{k-1}\mathrm{mod}255\\ ⋮\\ w_{ij}^p\left(x_k\right)=m_0+m_1{x}_k+m_2{x}_k^2+\cdots +m_{k-1}{x}_k^{k-1}\mathrm{mod}255\end{array}$ ； (2)

步骤3：通过求解方程组式(2)的解就能得到所需要的 $m_0,m_1,m_2,\cdots ,m_{k-1}$ 的值，其中 $m_0$ 就是要恢复水印图像的像素值，将其存储在需要恢复水印图像的相应位置。类似地，对每个像素进行处理，最后能恢复出水印图像 [11] [12] ；

步骤4：恢复载体图像。再次顺序扫描图像，将扫描到的 $\left[a+1,b\right]$ 内的像素值减去1，即可恢复载体图像。

4. 实验验证

选取大小为 $50\times 50$ 的Lena灰度图像作为水印图像，根据3.1节影子图像生成算法可生成8幅影子图像，如图1所示。选取大小均为 $512\times 512$ 的Pepper，Baboon和Pens等8幅载体图像，如图2所示。根据3.2节嵌入影子图像算法，将8幅影子图像分别嵌入到8幅载体图像中，得到含水印图像，如图3所示。提取出8幅影子图像后，根据3.3节提取影子图像及恢复载体图像算法，提取的水印图像，如图4所示。

图1. 影子图像

图2. 载体图像

图3. 含水印图像

图4. 提取的水印图像

5. 算法分析

透明性、鲁棒性、安全性、嵌入容量和算法执行效率是评价图像水印算法主要性能指标 [13] 。

5.1. 透明性

透明性是指数字水印的嵌入不能影响图像的正常使用，不会引起人类视觉系统的察觉。透明性可通过人眼进行主观评价或利用峰值信噪比(Peak Signal-to-Noise Ratio，简称PSNR)进行客观评价。PSNR定义为：

$\text{PSNR}=10\lg \frac{{255}^2}{\frac{1}{m\times n}{\displaystyle \underset{i=0}{\overset{m-1}{\sum }}{\displaystyle \underset{j=0}{\overset{n-1}{\sum }}{\left(X\left(i,j\right)-X_W\left(i,j\right)\right)}^2}}}$ (3)

其中， $X\left(i,j\right)$ 为原始图像的像素值， $X_W\left(i,j\right)$ 为含水印图像的像素值。PSNR值越小，则表示图像质量下降越多，透明性越差。反之，其值越大，透明性越好。

实验测得，图3所示的含水印图像对应的PSNR平均值30.86。虽然该数值偏小些，但是基于直方图平移的图像水印算法是一种可逆水印技术，可无损地恢复出原始载体图像。

5.2. 鲁棒性

鲁棒性是指含水印图像在经过常规信号处理操作后仍能检测水印的能力。针对图像的常规操作包括空间滤波、JPEG压缩、剪切攻击、打印与复印、几何变形和噪声攻击等。鲁棒性评价一般由归一化相关系数(Normalized Correlation，简称NC)来衡量。NC的定义为：

$\text{NC}=\frac{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}W\left(i,j\right)W^{\prime }\left(i,j\right)}}}{{\displaystyle \underset{i=1}{\overset{m}{\sum }}{\displaystyle \underset{j=1}{\overset{n}{\sum }}{W}^2\left(i,j\right)}}}$ (4)

其中， $W$ 表示原始水印图像， $W^{\prime }$ 为提取的水印图像。NC越接近于1，则表明提取的水印就越接近于原始水印，水印算法的鲁棒性越健壮。

在无噪声的情况下，计算图4和图1对应的NC的值为1，即提取的水印图像与原始水印图像完全相同。同时，通过对图像的JPEG压缩、裁剪攻击和高斯噪声攻击等测试，表明了新算法具有良好的鲁棒性。

5.3. 安全性

安全性是指水印算法能够抵抗各种破坏水印行为的能力，即未授权者不能去除、嵌入和检测水印。同时，水印信息应该很难被他人复制和伪造。

新算法利用了秘密分享的方案，将一幅水印图像分解成n幅影子图像。在提取水印时，必须由p份影子图像联合起来才能提取出水印图像，从而提高了图像水印算法的安全性。

5.4. 嵌入容量

嵌入容量是指采用水印算法能嵌入水印信息的多少。人们期望水印算法具有较大的嵌入容量。新算法将p幅影子图像分别嵌入到p幅载体图像中，从而扩大了水印算法的嵌入容量。同时，用户也可根据实际应用需要，通过调整载体图像的幅数，来控制嵌入容量的大小。

5.5. 算法执行效率

算法的时间复杂度是衡量算法执行效率的重要依据，通常用函数 $T\left(n\right)$ 来表示。

在生成影子图像时，须构造一个 $k-1$ 次拉格朗日多项式，如公式(1)所示。其时间复杂度 $T\left(n\right)=O\left(n^{k-1}\right)$。在提取水印图像时，须构造拉格朗日方程组，如公式(2)所示。其时间复杂度为 $T\left(n\right)=O\left(n^{k-1}\right)$。

同时，在影子图像嵌入过程中，主要包括像素比较、像素扫描和像素平移三个操作，其复杂度分析为：1) 需要 $\left(n-1\right)$ 次像素比较来确定峰值点和零值点，其中n为灰度级数；2) 令图像大小size，则需要

进行size次像素扫描；3) ${\displaystyle \underset{i\in \left(\text{peak}\_\text{point},\text{zero}\_\text{point}\right)}{\sum }h\left(i\right)}$ 次像素平移和一半数量峰值点向零点变化的加法操作 $\frac{1}{2}h\left(\text{peak}\_\text{point}\right)$。其中， $h\left(i\right)$ 为直方图函数， $\text{peak}\_\text{point}$ 为峰值点， $\text{zero}\_\text{point}$ 为零点。因此，嵌入水印算法的复杂度为：

$T\left(n\right)=O\left(\left(n-1\right)+\text{size}+{\displaystyle \underset{i\in U\left(\text{peak}\_\text{point},\text{zero}\_\text{point}\right)}{\sum }h\left(i\right)+\frac{1}{2}h\left(\text{peak}\_\text{point}\right)}\right)$ (5)

对于实际图像，由于size远大于n，故嵌入操作的时间复杂度近似为 $T\left(n\right)=O\left(\text{size}\right)$ [14] 。

实验测得，将1幅影子图像嵌入到1幅载体图像中平均耗时为0.36秒。说明新算法是高效的。

6. 结论

将秘密分享方案与基于直方图平移的图像水印算法有机结合，提出一种基于秘密分享和直方图平移的多图像水印算法。该算法利用秘密分享方案提高了水印算法的安全性。同时，通过增加载体图像幅数，增大了水印算法的嵌入容量。算法分析和实验结果表明，提出的多图像水印算法具有良好的鲁棒性、安全性和高效性。

致谢

非常感谢国家自然科学基金“大容量高安全的加密域图像可逆水印算法研究”(61501465)和江苏省大学生创新训练项目“加密域图像可逆水印算法研究”(201810290059X)对该文的资助。感谢匿名审稿人对论文提出建设性的修改意见。

文章引用

赵卓影,张佳志,张晓强. 基于秘密分享和直方图平移的多图像水印算法
Multi-Image Watermarking Algorithm Based on Secret Sharing and Histogram Shifting[J]. 图像与信号处理, 2019, 08(02): 83-89. https://doi.org/10.12677/JISP.2019.82012

参考文献