針對頂點策略優化的三維模型可逆數據隱藏算法

張國有,米 佳

(太原科技大學 計算機科學與技術學院,山西 太原 030024)

1 概 述

隨著計算機等電子設備的發展和互聯網技術的普及,數字多媒體在日常生活中被廣泛使用,三維模型作為一種重要的媒體類型,成為人們分享和傳遞信息的重要載體。由于數字化本身具有強移植和易傳播的特點,給其安全問題帶來了嚴峻的考驗,譬如模型數據的竊取、盜版和非法篡改等。隨著各種媒體類型外包到云端的需求越來越大,云計算為存儲多媒體和數據操作提供了巨大的優勢,保護隱私和數據機密性成為目前云計算技術廣泛關注的問題。因此,為了防止未經授權的信息泄漏,原始模型數據在外包到云之前會被加密,云端會在網格中嵌入海量重要數據以識別模型的真實性和完整性。同時云服務提供商無權在數據嵌入信息的過程中對模型造成破壞,因此需要可逆數據隱藏(Reversible Data Hiding,RDH)技術將附加數據嵌入到數字媒體后,實現高質量恢復[1]。

應用在圖像媒體的RDH技術主要分為普通域和加密域[2]。普通域包括直方圖平移、差分擴展、圖像插值、整數變換技術等[3-6],而加密域根據是否需要對圖像媒體進行預處理分為加密后騰出空間(Vacating Room After Encryption,VRAE)[7-9]和加密前預留空間(Reserving Room Before Encryption,RRBE)[10-13],其中VRAE框架是圖像媒體直接在云端進行加密嵌入,RRBE框架通過加密前預留空間獲得大量冗余提高嵌入率。

現有的三維模型的RDH方法主要分為四個域:空間域、變換域、壓縮域和加密域。空間域方法[14-16]利用網格的空間相關性來嵌入數據,例如通過修改頂點坐標和網格拓撲結構進行嵌入。變換域方法[17-19]是將數據嵌入到變換系數中,并且文獻[19]將附加信息嵌入到模型的顏色信息中,通過傅里葉變換提高算法的性能。壓縮域方法[20-22]是通過壓縮網格頂點將數據嵌入到模型中。

加密域中的RDH則是一種更為可靠的方案,它可以起到更好的隱私保護作用[23-27]。Jiang等人[23]使用縮放和量化將三維網格模型的頂點坐標映射到整數,通過流密碼加密獲得加密的網格,翻轉加密坐標的幾個最低有效位(LSB)嵌入附加數據。在接收端對標記的加密網格進行解密,然后利用設計的平滑度量函數實現數據提取和網格重建。但此算法在嵌入容量和重建網格質量方面存在不足。為了改善算法性能,許多研究者針對文獻[23]提出改進[24-27]。

Li[24]將三維模型劃分為不重疊的補丁,用每個補丁的三個方向值來嵌入水印提高嵌入率.。Shah[25]提出了一個同態Paillier密碼系統的兩層RDH框架,這種框架在簡單和密集的網格上成功實現了高嵌入率。Xu[26]提出了一種預測誤差檢測的方法,利用環預測提高嵌入率及恢復質量。Hao[27]采用交叉預測及自適應閾值來提高安全性,但是由于加擾與嵌入的統一進行,模型恢復質量不被確定。

通過對以上方法的分析,為解決高嵌入率下的模型恢復質量問題,該文利用預測策略和拉普拉斯算子進行優化,提出一種針對模型頂點策略優化的可逆數據隱藏算法,通過劃分全鄰域計算新的重心頂點集合,采用預測策略預測所有頂點集合的最高有效位來確定最大嵌入長度,在接受端迭代半窗拉普拉斯算子得到光滑的恢復模型和局部細節特征, 提高嵌入率和重建網格質量,并采用余切拉普拉斯算子對模型進行可視化分析,提高人眼對恢復模型感知力。

2 方 法

三維網格模型以各種文件格式表示,例如OFF,PLY,OBJ等。假設M=(V,E,F)是一個給定的包含了N個頂點的三角網格模型,其中V表示模型中頂點的集合,E表示模型中邊的集合,而F表示模型中面的集合。E與F為網格的拓撲部分即連接關系。

2.1 預處理

(1)

(2)

bi,j,w為整數坐標的二進制位表示,即原始網格的二進制坐標形式。接收者可以通過式3將處理后的整數坐標轉換為浮點坐標,以便對網格模型進行光滑處理。

(3)

m是確定網格無損恢復的重要參數。m的值對應于整數坐標的位長L為:

(4)

不同的m對應不同的位長L,這意味著m影響恢復網格的恢復質量和每個階段的運行效率。

根據模型頂點的浮點值壓縮為整數坐標值后,發送方按照升序遍歷網格數據中的所有頂點,根據頂點之間的拓撲信息計算預測集合C和參考集合R。首先遍歷數據中的第一個頂點,將這個頂點加入到C中,找到它的相鄰頂點加入到R中,得到一環局部平均鄰域(全鄰域)。

遍歷完所有頂點的全鄰域后進行劃分,從而計算新的重心頂點集合E進行頂點值預測。全鄰域處理的具體算法步驟如下:

(1)計算頂點V0的坐標值為vi,其微分坐標即δ坐標,如式5所示。

(5)

其中,δi=(δx,δy,δz),|NV(vi)|是vi的相鄰頂點的集合即全鄰域,如圖1(a)。|NV(vi)|也是vi的直接鄰居數。

(2)計算vi的質心,如式6所示,檢索其他鄰居到全鄰域平面的最短距離。選擇距離最短的鄰居并將其與vj配對,將NV(vi)與直線vi,vk分為左和右兩個鄰域(子集/窗口)即生成2|NV(vi)|。

(6)

(7)

遍歷其中一個子集的所有頂點和面,分配大小為頂點數和面數之和的空間,利用網格結構拓撲關系連接新頂點坐標,如圖1(b)。將所有新頂點坐標添加到一個新的頂點集合,即重心集合E。

圖1 平面上全鄰域劃分及重心添加圖示

2.2 預測策略

嵌入重要數據前對模型頂點進行預測檢測可以獲得大量冗余[26],從而提高嵌入率。數據嵌入時除了使用頂點笛卡爾坐標的三個坐標向量、兩個原始頂點集合外,新頂點重心集合也用于預測策略,從而進一步實現高嵌入。

預測集合C與重心集合E歸為嵌入集合,用于嵌入附加數據,參考集合R用于在整個過程中不修改頂點的情況下恢復網格。測試C與E中的頂點是否有預測誤差以及可嵌入頂點的最大嵌入長度,而具有預測錯誤的頂點不進行數據嵌入。預測策略步驟如下:

(1)將求出的重心坐標轉化為二進制坐標,如公式8:

(8)

其中,bi,j,c表示重心坐標的二進制流。

(2)以圖2為例,以坐標x向量為例進行兩次預測,分別為E和C,R之間的預測以及C和R之間的預測。

(3)對于新頂點集E,如果C和R的坐標0的個數大于等于1的個數,則預測位為0;如果0的個數小于1的個數,預測位為1。

(4)從MSB到LSB依次比較各坐標的每一位直到某一位出現不同,在這一位置進行取反與前面的相同位的位數(label)一起得到最大嵌入長度為 label+1位。

(5)同理,在確定C的最大嵌入長度時用R進行預測,如果R的坐標0的個數大于等于1的個數,則預測位為0;如果0的個數小于1的個數,預測位為1。

(6)對于坐標的y向量和z向量使用相同的預測策略,最大嵌入長度為每個集中所有頂點的最大嵌入長度。

圖2 預測策略圖示

2.3 流密碼加密

為了確保在云端存儲的安全性,發送端對預測策略下的集合數據進行流密碼加密,如式9、式10所示:

bi,j,k=bi,j,w∪bi,j,c

(9)

ei,j,k=bi,j,k⊕si,j,k

(10)

其中,si,j,k是二進制隨機密碼流,bi,j,k是坐標二進制位,ei,j,k是生成的密碼,⊕為異或運算。

(11)

2.4 數據嵌入

發送方將嵌入集合中的數據嵌入到每個頂點的附加信息長度中,將x,y和z坐標值的t+1個MSB替換為t+1位進行嵌入,即在嵌入集合中的每個頂點嵌入3×(t+1)位。發送方獲得帶有附加數據的加密網格,即標記的加密網格。

(12)

2.5 數據提取

在收到標記的加密網格后,接收者可以使用數據隱藏密鑰提取附加數據,或者選擇直接對網格進行解密及光滑恢復。

從嵌入集合的頂點坐標中提取沒有預測誤差的t+1個MSB,然后使用數據隱藏密鑰獲得相應的明文附加數據。

(13)

2.6 網格解密及光滑恢復

使用加密密鑰對標記的加密網格執行異或解密,恢復參考集合的坐標,根據預測策略,恢復嵌入集合的坐標,同時為了更好地去除噪聲和減輕收縮,采用半窗拉普拉斯算子對模型進行光滑恢復,以此保留網格模型的特征[28],實現高質量恢復。光滑恢復的算法步驟如下:

(1)計算頂點vi的法向量,如式14:

(14)

對每一個子集有:

(15)

(2)將半窗拉普拉斯算子投影到2|NV(vi)|的傳統拉普拉斯算子上,如式16:

δi=(di·ni)ni

(16)

其中,Vsub是所有子集,d表示半窗拉普拉斯算子,n表示傳統拉普拉斯算子的方向。

(3)計算每個頂點的正則化能量,如式17:

(17)

(4)采用半窗拉普拉斯算子迭代更新頂點位置使模型趨于平滑。

Vt+1=Vt+λdt?2Vt

(18)

其中,dt為時間步長,λ是熱擴散中的擴散速度, ?2Vt是給定網格頂點上的梯度散度。

3 實驗結果及討論

文中算法在The Princeton Shape Retrieval and Analysis Group(http://shape.cs.princeton.edu/benchmark/)和The Stanford 3D Scanning Repository(http://graphics.stanford.edu/data/3Dscanrep/)數據集上進行測試,并從以下幾個方面分析了該方法的性能:嵌入容量、恢復質量以及閾值m及頂點處半窗拉普拉斯算子迭代次數對恢復模型質量的影響。同時與現有文獻進行了比較來評估對比不同模型和不同方法的算法性能,最后采用平均曲率進行可視化分析。

3.1 實驗環境

算法程序在Windows10,Visio Studio 2017開發,搭建matlab環境實現優化頂點策略,并配置OpenGL開發環境實現模型渲染。實驗服務器為CPU:i7-10870H(8核 2.20 GHz),系統內存16 GB,硬盤512G。

實驗中相關參數設置如下:算法閾值m是在恢復模型質量和過程的計算開銷之間的權衡,在m對應的整數坐標位長L={8,16,32,64}中尋優取得,迭代次數t是模型恢復質量和人眼感知的權衡,在t={1,2,3,4,5,6,7}中尋優取得,最優參數結果在第3.3節中詳細介紹。

3.2 數據集

該文使用兩個數據集評估算法的有效性。(1)The Princeton Shape Retrieval and Analysis Group。這是廣泛使用的三維模型庫基準,The Princeton Shape Retrieval and Analysis Group共包含161個大類覆蓋的1 814個.off格式的三維模型,其中907種模型用于訓練和驗證,剩余的907種模型通過訓練后的參數來進一步得到測試集結果。(2)The Stanford 3D Scanning Repository,其數據集在.obj文件格式模型上進一步測試文中算法對密集網格的適用性及有效性。

3.3 評價指標

通過Hausdorff距離和信噪比來判斷網格恢復質量,通過嵌入率判斷模型嵌入的最大信息量。

3.3.1 恢復質量

Hausdorff距離和信噪比(Signal to Noise Ration,SNR)可用于測量網格的幾何失真[29],Hausdorff距離是描述兩組點之間相似度的度量,是對兩組點之間距離的定義。

(19)

其中,M和N代表兩個集合,D(M,N)代表集合M中任意點M和集合N中任意點N之間的歐氏距離。

在網格內容中加入一些噪聲后網格的幾何失真可以通過信噪比(SNR)來衡量,其定義如下:

SNR=

(20)

該文測試了原始模型和恢復模型之間的 Hausdorff距離和SNR,m的變化。因此,改變m的次數觀察計算原始模型和恢復模型之間的 Hausdorff距離和SNR。如圖3、圖4所示,Hausdorff 距離隨著m的增加線性減小,而SNR線性增加,表明模型的恢復質量隨著m的增加而提高。可以觀察到m=6平衡了模型的恢復質量和開銷時間。因此,選擇m=6進行實驗。

圖3 測試模型在不同m下的Hausdorff距離

圖4 測試模型在不同m下的SNR

3.3.2 嵌入容量

嵌入率是通過每頂點比特數來衡量的,它是網格模型中嵌入比特數與頂點數的比值。嵌入率(Embedding Rate,ER)越大,可以隱藏的附加信息越多。如前所述,若選取m=4的值,對應16位的二進制位長來表示整數坐標值。頂點坐標值用16位長表示,對于新嵌入集合,在一個全鄰域中的可候選嵌入位數從 1×16位增加到(η+1)×16位,其中η為重心坐標個數。

3.4 不同模型的比較

該文選擇測試常用模型beetle,mushroom,mannequin,將Hausdorff距離、SNR、ER與現有算法進行了比較,如表1所示,可以看出對模型頂點進行策略優化在評價指標上有一定的提高。

表1 不同模型在現有算法上的性能比較

3.5 不同方法的比較

將所提框架的信噪比和嵌入率與現有文獻的進行了比較,如圖5和圖6所示。在圖5中,通過半窗拉普拉斯算子恢復頂點位置,使得文中算法的SNR明顯比其余算法的高,恢復質量得到提高;在圖6中,新重心集合的添加增大了嵌入集合容量,優化后的預測策略增大了嵌入位,使文中算法的嵌入率比其余四種算法的高。

圖5 文中方法和現有方法測試網格平均SNR的比較

圖6 文中方法和現有方法測試網格平均ER的比較

3.6 可視化展示

相比于其他算法中傳統的評價指標,例如Hausdorff距離和信噪比(SNR),經過顏色渲染的網格模型更容易進行人眼感知。采用頂點余切拉普拉斯算子對應到平均曲率法線[30],繪制彩色散點圖對恢復模型進行可視化分析。在圖7中,模型頂點數依次由小到大排列,其中內圈代表模型顏色,外圈代表曲率顏色,不同模型有不同的曲率值,每個模型隨機選取局部曲率值來映射顏色,平均曲率值越大,色彩越鮮艷。相比經過平均曲率渲染的模型,利用散點圖可以看出較平坦區域顏色以青綠色為主,而曲面彎曲程度較大的部分以紫色為主,因此對于恢復模型,除傳統評價指標Hausdorff 距離和SNR外,也可以通過人眼觀察模型紫色區域判斷恢復質量。

圖7 模型在絕對平均曲率下的局部散點圖

圖8分別為mushroom,mannequin,beetle模型的算法效果,從左到右依次為原始模型、加密模型、嵌入模型、1次迭代光滑模型、3次迭代光滑模型、5次迭代光滑模型、7次迭代光滑模型,即模型使用頂點處半窗拉普拉斯算子進行不同次迭代后光滑恢復的效果。可以看到,隨著迭代次數的增加,網格模型不可避免地會出現收縮特征,如mannequin的眼睛、鼻子等尖銳部分,從而降低了恢復質量。同時可以看出光滑模型較原始模型,顏色較深處的高曲率區域即紫色區域,在去噪的同時更好保留了細節特征,實現了可逆數據隱藏下的頂點策略優化效果。因此,為了保證模型高恢復質量支撐良好的實驗效果,實驗中迭代1次進行光滑得到算法指標。

圖8 模型算法效果

表2 與現有方法的方案效果對比

表2對比了beetle模型和mannequin模型在不同方法下的人眼感知效果。

綜上所述,文中算法不僅在一定程度上實現了高嵌入率,而且獲得了更高質量的恢復網格,可以進一步對恢復模型人眼感知。

如表3,在The Stanford 3D Scanning Repository中針對頂點密集網格模型Stannf bunny進一步測試性能,其頂點數為34 843,面數為69 541。展示了文中方法相比于其他方法的可視化性,密集網格模型可廣泛用于3D打印,表明文中方法有一定的性能,并且進一步驗證了對頂點密集型網格的適用性和有效性。

表3 不同方法下Stannf bunny(bunnybig)的可視化度

4 結束語

如今三維網格廣泛應用于多媒體、建模、渲染、3D打印等實際領域,網格模型的發展也越發具有意義。為提高模型安全性,圍繞頂點處預測策略和拉普拉斯算子,提出一種策略優化的可逆數據隱藏算法。采用模型頂點到切平面的最短距離將全鄰域劃分為兩個子集,以生成新的重心集合,預測策略預測所有頂點集合的最高有效位確定最大嵌入長度,迭代半窗拉普拉斯算子得到高質量的恢復模型,采用余切拉普拉斯算子下的平均曲率繪制三維散點圖渲染模型,從而實現實際場景下的安全應用。實驗結果表明,在高嵌入率下有效提高了恢復質量,并且在人眼感知光滑模型方面也有較好的效果。未來將探索運行效率更高的優化算法,提高模型在深度學習等實際領域中的安全性。