一種基于矢量地圖特征點和分塊的零水印算法

孫鴻睿，朱建軍，尹鵬程，施永勝

（1.中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南長沙410083；2.常德市國土資源規(guī)劃測繪院，湖南常德415000；3.中國礦業(yè)大學(xué)環(huán)境與測繪學(xué)院，江蘇徐州221008；4.徐州市國土資源局，江蘇徐州221006）

一種基于矢量地圖特征點和分塊的零水印算法

孫鴻睿1，2，朱建軍1，尹鵬程3＊，施永勝2

（1.中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南長沙410083；2.常德市國土資源規(guī)劃測繪院，湖南常德415000；3.中國礦業(yè)大學(xué)環(huán)境與測繪學(xué)院，江蘇徐州221008；4.徐州市國土資源局，江蘇徐州221006）

近幾年，數(shù)字水印作為版權(quán)保護的關(guān)鍵技術(shù)被用于矢量地圖。目前，矢量圖形水印算法主要分為空域算法和頻域算法［1］，但這兩種算法在完成數(shù)字水印嵌入的同時，均修改了矢量地圖數(shù)據(jù)，會影響地圖精度，而且數(shù)字水印容易擦除。針對這一問題，溫泉等首先提出了零水印方案，并成功將其應(yīng)用于數(shù)字圖像中［2］。零水印是指不修改原始作品的內(nèi)容，利用原始作品的重要特征構(gòu)造水印，能解決水印魯棒性和不可見性之間的矛盾。本文在前人研究的基礎(chǔ)上，設(shè)計了一種基于矢量地圖特征點和分塊的零水印算法，可以有效提高數(shù)據(jù)壓縮、頂點增加（刪除）以及數(shù)據(jù)裁剪等操作的魯棒性。

1 基于矢量地圖特征點的零水印構(gòu)造方案

盡管矢量地圖冗余數(shù)據(jù)相對較少，但在不影響精度的情況下，允許線（面）狀數(shù)據(jù)壓縮［3］。為使算法能對抗數(shù)據(jù)壓縮，在水印嵌入前先對原始地圖做壓縮處理，提取特征點，本文選擇矢量數(shù)據(jù)壓縮算法中比較經(jīng)典的道格拉斯壓縮算法；為使地圖能對抗裁剪，可對地圖進行分塊處理，保證每一矩形網(wǎng)格內(nèi)至少能嵌入一次水印，也可嵌入盡可能多的水印，保證裁剪后圖形仍保留完整的水印信息。

1.1 零水印構(gòu)造方案

可以利用地圖分塊后每一子塊內(nèi)相鄰特征點所在直線的夾角值所對應(yīng)的二進制序列與置亂后水印圖像所對應(yīng)的二進制序列來構(gòu)造零水印，本文是對二者進行邏輯運算，實現(xiàn)零水印的構(gòu)造模式。在地圖分塊時，為保證每一分塊內(nèi)都能完整地嵌入一次水印，需要預(yù)先計算水印信息的比特數(shù)；對于給定的水印圖像，能夠預(yù)先知道其水印信息容量，可以據(jù)此對地圖進行分塊。零水印構(gòu)造流程如圖1。

圖1 零水印構(gòu)造流程

1.2 特征點提取

本文選擇矢量數(shù)據(jù)壓縮算法中比較經(jīng)典的道格拉斯壓縮算法，其基本思想是［4］：將線劃上的第一點作為固定點，最后一點作為浮動點，這兩點確定一條直線。計算線劃上所有中間點到直線的距離，將距離最大者與事先給定的閾值相比較，如果最大距離小于給定的閾值，則所有中間點均舍去；否則，保留線劃上具有最大距離的點，并以此點為基準將整條線劃一分為二。重復(fù)上述過程，直至沒有多余的點可被舍去為止。

1.3 地圖分塊

假定某一分塊內(nèi)包含相鄰特征點所在直線間夾角s個，水印信息比特數(shù)為a，因為每個角度值b都可以表示為8位二進制數(shù)b′，因此這一分塊內(nèi)能夠完整地嵌入一次水印的條件可表示為：8s≥a。依據(jù)上述規(guī)則，將給定的矢量地圖分成n個（可構(gòu)造零水印的最大數(shù)）矩形塊。

1.4 水印圖像的置亂

為了增強水印的安全性，通常在嵌入水印前對水印進行置亂操作，本文采用Arnold變換［5］，又稱“貓臉”變換。對于一幅大小為M＊M的圖像，Arnold變換可以表達為：

Arnold變換具有周期性，即對圖像進行一定次數(shù)的Arnold變換后，能夠重新得到原始圖像。例如，原始水印圖像（圖2a）尺寸為40＊40，圖2b－圖2d分別給出了變換1次、10次、30次的置亂結(jié)果。當Arnold變換30次后，水印圖像將恢復(fù)成原始圖像，即該圖像的置亂周期為30次。

圖2 Arnold置亂示例

2 零水印的提取

水印提取為上述水印構(gòu)造的逆過程，將構(gòu)造的n個零水印與Li子塊內(nèi)相鄰特征點直線夾角所構(gòu)成的二進制序列Bi′（i＝1，2，…，n；n為分塊數(shù)）進行二進制按位異或運算，得到置亂后的水印圖像，再對該圖像進行還原，即可得到n個含有版權(quán)信息的原始水印圖像。零水印提取流程如圖3。

圖3 零水印提取流程

3 實驗分析

3.1 零水印構(gòu)造實驗

為驗證所提算法的可行性和正確性，以1∶500的等高線圖為原始地圖，以40＊40的水印圖像為負載，在Matalab7.0平臺上實現(xiàn)本文所提算法。原始地圖頂點數(shù)為60 251，利用道格拉斯壓縮算法提取特征點，本文取閾值0.7，明顯高于地圖數(shù)據(jù)所允許的壓縮程度，用于提高地圖抗簡化能力。數(shù)據(jù)壓縮后提取特征點為7 339個，壓縮率為88%。

按照上述分塊規(guī)則對地圖進行分塊處理，每一分塊內(nèi)至少需要特征點組成角度值40＊40／8＝200個，可將地圖分成16塊，即可構(gòu)造16個零水印。

按照上述方法提取出特征點后，計算每一子塊內(nèi)相鄰特征點直線夾角Bi（i＝1，2，…，200），并轉(zhuǎn)換成二進制序列Bi′（i＝1，2，…，1 600），與置亂后的水印二進制序列進行按位異或運算，可得到16個零水印。

3.2 零水印的魯棒性測試

為了檢驗本文算法的魯棒性，對矢量數(shù)字地圖進行平移、旋轉(zhuǎn)、放大（縮小）、頂點刪除（增加）及地圖裁剪等操作。由于矢量數(shù)字地圖本身的特性以及本算法采用相鄰特征點間直線的夾角構(gòu)造水印，進行平移、旋轉(zhuǎn)或者縮放均不會影響特征點間直線的夾角，所以前3種操作對水印信息的檢測沒有影響。

用NC系數(shù)作為檢測水印與原水印相似性程度的客觀度量，對其他攻擊的魯棒性進行測試。水印相似度檢驗的通用公式為：

各種處理方式下水印提取效果如表1。

4 結(jié)語

本文設(shè)計了一種基于矢量地圖特征點和分塊的零水印算法，利用地圖分塊后每一子塊內(nèi)相鄰特征點所在直線的夾角構(gòu)成的二進制序列，與置亂后的水印圖像進行二進制位異或運算來構(gòu)造零水印。通過仿真實驗分析，該算法可有效對抗地圖幾何變換（平移、旋轉(zhuǎn)、縮放等），在數(shù)據(jù)壓縮、頂點刪除（增加）以及數(shù)據(jù)裁剪方面具有更強的魯棒性。需要指出的是，構(gòu)造的零水印需要送版權(quán)注冊管理中心（IPR）注冊，當版權(quán)發(fā)生糾紛時，通過公開檢測算法提取版權(quán)標識才能達到版權(quán)保護的目的。

［1］ 閔連權(quán).一種魯棒的矢量地圖數(shù)據(jù)的數(shù)字水印［J］.測繪學(xué)報，2008，37（2）：262－267.

［2］ 溫泉，孫錟鋒，王樹勛.零水印的概念與應(yīng)用［J］.電子學(xué)，2003，31（2）：214－216.

［3］ 朱長青，楊成松，李中原.一種抗數(shù)據(jù)壓縮的矢量地圖數(shù)據(jù)數(shù)字水印算法［J］.測繪科學(xué)技術(shù)學(xué)報，2006，23（4）：281－283.

［4］ 華一新.地理信息系統(tǒng)原理與技術(shù)［M］.鄭州：中國人民解放軍測繪學(xué)院，1999.

［5］ ARNOLD V I，AVEZ A.Ergodic problems of classical mechanics［A］.Mathematical Physics Monograph Series［C］.New York：W A Benjamin，Inc，1968.

2012－02－07；

2012－03－12

湖南省科技計劃項目（2009SK3053）；湖南省教育廳重點實驗室項目（09K006）

孫鴻睿（1980－），女，博士，研究方向為空間數(shù)據(jù)數(shù)字水印等。＊通訊作者E－mail：cumtyinpc＠163.com