基于Weisfeiler-Lehman 圖核算法的裝配體模型比較方法

左 咪，鄧 蘭，薛 婷，閆起源

（西安建筑科技大學(xué)機(jī)電學(xué)院，陜西 西安 710055）

1 引言

隨著三維掃描技術(shù)和計(jì)算機(jī)圖形學(xué)的發(fā)展以及計(jì)算機(jī)性能的提高，三維模型已成為繼聲音、圖像和視頻之后的第四種多媒體數(shù)據(jù)類型。機(jī)械領(lǐng)域的企業(yè)經(jīng)過(guò)多年的積累形成了包含豐富經(jīng)驗(yàn)知識(shí)信息的三維模型庫(kù)，日益發(fā)達(dá)的互聯(lián)網(wǎng)技術(shù)為人們對(duì)三維模型的共享和處理提供了條件，重用這些信息可以大大提高設(shè)計(jì)生產(chǎn)效率。三維信息相似度比較技術(shù)是模型信息檢索、通用結(jié)構(gòu)挖掘等三維信息重用的基礎(chǔ)。

目前對(duì)于三維模型信息比較主要基于：1 三維模型的三維特征提取匹配。但是在三維模型的特征提取過(guò)程中，不可避免的會(huì)簡(jiǎn)化部分三維模型的特征，且往往僅從三維模型幾何特征出發(fā)，進(jìn)而導(dǎo)致匹配過(guò)程的不完全精確。近年來(lái)，隨著產(chǎn)品全三維體系的不斷成熟，CAD 模型在工藝、功能和材料等非幾何信息描述方面能力的不斷增強(qiáng)，且參與模型定義的設(shè)計(jì)部門和專業(yè)日益增多，進(jìn)而形成了包含多源信息的CAD 模型[3]因此，基于模型的創(chuàng)建過(guò)程進(jìn)行的三維模型檢索從更加全面的角度進(jìn)行三維裝配體模型相似度比較技術(shù)可以從結(jié)構(gòu)設(shè)計(jì)、工藝設(shè)計(jì)、仿真驗(yàn)證工作和信息表達(dá)等多方面支持設(shè)計(jì)重用。

因此提出基于Weisfeiler-Lehman 圖核算法的裝配體模型比較方法。首先用圖模型對(duì)多源裝配體模型進(jìn)行信息的轉(zhuǎn)化表達(dá)并進(jìn)行初步信息歸類，形成裝配體類碼連接圖；將W-L 圖匹配算法和核函數(shù)綜合應(yīng)用，對(duì)裝配體類碼圖進(jìn)行相似度計(jì)算，實(shí)現(xiàn)裝配體之間的相似度計(jì)算。

2 裝配體類碼連接圖

裝配體模型中包含大量的零件及連接關(guān)系，每個(gè)零件又包含了外形、尺寸、位置、材料、工藝等多種信息。這些信息的數(shù)據(jù)類型種類繁雜、量大、存儲(chǔ)方式各異，因此，用裝配體屬性連接圖對(duì)裝配體信息圖形化表達(dá)，用圖中的節(jié)點(diǎn)表達(dá)裝配體中的零件信息，用圖中節(jié)點(diǎn)之間的連接關(guān)系表達(dá)零件之間的裝配關(guān)系。然后分別對(duì)節(jié)點(diǎn)和連接關(guān)系進(jìn)行分類，用類碼簡(jiǎn)化規(guī)整信息表達(dá)，形成裝配體類碼連接圖。

【定義 1】裝配體屬性連接圖：G=｛P，E，A（P），A（E）｝，其中，P=｛p1，p2，…，pnp｝表示各個(gè)零件節(jié)點(diǎn)集合；E=｛e1，e2，…，ene｝表示連接關(guān)系集合；A（P）=｛A（p1），A（p2），…，A（pnp）｝表示零件的屬性集合；A（E）=｛A（e1），A（e2），…，A（ene）｝表示各個(gè)連接關(guān)系的屬性集合。

為裝配體中的零件建立節(jié)點(diǎn)屬性如下：

式中：AName（pi）—名稱屬性；AMaterial（pi）—零件材料；AFun（pi）—零件功能；ASize（pi）—零件尺寸；AClass（pi）—零件類型；由于在機(jī)械產(chǎn)品中常常有一些零件成組出現(xiàn)，這些零件且與其他零件具有相同的連接關(guān)系，具有相同的功能，我們可以將該組零件用一個(gè)節(jié)點(diǎn)表達(dá)以簡(jiǎn)化數(shù)據(jù)；ANo.P（pi）—成組零件節(jié)點(diǎn)中的零件個(gè)數(shù)；ATolerance（pi）—該零件中與零件功能直接相關(guān)的最關(guān)鍵的尺寸公差要求，該屬性的數(shù)據(jù)結(jié)構(gòu)為｛公差類型、基本尺寸、偏差值=|上偏差-下偏差|｝，例如軸承內(nèi)徑公差｛尺寸公差、30、0.2｝。零件節(jié)點(diǎn)屬性可以根據(jù)具體應(yīng)用進(jìn)行增加或減少。

零件之間的連接關(guān)系可以分為普通的接觸關(guān)系和根據(jù)裝配工藝文件中有裝配要求的連接關(guān)系。對(duì)于后者可以進(jìn)一步分類，具體包括螺紋連接、鉚接、銷釘連接、焊接等。根據(jù)連接關(guān)系的分類，連接關(guān)系的屬性建立如下：

式中：AClass（ei）—連接類型；AForm（ei）—連接形式；AMaterial（ei）—連接材料。

具體應(yīng)用基于密度的DBSCAN 聚類算法分別對(duì)零件和連接關(guān)系進(jìn)行聚類，并對(duì)相同類型的元素賦予相同的類碼。用類碼重新定義屬性連接圖中的節(jié)點(diǎn)和連接關(guān)系的標(biāo)簽，形成類碼連接圖。該算法將數(shù)據(jù)集中高密度區(qū)域用低密度區(qū)域分割，可以從帶有“噪聲”的數(shù)據(jù)集中發(fā)現(xiàn)任意形狀的聚類，可以有效的進(jìn)行空間聚類。零件特征信息是由其六類屬性定義，因此，由零件屬性構(gòu)成零件屬性空間，每個(gè)零件可以看作是處于六維空間中的點(diǎn)。將DBSCAN 算法應(yīng)用于零件屬性空間點(diǎn)在零件屬性空間中的聚類過(guò)程，算法中涉及的點(diǎn)即為零件屬性空間點(diǎn)。

DBSCAN 聚類算法過(guò)程為：定義在給定半徑（Eps）的鄰域內(nèi)數(shù)據(jù)對(duì)象的個(gè)數(shù)必須大于給定閾值（MinPts）。將DBSCAN 算法應(yīng)用到零件屬性空間，兩個(gè)點(diǎn)之間的距離與這兩個(gè)點(diǎn)代表的零件的相似度負(fù)相關(guān)，即兩個(gè)零件的相似度越高，它們的點(diǎn)在零件屬性空間中的距離越小，反之則越大。因此兩個(gè)零件點(diǎn)的距離dist（p1，p2）表示如下：

零件和連接關(guān)系的相似度計(jì)算是比較它們的具體屬性值，然后通過(guò)加權(quán)求和零件各類屬性的相似度來(lái)確定零件之間的差異。在裝配體模型中，由于這些信息的多樣性，需要四種不同類型的屬性來(lái)表示這些信息：（1）標(biāo)準(zhǔn)語(yǔ)義屬性，用字符串形式表達(dá)。一個(gè)零件或連接關(guān)系的該類屬性的取值是通過(guò)從一個(gè)已有的列表中選擇其中之一來(lái)完成，其屬性值可以窮舉。若兩個(gè)要比較的屬性值相同則相似度為1，否則為0；（2）非標(biāo)準(zhǔn)語(yǔ)義屬性，用字符串形式表達(dá)。這類屬性是在模型定義過(guò)程中由參與的設(shè)計(jì)人員給出，屬性值不可窮舉。例如一個(gè)零件的名稱。這類屬性用杰卡德（Jaccard）相似度進(jìn)行比較，即由兩個(gè)屬性中所有字符串的交集和并集的比值確定；（3）量化屬性，用具體數(shù)值來(lái)表達(dá)。如一個(gè)零件的具體尺寸只能用數(shù)值表示。這類屬性的相似度為較小值與較大值的比值，兩個(gè)數(shù)值差異越大則相似度越低；（4）公差屬性，若公差屬性中的公差類型相同且基本尺寸按照（3）中量化屬性比較方法相似度高于75%，那么繼續(xù)用（3）中量化屬性比較方法計(jì)算偏差值的相似度，否則公差類型不同或者基本尺寸差異較大，公差信息比較無(wú)意義，那么在后續(xù)的零件相似度比較過(guò)程中公差屬性相似度不納入加權(quán)比較過(guò)程。

3 基于 Weisfeiler-Lehman（WL）圖核算法的裝配體模型相似度計(jì)算

隨著圖結(jié)構(gòu)的廣泛應(yīng)用，圖核算法已經(jīng)被應(yīng)用到很多領(lǐng)域并廣受關(guān)注，成為一個(gè)快速發(fā)展的結(jié)構(gòu)化數(shù)據(jù)學(xué)習(xí)分支。它可以將圖形結(jié)構(gòu)化數(shù)據(jù)和向量機(jī)、內(nèi)核PCA 等大量機(jī)器學(xué)習(xí)算法聯(lián)系起來(lái)，進(jìn)而解決圖結(jié)構(gòu)表示的實(shí)際問(wèn)題。W-L 圖核算法將W-L圖匹配算法與核函數(shù)結(jié)合起來(lái)，可以有效的進(jìn)行帶標(biāo)簽圖結(jié)構(gòu)相似度分析。

3.1 W-L 圖匹配算法

1968 年 Weisfeiler 和 Lehman 提出了 k 維 Weisfeiler-Lehman匹配算法，在這里我們應(yīng)用一維WL 算法，或稱單一頂點(diǎn)細(xì)分算法，它的基本思路是對(duì)每個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)集合的標(biāo)簽進(jìn)行排序生成該頂點(diǎn)的鄰接點(diǎn)標(biāo)簽序，然后把這個(gè)頂點(diǎn)的標(biāo)簽和它的鄰接點(diǎn)標(biāo)簽序進(jìn)行組合壓縮再排序形成新的更短的標(biāo)簽，如圖2所示。

在W-L 算法的每次迭代中，對(duì)于G 和G′中所有節(jié)點(diǎn)v，如果在歷次迭代中，我們得到的新標(biāo)簽li（p）是一致的，就表明G 和G′具有相同的標(biāo)簽。因?yàn)橹挥性谶@種情況下，它們才會(huì)得到相同的新標(biāo)簽。因此，我們用r（（P，E，li））=（P，E，li+1）表示W(wǎng)-L 算法中的重新定義標(biāo)簽函數(shù)。

【定義2】：對(duì)G=（P，E，li）=（P，E，l0）進(jìn)行i 次迭代生成圖Gi=（P，E，li）。那么｛G0，G1，…，Gh｝=｛（P，E，l0），（P，E，l1），…，（P，E，lh）｝為W-L 序列圖集。

3.2 W-L 圖核

用Σi∈Σ 表示在各代W-L 圖中各個(gè)節(jié)點(diǎn)標(biāo)簽集合。用Σ0表示G 和G′的原始節(jié)點(diǎn)標(biāo)簽的集合（重復(fù)出現(xiàn)的標(biāo)簽在Σi中僅顯示一次）。將每個(gè)Σi中的元素按照從小到大的順序排列。用c（jGi，σ）ij表示圖G 經(jīng)過(guò)i 次迭代生成圖G 中 σij的出現(xiàn)次數(shù)。，將圖 Gi中的節(jié)點(diǎn)信息進(jìn)行規(guī)整壓縮，用一個(gè)一維向量表達(dá)。

對(duì)于兩個(gè)要比較的圖生成的一維向量之間，相同標(biāo)簽節(jié)點(diǎn)的個(gè)數(shù)信息一一對(duì)應(yīng)，便于后續(xù)的計(jì)算比較。如果兩個(gè)向量方向相同，那么它們的標(biāo)準(zhǔn)內(nèi)積值最大，如果方向相反，標(biāo)準(zhǔn)內(nèi)積值最小。因此，內(nèi)積值的大小可以反應(yīng)兩個(gè)向量的相似程度，因此基于向量?jī)?nèi)積，定義兩個(gè)圖的W-L 圖核可以表示為：

3.3 裝配體模型W-L 圖核相似度算法

剪枝標(biāo)注：在每次W-L 算法第i 次迭代之前，我們遍歷Gi和中所有節(jié)點(diǎn)，標(biāo)注出來(lái)另外一個(gè)圖節(jié)點(diǎn)標(biāo)簽中沒(méi)有出現(xiàn)過(guò)的節(jié)點(diǎn)集合及其相關(guān)的連接，剩余GWi和如圖 2 所示。因?yàn)樗鞧 和G′中明顯相異的部分，后續(xù)的W-L 圖核算法中僅僅對(duì)GWi和迭代，進(jìn)行標(biāo)簽的重新編排壓縮再定義。因此剪枝標(biāo)注操作可以減小后續(xù)W-L 算法中計(jì)算圖的規(guī)模，提高效率。由于Di和代表圖 Gi和中相異的部分，所以在計(jì)算相似度時(shí)用包含Di和的 Gi和來(lái)計(jì)算。雖然剪枝標(biāo)注操作可能會(huì)導(dǎo)致Gi和分裂成多個(gè)子圖，但是并不會(huì)影響后續(xù)的一維向量的轉(zhuǎn)化操作，在這里進(jìn)行相似度計(jì)算的時(shí)候，我們?nèi)匀豢梢园阉鼈儺?dāng)作一個(gè)整體來(lái)計(jì)算。

從W-L 圖匹配算法中我們可以知道，W-L 算法可以將圖中的連接關(guān)系信息逐步集成到節(jié)點(diǎn)標(biāo)簽信息中，得到W-L 序列圖集。那么對(duì)于圖G 和G′的W-L 序列圖集，如果任意一代Di-1和為空，G 和G′圖核相似度恒為1，那么迭代結(jié)束，說(shuō)明這兩個(gè)圖同構(gòu)；如果兩個(gè)圖中有部分子圖同構(gòu)，經(jīng)過(guò)多次迭代之后，相同的子圖可能會(huì)集中在GWi和中，圖核相似度將不會(huì)變化成為定值，迭代結(jié)束；除了這兩種情況外，經(jīng)過(guò)多次迭代，圖結(jié)構(gòu)信息將逐步集中到圖的節(jié)點(diǎn)標(biāo)簽上，直到兩個(gè)圖的標(biāo)簽全部不相同，GWi和為空，相應(yīng)的圖核相似度為0，迭代結(jié)束。

那么兩個(gè)圖的相似度根據(jù)其W-L 序列圖集歷代之間的圖核相似度計(jì)算而得：

4 實(shí)例驗(yàn)證

選取一組裝配體模型為實(shí)例驗(yàn)證對(duì)象，這組模型包含2 個(gè)減速器模型和2 個(gè)飛機(jī)卡板模型。先比較2 個(gè)減速器模型，經(jīng)過(guò)第一步的裝配體信息處理，將模型轉(zhuǎn)化為裝配體類碼連接圖，如圖1 所示。

圖1 兩個(gè)減速器模型、屬性連接圖及其類碼圖Fig.1 Two Reducer Models，Corresponding Attribute Connection Graphs and Their Class Code Graphs

圖2 對(duì)減速器模型應(yīng)用W-L 圖核相似度算法第一次迭代Fig.2 Applying First Iteration of W-L Graph Kernel Similarity Algorithm to the Reducer Models

表1 模型1 與模型2 用W-L 圖核相似度計(jì)算Tab.1 Calculating Similarity Process Between Model 1 and Model 2 by W-L Graph Kernel Similarity Algorithm

圖3 兩個(gè)飛機(jī)卡板模型屬性連接圖及其類碼圖Fig.3 Two Aircraft Card Board Models，Corresponding Attribute Connection Graphs and Their Class Code Graphs

表2 飛機(jī)卡板模型用W-L 圖核相似度計(jì)算Tab.2 Calculating Similarity Process Between Two Aircraft Card Board Models by W-L Graph Kernel Similarity Algorithm

在第一組減速器模型中，模型1 為錐齒輪減速器，模型2 為蝸輪蝸桿傳動(dòng)減速器，但二者都一級(jí)減速，用到的軸承、軸承蓋、箱體等零件，經(jīng)過(guò)驗(yàn)證計(jì)算得到0.7756 的相似度，可以體現(xiàn)其差異和相同的部分。飛機(jī)卡板模型中，模型3 和模型4 的包含的零件相同，零件解雇大致相當(dāng)，但模型4 中多一個(gè)角材零件，經(jīng)過(guò)驗(yàn)證計(jì)算得到0.9003 的相似度，可以驗(yàn)證算法的有效性。

5 總結(jié)與展望

針對(duì)多部門參與建立的多源裝配體模型的檢索、通用結(jié)構(gòu)挖掘等設(shè)計(jì)重用，建立了一種基于Weisfeiler-Lehman 圖核算法的裝配體模型比較方法。

（1）裝配體類碼連接圖可以將復(fù)雜紛亂的多源裝配體信息整理成圖模型，便于成熟的圖論算法應(yīng)用，類碼可以將部分信息復(fù)雜的屬性信息進(jìn)行初步比較分析并簡(jiǎn)化成便于數(shù)學(xué)運(yùn)算的數(shù)字形式，降低圖信息的復(fù)雜度。

（2）W-L 算法融合核函數(shù)不用計(jì)算復(fù)雜的非線性變換，直接得到非線性變換的內(nèi)積，應(yīng)用于圖的模型中可以大大簡(jiǎn)化計(jì)算復(fù)雜度，實(shí)現(xiàn)圖之間的相似度計(jì)算進(jìn)而實(shí)現(xiàn)裝配體之間的相似度計(jì)算。

在相似度分析過(guò)程中沒(méi)有將圖中的連接關(guān)系的標(biāo)簽信息、零件之間的裝配體尺寸公差等要求納入比較過(guò)程，在后續(xù)研究中可以進(jìn)一步完善；另外裝配體的比較過(guò)程中，沒(méi)有體現(xiàn)不同零件之間在比較過(guò)程中的差異性還需后續(xù)進(jìn)一步研究。