基于曲度特征的三維模型檢索算法

周繼來 周明全 耿國華 王小鳳

摘要：針對如何提高復雜曲面的三維模型的檢索精度的問題，提出了一種基于曲度特征的三維模型檢索算法。首先，在模型表面選取隨機采樣點，計算點所在局部曲面的高斯曲率和平均曲率，通過高斯曲率和平均曲率求出隨機點的曲度值，曲度值表明了曲面的凹凸屬性。然后，以模型的質心為球心，以隨機點與質心距離和曲度值為坐標軸建立坐標系，統計出一定距離范圍內曲度值分布的概率，構建距離與曲度的分布矩陣，以此分布矩陣作為三維模型特征描述符。該特征描述符具有旋轉不變性和平移不變性，能夠很好地反映復雜曲面的幾何特征。最后，通過比較分布矩陣給出不同模型間的相似度。實驗結果表明，該方法相比形狀分布算法的檢索性能有較大提高，尤其適用于具有復雜曲面的三維模型檢索。

關鍵詞：

特征提取；曲度；高斯曲率；平均曲率；三維模型檢索

中圖分類號： TP391.72 文獻標志碼：A

0引言

三維模型庫已經在機械制造、動畫設計、分子生物、數字化考古等領域得到了廣泛的應用。Internet的出現使三維模型的使用和傳播變得非常便捷，三維模型庫中的模型數量呈現出幾何級數的增長，因此，如何從三維模型庫中快速、有效地找到所需要的或相近的模型，已成為三維模型檢索技術所要解決的核心問題[1-2]。

目前已有的基于內容的特征提取技術中，Osada等[3]提出了形狀分布（Shape Distribution）算法（D2描述子），它的主要的優勢是它的簡便性，但是該方法對于復雜形狀的模型區分度不高，由圖1可以看出對于具有復雜曲面的模型D2算法提取的特征趨近相似。以D2算法為基礎有諸多的改進，比如區分點對屬性、加入點對間法相量夾角和點所在三角形的面積作為權值[4-6]等。這些方法對提高檢索效率都有一定提高，但都不能有效反映復雜曲面的幾何特征。周明全等[7]基于三維模型內部對稱關系提出了一種空間對稱描述符來表示三維模型的幾何特征，該方法應用于具有對稱特性的模型上取得了良好的檢索效果，但檢索效率有待提高。朱新懿等[8]利用三維模型的形狀變化信息提取出形狀特征描述符，如何選擇模型切割方向對檢索結果有較大影響。Torkhani等[9]提出了一種局部特征擴展錐曲率（extended conecurvature feature）并將其與提取的顯著點和顯著區域相結合計算三維模型的形狀分布特征。Chen等[10]將局部曲面的曲率分布作為形狀描述特征提取出來。Liu等[11]將曲面的內在曲率值作為特征描述符，包含了高斯曲率和平局曲率等反映模型局部曲面的幾何性質，因此能夠提高對于復雜形狀的模型區分度。高斯曲率和平均曲率反映曲面局部的彎曲程度，但也有各自的不足之處，本身存在著對特定曲面不敏感問題。

本文提出一種基于曲度特征的三維模型檢索算法，曲度特征計算當中包含了高斯曲率和平均曲率，能夠較好地克服高斯曲率和平均曲率對特定曲面不敏感的不足，又能準確反映曲面的幾何屬性，因而能夠提高模型檢索的精度和準度。

1算法描述

空間曲面上的任意一點的曲率是描述三維模型形狀的重要屬性，它反映了點所在曲面的凹凸程度，具有旋轉不變性和平移不變性。本文算法首先在模型表面選取隨機采樣點并計算點所在曲面的高斯曲率和平均曲率，通過高斯曲率和平均曲率求出曲度特征；然后以模型的質心為球心，以隨機點的與質心距離和曲度值為坐標軸，統計出曲度值分布的概率，構建距離與曲度的分布矩陣；最后通過比較分布矩陣給出不同模型間的相似度。圖2所示為3個模型曲度特征算法的檢索過程。

1.1曲面曲率計算

算法所采用的Voronoi曲率估算方法是Meyer等[12]提出的，由文獻[13]可知該方法相對于其他離散曲率估算法具有良好的穩定性和精確度。該方法的主要思想是：把光滑曲面看作是一族網格的極限或者是線性逼近，把三角網格每個頂點的度量性質看作是此空間網格在此點一個小鄰域的平均度量。其主要步驟如下。

1）計算法矢量。

如圖3所示，對于三維網格上任意一點Pi，由式（1）可計算出其法矢量Ni，其中nj和sj為三角形PVjVj+1的法矢量和面積。

如圖3所示，三維網格上任意一點Pi計算法矢量Ni，nj和sj為三角形PVjVj+1的法矢量和面積，Ni為頂點Pi的法矢量。這句話不太通順，請作相應調整。

2）計算混合面積。根據頂點Pi和與其鄰接的頂點所組成的局部區域的角度和面積等近似計算出曲率值。如圖4所示，其中陰影區的面積根據所屬三角形的類型選擇不同方法計算面積，對于銳角三角形，取三角形外心與除Pi所對邊外的兩條邊中點相連接區域面積A1；對于鈍角三角形，取鈍角所對邊的中點與另兩條邊的中點相連接區域面積A2。整個混合面積AM為所有鄰接三角形混合面積之和。

1.2曲度計算

由微分幾何[14]可知，高斯曲率和平均曲率能夠反映曲面的幾何不變量，它們表示點所在曲面局部的彎曲程度，但也有各自的不足之處，高斯曲率可以表示為最大主曲率k1和最小主曲率k2的乘積KG=k1×k2。當一個點在圓柱形曲面上時，它的最小曲率k2為值為0。由此可知，該點的高斯曲率值也為0，而平面的主曲率都為0，所以如果將高斯曲率作為特征提取，則其無法有效區分圓柱曲面和平面。平均曲率KH=（k1+k2）/2是最大主曲率與最小主曲率的和，當曲面存在鞍點時，該點平均曲率值為0，所以如果將平均曲率作為特征提取，其無法有效區分曲面上的鞍點和平面上的點。高斯曲率值和平均曲率都存在對特定的曲面不敏感的情況，如果單一使用會影響三維模型檢索的精度和準度[15]，因此使用曲度作為一個特征值，計算式為：Cp=4K2H-2KG。

曲度值表示為高斯曲率和平均曲率差值的形式，當遇到圓柱曲面時，平均曲率值不為0，而遇到曲面上的鞍點時，高斯曲率值不為0，因此，曲度可以避免平均曲率和高斯曲率不足，其能夠有效地區分圓柱形曲面點、鞍點和平面點。此外，當三維模型表面比較光滑時，曲面的平均曲率值比較小，以平均曲率作為特征描述符對此類模型的區分度不高，與之相比，高斯曲率則具有較好的識別度。另一方面，由于曲度是高斯曲率和平均曲率的差值，從而可以較好地克服高斯曲率在曲面上分布性對均勻的不足，所以曲度作為特征描述符能有效提高模型檢索的精度和準度。

1.3計算隨機點曲度

隨機點選取采用D2算法的方式，經過實驗，采樣點的數量為5000時就可以達到比較理想的區分度。由于三維模型是以三角面片去近似逼近顯示復雜曲面的，這樣每個三角面片都具有曲度值，因此在選定隨機采樣點后可以使用式（4）計算該點的曲度：

1.4構建曲度分布矩陣

以模型質心為球心，模型的質心由式（5）求出。其中：p0為三維模型的質心；pi為模型的每個頂點坐標；N為頂點總數。pi到質心p0的距離為di，由此可以得到模型頂點到質心的最大距離dmax。

p0=1N∑Ni=1pi（5）

di=（xi-x0）2+（yi-y0）2+（yi-y0）2（6）下標是小寫字符“o”，還是數字“0”？請明確。

以dmax為半徑作包圍球，將dmax等分為n份（n=50），d′=dmax/n，d′為距離增量。將曲度的最大值Cmax等分為m份（m=30）此處加了逗號，這樣表述是否符合表達？請明確。C′=Cmax/m，C′為曲度增量。統計落入每個距離和曲度所對應的區間中隨機采樣點出現的概率，從而構成了一個30×50的特征矩陣。這樣如圖6所示構建出了三維模型曲面類型分布矩陣，該矩陣記錄了不同距離區間上曲度的分布情況，由于更多地反映了模型幾何形狀信息，從而能有效地提高模型檢索時的區分度。

1.5三維模型相似性度量

通過提取模型的曲面曲度信息將三維模型相似性度量轉化為曲度分布矩陣之間的距離計算。相似性度量通常采用的方式為歐氏距離，歐氏距離的優點是計算簡單，但缺點是在計算中它沒有充分考慮到各個計算分量之間存在的相關性，使最終的產生結果會受到多個分量的干擾，導致比較精度的下降。為克服歐氏距離的不足，更好地反映矩陣所代表的模型間的相似度，采用Manhattan距離[16]，設U和V分別為兩個模型的曲面類型分布矩陣，則U和V的相似性度量由式（7）計算得出：

D（U，V）=∑29i=0∑49j=0|uij-vij|（7）

2實驗及結果分析

在使用Visual Studio 2010和OpenGL編程環境實現曲度特征（Curvedness Feature， CF）算法，實驗平臺為Intel i52400 3.10GHz CPU、4GB內存的IBM PC機。首先將CF算法與D2算法提取的特征進行對比，圖7所示為5個模型的D2形狀分布直方圖和曲面類型分布矩陣。由表1中可以看出，三維模型螞蟻和手、牛和兔子的形狀直方圖的曲線比較相似，但這些模型卻有很大不同。這是因為D2算法只提取了模型的空間坐標距離信息，無法有效反映三維模型曲面的幾何信息，而曲度特征包含了模型曲面的幾何特征，因此對于具有復雜曲面的模型CF算法能夠在反映三維模型幾何特征上比D2算法有更高的區分度。

為驗證算法的有效性，使用普林斯頓模型庫（Princeton Shape Benchmark， PSB）[17]，從模型庫中選取30類，每類10個模型，共300個模型進行實驗。使用CF、D2、絕對角距離（AbsoluteAngle Distance， AAD）[18]和文獻[8]并依照模型的相似性排序返回檢索出的前7個最相近的模型。圖8所示，CF算法由于選取的特征具有旋轉、平移不變性，因而能有效地反映三維模型的整體形狀特征和局部細節特征，提高檢索結果的準確率。

為評價算法的檢索性能，采用返回的F-1個模型中屬于本類模型的比例（FirstTier， FT）（其中F為待檢索模型所屬類的模型個數），返回的2（F-1）個模型中屬于本類模型的比例（SecondTier， ST），返回的第一個模型屬于目標類的比例（Nearest Neighbor， NN）和增益值（Discounted Cumulative Gain， DCG）4種指標。由表1中的數據顯示：CF算法的檢索性能比D2算法有明顯提高，從而證明CF算法具有良好的檢索效果。

由圖9可知，CF算法綜合性能要優于D2、AAD和文獻[8]的算法，這是由于本文算法將隨機采樣點所在局部曲面的幾何信息和點相對于模型質心的距離信息集合在一起形成了分布矩陣，從而使具有復雜曲面的三維模型的幾何特征能夠更多地反映在提取的特征值中，且不需對3D模型的姿態進行預處理，而且由于算法采用的是在三維表面隨機選擇的點，使其對模型的簡化和部分噪聲具有不敏感性。

CF算法在三維模型表面用選取5000個隨機點，每個點與模型質心的距離只需計算一次，而D2算法的1024點間的距離計算次數需要523776次，因此CF算法在距離計算階段比D2算法要快。在進行特征值比較時，Manhattan距離計算的時間復雜度為O（n2），不過CF算法的特征值為50×30矩陣，因此CF算法的總體運行時間略少于D2算法。

3結語

曲度算法將高斯曲率和平均曲率作為模型特征提取出來，結合隨機點的幾何距離統計出分布的概率，構建曲度特征矩陣，通過比較曲度特征獲得三維模型間的相似度。由于曲率性質具有旋轉和平移不變性，因此不用預先對模型進行使用主成分分析法（Principal Component Analysis）等方法進行預處理。通過實驗表明，CF算法對于具有復雜曲面的模型有較好的檢索效果。下一步研究的方向是在已有工作的基礎上尋找更有效的曲面特征提取方法和更高效的特征比較方法。

參考文獻：

[1]

霍星，譚結慶.利用特征向量的三維模型檢索[J].工程圖學學報，2009，30（3）：76-79.（HUO X，TAN J Q.3D model retrieval based on feature vector [J]. Journal of Engineering Graphics， 2009， 30（3）： 76-79.）

[2]

徐士彪，車武軍，張曉鵬.基于形狀特征的三維模型檢索技術綜述[J].中國體視學與圖像分析，2010，159（4）：439-450.（XU S B， CHE W J，ZHANG X P. A survey of 3D model retrieval based on shape features [J]. Chinese Journal of Stereology and Image Analysis， 2010，159（4）：439-450.）

[3]

OSADA R， FUNKHOUSER T， CHAZELLE B， et al. Shape distributions [J].ACM Transactions on Graphics， 2002， 21（4）： 807-832.

[4]

GAO Y， DAI Q H， ZHANG N Y. 3D model comparison using spatial structure circular descriptor [J]. Pattern Recognition， 2010， 43（3）： 1142-1151.

[5]

蔣立軍，張旭堂，張廣玉.基于面積分布算子的三維模型檢索算法[J].計算機工程與應用，2012，48（12）：6-13.（JIANG L J， ZHANG X T， ZHANG G Y. 3D model retrieval method based on area distributions [J]. Computer Engineering and Applications， 2012， 48（12）： 6-13.）

[6]

SHIH J L， CHEN H Y. A 3D model retrieval approach using the interior and exterior 3D shape information [J]. Multimedia Tools and Applications， 2009， 43（1）： 45-62.

[7]

周明全，樊亞春，耿國華.一種基于空間對稱變換的三維模型形狀描述方法[J].電子學報，2010，38（4）：853-859.（ZHOU M Q， FAN Y C， GENG G H. A spatial symmetry descriptor for 3D model [J]. Acta Electronica Sinica， 2010， 38（4）： 853-859.）

[8]

朱新懿，耿國華.使用形狀變化描述三維模型[J].計算機應用研究，2015，32（3）：922-925.（ZHU X Y， GENG G H. Shape variation representation of 3D shape descriptor [J]. Application Research of Computers， 2015， 32（3）： 922-925.）

[9]

TORKHANI F， WANG K， CHASSERY J M. A curvaturetensor based perceptual quality metric for 3D triangular meshes [J]. Machine Graphics & Vision， 2013， 32（16）： 1-25.

[10]

CHEN Q， YU Y M. 3D CAD model retrieval based on feature fusion [J]. Advanced Materials Research， 2013， 765/766/767： 316-319.

[11]

LIU Y J， ZHANG X D， LI Z M， et al. Extended conecurvature based salient points detection and 3D model retrieval [J]. Multimedia Tools and Applications， 2013， 64（3）： 671-693.

[12]

DESBRUN M， MEYER M， SCHRODER P， et al. Implicit fairing of irregular meshes using diffusion and curvature flow [C]// SIGGRAPH99： Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques. New York： ACM， 1999： 317-324.

[13]

方惠蘭，王國瑾.三角網格曲面上離散曲率估算方法的比較與分析[J].計算機輔助設計與圖形學學報，2005，17（11）：17-23.（FANG H L， WANG G J. Comparison and analysis of discrete curvatures estimation methods for triangular meshes [J]. Journal of ComputerAided Design & Computer Graphics， 2005， 17（11）： 17-23.）

[14]

吳大任.微分幾何講義[M].北京：人民教育出版社，1984：126-128.（WU D R. Differential Geometry [M]. Beijing： Peoples Education Press， 1984： 126-128.）

[15]

屠宏，耿國華.一種基于局部特征的三維模型檢索算法[J].計算機工程，2015，41（3）：218-222.（TU H， GENG G H. A 3D model retrieval algorithm based on local feature [J]. Computer Engineering， 2015， 41（3）： 218-222.）

[16]

DEJIAN V， VRANI C， DIETMAR S. An improvement of rotation invariant 3D shape descriptor based on functions on concentric sphere [C]// Proceedings of the 2003 IEEE International Conference on Image Processing. Piscataway， NJ： IEEE， 2003： 757-760.

[17]

SHILANE P， MIN P， KAZHDAN M， et al. The Princeton shape benchmark [C]// SMI04： Proceedings of the 2004 International Conference on Shape Modeling and Applications. Washington， DC： IEEE Computer Society， 2004： 167-178.

[18]

OHBUCHI R， MINAMITANI T， TAKEI T. Shapesimilarity search of 3D models by using enhanced shape functions [C]// TPCG03： Proceedings of the Theory and Practice of Computer Graphics 2003. Washington， DC： IEEE Computer Society， 2005： 97-104.