基于零水印與脆弱水印的矢量地理數據多重水印算法*

梁偉東，張新長2,，奚旭，張鵬程

(1.中山大學地理科學與規(guī)劃學院，廣東 廣州 510275; 2.廣州大學地理科學學院，廣東 廣州 510006；3. 廣州市城市規(guī)劃勘測設計研究院，廣東 廣州 510060)

矢量地理數據具有精度高、更新快等優(yōu)點，已被廣泛用于國防科技、經濟發(fā)展等各方面。同時矢量地理數據制作成本高、易于非法傳播與篡改，對其版權保護與內容認證一直是信息安全領域的重點，其中數字水印技術是一種較為有效的手段[1]?，F有的矢量地理數據數字水印研究，一般只針對版權保護或內容認證，若將兩者相結合，對于矢量地理數據的保護將更為全面與高效，而多重水印技術目前是較好的實現方式。但現有的矢量地理數據多重水印算法主要用于版權保護[2-4]，能同時提供版權保護與內容認證的多重水印算法很少，其主要原因是：用于版權保護的水印需要強魯棒性，而用于內容認證的水印強調敏感性，如何保證兩種水印有效且互不影響是一個難點。隨著數字水印技術的發(fā)展，零水印作為一種不對原始數據進行修改的新的數字水印技術[5]，具有優(yōu)異的高保真度，為解決上述問題提供新的思路：利用零水印算法或相關無損嵌入技術使兩種水印相互獨立，二者既能正常生效又避免產生影響。

在版權保護方面，矢量地理數據零水印算法已有相關應用，算法的關鍵是提取與數據載體緊密相關的特征信息，包括：數據整體的各層次拓撲結構[6]與各類統計信息[7]；數據各部分特征點，通過特定方法[8]構造出的角度序列[9]、距離序列[10]、比值序列[11]和特征點平均坐標[12]等信息；以及屬性信息中的要素編碼序列等[13]。各種零水印算法對幾何攻擊、數據壓縮和裁剪等水印攻擊均具有一定的魯棒性，但由于特征信息穩(wěn)定性不一，魯棒性與安全性存在一定差異。在內容認證方面，利用脆弱水印對矢量地理數據進行精確認證，可判別數據是否完整或發(fā)生變化，并定位被篡改的數據到相應的數據塊、組[14-16]或節(jié)點上[17, 18]。但是，現有算法中較少能實現水印無損嵌入，可逆水印技術[19]雖然可以無損恢復數據，但是當攻擊者篡改恢復后的數據，脆弱水印技術則無法有效應對，因此，目前較為缺乏一種能為矢量地理數據持續(xù)提供精確認證且無損嵌入的脆弱水印。

基于此，本文提出一種兼顧版權保護與內容認證的多重水印算法：首先對矢量圖元節(jié)點數據進行分塊，針對版權保護，本文分別利用道格拉斯算法和Delaunay三角網提取特征點和特征信息，結合Arnold置亂算法，設計一種魯棒性強、容量大、安全性高的高保真零水印算法；針對精確認證，本文通過空間排序與零比特動態(tài)擴展，設計一種精確定位到點的無損嵌入的脆弱水印。本算法通過實現多重水印的無損嵌入，達到兩種水印之間互不影響的目的，有效解決了前文提出的問題，有助于全面而高效地保護矢量地理數據。

1 多重水印算法設計

1.1 技術路線

本文多重水印算法以矢量圖元節(jié)點數據為基礎，水印構造與水印提取檢驗流程如圖1和圖2所示。

在數據分塊的基礎上進行多重水印構造，通過在每個分塊中嵌入水印信息，增加水印的個數，可提高魯棒水印抵抗裁剪攻擊的能力以及脆弱水印定位被篡改數據的效率與精度。本文選取點約束分塊法[16]對數據進行分塊，該方法在面積四叉樹分塊法[20]基礎上，將點數量大于閾值的分塊繼續(xù)劃分，直到點的數量小于閾值。在構造零水印時，算法的關鍵是從數據中提取穩(wěn)定的特征信息，而拓撲信息一般較為穩(wěn)定。本文首先利用道格拉斯算法提取特征點，根據Delaunay三角網空外接圓和最大化最小角性質以及局部穩(wěn)定性，將各三角形角度值作為數據特征信息，構造具有較高水印容量[21]和魯棒性的零水印。在構造脆弱水印方面，為保證在各種攻擊后準確地將無序的數據集合映射到有序的水印信息上，從而正確地恢復水印信息[22]，本文采用Hilbert曲線進行空間排序，構建各節(jié)點數據的空間關系；引入零比特動態(tài)擴展技術[23]，將每個節(jié)點數據產生的水印值取模，并以相應個數的0組成零比特值，生成水印序列，按實際需求加入到該點及臨近點的坐標末尾。

多重水印提取與檢測是水印構造的逆過程，零水印檢測是將提取到的水印圖像與原始水印圖像進行對比，根據相似度確定版權歸屬，從而對數據進行版權保護；脆弱水印檢測是將提取到的原始水印序列與計算得到的現有水印序列進行對比，根據其結果進行內容認證。

1.2 多重水印構造

第1步，對矢量地理數據進行預處理，包括數

圖1 多重水印構造過程Fig.1 The construction process of multiple watermarks

圖2 多重水印提取與檢測Fig.2 The process of multiple watermark extraction and detection

據檢查、提取要素中各類節(jié)點數據等。

第2步，分塊處理：

多重水印算法中由于功能不同，構造零水印與脆弱水印時初次分塊面積分別設置為S1和S2，點個數閾值分別設置為P1和P2。

第3步，構造零水?。?/p>

1)水印圖像處理：對原始二值水印圖像W進行Arnold置亂，提高水印的安全性。

2)生成水印信息：將置亂水印圖像，轉化為0和1的有序序列，每8個值為1組，分為k組，每組序列均可轉化成一個整數值n(n=0,1,…255)，將k個n值組成水印序列Wn；

3)提取特征點：對構造零水印的分塊數據，選取合適的閾值，利用道格拉斯算法提取各個分塊的特征點；

4)構建Delaunay三角網：由各分塊特征點生成三角網，并記錄各三角形的角度值，組成角度序列An，保證每個分塊內的角度序列An的長度大于水印序列Wn的長度；

5)補位操作：若某分塊角度序列An長度是水印序列Wn長度的a倍，則在水印序列Wn的末尾補上b個原有水印序列，如An長度為2 439，Wn長度為800，則Wn補上2Wn位，長度增長為2 400。將An與補位后的Wn進行異或操作，得到1個或a個零水印。將各個分塊產生的包含若干個零水印的圖像，以及原始水印圖像保存至版權保護中心(IPR)，并加入具有法律效力的時間戳，抵御解釋攻擊。

第4步，構造脆弱水?。?/p>

1)空間排序：對構造脆弱水印的分塊數據中的節(jié)點數據按照Hilbert曲線進行排序；

(1)

(Xz,Yz)=((f2(Xb,Yb))10)%10

(2)

c=f3(Xz,Yz)=(Xz⊕Yz)%5

(3)

3)水印無損添加：為了有效抵抗刪點攻擊，對分塊內任意節(jié)點Pi(Xi,Yi)及Hilbert排序中的后鄰點Pi+1(Xi+1,Yi+1)，利用零比特動態(tài)擴展，將Pi的脆弱水印信息Wf，分別加入到橫坐標Xi末位和Pi+1的縱坐標Yi+1末位；若Pi為分塊的末點，則該點的Wf添加到分塊的首點的縱坐標上。對各分塊進行上述操作。

1.3 多重水印提取與檢驗

第1步，對待檢測矢量地理數據進行預處理。

第2步，提取與檢驗零水印：

4)對比驗證：將多個提取水印圖像W’與原始水印圖像W進行驗證，利用歸一化相關系數NC值(Normalized Correlation)衡量兩圖像相似性，公式如下：

(4)

第3步，提取與檢驗脆弱水印：

1)待檢測數據處理：按照與前文相同的方法，對待檢測數據進行分塊、Hilbert空間排序處理；

2)提取水印處理：從各分塊內提取任意節(jié)點Pi(Xi,Yi)坐標末尾的原始脆弱水印信息，記橫坐標提取到的水印信息為Wf，后鄰點Pi+1(Xi+1,Yi+1)縱坐標提取到的水印信息為Wf+1；

2 實驗與分析

本文提出的多重水印算法，可應用于各類點狀數據、線狀數據和面狀數據中，其中，線狀數據需要提取各圖元中的節(jié)點數據，面狀數據可轉化為線狀數據再提取節(jié)點數據。本文選取廣州市海珠區(qū)1∶5 000 Shp格式的道路矢量數據作為實驗數據，其中，線狀要素共15 791條，預處理后數據點總個數為50 717個。

2.1 零水印實驗

本文選用寫有“中大地規(guī)院”的二值圖像作為原始水印，大小為80×80，水印序列Wn的長度為800。對節(jié)點數據進行點約束分塊處理，初次分塊面積為總面積的1/4，點個數閾值P為5 000；道格拉斯算法提取特征點的閾值為500 m，共提取7 976個特征點，壓縮比為84.27%；通過構建Delaunay三角網以及角度序列與水印序列的異或運算，最終獲得18個分塊和32個零水印，可證本算法容量較大。本次實驗利用NC值與還原的零水印個數，綜合衡量該算法能否抵御各種常見的水印攻擊，其中NC值閾值設定為0.8。

(1)唯一性驗證

由于零水印并不直接添加到原始數據中，且數字水印必須是唯一的，因此需要檢驗本算法構造的零水印是否具有唯一性。檢驗方法是，選用廣州市天河區(qū)和越秀區(qū)的道路矢量圖作為對照，與海珠區(qū)道路矢量數據構造的零水印進行提取水印操作，結果如表1所示。作為對照的兩組數據NC值均小于閾值，即水印驗證失敗，本算法構造的零水印具有唯一性。

表1 零水印唯一性驗證結果Table 1 The result of zero-watermarking uniqueness verification

(2)幾何攻擊

幾何攻擊包括：平移、旋轉、縮放和裁剪等攻擊手段，是矢量地理數據的常見操作。由于矢量地理數據的中各要素的拓撲關系具有平移、旋轉、縮放不變性，本算法零水印是基于拓撲關系構造的，因此這3種攻擊手段對水印信息驗證沒有影響。對實驗數據分別裁剪25%(A1)，50%(A2)和75%(A3)，對裁剪后的數據提取水印，結果如表2所示。由于本文算法構建了多個零水印，且均勻分布于數據中，可有效抵御裁減攻擊。

(3)數據編輯攻擊

數據編輯攻擊包括：增加節(jié)點、刪除節(jié)點等攻擊手段。對實驗數據分別增加與刪除1 000個(B1、C1)、3 000個(B2、C2)和5 000個節(jié)點(B3、C3)，對編輯后的數據提取水印，結果如表2所示。隨著刪除點個數增加，NC值與還原的零水印數量有所下降，即部分特征點也被刪除，但由于本算法已構建Delaunay三角網，部分節(jié)點增加或刪除，只影響臨近的三角形，因此，本文零水印算法對數據編輯攻擊具有較強魯棒性。

(4)數據壓縮攻擊

道格拉斯算法是常用的數據壓縮方法，對實驗數據分別進行25%(D1)，50%(D2)和75%(D3)的壓縮攻擊，提取水印后，結果如表2所示。由于本文零水印算法設置了比正常壓縮程度更高的閾值，對數據壓縮攻擊具有很強的魯棒性。

(5)數據轉換攻擊

數據轉換攻擊包括數據投影轉換和數據格式轉換，其中數據投影轉換較為常用。實驗數據采用WGS-1984-UTM投影坐標，我國常用的坐標系包括CGCS2000坐標系、西安80坐標系(E1)和北京54坐標系(E2)，由于實驗數據所在區(qū)域WGS84坐標系與CGCS2000坐標系誤差極小，不具有實驗意義，故只對其余2個坐標系進行投影轉換檢驗，分別提取水印后，結果如表2所示。由于投影變換對數據點操作強度較大，造成NC值較低，但仍然大于0.8，可證本文零水印算法對數據轉換攻擊具有較強魯棒性。

(6)組合攻擊

組合攻擊是指對實驗數據同時使用多種攻擊手段的綜合性攻擊，由于攻擊手段未知，且同時進行攻擊，抵御難度較大。本實驗選取地圖綜合中的簡化路網作為組合攻擊，包括2個內容：去除實驗數據中的“環(huán)島”與匝道(F1)，并在此基礎上刪除部分低等級道路(F2)。進行上述操作后，分別有約2 000個和10 000個數據點被修改，提取水印后，結果如表2所示。根據實驗結果，本文零水印對組合攻擊具有一定魯棒性，但隨著攻擊強度增大，魯棒性有所下降。

表2 數據裁剪、編輯、壓縮、轉換攻擊和組合攻擊結果Table 2 The result of data cropping attack, editing attack, compression attack, transformation attack and combination attac

2.2 脆弱水印實驗

對節(jié)點數據進行點約束分塊處理，綜合考慮精確認證以及篡改數據定位的效率與精度，初次分塊面積為總面積的1/64，點個數閾值P為1 000。本算法采用零比特動態(tài)擴展，實現脆弱水印無損嵌入，具有良好的不可見性。為檢驗本算法的準確性，對已加入脆弱水印的實驗數據不作任何修改并進行精確認證，認證結果通過，可證算法具有可行性。

(1)增點攻擊

對加入脆弱水印的矢量數據增加1條包含10個節(jié)點的線要素，進行水印提取與驗證，增點攻擊沒有通過脆弱水印的精確認證，并有效檢測到新增的點要素，結果如圖3所示。由于增加的點要素不包含脆弱水印信息，因此，不能提取原始水印信息Wf，這是增點攻擊區(qū)別于其他攻擊的明顯特征；另外結合屬性信息中的重要字段等進行判別可起到輔助作用。

(2)刪點攻擊

對已加入脆弱水印的矢量數據刪除某段道路及其所有節(jié)點，進行水印提取與驗證，結果如圖4所示。刪點攻擊沒有通過脆弱水印的精確認證，并有效檢測到被刪除的點要素，標注出其前鄰點和后鄰點，達到水印抗刪除的預期效果。由于經過空間排序，被刪除點要素的前后鄰點并不一定是所在線要素的起點與末點，因此本實例具有兩個前鄰點與后鄰點，且空間上沒有關聯性。

(3)平移攻擊

對已加入脆弱水印的矢量數據進行整體平移與局部平移，并進行水印提取與驗證。平移操作實質上是對數據點的坐標進行修改，基于坐標值的原始水印信息也相應發(fā)生變化，因此，數據整體平移后，超過90%的點要素被標記；局部平移的點要素也被標記，如圖5所示。

圖3 增點攻擊結果Fig.3 The result of adding elements attack

圖 4 刪點攻擊結果Fig.4 The result of delecting elements attack

圖5 平移攻擊結果Fig.5 The result ofatranslation elements attack

3 結 論

本文基于矢量圖元節(jié)點數據，提出一種基于零水印與脆弱水印的多重水印算法，一方面將魯棒水印與脆弱水印相結合，利用零水印和無損嵌入技術解決了兩種不同性質水印互相干擾的問題，達到兼顧數據版權保護與精確認證的目的；另一方面，本算法對水印的提取與驗證，無需原始數據參與，是一種盲水印，具有較高實用性。根據水印的特點與功能，本算法進行不同尺度的數據分塊，結合道格拉斯算法和Delaunay三角網分別提取具有代表性的特征點和穩(wěn)定的特征信息，構造出容量大、安全性高的零水印，并對幾何變換、數據編輯、數據壓縮、數據轉換以及綜合攻擊具有較強魯棒性，可有效保護數據的版權；在精確認證方面，本算法利用空間排序的方法，建立各分塊內節(jié)點數據間較為穩(wěn)定的空間關系，并嘗試將脆弱水印與零比特動態(tài)擴展技術相結合，在確保水印信息對數據的精度與使用沒有造成任何影響的同時，對數據的真實性和完整性進行有效判別，能精確定位被篡改的部分數據到數據點，滿足實際應用需求。

由于將脆弱水印信息加入到坐標值末尾，本文算法與文獻[16-18]的算法均對精度約減攻擊抵抗較弱，水印可能會被整體破壞；另外，現有的精確認證算法還不能有效判別常見的攻擊類型。下一步研究工作的重點將放在選取更穩(wěn)定安全的脆弱水印嵌入方式，以及分析記錄常見攻擊類型的特征，希望有所收獲。