加点奇偶性空间矢量地图数据库水印算法

钱立

（四川职业技术学院计算机科学系,四川 遂宁 629000）

加点奇偶性空间矢量地图数据库水印算法

钱立

（四川职业技术学院计算机科学系,四川 遂宁 629000）

空间矢量地图数据库水印算法是空间矢量地图水印与数据库水印相结合的一类算法.大量空间矢量地图数据存放于数据库中，借助于数据库水印思想，在元组的地理属性上标记水印.本文提出的算法利用改变空间矢量数据组成点数目的奇偶性来嵌入水印信息，算法特别之处在于在进行水印嵌入与提取操作之前，利用加密算法和哈希函数生成了一个辅助数据表，用于确定水印嵌入或提取的顺序.实验结果表明本算法对地图平移、旋转、缩放操作具有较强的鲁棒性，同时也能抵抗在一定程度范围内的地图化简攻击.

矢量地图；数字水印；数据库

1 引言

数字空间矢量地图的制作常耗费大量的人力、物力、财力和时间，因而对于数字地图的生产者来说这是一大笔重要的数字财富.随着矢量地图应用的扩大，大量数字地图的数据有转向存储于数据库的趋势.目前已有多种数据库支持空间矢量数据，同时一些数据库应用需要将数据库产品出售给客户，例如地理信息系统中一般就包括价格不菲的空间数据库[1].

然而，数字矢量地图的应用面临着诸如数字版权保护、数据授权、数据源追踪等亟待解决的问题[2]，为此相关的矢量地图数字水印技术便应运而生.由于空间矢量地图与数据库结合，借助于数据库水印思想，本文提出了加点奇偶性空间矢量地图数据库水印算法.

本文的结构组织如下，第二节主要介绍加点奇偶性水印算法思想；第三节是对该算法的分析，包括几种常见水印攻击的鲁棒性分析；第四节描述该算法的实现、实验及结果；第五节给出本文的总结.

2 水印算法

2.1 概述

空间矢量地图水印技术是最近几年才逐步发展起来的.目前已有多种矢量地图算法提出，比如最低有效位水印，基于差异扩大的水印[4]，网格水印等.对于算法思想，有利用改变矢量点之间的位置关系嵌入水印，如S a k amoto[3]提出的和K ang[5]改进的算法，还有H uber[6]、K yi T ae P ar k[7]提出的插值算法；有利用变换域方式的，针对多边形，V assi l ios[8]将水印嵌入到D F T变换的幅值系数中等.

数据库水印技术就是在数据库中数据表的元组上嵌入一定意义的水印信息，而这些水印信息不能破坏原有数据的有效性和可用性.最早研究数据库水印是I B M的A lmaden研究中心R a k esh A gra w al等人[9].

空间矢量地图数据库水印算法是空间矢量地图水印与数据库水印相结合的一类算法.大量空间矢量地图数据存放于数据库中，可利用数据库处理海量信息效率的优势得到更广泛的应用，同时借助于数据库水印思想，在元组的地理属性上标记水印以保证空间矢量地图的版权.

2.2 相关知识

数字水印算法要保证嵌入的水印信息不易被察觉，不能对原有数据的有效使用造成影响，能被提取识别，同时还应具有很强的鲁棒性，即要能抵抗常见方式的水印攻击.数字水印嵌入和提取的一般过程如图1[10]所示.矢量地图水印和数据库水印原理也是如此.

空间矢量地图以层来表达，每个层描述同一类地物，比如河流.在空间数据库中存储时用不同的矢量类型来描述，P ostgis是对P ostgre S Q L数据库提供空间数据支持的一个开源模块，它提供的数据类型主要有P oint，L ine S t ring，P olygon等.P oint类型表示点，是最基本的数据类型.对于2D地图上的点有经度纬度属性，即有x，y坐标值，对于3D地图上的点则还有高度属性，即有x，y，z坐标值.2D点表示为P oint（x y）；L ine S tring类型表示线，线由多个点组成，2D线表示为L ine S t ring（x1y1,x2y2,x3y3,……,xnyn）.P olygon类型表示多边形，多边形也是由多个点组成，如果线的首尾两点相同，则表明线是闭合的，即是一个多边形，2D多边形表示为P olygon（（x1y1,x2y2,x3y3,……,x1y1））.

图1 数字水印模型

为了使数字地图重要的矢量数据能存储于数据库中，P ostgis会为存储矢量数据的字段指定某种数据类型，如L ine S tring表明存放的是G is线对象数据.其存储方式如图2，G I D表示地图元组的唯一性标识，属性值是对该元组的一些辅助描述如名称，长度或面积等，地图属性G eom就是专门存储矢量数据的.

图2 矢量数据存储方式

2.3 预处理算法

根据数据库水印思想，对数据库表中的数据嵌入水印时，需要确定对数据表的哪些元组，元组的哪些属性，属性值的哪些位作水印标记.本文讨论的空间矢量地图数据库水印只是在选定元组存放地图矢量数据属性上进行操作.地图矢量数据属性中是一系列的矢量点，而最终就是对这些点数目进行处理.本文水印算法包括三个方面：辅助数据表的预处理算法，水印嵌入算法和水印提取算法，重点是预处理过程.

预处理就是在数据表的元组中选择出适合嵌入水印的元组集合（水印域），目的不只是要指定在哪些元组上嵌入水印，还要确定嵌入水印的先后次序.预处理要用到对称加密算法和数字报文摘要算法.数字报文摘要算法实质就是某种单向H ash函数，常见的有M D5和S H A等.本文采用DE S加密和M D5哈希算法.

单向H ash函数H对一个变长的输入消息M进行操作后返回一个定长的哈希值h，表示为h=H (M)。该函数有几个特征：a)给定M，容易计算出h，b)给定h，通过H(M)=h反向运算不容易计算出M，c)给定M，找到另一个消息M’使得H(M)=H(M’)是非常困难的[7].

本文算法可应用于L ine S t ring和P olygon类型数据，介绍时以L ine S tring进行说明.针对线形L ine S t ring类型的矢量数据，依次进行如下处理：

（1）先以小于地图精度τ，例如β倍τ（β∈(0,1)）进行一次化简操作，得到这种化简程度下的G is对象关键点并做好暂存，原数据表的G is对象不变；

（2）从暂存G is对象中筛选出水印域，其中的G is对象满足条件：组成点的数目大于3，并且图形不能闭合（即I s R ing为假）；

（3）在水印域中取每一个G is对象长度描述属性L ength字段的整数部分转换为字符串S1，如果该字段的值小于1000，则乘以一个放大因子factor，使其大于1000；

（4）在水印域中取每一个G is对象数据，计算L ine S t ring类型线上首尾两点的x坐标差值的绝对值|D x|，y坐标差值的绝对值|D y|；计算第二点和倒数第二点的x坐标差值的绝对值|L x|，y坐标差值的绝对值|L y|.如果D x，D y，L x，L y小于1000，则乘以一个放大因子factor，使其大于1000；

（5）计算比例常数 R x=|D x|/|L x|，R y=|D y| /|L y|，若|L x|或|L y|为0，则对应取R x或R y等于0；

（6）将上面计算的R x，R y转换为字符串，与S1连接为新字符串S2；

（7）给定一个密钥K ey，采用DE S算法对S2进行加密运算得到S k ey；

（8）对加密后的S k ey再进行M D5运算得到S md5；

（9）将该条记录的关键字G I D与S md5填入一张新建的临时表中.同时需要删除S md5相同的记录以保证临时表中每条记录的S md5均不相同.

预处理最终建好这样一个临时辅助表，在后面的水印嵌入或提取中会使用该表.

2.4 水印嵌入提取算法

本算法的水印嵌入与提取过程均要首先进行预处理生成辅助数据表.嵌入的水印是一个16×16的黑白B M P图片，并将其转换为T X T文本形式表示，如图3左表示汉字“印”.

图3 水印图片及增加点坐标

2.4.1 嵌入

首先按照预处理算法生成辅助数据表，然后对辅助表S md5字段排序，依次判断该G is对象组成点的数目n的奇偶性：

（1）如果要嵌入0，则n必须为偶数.若n已为偶数，则不作任何处理；若n为奇数，则需在原G is对象除去首尾和次首尾四个关键点的其余任何两关键点之间添加一个新的不同点，使n变为偶数.需要注意的是添加的新点将导致该G is对象的形状改变，但只要这个改变量在地图精度τ允许范围内，则仍然是有效地图.如图示的A、B点之间可选择添加一个误差t在βτ＜t＜τ（β∈(0,1)）之间的点N，新增点坐标（图3右）采用如下方式计算：

图中线段A B是L ine S t ring类型G is对象上某一段，需在A B之间添加一个误差为t的新点N.M为线段A B的中点，N M垂直A B于点M.

a)计算点M坐标：X m=(X a+X b)/2,Y m=(Y a+Y b) /2；

b)求出角度α：α=atan((Y b-Y a)/(X b-X a))，若X a=X b，则α=90°；

c)计算新加点N坐标：X n=X m+t*sinα,Y n=Y m +t*cosα.

（2）如果要嵌入1，则n必须为奇数.若n已为奇数，则不作任何处理；若n为偶数，则同上方式在原G is对象上添加一个新的不同点，使n变为奇数.

2.4.2 盲检测提取

（1）先以β倍地图精度τ进行一次化简，并暂存G is对象关键点；然后生成辅助表，与水印嵌入时构造方式一样.

（2）对辅助表S md5字段排序，依次判断该G is对象组成点数目n的奇偶性：若n为偶数，则嵌入的水印为0；若n为奇数，则嵌入的水印为1.

3 水印算法分析

3.1 水印嵌入提取分析

水印嵌入之前需先给定密钥，选择合适的水印域，构造辅助表.选择的G is对象组成点的数目要大于某个值并且不能闭合（针对L ine S t ring类型）.如果能满足这个条件的记录数目过少则不能完整嵌入水印.提取水印时也需先给定密钥，以此重新生成辅助表，并利用辅助表能准确确定哪些元组嵌入了水印，也能确定水印嵌入的次序，从而能提取出完全正确的水印.

水印可以是黑白B M P图片或字符串。如果嵌入的水印是16×16黑白B M P图片，则至少需要256条符合以上条件的记录才能完整嵌入.如果嵌入的水印是字符，每个汉字字符需要16位表示，则对应需要16条记录.嵌入图片优点是如果遭到元组删除或添加攻击时，在一定范围内提取出的水印仍能辨别，缺点是水印信息量较大.嵌入字符串的优点是嵌入信息量较小，但其致命缺点是一旦提取出的前16中某位由于遭受元组删除或添加攻击产生水印错位时，提取的水印就完全错误.

3.2 水印抗几何攻击和抗重排分析

空间矢量地图数据库水印的攻击有地图操作带来的几何攻击，如平移、旋转、缩放等，有对矢量数据对象重排和顶点重排的攻击，有对数据库元组增删的攻击，还有对元组矢量数据顶点的增删改的攻击等.

本算法采用增加点使组成G is对象点的数目呈现奇偶性，以此来判断嵌入的水印是0或1.一般的地图操作，如平移、旋转和缩放都不会影响到组成G is对象点的数目变化.能否准确提取水印关键在于确定水印提取的次序.

本算法的核心是构造了一个用于嵌入和提取水印的辅助表，该表进行了DE S加密和M D5哈希处理，这样只有拥有密码的主人才能提取正确水印.该辅助表的主要目的就是确定唯一的水印嵌入或提取次序.而这个次序由几个相对不变量决定，针对L ine S t ring数据类型，一个不变量是G is对象长度描述L ength，一个不变量是首尾两点x坐标差值与次首尾两点x坐标差值的比值R x，另一个不变量是首尾两点y坐标差值与次首尾两点y坐标差值的比值R y.比值R x，R y之所以不会随着地图平移、旋转和缩放而变化，是因为每个G is对象自身相似相关性不变.也就是说不管矢量地图是平移旋转，还是放大缩小，每个G is对象的各个组成边在对象内所占的比例是恒定的.正如一幅直立人像照片，照片放大后人像的头部占身长的长度比例是一个值R，如果缩小照片，人像的头部占身长的比例仍然是R，保持不变.所以对这三个相对不变量经过DE S加密和M D5处理后，选取出的元组及其排列次序也不会改变，即是说提取水印时生成的辅助表与嵌入时生成的辅助表是一致的，因此能准确提取出水印.

一幅空间矢量地图存储于数据库中表现为一个数据表，地图中的每一个对象都由数据表的一个元组表示，元组的排列有一定的次序.元组重排（也称为对象重排）攻击指的是重新排列元组的次序来达到对水印破坏的目的.每一个元组的矢量数据是由一系列有次序的点组成的，如果对这些点逆向排列，结果表示出的地图对象在呈现上不会有所变化，采用这种方式的攻击为顶点重排攻击.

由于本算法选取的三个相对不变量与数据库元组的排序无关，也与元组矢量数据中顶点的排序无关，故能经受元组重排和顶点重排方式攻击.

3.3 抗一定程度化简攻击分析

空间数据库对空间矢量数据的化简操作可利用P ostgis模块的simply()函数实现不同程度的化简，该函数使用D ouglas-P eu k er算法进行化简运算.为了能使算法对一定程度的化简操作具有较好的鲁棒性，本算法先进行以小于地图精度的某个值（βτ）进行化简操作，然后才按照G is对象组成点数目的奇偶性嵌入水印。需要添加的新不同点误差t在βτ＜t＜τ（β∈(0,1)）范围内，所以只要地图以小于βτ值进行化简操作后，仍可提取到正确的水印.

4 水印算法验证

4.1 算法实现

该水印算法实验实现环境：在W indo w s平台下，采用开源数据库P ostgre S Q L，并配合对空间矢量数据支持的P ostgis模块来存储空间矢量数据，使用开源Q uantum G I S来展示地图.该算法使用J a v a语言和P ostgis支持J a v a的J D BC技术编程实现.

4.2 实验及结果

实验的水印是图3左黑白B M P图片.实验地图有北美加拿大全境的河流、公路、铁路地图和多幅天津海事地图.

（1）水印嵌入提取实验

图4 水印嵌入提取及地图平移、旋转攻击测试

嵌入提取实验是指在嵌入水印后，删除辅助表；在提取水印时重新生成辅助表来提取.这个实验过程不对嵌入水印后的地图进行任何攻击.实验的结果是提取出的水印与嵌入的水印完全一致，见图4左边上下两图.

（2）地图平移旋转攻击实验

图4右上是地图在x，y方向分别平移了80000和40000米，图4右下是在平面上旋转了23°.根据前面抗平移旋转的几何分析可判断实验结果正确.

（3）地图缩放化简攻击实验

图5 地图缩放、化简、元组删除攻击测试

图5a)是地图嵌入水印后在x，y方向上分别缩小至原来的0.6倍和0.8倍的不等比例缩放攻击.图5b)是地图嵌入水印后以500m（小于地图精度）参数进行化简的攻击.

4.3 非盲检提取水印

根据前面的分析及实验，提出的算法可盲检提取水印.该算法对于非恶意数字地图操作攻击具有很强的鲁棒性.但是对于数据库元组增删攻击，提取出的水印信息很可能增加某些无效位或缺失某些水印位，从而导致提取的水印不可识别.为了抵抗这种攻击，可同时作两方面改进.一方面提取水印时采取非盲检技术，在嵌入水印后，要保存辅助数据表的M D5序列.非盲检提取水印时，使用该M D5序列依次对比提取，若缺位则默认水印为1.另一方面为了减小删除嵌有水印的G is对象的机会，需减少水印信息量.为了使水印数据量较小但含义丰富，水印可采用字符串表达.一个汉字可用16位二进制数表达，若水印为4个汉字，则需要64位二进制位表达.这比起一个16×16的黑白图片所需的256位减少很多，而水印信息含量却增加了3倍.同时为了提高水印提取的精确度，可奇数倍数重复嵌入字符串，比如3或5次.在非盲检水印提取时根据投票多数决定原则判断提取水印.

图5c)是地图嵌入水印后，随机删除10%的元组攻击，颜色较浅的线是已删除的元组，此处作对比线.经过非盲检提取水印表明小部分水印受到破坏，但仍能识别.

5 总结

本文提出了一种新的空间矢量地图数据库水印算法，该算法的主要思想是利用改变空间矢量数据组成点数目的奇偶性来嵌入水印，同时使用加密算法和哈希函数来生成辅助表，利用该表确定水印嵌入或提取的顺序.

本算法当需增加点改变矢量数据组成点数目的奇偶性时，在一定的地图精度范围内添加一个不同点，虽然给地图的形状带来改变，但不影响其使用精度.综合分析和多组实验攻击测试表明，本算法对矢量地图常见的几何攻击、对象重排攻击、顶点重排攻击和抵抗一定程度上的化简攻击具有较强的鲁棒性.为了抵抗数据库元组增删攻击，可采用嵌入字符串水印和非盲检水印检测来提高抗攻击性.

[1]N iu X ia M u,S hao C heng Y ong,W ang X iao T ong.:G I S W ater mar k ing:H iding D ata in 2D V ector M aps[J].S tudies in C omputational I ntel ligence(SC I),2007,58：123-155.

[2]朱勤，于守健，乐嘉锦.数据库水印研究与进展[J].计算机工程与应用，2006，（29）：198-201.

[3]S a k amoto,M.,M atsuura,Y.,T a k ashima,Y.(2000):A schema of digital w atermar k ing for geographical map data[J].S ymposium on cryptography and I nformation security.

[4]W ang X iaotong,S hao C hengyong,X u X iaogang,et al. R e v ersible D ata-H iding S cheme for 2-D V ector M aps B ased on D if ference E x pansion.I EEE T ransactions on I nformation F orensicsand S ecurity,2007,2(3).

[5]K ang,H.(2001):A v ector w atermar k ing using the gen erali z ed square mas k[J].P roc.I nterna tional S ympo sium on I nformation T echnology:C oding and C omput ing：234-236.

[6]H uber,B.:G is&steganography– part 3:V ector steganography.A v ailable:ht tp://www.directionsmag. com/

[7]K yi?T ae?P ar k,K ab?I l?K im,Hw an?I l?K ang,et al.? D igital G eographical M ap W atermar k ing U sing P oly l ine I nterpolation[A],A d v ances in M ul timedia I n formation P rocessing-P C M2002[C],S pringer B er l in, 2002：225-243.

[8]S olachidis V assi l ios,N i k olaidis N ii k os,P itas ban nis:W atermar k ing polygonal l ines fourier descrip tiors[A].I n:P rocessings of I EEE I ntermational C on ference on A coustics,S peechand S ignal P rocessing(I C A SS P’2000)[C],I stanbul,T ur k ey,2000,5:1955-19 58.

[9]R a k esh A gra w al,J er ry K iernan.W atermar k ing R ela tional D atabase[A].P roceeding of th 28th V L D B C on ference[C],H ong K ong,C hina2002.

[10]冯雪，朱新山，汤帜.多媒体数字水印技术研究进展[J].计算机工程与应用，2007，(13)：1-6+10.

SpatialVectorMap DatabaseWatermarking A lgorithm ofAdding Point and Judging Parity

QI A N L i
(S ichuan V ocational and T echnical C ol lege,D epar tment of C omputer S cience, S uining S ichuan 629000)

S patial v ector map database w atermar k ing algorithm is designed by integrating spatial v ector map w atermar k ing and database technologies.A large number of spatial v ector maps are stored in database,of w hich copyrights are protected by w atermar k ing the at t ributes v alues of geographic ob j ects in databases.I n this paper,w e propose an algorithm w hich uti l i z es odd and e v en features of spatial points to embed and detect w atermar k s.T his algorithm employs encryption and a H A S H function to produce an au x i l iary table for ensuring the only order of embedding or detecting w atermar k s.E xperiment resul ts sho w that our algorithm has a good robustness against v ector map t ranslation,rotation,z oom,and simpl i f ication tosomedegreeas w el l.

V ector M ap;D igital W atermar k ing;D atabase

TP391

A

1672-2094(2013)01-0146-06

责任编辑：张隆辉

2012-12-07

四川职业技术学院自然科学项目：基于空间矢量数据库的数字水印技术研究(2009Z04).

钱 立（1978-），男，四川大英人，四川职业技术学院计算机科学系讲师，硕士.研究方向：J a v a，数据库，数字水印技术.