一种基于动态分块和差值直方图平移的可逆水印算法

何文广，王耀民

（广东医学院信息工程学院，湛江524023）

一种基于动态分块和差值直方图平移的可逆水印算法

何文广，王耀民

（广东医学院信息工程学院，湛江524023）

基于图像内容的自适应嵌入已成为可逆水印算法的研究热点。探讨图像分块对算法性能的影响，得出基于差值直方图平移的可逆水印算法不存在最优分块尺寸这一结论，继而提出一种动态分块的差值计算方法。算法的基本思想是以多种分块替代固定分块，动态分块时充分考虑图像纹理复杂度，使得多种分块的数量比例能自适应于嵌入级别，解决传统差值计算方法中因较小分块引起的水印容量有限问题，以及因较大分块引起的分块内像素相似性下降问题。实验结果表明算法在嵌入容量和图像质量方面均有较大优势，为提高差值扩展的效率提供一种新思路。

图像纹理；动态分块；直方图平移；可逆水印

0　引言

图像数字水印技术根据含水印图像是否可恢复分为可逆和不可逆水印技术［1］。可逆水印又称无损水印，它对信号的篡改非常敏感并且能在提取出水印后无损地恢复原始图像，适用于图像完整性认证。因此，可逆图像水印技术可用于医学、军事和遥感等特殊领域。

现有可逆水印算法中空域算法可进一步划分为差值扩展、误差扩展和直方图平移三大类。差值扩展（Difference Expansion，DE）的方法首先由Tian［1］提出，算法思想是通过扩展相邻像素的差值实现水印嵌入。Alattar［2］随后通过扩展相邻的多个像素差值扩展了DE算法，进一步提升了水印嵌入率。误差扩展（Prediction Error Expansion，PEE）在差值扩展的基础上引入了误差预测技术，像素灰度值与预测值的差值被用于嵌入水印。由于预测值能基于多个相邻像素计算产生，因此误差扩展能获得相对更优的数据冗余。误差扩展的方法由Thodi［3］首先提出，并衍生出一系列的改进算法，包括Hu［4］等提出的定位图压缩方法，Luo［5］等提出的线性插值方法，Chen［6］等提出多重预测方法，以及Li［7］等提出的单遍多比特嵌入方法。熊［8］对多遍单比特和单遍多比特两类嵌入方案进行了性能分析。

Ni［9］首先提出了基于直方图平移（Histogram Shifting，HS）的水印嵌入方法，算法具有复杂度低和水印图像质量高的特点，但水印容量受限于峰值出现的频率，不能高效地处理直方图相对平坦的这一类载体图像。针对这一问题，Lee［10］首先提出使用差值直方图替代灰度直方图，从而获得了更为陡峭的直方图，提高水印容量的同时也减少了平移像素个数。利用相邻像素构建差值的方法在Lin［11］、Li［12］和Zhao［13］中也得到使用。Lin［11］首先以相邻像素的灰度差值构建差值图，然后划分差值图，在每一分块内实施直方图平移。Li［12］和Zhao［13］均通过逐一扫描所有像素并两两相减产生差值，Zhao［13］在Li［12］的基础上使用了多重直方图平移的方法。Kim［14］使用降采样的方法构造多幅差值子图，然后针对每一幅子图实施多重直方图平移。Kim［14］算法本质上利用了分块内像素的相似性产生数据冗余，针对这一点Luo［15］提出选取分块内的中值组成新的参考子图，这使得差值直方图更为陡峭，进而改进了Kim［14］算法。Li［16］在Lee［10］的基础上提出了二维差值直方图平移的水印嵌入方案，将部分待平移差值转换为可嵌入差值，提高了算法性能。

本文提出一种自适应于载体图像的动态分块方法，以进一步提高差值直方图平移中可嵌入差值的数量。算法的基本原理是根据图像纹理复杂度做出分块预测，将载体图像进行非固定式分块，最后在分块内实施差值直方图平移实现水印嵌入。

1　差值直方图平移

在Luo［15］算法中，载体图像首先被划分为若干尺寸为ΔU×ΔV、互不重叠的子块；然后对子块内所有像素按灰度值升序排序，如b1≤b2≤…≤bΔu×Δv，并选取中值作为参考像素bref。例如当ΔU=ΔV=4时，b8被选定为参考像素；最后，所有非参考像素减去参考像素产生差值：

1≤i≤ΔU×ΔV，i≠ref。在水印嵌入过程中，Luo［15］沿用了Kim［14］算法中多重直方图平移的方法，整个过程可分为平移和扩展两部分。首先，设置嵌入级别EL，落入区间（-∞，-EL）∪（EL，+∞）的差值不适用于嵌入水印，对其进行平移：

落入区间［-EL，EL］的差值通过差值扩展的方法嵌入一个水印比特w：

最后，计算出新的像素灰度：

1≤i≤ΔU×ΔV，i≠ref。由公式（3）、（4）可知，水印嵌入过程并没有修改参考像素bref，因此在水印提取时需要传输的辅助信息只有分块尺寸ΔU×ΔV及嵌入级别EL。

假设载体图像大小为M×N，则划分所得的子块数量为⌊M/ΔU」×⌊N/ΔV」。由于每一分块产生ΔU×ΔV-1个差值，因此差值总量为：

假设nin表示扩展差值数量，nout表示平移差值数量，则nd=nin+nout。显然，分块尺寸ΔU×ΔV决定了差值总量：尺寸越大，差值越多。另一方面，嵌入级别EL则决定了nin所占的比例：EL越大，nin所占比例越大。然而，当固定EL增大分块尺寸时，分块内像素之间的相似性往往相对变弱，容易导致nout的增长率超过nin的增长率，进而降低算法性能。同样地，当固定分块尺寸增大EL时，nout向nin转换的比例将持续下降，而对载体图像的扰动却持续加剧。

综上所述可知，基于固定分块的差值直方图平移方法不存在最优的分块尺寸。当容量需求较小时，适合选择较小的分块尺寸。而随着容量需求的增长，必须逐步选择更大的分块尺寸。

2　本文算法

2.1动态分块

假设原图像为M×N的灰度图像。首先，将原图像划分为若干8×8分块，记为B8k，k=1，2，…，⌊M/8」×⌊N/ 8」。然后，对每一个8×8分块进行以下处理：

图1分块划分

当所有8×8分块全部处理完毕后，载体图像被划分为四种尺寸不一的独立嵌入子块，记为BI，BII，BIII，BIV，如图2所示。最后，针对每一个独立的嵌入子块实施差值直方图平移实现水印嵌入。

图2　独立的嵌入子块

表1以Lena图为例对比了固定分块与动态分块两种分块方法对差值计算的影响。由表中数据可知，动态分块的方法提供了近乎一致的水印嵌入容量，并同时较好地限制了平移差值的数量，对提高含水印图像质量有重大意义。

表1　不同分块方法对差值计算的影响

2.2水印嵌入

按上节所述对载体图像进行动态分块，得到一系列独立嵌入子块后，水印嵌入算法可描述为以下5个步骤。

（1）计算参考像素

将每一独立嵌入子块中的所有像素按灰度值升序排序，取中值作为参考像素。例如，BII子块含有12个像素，则排序后排名第6的像素被选为参考像素，记为bref。

（2）子块分类

分别用nL，nO，nR表示分块内灰度值小于、等于和大于参考像素的像素个数，将分块划分为以下4类：

的引入能确保具有与参考像素相同灰度值的像素被修改后交替出现在参考像素的两侧，从而确保分块内参考像素不变。

2.3水印提取和图像恢复

在实施水印提取和图像恢复之前，同样需要参考2.1节对含水印图像进行动态分块。由于水印嵌入算法能维持独立嵌入子块的参考像素不变，因此在接下来的动态分块中只需将分块预测的条件改为“差值全落入区间［-2×EL-1，2×EL+1］”，即可得到与2.2节完全一致的图像分块。得到一系列独立嵌入子块后，水印提取和图像恢复算法可描述为以下4个步骤。

（1）计算参考像素

将每一独立嵌入子块中的所有像素按灰度值升序排序，取中值作为参考像素。

（2）构建差值直方图

计算每一个分块Bk内所有非参考像素与参考像素的灰度差值，然后组成差值直方图。

2.4溢出处理

对于灰度级为8比特的灰度图像，像素灰度范围为［0，255］。本文算法对灰度的最大修改值为EL+1，因此灰度值在［0，EL］或［255-EL，255］之内的像素在嵌入水印后可能产生溢出。本文采用了直方图收缩的方法，使用「log2（EL+2）⌉长度的比特序列区分灰度值在［0，EL+1］或［255-EL-1，255］范围内的像素。最后将上述比特序列做无损压缩后嵌入到载体图像中。

3　实验结果与分析

为了分析和评估算法性能，本节将本文算法与若干水印嵌入容量较大的可逆水印算法进行比较，主要评价各算法在相同水印嵌入量下的含水印图像质量。实验中使用实际嵌入的水印位数（bits）或每像素嵌入比特率（bits per pixel，bpp）来描述算法水印容量，使用峰值信噪比（PSNR）来描述含水印图像质量，其计算公式为：

实验测试图像来自USC-SIPI标准图像库，图像大小（像素个数）均为512×512，灰度级数为8 bit，如图3所示。测试图像纹理特征各异，其中Peppers平滑区域较多，Lena和Airplane次之，Barbara的纹理相对复杂。各算法嵌入的水印信息约定为相同的伪随机序列值，由MATLAB随机函数产生。

图3　实验测试图像

图4　不同测试图像的性能比较

首先采用本文算法对所有测试图像实施水印嵌入。图4对各测试图像在水印嵌入容量达0.9bpp之前的PSNR值进行了对比。对比的结果显然符合预期，纹理相对复杂的Barbara不仅在相同嵌入级别时获得较小的水印容量，并且在相同水印嵌入容量时PSNR值相对较小。

图5将Luo［15］算法在4种分块尺寸下的实验数据与本文算法所得数据分别进行了比较。通过与本文算法的比较，不难发现Luo［15］算法在2×2和3×3分块时水印容量增长停滞问题较为凸显。当嵌入级别较小时，两类算法表现出近似的性能。但随着嵌入级别的提升，Luo算法逐渐出现水印容量增长的瓶颈。Luo算法4×4分块与本文算法的性能差别表现在前期，凸显的是分块内像素相似性减弱的问题。这一点在5×5分块的性能表现上得到进一步印证。

图5　基于Lena图像的性能比较

基于测试图像Airplane和Barbara的性能比较出现类似的结果，分别如图6、图7所示。由此可见，动态分块的方法能依据不同的嵌入级别高效地完成图像分块，分块结果能同时维持水印容量增长和分块内像素的相似性。另外，通过分别比较图7（a）和图8（a），以及图7（b）和图8（b），不难发现随着图像纹理复杂度的增加，尽管本文算法仍能保持水印容量增长方面的优势，但PSNR值方面的优势却在逐步萎缩，这说明图像纹理复杂度对本文算法中分块预测的效率有直接影响。

图6　基于Airplane图像的性能比较

图7　基于Barbara图像的性能比较

Peppers图像相对平滑，实验结果表明本文算法性能优于各种固定分块方法，如图8所示。

4　结语

图像分块在可逆水印算法中具有较大研究意义，分块的方法能影响各类算法的性能。本文选择差值直方图平移作为切入点，得出不存在最优分块尺寸这一结论，继而提出一种动态分块的差值计算方法。实验结果表明，基于图像纹理复杂度和嵌入级别能实现有指导性的图像分块，以多种分块替代固定分块的动态分块方法确实能解决了传统差值计算方法中因较小分块引起的水印容量有限问题，以及因较大分块引起的分块内像素相似性下降问题，最终在提升水印容量的同时较好地维持了水印图像质量。

图8　基于Peppers图像的性能比较

［1］J.Tian.Reversible Data Embedding Using a Difference Expansion［J］.IEEE Transactions on Circuits and Systems for Video Technology，2003，13（8）：890-896.

［2］A.M.Alattar.Reversible Watermark Using the Difference Expansion of a Generalized Integer Transform［J］.IEEE Transactions on Image Processing，2004，13（8）：1147-1156.

［3］Thodi D M，Rodriguez J J.Expansion Embedding Techniques for Reversible Watermarking［J］.IEEE Transactions on Image Processing，2007，16（3）：721-730.

［4］Y.Hu，H.K.Lee，J.Li.DE-Based Reversible Data Hiding with Improved Overflow Location Map［J］.IEEE Trans on Circuits and Systems for Video Technology，2009，19（2）：250-260.

［5］L.Luo，Z.Chen，M.Chen，X.Zeng，Z.Xiong，Reversible Image Watermarking Using Interpolation Technique，IEEE Trans.Inf. Forensics Secur，2010，5（1）：187-193.

［6］Chen X Y，Sun X M，et al.Reversible Watermarking Method Based on Asymmetric-Histogram Shifting of Prediction Errors［J］.Journal of Systems and Software，2013，86（10）：2620-2626.

［7］X.Li，B.Yang，T.Zeng.Effcient Reversible Watermarking Based on Adaptive Prediction-Error Expansion and Pixel Selection［J］. IEEE Transactions on Image Processing，2011，20（12）：3524-3533.

［8］熊祥光.基于直方图平移的多遍与多比特嵌入性能比较［J］.计算机应用研究，2015，32（8）：2437-2440，2446.

［9］Z.Ni，Y.-Q.Shi，N.Ansari，W.Su.Reversible Data Hiding［J］.IEEE Trans on Circuits and Systems for Video Technology，2006，16（3）：354-362.

［10］S.K.Lee，Y.H.Suh，Y.S.Ho.Reversible Image Authentication Based on Watermarking［C］.In Proc.IEEE ICME 2006：1321-1324.

［11］Lin C C，Tai W L，Chang C C.Multilevel Reversible Data Hiding Based on Histogram Modification of Difference Images［J］.Pattern Recognition，2008（41）：3582-3591.

［12］Y.C.Li，C.M.Yeh，C.C.Chang.DataHidingBasedontheSimilarityBetween NeighboringPixelswithReversibility［J］. Digital Signal Processing，2010，20（4）：1116-1128.

［13］Z.-Z.Zhao，H.Luo，Z.-M.Lu，J.-S Pan.Reversible Data Hiding Based on Multilevel Histogram Modification and SequentialRecovery［J］.Journal of Electronics and Communications，2011，65：814-826.

［14］Kim K，Lee M，et al.Reversible Data Hiding Exploiting Spatial Correlation Between Sub-Sampled Images［J］.Pattern Recognition，2009（42）：3083-3096.

［15］Luo H，Yu F X，et al.Reversible Data Hiding Based on Block Median Preservation［J］.Information Sciences，2011，181：308-328.

［16］X.Li，W.Zhang，X.Gui，and B.Yang.A Novel Reversible Data Hiding Scheme Based on Two-Dimensional Difference-Histogram Modication［J］.IEEE Transactions on Information Forensics and Security，2013，8（7）：1091-1100.

A Reversible Watermarking Scheme Based on Dynamic Partition and Difference Histogram Shifting

HE Wen-guang，WANG Yao-min
（School of Information Engineering，Guangdong Medical University，Zhanjiang 524023）

Adaptive embedding based on image content has become a hot research topic of reversible watermarking.Discusses the impact of image partition on the performance of the scheme，and the conclusion is that there is no optimal block size for difference histogram shifting based reversible watermarking schemes.After that proposes a new method for difference calculation based on dynamic partition.The basic idea of dynamic partition is to replace the fixed block size with multiple block sizes and the image texture complexity can be taken into account to achieve effective image partition.The numbers of several size-variable blocks are adaptive to the embedding level，which helps to solve the problem of the limited amount of embedding capacity due to small block and the problem of low similarity of pixels within large block existed in traditional difference calculation.The experimental results verify that the proposed scheme not only perform outperformance about embedding capacity and watermarked image quality，but also provides a new way for improving the efficiency of difference expansion.

Image Texture；Dynamic Partition；Histogram Shifting；Reversible Watermarking

1007-1423（2016）23-0057-07DOI：10.3969/j.issn.1007-1423.2016.23.015

2016-05-10

2016-08-10

国家自然科学基金（No.81201763）、湛江市科技攻关项目（No.2013B01181）

何文广，讲师，硕士，研究方向为信息隐藏、图像处理王耀民，讲师，硕士，研究方向为计算机安全