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

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

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

1 機(jī)械零件模型骨架

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

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

2 骨架相似度計(jì)算

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 計(jì)算 T矩陣的相似度

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

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

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

2.3 搜索匹配 T矩陣

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

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

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

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

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

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

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

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

根據(jù)式（7），

2.4 計(jì)算骨架相似度

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

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

圖2和圖3中模型1骨架和模型2骨架的骨架枝總長(zhǎng)分別為257，184。相匹配的骨架枝長(zhǎng)度分別為：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 實(shí)例驗(yàn)證

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

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

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

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

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

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

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

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

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

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

5 結(jié) 論

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

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

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