一种基于矢量要素存储顺序的水印方法

吴国梁，张 黎，高 翔

（1.重庆市地理信息中心，重庆401121）

一种基于矢量要素存储顺序的水印方法

吴国梁1，张 黎1，高 翔1

（1.重庆市地理信息中心，重庆401121）

提出了一种基于矢量要素对象存储顺序的数字水印方法。利用算术编码技术，将水印信息隐藏在矢量对象的存储顺序中，实现了对数字水印的嵌入与提取。实验表明，该算法不会改变数据的几何精度，具有较好的透明性，对裁剪﹑缩放﹑平移﹑旋转﹑坐标转换等攻击具有较好的鲁棒性。

矢量要素；存储顺序；数字水印

随着信息技术的发展和大数据时代的到来，数据的加密﹑认证﹑防伪和版权保护等越来越为人们所重视。数字水印就是一种能够携带版权保护信息和认证信息的数字产品版权保护技术[1]。由于易复制﹑修改和再传输等特性，测绘地理信息成果电子数据的管控比传统纸质数据更加困难[2]，通过嵌入数字水印来标识成果数据，不失为一种好的管理方法。目前保护矢量数据的数字水印技术，主要包括基于坐标点的算法﹑基于变换域的算法﹑基于地图划分的算法和基于坐标点排序划分的算法等，如基于灰度图像的矢量数据水印算法﹑LSB算法等[3-5]。这些算法要么改变了矢量对象的空间坐标，降低了数据精度；要么难以抵御缩放﹑旋转﹑坐标转换等方法的攻击，实用性不强[3,6]。本文提出了一种基于矢量要素对象存储顺序的数字水印嵌入和提取方法，在不降低数据精度的情况下，能有效抵御裁剪﹑缩放﹑平移﹑旋转﹑坐标转换等攻击，具有较好的安全性和实用性。

1 水印方法设计

1.1 基本原理

首先利用算术编码技术把要嵌入的水印信息转换为一个整数N，确定最少需要的元素个数M，进行全排列，并找出序号为N的元素的具体排列顺序；再按坐标大小对矢量数据对象进行排序，按M对数据对象进行分组，根据序号为N的元素的排列顺序对每组数据对象的存储顺序进行调整，从而实现水印信息的嵌入。水印信息提取时，先按坐标大小对数据对象进行排序，通过与原始数据对象的存储顺序进行比较，提取水印单元和具体的数据对象排列顺序；再推算出排列序号N；然后利用算术编码技术对N进行译码，从而提取出水印信息。

本文以在一幅标准的1∶500矢量数字地形图中嵌入和提取“重庆测绘质检”的水印信息为例，说明该算法的实现过程。

1.2 水印的嵌入

1）采用算术编码方法将水印信息表示为0～1的一 个间隔，即将“重庆测绘质检”字符串编码成[0,1]区间上的一个浮点小数。符号序列越长，编码表示它的间隔越小，这一间隔所需的位数就越多。为了简化计算，假设各字符的概率分布如表1所示。根据假设的概率分布，水印字符的编码过程如表2所示。

表1 水印字符的概率分布

表2 水印的编码过程

2）令(M-1)!＜31 042＜M!，易得M=8，选取8个元素(A1,A2,A3,A4,A5,A6,A7,A8)进行全排列，排列顺序如表3所示。

下面计算序号31 042的具体排列，方法步骤为：

①建立一个数组a[0]=A1, a[1]=A2,a[2]=A3, a[3]= A4, a[4]=A5, a[5]=A6, a[6]=A7, a[7]=A8，共8个元素；②31 042-1=31 041，计算31 041/(8-1)！，商为6，余数为801，所以排列的第一个元素为a[6]=A7；③ 去掉A7，将a[6]后面的元素依次向前移动一位，得到一个新的数组a[0]=A1, a[1]=A2, a[2]=A3, a[3]=A4, a[4]=A5, a[5]=A6, a[6]=A8，共7个元素；④计算801/ (7-1)！，商为1，余数为81，所以排列的第二个元素为a[1]=A2；依此类推，可计算得到序号31 042对应的排列顺序为(A7,A2,A1,A6,A4,A5,A8,A3)。

表3 元素排序

3）读入待嵌入水印的矢量数字地形图文件，并根据数据对象坐标的大小进行排序，计为V (V1, V2, …,V8, …,VD)。

①根据水印信息31 042的计算，需要8个数据对象的空间关系才能完整描述清楚，所以取出一个水印单元S (V1, V2,…,V8)∈V(V1, V2,…,V8,…,VD)，(V1,V2,…, V8)与(A1,A2,…,A8)分别对应，其存储顺序调整为(V7,V2,V1,V6,V4,V5,V8,V3)；②循环步骤①，直至剩余数据对象不足一个水印单元为止。

4）将调整存储顺序后的数据对象写入文件中，即完成了水印的嵌入。嵌入水印前后数据对象存储顺序对比如图1所示。

图1 水印嵌入前后数据对象的存储顺序对比

1.3 水印的提取

1）读入已嵌入水印的地形图数据，记录其原始对象顺序信息V ′(V ′1,V ′2,…,V ′M,…,V ′D)，根据对象的坐标大小进行排序，得到V(V1,V2,…,VM,…,VD)。

2）比较V与V ′两个数列，若含有水印信息，则两个数列存在明显有规律的对应关系，可据此提取水印单元S。

3）以水印“重庆测绘质检”为例，一个水印单元包含8个数据对象S(V1,V2,…,V8)，数据对象按坐标大小排列记为(A1,A2,A3,A4,A5,A6,A7,A8)，可以推出V1=A7,V2=A2,…,V8=A3，从而得到水印单元的排列为(A7,A2,A1,A6,A4,A5,A8,A3)。

4）由排列(A7,A2,A1,A6,A4,A5,A8,A3)推算其排列序号。①排列逆数。排列中某元素序号后面小于它的元素序号个数称为它的逆数。A2元素后面只有A1的序号比它小，因此其逆数为1，同理A4元素后面有A3序号比它小，其逆数为1，依此类推排列(A7,A2,A1,A6,A4,A5,A8,A3)的逆数为（6,1,0,3,1,1,1,0）。②排列的权序。在1，2，3，4，5，6，7，8个数字组成的全排列中，定义第n个数字的权序是(8-n)!，所以任何一个排列的权序都是(7!，6!，5!，4!，3!，1!，0!)。③排列的序号N =权序×逆数+1。N=(6,1,0,3,1,1,1,0)×(7!，6!，5!，4!，3!，1!，0!)+1 = 6×7!+1×6!+0×5!+3×4!+1×3!+1×2!+1×1!+0×0!+1= 31 042。

5） 根据算术编码，水印信息31 042恢复为0.310 42。0.310 42的译码过程如表4所示。水印的提取过程如图2所示。

表4 译码过程

图2 水印提取过程

2 实验结果及分析

本文用于嵌入水印的地形图共包括122个多边形﹑2 436条多线段﹑1 017个文字﹑1 834个块参照，水印信息为字符串“重庆测绘质检”。

2.1 几何精度

图3为原始地形图与嵌入水印后地形图的叠加，可见两个图层的数据完全重合，地形图的几何精度无损，因此本文的水印算法在视觉上是透明的。

图3 嵌入水印前后的地形图套合效果

2.2 鲁棒性

水印的鲁棒性是指对矢量地图数据进行常规的攻击处理操作后，仍能保持水印被正常提取[7]。通过地图裁剪﹑几何变换﹑随机噪声等攻击对水印信息带来的干扰，分析水印算法的鲁棒性，实验结果如表5所示。可以看出，水印算法对常规的地图攻击方式，如裁剪﹑平移﹑旋转﹑缩放﹑随机噪声﹑随机增点﹑格式转换等的鲁棒性较高。

表5 水印算法鲁棒性统计

3 结 语

基于矢量要素对象存储顺序的数字水印算法，将水印信息与矢量数据对象空间关系特征相结合，通过调整矢量数据对象的存储顺序，避免了对对象坐标的调整，保证了数据精度不受影响。由于数据对象空间关系不变的特征，所以该算法对缩放﹑平移﹑坐标转换﹑旋转等攻击具有较好的鲁棒性。该算法可广泛用于矢量空间数据的版权认证﹑追踪，特别适合对精度要求严格的矢量数据嵌入水印。

[1] 陈明奇,纽心忻,杨义先.数字水印的研究进展和应用[J].通信学报,2001,22(5):71-79

[2] 吴金海,林福宗.基于数字水印的图像认证技术[J].计算机学报,2004,27(9):1 153-1 161

[3] 王云飞,赵婧,王拓,等.一种抗几何变换攻击的矢量数据盲水印算法[J].计算机工程,2013,39(1):136-139

[4] 高会军,刘文霞,暴轩,等.一种基于LSB算法的数字水印改进技术[J].现代电子技术,2009(13):86-88

[5] 吴海涛,詹永照.数字水印技术综述[J].软件导刊, 2015,14(8):45-49

[6] 吴柏燕,李朝奎,王伟,等.一种面向地图对象的矢量地图数字水印方法[J].地理信息世界,2011(2):45-52

[7] 李强,闵连权,吴彬,等.一种实用的矢量地图数据盲数字水印解决方案[J].测绘工程,2010,19(4):65-67

P208

B

1672-4623（2017）09-0016-03

10.3969/j.issn.1672-4623.2017.09.005

2017-02-24。

项目来源：重庆市规划局2016年重点决策应用咨询和科技成果推广应用资助项目。

吴国梁，工程师，主要研究方向为测绘地理信息成果质检、测绘地理信息标准化、城市规划等。