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

張祥+劉陽(yáng)陽(yáng)+陽(yáng)鼎

摘要： 提出了一種基于機(jī)械零件模型骨架的檢索方法.將零件庫(kù)中提取的機(jī)械零件進(jìn)行預(yù)處理去倒角、圓角以及圓孔等，保證處理之后得到無(wú)中空結(jié)構(gòu)的零件模型；運(yùn)用電場(chǎng)法對(duì)預(yù)處理后的零件模型骨架提取，得到完整的骨架模型；利用骨架樹匹配計(jì)算出零件模型相似度.試驗(yàn)證明該方法能夠快速實(shí)現(xiàn)零件模型骨架檢索.

關(guān)鍵詞： 機(jī)械零件； 預(yù)處理； 電場(chǎng)法； 骨架樹； 骨架提取

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

機(jī)械零件骨架可以形象地表示出其拓?fù)浣Y(jié)構(gòu)特征，作為零件三維模型幾何和拓?fù)浣Y(jié)構(gòu)的簡(jiǎn)化表示[1]，被廣泛應(yīng)用于機(jī)械設(shè)計(jì)、醫(yī)療機(jī)械等行業(yè)[2].目前關(guān)于骨架提取的方法越來(lái)越多[3-5].本文基于物理學(xué)知識(shí)，沿著電場(chǎng)線方向電勢(shì)降低，即隨著零件模型內(nèi)部點(diǎn)到邊界點(diǎn)距離的增大電勢(shì)而降低，采用電場(chǎng)法實(shí)現(xiàn)對(duì)零件模型骨架的提取，提取骨架之后利用骨架的特征完成骨架的相似度計(jì)算[6].

1 機(jī)械零件三維模型預(yù)處理

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

如圖1（a）中的零件預(yù)處理之后，得到的模型均為無(wú)中空結(jié)構(gòu)零件模型，如圖1（b）所示.

2 骨架提取

零件骨架的提取在一定程度上保留了零件原有的拓?fù)潢P(guān)系以及零件的穩(wěn)定性.骨架的直觀性、簡(jiǎn)潔性、連通性以及中心性更能使復(fù)雜的零件模型簡(jiǎn)單化，所以骨架的提取算法被廣泛應(yīng)用.

2.1 機(jī)械零件起始點(diǎn)的選擇

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

2.2 機(jī)械零件模型骨架的提取

任何一個(gè)機(jī)械零件表面外形均帶有正電荷，而由于這些正電荷形成一個(gè)相對(duì)穩(wěn)定的電場(chǎng)，電場(chǎng)線的方向總是垂直于機(jī)械零件模型的表面且由外向內(nèi)，根據(jù)物理電學(xué)知識(shí)，零件模型表面到模型內(nèi)部電勢(shì)隨著距離的減小而增大.因此可知零件表面的電勢(shì)無(wú)窮大，而零件內(nèi)部必然存在電勢(shì)較低的點(diǎn).

定義機(jī)械零件內(nèi)任意點(diǎn)P的排斥力為：

式中：P為零件內(nèi)沿著受力方向前進(jìn)的一點(diǎn)；Bi為P點(diǎn)的電場(chǎng)線方向與邊界表面的交點(diǎn)；R為點(diǎn)Bi與P點(diǎn)之間的距離；n為P點(diǎn)的受力個(gè)數(shù)；m為力的階數(shù)，受力的大小分別為1/Rm.

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

零件模型點(diǎn)的方向和大小均已確定，如圖3所示.其中A為零件模型表面的頂點(diǎn)，對(duì)零件模型內(nèi)無(wú)限接近頂點(diǎn)A的骨架起始點(diǎn)P進(jìn)行受力分析.

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

3 骨架形狀相似性

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

3.1 骨架樹的建立

為了準(zhǔn)確描述骨架的拓?fù)浣Y(jié)構(gòu)特征，將零件模型的骨架映射到二維樹結(jié)構(gòu)中，形成骨架樹結(jié)構(gòu).

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

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

3.2 骨架的相似度

由上述提取骨架方法可知，骨架起始點(diǎn)沿著合力方向按照一定步長(zhǎng)得到骨架枝，然而得到的骨架枝是無(wú)數(shù)個(gè)離散曲線或直線的點(diǎn).構(gòu)成骨架枝的點(diǎn)的

得到的是空間曲線和環(huán)狀骨架枝；第二，當(dāng)其中一組為零，另一組不為零時(shí)，則一個(gè)骨架枝為空間直線，另一個(gè)骨架枝為空間曲線.在對(duì)曲線各個(gè)數(shù)據(jù)點(diǎn)曲率計(jì)算相似度之前，要對(duì)離散的點(diǎn)進(jìn)行匹配，判別離散點(diǎn)是否匹配，如式（2）所示：

曲線數(shù)據(jù)點(diǎn)匹配之后對(duì)骨架枝的相似度計(jì)算如式（4）所示：endprint

式中：fi和fj分別為骨架枝A和B的步長(zhǎng)；m和n分別為兩個(gè)骨架枝的三維數(shù)據(jù)點(diǎn)集的數(shù)量.

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

求出骨架枝每個(gè)數(shù)據(jù)點(diǎn)的曲率和弗朗內(nèi)特標(biāo)架，計(jì)算骨架枝上點(diǎn)的曲率和弗朗內(nèi)特標(biāo)架值來(lái)表示骨架枝之間的相似度大小.曲率和弗朗內(nèi)特標(biāo)架計(jì)算如式（5）所示[9]：

4 結(jié) 論

本文提出了基于機(jī)械零件骨架相似度算法，通過(guò)兩個(gè)階段完成.第一階段通過(guò)電場(chǎng)法生成模型骨架并轉(zhuǎn)換成骨架樹.第二階段通過(guò)匹配骨架枝進(jìn)而計(jì)算整個(gè)骨架形狀相似度.主要采用空間離散曲線的曲率和弗朗內(nèi)特標(biāo)架進(jìn)行空間曲線相似性計(jì)算.將骨架枝相似度匹配轉(zhuǎn)化成易于計(jì)算的點(diǎn)云空間曲線，具有較高的準(zhǔn)確性和有效性.

參考文獻(xiàn)：

[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] 王桂平，王衍，任嘉辰.圖論算法理論，實(shí)現(xiàn)及應(yīng)用[M].北京：北京大學(xué)出版社.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] 朱文博，耿國(guó)慶，劉陽(yáng)陽(yáng)，等.基于骨架樹的機(jī)械零件三維模型檢索方法[J].機(jī)械工程學(xué)報(bào)，2016，52（13）：204-212.

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