一種基于MapReduce的電子地圖數(shù)字水印處理方法

方曉樂　王倩雪　陳鑫祥　吳永靜

1(廣東省國土資源技術(shù)中心數(shù)據(jù)管理室　廣東 廣州 510075)2(廣東工業(yè)大學(xué)自動化學(xué)院　廣東 廣州 510075)

?

一種基于MapReduce的電子地圖數(shù)字水印處理方法

方曉樂1王倩雪2陳鑫祥1吳永靜1

1(廣東省國土資源技術(shù)中心數(shù)據(jù)管理室廣東 廣州 510075)2(廣東工業(yè)大學(xué)自動化學(xué)院廣東 廣州 510075)

電子地圖在互聯(lián)網(wǎng)上發(fā)布后，可以通過數(shù)字水印技術(shù)來保護(hù)其所有者的版權(quán)。為了提高數(shù)字水印算法嵌入的執(zhí)行效率，提出一種并行的電子地圖數(shù)字水印嵌入法。該方法基于并優(yōu)化了MapReduce編程模型，再結(jié)合一種具有高魯棒性、基于離散余弦變換(DCT)的數(shù)字水印法，對海量的電子地圖瓦片進(jìn)行并行的水印加載。最后在測試實驗中表明，該方法較傳統(tǒng)模式，提升了工作效率。

電子地圖MapReduceDCT數(shù)字水印并行處理云計算海量

0　引　言

在地理信息系統(tǒng)(GIS)應(yīng)用中，隨著模擬地圖向數(shù)字地圖的轉(zhuǎn)變，電子地圖已是不可或缺的表現(xiàn)形式之一[1]。電子地圖采用了通用的數(shù)字圖片格式，在互聯(lián)網(wǎng)中為使用者們提供地理信息服務(wù)。由于其存在形式具有無限次的復(fù)制性，并且復(fù)制處理手段相對非常簡單和低廉，再加上網(wǎng)絡(luò)傳播的便捷性，電子地圖極易被非法仿制、處理和傳播。因此，數(shù)字水印技術(shù)被廣泛地應(yīng)用到保護(hù)電子地圖所有者版權(quán)中[2-4]。

數(shù)字水印技術(shù)被大量使用在解決數(shù)字作品版權(quán)保護(hù)上，包括了圖像、視頻、文本和音頻等。數(shù)字水印技術(shù)將一些標(biāo)識信息(即數(shù)字水印)直接嵌入數(shù)字載體當(dāng)中(包括多媒體、文檔、軟件等)或是間接表示(修改特定區(qū)域的結(jié)構(gòu))，且不影響原載體的使用價值，也不容易被探知和再次修改。而通過這些隱藏在載體中的信息，可以達(dá)到防偽溯源、版權(quán)保護(hù)的目的[5]。

當(dāng)前，大部分的數(shù)字水印算法都是串行單機(jī)對圖片進(jìn)行水印嵌入的[6-9]。當(dāng)面對海量圖片(比如電子地圖瓦片)處理的時候，傳統(tǒng)的單機(jī)處理方式往往會顯得力不從心。云計算并行處理是提升海量工作效率的最熱門方法之一，對此有許多的研究[8-12]。其中文獻(xiàn)[11]提出一種基于MapReduce的方法，從而提高了在地理信息數(shù)據(jù)地物中加入水印的效率。本文針對海量電子地圖瓦片這種情況，結(jié)合之前的一些研究工作[6]，提出一種新的數(shù)字水印處理方法：利用并優(yōu)化MapReduce并行計算架構(gòu)，結(jié)合DCT變換數(shù)字水印算法，通過若干臺PC終端，把水印并行嵌入到海量的電子地圖瓦片中。

1　電子地圖與數(shù)字水印算法

1.1電子地圖瓦片

隨著WebGIS和計算機(jī)等技術(shù)的發(fā)展，電子地圖網(wǎng)站(比如國外的Google、Bing，國內(nèi)的百度、天地圖等)都是采用電子地圖瓦片的模式來提供地圖服務(wù)[13]。在這樣的模式下，所有瀏覽中調(diào)用到的地圖都是由若干瓦片組合而成的，不同地圖比例尺的瓦片集會預(yù)先生成并存放在地圖服務(wù)器中。而瓦片往往采用壓縮強(qiáng)度大、容量小的格式，從而使其能夠滿足在互聯(lián)網(wǎng)上被使用者流暢地瀏覽[14]。本文中所用的電子地圖瓦片源自“天地圖·廣東”[14],每張瓦片(如圖1所示)有以下特點(diǎn)：(1) 分辨率較?。?56×256的像素級別；(2) 為了減小其容量，采用了高強(qiáng)度的切割壓縮法[15]，格式為JPEG；(3) “天地圖·廣東”要提供全廣東省各比例尺級別的地圖服務(wù)，因此有海量的瓦片；(4) 瓦片色彩較一般的圖片比較單調(diào)，嵌入水印魯棒性難以保證。

圖1　“天地圖·廣東”地圖影像瓦片樣圖

1.2DCT數(shù)字水印算法

互聯(lián)網(wǎng)時代，數(shù)字水印作為保護(hù)數(shù)字作品版權(quán)的最主要方式之一，已經(jīng)有許多研究者們提出了不同的算法[2,4,16,17]，主要有兩種方式：(1) 在圖片的像素空間不重要位LSB嵌入水印信息；(2) 先進(jìn)行轉(zhuǎn)域的變換(DCT、傅里葉等)，再在其不易被人眼覺察的位置嵌入水印信息。綜合了各方面因素情況下，文獻(xiàn)[6]提出了一種具有強(qiáng)魯棒性且適用于電子地圖瓦片的數(shù)字水印算法，其嵌入處理的步驟如下：

第一步導(dǎo)出數(shù)字水印的像素(像素為0和1的雙值格式)，并把像素值的次序通過隨機(jī)數(shù)置亂；

第二步導(dǎo)出電子地圖瓦片的“YUV”(其中“Y”表示明亮度，也就是灰階值；而“U”和“V” 表示的則是色度，作用是描述影像色彩及飽和度，用于指定像素的顏色)中的“Y”值(每個值范圍0～255)；

第三步把導(dǎo)出的“Y”值數(shù)列拆分成若干個不重疊的8×8分辨率小分塊，每塊都進(jìn)行DCT變換，轉(zhuǎn)換成頻率域，DCT變換的公式如下：

(1)

其中：

(2)

完成DCT變換后，每一個分塊再通過量化矩陣M(如圖2量化矩陣所示，矩陣數(shù)值和一個壓縮質(zhì)量指數(shù)QF相關(guān)，QF越大則圖片壓縮度越高)進(jìn)行量化處理；

1611101624405161121214192658605514131624405769561417222951878062182237566810910377243555648110411392486478871031211201017292959811210010399

圖2量化矩陣圖

第四步把置亂順序的水印像素嵌入到每個“Y” DCT變換分塊的低頻部分(人類肉眼一般對低頻部分不敏感，隱藏在低頻部分不易被察覺)，設(shè)定一個C表示DCT系數(shù)，m表示量化矩陣中的對應(yīng)值，sign表示C的符號(正或負(fù))，C*表示嵌入后的新系數(shù)，那么當(dāng)嵌入像素的值為0的時候：

(3)

當(dāng)嵌入像素的值為1時：

(4)

第五步設(shè)置一個加權(quán)值，改善嵌入水印后地圖瓦片的可視效果。設(shè)D為同一位置嵌入數(shù)字水印后和嵌入前“Y”量的差值，則加權(quán)值可以設(shè)為：

D=Y-Y*Y**=Y*+f×D

(5)

通過以上五步，可以實現(xiàn)數(shù)字水印在電子地圖瓦片上的嵌入。在文獻(xiàn)[6]中，還詳細(xì)描述了數(shù)字水印的析出方法，可以脫離原圖，單單通過帶水印瓦片成功析出所嵌入的數(shù)字水印。本文主要描述瓦片水印的并行快速嵌入方式，析出方法則不予講解。

2　數(shù)字水印嵌入并行處理方法

使用DCT數(shù)字水印算法可以實現(xiàn)數(shù)字水印在電子地圖瓦片的嵌入，然而在面對海量瓦片需要處理的時候，傳統(tǒng)方式下依靠單機(jī)單線的處理方式會導(dǎo)致效率極其低下。而云計算這個新概念的出現(xiàn)，為海量電子地圖瓦片數(shù)字水印算法處理提供了新的解決方案和思路。云計算是一種新的分布式計算架構(gòu)，一方面它可以利用所有閑置資源參與運(yùn)算；另一方面它可以滿足GIS高容量和高效訪問量計算量的需求[18]。其中基于開源架構(gòu)Hadoop分布式文件系統(tǒng)的MapReduce編程模式是其最為熱門的解決方案之一[11,12]。它通過映射的方式(“Map”)將數(shù)據(jù)的處理任務(wù)并行地分配在集群的計算機(jī)節(jié)點(diǎn)上，再將并發(fā)處理的結(jié)果歸約(“Reduce”)已完成計算，非常適合海量數(shù)據(jù)的分析計算處理。

2.1Hadoop分布式文件系統(tǒng)

Hadoop分布式文件系統(tǒng)HDFS(Hadoop Distribute File System)是一個被設(shè)計成適合運(yùn)行在通用硬件上的分布式文件系統(tǒng)。HDFS系統(tǒng)具備高度容錯性、適合部署在廉價的機(jī)器上、高吞吐量、非常適合大規(guī)模數(shù)據(jù)集應(yīng)用等特點(diǎn)。HDFS放寬了一部分POSIX約束，來實現(xiàn)流式讀取文件系統(tǒng)數(shù)據(jù)的目的。HDFS在最開始是作為Apache Nutch搜索引擎項目的基礎(chǔ)架構(gòu)而開發(fā)的[19,20]。

HDFS的結(jié)構(gòu)是主從式的，其中主節(jié)點(diǎn)(又稱為名字節(jié)點(diǎn))是一個用于管理文件命名空間和調(diào)節(jié)客戶端訪問文件的主服務(wù)器；而從節(jié)點(diǎn)(又稱為數(shù)據(jù)節(jié)點(diǎn))則是若干個機(jī)器(通常一個節(jié)點(diǎn)對應(yīng)一個機(jī)器，可以是PC、服務(wù)器，甚至是虛擬機(jī))，它們用來管理對應(yīng)節(jié)點(diǎn)的存儲。

在HDFS中創(chuàng)建數(shù)據(jù)的時候，會建立一個或多個與數(shù)據(jù)相對應(yīng)的塊文件(block)。為了數(shù)據(jù)的安全性，這些文件一般會被設(shè)置成復(fù)制出若干個冗余備份保存在隨機(jī)不同的數(shù)據(jù)節(jié)點(diǎn)上。這樣的方式不僅保證安全，而且可以實現(xiàn)MapReduce程序讀取數(shù)據(jù)時可以從多個服務(wù)器中獲取，從而改善服務(wù)的伸縮性。如在GIS中的瓦片數(shù)據(jù)可以通過建立快速索引以存儲路徑統(tǒng)一管理的形式存放到HDFS中，使用屬性查詢代替空間查詢，可以避免復(fù)雜的空間計算，節(jié)省瀏覽地圖時的多讀取時間，實現(xiàn)地圖瓦片讀取時的多點(diǎn)響應(yīng)[12]。而這種所謂的“write-one-read-many”方式在寫文件的時候，則會效率有些慢，而這也是在HDFS上使用MapReduce算法執(zhí)行并行電子地圖瓦片嵌入處理時需要解決的難點(diǎn)。

2.2MapReduce算法的優(yōu)化

MapReduce工作一般流程可如圖3所示，所有輸入源數(shù)據(jù)會被編排成一個個鍵值對，具體有6個步驟：(1) 首先對輸入數(shù)據(jù)源進(jìn)行分組；(2) 主節(jié)點(diǎn)調(diào)度從節(jié)點(diǎn)執(zhí)行Map任務(wù)；(3) 從節(jié)點(diǎn)讀取輸入源所分配的對應(yīng)組；(4) 從節(jié)點(diǎn)執(zhí)行Map任務(wù)，將任務(wù)輸出保存在本地；(5) 主節(jié)點(diǎn)調(diào)度從節(jié)點(diǎn)執(zhí)行Reduce任務(wù)，從節(jié)點(diǎn)讀取Map任務(wù)中所有輸出文件；(6) 從節(jié)點(diǎn)執(zhí)行Reduce任務(wù)，將任務(wù)匯總(鍵值對)組合輸出保存到HDFS。

圖3　一般情況下MapReduce的工作流程圖

針對電子地圖瓦片數(shù)字水印的嵌入工作，MapReduce需要在以下幾個方面進(jìn)行相應(yīng)的優(yōu)化(如圖4所示)：首先在默認(rèn)的MapReduce編程模型中，鍵值對的Key是指文件中的行，而Value是指對應(yīng)行的文本內(nèi)容。這樣的設(shè)定并不適合數(shù)字水印嵌入工作的并行處理，需要做相應(yīng)程序源碼上的修改，即Key表示每張圖的路徑文件名，Value表示對應(yīng)圖的內(nèi)容。其次在Reduce的環(huán)節(jié)，Map的輸出還要重新被調(diào)度給從節(jié)點(diǎn)進(jìn)行Reduce任務(wù)，這對于并行處理數(shù)字水印嵌入工作顯得不必要?？梢匀コ齊educe的環(huán)節(jié)，直接由本地轉(zhuǎn)存HDFS，這樣會提高效率，節(jié)省資源，具體修改后的流程可如圖4所示。綜上，在程序代碼方面(Java)：

1) 首先需要新增一個類(如命名ImageWritable)，使用源碼中WritableComparable類的接口，用于描述和構(gòu)建Value(圖片的內(nèi)容)；

2) 其次需要新增一個類(如命名ImageRecordReader)，繼承源碼中RecordReader類，用于描述Key(Text類型，表示文件路徑)和Value(ImageWriatble類型，表示文件的圖片內(nèi)容)的讀取關(guān)系；

3) 再者需要新增一個類(如命名ImageInputFormat)，繼承源碼中FileInputFormat類，用于讀電子地圖瓦片文件；

4) 最后設(shè)置Reduce程序為無效。

圖4　電子地圖瓦片數(shù)字水印嵌入的工作流程圖

3　測　試

3.1測試數(shù)據(jù)

“天地圖·廣東”每年更新一次電子地圖，會涉及約2.1×107張、JPEG格式、超過250 GB的電子地圖瓦片，包括了矢量和影像數(shù)據(jù)。本文的電子地圖數(shù)字水印嵌入實驗中，使用了“天地圖·廣東”中約20 GB、2×106張的電子地圖瓦片樣本。

3.2測試環(huán)境

測試用了8臺PC，配置可見表1所示。其中1臺PC為主節(jié)點(diǎn)，7臺PC為從節(jié)點(diǎn)，通過千兆網(wǎng)絡(luò)組成集群。每臺PC都安裝了CentOS 6.5 Linux操作系統(tǒng)，使用Hadoop版本2.2，以及帶Java環(huán)境版本1.7。

表1　Hadoop集群的硬件配置

3.3測試流程

測試主要驗證大量電子地圖瓦片在新的并行數(shù)字水印嵌入方法下，效率能夠得到明顯的改善。步驟如下：(1) 使用單臺PC，使用傳統(tǒng)Java方式下[6]的數(shù)字水印嵌入程序，對2×103張、2×104張、2×105張、2×106張電子地圖瓦片分別執(zhí)行并記錄時間；(2) 使用Hadoop集群，使用本文優(yōu)化后MapReduce的數(shù)字水印并行嵌入處理程序，對2×103張、2×104張、2×105張、2×106張與步驟(1)相同的電子地圖瓦片分別執(zhí)行并記錄時間。

3.4測試結(jié)果與分析

測試實驗結(jié)果如表2所示，由表中的數(shù)據(jù)可以看出，隨著參與的電子地圖瓦片數(shù)量增大，并行數(shù)字水印嵌入處理方法的優(yōu)勢就越為凸顯。在2×106張瓦片的處理結(jié)果中，單PC需要超過12小時的時間來完成處理，而集群PC并行處理方法下，不到1小時已經(jīng)可以完成?？梢?，在新的電子地圖數(shù)字水印并行處理方法下，效率較傳統(tǒng)方式有顯著提升。

表2　測試實驗結(jié)果

4　結(jié)　語

針對在傳統(tǒng)串行方式下處理海量電子地圖瓦片水印的速率比較緩慢，本文提出了一種并行處理的數(shù)字水印嵌入方法。該方法在MapReduce編程模型下，為了適應(yīng)電子地圖的分布式存放，舍棄了Reduce端，節(jié)省了重新洗牌分配組合的時間；同時重新定義了合適的鍵值對，把數(shù)字水印嵌入工作放在Map環(huán)節(jié)，實現(xiàn)并行的處理。通過對“天地圖·廣東”電子地圖瓦片樣本數(shù)據(jù)的測試對比試驗，驗證了該方法在海量地圖瓦片數(shù)字水印嵌入處理的高效性。

[1] 劉斌,劉正軍,王亮,等.省級應(yīng)急平臺體系基礎(chǔ)地理信息平臺的設(shè)計研究[J].測繪科學(xué),2008,33(S1):84-87.

[2] 王小虎,邵楷,吳愛華.一種地圖水印的嵌入方法[J].長春大學(xué)學(xué)報,2010,20(2):45-47.

[3] 張佐理.一種抗壓縮的矢量地圖水印算法[J].計算機(jī)工程,2010,36(20):137-139.

[4] 閔連權(quán),喻其宏.基于離散余弦變換的數(shù)字地圖水印算法[J].計算機(jī)應(yīng)用與軟件,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變換的數(shù)字水印算法在“天地圖·廣東”中的應(yīng)用[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技術(shù)[J].中文信息學(xué)報,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的高效地理數(shù)據(jù)水印方法[J].華中科技大學(xué)學(xué)報:自然科學(xué)版,2012(S1):179-182.

[12] 林碧英,王艷萍.基于Hadoop的電力地理信息系統(tǒng)數(shù)據(jù)管理[J].計算機(jī)應(yīng)用,2014,34(10):2806-2811.

[13] 邱儒瓊,王波.基于預(yù)生成技術(shù)的WebGIS數(shù)據(jù)處理系統(tǒng)設(shè)計與實現(xiàn)[J].測繪科學(xué),2008,33(S1):138-139.

[14] 蘇旭明,譚建成.WebGIS中瓦片地圖關(guān)鍵技術(shù)研究[J].北京測繪,2012(2):9-11.

[15] 陳鑫祥,吳錦超.利用ArcGIS Engine實現(xiàn)天地圖瓦片數(shù)據(jù)的切割[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平臺在云計算中的應(yīng)用[J].軟件,2011,32(4):36-38,50.

[20] 徐煥良,翟璐,薛衛(wèi),等.Hadoop平臺中MapReduce調(diào)度算法研究[J].計算機(jī)應(yīng)用與軟件,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)。方曉樂，工程師，主研領(lǐng)域：計算機(jī)通信，GIS。王倩雪，講師。陳鑫祥，高工。吳永靜，教授級高工。

TP3

A

10.3969/j.issn.1000-386x.2016.10.047