基于坐标定位的矢量数据水印算法研究

金永涛 吴俊聪 陈曦 杨秀峰 周建伟



基于坐标定位的矢量数据水印算法研究

金永涛1,2吴俊聪1陈曦1杨秀峰1,2周建伟1,2

（1 北华航天工业学院，廊坊 065000）（2 河北省航天遥感信息处理与应用协同创新中心，廊坊 065000）

针对遥感专题产品质量（quality）监督过程中的责任追溯问题，在离散傅里叶变换方法的基础上提出一种改进算法，有效解决了将水印信息嵌入到矢量数据文件后的数据精度、抗攻击能力等技术难题。水印信息嵌入过程首先应用Arnold、进制转换、快速傅里叶变换等方法对二值水印信息进行预处理；其次根据密钥产生不重复伪随机数组，进行嵌入位置选取；最后将水印信息嵌入到目标位置序列横坐标的频域中。水印提取时，通过设计的定位方法，降低目标点纵坐标识别错误的几率。运用该算法分别对廊坊市林地、固安县小麦、巨鹿县设施蔬菜三组矢量数据进行实验，结果表明，提取得到水印与原水印相似度最高为100%，最低为89%，且算法对原始数据造成的误差在0.01m以内。实验结果表明，算法对原文件横纵坐标影响很小，可以有效抵抗数据添加、删除、修改、移动等攻击，因此，算法对于解决遥感专题产品质量（quality）监督过程中的技术难题切实有效。

坐标定位 傅里叶变换 质量监督 数字水印 信息安全 遥感

0 引言

对于涉及区域广、种类多、精度要求高的遥感专题产品，特别是面向县域的遥感专题产品，通常需要几个人，甚至几十人分工协作来完成，处理环节繁多。目前遥感专题产品的质量（quality）监督基本上都是采用人工记录方式，对生产出质量（quality）不合格遥感专题产品的工作人员较难进行责任追溯，且工作效率低下，在很大程度上制约了遥感专题产品生产效率和生产规模的提升。

数字水印技术是指将含有遥感数据处理人员姓名、任务等数字水印信息嵌入到矢量数据文件中，能够提高工作人员的产品质量（quality）责任意识，有利于对问题产品进行责任追溯，是解决遥感专题产品质量（quality）瓶颈问题的可行方法。目前数字水印技术普遍应用于电子出版物版权保护领域，针对遥感专题产品质量（quality）监督领域鲜有研究，例如，文献[1]根据矢量地图数据各要素层所含数据的多少，设计不同分类规则以实现嵌入不同大小的水印信息。该算法考虑到了数据量对统计特性的影响，对各种数据攻击具有一定的抵抗能力。然而对于矢量数据增加攻击操作，由于没有对含水印数据点的精准定位，水印信息提取效果不理想。文献[2]运用聚类的思想，采用K均值算法（K-means）对矢量数据进行聚类，将水印信息嵌入到分类后的载体中，取得良好效果，但在抵抗矢量数据移动攻击时，水印信息的提取效果不理想。文献[3]将数字水印信息嵌入到离散傅里叶变换的幅度和相位中，能够抵抗数据增加、平移、删除等攻击，但是只保证数据的位置精度控制在2m以内（矢量数据水印信息的嵌入是通过修改数据点坐标实现的，2m指的是嵌入水印后与原始数据对应点坐标的差），精度范围略大。因此，需要对当前数字水印算法进行改进，以满足遥感专题产品质量（quality）监督过程中对数据精度、抗攻击能力的技术需求。

本文通过将数字水印信息转换为十进制，结合快速傅里叶变换来增加数字水印容量；通过设计的坐标定位方法，在矢量数据进行增加、随机删除、移动、剪裁等攻击操作时，高质量（quality）保障嵌入到遥感专题产品数字水印的可识别性；并通过大量实验总结得出，能够将嵌入水印对原始数据造成的误差控制在0.01m以内（即含水印信息数据与原始数据对应点坐标差小于0.01m），攻击强度小于20%时，提取得到的水印与原水印相比相似度很高，特别地，在增加数据攻击时，相似度为100%，从而有效解决遥感专题产品质量（quality）监督过程中的责任追溯问题。

1 算法设计

本文提出的算法分为水印信息预处理过程、嵌入过程与提取过程。将处理后的水印信息嵌入到目标遥感专题产品，得到含水印的矢量数据文件，经过一系列处理操作的攻击后，对矢量数据文件进行水印提取，再得到对应的水印信息。嵌入水印流程如图1所示。

图1 嵌入水印流程图

1.1 水印信息预处理

数字水印嵌入遥感专题产品矢量数据文件之前，需要对水印信息进行置乱、进制转换、快速傅里叶变换等预处理，以得到适应算法的水印信息。数字水印预处理选择128像素×32像素二值图像作为原始水印信息（二值图像大小可根据质量（quality）监督实际需要而设定）。

1.1.1 水印信息置乱

水印信息置乱使用32像素×32像素（采用16像素×16像素、8像素×8像素、4像素×4像素与32像素×32像素原理相同，相应的分块数即变为256、64、16）的Arnold变换算法：首先，将128像素×32像素原始水印信息sWater划分为4个32像素×32像素待置乱水印信息平台water[4]；再对每个待置乱水印信息做Arnold变换，得到4个置乱后的32像素×32像素水印信息atWater[4]；然后把atWater[4]组合为128像素×32像素置乱后的水印信息tWater。由于Arnold变换为周期性变换，故将置乱次数计作密钥key，32像素×32像素Arnold变换周期为24。

1.1.2 水印信息进制转换

水印信息进制转换目的是把水印信息编码为一维序列，为后面水印信息傅里叶变换做准备，同时为了降低水印信息对原矢量文件的影响程度，采用归一化方法，使序列中的每个数据都小于0.01。

具体做法是将之前得到的tWater按照先行后列的顺序，编码为一维序列sArray；再将sArray中的每8个二进制位合为一个十进制数字，得到的dArray；把dArray中的每个数据都除以25 600，使其小于0.01（由于8位二进制数最大为255，故得到的数都小于0.01），得到新的dArray。sArray和dArray如式（1）和式（2）所示：

1.1.3 水印信息快速傅里叶变换

快速傅里叶变换是离散傅里叶变换的一种快速算法，能够把空域信息转换为频域信息，接受复数输入。在频域嵌入数字水印的好处是能够使水印信息分散到空域中的每个点上，增加了算法的鲁棒性。

将dArray进行傅里叶变换得到DArray如式（3）所示，其中0表示复数虚部为0，这里为了对比将其写出，i为虚数单位，、为傅里叶变换后的序号。

1.2 数字水印嵌入

将原矢量文件进行快速傅里叶变换，根据水印信息置乱时的密钥key选取嵌入位置；再利用加性准则完成数字水印的嵌入过程；最后将得到的频域系数进行快速傅里叶逆变换，将新的坐标点替换原来的坐标点，使原矢量文件嵌入水印信息。

1.2.1 嵌入位置的选取

1.2.2 水印信息的嵌入

（1）对横坐标的水印嵌入

将dData中的数据做傅里叶变换，得到频域数据DData，如式（5）所示；再应用加性准则，将傅里叶变换后的水印数据DArray嵌入到DData中，进行快速傅里叶逆变换，得到含有水印的数据wateredData，如式（6）所示；然后根据生成的不重复随机位置，将横坐标进行替换，得到含有水印信息的数据wateredData；最后，用wateredData中的实部替换原始数据中对应选取位置点的横坐标，获得含水印信息的矢量文件。

（2）含水印信息点的坐标定位

提取水印信息时，由于不是每个数据点都含有水印信息，判读数据点是否含有水印信息是通过比较纵坐标是否相同得出的。为了防止含水印信息点的纵坐标与矢量数据中不含水印信息的数据点的纵坐标相同的情况，需要对其纵坐标进行修改。具体过程分为以下两个步骤：一、去除含水印信息数据点的纵坐标序列自身出现重复（即自身重复）；二、去除水印信息数据点的纵坐标序列与不含水印信息点的纵坐标出现重复（即其他重复）。

2）其他重复：在去除自身重复后，如不含水印信息点的纵坐标与含水印信息点的纵坐标相同，则不含水印信息点的纵坐标在原纵坐标基础上加0.000 1，提取水印时结合横坐标的阈值控制，从而精准定位出含水印信息的坐标点，保证不会出现含水印信息点识别错误的情况。

1.3 数字水印提取

数字水印提取过程是嵌入过程的逆过程，同时加入了对删去点的容错机制，使得算法能够在很大程度抵抗对添加水印信息矢量文件中矢量实体进行添加、删除、移动等操作的攻击。算法应用的容错机制包括信息填充和匹配水印集。

1.3.1 信息填充

信息填充采用丢失值与前一个值相同的办法进行填充。具体方法如下：

对于存在空值的序列，从前向后遍历，如果遍历到空值，则令该处值与前一个值相同，直到遍历结束。然后，再对该序列从后向前遍历，如果还有空值，则令该处值与后面一个值相同，直到遍历结束，这样即可得到一个没有空值且数值曲线近似于原数值曲线的序列。第二次遍历的目的是防止最前面的几个值是空值的情况。

1.3.2 匹配水印集

1.4 水印容量分析

水印容量是固定大小的水印信息至少需要数据点的个数来进行算法实现，或者固定大小的数据信息，根据算法最多能嵌入水印信息的大小。

本文算法嵌入128像素×32像素大小的二值比特图最少需要512个坐标点，根据实际操作需求，可以对水印图像进行扩大，水印图像的大小最多为坐标点个数的8倍。

2 实验与分析

实验采用三个遥感专题产品矢量文件，如图2所示，图为使用ArcGis软件打开文件并进行屏幕的截取获得，其中图2（a）是廊坊市2015年9月林地遥感专题产品矢量文件，嵌入水印“S0106ZQY1509LD”；图2（b）是固安县2016年4月小麦遥感专题产品矢量文件，嵌入水印“S0018XD1604XM”；图2（c）是巨鹿县2015年6月设施蔬菜遥感专题产品矢量文件，嵌入水印“T0010YXF1506SS”。嵌入水印的标识（代码）中包含有多个数据点，如：人员编码、姓名、产品生成时间，产品类别代码等。

2.1 可视化比较

对应用文中提出的算法进行水印嵌入前后的矢量数据进行比较，将图像比例尺放大至1:1。对含水印信息数据点进行观察，含水印数据与原数据相比误差极小或没有任何区别，可以满足水印的不可感知性要求，能够很大程度满足遥感影像质量（quality）监督的需要。

图2 遥感专题产品矢量文件

2.2 误差分析

数据精度是遥感专题产品中备受关注的问题，数字水印的嵌入往往导致目标数据精度的降低，为数据的生产者和使用者带来不必要的麻烦，数字水印的嵌入不能对原始数据的精度产生太大影响，通常将精度的偏差控制在可以接受的范围之内，文中提出的算法对原始数据的改动非常小，能够很好的满足遥感专题产品的精度要求。将嵌入水印信息后的数据与原始数据对应点做减法即可得出嵌入水印前后数据误差值，表1为文中算法对原始数据造成的误差范围，以及各个范围之中数据点的个数，其中最大误差值为0.007 5m。

表1 嵌入水印前后数据误差范围及点数表

Tab.1 The range of data error and the number of data points after embedding watermark

2.3 鲁棒性分析

通过对含有水印的数据进行攻击来验证本文所提出的算法的鲁棒性，水印攻击采用的是几何攻击方法，即增加、删除、移动和剪裁等方式，使用ArcGis软件对含有水印信息的数据进行不同强度的几何攻击，然后对受到几何攻击的矢量数据进行水印提取，并计算提取后的水印信息与原始水印信息的相似度。表2列出了本文提出的算法对三种实验数据不同操作的抵抗能力。其中，攻击点数指坐标信息发生了变化的点的数量，攻击强度表示受到攻击的点数占总点数的百分比，与原水印相似度指提取得到的水印信息与原始水印信息的匹配程度。

表2 算法对三种实验数据操作攻击抵抗能力分析

Tab.2 Analysis of the resistance of the algorithm to three kinds of experimental operation attacks

（a）廊坊市林地数据

（a）The woodland data of Langfang

攻击方式攻击点数/个攻击强度/%与原水印相似度/%能否匹配正确 增加数据165 7105.00100是 331 41010.06100是 500 12615.10100是 671 21120.29100是 随机删除173 7685.2597.24是 316 4189.5595.26是 510 40815.4192.48是 679 22820.5190.53是 移动数据139 9294.2298.02是 331 89010.0294.90是 511 18815.4392.38是 903 43521.2489.28是 剪裁159 4864.8297.51是 310 4059.3795.56是 478 60414.4592.77是 641 07619.3689.87是

（b） 固安县小麦数据

（c）巨鹿县设施蔬菜

从表2可以看出，本文提出的算法对增加数据操作具有很好的抵抗能力，不会影响数字水印的正常提取。根据经验，实际工作中攻击强度一般都在20%以内，如果需要有更高的抗攻击性要求，则要以牺牲水印容量和精度为代价，具体实施办法可以用4个不同的密钥对水印信息进行置乱，随后生成4个互相无重复元素的伪随机序列，实现水印信息的冗余，提取时则可以用去掉一个最大值和一个最小值，求平均值的办法来提高抗攻击的能力。

图3是根据表2攻击点数分别对含数字水印矢量数据剪裁左边部分后提取的水印图片，按照从左到右、从上到下的顺序依次表示剪裁强度逐渐增大后的提取效果。实验表明，剪裁强度在20%以下时，提取得到的水印信息仍然清晰可见，因此，本文提出的算法能够很好地抵抗对矢量数据的常见攻击。

图3 三种实验数据剪裁左边部分后提取的水印图片（左侧：原数据，右侧：受到攻击后数据）

3 结束语

实验结果表明，本文提出的算法对廊坊市林地、固安县小麦、巨鹿县设施蔬菜三种矢量数据的水印提取效果良好，攻击强度在20%以内时，相似度为89%以上，尤其对增加数据抵抗性最高，相似度为100%。嵌入水印后的数据与原数据的误差小于0.01m，能够很好地满足遥感专题产品的质量（quality）要求，并且算法在矢量数据数字水印方面具有一定的普遍性。在下一步的研究中，将着重研究盲水印与分级授权问题，从而更好地满足遥感专题产品质量（quality）监督的需要。

[1] 闵连权. 一种鲁棒的矢量地图数据的数字水印[J]. 测绘学报, 2008, 37(2): 262-267. MIN Lianquan. A Robust Digital Watermarking in Cartographic Data in Vector Format[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(2): 262-267. (in Chinese)

[2] 曾端阳, 闫浩文, 牛莉婷, 等. 矢量地图的一种非盲数字水印算法[J]. 兰州交通大学学报, 2013, 32(4): 176-180.ZENG Duanyang, YAN Haowen, NIU Liting, et al. A Non-blind Digital Watermarking Algorithm for Vector Map Data[J]. Journal of Lanzhou Jiaotong University, 2013, 32(4): 176-180. (in Chinese)

[3] 许德合, 朱长青, 王奇胜. 利用DFT幅度和相位构建矢量空间数据水印模型[J]. 北京邮电大学学报, 2011, 34(5): 25-28.XU Dehe, ZHU Changqing, WANG Qisheng. A Construction of Digital Watermarking Model for the Vector Geospatial Data Based on Magnitude and Phase of DFT[J]. Journal of Beijing University of Posts and Telecommunications, 2011, 34(5): 25-28. (in Chinese)

[4] XU X, ZHANG Q. A New Watermarking Method Based on DCT[J]. Microcomputer Information, 2007, 23(12): 59-61.

[5] WHEN Q X, YANG J W. Wavelet Domain Watermark Algorithm Based on Median Filtering[J]. Computer Engineering, 2009, 35(18): 151-153.

[6] LI X D. Image Digital Watermarking Algorithm in Dct Domain for Resisting Brightness-and-contrast Adjusting Attack[J]. Journal of Optoelectronics Laser, 2013, 24(6): 1184-1190.

[7] SHI H, LIN CH, LI M C, et al. Contourlet Transform Based Digital Watermarking Algorithm Robust to Geometric Distortion[J]. Journal of Optoelectronics Laser, 2011, 22(10): 1575-1581.

[8] YE CH, SHEN Y Q, LI H, et al. A DWT Digital Watermarking Algorithn Based on HVS[J]. Journal of Zhejiang University(Sciences Edition), 2013, 40(2): 152-155.

[9] ZHAO X, HAO L. Overview of Digital Watermark[J]. Computer Engineering and Design, 2006, 27(11): 1946-1950.

[10] CHAI L J, LI R, YI Y Q. A Multiple Watermarks Algorithm for Image Content Authentication[J]. Journal of Central South University, 2012, 19(10): 2866-2874.

[11] 周欣, 杨国鹏, 杨俊峰. “天绘一号”卫星中级产品质量控制方法研究[J]. 航天返回与遥感, 2017, 38(1): 69-77. ZHOU Xin, YANG Guopeng, YANG Junfeng. Quality Control Method Research of Th-01 Satellite Intermediate Products[J]. Spacecraft Recovery & Remote Sensing, 2017, 38(1): 69-77. (in Chinese)

[12] JIA P H, CHEN Y Z, MA J S, et al. Digital Watermark-based Security Technology for Geo-Spatial Graphics Data[J]. Chinese Geographical Science, 2006, 16(3): 276-281.

[13] CAO R, WANG Y, LI X L. Digital Watermarking Algorithm Based on Phase and Amplitude of DFT Domain[J]. Computer Applications, 2005, 25(11): 2536-2543.

[14] JOSEPH J K, RUANAIDH O, PUN T. Rotation, Scale, and Translation Invariant Digital Image Watermarking[C]// International Conference on Image Processing, Switzerland, 1997.

[15] HAYES M. The Reconstruction of a Multidimensional Sequence from the Phase or Magnitude of its Fourier Transform[J]. IEEE Transactions on Acoustics, Speech, and Signal Processing, 1982, 30(2): 140-154.

[16] RUANAIDH J, DOWLING W J, BOLAND F M. Phase Watermarking of Digital Images[C]// International Conference on Image Processing, Lausanne, Switzerland, 1996.

[17] ZHENG D, ZHAO J, SADDIK A E. RST-invariant Digital Image Watermarking Based on Log-polar Mapping and Phase Correlation[J]. Circuits & Systems for Video Technology IEEE Transactions on, 2003, 13(8): 753-765.

[18] YANG H C. A Robust Watermarking Method Based on DCT[J]. Microcomputer Information, 2009, 25(18): 49-51.

[19] 屈颖歌, 曾生根, 夏德深. 从图像信息容量和图像功率谱看CBERS-1卫星图像[J]. 航天返回与遥感, 2002, 23(2): 40-45. QU Yingge, ZENG Shenggen, XIA Deshen. Appraise the CBERS-1 Image Quality with Image Information Capacity and Power Spectrum[J]. Spacecraft Recovery & Remote Sensing, 2002, 23(2): 40-45. (in Chinese)

[20] 谭伟, 齐文雯, 何红艳. 一种场景无关的图像清晰度评价方法[J]. 航天返回与遥感, 2017, 38(1): 107-114. TAN Wei, QI Wenwen, HE Hongyan. A Scenes Independent Image Definition Evaluation Method[J]. Spacecraft Recovery & Remote Sensing, 2017, 38(1): 107-114. (in Chinese)

（编辑：庞冰）

Research on Vector Watermarking Algorithm Based on Coordinate Location

JIN Yongtao1,2WU Juncong1CHEN Xi1YANG Xiufeng1,2ZHOU Jianwei1,2

（1 North China Institute of Aerospace Engineering, Langfang 065000, China）（2 Hebei Collaborative Innovation Center for Aerospace Remote Sensing Information Processing and Application,Langfang 065000, China）

In order to solve the problem of traceability in the process of quality supervision of remote sensing thematic products, an improved algorithm is proposed based on the discrete Fourier transform method, which solves the problem of data precision and anti-attack ability after embedding the watermark information into the vector data file. During the watermark information embedding process, the binary watermark information is firstly preprocessed using Arnold, binary conversion to decimal and fast Fourier transform. Secondly, the non-repetitive pseudo-random array is generated according to the key, and then the embedding position is selected. Finally, the watermark information is embedded and the target position sequence is in the frequency domain of the abscissa. In watermark extraction, the positioning method is designed to reduce the misidentification probability of the target point in the vertical axis. In this paper, three groups of vector data are selected to verify the method, i.e., woodland in Langfang City, Gu'an County wheat, Julu County facilities for vegetables. The results show that the highest similarity between the extracted watermark and the original one is 100% and the lowest is 89%, and the error caused by the algorithm to the original data is within 0.01m. The experimental results show that the algorithm has little effect on the vertical and horizontal coordinates of the original file, and can effectively resist the attacks such as data addition, deletion, modification and movement. Therefore, the algorithm is effective to solve the technical problems in the process of quality supervision of remote sensing thematic products.

coordinate location; fourier transform; quality supervision; digital watermarking; information safety; remote sensing

TP301.6

A

1009-8518(2017)06-0098-09

10.3969/j.issn.1009-8518.2017.06.012

金永涛，男，1978年生，2011年获天津工业大学计算机技术专业硕士学位，副教授。研究方向为遥感技术与应用、计算机网络与信息安全。E-mail：jsj_jin@126.com。

2017-06-30

国家高分辨率对地观测系统重大专项（67-Y20A07-9002-16/17）；国家高分辨率对地观测系统重大专项（67-Y40G097-9002-15/18）；河北省军民结合产业发展专项资金（JMJHZX-2016-01）