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

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

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

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

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

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

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

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

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

1.2 特征點(diǎn)提取

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

1.3 地圖分塊

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

1.4 水印圖像的置亂

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

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

圖2 Arnold置亂示例

2 零水印的提取

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

圖3 零水印提取流程

3 實(shí)驗(yàn)分析

3.1 零水印構(gòu)造實(shí)驗(yàn)

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

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

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

3.2 零水印的魯棒性測試

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

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

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

4 結(jié)語

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

［1］ 閔連權(quán).一種魯棒的矢量地圖數(shù)據(jù)的數(shù)字水?。跩］.測繪學(xué)報(bào)，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é)報(bào)，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

湖南省科技計(jì)劃項(xiàng)目（2009SK3053）；湖南省教育廳重點(diǎn)實(shí)驗(yàn)室項(xiàng)目（09K006）

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