1.一种定位篡改图元组的矢量地图完整性认证方法，其特征在于，包括以下步骤：(1)图元顶点分类；

将矢量地图图元的顶点划分为两类：标记顶点和非标记顶点，标记顶点用于嵌入其所在图元所属图元组的组别信息(即标记)，非标记顶点可嵌入认证水印，将每个线图元的第一个顶点和最后一个顶点视为其标记顶点，其他顶点视为非标记顶点；

(2)基于模拟退火方法的图元组自适应划分；

依据每个图元的非标记顶点数目，将矢量地图的图元划分为若干组，将得到的最优图元组划分方法记为Sbest，假设Sbest划分的图元组数目为g(Sbest)，Sbest的第i(j＝1,2,…,g(Sbest))个图元组为 中图元的数目为 中第 个图元为(3)生成认证水印；

生成步骤(2)中每个图元组的认证水印；将图元组 的认证水印记为Hj＝{hj,i∈{0,1},i＝0,1,...,L-1}，其中，L表示Hj中比特的数目，hj,i(i＝0,1,…,L–1)表示Hj的第i个比特，将Hj转换为待嵌入水印序列Wj＝{wj,i|wj,i＝0,1,…,2c–1,i＝0,1,…,c-1 c-2 0Nr–1}，wj,i＝hj,i×c×2 +hj,i×c+1×2 +…+hj,(i+1)×c-1×2；

(4)嵌入认证水印；

利用基于量化的可逆信息隐藏方法，将步骤(3)中生成的待嵌入水印序列Wj(j＝1,

2,…,g(Sbest))嵌入到图元组 的前 个非标记顶点中；在图元组 中嵌入其对应的认证水印Hj后，得到含水印图元组 将 的含水印线图元记为(5)标记图元；

利用步骤(4)的信息嵌入方法，在含水印图元组 的每个线图元

的标记顶点的坐标中嵌入组别信息(即该组的索引值j)，在每个图元中嵌入标记后，得到含标记矢量地图；

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

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

从每个线图元的标记顶点中提取嵌入的标记，并将标记顶点恢复至嵌入标记前的状态，利用标记识别每个图元组的图元，得到含水印图元组(6.2)水印提取及原始数据恢复；

从每个含水印图元组 中提取认证水印并恢复矢量地图原始

数据，将恢复数据后的含水印图元组 记为 从 中提取出的水印序列记为Wj'＝c{wj,i'|wj,i'＝0,1,…,2 –1,i＝0,1,…,Nr–1}，利用以下公式，将Wj'转化为二进制序列Hj'＝{hj,i'|hj,i'∈{0,1},i＝0,1,…,L–1}，(6.3)生成认证水印；

利用步骤(3)的方法，生成每个恢复数据后的图元组的认证水印，假设为图元组生成的认证水印为Hj”＝{hj,i”|hj,i”∈{0,1},i＝0,1,…,L–1}；

(6.4)水印认证；

依据图元组 中提取出的水印Hj'和生成的水印Hj”，判定该图元组是否发生篡改，若Hj'＝Hj”，则该组未发生篡改；否则，该组发生了篡改，验证完每个图元组的完整性后，显示所有被篡改的图元。

2.根据权利要求1所述的定位篡改图元组的矢量地图完整性认证方法，其特征在于：定义利用模拟退火方法自适应划分图元组所需的解为：将矢量地图M的所有线图元的一种排列视为一个解，假设矢量地图M包含N个线图元，将Sr＝{P1,P2,…,PN}视为一个解，Pi(i＝1,

2,…,N)表示解Sr中第i(j＝1,2,…,N)个线图元。

3.根据权利要求1所述的定位篡改图元组的矢量地图完整性认证方法，其特征在于：定义利用模拟退火方法自适应划分图元组所需的评价函数为：Cost(Sr)＝N-g(Sr)，其中，Cost(Sr)为解Sr的评价函数值，其中，g(Sr)表示解Sr能够划分的图元组数目，计算g(Sr)的具体方法如下：(2.1)设定每个图元组需满足的条件，假设每个图元组需嵌入的认证水印的比特数目为L(L≥1)，每个非标记顶点坐标可隐藏的信息比特数目为c，则每个图元组至少包含个非标记顶点，才能完全嵌入L比特的认证水印，假设一个图元组中非标记顶点的数目为Nc(Nc≥0)，则该图元组需满足如下条件：Nc≥Nr(2.2)选取解Sr的第一个图元组，将线图元Pi的非标记顶点数目记为 解Sr的第j(j>

0)个图元组记为Gj，将解Sr的前 个线图元划分至第一个图元组G1中，其中 为满足如下关系的最小正整数(2.3)将余下的解Sr的线图元划分为各个图元组，对于每个图元组Gj(j>1)，将解Sr余下的解Sr的前 个线图元划分给该组， 为满足如下关系的最小正整数δ表示图元组Gj之前的组(即G1,G2…,Gj-1)包含的线图元的数目，即由于顺次将解Sr的线图元划分为各个图元组，可能存在最后的图元组无法完全嵌入认证水印的情况，此时，将最后一组和倒数第二组合并为一组，将解Sr的线图元划分为各个组后，得到图元组数目g(Sr)。

4.根据权利要求1所述的定位篡改图元组的矢量地图完整性认证方法，其特征在于：定义利用模拟退火方法自适应划分图元组所需的新解生成函数为：假设Sr为当前解，通过随机交换Sr的两个线图元位置的方式，生成当前解的新解，将新解生成函数记为Neighbor(·)。

5.根据权利要求1所述的定位篡改图元组的矢量地图完整性认证方法，其特征在于：利用模拟退火方法，自适应划分图元组的具体过程如下：(2.4)假设初始解为So，当前解为Scur，最优解为Sbest，初始温度为To，当前温度为Tcur，内层循环最大次数为Innermax，外层循环最大次数为Outermax，当前内层循环次数为Innercur，当前外层循环次数为Outercur，矢量地图M的N个线图元依据记录号的排列为 令Scur＝So，Sbest＝So，Tcur＝To，Innercur＝0，Outercur＝0，(2.5)利用新解生成函数Neighbor(·)，由当前解Scur生成新解Snew，(2.6)依据增量ΔC，判定是否接受新解Snew

ΔC＝Cost(Snew)-Cost(Scur)

kB为Boltzmann常数，random为在区间(0,1)内均匀分布的随机小数，如果ΔC＜0或者exp(-ΔC/(kBTcur))＞random，则接受新解Snew为当前解，即另Scur＝Snew；如果接受Snew为当前解并且Cost(Snew)

6.根据权利要求1所述的定位篡改图元组的矢量地图完整性认证方法，其特征在于：生成认证水印Hj的方法如下：其中，I(·)表示获取空间数据和属性数据的方法，k表示生成hash(·)输入参数的私钥，Vj图元组 顶点的数目，Min表示该矢量地图的索引值，hash(·)表示一个已有的加密哈希算法，grouphash(Hja,L,K)表示在私钥K的控制下从比特序列Hja中选择L比特的方法，方法I(·)获取图元组 的空间数据时，按照如下方法扫描该组的图元顶点：对于一个线图元，从具有较大y坐标的标记顶点所在端扫描至另一端，在图元组内部，则从具有较大y坐标的标记顶点的线图元扫描至具有较小y坐标的标记顶点的线图元。

7.根据权利要求1所述的定位篡改图元组的矢量地图完整性认证方法，其特征在于：假设在非标记顶点vn(xn,yn)的x坐标xn中嵌入的水印为wj,i，嵌入wj,i的方法如下：其中，

linterval为满足如下关系的实数

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

8.根据权利要求1所述的定位篡改图元组的矢量地图完整性认证方法，其特征在于：假设在标记顶点vm'(xm',ym')的x坐标xm'中嵌入的标记为j(j＝1,2,…,g(Sbest))，从xm'中提取j的具体步骤如下：(6.1.1)利用下式提取标记j

其中

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