邢慧芬，黄贵林，汤柱亮

巢湖学院信息工程学院，合肥，238000

基于直方图平移和自适应插值的可逆水印算法

邢慧芬，黄贵林，汤柱亮

巢湖学院信息工程学院，合肥，238000

基于直方图平移和自适应插值扩展，提出一种可逆水印算法。首先利用直方图平移的方法对图像进行预处理，解决水印嵌入过程中像素值的上溢和下溢。然后采用一种自适应插值方法求得图像的预测值，并计算原始图像与预测图像的差值，在差值直方图峰值点嵌入水印信息。接收方利用同样的插值方法得到预测值，再与含水印像素求差，提取差值中的水印信息，并恢复出原始图像。实验证明，由于利用水平、垂直、45°和135°四个方向进行预测，使误差更集中，直方图峰值更大，从而实现高容量的信息嵌入。

可逆数字水印；自适应插值；直方图平移

1 相关研究与问题提出

随着互联网的发展，图像、视频、音频等数字多媒体信息的传输越来越方便，伴随而来的数字媒体信息的非法复制、传输现象也不断出现，严重影响了数字多媒体创作者、拥有者的权益。数字水印技术的出现，可以较好解决这方面的问题。而在一些敏感领域，诸如医学上的医疗图像、法律上的证据图像、军事上的卫星图像等，图像上的每一个像素值都至关重要，修改这些图像的任何一个细节将会造成意想不到的后果，因此需要一种既能可靠的传输秘密信息，又能恢复原始图像的技术。为此，人们提出了可逆数字水印技术。

可逆数字水印算法最早出现在1997年Barton的一项美国专利中[1]，该专利基于空间域提出了一种脆弱水印的算法。该算法使用模-256(module-256)方法处理像素值溢出问题，因而会造成额外的椒盐(salt-and-pepper)噪声。后来，C. D. Vleeschouwer等人针对Barton方法中出现的问题，提出了拼凑算法和可环绕成圆圈的直方图频率算法，有效地减少了椒盐噪声的产生[2]。2003年，Tian提出基于差分扩张(Difference Expansion，DE)算法的可逆水印，DE作为整数小波变换的一种，通过扩展相邻两像素的差分来实现水印的嵌入[3]。2006年，Ni等人提出直方图平移的可逆水印，这种方法统计图像中像素灰度值，利用图像灰度直方图的特征，在空缺的灰度级中嵌入水印信息[4]。

将直方图平移方法和差分扩张(DE)算法相结合，是近年来研究可逆水印技术的重要方法之一。Lin和Hsueh在2008年提出的可逆水印算法是，先将图像划分为1×3或3×1的图像块，然后分别求出像素1和像素2以及像素2和像素3之间的差值，利用直方图平移方法，在这些差值中嵌入水印信息[5]。2009年，Hu等人在整数小波变换域中将DE(difference expansion)算法和直方图平移方法相结合来减少头信息量，从而增加水印信息的嵌入量[6]。Luo等人在2010年使用一种插值算法对像素值进行预测，然后求得原始值与预测值的差值，在这些差值中嵌入水印信息，取得了很好的效果[7]。此外，文献[8-9]都是通过周围像素值对目标像素进行插值预测，从而求得目标像素的预测值，再在原始值与预测值的差值中嵌入水印信息的方法达到可逆的效果。本文在Luo方法[7]的基础上，推导出一种新的自适应预测方法，并根据这种自适应预测方法求得目标像素的预测值。

2 自适应插值

Luo方法[7]是一种基于两个方向的自适应插值方法，本文在此基础上推导出一种基于四个方向的自适应插值方法，这种方式基于水平、垂直、45°和135°四个方向进行预测，充分利用图像临近像素间的相关性，使插值误差更集中，直方图峰值更大，图像的嵌入容量更高。

2.1 子采样模型

首先，将一副原始图像划分为4个子图像(图1)，其中白色部分为缺失的部分，黑色部分为原始像素值，这样便可以将一幅待预测的图像(a)分成4幅子图像(b)～(e)进行单独的预测。因此，只要用原始图像的3/4像素预测剩余的1/4像素4次，就可以完成对整幅图像的一次完整性预测。

图1 (a)为原始图像 (b)～(e)划分后的4个子图像 图2 图像插值示意图

2.2 自适应方法推导

(1)

而对待预测像素的第二次预测方法，则结合最小线性均方误差方法(LMMSE)：

(2)

wh(n)+wv(n)+w45(n)+w135(n)=1

(3)

进一步求得四个方向上的原始值与预测值的差值eh(i,j)，ev(i,j)，e45(i,j)和e135(i,j)分别为：

(4)

(5)

(6)

从文献[10]得知，对于一幅自然图像，ei(n)和ej(n)是弱相关的，因此E[ei(n)·ej(n)]=0(其中i,j=h,v,45,135，而且i≠j)，所以公式(7)修改为：

(8)

(9)

(10)

(11)

综上所述，本文的预测值由公式(2)所得到，其中权重由公式(9)决定，初预测值由公式(1)求得。

3 本文方法

3.1 溢出问题

在8-bits灰度图像中嵌入水印信息可能会造成像素值从255变为256或者从0变为-1，本文用直方图平移的方法避免像素值的溢出。

设hist(0)≠0或者hist(255)≠0(hist(n)表示像素值为n的频数)，从0开始从左到右找出原始图像一个最小峰值点LN；同理，从255开始从右到左找到原始图像一个最小峰值点RN。不失一般性，将像素值在 0,LN向右平移一位，则平移后有：hist(0)=0，hist(1)=hist(0)，…，

hist(LN)=hist(LN-1)+hist(LN)

若hist(LN)=0,hist(RN)=0，将LN、RN作为附加数据嵌入原始图像，以便接收端恢复图像。若hist(LN)≠0或者hist(RN)≠0时，这时就需要创建一个定位图，可以用“0”表示原始像素LN，用“1”表示像素值为(LN-1)(即平移后像素值为LN)的像素，接收端在提取定位图信息后以便恢复原始图像。

3.2 嵌入水印

设待嵌入的信息P有水印信息W和头信息O两部分组成，即P=W∪O=p1p2…pj，其中pi∈{0,1},1≤i≤j，j为实际嵌入信息的长度，其中头信息O是解决像素值上溢和下溢所产生的附加信息。

本文的水印嵌入过程可以分为以下6个步骤。

(1)按照3.1所述对原始图像进行预处理，记录附加信息O，得到实际嵌入信息P。

(2)按2.1所述将一幅图像划分为4个子图像，从子图像1(b)到子图像1(e)依次进行步骤3)到步骤(6)的操作。完成一次子图像1(b)到子图像1(e)的插值和嵌水印就相当于完成一次单层水印嵌入。

(4)求得差值的直方图，计算得到左峰值点LM，右峰值点RM，左零值点LZ，右零值点RZ。

(5)再次扫描图像，进行公式(12)的水印信息嵌入，其中b为水印信息0或1。

(12)

(13)

3.3 水印提取

为了提取水印，需将LM等信息作为秘密进行单独传输，以便接收端提取水印信息。

(1)读取一副含水印信息的图像，按2.1节方式将一副图像划分为4个子图像。在提取水印时，为了完整地提取水印信息，提取过程从子图像1(e)依次到子图像1(b)，重复步骤(2)到(3)。

(3)求得差值e′(n)的直方图，根据LM等信息，用公式(14)提取水印信息，公式(15)恢复出原始差值，最后根据公式(16)恢复出原始图像。

(14)

(15)

(16)

4 仿真实验结果与分析

为了验证本方案的性能，选取lena图像、airplane图像、baboon图像、sailboat图像四幅较为典型的大小为512×5128-bits灰度图像进行实验，如图4所示。其中“lena”和“airplane”变换比较平坦，而“baboon”和“sailboat”细节丰富纹理明显。

图3 (a)Luo的差值直方图 (b)本文的差值直方图

图4 原始图像

为了对实验结果进行分析比对，采用峰值信噪比(PSNR)和嵌入容量(嵌入到载体图像的比特位的个数，用bits表示)作为算法的性能评估标准。峰值信噪比PSNR的计算由公式(17)计算所得。

(17)

其中，MSE(Mean Square Error)为均方差：

(18)

在插值预测与直方图平移相结合的算法中，差值直方图中心尖峰越高，说明预测效果越好，算法的水印嵌入量就越高。这里以图4中的“Lena”为例，分别给出Luo[10]方法的预测方法和本文提出的预测方法的差值直方图进行对比，结果如图3(a)和3(b)所示。从图中可以看出，本文的差值直方图相比原始直方图，峰值点有明显的提高。

为了分析比较，将本方案和文献花[7]、[9—10]进行比对，结果如表1所示。从表1可以看出，相较于其他3种方法，本文方法不管在嵌入容量还是峰值信噪比(PSNR)上都有明显的提高。对于平坦图像，本文方法提高的效果更加明显，尤其是airplane图像，其嵌入量大幅提高；本文提出的自适应插值方法，充分利用了图像相邻像素间的相关性，是该算法拥有更大嵌入量的重要原因。本文的图像峰值信噪比(PSNR)都接近48dBs，通常图像峰值信噪比大于30时，主观上已很难察觉图像的变化，因此本文方法很好地保存了原始图像的视觉效果。由于首先利用3.1节所述直方图平移的方法很好地避免了像素值溢出问题；在水印提取时，先对标志信息提取出来用于定位像素值溢出位置，从而达到提取水印信息、恢复原始图像的可逆目的。

表1 水印嵌入量与PSNR比较

5 结束语

利用直方图平移和自适应插值扩展方法，提出一种可逆水印方案。首先对原始图像进行直方图平移，很好地解决了嵌入过程图像像素值的上溢和下溢。然后，基于水平、垂直、45°和135°四个方向对图像进行自适应插值，充分利用了图像相邻像素间的相关性，使插值误差更集中，直方图峰值更大，从而实现高容量的信息嵌入。与近期的一些方法比较可以看出，本文提出的方法不管是在平坦图像还是细节图像方面都具有一定的优势，而且每次嵌入水印的最大像素值改变量为1bit，很好地保存了原始图像的视觉效果。但在传输的过程中需要将LM等信息作为秘密进行额外单独传输，具有一定的安全隐患。

[1]J M Barton.Method and apparatus for embedding authentication information within digital data[P].U.S. Patent, Patent Number:5,646,997.1997

[2]C D Vleeschouwer,J F Delaigle，B Macq.Circular interpretation of bijective transformations in lossless watermarking for media asset management[J].IEEE Trans Multimedia,2003,5(1):97-105

[3]Jun Tian.Reversible data embedding using a difference expansion[J].IEEE Transaction on Circuits and Systems for Video Technology,2003,13(8):890-896

[4]Z Ni,Y Q Shi.Reversible Data Hiding[J].IEEE Transaction on Circuits and Systems for Video Technology,2006,16(3):354-362

[5]C C Lin，N L Hsueh.A lossless data hiding scheme based on three-pixel block differences[J].Pattern Recognition,2008,41(4):1415-1425

[6]Y Hu,H K Lee,J Li.De-based reversible data hiding with improved overflow location map[J].IEEE Trans. Circuits and Systems for Video Technology,2009,19(2):250-260

[7]L X Luo,Z Y Chen,M Chen，et al.Reversible image watermarking using interpolation technique[J].IEEE Transaction Information Forensics and Security, 2010,5(1):187-193

[8]王继军．图像插值空间大容量可逆数字水印算法[J]．中国图象图形学报，2014，19(4):527-533

[9]熊祥光．基于图像插值的大容量可逆水印算法[J]．光电子，2016，27(6)：646-654

(责任编辑：汪材印)

TP309.2

：A

：1673-2006(2017)07-0095-05

10.3969/j.issn.1673-2006.2017.07.025

2017-03-10

巢湖学院科研课题“感知哈希在图像认证中的应用”(XLY-201410)；巢湖学院科研课题“基于分行理论的图像压缩方法的研究”(XLY-201612)；巢湖学院科研课题“芯片测试集合并方法研究”(XLY-201409)。

邢慧芬(1986-)，女，安徽阜阳人，硕士，助教，研究方向：图像认证。