歡迎登錄中國視覺網!
學術論文頻道
ACADEMIC PAPERS
位置導航:首頁 >> 學術論文 >> 技術前沿 >> 矢量地圖的無損數據隱藏算法

矢量地圖的無損數據隱藏算法

發布時間:2020-04-15     來源:中國視覺網       訪問次數:2270


   摘  要:在矢量地圖中隱含水印信息,地圖數據的質量往往由于水印的嵌入而受到影響。可逆水印技術(又稱無損數據隱藏)具有完整恢復載體數據的能力,因而更加適用于矢量地圖。本文基于差值擴大的思想,提出了一種應用于矢量地圖的無損數據隱藏算法。算法根據矢量地圖對數據精度的特殊要求提出了相應的水印嵌入條件,并通過修改地圖中相鄰頂點坐標間的差值來嵌入水印信息。水印的提取過程不僅能夠得到隱藏信息,而且能夠準確無誤的恢復原始地圖數據。實驗結果表明算法具有較高的信息載荷(約0.58 bit/vertex),其應用前景包括矢量地圖數據的篡改鑒別、元數據格式兼容以及基于矢量地圖的隱藏通信。

   摘  要:矢量地圖;無損數據隱藏;差值擴大;信息載荷

1 引 言

   隨著地理信息系統的廣泛應用,數字矢量地圖在分發和使用過程中存在的諸如版權保護、篡改鑒別等數據安全問題日益凸顯出來。數字水印技術被引入到矢量地圖數據中,成為解決此類問題的重要輔助手段[1-4]。但是,水印數據的嵌入不可避免的會給原始地圖數據帶來擾動,在一定程度上降低了地圖數據的質量。可逆水印技術又稱為無損數據隱藏,是指能夠完整恢復原始載體數據的水印算法。該技術主要應用于原始載體數據不容篡改的場合,如醫學影像和用于法庭證據的數據。由于矢量地圖的應用環境比較嚴格,通常希望避免對原始地圖數據的任何改動,因此可逆水印技術對于矢量地圖數據具有很強的適用性。目前可逆水印技術的研究主要集中在柵格圖象領域,主要的方法包括利用可逆模加[5]、無損壓縮[6]、改變直方圖[7,8]和差值擴大[9]來實現算法的可逆性,針對二維矢量數據的可逆算法研究則較少受到關注。M. Voigt等人通過改變原始矢量地圖數據的整數DCT系數來隱含水印信息[10],這也是目前公開發表的關于二維矢量圖形可逆水印算法的僅有的一篇文獻。該算法存在的主要缺陷是水印嵌入對含水印地圖數據造成的擾動過大。國內也有人進行矢量地圖水印算法的研究工作[11-15],但尚未見到有關可逆算法的討論。

   差值擴大法[9]是由J. Tian提出的一種用于柵格圖象的可逆水印算法。本文借鑒該算法的實現思想,提出了一種矢量地圖空間域無損數據隱藏算法。矢量地圖數據與柵格圖象數據在應用環境上的區別決定了在這兩類數據之中嵌入水印信息必須遵循不同的嵌入原則。柵格圖象水印需要保證圖象的視覺質量,而矢量地圖水印則關注數據精度。本文根據矢量地圖對數據精度的嚴格要求提出了采用差值擴大法嵌入水印的條件,通過對地圖中滿足嵌入精度條件的相鄰頂點的坐標差值進行移位操作,在不損失原始信息的情況下為水印數據提供額外的存儲空間。算法的實質是利用了地圖臨近頂點坐標數據具有較強相關性的特點。當隱藏的水印信息被提取出來之后,原始地圖數據能夠得到無損的恢復。

2 差值擴大技術

   差值擴大技術由J.Tian提出,用于在數字圖象中實現無損數據隱藏,其基本思想可以歸結為:針對具有較強相關性的原始載體數據中的相鄰數據點和(原始數據均為整數),首先用一組可逆變換來分別計算二者的差值和整數均值,即

   其中表示向下取整。載體數據的相關性意味著大多數情況下和的取值比較接近,因此其差值通常比較小。在一定的誤差范圍內,通過將值擴大為原來的倍(即左移位),即可為待隱藏的數據提供比特的冗余空間。將帶有隱藏數據的差值記為,結合原先的整數均值,含水印數據可以通過逆變換[公式(2)]得到。差值擴大算法用于無損數據隱藏具有兩個主要的優點:首先,由于值本身較小,因此水印嵌入引入的誤差較小;另外,由逆變換可知,每個差值上引入的誤差()將由兩個數據點和共同承擔,因此每個數據點所承受的誤差比較均勻。

3 矢量地圖的無損數據隱藏方案

   由前文分析可見,差值擴大技術在本質上是利用了原始數據的相關性來為隱藏數據提供存儲空間。大多數自然圖像數據具有強相關性的特點,即臨近像素通常具有相近的灰度值。而矢量地圖元素(多邊曲線和多邊形)是由大量密集的頂點按照特定的順序排列而成的,地圖數據就是這些頂點的二維坐標序列。在同一地圖元素中,頂點的密集性使得大多數相鄰頂點的位置十分接近,坐標數據間的差值也很小。地圖坐標數據體現出的這種強相關性使得差值擴大技術能夠應用于二維矢量地圖的無損數據隱藏。

3.1 頂點分組變換與嵌入精度條件判斷

1)頂點分組變換

   一幅原始地圖必然由點、線段、多邊曲線和多邊形四種類型的元素構成。點元素只包含一個頂點,因此不能用作數據隱藏。對于其他類型的每一個元素,首先進行頂點分組。以一個元素為例,假設該元素所包含的頂點表示為,將所有頂點按照先后順序,每相鄰兩點作為一組,則該元素的頂點被劃分為。對原始地圖中除點元素以外的所有元素都采用上述方法進行分組,則原始地圖中絕大多數相鄰頂點都兩兩組合為“頂點對”。假設其總數為,則其中任意一組可以表示為:

   其中和為構成該組的兩個頂點,而和分別是這兩點的二維坐標。接下來對每組中的兩個頂點,分別計算其橫、縱坐標的差值和整數均值,即

   要在原始地圖的橫坐標(縱坐標)中隱藏信息,只需要將差值擴大技術應用到差值序列中。即對中符合條件的數據向左移位,并將空出來的數據位用于存放待隱藏的信息。

2)嵌入精度條件

   通常矢量地圖數據都有各自的精度誤差容限(記為),當地圖坐標數據受到的擾動低于時,不會影響地圖的可用性。因此,水印嵌入所引入的坐標誤差通常也應該小于。在這個限制下,并不是所有的坐標差值和都適合進行移位操作的,必須滿足一定的嵌入精度條件。本文僅考慮差值擴大2倍(即左移一位)的情況,假設當前需要將水印數據位嵌入到“頂點對”的橫坐標中,則數據嵌入后對應的差值變為:

? 經過無損壓縮后的數據。在水印提取階段,當隱含的水印信息被提取出來之后,為進一步恢復原始地圖數據,必須知道哪些“頂點對”在水印嵌入時采用了差值擴大法,因此標志數據需要成為隱含水印信息的一部分,以供數據恢復階段使用。

? 水印嵌入時,差值序列中對應為1的元素將用差值擴大的方式來隱含水印數據,而對應為0的元素將采用直接替換最不顯著位(LSB)的方式來存儲水印信息。因此,為保證算法的可逆性,這些原始的LSB數據必須保存下來以供數據恢復時使用。就是差值序列中所有對應為0的元素的LSB組成的數據。和一樣,它經過無損壓縮后,也作為水印數據的一部分。

? 有效信息載荷。根據水印系統所需完成的功能,可以是原始地圖數據的數字摘要(用于篡改鑒別),或者是地圖元數據(用于地圖格式兼容),也可以是用戶需要傳輸的信息(作為一種隱藏通信方式)。

? 一些額外的控制數據,用于將前述三類數據合理的組織起來以構成完整的水印數據。

   如果原始地圖劃分的“頂點對”的總數為,則最終生成的水印數據的長度也為,記為。算法的實際有效信息載荷為:

其中表示二進制長度。

   是由水印數據直接替換的最低位得到的,因此為得到,需要將的最低位還原成相應的原始值,式中為中的索引。得到原始差值序列后,結合整數均值序列,即可通過式(2)完全恢復原始地圖數據。因此,本算法為無損的數據隱藏算法。

4 實驗結果

   將本算法應用于多種不同特征的矢量地圖,都取得了較好的效果。圖1是實驗所用原始地圖的一種。該圖為我國河流分布圖,比例尺為1:400萬,總共包含頂點數目為252000個,地圖坐標數據為精確到小數點后六位的小數。由于本算法適用于整數,因此實驗前需先將所有數據乘以轉換成整數坐標。實驗地圖的精度誤差容限為Km。為增加有效的信息載荷,本文在地圖橫、縱坐標中均隱藏數據,盡管含水印地圖的部分頂點的誤差超過了誤差容限,但由于本算法能夠完全恢復原始地圖數據,因此并不影響地圖的使用價值。實驗中的有效隱藏信息包含三個部分,分別是原始地圖的MD5哈希值(128 bits)、地圖元數據(10998 bits)、和一幅的灰度圖象(135424 bits,見圖2),這三部分數據分別用于原始地圖的篡改檢測、元數據格式兼容和隱藏通信。

   圖3為包含隱藏信息的地圖,可以看到算法沒有對地圖引入過大的擾動。圖4為提取的水印圖象,圖5為恢復后的原始地圖,MD5哈希值的比較可以證明該圖與原始地圖完全相同。算法的實際信息載荷為146550 bits,平均約為0.58 bit/vertex。

5 結 論

本文提出了一種應用于矢量地圖數據的無損數據隱藏算法。由于矢量地圖的應用環境比較嚴格,不允許隨意改動數據,因此數據隱藏的可逆性對于矢量地圖水印具有十分重要的意義。基于差值擴大的思想,本算法利用地圖相鄰頂點坐標的相關性,將隱藏信息嵌入到地圖數據的橫、縱坐標中。算法引入的擾動比較小,而且能夠完全恢復原始地圖數據。算法的有效信息載荷約為0.58 bit/vertex,通常能夠容納原始地圖的數字摘要、元數據、以及一定長度的秘密信息,從而能夠實現對原始地圖數據的篡改鑒別、元數據格式兼容以及基于矢量地圖的隱藏通信。算法的缺陷是地圖頂點的擾動方向沒有考慮原始地圖的形狀特征,因此在充分放大的地圖中,這些擾動使地圖具有不自然的外形特征。使算法具有更好的形狀保持特性和更高的有效信息載荷是我們正在進行的工作。

參 考 文 獻

[1]  Ohbuchi R, Ueda H, Endoh S. Robust watermarking of vector digital maps[C]. in Proc of IEEE International Conference on Multimedia and Expo(ICME ’02), Lausanne, Switzerland, Augest 26–29, 2002, vol 1, pp 577–580.

[2]  Voigt M, Busch C. Feature-based watermarking of 2d-vector data[C]. in Proceedings of SPIE, Security and watermarking of Multimedia Content, vol 5020, Santa Clara, USA, 2003, pp 359–366.

[3]  Nikolaidis N, Pitas I, Solachidis V. Fourier descriptors watermarking of vector graphics images[C]. in Proceedings of International Conference on Image Processing, Vancouver, BC, Canada, September 10–13, 2000, vol 3, pp 9–12.

[4]  Li Y Y, Xu L P. A blind watermarking of vector graphics images[C]. in Proceedings of Fifth International Conference on Computational Intelligence and Multimedia Applications, (ICCIMA 2003), Xi’an, P.R. China, Sept.27–30 2003, pp 424-429.

[5]  Honsinger C W, Jones P, Rabbani M, et al. Lossless recovery of an original image containing embedded data[P]. US patent applicat, Docket No 77 102/E-D, 1999.

[6]  Fridrich J, Goljan J, Du R. Invertible authentication[C]. Proceedings of SPIE 2001, Security and Watermarking of Multimedia Content, San Jose, CA, Jan 2001, 3971: 197-208.

[7]  Ni Z, Shi Y Q, Ansari N, et al. Reversible data hiding[C]. Proceedings of International Symposium on Circuits and Systems (ISCAS 2003), Bangkok, Thailand, May, 2003, (2): 912-915.

[8]  Leest A, Veen M, Bruekers F. Reversible image watermarking[C]. IEEE Proceedings of ICIP’03, September 2003, (2):731-734.

[9]  Tian J. Reversible watermarking by difference expansion[C]. Proceedings of Workshop on Multimedia and Security, Dec 2002, 19-22.

[10]  Voigt M, Yang B, Busch C. Reversible watermarking of 2d-vector data[C]. in Proceedings of the 2004 multimedia and security workshop on Multimedia and security, Sept 2004, 160-165

[11]  周旭, 畢篤彥. 基于中國剩余定理的GIS數字水印算法[J]. 中國圖形圖像學報, 2004, 9(5):611-615

[12]  王勛, 林海, 鮑虎軍. 一種魯棒的矢量地圖數字水印算法[J]. 計算機輔助設計與圖形學學報, 2004, 16(10): 1377-1381.

[13]  李媛媛, 許錄平. 用于矢量地圖版權保護的數字水印[J]. 西安電子科技大學學報(自然科學版), 2004, 31(5): 719-723

[14]  胡云, 伍宏濤, 張涵鈺, 等. 矢量數據中水印系統的設計與實現[J]. 計算機工程與應用, 2004, 40(21): 28-30

[15]  張海濤, 李兆平, 孫樂兵. 地理信息水印系統的開發[J]. 測繪通報, 2004, 5: 42-44


喜乐彩什么时候开奖