基于數字指紋的矢量地理數據幾何脫密算法

王 宇 璇,閆 浩 文*,張 黎 明,王 小 龍

(1.蘭州交通大學測繪與地理信息學院,甘肅 蘭州 730070;2.地理國情監測技術應用國家地方聯合工程研究中心,甘肅 蘭州 730070;3.甘肅省地理國情監測工程實驗室,甘肅 蘭州 730070;4.甘肅大禹九洲空間信息科技有限公司院士專家工作站,甘肅 蘭州 730070;5.蘭州大學資源環境學院,甘肅 蘭州 730000)

0 引言

面對矢量地理數據在安全保護與共享應用之間的突出矛盾,目前主要采用幾何精度脫密的方法進行處理[10,11]。幾何精度脫密是指遵照《基礎地理信息公開表示內容的規定(試行)》《公開地圖內容表示若干規定》等[12,13],對較高密級的涉密版數據添加位置擾動,降低空間精度,從而降低地理信息成果密級[14]。現有幾何精度脫密算法主要包含投影變換[15]等線性脫密算法和多項式變換、三角函數等非線性脫密算法[16,17]以及線性與非線性結合的混合算法[18]三大類,大多可依據脫密要求降低位置精度,實現對數據空間位置的安全保護。雖然幾何精度脫密可通過添加位置擾動弱化矢量地理數據的位置敏感性,但脫密后數據并非“無密可保”,其價值依然存在,若在使用時被非法傳播,脫密數據的可持續性將遭到破壞[19],故研究能在完成脫密的同時又可保護脫密數據版權的脫密算法,對保障矢量地理信息成果的安全共享具有重要意義。因此,本文提出一種可溯源的幾何精度脫密算法,以期在降低空間精度、保證脫密結果共享的前提下,實現對脫密數據泄露者進行溯源,從而達到保護脫密數據版權的目的。

1 研究方法

1.1 研究思路

幾何精度脫密的實質是通過建立原數據坐標與目標坐標之間的一對一映射關系[20],使原數據的坐標發生偏移,空間精度降低,從而保證原數據的空間位置信息安全。為在完成脫密的同時實現對脫密矢量地理數據的版權保護,本文研究思路包括以下3個關鍵步驟,具體流程如圖1所示。

圖1 總體思路流程圖

1)脫密算法構建。指紋嵌入數據可使其空間位置發生一定偏移[21],降低數據的隱蔽性。利用可控誤差的數字指紋嵌入算法[22],調整指紋信息嵌入時的誤差大小,在矢量地理數據中嵌入指紋信息,對數據的空間位置坐標進行隨機誤差干擾,可達到幾何精度脫密的目的。本文使用改進后的歸一化量化索引調制(Quantization Index Modulation,QIM)算法[23]嵌入指紋以實現數據脫密,并通過調整步長使誤差達到脫密精度要求。

2)脫密數據版權保護。數字指紋[24,25]可以對分發用戶進行跟蹤及追溯,將數字指紋技術作為本文脫密算法的模型基礎,可在滿足幾何精度脫密的條件下實現對脫密矢量地理數據的版權保護,當脫密數據被泄露時,可利用其中的數字指紋追溯到泄露用戶。本文采用容納用戶多、編碼效率高的GD-PBIBD(Group Divisible Partially Balanced Incomplete Block Design)編碼[26,27]構建數字指紋序列。

3)脫密算法評價。脫密后數據的空間方向關系、拓撲關系等仍需與原數據保持較高一致性,才能滿足脫密數據的共享性需求,故從精度評價、圖形形態相似性、方向關系一致性及拓撲關系一致性四方面[28]定量評價脫密算法,并驗證該算法可在應用脫密數據時對盜版者進行溯源,實現對脫密數據的版權保護。

1.2 基于數字指紋的幾何脫密算法

本文幾何脫密算法構建的核心思想為:基于抖動量化調制的思想[22]在矢量地理數據的X、Y坐標上嵌入指紋編碼,使數據精度發生改變,從而完成幾何精度脫密,主要包括指紋編碼和幾何脫密兩大模塊。

M=(mij)=[MOD(i×j,s)]i,j∈[0,s-1]

(1)

(2)

式中:Tk由T0的所有列向左循環移位k次得到。

(3)

Q=[M0|M1|M2|…|Ms-1]

(4)

式中:“|”表示矩陣的水平拼接,Mb為構建新索引矩陣Q的中間數組。

在工業化和城市化加快發展的進程中，人類向自然水體排放的生產和生活廢水越來越多，自然地表和地下水體受到越來越嚴重的污染，一些自然水體已經喪失了供水功能。在這樣的背景下，如果水權只是規定水量而不限定水質，很可能水權賦予的水量被污染而不能利用，所謂水權就失去了意義。因應現實的情況改變，水權的界定不但需要限定水量，還需要限定水質。只有這樣，才能保障水權權益，才能保證正常的用水秩序。

(5)

式中:b,c∈{0,1,…,s-1},j∈{0,1,…,s2-1}。

Tij=[J?J?Hi在第j個位置?…?J]

(6)

式中:J為大小為s×s2的全一矩陣,i,j∈[0,s2-1],“?”表示矩陣的垂直拼接。

2)幾何脫密。脫密的具體步驟如下:①讀取矢量要素圖層,獲取空間數據坐標值,并將坐標值存為坐標集V=[Vx(i),Vy(j)],其中i,j為正整數且i+j=N,N為要素層數據總坐標個數;②使用線性映射的最大值最小值歸一化方法對坐標數據進行歸一化,以使隨機干擾誤差范圍變小,增加精度控制的穩定性,通過歸一化處理將坐標值(x,y)映射到區間[0,1],得到(x′,y′)(式(7));③計算歸一化后坐標值所對應的指紋編碼索引位dx(式(8));④運用QIM方法將指紋嵌入坐標值(以x坐標值為例,y值同理)中(式(9));⑤反歸一化后得到脫密后的矢量地理數據,脫密完成。

(7)

dx=x′%len(F)

(8)

式中:F為指紋編碼,len(F)為指紋編碼的長度,x、y為坐標值。

(9)

式中:R為量化步長,F[dx]為二值偽指紋序列。

2 實驗

2.1 實驗數據及流程

為驗證本文算法在不同比例尺、數據量和復雜度下是否都能完成脫密,采用3幅不同比例尺的線要素shapefile格式的矢量地理數據作為實驗數據(圖2),其坐標投影系統為WGS-84高斯投影坐標系,3幅矢量數據分別包含7 850、23 854、52 663個點,數據量和復雜度逐次遞增。

圖2 實驗數據

實驗使用Python 3.7編碼實現,實驗環境:處理器為AMD R9 5900HS,CPU為3.10 GHz,運行內存為16 GB,操作系統為64位的Windows 10。實驗流程為:首先構建數字指紋,以參數s=3,q=3構建碼長為b=sq=27,可容納n=s2q-2=81個用戶的GD-PBIBD編碼;其次嵌入指紋完成脫密,嵌入時的步長根據脫密要求精度進行調整,本實驗假設脫密精度Δ=10 m、50 m、100 m(設置10 m已滿足現文件的脫密精度規定,設置50 m、100 m是為了與先前脫密算法[28]進行對比),完成脫密的數據以shapefile格式輸出并可視化,數據a、b、c的完整脫密過程的運行效率分別為0.53 s、0.69 s和0.78 s;最后根據評價指標對脫密算法性能及脫密數據質量進行定量評價,并驗證該脫密算法可在應用脫密數據時完成對泄露者的追蹤。

2.2 實驗結果分析

1)脫密精度評價。脫密精度是數據從較高密級脫密至較低密級的坐標偏差要求,完美的脫密結果期望所有經過脫密算法處理的點與原數據點的坐標偏移量都達到誤差要求(即大于等于脫密精度Δ),但由于誤差干擾的隨機性,誤差呈帶狀波動,所有數據點的最小偏移量達到誤差要求可能會導致最大偏移量過大,所以采用點位中誤差達到誤差要求(RMSE≈Δ)的標準評估精度。統計3幅數據在不同脫密精度要求下,脫密后不同點位偏移量的點數Ua、Ub、Uc(表1),并繪出不同脫密精度下所有數據點位偏移量的總點數統計圖(圖3)。圖3顯示,絕大多數點的坐標偏移量與脫密精度Δ相近,點數大致符合以脫密精度為軸呈正態分布的規律,說明脫密后的絕大多數點達到脫密精度,根據點位偏移量計算脫密后數據的中誤差(表2)可知,脫密后數據的中誤差滿足設定的要求,證明該算法滿足脫密需求,精度控制效果較穩定,誤差隨機且波動范圍較小,可以保證數據在使用時的共享安全性。由不同脫密精度要求下脫密前后局部效果對比(圖4)可以看出,對于不同復雜度的矢量數據,該脫密算法均可降低幾何精度,隨著脫密精度增加,脫密后數據的位置精度逐漸降低,與原數據的位置偏離逐漸變大。

表1 不同脫密精度要求下的點位偏移量統計

表2 不同脫密精度要求下脫密后數據的中誤差

圖3 不同脫密精度要求下的點位偏移量統計

圖4 脫密前后局部效果對比

2)脫密數據可用性評價。現有脫密算法評價多使用“目視識別法”與“圖片比對法”進行定性評價,僅有李安波等[28]采用定量評價算法對脫密算法效果進行評價,因此,本文選取文獻[28]算法與本文算法進行對比(表3)。由表3可知,在圖形形態相似性、方向關系一致性、拓撲關系一致性方面本文算法均表現更好。隨著脫密精度增加,各項一致性數據呈現緩慢下降趨勢,這說明為保證共享性,應根據地圖數據的覆蓋范圍調整脫密精度,大區域使用較大的脫密精度,小區域使用較小的脫密精度;脫密后的數據保留了矢量地理數據要素間的幾何與拓撲特征,未破壞原數據的空間關系,數據質量較高,可滿足使用需求,且數據的可用性較好。

表3 不同脫密精度要求下的一致性評價對比

3)溯源泄露者驗證。以脫密后的實驗數據a為例,隨機確定數據使用者的數量(W≤81),并假設脫密數據者中泄露數據的用戶有w個,提取這w份可疑數據中的數字指紋,并在分發指紋庫中用漢明距離進行比對查找,漢明距離最小者即為泄露者。從實驗結果(表4)可以看出,該脫密算法可成功溯源到數據泄露者,無遺漏和誤判,說明該脫密算法的版權保護效果較好,可在脫密數據共享時保障數據安全,維護了脫密數據的可持續性。

表4 溯源泄露者實驗結果

3 結束語

本文脫密算法利用可控誤差的數字指紋實現矢量地理數據的幾何精度脫密。經實驗驗證,本文脫密算法結果滿足脫密要求,并實現了脫密后數據使用時的版權保護,且位置擾動效果較穩定,能較好保持原矢量地理數據的空間方向關系與拓撲關系,在脫密數據使用時如有非法泄露,可根據數字指紋溯源追蹤到泄密者,以保證矢量地理數據的共享安全性。但目前針對脫密算法性能及脫密數據質量尚無系統的定量評價方案,故后續研究將關注脫密算法定量評價方案的設計。