機(jī)械零件模型局部形狀相似性檢索算法研究

王家樂(lè) 姜 波 黃逸民

浙江工商大學(xué)，杭州，310018

0 引言

隨著數(shù)字化技術(shù)和CAD技術(shù)的發(fā)展，三維模型被廣泛地用于機(jī)械設(shè)計(jì)領(lǐng)域。為了實(shí)現(xiàn)對(duì)海量機(jī)械零件模型數(shù)據(jù)的有效管理，特別是對(duì)已有的零件模型進(jìn)行復(fù)用，用戶往往要從龐大的模型數(shù)據(jù)庫(kù)中查詢(xún)所需模型或者瀏覽相似三維模型的聚類(lèi)。在設(shè)計(jì)新的三維形狀時(shí)，若能有效地從已有模型庫(kù)中找到相關(guān)模型并加以利用，則可大大減小工作量。

如何衡量和計(jì)算三維形狀相似性是實(shí)現(xiàn)三維模型查詢(xún)、聚類(lèi)或自動(dòng)標(biāo)注的關(guān)鍵，因此基于內(nèi)容的三維模型形狀特征提取和比較技術(shù)逐漸成為了研究熱點(diǎn)。三維模型的形狀相似性比較算法可以分為全局形狀相似性比較算法和局部形狀相似性比較算法兩大類(lèi)。在三維模型檢索研究的早期階段，大部分研究都集中于模型全局形狀特征的提取和比較。全局形狀描述符只支持模型間“整體－整體”的匹配，不能支持“部分－整體”匹配，要實(shí)現(xiàn)“部分－整體”匹配必須采用局部形狀描述符，而且局部形狀描述符一般比全局形狀描述符包含更豐富和復(fù)雜的形狀信息，形狀區(qū)分能力更強(qiáng)。因此，近年來(lái)三維模型局部形狀特征提取越來(lái)越得到研究者的重視。

本文提出一種三維機(jī)械零件模型局部形狀特征提取方法，用提取到的局部形狀特征構(gòu)建形狀特征向量，實(shí)現(xiàn)“部分－整體”的模型局部形狀檢索。

1 相關(guān)研究

在三維模型檢索研究的早期階段，大部分研究都集中于模型全局形狀特征的提取和比較。全局形狀特征提取算法根據(jù)三維模型的整體形狀信息生成一個(gè)形狀特征描述符。對(duì)全局形狀描述符的綜述文獻(xiàn)［1－2］較多，本文對(duì)此不做贅述。

近年來(lái)，三維模型局部形狀特征的研究逐漸興起。局部形狀特征提取算法的一般思想是：對(duì)三維模型某些局部區(qū)域單獨(dú)生成形狀特征向量，在衡量?jī)蓚€(gè)模型的相似性時(shí)，以各自局部區(qū)域的形狀特征向量集為基礎(chǔ)進(jìn)行計(jì)算。

構(gòu)建局部形狀特征描述符的一種思路是把模型分解成若干子部件，然后對(duì)這些子部件逐個(gè)提取形狀特征。Ferreira等［3］利用層次分割樹(shù)將網(wǎng)格模型迭代地分為子部件，然后再進(jìn)行相似性匹配。Wessel等［4］提出用圖元（圓柱、圓環(huán)、球等）對(duì)模型局部做匹配，從而將模型分解成若干圖元后再提取局部形狀特征。

這類(lèi)基于子部件的局部形狀特征提取方法需要解決模型部件分割（part segmentation）的問(wèn)題。而模型部件分割是比較困難的，分割算法往往由于要決定多個(gè)閾值而失去健壯性，或者需要用到復(fù)雜的機(jī)器學(xué)習(xí)機(jī)制［5］。一些利用了模型拓?fù)浣Y(jié)構(gòu)的檢索方法也可以視為是這種基于子部件的局部形狀描述符［6－7］，但拓?fù)浣Y(jié)構(gòu)提取算法一般對(duì)噪聲敏感，所以難以獲得穩(wěn)定的部件分割結(jié)果。

構(gòu)建局部形狀特征描述符的另一種思路是，在模型上尋找那些具有強(qiáng)形狀區(qū)分力的區(qū)域并且提取該區(qū)域的形狀特征向量，比較模型形狀時(shí)，用這些形狀特征向量間的距離來(lái)計(jì)算相似性。這類(lèi)方法中具有代表性的是 Funkhouser等［8］和Shilane等［9－10］提出的優(yōu)先隊(duì)列兩兩比較法。該方法先在模型上生成大量采樣點(diǎn)，然后提取采樣點(diǎn)周?chē)哪撤N形狀特征，通過(guò)兩兩比較這些形狀特征向量間的差異度，得到各采樣點(diǎn)所在區(qū)域的形狀區(qū)別度；比較模型間形狀時(shí)，構(gòu)建一個(gè)優(yōu)先級(jí)隊(duì)列以選取形狀區(qū)別力強(qiáng)的向量來(lái)計(jì)算相似度。

Funkhouser等［8］和 Shilane等［9－10］的方 法雖不需要先對(duì)模型做部件分割，但是其特征提取和形狀區(qū)分度排序的計(jì)算量非常大；特征比較時(shí)，需尋找局部特征向量間的對(duì)應(yīng)關(guān)系，計(jì)算同樣比較復(fù)雜。因此該方法目前也難以應(yīng)用于檢索要素頗多的模型。

在二維圖像分析領(lǐng)域，基于尺度不變特征變換（scale－invariant feature transform［11］，SIFT）的局部形狀比較算法已經(jīng)得到較多的研究。對(duì)于二維圖像而言，尺度不變特征是一種顯著性的局部特征（視覺(jué)上，尺度不變特征一般對(duì)應(yīng)于圖像中的角點(diǎn)），這些特征對(duì)旋轉(zhuǎn)、縮放和光照變化保持不變性，對(duì)視角變化、仿射變換和噪聲也保持一定程度的穩(wěn)定。研究表明SIFT是一種很好的圖像局部特征提取方法，尺度不變特征既包含豐富的形狀信息，又具有很好的健壯性和通用性［12］。近年來(lái)，有研究者將SIFT引入到三維模型的檢索中，其中，具有代表性的是Ohbuchi等［13］的。先將三維模型從多個(gè)視角投影成若干幅深度圖像，然后再采用SIFT算法對(duì)各個(gè)圖像提取尺度不變特征的方法。Ohbuchi等［13］方法的實(shí)質(zhì)，是一種基于圖像的三維模型檢索方式，只是在投影圖像的比對(duì)上采用了圖像的尺度不變局部特征。因此，類(lèi)似于文獻(xiàn)［1］中涉及的光域描述符，Ohbuchi等［13］的方法要渲染大量的深度圖像，計(jì)算量很大。

本文采用尺度不變特征來(lái)描述三維機(jī)械零件模型的局部形狀，與Ohbuchi等［13］方法的不同之處是，本文利用直接作用于三維體素模型上的SIFT算法提取局部形狀特征，無(wú)需將零件模型渲染成多幅二維圖像。

2 灰度體素化

體素空間相當(dāng)于圖像空間在維度上擴(kuò)展了一維，體素模型可視為三維空間中的“圖像”，所以SIFT操作可以較方便地應(yīng)用于三維體素模型之上。大多數(shù)模型都是以三維網(wǎng)格（3DMesh）表示方式存儲(chǔ)的，需要先將網(wǎng)格模型轉(zhuǎn)換為體素模型。

通常所用的體素化算法都是將網(wǎng)格模型轉(zhuǎn)換成體素空間中的二值體素集合，體素化過(guò)程是把組成網(wǎng)格模型的面片與體素柵格求交，根據(jù)面片與體素柵格相交的情況，把每一個(gè)體素的值置為0或1，0代表該體素位置不存在網(wǎng)格模型面片，1代表該體素位置存在網(wǎng)格模型面片。為了獲得更多的形狀信息，本文提出灰度體素化算法，灰度體素是指體素的值可取某范圍內(nèi)的灰度值。本文對(duì)涉及的灰度值有兩種定義方式：

（1）體素的灰度值代表包含在該體素內(nèi)的網(wǎng)格模型面片的面積，如圖1a所示。

（2）體素的灰度值代表包含在該體素內(nèi)的網(wǎng)格模型面片的離散高斯曲率，如圖1b所示。

圖1 體素灰度值的定義

離散高斯曲率的求法采用文獻(xiàn)［14］提到的方法，三角形某頂點(diǎn)v的離散高斯曲率為

式中，A（v）為頂點(diǎn)鄰域的Voronoi面積；∑θi為鄰域三角形的夾角和。

3 體素模型的SIFT算法

得到灰度體素模型后，可通過(guò)三維體素SIFT算法在灰度體素模型上提取尺度不變形狀特征。三維體素SIFT算法是二維圖像SIFT算法在三維空間中的變種。三維體素SIFT算法的第一步是計(jì)算多尺度高斯差分，其計(jì)算公式為

式中，＊ 表示卷積運(yùn)算；I（x，y，z）為體素模型灰度函數(shù)，（x，y，z）為體素坐標(biāo)；G（x，y，z，kσ）為高斯函數(shù)，k為［1，5］內(nèi)的整數(shù)，表示不同的尺度級(jí)別，σ為常量，σ＝。

式（1）中的尺度不變特征點(diǎn)是體素鄰域空間和尺度鄰域空間中的DOG極值點(diǎn)。

為提高特征的穩(wěn)定性，還需對(duì)獲取的極值點(diǎn)進(jìn)行篩選，以去除邊緣響應(yīng)。篩選使用的不等式為［15］

式中，H為DOG函數(shù)的Hessian矩陣；r為經(jīng)驗(yàn)閾值，一般選?。?0，50］內(nèi)的整數(shù)，本文實(shí)驗(yàn)中r取30。

僅當(dāng)DOG值使式（2）的不等式成立時(shí)，該點(diǎn)才被選取為最后的特征點(diǎn)。得到特征點(diǎn)后，即可根據(jù)特征點(diǎn)鄰域體素的梯度方向構(gòu)建尺度不變形狀特征向量。

4 特征向量構(gòu)建和相似性距離計(jì)算

零件模型的形狀特征由其尺度不變形狀特征向量集決定。對(duì)于兩個(gè)零件模型，直接兩兩比較它們尺度不變形狀特征向量集合中的向量是不合適的，因?yàn)槠浼现幸话惆瑪?shù)目很多的高維向量，計(jì)算和存儲(chǔ)的耗時(shí)與耗費(fèi)都很大。

本文采用 BoF（bag of features）的方式來(lái)減少待比較向量的數(shù)目。BoF是一種特征數(shù)據(jù)集比較方法，它源于文本檢索和自然語(yǔ)言處理領(lǐng)域里的Bag of Words策略。BoF方法的具體特征數(shù)據(jù)集比較過(guò)程如下：

首先從訓(xùn)練數(shù)據(jù)庫(kù)中的三維模型上采集大量尺度不變形狀特征，然后對(duì)這些形狀特征進(jìn)行聚類(lèi)。聚類(lèi)后形成的各個(gè)類(lèi)可以視為反復(fù)出現(xiàn)的典型形狀特征，因此把每個(gè)類(lèi)的類(lèi)中心構(gòu)造為一個(gè)形狀碼，全部類(lèi)中心的形狀碼就構(gòu)成了“形狀碼本”。三維模型上的每個(gè)原始尺度不變特征都可以用“形狀碼本”中和它最近的“形狀碼”代替。構(gòu)建好形狀碼本后，對(duì)一個(gè)三維模型遍歷其尺度不變形狀特征向量集，找到所有尺度不變特征向量所對(duì)應(yīng)的形狀碼，同時(shí)把每個(gè)形狀碼對(duì)應(yīng)的尺度不變特征向量數(shù)目統(tǒng)計(jì)為直方圖，該形狀碼直方圖表示了形狀碼本中各碼在模型上出現(xiàn)的頻率。圖2為形狀碼生成過(guò)程示意圖。

模型間“部分－整體”的形狀匹配具有不對(duì)稱(chēng)含義，例如手臂可和人體相匹配，但反之不然。為了實(shí)現(xiàn)“部分－整體”的形狀匹配，需采用一種非對(duì)稱(chēng)距離函數(shù)。本文采用Kullback－Leibler距離［16］（簡(jiǎn)稱(chēng)KL距離）作為模型間 “部分－整體”匹配的距離計(jì)算公式。KL距離具有不對(duì)稱(chēng)性。假如P＝｛pi｝和Q＝｛qi｝分別代表兩個(gè)直方圖，那么只有當(dāng)P的所有分量都能與Q中的分量（可能是Q中部分分量）對(duì)應(yīng)時(shí)，DKL（P‖Q）才有較小值，否則將有較大值。KL距離的這個(gè)性質(zhì)正是“部分－整體”匹配所需要的。

圖2 形狀碼直方圖的生成過(guò)程

KL距離可表示為

KL距離公式中有對(duì)數(shù)運(yùn)算，而距離計(jì)算是檢索時(shí)需大量執(zhí)行的操作，所以要考慮優(yōu)化高維向量對(duì)數(shù)運(yùn)算的效率。依三維模型數(shù)據(jù)庫(kù)規(guī)模大小和模型種類(lèi)的不同，形狀碼本中形狀碼的數(shù)目（即P、Q的維度）在幾百至幾千之間。不過(guò)形狀碼直方圖向量一般具有稀疏性，所以P、Q中的大多數(shù)分量為零，利用這個(gè)特點(diǎn)可以構(gòu)造出基于查找表的快速對(duì)數(shù)運(yùn)算算法：將P、Q的分量量化為［0，255］內(nèi)的整數(shù)，然后構(gòu)造出256×256的二維數(shù)組ArrLog，ArrLog中每個(gè)元素存儲(chǔ)了P的某個(gè)分量值與Q的某個(gè)分量值之比的對(duì)數(shù)值。這樣就將對(duì)數(shù)運(yùn)算轉(zhuǎn)化成了對(duì)ArrLog中特定元素的訪問(wèn)取值操作，計(jì)算時(shí)間得以大量節(jié)省。

5 實(shí)驗(yàn)分析

實(shí)驗(yàn) 使 用 ESB（engineering shape benchmark）模型庫(kù)［17］來(lái)測(cè)試描述符的檢索性能。原始的ESB模型庫(kù)只含有已分類(lèi)的獨(dú)立零件模型，并不包含“子部件－完整部件”零件模型對(duì)。所以為了測(cè)試“部分－整體”匹配的準(zhǔn)確度，本文選取了ESB的6個(gè)類(lèi)中的零件模型，用建模工具將每個(gè)零件切分成2～3個(gè)部件。

本文采用信息檢索領(lǐng)域中常用的查準(zhǔn)率－查全率（precision－recall）［18］指標(biāo)來(lái)衡量檢索性能。查準(zhǔn)率是指檢索系統(tǒng)只返回相關(guān)對(duì)象的能力，查全率是指檢索系統(tǒng)返回所有相關(guān)對(duì)象的能力。假設(shè)C代表數(shù)據(jù)庫(kù)中所有相關(guān)對(duì)象的數(shù)目（即被查詢(xún)對(duì)象所屬類(lèi)中的對(duì)象數(shù)目），在前A個(gè)返回結(jié)果中有N個(gè)是相關(guān)對(duì)象，那么查準(zhǔn)率為N/A，查全率為N/C。查準(zhǔn)率和查全率之間存在制約關(guān)系，在非理想情況下隨著查全率的提高查準(zhǔn)率會(huì)下降，在查準(zhǔn)率－查全率圖中越靠近右上角的曲線代表越好的檢索性能。

實(shí)驗(yàn)測(cè)試了不同灰度體素化預(yù)處理情況下本文所采用的形狀特征的檢索性能。為了進(jìn)行對(duì)比，測(cè)試了 Ohbuchi等［13］以及 Cornea等［6］方法的性能。Ohbuchi等［13］的方法是近年來(lái)本研究領(lǐng)域中檢索準(zhǔn)確度排名前列的方法，Cornea等［6］的方法是一種典型的利用模型拓?fù)浣Y(jié)構(gòu)信息構(gòu)建特征的方法。實(shí)驗(yàn)所得的查準(zhǔn)率－查全率曲線如圖3所示。圖3中的Curvature代表在基于離散高斯曲率的灰度體素化預(yù)處理情況下，本文方法的查準(zhǔn)率－查全率曲線；Area代表在基于面積的灰度體素化預(yù)處理情況下，本文方法的查準(zhǔn)率－查全率曲線。

圖3 查準(zhǔn)率－查全率曲線

從圖3可以看到，本文方法要好于Cornea方法；基于離散高斯曲率的體素化效果要略好于基于面積的體素化效果，但兩者的性能均稍次于Ohbuchi方法。

表1所示為4種方法的特征提取時(shí)間。進(jìn)行實(shí)驗(yàn)的計(jì)算機(jī)配置是 CPU Intel Core2Duo 2.53GHz，內(nèi)存3GB，操作系統(tǒng) Windows XP Professional。

表1 特征提取時(shí)間

由于Ohbuchi方法需要渲染和計(jì)算大量的二維投影圖像，所以它的特征提取時(shí)間很長(zhǎng)。Cornea方法特征提取時(shí)間也比較長(zhǎng)，主要是模型骨架的抽取較為耗時(shí)。本文所提出的方法計(jì)算時(shí)間最短，其中模型灰度體素化占用了大部分時(shí)間。因此，如需進(jìn)一步優(yōu)化本文方法，可考慮設(shè)計(jì)基于GPU通用計(jì)算技術(shù)的灰度體素化加速算法。

另外，進(jìn)行Ohbuchi方法特征比較步驟所耗費(fèi)的時(shí)間要明顯高于其他三種方法。這是因?yàn)镺hbuchi方法需要窮舉式比對(duì)兩模型所有的投影圖像，因此Ohbuchi方法的檢索實(shí)時(shí)性是很差的。

6 結(jié)束語(yǔ)

本文介紹了一種基于局部形狀特征的機(jī)械零件三維模型檢索算法，首先將網(wǎng)格模型轉(zhuǎn)化為灰度體素模型，通過(guò)三維體素SIFT算法提取尺度不變形狀特征，然后利用BoF方法建立形狀碼直方圖，模型之間的形狀相似性由形狀碼直方圖向量間的KL距離求得。實(shí)驗(yàn)表明本文所提出的方法具有較高的檢索準(zhǔn)確性，同時(shí)計(jì)算時(shí)間消耗合理，能夠應(yīng)用于管理大規(guī)模零件庫(kù)，為設(shè)計(jì)重用提供支持。

［1］鄭伯川，彭維，張引，等.3D模型檢索技術(shù)綜述［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2004，16（7）：873－881.

［2］Tangelder J，Veltkamp R.A Survey of Content Based 3DShape Retrieval Methods［J］.Multimedia Tools Appl.，2008，39（3）：441－471.

［3］Ferreira A，Marini S，Attene M，et al.Thesaurus－based 3DObject Retrieval with Part－in－whole Matching［J］.Int.J.Comput.Vis.，2009，89（2/3）：1405－1573.

［4］Wessel R，Klein R.Learning the Compositional Structure of Man－made Objects for 3DShape Retrieval［C］//Proceedings of Eurographics 2010 Workshop on 3DObject Retrieval.Norrkoping，Sweden：Springer，2010：39－46.

［5］Chen X B，Golovinskiy A，F(xiàn)unkhouser T.A Benchmark for 3DMesh Segmentation［J］.ACM Transactions on Graphics，2009，28（3）：73－85.

［6］Cornea N D，Demirci M F，Silver D，et al.3DObject Retrieval Using Many－to－many Matching of Curve Skeletons［C］//IEEE International Conference on Shape Modeling and Applications.Cambridge，MA，USA：IEEE Computer Society，2005：368－373.

［7］Biasotti S，Marini S，Spagnuolo M，et al.Subpart Correspondence by Structural Descriptors of 3D Shapes［J］.Computer－Aided Design，2006，38（9）：1002－1019.

［8］Funkhouser T，Shilane P.Partial Matching of 3D Shapes with Priority－driven Search［C］//Symposium of Geometry Processing.Sardinia，Italy：Eurographics Association，2006：131－142.

［9］Shilane P，F(xiàn)unkhouser T.Selecting Distinctive 3D Shape Descriptors for Similarity Retrieval［C］//IEEE International Conference on Shape Modeling and Applications.Matsushima，Japan：IEEE Computer Society，2006：108－117.

［10］Shilane P，F(xiàn)unkhouser T.Distinctive Regions of 3DSurfaces［J］.ACM Transactions on Graphics，2007，26（2）：1－15.

［11］Lowe D G.Distinctive Image Features from Scale－invariant Keypoints［J］.International Journal of Computer Vision，2004，60（2）：91－110.

［12］Bakken T.An Evaluation of the SIFT Algorithm for CBIR［EB/OL］.（2007－08－16）［2012－04－25］.http：//caim.uib.no/publications/Bakken＿N30－2007.pdf.

［13］Ohbuchi R，Osada K，F(xiàn)uruya T，et al.Salient LocalVisual Features for Shape－based 3DModel Retrieval［C］//IEEE International Conference on Shape Modeling and Applications.New York，USA：IEEE Computer Society，2008：93－102.

［14］方惠蘭，王國(guó)瑾.三角網(wǎng)格曲面上離散曲率估算方法的比較與分析［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2005，17（11）：2500－2507.

［15］Flitton G T，Breckon T P，Megherbi N.Object Recognition Using 3DSIFT in Complex CT Volumes［C］//Proceedings of the British Machine Vision Conference. Aberistwyth， UK： BMVA Press，2010：1－12.

［16］Kullback S，Leibler R A.On Information and Sufficiency［J］.Annals of Mathematical Statistics，1951，22（1）：79－86.

［17］Jayanti S，Kalyanaraman Y，Iyer N，et al.Developing an Engineering Shape Benchmark for CAD Models［J］.Computer－Aided Design，2006，38（9）：939－953.

［18］Singhal A.Modern Information Retrieval：a Brief Overview［J］.Bulletin of the IEEE Computer Society Technical Committee on Data Engineering，2001，24（4）：35－42.