基于廣義變換矩陣的機械零件三維模型骨架匹配

（上海理工大學(xué) 機械工程學(xué)院，上海 200093）

設(shè)計零件時可以參考與之相似的零件，因此，如何在眾多零件中準(zhǔn)確快速檢索到類似零件是一個重要命題。You等[1]基于邊界表示法構(gòu)建模型的屬性圖，表達模型的形狀和拓?fù)浣Y(jié)構(gòu)，然后根據(jù)屬性圖找出模型之間的最大公共子圖，提出了針對局部特征的三維模型檢索方法。Cheng等[2]在模型表面計算隨機兩點間的距離獲得三維模型幾何特征的D2形狀分布圖，通過比較形狀分布曲線的相似度得到模型的相似度，但隨著計算的隨機采樣點達到一定數(shù)目時，外形特征不相似的模型也可能有大致相同的形狀分布曲線。徐敬華等[3]提出了基于遞歸分割的機械零件三維形狀結(jié)構(gòu)檢索方法，首先將機械零件歸一化處理，然后遞歸實體分割建立有序的滿二叉樹，通過計算非根節(jié)點實體構(gòu)建特征矢量之間的相似度，得到零件之間的相似度。董雁等[4]基于裝配結(jié)構(gòu)相似提出了一種零件檢索方法，通過功能面鄰接圖和定性幾何約束圖定義零件裝配結(jié)構(gòu)定性模型，用符號對裝配結(jié)構(gòu)進行編碼，利用裝配結(jié)構(gòu)碼實現(xiàn)相似結(jié)構(gòu)零件檢索，這種方法側(cè)重于機械零件之間的功能相似性。EI-Mehalawi等[5]提出了一種基于幾何和拓?fù)湎嗨贫鹊娜S機械零件檢索方法，將零件模型轉(zhuǎn)化為STEP格式，根據(jù)零件的結(jié)構(gòu)數(shù)據(jù)來構(gòu)造零件模型圖，通過比較模型圖的相似度來得到零件相似度，這種方法計算量較大。白靜[6]提出基于擴展特征樹的三維CAD模型相似評價方法，以三維CAD模型的邊界表示為輸入，通過交互定義設(shè)計特征及自動識別特征間關(guān)系的方法建立其擴展特征樹，并通過非精確的樹匹配算法及一種自適應(yīng)的權(quán)重分配方案實現(xiàn)三維CAD模型間的相似評價。由于很難統(tǒng)一標(biāo)準(zhǔn)的特征樹，因此，這種檢索方法具有一定的局限性和主觀性。Hajij等[7]基于Reeb圖理論，將三維網(wǎng)格化的模型分割成若干個褲子結(jié)構(gòu)，這種褲子結(jié)構(gòu)的特點是：分割后的每個模型具有3個邊界虧格為零且為可定向的表面。由于機械零件的三維模型很難分割成褲子結(jié)構(gòu)，因此，這種方法很難應(yīng)用于零件檢索。李雷等[8]針對現(xiàn)有的曲線骨架提取方法不是很理想的現(xiàn)狀，提出了一種新的曲線骨架提取方法。運用經(jīng)典集合覆蓋問題模型，對中值面進行優(yōu)化形成中值圖，根據(jù)中值圖以收縮的方式生成曲線骨架，但這種方法只適用于類似于人體具有管狀結(jié)構(gòu)的模型。

針對機械零件模型骨架，借鑒機器人學(xué)中描述廣義連桿之間關(guān)系的理論方法，本文提出一種基于廣義變換矩陣的機械零件三維模型骨架匹配方法。對骨架枝建立廣義變換矩陣，通過計算匹配矩陣的相似度得到骨架的相似度，進而得到機械零件三維模型的相似度。

1 機械零件模型骨架

要實現(xiàn)機械零件三維模型檢索，首先需要將零件模型以一定方式進行表示，線性骨架是物體的一種降維表示，可以直觀簡潔地表示出機械零件三維模型的形狀和拓?fù)浣Y(jié)構(gòu)。由于常見的機械零件模型表面主要由平面和相對規(guī)則的曲面組成，因此，所提取出的骨架可以看成由若干骨架點相連構(gòu)成。本文將針對由骨架點構(gòu)成的機械零件三維模型骨架，研究骨架的匹配計算。機械零件模型骨架可以根據(jù)文獻[9]中所述的電場法來生成。首先對零件模型進行預(yù)處理，過濾掉零件模型上的一些附加特征，如螺紋、倒角及鍵槽等，然后假設(shè)模型表面均勻分布正電荷，根據(jù)物理靜電學(xué)知識可知模型內(nèi)部某點存在最小電勢點，最小電勢點的位置即為零件骨架的骨架點，連接相鄰骨架點形成完整模型骨架。圖1為根據(jù)文獻[9]的方法所生成的模型骨架。

圖1 提取模型 1 的骨架Fig.1 Extracting the skeleton of model one

2 骨架相似度計算

骨架體現(xiàn)零件模型的整體特征。本文將2個骨架點之間的連線稱為骨架枝，整個骨架是由若干段骨架枝構(gòu)成的。工業(yè)機器人學(xué)[10]中的機械手是由一系列的連桿組成的，骨架枝可以看成連桿，運用機械手的相關(guān)知識，相鄰坐標(biāo)間及其相應(yīng)連桿可以用廣義變換矩陣來表示。因此，骨架枝也可以通過廣義變換矩陣來表示，通過計算廣義變換矩陣的相似度得到骨架枝的相似度，從而找到相匹配的骨架枝，進而得到整個骨架的相似度。

2.1 構(gòu)建骨架枝的 T 矩陣

建立機器人運動模型常用D-H（Denavit-Hartenberg）參數(shù)法[11]，這種方法能很好地表示出機械手連桿之間的位置形狀信息。根據(jù)機械手連桿的相關(guān)知識，為每一個連桿建立一個坐標(biāo)系，描述一個連桿坐標(biāo)系與下一個連桿坐標(biāo)系間相對關(guān)系的齊次變換矩陣稱為A矩陣，2個或2個以上的A矩陣的乘積，表示連桿相對于固定坐標(biāo)系位姿，稱為T矩陣。將這一理論運用到骨架枝相互關(guān)系的建立上，構(gòu)建骨架枝的T矩陣。

骨架由若干個骨架點（G0，G1，G2，···，Gn）構(gòu)成，設(shè)模型的質(zhì)心為O點 ，將最靠近O點的骨架點記為G0，與G0相鄰的骨架點記為G1（與G0相鄰的骨架點，可能不止一個，任意指定其中之一為G1點，只要G0和G1的連線是骨架枝即可）。首先建立固定坐標(biāo)系，記為{0}，建立的方法為：以G0為原點建立笛卡爾直角坐標(biāo)系，模型的最小包絡(luò)長方體的最大邊長與y0軸平行，最小邊長與z0軸平行，中間大小的邊長與x0軸平行，如果零件的最小包絡(luò)長方體某兩條，甚至三條邊長度相等，則任選其中一條邊與坐標(biāo)軸平行。建立骨架枝的坐標(biāo)系{1}，建立的方法為：仍然以G0為原點，即坐標(biāo)系{0}和{1}原點相同，骨架枝為x1軸，方向由G0指向G1，根據(jù)右手直角坐標(biāo)系法則確定y1軸的方向和z1軸的方向。再以G1點為原點建立骨架枝的坐標(biāo)系{2}，骨架枝為x2軸，方向由G1指向G2，根據(jù)右手直角坐標(biāo)系法則確定y2軸的方向和z2軸的方向。依此類推，在每個骨架點處建立一個坐標(biāo)系，也就是對每個骨架枝建立了一個坐標(biāo)系。一個骨架枝坐標(biāo)系相對于下一個骨架枝坐標(biāo)系間相對關(guān)系的廣義變換Ai矩陣[10]為

式中：i=1,2,···,m，m為 骨架枝數(shù)；bi-1表示沿著xi-1軸，從zi-1軸移動到zi軸的距離；αi-1表示繞著xi-1軸，從zi-1軸旋轉(zhuǎn)到zi軸的角度；di表示沿著zi軸，從xi-1軸移動到xi軸的距離；θi表示繞著zi軸，從xi-1軸旋轉(zhuǎn)到xi的角度。

A1矩陣表示骨架枝的坐標(biāo)系{1}相對于固定坐標(biāo)系{0}的位姿，A2矩陣表示骨架枝的坐標(biāo)系{2}相對于坐標(biāo)系{1}的位姿，那么，坐標(biāo)系{2}相對于固定坐標(biāo)系{0}的位姿可用A1和A2的乘積，用T2來表示。

同理，A3矩陣表示坐標(biāo)系{3}相對于{2}的位姿，則{3}相對于{0}的位姿為

依此類推，建立每一個骨架枝相對于固定坐標(biāo)系{0}的T矩陣。

圖2是圖1所示模型1的骨架和坐標(biāo)系圖。G0點是最靠近質(zhì)心的骨架點，其他各點依次標(biāo)注為G1，G2，···，G12，共13個骨架點；，共13個骨架枝。以G0為原點建立固定坐標(biāo)系{0}，模型1的最小包絡(luò)長方體的最大邊長與y0軸平行，最小邊長與z0軸平行（z0軸垂直紙面向外），中間大小的邊長與x0軸平行。建立骨架枝的坐標(biāo)系{1}，仍然以G0為原點，骨架枝為x1軸，方向由G0指向G1，根據(jù)右手直角坐標(biāo)系法則確定y1軸的方向和z1軸的方向。再以G1點為原點建立骨架枝的坐標(biāo)系{2}，骨架枝為x2軸，方向由G1指向G2，根據(jù)右手直角坐標(biāo)系法則確定y2軸的方向和z2軸的方向。所有z軸均垂直紙面向外，為簡化圖形，未畫出。依次類推，在每個骨架點處建立坐標(biāo)系，也就是對每個骨架枝建立了一個坐標(biāo)系。

圖2 模型 1 的骨架及坐標(biāo)系Fig.2 Skeleton and coordinate system of model one

根據(jù)式（1）計算A1矩陣。b0是沿著x0軸，從z0軸移動到z1軸的距離，為0；α0是繞著x0軸，從z0軸旋轉(zhuǎn)到z1軸的角度，為0；d1表示沿著z1軸，從x0軸移動到x1軸的距離，為0；θ1表示繞著z1軸，從x0軸旋轉(zhuǎn)到x1的角度，為75.000°。將這些數(shù)值代入式（1）中，得到式（4）。

因為，A1矩陣表示骨架枝的坐標(biāo)系{1}相對于固定坐標(biāo)系{0}的位姿，所以，A1=T1。

根據(jù)式（1）計算A2矩陣。b1是沿著x1軸，從z1軸移動到z2軸的距離，為12.000；α1是繞著x1軸，從z1軸旋轉(zhuǎn)到z2軸的角度，為0；d2表示沿著z2軸，從x1軸移動到x2軸的距離，為0；θ2表示繞著z2軸，從x1軸旋轉(zhuǎn)到x2的角度，為-11.300°。將這些數(shù)值代入式（1）中，得到式（5）。

A2矩陣表示骨架枝的坐標(biāo)系{2}相對于骨架枝坐標(biāo)系{1}的位姿，所以，坐標(biāo)系{2}相對于固定坐標(biāo)系{0}的位姿按式（2）計算。

同理，計算A3和T3，A4和T4，···，A13和T13，完成每一個骨架枝的T矩陣計算。需要說明的是，若骨架枝回到原點時如何處理的問題。如圖2所示，骨架枝回到G0點，則A8矩陣表示骨架枝的坐標(biāo)系{8}相對于骨架枝坐標(biāo)系{7}的位姿，T8=A1A2A3A4A5A6A7A8=T7A8表示坐標(biāo)系{8}相對于固定坐標(biāo)系{0}的位姿。而骨架枝構(gòu)建A9矩陣時要相對于固定坐標(biāo)系{0}，即A9矩陣表示骨架枝的坐標(biāo)系{9}相對于{0}的位姿，所以，A9=T9。

2.2 計算 T矩陣的相似度

為了計算T矩陣的相似度，將4×4的T矩陣轉(zhuǎn)化成一個16維的向量，記為TR，可采用Matlab中的reshape函數(shù)reshape(T,1,16)來實現(xiàn)[12]，即TR按T矩陣的列依次取數(shù)據(jù)生成，如式（7）所示。設(shè)

將T矩陣轉(zhuǎn)化為向量TR后，引用統(tǒng)計學(xué)中的相關(guān)性度量方法，通過計算2個向量的皮爾遜相關(guān)系數(shù)[13]就可以得到2個T矩陣的相似度sim(Tn,Tm)。

式中：Tn和Tm表示2個T矩陣；TRn是由Tn矩陣按式（7）生成的一維向量：Rn是Tn生成向量中所有元素的平均值；TRm是由Tm生成的向量；Rm是Tm生成向量中所有元素的平均值；TRni為TRn的一個元素；TRmi為TRm的一個元素。

2.3 搜索匹配 T矩陣

設(shè)骨架P有p個骨架枝，則構(gòu)建了p個T矩陣，按照式（7）生成了相應(yīng)的p個TR向量。同理，另一骨架Q有q個 骨架枝，則構(gòu)建了q個T矩陣，生成了相應(yīng)的q個TR向 量，p個TR向 量和q個TR向量兩兩間根據(jù)式（8）進行計算，得到p×q對相似度值，搜索得到min(p,q)對匹配向量，即找到min(p,q)對匹配的T矩陣。搜索方法的步驟：

步驟1將p×q對相似度值從高到低排列，存放在臨時數(shù)據(jù)表1中。

表1 臨時數(shù)據(jù)表Tab.1 Temporary data table

步驟2取表1中第一行，即找到一對匹配T矩陣(Tn,Tm)，放在一張新表中（結(jié)構(gòu)同表1）；然后刪除表1中所有包含Tn和Tm的行。

步驟3重復(fù)步驟2，直到表1為空。這樣就找到了min(p,q)對匹配T矩陣，并被記錄在新表中。

圖3為模型2的骨架及其坐標(biāo)系，共有7個骨架枝，每一骨架枝構(gòu)建一個T矩陣，分別為。

圖3 模型 2 的骨架及其坐標(biāo)系Fig.3 Skeleton of model two and its coordinate system

將模型1和模型2的T矩陣兩兩進行相似度計算，搜索匹配對。例如，模型1的骨架枝和模型2的骨架枝構(gòu)建的矩陣T9和分別為

根據(jù)式（7），

2.4 計算骨架相似度

找到相匹配的T矩陣，就是找到了匹配的骨架枝，2個骨架P和Q的相似度sim(P,Q)為：分子是相匹配的2個骨架枝T矩陣的相似度乘以該對骨架枝的長度，并計算所有匹配對的乘積之和，分母為個骨架所有骨架枝的長度總和，如式（9）所示。

式中：Tn和Tm代表上面計算出的相匹配的T矩陣對；sim(Tn,Tm)是其相似度值；Ln和Lm代表各自的骨架枝長度，共有min(p,q)對；LP表示骨架P所有骨架枝的長度總和；LQ表示骨架Q所有骨架枝的長度總和。

圖2和圖3中模型1骨架和模型2骨架的骨架枝總長分別為257，184。相匹配的骨架枝長度分別為：L7=20，L1′=10，L2=10，L2′=29，L9=33，L3′=29，L10=31，L4′=34，L11=43，L5′=37，L12=34，L6′=38，L13=7，L7′=7。代入式（9）中，可得兩骨架相似度

3 實例驗證

為了驗證本文算法的可行性和準(zhǔn)確性，將圖1示例零件與自行開發(fā)的檢索系統(tǒng)中的機械零件進行匹配。測試數(shù)據(jù)庫已按照軸套類、輪盤蓋類、叉架類、箱體類這4大類零件分類。圖1示例零件屬于叉架類，故在叉架類零件子集中進行匹配。表2為相似度數(shù)值從大到小排列的前20個機械零件。

根據(jù)檢索結(jié)果可知，表2中0056號機械零件與圖1示例模型1的相似度最高，此零件與圖1模型1在結(jié)構(gòu)和功能上有很大的相似性，因此，模型1在加工制造等方面完全可以借鑒0056號機械零件相應(yīng)的制造工藝。從表2中也可以看出，0326號正是圖3模型2，它與圖1所示模型1相似度為0.760。

表2 圖1 示例零件的檢索結(jié)果Tab.2 Retrieval results for the sample part of figure 1

4 實驗分析

為了驗證本文算法的有效性和檢索效率，將本文算法、D2形狀分布算法[2]和基于遞歸分割算法[3]從計算量和查準(zhǔn)率-查全率曲線（P-R曲線）兩方面進行對比。本算法的實驗平臺為Inte(R)Core(TM)i5-8250UCPU@1.60GHz1.80GHz，內(nèi)存 8GB的華為 PC 機以及 Visual Studio 2010，SolidWorks 2016軟件環(huán)境，以前面所述的機械零件庫作為測試數(shù)據(jù)庫。

在計算量上，由于大多數(shù)機械零件形狀相對規(guī)則，骨架枝的數(shù)量并不多，因此，計算骨架枝所對應(yīng)的T矩陣相似度的計算量較小?；谶f歸分割算法首先將零件實體分割，然后建立有序的滿二叉樹，比較非根節(jié)點實體的相似度，得到零件的相似度，計算量明顯較大。本文算法的計算量小于基于遞歸分割算法。D2形狀分布算法只考慮單一特征的表面隨機樣點間的距離，計算量最小。在本文所述實驗平臺的基礎(chǔ)上，采用上述3種算法檢索同一個機械零件模型所需時間如表3所示。

表3 檢索相似零件耗時量Tab.3 Time-consuming of retrieving similar parts

查準(zhǔn)率-查全率曲線是評判檢索系統(tǒng)準(zhǔn)確性的重要手段。圖4是上述3種算法的P-R曲線，可以看出，在查全率為0.3時，本文算法的查準(zhǔn)率為0.63，基于遞歸分割算法的查準(zhǔn)率為0.69，D2形狀分布算法的查準(zhǔn)率只有0.25。當(dāng)查全率上升到0.7時，本文算法的查準(zhǔn)率為0.36，基于遞歸分割算法的查準(zhǔn)率為0.32，D2算法的查準(zhǔn)率只有0.08?？梢钥闯?，本文算法的查準(zhǔn)率-查全率均優(yōu)于D2形狀分布算法；當(dāng)查全率低于0.55時，本文算法的查準(zhǔn)率略低于基于遞歸分割算法，但是，當(dāng)查全率高于0.55時，本文算法的查準(zhǔn)率略高于基于遞歸分割算法。

圖4 查準(zhǔn)率-查全率曲線圖Fig.4 Accuracy-recall curve

綜合考慮計算量和查準(zhǔn)率-查全率兩個方面可以看出，本文算法在機械零件檢索方面有一定優(yōu)勢。雖然計算速度略低于D2形狀分布算法，但是，P-R曲線性能明顯好于D2形狀分布算法；本文算法與基于遞歸分割算法的P-R曲線有交叉，各自在某一范圍有一定的優(yōu)勢，但是，本文算法的計算速度明顯優(yōu)于基于遞歸分割算法。綜上所述，本文算法具有較好的實用性。

5 結(jié) 論

a.借鑒機器人學(xué)中描述廣義連桿之間關(guān)系的理論方法，將機械零件骨架枝看成連桿，在骨架點處建立固定坐標(biāo)系及骨架枝坐標(biāo)系，構(gòu)建骨架枝的廣義變換T矩陣。

b.將4×4的T矩陣轉(zhuǎn)化成16維的向量，通過計算2個向量的皮爾遜相關(guān)系數(shù)得到2個T矩陣的相似度，即得到2個骨架枝的相似度；搜索到相匹配的骨架枝后，計算整個骨架的相似度。

c.本文提出的匹配算法不僅適用于基于電場法建立的骨架，而且對其他方式建立的骨架，只要存在骨架點和骨架枝都具有適用性。通過實例驗證和實驗分析，綜合考慮計算量和查準(zhǔn)率-查全率兩方面，本文算法高效、準(zhǔn)確，綜合性能優(yōu)于D2形狀分布算法和基于遞歸分割算法。