1.一种矢量地图完整性认证方法，其特征在于：

(1)图元顶点分类；

将矢量地图图元的顶点划分为两类：标记顶点和非标记顶点，图元为线图元或面图元，标记顶点用于标记图元所在数据单元，非标记顶点可嵌入认证水印和定位信息,将每个线图元的第一个顶点和最后一个顶点视为其标记顶点，其他顶点视为非标记顶点；将每个面图元的第二个顶点和倒数第二个顶点视为其标记顶点，其他顶点视为非标记顶点；

(2)数据单元划分；

依据每个数据单元需嵌入的定位信息长度和认证水印长度，将原始矢量地图划分为若干数据单元，假设矢量地图M包含N个图元，图元为线图元或面图元，记为P1,P2,…,PN，Pj表示第j个图元，j＝1,2,…,N，线图元Pj的顶点数目记为 划分的数据单元的数目为Nu，1≤Nu≤N，第i个数据单元为Ui，i＝0,1,…,Nu–1，数据单元序列记为 数据单元Ui所含的图元记为 为数据单元Ui的图元数目；

(3)关联数据单元；

实现数据单元间的一一映射，使每个数据单元都有唯一存储其定位信息的关联数据单元和在此数据单元中存储定位信息的被关联数据单元，具体方法为：不断地生成随机数对(r1,r2)；r1,r2＝0,1…Nu-1；通过交换序列U中元素Ur1和Ur2的位置，实现序列U的置乱，得到置乱后的序列U'＝{U1',U2',…,Um'}；依据序列U和U'，建立数据单元Ui→Ui'I，i＝0,1…Nu-

1，的一一映射，对于每一个映射关系Ui→Ui'，将数据单元Ui'视为数据单元Ui的关联数据单元，将Ui视为Ui'的被关联数据单元，Ui的定位信息将存储于Ui'中；

(4)构建定位信息；

对于每个数据单元，依据其最小外接矩形的顶点信息，构建其定位信息，具体方法为：计算数据单元Ui，i＝0,1…Nu-1，的最小外接矩形MERi＝{vi,0,vi,1,vi,2,vi,3}，其中，vi,j(xi,j,yi,j)为MERi的第j个顶点，j＝0,1,2,3；选取MERi的3个顶点作为数据单元Ui的定位信息，记为 将其被关联数据单元的定位信息记为其中，MERi”为数据单元Ui的被关联数据单元最小

外接矩形；

(5)生成认证水印；

利用散列算法，生成步骤(2)中每个数据单元的认证水印，将数据单元Ui的认证水印记为Hi，i＝0,1…Nu-1；

(6)嵌入定位信息和认证水印；

对于每个数据单元Ui，i＝0,1…Nu-1，利用可逆信息隐藏方法，将步骤(4)生成的其被关联数据单元的定位信息Qi”和步骤(5)生成的该数据单元的认证水印Hi嵌入其前Nr个非标记顶点中，在数据单元Ui中嵌入其被关联数据单元的定位信息Qi”和其认证水印Hi后，得到含水印数据单元 将 的含水印图元记为(7)标记图元；

利用步骤(6)的信息嵌入方法，在含水印数据单元 的每个图元的标记顶点的坐标中嵌入该数据单元的索引信息i，在每个图元中嵌入标记后，得到含标记矢量地图；

(8)水印认证及原始数据恢复；

依据图元标记及可逆信息隐藏方法，恢复矢量地图数据并定位篡改，具体步骤如下：(8.1)识别原始图元组；

从每个图元的标记顶点中提取嵌入的标记，并将标记顶点恢复至嵌入标记前的状态，利用标记识别每个数据单元的图元，得到含水印数据单元(8.2)定位信息和认证水印提取及原始数据恢复；

从每个含水印数据单元 中提取其被关联数据单元的定位信息 和其认证水印 以备其被关联数据单元的原始区域定位和本数据单元的水印认证，并恢复矢量地图原始数据，得到恢复数据后的数据单元(8.3)生成认证水印；

利用步骤(5)的方法，生成每个恢复数据后的数据单元 的认证水印，假设为 生成的认证水印为Hi”；

(8.4)水印认证；

依据数据单元 中提取出的水印 和生成的水印Hi”，判定该数据单元是否发生篡改，若 则该数据单元未发生篡改；否则，认为该数据单元发生了篡改，并转入步骤(8.5)定位篡改区域，(8.5)定位篡改区域；

检测数据单元 的关联数据单元是否发生了篡改，若其关联数据单元未发生篡改，则利用其关联数据单元中提取的该数据单元的定位信息，计算该数据单元的原始最小外接矩形MERi，并结合该数据单元当前最小外接矩形 计算MERi和 的并集，得到最终的篡改区域定位结果；否则，仅将该数据单元当前的最小外接矩形 视为篡改区域，验证完每个数据单元的完整性后，显示所有被篡改的数据单元区域。

2.根据权利要求1所述的一种矢量地图完整性认证方法，其特征在于：若数据单元Ui需嵌入的定位信息和认证水印长度分别为Lc比特和La比特，每个非标记顶点坐标中可嵌入的信息数目为c比特，则该数据单元所需非标记顶点数目为 因此，若数据单元Ui所含的非标记顶点数目为 若在数据单元Ui中完全嵌入Lc比特的定位信息和La比特的认证水印， 和Nr需满足如下条件基于该条件，利用以下方法划分数据单元：

(2.1)将 条图元划分到数据单元U0中， 为满足如下关系的最小正整数(2.2)依据步骤(2.1)的方法，顺次将余下的图元划分为数据单元，即对于任意数据单元Ui，i>0，从余下的图元中选择 条图元作为其成员， 为满足如下关系的最小正整数δ为数据单元U0至图元组Ui-1中所有图元的数目，即由于顺次将图元划分为数据单元，最后一个数据单元的图元可能无法提供足够嵌入空间，此时，将最后一个数据单元的图元划分至倒数第二个数据单元中。

3.根据权利要求1所述的一种矢量地图完整性认证方法，其特征在于：方法I(·)获取数据单元Ui的空间数据时，按照如下方法扫描该数据单元的图元顶点：对于图元内部顶点，从具有较大y坐标的标记顶点所在端扫描至另一端；在数据单元中，则从具有较大y坐标的标记顶点的图元扫描至具有较小y坐标的标记顶点的图元。

4.根据权利要求1所述的一种矢量地图完整性认证方法，其特征在于：假设在非标记顶点vn(xn,yn)的x坐标xn中嵌入的水印为w，w＝0,1,…,2c-1，利用如下方法嵌入w其中，linterval为满足如下关系的实数

τ为矢量地图M的精度误差容限。

5.根据权利要求1所述的一种矢量地图完整性认证方法，其特征在于：假设在标记顶点vm'(xm',ym')的x坐标xm'中嵌入的标记为i，i＝0,1…Nu-1，从xm'中提取i的具体步骤如下：(8.1.1)利用下式提取标记i

其中

(8.1.2)利用下式，恢复xm'的原始数据