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

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

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

0 引 言

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

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

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

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

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

1 Shamir秘密共享方案理論

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

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

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

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

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

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

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

2.1 特征點的選擇

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

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

在原始三維模型的t(1

2.2 共享三維模型生成

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

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

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

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

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

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

2.3 三維模型重建

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

圖2 原始三維模型的重建

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

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

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

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

3 實 驗

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

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

圖3 Venus模型共享與重建模型實驗結果

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

3.1 實驗性能的客觀指標評價

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

3.1.1 Hausdorff距離

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

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

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

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

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

3.1.2 均方根誤差

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

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

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

表1 共享模型與原始模型之間的客觀指標評價

3.2 所提算法與現有算法的比較

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

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

4 結 語

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