改进的成对预测误差扩展可逆数据隐藏算法

Improved Reversible Data Hiding Algorithm for Pairwise Prediction Error Expansion

摘要: 基于成对预测误差扩展是目前一种大容量低失真的可逆数据隐藏技术。误差扩展算法通过生成二维预测误差直方图确定最优扩展路径以完成自适应地修改。中值边缘检测器和菱形预测的方法只考虑了部分被测像素周围的相邻像素，本文考虑了被测像素周围的八个像素值，更好地利用了图像像素之间的相关性，并在此基础上，更精确地区分像素局部区域纹理度的高低，来实现选择像素值的精确度。所提方法在嵌入相同容量的秘密信息时，图像的失真度都优于现有算法，具有更好的视觉质量。

Abstract: Expansion based on pairwise prediction errors is currently a reversible data hiding technology with large capacity and low distortion. The error expansion algorithm determines the optimal expansion path by generating a two-dimensional prediction error histogram to complete the adaptive modifi-cation. The median edge detector and diamond prediction method only considers the neighboring pixels around part of the measured pixel. This article considers the eight pixel values around the measured pixel, which makes better use of the correlation between image pixels, and on this basis, the level of texture in the local area of the pixel is more accurately distinguished to achieve the accuracy of the pixel value selection. When the proposed method embeds the same capacity of secret information, the distortion of the image is better than that of the existing algorithm, and it has better visual quality.

1. 引言

传统的信息隐藏方法 [1] 在使用过程中会出现载体信息丢失的情况，攻击者 [2] 对秘密信息的盗取和恶意篡改等行为也会使得秘密信息被泄露。因此可逆信息隐藏 [3] 成为了近年来研究的热点。可逆数据隐藏技术将隐藏数据以某种算法嵌入到公开的载体图像中进行秘密地传输。接收方可以根据嵌入算法的逆过程来获得之前隐藏的数据，并且无失真地恢复原来的载体图像 [4]。由于可逆数据隐藏技术具有可逆性 [5] 和保密性 [6]，被广泛地应用在医疗和军事等领域。在实际应用中需要大容量 [7] 地嵌入秘密信息，而大容量地嵌入秘密信息往往会造成图像失真度低。因此，目前研究的关键问题在于如何尽可能地平衡好嵌入秘密信息的大小和图像失真度 [8] 两者之间的关系。

目前的文献中提出了很多可逆的数据隐藏技术。2003年，Tian等人 [9] 提出了一种基于差值扩展的可逆数据隐藏方法。该算法将秘密信息嵌入到相邻像素对的差值中，但嵌入容量不足以满足需要。随后，为了增大嵌入容量，Celik [10] 等人提出了最低有效位压缩方法，通过压缩辅助信息来提高嵌入秘密信息的容量。然而，由于其采用无损压缩的方法，当嵌入容量过大时会造成图像的峰值信噪比(PSNR)急剧下降。后来，Ni等人 [11] 最先提出了基于直方图修改的可逆数据隐藏的方法。该方法提高了图像的失真度，但由于采用基于图像像素生成直方图的峰值进行数据嵌入，从而使其嵌入容量有限。Lee [12] [13] 等人提出了基于差分直方图平移的方法，由于在直方图中差值的峰值最高，以此获得更大的冗余空间。Xuan等人提出用四个阈值来辅助秘密信息进行双层嵌入，增加了嵌入容量。Ou等人提出了成对预测误差扩展的方法，通过在固定的像素值上嵌入秘密信息，提升了图像的质量。Xiao等人提出了动态规划算法，缩短了算法运行时间。

本文对Xiao等人的方法进行了改进，提出了一种更多考虑到图像内容和像素之间相关性的方法，主要贡献如下：

1) 提出了一种全新的全封闭预测方法。结合了先前工作中的MED (中值边缘检测器预测器)和菱形预测方法的优点，充分利用了被测像素值周围的相邻像素，得出更为精确的预测值，为嵌入秘密信息时选择嵌入像素值的位置提高了准确率，更进一步提高了嵌入后图像的视觉质量。

2) 提出了一种基于全封闭预测方法的计算像素局部区域纹理度高低的方法，3 × 3的像素可以被分成上下两部分，每部分分别计算相邻像素和被测像素差的绝对值之和，再将这两部分计算的值相加，在计算的过程中，充分考虑了像素内容，更为精确地区分像素局部区域的纹理度高低，进一步提高了选择嵌入像素的精度，从而改善可逆信息隐藏的失真度。

3) 实验结果表明，所提方法在嵌入大量的秘密信息时，图像具有较高的峰值信噪比，更好地平衡了嵌入容量和图像质量之间的矛盾。

2. 相关工作

2.1. 传统的预测误差扩展(C-PEE)

Wang等人的工作提出了传统预测误差扩展的可逆数据隐藏方案。通过修改预测误差，来进行秘密数据的嵌入，该方法可以将有效载荷嵌入到具有高标记图像质量的图像中，但是嵌入容量较少，图像的失真度也很高。现在我们将简要介绍这种方法。为了清晰地表示，只给出了基于直方图平移的嵌入阶段。首先，生成预测误差直方图。对于原图像I，将像素按照特定的顺序扫描(从左上角以光栅扫描方式扫描原图像I，不包括最右列和最后一行)得到的像素序列可以表示为 $\left(x_1,\cdots ,x_n\right)$，其中，x₁是被扫描的第一个像素值，N是所有被扫描图像的总数。中值边缘检测器预测方法 [14] 来预测每一个像素值，像素预测值为 ${\hat{x}}_i$，用原来的像素值减去像素的预测值，就是预测误差，公式如下：

$e_i=x_i-{\hat{x}}_i$

MED预测方法依赖于被测像素值的右边、下边和斜对角的像素值如图1所示。

Figure 1. Context of the measured pixel

图1. 被测像素的上下文

MED预测方法需要用特定的顺序将原始图像进行扫描，利用被测像素值的右边、下边和斜对角的像素值进行预测，像素预测值被表示如下：

${\hat{x}}_i=\{\begin{array}{ll}\min \left(u,v\right),\hfill & \text{if}w\ge \max \left(u,v\right)\hfill \\ \max \left(u,v\right),\hfill & \text{if}w\le \min \left(u,v\right)\hfill \\ u+v-w,\hfill & \text{otherwise}\hfill \end{array}$

其中， $\min \left(u,v\right)$ 和 $\max \left(u,v\right)$ 分别表示计算u和v时的较大和较小的函数。被测像素值x的预测结果为 ${\hat{x}}_i$，用被测像素的像值减去预测值，就可以得到预测误差，从而获得预测误差序列 $\left(e_1,\cdots ,e_n\right)$，将预测误差进行统计生成预测误差直方图 [15]。

对预测误差直方图进行修改，传统的预测误差扩展修改包括以下几个步骤：

${\tilde{e}}_i=\{\begin{array}{ll}{e}_i+m,\hfill & \text{if}{e}_i=0\hfill \\ e_i-m,\hfill & \text{if}{e}_i=-1\hfill \\ e_i+1,\hfill & \text{if}{e}_i>0\hfill \\ e_i-1,\hfill & \text{if}{e}_i<0\hfill \end{array}$

其中，m表示要嵌入的秘密信息位， $m\in \left(0,1\right)$。当预测误差为0或−1时，修改预测误差直方图，在预测误差为0或者−1时嵌入秘密信息；预测误差大于0或者小于−1时，将预测误差直方图向前或者向后移动一个扩展箱的位置，以便腾出更多的空间保证数据嵌入的可逆性。原图像素在嵌入秘密信息后像素值就表示为 ${\tilde{x}}_i={\hat{x}}_i+{\tilde{e}}_i$，也就是像素预测值与嵌入秘密信息之后的预测误差之和。

在图2中表示出了用于传统预测误差扩展的图示。图2中表示出了传统预测误差扩展的扩展箱的位置变化过程 [16]，其中红色扩展项(预测误差为−1和0)被嵌入数据而绿色扩展箱(预测误差大于0或者小于−1)进行了移动。

Figure 2. On the method of traditional prediction error expansion

图2. 关于传统预测误差扩展的方法

传统预测误差扩展的提取过程是嵌入秘密信息的逆过程，提取和图像恢复过程总结如下。首先，得到嵌入秘密信息之后的预测误差，然后，原始图像的像素预测误差表示为

$e_i=\{\begin{array}{ll}{\tilde{e}}_i,\hfill & \text{if}{\tilde{e}}_i\in \left\{-1,0\right\}\hfill \\ {\tilde{e}}_i-1,\hfill & \text{if}{\tilde{e}}_i>0\hfill \\ {\tilde{e}}_i+1,\hfill & \text{if}{\tilde{e}}_i<0\hfill \end{array}$

最后，图像像素恢复为 $x_i={\hat{x}}_i+e_i$。

2.2. 自适应嵌入和最佳预测误差选择相结合的预测误差扩展

针对传统预测误差进行改进，其中有自适应嵌入的预测误差扩展方法 [17] 和最佳预测误差选择的预测误差扩展方法，将这两种方法结合起来就是这部分要进行描述得方法(AO-PEE)。

首先是自适应嵌入策略，为了更好地利用图像的冗余，提出了复杂度度量n_i，并且，只有当n_i < T时嵌入的那一部分可以用来嵌入秘密信息，T是预先选择的阈值且T > 0。这相当于，对于每个像素(n_i < T)时，将根据传统预测误差扩展方法的嵌入程序进行处理。否则，也就是n_i ≥ T，像素会被忽略，值保持不变。在这种方法中，是影响嵌入性能的重要因素。为了更好地利用平滑像素，T被当作最小的正整数，这样有效载荷就可以被成功嵌入。将有效载荷嵌入后，阈值的选取从0开始，每次值增加1，直到找到最优的图像质量，那么相对应的T便是要确定的阈值。

复杂度测量是计算每个像素差异的平均值，即

$n_i=\frac{\left|u-v\right|+\left|v-w\right|+\left|w-u\right|}{3}$

其次，最佳预测误差的选择需要考虑满足以下要求的特定的预测误差直方图，假定嵌入容量为。在这种情况下，将嵌入失真的期望值范数可以表示为

$E\left({\Vert \tilde{I}-I\Vert }_2^2\right)=\underset{i=1}{\overset{N}{{\displaystyle \sum }}}E\left({\left({\tilde{x}}_i-x_i\right)}^2\right)=\frac{1}{2}\left(h\left(-1\right)+h\left(0\right)\right)+\underset{e\notin \left\{-1,0\right\}}{{\displaystyle \sum }}{h}_{\left(e\right)}=N-H$

其中，I和 $\tilde{I}$ 分别用来表示原图像和嵌入秘密信息之后的图像，由于被嵌入像素不一定要在预测误差为−1和0的像素上，对于这种特定的预测误差直方图，可以选择预测误差 [18] 为−1和1的像素上嵌入秘密信息，预测误差为0的像素保持不变。那么嵌入失真的期望值发生了变化从N − H和N − 2H。如图3所示：

Figure 3. On the method of adaptive prediction error expansion

图3. 关于自适应预测误差扩展的方法

这一发现表明可以通过改变预测误差的选择来增加秘密信息的嵌入容量。基于此，发现对于给定的嵌入容量，可以选择两个预测误差满足a，a和b的具体数值可以通过重复嵌入来决定最佳的预测误差。由于a和b的变动，嵌入秘密信息像素的预测误差变为

${\tilde{e}}_i=\{\begin{array}{ll}{e}_i,\hfill & \text{if}a<e_i<b\hfill \\ e_i+m,\hfill & \text{if}{e}_i=b\hfill \\ e_i-m,\hfill & \text{if}{e}_i=a\hfill \\ e_i+1,\hfill & \text{if}{e}_i<b\hfill \\ e_i-1,\hfill & \text{if}{e}_i<a\hfill \end{array}$

将这两个改进结合起来就是这部分要描述的AO-PEE，AO-PEE需要确定三个参数：复杂度阈值T，扩展箱(a, b)。T是最小的正整数，对于给定的(a, b)，重复嵌入秘密信息的步骤来收集(a, b)，当嵌入失真最小时，相对应的参数便是要找的最佳参数。通过这两方面的改进，AO-PEE的性能得到了提高。

3. 本文方法

3.1. 全封闭的预测方法

本文采用了全封闭的预测方法，和目前常用的MED预测方法和菱形预测方法相比有些许不同，目前工作中的MED预测方法和菱形预测方法的优点，充分利用了被测像素值周围的相邻像素，得出更为精确的预测值，为嵌入秘密信息时选择嵌入像素值的位置提高了准确率，更进一步提高了嵌入后图像的视觉质量。根据整体的算法来选取合适的预测方法，合适的预测方法可以去掉原始图像像素间大部分相关的信息，从而使得预测误差分布集中在0附近，由预测误差生成的直方图从最中间向两侧递减，这样尖锐的直方图可以提高算法的性能。本文采用了一种基于全封闭预测方法的计算像素局部区域纹理度高低的方法，3 × 3的像素可以被分成上下两部分，每部分分别计算相邻像素和被测像素差的绝对值之和，再将这两部分计算的值相加，在计算的过程中，充分考虑了像素内容，更为精确地区分像素局部区域的纹理度高低，进一步提高了选择嵌入像素的精度，从而改善可逆信息隐藏的失真度。图4表示各像素之间的位置关系。

自然图像中，像素值间存在着很强的相似性，相邻像素的相似度随着像素距离的增加而逐渐减小，邻近像素在统计意义上应有最强的相关性，当前像素通过其邻近像素来预测的准确度也应最高。相比之前的MED方法考虑了被测像素相邻的三个像素，如图1所示。菱形预测方法考虑了被测像素周围相邻的四个像素值。本文所提出的全封闭的预测方法考虑到了被测像素周围所有相邻的像素值，更好地利用了像素之间的相关性，为选择被嵌像素提高了准确性。像素值x是要进行预测的像素，将周围相邻的像素分别用八个像素来进行表示 $\left\{x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8\right\}$，这八个像素值的平均值就是像素x的预测值，如图4所示：

Figure 4. Closed prediction method

图4. 全封闭预测方法

基于成对预测误差扩展嵌入数据的可逆数据隐藏方法，将要移动的像素分为可嵌入像素和不可嵌入像素两大类。可嵌入像素通过修改预测误差值来嵌入秘密信息；但是，不可嵌入像素不仅没有携带秘密信息，而且还需要进行移位。为了提高算法的嵌入容量，通常希望最大化可嵌入像素的数量，同时最小化那些不可嵌入的像素。那么，进行判断的前提首先要有一个精确的像素预测值，因为无论是后续的计算误差能量估计的方法需要用到像素预测值，而且误差能量估计方法的计算直接影响到了我们对目前像素值它是否可以进行嵌入像素的判断，减少不可嵌入像素的数量。

3.2. 误差能量估计

对于大多数自然图像，预测误差在当前处理像素周围的区域具有很强的相关性。现有的方法未能全面的依赖图像内容，可以进一步利用这种相关性和尽可能多的依赖于图像的内容来消除可能不可以嵌入的预测误差 [19]。误差能量估计计算如下：

$\Delta =d_h+d_v$

$d_h=\left|x_2-x\right|+\left|x_4-x\right|+\left|x_7-x\right|+\left|x_5-x\right|$

$d_v=\left|x_1-x\right|+\left|x_3-x\right|+\left|x_6-x\right|+\left|x_8-x\right|$

这里需要注意x的下标表示的是当前处理像素的上下文位置如图3所示。

一旦得到误差能量Δ的估计值，可以基于Δ将预测误差分类为可嵌入和不可嵌入的误差。Δ的值较大表明相应的预测误差也较大，很可能是不能嵌入的预测误差。因此，在可以嵌入所有秘密信息的前提下，需要尽可能地选择较小的误差能量，来获得最好的图像质量。也就是说，要尽可能地选择在相对平滑的区域里嵌入秘密信息 [20]，相对粗糙的区域保持不变。

3.3. 嵌入过程

在这一节中，将详细描述秘密信息嵌入的过程，图像恢复和提取 [21] 的过程是嵌入的逆过程，就不详细描述了。

因为二维预测误差直方图比一维预测误差直方图可以更好地反映图像数据中的复杂依赖性，因此利用二维预测误差直方图是有价值的。在这项工作中，基于二维预测误差直方图的修改策略称为双向预测误差扩展，其中通过扩展和转移直方图的预测误差来实现数据嵌入。成对PEE比传统的PEE在高维空间中可以更自然延伸。事实上，合理的直方图修改策略有助于提高可逆数据隐藏的性能。

基于成对预测误差的算法第一步需要先将预测误差进行成对匹配，然后再根据嵌入策略嵌入秘密信息。首先，按照特定的序列扫描图像(第一行像素除外)，将扫描像素收集成一维序列，按照3.1的方法计算像素的预测误差，将预测误差采用全封闭的预测方法，得到像素预测值，根据公式计算预测误差，生成预测误差系列 $\left(e_1,\cdots e_n\right)$，将它转化成新的序列 $\left(e_1,\cdots e_{n/2}\right)$，选取的成对预测误差就是其中的 $e_i=\left(e_{2i-1},e_{2i}\right)$。接下来对于像素选择策略而言。只有误差能量小于预设的阈值T的预测误差选择生成二维预测误差直方图，其次，构造溢出位置图数据嵌入后像素的灰度值可能超出范围。为了防止这种情况，对图像进行预处理，将这些像素值调整到一个可靠的范围。由于方法中对每个像素值的修改最多为1，所以只需要按以下方式调整边缘值像素。像素值是255的话，将修改为254；如果是0，就修改为1。并且，每个修改后的像素在位置图中标记为1，而其他像素标记为0。然后对位置图进行无损压缩 [22]，进一步减小其大小。

二维预测误差直方图的划分是根据成对的预测误差生成二维预测误差直方图，以第一象限为例。首先，直方图可以分成三个部分，如图5所示，以对角线的坐标点为分界线，对角线的坐标点为一部分，还有对角线上下两部分一共三部分。通过2D-PEH划分，坐标变换三角形区域转换为矩形。在图7的左图中显示了第一象限中的2D-PEH划分，并且对于右下三角形区域(绿点)，该区域中的每个 $\left(x,y\right)$ 都被转换为 $\left(x^{\prime },y^{\prime }\right)$ 为将对角线上下两部分进行变换公式如下：

$\{\begin{array}{l}{x}^{\prime }=x-y-1\hfill \\ y^{\prime }=y-b\hfill \end{array}$

Figure 5. Area division

图5. 区域划分

在成对预测误差扩展生成的坐标系中，找到一条最佳的路径来进行数据的嵌入。给定(n, m)，通过公式来确定最佳扩展路径。其中，P (n, m)表示在(0, 0)开始和在(n, m)结束的路径，q是给定的容量， $b\in \left\{0,1,2,3\right\}$，n = 7， 0 ≤ m ≤ 7。

需要根据在划分的直方图中确定的最佳路径，可以将坐标系的象限分成两部分，最佳路径上边部分的预测误差进行嵌入而且只进行向上嵌入秘密信息，最佳路径下边部分的预测误差只向右嵌入秘密信息，最佳路径以外的不做任何变化。嵌入的时候采用双层嵌入，将图像分为阴影和空白两部分，如图6所示，这里详细描述空白部分的嵌入过程，空白部分嵌入完成后，再进行阴影部分的嵌入，直到所有的秘密信息都嵌入。

Figure 6. Shadows and white space

图6. 阴影和空白部分

为了更好地提取和恢复图像，辅助信息和压缩溢出位置图也需要进行嵌入，辅助信息包括：

1) 参数b (2位)、T (2位)、m (2位)

2) 最优扩展路径P (7, m) (m + 7位)

3) 压缩溢出位置图的长度(18位)

4) 压缩溢出位置图

5) 最后修改像素对的嵌入位置(16位)

在方法中，将这辅助信息依次嵌入到原图像素第一行的最低有效位中，在数据提取时首先提取。第一行像素被替换的LSB [23] 和利用霍夫曼编码压缩的位置图将作为有效载荷的一部分嵌入到原图图像中。也就是说，嵌入的有效负载包括三个部分：替换的LSB、压缩的位置图和秘密消息。

4. 实验结果

在这一节中，通过与传统的预测误差扩展、Sachnev等人 [24] 的方法、Ou等人的方法 [25] 和Xiao [26] 等人最近提出的成对预测误差扩展方案进行比较，来评估方法的嵌入性能。使用标准格式为JEPG的大小的灰度图像进行比较，包括Lena、Baboon、Barbara、Airplane、Elaine、Lake、Boat、和Peppers八张图片，从USC-SIPI图像数据库中下载得到的。根据一些实验数据，可以看出，在各种容量下，所提出的方法优于三种比较方法。更具体地说，表1和表2给出了用于这四种方法的嵌入容量为10,000位和20,000位的峰值信噪比。

从表1中可以看出所提出的方法，除了较为平滑的图像Airplane和目前的方法相比峰值信噪比几乎相似外，其他的图像峰值信噪比有了显著提高，平均增加了0.82 db。表2显示出当嵌入秘密信息的大小为20,000位时，峰值信噪比平均增加了1.25 db。从表2中发现，本文所提出的方法对图像较为粗糙和嵌入容量较大时，图像嵌入之后的视觉质量更好。图像较为平滑的，性能提高不是很明显。图7和图8是嵌入20,000位时，选取了Pepper、Baboon、Lena、Lake原图和嵌入之后的图像对比。可以看出嵌入之后的图像和原图像几乎无差别。

Table 1. When embedding 10,000 bits, the proposed method compares the peak signal-to-noise ratio with the method of Ou et al.

表1. 嵌入10,000位时，所提出的方法与Ou等人的方法比较峰值信噪比

Table 2. When embedding 20,000 bits, the proposed method compares the peak signal-to-noise ratio with the method of Ou et al.

表2. 嵌入20,000位时，所提出的方法与Ou等人的方法比较峰值信噪比

Figure 7. Original images of Baboon, Peppers, Lena, Lake

图7. Baboon、Peppers、Lena、Lake的原图

Figure 8. Baboon, Peppers, Lena, Lake after embed 20,000

图8. 嵌入20,000位之后的Baboon、Peppers、Lena、Lake的图片

Figure 9. Hu’s method, Xiao’s method, and the method proposed in this article are used to compare performance on different pictures

图9. Hu的方法、Xiao的方法、本文提出的方法分别在不同的图片上作性能比较

对于Xiao等人基于成对预测扩展的方法，我们的算法是对他们工作的直接改进。在图9中可以观察到，除了粗糙的图像Baboon之外，可以为每个图像提供一个更大的PSNR，无论EC是什么。Sachnev等人的方法是基于PEE结合嵌入位置选择策略。对于该方法，使用四个相邻像素的整数平均值来预测像素值。此外，使用排序技术基于局部方差的大小记录预测误差，一个像素如果其局部有较小的方差，则应预先嵌入该方法性能良好，优于一些典型的RDH方案。经过实验证明，在大多数情况下，的方法比这种性能良好的方法要好。然而，对于一些图像，当EC接近其最大值时(例如，当EC大于10,000位时，对于图像Baboon，当EC大于47,000位时，对于Airplane)，Sachnev等人的方法可以实现更大的PSNR。原因是，在这种情况下，由于EC是高的，不能很好地利用像素相关性的优势。此外，在这种情况下，光滑的图像是不够的，必须使用粗糙的图像来嵌入数据。这也不利于嵌入性能。但是，对于中等程度的EC，我们的方法更好。参考表1，我们的方法将Sachnev等人的EC提高了3.68 dB。

5. 实验结果

本文提出了一种改进的基于2D-PEH成对嵌入的预测误差扩展的可逆数据隐藏方案，作为成对预测误差扩展方法(Xiao)的改进。通过紧密联系被测像素之间的相关性，考虑了一种全新的全封闭式的预测方法，提高了选择嵌入像素的准确性。此外，本文更多地依赖于图像的内容，提出了误差能量估计算法，可以避免可能不可以进行嵌入的预测误差。并且给出了实验结果，证明了该方案在容量失真性能方面的优越性。该方法的主要优点是在粗糙图像上和嵌入大容量时有显著提高。然而，对于较为平滑的图像提高不是很明显，因为在较为平滑的图像上先前的算法对像素选择上和所提出的算法基本相同。而粗糙的图像比先前的算法在像素选择上提高了准确率。最后，在未来工作的一个可能方向是提高平滑图像上的图像质量。