一種基于分塊DCT變換的三維網格模型半脆弱水印算法*

徐 濤，羅中良，陳志芳，蔡彬滔

(惠州學院計算機科學系，廣東 惠州 516007)

數字水印技術為多媒體信息安全領域的一個研究熱點方向，在圖像水印方面已有不少專家學者進行了研究探討[1-3]，近年來該技術開始推廣到三維網格模型領域[4-6]，而脆弱水印技術則為三維網格模型數字水印領域的一個新的研究重點方向。網格模型脆弱水印可分為完全脆弱水印和半脆弱水印兩類。前者可以檢測出任何對網格數據進行的破壞，而后者則允許水印可抵抗一定程度的非惡意數據破壞。在完全脆弱數字水印方法研究方面，Yeung等[7]提出了三維網格模型的首個脆弱水印算法，通過調整索引表中的頂點為“有效”或“無效”來嵌入水印，對網格非法篡改具有較高的敏感性，但篡改定位只能反映在抽象的二維平面映射圖中；Chou等[8]在直角坐標中選中一批標記頂點(Mark Vertex)讓它們與其鄰域頂點之間維持一種預定義的約定關系來實現水印嵌入，具有較高的篡改敏感性，但對于篡改的位置只能給出一組可疑頂點的輸出序列。而在半脆弱數字水印方法方面，Wu等[9]提出的半脆弱水印算法將頂點與一環鄰域質心的矢量長度值選作水印嵌入對象，可容忍RST相似變換處理，對于篡改位置算法能給出可視化定位標識；Cho等[10]提出的算法將原始網格分解為粗糙網格和一組小波系數，將選中的一幅標志圖像(Logo Pattern)作為半脆弱水印嵌入到粗糙網格中，可容忍RST相似變換處理，篡改定位只能反映在標志圖像的改動上，缺乏直觀性；Lin等[11]對Yeung的算法做出了改進，擴大了頂點的容忍改動范圍，可容忍網格頂點坐標值量化處理，但對RST相似變換缺乏容忍能力；Chou等[12]提出的算法將半脆弱水印嵌入到模型面片的子集中，使它們與鄰接的頂點保持預先定義的關系，只能容忍模型的RST相似變換。

由于半脆弱水印能夠對惡意數據破壞和正常數據處理加以區分，因此具有更廣泛的應用范圍，而現階段對網格模型半脆弱水印方法研究偏少。本文提出一種基于新的三維網格模型半脆弱水印算法，可定位出模型的被篡改位置。

1 網格模型半脆弱水印算法設計要求

如何正確區分來自侵權者的惡意攻擊和來自用戶方的正常數據處理成為算法設計的一個必要前提條件，從目前三維網格模型的應用情況來看，至少以下幾種數據處理應當視為非惡意攻擊：RST相似變換，包括模型的平移、旋轉和各向一致縮放處理，它們不會對模型的外觀視覺質量造成影響；低強度的頂點坐標值量化處理，為了節省網絡帶寬，可采用取整量化方法適當降低頂點坐標的浮點數精度，不應視為惡意攻擊；低強度的噪聲污染，模型經由網絡傳播復制過程中，幾何數據可能會造成輕微噪聲污染。但應當指出的是，頂點坐標值量化處理和噪聲的強度應控制在模型“內容保持”的范圍內，超出許可尺度時則應視為惡意攻擊。

2 半脆弱水印嵌入算法描述

模型的旋轉極易造成水印提取時出現不同步，因此本文采用了主元分析對網格模型進行校準預處理；另一方面，對于半脆弱水印來講，需要將水印信號均勻、完整的覆蓋到整個模型，因此算法要對模型進行均勻分塊處理，每個分塊用于隱藏一位半脆弱水印信號。

2.1 網格模型PCA校準和分割預處理

主元分析(Principal component analysis，簡稱為PCA)用于模型的校準定位預處理，其過程可描述如下：首先求出網格模型M的質心Vc，將質心位置設為三維笛卡爾直角坐標系的原點，對頂點坐標進行修正預處理，然后計算模型頂點的協方差矩陣，然后構造旋轉矩陣R，對頂點集V中的各頂點進行坐標變換，得到姿態調整后的頂點集Vr和網格模型Mr。通過對網格模型做主元分析預處理，可有效的解決網格旋轉帶來的影響，在三維網格模型數據檢索領域有著廣泛應用[13]，在三維網格模型數字水印領域亦可以用來解決水印的同步性問題，即不論是對原始模型嵌入水印，還是對待測的疑似篡改模型提取水印，都要首先對其進行主元分析預處理，將模型調整為同一姿態，這樣可使得水印信號被同步嵌入和提取。

為了使半脆弱水印可以均勻的覆蓋到模型的各個部位，需要將模型按頂點的拓撲連通關系均勻分割成若干分塊，這里我們采用了Metis軟件包作為分割算法軟件，它可以將模型網格模型按指定的塊數進行快速、均勻的分塊(分塊效果如圖1所示)。

圖1 網格模型Metis分塊效果Fig.1 Mesh partitioned effects by Metis

2.2 塊內頂點DCT變換和半脆弱水印嵌入

將原始模型進行主元分析校準預處理，并采用Metis軟件分割成s塊后，在每個分塊內進行直角坐標空間到球面坐標空間的轉換。即計算各頂點在以網格質心為原點的球面坐標系中的坐標值，包括半徑r、經度角θ、緯度角φ。

每個分塊內的頂點球面坐標的半徑r值被分成一組序列，以第i個分塊為例，可記為ri,1,ri,2,ri,3,.....ri,m，其中m為第i個分塊內頂點的數目，將每個分塊內的半徑值序列進行一維DCT變換，每個分塊可得到一組長度和塊內頂點數目相同的DCT系數序列A，將每一組DCT系數序列取絕對值后，按從小到大的順序排好序，為了使模型的失真最小，選擇最小的三個DCT系數的絕對值作為水印載體，以第i個分塊為例，從小到大的這三個系數依次記為αi,1,αi,2,αi,3。

采用密鑰key生成一組長度為s(與模型的分塊數目相同)，由1、0組成的偽隨機二進制序列w作為嵌入用的半脆弱水印序列，每個模型分塊用于隱藏一位水印，以第i個分塊為例，水印的嵌入按式(1)方法進行。

(1)

各分組修改完畢后，按組內各元素原始位置和排序后位置之間的對應關系重新進行調整，得到修改后的DCT系數絕對值序列，然后參照原始序列A校對正負符號，得到嵌入水印后的DCT系數序列A′，與原始序列A相比，A′的各位元素正負符號一致，但由于嵌入水印的緣故，某些元素的幅值出現了少量變動。接下來將嵌入水印后的DCT系數序列A′進行DCT逆變換，得到組內模型各頂點嵌入水印后的半徑r值，依據先前記錄下的經、緯度角參數轉換回直角坐標，得到該分塊嵌入后的頂點直角坐標。每個分塊依次執行上述步驟后，得到嵌入半脆弱水印后的三維模型Mw。

3 半脆弱水印提取算法與篡改定位方法描述

水印提取時無需原始網格參與，當懷疑模型被非法篡改時，將待測模型按前述的分塊數目s進行Metis分塊，重復前述嵌入水印的過程，每個分塊內將待測模型的半徑r值序列進行DCT變換，然后對DCT系數取絕對值后排序，最終可得到s組隱藏水印信號的三元組，在每一個三元組內提取半脆弱水印信號，以第i組為例，按式(2)的規則提取二進制水印序列。

(2)

以原始密鑰key生成原始水印w，與提取出的水印w'逐位進行匹配，當出現匹配錯誤時，意味著該位對應的網格分塊被篡改，記錄下該分塊的編號，水印全部匹配完畢后，將有問題的網格分塊以高亮的形式顯示標記，用戶即可確認篡改位置所在。

4 實驗結果與比較

為了測試本文所提半脆弱水印算法的性能，在VC++和 OpenGL平臺上對上述算法進行了編程實現，實驗采用的標準測試模型為Bunny(35 947個頂點，69 451個三角形面片)、ManFace(16 374個頂點，32 744個三角形面片)和Happy Buddha(543 652個頂點，1 087 716個三角形面片)，嵌入的半脆弱水印為一組以密鑰key生成，由1、0組成的二進制偽隨機序列，水印序列的長度與模型分塊的數目相同。在實驗結果和分析部分，分別從水印透明性、水印容忍網格正常數據處理能力、水印對局部惡意攻擊的定位能力等方面對算法性能進行了評價。另外，從容忍正常數據處理能力和對局部惡意攻擊的定位能力方面，將本算法和其他網格模型半脆弱水印算法進行了比較。

4.1 水印透明性評價方法和模型分塊數目的選擇

4.1.1 水印透明性評價方法 本文采用的水印透明性評價方法包括幾何誤差評價和視覺失真評價兩類：

1) 幾何誤差評價。

采用頂點三維直角坐標的信噪比(SNR)作為評價指標，記為SNRmesh，計算公式如式(3)。

SNRmesh=

(3)

2) 視覺失真評價。

為了客觀的評價模型視覺失真，本文采用模型截圖采樣的PSNR平均值來衡量[14]：選擇8個觀測視角，計算嵌入水印前后模型截圖的PSNR(峰值信噪比)，然后取平均值，記為PSNRimage，將其作為模型視覺失真程度的客觀評價指標，該值越大表示模型視覺失真越小。

4.1.2 網格模型分塊數目的選擇 在本算法中，增加分塊數目雖然可以提高篡改定位的精度，但卻會導致水印透明性下降，原因為水印嵌入時只固定改變分塊內1個DCT系數的值，而各分塊生成的DCT系數的數目與其塊內頂點的數目相等，所以塊內頂點數目越多，頂點幾何數據受擾動的幅度就越小。從客觀指標來看(參見表1)，隨著模型分塊數目的增加，SNRmesh值和PSNRimage值均呈遞減趨勢，說明水印的透明性隨著分塊數目增加而下降，當分塊數目過多時，肉眼將會察覺出模型外觀失真。為確保嵌入的水印具有良好的透明性，以PSNRimage≥35 dB作為閾值，將分塊數目設定為Bunny模型600塊、ManFace模型200塊、Happy Buddha模型6 000塊。

表1 不同分塊數目時水印透明性評價結果(Bunny模型)Table 1 Evaluation results of watermark transparency by different partitioned numbers

4.2 水印敏感性評價方法和實驗結果

當網格模型經歷正常數據處理時，半脆弱水印應對此具備容忍能力，即不敏感，而當模型某部位遭受惡意攻擊時，隱藏在該部位的半脆弱水印則應做出相應改變，以實現篡改檢測定位。水印對模型改動的敏感程度可以提取出的半脆弱水印序列和原始半脆弱水印序列之間的相似性Sim作為評價指標，如式(4)。

(4)

其中w(i)和w'(i)分別表示原始水印序列和提取到水印序列的第i位值，L為水印序列的長度。當Sim=1.0時，說明提取到的水印序列與原始水印序列可完整匹配，表示網格模型沒被改動或只是經歷了容許范圍內的網格正常數據處理；當Sim<1.0時，說明提取到的水印與原始水印之間出現了匹配出錯位，表示網格模型被惡意攻擊或經歷了超出容許范圍的網格正常數據處理。

4.2.1 算法對模型RST相似變換處理的容忍能力分析及實驗結果

1)模型平移處理。本算法中水印嵌入實際修改的是模型頂點至模型質心的距離(即半徑值)，該距離不會隨著模型平移發生改變，因此平移對水印提取不會產生影響。

2)模型各向一致縮放處理。當模型進行各向一致縮放處理，表現為模型的所有頂點的幾何數據同時縮放了相同倍數，即所有頂點在球面坐標空間中的半徑值同時縮放了相同倍數，進行分塊及塊內DCT變換處理后，得到的DCT變換系數及其絕對值也將同時縮放相同的倍數，本文所提算法將水印信號隱藏到三個DCT變換系數絕對值的線性關系中，當這三個系數的絕對值縮放相同倍數時，該線性關系并不會發生任何改變，因此各向一致縮放處理不會對水印提取造成任何影響。

3)模型旋轉處理。在嵌入和提取水印之前，都對模型進行了PCA主元分析，將模型調整為同一姿態，確保水印可同步提取，因此可容忍模型的旋轉處理。

實驗結果也表明(參見表2)，本算法嵌入的半脆弱水印對RST相似變換處理表現不敏感，水印相關值都達到了最大值1.0。

表2 模型RST相似變換處理后水印相關值Table 2 Watermark correlation values after model RST processing

4.2.2 算法對模型頂點隨機噪聲和頂點坐標值量化的實驗結果

1)頂點隨機噪聲。

通過隨機擾動嵌入水印后模型頂點的球面坐標半徑值來添加隨機噪聲，表3給出的實驗結果表明，算法嵌入的水印對低強度的噪聲(如強度在0.000 5以下)具備一定抵抗能力(如圖2(a)所示)，可滿足算法對輕微噪聲污染的容忍要求，但隨著噪聲攻擊強度增大，水印相關性急劇下降，即高強度的噪聲可理解為模型遭受了惡意攻擊(如圖2(b)所示)。

圖2 頂點隨機噪聲造成的模型外觀失真(Happy Buddha)Fig.2 Model appearance distortion by adding random noise on vertices

隨機噪聲強度Bunny模型ManFace模型HappyBuddha模型0.00031.01.01.00.00051.01.01.00.0010.770.760.740.0030.560.530.46

2)算法對模型頂點坐標值量化處理的實驗結果。

目前絕大多數網格模型的頂點坐標均采用6位浮點數精度表示，表4的實驗結果表明，當浮點數精度保持在4位或更高位數時，對模型外觀造成的視覺失真較小，可認為其控制在“內容保持”的范圍內，從實驗結果可以看出，本算法嵌入的半脆弱水印對此敏感度較低，具備良好的容忍性；但當浮點數精度降低到2位數時，肉眼將很容易覺察到模型外觀視覺質量出現失真(如圖3所示)，此時模型的外觀視覺失真已經超出了許可尺度，應視為惡意攻擊，從實驗結果可以看出，水印對此表現敏感，水印相關值急劇下降。

表4 頂點坐標量化處理后水印相關值Table 4 Watermark correlation values after quantization of vertex coordinates

圖3 頂點坐標值量化對模型造成的外觀失真Fig.3 Model appearance distortion by quantization of vertex coordinates

4.2.3 半脆弱水印對局部惡意攻擊的定位能力測試 實驗中采用了兩種局部惡意攻擊：局部變形和局部頂點隨機噪聲，半脆弱水印對此類攻擊的檢測定位結果參見圖4。由于定位惡意攻擊位置時以網格的分塊為單位精度，一處攻擊可能涉及多個分塊，而實際攻擊部位一般不會與Metis分塊的輪廓吻合，因此實際得到的定位結果往往會略大于實際攻擊的部位。實驗結果表明，本文所提半脆弱水印算法對于惡意攻擊表現敏感，當惡意攻擊發生在局部位置時，可較準確的定位出篡改發生位置。

圖4 半脆弱水印對局部惡意攻擊的檢測定位Fig.4 Detection and location of local malicious attacks

4.3 與其他三維網格模型半脆弱水印算法的比較

與本算法進行比較的網格模型半脆弱水印算法為Wu[9]的算法、Cho[10]的算法、Lin[11]的算法、Chou[12]的算法。與其他算法相比，本算法的主要優點為可容忍較多類型的網格模型正常數據處理，且能實現篡改位置的可視化定位標識。具體比較結果如表5所示。

表5 與其他半脆弱水印算法的比較結果Table 5 Compared results with other semi-fragile watermarking algorithms

5 結 語

本文提出了一種基于內容級認證的網格模型半脆弱水印算法，網格分割處理后，在每個分塊的頂點幾何數據的DCT變換域系數中都嵌入1位半脆弱水印信號，確保水印對模型的完整覆蓋，懷疑網格模型被非法篡改時，將提取出的水印序列與原始水印序列按位匹配可定位出篡改位置所在。在容忍網格正常數據處理方面，水印可不受RST相似變換處理影響，同時在模型“內容保持”的前提下，可容忍較低強度的頂點坐標值量化處理和隨機噪聲處理；而當網格模型遭受惡意攻擊時，水印則表現敏感，可較準確的定位出篡改位置，并能以直觀的可視化形式對其做出定位標記。

[1] 周燕, 張德豐, 馬子龍. 基于壓縮傳感的圖像哈希水印算法研究[J]. 中山大學學報: 自然科學版, 2010, 6(49): 58-63.

[2] 蔡龍飛，趙慧民，方艷梅. 一種公鑰密碼體制下指紋識別與數字水印的身份認證協議[J]. 中山大學學報: 自然科學版, 2013, 4(52): 51-57.

[3] 王國棟 劉粉林 汪 萍 耿楠楠. 一種篡改檢測與篡改定位分離的圖像認證方案[J]. 計算機學報, 2013, 10(30): 1880-1888.

[4] LUO M，BORS A G. Surface-preserving robust watermarking of 3-D shapes[J], IEEE Transactions on Image Processing, 2011,20(10):2813-2826.

[5] ZAFEIRIOUS S, TEFAS A, PITAS I. Blind robust watermarking schemes for copyright protection of 3D mesh objects[J]. IEEE Transactions on Visualization and Computer Graphics 2005, 11(5):596-607.

[6] CHO J W, PROST R, JUNG H Y. An oblivious watermarking for 3-D polygonal meshes using distribution of vertex norms[J]. IEEE Transactions on Signal Processing, 2007, 55(1):142-155.

[7] YEO B L, YEUNG M. Watermarking 3D objects for verification[J]. IEEE Computer Graphics and Applications, 1999, 19(1):36-45.

[8] CHOU C M, TSENG D C. A public fragile watermarking scheme for 3D model authentication[J]. Computer-Aided Design, 2006, 38(9):1154-1165.

[9] WU H T, CHEUNG Y M. A high-capacity data hiding method for polygonal meshes[C]. Springer：LNCS, Volume(4437), 2007:188-200.

[10] CHO W H, LEE M E, LIM H, et al, Watermarking technique for authentication of 3-D polygonal meshes[C]. Springer：LNCS, Volume(3304), 2005:259-270.

[11] LIN H Y, LIAO H. Authentication of 3-D polygonal meshes[C]. Springer：LNCS, Volume(2939), 2004:168-183.

[12] CHOU C M, TSENG D C. Affine-transformation-invariant public fragile watermarking for 3D model authentication[J]. IEEE Computer Graphics and Applications, 2009, 29(2):72-79.

[13] 崔晨旸.三維模型檢索中關鍵技術的研究[D]. 杭州：浙江大學，2005.

[14] 孫樹森.三維模型數字水印技術及防重構技術研究[D]. 杭州：浙江大學，2006.