基于特征點選取的三維模型共享算法

曹金亮，呂 琪，劉 麗，李志宏

（太原科技大學(xué) 電子信息工程學(xué)院，山西 太原 030024）

0 引 言

近年來，計算機和信息技術(shù)的飛速發(fā)展拓寬了三維模型在各種領(lǐng)域的應(yīng)用，包括制造業(yè)、娛樂業(yè)以及軍事領(lǐng)域。為了防止盜版和對三維模型內(nèi)容的非法訪問，對于三維模型數(shù)據(jù)的保護技術(shù)至關(guān)重要。以前的一些工作已經(jīng)提出保護這種特定類型數(shù)據(jù)的傳輸和存儲算法[1-3]。對三維模型數(shù)據(jù)保護的經(jīng)典算法是加密算法，即借助密鑰將模型數(shù)據(jù)加密為無法讀取的內(nèi)容。由于加密后的模型數(shù)據(jù)失去了原有的意義，因此容易引起攻擊者的懷疑，同時，密鑰掌握在一個人的手中，也增加了數(shù)據(jù)的危險性。秘密共享可以將模型數(shù)據(jù)和密鑰共享為多個份額，由多人共同承擔(dān)保護數(shù)據(jù)和密鑰的責(zé)任，從而降低了秘密數(shù)據(jù)管理者權(quán)力過于集中的風(fēng)險，更大程度地保護了秘密數(shù)據(jù)的安全性和完整性。

1979年，Shamir[4]和Blakley[5]分別使用多項式插值法和超平面幾何學(xué)獨立開發(fā)了第一個（k，n）閾值方案。他們的方法是：在n個參與者之間共享秘密，并規(guī)定至少k個參與者聯(lián)合起來才可以重構(gòu)秘密，從而有效地解決了與標(biāo)準(zhǔn)加密方法有關(guān)的問題。

在過去的幾十年中，許多秘密共享概念已經(jīng)應(yīng)用于圖像處理領(lǐng)域，生成了秘密圖像共享方案[6-8]。近幾年，秘密共享技術(shù)在圖像處理領(lǐng)域得到了廣泛的應(yīng)用。但是，由于三維模型數(shù)據(jù)量龐大，共享過程計算復(fù)雜度高，因此，秘密共享技術(shù)在三維模型數(shù)據(jù)的保護中并未得到很好的應(yīng)用。

近年來，秘密三維模型共享方案[9-11]被陸續(xù)提出。2011年，Elsheh和Hamza[9]首次將Blakley的秘密共享方案[5]以及Thien和Lin[7]的秘密圖像共享方法直接應(yīng)用在三維模型上以保護它們的安全。該方案使用無損數(shù)據(jù)壓縮方法（如Huffman編碼等）壓縮3D模型數(shù)據(jù)，利用秘密共享技術(shù)將壓縮后的模型數(shù)據(jù)進行共享，得到多個較小尺寸的共享份額，并分?jǐn)偨o多人進行保存。該方案分?jǐn)偭四Ｐ蛿?shù)據(jù)保護的責(zé)任，提高了模型數(shù)據(jù)的安全性，同時，小的共享份額有利于數(shù)據(jù)的存儲和傳輸。然而，此方案改變了原始模型的頂點數(shù)量和模型的大小。2016年，Tsai Y[10]等人提出了基于空間細(xì)分的幾何點云秘密三維模型共享方案，將數(shù)據(jù)處理的復(fù)雜度從實數(shù)運算降低到整數(shù)運算，但方案僅在封面三維模型中共享秘密三維模型的近似幾何形狀。2017年，Lee S S、Huang Y J和Lin J C[11]利用秘密共享方案提出了一種交叉恢復(fù)方案來保護一組3D模型，丟失或損壞的模型可以在幸存的經(jīng)過身份驗證的模型的相互支持下進行重建。

為了在保證三維模型安全性的同時減少計算量，本文提出一種基于特征點選取的三維模型共享算法。該方法在原始三維模型中選取一部分頂點為特征點，使用Shamir[4]秘密共享方案為每個特征點生成n個子特征點，這些子特征點代替原始三維模型中的特征點形成n個共享三維模型。在重建過程中，選取k個共享三維模型來重建原始三維模型。

1 Shamir秘密共享方案理論

1979年，Shamir提出了（k，n）門限的秘密共享方案。該方案基于拉格朗日插值的方法將秘密分為n個份額，只有當(dāng)至少k個份額聯(lián)合起來才可以重建秘密。少于k個份額，則不能得到這個秘密的任何信息。

在秘密共享階段，假設(shè)秘密數(shù)據(jù)S是任意整數(shù)，隨機選取素數(shù)p并定義k-1階多項式共享函數(shù)，如式（1）所示：

式中：a0=S，a1,a2,…,ak-1是從[0,p-1]中隨機選取的整數(shù)，對每個份額的計算如式（2）所示：

利用式（2）可將秘密數(shù)據(jù)S分割為n個份額S1,S2,…,Sn。

在秘密重建階段，至少需要k個或更多份額才能重建秘密S。因此，參與者可以合作使用拉格朗日插值算法來恢復(fù)f(x)的系數(shù)a1,a2,…,ak-1，從而得到原始秘密S=a0。具體通過式（3）求得：

2 基于特征點選取三維模型共享算法

本文提出的算法利用MFC框架和OpenGL搭建軟件環(huán)境，使用Visual Studio 2012作為開發(fā)軟件，使用C++作為開發(fā)語言，建立一個展示三維模型的操作界面，使用經(jīng)典的三維模型作為原始模型進行實驗。三維模型表示為M=(V,F)。其中，V為三維網(wǎng)格模型的頂點集合，V={vi|vi=(xi,yi,zi),xi,yi,zi∈R,1

2.1 特征點的選擇

為了共享三維模型，本文提出的方法僅在三維模型特征頂點的坐標(biāo)上應(yīng)用共享方案。特征點位于三維模型凹凸不平的區(qū)域，通常包含較多的三維模型形狀輪廓信息，干擾不均勻區(qū)域的頂點會導(dǎo)致三維模型很明顯的失真，從而保護了三維模型。本文通過計算頂點的突出值[12]從模型中選擇這些特征點，即通過計算頂點與其一環(huán)鄰域內(nèi)所有鄰接點的點積和獲得特征點。頂點vi法向量的計算如式（4）所示，頂點vi的突出值Q(vi)的計算如式（5）所示：

計算所有頂點的突出值，按從大到小的順序選擇突出頂點。如果兩個突出點之間的歐式距離小于閾值R，則丟棄數(shù)值小的頂點。

在原始三維模型的t(1

2.2 共享三維模型生成

本文方案中，共享三維模型的生成過程如圖1所示。

圖1 共享三維模型的生成過程

共享三維模型的生成過程具體步驟如下。

（1）選取原始模型M中的t個原始特征點并記錄序號。

（2）對t個特征頂點進行秘密共享。在此過程中，通過Shamir秘密共享方案對序號為P1的特征頂點v1的原始三維坐標(biāo)(x1,y1,z1)進行共享，生成n個不同三維坐標(biāo)的子特征點，同時確定恢復(fù)重建特征頂點v1所需的共享數(shù)k(2≤k≤n)。對其他t-1個特征頂點v2(x2,y2,z2),v3(x3,y3,z3),…,vt(xt,yt,zt)重復(fù)上述操作，每個特征頂點生成n個共享數(shù)，重建所需的共享數(shù)都為k(2≤k≤n)，便生成了n組子特征頂點，每組均包含t個子特征頂點。

（3）共享三維模型的生成。在每個特征頂點都生成n個子特征點后，根據(jù)原始模型中t個原始特征點的序號P1,P2,…,Pt，將一組t個子特征頂點代替t個原始特征點，便生成了一個與原始相比具有幾何失真的共享三維模型。將此操作重復(fù)n次，便生成了n個共享三維模型M1,M2,…,Mn。

2.3 三維模型重建

原始三維模型的重建過程如圖2所示。

圖2 原始三維模型的重建

原始三維模型的重建過程具體步驟如下。

（1）在生成的共享三維模型中任意選取k個共享模型。

（2）t個原始特征點的恢復(fù)。根據(jù)特征頂點的序號在k個共享模型中選取k組子特征點，每組均包含t個子特征頂點。在每組子特征頂點中選取和序號對應(yīng)的子特征點，k個子特征點通過Shamir秘密重建方案恢復(fù)出序號為原始特征點的原始三維坐標(biāo)。對其余t-1個子特征頂點重復(fù)上述操作，恢復(fù)出原始特征頂點。

（3）原始三維模型M的重建。在k個共享模型中任意選取一個模型，在t個原始特征頂點恢復(fù)完成后，根據(jù)序號，將恢復(fù)出來的原始特征點代替此模型中的t個子特征點，即恢復(fù)重建出了與原始模型M相同的三維模型。

3 實 驗

為了驗證本文基于特征點選取的三維模型算法的有效性，將本文方法應(yīng)用于三維模型Venus，實驗結(jié)果如圖3所示。實驗參數(shù)為：k=3，n=4。原始Venus模型M圖3（a）和圖3（b）具有100 759個頂點，201 514個三角面片，選取了3 341個特征頂點。圖3（c）～圖3（f）是由本文提出的共享方案產(chǎn)生的4個共享三維模型M1,M2,M3,M4。圖3（g）～ 圖3（j）是重建的三維模型。

共享三維模型具有與原始三維模型相同數(shù)量的頂點與三角面片。與原始三維模型相比，可明顯觀察到共享的三維模型雖具有原始模型的大體形狀，但仍具有很大程度的幾何失真。觀察比較圖3（a）與圖3（c），兩圖都是人物頭部的正面，然而由于圖3（a）到圖3（c）的過程中，模型的特征點的坐標(biāo)發(fā)生了改變，圖3（c）中整個Venus模型表面粗糙不光滑，面部五官難以辨認(rèn)，特征點明顯且聚集的模型的鼻子已經(jīng)模糊，鼻梁低且塌；觀察比較圖3（b）與圖3（d），兩圖都是人物頭部的側(cè)面，圖3（d）中Venus模型的輪廓已經(jīng)不清晰，部分區(qū)域甚至尖銳且突出，頸部與頭部的界限已經(jīng)無法辨認(rèn)，下巴的形狀發(fā)生了變化。圖（e）為模型的頭部的上方，由于頭部上方與人物的發(fā)型組合成了一個較平滑的大面片，因此此區(qū)域的特征點較為稀疏，此區(qū)域的粗糙程度仍然能被明顯觀察到。圖3（f）為模型頭部的另一側(cè)面，在此圖中可觀察到人物頭部后面的發(fā)型已經(jīng)不復(fù)存在，與圖3（a）中整潔的發(fā)型相比，發(fā)生了很大的失真。

圖3 Venus模型共享與重建模型實驗結(jié)果

這些細(xì)節(jié)觀察對比與分析，證明了模型的基本特征信息已經(jīng)不存在且難以分辨，說明算法達(dá)到了保護原始模型信息的目的。實驗設(shè)定k=3，因此實驗中至少3個共享三維模型的任意組合，都可以精確地?zé)o損恢復(fù)原始三維模型，少于3個則不能恢復(fù)模型。圖3（g）和圖3（h）分別展示了由M1、M2、M3這3個共享模型組合重建的模型與由M1、M2、M4這3個共享模型組合重建的模型。由于秘密共享方案中的恢復(fù)與重建是無損的，在假定所有參與者都是誠實的、用于恢復(fù)原始模型的共享模型是真實且沒有損壞的情況下，實驗結(jié)果重建的模型與原始模型是完全相同的，頂點數(shù)量和位置沒有任何偏差。圖3（i）和圖3（j）分別展示出了由M2、M3、M4這3個共享模型組合重建的模型與由M1、M3、M4這3個共享模型組合重建的模型。圖3（i）與圖3（a）、圖3（j）與圖3（b）都是模型的同一角度，由于算法在共享過程中只改變了頂點位的坐標(biāo)，并沒有破壞或改變點與點之間的連接性，因此在頂點坐標(biāo)與位置相同的情況下，兩組對比模型中點與點之間的連接、每個三角面片的大小與位置完全相同，面片組成的整個模型自然也相同。

3.1 實驗性能的客觀指標(biāo)評價

本文采用Hausdorff距離（Hausdorff Distance，HD）[13]和均方根誤差（Root Mean Squared Error，RMSE）[14]兩個指標(biāo)對使用本文算法生成的共享三維模型與原始模型進行比較。

3.1.1 Hausdorff距離

Hausdorff距離表示的是兩組點集相似程度的一種度量，即可以描述并測量共享三維模型M1,M2,…,Mn與原始模型M的不相似程度。HD距離越大，相似程度越小。具體地說，假設(shè)有兩組集合分別為A={a1,a2,…,aq}，B={b1,b2,…,bq}。單向HD距離定義為在集合A中選擇一個距離集合B最近的點，記為ai，再計算集合B中每個點b1,b2,…,bq到ai的距離，并將距離從大到小排序，距離最大的值就是HD距離的值。

根據(jù)定義，計算集合A到集合B的單向HD距離如式（6）所示：

集合B到集合A的單向HD距離計算如式（7）所示：

式中：||a-b||表示a和b的歐氏距離。集合A與集合B之間的雙向HD距離計算如式（8）所示，雙向HD距離是兩個單向HD距離之間的最 大值。

對應(yīng)到三維模型上，雙向HD距離是從三維模型Ma的某個特征頂點到另一個三維模型Mb表面的最大距離與該頂點在三維模型Mb上的對稱點到三維模型Ma表面的最大距離的最大值。

3.1.2 均方根誤差

均方根誤差用于計算兩個三維模型成對頂點之間的平均距離，可以反映出原始模型與共享三維模型的變化。均方根誤差具體計算如式（9）所示：

式中：(xj,yj,zj)表示原始三維模型M中特征頂點的坐標(biāo)，(xj′,yj′,zj′)表示共享三維模型M1,M2,…,Mn中特征頂點的坐標(biāo)，j表示特征頂點的序號。利用式（9）計算共享三維模型M1,M2,…,Mn與原始模型M上同樣特征點之間的距離。

共享模型與原始模型之間的HD距離的度量評價如表1所示。從表1可以看出，原始模型M與重建模型M5的HD距離作為對比標(biāo)準(zhǔn)，由于特征點坐標(biāo)的改變，原始模型與其他共享模型之間的HD距離發(fā)生了變化，即失真導(dǎo)致的變化；原始模型M與重建的模型M5的RMSE作為對比標(biāo)準(zhǔn)，由于重建的過程是無損的，因此原始模型M與重建的模型M5特征點的坐標(biāo)是相同的，根據(jù)式（9），兩者之間的RMSE結(jié)果為0，而其他共享模型的特征點的坐標(biāo)被改變，RMSE也發(fā)生了變化，算法僅僅改變共享模型的特征點的坐標(biāo)的小數(shù)點后第3位和4位，共享時選擇的p=9，因此共享模型之間同一點的坐標(biāo)相差并不大，導(dǎo)致各個RMSE結(jié)果相差也不大。

表1 共享模型與原始模型之間的客觀指標(biāo)評價

3.2 所提算法與現(xiàn)有算法的比較

將本文所提算法與現(xiàn)有算法在以下方面進行比較：運用在三維模型上的秘密共享方案、在共享之前是否使用壓縮算法對原始三維模型進行壓縮、是否涉及多秘密共享、是否只共享部分頂點達(dá)到具有幾何失真的效果、是否具有可選擇性，可以自行選擇共享的坐標(biāo)位以及實驗結(jié)果中生成的共享三維模型的大小。具體結(jié)果如表2所示。

表2 與之前的三維模型的共享方案的比較

4 結(jié) 語

針對三維模型的安全性與完整性等問題，本文提出了一種基于特征點選取的三維模型共享算法，通過生成幾何失真的n個共享三維模型來保護原始的三維模型，當(dāng)組合n個共享份額中的至少k個共享份額時，就可以無損地恢復(fù)原始的秘密三維模型。在共享過程中，通過使用Shamir秘密共享方案對選取的特征頂點進行共享并生成子特征點，進而生成共享三維模型。共享的三維模型保留了原始三維模型的大小、頂點以及面片數(shù)目，它們都具有視覺上的幾何失真。實驗結(jié)果與分析證明本文的算法是有效可行的。