一种基于地图数据栅格化的鲁棒性盲水印嵌入与提取方法

摘要

本发明涉及一种基于地图数据栅格化的鲁棒性盲水印嵌入与提取方法，有效解决数字地图数据的所有权认证，防止非法拷贝的问题，该方法是，首先利用双混沌系统生成的混沌序列对原始水印信息进行加密以增强水印的安全性；然后对数字地图数据进行栅格化处理，使各个数据点分布到整个栅格单元；最后依据水印信息对位于各个栅格单元中的地图数据集进行修改，在每一栅格单元中嵌入一位水印信息，当所有栅格单元中的数据都处理完后，就实现了水印信息的嵌入；提取水印时，直接从待检测数据获得所嵌入的水印信息；本发明具有很好的不可感知性，以及对数据的增加、删除、修改等更新攻击、数据的裁剪、噪声等攻击行为具有较强的鲁棒性，实用性强。

说明书

一、技术领域

本发明涉及一种基于地图数据栅格化的鲁棒性盲水印嵌入与提取方法，是一种适用于数字地图的版权保护，防止非法拷贝的数字水印方法。

二、背景技术

数字水印技术是随着数字化的进程而逐渐发展起来的数字作品的版权保护技术，目前水印技术的研究主要集中在图像等多媒体数据领域，由于数字地图数据的独特性，使得目前一般的水印算法并不适合于数字地图数据的版权保护。

数字地图是以数字形式来表示空间信息的地图。与模拟地图相比，数字地图更容易受到一些不法用户和商家的随意复制、篡改、传播等非法行为，地图的版权保护问题遇到了新的挑战。

数字地图的版权保护问题已日益引起人们的重视，并提供了一些保护方法，例如，“一种基于方形面块的地图水印算法”(2001年韩国釜山ISIE会议，康万等){“A map datawatermarking using the generalized square mask”(ISIE，Pusan，Korea，2001，KangHwan Il，et al))和“矢量数字地图的鲁棒水印”(2002年瑞士洛桑国际多媒体会议，奥布池等)[“Robust watermarking of vector digital maps”(Proceedings of ICME 2002，Lausanne，Switzerland，2002，R Ohbuchi，et al)]首先把矢量数据按空间位置分块，然后根据水印信息对各个块的坐标值进行轻微的调整，属于空域水印方法；又如，“基于离散余弦变换的矢量地图数据的水印版权保护算法”(2001年国际地理科学和遥感会议，吉塔米列等)[“Copyright protection of vector map using digital watermarking method basedon discrete fourier transform”(Proceedings of IEEE 2001 International Geoscienceand Remote Sensing，2001，I.Kitamura，et al)]和“基于傅立叶描述子的水印多边形线”(2001年国际声学、语音和符号处理会议，土耳其伊斯坦布尔、索拉池地斯等)[“Watermarkingpolygonal lines using fourier descriptors”(Proceedings of IEEE InternationalConference on Acoustics，Speech，and Signal Processing，Istanbul，Turkey，2000，V.Solachidis，et al)]根据定位点构成一个实数序列，然后对实数序列进行傅立叶变换，在变换域嵌入水印信息；“基于网格频谱域的二维矢量地图的水印”(第15次国际形体建模和应用会议，韩国首尔，奥布池等)[“Watermarking 2D vector maps in the mesh-spectraldomain”(The fifth International Conference on Shape Modelling andApplications，Seoul，Korea，2003，R Ohbuchi，et al)]首先利用地图数据构成Delaunay三角网格，再把所构成的网格转化成Laplacian频谱，在频谱系数嵌入水印信息；“基于小波变换的矢量数字地图水印”(地理信息系统协会的年度会议，日本东京，吉塔米列等)[“Watermarking vector digital map using wavelet transformation”(Proceedings ofAnnual Conference of the Geographical Information SystemsAssociation，Tokyo，Japan，2000，Kitamura I，et al)]是把矢量地图转化成类似栅格图像的表示方式，并采用了类似基于小波变换域的图像水印方法；“二维矢量数据的可逆水印”(2004年美国计算机协会国际多媒体和安全会议，邬吉特等)[“Reversible Watermarkingof 2D-vector Data”(Proceedings of the 2004 ACM International Workshop on Multimediaand security，2004，M Voigt et al)]提出了一种基于离散余弦变换的地图数据水印方法；“用于矢量地图版权保护的数字水印”(西安电子科技大学学报，2004，31(5)李媛媛等)提出了根据分块的密度大小自适应调整水印嵌入强度的地图数据水印方法。“矢量图形中基于小波变换的盲水印算法”(光子学报，2004，33(1)李媛媛等)提出了基于小波变换的矢量图形盲水印方法。“一种抗数据压缩的矢量地图数据数字水印算法”(测绘科学技术学报，2006，23(4)，朱长青等)在坐标数据的小波域嵌入水印信息，可以抵抗一定程度上的数据压缩。目前的大多数水印算法主要考虑的是抵抗几何攻击的鲁棒性，而对地图数据来说，它一般是作为其它信息系统的基础数据，由于数据定位精度的权威性使得用户对地图数据的任何操作都会非常谨慎，数据一般不会受到几何攻击，更关心的应是抵抗数据增加、删除、修改、裁剪、噪声等攻击操作的鲁棒性。因此这些方法针对数字地图的特有攻击的鲁棒性并不强。

本发明申请的发明人在文献“基于离散余弦变换的数字地图水印算法”(计算机应用与软件，2007，24(1))中提出了首先把地图数据转化为灰度图像的表示方式，然后对灰度图像进行离散余弦变换，把水印嵌入在离散余弦变换系数中的水印方法；在文献“基于统计特性的矢量地图数据的水印算法”(哈尔滨工业大学学报，2006，增刊)和“矢量地图数据的数字水印技术”(测绘通报，2007，1)中提出了基于统计特性的地图数据的水印方法及其改进方法，整个方案的思路是首先按照某种规则将数据分类，然后修改各个类的统计特征，从而嵌入水印信息。方法对地图数据的增加、删除、修改等更新操作、裁剪操作具有较强的鲁棒性，但是抵抗噪声攻击的鲁棒性不强，其创新仍势在必行。

三、发明内容

本发明的目的在于针对现有技术的不足，根据数字地图数据的特点、使用方式、攻击行为等，提出一种更鲁棒的数字地图数据的水印方法，即一种基于地图数据栅格化的鲁棒性盲水印嵌入与提取方法，可有效抵抗数据的增加、删除、修改等更新操作，以及数据的裁剪、噪声等攻击行为，并且在水印检测时，不需要原始数字地图数据的参与，是一种真正意义上的盲水印方法，有更大的实用性。

为实现这样的目的，本发明采用了如下的技术解决方案，首先利用加密技术对原始水印信息进行加密以增强水印的安全性；然后对数字地图数据进行栅格化处理，依据水印信息对栅格化处理后的数据进行修改，实现水印信息的嵌入。在提取水印时，不需要原始矢量地图数据的参与，直接从待检测数据获得所嵌入的水印信息，是一种盲水印方法。

本发明的方法主要包括水印嵌入和水印提取两个过程，如图1所示。具体步骤如下：

1、水印嵌入过程

原始水印信息{w_i，i＝1，2，...，I×J}为I×J大小的二值图像，为增强水印的安全性，首先利用双混沌系统生成一个混沌序列对水印信息进行加密；然后制作一个特殊的I×J大小的二维栅格图，对数字地图的各个要素层的数据进行栅格化处理，数字地图的数据集为{(x_i，y_i)，i＝1，2，...，N}，N为数据集的个数，根据特定的映射规则S＝f(x_kx_k-1...x₀，y_ky_k-1...y₀)＝mod(x₂x₁，I)+mod(y₂y₁，J)×I把各个数据点映射到每一栅格单元中；最后，根据水印信息以及数据的误差容限g对位于各个栅格单元中的数据的特定信息进行修改，从而实现水印信息的嵌入。

2、水印提取过程

水印信息的提取其实是水印信息嵌入过程的逆过程，按照水印嵌入过程相同的栅格化方法对数字地图的数据集进行栅格化处理，然后提取位于各个栅格单元中的数据的特定信息从而获得“1-比特”的水印信息w_i，把这些水印信息进行相应的解密就获得了嵌入在数据中的版权信息w。由于提取水印信息是直接通过各个栅格单元中的数据的特定信息获得的，因而并不需要原始数字地图数据的参与，是一种真正意义上的盲水印方法，有更大的实用性。

四、附图说明

图1为本发明的水印嵌入/提取过程的流程图。

在图1中数据的误差容限是一个变量，不同比例尺的数字地图数据有不同的数据误差容限。

图2为基于双混沌序列的水印加密流程及加密效果图。

其中图2(a)为水印加密流程图，图2(b)为原始水印信息，它是一个32×32大小的二值图像，用来作为版权标志，图2(c)为加密后的水印信息，它是真正要嵌入的水印。

图3为嵌入水印后图形视觉上不可感知性的效果图。

图3中的测试数据为1∶25万地图数据，线画图为原始数据可视化的图形，圆点表示嵌入水印后的数据，右图是左图选定区域放大后的效果图。可以看出，图形经过放大后，人眼仍感觉不到变化，表明该发明在视觉上是不可感知的。

图4为水印方法对数据更新攻击的鲁棒性。

其中图4(a)、(b)、(c)分别为对原始数据增加60％、删除50％和修改30％后的可视化效果图，图4(d)、(e)、(f)是从中提取出的水印。

图5为水印方法对数据裁剪攻击的鲁棒性。

其中图5(a)-(h)为常用的8种裁剪攻击方式，图5(i)-(p)分别为从中提取出的水印。

图6为水印方法对噪声攻击的鲁棒性。

其中图6(a)、(b)添加的噪声服从高斯分布，噪声强度分别为1、2，图6(c)、(d)是从中提取出的水印。

五、具体实施方式

下面结合附图和实施例对本发明的技术方案做进一步的描述。

1、水印嵌入：水印嵌入过程主要包括水印信息加密、数字地图数据栅格化处理、修改各个栅格单元中的数据三部分。

1)水印信息加密

本发明采用基于双混沌序列的水印加密方法。原始水印信息{w_i，i＝1，2，...，I×J}为I×J大小的二值图像，为增强水印的安全性，首先对水印信息进行加密。采用Logistic映射生成伪随机序列{x_k}，同时采用混合光学双稳模型生成伪随机序列{y_k}，再把随机序列{x_k}和{y_k}相对应的元素进行“XOR”操作生成加密密钥流{d_k}，然后，把加密密钥流与水印数据流逐字节进行“XOR”操作，从而完成水印信息的加密。

第一步，给定密钥x₀作为系统的初值，x₀∈(0，1)。

{第二步，以密钥x₀为初值，对式(1)进行反复迭代，生成足够长度的随机序列{x_k，k＝0，1，2，3，......}，对随机序列{x_k，k＝0，1，2，3，......}的各个元素x_k，从小数点后首位非0数字开始，顺序取9位数字组成一个长整型数据Ld1_k，所有元素处理完后，得到长整型随机序列{Ld1_k，k＝1，2，3，......}。

x_k+1＝μx_k(1-x_k)                              (1)

式(1)中：0≤μ≤4，称为分枝参数。当x_k∈(0，1)且3.5699456＜μ≤4时，logistic映射工作于混沌状态。

{以密钥x₀为初值，对式(2)进行反复迭代，以同样的方法生成长整型随机序列{Ld2_k，k＝1，2，3，......}。

x_n+1＝A×sin²(x_n-x_B)                       (2)

式(2)是一混合光学双稳模型，随着参数A和x_B的变化，系统将从固定点失稳，经倍周期分叉进入混沌。在混沌区，除去其窗口，系统输出序列{x_k}是一个很好的随机序列。

第三步，对随机序列{Ld1_k，k＝1，2，3，......}和{Ld2_k，k＝1，2，3，......}的相对应的元素进行“XOR”操作，得到随机序列{Ld_k，k＝1，2，3，......}，即{Ld_k＝Ld1_kLd2_k，k＝1，2，3，......}。

随机序列{Ld_k，k＝1，2，3，......}是一个长整型数据序列，对序列的各个元素Ld_k进行取模运算，得到一个整型随机序列{d_k，k＝1，2，3，......}，把它作为加密密钥流。

第四步，把水印数据流{m_k，k＝0，1，2，3，......}与加密密钥流{d_k，k＝0，1，2，3，......}进行“XOR”操作，生成乱码形式的水印密文流{w_k，k＝0，1，2，3，......}，即w_k＝m_kd_k，完成水印信息的加密。

2)数字地图数据栅格化处理

首先，根据水印信息的大小I×J制作一个与水印信息同大小的二维栅格图；然后，从测绘数据库中读取数字地图的数据集{(x_i，y_i)，i＝1，2，...，N}，N为数据集中数据的个数；最后，对地图数据集中的每一个数据点(x_i，y_i)，根据特定的映射规则S＝f(x_kx_k-1...x₀，y_ky_k-1...y₀)＝mod(x₂x₁，I)+mod(y₂y₁，J)×I把该数据点映射到二维栅格图相应的栅格单元中。当数据集中的所有数据点都处理完后，就完成了数字地图数据的栅格化处理。

3)修改各个栅格单元中的数据

经过上一步栅格化处理后，地图数据被分配到各个栅格单元中，在每一栅格单元中嵌入1位水印信息。第i个栅格单元中要嵌入的水印信息为w_i，根据水印信息以及数据的误差容限g对位于这一栅格单元中的所有数据的特定信息进行显著的修改，从而实现水印信息的嵌入。

对每一个数据点point(x，y)按以下步骤修改：

第一步，获取数据点point(x，y)的特定信息nChara(x，y)、尾数nMantissa；

第二步，如果在该栅格单元的数据集中要嵌入的信息w_i＝1，则执行第三步；否则，执行第六步；

第三步，如果数据点的特定信息nChart＝B，并且尾数满足nMantissa-gw_j＜0，则修改该坐标点为point[i]＝point[i]-gw_j；

第四步，如果数据点的特定信息nChart＝B，并且尾数满足nMantissa+gw_j＞10，则修改该坐标点为point[i]＝point[i]+gw_j；

第五步，否则，修改该坐标点的尾数信息nMantissa＝D，转第九步；

第六步，如果数据点的特定信息nChart＝A，并且尾数满足nMantissa+gw_j＜0，则修改该坐标点为point[i]＝point[i]+gw_j；

第七步，如果数据点的特定信息nChart＝A，并且尾数满足nMantissa-gw_j＞10，则修改该坐标点为point[i]＝point[i]-gw_j；

第八步，否则，修改该坐标点的尾数信息nMantissa＝C。

第九步，该数据点修改完毕。

上述各步中，数据点point(x，y)的特定信息nChara(x，y)指的是该数据点x坐标的十位信息，A、B分别代表该十位信息的奇偶性；尾数nMantissa指的是该数据点x坐标的个位信息，C、D分别代表该个位信息为4和5；g为数据的误差容限。

2、水印提取过程

水印信息的提取其实是水印信息嵌入过程的逆过程，按照水印嵌入过程相同的栅格化方法对数字地图的数据集进行栅格化处理，然后提取位于各个栅格单元中的数据的特定信息从而获得“1-比特”的水印信息w_i，把这些水印信息进行解密就获得了嵌入在数据中的版权信息w。由于提取水印信息是直接通过各个栅格单元中数据的特定信息获得的，因而并不需要原始数字地图数据的参与，是一种真正意义上的盲水印方法，有更大的实用性。

本发明利用数字地图数据的栅格化处理，把水印信息嵌入到各栅格单元数据的特定信息中，方法易于实现，具有不可感知性好和鲁棒性强等特点，并且在水印检测时不需要原始数据的参与，是一种盲水印方法，适用范围广，易于推广到如统计数据等其它类型数据的版权保护中。

以下为验证本发明的实用性，选择一幅1∶25万数字地图的交通数据作为实验数据源，该要素层的数据量为270KB，共有12229个定位点。

1、嵌入水印后对图形视觉上的不可感知性的影响

为了保证水印的安全性，嵌入水印后，图形在视觉上不能引起人们可感知的失真，图3为嵌入水印前后图形视觉效果的对比图。其中线画图为原始数据可视化的图形，圆点表示嵌入水印后的数据，图形的变化是非常小的，人眼是根本感觉不到的。右图是左图选定区域放大后的效果图，可以看出，图形经过放大后，人眼仍感觉不到变化。因而该水印方法在视觉上是不可感知的。

2、嵌入水印后对数据定位精度的影响

对数字地图数据来说，水印的不可感知性不仅指图形视觉上的不可感知性，更重要的是水印操作所引起的数据变化不能超过数据定位精度的限制。数据精度是评价地图数据水印的一个重要指标，因为数据精度是地图数据的本质特征，缺乏精度的数据将失去价值。水印的操作不仅不能引起人们视觉上的变化，更不能引起数据质量的明显下降，建立的水印方法必须满足对数据精度是透明的这一基本要求。

对数据定位精度的透明性，本发明采用均方误差和最大误差来衡量，测试数据为1∶25万地图数据，数据的单位为1/4秒，测试结果如表1所示。

表1数据精度不可感知性统计表

  误差量  点数  占数据总量的百分比  均方误差  0  6077  49.6934  1.15439  1  1844  15.0789  2  651  5.32341  3  3657  29.9043  ＞3  0  0

“误差量”是指由于嵌入水印所引起的数据失真的幅度，“点数及百分比”指的是具有相应误差量的数据点的个数及其在整个数据中所占的比重，“均方误差”指的是由于水印的嵌入操作对整个数据所引起的误差的衡量。

由表1可知，嵌入水印所引起的均方误差非常小，最大误差也在数据的误差容限范围内，并且将近一半的数据是没有误差的。因此，该方法在数据的定位精度上也是透明的。

3、对数据更新攻击的鲁棒性

图4(a)是对原始数据再增加7338个数据点后的可视化效果图，新增加的数据量占原数据量的60％，图4(d)是从中提取出的版权信息。

图4(b)是对原始数据随机删除6115个数据点后的可视化效果图，删除的数据量占原数据量的50％，图4(e)是从中提取出的版权信息。

图4(c)是对原始数据中的部分数据进行编辑修改后的可视化效果图，修改的数据量占原数据量的30％，图4(f)是从中提取出的版权信息。

实验表明，即使对原始数据增加60％、删除50％、修改30％的数据量后，仍能从中提取出有效的版权信息，因此，方法对数据的增加、删除、修改等更新操作具有较强的鲁棒性。

4、对数据裁剪的鲁棒性

本发明采用常用的8种裁剪方式测试水印的鲁棒性。

图5(i)-(p)分别为从图5(a)-(h)这8种裁剪方式下提取出的水印信息，可以看出，该方法对数据的裁剪攻击具有较强的鲁棒性。

5、对噪声攻击的鲁棒性

图6是对含水印数据添加随机噪声后的可视化效果图，所添加的噪声服从高斯分布，图6(a)、(b)添加的噪声强度分别为1、2，图6(c)、(d)是从中提取出的版权信息，实验表明，在数据精度允许的范围内，水印具有较强的抵抗噪声攻击的能力。

综合分析，与现有的数字地图水印方法相比，本发明的方法具有以下一些优点：

1、本发明方法是一个盲水印方法，水印检测时不需要原始数字地图数据的参与，适用范围广。

2、基于变换域的方法往往依赖于数据点的排序，而实际上对数字地图数据来说，数据是无序的，没有一个固定的数据顺序，对数据进行乱序操作既不影响图形的视觉效果，也不影响数据的定位精度，改变的只是数据的存储位置，从而使得这类方法抗数据的乱序攻击的鲁棒性不强，即使在原始数据的参与下可以对数据进行重新排序，但对大数据量的数字地图数据来说，仍是一个很大的时间消耗。而本发明不依赖于数据点的顺序，对数据点的乱序操作具有很强的免疫力，易于推广到如统计数据等其它类型数据的版权保护中，因此有更大的实用性。

3、目前的方法一般依赖于数据实体(对象)，而对数字地图数据来说，对象的表示方法不唯一，同一个地理实体可以用多种不同的模型表示，如某一对象既可表示成L＝{(x₁，y₁)，(x₂，y₂)，...，(x_n，y_n)}，也可表示成L＝{(x_n，y_n)，(x_n-1，y_n-1)，...，(x₁，y₁)}，当然还可表示成L₁＝{(x₁，y₁)，(x₂，y₂)，......，(x_k-1，y_k-1)}、L₂＝{(x_k，y_k)，(x_k+1，y_k+1)，...，(x_n，y_n)}等等许多形式，这种同一对象的多种表示方式容易引起检测水印的失败。而本发明方法不依赖于地理实体，仅仅依赖于组成地理实体的各个数据点本身，因而抗地理实体的不同表达模型的攻击能力较强。

4、数据的透明性(不可感知性)较好。由于水印嵌入时严格限定对数据的修改在数据的精度容限范围内，因此可以保证数据具有较好的不可感知性，图3和表1也证明了这一点。

5、水印抵抗各种常见攻击的鲁棒性强。地图数据常见的攻击方式有数据更新、裁剪、噪声等，但一般不会受到几何攻击。本发明充分考虑到数字地图数据的这一特点，方法对数据的增加、删除、修改等更新攻击和裁剪、噪声等攻击都具有较强的鲁棒性，图4、图5、图6也证明了这一点。