基于防重復嵌入雙水印的DEM完整性認證算法

許 惠，任 娜，朱 長 青

(南京師范大學虛擬地理環境教育部重點實驗室,江蘇 南京 210023;江蘇省地理信息資源開發與利用協同創新中心,江蘇 南京210023)

基于防重復嵌入雙水印的DEM完整性認證算法

許 惠，任 娜*，朱 長 青

(南京師范大學虛擬地理環境教育部重點實驗室,江蘇 南京 210023;江蘇省地理信息資源開發與利用協同創新中心,江蘇 南京210023)

針對脆弱水印無法證明自身存在性的問題以及為防止通過先篡改再嵌入水印的篡改抵賴行為，提出一種基于防重復嵌入雙水印的DEM完整性認證算法。該算法在水印嵌入前加入魯棒水印預檢測機制，若檢測到數據含有魯棒水印則無法繼續對數據進行任何水印嵌入操作；若無，則根據DEM數據特征將載體數據劃分為特征區域和非特征區域兩部分。其中，特征區域用于嵌入魯棒水印，由該部分數據生成的脆弱水印嵌入至數據的非特征區域。在水印檢測時，首先檢測魯棒水印的存在性，若無則直接判斷水印被破壞，說明數據不完整，若存在則繼續檢測脆弱水印的完整性，根據脆弱水印的檢測結果進一步判斷數據的完整性。實驗結果表明，該算法能夠有效防止水印的重復嵌入，同時完整性認證準確性良好。

數字高程模型；雙水印；完整性認證；防重復嵌入

0 引言

在信息技術迅速發展的大背景下，地理數據的經濟和社會效益得到越來越多的關注和重視，數據的可靠性及完整性問題已然成為一個熱門的研究課題。脆弱水印作為一種先進的數據完整性認證技術手段，目前已有眾多學者對其在地理數據完整性認證方面的應用進行了深入研究，但主要集中在矢量和遙感影像數據[1-11]，針對DEM數據完整性認證的脆弱水印算法則鮮少見刊。

將脆弱水印技術應用于矢量地理數據的完整性認證首見于1993年Cox所發表的文章[1]，但算法抗攻擊性較弱；為增強水印算法的抗攻擊能力，任娜等[2]通過建立數據點之間的空間位置關系實現了能夠抗要素刪除的矢量地理數據脆弱水印算法。通過對數據分組、分段能夠更加精確地定位篡改，鄭良斌等[3,4]將矢量數據進行分塊，并由對應的Hash值生成脆弱水印序列，嵌入到各分塊壓縮后的冗余空間中再整體替換原始序列，檢測時比較生成和提取的Hash序列即可判斷數據的完整性；李莎莎等[5]首先對數據進行分組，然后利用混沌系統生成脆弱水印信息嵌入到矢量數據的LSB中，有效增強了算法的安全性。王奇勝等[6]將基于數據點生成的脆弱水印信息嵌入到數據的坐標上，將魯棒水印信息嵌入到數據的坐標上，在數據更新和數據拼接等含有版權水印信息較少的情形中有效提高了水印檢測結果的可靠性和準確性。在遙感影像數據脆弱水印方面，Qin等[7]使用小波分析提出了一種基于邊緣特征的遙感影像數據的完整性認證算法；丁凱孟等[8]運用感知哈希實現了同樣基于邊緣特征的認證算法，通過對遙感影像進行格網劃分、提取單元格邊緣特征、用Hash函數對邊緣矩陣奇異值進行歸一化得到影像的感知哈希散列，比較接收與提取的感知哈希散列完成對影像數據的完整性認證；Caldelli等[9]、Ho等[10]、易小偉等[11]分別提出了基于JPEG-LS壓縮標準、固定正弦變換和圖像壓縮碼流的衛星遙感影像完整性認證算法。

以上基于脆弱水印的完整性認證方法主要側重于增強算法的抗攻擊能力、提高篡改定位的精度和認證的準確性，且均以待檢測數據已嵌入過脆弱水印為前提，在無法得知待檢測數據是否含有脆弱水印時，存在將未嵌入水印的數據和嵌入水印后遭受篡改的數據均認定為認證不通過而無法區分的問題。另一方面，在實際應用中，由于DEM數據生產者和使用者兩相分離，別有用心者可以通過先篡改含有脆弱水印的DEM數據，然后再次嵌入相同脆弱水印的方式抵賴其篡改行為，則使得對數據完整性認證的準確性大打折扣。

因此，本文針對DEM的數據特征，設計了一種能夠防止重復嵌入的魯棒與脆弱雙水印的完整性認證算法，能夠更加有效地認證DEM數據的完整性，并防止通過重復嵌入脆弱水印帶來的篡改抵賴行為。

1 算法思想

本文所提出的防重復雙水印算法是指對數據同時嵌入具有強魯棒性的魯棒水印和較優脆弱性的脆弱水印相結合的水印算法，其中，魯棒水印用來解決水印的防重復嵌入問題，脆弱水印用來解決數據的完整性認證問題，兩者相得益彰。具體來說即為：一方面，在向載體數據中嵌入脆弱水印之前，首先檢測該數據是否已含有魯棒水印，若無則依次嵌入魯棒和脆弱水印，若有則不再允許嵌入任何水印信息，保證數據能且只能被嵌入一次水印，達到防重復嵌入的目的；另一方面，脆弱水印的存在性可由魯棒水印間接證明，兩者同時嵌入，因此還可以增強脆弱水印完整性認證結果的可靠性。

綜上，可對所提出的防重復嵌入雙水印的算法思路進行如下描述：水印嵌入時，利用魯棒水印的魯棒性，首先向數據中嵌入魯棒水印作為載體數據已嵌入過水印的標記，當嘗試再次向含水印的數據中嵌入水印時，首先檢測出數據中魯棒水印的存在與否，已存在魯棒水印則無法再次嵌入任何水印信息，從而達到防重復嵌入的效果；然后在魯棒水印的基礎上嵌入脆弱水印。水印檢測時，依次檢測魯棒水印的存在性和脆弱水印的完整性，結合兩者檢測結果，綜合判斷數據的完整性。

2 算法設計與實現

2.1 水印信息生成與嵌入

水印的生成與嵌入分為脆弱水印和魯棒水印的生成與嵌入兩部分。其中，魯棒水印選用文獻[12]中基于映射和量化機制的DEM魯棒水印算法，并在此基礎上進行調整和改進。該算法不僅對各種針對DEM數據的攻擊具有強魯棒性，而且能夠很好地控制水印誤差，已得到了廣泛應用。脆弱水印使用MD5 Hash算法生成基于原始數據內容的脆弱水印信息，其對輸入的高敏感性、良好的單向性(不可逆性)和抗碰撞性的特點能夠有效增強算法的安全性。

根據前文分析可知，本算法水印嵌入的順序為先嵌入魯棒水印后嵌入脆弱水印，且水印嵌入前采取了魯棒水印預檢測的機制。算法的具體步驟如下：

(1)提取地形特征點。使用D8算法提取待嵌入水印DEM數據S的地形特征點，得到數據的特征區域S1和非特征區域S2，兩者符合如下關系式：

(1)

(2)檢測魯棒水印。由步驟(1)得到待嵌入水印DEM數據的特征區域，從該區域中檢測魯棒水印(具體檢測步驟見2.2節)，若不存在魯棒水印說明數據是還未嵌入水印的原始數據，跳至步驟(3)；若已存在魯棒水印則跳至步驟(5)，不再對該數據進行任何水印嵌入操作，從而可以有效防止水印的重復嵌入。

(3)嵌入魯棒水印。對還未嵌入任何水印的原始DEM數據，使用映射機制由數據的特征區域S1生成魯棒水印W_R；然后將魯棒水印信息W_R量化嵌入到數據的特征區域S1中，完成魯棒水印的嵌入：

(2)

其中，⊕表示魯棒水印嵌入規則。

(3)

提取DEM數據的非特征區域S2：

S2={S2i,i=1,2,…,64;S2i∈{0,1}}

(4)

2.2 水印檢測與完整性認證

水印信息的檢測是水印信息嵌入的逆過程。水印檢測和完整性認證同樣包括兩部分，分別是用于證明水印存在性的魯棒水印檢測和用于完整性認證的脆弱水印檢測。算法的具體步驟如下：

(2)魯棒水印檢測。首先，按照魯棒水印嵌入的逆過程提取魯棒水印信息W_R′；然后，由于本算法中水印信息無意義，故再次生成原始的魯棒水印信息W_R，計算其與提取出的魯棒水印信息W_R′之間的相關性，相關性檢測公式如式(5)所示[12]。

(5)

若相關系數小于閾值0.5,說明待檢測數據中不含魯棒水印，可直接判斷認證不通過；若相關系數大于閾值0.5,則跳至步驟(3)，進一步檢測數據中脆弱水印的完整性。

3 實驗與分析

對本文提出的算法進行驗證，實驗數據為一幅大小為509×515、分辨率為5 m、比例尺為1∶1萬、浮點型的柵格DEM數據(圖1)。從圖1可以看出，主觀視覺上很難察覺出載體DEM數據在水印嵌入前后的差異，說明本文算法嵌入雙水印后具有好的不可感知性。

圖1 嵌入水印前與嵌入水印后的DEM數據

Fig.1 The original and watermarked DEM data

圖2給出了水印嵌入前后的實驗數據在Matlab中的三維可視化效果圖(以數據圖像的灰度值為縱坐標填充高程值)。由圖2可觀察到，從主觀視覺上，嵌入水印前后對DEM三維可視化效果幾乎沒有差別。計算嵌入前后兩幅DEM數據的PSNR值為51.071，高于人眼可識別差異PSNR值范圍(35～40)。由此可見，本文算法實現了水印嵌入的不可見性要求。

圖2 原始DEM與含水印DEM的三維可視化效果

Fig.2 The 3D visualization renderings of the original and watermarked DEM

3.1 認證準確性與防重復嵌入實驗分析

針對DEM數據的一些常見修改操作，使用本文所提出的防重復嵌入雙水印算法進行完整性認證和防重復嵌入實驗，嵌入水印并經修改的實驗數據如表1所示。對表1中經不同篡改的含水印DEM數據進行完整性認證與防重復嵌入檢測實驗，結果如表2所示。從表2可以看出：1)經過一些常見攻擊后，提取的魯棒水印的相關系數均大于設置的閾值0.5，表明本文算法的魯棒水印對一定強度的攻擊具有較強的魯棒性；2)數據修改后，能夠有效鑒別出數據篡改，認證數據的完整性，表明本文算法的脆弱水印具有好的脆弱性；3)從防重復嵌入結果來看，本文算法嵌入水印后不可重復嵌入水印，說明算法能夠很好地防止水印的重復嵌入，與理論分析結果保持一致。

3.2 水印嵌入精度影響分析

(1)數據精度影響分析。表3顯示了水印嵌入前后DEM數據的高程最大/小值、平均高程值及高程標準差的統計結果。由表3可知，水印嵌入前后，DEM數據高程最小值沒有變化，高程最大值、平均高程值和高程標準差變化均為0.01 m，變化幅度較小。如此表明，水印的嵌入所帶來的數據誤差較小，對DEM數據統計學精度影響較小。

(2)應用精度影響分析。數據應用精度是評價DEM數據的另一重要指標，此處選取等高線和匯水線分析本文算法對DEM數據應用精度的影響，分別如圖3和圖4所示。從圖3 和圖4可以看出，從原始DEM和含水印DEM數據中提取出的等高線與匯水線吻合程度較高，本文算法水印的嵌入對DEM等高線與匯水線提取影響不大，能夠滿足DEM數據在等高線與匯水線提取方面的應用精度需求。

表1 不同篡改方式下的含水印DEM數據

Table 1 The watermarked DEM data under different modify ways

DEM數據暈渲效果圖

表2 認證準確性與防重復嵌入實驗結果

Table 2 The experimental results of certification accuracy and preventing re-embedding analysis

DEM數據編號修改方式魯棒水印相關系數認證結果防重復嵌入結果結果準確性圖1b不做修改0.978通過不可重復嵌入正確表1a高程平移(h+9)0.803不通過不可重復嵌入正確表1b高程縮放(h*10)0.796不通過不可重復嵌入正確表1c隨機噪聲[-5,5]0.555不通過不可重復嵌入正確表1d數據刪除(5%)0.765不通過不可重復嵌入正確表1e數據裁剪(25%)0.778不通過不可重復嵌入正確表1f部分替換(25%)0.815不通過不可重復嵌入正確

表3 水印嵌入前后DEM數據基本統計信息

Table 3 The basic statistical information of the original and watermarked DEM m

高程最小值高程最大值平均高程值標準差原始DEM894.561106.71993.8140.74含水印DEM894.561106.70993.8040.73

4 結語

本文針對DEM數據的地形特征，結合魯棒水印與脆弱水印各自的優點，設計了一種能夠防止重復嵌入的雙水印完整性認證算法,利用具有強魯棒性的魯棒水印間接證明脆弱水印的存在性，提高了完整性認證結果的可靠性；同時，在脆弱水印嵌入前采取的魯棒水印預檢測機制實現了水印的防重復嵌入，有效避免了通過先篡改再嵌入脆弱水印的篡改抵賴行為。對算法完整性認證和防重復嵌入兩方面的實驗分析結果表明，該算法能夠準確認證DEM數據的完整性并能有效防止水印的重復嵌入，且算法引起誤差較小、性能較優。

圖3 原始DEM與含水印DEM提取等高線結果對比

Fig.3 The comparison of extracted contours of the original and watermarked DEM

圖4 原始DEM與含水印DEM提取匯水線結果對比

Fig.4 The comparison of extracted stream networks of the original and watermarked DEM

[1] COX G S,DE JAGER G.A survey of point pattern matching techniques and a new approach to point pattern recognition[A].Proc.of South African Symposium on Communications and Signal Processing[C].1993.243-248.

[2] 任娜,吳維,朱長青.一種點約束分塊的矢量地理數據精確認證算法[J].地球信息科學學報,2015,17(2):166-171.

[3] 鄭良斌,賈玉祿,王群.用于矢量地圖完整性驗證的脆弱數字水印算法[J].計算機工程與應用,2010,46(26):99-101.

[4] ZHENG L,YOU F.A Fragile digital watermark used to verify the integrity of vector map[A].E-Business and Information System Security,EBISS′09[C].International Conference on.IEEE,2009.1-4.

[5] 李莎莎,王海榮,周衛,等.基于易碎水印的GIS矢量數據完整性認證方法[J].測繪通報,2013(11):101-105.

[6] 王奇勝,朱長青,符浩軍.利用數據點定位的矢量地理數據數字水印算法[J].測繪學報,2013,42(2):310-316.

[7] QIN Q,WANG W,CHEN S,et al.Research of digital semi-fragile watermarking of remote sensing image based on wavelet analysis[A].IGARSS′04.2004 IEEE International Conference on Geoscience and Remote Sensing Symposium[C].2004,4:2542-2545.

[8] 丁凱孟,朱長青.一種用于遙感影像完整性認證的感知哈希算法[J].東南大學學報(自然科學版),2014,44(4):723-727.

[9] CALDELLI R,MACALUSO G,BARNI M,et al.Joint near-lossless watermarking and compression for the authentication of remote sensing images[A].IGARSS′04.2004 IEEE International Conference on Geoscience and Remote Sensing Symposium[C].2004,1:297-300.

[10] HO A T S,ZHU X,WOON W M.A semi-fragile pinned sine transform watermarking system for content authentication of satellite images[A].IGARSS′05.2005 IEEE International Conference on Geoscience and Remote Sensing Symposium[C].2005,2:737-740.

[11] 易小偉,馬恒太,鄭昌文,等.基于有向圖構造的衛星遙感圖像認證算法[J].宇航學報,2014,35(5):581-589.

[12] 王志偉.DEM數字水印模型與算法研究[D].鄭州:解放軍信息工程大學,2011.

An Integrity Authentication Algorithm for DEM Based on the Preventing Re-embedded Double Watermarking

XU Hui,REN Na,ZHU Chang-qing

(Key Laboratory of Virtual Geographic Environment of Ministry of Education,Nanjing Normal University,Nanjing 210023;2.Jiangsu Center for Collaborative Innovation in Geographical Information Resource Development and Application,Nanjing 210023,China)

In this paper,a double watermarking based integrity authentication algorithm is proposed to prevent watermark being embedded repeatedly.The aim is to solve the problem that fragile watermarking cannot prove the existence of itself,and prevent the tampering repudiation behavior by tampering the watermarked data first and then embedding the same watermarking information again.The pre-detection mechanism of robust watermarking is performed before the watermarking is embedded,so that any kind of watermarking cannot be embedded if the robust watermarking is already detected in the carrier data.Otherwise,the carrier data was divided into two parts according to the data features,namely the feature region and the non-feature region.The feature region is used to embed robust watermarking and generate the fragile watermarking,which will be embedded into the non-feature region.During the watermarking detection,the existence of the robust watermarking is detected at first.If there is no the robust watermarking,it shows the watermarking is destroyed and the data is incomplete.Otherwise,the integrity of the fragile watermarking will be detected.The integrity of the data will be further determined by the detecting result of fragile watermarking.The experimental results show that the proposed algorithm is able to prevent the watermarking being embedded repeatedly and has good performance for the integrity certification.

digital elevation model;double watermarking;integrity authentication;preventing re-embedded

2015-06-15；

2015-12-21

國家社科基金重大項目(11&ZD162)；國家自然科學基金青年項目(41301413)；江蘇省自然科學基金青年項目(BK20130903);國家測繪地理信息公益性行業科研專項(201512021、201512019)

許惠(1991-)，女，碩士研究生，研究方向為空間數據安全。*通訊作者E-mail:renna1026@163.com

10.3969/j.issn.1672-0504.2016.01.007

P208

A

1672-0504(2016)01-0034-05