摘要:为了解决空间信息网络传输和空间信息共享的版权保护问题，本文提出了一种具有鲁棒性的2D矢量图形的水印算法。在GIS中，矢量图形是其最基本的表达方式，常需针对2D矢量图形的大数据集进行水印嵌入处理,本方法先将空间矢量图层按照自身所含的多边形特征进行分解；对分解后的矢量多边形进行分析，选择合适的多边形的线段，在其顶点处嵌入水印；而提取水印的过程，则是对原矢量图形和水印图形进行分析，根据嵌入水印顶点的位置或坐标值得到水印信息的序列。实验证明，该方法对于空间信息的常规图形操作，如：矢量图层的坐标变换、平移、旋转、缩放，以及图形的剪切，点的添加删除等，均具有较强的鲁棒性。
   关键词: 数字水印；矢量图形
   1.引言
   随着多媒体技术和网络技术的迅速发展，对广泛应用于GIS中的空间信息数据的版权保护成为一个迫切需要解决的问题。
   从空间信息模型两分法的理论出发，空间数据主要可分为栅格数据和矢量图形数据。与栅格数据相比，矢量数据有以下两个优点：⑴ 数据量小、精度较高；⑵可以任意地放大缩小而不失真。矢量图形数据以其明显的优势被视为网络空
间信息发布，或网络GIS的重要数据格式，而对矢量图形数据的知识产权保护则显得尤其重要。
   近几年，数字水印技术作为一种在开放的网络环境中保护数字产品版权的新技术，逐步得到发展。但是，数字水印技术大部分都集中在数字图像和视频方面。近年来，逐渐推出现一些有关的对于图形数据数字水印方法研究的文章。例如：文献[1]针对多边形数据，使用一维离散傅立叶变换(DFT)，将水印嵌入到DFT变换的幅值系数中，其结果会引起矢量图形的轻微失真；文献[2]和文献[3]提出了基于小波变换的水印方法，其中：文献[2]通过离散小波变换将顶点序列分解成不同空间和频率上的复值系数，并根据水印的大小与小波系数之间的关系把水印嵌入到小波系数的幅值中；文献[3]提出了基于复数小波域的2维矢量图形的水印算法，利用Dual Tree复数小波变换的优点，将水印嵌入相对坐标线的复数小波中。，这两种方法都具有良好的不可见性和对通常的图形几何变换具有较强的鲁棒性，但是都没有充分考虑对图形剪切的鲁棒性；文献[4]提出了在矢量图形的线段中插入点、改变线段的长度、方向和属性等方法来作为水印信息，其要插入点的位置和改变线段长度的位置太很单一，使之因此并不具有较很强的鲁棒性，而改变线段的方向和属性的方法并不适合于精确的矢量数据；文献[5]、[6]、[7]都是利用坐标值的容差(Tolerance)嵌入水印，其中：文献[5]采用由-tolerance和+tolerance的值组成的PN-sequence(pseudo-noise sequence)作为水印信息，将其嵌入到2D矢量图形的坐标数据中，通过PN-sequence和添加水印数据的关系来发现水印；文献[6]把矢量图形分为网格，将图形分为几个子区域，通过在容差(Tolerance)范围内移动坐标点来添加水印；文献[7]提出一种基于四叉树划分矢量地图的空域水印方法，根据顶点的密度将图形划分为不同大小的矩形框，在矩形内通过移动坐标点来嵌入水印信息，这三种方法都对在容差范围域内改变坐标值的攻击具有很好的鲁棒性，而但这三种水印方法均改变了原始图形的坐标值。
   本文在文献[4]和文献[6] 的基础上，提出了一种新的鲁棒性矢量图形水印算法，即：借鉴矢量图形分区的理念，但按照图层自身包含的多边形进行子区域分解，再将每一个多边形分解为多条边或多条曲线，选取合适的边或曲线，并在其顶点的容差范围内嵌入水印信息，实现矢量图层的数字水印算法。
   2.水印算法
   2.1 图形的分割
   空间数据的每个矢量图层均可被称之为大数据集，若要对其进行高效率的水印处理，则需对矢量图形进行分割处理。文献[6]、[7]分别利用网格和矩形框进行分割，可能造成一个多边形的水印和相邻的多边形有联系，如果攻击者只剪切其中某一个多边形区域的信息，便有可能造成水印的丢失。此外，在矢量图层中多边形的公共边问题是嵌入水印的一个重要障碍，它可能造成由于水印的重复嵌入，而导致水印提取的失败。因此，本文在讨论水印算法之前，先提出将矢量图层按照自身的内部多边形进行分割和基于多边形的最小边界矩形框(MBR, Minimum Boundary Rectangle)处理公共边的方法，从而提高水印的鲁棒性。
   首先，将矢量图层按照本身所包含的多边形分割成为若干个多边形区域，如果某一个多边形所包含的点数目少于要嵌入水印的长度n，就将此多边形合并到点数目最少的相邻多边形中。这样，原矢量图层就被分割为若干包含一个或者多个多边形的子区域；然后，求出每一个子区域的MBR，根据在MBR中包含的相邻多边形，获得这些多边形的公共边集合。图1虚线矩形框为多边形A的MBR，根据包含的多边形，获得多边形A的公共边a1、a2、a3、a4、a5的 信息。

图1  图形分割

   2.2  水印的嵌入
   第一个嵌入水印信息的子区域将会决定其它区域添加水印的情况，故选择整个矢量图层的质心所在的子区域作为第一个嵌入水印的区域。
   为了提高嵌入水印和提取水印的效率，只对每一个子区域中一条边嵌入水印信息即可，它其满足：
⑴ 未添加水印的边，即相邻的多边形没有对其嵌入水印信息；
⑵ 含有点的数目大于水印长度n。如果子区域所有边中点的数目少于n，逆时针或者顺时针合并相邻的边，直到满足点大于等于n时为止；
⑶ 满足以上两个条件的边集合中，选取离子 满足以上两个条件的边集合中，选取离子区域质心最远点所在的边。
   假设满足上述三个条件的边有u个顶点，用m=（m1，m2...mn）表示坐标值。用 w=（w1，w2...wn）表示n位水印的信息，其中w属于｛-1，1｝，取值由用户自定义的密钥key产生。用b=（b1，b2...bn）表示u个顶点的水印序列值，因为u>n，故要重复嵌入水印c=【u/n】次，且满足bi=wj其中，本文将在顶点的容差范围内，嵌入一个新的坐标点作为水印。这样可以防止由图形坐标精度取舍的原因而造成图形的失真。用m=（m1，m2...mn）表示增加点的坐标值，与原图形顶点m关系如下

   其中，a是坐标容差范围的绝对值。当bi=-1时，在mi的(-Tolerance,0)范围内，在的-a 处嵌入点mi；当bi=1时，在mi的(0,Tolerance) 的a处嵌入点 。
    经过以上操作，就可对含有u个点的多边形的线段，在容差范围内嵌入u个新的点作为该图形的水印信息。
   2.3 水印的提取
   水印的提取就是检验图层是否含有嵌入的水印信息，从而证明对图层是否拥有版权。
   为了能够成功从检验图层中提取出水印，需要进行与原始图层间几何配准。首先，对检验图层进行同样的分割，利用嵌入水印取边的过程获取添加水印的边；然后利用原始图层和检测图层中的边起始点、终点及质心集合作为几何配准的控制点，则可利用公式(1)进行几何校正：

   其中，｛x1，y1｝和｛x，y｝分别表示水印图层和原始图层中的坐标值，｛aij｝是图层的缩放、旋转和平移的参数。使用文献[7]的IAM（Iterative Alignment- Minimization）算法，进行精细地几何校正，从而可检测原始图层与矢量图层点之间一一对应关系，以便检查出删除或者添加的坐标点。
   随后，就可提取水印信息。首先，根据原始图层所确定地添加水印的序列｛wi｝；然后，对检测图层进行分析，获取添加水印的边，利用公式

   求出水印图层中的水印信息｛wi｝；最后，通过相似度来检测原始水印和提取水印的相似性： ，其 (3)
如果相似度大于某一阈值T，则认为提取的水印正确，否则水印不存在。T取得经验值0.75。
   3  水印鲁棒性的讨论
   水印必须具有一定的鲁棒性，才会真正起到保护数据版权和来源认证的作用。因此，需要讨论本文提出的水印算法是否在经过常用的图层几何变换，如：平移、旋转、剪切、缩放、添加和删除坐标点等操作后仍具有很好的鲁棒性。
   3.1 平移、旋转、缩放
   将图层的分别沿x轴和y轴移动tx和ty 的距离可以利用上面公式(1)解决平移问题，即

   (3) 2D图层的旋转是指将p点绕坐标原点转动某个角度阿尔法到新的点P。同样可以利用公式(1)解决旋转问题，得到：

   图层的缩放是对p点相对于原点沿x轴缩放Sx，沿y轴缩放 ，也可利用上面公式(1)解决缩放问题：  

   由此，。可以证明基于公式(1)的平移、旋转和缩放等几何变换，均不会对水印图层造成影响。
   3.2 坐标点的添加删除点
   如前所述，首先获取原始图层要嵌入水印部分的坐标值m=（m1，m2...mn）和检验图层水印部分的坐标值p=（p1，p2...pn）（其中由于攻击者可能添加或者删除坐标点，因此k可能大于也可能小于2u），然后使用文献[7]的IAM算法可以检测处于原始图层与检测图层之间各点一一对应关系，从而检测出删除或添加的坐标点。
   根据水印添加的方法过程， 在检测未经破坏的水印图层中，所添加水印的线段上每一个节点处容差范围内应该有另外一个点(即作为嵌入水印信息的点)，因此在检测图层中，如果存在与原始图层中的点m (i ∈[1,u])相对应的点p ( j ∈ [1, k])，它的情况有两种：
   ⑴ Pj的容差如果有多个点的，选择恰在 处上存在一点，例如存在的点为的点P1，消除其它的点则使m2i=pj，m2i+1=p1；
   ⑵ Pj的容差的阿尔法处没有点存在如果没有此点，即此水印信息可能被破坏，则使在此点添加一个重叠的点如果在检测图层 的坐标值中没有点与 相对应的情况，则使m2i=pj，m2i+1=p1 。
   最终可以根据m=（m1，m2...mn）和p=（p1，p2...pn）获得有包含水印信息的2u个坐标值的 ，然后按照检测的方法进行处理根据公式(2)求出水印图层中的水印信息｛wi｝,最后根据公式(3)求出相似度。因此，适当的点的添加与删除并不影响水印信息的提取。
   3.3 图形的剪切
   如果攻击者只需要图层某一部分的图形数据，而不是整个图层的数据，就会对图层进行剪切操作。由于本文的方法是对每一个图层内部的每一个多边形嵌入水印信息，则无论剪裁图层的任何部位可很好的保护每一个多边形数据，只要剪切图层含中含有至少一个多边形，均可很好地被检测出水印信息。此外，如果矢量图层中包含某一条很长的河流或者很大的区域，即一个多边形含有很多的节点时，则可以将此线段或多边形再次进行分割，分割成一些相对比较小的区域或较短的线段，对每一个分小区或分段域嵌入水印信息后，再将它们这些区域合并在一起组成原线段或多边形。
   4 实验结果分析
   SVG作为新一代网络矢量数据发布的标准，正在被广泛应用于GIS应用系统中。然而，由于SVG是以开放源的数据文档呈现在网络环境中，必然涉及到数据安全和数据版权的问题。 因此，本研究以一SVG矢量图形为例，进行算法的实验研究，以证明其实用性和有效性。
   4.1 实验步骤
   实验数据选择广东省县市级行政边界的SVG矢量图层做实验，具体试验步骤如下：
   ⑴ 将原矢量图层(如图2左图)按照本文2.1中图层分割的方法进行分割，原始图层含有132185节点，共121个多边形。合并节点的数目少于水印长度n的多边形，而得到99个子区域。
   (2) 在每一个区域中选取满足条件的边界线段，按照本文2.2中水印嵌入的方法对其嵌入水印，嵌入水印后的矢量图形如图2右图。

图2  原始图形与嵌入水印后的图形

   ⑶ 对添加水印后的图形进行一系列的攻击，按照本文2.3中水印提取的方法检验水印的鲁棒性。
   在水印嵌入过程中，需要注意：嵌入水印的长度n，如果嵌入的水印信息太短或很少不利于提取，但若太长，水印的鲁棒性就会变差；同时，水印太长，会有很多线段所含的节点数目少于n，需进行大量的合并操作，从而降低添加水印和检测水印的效率。水印的长度n可根据图层的情况而定，此次实验中选取n=64，即：64位用户定义的key生成的随机的由{-1,1}组成的序列。
   4.2 鲁棒性验证
   验证是对实验数据中的子区域进行分析，图3为图2右图矢量图层中的一个子区域，(a)为含有1552个点未嵌入水印的原始图形，分割为6条边界线段，满足选择边的三个条件后，选择了一条有224个节点的边来嵌入水印；(b)为嵌入水印后的图形，图形上的虚线矩形框是添加水印信息的区域，右边大的矩形框是嵌入水印区域放大后的部分区域：其中A、B、C为原始图形的点，a、b、c为添加的点，经过水印处理后此多边形图形有1776个点，其中224个为水印信息；(c)为水印图形平移后的图形；(d)为水印图形旋转45度角后的图形；(e) 为水印图形缩小1/2后的图形。

    针对上述实验结果，表1给出了在三种情况下按照提取水印的方法所得到的相似度，阈值取0.75，由表中的数据可以看出，本算法对水印图形平移、旋转和转移具有很好的鲁棒性：

表1    鲁棒性测试结果(阈值取 0.75)

表2    添加删除点鲁棒性测试结果(阈值取 0.75)

   同时，表2还对嵌入水印图形分别进行了添加和删除5个和30个点的鲁棒性检测结果。由于添加删除节点位置和数目不同，提取水印的相似度和效率则会有很大差异。如果添加的点恰在 处，水印提取相似度和效率的效率就会随着添加点的增多而越低降低，但可成功提取水印信息；如果是在非水印区域，就可用文献[7]的IAM算法删除这些多余的点，可以成功提取水印信息。如果删除的点在水印区域，水印提取的成功率会随着删除点的增多而降低。
   对矢量图层剪切的方式有很多种，实验只选取其中一部分，图4是对图2(b)的两种剪切的方式，经实试验证明只要剪切后的图层包含一个完整的多边形或线段图形，就可以成功的提取水印信息。

   5.结论
   本文尝试了一种新的矢量图层数字水印算法。该算法将矢量图层按照自身的多边形分割为子区域，对每个子区域中某一条边顶点的容差范围内嵌入新的点作为水印信息。实验证明，此算法对图形的几何变换、点的添加、删除和剪切都具有较好的鲁棒性，可以很好的起到矢量图形数据的版权保护作用。然而，本文算法是非盲水印算法，如何实现矢量图形的频域中嵌入水印的算法和盲水印算法将是今后工作的重点。

   参考文献
[1] Solachidis Vassilios, Nikolaidis Niikos, Pitas Ioannis Watermarking polygonal lines fourier descriptiors[A]. In: Processings of IEEE Intemational Conference on Acoustics, Speech and Signal Processing( ICASSP’2000)[C], Istanbul, Turkey, 2000,5: 1955~1958
[2] Li Yuanyuan, Xu Luping  Vector Graphical Objects Watermarking Scheme in Wavelet Domain. ACTA Photonica Sinica,2004,1(33).[李媛媛,许录平.矢量图形中基于小波变换的盲水印算法,2004,1(33)]
[3] Zhang Qin, Xiang Hui, Meng Xiangxu  Watermarking vector graphics based on complex wavelet transform. Journal of Image and Graphics,2005,4(10)[张琴,向辉,梦祥旭.基于复数域的图形水印方法.中国图象图形学报,2005,4(10)]
[4] Sonnet Henry, Isenberg Tobias, Dittmann Jana, et al  Illustration watermarks for vector graphic[J]. In: Proceeding of 11th Pacicif Conference on Computer Graphics and Applications (PG2003)[C], Canmore, Canada, 2003:73~82[5] Michael Voigt, Christoph Busch Watermarking 2D-Vector Data for Geographical Information System. In Proc.IS&T/SPIE Electronic Imaging 2002,4675:621~628
[6] Michael Voigt, Christoph Busch.Feature-based Watermarking of 2D-vector data[A]. In: Processing of SPIE, Santa Clara, 2003,5020:359~366
[7] Ryutarou Ohbuchi, Hiroo Uedda, Shuh Endoh  Robust watermarking of vector digital maps. In: Processing of IEEE International Conference on Multimedia and Expo 2002 (ICME 2002), Lausanne, Switzerland, 2002,8
[8] Hongmei Gou, Min Wu Fingerprinting Curves. In: Lecture Notes in Computer Science,2005,3304.