一种抗几何变换攻击的矢量数据盲水印算法

王云飞，赵 婧，王 拓，崔伟宏

(1.中国科学院遥感应用研究所，北京 100101；2.北京四维图新科技股份有限公司，北京 100028)

1 概述

矢量数据是国家经济建设中的一种重要战略资源，其安全性问题十分值得关注。数字水印技术作为保护数据版权的一种有效手段，近年来得到广泛的应用。对于矢量数据，目前水印算法研究主要集中在以下4个方面：

(1)基于坐标点的水印算法。该类算法将水印直接嵌入到地物坐标点中，例如基于灰度图像的矢量地理空间数据水印算法[1]和抗数据压缩的矢量地图数据数字水印算法[2]。

(2)基于变换域的水印算法。该类算法将水印信息嵌入到坐标序列的变换域中，例如基于小波变换的水印算法[3-4]和基于离散傅里叶变换(Discrete Fourier Transform, DFT)的水印算法[5-6]。

(3)基于地图划分的水印算法。该类算法将水印信息分区域嵌入到地图坐标中，例如基于MQUAD的水印算法[7]和基于坐标映射划分的水印算法[8-10]。

(4)基于坐标点排序划分的水印算法。该类算法通过新增或移动坐标点到指定的坐标划分区域来嵌入水印，例如文献[11-12]的算法。

现有的矢量数据水印算法对地图噪声、地图裁剪等常规攻击方式具有较好的鲁棒性，但是对几何变换攻击的鲁棒性较差。目前可以抵抗几何变换攻击的水印算法主要包括 2种：(1)通过几何校正[13-14]，恢复待测数据到原始数据的坐标体系下，但这种方法精度低，不利于在实际中应用。(2)基于变换域的水印算法，但这类算法大多属于非盲水印算法，并且对随机增点和地图压缩攻击鲁棒性较差。针对以上问题，本文在现有研究成果的基础上，提出一种抗几何变换攻击的矢量数据盲水印算法，该算法主要针对线图层和面图层。

2 抗几何变换攻击的矢量数据水印算法

2.1 算法思路

为了增强水印信息对几何变换攻击的鲁棒性，一种有效的方式是将水印信息嵌入到几何变换不变域中。以线地物为例，如图 1所示，其中，P1～P5为线地物坐标节点；r1～r4为坐标节点与起始坐标节点的距离。地物经过几何变换后，每一个节点的坐标位置都发生了变化，但是每个节点之间的距离比值并没有发生变化，例如图中的r2/r1，不管地物经过何种几何变换，其比值都是固定的，因此，本文选择该值作为几何变换的不变域进行水印嵌入，将水印信息按位嵌入到图中的r2/r1、r3/r1、r4/r1中。

图1 线状地物的几何不变域

此外，如果直接选取地物的坐标节点进行水印嵌入，提取出的水印信息很容易会被地图压缩和随机增点等攻击所干扰。为了增强水印的鲁棒性，本文将水印嵌入到地物的特征点中。尽管矢量数据的冗余较小，但是在不影响精度的条件下，适当的数据压缩是被允许的。如图2所示，点P1、P3、P4、P6为线的特征点，P2和 P5为线的冗余点，删除此类点即实现了数据压缩，而且不会对原始数据的精度影响太大。

图2 线数据的特征点和冗余点

2.2 水印信息的生成

目前水印信息有2种生成方式：(1)利用水印图像获取水印字节；(2)直接转换水印字符为水印字节。相比之下，方式(1)生成的水印信息可识别性较好，如果水印字节中的部分字节被干扰，水印信息仍能较完整地识别出来，缺点是水印占据空间较大，嵌入一条完整的水印信息需要的坐标点数目较多，因此，该方式只适用于地物坐标节点较多的地图。方式(2)生成的水印信息鲁棒性相对较弱，优点是占用空间很小，水印可以多次重复嵌入和提取，因此，可以通过多数原则来判别水印信息的每一位值，从而提高水印信息的鲁棒性。

本文将水印分别嵌入到每个地物特征点的距离比例中，从水印嵌入的完整性上考虑，算法选择方式(2)生成水印信息。为进一步增强水印的抗干扰能力，利用汉明(7, 4)码对初始水印信息进行纠错编码。

2.3 水印嵌入流程

水印的嵌入流程如下：

(1)按照一定的压缩比例，利用 Douglas-Peucker压缩算法提取原始图层地物的特征点，对每个特征点，属性中记录特征点所在的地物编号和节点编号。

(2)计算每个地物的特征点距离比值，将水印信息按位嵌入到该距离比值中。其中，每一个地物嵌入一条水印信息，如果地物特征点数目小于水印信息位数目，则按照特征点数目，嵌入水印的前几位信息。

定义 ai为每一个坐标节点的距离比值，其中，a1=r2/r1；a2=r3/r1；…；an=rn+1/r1。将 ai按由小到大的顺序组成一个序列L，定义一个阈值C，将L划分为不同的部分，如图3所示。如果当前水印值为0，则将ai移动到偶数间隔中，否则，将ai移动到奇数间隔中。

图3 序列L的划分

假设序列L中一共含有n个比值数据，其中，最小值和最大值分别为amin和amax；阈值C的计算公式如下：

其中，u为用户自定义系数，一般可以选择为10。由于amin和amax用于计算阈值C，因此这2个值不嵌入水印信息。

最后根据嵌入水印后的ai和r1，计算嵌入水印后的特征点距离ri+1，并根据ri+1移动对应的特征点Pi+2的坐标，从而完成该水印位的嵌入。

(3)根据特征点图层中每个点的地物编号和节点标号，替换原始图层中的特征点，从而实现原始图层的水印嵌入。

2.4 水印提取流程

水印的提取算法是嵌入算法的逆过程：

(1)按照水印嵌入时的压缩比例，利用 Douglas-Peucker压缩算法提取原始图层地物的特征点。

(2)计算每个地物的特征点距离比值 ai，并将 ai按照大小关系形成序列L，将L按阈值C进行划分，根据ai所在的奇偶间隔提取出相应的水印信息位。

(3)根据每一个地物提取出的水印信息，由多数原则选取水印信息的每一位值，最终提取出嵌入的水印信息。

3 实验结果与分析

下面通过实验对本文的水印算法进行性能分析。地图采用四川省县级区划行政图，一共包括234个多边形，Douglas-Peucker压缩限差选取0.005，水印信息选取字符串“IRSA”，占 32 bit，经过汉明码纠错编码后占56 bit，嵌入水印后的地图如图4所示。

图4 嵌入水印后的县级区划行政图

3.1 透明性

图5展示了原始图层和嵌入水印后图层的叠加图，从可视化角度看，2个图层的数据几乎一致，因此，本文的水印算法在视觉上是透明的。

图5 原始图层和嵌入水印后图层的叠加图

3.2 嵌入误差

原始图层一共含有234个多边形、71 730个节点，通过 Douglas-Peucker算法，水印数据嵌入到其中的15 918个特征点的坐标中。嵌入误差的实验结果如表1所示，可以看出，水印嵌入后坐标点误差均在图层精度范围内。

表1 本文算法的嵌入误差

3.3 鲁棒性

最后就随机噪声、随机增点、地图压缩、地图裁剪和几何变换攻击对水印信息带来的干扰，对水印算法的鲁棒性进行分析，实验结果如表2所示。从中可以看出，本文算法对常规的地图攻击方式，例如随机噪声、随机增点、地图压缩、地图裁剪等鲁棒性较高，只有在地图压缩比例过大时，算法才会提取失败。在实际应用中，过大比例的地图压缩会严重影响原始数据精度，因此，这种攻击方式并不常见。由于本文算法将水印信息嵌入到地物特征点的距离比值中，因此对于几何变换攻击，水印信息的提取不受影响。

表2 本文算法的水印鲁棒性

4 结束语

本文提出一种可以抵抗几何变换攻击的矢量数据盲水印算法，算法选取地物坐标节点距离比值这一几何不变域作为水印嵌入位。通过实验证明，算法能够抵抗几何变换攻击，水印在经过适度地图压缩、地图裁剪和随机增点等攻击后可以正确提取出来，只有当地图压缩比例过大时，水印才会提取失败，这也是下一步需要改进的方向。

[1]郭思远, 朱长青.基于灰度图像的矢量地理空间数据水印算法[J].测绘工程, 2008, 17(1): 21-23.

[2]朱长青, 杨成松, 李中原.一种抗数据压缩的矢量地图数据数字水印算法[J].测绘科学技术学报, 2006, 23(4):281-283.

[3]杨成松, 朱长青.基于小波变换的矢量地理空间数据数字水印算法[J].测绘科学技术学报, 2007, 24(1): 37-39.

[4]李媛媛, 许录平.矢量图形中基于小波变换的盲水印算法[J].光子学报, 2004, 33(1): 97-100.

[5]许德合, 王奇胜, 朱长青.基于 DFT幅度的矢量地理空间数据数字水印算法[J].测绘科学, 2008, 33(5): 129-131.

[6]许德合, 朱长青, 王奇胜.利用QIM的DFT矢量空间数据盲水印模型[J].武汉大学学报: 信息科学版, 2010,35(9): 1100-1103.

[7]Ohbuchi R, Ueda H, Endoh S.Robust Watermarking of Vector Digital Maps[C]//Proceedings of IEEE Conference on Multimedia and Expo 2002.Lausanne, Switzerland:IEEE Press, 2002: 1-4.

[8]王 勋, 林 海, 鲍虎军.一种鲁棒的矢量地图数字水印算法[J].计算机辅助设计与图形学学报, 2004, 16(10):1377-1381.

[9]闵连权.一种鲁棒的矢量地图数据的数字水印[J].测绘学报, 2008, 37(2): 262-267.

[10]杨成松, 朱长青, 陶大欣.基于坐标映射的矢量地理数据全盲水印算法[J].中国图象图形学报, 2010, 15(4):684-688.

[11]王 伟, 李 岩.一种鲁棒性的2D矢量图形水印算法[J].中国图象图形学报, 2007, 12(2): 200-205.

[12]Wang Chungming, Wang Pengcheng.Data Hiding on Point-sampled Geometry[J].Journal of the Chinese Institute of Engineers, 2006, 29(3): 539-542.

[13]金 聪, 叶俊民, 许凯华.具有抗几何攻击能力的盲数字图像水印算法[J].计算机学报, 2007, 30(3): 474-481.

[14]杨晓元, 季称利, 王育民.基于几何变换特征集的水印图像失真校正算法[J].计算机工程与应用, 2005, 41(16):127-129.