一种基于矢量空间数据对象存储顺序的数字水印方法

摘要

本发明公开了一种基于矢量空间数据对象存储顺序的数字水印方法，首先利用算术编码技术，将水印信息转换为一个整数N，计算出最少需要的元素个数M，并进行全排列，解算出序号N的元素具体排列顺序。对矢量数据对象按坐标的大小进行排序，并按M对数据对象进行分组；根据序号N的元素具体排列顺序对每组数据对象的存储顺序进行调整。水印信息提取时，对数据对象按坐标大小进行排序，通过与原始数据对象存储顺序进行比较分析，提取水印单元和具体的数据对象排列顺序，然后推算出排列序号N，再利用算术编码技术对N进行译码，从而提取出水印信息。本发明可实现水印信息的嵌入和提取，对缩放、平移、旋转、坐标转换等攻击具有较好的鲁棒性。

说明书

技术领域

本发明涉及利用算术编码技术，将水印信息隐藏在矢量空间数据对象存储顺序中，从而实现矢量数据数字水印的嵌入与提取。

背景技术

随着大数据时代的到来，矢量空间数据作为信息的基本载体，其安全性和版权保护越来越重要。目前对矢量空间数据保护的数字水印技术，主要是对水印信息进行编码，将这些编码编入到矢量对象坐标的最低有效位上从而实现水印信息的来嵌入。但由于改变了矢量对象的空间坐标，降低了数据精度，同时无法抵御缩放、旋转、坐标转换等方法的攻击等问题。所以从实用性角度来看，目前的矢量空间数字水印仍无法解决精度损失问题，同时也不能有效对抗坐标转换、旋转等攻击，缺乏安全性和实用性。

发明内容

针对目前矢量空间数据水印算法会降低数据的精度，鲁棒性不强等问题，本发明的目的在于：提出了一种结合矢量数据对象空间关系特征水印嵌入和提取的方法，在不降低数据精度的情况下，能有效抵御坐标转换、旋转、缩放、平移等方法的攻击。

为了实现上述目的本发明所采用的技术方案是：

一种基于矢量空间数据对象存储顺序的数字水印方法，其特征在于：

1)编码水印信息：利用算术编码技术将被编码符号串表示为0到1之间的小数，去掉“0.”，保留小数部分，使之变为整数N；

2)确定M的值使(M-1)！<N<M！，选取M个元素，记为A₁,A₂……A_M，将所述M个元素进行全排列，并将排列结果按照从小到大计数为1到M！，选择第N种排列结果，获得其排列顺序；

3)读取待嵌入水印的矢量空间数据对象，对矢量空间数据对象按照坐标的大小进行排序V(V₁,V₂......V_M......V_D)，其中D>M，然后每M个矢量空间数据对象划分为一组，每组为一个水印单元S，将每个水印单元S中的数据对象按照步骤2)中获得的排列顺序重新排列，从而实现水印信息的嵌入，并保存嵌入水印后的文件；

4)水印信息提取时，读取矢量数据文件，记下矢量数据对象的存储顺序，然后按矢量数据对象坐标的大小进行排序，比较两种排序，提取出水印单元S以及水印单元S中数据对象的具体排列顺序，计算出该排列顺序的序号为N；

5)将序号N前面添加“0.”，形成一个0至1间的小数，再根据算术编码技术进行译码，从而提出具体的水印信息；显示带有水印信息的矢量空间图。

为了更好地实现上述方案，步骤2)所述选取的M个元素是互不相等的。

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

附图说明

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

图2为水印信息提取过程示意图；

图3为算术编码过程示意图。

具体实施方式

实例：用ArcMap读取矢量图形文件(即为待嵌入水印的矢量空间数据对象)，试验数据为“重庆市兴趣点”，shp格式，几何属性为点，水印信息为"重庆师范大学"。

一、水印嵌入过程

1)采用算术编码方法将被编码符号串(序列)表示成0和1之间的一个间隔，即对一串符号直接编码成[0,1]区间上的一个浮点小数，符号序列越长，编码表示它的间隔越小，表示这一间隔所需的位数就越多。为了简化计算，可假设具有如下概率分布：

字符概率范围大0.1[1,0.1)学0.1[0.1,0.2)重0.2[0.2,0.4)庆0.2[0.4,0.6)师0.2[0.6,0.8)范0.2[0.8,1)

参见图3，"重庆师范大学"编码过程如下：

将0.31042去掉0.得到整数31042。

2)根据(M-1)！<31042<M！，因为7！＝5040，8！＝40320，可算出M＝8。

所以需选取8个元素(A₁，A₂，A₃，A₄，A₅，A₆，A₇，A₈)进行排列：

按排列元素序号从小到大进行计数，如下：

1  (A₁，A₂，A₃，A₄，A₅，A₆，A₇，A₈)

2  (A₁，A₂，A₃，A₄，A₅，A₆，A₈，A₇)

…….

40320(A₈，A₇，A₆，A₅,A₄,A₃,A₂,A₁)

现在需要计算31042的具体排列：

(1)建立一个数组a[0]＝A₁,a[1]＝A₂,a[2]＝A₃,a[3]＝A₄,a[4]＝A₅,a[5]＝A₆,a[6]＝A₇,a[7]＝A₈共8个元素。

(2)31042-1＝31041，计算31041/(8-1)！，商为6，余数为801，所以排列的第一个元素a[6]＝A₇

(3)去掉A₇，将a[6]后面的元素依次向前移动一位，得到一个新的数组a[0]＝A₁,a[1]＝A₂,a[2]＝A₃,a[3]＝A₄,a[4]＝A₅,a[5]＝A₆,a[6]＝A₈共7个元素

(4)计算801/(7-1)！，商为1，余数为81，所以排列的第二个元素a[1]＝A₂

(5)去掉A₂，将a[1]后面的元素依次向前移动一位，得到一个新的数组a[0]＝A₁,a[1]＝A₃,a[2]＝A₄,a[3]＝A₅,a[4]＝A₆,a[5]＝A₈,共6个元素

(6)计算81/(6-1)！，商为0，余数为81，所以排列的第三个元素a[0]＝A₁

(7)去掉A₁，将a[0]后面的元素依次向前移动一位，得到一个新的数组a[0]＝A₃,a[1]＝A₄,a[2]＝A₅,a[3]＝A₆,a[4]＝A₈共5个元素

(8)计算81/(5-1)！，商为3，余数为9，所以排列的第四个元素a[3]＝A₆

(9)去掉A₆，将a[3]后面的元素依次向前移动一位，得到一个新的数组a[0]＝A₃,a[1]＝A₄,a[2]＝A₅,a[3]＝A₈共4个元素

(10)计算9/(4-1)！，商为1，余数为3，所以排列的第五个元素a[1]＝A₄

(11)去掉A₄，将a[1]后面的元素依次向前移动一位，得到一个新的数组a[0]＝A₃,a[1]＝A₅,a[2]＝A₈,共3个元素

(12)计算3/(3-1)！，商为1，余数为1，所以排列的第六个元素a[1]＝A₅

(13)去掉A₅，得到一个新的数组a[0]＝A₃,a[1]＝A₈共2个元素

(14)计算1/(2-1)！，商为1，余数为0，所以排列的第七个元素a[1]＝A₈，第八个元素为a[0]＝A₃

所以31042对应的排列顺序为(A₇，A₂，A₁，A₆，A₄，A₅，A₈，A₃)，参见图1。

3)读入待嵌入水印的数据“重庆市兴趣点”文件，并根据数据对象坐标的大小进行排序，计为V(V₁，V₂，......V₈......V_D)。

(1)根据水印信息31042计算，需要8个数据对象的空间关系才能完整描述清楚，所以取出一个水印单元S(V₁，V₂......V₈)∈V(V₁,V₂......V₈......V_D)，(V₁，V₂......V₈)与(V₁，V₂......V₈)分别对应，其存储顺序调整为(V₇，V₂，V₁，V₆，V₄，V₅，V₈，V₃)。

(2)循环步骤(1)，直至剩余数据对象不足一个水印单元止。

4)将调整存储顺序后的数据对象写入文件中。

二、水印提取过程

1)读入嵌入水印的数据“重庆市兴趣点”，记录其原始对象顺序信息V′(V₁′，V₂′，......V_M′......V_D′)，根据对象的坐标大小进行排序，V(V₁，V₂......V_M......V_D)。

2)比较V与V′两个数列，如果含有水印信息，两个数列存现明显有规律的对应关系，从而提取水印单元S，如图2。

3)以水印"重庆师范大学"为例，一个水印单元包含8个数据对象S(V₁，V₂，......V₈)，数据对象按坐标大小排列记为(A₁,A₂,A₃，A₄，A₅，A₆，A₇，A₈)，可以推出，V₁＝A₇，V₂＝A₂……V₈＝A₃,从而推出水印单元的排列为(A₇，A₂，A₁，A₆，A₄，A₅，A₈，A₃)。

4)由排列(A₇，A₂，A₁，A₆，A₄，A₅，A₈，A₃)推算其排列序号。

(1)排列逆数

排列中某元素序号后面小于他的元素序号个数称为他的逆数。A₂元素后面只有A₁的序号比他小，因此其逆数为1，同理A₄元素后面有A₃序号比他小，其逆数为1，如此类推排列(A₇，A₂，A₁，A₆，A₄，A₅，A₈，A₃)的逆数为(6,1,0,3,1,1,1,0)。

(2)排列的权序

在1，2，3，4，5，6，7，8个数字组成的全排列中，定义第n个数字的权数是(10-n)！,所以任何一个排列的权序都是(7！，6！，5！，4！，3！，1！，0！)

(3)排列的序号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＝31042

5)根据算术编码，水印信息31042恢复为0.31042。

0.31042译码过程如下：

本发明利用算术编码技术，将水印字符串转换为0至1间的小数，然后将小数去掉0.转换为整数。通过对排列顺序计数，实现整数与具体的排列顺序相对应，并将矢量空间数据对象的存储顺序与排列顺序相对应，从而实现矢量数据数字水印的嵌入与提取。