EN中文

Journal of Geo-information Science >

2015 , Vol. 17 >Issue 2: 166 - 171

DOI: https://doi.org/10.3724/SP.J.1047.2015.00166

Orginal Article

An Accurate Authentication Algorithm Based on Point Constraint Block for Vector Geographic Data

  • REN Na , * ,
  • WU Wei ,
  • ZHU Changqing
Expand
  • 1. Key Laboratory of Virtual Geographical Environment, Ministry of Education, Nanjing Normal University, Nanjing 210023, China;2. Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application, Nanjing 210023, China
*Corresponding author: REN Na, E-mail:

Received date: 2014-11-12

  Request revised date: 2014-12-02

  Online published: 2015-02-10

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

Fragile watermarking technique has been viewed as an effective method to achieve content authentication, which not only detect any modifications that occurred, but also locate the modified areas. Based on fragile watermarking technology, an accurate authentication scheme based on point constraint block is proposed, which detects the malicious attacks with high accuracy while ensuring to locate exactly the tampered area for vector geographic data. Our innovative strategy is based on point constraint block and uses the spatial relationships between the elements of data points. In the authentication information embedding process, vector geographical data is divided into blocks according to the method of point constraint block, and the spatial positional relationship between the data points of each block is reordered by the "Zig-Zag" pattern, so as to establish an organized positional relationship between data points. Then, for each point, the fragile watermark information is generated by its adjacent point, and is embedded into the current point. In the process of content authentication, the extracted watermark information is compared with the generated watermark information, and the comparative result is used to judge whether the data have been updated. The proposed algorithm is furthermore compared with the method that is based on a uniform block, and the experimental results show that the proposed authentication algorithm can accomplish accurate authentication when the data is updated, and it has the ability to achieve the accurate authentication of deleted elements. Meanwhile, when data modifications are detected, it can locate and mark the modification positions.

Key words： vector geographic data; fragile watermarking; point constraint block; accurate authentication; anti-deleting

Cite this article

REN Na , WU Wei , ZHU Changqing . An Accurate Authentication Algorithm Based on Point Constraint Block for Vector Geographic Data[J]. Journal of Geo-information Science, 2015 , 17(2) : 166 -171 . DOI: 10.3724/SP.J.1047.2015.00166

1 引言

矢量地理数据的真实性和可靠性直接决定了数据的使用价值,变化检测在数据更新维护过程中发挥着重要作用。脆弱水印技术是近年来兴起的一种信息安全前沿技术,在内容认证、修改定位、数据重构等方面有广泛的应用。脆弱水印技术将水印信息嵌入到载体数据中,水印信息和载体数据融为一体,认证时无需原始数据,从而克服了数字签名技术的缺陷,可实现对数据内容真实性的精确认证,同时对发生变化的数据位置进行检测定位[1-2]。
脆弱水印是数字水印技术的一个重要分支,它能准确检测到数据的篡改位置、篡改量甚至篡改类型,是解决矢量地理数据完整性认证难题的有力手段。随着矢量地理数据应用的深入,尤其是网络化应用的普及,矢量地理数据认证方面的要求也日趋增多。如何在矢量地理数据遭破坏后及时发现并有效检测破坏信息、鉴别数据的变化类型与位置,是当前迫切需要解决的问题。
目前,针对矢量地理数据的水印技术研究集中在用于版权保护的鲁棒水印技术[3-9],而用于内容认证的脆弱水印技术研究相对较少[10-11]。Cox等[12]在1993年最早公开发表了关于矢量地理数据脆弱水印的文献,文中提出将水印信息嵌入到矢量地图的顶点坐标上。由于该算法是将水印信息按照比特位分别嵌入到各个数据点上,因此无法抵抗各种形式的攻击。考虑到矢量地理数据篡改定位精度,很多学者将矢量地理数据进行分块或组,能够将篡改定位精确到相应的分块或组[13-17]。王奇胜等[18]利用矢量地理数据自身的特征生成脆弱水印,并且将水印信息嵌入到数据点上,将篡改定位精确到数据点。因此,一旦整个要素被整体删除时,就无法检测到水印信息,即被“伪认证”通过。
由此可见,目前矢量地理数据精确认证的分块方法中,并未充分考虑矢量地理数据的要素特征和其分布特征,定位精度还不能满足实际需求,且不能抵抗要素的删除攻击。本文以点约束对矢量地理数据进行分块,并利用块内要素之间的空间位置关系,为要素之间重新建立相互联系,以此实现基于脆弱水印技术的抗要素删除的矢量数据精确认证算法。

2 算法思想

本文算法从2个角度对矢量地理数据脆弱水印算法进行设计：（1）点约束分块;（2）块内数据的重排序。本文考虑在对数据点排序之前先进行分块操作,利用对数据点进行分块的方式来提高定位精度和准确度。
（1）点约束的分块机制。为有效适应矢量地理数据的复杂性及分块不均匀性,提出点约束的分块方法以提高定位精度和准确度。
（2）要素数据点的重排序。对每个分块内的数据点进行“之字形”排序,建立块内要素的联系,这是有效抵抗要素删除攻击的根本。
（3）基于量化的思想嵌入水印信息,可有效控制数据的精度,从而不影响矢量地理数据的使用价值。

3 点约束的矢量地理数据分块方法

矢量地理数据通过使用数据点的坐标来表示地理要素,这些坐标一般使用绝对坐标,每一个坐标都具有精确的定位价值,描述了地理要素的轮廓信息。数据点的多少和分布取决于地理要素的复杂程度,有些很复杂的地理要素就需要细密的坐标点来表示,有些很规则的只需要稀疏的坐标点就可以表示。因此,矢量地理数据的数据点坐标分布并不是均匀的。如果只是单纯的均匀分块,并不适用于复杂的矢量地理数据精确认证算法。

3.1 均匀分块方法

原始矢量地理数据记为V,读取其所有的数据点,记为 P = { p i ( x i , y i ) | i = 1,2 , … , m } ,其中,xi和yi是数据点pi的横坐标和纵坐标值,m是数据点的总数。所有数据点围成的区域面积记为Sv,S为自定义的最小数据块的面积。数据点的均匀分块方法如下：
（1）将V按照水平方向分成面积相等的2个数据子块,记为Vh1和Vh2。如果Vh1和Vh2中任一子块数据点围成的区域面积小于S,则取消V的分块操作。
（2）对于数据子块Vh1再按照y轴方向分成面积相等的2个数据子块,记为Vh1w1和Vh1w2。如果Vh1w1和Vh1w2中任一子块数据点围成的区域面积小于S,则取消Vh1的分块操作。
（3）对于数据子块Vh2再按照y轴方向分成面积相等的两个数据子块,记为Vh2w1和Vh2w2。如果Vh2w1和Vh2w2中任一子块数据点围成的区域面积小于S,则取消Vh1的分块操作。
（4）重复步骤（1）至（3）,直至分块完成。

3.2 点约束的分块方法

均匀分块是按照面积进行分块,只适用于要素分布比较均匀的矢量地理数据。但是矢量数据的数据点坐标分块常常存在分布不均匀的情况,有些很复杂的地理要素就需要细密的坐标点来表示,有些很规则的只需要稀疏的坐标点就可以表示。为解决这一问题,进一步提出点约束的分块方法,以实现更好的变化检测定位精度和准确度。具体步骤如下：
（1）按照均匀分块方法将数据分为面积相等的均匀数据子块Vn;
（2）根据实际需求,假定自适应分块的点约束条件为每个数据子块中包含的数据点个数不超过t。如果数据子块Vn中包含的数据点个数大于t,则按照均匀分块方法,继续将数据子块Vn按照x轴方向或y轴方向分为面积相等的2个数据子块。对每一个数据子块都重复操作,直至所有的数据子块中包含的数据点个数都小于或者等于t。
其中,面积S的大小对于修改定位的精度有着至关重要的作用,如果面积S过大,在认证检测时对于修改的定位精度就会相对较差;如果面积 S 过小,则分块操作的耗时就会比较长,影响数据认证的效率。

4 基于脆弱水印的精确认证算法

本文算法的具体流程如图1所示。脆弱水印信息嵌入基本过程：
Fig. 1 Flowchart of accurate authentication algorithm

图1 精确认证算法的流程图

（1）对矢量地理数据按照点约束分块方法对矢量地理数据进行分块;
（2）对于每个分块内的数据点进行空间位置关系的“Zig-Zag”排序,提取每个分块内的所有数据点,将数据点按照x坐标值和y坐标值由小到大进行“Zig-Zag”排序,从而建立数据点之间的位置关系;
（3）脆弱水印信息生成。假设水印信息为, w = { 0,1 , 2 , ⋯ , N - 1 } ,按照下面的公式生成脆弱水印信息值。
w i = f 2 ( k i ) （1）
k i = f 1 ( y i * ) = ( ( y i * ) 2 ⊕ R M i ) 10 （2）
w i = f 2 ( k i ) = N - 1 2 1 + sin 2 π k i N - 1 （3）
式中, y i * 用二进制序列表示,长度为L,则RMi用随机数发生器生成长度为L的二值序列, ⊕ 表示异或操作。函数 f 1 ( y i * ) 是将坐标精度位前数值的二进制信息与等长的伪随机序列进行异或操作,并且将所得的二进制序列转换为十进制的整数 k i , k i ∈ Z , Z 为整数集;函数 f 2 ( k i ) 是利用映射函数将整数 k i 映射生成水印信息 w i , w i ∈ W 。
（4）将前一个数据点所生成的脆弱水印信息,按照量化的思想嵌入到排序后的相邻数据点y坐标值的精度位上。
脆弱水印检测和精确认证的基本过程为：
① 按照嵌入时相同的方法,对矢量地理数据进行分块及块内数据点排序;
② 利用前一个数据点计算得到脆弱水印信息并且量化;
③ 与从相邻数据点y坐标精度位上的原始脆弱水印信息进行比较,如果两者相等,则表示数据没有发生修改,精确认证通过;反之则表示发生篡改,精确认证不通过,并对该位置进行定位和标记。

5 算法实验与分析

对本文提出的算法进行实验验证,实验数据为一幅1：25万的等高线图,其中,包含线状要素235条,数据点总个数为34 282个,如图2所示。为兼顾认证效率和变化检测的定位精度,令最小分块面积为S=1/1000Sv,数据块中包含的数据点个数最大值t=50。
Fig. 2 Original data

图2 原始数据

（1）可视化分析
对比嵌入水印前后的局部放大数据来判断本文算法的不可见性,对比结果如图3所示。从图3可看出,嵌入脆弱水印后的数据从肉眼很难看出二者的差别。由此可见,本文算法具有良好的不可见性。
Fig. 3 Visual results before and after embedding a fragile watermark (partial enlarged view)

图3 嵌入脆弱水印前后的数据可视化对比结果（局部放大图）

（2）误差分析
对嵌入脆弱水印前后的数据进行误差统计和分析,结果如表1所示。从表1看出,脆弱水印嵌入时的点约束分块处理同样没有对数据精度造成过多的影响,依旧只有少量数据点的误差较大,仍在可接受的误差范围内,整体来说不影响数据的使用价值。
Tab. 1 Error analysis

表1 误差分析

精度位变化大小 数据点个数（个） 占总数比例（%）
0 12081 35.24
0-1 14015 40.88
1-2 6750 19.69
2-3 1436 4.19
>3 0 0
（3）矢量地理数据精确认证
对嵌入认证信息的矢量地理数据进行精确认证,该数据未进行任何的攻击处理,认证结果如图4所示。从图4的实验结果可以看出,对没有经过任何变化的含认证信息的矢量地理数据进行精确认证时,数据能顺利通过认证,未显示有篡改信息,不予标记。
Fig. 4 Accurate authentication results

图4 精确认证结果

（4）增加要素
对含认证信息的矢量地理数据增加2个要素,一个在要素分布密集区域,另一个在要素分布稀疏区域。分别采用均匀分块和点约束分块方法进行认证,结果如图5所示。其中,图5（a）采用的是采用均匀分块的认证结果,图5（b）采用的是点约束分块的认证结果。对比图5（a）和图5（b）的认证结果可以看出,本文提出的点约束分块方法能够检测到要素增加的修改。同样的最小分块面积,在要素分布相对密集的区域增加要素,点约束分块算法比均匀分块方法的修改定位更为集中,定位的精度和准确度效果都较好;在要素分布相对稀疏的区域增加要素,修改定位精度和准确度与均匀分块算法保持一致。
Fig. 5 Authentication results after adding elements to watermarked data elements

图5 含水印数据增加要素后的认证结果

（5）平移要素
对含认证信息的数据进行整体的平移操作,再对其进行认证,结果如图6所示。其中,图6（a）采用的是均匀分块的认证结果,图6（b）采用的是点约束分块的认证结果。从图6（a）和图6（b）认证结果可以看出,对含水印数据进行平移后,本文算法同样能有效检测出平移修改并且定位修改,与均匀分块算法的检测效果相差不大。
Fig. 6 Authentication results after translating elements to watermarked data elements

图6 含水印数据平移要素后的认证结果

（6）删除要素
对含水印数据进行删除要素攻击,分别在数据分布密集和稀疏的区域删除一个要素,然后再对其进行认证,结果如图7所示。其中,图7（a）采用的是均匀分块的认证结果,图7（b）采用的是点约束分块的认证结果。对比图7（a）和图7（b）的认证结果可以看出,本文算法能检测到要素删除的修改。同样的最小分块面积,在要素分布相对密集位置删除一个要素,点约束的分块方法比均匀分块方法的修改定位更集中、精度更高;在要素相对稀疏位置删除一个要素,修改定位精度和准确度与均匀分块的认证结论保持一致。
Fig. 7 Authentication results after deleting elements from watermarked data elements

图7 含水印数据删除要素后的认证结果

6 结语

本文提出点约束分块的矢量地理数据精确认证算法,既能利用脆弱水印技术实现快速、高效的数据变化检测,并可识别数据变化的位置、类型等。该算法的特点：（1）适合于要素分布不均匀的数据,可较好地修改定位精度和准确度,算法的普适性较高;（2）能有效抵抗要素删除攻击;（3）是盲检测的精确认证算法,适于实际应用。其研究成果可为地理国情监测、矢量地理数据的更新与维护等提供新的技术手段。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Alomari R S, Al-Jaber A.A fragile watermarking algorithm for content authentication[J]. International Journal of Computing & Information Sciences, 2004,2(1):27-37.

[2]
Meenakshidevi P, Venkatesan M, Duraiswamy K.A fragile watermarking scheme for image authentication with tamper localization using integer wavelet transform[J]. Journal of Computer Science, 2009,5(11):831-837.

[3]
Doncel V R, Nikolaidis N, Pitas I.An optimal detector structure for the Fourier descriptors domain watermarking of 2D vector graphics[J]. IEEE Transactions on Visualization and Computer Graphics, 2007,13:851-863.

[4]
闵连权. 一种鲁棒的矢量地图数据的数字水印[J].测绘学报,2008,7(2):262-267.

[5]
张丽娟,汪海龙,牛夏牧,等.基于统计特征的二维矢量地图鲁棒水印算法[J].电子学报,2005,33(12A):2312-2316.

[6]
钟尚平,刘志峰,陈群杰.采用复合整数变换差值扩大法的矢量地图可逆水印算法[J].计算机辅助设计与图形学学报,2009,21(12):1840-1849.

[7]
杨成松,朱长青.基于常函数的抗几何变换的矢量地理数据水印算法[J].测绘学报,2011,40(2):256-261.

[8]
Lee S H, Kwon K R.Vector watermarking scheme for GIS vector map management[J]. Multimedia Tools and Applications, 2013,63(3):757-790.

[9]
Wu B Y, Wang W.Research on applied technology in blind and shape-preserving watermarking of vector map data using variable quantization step[J]. Advanced Materials Research, 2014, 886: 706-710.

[10]
Yue M L, Peng Z Y, Peng Y W. A Fragile watermarking scheme for Modification type characterization in 2D vector maps[C]. 16th Asia-Pacific Web Conference (APWeb). Changsha, China. 2014, 8709:129-140.

[11]
Yue M L, Peng Z Y, Peng Y W.A fragile watermarking scheme for modification type characterization in 2D vector maps[C]. Web Technologies and Applications - 16th Asia-Pacific Web Conference, APWeb 2014, Proceedings, 2014, 8709: 129-140.

[12]
Cox G S, De Jager G.A survey of point pattern matching techniques and a new approach to point pattern recognition[C]. Proceedings of South African Symposium on Communications and Signal Processing, 1993:243-248.

[13]
郑良斌,贾玉禄,王群.用于矢量地图完整性验证的脆弱数字水印算法[J].计算机工程与应用,2010,46(26):99-101.

[14]
郑良斌,冯柳平,陈如琪,等.矢量图形脆弱水印研究与实现[J].计算机应用研究,2011,28(10):3820-3822.

[15]
Zheng L, You F.A fragile digital watermark used to verify the integrity of vector map[C]. EBISS'09. International Conference on E-Business and Information System Security, IEEE, 2009:1-4.

[16]
Zheng L, Li Y, Feng L, et al. Research and implementation of fragile watermark for vector graphics[C].2010 2nd International Conference on Computer Engineering and Technology (ICCET), IEEE, 2010,1:V1-522-525.

[17]
李莎莎,王海荣,周卫,等. 基于易碎水印的GIS矢量数据完整性认证方法[J].测绘通报,2013(11):101-105.

[18]
王奇胜,朱长青.一种用于精确认证的矢量地理数据脆弱水印算法[J].测绘科学技术学报,2012,29(3):218-221.

Options
Outlines

/

〈 〉