基于二維信息集的CAD模型相似度評(píng)價(jià)方法研究

丁淑輝，周 鑫，曾慶良，夏 群

（1.山東科技大學(xué)機(jī)電學(xué)院，山東 青島 266590；2.新泰市科學(xué)技術(shù)局，山東 泰安 271200）

1 引言

隨著數(shù)據(jù)庫(kù)和云平臺(tái)技術(shù)的發(fā)展，很多企業(yè)為了管理現(xiàn)有模型建立了模型數(shù)據(jù)庫(kù)以及模型云平臺(tái)，機(jī)械產(chǎn)品的開(kāi)發(fā)大多是在現(xiàn)有模型的信息重用基礎(chǔ)上完成的，因此在模型庫(kù)中準(zhǔn)確地檢索到相似度高的模型，對(duì)縮短研發(fā)周期、提高研發(fā)效率有著重要意義。

基于內(nèi)容的模型檢索［1］是當(dāng)前主流的檢索方法，文獻(xiàn)［2］最早提出使用屬性鄰接圖（Attributed Adjacency Graph，AAG）來(lái)表達(dá)模型的拓?fù)浣Y(jié)構(gòu)，后經(jīng)學(xué)者對(duì)基于AAG的方法的不斷研究，目前基于圖的特征識(shí)別與模型相似度評(píng)價(jià)方法已成為主流［3］。文獻(xiàn)［4］對(duì)模型的骨架建立坐標(biāo)系，然后使用廣義變換矩陣表示模型骨架，將模型的相似度轉(zhuǎn)化為矩陣相似度比較。以模型的整體結(jié)構(gòu)作為相似度評(píng)價(jià)依據(jù)，可以較好的比較兩模型間的整體結(jié)構(gòu)，但模型的部分重要局部結(jié)構(gòu)不能得到充分比較。文獻(xiàn)［5］將模型進(jìn)行區(qū)域分割，通過(guò)比較不同模型間最具有代表性的局部特征得到模型相似度。此方法能夠充分考慮模型細(xì)節(jié)，但只有對(duì)用途相近的同種類模型進(jìn)行比較時(shí)，才能較好的體現(xiàn)。通過(guò)引入高效的算法提高模型檢索效率，文獻(xiàn)［6］使用粒子群算法對(duì)所建立的相似度矩陣進(jìn)行搜索；文獻(xiàn)［7］用加權(quán)圖逼近方法找到不同模型對(duì)應(yīng)的最大公共子圖，以得到模型的相似度；文獻(xiàn)［8］構(gòu)建了零件加工面擴(kuò)展AAG，將模型邊與面的形狀因素包括進(jìn)來(lái)進(jìn)行特征識(shí)別；文獻(xiàn)［9］將模型中同種類型的面進(jìn)行匹配，通過(guò)計(jì)算所有類型的面的最優(yōu)匹配方案，并加權(quán)求解模型間的相似性。

當(dāng)前方法多數(shù)以模型拓?fù)浣Y(jié)構(gòu)作為主要評(píng)價(jià)依據(jù)，而AAG作為一種模型的表示方式并不能完全反應(yīng)模型的實(shí)際情況，從而導(dǎo)致所得到的相似度結(jié)果與實(shí)際情況不符。AAG在計(jì)算機(jī)內(nèi)部表示為AAM［10］，傳統(tǒng)的AAM僅包含模型結(jié)構(gòu)信息及基本屬性信息，如模型表面鄰接關(guān)系、模型元素基本屬性等，雖然可以較好地表達(dá)模型本身的拓?fù)浣Y(jié)構(gòu)及基本形狀，但并不能有效反映模型間的差別，如圖1 所示。圖1（a）、圖1（b）兩圖所示A、B兩模型的AAG相同，如圖1（c）所示；因其表面形狀、交線的凹凸性等基本性質(zhì)相同，兩圖的AAM也相同。由此可見(jiàn)，傳統(tǒng)AAG、AAM并不能完整、準(zhǔn)確的反映模型基本形狀。

圖1 不同模型及其AAGFig.1 Models and Their Corresponding AAG

基于上述問(wèn)題，通過(guò)提取模型拓?fù)渑c尺寸信息，創(chuàng)新性的構(gòu)建了基于AAM的模型信息集，提出了基于模型信息集的模型相似度評(píng)價(jià)方法。以模型信息集作為信息來(lái)源，以模型表面作為頂點(diǎn)獨(dú)立集，以模型間每對(duì)表面間相似度為權(quán)重，建立賦值完全偶圖。使用Kuhn-Munkres算法（以下簡(jiǎn)稱KM算法）得到其最優(yōu)匹配作為兩模型的最相似匹配，并評(píng)價(jià)其相似度。

2 基于AAM的二維信息集的建立

模型信息的提取是模型相似性比較的基礎(chǔ)和關(guān)鍵，在研究模型信息需求及提取方法的基礎(chǔ)上，建立了基于AAM的二維信息集，為模型相似度評(píng)價(jià)提供數(shù)據(jù)支持。

2.1 模型B-rep模式信息提取與表示方法

在三維模型的基于圖的表達(dá)中，以圖的節(jié)點(diǎn)表示模型表面、以節(jié)點(diǎn)連線表示兩個(gè)面的交線，以模型表面和交線的拓?fù)浣Y(jié)構(gòu)、基本形狀等作為基本屬性，構(gòu)建AAG用于三維模型的抽象表達(dá)。在原有AAM的基礎(chǔ)上增加了模型表面、交線等元素的尺寸信息，連同原有AAM所表達(dá)的拓?fù)浣Y(jié)構(gòu)信息，組成模型二維信息集，完整表達(dá)模型的拓?fù)浣Y(jié)構(gòu)與幾何信息。

模型信息的自動(dòng)提取是構(gòu)建模型信息集的前提，現(xiàn)存三維模型由多款建模軟件完成，由于建模方法和數(shù)據(jù)結(jié)構(gòu)的差異，各類軟件無(wú)法通過(guò)統(tǒng)一的方法直接讀取模型信息。不過(guò)，各軟件模型的表達(dá)模式是相對(duì)穩(wěn)定的，當(dāng)前多數(shù)建模軟件均支持邊界表示（Boundary Representation，B-rep）模型表示。實(shí)驗(yàn)中相似度評(píng)價(jià)所用的模型信息均來(lái)自于模型的B-rep表達(dá)模式。

模型B-rep表達(dá)模式中數(shù)據(jù)信息的提取，主要有兩種方法：基于STEP 中性格式的數(shù)據(jù)提取和基于模型開(kāi)發(fā)軟件的二次開(kāi)發(fā)。采用后者進(jìn)行模型數(shù)據(jù)讀取，利用軟件開(kāi)發(fā)商提供的二次開(kāi)發(fā)函數(shù)訪問(wèn)模型，獲取模型數(shù)據(jù)。以Creo軟件的Creo Toolkit二次開(kāi)發(fā)工具包為例，其常用二次開(kāi)發(fā)函數(shù)，如表1所示。

表1 Creo Toolkit常用函數(shù)Tab.1 Commonly Used Functions in Creo Toolkit

2.2 幾何元素凹凸性判斷方法

幾何元素的凹凸性可通過(guò)ProGeomitemdataGet 函數(shù)獲得，結(jié)合說(shuō)明其判斷方法，如圖2所示。

圖2 凹凸性判斷模型Fig.2 The Model for Concavity Judgment

模型中的邊分為直線、圓弧和一般曲線三類，其凹凸性的判斷方法如下：當(dāng)兩面交線為直線時(shí)，使用兩相交面的夾角判斷其凹凸性。在實(shí)體側(cè)，若兩面夾角小于180°，此交線為凸邊，如圖中的邊d；若兩面夾角大于180°，則此交線為凹邊，如圖中的邊c。當(dāng)兩個(gè)面交線為圓弧時(shí)，若圓弧是凸圓柱面的邊，則為凸邊，如圖中的邊a；若圓弧為凹圓柱面的邊，則為凹邊，如圖中的邊b。除直線與圓弧之外的交線均視為一般曲線。

模型中的面分為平面、圓柱面和一般曲面三類，其凹凸性判斷方法如下：當(dāng)平面與所有相鄰表面的交線均為凸邊時(shí)，該平面為凸面，如圖中的面3；否則為凹面，如圖中的面1。當(dāng)圓柱面的法向量方向指向軸線時(shí)，該圓柱面為凹面，如圖中的圓柱面4；當(dāng)圓柱面的法向量方向指向軸線反方向時(shí)，該圓柱面為凹面，如圖中的圓柱面2。除平面與圓柱面之外的面均視為一般曲面。

2.3 模型拓?fù)浣Y(jié)構(gòu)矩陣的建立

模型拓?fù)浣Y(jié)構(gòu)反映了模型面與面之間的位置關(guān)系，以及模型中面和交線的主要形狀，是首先要表達(dá)的模型要素。設(shè)模型由k個(gè)面組成，其編號(hào)依次為1至k，使用AAM表達(dá)模型拓?fù)浣Y(jié)構(gòu)，其對(duì)角線元素表示模型的面，非對(duì)角線元素表示模型面與面的交線，建立模型拓?fù)浣Y(jié)構(gòu)矩陣TM如下所示。

式中：元素TMij—模型面（i=j時(shí)）或兩個(gè)面的交線（i≠j時(shí)）的幾何屬性，其取值規(guī)則如下：

（1）當(dāng)i≠j時(shí)，TMij(i，j= 1，2，…，k)表示編號(hào)為i和j的面的交線的屬性，其值取決于線的凹凸性以及交線類型兩方面，如式（2）所示。

式中：TM1—交線的凹凸性，其取值，如式（3）所示。

TM2交線的類型，其取值，如式（4）所示。

（2）當(dāng)i=j時(shí)，TMij(i，j= 1，2，…，n)表示TMii(i= 1，2，…，n)，表示編號(hào)為i的模型表面的屬性值。

當(dāng)表面為平面時(shí)，其值如下所示。

若該面與所有相鄰面的交線都是凸邊，即式（1）中該面元素所在的行和列均為正數(shù)，則TMii=+1；否則TMii=- 1。

當(dāng)面為曲面時(shí)，模型表面的屬性值取決于表面的凹凸性和類型，其值如式（6）所示。

式中：TM3—面的凹凸性，其取值如式（7）所示；TM4—面的類型，其取值，如式（8）所示。

2.4 模型尺寸矩陣的建立

模型尺寸反映了模型的次要的幾何形狀，是模型相似性精確比較過(guò)程中不可或缺的因素。與模型拓?fù)渚仃囶愃?，模型尺寸矩陣采用AAM來(lái)表達(dá)尺寸參數(shù)，對(duì)角線元素反映模型表面尺寸屬性，非對(duì)角線元素反映表面交線尺寸屬性，如下所示。

式中：主對(duì)角線元素SMii(i= 1，2，…，k)表示模型中編號(hào)為i的表面面積，非主對(duì)角線元素SMij(i，j= 1，2，…，k，i≠j)表示模型中編號(hào)為i和j的面的交線長(zhǎng)度，k—模型中表面的數(shù)量。

2.5 模型二維信息集

為全面表示模型拓?fù)浣Y(jié)構(gòu)和尺寸信息，結(jié)合前述模型拓?fù)浣Y(jié)構(gòu)矩陣和尺寸矩陣，建立模型二維信息集如下所示。

式中：TM—模型幾何矩陣，其定義如式（1）所示；SM—模型尺寸矩陣，其定義如式（9）所示。采用基于B-rep模式的模型信息提取方法遍歷模型得到式（10），其基本流程如下：首先提取模型表面信息，包括ID、面積、凹凸性等基本屬性；遍歷模型表面得到模型所有輪廓線，從而得到模型所有邊的集合；識(shí)別邊所在的兩個(gè)面，得到邊在AAM 中的位置；最后提取模型邊的凹凸性、類型及其尺寸等信息生成二維信息集。

3 基于二維信息集的模型相似度評(píng)價(jià)

基于上述方法，對(duì)將要進(jìn)行相似度評(píng)價(jià)的源模型和目標(biāo)模型分別建立二維信息集：InfSetS={TMS，SMS}和InfSetT={TMT，SMT}，完成基礎(chǔ)數(shù)據(jù)信息的提??；分別以兩個(gè)模型的表面作為頂點(diǎn)獨(dú)立集，以兩頂點(diǎn)獨(dú)立集之間每對(duì)頂點(diǎn)間的相似度作為其權(quán)重，構(gòu)建賦權(quán)完全偶圖。使用KM算法計(jì)算源模型和目標(biāo)模型間的最優(yōu)匹配，并評(píng)價(jià)其相似度。

3.1 源模型與目標(biāo)模型表面的最優(yōu)匹配

對(duì)源模型和目標(biāo)模型進(jìn)行相似度評(píng)價(jià)，首先要盡可能多的找到兩模型間拓?fù)浣Y(jié)構(gòu)相同或最相似的表面，并建立這些表面間的一一對(duì)應(yīng)關(guān)系，即：以最相似為評(píng)價(jià)標(biāo)準(zhǔn)，對(duì)兩模型的表面進(jìn)行最優(yōu)匹配。將其抽象為賦權(quán)完全偶圖的最優(yōu)匹配問(wèn)題，即：分別以源模型和目標(biāo)模型的表面作為頂點(diǎn)獨(dú)立集VS和VT，并以兩獨(dú)立集間每對(duì)表面間的相似度為權(quán)值建立賦權(quán)完全偶圖，求其最優(yōu)匹配，使得匹配中各邊的權(quán)值和最大。

考慮到兩模型存在面的數(shù)量不相等的情況，向數(shù)量少的頂點(diǎn)獨(dú)立集添加補(bǔ)充面，以保證偶圖中兩個(gè)獨(dú)立集中頂點(diǎn)的數(shù)量相等，才可能使得偶圖中兩頂點(diǎn)獨(dú)立集的匹配為完美匹配。假定源模型的表面數(shù)量為m，目標(biāo)模型的表面數(shù)量為n，且m＜n，分別以源模型和目標(biāo)模型的表面作為頂點(diǎn)獨(dú)立集建立偶圖時(shí)，應(yīng)向目標(biāo)模型添加n-m個(gè)補(bǔ)充面。此時(shí)，源模型的頂點(diǎn)獨(dú)立集，如式（11）所示，目標(biāo)模型頂點(diǎn)獨(dú)立集，如式（12）所示。

式中：FSi—源模型的第i個(gè)表面；FSm+i—目標(biāo)模型的第i個(gè)補(bǔ)充

表面；FTi—目標(biāo)模型的第i個(gè)表面。

在向模型添加補(bǔ)充面后，添加補(bǔ)充面屬性信息并更新其信息集。例如，源模型添加補(bǔ)充面后，其拓?fù)浣Y(jié)構(gòu)矩陣TMS由式（1）更新至式（13）。

式中：當(dāng)i≤m且j≤m時(shí)，矩陣中元素TMij與矩陣原有元素相同位置不變；當(dāng)i＞m或j＞m時(shí)，矩陣中元素TMij為補(bǔ)充面屬性信息，此處TMij= 0。

以模型表面的類型、表面面積、表面臨面數(shù)以及邊數(shù)作為參考依據(jù)計(jì)算源模型表面i和目標(biāo)模型表面j之間的相似度，其計(jì)算公式如下：

式中：ω0—模型表面的類型權(quán)值，當(dāng)表面i與j為同種類型時(shí)，ω0=1，反之ω0= 0，模型表面的類型見(jiàn)式（5）～式（8）；ω1—模型表面的面積權(quán)值，ω2—鄰面數(shù)權(quán)值，ω3—邊數(shù)權(quán)值，且ω1+ω2+ω3= 1，按照各項(xiàng)因素對(duì)模型相似性的影響并結(jié)合實(shí)驗(yàn)得出當(dāng)ω1= 0.7，ω2= 0.2，ω3=0.1 時(shí)效果較好。Sar—面i與面j的面積相似度，其計(jì)算公式，如式（15）所示；Sns—兩個(gè)面的鄰面數(shù)相似度，其計(jì)算公式，如式（16）所示；Sne—兩個(gè)面的邊數(shù)相似度，其計(jì)算公式，如式（17）所示。

式中：Ai和Aj—源模型中的第i個(gè)面和目標(biāo)模型中第j個(gè)面的面積，其值可通過(guò)式（9）中的主對(duì)角線元素SMii獲得；同理，Vi和Vj、Ei和Ej—源模型中的第i個(gè)面和目標(biāo)模型中第j個(gè)面臨面數(shù)量和邊數(shù)量，可通過(guò)AAG每個(gè)頂點(diǎn)的度、式（1）所示模型幾何尺寸矩陣第i（j）行中非零的非主對(duì)角線元素的個(gè)數(shù)獲得。根據(jù)以上構(gòu)造的兩個(gè)頂點(diǎn)獨(dú)立集VS和VT，以及兩獨(dú)立集中各頂點(diǎn)對(duì)間的相似度權(quán)值，構(gòu)造賦權(quán)完全偶圖如下：

式中：VS和VT—由源模型和目標(biāo)模型構(gòu)建的頂點(diǎn)獨(dú)立集，|VS| =|VT|；E(s，t) —兩頂點(diǎn)獨(dú)立集間每對(duì)頂點(diǎn)間的邊集，其權(quán)值ω(st)由式（14）確定。

偶圖最優(yōu)匹配問(wèn)題通常使用KM算法求解，通過(guò)引入可行頂點(diǎn)標(biāo)號(hào)的方法，將偶圖最優(yōu)匹配問(wèn)題轉(zhuǎn)化為偶圖完美匹配下的最大加權(quán)匹配。計(jì)算由源模型和目標(biāo)模型構(gòu)成的賦值完全偶圖G=(VS，VT，E(s，t) )的最優(yōu)匹配的具體實(shí)施步驟如下：（1）確定圖中各頂點(diǎn)的可行頂點(diǎn)標(biāo)號(hào)（以下簡(jiǎn)稱頂標(biāo)）。其初始值取值如下：

式中：VS、VT—偶圖的兩個(gè)獨(dú)立集；ω(s，t)—源模型中的表面s和目標(biāo)模型中的表面t的相似度權(quán)值，滿足條件：l(s)+l(t)≥

（2）確定相等子圖Gl，并在Gl上任取一匹配M作為初始匹配。相等子圖是以El為邊集的G的生成子圖，滿足條件：El={(s，t) ∈E|l(s)+l(t)=ω(s，t)}。

（3）判斷：若M飽和VS的每個(gè)頂點(diǎn)，則M為最優(yōu)匹配，輸出最優(yōu)匹配結(jié)果；否則在VS中任取一M不飽和頂點(diǎn)u，令頂點(diǎn)u為頂點(diǎn)集S，并建立頂點(diǎn)集W，W←?。

（4）若NGl（S）=W，更新VS、VT的頂標(biāo)，其取值，如式（20）～式（21）所示。更新之后以l'代替l，以Gl'代替Gl。

式中：s∈S，t?W—s從獨(dú)立集VS已匹配點(diǎn)找，t從獨(dú)立集VT未匹配點(diǎn)找。

其中，只更新獨(dú)立集VS已匹配點(diǎn)與獨(dú)立集VT已匹配點(diǎn)的頂標(biāo)。

（5）選取t∈NGl(S)W，若t為M飽和的，則說(shuō)明t已經(jīng)被匹配，設(shè)此t在M中的匹配為(s)，t，將此t加入頂點(diǎn)集W，將與此t匹配的s加入頂點(diǎn)集S，并轉(zhuǎn)到步（4）；若t為M不飽和的，則說(shuō)明此t可作為可擴(kuò)路的起點(diǎn)，令P為Gl中的M可擴(kuò)（u，t）路M←MΔE(P) ，轉(zhuǎn)到（3）。經(jīng)過(guò)以上計(jì)算，得到偶圖中兩頂點(diǎn)獨(dú)立集FS和FT的最優(yōu)匹配M，設(shè)M中源模型與目標(biāo)模型的對(duì)應(yīng)關(guān)系為：

根據(jù)式（22）中的此匹配結(jié)果調(diào)整目標(biāo)模型信息集InfSet中兩個(gè)矩陣中元素的位置，使其每個(gè)頂點(diǎn)元素與源模型中相匹配的面具有相同的位置，變換位置后的目標(biāo)模型信息集如下：

式中：TMT'、SMT'—變換位置后的目標(biāo)模型幾何矩陣和尺寸矩陣。

3.2 兩模型總體相似度評(píng)價(jià)

上文中兩模型間表面的最優(yōu)匹配僅考慮了表面元素的相似度，模型總體相似度的計(jì)算將邊元素相關(guān)信息也考慮進(jìn)來(lái)。

以最優(yōu)匹配結(jié)果所對(duì)應(yīng)的調(diào)整后的模型信息集為例說(shuō)明相似度評(píng)價(jià)方法，其計(jì)算公式如下所示。

式中：Sim—源模型和目標(biāo)模型的總體相似度；S1—拓?fù)浣Y(jié)構(gòu)相似度；S2—幾何尺寸相似度，ω4、ω5為權(quán)值，ω4+ω5= 1，按照各項(xiàng)因素對(duì)模型相似性的影響并結(jié)合實(shí)驗(yàn)得出當(dāng)ω4= 0.75，ω2= 0.25時(shí)效果較好。

拓?fù)浣Y(jié)構(gòu)相似度S1表示兩模型同種幾何元素的比例，即一一比較TMS'與TMt'對(duì)應(yīng)位置的元素，若TMS'與TMT'相同位置元素值相同，則表面兩模型當(dāng)前幾何元素種類相同。

由于在模型幾何矩陣中關(guān)于交線的元素重復(fù)出現(xiàn)，所以在計(jì)算拓?fù)浣Y(jié)構(gòu)相似度時(shí)只考慮所有主對(duì)角線元素以及主對(duì)角線以上的元素，此時(shí)可將模型幾何矩陣視為上三角矩陣，拓?fù)浣Y(jié)構(gòu)相似度S1計(jì)算公式，如下所示。

式中：N1—源模型和目標(biāo)模型幾何矩陣的上三角矩陣中相同位置的非零等值元素的個(gè)數(shù)；N2—目標(biāo)模型幾何矩陣上三角矩陣中非零元素個(gè)數(shù)。

幾何尺寸相似度S2計(jì)算相同種類幾何元素所對(duì)應(yīng)的尺寸的相似度。仍然將模型尺寸矩陣視為上三角矩陣進(jìn)行使用，幾何尺寸相似度S2的計(jì)算公式，如式（26）所示。

式中：n—兩模型相同種類幾何元素個(gè)數(shù)，其計(jì)算公式，如式（27）所示。LSi—兩信息集中相同位置的一組相同類型元素在源模型中的尺寸屬性，當(dāng)元素是面時(shí)，尺寸屬性為其面積；當(dāng)元素是邊時(shí)，尺寸屬性為其長(zhǎng)度。LTi—表示兩信息集中相同位置的一組相同類型元素在目標(biāo)模型中的尺寸屬性，取值同上。

式中：nlS、nlT—源模型與目標(biāo)模型的直線邊的數(shù)量；naS、naT—源模型與目標(biāo)模型的圓弧邊的數(shù)量；npS、npT—源模型與目標(biāo)模型的平面的數(shù)量；ncS、ncT—源模型與目標(biāo)模型的圓柱面的數(shù)量。

4 實(shí)驗(yàn)驗(yàn)證及算法性能比較

為驗(yàn)證算法的有效性，以Creo Toolkit 二次開(kāi)發(fā)包為工具、Microsoft Visual Studio 2015為集成開(kāi)發(fā)環(huán)境，基于Creo 4.0平臺(tái)進(jìn)行二次開(kāi)發(fā)，提取模型拓?fù)浣Y(jié)構(gòu)與尺寸信息并評(píng)價(jià)其相似度。本例使用的源模型與目標(biāo)模型，如圖3所示。以源模型與目標(biāo)模型A為例詳細(xì)說(shuō)明相似度評(píng)價(jià)方法。

圖3 實(shí)例模型Fig.3 Case Models

提取源模型原始信息并建立其拓?fù)浣Y(jié)構(gòu)矩陣與尺寸矩陣，模型原始信息，如圖4所示。其矩陣，如式（28）、式（29）所示。同理提取目標(biāo)模型原始信息并建立其矩陣。

圖4 源模型信息提取Fig.4 Source Model Information Extraction

源模型和目標(biāo)模型的表面數(shù)量分別為8和9，故應(yīng)向源模型添加1個(gè)補(bǔ)充面，添加補(bǔ)充面信息后源模型的拓?fù)浣Y(jié)構(gòu)矩陣與尺寸矩陣，如式（30）、式（31）所示。

分別以源模型和目標(biāo)模型的表面作為頂點(diǎn)建立偶圖，由式（14）計(jì)算出兩頂點(diǎn)獨(dú)立集之間每對(duì)頂點(diǎn)間的邊的權(quán)值ω(st) ，計(jì)算結(jié)果以矩陣形式表示，如式（32）所示。

以上結(jié)果表明，偶圖的最優(yōu)匹配為：

FS1?FT1；FS2?FT6；FS3?FT3；FS4?FT4；

FS5?FT2；FS6?FT5；FS7?FT7；

FS8?FT8；FS9?FT9

應(yīng)對(duì)目標(biāo)模型拓?fù)浣Y(jié)構(gòu)矩陣和尺寸矩陣中的第2行（列）與第5 行（列）、第5 行（列）與第6 行（列）進(jìn)行行列交換，結(jié)果如式（33）、（34）所示。

根據(jù)式（24）求得源模型與目標(biāo)模型A的相似度為0.71。以同樣方法求得其他模型間的相似度，如表2所示。

表2 相似度求解結(jié)果Tab.2 Model Similarity

為驗(yàn)證文中算法的性能，使用文中算法與文獻(xiàn)［9］提出的方法進(jìn)行對(duì)比，評(píng)價(jià)模型的相似度。采用工作站Intel（R）Xeon（R）CPU E5-2630 v3@2.40GHz（64.0GB內(nèi)存）作為本算法實(shí)驗(yàn)平臺(tái)，篩選了1000個(gè)常見(jiàn)Creo模型作為測(cè)試模型庫(kù)，選取其中一個(gè)模型作為源模型，以文中前述的相似度評(píng)價(jià)方法求解模型庫(kù)中其余模型與源模型的相似度。在耗時(shí)量方面，文中算法為兩部分：模型信息預(yù)處理耗時(shí)與相似度計(jì)算耗時(shí)。其中，模型信息預(yù)處理包括文件讀取、模型數(shù)據(jù)讀取、信息集矩陣建立等運(yùn)算，其耗時(shí)量占比較大。

文中算法為每個(gè)模型創(chuàng)建信息集，信息集完成后，后續(xù)可對(duì)其多次使用，而無(wú)需每次使用時(shí)重新處理模型；文獻(xiàn)［9］所述方法由于缺少信息儲(chǔ)存介質(zhì)，每次使用模型時(shí)都需要重新提取模型信息。不同算法的耗時(shí)量比較，可以看出文中算法在未進(jìn)行模型信息預(yù)處理時(shí)耗時(shí)量較大，而在完成模型預(yù)處理后運(yùn)算耗時(shí)量明顯減小，如表3所示。

表3 不同算法的耗時(shí)量比較Tab.3 Comparison of Time Consumption

用查準(zhǔn)率-查全率曲線對(duì)兩種算法進(jìn)行對(duì)比，其實(shí)驗(yàn)結(jié)果，如圖5所示?？梢钥闯鲈诓槿瘦^低的情況下文中算法與對(duì)比算法的查準(zhǔn)率差距不大，當(dāng)查全率高于0.5時(shí)文中算法的查準(zhǔn)率較對(duì)比算法有較明顯提升，這是因?yàn)槲闹兴惴ňC合考慮了模型表面和邊的形狀以及幾何因素對(duì)其相似度的影響，提升了模型表面間相似性計(jì)算的準(zhǔn)確性。綜合考慮運(yùn)算時(shí)間與查準(zhǔn)率-查全率曲線，文中算法雖然在未建立信息集時(shí)的運(yùn)算時(shí)間較長(zhǎng)，但在數(shù)據(jù)的重復(fù)利用方面文中算法有一定的優(yōu)勢(shì)，在查全率較高的時(shí)候文中算法的查準(zhǔn)率也有所提升。

圖5 RP曲線Fig.5 RP Curve

5 結(jié)論

通過(guò)建立二維信息集完成對(duì)CAD模型的拓?fù)浣Y(jié)構(gòu)與幾何尺寸的表達(dá)，分別以兩個(gè)模型的表面建立頂點(diǎn)獨(dú)立集，并以每對(duì)表面的相似度作為權(quán)重，構(gòu)建賦權(quán)完全偶圖，通過(guò)使用KM算法得到圖的最優(yōu)匹配，以得到兩模型相似度最高的面的對(duì)應(yīng)關(guān)系，然后再考慮兩模型的邊對(duì)相似度結(jié)果的影響，最終評(píng)價(jià)兩模型整體相似度。與傳統(tǒng)的CAD模型相似度評(píng)價(jià)方法相比較，文中方法做出了以下改進(jìn)：

（1）在模型信息提取的基礎(chǔ)上，創(chuàng)建了一種模型信息集，在傳統(tǒng)AAG只能表達(dá)模型拓?fù)浣Y(jié)構(gòu)信息的基礎(chǔ)之上，通過(guò)模型拓?fù)浣Y(jié)構(gòu)矩陣和模型尺寸矩陣完善了模型信息的表達(dá)，實(shí)現(xiàn)了CAD模型特征的準(zhǔn)確識(shí)別與相似度評(píng)價(jià)，推動(dòng)了從單純幾何形狀檢索向基于模型語(yǔ)義的模型相似度評(píng)價(jià)的轉(zhuǎn)換。

（2）應(yīng)用圖論中有關(guān)匹配問(wèn)題的相關(guān)算法，通過(guò)添加補(bǔ)充面，建立了模型的相似度評(píng)價(jià)算法，可完成差異較大的模型間的評(píng)價(jià)，降低了對(duì)參與評(píng)價(jià)的源模型與目標(biāo)模型之間的適用性要求，提高了模型相似度評(píng)價(jià)的普適性。