基于機械零件三維模型骨架相似性度量算法

張祥+劉陽陽+陽鼎

摘要： 提出了一種基于機械零件模型骨架的檢索方法.將零件庫中提取的機械零件進行預處理去倒角、圓角以及圓孔等，保證處理之后得到無中空結構的零件模型；運用電場法對預處理后的零件模型骨架提取，得到完整的骨架模型；利用骨架樹匹配計算出零件模型相似度.試驗證明該方法能夠快速實現零件模型骨架檢索.

關鍵詞： 機械零件； 預處理； 電場法； 骨架樹； 骨架提取

中圖分類號： TH 128 文獻標志碼： A

機械零件骨架可以形象地表示出其拓撲結構特征，作為零件三維模型幾何和拓撲結構的簡化表示[1]，被廣泛應用于機械設計、醫療機械等行業[2].目前關于骨架提取的方法越來越多[3-5].本文基于物理學知識，沿著電場線方向電勢降低，即隨著零件模型內部點到邊界點距離的增大電勢而降低，采用電場法實現對零件模型骨架的提取，提取骨架之后利用骨架的特征完成骨架的相似度計算[6].

1 機械零件三維模型預處理

根據三維軟件建模過程的特性，零件模型的特征是逐漸疊加形成，其中包括基準特征，輔助特征以及附加特征等.附加特征包括倒角、圓孔、鍵槽等特征，附加特征是在不改變零件模型基本特征主要形狀的前提下，對已有特征進行局部修飾的建模特征，而零件模型的骨架主要取決于零件的主干部位，因此它的存在并不影響零件模型的結構工藝以及整體拓撲結構.

如圖1（a）中的零件預處理之后，得到的模型均為無中空結構零件模型，如圖1（b）所示.

2 骨架提取

零件骨架的提取在一定程度上保留了零件原有的拓撲關系以及零件的穩定性.骨架的直觀性、簡潔性、連通性以及中心性更能使復雜的零件模型簡單化，所以骨架的提取算法被廣泛應用.

2.1 機械零件起始點的選擇

機械零件經過預處理之后得到零件模型的主干部分.骨架起始點的選擇是保證骨架能順利進行的前提.每個零件都有頂點，頂點是面與面、線與線之間的交點.其作用不僅決定了零件模型的外形結構特征，也影響零件模型的三維立體空間的分布.經過預處理之后的機械零件模型的外形表面通常是由平面、圓柱面、球面、球面圓、錐面以及各種曲率不同的曲面擬合組成.對于平面而言，零件骨架的起始點選擇相對容易；對于規則或者不規則的曲面而言，零件骨架的起始點選擇原則是選擇無限接近零件頂點的內部模型點，而不直接選擇零件模型的頂點，是由于根據物理電學知識，零件模型表面到模型內部電勢隨著距離的減小而增大，因此可知零件表面的電勢無窮大，而零件內部必然存在電勢較低的點.頂點屬于表面一部分，電勢無窮大，當頂點向內部方向移動時，會發生勢能的突變，受力程度難以控制，所以零件骨架的起始點應選擇模型內部，但無限靠近頂點.如圖2所示.

2.2 機械零件模型骨架的提取

任何一個機械零件表面外形均帶有正電荷，而由于這些正電荷形成一個相對穩定的電場，電場線的方向總是垂直于機械零件模型的表面且由外向內，根據物理電學知識，零件模型表面到模型內部電勢隨著距離的減小而增大.因此可知零件表面的電勢無窮大，而零件內部必然存在電勢較低的點.

定義機械零件內任意點P的排斥力為：

式中：P為零件內沿著受力方向前進的一點；Bi為P點的電場線方向與邊界表面的交點；R為點Bi與P點之間的距離；n為P點的受力個數；m為力的階數，受力的大小分別為1/Rm.

由式（1）可知，隨著力的階數m的變化，電場力FP也隨著變化，根據文獻[7]，m=6時，試驗效果最佳.對于零件模型的一點，受到排斥力的作用，其合力方向即該點與相鄰面垂直方向電場排斥力的矢向量和.

零件模型點的方向和大小均已確定，如圖3所示.其中A為零件模型表面的頂點，對零件模型內無限接近頂點A的骨架起始點P進行受力分析.

圖3中Fi（i=1，2，3，…，6）分別對應零件模型邊界對起始點P的6個方向的電場斥力，6個力的方向和大小由式（1）可得，B1為零件模型表面邊界與電場線方向的交點，Fp為6個力的合力方向.因此設定單位步長并沿著合力方向移動，必然得到下一個點的目標.以此方法進行，最后得到電勢最小的點.以此方法得到骨架的路徑，生成骨架.如圖4（a）中從A，D，E，H各個骨架起始點出發至電勢最低處之前發生融合，到O1處，因此只需從O1處沿合力方向移動.如果兩個最小電勢點與已生成的骨架分枝或者零件模型沒有交叉點，則認為兩個點均為電勢最低點，因此可以將兩個電勢最低點相連，與起始點開始的骨架路徑組成一套完整的機械零件骨架，如圖4所示.

3 骨架形狀相似性

計算骨架相似首先建立模型骨架樹，完成對骨架枝的匹配尋找，其次計算骨架枝間的相似度[8].

3.1 骨架樹的建立

為了準確描述骨架的拓撲結構特征，將零件模型的骨架映射到二維樹結構中，形成骨架樹結構.

零件模型骨架存在任意兩個或者兩個以上線段相連的點，稱為骨架樹的節點.只有一個鄰接點的骨架稱為端點.任意兩個以上的鄰接點稱為分支點.以任何一個分支點為球心做出與零件模型表面相切的最大內切球，靠近零件模型重心或者具有最大球半徑的分支點稱為根節點.其余分支點稱為根節點的子節點.

圖5為機械零件模型的骨架，圖6為模型骨架樹.

3.2 骨架的相似度

由上述提取骨架方法可知，骨架起始點沿著合力方向按照一定步長得到骨架枝，然而得到的骨架枝是無數個離散曲線或直線的點.構成骨架枝的點的

得到的是空間曲線和環狀骨架枝；第二，當其中一組為零，另一組不為零時，則一個骨架枝為空間直線，另一個骨架枝為空間曲線.在對曲線各個數據點曲率計算相似度之前，要對離散的點進行匹配，判別離散點是否匹配，如式（2）所示：

曲線數據點匹配之后對骨架枝的相似度計算如式（4）所示：endprint

式中：fi和fj分別為骨架枝A和B的步長；m和n分別為兩個骨架枝的三維數據點集的數量.

對于上述第一種情況，采用差分法比較其相似度.由微分幾何學中相關理論可知，空間離散曲線可以分為函數擬合法和差分法，函數法難以通過函數表示生成骨架枝的多樣性和復雜性，故不采用.所以本文利用電場法生成步長相等的骨架枝的特性，因此采用差分法.

求出骨架枝每個數據點的曲率和弗朗內特標架，計算骨架枝上點的曲率和弗朗內特標架值來表示骨架枝之間的相似度大小.曲率和弗朗內特標架計算如式（5）所示[9]：

4 結 論

本文提出了基于機械零件骨架相似度算法，通過兩個階段完成.第一階段通過電場法生成模型骨架并轉換成骨架樹.第二階段通過匹配骨架枝進而計算整個骨架形狀相似度.主要采用空間離散曲線的曲率和弗朗內特標架進行空間曲線相似性計算.將骨架枝相似度匹配轉化成易于計算的點云空間曲線，具有較高的準確性和有效性.

參考文獻：

[1] AUO C K，TAI C L，CHU H K，et al.Skeleton extraction by mesh contraction[J].ACM Transactions on Graphics，2008，27（3）：441-449.

[2] LIVESU M，SCATENI R.Extracting curveskeletons from digital shapes ussing occluding contours[J].The Visual Computer，2013，29（9）：907-916.

[3] AURENHAMMER F.Voronoi diagrams a survey of a fundanmental geometric data structure[J].ACM Computering Surveys，1991，23（3）：345-405.

[4] XIE W J，THOMPSON R P，PERUCCHIO R.A topology preserving parallel 3D thinning algorithm for extracting the curveskeletons[J].Pattern Recognition，2003，36（7）：1529-1544.

[5] NIBLACK C W，Gibbons P B，Capson D W.Generating skeletons and centerlines from the distance transform[J].Graphical Models and Image Processing，1992，54（5）：420-437.

[6] 王桂平，王衍，任嘉辰.圖論算法理論，實現及應用[M].北京：北京大學出版社.2011.

[7] AHUJA N，CHUANG J H.Shape representation using a generalized potential field model[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，1997，19（2）：169-176.

[8] 朱文博，耿國慶，劉陽陽，等.基于骨架樹的機械零件三維模型檢索方法[J].機械工程學報，2016，52（13）：204-212.

[9] 馬國慶，陶萍萍，楊周旺.點云空間曲線的微分信息計算及匹配的方法[J].計算機工程與應用，2010，46（1）：164-168.endprint