开放科学（资源服务）标志码（OSID）：

0 概述

可逆数据隐藏是一种只需要对载体图像的像素进行轻微修改，并将数据隐藏在载体图像中的技术。该技术从被嵌入数据的载体图像中无损地提取数据，同时完全恢复出原载体图像^[1-2]。可逆数据隐藏技术在医学图像^[3-5]、军事图像、法律取证等领域中传输和使用数据时，能够确保数据不失真^[6-8]。

早期的可逆数据隐藏技术^[9-11]通过压缩载体图像的一个位平面来创造空间，并进行数据嵌入，但其可逆性高度依赖于压缩算法的性能。文献[12]提出DE算法，通过对载体图像进行整数小波变换，同时计算并扩展差值，以嵌入可逆数据。为充分利用自然图像的冗余空间，预测误差扩展（Prediction Error Expansion，PEE）^[13]采用预测误差代替DE算法中的差值，受到许多研究人员的关注^[14-16]。

文献[17]结合PEE提出像素值排序（Pixel Value Ordering，PVO）算法。该算法将载体图像分成非重叠同等大小的块，并对块内的像素进行排序，通过计算预测误差为块中最大（小）值与次大（小）值的差值，以修改最大（小）值嵌入数据。在PVO算法中，预测误差等于1的图像块被用于嵌入数据，预测误差等于0的图像块未被利用。文献[18]提出改进的PVO（IPVO）算法，根据最大（小）值和次大（小）值的空间位置预测误差，误差等于0和误差等于1的图像块都被用于嵌入数据，以提高PVO的嵌入容量。文献[19]提出PVO-K，同时修改k个最大（小）值以嵌入1 bit数据，当k=1时，PVO-K退化为PVO。文献[20]提出PPVO，打破了PVO中分块的限制，将每个像素作为一个嵌入单元。文献[21]将PVO生成的预测误差两两分为一组，采用2D的方式成对修改误差以嵌入数据。研究人员利用可逆约束对像素进行动态预测，从而提升PVO的嵌入容量^[22]。为获得更大的嵌入容量，文献[23]将图像块的复杂度分为m个级别，根据不同级别动态地修改块内像素的个数。

本文提出基于像素值排序的块再分算法。构建12种分块模式将1个图像块分为2个子块，对每个子块采用不同的扫描顺序及嵌入策略，以充分利用图像块中每个像素之间的相关性。此外，设计一种局部复杂度的计算方式，当嵌入数据时，只处理复杂度小于阈值的图像块，提高嵌入数据后图像的视觉质量。

1 基于像素值排序的可逆数据隐藏算法

PVO算法^[17]通过对图像进行分块，并将块内的n个像素按照升序排列，使得$ {x}_{\sigma \left(1\right)}\le {x}_{\mathrm{\sigma }\left(2\right)}\le \cdots \le {x}_{\sigma \left(n\right)} $，在此基础上，计算预测误差$ {e}_{\mathrm{m}\mathrm{a}\mathrm{x}}={x}_{\sigma \left(n\right)}-{x}_{\sigma (n-1)} $。PVO和IPVO算法的预测误差直方图如图 1所示。

POV预测误差e_max的直方图误差范围在$ \left(0, +\mathrm{\infty }\right) $，峰值点为1。PVO算法通过e_max=1来嵌入数据。

文献[18]提出改进的像素值排序（IPVO）算法，其目的是利用在PVO算法中被放弃的最大（小）值与次大（小）值相等的图像块来嵌入数据。IPVO计算得到的预测误差d_max=x_u-x_v，其中$ u=\mathrm{m}\mathrm{i}\mathrm{n}\left(\sigma \right(n), \sigma (n-1\left)\right) $，$ v=\mathrm{m}\mathrm{a}\mathrm{x}\left(\sigma \right(n), \sigma (n-1\left)\right) $。IPOV预测的误差直方图如图 1（b）所示，预测误差d_max的直方图误差范围在$ \left(-\mathrm{\infty }, +\mathrm{\infty }\right) $，峰值点为0。IPVO利用d_max=0和d_max=1来嵌入数据，大幅增大了PVO的嵌入容量。

当数据被嵌入到图像块后，图像块的最大值被修改为$ {x}_{\sigma \left(n\right)}^{'}={x}_{\sigma \left(n\right)}+b $，最小值被修改为$ {x}_{\sigma \left(n\right)}^{'}={x}_{\sigma \left(n\right)}-b $，其他像素保持不变，保证了算法的可逆性。在提取过程中，水印误差为$ {d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{'}={x}_{u}^{'}-{x}_{v}^{'} $，如果$ {d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{'}\in \left\{\mathrm{1, 2}\right\} $，则提取的数据$ b={d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{'}-1 $，如果$ {d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{'}\in \left\{-\mathrm{1, 0}\right\} $，则提取的数据$ b=-{d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{'} $，最终恢复的原始像素$ {x}_{\sigma \left(n\right)}={x}_{\sigma \left(n\right)}^{'}-b $。

IPVO在3×3图像块最大值上嵌入和提取数据的过程如图 2所示。

当原始块的9个像素排序后，最大值$ {x}_{\sigma \left(9\right)} $为158，次大值$ {x}_{\sigma \left(8\right)} $为157，其中$ \sigma \left(9\right)=6 $，$ \sigma \left(8\right)=9 $，预测误差$ {d}_{\mathrm{m}\mathrm{a}\mathrm{x}}={x}_{\sigma \left(9\right)}-{x}_{\sigma \left(8\right)}={x}_{6}-{x}_{9}=1 $。假设嵌入数据b=1，则$ {d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{'}={d}_{\mathrm{m}\mathrm{a}\mathrm{x}}+b $，因此，最大值$ {x}_{\sigma \left(9\right)} $被修改为$ {x}_{\sigma \left(9\right)}^{'}={x}_{\sigma \left(9\right)}+b=158+1=159 $。在提取数据的过程中，IPVO同样对水印块的像素进行排序，水印块的位置序列$ {\sigma }^{'} $与原始块的位置序列$ \sigma $相同，水印误差$ {d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{'}={x}_{\sigma \left(9\right)}^{'}-{x}_{\sigma \left(8\right)}^{'}={x}_{6}^{'}-{x}_{9}^{'}=2 $。因为$ {d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{'}\in \left\{\mathrm{1, 2}\right\} $，所以提取数据$ b={d}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{'}-1=1 $，同时原始像素被恢复为$ {x}_{\sigma \left(9\right)}={x}_{\sigma \left(9\right)}^{'}-b=159-1=158 $。

2 本文算法 2.1 分块模式

分块模式将原始图像分成3×3不重叠的块，将每一个块内包含的9个像素划分为2个像素集，即像素集A和像素集B。像素集A包含4个像素，采用次大像素值预测最大像素值和次小像素值的方法。像素集B包含当前块内剩下的5个像素，采用中值像素分别预测其余4个像素的方法。这样的划分方式共有$ {\mathrm{C}}_{9}^{4} $种，其目的是为了更充分利用像素之间的相关性。由于像素之间的相关性越高，产生的预测误差直方图分布越集中，因此可被用于嵌入数据的像素就越多。本文考虑到像素与像素之间的距离越近，其相关性越好，因此，像素集的划分应尽可能地让像素集内的像素彼此相连。在这$ {\mathrm{C}}_{9}^{4} $种划分方式中，12种细分块的模式如图 3所示。

2.2 数据嵌入与提取

本文采用图 3中的模式1进行数据嵌入与提取。

2.2.1 数据嵌入

数据分块示意图如图 4所示。

在数据嵌入过程中，对于图 4中的子块A，首先逐行读取子块A的像素，获得像素序列$ \left\{{p}_{1}, {p}_{2}, {p}_{4}, {p}_{5}\right\} $，然后将其按照升序排列，得到$ \left\{{p}_{\omega \left(1\right)}, {p}_{\omega \left(2\right)}, {p}_{\omega \left(3\right)}, {p}_{\omega \left(4\right)}\right\} $，其中，$ \omega $是一个双射，使得$ {p}_{\omega \left(1\right)}\le {p}_{\omega \left(2\right)}\le {p}_{\omega \left(3\right)}\le {p}_{\omega \left(4\right)} $。如果像素$ {p}_{\omega \left(w\right)}={p}_{\omega \left(r\right)} $，并且$ w < r $，则$ \omega \left(w\right) < \omega \left(r\right) $，计算预测误差$ {e}_{1, j} $，如式（1）所示：

$ {e}_{1, j}={p}_{u}-{p}_{v} $

(1)

其中：$ j\in \left\{\mathrm{1, 2}\right\} $；当j=1时，$ u=\mathrm{m}\mathrm{i}\mathrm{n}\left\{\omega \left(j\right), \omega \left(2\right)\right\} $，$ v=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\omega \left(j\right), \omega \left(2\right)\right\} $；当j=2时，$ u=\mathrm{m}\mathrm{i}\mathrm{n}\left\{\omega (j+1), \omega \left(4\right)\right\} $，$ v=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\omega (j+1), \omega \left(4\right)\right\} $。

如果b为嵌入的数据，$ b\in \left\{\mathrm{0, 1}\right\} $，那么计算得到的水印误差$ {e}_{1, j}^{'} $如式（2）所示：

$ {e}_{1, j}^{'}=\left\{\begin{array}{l}{e}_{1, j}-b\begin{array}{c}, {e}_{1, j}=0\end{array}\\ {e}_{1, j}+b\begin{array}{c}, {e}_{1, j}=1\end{array}\\ {e}_{1, j}-1\begin{array}{c}, {e}_{1, j} < 0\end{array}\\ {e}_{1, j}+1\begin{array}{c}, {e}_{1, j} > 1\end{array}\end{array}\right. $

(2)

相应地，当数据被嵌入后，子块A的最小像素$ {p}_{\omega \left(1\right)} $被修改为：

$ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}^{'}=\left\{\begin{array}{l}{p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}-b, {e}_{1, j}=1\ \mathrm{o}\mathrm{r}\ {e}_{1, j}=0\\ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}-1, {e}_{1, j} > 1\ \mathrm{o}\mathrm{r}\ {e}_{1, j} < 0\end{array}\right. $

(3)

其中：$ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}={p}_{\omega \left(1\right)} $；$ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}^{'}={p}_{\omega \left(1\right)}^{'} $。

最大像素$ {p}_{\omega \left(4\right)} $被修改为：

$ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}^{'}=\left\{\begin{array}{l}{p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}+b, {e}_{1, j}=1\ \mathrm{o}\mathrm{r}\ {e}_{1, j}=0\\ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}+1, {e}_{1, j} > 1\ \mathrm{o}\mathrm{r}\ {e}_{1, j} < 0\end{array}\right. $

(4)

其中：$ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}={p}_{\omega \left(4\right)} $；$ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}^{'}={p}_{\omega \left(4\right)}^{'} $。

对于子块B，采用从上向下和从右至左的顺序读取像素，得到像素序列$ \left\{{p}_{3}, {p}_{6}, {p}_{9}, {p}_{8}, {p}_{7}\right\} $，将其按照升序排列得到$ \left\{{p}_{\tau \left(1\right)}, {p}_{\tau \left(2\right)}, {p}_{\tau \left(3\right)}, {p}_{\tau \left(4\right)}, {p}_{\tau \left(5\right)}\right\} $，其中，$ \tau $是双射，使得$ {p}_{\tau \left(1\right)}\le {p}_{\tau \left(2\right)}\le {p}_{\tau \left(3\right)}\le {p}_{\tau \left(4\right)}\le {p}_{\tau \left(5\right)} $。如果$ {p}_{\tau \left(w\right)}={p}_{\tau \left(r\right)} $，并且$ w < r $，则$ \tau \left(w\right) < \tau \left(r\right) $，预测误差$ {e}_{2, j} $如式（5）所示：

$ {e}_{2, j}={p}_{s}-{p}_{t} $

(5)

其中：$ j\in \{\mathrm{1, 2}, \mathrm{3, 4}\} $；当$ j\in \left\{\mathrm{1, 2}\right\} $时，$ s=\mathrm{m}\mathrm{i}\mathrm{n}\left\{\tau \right(j), \tau (3\left)\right\} $，$ t=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\tau \right(j), \tau (3\left)\right\} $；当$ j\in \left\{\mathrm{3, 4}\right\} $时，$ s=\mathrm{m}\mathrm{i}\mathrm{n}\left\{\tau \right(j+1), \tau (3\left)\right\} $，$ t=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\tau \right(j+1), \tau (3\left)\right\} $。

本文根据式（2）修改预测误差$ {e}_{2, j} $以嵌入数据b。当$ j\in \left\{\mathrm{1, 2}\right\} $时，像素$ {p}_{\tau \left(j\right)} $根据式（3）被修改为$ {p}_{\tau \left(j\right)}^{'} $，其中，$ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}={p}_{\tau \left(j\right)} $，$ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}^{'}={p}_{\tau \left(j\right)}^{'} $；当$ j\in \left\{\mathrm{3, 4}\right\} $时，像素$ {p}_{\tau (j+1)} $根据式（4）被修改为$ {p}_{\tau (j+1)}^{'} $，其中，$ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}={p}_{\tau (j+1)} $，$ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}^{'}={p}_{\tau (j+1)}^{'} $。

本文算法将3×3的图像块修改为可以嵌入6 bit图像块，与PVO和IPVO等算法相比，大幅提升了嵌入容量。IPVO和本文算法的预测误差值对比如图 5所示。图 5选取了Lena的3×3的图像块，如果采用IPVO算法，则只能得到2个可以被用于嵌入数据的预测误差。如果使用本文算法，将得到6个可以被用来嵌入数据的预测误差。

2.2.2 数据提取

在数据的提取过程中，假设水印块A排序后的像素序列为$ \left\{{p}_{\omega \left(1\right)}^{'}, {p}_{\omega \left(2\right)}^{'}, {p}_{\omega \left(3\right)}^{'}, {p}_{\omega \left(4\right)}^{'}\right\} $，已知$ {p}_{\omega \left(1\right)}^{'}\le {p}_{\omega \left(1\right)} $，$ {p}_{\omega \left(2\right)}^{'}={p}_{\omega \left(2\right)} $，$ {p}_{\omega \left(3\right)}^{'}={p}_{\omega \left(3\right)} $，$ {p}_{\omega \left(4\right)}^{'}\ge {p}_{\omega \left(4\right)} $，即水印块A的像素按升序排列后与原始块A的像素排序后得到的位置序列相同。因此，原始块A的嵌入算法是可逆的，同理，原始块B的嵌入算法也是可逆的。水印块A的预测误差$ {e}_{1, j}^{'}={p}_{u}^{'}-{p}_{v}^{'} $，其中，j、u、v的定义与式（1）相同。提取得到的数据b如式（6）所示：

$ b=\left\{\begin{array}{l}{e}_{1, j}^{'}-1, {e}_{1, j}^{'}\in \left\{\mathrm{1, 2}\right\}\\ -{e}_{1, j}^{'}, {e}_{1, j}^{'}\in \left\{0, -1\right\}\end{array}\right. $

(6)

将水印块A中的像素$ {p}_{\omega \left(1\right)}^{'} $恢复为$ {p}_{\omega \left(1\right)} $，如式（7）所示：

$ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}=\left\{\begin{array}{l}{p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}^{'}+{e}_{1, j}^{'}-1, {e}_{1, j}^{'}\in \left\{\mathrm{1, 2}\right\}\\ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}^{'}-{e}_{1, j}^{'}, {e}_{1, j}^{'}\in \left\{0, -1\right\}\\ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}^{'}+1, {e}_{1, j}^{'} < -1\ \mathrm{o}\mathrm{r}\ {e}_{1, j}^{'} > 2\end{array}\right. $

(7)

其中：$ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}={p}_{\omega \left(1\right)} $；$ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}^{'}={p}_{\omega \left(1\right)}^{'} $。

根据式（8）将像素$ {p}_{\omega \left(4\right)}^{'} $恢复为$ {p}_{\omega \left(4\right)} $：

$ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}=\left\{\begin{array}{l}{p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}^{'}-{e}_{1, j}^{'}+1, {e}_{1, j}^{'}\in \left\{\mathrm{1, 2}\right\}\\ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}^{'}+{e}_{1, j}^{'}, {e}_{1, j}^{'}\in \left\{0, -1\right\}\\ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}^{'}-1, {e}_{1, j}^{'} < -1\ \mathrm{o}\mathrm{r}\ {e}_{1, j}^{'} > 2\end{array}\right. $

(8)

其中：$ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}={p}_{\omega \left(4\right)} $；$ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}^{'}={p}_{\omega \left(4\right)}^{'} $。

对于水印块B，假设像素按照升序排列后得到的像素序列为$ \left\{{p}_{\tau \left(1\right)}^{'}, {p}_{\tau \left(2\right)}^{'}, {p}_{\tau \left(3\right)}^{'}, {p}_{\tau \left(4\right)}^{'}, {p}_{\tau \left(5\right)}^{'}\right\} $，同样计算预测误差$ {e}_{2, j}^{'}={p}_{s}-{p}_{t} $，其中，j、s、t的定义同式（5）相同。本文根据式（6）提取数据b，恢复出块内除中值像素外的所有像素。当$ j\in \left\{\mathrm{1, 2}\right\} $时，根据式（7）将$ {p}_{\mathrm{\tau }\left(j\right)}^{'} $恢复为$ {p}_{\tau \left(j\right)} $，其中，$ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}={p}_{\tau \left(j\right)} $，$ {p}_{\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}}^{'}={p}_{\tau \left(j\right)}^{'} $；当$ j\in \left\{\mathrm{3, 4}\right\} $时，根据式（8）将$ {p}_{\tau (j+1)}^{'} $恢复为$ {p}_{\tau (j+1)} $，其中，$ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}={p}_{\tau (j+1)} $，$ {p}_{\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{t}\mathrm{e}\mathrm{r}}^{'}={p}_{\tau (j+1)}^{'} $。

2.2.3 数据嵌入与提取样例

本文算法的数据嵌入与提取过程如图 6所示。数据嵌入过程首先将原始块分为子块A和子块B，对于子块A，逐行扫描像素，排序得到像素序列$ {p}_{\omega }=\left\{\mathrm{159, 160, 160, 161}\right\} $。根据式（1）计算预测误差$ {e}_{\mathrm{1, 1}} $和$ {e}_{\mathrm{1, 2}} $，根据式（3）和式（4）修改最大和最小像素嵌入b₁和b₂。对于子块B，从上向下和从右到左扫描像素，排序得到像素序列$ {p}_{\mathrm{\tau }}=\{\mathrm{159, 160, 160}, $ $ \mathrm{161, 163}\} $，根据式（5）计算4个预测误差为$ {e}_{\mathrm{2, 1}} $、$ {e}_{\mathrm{2, 2}} $、$ {e}_{\mathrm{2, 3}} $和$ {e}_{\mathrm{2, 4}} $，根据式（3）和式（4）将$ {p}_{8} $、$ {p}_{6} $、$ {p}_{5} $、$ {p}_{9} $修改为$ {p}_{8}^{\mathrm{\text{'}}} $、$ {p}_{6}^{\mathrm{\text{'}}} $、$ {p}_{5}^{\mathrm{\text{'}}} $、$ {p}_{9}^{\mathrm{\text{'}}} $，以嵌入b₃、b₄和b₅。最后将两个子块内所有被修改的像素更新到原始块对应的位置上，以生成水印块。

数据提取过程与数据嵌入过程相同，首先对水印块进行分块，得到水印像素序列$ {p}_{\omega }^{'} $和$ {p}_{\tau }^{'} $，然后分别计算这两个水印序列的预测误差，对于$ {p}_{\omega }^{'} $，计算误差$ {e}_{\mathrm{1, 1}}^{\mathrm{\text{'}}} $和$ {e}_{\mathrm{1, 2}}^{\mathrm{\text{'}}} $，对于$ {p}_{\mathrm{\tau }}^{'} $，计算误差$ {e}_{\mathrm{2, 1}}^{\mathrm{\text{'}}} $、$ {e}_{\mathrm{2, 2}}^{\mathrm{\text{'}}} $、$ {e}_{\mathrm{2, 3}}^{\mathrm{\text{'}}} $和$ {e}_{\mathrm{2, 4}}^{\mathrm{\text{'}}} $，根据式（6）提取出b₁、b₂、b₃、b₄和b₅，根据式（7）和式（8）恢复出原始像素$ {p}_{2} $、$ {p}_{3} $、$ {p}_{8} $、$ {p}_{6} $、$ {p}_{5} $和$ {p}_{9} $，最后将所有恢复的像素更新到水印块的相对位置上，得到原始块。

2.3 局部复杂度

本文考虑到自然图像中包含大量粗糙块，如果对这些粗糙块进行数据的嵌入操作，将会产生大量的移位像素，从而降低图像的嵌入性能。在文献[17]中，一个块的局部复杂度定义为当前块的次大像素值与次小像素值的差值。然而，当分块较小时，参与排序的像素过少，难以反映灰度值的变化趋势，因此，文献[17]计算的局部复杂度不准确。

由于自然图像的相邻像素呈高度相关关系，因此可以推断相邻图像块的复杂度也具有高度相关关系。一个光滑块周围的图像块也光滑，一个粗糙块周围的图像块必定粗糙。本文定义一个图像块的上下文像素为其所有相邻块中距离该块最近的像素。图像块的上下文像素集C如式（9）所示：

$ \begin{array}{l}C=\{{p}_{i-1, j+m}, {p}_{i+3, j+m}, {p}_{i+n, j-1}, {p}_{i+n, j+3}|\\ \left.m=-\mathrm{1, 0}, \mathrm{1, 2}, 3\text{；}n=\mathrm{0, 1}, 2\right\}\end{array} $

(9)

上下文像素集C的方差被定义为图像块的局部复杂度N_NL，如式（10）所示：

$ {N}_{\mathrm{N}\mathrm{L}}=\sqrt{\frac{\sum\limits _{m=-1}^{3}\left\{\right({p}_{i-1, j+m}{-\stackrel{-}{p})}^{2}+\left({p}_{i+3, j+m}{-\stackrel{-}{p})}^{2}\right\}+\sum\limits _{n=0}^{2}\left\{\right({p}_{i+n, j-1}{-\stackrel{-}{p})}^{2}+\left({p}_{i+n, j+3}{-\stackrel{-}{p})}^{2}\right\}}{16}} $

(10)

其中：$ \stackrel{-}{p} $为像素集C内像素的平均值。

一个3×3图像块的上下文像素示意图如图 7所示。

如果一个图像块的N_NL小于给定的阈值T，则是平滑块。本文按照2.2节的方式对平滑块进行块再分，以嵌入数据。如果一个图像块的N_NL大于等于给定的阈值T，则为复杂块，对于复杂块不做任何处理。

3 算法流程 3.1 嵌入算法

嵌入算法主要分为以下3个步骤：

1）图像分块与位置地图的构建。首先将原始图像中除第一行像素以外的所有像素分为3×3不重叠的块$ \left\{{X}_{1}, {X}_{2}, \cdots , {X}_{N}\right\} $，其中，N为块的总数。如果一个像素为255或者0，则在嵌入过程中有可能被修改为256或者-1，会造成上溢或者下溢。为解决该问题，若X_i内含有像素255或者0，将其标记为L_LM（i）=1；否则标记为L_LM（i）=0。最后将所有的L_LM，即图像的位置地图压缩成一个长度为L_CLM的比特流串。

2）秘密数据嵌入。在执行数据嵌入的过程中，嵌入算法只对所有L_LM（i）=0的图像块进行嵌入。对于每个L_LM（i）=0的图像块X_i，首先计算它的局部复杂度N_NL。如果$ {N}_{\mathrm{N}\mathrm{L}}\ge T $，则为粗糙块，不做任何处理；如果$ {N}_{\mathrm{N}\mathrm{L}} < T $，则为平滑块。按照2.2.1节提出的方法进行块再分，根据式（1）和式（5）计算误差$ {e}_{1, j} $和$ {e}_{2, j} $，根据式（2）进行误差的扩展或者移位以嵌入秘密数据。当所有的秘密数据都被嵌入完成后，该步骤将停止，最后一个嵌入数据的图像块被记为X_end。

3）辅助数据和位置地图的嵌入。为实现数据的可逆恢复，辅助数据和位置地图被嵌入到图像第一行像素的最低有效位（Least Significant Bit，LSB）中。辅助数据为压缩位置地图的长度L_CLM、阈值T、块尺寸以及结束位置X_end。利用这些数据替换图像第一行的LSB，并将替换掉的LSB压缩成比特流S_LSB，最后按照步骤2将其嵌入到图像的剩余区域中，即$ \left\{{X}_{\mathrm{e}\mathrm{n}\mathrm{d}}, {{X}_{\mathrm{e}\mathrm{n}\mathrm{d}}}_{+1}, \cdots , {X}_{N}\right\} $。

3.2 提取算法

提取算法主要分为以下3个步骤：

1）辅助数据与位置地图的提取。在解码端，提取算法读取水印图像第一行像素的LSB位，提取L_CLM、阈值T、块尺寸、结束位置X_end以及压缩的位置地图，并将其解压得到位置地图。

2）数据提取。首先将水印图像除第一行以外的所有像素分为3×3的块，然后查找每个块的标记L_LM（i），计算L_LM（i）=0的水印块复杂度N_NL，最后将满足L_LM（i）=0并且$ {N}_{\mathrm{N}\mathrm{L}} < T $的水印块按照2.2节的方法进行再分块，计算水印误差$ {e}_{1, j}^{'} $和$ {e}_{2, j}^{'} $，并根据式（6）提取出秘密数据和压缩的比特流S_LSB。

3）图像恢复。首先将提取的秘密数据按照2.2.2节的方法恢复出图像的原始块$ \left\{{X}_{1}, {X}_{2}, \cdots , {X}_{N}\right\} $，然后解压S_LSB，将其替换掉图像第一行像素的LSB位，最后恢复出整个图像。

4 实验结果与分析

本文利用MATLAB R2018a软件在6幅512×512像素的灰度图像上，对比现有的基于像素值排序的可逆数据隐藏算法与本文算法的性能。6张测试图如图 8所示，这些图像都是从USC-SIPI数据库中下载获得，在嵌入过程中数据b是随机生成的0，1序列。

本文在12种分块模式下对Lena图和Baboon图进行峰值信噪比（Peak Signal to Noise Ratio，PSNR）对比，结果如图 9所示。从图 9可以看出，当采用分块模式1时，图像的PSNR性能最优，因此，本文算法的最优模式为模式1。

在最优模式下不同算法的PSNR对比如图 10所示。从图 10可以看出，在大多数情况下，本文算法的PSNR都最优，并且随着嵌入容量的增大，PSNR的增益更明显。因此，嵌入容量越大，本文算法的性能越优。

从图 10可以看出，当Baboon图的嵌入容量小于8 000 bit以及Barbara图的嵌入容量小于12 000 bit时，本文算法的PSNR不是最高，其原因主要有两个：1）本文算法未根据嵌入容量自适应选择图像块大小，即不能在嵌入容量较低时，采用更大的5×5图像块进行再分块，而对于这类复杂图像，相邻像素联系不紧密，使得对平滑块的选择更为精确，需要更多的上下文像素来计算局部复杂度，因此，本文算法的PSNR不是最高；2）以上对比的其他算法在实验过程中都通过穷举搜索法选择最优参数，尽管这种方式可以提升PSNR，但是也会增大计算复杂度。

当嵌入容量为1 000 bit时，不同算法在6张图上的PSNR对比如表 1所示。从表 1可以看出，相比其他算法，本文算法的平均PSNR增益分别为1.22 dB、2.00 dB、2.08 dB、1.99 dB、1.68 dB、0.70 dB。这表明本文算法在低嵌入容量下能够有效提升嵌入数据后的图像质量。

不同算法的最大嵌入容量对比如图 11所示。分块越小，最大嵌入容量就越大。在文献[17]中，当采用2×2分块时，图像的嵌入容量达到了最大值。本文算法是在3×3固定大小的分块上实现的。从图 11可以看出，本文算法的最大嵌入容量在某些图像上是最大的，其原因为对于一个3×3大小的图像块，最多可以嵌入6 bit数据，充分地利用了图像块内的每一个像素。不同算法的计算复杂度对比如表 2所示。

文献[17]通过穷举搜索出三个最优参数，即块尺寸$ {r}_{L}，{c}_{L} $和阈值T_L，其中$ {r}_{L}\in \left\{\mathrm{2, 3}, \mathrm{4, 5}\right\} $，$ {c}_{L}\in \left\{\mathrm{2, 3}, \mathrm{4, 5}\right\} $，$ {T}_{L} $有$ {N}_{L} $个候选数，因此，文献[17]的计算复杂度近似为$ O\left(16{N}_{L}\right) $。同理，文献[18]的计算复杂度近似为$ O\left(16{N}_{P}\right) $，其中，16和$ {N}_{P} $分别为最优尺寸$ {r}_{P}\times {c}_{p} $和最优阈值$ {T}_{p} $的候选数。文献[23]需要穷举搜索4个最优参数，即$ vT\mathrm{、}{T}_{w}\mathrm{、}{r}_{w} $和$ {c}_{w} $，其中，$ {r}_{w}\in \left\{\mathrm{3, 4}, 5\right\} $，$ {c}_{w}\in \left\{\mathrm{3, 4}, 5\right\} $，$ {T}_{w} $有m个候选数，$ m=⌊({r}_{w}\times {c}_{w}-1)/2⌋ $，$ vT $有$ {N}_{w} $个候选数。文献[23]的计算复杂度近似为$ O(9m\times {N}_{w}) $。而本文算法只需要确定一个参数，即阈值T，因此计算复杂度仅为$ O\left(N\right) $，其中，N为阈值T的候选数。

本文根据不同的嵌入容量，采用不同的最优阈值T^*改进本文算法。本文改进的算法与文献[17-18]、文献[23-26]算法在Barbara和Baboon的PSNR对比如图 12所示。从图 12可以看出，无论嵌入容量是多少，本文改进算法的PSNR都远大于现有算法。

5 结束语

本文提出基于像素值排序的可逆数据隐藏算法。通过计算每一个图像块的局部复杂度，并对比局部复杂度与阈值的大小，将局部复杂度小于阈值的图像块进行分块，同时设计12种分块模式，并通过实验测试不同分块模式下的嵌入性能，选择能够得到最优嵌入性能的模式进行数据嵌入。此外，通过改进本文算法，根据嵌入容量自适应地选择最优阈值T^*，以提高嵌入性能。实验结果表明，本文算法能够充分利用图像块内的每个像素，具有较优的嵌入性能。后续将在4×4和6×6图像块上设计分块策略，进一步提升图像块的嵌入性能。