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

曹劉娟，門朝光，孫建國

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

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

本文結合人工神經網絡與奇異值分解理論提出一種能夠有效抵抗簡化、壓縮及常見幾何攻擊的二維矢量地圖雙重零水印算法，利用水印算法魯棒互補的特性達到對矢量地圖全面保護的目的.

1 特征點提取

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

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

2 零水印方案

2.1 零水印方案

本文零水印方案以線圖元特征點和非特征點序列為基礎，分別構造魯棒的零水印，提高水印的綜合性能從而達到對矢量地圖全面保護的目的.如圖1所示，首先對矢量地圖的每條線圖元進行特征點提取，并對提取的特征點序列采用BP神經網絡模型的方法;對非特征點序列采用矩陣奇異值分解的方法，分別得到2部分的零水印參數.

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

人工神經網絡是性能優良的非線性自適應系統，通過輸入輸出樣本集的訓練，可以實現從輸入到輸出的任意非線性映射，同時數字水印系統可看作是非線性映射過程，因此針對反映線圖元基本形狀的特征點，本文采用BP神經網絡來構建特征點之間的關系模型，并由此構造能夠抵抗簡化、壓縮攻擊的零水印.

基于奇異值分解的數字水印技術有以下優點: 1)奇異值分解對原始矩陣大小無任何要求;2)奇異值穩定性好，當矩陣受到小的擾動時奇異值基本不變;3)奇異值反映的是圖像內蘊特性而不是視覺特性，反映的是矩陣元素之間的關系.因此針對反映線圖元細節的非特征點，本文利用矩陣奇異值的穩定性來構造對常見幾何攻擊穩健的零水印.

2.2 基于BP神經網絡的零水印算法

構造零水印的過程以矢量地圖線圖元頂點橫坐標為例進行闡述，縱坐標與其相似:

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

2)計算出 M=max{xi－4，xi－3，xi－2，xi－1，xi，xi+1，xi+2，xi+3，xi+4}，通過除以M 將9個系數規范化到［0，1］區間，以滿足BP神經網絡的輸入和輸出要求.

3)建立一個8×10×1的神經網絡，以xi對應的規范化系數Pxi為輸出，以其他8個規范化系數為輸入構成一個學習樣本，依此方法選取若干其他線圖元的特征點形成樣本集.設定訓練的目標為平均絕對誤差MAE＜T，其中T為常數.

4)比較每條線圖元的規范化系數Pxi與其對應的神經網絡實際輸出值Pxi'的大小，依此得出對應的二元表

式中:⊕表示異或運算，m表示水印圖片總比特數.

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

同樣以矢量地圖頂點橫坐標為例進行闡述，縱坐標與其相似:

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

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

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

2.4 水印提取及檢測

水印的提取過程與水印嵌入過程相對應，特征點序列水印提取步驟如下:

1)依據道格拉斯－普克法，對矢量地圖的線圖元進行特征點提取.

2)針對矢量地圖每個線圖元的特征點集合Vf，選定具有高相關性的9個特征點，并取其橫坐標的整數部分，將9個系數規范化到［0，1］區間.

3)應用在零水印構造部分建立的8×10×1的神經網絡模型，對應的8個規范化系數為輸入，并計算輸出值.

4)比較所選特征點 xi'對應的規范化系數值與神經網絡實際輸出值″的大小，依此得出對應的二元表

非特征點序列水印提取步驟如下:

1)依據道格拉斯－普克法，對矢量地圖的線圖元進行特征點提取.

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

通過獲得的版權標識可以確定檢測地圖的真實性，達到版權保護的目的.本文的水印檢測采用相關性判定，判定公式如下:

式中:w為原始版權標識信息，w'為檢測出的水印信息，通過設定合適的閾值來判定版權的歸屬.若檢測值ρ大于閾值，則承認其版權，否則視為侵權.從統計學的觀點出發，考慮可能的誤判概率和虛警概率，設定本算法的閾值為0.6，即檢測值大于0.6則認定版權.

3 實驗結果

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

在下面的試驗中包括了2個部分:

1)針對特征點序列，基于BP神經網絡模型的零水印方案抗簡化、抗壓縮攻擊試驗.

2)針對非特征點序列，矩陣奇異值構造的零水印方案抗幾何攻擊試驗.原始矢量地圖在無任何攻擊條件下的檢測值ρ均為1.

圖2 零水印構造實驗Fig.2 The experiment of zero-watermarking construction

3.1 基于BP神經網絡的零水印魯棒性試驗

為驗證基于BP神經網絡模型零水印方案的魯棒性，我們對矢量地圖在簡化、壓縮攻擊條件下進行了版權標識檢測實驗.表1、2分別給出了相應攻擊條件下的檢測值ρ的情況.

表1 算法對地圖簡化攻擊的魯棒性Table 1 The algorithm robustness to simplification attack

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

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

本文采用參考文獻［13-14］的矢量地圖壓縮算法進行實驗，由表2可知，地圖經過比例高達15%，20%的壓縮后，監測值仍然高達0.91.

3.2 基于矩陣奇異值的零水印魯棒性試驗

通過前面的實驗可知基于BP神經網絡模型的零水印方案對矢量地圖的簡化、壓縮攻擊有較好的魯棒性，而針對常見的幾何攻擊，本文的零水印方案依然有效.下面的實驗結果也充分說明了這點.表3分別給出了在各種幾何攻擊條件下的檢測值ρ的情況.

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

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

3.3 區分度實驗

利用本方案針對“哈爾濱河流分布圖”產生的檢測密鑰圖像分別對“英國高速公路圖”，“中國高速公路圖”進行水印提取(如圖3)，并通過檢測公式計算提取的水印與原始版權標識的相關性，得到的監測值ρ分別為0.014和0.038，遠遠小于閾值，說明這2幅地圖不在版權保護范圍內.由此可知該水印方案抑制互相關性好，包含了地圖的重要特征，可以區分不同的地圖.

由實驗可知，本文研究的分別針對特征點與非特征點序列的雙重零水印方案在魯棒性方面有較好的互補性，同時采用2種方案能夠達到對矢量地圖全面保護的目的.

圖3 區分度實驗采用的矢量地圖Fig.3 The vector maps used for differentiation experiment

4 結束語

本文提出一種針對二維矢量地圖線圖元特征點與非特征點分別進行參數構造的雙重零水印算法.并將構造的零水印圖案送版權管理中心注冊，當發生版權糾紛時，通過公開算法恢復版權標識，達到版權保護的目的.實驗驗證該雙重零水印方案具有較好的魯棒性，并且整個過程中不對原始數據進行任何修改，因此適用于高保真場合二維矢量地圖的版權保護.

［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域上數字水印分存算法［J］.計算機學報，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］張佐理，孫樹森，汪亞明，等.二維矢量數字地圖的零水印算法［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矢量空間數據壓縮方法探討［J］.中國圖形圖像學報，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］李琦，楊超偉，陳愛軍.WebGIS中的地理關系數據庫模型研究［J］.中國圖象圖形學報，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.