方曉樂(lè)　王倩雪　陳鑫祥　吳永靜

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

?

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

方曉樂(lè)1王倩雪2陳鑫祥1吳永靜1

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

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

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

0　引　言

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

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

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

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

1.1電子地圖瓦片

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

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

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

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

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

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

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

(1)

其中：

(2)

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

1611101624405161121214192658605514131624405769561417222951878062182237566810910377243555648110411392486478871031211201017292959811210010399

圖2量化矩陣圖

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

(3)

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

(4)

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

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

(5)

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

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

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

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

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

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

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

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

MapReduce工作一般流程可如圖3所示，所有輸入源數(shù)據(jù)會(huì)被編排成一個(gè)個(gè)鍵值對(duì)，具體有6個(gè)步驟：(1) 首先對(duì)輸入數(shù)據(jù)源進(jìn)行分組；(2) 主節(jié)點(diǎn)調(diào)度從節(jié)點(diǎn)執(zhí)行Map任務(wù)；(3) 從節(jié)點(diǎn)讀取輸入源所分配的對(duì)應(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ù)匯總(鍵值對(duì))組合輸出保存到HDFS。

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

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

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

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

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

4) 最后設(shè)置Reduce程序?yàn)闊o(wú)效。

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

3　測(cè)　試

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

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

3.2測(cè)試環(huán)境

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

表1　Hadoop集群的硬件配置

3.3測(cè)試流程

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

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

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

表2　測(cè)試實(shí)驗(yàn)結(jié)果

4　結(jié)　語(yǔ)

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

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

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

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

[4] 閔連權(quán),喻其宏.基于離散余弦變換的數(shù)字地圖水印算法[J].計(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] 方曉樂(lè),吳永靜,李志中,等.一種基于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é)報(bào),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é)報(bào):自然科學(xué)版,2012(S1):179-182.

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

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

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

[15] 陳鑫祥,吳錦超.利用ArcGIS Engine實(shí)現(xiàn)天地圖瓦片數(shù)據(jù)的切割[J].北京測(cè)繪,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] 方曉樂(lè),吳永靜,萬(wàn)寶林,等.基于云平臺(tái)的“天地圖·廣東”測(cè)試[J].地理空間信息,2014,12(5):152-153.

[19] 王宏宇.Hadoop平臺(tái)在云計(jì)算中的應(yīng)用[J].軟件,2011,32(4):36-38,50.

[20] 徐煥良,翟璐,薛衛(wèi),等.Hadoop平臺(tái)中MapReduce調(diào)度算法研究[J].計(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。廣東省國(guó)土資源廳科研專(zhuān)項(xiàng)項(xiàng)目(GDGT KJ2014006)。方曉樂(lè)，工程師，主研領(lǐng)域：計(jì)算機(jī)通信，GIS。王倩雪，講師。陳鑫祥，高工。吳永靜，教授級(jí)高工。

TP3

A

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