吳國梁，張 黎，高 翔

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

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

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

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

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

矢量要素；存儲順序；數(shù)字水印

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

1 水印方法設(shè)計

1.1 基本原理

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

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

1.2 水印的嵌入

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

表1 水印字符的概率分布

表2 水印的編碼過程

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

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

①建立一個數(shù)組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，余數(shù)為801，所以排列的第一個元素為a[6]=A7；③ 去掉A7，將a[6]后面的元素依次向前移動一位，得到一個新的數(shù)組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，余數(shù)為81，所以排列的第二個元素為a[1]=A2；依此類推，可計算得到序號31 042對應(yīng)的排列順序為(A7,A2,A1,A6,A4,A5,A8,A3)。

表3 元素排序

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

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

4）將調(diào)整存儲順序后的數(shù)據(jù)對象寫入文件中，即完成了水印的嵌入。嵌入水印前后數(shù)據(jù)對象存儲順序?qū)Ρ热鐖D1所示。

圖1 水印嵌入前后數(shù)據(jù)對象的存儲順序?qū)Ρ?/p>

1.3 水印的提取

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

2）比較V與V ′兩個數(shù)列，若含有水印信息，則兩個數(shù)列存在明顯有規(guī)律的對應(yīng)關(guān)系，可據(jù)此提取水印單元S。

3）以水印“重慶測繪質(zhì)檢”為例，一個水印單元包含8個數(shù)據(jù)對象S(V1,V2,…,V8)，數(shù)據(jù)對象按坐標大小排列記為(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)推算其排列序號。①排列逆數(shù)。排列中某元素序號后面小于它的元素序號個數(shù)稱為它的逆數(shù)。A2元素后面只有A1的序號比它小，因此其逆數(shù)為1，同理A4元素后面有A3序號比它小，其逆數(shù)為1，依此類推排列(A7,A2,A1,A6,A4,A5,A8,A3)的逆數(shù)為（6,1,0,3,1,1,1,0）。②排列的權(quán)序。在1，2，3，4，5，6，7，8個數(shù)字組成的全排列中，定義第n個數(shù)字的權(quán)序是(8-n)!，所以任何一個排列的權(quán)序都是(7!，6!，5!，4!，3!，1!，0!)。③排列的序號N =權(quán)序×逆數(shù)+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） 根據(jù)算術(shù)編碼，水印信息31 042恢復(fù)為0.310 42。0.310 42的譯碼過程如表4所示。水印的提取過程如圖2所示。

表4 譯碼過程

圖2 水印提取過程

2 實驗結(jié)果及分析

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

2.1 幾何精度

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

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

2.2 魯棒性

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

表5 水印算法魯棒性統(tǒng)計

3 結(jié) 語

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

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

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

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

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

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

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

[7] 李強,閔連權(quán),吳彬,等.一種實用的矢量地圖數(shù)據(jù)盲數(shù)字水印解決方案[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。

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

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