基于视觉密码和边缘检测的零水印算法

曲长波　李栋栋

(辽宁工程技术大学软件学院　辽宁 葫芦岛 125105)



基于视觉密码和边缘检测的零水印算法

曲长波李栋栋

(辽宁工程技术大学软件学院辽宁 葫芦岛 125105)

在版权认证领域，传统的水印算法往往是在载体图像中嵌入二值图像。这种算法有两个缺点：一是水印的嵌入改变了载体图像，而在医学和侦查等领域需要保留原始数据；二是图像受到篡改攻击后，很难判断攻击的类型和位置。针对以上两个问题，提出一种基于视觉密码和边缘检测的零水印算法。首先，对载体图像进行置乱和奇异值分解等操作提取特征矩阵；然后，将特征矩阵按照算法生成公有图和私有图；最后，将私有图和零水印存至认证中心。另外，应用游程编码对图像边缘进行无损压缩生成密钥，用来进行篡改检测。实验表明，该算法具有非常好的鲁棒性和安全性，尤其是抵御噪声攻击；在篡改检测方面也具有很好的效果。

版权认证视觉密码特征矩阵边缘检测

0　引　言

信息隐藏技术是一门新兴学科，即将秘密信息隐藏到普通文件中，保证秘密信息不被盗密者发现并在网络中安全传输的技术[14]。在版权保护方面，文献[6,12]提出的数字水印技术多将水印嵌入载体图像，这种嵌入方式影响了载体图像的完整性，在对数据完整性要求较高的医学和侦查领域，这显然是不合理的[4]。在侦查等领域，我们还需要对图像进行篡改检测，以便于对图像所受攻击进行鉴别和定位，而近年来的水印技术很少将两者进行结合。另外，在算法保护方面，算法的加密也是很重要的一部分，因为算法一旦泄露，不但起不到保护版权的作用，甚至为侵权和盗版提供了更便利和以假乱真的渠道。

基于以上问题，本文提出基于视觉密码和边缘检测的零水印算法。在水印嵌入上，零水印算法通过提取载体图像的固有特征生成零水印的两部分，从而保护载体图像的完整性。在篡改检测上，应用游程编码对提取载体图像边缘后所得图像进行无损压缩生成密钥，用于后期篡改检测和定位。在算法保护方面，利用视觉密码技术将版权水印根据载体图像固有特征和固定的匹配算法生成水印的两个分图：一个分图标志图像信息，并在生成后进行销毁；一个分图注册到认证中心1。同时，将两个分图叠加后生成的零水印注册到认证中心2，这种版权认证方式采用了“三方分离”的方法。分图可以一个嵌入，一个进行版权保护[9]。除了拥有两个分图并进行叠加获得零水印以外，还需要到认证中心检测才能确定版权归属。任何一方单方持有水印的一个分图甚至是版权水印都无法解密图像，从而保证了算法的安全性。Hsu等[7]提出了一种视觉密码的数字水印方案，该方案采用传统嵌入方式，使原始数据遭到破坏；曲长波等[10]提出了一种小波域视觉密码零水印算法，该算法在提取特征矩阵时采用均值和指定方法生成零水印，对于噪声攻击等影响均值的方法没有好的鲁棒性；曲长波等[3]提出平衡多小波的视觉密码技术，该算法的特征信息不够全面，导致鲁棒性不够好。本文在考虑到以上各问题的基础上，平衡了文献[7，10]的缺点，在此基础上又增加了篡改检测。实验表明该算法具有较高的鲁棒性和安全性，其中篡改检测对多种常见攻击具有十分好的检测效果。

1　算法理论基础

1.1奇异值分解

数值分析中的奇异值分解是一种矩阵对角化的数值算法[11]，可以将指定矩阵分解为3个矩阵的乘积，即：

(1)

奇异值分解可以快速将大量的信号能量压缩到很少的系数中。奇异值所表现的是图像的固有特征而非视觉特性，为水印的不可见性提供了保障[6]。根据奇异值分解的这种特性，可以将其应用到图像的分解中，用少量数据描述图像主要特征并生成零水印，从而获得鲁棒性较好的零水印算法。

1.2视觉密码技术

视觉密码是一种只需人眼解密图像而不需要其余处理过程参与的加密方式[15]。可以通过将一幅保密图像分解为公有图和私有图两部分进行图像加密，并把两部分图像叠加后进行解密[16]。可视密码方案消除了复杂的解密过程,加密图像可以通过叠加操作恢复[2]。

算法[17〗：设加密图像尺寸为N×N，加密图像按照算法生成两个2N×2N的部分。加密图像的1个像素分解成4个像素，其中白色像素分解为2×2的仅有2个黑像素的灰色矩阵，而黑色像素分解为2×2的有4个黑像素的全黑矩阵。图1是加密图像分解和加密产生的效果图，(a)“版权保护”经过分解成为两部分：(b)和(c)。(d)是将两部分叠加后得到的解密图像。

图1　视觉密码效果图

2　零水印及密钥生成算法

2.1特征矩阵提取算法

特征矩阵提取过程分为小波变换、分块操作、奇异值分解、取最大奇异值操作和取最高位操作。设载体图像I大小为M×M，水印图像W大小为m×m，则具体步骤如下：

(1) 采用置乱变换技术对图像进行预处理[8]，把载体图像I进行置乱，像素重新分布后得到置乱后的图像S。

(2) 对载体图像进行L级小波变换，得低频域cAL。把cAL均分为m×m块，得到Bij(i,j∈{1,2,…,M/(2L×m)})矩阵分块。

(3) 将Bij进行奇异值分解，把每块的最大奇异值经过四舍五入和取最高位操作得到过渡矩阵Xij(i,j∈{1,2,…,M/(2L×m)})。

(4) 最后根据过渡矩阵X的奇偶性生成特征矩阵Y。即:

(2)

2.2零水印生成算法及算法销毁方式

在得到特征矩阵Y之后，结合特征矩阵和版权水印图像，用视觉密码技术形成版权保护图像的两个部分，具体算法如表1所示。

表1　零水印算法生成图示

即：

(3)

(4)

从式(4)可以看出，公有图的每个像素M(i,j)的生成方式仅仅依赖于特征矩阵的每个像素Y(i,j)，与二值版权水印W(i,j)无关。为了预防算法的泄露，在两分图生成后，先将零水印MO和私有图O保存至不同认证中心2和认证中心1，实现认证分离。然后，立即将水印生成式(3)中私有图O(i,j)的生成方式和二值版权水印W进行销毁，仅留下公有图M(i,j)的生成算法以用来后期提取。

2.3密钥生成算法

密钥生成算法分为载体图像边缘检测和游程编码无损压缩两部分。游程编码主要思想是指将连续相同的信号用信号值和长度所组成的二元数组来替代[5]。方法如下：

(1) 首先对载体图像应用合适微分算子和阈值进行边缘检测得到二值图像E。根据文献[18]中各类算子边缘检测的特点，选用检测轮廓清晰、细节完整度较高的算子。不同阈值与压缩率和漏警率[19]的关系如图2所示。

(2) 然后对E应用游程编码RLC(Run Length Coding)进行无损压缩得到一维数值序列K。

(3) 最后，将一维数值序列K作为密钥K进行保存，用于后期检测。

图2　不同阈值压缩率及漏警率折线图

根据图2可以看出，随着选定的算子(canny)在提取边缘时阈值的不断增大，游程编码的压缩率逐步提高，并在0.1时达到顶峰；同时，后期篡改检测(选用50个随机3×3篡改区域进行漏警率计算)的漏警率也在逐步增大，而在0.1时有较小回落。本着使密钥数据量最小和定位精准度高的原则，应该选择压缩率最高和漏警率最低的阈值作为本文设定的阈值，而对于其他图像，应具体问题具体分析。

3　零水印认证及篡改检测算法

3.1水印认证算法

零水印认证主要是公有图的提取。载体图像在经过攻击后得到图像I’，对图像I’进行同2.1节的特征矩阵提取，在提取到特征矩阵之后，结合2.2节中M(i,j)的算法生成零水印的公有图M。最后，公有图M和认证中心1保存的零水印私有图O进行叠加，得到攻击后的零水印图像，将攻击后的零水印图像与认证中心2得到的零水印图像进行比较，即可完成图像的版权认证。具体认证过程如下：

(1) 应用置乱算法，把载体图像I’进行置乱，像素重新分布后得到置乱后的图像S’。

(2) 对载体图像S’进行L级小波变换，获得低频域cA。把cA均分为m×m块，得到Bij(i,j∈{1,2,…,M/(2L×m)})矩阵分块。

(3) 将Bij进行奇异值分解，把每一块的最大奇异值经过四舍五入和取最高位操作得到过渡矩阵Xij(i,j∈{1,2,…,M/(2L×m)})。

(4) 最后根据过渡矩阵X的奇偶性生成特征矩阵Y。即:

(5)

(5)应用2.2节中销毁后所剩算法生成零水印的公有图M。即：

(6)

(6) 将公有图M与认证中心1提取的私有图O进行叠加，并与认证中心2提取的零水印MO进行比对，确定版权所有。

3.2篡改检测算法

篡改定位是基于数字水印图像认证技术的一个突出优点, 也是衡量脆弱水印算法性能的重要指标之一[1]。篡改检测应用的是边缘检测和游程编码的方式。游程编码对于二值图像非常有效[13]，因为游程编码是连续精确的编码，对任何一位的改变都十分敏感，任何对图像边缘的破坏都会使得密钥K改变，所以篡改判断比较精确。方法如下：

(1) 对攻击后的图像I’应用2.3节中相同阈值和微分算子提取边缘得到二值图像E’。

(2) 按照2.3节中保存的密钥K和游程编码程序解压得到二值图像E。

(3) 然后对E’应用游程编码RLC进行无损压缩得到一维数值序列K’。

(4) 判断K与K’是否相等，若不等，则图像受到篡改。

(5) 将E与E’进行比对，判断图像所受篡改的类型及位置。

4　实验结果

4.1实验参数

实验环境为Matlab R2010b,实验选取512×512的灰度图像Lena为载体图像。版权水印为32×32的“版权保护”图像，小波选择Haar小波基进行二级小波变换，置乱方式为Arnold置乱算法，边缘检测采用canny算子，阈值为0.1。版权水印如图3(a)所示，载体图像如图3(b)所示。

图3　版权水印和载体图像

4.2评价标准

数字水印鲁棒性的衡量标准本文选择归一化相关系数(NC)来衡量：

(7)

篡改检测实验效果如图4-图6所示。

图4　噪声攻击对比图像

图5　剪切攻击对比图像

图6　涂改攻击对比图像

篡改检测实验效果图展示了该算法对常见攻击的检测效果，从图中可以看出，载体边缘图(图4(a))在和经受攻击后的各个边缘图像对比后能清楚地判断图像遭受攻击的类型和位置。噪声攻击(图4(b-d))、剪切攻击(图5)和涂改攻击(图6)清楚地显示了载体图像(图3(b))在遭受攻击的类型和程度不同时呈现的检测图。根据篡改检测实验图，可以判断载体图像在传输过程中所遭受的攻击类型和位置，有利于后期对图像完整性及其来源的判断。实验对照如表2、表3所示。

表2　篡改检测实验Lena密钥(K)对照表

表3　Lena鲁棒性实验性能(NC) 对照表

续表3

注：-表示无此项

5　实验结果分析

5.1篡改检测分析

从图4-图6和表2可以很清楚地看出篡改检测算法实现了比较精确的篡改鉴别及定位。图4-图6非常直观地反映了载体图像在接受各类攻击后呈现的边缘检测图，与原始边缘检测图(图4(a))进行精确比对，可以很容易判断载体图像所受的攻击类型及其位置，尤其是对旋转攻击、噪声攻击、剪切攻击、区域攻击、涂改攻击的定位和判断十分准确。表2用密钥K反映了载体图像是否受到篡改，对于以上各类攻击都具有精确的判断。这利用了游程编码是精确编码的优势，边缘图像任意像素的修改都会影响游程编码的密钥K。表2在数据上应用K的长度来进行比对，这是由于K序列一般较长，一般通过长度就可以判断，对于精确度要求很高的领域，可以直接进行K的比对。

5.2鲁棒性实验分析

由表3可知，本文算法在噪声攻击、滤波攻击、压缩攻击、左上角剪切攻击方面具有十分强的鲁棒性。这是因为奇异值分解和取最高位操作使得图像能量更加集中，特征信息更具代表性。该算法应用文献[3，10]视觉密码的优点，采纳文献[7]零水印算法分图组合方式，同时提出了不同于二者的特征矩阵和零水印生成方式，又采取了“三方分离”加密方式，这样算法在鲁棒性和安全性上都有较大提升。

在旋转攻击和中心剪切方面，本文算法综合考虑文献[3，7，10]的优缺点，在旋转攻击较文献[3，7]有较大提升，在中心剪切较文献[3，10]有较大提升。综合以上各类攻击来看，本文算法在以上各类攻击的综合性能方面较文献[3，7，10]都有较大提高。

5.3安全性分析

在版权保护领域，除了对版权进行精确认证外，还需要考虑到整个保护过程的安全性。在阅读各类数字水印文献的基础上，针对各类文献缺乏算法保护的问题，本文提出了将视觉密码应用于数字水印的方法。同时提出了实现水印认证“三方分离”和零水印生成“版权水印销毁”、“算法销毁”的策略。“三方分离”充分利用视觉密码可以将载体图像分解的特点，分解后的私有图和公有图互不关联，叠加后的零水印也与任何一个分图不关联，仅有在同时持有三者的情况下才可以完成版权认证，这样提高了认证的安全性。“版权水印销毁”和“算法销毁”针对解决版权拥有者内部或其他原因引起的算法泄露。通过将原先参与生成零水印的“版权水印”进行销毁来杜绝零水印的可复制性，以防盗版等侵权行为；“算法销毁”利用了本文算法中公有图生成仅仅依赖于特征矩阵的特点，将原先生成算法中私有图的生成算法进行销毁，仅留下公有图生成算法用于后期提取对比。因为私有图算法在销毁前已存至认证中心1，这样即便是公有图算法泄露，私有图算法已经销毁且私有图仅在认证中心1可得，盗密者无法完成版权认证的复制，从而实现了算法和版权认证的安全性。

6　结　语

在考虑传统水印算法以嵌入方式加入水印和难以实现篡改检测的基础上，提出了一种将二者结合的基于视觉密码和边缘检测的零水印算法。同时，对版权保护过程中算法和水印的安全性进行了设计。这样，零水印算法不但保证了原始数据的完整性、算法的安全性，还可以通过篡改检测的方式进行篡改的定位和鉴别。本文算法在医学和侦查领域若是能得到应用，将会有较好的实际效果。实验表明，本文算法在鲁棒性上具有十分好的综合性能，在安全性和篡改检测方面也有较好效果和判断结果。

[1] 陈帆,王宏霞.定位像素篡改的安全脆弱水印算法[J].铁道学报,2011,33(1):63-68.

[2] Rao R Y.Secure visual cryptography[J].International Journal of Engineering and Computer Science, 2013, 2(1):265-303.

[3] 曲长波,杨晓陶,袁铎宁.平衡多小波视觉密码零水印算法[J].计算机工程,2014,40(9):178-182.

[4] He H,Chen F,Tai H M,et al.Performance analysis of a block-neighborhood-based self-recovery fragile watermarking scheme[J].Information Forensics and Security,IEEE Transactions on,2012,7(1):185-196.

[5] 符浩军,范承啸,朱长青,等.基于游程长度的二值栅格地理数据水印算法[J].测绘与空间地理信息,2014,37(11):14-17.

[6] 薛胜男,陈秀宏.基于混沌加密和SVD 的数字图像水印算法[J].计算机工程,2012,38(19) :107-110.

[7] Hsu C S,Tu S F.Digital watermarking scheme with visual cryptography[J].IMECS,Hong Kong,2008,1:659-662.

[8] 王国栋,刘粉林,汪萍,等.一种篡改检测与篡改定位分离的图像认证方案 [J].计算机学报,2007,30(10):1880-1888.

[9] Han Y Y,He W C,Ji S,et al.A digital watermarking algorithm of color image based on Visual Cryptography and Discrete Cosine Transform[C]//P2P,Parallel,Grid,Cloud and Internet Computing (3PGCIC),2014 Ninth International Conference on.IEEE,2014:525-530.

[10] 曲长波,杨晓陶,袁铎宁.小波域视觉密码零水印算法[J].中国图象图形学报,2014,19(3):365-372.

[11] 赵春晖,刘巍.基于压缩感知的交互支持双水印算法[J].电子学报,2012,40(4):681-687.

[12] 叶天语.DWT—SVD 域全盲自嵌入鲁棒量化水印算法[J].中国图象图形学报,2012,17(6):644-650.

[13] 张德丰.数字图像处理 (MATLAB 版)[M].人民邮电出版社,2009.

[14] 王丽娜,郭迟，李鹏.信息隐藏技术实验教程[M].武汉大学出版社,2004.

[15] Amirtharajan R,Sulthana S,Rayappan J B B.Seeing and believing is a threat:A visual cryptography schemes[J].Research Journal of Information Technology,2013,5(3):435-441.

[16] Surekha B,Swamy G N.Visual Secret Sharing Based Digital Image Watermarking[J].International Journal of Computer Science Issues (IJCSI),2012,9(3):312-317.

[17] Naor M,Shamir A.Visual cryptography[C]//Advances in Cryptology—EUROCRYPT’94.Springer Berlin Heidelberg,2006,950:1-12.

[18] 赵芳,栾晓明,孙越.数字图像几种边缘检测算子检测比较分析[J].自动化技术与应用,2009,28(3):68,72.

[19] 和红杰.数字图像安全认证水印算法及其统计检测性能分析[D].成都:西南交通大学,2008.

ZERO WATERMARKING ALGORITHM BASED ON VISUAL CRYPTOGRAPHY AND EDGE DETECTION

Qu ChangboLi Dongdong

(College of Software,Liaoning Technical University,Huludao 125105，Liaoning,China)

In the field of copyright certification, traditional watermarking algorithm usually embeds the binary image into carrier image.Such algorithm has two shortcomings:the one is that the embedded watermarking changes carrier image, but in the fields such as medicine and investigation there have higher demand in original data integrity; the other is that once the image is suffered from tampering attack, it is hard to judge the type and location of attacks.To solve the above two problems, this paper proposes a new zero watermarking algorithm which is based on visual cryptography and edge detection.First, it operates scrambling and singular value decomposition on carrier image to extract the characteristic matrix.Then, according to the algorithm it generates public graph and private graph from characteristics matrix.Finally, it saves the private graph and zero watermark to certification centre.In addition, it applies the run-length coding to make lossless compression on image edge to form secret key, which is used for tamper detection.Experiment shows that the algorithm has very good robustness and security, especially in noise attack resistance.It also achieves excellent effect in terms of tamper detection.

Copyright authenticationVisual cryptographyCharacteristic matrixEdge detection

2015-04-27。曲长波，高工，主研领域：网络工程，信息安全技术。李栋栋，硕士生。

TP309.2

A

10.3969/j.issn.1000-386x.2016.09.076