图像四叉树剖分下的自适应数字水印算法

2017-12-29刘文星陈伟刘渊

网络与信息安全学报 2017年12期

刘文星，陈伟，刘渊

图像四叉树剖分下的自适应数字水印算法

刘文星，陈伟，刘渊

（江南大学数字媒体学院，江苏无锡 214122）

提出了一种图像四叉树矩形剖分下的自适应数字水印算法。通过对原始图像在多个尺度上进行最小二乘多项式逼近，将图像进行非均匀剖分，并以四叉树结构的形式进行表达。该四叉树结构既实现了对原始图像的逼近，同时携带了图像的纹理结构信息。通过统计各子区域上的剖分网格数目，计算不同区域上水印嵌入的强度，从而实现自适应数字水印方案。实验结果表明，该算法具有良好的透明性和顽健性。

图像剖分；四叉树；最小二乘；水印

1 引言

随着当代信息技术的蓬勃发展，传统信号处理的研究内容及应用范围得到极大扩张。作为一类典型的二维信号，数字图像处理涵盖了去噪、压缩、重构、超分辨率、特征提取、水印等多个领域。与一维信号相比，二维图像的特征更为丰富，也更为复杂。因此，如何高效地表达数字图像是上述诸多应用的基础[1]。

为了克服小波方法在捕获图像奇异特征方面的不足，来自多个领域的多位学者在小波变换理论的基础上发展了多尺度几何分析理论[3]，主要包括楔波[4]（wedgelet）、曲线波[5]（curvelet）、脊波[6]（ridgelet）、条带波[7]（bandelet）、剪切波[8]（shearlet）、轮廓波[9]（contourlet）等。这些不同方法的理论是相似的，差别在于所选择的基函数形态不同。与小波变换相比，多尺度几何变换改进了图像在奇异处的表达性能，其应用范围也囊括了去噪、压缩、复原、安全等图像处理的多个领域。但是，实际图像的类型十分复杂，不仅导致各种多尺度分析工具的计算复杂度很高，甚至会出现逼近效果不如传统小波变换的情形。

作为图像信息隐藏[10~12]的重要分支，数字水印技术得到广泛的研究与发展[13,14]。针对多尺度几何变换计算复杂度高、适用图像类型单一的特点，本文研究图像四叉树矩形剖分下的数字水印算法。图像四叉树结构分解作为一种高效的图像多尺度逼近方法，在图像处理的多个领域取得了成功的应用。在通常的数字水印嵌入算法中，首先图像经过均匀剖分（一般为8×8），对所有分块逐个进行频域变换（DCT、DWT等）后，再对每组频域系数施加乘性或加性法则完成水印的嵌入。由于对图像各区域不加区分地对待，即不论某区域的纹理复杂程度如何，均以相同的强度进行水印的嵌入，从而在水印图像质量与算法顽健性之间很难取得平衡。

另一方面，从人类视觉系统（HVS, human visual system）的特性出发，它具有以下特点：1)对图像边缘位置信息敏感，而对边缘的灰度误差不敏感；2) 视觉掩盖效应，受背景亮度、纹理复杂度及信号频率的影响，在保证不被人眼察觉的前提下，图像不同局部特征的区域允许被改变的强度不同[15]。

本文从图像四叉树剖分算法出发，通过图像剖分结果的非均匀特性，利用人类视觉系统特征，充分考虑图像不同区域的灰度特性，根据图像不同区域的纹理复杂程度，设计自适应水印嵌入算法，提高水印图像质量和算法的顽健性。

图1 图像区域的自相似剖分及其四叉树表达

2 数字图像四叉树剖分与重构

2.1 数字图像四叉树剖分

简记为

如图1(b)所示，四叉树的根节点代表原始图像，不同的层次代表递归剖分步数，叶子节点为最终剖分结果，每个剖分子区域（即每个叶节点）用一个几何面片（本文选取二元一次多项式）进行逼近。因此，只需在四叉树叶子节点处存储面片信息即可。

最小二乘法是一种数学的优化方法，通过最小化误差平方和拟合数据最佳的函数匹配，利用最小二乘法匹配的函数可以简便地求出未知的数据，并使所求的数据与原始数据的平方差最小。

本文是对图像数据进行处理，所以使用的是二维情形下的最小二乘法。

线性二元函数表达式如下。

误差平方差可表示为

计算平方差最小情况下的参数、、，即对上式的每个参数求偏导。

化简并展开

将上述每个部分用1,2,…,9表示，将方程组化为矩阵形式

图像的非均匀四叉树剖分流程如图2所示。

图2 图像的非均匀四叉树剖分流程

2.2 图像重构

(a) 原始图像

(b) 四叉树剖分

图3 图像的四叉树剖分

对于给定的图像，误差阈值设定越小，四叉树剖分网格越精细，叶子节点越多，则重构图像质量越高，但时间花费越高。表1列出了对同一张Lena图像进行不同精度剖分的实验结果。

从实验结果可以看出，图像剖分结果与预期一致。对于同一张图像，随着误差阈值的减小，剖分网格不断细化，新增加的精细网格主要集中在图像纹理细节丰富区域，而灰度平缓区域的网格剖分几乎保持不变。这一现象本质上与图像的多分辨分析及多尺度变换一致，这也正是下文中设计水印算法的依据。

3 图像四叉树剖分下的数字水印算法

3.1 算法设计思路

如前文所述，在通常的频域水印嵌入算法中，将图像均匀地剖分为8×8分块，并未考虑图像纹理在区域分布上的非均匀性。本文首先对图像进行非均匀四叉树剖分，然后计算每个8×8分块中细分子块的数目。根据剖分算法可知，在图像纹理复杂的区域，剖分网格越精细，即细分子块越多，反之亦然。因此，用细分子块数目衡量该区域的纹理复杂程度。

本文算法设置最小剖分子块尺寸为2×2。因此，在任意8×8分块中，所含子块的数目只有6种：1、4、7、10、13和16，如图4所示。

图4 细分子块的种类

3.2 数字水印非均匀嵌入算法

1) 水印嵌入算法

①对二值水印图像作Arnold置乱操作，得到经次置乱的水印图像img_mark，其中作为密钥。

其中，参数代表水印嵌入灵活度，取值范围为[0.01, 0.05]。

if_mark= 0, then= 1

else= −1

_dct[0][0]=_dct[0][0]×(1+sI)

④将每个分块进行DCT逆变换，得到含水印图像。

2) 水印提取算法

①对含水印图像，按8×8分块做DCT变换，并提取出每个分块的DC分量_dct[0][0]。

②对原图做相同操作，记为_dct[0][0]。

③ if_dct[0][0]−_dct[0][0] > 0

水印 = 0

else 水印 = 1

对所得水印图像做次逆Arnold变换，恢复水印图像_。

表1 不同误差阈值下的图像剖分结果

4 实验

为了比较所提取水印图像的质量，计算归一化相关度（NC, normalized correlation）来度量提取水印与原始水印的相似程度，以此评判算法的顽健性。计算公式如下。

本文对不同嵌入强度下多种攻击（包括无攻击、椒盐噪声、剪切、不同压缩率等）进行了测试。因篇幅所限，这里仅显示对Lena图的实验结果，包括被攻击水印图像的形态及其、水印嵌入强度、提取的水印图像的形态及误差等，如表2~表6所示。嵌入强度表征了自适应水印嵌入的灵活程度，实验结果表明，通过适当提高嵌入强度，本文算法对以上各种攻击的顽健性均有所提高，特别是剪切攻击和压缩攻击，效果更为明显。

表2 无攻击情况下测试结果

表3 椒盐噪声攻击情况下测试结果

表4 剪切攻击情况下测试结果

表5 压缩攻击（压缩率0.4）情况下测试结果

表6 压缩攻击（压缩率0.6）情况下测试结果

表7 不同强度受JPEG压缩的水印效果（Q=40）

以上实验中，嵌入强度的范围在（0.01, 0.06）较为合适，通过大量实验，提高嵌入强度对各种攻击的顽健性均有提高，其中最为明显的是剪切攻击，其次是压缩攻击，椒盐噪声攻击的顽健性几乎没有提高。同时也能发现强度的提高会降低加水印图片的质量，灵活度提升到0.04以上时，几乎各种攻击的顽健性的提升几乎为零，甚至会出现=0.03与=0．02剪切攻击顽健性下降的情况，所以为了保证嵌水印图像的质量即较高，将设置为合适的值即可，经过实验，通常设置=0.02。

5 传统均匀嵌入水印的方法比较

常用的DCT域上将水印信息嵌入DC系数的方法虽然在抗压缩方面的顽健性较好，但改变DC分量对宿主图像的影响很大，会出现方块效应。

6 结束语

针对传统图像多尺度几何变换计算复杂度高、适用图像类型单一等缺点，本文基于图像的四叉树矩形剖分，将图像表达为一系列几何面片，并根据逼近结果计算图像不同区域的纹理复杂程度，设计出自适应的非均匀水印嵌入强度算法。实验结果表明，本文算法在保证载体图像质量的条件下，对多种攻击（特别是噪声攻击、压缩攻击等）的顽健性均有所提高。

[1] YANG J, PENG Y, XU W, et al. Ways to sparse representation: a overview[J]. Science in China Series F: Information Sciences, 2009, 52(4): 547-722.

[2] 戴琼海. 多维信号处理: 快速变换、稀疏表达与低秩分析[M]. 北京: 清华大学出版社, 2016.

DAI Q H. Multidimensional signal processing: fast transform, sparse representation, and low rank analysis[M]. Beijing: TsinghuaUniversityPress, 2016.

[3] 焦李成，谭山. 图像的多尺度几何分析: 回顾和展望[J]. 电子学报, 2003, 31(12A):1975-1981.

JIAO L C, TAN S. Development and prospect of image multiscale geometric analysis[J]. Acta Electronica Sinica, 2003, 31(12A): 1975-1981.

[4] CANDÈS E J. Ridgelets: theory and applications[D]. Stanford: Department and Statistics, Stanford University, 1998.

[5] CANDÈS E J, DONOHO D L. Curvelets and curvilinear integrals[J]. Annals of Smfisfies, 1999, 27(3):859-897.

[6] DONOHO D L. Wedgelets: nearly minimax estimation of edges[J]. Journal of Approximation Theory, 2001, 113(1):59-90.

[7] PENNEC E L, MALLAT S. Sparse geometric image representation with bandelets[J]. IEEE Transactions on Image Processing, 2005, 14(1): 1665-1677.

[8] EASLEY G, LABATE D, LIM W Q. Sparse directional image representation using the discrete shearlet transform[J]. Applied and Computational Harmonic Analysis, 2008, 25 (1): 25-46.

[9] DO M N, VETTERLI M. The contourlet transform: an efficient directional multiresolution image representation[J]. IEEE Transactions on Image Processing, 2005, 14(12): 2091-2106.

[10] 陈伟，陈亚楠，刘渊. 复数基下的数字媒体表达及信息隐藏[J]. 网络与信息安全学报, 2016, 2(12): 20-26.

CHEN W, CHEN Y N, LIU Y. Digital media representation under complex number base and its application on information hiding[J]. Chinese Journal of Network and Information Security, 2016, 2(12): 20-26.

[11] HENGARTNER U. Hiding location information from location-based services[C]//The International Conference on Mobile Data Management, Mannheim. 2007:268-272.

[12] 余建德，宋瑞霞，齐东旭. 基于数字图像三角形剖分的信息伪装算法[J]. 计算机研究与发展, 2009,46(9):1432-1437.

YU J D, SONG R X, QI D X. A Scheme for steganography based on triangular partition of digital images[J]. Journal of Computer Research and Development, 2009,46(9):1432-1437.

[13] 孙圣和，陆哲明. 数字水印技术及应用[M]. 北京: 科学出版社, 2004.

SUN S H, LU Z M. Digital watermarking technology and application[M]. Beijing: Science Press, 2004.

[14] 王志红, 黄惠芬, 常玉红. 基于SVD分解和Hadamard变换的图像半脆弱水印技术[J]. 网络与信息安全学报, 2017,3(5): 26-31.

WANG Z H, HUANG H F, CHANG Y H. Semi-fragile watermarking technology based on SVD decomposition and Hadamard transform[J]. Chinese Journal of Network and Information Security, 2017, 3(5): 26-31.

[15] 王晶，王向阳. 基于人类视觉系统的数字图像水印方法[J]. 计算机工程, 2011,37(13):107-108,112.

WANG J, WANG X Y. Digital image watermark method based on human visual system[J]. Computer Engineering, 2011, 37(13): 107-108,112.

Adaptive digital watermarking algorithm under image quad-tree partition

LIU Wen-xing, CHEN Wei, LIU Yuan

(School of Digital Media, Jiangnan University, Wuxi 214122, China)

An adaptive digital watermarking algorithm based on image quad-tree partition was proposed. The original image was approximated by various least square polynomial patches at multiple scales and was organized by a quad-tree structure. At the same time, this representation also reflected the texture information of image. By calculating the watermark embedding intensity in different regions, an adaptive digital watermarking scheme based on the number of the refined meshes in each region was realized. The experiment results show that this algorithm has the good imperceptibility and robustness.

image partition, quad-tree, least square, watermarking

TP393

10.11959/j.issn.2096-109x.2017.00219

2017-10-14；

2017-12-03。

陈伟，wchen_jdsm@163.com

国家自然科学基金资助项目（No.61602213）；国家科技支撑计划基金资助项目（No.2015BAH54F00）

The National Natural Science Foundation of China (No.61602213), The National Science and Technology Support Program (No.2015BAH54F00)

刘文星（1994 -），男，重庆人，江南大学本科生，主要研究方向为图像处理。