一种基于MapReduce的电子地图数字水印处理方法
2016-11-08方晓乐王倩雪陈鑫祥吴永静
方晓乐 王倩雪 陈鑫祥 吴永静
1(广东省国土资源技术中心数据管理室 广东 广州 510075)2(广东工业大学自动化学院 广东 广州 510075)
一种基于MapReduce的电子地图数字水印处理方法
方晓乐1王倩雪2陈鑫祥1吴永静1
1(广东省国土资源技术中心数据管理室广东 广州 510075)2(广东工业大学自动化学院广东 广州 510075)
电子地图在互联网上发布后，可以通过数字水印技术来保护其所有者的版权。为了提高数字水印算法嵌入的执行效率，提出一种并行的电子地图数字水印嵌入法。该方法基于并优化了MapReduce编程模型，再结合一种具有高鲁棒性、基于离散余弦变换(DCT)的数字水印法，对海量的电子地图瓦片进行并行的水印加载。最后在测试实验中表明，该方法较传统模式，提升了工作效率。
电子地图MapReduceDCT数字水印并行处理云计算海量
0 引 言
在地理信息系统(GIS)应用中，随着模拟地图向数字地图的转变，电子地图已是不可或缺的表现形式之一[1]。电子地图采用了通用的数字图片格式，在互联网中为使用者们提供地理信息服务。由于其存在形式具有无限次的复制性，并且复制处理手段相对非常简单和低廉，再加上网络传播的便捷性，电子地图极易被非法仿制、处理和传播。因此，数字水印技术被广泛地应用到保护电子地图所有者版权中[2-4]。
数字水印技术被大量使用在解决数字作品版权保护上，包括了图像、视频、文本和音频等。数字水印技术将一些标识信息(即数字水印)直接嵌入数字载体当中(包括多媒体、文档、软件等)或是间接表示(修改特定区域的结构)，且不影响原载体的使用价值，也不容易被探知和再次修改。而通过这些隐藏在载体中的信息，可以达到防伪溯源、版权保护的目的[5]。
当前，大部分的数字水印算法都是串行单机对图片进行水印嵌入的[6-9]。当面对海量图片(比如电子地图瓦片)处理的时候，传统的单机处理方式往往会显得力不从心。云计算并行处理是提升海量工作效率的最热门方法之一，对此有许多的研究[8-12]。其中文献[11]提出一种基于MapReduce的方法，从而提高了在地理信息数据地物中加入水印的效率。本文针对海量电子地图瓦片这种情况，结合之前的一些研究工作[6]，提出一种新的数字水印处理方法：利用并优化MapReduce并行计算架构，结合DCT变换数字水印算法，通过若干台PC终端，把水印并行嵌入到海量的电子地图瓦片中。
1 电子地图与数字水印算法
1.1电子地图瓦片
随着WebGIS和计算机等技术的发展，电子地图网站(比如国外的Google、Bing，国内的百度、天地图等)都是采用电子地图瓦片的模式来提供地图服务[13]。在这样的模式下，所有浏览中调用到的地图都是由若干瓦片组合而成的，不同地图比例尺的瓦片集会预先生成并存放在地图服务器中。而瓦片往往采用压缩强度大、容量小的格式，从而使其能够满足在互联网上被使用者流畅地浏览[14]。本文中所用的电子地图瓦片源自“天地图·广东”[14],每张瓦片(如图1所示)有以下特点：(1) 分辨率较小：256×256的像素级别；(2) 为了减小其容量，采用了高强度的切割压缩法[15]，格式为JPEG；(3) “天地图·广东”要提供全广东省各比例尺级别的地图服务，因此有海量的瓦片；(4) 瓦片色彩较一般的图片比较单调，嵌入水印鲁棒性难以保证。
图1 “天地图·广东”地图影像瓦片样图
1.2DCT数字水印算法
互联网时代，数字水印作为保护数字作品版权的最主要方式之一，已经有许多研究者们提出了不同的算法[2,4,16,17]，主要有两种方式：(1) 在图片的像素空间不重要位LSB嵌入水印信息；(2) 先进行转域的变换(DCT、傅里叶等)，再在其不易被人眼觉察的位置嵌入水印信息。综合了各方面因素情况下，文献[6]提出了一种具有强鲁棒性且适用于电子地图瓦片的数字水印算法，其嵌入处理的步骤如下：
第一步导出数字水印的像素(像素为0和1的双值格式)，并把像素值的次序通过随机数置乱；
第二步导出电子地图瓦片的“YUV”(其中“Y”表示明亮度，也就是灰阶值；而“U”和“V” 表示的则是色度，作用是描述影像色彩及饱和度，用于指定像素的颜色)中的“Y”值(每个值范围0～255)；
第三步把导出的“Y”值数列拆分成若干个不重叠的8×8分辨率小分块，每块都进行DCT变换，转换成频率域，DCT变换的公式如下：
(1)
其中：
(2)
完成DCT变换后，每一个分块再通过量化矩阵M(如图2量化矩阵所示，矩阵数值和一个压缩质量指数QF相关，QF越大则图片压缩度越高)进行量化处理；
1611101624405161121214192658605514131624405769561417222951878062182237566810910377243555648110411392486478871031211201017292959811210010399
图2量化矩阵图
第四步把置乱顺序的水印像素嵌入到每个“Y” DCT变换分块的低频部分(人类肉眼一般对低频部分不敏感，隐藏在低频部分不易被察觉)，设定一个C表示DCT系数，m表示量化矩阵中的对应值，sign表示C的符号(正或负)，C*表示嵌入后的新系数，那么当嵌入像素的值为0的时候：
(3)
当嵌入像素的值为1时：
(4)
第五步设置一个加权值，改善嵌入水印后地图瓦片的可视效果。设D为同一位置嵌入数字水印后和嵌入前“Y”量的差值，则加权值可以设为：
D=Y-Y*Y**=Y*+f×D
(5)
通过以上五步，可以实现数字水印在电子地图瓦片上的嵌入。在文献[6]中，还详细描述了数字水印的析出方法，可以脱离原图，单单通过带水印瓦片成功析出所嵌入的数字水印。本文主要描述瓦片水印的并行快速嵌入方式，析出方法则不予讲解。
2 数字水印嵌入并行处理方法
使用DCT数字水印算法可以实现数字水印在电子地图瓦片的嵌入，然而在面对海量瓦片需要处理的时候，传统方式下依靠单机单线的处理方式会导致效率极其低下。而云计算这个新概念的出现，为海量电子地图瓦片数字水印算法处理提供了新的解决方案和思路。云计算是一种新的分布式计算架构，一方面它可以利用所有闲置资源参与运算；另一方面它可以满足GIS高容量和高效访问量计算量的需求[18]。其中基于开源架构Hadoop分布式文件系统的MapReduce编程模式是其最为热门的解决方案之一[11,12]。它通过映射的方式(“Map”)将数据的处理任务并行地分配在集群的计算机节点上，再将并发处理的结果归约(“Reduce”)已完成计算，非常适合海量数据的分析计算处理。
2.1Hadoop分布式文件系统
Hadoop分布式文件系统HDFS(Hadoop Distribute File System)是一个被设计成适合运行在通用硬件上的分布式文件系统。HDFS系统具备高度容错性、适合部署在廉价的机器上、高吞吐量、非常适合大规模数据集应用等特点。HDFS放宽了一部分POSIX约束，来实现流式读取文件系统数据的目的。HDFS在最开始是作为Apache Nutch搜索引擎项目的基础架构而开发的[19,20]。
HDFS的结构是主从式的，其中主节点(又称为名字节点)是一个用于管理文件命名空间和调节客户端访问文件的主服务器；而从节点(又称为数据节点)则是若干个机器(通常一个节点对应一个机器，可以是PC、服务器，甚至是虚拟机)，它们用来管理对应节点的存储。
在HDFS中创建数据的时候，会建立一个或多个与数据相对应的块文件(block)。为了数据的安全性，这些文件一般会被设置成复制出若干个冗余备份保存在随机不同的数据节点上。这样的方式不仅保证安全，而且可以实现MapReduce程序读取数据时可以从多个服务器中获取，从而改善服务的伸缩性。如在GIS中的瓦片数据可以通过建立快速索引以存储路径统一管理的形式存放到HDFS中，使用属性查询代替空间查询，可以避免复杂的空间计算，节省浏览地图时的多读取时间，实现地图瓦片读取时的多点响应[12]。而这种所谓的“write-one-read-many”方式在写文件的时候，则会效率有些慢，而这也是在HDFS上使用MapReduce算法执行并行电子地图瓦片嵌入处理时需要解决的难点。
2.2MapReduce算法的优化
MapReduce工作一般流程可如图3所示，所有输入源数据会被编排成一个个键值对
图3 一般情况下MapReduce的工作流程图
针对电子地图瓦片数字水印的嵌入工作，MapReduce需要在以下几个方面进行相应的优化(如图4所示)：首先在默认的MapReduce编程模型中，键值对的Key是指文件中的行，而Value是指对应行的文本内容。这样的设定并不适合数字水印嵌入工作的并行处理，需要做相应程序源码上的修改，即Key表示每张图的路径文件名，Value表示对应图的内容。其次在Reduce的环节，Map的输出还要重新被调度给从节点进行Reduce任务，这对于并行处理数字水印嵌入工作显得不必要。可以去除Reduce的环节，直接由本地转存HDFS，这样会提高效率，节省资源，具体修改后的流程可如图4所示。综上，在程序代码方面(Java)：
1) 首先需要新增一个类(如命名ImageWritable)，使用源码中WritableComparable类的接口，用于描述和构建Value(图片的内容)；
2) 其次需要新增一个类(如命名ImageRecordReader)，继承源码中RecordReader类，用于描述Key(Text类型，表示文件路径)和Value(ImageWriatble类型，表示文件的图片内容)的读取关系；
3) 再者需要新增一个类(如命名ImageInputFormat)，继承源码中FileInputFormat类，用于读电子地图瓦片文件；
4) 最后设置Reduce程序为无效。
图4 电子地图瓦片数字水印嵌入的工作流程图
3 测 试
3.1测试数据
“天地图·广东”每年更新一次电子地图，会涉及约2.1×107张、JPEG格式、超过250 GB的电子地图瓦片，包括了矢量和影像数据。本文的电子地图数字水印嵌入实验中，使用了“天地图·广东”中约20 GB、2×106张的电子地图瓦片样本。
3.2测试环境
测试用了8台PC，配置可见表1所示。其中1台PC为主节点，7台PC为从节点，通过千兆网络组成集群。每台PC都安装了CentOS 6.5 Linux操作系统，使用Hadoop版本2.2，以及带Java环境版本1.7。
表1 Hadoop集群的硬件配置
3.3测试流程
测试主要验证大量电子地图瓦片在新的并行数字水印嵌入方法下，效率能够得到明显的改善。步骤如下：(1) 使用单台PC，使用传统Java方式下[6]的数字水印嵌入程序，对2×103张、2×104张、2×105张、2×106张电子地图瓦片分别执行并记录时间；(2) 使用Hadoop集群，使用本文优化后MapReduce的数字水印并行嵌入处理程序，对2×103张、2×104张、2×105张、2×106张与步骤(1)相同的电子地图瓦片分别执行并记录时间。
3.4测试结果与分析
测试实验结果如表2所示，由表中的数据可以看出，随着参与的电子地图瓦片数量增大，并行数字水印嵌入处理方法的优势就越为凸显。在2×106张瓦片的处理结果中，单PC需要超过12小时的时间来完成处理，而集群PC并行处理方法下，不到1小时已经可以完成。可见，在新的电子地图数字水印并行处理方法下，效率较传统方式有显著提升。
表2 测试实验结果
4 结 语
针对在传统串行方式下处理海量电子地图瓦片水印的速率比较缓慢，本文提出了一种并行处理的数字水印嵌入方法。该方法在MapReduce编程模型下，为了适应电子地图的分布式存放，舍弃了Reduce端，节省了重新洗牌分配组合的时间；同时重新定义了合适的键值对，把数字水印嵌入工作放在Map环节，实现并行的处理。通过对“天地图·广东”电子地图瓦片样本数据的测试对比试验，验证了该方法在海量地图瓦片数字水印嵌入处理的高效性。
[1] 刘斌,刘正军,王亮,等.省级应急平台体系基础地理信息平台的设计研究[J].测绘科学,2008,33(S1):84-87.
[2] 王小虎,邵楷,吴爱华.一种地图水印的嵌入方法[J].长春大学学报,2010,20(2):45-47.
[3] 张佐理.一种抗压缩的矢量地图水印算法[J].计算机工程,2010,36(20):137-139.
[4] 闵连权,喻其宏.基于离散余弦变换的数字地图水印算法[J].计算机应用与软件,2007,24(1):146-148,174.
[5] Cox I,Miller M,Bloom J,et al.Digital Watermarking and Steganography[M].San Francisco:Morgan Kaufmann Publishers,2007.
[6] 方晓乐,吴永静,李志中,等.一种基于DCT变换的数字水印算法在“天地图·广东”中的应用[J]. 地理信息世界,2014,21(3):100-104.
[7] HwaiTsu Hu,LingYuan Hsu.Robust, Transparent and High-capacity Audio Watermarking in DCT Domain[J].Signal Processing,2014,109:226-235.
[8] 李锐,王斌.文本处理中的MapReduce技术[J].中文信息学报,2012,26(4):9-20.
[9] Hassan M A H,Bamha M,Loulergue F.Handling Data-skew Effects in Join Operations Using MapReduce[J].Procedia Computer Science,2014,29:145-158.
[10] Zhuhong You,Jianzhong Yu,Lin Zhu,et al.A MapReduce based parallel SVM for large-scale predicting protein-protein interactions[J].Neurocomputing,2014,145:37-43.
[11] 彭煜玮,岳名亮,汪传建.基于MapReduce的高效地理数据水印方法[J].华中科技大学学报:自然科学版,2012(S1):179-182.
[12] 林碧英,王艳萍.基于Hadoop的电力地理信息系统数据管理[J].计算机应用,2014,34(10):2806-2811.
[13] 邱儒琼,王波.基于预生成技术的WebGIS数据处理系统设计与实现[J].测绘科学,2008,33(S1):138-139.
[14] 苏旭明,谭建成.WebGIS中瓦片地图关键技术研究[J].北京测绘,2012(2):9-11.
[15] 陈鑫祥,吴锦超.利用ArcGIS Engine实现天地图瓦片数据的切割[J].北京测绘,2013(4):17-20.
[16] Bahi J M,Fang X L,Guyeux C,et al.Suitability of chaotic iterations schemes using XORshift for security applications[J].Journal of Network and Computer Applications,2014,37:282-292.
[17] Mohanty S P,R Kumara C,Nayak S.FPGA Based Implementation of an Invisible-Robust Image Watermarking Encoder[C]//Lecture Notes in Computer Science (LNCS),2004,3356:344-353.
[18] 方晓乐,吴永静,万宝林,等.基于云平台的“天地图·广东”测试[J].地理空间信息,2014,12(5):152-153.
[19] 王宏宇.Hadoop平台在云计算中的应用[J].软件,2011,32(4):36-38,50.
[20] 徐焕良,翟璐,薛卫,等.Hadoop平台中MapReduce调度算法研究[J].计算机应用与软件,2015,32(5):1-6,16.
AN ELECTRONIC MAP WATERMARKING PROCESSING METHOD BASED ON MAPREDUCE
Fang Xiaole1Wang Qianxue2Chen Xinxiang1Wu Yongjing1
1(LandandResourcesTechnologyCenterofGuangdongProvince,Guangzhou510075,Guangdong,China)2(CollegeofAutomation,GuangdongUniversityofTechnology,Guangzhou510075,Guangdong,China)
The copyrights of the owners who releasing electronic maps on the Internet can be protected through digital watermarking technologies. In this paper we propose a parallel digital watermarking embedding method for electronic maps aimed at improving the execution efficiency of digital watermarking algorithm embedding. This method is based on MapReduce programming model and it optimises the model, and then combines a DCT-based digital watermarking algorithm with high robustness to carry out parallel watermarking load on massive electronic maps tiles. At last, it is shown in test experiment that the proposed method improves working efficiency than the traditional mode.
Electronic mapMapReduceDCTWatermarkingParallel processingCloud computingMass
2015-06-10。广东省国土资源厅科研专项项目(GDGT KJ2014006)。方晓乐，工程师，主研领域：计算机通信，GIS。王倩雪，讲师。陈鑫祥，高工。吴永静，教授级高工。
TP3
A
10.3969/j.issn.1000-386x.2016.10.047
