二維矢量地圖雙重零水印算法

曹劉娟，門(mén)朝光，孫建國(guó)

(哈爾濱工程大學(xué) 高可信計(jì)算技術(shù)研究中心，黑龍江 哈爾濱 150001)

作為地理信息系統(tǒng)(geographic information system，GIS)的重要數(shù)據(jù)源，二維矢量地圖已在國(guó)民經(jīng)濟(jì)各領(lǐng)域得到廣泛的應(yīng)用，由于其制作成本高、數(shù)據(jù)量大且易被非法復(fù)制、篡改和傳播等特性，使得二維矢量地圖的安全問(wèn)題日益突出.目前針對(duì)二維矢量地圖版權(quán)保護(hù)的數(shù)字水印技術(shù)才剛剛興起，主要有基于空間域的水印算法［1-3］，基于變換域的水印算法［4-6］，基于時(shí)間/尺度域的水印算法［7-8］.這些算法是通過(guò)直接或間接地修改頂點(diǎn)坐標(biāo)完成水印信息的嵌入，而這種水印是以犧牲地圖數(shù)據(jù)精度為代價(jià)的，在很多數(shù)據(jù)高保真場(chǎng)合是不被允許的.零水印技術(shù)是通過(guò)抽取圖像的重要特征來(lái)構(gòu)造水印信息，不對(duì)原始數(shù)據(jù)進(jìn)行任何更改，很好地平衡了傳統(tǒng)水印不可感知性和魯棒性之間的矛盾，因此對(duì)矢量地圖高保真場(chǎng)合下的版權(quán)保護(hù)有很高的適用性.近年來(lái)零水印技術(shù)主要應(yīng)用于視頻和柵格圖像領(lǐng)域，主要有基于DCT變換域、基于DWT變換域和基于高階累積量的水印構(gòu)造方法.而針對(duì)二維矢量數(shù)據(jù)零水印算法的研究則較少受到關(guān)注.文獻(xiàn)［9］通過(guò)對(duì)原始矢量地圖地物坐標(biāo)進(jìn)行平均分塊，根據(jù)分塊內(nèi)的頂點(diǎn)個(gè)數(shù)采用加密變換方式構(gòu)造水印圖像.該方案較為簡(jiǎn)單，抵抗數(shù)據(jù)壓縮、簡(jiǎn)化攻擊的能力較弱.文獻(xiàn)［10］利用矢量地圖宏觀和微觀的拓?fù)涮匦詷?gòu)造零水印，該方案對(duì)部分水印攻擊有較好的魯棒性.文獻(xiàn)［11］根據(jù)矢量地圖的拓?fù)鋵哟螌?duì)所有頂點(diǎn)進(jìn)行分類獲取特征序列，并對(duì)選取的2個(gè)特征序列建立映射關(guān)系生成零水印，該算法可抵抗多種組合攻擊，在混沌系統(tǒng)初始參數(shù)未知的情況下，零水印無(wú)法被檢測(cè)到.

本文結(jié)合人工神經(jīng)網(wǎng)絡(luò)與奇異值分解理論提出一種能夠有效抵抗簡(jiǎn)化、壓縮及常見(jiàn)幾何攻擊的二維矢量地圖雙重零水印算法，利用水印算法魯棒互補(bǔ)的特性達(dá)到對(duì)矢量地圖全面保護(hù)的目的.

1 特征點(diǎn)提取

矢量地圖由不同的圖元組成，線圖元中的河流、公路、等高線等遍布矢量地圖的整個(gè)空間且是構(gòu)成矢量地圖的重要組成部分，因此具有抗剪切和不可刪除性，否則矢量地圖的利用價(jià)值將大幅降低.本文利用這些線實(shí)體的特征信息來(lái)構(gòu)造魯棒的零水印.

考慮矢量地圖水印算法對(duì)圖形簡(jiǎn)化攻擊的魯棒性，本文以線圖元特征點(diǎn)提取為基礎(chǔ)，針對(duì)提取的特征點(diǎn)與非特征點(diǎn)序列的特性，分別構(gòu)與其造相適應(yīng)的零水印.特征點(diǎn)即是維持多邊形圖元形狀特征的點(diǎn)，例如一條線圖元的端點(diǎn)、拐點(diǎn)、極值點(diǎn)等.特征點(diǎn)提取算法采用經(jīng)典的道格拉斯－普克法(Douglas-Peucker)［12］.

2 零水印方案

2.1 零水印方案

本文零水印方案以線圖元特征點(diǎn)和非特征點(diǎn)序列為基礎(chǔ)，分別構(gòu)造魯棒的零水印，提高水印的綜合性能從而達(dá)到對(duì)矢量地圖全面保護(hù)的目的.如圖1所示，首先對(duì)矢量地圖的每條線圖元進(jìn)行特征點(diǎn)提取，并對(duì)提取的特征點(diǎn)序列采用BP神經(jīng)網(wǎng)絡(luò)模型的方法;對(duì)非特征點(diǎn)序列采用矩陣奇異值分解的方法，分別得到2部分的零水印參數(shù).

圖1 雙重零水印構(gòu)造方案Fig.1 The construction scheme of double zero-watermarking

人工神經(jīng)網(wǎng)絡(luò)是性能優(yōu)良的非線性自適應(yīng)系統(tǒng)，通過(guò)輸入輸出樣本集的訓(xùn)練，可以實(shí)現(xiàn)從輸入到輸出的任意非線性映射，同時(shí)數(shù)字水印系統(tǒng)可看作是非線性映射過(guò)程，因此針對(duì)反映線圖元基本形狀的特征點(diǎn)，本文采用BP神經(jīng)網(wǎng)絡(luò)來(lái)構(gòu)建特征點(diǎn)之間的關(guān)系模型，并由此構(gòu)造能夠抵抗簡(jiǎn)化、壓縮攻擊的零水印.

基于奇異值分解的數(shù)字水印技術(shù)有以下優(yōu)點(diǎn): 1)奇異值分解對(duì)原始矩陣大小無(wú)任何要求;2)奇異值穩(wěn)定性好，當(dāng)矩陣受到小的擾動(dòng)時(shí)奇異值基本不變;3)奇異值反映的是圖像內(nèi)蘊(yùn)特性而不是視覺(jué)特性，反映的是矩陣元素之間的關(guān)系.因此針對(duì)反映線圖元細(xì)節(jié)的非特征點(diǎn)，本文利用矩陣奇異值的穩(wěn)定性來(lái)構(gòu)造對(duì)常見(jiàn)幾何攻擊穩(wěn)健的零水印.

2.2 基于BP神經(jīng)網(wǎng)絡(luò)的零水印算法

構(gòu)造零水印的過(guò)程以矢量地圖線圖元頂點(diǎn)橫坐標(biāo)為例進(jìn)行闡述，縱坐標(biāo)與其相似:

1)針對(duì)矢量地圖每條線圖元的特征點(diǎn)集合Vf，選定具有高相關(guān)性的9個(gè)特征點(diǎn)(即最密集的9個(gè)特征點(diǎn))，并取其橫坐標(biāo)的整數(shù)部分:xi－4、xi－3、xi－2、xi－1、xi、xi+1、xi+2、xi+3、xi+4.

2)計(jì)算出 M=max{xi－4，xi－3，xi－2，xi－1，xi，xi+1，xi+2，xi+3，xi+4}，通過(guò)除以M 將9個(gè)系數(shù)規(guī)范化到［0，1］區(qū)間，以滿足BP神經(jīng)網(wǎng)絡(luò)的輸入和輸出要求.

3)建立一個(gè)8×10×1的神經(jīng)網(wǎng)絡(luò)，以xi對(duì)應(yīng)的規(guī)范化系數(shù)Pxi為輸出，以其他8個(gè)規(guī)范化系數(shù)為輸入構(gòu)成一個(gè)學(xué)習(xí)樣本，依此方法選取若干其他線圖元的特征點(diǎn)形成樣本集.設(shè)定訓(xùn)練的目標(biāo)為平均絕對(duì)誤差MAE＜T，其中T為常數(shù).

4)比較每條線圖元的規(guī)范化系數(shù)Pxi與其對(duì)應(yīng)的神經(jīng)網(wǎng)絡(luò)實(shí)際輸出值Pxi'的大小，依此得出對(duì)應(yīng)的二元表

式中:⊕表示異或運(yùn)算，m表示水印圖片總比特?cái)?shù).

2.3 基于奇異值的零水印算法

同樣以矢量地圖頂點(diǎn)橫坐標(biāo)為例進(jìn)行闡述，縱坐標(biāo)與其相似:

1)綜合考慮所有線圖元非特征點(diǎn)情況，對(duì)矢量地圖每條線圖元的非特征點(diǎn)集合構(gòu)造一個(gè)固定大小的實(shí)數(shù)矩陣C=(Ci，j)∈RM×N;

2)對(duì)C進(jìn)行奇異值分解，有C=U∑VT，其中U∈RM×M和V∈RN×N都是正交陣，對(duì)角矩陣∑ = diag(σ1，σ2，…，σN)，滿足 σ1≥σ2≥…≥σr＞σr+1=…=σN=0.其中r是∑的秩，它等于非零奇異值的個(gè)數(shù)，σi是由該分解唯一確定的矩陣C的奇異值;

3)計(jì)算矩陣C的第一個(gè)奇異值 σ1.令S=(m為所選線圖元的條數(shù));

2.4 水印提取及檢測(cè)

水印的提取過(guò)程與水印嵌入過(guò)程相對(duì)應(yīng)，特征點(diǎn)序列水印提取步驟如下:

1)依據(jù)道格拉斯－普克法，對(duì)矢量地圖的線圖元進(jìn)行特征點(diǎn)提取.

2)針對(duì)矢量地圖每個(gè)線圖元的特征點(diǎn)集合Vf，選定具有高相關(guān)性的9個(gè)特征點(diǎn)，并取其橫坐標(biāo)的整數(shù)部分，將9個(gè)系數(shù)規(guī)范化到［0，1］區(qū)間.

3)應(yīng)用在零水印構(gòu)造部分建立的8×10×1的神經(jīng)網(wǎng)絡(luò)模型，對(duì)應(yīng)的8個(gè)規(guī)范化系數(shù)為輸入，并計(jì)算輸出值.

4)比較所選特征點(diǎn) xi'對(duì)應(yīng)的規(guī)范化系數(shù)值與神經(jīng)網(wǎng)絡(luò)實(shí)際輸出值″的大小，依此得出對(duì)應(yīng)的二元表

非特征點(diǎn)序列水印提取步驟如下:

1)依據(jù)道格拉斯－普克法，對(duì)矢量地圖的線圖元進(jìn)行特征點(diǎn)提取.

3)對(duì)矩陣C(k)'，k=1，2，…，m(m為線圖元的條數(shù))進(jìn)行奇異值分解，計(jì)算第一個(gè)奇異值'，令

通過(guò)獲得的版權(quán)標(biāo)識(shí)可以確定檢測(cè)地圖的真實(shí)性，達(dá)到版權(quán)保護(hù)的目的.本文的水印檢測(cè)采用相關(guān)性判定，判定公式如下:

式中:w為原始版權(quán)標(biāo)識(shí)信息，w'為檢測(cè)出的水印信息，通過(guò)設(shè)定合適的閾值來(lái)判定版權(quán)的歸屬.若檢測(cè)值ρ大于閾值，則承認(rèn)其版權(quán)，否則視為侵權(quán).從統(tǒng)計(jì)學(xué)的觀點(diǎn)出發(fā)，考慮可能的誤判概率和虛警概率，設(shè)定本算法的閾值為0.6，即檢測(cè)值大于0.6則認(rèn)定版權(quán).

3 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)采用的二維矢量地圖為“哈爾濱河流分布圖”MapInfo/Tab格式，如圖2(a)所示，頂點(diǎn)個(gè)數(shù)為6 831，所使用的版權(quán)標(biāo)識(shí)為64×64的二值圖像，如圖2(b)所示.圖2(c)和圖2(d)分別為以特征點(diǎn)和非特征點(diǎn)序列為基礎(chǔ)構(gòu)造的檢測(cè)密鑰圖像.實(shí)驗(yàn)驗(yàn)證環(huán)境為:Visual C++6.0及MapInfo Mapx插件.

在下面的試驗(yàn)中包括了2個(gè)部分:

1)針對(duì)特征點(diǎn)序列，基于BP神經(jīng)網(wǎng)絡(luò)模型的零水印方案抗簡(jiǎn)化、抗壓縮攻擊試驗(yàn).

2)針對(duì)非特征點(diǎn)序列，矩陣奇異值構(gòu)造的零水印方案抗幾何攻擊試驗(yàn).原始矢量地圖在無(wú)任何攻擊條件下的檢測(cè)值ρ均為1.

圖2 零水印構(gòu)造實(shí)驗(yàn)Fig.2 The experiment of zero-watermarking construction

3.1 基于BP神經(jīng)網(wǎng)絡(luò)的零水印魯棒性試驗(yàn)

為驗(yàn)證基于BP神經(jīng)網(wǎng)絡(luò)模型零水印方案的魯棒性，我們對(duì)矢量地圖在簡(jiǎn)化、壓縮攻擊條件下進(jìn)行了版權(quán)標(biāo)識(shí)檢測(cè)實(shí)驗(yàn).表1、2分別給出了相應(yīng)攻擊條件下的檢測(cè)值ρ的情況.

表1 算法對(duì)地圖簡(jiǎn)化攻擊的魯棒性Table 1 The algorithm robustness to simplification attack

本文采用的簡(jiǎn)化算法為道格拉斯－普克法，簡(jiǎn)化閾值在0.2～1.0 m，每隔0.2 m進(jìn)行一次實(shí)驗(yàn).由表1可知，算法具有較好的抗簡(jiǎn)化攻擊能力.

表2 算法對(duì)壓縮攻擊的魯棒性Table 2 The algorithm robustness to compression attack

本文采用參考文獻(xiàn)［13-14］的矢量地圖壓縮算法進(jìn)行實(shí)驗(yàn)，由表2可知，地圖經(jīng)過(guò)比例高達(dá)15%，20%的壓縮后，監(jiān)測(cè)值仍然高達(dá)0.91.

3.2 基于矩陣奇異值的零水印魯棒性試驗(yàn)

通過(guò)前面的實(shí)驗(yàn)可知基于BP神經(jīng)網(wǎng)絡(luò)模型的零水印方案對(duì)矢量地圖的簡(jiǎn)化、壓縮攻擊有較好的魯棒性，而針對(duì)常見(jiàn)的幾何攻擊，本文的零水印方案依然有效.下面的實(shí)驗(yàn)結(jié)果也充分說(shuō)明了這點(diǎn).表3分別給出了在各種幾何攻擊條件下的檢測(cè)值ρ的情況.

表3 算法對(duì)幾何攻擊的魯棒性Table 3 The algorithm robustness to geometry attacks

由于矢量地圖本身具有無(wú)損縮放、平移和旋轉(zhuǎn)的特性，因此在這幾種攻擊情況下，水印檢測(cè)值均為1.矢量地圖的格致轉(zhuǎn)換攻擊是指地圖在不同數(shù)據(jù)格式之間進(jìn)行轉(zhuǎn)換時(shí)，由于不同格式支持的數(shù)據(jù)單位或精度不同，轉(zhuǎn)換后的數(shù)據(jù)會(huì)產(chǎn)生差異.表3中所對(duì)應(yīng)的格致轉(zhuǎn)換、剪切1/8、剪切1/4、剪切1/2均為對(duì)應(yīng)攻擊情況下的檢測(cè)均值.由表3可知，幾何攻擊條件下的檢測(cè)值均大于閾值0.6，具有較好的魯棒性.

3.3 區(qū)分度實(shí)驗(yàn)

利用本方案針對(duì)“哈爾濱河流分布圖”產(chǎn)生的檢測(cè)密鑰圖像分別對(duì)“英國(guó)高速公路圖”，“中國(guó)高速公路圖”進(jìn)行水印提取(如圖3)，并通過(guò)檢測(cè)公式計(jì)算提取的水印與原始版權(quán)標(biāo)識(shí)的相關(guān)性，得到的監(jiān)測(cè)值ρ分別為0.014和0.038，遠(yuǎn)遠(yuǎn)小于閾值，說(shuō)明這2幅地圖不在版權(quán)保護(hù)范圍內(nèi).由此可知該水印方案抑制互相關(guān)性好，包含了地圖的重要特征，可以區(qū)分不同的地圖.

由實(shí)驗(yàn)可知，本文研究的分別針對(duì)特征點(diǎn)與非特征點(diǎn)序列的雙重零水印方案在魯棒性方面有較好的互補(bǔ)性，同時(shí)采用2種方案能夠達(dá)到對(duì)矢量地圖全面保護(hù)的目的.

圖3 區(qū)分度實(shí)驗(yàn)采用的矢量地圖Fig.3 The vector maps used for differentiation experiment

4 結(jié)束語(yǔ)

本文提出一種針對(duì)二維矢量地圖線圖元特征點(diǎn)與非特征點(diǎn)分別進(jìn)行參數(shù)構(gòu)造的雙重零水印算法.并將構(gòu)造的零水印圖案送版權(quán)管理中心注冊(cè)，當(dāng)發(fā)生版權(quán)糾紛時(shí)，通過(guò)公開(kāi)算法恢復(fù)版權(quán)標(biāo)識(shí)，達(dá)到版權(quán)保護(hù)的目的.實(shí)驗(yàn)驗(yàn)證該雙重零水印方案具有較好的魯棒性，并且整個(gè)過(guò)程中不對(duì)原始數(shù)據(jù)進(jìn)行任何修改，因此適用于高保真場(chǎng)合二維矢量地圖的版權(quán)保護(hù).

［1］COX G S，JAGER G.A survey of point pattern matching technique and a new approach to point pattern recognition［C］//Proceedings of Symposium on Communication and Signal Processing.Lesotho，1993:243-248.

［2］OHBUCHI R，UEDA H，ENDOH S.Robust watermarking of vector digital maps［C］//Proceedings of IEEE Conference on Multimedia and Expo 2002(ICME 2002).Lausanne，Switzerland，2002:1-4.

［3］VOIGT M，BUSCH C.Feature-based watermarking of 2D vector data［C］//Proceedings of SPIE.Santa Clara，USA，2003:359-366.

［4］ZHONG S P，GAO Q S.The feasibility analysis of normalized-correlation-based vector maps watermarking detection algorithm and the improved watermarking algorithm［J］.Journal of Image and Graphics，2006，11(3):401-409.

［5］VOIGT M，YANG B，BUSCH C.Reversible watermarking of 2D-vector data［C］//Proceedings of the 2004 ACM International Workshop on Multimedia and security.Magdeburg，Germany，2004:160-165.

［6］姚惠明，周冠玲，楊義先，等.一種基于矢量共享方案的DCT域上數(shù)字水印分存算法［J］.計(jì)算機(jī)學(xué)報(bào)，2004，27(7):998-1003.

YAO Huiming，ZHOU Guanling，YANG Yixian，et al.A DCT domain digital watermarking sharing algorithm based on vector secret sharing scheme［J］.Chinese Journal of Computers，2004，27(7):998-1003.

［7］ZHANG Q，XIANG H，MENG X X.Watermarking vector graphics based on complex wavelet transform［J］.Journal of Image of Graphics，2005，4(10):12-15.

［8］ZHANG C Q，YANG C S，WANG Q S.A watermarking algorithm for vector geo-spatial data based on integer wavelet transform［C］//The International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences.Beijing，China，2008:15-18.

［9］張佐理，孫樹(shù)森，汪亞明，等.二維矢量數(shù)字地圖的零水印算法［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30(6):1474-1479.

ZHANG Zuoli，SUN Shusen S，WANG Yaming，et al.Zero-watermarking algorithm for 2D vector map［J］.Computer Engineering and Design，2009，30(6):1474-1479.

［10］LI A，LIN B X，CHEN Y，et al.Study on copyright authentication of GIS vector data based on zerowatermarking［C］//The International Archives of the Photogrammetry，Remote Sensing and Spatial Information Sciences.Beijing，China，2008:1783-1786.

［11］DU Q Z，PENG F.A zero-watermark algorithm with realmean for 2D Engineering graphic［C］//International Symposium on Electronic Commerce and Security.Guangzhou，China，2008:890-893.

［12］DOUGLAS D H，PEUCHER T K.Algorithms for the reduction of the number of points required to represent a digitized line or its cariture［J］.Canadian Cartographer，1973，10:112-122.

［13］李青元，劉曉東，曹代勇.Web GIS矢量空間數(shù)據(jù)壓縮方法探討［J］.中國(guó)圖形圖像學(xué)報(bào)，2001，6(12):1225-1229.

LI Qingyuan，LIU Xiaodong，CAO Daiyong.Research in web GIS vector spatial data compression methods［J］.Journal of Image and Graphics，2001，6(12):1225-1229.

［14］李琦，楊超偉，陳愛(ài)軍.WebGIS中的地理關(guān)系數(shù)據(jù)庫(kù)模型研究［J］.中國(guó)圖象圖形學(xué)報(bào)，2000，5(2):119-123.

LI Qi，YANG Chaowei，CHEN Aijun.Research on geographical relational database model in WebGIS［J］.Journal of Image of Graphics，2000，5(2):119-123.