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

王家樂 姜 波 黃逸民

浙江工商大學，杭州，310018

0 引言

隨著數字化技術和CAD技術的發展，三維模型被廣泛地用于機械設計領域。為了實現對海量機械零件模型數據的有效管理，特別是對已有的零件模型進行復用，用戶往往要從龐大的模型數據庫中查詢所需模型或者瀏覽相似三維模型的聚類。在設計新的三維形狀時，若能有效地從已有模型庫中找到相關模型并加以利用，則可大大減小工作量。

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

本文提出一種三維機械零件模型局部形狀特征提取方法，用提取到的局部形狀特征構建形狀特征向量，實現“部分－整體”的模型局部形狀檢索。

1 相關研究

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

近年來，三維模型局部形狀特征的研究逐漸興起。局部形狀特征提取算法的一般思想是：對三維模型某些局部區域單獨生成形狀特征向量，在衡量兩個模型的相似性時，以各自局部區域的形狀特征向量集為基礎進行計算。

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

這類基于子部件的局部形狀特征提取方法需要解決模型部件分割（part segmentation）的問題。而模型部件分割是比較困難的，分割算法往往由于要決定多個閾值而失去健壯性，或者需要用到復雜的機器學習機制［5］。一些利用了模型拓撲結構的檢索方法也可以視為是這種基于子部件的局部形狀描述符［6－7］，但拓撲結構提取算法一般對噪聲敏感，所以難以獲得穩定的部件分割結果。

構建局部形狀特征描述符的另一種思路是，在模型上尋找那些具有強形狀區分力的區域并且提取該區域的形狀特征向量，比較模型形狀時，用這些形狀特征向量間的距離來計算相似性。這類方法中具有代表性的是 Funkhouser等［8］和Shilane等［9－10］提出的優先隊列兩兩比較法。該方法先在模型上生成大量采樣點，然后提取采樣點周圍的某種形狀特征，通過兩兩比較這些形狀特征向量間的差異度，得到各采樣點所在區域的形狀區別度；比較模型間形狀時，構建一個優先級隊列以選取形狀區別力強的向量來計算相似度。

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

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

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

2 灰度體素化

體素空間相當于圖像空間在維度上擴展了一維，體素模型可視為三維空間中的“圖像”，所以SIFT操作可以較方便地應用于三維體素模型之上。大多數模型都是以三維網格（3DMesh）表示方式存儲的，需要先將網格模型轉換為體素模型。

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

（1）體素的灰度值代表包含在該體素內的網格模型面片的面積，如圖1a所示。

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

圖1 體素灰度值的定義

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

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

3 體素模型的SIFT算法

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

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

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

為提高特征的穩定性，還需對獲取的極值點進行篩選，以去除邊緣響應。篩選使用的不等式為［15］

式中，H為DOG函數的Hessian矩陣；r為經驗閾值，一般選取［10，50］內的整數，本文實驗中r取30。

僅當DOG值使式（2）的不等式成立時，該點才被選取為最后的特征點。得到特征點后，即可根據特征點鄰域體素的梯度方向構建尺度不變形狀特征向量。

4 特征向量構建和相似性距離計算

零件模型的形狀特征由其尺度不變形狀特征向量集決定。對于兩個零件模型，直接兩兩比較它們尺度不變形狀特征向量集合中的向量是不合適的，因為其集合中一般包含數目很多的高維向量，計算和存儲的耗時與耗費都很大。

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

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

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

圖2 形狀碼直方圖的生成過程

KL距離可表示為

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

5 實驗分析

實驗 使 用 ESB（engineering shape benchmark）模型庫［17］來測試描述符的檢索性能。原始的ESB模型庫只含有已分類的獨立零件模型，并不包含“子部件－完整部件”零件模型對。所以為了測試“部分－整體”匹配的準確度，本文選取了ESB的6個類中的零件模型，用建模工具將每個零件切分成2～3個部件。

本文采用信息檢索領域中常用的查準率－查全率（precision－recall）［18］指標來衡量檢索性能。查準率是指檢索系統只返回相關對象的能力，查全率是指檢索系統返回所有相關對象的能力。假設C代表數據庫中所有相關對象的數目（即被查詢對象所屬類中的對象數目），在前A個返回結果中有N個是相關對象，那么查準率為N/A，查全率為N/C。查準率和查全率之間存在制約關系，在非理想情況下隨著查全率的提高查準率會下降，在查準率－查全率圖中越靠近右上角的曲線代表越好的檢索性能。

實驗測試了不同灰度體素化預處理情況下本文所采用的形狀特征的檢索性能。為了進行對比，測試了 Ohbuchi等［13］以及 Cornea等［6］方法的性能。Ohbuchi等［13］的方法是近年來本研究領域中檢索準確度排名前列的方法，Cornea等［6］的方法是一種典型的利用模型拓撲結構信息構建特征的方法。實驗所得的查準率－查全率曲線如圖3所示。圖3中的Curvature代表在基于離散高斯曲率的灰度體素化預處理情況下，本文方法的查準率－查全率曲線；Area代表在基于面積的灰度體素化預處理情況下，本文方法的查準率－查全率曲線。

圖3 查準率－查全率曲線

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

表1所示為4種方法的特征提取時間。進行實驗的計算機配置是 CPU Intel Core2Duo 2.53GHz，內存3GB，操作系統 Windows XP Professional。

表1 特征提取時間

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

另外，進行Ohbuchi方法特征比較步驟所耗費的時間要明顯高于其他三種方法。這是因為Ohbuchi方法需要窮舉式比對兩模型所有的投影圖像，因此Ohbuchi方法的檢索實時性是很差的。

6 結束語

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

［1］鄭伯川，彭維，張引，等.3D模型檢索技術綜述［J］.計算機輔助設計與圖形學學報，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，Funkhouser 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，Funkhouser 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，Funkhouser 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，Furuya 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］方惠蘭，王國瑾.三角網格曲面上離散曲率估算方法的比較與分析［J］.計算機輔助設計與圖形學學報，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.