一種三維工程圖可逆水印算法

李 黎,趙 涵,方曉君

(杭州電子科技大學圖形圖像研究所,浙江杭州310018)

0 引 言

目前圍繞CAD模型本身的相關研究很少,而且大多也只停留在多邊形網(wǎng)格模型上。3D網(wǎng)格數(shù)字水印研究進展[1]一文中對變換域方面的研究作了很好的總結(jié)。2004年提出了基于球面參數(shù)化的三維網(wǎng)格模型水印算法[2、3]。這些三維網(wǎng)格模型水印算法原始數(shù)據(jù)不可恢復。本算法借鑒圖像可逆水印算法[4],利用差值擴大法通過對Solidworks三維工程圖的適當預處理來提高載體數(shù)據(jù)的冗余空間,然后將水印信息和標志位分別嵌入頂點小數(shù)部分的不同位置,實現(xiàn)了水印的盲提取,原始工程圖數(shù)據(jù)能夠完全恢復。

1 差值擴大法簡介

差值擴大法是用于二維圖像的可逆水印算法[5]。其基本思想可以歸結(jié)為:針對原始載體兩個數(shù)據(jù)點x1和x2(原始數(shù)據(jù)均為整數(shù)),首先用一組可逆變換來分別計算二者的差值d和整數(shù)均值m,即:

這組變換是可逆的,其逆變換為:

在一定誤差范圍內(nèi),通過將d值擴大為原來的2i倍(即左移i位),即可為待隱藏的數(shù)據(jù)提供i比特的冗余空間。將帶有隱藏數(shù)據(jù)的差值記為d′結(jié)合原先的整數(shù)均值m,含水印數(shù)據(jù)可以通過逆變換式2得到。

2 Solidworks三維工程圖的可逆水印算法

2.1 提高Solidworks三維工程圖冗余信息

具體通過以下兩個方法對Solidworks三維工程圖數(shù)據(jù)增加冗余空間。

(1)Solidworks三維工程圖中頂點坐標默認保留小數(shù)點后8位有效數(shù)字,將小數(shù)部分擴展為8個頂點。以某頂點x坐標為例(x=18.233 959 95),擴展為8個頂點(x1=2,x2=3,x3=3,x4=9,x5=5,x6=9,x7=9,x8=5)。水印嵌入后將上述8個頂點按順序還原成一個頂點(18.233 959 95)。考慮到工程圖的透明性,頂點整數(shù)部分未被用于水印嵌入,其值在水印嵌入前后保持不變。在Solidworks三維工程圖草圖中增加頂點。

(2)在工程圖草圖原有線段或曲線上添加一條樣條曲線,使新的樣條曲線與原有線段或曲線重合,然后將原有線段或曲線上的幾何關系,轉(zhuǎn)移到新添加的多頂點樣條曲線上,最后刪除原有線段或曲線。繪制新線段或曲線時可以增加適當頂點來提高信息冗余量。

2.2 選取適用于水印嵌入的頂點

排除Solidworks三維工程圖中心線、基準面上頂點,及頂點小數(shù)部分第5、6或第7、8位連續(xù)兩位值為9的點,按照x、y軸坐標從大到小的順序依次選取草圖中頂點。假設符合上述條件的頂點為{v1,v2,v3,v4,…}。以橫坐標為例,任意一個xi可擴展為8位}將擴展后的頂點分別組合為頂點對。其中)}用于水印嵌入,}用于對應標志位嵌入。

2.3 確定水印對應的標志位

2.4 水印嵌入算法

差值擴大算法用于Solidworks三維工程圖具有兩個主要的優(yōu)點:第一,當d值本身較小時,水印嵌入引入的誤差也較小;第二,由逆變換可知,每個差值上引入的誤差(d′-d)將由兩個數(shù)據(jù)點x1和x2共同承擔,因此每個數(shù)據(jù)點所承受的誤差比較均勻。水印嵌入過程具體分為以下幾個步驟。

(1)通過2.2節(jié)的方法選取頂點,{v1,v2,v3,v4,…}為符合要求的頂點。

(2)增加Solidworks三維工程圖草圖中的頂點。

(3)在草圖中去除這些頂點的幾何、拓撲關系(固定、重合、垂直等)。

(4)以橫坐標為例,假設flag=1的數(shù)目為S。flag=1對應的{)}中的頂點對使用差值擴大技術嵌入水印Wi。方法如下所示:和mi通過式2進行逆變換,即可得到含水印的橫坐標數(shù)據(jù)。縱坐標嵌入水印方法完全相同。

原始差值末位不再另外保存。頂點原始數(shù)據(jù)小數(shù)部分前4位可完全恢復,后4位不能恢復。

2.5 水印提取算法及數(shù)據(jù)恢復

水印的提取是水印嵌入的逆過程,本文算法中,由于水印信息和對應的標志位信息采用不同的嵌入方法,在水印的提取過程中先提取標志位信息,再提取水印信息。具體步驟如下:

再結(jié)合整數(shù)均值mi,即可通過式2完全恢復原始Solidworks三維工程圖頂點原始數(shù)據(jù)。fi=0頂點數(shù)據(jù)無需變化?？v坐標水印提取、恢復方法與模坐標完全相同。

3 實驗結(jié)果

為驗證本文算法的有效性,選擇hydraulic圖來測試水印的可逆性?？捎庙旤c數(shù)為176個(11×8×2)。為增加信息冗余量,本文在每兩個頂點之間增加一個點頂點?？捎庙旤c數(shù)為304個(19×8×2)。水印嵌入前后草圖如圖1所示,水印嵌入之前和之后的三維工程圖hydraulic clamp如圖2所示。

圖1 原始草圖與水印嵌入后的草圖

圖2 原始工程圖與嵌入后的工程圖

實驗結(jié)果表示,本算法具有較好的透明性。另外solidworks三維工程圖受平移、旋轉(zhuǎn)和縮放等攻擊后,頂點坐標的值不改變,所以水印對該種類型的攻擊具有很好的魯棒性。

4 結(jié) 論

本文針對solidworks三維工程圖數(shù)據(jù)精度高的特點提出基于差值擴大法的可逆水印算法。由于solidworks三維工程圖不允許數(shù)據(jù)隨意改動,因此數(shù)據(jù)隱藏的可逆性具有十分重要的應用意義。通過水印嵌入之前的預處理提高數(shù)據(jù)的冗余量,實驗結(jié)果表明本算法水印具有較好的透明性,能夠抵抗平移、旋轉(zhuǎn)和縮放攻擊,而且能夠完全恢復精度范圍內(nèi)數(shù)據(jù)。將來的工作還需進一步提高算法的強壯性。

[1] 張新宇,彭維,張三元.3D網(wǎng)格數(shù)字水印研究進展[J].計算機輔助設計與圖形學學報,2003,15(8):913-920.

[2] Li Li,David Zhang,Zhigeng Pan.Watermarking 3D mesh by spherical parameterization[J].Computers&Graphics,2004,28(6):981-989.

[3] 潘志庚,孫樹森,李黎.三維模型數(shù)字水印綜述[J].計算機輔助設計與圖形學學報,2006,8(4):1 103-1 110.

[4] 邵承永,王孝通,徐曉剛.矢量地圖的無損數(shù)據(jù)隱藏算法研究[J].中國圖象圖形學報,2007,12(2):206-211.

[5] Tian J.Reversible water marking by difference expansion[C].Barcelona Spain:In Proceedings of IEEE international conference on Image Processing,2003,13(8):731-736.