基于空间拓扑的二维矢量空间数据数字水印方法

摘要

基于空间拓扑的二维矢量空间数据数字水印方法，包括有水印载体提取过程、对水印载体嵌入水印信息的过程和从水印载体检测水印信息的过程；所述水印载体提取过程为，在二维矢量空间数据指定图层中提取处于同一图斑内的各对象间的拓扑关系所对应度量值的统计值集合，将所得统计值集合作为水印载体；所述对水印载体嵌入水印信息的过程将水印载体通过HASH函数进行子集划分；分别在每个子集内嵌入水印信息的一个水印位；所述从水印载体检测水印信息的过程为，对水印载体通过HASH函数进行子集划分；判断每个子集中的数据呈现两种预定分布模式中的哪一种，从而辨别该子集内嵌入的水印位为0或1；综合所有子集检测出的水印串，确定水印载体中嵌入的水印信息。

说明书

技术领域

本发明属于版权保护技术领域，特别是涉及一种基于空间拓扑的二维矢量 空间数据数字水印方法。

背景技术

今天的世界是一个数字化的信息世界，几乎我们接触的所有信息都是采用 数字化载体。当数字化在数据的编辑、复制、分发等方面给我们带来很大方便 时，同时也带来了版权保护的难题。计算机通信和网络技术的快速发展使得数 据的非法复制和分发通过网络变得比以前任何时候都要便捷，也因此使得版权 保护问题的解决变得更加紧迫。

数字水印技术通过把版权信息隐藏于数据中为上述问题的解决提供了一种 可行的方案。虽然目前有关多媒体数字水印技术的研究已非常广泛和深入，但 有关地理信息系统中矢量空间数据数字水印的研究相对要少了很多。现在空间 数据的获取仍然是一个高成本的过程，数据生产者还无法承担免费提供数据。 作为一种保护数据版权的方式，二维矢量空间数据数字水印技术起着非常重要 的作用。

在现有的大部分水印算法中，矢量空间数据基本上被看作点云(坐标点的 集合)，而非地理对象的集合。水印信息直接隐藏在坐标点(或坐标点的频率系 数)中。这类方法因为从点云的角度来考虑水印信息的嵌入，在水印嵌入的过 程中没有地理对象的概念，因而忽略了地理对象的形状和空间关系，从而可能 导致地理对象的形状变形过大，或对象的空间关系产生冲突，比如，原本相离 的两地理对象可能会变成相交。另外，把水印信息直接隐藏在坐标点中更容易 受到坐标点攻击，比如插值、坐标点删除、地图综合或化简、重新数字化以及 因对数据的常规操作而带来的噪声等。

发明内容

本发明目的在于针对现有技术的不足，提出一种基于空间拓扑的二维矢量 空间数据数字水印方法。

本发明的技术方案为：包括有水印载体提取过程、对水印载体嵌入水印信 息的过程和从水印载体检测水印信息的过程；

所述水印载体提取过程为，在二维矢量空间数据指定图层中提取处于同一 图斑内的各对象间的拓扑关系所对应度量值的统计值集合，将所得统计值集合 作为水印载体；

所述对水印载体嵌入水印信息的过程包括以下步骤：

步骤1.1，将水印载体进行子集划分，划分所得子集个数m＝水印信息所含水印 位的长度Length(watermark)×重复嵌入次数N；

步骤1.2，分别在每个子集内嵌入水印信息的一个水印位，从而在水印载体内重 复嵌入水印信息N次；所述嵌入水印位的实现方式为，在数据的容错范围内调 整对象与其所在图斑的其他对象的拓扑关系，使得调整后子集内数据的分布呈 现两种预定分布模式中的一种，两种预定分布模式分别代表嵌入的水印位为0 或1；

所述从水印载体检测水印信息的过程包括以下步骤：

步骤2.1，对水印载体进行子集划分；

步骤2.2，判断每个子集中的数据呈现两种预定分布模式中的哪一种，从而辨别 该子集内嵌入的水印位为0或1；

步骤2.3，综合所有子集检测出的水印串，构成N个长度为Length(watermark) 的水印串，采用少数服从多数的投票机制比较这些水印串的相应位，决定水印 信息所含每个水印位应当是0或1，从而确定水印载体中嵌入的水印信息。

而且，所述指定图层为点层、线层或面层。

而且，所述水印载体提取过程中，所述拓扑关系采用相离关系(也可以采 用其它的拓扑关系)，具体实现方式包括以下步骤，

步骤3.1，将指定图层分块，分成n个图斑P₁，P₂，...，P_n；

步骤3.2，对指定图层中的任一图斑P_i，i∈[1，n]，假设P_i中含有k个对象fⁱ₁， fⁱ₂，...，fⁱ_k；对图斑P_i中的每个对象fⁱ_j∈P_i，j∈[1，k]，依次以图斑P_i中其他与 对象fⁱ_j相离的对象为参考对象，根据式1-1分别计算得到fⁱ_j与参考对象的相离 关系的度量值${\left(M_{\mathrm{fj}}^i\right)}^1,{\left(M_{\mathrm{fj}}^i\right)}^2,...,{\left(M_{\mathrm{fj}}^i\right)}^{j-1},{\left(M_{\mathrm{fj}}^i\right)}^{j+1},...,{\left(M_{\mathrm{fj}}^i\right)}^k;$对度量值 ${\left(M_{\mathrm{fj}}^i\right)}^1,{\left(M_{\mathrm{fj}}^i\right)}^2,...,{\left(M_{\mathrm{fj}}^i\right)}^{j-1},{\left(M_{\mathrm{fj}}^i\right)}^{j+1},...,{\left(M_{\mathrm{fj}}^i\right)}^k$构成的数据集采用箱线图去除离群点后， 再计算中位值median及均值mean；

${M_B}^A=\mathrm{area}\left(B\right)/\mathrm{area}(B\oplus \mathrm{dist}(\mathrm{aB},\mathrm{aA}))---(1-1)$

式中，area(B)是多边形B的面积，是形态膨胀运算算子，dist(aB，aA)为 多边形B的边界与多边形A的边界最近的两点之间的距离，由根据式1-2求取 如下：

dist(aB，aA)＝min(Dist(p，q)|p∈aB，q∈aA)        (1-2)

式中，p为多边形B的边界中的点，q多边形A的边界中的点；

步骤3.3，对于每个对象fⁱ_j，根据式1—3定义一个变量Cⁱ_j如下：

Cⁱ_j＝(mean-median)/(Q3-Q1)                         (1-3)

式中，Q₃和Q₁分别是度量值${\left(M_{\mathrm{fj}}^i\right)}^1,{\left(M_{\mathrm{fj}}^i\right)}^2,...,{\left(M_{\mathrm{fj}}^i\right)}^{j-1},{\left(M_{\mathrm{fj}}^i\right)}^{j+1},...,{\left(M_{\mathrm{fj}}^i\right)}^k$所构成数据集的上四分位数和下四分位数；变量Cⁱ_j反映了对象fⁱ_j与图斑P_i中其 他与对象fⁱ_j相离的对象在度量关系上的整体均衡情况；同一图斑P_i内的各对象 间的拓扑关系所对应度量值的统计值集合即为C_i＝{Cⁱ₁，...，Cⁱ_j，Cⁱ_j+1，...，Cⁱ_k}；

在对给定图层Layer中所有图斑P₁，P₂，...，P_n内的对象进行处理后，最终可 以得到数据C¹₁，C¹₂，...，C¹_k，...，Cⁱ_j，Cⁱ_j+1，...，Cⁱ_k，...，Cⁿ_k，这些数据 构成的数据集C即是水印嵌入的载体，C＝{C₁，C₂，...，C_n}。

而且，步骤3.1通过Hilbert排列码实现对二维矢量空间数据指定图层地图 数据分块。

而且，步骤1.1的具体实施方式为，设置m个空的子集D¹，D²，...，D^m， 其中1，2，...，m为组号；将每个Cⁱ_j∈C按组分配到子集D¹，D²，...，D^m中， 其所属组的组号通过一个加密的HASH函数来计算，计算方式如下：

对于一个HASH函数H₁()，输入一定长度的消息M，输出一个固定长度 的HASH值，即输出h＝H₁(M)，其中M是通过密钥k₁连接Cⁱ_j前面2位最高 有效位来生成；Cⁱ_j所属组的组号Group(Cⁱ_j)＝(h MOD m)+1，Group(Cⁱ_j)为Cⁱ_j所 属组的组号，其中MOD表示取模；

步骤1.2的具体实施方式包括以下步骤：

1)对于任一子集D^x，x∈[1，m]，设定一个数据轴，在数据轴上找到一个 基准点O^x，然后分别向左向右以步长d对数据轴进行分段，对每段进行编号， 把子集D^x中各数据落到数据轴上，；所述基准点O^x通过密钥k₂和HASH函数 H₂()确定，O^x＝H₂H(k₂o(x*0.1)o k₂)；所述步长d根据二维矢量空间数据 的地图精度确定；

2)如果要在子集D^x中嵌入水印位1，通过调整相应多边形的坐标，把落 在偶数编号的数据段上的数据调整到离其最近的奇数编号的数据段上去，从而 使子集D^x中的数据呈现代表所嵌入水印位为1的预定分布模式；

如果要在子集D^x中嵌入水印位0，通过调整相应多边形的坐标，把落在奇 数编号的数据段上的数据调整到离其最近的偶数编号的数据段上去，从而使子 集D^x中的数据呈现代表所嵌入水印位为0的预定分布模式。

而且，步骤2.1的具体实施方式为，用嵌入水印时的密钥k₁把水印载体分 散到空的子集D¹，D²，...，D^m中；

步骤2.2的具体实施方式为：

对每个子集D^x，x∈[1，m]，用密钥k₂计算出数据轴的基准点O^x；以基准点 O^x为起点，向左向右用步长d对数据轴分段；把子集D^x中的数据落到数据轴上， 并计算各数据所在数据段的编号，最后分别统计子集D^x中落在编号为偶数和编 号为奇数的数据段上的数据个数n_o和n_e，如果n_o-n_e>0，则认为子集D^x中嵌入 了水印位1；如果n_o-n_e<0，则认为子集D^x中嵌入了水印位0；如果n_o-n_e＝0， 则认为子集D^x中水印检测失败。

本发明具有以下主要有益效果：

其一.根据二维矢量空间数据的空间拓扑关系，能将该水印信息嵌入到空间 拓扑关系的统计特征中。同时，在不需要原始数据的情况下，利用本发明提供 的水印嵌入和水印检测方法解决了如何将水印信息有效地提取出来的难题。

其二.数字水印不影响原始数据的有用性，它是隐藏在原始数据中的特殊信 息，用于数据版权保护。对于含有水印的二维矢量空间数据，可用一个只对所 有者公开的水印密钥(包括密钥k1，密钥k2，数据分块参数λ和二维矢量空 间数据所提供地图的左上角坐标)检测出一个特殊的信息即水印，从而达到申 明版权的目的。

其三.水印信息嵌入在二维矢量空间数据的空间拓扑关系中，并在嵌入水印 时采用重复嵌入和检测时采用选举的方法，能够有效地抵抗缩放，平移，旋转 和插值等攻击。

附图说明

图1为本发明原理示意图；

图2为本发明实施例的嵌入水印信息示意图。

具体实施方式

本发明用于为二维矢量空间数据嵌入水印来提供版权保护。二维矢量空间 数据是地理空间的数字表达，数据本身承载着丰富的地理意义和地理规律。在 地理世界中，最有规律可循的是地理事物的空间分布。这种空间分布上的特征 可以通过地理目标的空间关系在统计上的特征体现出来。水印信息可隐藏在数 据空间关系的统计特征中。本发明是一种用数字水印技术保护二维矢量空间数 据版权的方法，它包括有水印载体提取过程、对水印载体嵌入水印信息的过程 和从水印载体提取水印信息的过程。参见附图1，本发明所提供的方案实际上 包括了两种应用流程：一种为嵌入水印流程，对嵌入水印前的2D矢量地图， 首先进行水印载体提取，然后对水印载体嵌入水印信息(实施例为执行步骤 3.1～3.3后执行步骤1.1、1.2)；一种为检测水印流程，对嵌入水印后的2D矢量 地图，首先进行水印载体提取，然后从水印载体提取水印信息的过程(实施例为 执行步骤3.1～3.3后执行步骤2.1～2.3)。具体实施时，二维矢量空间数据的产品 发行方可以采用嵌入水印流程，作为嵌入方在产品中加入水印后发售；在需要 验证版权时，产品发行方或公证机构可以作为检测方，采用检测水印流程，提 取出产品中所含水印信息。这两种流程的基础都是水印载体的提取，本发明选 择二维矢量空间数据的空间拓扑关系构成载体对象，并且通过引入度量值，把 拓扑关系与度量值结合起来描述空间关系。因此水印载体的提取由数据分块、 计算度量值、度量值分组这三步组成。二维矢量空间数据是由点、线、面三种 类型的图层数据构成，具体实施时可以分别对点层、线层和面层引入不同的度 量值来辅助描述拓扑关系，并分别对点层、线层、和面层添加水印。

本发明实施例选择通过相离关系构建水印载体，具体实施方式也可以选择 其它种类的拓扑关系。本发明实施例的提取水印载体具体步骤为：

步骤3.1，通过Hilbert排列码将指定图层分成n个图斑P₁，P₂，...，P_n；

指定图层Layer＝{P₁，P₂，...，P_n}。P₁表示指定图层Layer中的第1个图斑，P_n表示指定图层Layer中的第n个图斑。

具体实施时，先将整个指定图层Layer划分成2^λ×2^λ的网格，然后就是每个 网格的Hilbert编码，再根据Hilbert编码从小到大的顺序，判断各个网格内所包 含的对象。Hilbert编码连续的对象分到同一个图斑，Hilbert编码不连续的对象 分到不同的图斑。数据分块参数λ和图层左上角坐标可作为水印密钥内容之一 保存，由嵌入方和检测方共享。嵌入水印流程中，按照数据分块参数λ对嵌入 水印前的2D矢量地图的指定图层分块；检测水印流程中，按照数据分块参数λ 对嵌入水印后的2D矢量地图的指定图层分块。Hilbert编码是现有保持空间聚集 性最好的排列码技术，因此是本发明推荐的优选实施方式。

步骤3.2，对指定图层中的任一图斑P_i，i∈[1，n]，假设P_i中含有k个对象fⁱ₁， fⁱ₂，...，fⁱ_k；对图斑P_i中的每个对象fⁱ_j∈P_i，j∈[1，k]，依次以图斑P_i中其他与 对象fⁱ_j相离的对象为参考对象，根据式1-1分别计算得到fⁱ_j与参考对象的相离 关系的度量值${\left(M_{\mathrm{fj}}^i\right)}^1,{\left(M_{\mathrm{fj}}^i\right)}^2,...,{\left(M_{\mathrm{fj}}^i\right)}^{j-1},{\left(M_{\mathrm{fj}}^i\right)}^{j+1},...,{\left(M_{\mathrm{fj}}^i\right)}^k;$对度量值 ${\left(M_{\mathrm{fj}}^i\right)}^1,{\left(M_{\mathrm{fj}}^i\right)}^2,...,{\left(M_{\mathrm{fj}}^i\right)}^{j-1},{\left(M_{\mathrm{fj}}^i\right)}^{j+1},...,{\left(M_{\mathrm{fj}}^i\right)}^k$构成的数据集采用箱线图去 除离群点后，再计算中位值median及均值mean；

${M_B}^A=\mathrm{area}\left(B\right)/\mathrm{area}(B\oplus \mathrm{dist}(\mathrm{aB},\mathrm{aA}))---(1-1)$

式中，area(B)是多边形B的面积，是形态膨胀运算算子，dist(aB，aA)为 多边形B的边界与多边形A的边界最近的两点之间的距离，由根据式1-2求取 如下，

dist(aB，aA)＝min(Dist(p，q)|p∈aB，q∈aA)      (1-2)

式中，p为多边形B的边界中的点，q多边形A的边界中的点；

步骤2.3，对于每个对象fⁱ_j，根据式1—3定义一个变量Cⁱ_j如下：

Cⁱ_j＝(mean-median)/(Q3-Q1)                      (1-3)

式中，Q₃和Q₁分别是度量值${\left(M_{\mathrm{fj}}^i\right)}^1,{\left(M_{\mathrm{fj}}^i\right)}^2,...,{\left(M_{\mathrm{fj}}^i\right)}^{j-1},{\left(M_{\mathrm{fj}}^i\right)}^{j+1},...,{\left(M_{\mathrm{fj}}^i\right)}^k$所构成数据集的上四分位数和下四分位数；变量Cⁱ_j反映了对象fⁱ_j与图斑P_i中其 他与对象fⁱ_j相离的对象在度量关系上的整体均衡情况；同一图斑P_i内的各对象 间的拓扑关系所对应度量值的统计值集合即为C_i＝{Cⁱ₁，...，Cⁱ_j，Cⁱ_j+1，...，Cⁱ_k}； 其中采用箱线图去除离群点为现有技术，本发明不予赘述。

在对给定图层Layer中所有图斑P₁，P₂，...，P_n内的对象进行处理后，最终可 以得到数据C¹₁，C¹₂，...，C¹_k，...，Cⁱ_j，Cⁱ_j+1，...，Cⁱ_k，...，Cⁿ_k，这些数据 构成的数据集C即是水印嵌入的载体，C＝{C₁，C₂，...，C_n}。

本发明针对二维矢量空间数据的特点，研究将水印信息均匀地分布到数据 中的嵌入水印方案，保证该嵌入水印对数据的修改恰好在数据的使用范围内。 同时，研究在不需要原始数据的情况下，如何将水印信息有效地提取出来。本 发明所提供对水印载体嵌入水印信息的过程包括，步骤1.1，将水印载体进行子 集划分，因为水印信息一般采用1或0构成的数值串，因此划分所得子集个数m ＝水印信息所含水印位的长度Length(watermark)×重复嵌入次数N；步骤1.2， 分别在每个子集内嵌入水印信息的一个水印位，从而在水印载体内重复嵌入水 印信息N次；所述嵌入水印位的实现方式为，在数据的容错范围内调整对象与 其所在图斑的其他对象的拓扑关系，使得调整后子集内数据的分布呈现两种预 定分布模式中的一种，两种预定分布模式分别代表嵌入的水印位为0或1。本发 明所提供从水印载体检测水印信息的过程包括，步骤2.1，对水印载体进行子集 划分；步骤2.2，判断每个子集中的数据呈现两种预定分布模式中的哪一种，从 而辨别该子集内嵌入的数值为0或1；步骤2.3，综合所有子集检测出的水印串， 构成N个长度为Length(watermark)的水印串，采用少数服从多数的投票机制比 较这些水印串的相应位，决定水印信息所含每个水印位应当是0或1，从而确定 水印载体中嵌入的水印信息。

本发明实施例中，对水印载体嵌入水印信息的过程具体实现方式如下：

步骤1.1中，设置m个空的子集D¹，D²，...，D^m，其中1，2，...，m为组号； 将每个Cⁱ_j∈C按组分配到子集D¹，D²，...，D^m中，其所属组的组号通过一个加 密的HASH函数来计算，计算方式如下：

对于一个HASH函数H₁()，输入一定长度的消息M，输出一个固定长度 的HASH值，即输出h＝H₁(M)，其中M是通过密钥k₁连接Cⁱ_j前面2位最高 有效位来生成；Cⁱ_j所属组的组号Group(Cⁱ_j)＝(h MOD m)+1，Group(Cⁱ_j)为Cⁱ_j所 属组的组号，其中MOD表示取模；

其中MOD含义为取模，MSB(the Most Significant Bits)表示最高有效位， 取小数点后前2位最高有效位。

划分所得子集个数m＝水印信息所含水印位的长度Length(watermark)×重复 嵌入次数N，因此能够在水印载体{C¹₁，C¹₂，...，C¹_k，...，Cⁱ_j，Cⁱ_j+1，...， Cⁱ_k，...，Cⁿ_k}中将水印信息充分嵌入N次。

步骤1.2的具体实施方式包括以下步骤，

1)对于任一子集D^x，x∈[1，m]，设定一个数据轴，在数据轴上找到一个 基准点O^x，然后分别向左向右以步长d对数据轴进行分段，对每段进行编号， 把子集D^x中各数据落到数据轴上；所述基准点O^x通过密钥k₂和HASH函数 H₂()确定，O^x＝H₂(k₂o(x*0.1)o k₂)，H₁()可以等于H₂()，也可以不同； 所述步长d根据二维矢量空间数据的地图精度确定；

步长d的取值受到地图精度的限制。假设地图精度为τ。因为水印信息调 制在相离的拓扑关系上，度量值可以按下式计算。

M_B^A＝area(B)/Buffer(B，Dist_BA)                 (1-1)

Dist_BA是缓冲距离，也是B和A的最近距离。令R1＝area(B)/Buffer(B， (Dist_BA)+τ)，R2＝area(B)/Buffer(B，(Dist_BA)-τ)，则M_B^A的可调范围为[R1，R2]， 其可调幅度R’＝R2-M_B^A≈M_B^A-R¹。设Dⁱ中各数据的可调幅度的众数是R，则d 可取1.5*R，即d＝1.5*R。其中Buffer函数为把B按膨胀因子Dist_BA进行膨胀。

2)如果要在子集D^x中嵌入水印位1，通过调整相应多边形的坐标，把落在 偶数编号的数据段上的数据调整到离其最近的奇数编号的数据段上去，从而使 子集D^x中的数据呈现代表所嵌入水印位为1的预定分布模式；例如图2中，比 较嵌入水印信息位前和嵌入水印信息位1后，左边第1号数据段上的数据调整 到了右边第2号数据段；左边第3号数据段上的数据调整到了左边第2号数据 段。

在调整数据时，为了能够不超出数据的容错范围，本发明总结了约束条件 以方便实施。调整相应多边形的坐标时，满足以下约束条件即可，

(1)坐标调整幅度在数据精度允许范围内；

(2)不会改变对象间拓扑关系的类型，比如原本相离的对象，在调制水印后， 不能变成相交或其他类型的拓扑关系；

(3)多边形的形状变形不能太突兀，变形不能过大；

(4)不改变度量值之间的大小关系，即如果嵌入水印前，某两个度量值存在${\left(m_{\mathrm{fj}}^i\right)}^a>{\left(m_{\mathrm{fj}}^i\right)}^b$这种不等关系，那么嵌入水印后此不等式仍然成立；

(5)不能改变C^a1_b1和C^a2_b2的大小关系。

后两个条件保证了水印的嵌入不会改变地理对象的相对空间关系。

本发明实施例中，从水印载体检测水印信息的过程具体实现方式如下：

步骤2.1的具体实施方式为，用嵌入水印时的密钥k₁把水印载体分散到空的子 集D¹，D²，...，D^m中。此步骤和步骤1.1相应，采用同样的密钥k₁和HASH 函数H₁()求取组号，即可将每个Cⁱ_j∈C按组分配到子集D¹，D²，...，D^m中。

步骤2.2的具体实施方式为：

对每个子集D^x，x∈[1，m]，用密钥k₂计算出数据轴的基准点O^x；以基准点 O^x为起点，向左向右用步长d对数据轴分段；把子集D^x中的数据落到数据轴上， 并计算各数据所在数据段的编号，最后分别统计子集D^x中落在编号为偶数和编 号为奇数的数据段上的数据个数n_o和n_e，如果n_o-n_e>0，则认为子集D^x中嵌入 了水印位1；如果n_o-n_e<0，则认为子集D^x中嵌入了水印位0；如果n_o-n_e＝0， 则认为子集D^x中水印检测失败。此步骤和步骤1.2相应，采用同样的密钥k₂和 HASH函数H₂()确定基准点O^x。采用这种水印密钥制度，可以更好地保护水 印不被破解。

步骤2.3中，本发明实施例采用少数服从多数的投票机制来决定最终的水印串， 投票矩阵如下表所示。

 

水印位b₁b₂…_b|w|D¹～D^|w|D^|w|+1～D^2*|w|. . . D^(N-1)*|w|+1～D^m嵌入水印位0的 票数         嵌入水印位1的 票数         

其中|w|＝Length(watermark)(其中N表示重复嵌入次数)

经过投票判断，可以确认水印位b₁、b₂...b_|w|所对应的数值是0或是1，从 而推导出嵌入的水印信息。

本发明提供的这种二维矢量空间数据的水印嵌入及检测机制，可以采用 ArcGIS实现。嵌入方和检测方可以事先搭建二维矢量空间数据水印开发平台。 ArcGIS是一个地理信息系统(GIS)的开发平台，ArcGIS Engine是用于GIS 桌面应用程序的二次开发组件库。本领域技术人员可以利用ArcGIS的使用以 及ArcGIS Engine中的地图显示和地图操作等开发组件，根据本发明技术方案 提供水印嵌入及检测流程。