随着矢量地图数据的广泛应用，其安全问题日益突出，地图数据被非法窃取、篡改的风险不断增加，引起了人们的普遍关注^[1-4]。确保数据真实、可靠是开展各项应用的必要前提，对地图数据进行准确的完整性认证已成为迫切需求。脆弱水印是解决这一问题的有力技术手段，它能够有效认证出数据是否被篡改、哪里被篡改、篡改的程度有多大，从而保证数据可靠、可信、可用。

用于版权保护的鲁棒水印^[5-7]和面向完整性认证的脆弱水印是矢量地图数据数字水印技术的两个主要分支。近年来，随着地图数据完整性认证需求的增加，脆弱水印的研究开始得到关注，如文献[8]基于仿生学蜘蛛网原理，通过对比矢量地图与蜘蛛网的交叉状态和相交点数实现完整性认证；文献[9]通过建立不同要素间的关联关系，有效解决了要素整体删除后无法认证的问题；文献[10]利用相离地物拓扑关系的距离值生成认证水印，但只适用于面状数据。与栅格数据不同，矢量地图数据空间分布不均的离散性特征增大了篡改定位的难度。为实现准确的篡改定位，一般采用分块^[11-12]或分组的方法进行数据划分。其中，基于分组的脆弱水印既能满足标识篡改区域的定位要求，又能较好保持地图的整体特征，如文献[13]将线状实体根据坐标点数进行分组，使每个分组中的坐标点数均大于设定的阈值；文献[14]根据记录号将图元分组，通过插入顶点标记初始记录号；文献[15]将每3个坐标点分为一组，通过扩展曼哈顿距离的差值^[16]将水印嵌入；文献[17-18]根据每个地物的消息验证码将其分组，认证时通过不同的验证向量组合判定篡改位置和类型；文献[19]按照设定的数量阈值进行分组，将坐标求和后的均值经映射后生成脆弱水印；文献[20]根据能够容纳水印的最少实体数量进行分组，采用可逆的方法嵌入水印。基于实体分组的矢量地图脆弱水印通常存在以下不足：（1）分组缺乏稳定性。有些分组方案以每组中实体数量或坐标点个数作为分组依据，易受实体增删的影响，分组不同步必然导致整幅地图认证失败。（2）部分算法存在篡改漏检。将实体组的特征参数作为混沌映射的初值产生认证水印，生成水印的长度可根据实际需求自由调节，但若特征参数构造不当，会存在篡改漏检的隐患。（3）不能准确认证实体乱序、坐标点逆序操作。矢量地图数据所表达的内容与不同实体存储的先后、同一实体内坐标点的正序逆序无关^[21-24]，应使其通过认证。

针对以上问题，本文提出了一种定位篡改实体组的矢量地图脆弱水印算法，能够实现对地图数据的稳定分组，有效避免因特征参数构造不当引发的篡改漏检问题，并能对遭到篡改的实体组准确定位。

1 采用聚类思想的实体分组 1.1 实体表征方法

将矢量地图进行数据划分是实施完整性认证的重要步骤，通过数据划分，矢量地图被分解成若干互不重叠的数据单元。采用实体分组的数据划分方法能够避免同一个地理实体被人为地分割到不同的数据单元中，有效保持了地图的整体特征。实体分组必须具有稳定性，即除被篡改的实体外，其余实体的分组在水印嵌入和检测中要保持一致，这是完成准确篡改定位的前提。因此，应避免直接使用实体或坐标点个数作为分组依据，否则一旦遭到实体增删攻击，整幅地图中分组的同步性将被破坏。

为有效解决这一难题，本文采用基于聚类的实体分组方法，首先将各个地理实体用其最小外接矩形的中点表征，然后采用优化的k均值聚类方法将最小外接矩形的中点划分到各自类别中。最小外接矩形能够标识出地理实体的大致位置，是描述实体水平和竖直跨度的直观方法。以图 1(a)中的矢量地图为例，其地理实体的最小外接矩形中点分布如图 1(b)所示。由此可见，最小外接矩形中点分布与地理实体空间分布具有很大的相似性。

1.2 优化的k均值聚类

k均值聚类在数据挖掘、计算机视觉等领域有着广泛应用，其基本原理是在数据集$X = \left\{ {{x_1},{x_2} \cdots {x_n}} \right\}$中随机选取k个对象作为初始聚类中心，并将其余各对象分配到与之距离最近的初始聚类中心所在的类别中，把每个类中数据对象的均值作为新的聚类中心，依此循环，直至满足收敛条件。然而，由于初始聚类中心是随机选取的，未能充分考虑数据的实际分布情况，很可能会延长迭代时间甚至陷入局部最优解。因此，本文采用优化的k均值聚类，具体步骤如下：

1）计算数据集X的邻域半径ε。任意两个p维数据对象x_i、x_j间的欧氏距离为：

$D\left( {{x_i},{x_j}} \right) = \sqrt {{{({x_{i1}} - {x_{j1}})}^2} + {{({x_{i2}} - {x_{j2}})}^2} + \cdots + {{({x_{ip}} - {x_{jp}})}^2}} $

(1)

邻域半径ε定义为数据集X中两两数据对象欧氏距离加和的均值，计算方法为：

$\varepsilon = \frac{1}{{n\left( {n - 1} \right)}}\mathop {\sum\limits_{i = 1} }\limits^n \mathop {\sum\limits_{j = 1} }\limits^n D\left( {{x_i},{x_j}} \right)$

(2)

2）统计集合X中每个元素在邻域半径ε范围内包含数据对象的数量n，若大于阈值γ，则该点为高密集度点，将其加入集合G中。

3）在集合G中筛选出密集度最大的数据对象k₁，计算出G中距离k₁最远的对象k₂。

4）分别计算集合G中其余数据对象与k₁、k₂的距离之和d_i1 +d_i2，筛选出max (d_i1 +d_i2)，即与k₁、k₂距离之和最大的数据对象，将其记作k₃。

5）以此类推，继续计算出集合G中与k₁，k₂⋯k_{i- 1}距离之和最大的数据对象k_i，直到获取k个数据对象。

6）将这G个数据对象作为初始聚类中心，进行k均值聚类。

由于初始聚类中心分布在数据密集区域，更接近实际聚类中心，因此聚类收敛速度更快，需要迭代的次数更少。为提高篡改定位的精度，需要划分的类别数目众多，采用优化的k均值聚类可有效提高水印算法的总体效率。

2 结合混沌序列的脆弱水印构造模型

Logistic映射作为典型的混沌系统，广泛应用于水印序列的置乱加密，本文利用其对初值十分敏感的特性产生不收敛且非周期的伪随机序列并进行二值化处理，为每个实体组产生脆弱水印信息。具体实施时，首先需构造能够表征该实体组完整性的特征参数，然后将其作为混沌映射的初值，生成水印序列。完整性特征参数必须具有脆弱性和唯一性，脆弱性是指一旦实体组的内容发生改变，完整性特征参数也要随之发生改变；唯一性是指同一实体组对应唯一的完整性特征参数，不同的实体组对应不同的完整性特征参数。因此，构造完整性特征参数对于整个水印算法的安全至关重要，若构造不当，容易存在漏检或虚警隐患。

2.1 篡改漏检问题分析

设地图坐标的精度位为小数点后第p位，水印嵌入位为小数点后第q位，则p < q < e，e为能够保证水印正确提取的最大位。本文将坐标嵌入位后数值的改变不再视为篡改。为对其安全性进行分析，构造如下完整性特征参数：

${a_i} = \frac{{\mathop {\sum\limits_{j = 1} }\limits^{{n_i}} \left( {{x_{ij}} + {y_{ij}}} \right)}}{{2{n_i}}}$

(3)

式中，a_i为第i个实体组的完整性特征参数；n_i为第i个实体组中坐标点数；x_ij、y_ij为第i个实体组中的第j个坐标点的横、纵坐标在水印嵌入位前的数值。值得注意的是，为避免水印嵌入带来的误差对混沌初值的影响，只让水印嵌入位之前的坐标数值参与运算。

1）漏检情况1。对第i个实体组中的横、纵坐标在水印嵌入位前的数值作以下篡改：

$\left\{ {\begin{array}{*{20}{l}} {{x_{ij}}' = {x_{ij}} + {\rm{\Delta }}{x_{ij}}}\\ {{y_{ij}}' = {y_{ij}} + {\rm{\Delta }}{y_{ij}}} \end{array}} \right.\left( {j = 1,2 \cdots {n_i}} \right)$

(4)

式中，Δx_ij、Δy_ij为篡改变化量。将x_ij'、y_ij'代入式（3）可得：

${a_i} = \frac{{\mathop {\sum\limits_{j = 1} }\limits^{{n_i}} \left( {{x_{ij}} + {y_{ij}}} \right) + \mathop {\sum\limits_{j = 1} }\limits^{{n_i}} \left( {{\rm{\Delta }}{x_{ij}} + {\rm{\Delta }}{y_{ij}}} \right)}}{{2{n_i}}}$

(5)

则只需满足：

$\left( {{\rm{\Delta }}{x_{i1}} + {\rm{\Delta }}{x_{i2}} + \cdots + {\rm{\Delta }}{x_{i{n_i}}}} \right) + \left( {{\rm{\Delta }}{y_{i1}} + {\rm{\Delta }}{y_{i2}} + \cdots + {\rm{\Delta }}{y_{i{n_i}}}} \right) = 0$

(6)

即可保证在发生篡改的情况下，a_i仍旧保持不变。这意味着在满足式(6)的条件下，遭到篡改后的数据仍会产生与原始数据相同的脆弱水印信息，在水印嵌入位上的值保持不变的情况下，可使篡改后的数据通过认证，导致漏检问题。

2）漏检情况2。原始数据中坐标点的顺序为P₁、P₂、P₃、P₄、P₅、P₆（图 2(a)），篡改后数据中坐标点的顺序为P₁、P₂、P₃、P₄、P₅、P₆（图 2(b)）。在篡改后的数据中，虽然坐标点的位置均未发生改变，但其在线状实体中的先后顺序已经改变，导致这6个坐标点所表示的线状实体与原始数据已经完全不同。将篡改前后的6个坐标点分别代入式(5)，可得到相同的a_i，从而产生相同的脆弱水印。若P₃、P₄两个坐标点上嵌入的水印比特相同，则改变P₃、P₄在实体中的先后顺序不会对水印检测产生影响，导致遭到篡改后的数据同样能够通过认证，引发漏检问题。

2.2 脆弱水印生成方案及分析

为有效解决以上问题，本文通过构建安全的完整性特征参数来消除漏检隐患。对于第i个分组中的第t个实体，其完整性特征参数b_it为：

${b_{it}} = {\rm{ }}\frac{{\prod\limits_{j = 1}^{{n_t} - 1} {\left( {{x_{t,j}} + {x_{t,j + 1}}} \right)} \lambda }}{{\prod\limits_{j = 1}^{{n_t} - 1} {\left( {{y_{t,j}} + {y_{t,j + 1}} + K} \right)} }}$

(7)

式中，n_t为该分组中第t个实体上坐标点的个数；x_{t, j}、y_tj, 为该分组中第t个实体上第j个点的横、纵坐标在水印嵌入位前的数值；λ为数值调节因子；K为由安全密钥产生的伪随机数，用于避免可能发生的约分，增强特征参数的安全性。

设第i个实体组中共含有m_i个实体，则第i个实体组的完整性特征参数b_i为：

${b_i} = \prod\limits_{t = 1} ^{{m_i}} {b_{it}}$

(8)

取b_i的小数部分，使其处于(0，1)区间，即：

${b_i}' = {\rm{mod}}\left( {{b_i},1} \right)$

(9)

将b_i'作为Logistic映射的初值，并将生成的序列进行二值化处理，生成每个实体组的脆弱水印。

本文设计的脆弱水印构造模型具有很强的安全性。首先，由于将同一实体上相邻的坐标点相互关联，结合安全密钥并采用连乘运算求取实体的特征参数，有效避免了篡改漏检的可能。其次，生成的认证信息不受实体乱序、坐标点逆序的影响。由乘法交换律可知，同一实体上的坐标点逆序操作不会改变b_it的结果。而对于不同实体的乱序操作，由于乱序并不会改变实体本身的空间分布，聚类分组可保证其分组的准确性；同样，因式的先后顺序不会改变乘积b_i的结果，因此实体乱序后各分组仍会产生与乱序前相同的认证信息。

3 水印算法设计 3.1 水印嵌入

脆弱水印嵌入的具体步骤如下：

1）求取地图数据中每个实体最小外接矩形的中点。

2）采用优化的k均值聚类方法对所有实体最小外接矩形的中点进行聚类，并将聚类中心C作为密钥保存。采用聚类分组方法有效避免了实体增删导致的分组不同步问题。聚类的类别数为k，每个类别即为一个实体组，k与篡改定位的精度密切相关，其取值根据认证精度的实际要求自适应设定。k的取值越大，分组的数量越多，篡改定位精度越高；k的取值越小，分组的数量越少，篡改定位精度越低。

3）按照§2.2所述方法为每个实体组生成脆弱水印W_i。

4）在每个实体组中，提取各个坐标点在水印嵌入位q前的坐标数值，并按照横坐标从小到大的顺序排列，若其值相同，再按照纵坐标从小到大的顺序依次排列。排序操作确保了实体乱序、坐标点逆序后水印信息的同步性。

5）将每个实体组的脆弱水印W_i采用修改最低有效位的方式，依次嵌入到该组排序后各坐标点水印嵌入位上，得到含水印的数据。

6）重复步骤4）和步骤5），直至所有实体组的脆弱水印嵌入完毕。

3.2 水印检测与篡改定位

脆弱水印检测与篡改定位的步骤如下：

1）求取待测地图数据中每个实体最小外接矩形的中点。

2）为确保聚类分组与水印嵌入时相同，将密钥C作为初始聚类中心进行k均值聚类，聚类的每个类别即为一个实体组。

3）按照§2.2所述方法为每个实体组生成脆弱水印，记为RW_i。

4）在每个实体组中，提取排序后各坐标点水印嵌入位的最低有效位，并将其依次连接成二值序列RW_i。

5）若RW_i= RW_i，则该实体组未遭篡改，其通过完整性认证；若RW_i≠ RW_i，则该实体组遭到了篡改，其未通过完整性认证，并对该实体组进行篡改标识，从而达到篡改定位的目的。

6）遍历所有实体组，使其均完成水印检测和篡改定位。

4 实验与分析

为验证算法性能，在Windows 7操作系统上采用VS2010开发平台进行仿真实验。硬件环境为Intel(R) Core(TM) i5-2400 CPU (3.10 GHz)，4 GB RAM，NVIDIA GeForce 605显卡。实验数据采用某地1:50万的水系线状数据，如图 3所示。实验数据共含有822个线状实体，25 005个坐标点，地理坐标精度位为小数点后第4位，地理坐标最大误差容限为1 × 10^-4，数据精度为50 m。

4.1 不可见性

按照本文设计的算法将脆弱水印嵌入实验数据，将水印嵌入前后的矢量地图进行局部放大对比，如图 4所示。实验结果表明，视觉上无法分辨出水印嵌入前后地图数据的差异，水印算法具有良好的不可感知性。由于水印嵌入在数据精度位后，即q > p，因此不会对地图精度产生影响。在1:50万的矢量地图数据中，q的最小取值为5，则嵌入水印后对横、纵坐标的最大改变量为1 × 10^-5，坐标点的最大偏移量约为1.414 × 10^-5，严格控制在误差容限内，算法具有良好的不可见性。

4.2 篡改定位能力

篡改定位能力是衡量脆弱水印算法性能的重要指标，对嵌入水印后的矢量地图数据实施增加实体、删除实体、修改实体、实体乱序及坐标点逆序等操作，综合验证算法的篡改定位能力。

1）增加实体

在增加实体后的整幅地图数据中，最小外接矩形的中点数量增加，该实体所属聚类类别中对象的数量相应增加，且它的加入改变了该分组的完整性特征参数值，导致分组认证失败。在图 5(a)中，A标识增加实体的位置，篡改定位结果如图 5(b)所示。

2）删除实体

在删除实体后的整幅地图数据中，最小外接矩形的中点数量减少，该实体所属聚类类别中对象的数量相应减少，并且由于该实体被整体删除，必定改变整个分组的完整性特征参数值，使该分组认证失败。在图 6(a)中，B标识删除实体的位置，篡改定位结果如图 6(b)所示。

3）修改实体

修改实体可能导致两种情况，一种是修改后的实体仍在原来的分组中，此时仅该组的完整性特征参数值发生改变；另一种是修改后的实体不再属于原来的分组，而是划归到了其他分组，此时这两组的完整性特征参数值均会发生改变。在图 7(a)中，C标识修改实体的位置，篡改定位结果如图 7(b)所示。

4）实体乱序和坐标点逆序

由于本文设计的完整性特征参数不受实体乱序和坐标点逆序的影响，并且坐标排序处理确保了水印嵌入和检测的同步性，因此算法能够准确认证实体乱序和坐标点逆序操作。图 8(a)为实验数据的局部放大图，将实体a、b、c、d的存储顺序两两互换，将实体e、f中的坐标点逆序排列，整幅地图数据的认证结果如图 8(b)所示。

文献[13, 15, 19-21]同为采用分组思想的矢量地图脆弱水印算法。将本文算法与之进行对比，设遭到篡改的实体位于N个分组中，以实际可定位出篡改的实体组数量作为衡量依据，实验结果如表 1所示。

由表 1可知，文献[13, 15, 19]在增删实体后，定位出篡改的实体组数量大于或等于N，这是由于遭受增删实体篡改后，可能使分组中的坐标点数不再满足阈值要求，导致分组结果改变，引起后续认证失败。此外，文献[13, 15, 19]均不能对实体乱序及坐标点逆序做出正确认证。文献[20-21]虽将分组结果嵌入实体中以保证稳定性，但在遭到修改实体攻击时，嵌入点所携带的信息仍存在被破坏的可能，使定位结果偏大。因此，通过对比实验表明，本文算法的性能优于同类算法。

5 结语

本文提出了一种定位篡改实体组的矢量地图脆弱水印算法，能够实现对篡改数据的准确定位，避免了同一个地理实体被人为割裂到不同的数据单元中，其主要创新点如下：

1）采用优化的k均值聚类对实体进行分组，外接矩形的中点被划分到的类别即为该地理实体所属的组别，避免了因实体增删导致的分组结果不同步问题。

2）结合混沌序列的脆弱水印构造模型中设计了全新的完整性特征参数生成方法，能够有效解决篡改漏检问题，具有很强的安全性。

3）水印嵌入和检测前的坐标点排序处理保证了实体乱序、坐标点逆序后水印信息的同步性，实现了对此类操作的准确识别。

综上所述，本文算法有效保持了矢量地图的数据精度，能够对地图数据的完整性作出准确认证，确保数据安全可靠。