周繼來(lái) 周明全 耿國(guó)華 王小鳳

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

關(guān)鍵詞：

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

中圖分類號(hào)： TP391.72 文獻(xiàn)標(biāo)志碼：A

0引言

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

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

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

1算法描述

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

1.1曲面曲率計(jì)算

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

1）計(jì)算法矢量。

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

如圖3所示，三維網(wǎng)格上任意一點(diǎn)Pi計(jì)算法矢量Ni，nj和sj為三角形PVjVj+1的法矢量和面積，Ni為頂點(diǎn)Pi的法矢量。這句話不太通順，請(qǐng)作相應(yīng)調(diào)整。

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

1.2曲度計(jì)算

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

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

1.3計(jì)算隨機(jī)點(diǎn)曲度

隨機(jī)點(diǎn)選取采用D2算法的方式，經(jīng)過(guò)實(shí)驗(yàn)，采樣點(diǎn)的數(shù)量為5000時(shí)就可以達(dá)到比較理想的區(qū)分度。由于三維模型是以三角面片去近似逼近顯示復(fù)雜曲面的，這樣每個(gè)三角面片都具有曲度值，因此在選定隨機(jī)采樣點(diǎn)后可以使用式（4）計(jì)算該點(diǎn)的曲度：

1.4構(gòu)建曲度分布矩陣

以模型質(zhì)心為球心，模型的質(zhì)心由式（5）求出。其中：p0為三維模型的質(zhì)心；pi為模型的每個(gè)頂點(diǎn)坐標(biāo)；N為頂點(diǎn)總數(shù)。pi到質(zhì)心p0的距離為di，由此可以得到模型頂點(diǎn)到質(zhì)心的最大距離dmax。

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

di=（xi-x0）2+（yi-y0）2+（yi-y0）2（6）下標(biāo)是小寫字符“o”，還是數(shù)字“0”？請(qǐng)明確。

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

1.5三維模型相似性度量

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

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

2實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

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

3結(jié)語(yǔ)

曲度算法將高斯曲率和平均曲率作為模型特征提取出來(lái)，結(jié)合隨機(jī)點(diǎn)的幾何距離統(tǒng)計(jì)出分布的概率，構(gòu)建曲度特征矩陣，通過(guò)比較曲度特征獲得三維模型間的相似度。由于曲率性質(zhì)具有旋轉(zhuǎn)和平移不變性，因此不用預(yù)先對(duì)模型進(jìn)行使用主成分分析法（Principal Component Analysis）等方法進(jìn)行預(yù)處理。通過(guò)實(shí)驗(yàn)表明，CF算法對(duì)于具有復(fù)雜曲面的模型有較好的檢索效果。下一步研究的方向是在已有工作的基礎(chǔ)上尋找更有效的曲面特征提取方法和更高效的特征比較方法。

參考文獻(xiàn)：

[1]

霍星，譚結(jié)慶.利用特征向量的三維模型檢索[J].工程圖學(xué)學(xué)報(bào)，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]

徐士彪，車武軍，張曉鵬.基于形狀特征的三維模型檢索技術(shù)綜述[J].中國(guó)體視學(xué)與圖像分析，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].計(jì)算機(jī)工程與應(yīng)用，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]

周明全，樊亞春，耿國(guó)華.一種基于空間對(duì)稱變換的三維模型形狀描述方法[J].電子學(xué)報(bào)，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]

朱新懿，耿國(guó)華.使用形狀變化描述三維模型[J].計(jì)算機(jī)應(yīng)用研究，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]

方惠蘭，王國(guó)瑾.三角網(wǎng)格曲面上離散曲率估算方法的比較與分析[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，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]

屠宏，耿國(guó)華.一種基于局部特征的三維模型檢索算法[J].計(jì)算機(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.