基于结构特征的矢量地图数字水印算法研究

孙建国¹，门朝光¹，曹刘娟¹，李成名²

(1. 哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨，150001；

2. 中国测绘科学研究院，北京，100080)

摘  要：提出一种基于地图图层结构特征的数字水印算法。根据矢量地图所含结点、线路和区域3种图层的拓扑特点，定义不同的度量规则并引入模糊聚类分析方法，对矢量地图进行综合优化，获得地图内可供水印嵌入的矢量目标集合；同时，选用比特位复合的方式，将水印信息嵌入地图属性文件描述目标对象的坐标块中。研究结果表明：采用该算法达到了地图精度的零损伤要求；在不同矢量数据压缩比率下，该算法比其他方法的误码率低10%~20%；在抗几何攻击方面，该算法与同领域水印算法相比，所产生的平均误码率可降低50%。

关键词：矢量地图；数字水印；结构特征；拓扑

中图分类号：TP390.1          文献标志码：A         文章编号：1672-7207(2010)04-1467-06

Digital watermarking of vector maps based on structure features

SUN Jian-guo¹, MEN Chao-guang¹, CAO Liu-juan¹, LI Cheng-ming²

(1. School of Computer Science and Technology, Harbin Engineering University, Harbin 150001, China;

2. Chinese Academy of Surveying and Mapping, Beijing 100080, China)

Abstract: A watermarking algorithm based on the characteristics of the structure of map layers was proposed. According to the topological characteristics of three basic layers such as nodes, segment, region in a vector map, with fuzzy clustering analysis methods, an optimized embedded target set was achieved by different appraisement rules. Using the bit-compound, watermark was embedded into the corresponding coordinate blocks of vector objects in an attribute file. The results show that the requirement of lossless accuracy can be achieved; false negative rates (FNR) can be reduced by 10%-20% at different compression ratios and compared with other algorithms mentioned, the average FNR will be reduced by 50%.

Key words: vector map; digital watermarking; structure feature; topology

伴随世界军事经济发展，地理信息系统和智能运输系统的广泛应用，矢量地图逐步成为重点研究的数字化产品。矢量地图数字水印技术有效解决了日益严峻的数字地图非法侵权以及恶意篡改等违法犯罪问题。目前，矢量地图数字水印技术研究主要集中于空域和频域(变换域)2类。空域水印对矢量地图的数据精度损失较大，虽不断引入改进策略^[1]，但其鲁棒性能和抗数据压缩能力具有明显的局限性；频域方法以离散傅里叶变换(DFT)^[2]、离散余弦变化(DCT)^[3]、离散小波变换(DWT)^[4]3种方法为主，均属研究热点；但频域水印对矢量地图精度存在一定损伤，对此，马桃林等^[5]提出通过坐标漂移方式嵌入水印的方法。该方法大大降低了地图的精度损失，但由于策略的局限性，算法综合性能较差，特别是抗数据压缩攻击能力没有获得明显提升。概括地说，主要原因在于缺乏一种优化选择策略指导嵌入对象的选取，使得携带水印的对象在压缩过程中被去除，从而引起水印失效。在此，本文作者提出一种基于矢量地图拓扑结构特征的数字水印算法。矢量地图结构特征主要包括矢量对象的图层、坐标等属性信息及对象间拓扑关系^[6]。利用聚类分析方法对隶属于不同基础图层的目标群采取不同的评价策略，最终获得一个综合优化后的水印嵌入目标群；同时，将水印信息嵌入地图的属性文件，利用目标对象坐标值0 bit扩展的方式达到精度无损的要求，同时，提高了水印抗矢量数据压缩的能力，水印的实用性得到提升。

1  嵌入目标群的优化选取策略

1.1  矢量地图的空间演化特性

矢量地图具有明显的空间演化特性。水印嵌入群的形成过程对应矢量空间的简化过程，即演化的逆过程。下述定义均以矢量地图作为特定基础。

定义1(离散度量空间)：设集合X为矢量地图中N个独立的矢量对象，度量，表示任意2个矢量对象的相关度。

定义2(拓扑空间)：由度量空间性质，对于包含若干矢量对象的集合A_i是(X, ρ)上的开集(A_iX)，若存

在集族，则称(X, I)为拓扑空间，表示任意对

象集合间的相关性。

定义3(矢量空间)：在拓扑空间(X, I)中，对于元素A_i，若对于任意对象，图层E上都有唯一的E(a)对应，则称为矢量空间，其中：  {0, 1}，E只包括基本图层，即点、线和区域图层。

对于矢量空间，由于复合各种图形和图像形式的渲染效果，其最终表现为可应用的矢量地图，至此，完成了地图的生成过程。地图解析则是该过程的逆序，输出为水印嵌入对象目标群。

         定义4(目标群)：在地图解析过程中，由经过选择用来嵌入水印编码的对象所组成的集合称为目标群，或嵌入目标群T。称所有备选对象组成的集合为候选目标群C_T，C_T。

1.2  候选目标群的生成

生成候选目标群C_T步骤如下。

(1) 移除渲染图层。对于矢量空间(其中，；E₃表示地图的3种基本图层；为渲染层)，总体分为14类地图元素^[7]。移除，即，转化为最简空间。

(2) 依据对象x所在图层结构特征，评价其是否为水印嵌入目标。定义A_i为地图点集，B_i为线集，C_i

为区域集，则拓扑空间中，{，，}，矢量对象x空间坐标形式为I₀=(x, y)。对于

任意对象(x_i, y_i)∈A_i，当且仅当＞0时，；道路B_i = ，(x₁, y₁)为道路的起点，(x_i, y_i)为道路终点；C_i= 为闭合道路，简称闭路。

据此，矢量地图可表示为3个独立子空间：离散对象子空间(X_A, I_A)、道路子空间(X_B, I_B)以及闭路子空间(X_C, I_C)，且满足：

    (1)

         (2)

(3) 对于各子空间，按照具体规则，提取特征对象后剔除拓扑I_A，I_B和I_C，形成离散对象集合。

规则1(离散对象子空间(X_A, I_A))：任意的开     集，存在实数＞0，使得对象I_i∈A, I_m∈A，0＜≤成立，此时，称(x_i, y_i)为I_A的特征点，记作集合K(I_i)，每一个开集都存在至少1个关键点。

规则2(道路子空间(X_B, I_B))：任意的开集，存在关系R，结点I_i, I_j, I_k∈B，满足I_iRI_j，I_jRI_k成立，称I_j为R的中继，I_i为R的起始，I_k为R的终端，记作K(I_i, I_j)。

规则3(对于闭路子空间(X_C, I_C))，任意的开集，对于关系，若存在子集S₁={I_i, I_j, …, b_k}∈C，则满足, …, 成立；若存在子集S₂={I_i, I_j, …, b_k}∈C，则满足，…, 成立。以此递推，则I_C的特征点记作K(I_ij)= {}。

由规则1~3，矢量地图的候选目标群为K(X)={K(I_i), I(I_i, I_j), K(I_ij), I_i, I_j, I_ij∈X}，K(X)是由I′引导的。去除I′，得离散度量空间：

     (3)

式中：为E₃的逆运算。

1.3  目标群选取

利用图层的拓扑结构特征^[8]，确定候选目标群K(X)。采用基于距离的模糊聚类分析方法能够完成最终目标群K_C(X)的选取，K_C(X)K(X)。

定义5 (属性熵值)： 在(X, ρ)中，为了表示从属于不同属性图的对象在水印嵌入中的优先选择权，将其定义为属性熵，记作A_x。

定义6 (隶属度)：由矢量对象η∈K(X)可得：

    (4)

式中：f(x, η)表示矢量对象x隶属以η为中心的集簇的概率，A_x为对象的属性熵值；x=[x_i, x_j]^T。存在水印嵌入目标群：

。

模糊聚类分析方法的思路是：

(1) 根据水印容量N，确定K_C(X)的规模为N′，且K_C(X)K(X)；

(2) 对于(X, ρ)，调整阈值δ (式(3))，使得。其中：n＞N′；X_i的中心为η_i；

(3) 对于K(X)，由隶属度定义，重新生成以η_i为中心的集簇；

(4) 对于每个集簇，选取N′/i个f(x)值较大的对象，生成目标群T=K_C(X)。

2  基于结构特征的水印算法

2.1  水印标志嵌入

基于以上方法所确定的目标对象在携带水印后都能够保证被去除的概率较小。为了保证地图精度无损失，将水印信息嵌入到目标对象的属性文件内，采取坐标比特位微调的方式实现。主要过程为：

(1) 读取属性文件中描述目标的对象定义块。以矢量地图开发软件MAPX^[9]应用为例，如表1所示，地图的属性信息主要存储在MAP文件中，该文件由512或1 024字节的数据块组成，描述了矢量空间中对象的名称、位置、索引以及整个系统的结构等信息，每个数据块的第1个字节称为块标记。对象定义块使用16位整数和32位整数定义了地图空间中所有的矢量对象。在坐标块中，复杂对象由1个子对象描述和实际坐标组成，单一对象仅由坐标组成。

表1  MAPX属性文件标记

Table 1  Definition of attributes file for MAPX

 (2) 根据对象定义块搜索坐标，获得对象坐标值。

(3) 对坐标值采用比特微调方式嵌入水印。由步骤1知，每个坐标块中都存在大量保留字节，因此，可以对目标对象的坐标进行字节复合操作。定义“?”为字节连接标志，则对于水印串W，，s.t. (x_i, y_i)=(x_i?0₁…0_m, y_i?0₁…0_n)，且0＜m≤2, 0＜n≤4，

其中：，n表示与W_k的比特值(0或1)

相同的连续字节数。当W中存在1个比特值相同的序列W=W_kW_k+1…W_k+q, q＞4时，为防止嵌入过程的数据溢出，则需将该序列划分成若干元素个数不超过4的子序列嵌入坐标块中。图1所示描述了利用4个目标对象嵌入1个8 bit水印编码的过程。

图1  坐标微调操作流程

Fig.1  Flowchart of coordinate micro-tuning

通常，作为辅助水印检测的向量I=[ I_i, I_j, I_k, I_m]^T被保存下来，向量I保存了携带水印的目标对象的必要属性信息，包括矢量对象名称、对象坐标块及具体操作。

2.2  水印标志检测

由于水印载体是属性文件，因此，水印标识检测实质是对属性文件内容的一次选择性遍历。

通常，检测到的水印标志W_t由于载体受到攻击，会造成部分信息丢失，造成W_t与原水印W不一致，对此，提出一种水印相似度检测方式：

       (5)

          (6)

其中：n为水印容量。

3  实验与分析

3.1  精度损失实验

采用基于MAPX插件的VC.NET矢量地图程序测试算法对地图精度的影响。

李媛媛等^[4]提出DWT算法，选择矢量地图图像的蓝色通道嵌入水印，在嵌入水印时，根据小波系数的重要性分别采用不同的嵌入强度来嵌入水印。马桃林等^[5]提出坐标漂移算法，基于特定二维矢量地图DXF文件，利用Z维坐标无效的特点，进行坐标漂移来嵌入水印信息。Deng等^[10]提出一种基于双重网格的数字水印空域算法，该算法通过双重网格划分，将水印信息分散隐藏到节点坐标的最低有效位上。钟尚平^[11]提出DFT算法，对MQUAD算法进行修正和扩展，通过离散傅里叶变换，把水印信息嵌入在变换后的中频系数中。闵连权等^[12]提出DCT算法，提取地图数据的特征点组成特征图像，对特征图像作离散余弦变换，把水印信息嵌入在中低频系数上。表2所示为本算法与空域^[10]，DFT^[11]，DWT^[4]和DCT^[12]算法以及坐标漂移算法^[5]的精度损失比较结果。

实验结果表明：水印信息嵌入属性文件且采取坐标值复合有限个0 bit的方式能够最终实现精度无损。

3.2  抗压缩攻击实验

矢量地图数据压缩的任务在于使用尽可能少的抽样对象来描述整个矢量空间，并保证在误差范围内再现地图的属性特征。在矢量数据压缩的过程中，所有矢量对象都存在被去除的情况，一旦携带水印信息的对象被剔除，则很容易导致水印失效或水印信息提取失败。

李青元等^[13]提出了一种利用4种途径相结合的压缩算法。该压缩法压缩率可达80%以上。为了测试算法在抗压缩攻击方面的性能，选取2种典型的矢量压缩算法^[14](即对地图坐标数据类型进行转换和对矢量地图上弧线进行“滤点压缩”)用于测试。

表3所示为2种压缩攻击下各算法的误码率(即错误字节/水印总字节)比较。从表3可见：空域算法误码率较大；坐标漂移算法与本文算法类似，也利用文件作为嵌入载体，但嵌入对象选取采取随机策略，使得目标对象在压缩过程中易被去除。

3.3  鲁棒性实验

实验主要选取了剪切攻击及扭曲变形等几何攻击，测试结果如表4所示。从表4可见：本文作者提出的算法的各项指标都优于其他算法。坐标漂移算法由于采用属性文件为水印载体，所以，对于变形扭曲攻击方式的误码率同样为0；但由于嵌入对象的选取没有具体的优化指导策略，在应对几何攻击时，误码率偏大。本文作者提出的算法由于采用了嵌入目标群优化选取策略，所以，携带水印的矢量对象具有较低的被去除概率。

表2  嵌入水印前后算法精度比较

Table 2  Precision comparison after watermark being embedded

表3  压缩算法下各算法误码率对比

Table 3  Comparison of false negative rate between watermarking algorithms

表4  几何攻击下本文算法与同类算法的比较

Table 4  Comparison of false negative rate between the same algorithm for attacks

4  结论

(1) 提出了矢量地图的空间演化特性，通过空间模型简化，可获得任意矢量地图的最简拓扑特征图层，即点、线和区域图层，并对各图层相应地定义了其特征点的选取规则。

(2) 所提出的基于结构特征的矢量地图数字水印算法通过模糊聚类分析方法，选取较优的矢量对象作为水印嵌入目标，并结合目标对象的坐标属性信息，通过比特位扩展方式嵌入水印信息，达到了对地图的图形图像及精度零损伤的要求。

(3) 该算法应对几何攻击及复杂矢量压缩攻击方面的能力较强，使水印检测的误码率较低。

参考文献：

[1] Dhbuchi R, Veda H, Endoh S. Robust watermarking of rector digital maps[C]//Proceedings of IEEE International Conference on Multimedia and Expo. Lausanne: IEEE, 2002: 577-580.

[2] Solachidis V, Nikolaidis N, Pitas I. Fourier descriptors watermarking of vector graphics images[C]//Proceedings of the International Conference of Image Processing. Vancouver: IEEE Computer Society Press, 2000: 9-12.

[3] Nikolaidis N, Solachidis V. Fourier descriptors watermarking of vector graphics images[C]//Proceedings of the International Conference of Image Processing. Vancouver: IEEE Computer Society Press, 2000: 10-13.

[4] 李媛媛, 许录平. 矢量图形中基于小波变换的盲水印算法[J]. 光子学报, 2004, 33(1): 97-100.
LI Yuan-yuan, XU Lu-ping. Vector graphical objects watermarking scheme in wavelet domain[J]. Acta Photonica Sinica, 2004, 33(1): 97-100.

[5] 马桃林, 顾种, 张良培. 基于二维矢量数字地图的水印算法研究[J]. 武汉大学学报: 信息科学版, 2006, 31(9): 792-794.
MA Tao-lin, GU Zhong, ZHANG Liang-pei. Watermarking algorithm on 2D vector digital maps[J]. Geomatics and Information Science of Wuhan University, 2006, 31(9): 792-794.

[6] XU De-he, ZHU Chang-qing, WANG Qi-sheng. A survey of the research on digital watermark for the vector digital map[J]. Geomantic World, 2007, 12(6): 42-48.

[7] 倪金生, 王永明, 钱晓明. 地图矢量化技术实践教程[M]. 北京: 电子工业出版社, 2008: 20-24, 35.
NI Jin-sheng, WANG Yong-ming, QIAN Xiao-ming. Vector map technology practice course[M]. Beijing: Electronics Industry Press, 2008: 20-24, 35.

[8] Voigt M, Yang B, Busch C. Reversible watermarking of 2D-vector data[C]//Proceedings of the 2004 Multimedia and Security Workshop on Multimedia and Security. New York: IEEE, 2004: 160-165.

[9] 齐锐, 屈韶琳. 用 MapX开发地理信息系统[M]. 北京: 清华大学出版社, 2003: 5-13.
QI Rui, QU Shao-lin. Development of geographic information system with MapX[M]. Beijing: Tsinghua University Press, 2003: 5-13.

[10] DENG Shu-jun, LU Liang, CHE Sen. Research on a digital watermarking algorithm suitable to vector map[C]//Proceedings of the IEEE International Conference on Automation and Logistics. Qingdao: IEEE Computer Society Press, 2007: 1236-1240.

[11] 钟尚平. 双重嵌入MQUAD水印算法分析与改进[J]. 计算机研究与发展, 2005, 42(S1): 142-149.
ZHONG Shang-ping. Analysis and improvement of double embedded MQUAD watermarking algorithm[J]. Journal of Computer Research and Development, 2005, 42(S1): 142-149.

[12] 闵连权, 喻其宏. 基于离散余弦变换的数字地图水印算法[J]. 计算机应用与软件, 2007, 24(1): 146-174.
MIN Lian-quan, YU Qi-hong. A digital map watermarking algorithm based on discrete cosine transform[J]. Computer Applications and Software, 2007, 24(1): 146-174.

[13] 李青元, 刘晓东, 曹代勇. Web GIS矢量空间数据压缩方法探讨[J]. 中国图形图像学报, 2001, 6(12): 1225-1229.
LI Qing-yuan, LIU Xiao-dong, CAO Dai-yong. Discussion of vector data compression for Web GIS[J]. Chinese Journal of Image and Graphics, 2001, 6(12): 1225-1229.

[14] 李琦, 杨超伟, 陈爱军. WebGIS中的地理关系数据库模型研究[J]. 中国图像图形学报, 2000, 5(2): 119-123.
LI Qi, YANG Chao-wei, CHEN Ai-jun. Research of geographic database model[J]. Chinese Journal of Image and Graphics, 2000, 5(2): 119-123.

收稿日期：2009-07-20；修回日期：2009-10-15

基金项目：中央高校基础研究基金资助项目(HEUCF061006)

通信作者：孙建国(1981-)，男，黑龙江巴彦人，博士研究生，讲师，从事信息隐藏、数字水印研究；电话：0451-82518010；E-mail: sunjianguo@hrbeu.edu.cn

(编辑 刘华森)