基于頂點(diǎn)排序的三維模型數(shù)字水印算法

翟 浩，楊 有，萬 輝

(1.重慶師范大學(xué)計(jì)算機(jī)信息與科學(xué)學(xué)院，重慶 401331;2.重慶師范大學(xué)科研處，重慶 401331)

基于頂點(diǎn)排序的三維模型數(shù)字水印算法

翟 浩1，楊 有1，萬 輝2

(1.重慶師范大學(xué)計(jì)算機(jī)信息與科學(xué)學(xué)院，重慶 401331;2.重慶師范大學(xué)科研處，重慶 401331)

提出一種基于頂點(diǎn)排序的三維模型多重?cái)?shù)字水印算法.算法的主要思想是首先將三維模型進(jìn)行定位、定向以及定型，將此狀態(tài)作為三維模型的初始狀態(tài);然后利用LSB的方法將水印信息多重循環(huán)嵌入到該三維模型中，以提高水印信息的魯棒性.實(shí)驗(yàn)結(jié)果表明，該算法針對平移、旋轉(zhuǎn)、全比例縮放和細(xì)分等攻擊具有很高的魯棒性，針對單比例縮放、剪切和簡化攻擊，魯棒性有待進(jìn)一步提高.該算法可以有效保護(hù)三維模型的版權(quán).

數(shù)字水印;三維模型;頂點(diǎn)排序;多重水印

1 本文算法

本文算法是將文字信息作為水印信息，而將三維模型作為嵌入載體.嵌入過程是首先將文字信息轉(zhuǎn)換成GB2312碼，得到二進(jìn)制信息，對二進(jìn)制信息采用異或加密.然后將三維模型的中心坐標(biāo)求出來，將三維模型的中心坐標(biāo)移至坐標(biāo)原點(diǎn)，以應(yīng)對平移變換，接著將三維模型的方向特征向量求出來，使該向量與Z軸一致，以應(yīng)對旋轉(zhuǎn)變換.接著將三維模型的中心坐標(biāo)到三維模型各頂點(diǎn)的平均距離求出來，以便將來對嵌入水印的模型進(jìn)行縮放修改，以使模型恢復(fù)到嵌入水印之前的狀態(tài).最后對三維模型的頂點(diǎn)根據(jù)原點(diǎn)到三維模型各頂點(diǎn)的距離進(jìn)行從小到大的排序，然后將已經(jīng)加密的二進(jìn)制信息多次循環(huán)嵌入到已排序的頂點(diǎn)上，嵌入水印信息之前加上0000 0000 0000 0000作為水印起始標(biāo)記，水印信息之后加上0000 0000 0000 0000作為水印結(jié)束標(biāo)記，并利用LSB的方法多次循環(huán)嵌入到該三維模型中.水印提取過程是首先將三維模型的中心坐標(biāo)求出來，通過平移變換，將三維模型的中心移至三維坐標(biāo)原點(diǎn).接著求出三維模型的方向特征向量，根據(jù)三角形的三角變換，進(jìn)行沿X軸、Y軸的對應(yīng)旋轉(zhuǎn)后，使該向量與Z軸一致，就達(dá)到了旋轉(zhuǎn)不變性的要求.然后求得三維模型的中心點(diǎn)到模型各頂點(diǎn)的平均距離，將此距離與嵌入水印前的平均距離相除，以求得縮放倍數(shù)，對帶有水印信息的三維模型按比例縮放，以達(dá)到縮放不變性.最后對三維模型按照中心點(diǎn)到模型各頂點(diǎn)的距離按從小到大的順序進(jìn)行排序，按照此順序依次從帶有水印信息的各頂點(diǎn)提取出多組水印信息，分別計(jì)算相關(guān)值，并取最大的相關(guān)值作為實(shí)驗(yàn)結(jié)果.水印檢測過程主要是根據(jù)相關(guān)值公式求得提取出來的二進(jìn)制信息和嵌入的二進(jìn)制信息的相關(guān)性，并通過閾值來判定提取出來的二進(jìn)制信息是否能證明該模型的所有權(quán).

1.1 水印嵌入過程

首先，根據(jù)GB2312碼將水印信息(這里取“翟浩”)轉(zhuǎn)換成二進(jìn)制數(shù)據(jù)，在對此二進(jìn)制數(shù)據(jù)與10進(jìn)行異或，從而得到加密的二進(jìn)制數(shù)據(jù).然后的工作就是獲取三維模型各頂點(diǎn)的橫坐標(biāo)、縱坐標(biāo)以及豎坐標(biāo)的坐標(biāo)信息.首先需要確定三維模型的中心坐標(biāo):

為了最大限度地恢復(fù)嵌入水印之前三維模型的狀態(tài)，需要對所有頂點(diǎn)進(jìn)行計(jì)算，并取其所有頂點(diǎn)坐標(biāo)的平均值，將此坐標(biāo)移回到坐標(biāo)原點(diǎn)，然后去求三維模型的方向特征向量:

將該三維模型沿Z軸旋轉(zhuǎn)α度，在沿Y軸旋轉(zhuǎn)β度，就使該三維模型的方向特征向量與Z軸

最后對三維模型的所有頂點(diǎn)按中心點(diǎn)到模型各頂點(diǎn)的距離從小到大進(jìn)行排序，對于距離相等的，則按X軸坐標(biāo)進(jìn)行從小到大排序;對于距離大小和X軸坐標(biāo)都相等的，則對Y軸坐標(biāo)進(jìn)行從小到大排序;對于距離大小、X軸坐標(biāo)、Y軸坐標(biāo)都相等的，則按Z軸坐標(biāo)進(jìn)行從小到大的排序.最終得到確定三維頂點(diǎn)的一維排序.最后將二進(jìn)制水印信息前面加上0000 0000 0000 0000作為水印起始標(biāo)記，尾部加上0000 0000 0000 0000作為水印結(jié)束標(biāo)記，利用LSB的方法多重循環(huán)嵌入到已排序的頂點(diǎn)上.

方向一致.接著求原點(diǎn)到3D模型各頂點(diǎn)的平均距離r1，為使將來提取水印信息時(shí)提供參考依據(jù)，以應(yīng)對縮放變換.

圖1 旋轉(zhuǎn)參考圖

1.2 水印提取過程

首先，需要做的是將三維模型恢復(fù)到嵌入水印信息前的狀態(tài)，這就涉及到對現(xiàn)有的三維模型進(jìn)行重定位.先求出含水印三維模型的中心坐標(biāo):

將該三維模型沿逆方向分別移動Xc'、Yc'、Zc'，使該三維模型的中心坐標(biāo)移至嵌入水印之前的位置，以抵抗平移攻擊.求出三維模型的方向特征向量:

從而求得三維模型的方向特征向量，然后根據(jù)圖1所示求得旋轉(zhuǎn)角度α，β.

將該三維模型沿Z軸旋轉(zhuǎn)α度，再沿Y軸旋轉(zhuǎn)β度，就使該三維模型的方向特征向量與Z軸方向一致;接著求該原點(diǎn)到三維模型各頂點(diǎn)的平均距離:

根據(jù)原始模型的平均距離r1和嵌入水印后三維模型的平均距離r2，還需要求出縮放倍數(shù)s:

s就是所謂的縮放倍數(shù)，對水印模型進(jìn)行縮放s倍，使水印模型盡可能恢復(fù)到嵌入水印之前的狀態(tài).最后對三維模型的所有頂點(diǎn)按原點(diǎn)到模型各頂點(diǎn)的距離從小到大進(jìn)行排序;對于距離相等的，則按X軸坐標(biāo)進(jìn)行從小到大排序;對于距離大小和X軸坐標(biāo)都相等的，則對Y軸坐標(biāo)進(jìn)行從小到大排序;對于距離大小、X軸坐標(biāo)和Y軸坐標(biāo)都相等的，則按Z軸坐標(biāo)進(jìn)行從小到大的排序.最終得到確定的三維頂點(diǎn)的一維排序.從已經(jīng)排序的頂點(diǎn)上依次提取出多組二進(jìn)制信息，并做記錄.計(jì)算每組數(shù)據(jù)的相關(guān)值，取最大的相關(guān)值作為實(shí)驗(yàn)結(jié)果.

1.3 水印檢測過程

水印檢測過程主要是進(jìn)行相關(guān)值的計(jì)算，通過相關(guān)值來確定模型所有者的版權(quán).

設(shè)定W'是提取出來的二進(jìn)制數(shù)據(jù)，W是原始二進(jìn)制數(shù)據(jù)，W'avg是W'序列中各位的平均值，Wavg是W序列中各位的平均值，N是水印序列總比特?cái)?shù).將隨機(jī)生成的二進(jìn)制數(shù)據(jù)與原始二進(jìn)制數(shù)據(jù)相關(guān)值的最大相關(guān)值設(shè)定為閾值.這里所說的隨機(jī)序列取得越多，取的閾值越精確.如果提取出來的二進(jìn)制數(shù)據(jù)與原始二進(jìn)制數(shù)據(jù)的相關(guān)值大于閾值，則可以證明模型所有者的版權(quán);否則，則不能證明.

2 實(shí)驗(yàn)結(jié)果

本算法是在Matlab2010和VC++6.0的環(huán)境下實(shí)現(xiàn)的，主要是針對Dolphin網(wǎng)格模型進(jìn)行實(shí)驗(yàn)，其中該模型共有211個(gè)頂點(diǎn)組成，水印信息是采用一維二進(jìn)制序列.水印檢測閾值的確定主要是根據(jù)相關(guān)值公式進(jìn)行.為了確定閾值，首先隨機(jī)生成1 000個(gè)二進(jìn)制的水印信息，與原始水印信息進(jìn)行比較，原始水印信息與隨機(jī)水印信息的最大相關(guān)值為0.42，于是設(shè)定閾值為0.45.原始Dolphin模型和嵌入水印的Dolphin模型如圖2所示.

圖2 嵌入水印前后的三維模型效果圖

實(shí)驗(yàn)中，首先對嵌入水印的三維模型進(jìn)行各種攻擊，包括平移攻擊、旋轉(zhuǎn)攻擊、全比例縮放攻擊、單比例縮放攻擊、剪切攻擊、細(xì)分攻擊以及簡化攻擊等.然后從已遭受攻擊的三維模型中提取水印信息，與原始水印信息進(jìn)行相關(guān)值計(jì)算.實(shí)驗(yàn)結(jié)果通過相關(guān)值的大小給出.

平移、旋轉(zhuǎn)和全比例縮放等攻擊后的測試結(jié)果如表1所示.此表包含攻擊類型和相關(guān)值兩列.該表中每項(xiàng)數(shù)據(jù)均是經(jīng)過三次實(shí)驗(yàn)，求平均值作為實(shí)驗(yàn)結(jié)果.從表1可以看出，該算法針對平移、旋轉(zhuǎn)和全比例縮放等攻擊具有較高的魯棒性.

單比例縮放、剪切、簡化和細(xì)分攻擊后的測試結(jié)果如表2所示.此表包含四大類攻擊類型，每類攻擊類型包含攻擊比例和相關(guān)值兩列.該表中每項(xiàng)數(shù)據(jù)都是經(jīng)過三次實(shí)驗(yàn)，然后求取平均值作為實(shí)驗(yàn)結(jié)果.從表中數(shù)據(jù)可以看出，此算法的魯棒性有待進(jìn)一步加強(qiáng).

表1 平移、旋轉(zhuǎn)、全比例縮放攻擊后的實(shí)驗(yàn)結(jié)果

表2 單比例縮放、剪切、簡化和細(xì)分攻擊后的測試結(jié)果

本文算法的實(shí)驗(yàn)結(jié)果與文獻(xiàn)［12］和文獻(xiàn)［13］算法的實(shí)驗(yàn)結(jié)果對比如表3所示.該表針對平移、剪切、旋轉(zhuǎn)、等比例縮放等攻擊的相關(guān)值來進(jìn)行實(shí)驗(yàn)結(jié)果的對比.從實(shí)驗(yàn)數(shù)據(jù)可以看出，本文算法針對以上各類攻擊都具有較好的魯棒性.

對于平移攻擊、旋轉(zhuǎn)攻擊、均勻縮放攻擊，由于本算法在對水印信息進(jìn)行采樣時(shí)會對檢測模型進(jìn)行重定位和重采樣，將遭到攻擊后的三維模型恢復(fù)到未攻擊之前的位置、方向以及大小，所以本算法針對這類攻擊基本上不受影響，水印幾乎可以完整提取出來.

表3 文獻(xiàn)［12］和文獻(xiàn)［13］算法的實(shí)驗(yàn)結(jié)果與本文算法的實(shí)驗(yàn)結(jié)果對比

對于單比例縮放攻擊，這里將Z軸進(jìn)行單比例縮放，縮放攻擊后的結(jié)果導(dǎo)致三維模型的一部分頂點(diǎn)與三維模型的中心點(diǎn)的距離發(fā)生了變化，導(dǎo)致嵌入的水印信息遭到一定的破壞，但即使遭到破壞，也遠(yuǎn)遠(yuǎn)超出實(shí)驗(yàn)中設(shè)定的閾值.

對于剪切攻擊，對三維模型剪切的比例分別為90﹪、80﹪、70﹪.對于每次的剪切攻擊，需要對三維模型進(jìn)行3個(gè)不同部位的剪切，然后取平均值作為該次剪切的實(shí)驗(yàn)結(jié)果.相對來說，本算法針對于剪切攻擊的效果不是十分理想，有待進(jìn)一步加強(qiáng).

對于細(xì)分攻擊，本算法體現(xiàn)的魯棒性還是很好的.每進(jìn)行一次細(xì)分，就會在相鄰的頂點(diǎn)之間的線上加上另外一個(gè)頂點(diǎn)，細(xì)分的次數(shù)越多，增加的頂點(diǎn)也會相應(yīng)增加.但從實(shí)驗(yàn)結(jié)果來看，相關(guān)值還是很高的.

對于簡化攻擊，會對三維模型的頂點(diǎn)數(shù)目分別簡化為原模型的90﹪、80﹪、70﹪，當(dāng)三維模型簡化到原模型的70﹪，該三維模型已經(jīng)變得相當(dāng)粗糙，基本上已經(jīng)接近失去應(yīng)用價(jià)值.但從三維模型提取出來的水印信息仍然遠(yuǎn)遠(yuǎn)高于設(shè)定的閾值.

從上述實(shí)驗(yàn)結(jié)果可以看出，本文提出的算法不受平移、旋轉(zhuǎn)以及均勻縮放等攻擊的影響，對于細(xì)分攻擊也具有較強(qiáng)的魯棒性.然而，對于單比例縮放攻擊、剪切攻擊以及簡化攻擊的魯棒性雖然遠(yuǎn)遠(yuǎn)超過了閾值，但卻不是很理想，有待進(jìn)一步研究.

3 結(jié)語

本文算法在嵌入水印信息時(shí)，通過對三維模型進(jìn)行定位、定向、定型，然后將水印信息加密后利用LSB的方法，多重循環(huán)嵌入到三維模型的頂點(diǎn)上.在進(jìn)行水印信息提取時(shí)，將遭到攻擊的三維模型進(jìn)行重定位、重定向以及重定型，然后依次從已排序的頂點(diǎn)上提取水印信息，并按照水印起始標(biāo)記和水印結(jié)束標(biāo)記依次提取多組水印信息，然后分別進(jìn)行相關(guān)值計(jì)算，取最大的相關(guān)值作為實(shí)驗(yàn)結(jié)果.本算法在提取水印過程中，不需要提供原始三維模型信息，屬于一種盲水印算法.實(shí)驗(yàn)結(jié)果表明，本文算法針對平移攻擊、旋轉(zhuǎn)攻擊、細(xì)分攻擊以及全比例縮放攻擊具有較高的魯棒性，但面對單比例縮放攻擊、剪切攻擊以及簡化攻擊，雖然求得的相關(guān)值遠(yuǎn)遠(yuǎn)超過設(shè)定的閾值，但其魯棒性卻不是十分理想.因此，提高針對于單比例縮放攻擊、剪切攻擊以及簡化攻擊的能力將是進(jìn)一步研究的重點(diǎn).

［1］彭靜，侯祥勇，馬燕，等.一種自適應(yīng)圖像灰度水印算法［J］.西南大學(xué)學(xué)報(bào):自然科學(xué)版，2009，31(7):171-175.

［2］Wang JR，F(xiàn)eng JQ，Miao YW.A robust confirmable watermarking algorithm for 3D mesh based on manifold harmonics analysis［J］.The Visual Computer，2012，28(11):1049-1062.

［3］Wang K，Guillaume L，Denis F，et al.Three-dimensionalmeshes watermarking:review and attack-centric investigation［J］.Information Hiding，2007，67(45):50-64.

［4］唐斌，康寶寶，王國棟，等.基于三維網(wǎng)格模型的雙重?cái)?shù)字盲水印算法［J］.計(jì)算機(jī)工程，2012，38(7):117-122.

［5］Wang Y P，Hu SM.A new watermarkingmethod for3D model based on integral invariants［J］.IEEE Transactions Visualization and Computer Graphics，2009，15(2):285-295.

［6］Wang Y P，Hu S M.Optimization approach for 3D modelwatermarking by linear binary programming［J］.Computer Aided Geometric Design，2010，27(5):395-404.

［7］劉曉寧，周明全.三維幾何模型數(shù)字水印綜述［J］.計(jì)算機(jī)應(yīng)用與軟件，2007，24(6):14-16.

［8］胡敏，劉輝.基于特征點(diǎn)的自適應(yīng)三維網(wǎng)格數(shù)字水印算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版，2010，33(1):55-59.

［9］胡敏，謝穎，許良鳳，等.基于幾何特征的自適應(yīng)三維模型數(shù)字水印算法［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2008，20(3):390-394.

［10］闕大順，胡金，陳碧.基于三維網(wǎng)格的三維模型盲數(shù)字水印算法［J］.武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2009，31(1):1-4.

［11］王新宇，詹永照.結(jié)合頂點(diǎn)趨勢檢測的三維模型數(shù)字水印算法［J］.計(jì)算機(jī)應(yīng)用，2011，31(10):2665-2669.

［12］齊敬敬，顧永軍，黨長青.一種三維網(wǎng)格模型的數(shù)字水印算法［J］.計(jì)算機(jī)仿真，2012，29(6):253-256.

［13］林克正，姚歡，卜雪娜.塊矢量拉普拉斯矩陣的三維模型數(shù)字水?。跩］.哈爾濱理工大學(xué)學(xué)報(bào)，2011，16(5):113-117.

(責(zé)任編輯 穆 剛)

Three-dimensionalmodel of digital watermarking algorithm based on vertex sort

ZHAIHao1，YANG You1，WAN Hui2
(1.College of Computer and Information Science，Chongqing Normal University，Chongqing 401331，China;
(2.Scientific Research Department，Chongqing Normal University，Chongqing 401331，China)

A multiple digitalwatermarking algorithm based on the three-dimensionalmodel of vertex sort is proposed and the algorithm has significance to protect the copyright of three-dimensionalmodel.Themain idea of the algorithm is that themodel should be located，directed and shaped with the purpose of getting the initial state of three-dimensionalmodel.Then in order tomaximum improve the robust ofwatermark information，multiple cycle embed the binary watermark information in the three-dimensionalmodel using the way of LSB.Experimental results show that the algorithm own a high robustness for translation，rotation，and uniform scaling attacks.For shear attack，simplification attack and single scaling，its robustness need to be further improved.

digital watermarking;three-dimensionalmodel;vertex sort;multiple watermarking

TP312

A

1673-8004(2014)05-0128-06

數(shù)字水印技術(shù)是目前防偽及信息安全技術(shù)領(lǐng)域的一個(gè)新方向，它可以對各種形式的多媒體數(shù)字作品(圖像、視頻、音頻等)的版權(quán)進(jìn)行保護(hù)，即是通過在原始數(shù)據(jù)中嵌入秘密信息——水印來證實(shí)該數(shù)據(jù)的所有權(quán)［1］.隨著采集設(shè)備和加工技術(shù)的快速發(fā)展，三維模型被廣泛應(yīng)用于影視、3D游戲和文化財(cái)產(chǎn)的保護(hù).在這期間，未經(jīng)授權(quán)的復(fù)制、修改和傳播已經(jīng)變得越來越普遍.人們正面臨著嚴(yán)峻的三維模型版權(quán)保護(hù)問題，這個(gè)問題在計(jì)算機(jī)圖形學(xué)和多媒體中也是一個(gè)重要的課題［2］.因此，基于信息隱藏理論的三維模型數(shù)字水印技術(shù)被提出來，該技術(shù)展示了對版權(quán)保護(hù)和所有權(quán)認(rèn)證的有效方法［3］.

三維模型數(shù)字水印算法的概念自從1997年由Obuchi在ACM multimedia97國際會議上提出來以后，便開啟了三維模型數(shù)字水印技術(shù)的時(shí)代.第二年，以O(shè)hbuchi為首的研究人員，提出了具有時(shí)代意義的水印算法［4］:三角形相似四元組算法、四面體體積比算法.根據(jù)不同的目的和應(yīng)用，水印算法可以被分為魯棒水印算法和脆弱水印算法.魯棒水印算法通常是為所有者認(rèn)證設(shè)計(jì)的，而脆弱水印算法［5，6］通常是為完整性認(rèn)證設(shè)計(jì)的.目前，三維模型的水印算法可以分為空域水印算法和頻域水印算法［7］.頻域算法雖然魯棒性比空域算法高，但其復(fù)雜度較高，執(zhí)行時(shí)間較長，而且嵌入容量較小.胡敏等［8］提出了一種自適應(yīng)網(wǎng)格水印算法，該算法按模長進(jìn)行分組，將每組模長進(jìn)行DCT變換，然后在頻域上嵌入水印信息，該算法有效解決了局部失真的問題.空域算法大多通過直接或間接修改模型坐標(biāo)來嵌入水印信息，復(fù)雜度較低，嵌入容量較大，但魯棒性不是很高.2008年，胡敏等人提出了一種基于幾何特征的自適應(yīng)三維模型數(shù)字水印算法［9］.該算法將各頂點(diǎn)鄰域內(nèi)的頂點(diǎn)位置的平均差值作為掩蔽因子嵌入水印信息，可以抵抗幾何攻擊和抵抗部分剪切、附加隨機(jī)噪聲和網(wǎng)格簡化的攻擊.闕大順等［10］提出了一種三維網(wǎng)格模型的數(shù)字水印算法，該算法在提取水印時(shí)要求網(wǎng)格頂點(diǎn)序號與原始水印頂點(diǎn)序號完全一致，極大地提高了網(wǎng)格頂點(diǎn)的識別概率.王新宇等［11］提出了一種新的結(jié)合頂點(diǎn)趨勢檢測的三維模型數(shù)字水印算法，該算法選擇體現(xiàn)三維模型整體形狀信息的頂點(diǎn)范數(shù)嵌入水印，通過比較待檢測模型與原始模型頂點(diǎn)范數(shù)的變化關(guān)系，以變化趨勢為依據(jù)，實(shí)現(xiàn)水印信息的檢測.由于越靠近模型中心的頂點(diǎn)在遭到破壞時(shí)模型的失真率越高，上述算法都沒有充分利用三維模型的自身特性.于是，一種基于頂點(diǎn)排序的三維模型多重?cái)?shù)字水印算法在本文被提出來，該算法充分利用三維模型的自身特性，做到算法實(shí)現(xiàn)簡單，復(fù)雜度低，針對各類水印攻擊都具有較好的魯棒性.

2014-01-30

重慶市教委科研項(xiàng)目(KJ120611);重慶師范大學(xué)橫向科研項(xiàng)目(60102000148).

翟浩(1987-)，男，山西大同人，碩士研究生，主要從事數(shù)字水印和信息隱藏技術(shù)方面的研究.

楊有(1965-)，男，重慶人，副教授，博士，主要從事數(shù)字圖像處理、信息安全與系統(tǒng)集成方面的研究.