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

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

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所示，所有輸入源數據會被編排成一個個鍵值對，具體有6個步驟：(1) 首先對輸入數據源進行分組；(2) 主節點調度從節點執行Map任務；(3) 從節點讀取輸入源所分配的對應組；(4) 從節點執行Map任務，將任務輸出保存在本地；(5) 主節點調度從節點執行Reduce任務，從節點讀取Map任務中所有輸出文件；(6) 從節點執行Reduce任務，將任務匯總(鍵值對)組合輸出保存到HDFS。

圖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