一種基于矢量要素存儲順序的水印方法

吳國梁，張 黎，高 翔

（1.重慶市地理信息中心，重慶401121）

一種基于矢量要素存儲順序的水印方法

吳國梁1，張 黎1，高 翔1

（1.重慶市地理信息中心，重慶401121）

提出了一種基于矢量要素對象存儲順序的數字水印方法。利用算術編碼技術，將水印信息隱藏在矢量對象的存儲順序中，實現了對數字水印的嵌入與提取。實驗表明，該算法不會改變數據的幾何精度，具有較好的透明性，對裁剪﹑縮放﹑平移﹑旋轉﹑坐標轉換等攻擊具有較好的魯棒性。

矢量要素；存儲順序；數字水印

隨著信息技術的發展和大數據時代的到來，數據的加密﹑認證﹑防偽和版權保護等越來越為人們所重視。數字水印就是一種能夠攜帶版權保護信息和認證信息的數字產品版權保護技術[1]。由于易復制﹑修改和再傳輸等特性，測繪地理信息成果電子數據的管控比傳統紙質數據更加困難[2]，通過嵌入數字水印來標識成果數據，不失為一種好的管理方法。目前保護矢量數據的數字水印技術，主要包括基于坐標點的算法﹑基于變換域的算法﹑基于地圖劃分的算法和基于坐標點排序劃分的算法等，如基于灰度圖像的矢量數據水印算法﹑LSB算法等[3-5]。這些算法要么改變了矢量對象的空間坐標，降低了數據精度；要么難以抵御縮放﹑旋轉﹑坐標轉換等方法的攻擊，實用性不強[3,6]。本文提出了一種基于矢量要素對象存儲順序的數字水印嵌入和提取方法，在不降低數據精度的情況下，能有效抵御裁剪﹑縮放﹑平移﹑旋轉﹑坐標轉換等攻擊，具有較好的安全性和實用性。

1 水印方法設計

1.1 基本原理

首先利用算術編碼技術把要嵌入的水印信息轉換為一個整數N，確定最少需要的元素個數M，進行全排列，并找出序號為N的元素的具體排列順序；再按坐標大小對矢量數據對象進行排序，按M對數據對象進行分組，根據序號為N的元素的排列順序對每組數據對象的存儲順序進行調整，從而實現水印信息的嵌入。水印信息提取時，先按坐標大小對數據對象進行排序，通過與原始數據對象的存儲順序進行比較，提取水印單元和具體的數據對象排列順序；再推算出排列序號N；然后利用算術編碼技術對N進行譯碼，從而提取出水印信息。

本文以在一幅標準的1∶500矢量數字地形圖中嵌入和提取“重慶測繪質檢”的水印信息為例，說明該算法的實現過程。

1.2 水印的嵌入

1）采用算術編碼方法將水印信息表示為0～1的一 個間隔，即將“重慶測繪質檢”字符串編碼成[0,1]區間上的一個浮點小數。符號序列越長，編碼表示它的間隔越小，這一間隔所需的位數就越多。為了簡化計算，假設各字符的概率分布如表1所示。根據假設的概率分布，水印字符的編碼過程如表2所示。

表1 水印字符的概率分布

表2 水印的編碼過程

2）令(M-1)!＜31 042＜M!，易得M=8，選取8個元素(A1,A2,A3,A4,A5,A6,A7,A8)進行全排列，排列順序如表3所示。

下面計算序號31 042的具體排列，方法步驟為：

①建立一個數組a[0]=A1, a[1]=A2,a[2]=A3, a[3]= A4, a[4]=A5, a[5]=A6, a[6]=A7, a[7]=A8，共8個元素；②31 042-1=31 041，計算31 041/(8-1)！，商為6，余數為801，所以排列的第一個元素為a[6]=A7；③ 去掉A7，將a[6]后面的元素依次向前移動一位，得到一個新的數組a[0]=A1, a[1]=A2, a[2]=A3, a[3]=A4, a[4]=A5, a[5]=A6, a[6]=A8，共7個元素；④計算801/ (7-1)！，商為1，余數為81，所以排列的第二個元素為a[1]=A2；依此類推，可計算得到序號31 042對應的排列順序為(A7,A2,A1,A6,A4,A5,A8,A3)。

表3 元素排序

3）讀入待嵌入水印的矢量數字地形圖文件，并根據數據對象坐標的大小進行排序，計為V (V1, V2, …,V8, …,VD)。

①根據水印信息31 042的計算，需要8個數據對象的空間關系才能完整描述清楚，所以取出一個水印單元S (V1, V2,…,V8)∈V(V1, V2,…,V8,…,VD)，(V1,V2,…, V8)與(A1,A2,…,A8)分別對應，其存儲順序調整為(V7,V2,V1,V6,V4,V5,V8,V3)；②循環步驟①，直至剩余數據對象不足一個水印單元為止。

4）將調整存儲順序后的數據對象寫入文件中，即完成了水印的嵌入。嵌入水印前后數據對象存儲順序對比如圖1所示。

圖1 水印嵌入前后數據對象的存儲順序對比

1.3 水印的提取

1）讀入已嵌入水印的地形圖數據，記錄其原始對象順序信息V ′(V ′1,V ′2,…,V ′M,…,V ′D)，根據對象的坐標大小進行排序，得到V(V1,V2,…,VM,…,VD)。

2）比較V與V ′兩個數列，若含有水印信息，則兩個數列存在明顯有規律的對應關系，可據此提取水印單元S。

3）以水印“重慶測繪質檢”為例，一個水印單元包含8個數據對象S(V1,V2,…,V8)，數據對象按坐標大小排列記為(A1,A2,A3,A4,A5,A6,A7,A8)，可以推出V1=A7,V2=A2,…,V8=A3，從而得到水印單元的排列為(A7,A2,A1,A6,A4,A5,A8,A3)。

4）由排列(A7,A2,A1,A6,A4,A5,A8,A3)推算其排列序號。①排列逆數。排列中某元素序號后面小于它的元素序號個數稱為它的逆數。A2元素后面只有A1的序號比它小，因此其逆數為1，同理A4元素后面有A3序號比它小，其逆數為1，依此類推排列(A7,A2,A1,A6,A4,A5,A8,A3)的逆數為（6,1,0,3,1,1,1,0）。②排列的權序。在1，2，3，4，5，6，7，8個數字組成的全排列中，定義第n個數字的權序是(8-n)!，所以任何一個排列的權序都是(7!，6!，5!，4!，3!，1!，0!)。③排列的序號N =權序×逆數+1。N=(6,1,0,3,1,1,1,0)×(7!，6!，5!，4!，3!，1!，0!)+1 = 6×7!+1×6!+0×5!+3×4!+1×3!+1×2!+1×1!+0×0!+1= 31 042。

5） 根據算術編碼，水印信息31 042恢復為0.310 42。0.310 42的譯碼過程如表4所示。水印的提取過程如圖2所示。

表4 譯碼過程

圖2 水印提取過程

2 實驗結果及分析

本文用于嵌入水印的地形圖共包括122個多邊形﹑2 436條多線段﹑1 017個文字﹑1 834個塊參照，水印信息為字符串“重慶測繪質檢”。

2.1 幾何精度

圖3為原始地形圖與嵌入水印后地形圖的疊加，可見兩個圖層的數據完全重合，地形圖的幾何精度無損，因此本文的水印算法在視覺上是透明的。

圖3 嵌入水印前后的地形圖套合效果

2.2 魯棒性

水印的魯棒性是指對矢量地圖數據進行常規的攻擊處理操作后，仍能保持水印被正常提取[7]。通過地圖裁剪﹑幾何變換﹑隨機噪聲等攻擊對水印信息帶來的干擾，分析水印算法的魯棒性，實驗結果如表5所示。可以看出，水印算法對常規的地圖攻擊方式，如裁剪﹑平移﹑旋轉﹑縮放﹑隨機噪聲﹑隨機增點﹑格式轉換等的魯棒性較高。

表5 水印算法魯棒性統計

3 結 語

基于矢量要素對象存儲順序的數字水印算法，將水印信息與矢量數據對象空間關系特征相結合，通過調整矢量數據對象的存儲順序，避免了對對象坐標的調整，保證了數據精度不受影響。由于數據對象空間關系不變的特征，所以該算法對縮放﹑平移﹑坐標轉換﹑旋轉等攻擊具有較好的魯棒性。該算法可廣泛用于矢量空間數據的版權認證﹑追蹤，特別適合對精度要求嚴格的矢量數據嵌入水印。

[1] 陳明奇,紐心忻,楊義先.數字水印的研究進展和應用[J].通信學報,2001,22(5):71-79

[2] 吳金海,林福宗.基于數字水印的圖像認證技術[J].計算機學報,2004,27(9):1 153-1 161

[3] 王云飛,趙婧,王拓,等.一種抗幾何變換攻擊的矢量數據盲水印算法[J].計算機工程,2013,39(1):136-139

[4] 高會軍,劉文霞,暴軒,等.一種基于LSB算法的數字水印改進技術[J].現代電子技術,2009(13):86-88

[5] 吳海濤,詹永照.數字水印技術綜述[J].軟件導刊, 2015,14(8):45-49

[6] 吳柏燕,李朝奎,王偉,等.一種面向地圖對象的矢量地圖數字水印方法[J].地理信息世界,2011(2):45-52

[7] 李強,閔連權,吳彬,等.一種實用的矢量地圖數據盲數字水印解決方案[J].測繪工程,2010,19(4):65-67

P208

B

1672-4623（2017）09-0016-03

10.3969/j.issn.1672-4623.2017.09.005

2017-02-24。

項目來源：重慶市規劃局2016年重點決策應用咨詢和科技成果推廣應用資助項目。

吳國梁，工程師，主要研究方向為測繪地理信息成果質檢、測繪地理信息標準化、城市規劃等。