汪传建,程莉,赵庆展,张丽,郭理

(1石河子大学信息科学与技术学院,石河子832003;2石河子大学经贸学院,石河子832003)

一种基于DCT的地理数据版权保护方法

汪传建1,程莉2,赵庆展1,张丽1,郭理1

(1石河子大学信息科学与技术学院,石河子832003;2石河子大学经贸学院,石河子832003)

为了保护地理数据的版权,根据地理数据所具有的特性,提出了一种基于DCT(discrete cosine transform)的地理数据水印算法。该算法对地理数据进行网格化操作以构造空域,实施DCT变换,轻微修改DCT系数,然后实施逆DCT变换,得到修改后的空域,通过调整地理数据中点的分布情况嵌入水印信息。实验结果表明:本算法能抵抗平移、缩放、旋转和化简攻击。

地理数据;水印;网格化;DCT变换

Abstract:To protect the copyright of geographical data,a geographical data watermarking algorithm is proposed in this paper considering the characteristics of geographical data.We compute minimum bounding rectangle of the geographical data,divide the geographical data into grids on the boundary of the minimum bounding rectangle,count the number of vertices in all cells and derive a grid weigh array.Discrete cosine transform is applied to the grid weigh array.Watermarks are hidden in the DCT coefficients by modifying the signs of DCT coefficients with middle frequencies.Inverse discrete cosine transform is applied to the modified DCT coefficients and modified grid weigh array is derived.The vertices are redistributed according to the modified grid weigh array.Experiments show that the algorithm is robust against translation,scaling,rotation and simplification attack.

Key words:geographical data;watermarking;discrete cosine transform

随着3S(RS、GIS、GPS)技术的广泛应用,地理数据的基础性作用日益凸显,地理数据的需求量越来越大;但是地理数据的采集和生产离不开专业的技术人才,需耗费大量的物力和财力。而且地理数据的拷贝非常容易,加上目前缺乏保护地理数据版权的有效措施,一旦地理数据被出售,非法拷贝就难以避免,这损害了数据生产者的利益[1]。近年来,国内外学者将数字水印技术应用于地理数据,提出了一些地理数据水印方法。根据水印特征域的不同,地理数据水印技术可分为空域水印模式、变换域水印模式。地理数据中的地物对象是由有组织的顶点集合构成的,地理数据实际上是基于某一地理坐标系统的顶点坐标序列。基于空域的地理数据水印方法是在精度范围内移动顶点或直接修改顶点的坐标值来嵌入水印信息[2-6]。基于变换域的地理数据水印模式的主要思路是:合理选择某种空域载体数据,对载体实施频域变换,然后通过修改频域系数来实现水印的嵌入。典型的变换域包括DFT域[7-8]、DWT域[9-10]和DCT域[11]。该算法具有抗几何攻击、顶点重排等攻击。但由于变换域的构造是基于数据顶点坐标,因此该法难以有效抵抗化简攻击。

本文根据地理数据所具有的特性,提出了一种新的基于DCT的地理数据水印算法。对地理数据进行网格化操作以构造空域,实施DCT变换,轻微修改DCT系数,然后实施逆DCT变换,得到修改后的空域,通过调整地理数据中点的分布情况嵌入水印信息。

1 水印嵌入

水印信息嵌入过程的基本流程如图1所示。

图1 水印嵌入过程Fig.1 Watermark embedding process

1.1 水印生成

本算法采用带有版权信息的黑白二值图像作为原始水印信息。为了增强水印的安全性,首先对原始水印图片进行置乱操作,然后读取置乱后图像的数据部分作为要嵌入的水印bit串。本文采用基于Arnold变换[12]的置乱方法对水印信息进行置乱。本文水印图像大小为32×32,进行 K次置乱操作后得到置乱后的水印图像W,W即为后面要嵌入的水印信息。置乱次数 K作为密钥的进行保存,水印检测时用于恢复出原来的水印图像。水印图像的置乱周期 T为24。

1.2 网格化

在对地理数据进行“网格化”处理之前,本文先用道格拉斯-普克算法对地理数据进行化简,将坐标点划分为关键点和非关键点。

为了对地理数据进行网格化处理,首先计算地理数据的最小绑定矩形,然后以最小绑定矩形为边界,把整个地图划分为大小相等的矩形组成的二维网格,将数据点分配到各个网格单元中。统计每个网格单元中非关键点的数目,得到一个网格权值矩阵G。本文在构造网格权值矩阵时需过滤关键点,而对非关键点只进行统计处理。过滤关键点是为了保证地图嵌入水印之后不会出现严重的变形。同时,确定二维网格时,为了保证水印的嵌入对地图影响最小,将网格单元大小取值为地理数据精度的一半以下。网格大小作为密钥保存,在水印提取过程中也需要使用该密钥对水印化数据进行网格化。

1.3 嵌入水印

对上述网格权值矩阵 G实施DCT变换,得到DCT频域系数矩阵。DCT系数分为低频分量、中频分量和高频分量。本算法选择DCT系数的中频分量嵌入水印信息。

本文通过修改AC系数正负值的方式达到嵌入水印的目的。具体修改过程如下:

在增加(Add)点的子函数中,从参数所指定的网格中任意选择1个点,如果其后面1个或前1个点也在这个网格内时,就在这2个点的连线中取个位置插入1个点(比如连线中点位置);在减少(Remove)点的子函数中,从该网格中任意选择1个非关键点,直接删除即可,因为在进行网格化之前已经对地图进行了关键点的过滤,地图的关键点没有统计在网格单元内,直接删除网格单元中的非关键点不会对地图的使用性造成严重影响。

经过水印预处理(置乱)→网格化→修改网格统计特性(包括DCT变换、修改频域系数嵌入水印、逆DCT变换)→调整网格中顶点的分布4个步骤,完成水印的嵌入,得到的是1个嵌入了给定水印图片的地理数据。

2 水印提取的过程

提取水印的过程需要提供嵌入水印时所使用的密钥 K(置乱次数)、网格单元的大小作为提取水印的参数。

2.1 网格化

根据地图边界以及给出的网格单元大小,采用与嵌入水印过程中相同的方法对地理数据进行网格化,并以相同的原则统计每个网格中点的数目(之前也要将关键点过滤掉),得到网格权值矩阵 Gd。

2.2 DCT变换以及提取水印

对网格权值矩阵 Gd做DCT变换,得到对应的频域系数矩阵Gd-AC,选择位于正中间的 N×N个频域系数DACi(1≤i≤N×N),根据正负判别的准则得到一个 N×N的比特串WSi(1≤i≤N×N),将其作为数据域部分写入1个黑白二值图像Wd。正负判别的流程如下:

图2 未嵌入水印时的地图Fig.2 The original geographical data

2.3 输出原始水印图像

根据Arnold变换的原理,假设一 N×N图像的变换周期为 T,对于一张已经置乱过 K(密钥之一)次的图像,只需在置乱 T-(KmodT)次就可以恢复。因此,对于上一步得到的黑白二值图像Wd,依据嵌入水印时作为密钥的置乱次数 K,再对Wd进行 T-(KmodT)次置乱就可以得到检测出的水印图像W0-d。

3 仿真实验与分析

使用 PostgreSQL+Post GIS作为地图数据服务器,MapServer作为地图显示服务器,测试数据为MapServer提供的演示数据,该地图为加拿大全境地图,在这里只采用其中的公路(road)图层作为测试数据集。数据集存储在数据库中共计有1548条元组,43489个坐标点。数据的地理范围为(-2200000,-712704)至 (3072832,3840000),将其分为256×256的网格,网格单元大小约为20000×15000。采用32×32的黑白二值图像(Arnold变换周期 T=24)作为原始水印图像。原始地理数据如图2所示,加水印后的地理数据如图3所示。

图3 嵌入水印后的地图Fig.3 The watermarked geographical data

将2幅地图进行叠加并局部放大对比显示的效果如图4所示,虚线椭圆中标识出的部分即为水印前后地图变形情况。

以原始水印图像和提取出来的水印图像的峰值信噪比(PS N R)及相关系数(N C)评价水印检测的结果,PS N R是一种评价图像的客观标准。对水印图像进行各种恶意攻击后,通过比较 N C系数的值,可以得到数字水印算法抗恶意攻击的能力,由 N C系数值的变化给出一个比较客观的评价准则。

对比提取的水印与原始水印,当 N C系数低于0.5时,基本可以认为水印信息被破坏了。因为对于任意一幅水印图像来说(白底黑字)表示版权信息的黑字一般会占到整幅图像的1/2左右。

图4 叠加并局部放大对比效果Fig.4 Overlaping and scaling locally the original and watermarked geographical data

对于平移、旋转、缩放、化简、重新排序等几何攻击(表1),本算法均能较有效地对抗。

文献[11]也是一种基于DCT域的地理水印方法,该方法能抵抗几何攻击,但不能抵抗化简攻击,主要原因是该方法中的DCT变换域是基于数据顶点坐标构造的,而化简操作会删除一些隐藏水印信息的顶点,从而破坏水印信息。本文DCT域的构造并非直接基于顶点坐标,而是基于网格中的顶点分布,并通过修改网格中顶点的分布来隐藏水印信息。虽然化简攻击可删除一些顶点,但是化简攻击对网格中的顶点分布影响较小,因此,本方法具有一定的抗化简攻击能力。

表1 本算法抵抗各种攻击的效果Tab.1 The robustness of the proposed algorithm

4 结语

本文结合图像置乱技术、离散余弦变换、人类视觉系统等思想,提出了一种基于网格化的地理数据水印算法。算法选择了检测结果直观、有特殊意义的二值图像作为原始水印,并在嵌入之前进行预处理。为了兼顾水印的不可见性和鲁棒性,选择在中频系数部分嵌入水印。最后用量化标准对算法进行了检测。通过仿真试验,证明了本算法对常见的非几何攻击和绝大多数几何攻击均具有较好的抗攻击性,但本算法的抗化简攻击能力有待改善。

[1]Niu X M,Shao C Y,Wang X T.GIS watermarking:hiding data in 2D vector maps,studies in computational intelligence[M].Berlin:Springer-Verlag,2007.

[2]李嫒媛,许录平.用于矢量地理空间数据版权保护的数字水印[J].西安电子科技大学学报:自然科学版,2004,31(5):719-723.

[3]贾培宏,马劲松,史照良,等.GIS空间数据水印信息隐藏与加密技术方法研究[J].武汉大学学报:信息科学版,2004,29(8):747-751.

[4]王勋,林海,鲍虎军.一种鲁棒的矢量地理空间数据数字水印算法[J].计算机辅助设计与图形学学报,2004,16(10):1377-1381.

[5]Wang C J,Peng Z Y,Peng Y W,et al.Watermarking 2D Vector Maps on Spatial Topology Domain[A].Shiguo Lian.MINES2009[C].Wuhan:IEEE Computer Society Press,2009:71-74.

[6]朱长青,杨成松,李中原.一种抗数据压缩的矢量地理空间数据数字水印算法[J].测绘科学技术学报,2006,23(4):281-283.

[7]Solachidis V,Pitas I.Watermarking polygonal lines using fourier descriptors[J].IEEE Computer Graphics and Applications,2004,24(3):44-51.

[8]Doncel V R,Nikolandis 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(TVCG),2007,13(5),851-863.

[9]李媛嫒,许录平.矢量图形中基于小波变换的盲水印算法[J].光子学报,2004,33(1):97-100.

[10]杨成松,朱长青.基于小波变换的矢量地理空间数据数字水印算法[J].测绘科学技术学报,2007,24(1):37-39.

[11]Voigt M,Busch C.Reversible watermarking of 2D-vector data[A].YANG B,MM&Sec 2004[C].Magdeburg:ACM,2004:160-165.

[12]丁玮,闫伟齐,齐东旭.基于Arnold变换的数字图像置乱技术[J].计算机辅助设计与图形学学报,2001,13(4):338-341.

A Geographical Data Copyright Protection Algorithm Based on Discrete Cosine Transform

WANG Chuanjian1,CHENG Li2,ZHAO Qingzhan1,ZHANG Li1,GUO Li1
(1 College of Information Science and Technology,Shihezi University,Shihezi 832003,China;2 College of Economics and Trade,Shihezi University,Shihezi 832003,China)

TP391

A

1007-7383(2010)04-0510-04

2010-01-01

国家科技支撑计划项目(2007BAH12B01、2007BAH12B07)

汪传建(1977-),男,讲师,从事数据库、地理数据库水印方面研究;e-mail:wcj㊦inf@shzu.edu.cn。