面向設(shè)計(jì)重用的三維CAD模型局部結(jié)構(gòu)檢索方法

張開興 杭晟煜 趙秀艷 王金星 宋正河 劉賢喜，3

(1．山東農(nóng)業(yè)大學(xué)機(jī)械與電子工程學(xué)院，泰安271018;2．中國農(nóng)業(yè)大學(xué)工學(xué)院，北京100083; 3．山東省園藝機(jī)械與裝備重點(diǎn)實(shí)驗(yàn)室，泰安271018)

面向設(shè)計(jì)重用的三維CAD模型局部結(jié)構(gòu)檢索方法

張開興1杭晟煜1趙秀艷1王金星1宋正河2劉賢喜1，3

(1．山東農(nóng)業(yè)大學(xué)機(jī)械與電子工程學(xué)院，泰安271018;2．中國農(nóng)業(yè)大學(xué)工學(xué)院，北京100083; 3．山東省園藝機(jī)械與裝備重點(diǎn)實(shí)驗(yàn)室，泰安271018)

為了更好地實(shí)現(xiàn)面向設(shè)計(jì)領(lǐng)域的三維CAD模型設(shè)計(jì)信息的有效重用，提出了一種融合語義的三維CAD模型局部結(jié)構(gòu)檢索方法。首先以設(shè)計(jì)特征作為設(shè)計(jì)語義信息的基礎(chǔ)載體，對三維CAD模型進(jìn)行結(jié)構(gòu)化表征，并用特征屬性鄰接圖來表示;然后設(shè)計(jì)能夠捕捉不同層次信息的特征描述子，構(gòu)建融合語義的特征相似性評價(jià)模型;最后采用子圖同構(gòu)算法計(jì)算查詢局部結(jié)構(gòu)與模型庫中零件的特征屬性鄰接圖的特征匹配對，以此計(jì)算相匹配局部結(jié)構(gòu)的相似度。實(shí)驗(yàn)結(jié)果表明，該方法能夠較好地實(shí)現(xiàn)融合語義的三維CAD模型局部結(jié)構(gòu)檢索，可以有效地支持面向農(nóng)機(jī)設(shè)計(jì)領(lǐng)域的三維CAD模型設(shè)計(jì)信息的重用?；跈z索的設(shè)計(jì)重用方法可為農(nóng)機(jī)裝備數(shù)字化設(shè)計(jì)中各類成果的有效重用提供多粒度、精確化和智能化的方法。

三維CAD模型;局部結(jié)構(gòu)檢索;設(shè)計(jì)重用;設(shè)計(jì)語義;特征屬性鄰接圖;子圖同構(gòu)

引言

日益增多的三維CAD模型為產(chǎn)品設(shè)計(jì)帶來了大量的可重用資源，且設(shè)計(jì)資源的重用在產(chǎn)品的創(chuàng)新設(shè)計(jì)中正變得越來越重要。據(jù)統(tǒng)計(jì)，在產(chǎn)品設(shè)計(jì)過程中，約40%是重用過去的部件設(shè)計(jì)，約40%是對已有設(shè)計(jì)部件的微小修改，而只有約20%是完全新的設(shè)計(jì)［1－2］。正是由于工程領(lǐng)域?qū)υO(shè)計(jì)資源重用的迫切需求，基于三維模型檢索的設(shè)計(jì)重用技術(shù)近年來成為研究熱點(diǎn)之一。然而已有方法通常只考慮三維CAD模型的整體檢索，忽略了產(chǎn)品數(shù)字化設(shè)計(jì)中的局部結(jié)構(gòu)檢索需求。事實(shí)上，在產(chǎn)品設(shè)計(jì)過程中，大量的設(shè)計(jì)重用是在更細(xì)觀的特征級和局部結(jié)構(gòu)級。即在更多情況下，能夠被重用的僅僅是模型間足夠相似的一些局部區(qū)域，而這些局部區(qū)域可以源于不同的三維CAD模型。因此，如何從海量產(chǎn)品模型中快速、有效地查找適合設(shè)計(jì)重用的局部結(jié)構(gòu)已成為產(chǎn)品開發(fā)各環(huán)節(jié)的一個(gè)迫切需求［3－4］。

近年來，三維CAD模型檢索技術(shù)研究正在向融合語義的方向發(fā)展，以更高的支持面向領(lǐng)域的重用，其基本思想是不僅考慮檢索對象幾何形狀的相似性，還要考慮應(yīng)用領(lǐng)域語義上的相似性［5］。BESPALOV等［6］利用尺度空間技術(shù)將三維網(wǎng)格模型分割為若干有意義的特征面片，并基于特征面片間的關(guān)聯(lián)關(guān)系構(gòu)建二叉樹，通過子圖匹配實(shí)現(xiàn)局部結(jié)構(gòu)檢索。BIASOTTI等［7］利用擴(kuò)展Reeb圖表征三維模型，并利用子圖匹配實(shí)現(xiàn)局部檢索。BAI等［8］提出了基于DBMS圖(多分辨率骨架圖)及子圖匹配的三維CAD模型局部結(jié)構(gòu)檢索方法。但是，這些方法主要面向三角網(wǎng)格模型，獲得的局部結(jié)構(gòu)難以捕捉與其關(guān)聯(lián)的設(shè)計(jì)信息，因而無法實(shí)現(xiàn)已有設(shè)計(jì)資源的有效重用［9］。

陶松橋等［10］提出了一種基于面屬性化鄰接圖非精確匹配的CAD模型搜索方法，通過提取CAD模型中的Brep信息將模型轉(zhuǎn)化為面屬性化鄰接圖，將非精確圖匹配問題轉(zhuǎn)化為二次優(yōu)化問題求解，可以實(shí)現(xiàn)模型的局部結(jié)構(gòu)檢索。LI等［11］提出基于特征依賴有向無環(huán)圖(Feature dependency directed acyclic graph，F(xiàn)DAG)的局部結(jié)構(gòu)檢索方法。該方法通過移除FDAG中關(guān)鍵點(diǎn)的方式提取可重用區(qū)域，并利用基于D2形狀分布圖的表征、相似性評價(jià)方法計(jì)算查詢實(shí)例和可重用區(qū)域之間的相似度。該方法以工程語義為基礎(chǔ)，因此，非常適合于三維CAD模型。BAI等［12］提出一種面向設(shè)計(jì)重用的三維CAD模型局部結(jié)構(gòu)檢索方法。該方法采用擴(kuò)展特征樹表示基于設(shè)計(jì)特征的三維CAD模型，然后基于啟發(fā)式規(guī)則提取潛在的可重用區(qū)域并且對其進(jìn)行表征，最后采用樹匹配算法實(shí)現(xiàn)由簡單查詢實(shí)例查找完整可重用區(qū)域的多模式局部結(jié)構(gòu)檢索。但是，這些方法還停留在特征幾何層面相似性評價(jià)，缺乏對特征的尺寸、精度、公差等設(shè)計(jì)語義信息的深入考慮，通常適用于產(chǎn)品概念設(shè)計(jì)階段的參考重用。

本文針對產(chǎn)品詳細(xì)設(shè)計(jì)階段的自適應(yīng)重用需求，提出融合語義的三維CAD模型局部結(jié)構(gòu)檢索方法。首先以設(shè)計(jì)特征作為設(shè)計(jì)語義信息的基礎(chǔ)載體，將三維CAD模型表示為具有設(shè)計(jì)語義信息的設(shè)計(jì)特征集合，并用特征屬性鄰接圖來表示和描述。此時(shí)，三維CAD模型局部結(jié)構(gòu)檢索問題可以轉(zhuǎn)換為查詢局部結(jié)構(gòu)與模型庫中零件的特征屬性鄰接圖子圖同構(gòu)匹配問題。然后，設(shè)計(jì)能夠捕捉不同層次信息的特征描述子，構(gòu)建融合語義的特征相似性評價(jià)模型，以支持特征的精細(xì)化比較。最后，根據(jù)匹配特征對的相似度計(jì)算相匹配局部結(jié)構(gòu)的相似度，以實(shí)現(xiàn)融合語義的局部結(jié)構(gòu)相似性評價(jià)。

1 設(shè)計(jì)特征語義信息模型的定義與表示

定義1:設(shè)計(jì)特征語義信息模型。設(shè)計(jì)特征語義信息模型由設(shè)計(jì)特征與設(shè)計(jì)語義信息構(gòu)成，可表示為

〈設(shè)計(jì)特征語義信息模型〉::=(［設(shè)計(jì)語義］〈設(shè)計(jì)特征〉)

〈設(shè)計(jì)語義〉::=〈特征間關(guān)聯(lián)設(shè)計(jì)語義〉|〈特征內(nèi)關(guān)聯(lián)設(shè)計(jì)語義〉

〈設(shè)計(jì)特征〉::=［特征內(nèi)關(guān)聯(lián)設(shè)計(jì)語義］〈幾何要素〉

其中，設(shè)計(jì)特征是設(shè)計(jì)語義信息的基礎(chǔ)載體，設(shè)計(jì)語義分為特征間關(guān)聯(lián)與特征內(nèi)關(guān)聯(lián)兩種模式。特征間關(guān)聯(lián)設(shè)計(jì)語義主要用來描述設(shè)計(jì)特征間的鄰接關(guān)系，包括父子、兄弟、對稱陣列、設(shè)計(jì)基準(zhǔn)等，特征內(nèi)關(guān)聯(lián)設(shè)計(jì)語義主要描述設(shè)計(jì)特征的基本屬性(如特征的類型、設(shè)計(jì)參數(shù)等)、設(shè)計(jì)要求(如尺寸、公差、表面粗糙度等)等。

定義2:特征屬性鄰接圖。特征屬性鄰接圖是一種用于描述設(shè)計(jì)特征語義信息模型內(nèi)部特征及特征間鄰接關(guān)系的圖結(jié)構(gòu)。在特征屬性鄰接圖中，每一個(gè)圖頂點(diǎn)對應(yīng)于模型中的一個(gè)設(shè)計(jì)特征，設(shè)計(jì)特征的基本屬性和設(shè)計(jì)要求作為頂點(diǎn)的屬性，圖中頂點(diǎn)間的關(guān)系與設(shè)計(jì)特征間的鄰接關(guān)系相對應(yīng)。

首先，利用一種基于圖和規(guī)則相結(jié)合的特征識別算法［13］對CAD模型包含的特征進(jìn)行自動識別，該算法對相交特征識別具有較好的效果，識別效率較高。對于模型中少量難以自動識別的特征，則利用人機(jī)交互來實(shí)現(xiàn)。本文考慮的設(shè)計(jì)特征主要是設(shè)計(jì)領(lǐng)域常見的凸臺類 (Boss)、型腔類 (Pocket)、臺階類(Step)、孔類 (Hole)和槽類特征(Slot)，以及由這些基本特征組合、或按一定規(guī)律排布而成的復(fù)合特征。然后，利用CAD系統(tǒng)的API函數(shù)對三維模型進(jìn)行解析(各主流 CAD系統(tǒng)都提供了在三維CAD模型上直接標(biāo)注尺寸精度、表面粗糙度等設(shè)計(jì)語義信息［14－15］)，提取與幾何點(diǎn)、邊、面關(guān)聯(lián)的設(shè)計(jì)語義信息，并根據(jù)設(shè)計(jì)特征組成的幾何要素集，將幾何關(guān)聯(lián)的尺寸、公差、表面粗糙度等信息映射到對應(yīng)的設(shè)計(jì)特征上，完成特征內(nèi)關(guān)聯(lián)設(shè)計(jì)語義信息的提取。從而實(shí)現(xiàn)將三維CAD模型表示為具有設(shè)計(jì)語義信息的設(shè)計(jì)特征集合，并用特征屬性鄰接圖來表示和描述。圖1給出了一產(chǎn)品三維CAD模型及其對應(yīng)的特征屬性鄰接圖，該模型由5個(gè)設(shè)計(jì)特征組成。

圖1 產(chǎn)品三維模型及其特征鄰接圖示例Fig．1 3Dmodel of sampling product and its feature adjacency graph

2 基于子圖同構(gòu)的三維模型局部結(jié)構(gòu)檢索方法

2.1 局部結(jié)構(gòu)匹配方法

為實(shí)現(xiàn)局部結(jié)構(gòu)匹配，本文將利用子圖同構(gòu)算法來實(shí)現(xiàn)屬性圖中尋找特定子屬性圖。

定義3:圖同構(gòu)。對于2個(gè)圖G=(V，E)、G'= (V'，E')，如果存在一一映射函數(shù)f:vi→v'j且e=(vi，vj)是G中的一條邊，當(dāng)且僅當(dāng)e'=(v'i，v'j)是G'的一條邊，則稱G、G'是同構(gòu)的。

定義4:子圖同構(gòu)。對于2個(gè)圖G=(V，E)、G'=(V'，E')，如果G'有子圖G″=(V″，E″)，V″V'，E″E'，使得G″與G同構(gòu)，則稱G、G'是子圖同構(gòu)的。

判斷2個(gè)圖是否同構(gòu)，本質(zhì)上就是看是否存在兩圖頂點(diǎn)之間的一個(gè)映射，使得兩圖的邊在該映射下也保持對應(yīng)。假設(shè)查詢局部結(jié)構(gòu)與模型庫中零件的特征鄰接屬性圖分別為G1與G2，采用子圖同構(gòu)算法可快速獲得G1與G2的一個(gè)匹配M，即G1到G2的一個(gè)映射。對于G1的每個(gè)頂點(diǎn)vi，在G2中只有1個(gè)頂點(diǎn)vj與vi相對應(yīng)，并且對于G1的每條邊ei，在G2中只有1條邊ej與ei相對應(yīng)，可以表示為

這里，查詢局部結(jié)構(gòu)作為模型庫中零件的子部分被認(rèn)為合理，而反之則不成立，因此，該映射是一個(gè)單射而非雙射。

給定2個(gè)圖G1、G2，其中G1為子圖，G2為大圖。設(shè)置一個(gè)映射匹配矩陣Mm×n(m=|G1|，n=|G2|)，Mm×n中任意一個(gè)元素mi，j的取值可以是0或1。其中，|Gi|(i=1，2)表示圖Gi的頂點(diǎn)個(gè)數(shù)，Mm×n表示圖G1與G2頂點(diǎn)間的對應(yīng)關(guān)系

判斷圖G1、G2是否子圖同構(gòu)，實(shí)際上就是看能否找到一個(gè)映射匹配矩陣Mm×n，使其滿足如下2個(gè)條件:每一行有且只有1個(gè)1;每一列至多只有1個(gè)1。如果找到滿足上述2個(gè)條件的映射匹配矩陣Mm×n，則說明圖G1與G2子圖同構(gòu)。

2.1.1 頂點(diǎn)映射匹配矩陣Mm×n初始化

在計(jì)算特征屬性鄰接圖G1、G2頂點(diǎn)映射匹配矩陣Mm×n時(shí)，引入了較多的特征屬性。在這些屬性中，有的屬性只要不同就可以將它們的頂點(diǎn)映射匹配矩陣元素 mi，j置為0，如特征類型。若圖 G1中第i個(gè)頂點(diǎn)對應(yīng)的特征類型為通槽，而圖G2中第j個(gè)頂點(diǎn)對應(yīng)的特征類型為孔，則可以置映射匹配矩陣Mm×n第i行第j列元素mi，j為0。這樣在局部結(jié)構(gòu)相似性評價(jià)之初，盡可能多地排除那些不可能的頂點(diǎn)對應(yīng)關(guān)系，以降低搜索空間的復(fù)雜度。

2.1.2 算法基本步驟

在頂點(diǎn)映射匹配矩陣初始化基礎(chǔ)上，進(jìn)行子圖同構(gòu)匹配搜索，具體步驟如下:

(1)輔助頂點(diǎn)集合定義

設(shè)置2個(gè)輔助的頂點(diǎn)集合V1和V2，分別用于存儲搜索過程中2個(gè)圖上已匹配上的頂點(diǎn)，初始時(shí)都置空;另外需要設(shè)置一個(gè)元素為V2的集合V3，用于存儲可能出現(xiàn)多種匹配的情況，初始時(shí)也置空。

(2)匹配搜索

搜索從映射匹配矩陣Mm×n的第一行開始，從左到右尋找值為1的列。對于任意的第i行，如果其第j列的值為1，并且該列沒有被占用，則表示找到1個(gè)可能匹配的頂點(diǎn)對，即圖G1的第i個(gè)頂點(diǎn)和圖G2的第j個(gè)頂點(diǎn)對應(yīng)，將這2個(gè)頂點(diǎn)分別加入到頂點(diǎn)集合V1和V2。

(3)匹配有效性判斷

如果新加入的這2個(gè)頂點(diǎn)在最終的同構(gòu)映射中確實(shí)是對應(yīng)匹配的頂點(diǎn)對，那么當(dāng)前時(shí)刻由圖G1中已匹配上的頂點(diǎn)集合V1構(gòu)成的子圖與圖G2中已匹配上的頂點(diǎn)集合V2構(gòu)成的子圖必定也是同構(gòu)的。根據(jù)這一原理，可以通過測試當(dāng)前V1構(gòu)成的子圖與V2構(gòu)成的子圖是否同構(gòu)來檢測新找到的列是否有效。

(4)匹配搜索循環(huán)

若V1構(gòu)成的子圖與V2構(gòu)成的子圖同構(gòu)，則說明新找到的列是有效的，設(shè)置占用標(biāo)志，進(jìn)入下一行;否則，在當(dāng)前行繼續(xù)尋找下一個(gè)有效列;如果當(dāng)前行搜索完畢都沒有找到一個(gè)有效列，則退回上一行，并且從上一行已經(jīng)占用列的下一列開始搜索。

2.1.3 算法分析

上述子圖同構(gòu)算法的時(shí)間復(fù)雜度主要集中在“大圖”中尋找“子圖”，而子圖同構(gòu)問題是NP完全問題，現(xiàn)有求解算法的時(shí)間復(fù)雜度一般比較高。本文算法在最好情況下只需對映射矩陣進(jìn)行一輪無回溯搜索，此時(shí)對應(yīng)的時(shí)間復(fù)雜度為O(m)，最差情況下需要遍歷映射矩陣所有可能分支，時(shí)間復(fù)雜度為O(n!/(n－m)!)，其中m為子圖頂點(diǎn)數(shù)目，n為大圖頂點(diǎn)數(shù)目。

為提高匹配效率，本文在設(shè)計(jì)算法時(shí)充分利用特征屬性鄰接圖中的特征屬性，使得初始映射匹配矩陣MA×I中的元素盡可能多的為0，大大降低了搜索空間的復(fù)雜度;并且在動態(tài)搜索過程中，每前進(jìn)一步，獲得一個(gè)可能匹配的頂點(diǎn)對之后，利用2個(gè)圖中當(dāng)前已匹配上的頂點(diǎn)集合組成的2個(gè)子圖應(yīng)該是同構(gòu)這一原理，迅速對該頂點(diǎn)對匹配關(guān)系的有效性進(jìn)行判斷，無需等到所有頂點(diǎn)都對應(yīng)齊全之后再集中判斷是否同構(gòu)，盡早丟棄不可能最終匹配的頂點(diǎn)對，加速了搜索的進(jìn)程。

2.2 融合設(shè)計(jì)語義的特征相似性評價(jià)

特征的精細(xì)化比較是三維CAD模型局部結(jié)構(gòu)相似性評價(jià)的基礎(chǔ)。為有效地實(shí)現(xiàn)特征的精細(xì)化比較，基于分析設(shè)計(jì)特征語義信息模型相似性比較中用到的屬性信息，設(shè)計(jì)了一個(gè)能夠描述不同層次信息的特征描述子，并對特征描述子的各組成要素進(jìn)行量化，然后將多種屬性融合構(gòu)建設(shè)計(jì)特征的相似性評價(jià)模型。該特征描述子被定義為一個(gè)5維向量，包括從高層次的設(shè)計(jì)語義信息到低層次的幾何信息。高層的設(shè)計(jì)語義信息包括設(shè)計(jì)特征類型、公差/表面粗糙度和特征鄰接關(guān)系，低層幾何信息包括幾何尺度和幾何形狀信息。由于上述組成要素具有不同的內(nèi)涵和測度，在進(jìn)行特征的相似性評價(jià)時(shí)，各組成要素的評價(jià)需按如下規(guī)則進(jìn)行。

(1)特征類型

如果2個(gè)相比較設(shè)計(jì)特征的類型不同，則認(rèn)為2個(gè)特征的相似度為0，即特征不相似。如果特征類型相同，則特征類型的相似度為1。設(shè)2個(gè)相比較特征分別為F1和F2，特征類型相似度表示為

(2)公差/表面粗糙度

在零件詳細(xì)設(shè)計(jì)階段，公差/表面粗糙度與特征所能實(shí)現(xiàn)的功能、行為等密切相關(guān)。對于幾何形狀完全相同的2個(gè)設(shè)計(jì)特征，如果尺寸精度差異比較大，則對應(yīng)的功能、行為可能非常不同。公差/表面粗糙度的相似度表示為

式中 T1、T2——2個(gè)相比較特征基本屬性中公差最高等級

R1、R2——2個(gè)特征表面粗糙度最小值

(3)拓?fù)溧徑雨P(guān)系

設(shè)計(jì)特征間的鄰接關(guān)系在三維CAD模型的相似性評價(jià)中占有重要的地位，在幾何形狀相似的前提下，具有相同鄰接關(guān)系的設(shè)計(jì)特征從設(shè)計(jì)重用角度講則更為相似。2個(gè)設(shè)計(jì)特征間鄰接關(guān)系的相似度表示為

式中 ne——2個(gè)特征中相融邊數(shù)量

n1、n2——與2個(gè)相比較特征相連接的特征數(shù)量

相融邊是指在特征鄰接屬性圖中，如果一對邊分屬類型相同的2個(gè)設(shè)計(jì)特征，這2個(gè)設(shè)計(jì)特征分屬不同的三維CAD模型，且每條邊所連接的2個(gè)設(shè)計(jì)特征的類型相同，則稱該對邊相融。

(4)幾何尺度

相同特征類型的設(shè)計(jì)特征，尺度不同可能導(dǎo)致其重用價(jià)值完全不同。例如，形狀相似的2個(gè)孔，但是其深度或廣度存在比較大的差異，導(dǎo)致其體積存在較大的不同，相應(yīng)的幾何驅(qū)動參數(shù)也存在較大的差異，可重用價(jià)值相對較小。因此，在模型局部結(jié)構(gòu)的相似性評價(jià)中同樣需要考慮尺度信息。

2個(gè)相比較特征之間的幾何尺度相似度SQ用其最小包圍盒(Oriented bounding box，OBB)來評價(jià)，即

式中 ai、bi——相比較的2個(gè)設(shè)計(jì)特征的最小包圍盒的長、寬、高

(5)幾何形狀

對于相同類型的設(shè)計(jì)特征，其幾何形狀可能存在差異。從設(shè)計(jì)重用角度來講，形狀相似是設(shè)計(jì)重用的前提。因此，為了計(jì)算設(shè)計(jì)特征形狀的差異性，本文采用形狀分布算法［16］對設(shè)計(jì)特征的幾何形狀進(jìn)行比較。通過對模型表面隨機(jī)取點(diǎn)，統(tǒng)計(jì)隨機(jī)點(diǎn)間的距離(D2)作為度量尺度并形成分布曲線。形狀相似度 SD采用推土機(jī)距離(Earth mover's distance，EMD)計(jì)算，EMD距離是一種有效且越來越被廣泛使用的集合間或向量間距離計(jì)算方式［17］，即

其中 H1={h11，h12，…，h1n}

H2={h21，h22，…，h2m}

式中 H1、H2——2個(gè)相比較特征的形狀分布曲線

綜上，2個(gè)特征F1與F2的相似度用δ表示，定義為特征類型、公差/表面粗糙度、鄰接關(guān)系、幾何尺度與形狀相似度的加權(quán)和，即

其中

式中 ωg——各分量的權(quán)重系數(shù)

當(dāng)特征類型不同時(shí)，δ等于0，無需進(jìn)行其他屬性(公差/表面粗糙度、鄰接關(guān)系、形狀等)的比較，以簡化特征相似性比較過程。

2.3 局部結(jié)構(gòu)相似度計(jì)算

當(dāng)局部結(jié)構(gòu)P1與P2之間的一個(gè)成功匹配被找到后，需要基于M以及其匹配頂點(diǎn)對的屬性來計(jì)算2個(gè)局部結(jié)構(gòu)的相似度。對于任意一個(gè)匹配頂點(diǎn)對(vi，M(vi))，其特征相似度計(jì)算公式為

其中

式中 ωi——頂點(diǎn)vi的權(quán)重

δ(vi，M(vi))——匹配頂點(diǎn)對的特征相似度

2個(gè)局部結(jié)構(gòu)的相似度定義為所有匹配頂點(diǎn)對特征相似度的加權(quán)和，匹配頂點(diǎn)對權(quán)重ωi采用啟發(fā)式規(guī)則設(shè)定。根據(jù)面向設(shè)計(jì)重用的三維CAD模型局部檢索需求特點(diǎn)，在特征屬性鄰接圖中，相似度相同的頂點(diǎn)權(quán)重相等，且相似度越大的頂點(diǎn)權(quán)重越大。

3 算法驗(yàn)證與討論

為了驗(yàn)證算法的有效性，以 Microsoft Visual Studio 2010為集成開發(fā)環(huán)境，Open CASCADE為幾何平臺，實(shí)現(xiàn)本文算法，實(shí)驗(yàn)中所使用模型主要來自于 普 渡 大 學(xué) 的 ESB (Engineering shape benchmark)［18］模型庫和項(xiàng)目組成員根據(jù)國家科技支撐計(jì)劃項(xiàng)目“農(nóng)機(jī)專業(yè)底盤數(shù)字化設(shè)計(jì)技術(shù)研究與示范”構(gòu)建的農(nóng)機(jī)專業(yè)底盤零部件模型庫。

表1所示為對圖1中的模型提取的特征描述子信息，包括特征類型、公差/表面粗糙度、特征鄰接關(guān)系等設(shè)計(jì)語義信息和幾何尺度、幾何形狀等幾何信息。

表1 模型特征描述子信息Tab．1 Information ofmodel feature descriptor

表2所示為從模型中選取紅色標(biāo)記的局部結(jié)構(gòu)對其進(jìn)行檢索，得到本文算法與文獻(xiàn)［10］算法檢索結(jié)果的比較。該局部結(jié)構(gòu)由1個(gè)非圓凸臺和2個(gè)通孔組成，文獻(xiàn)［10］算法基于面屬性鄰接圖，可以精確地查找到5個(gè)包含該局部結(jié)構(gòu)的三維模型，而本文算法基于特征屬性鄰接圖，除了可以精確查找到這5個(gè)模型外，還返回了和查詢局部結(jié)構(gòu)特征相同、形狀不同的3個(gè)模型，可更好地指導(dǎo)企業(yè)參考并重用已有模型。同時(shí)，由于模型特征的數(shù)目小于面的數(shù)目，本文算法效率高于文獻(xiàn)［10］算法。

表2 兩種算法檢索結(jié)果的比較Tab．2 Comparison of two kinds of algorithm s retrieval results

表3所示為從模型庫中分別選取2個(gè)典型的局部結(jié)構(gòu)對其進(jìn)行局部檢索，得到排列在前6個(gè)模型的結(jié)果，可以將模型庫中包含檢索局部結(jié)構(gòu)的模型全部檢索出來，并按相似度大小進(jìn)行排序，檢索效果較好。其中叉形局部結(jié)構(gòu)由8個(gè)特征組成，盤形局部結(jié)構(gòu)由5個(gè)特征組成，這些返回的局部結(jié)構(gòu)通常隱藏在外形各不相同的三維CAD模型中，設(shè)計(jì)人員難以通過已有商用CAD系統(tǒng)中預(yù)覽所有三維CAD模型交互地去發(fā)現(xiàn)，并對它們進(jìn)行重用。但是，通過本文方法可以有效地對這些局部結(jié)構(gòu)進(jìn)行提取，并且相匹配的局部結(jié)構(gòu)用紅色進(jìn)行標(biāo)識，而與這些局部結(jié)構(gòu)關(guān)聯(lián)的設(shè)計(jì)信息(如功能、裝配關(guān)系、裝配特征、有限元分析結(jié)果等)均可以推送給設(shè)計(jì)人員，供設(shè)計(jì)人員參考［19－20］。

表3 局部結(jié)構(gòu)檢索實(shí)例Tab．3 Retrieval exam ples of part structure

圖2給出了局部結(jié)構(gòu)檢索結(jié)果的查全查準(zhǔn)率圖［18］。由于檢索結(jié)果中包含了與各查詢局部結(jié)構(gòu)相關(guān)的所有零件模型，因此，其查準(zhǔn)率均為1.0。從圖2可以看出，當(dāng)查全率小于0.7時(shí)，平均查全查準(zhǔn)率曲線接近于查準(zhǔn)率為1.0的水平線，這意味著隨著檢索到的相關(guān)局部結(jié)構(gòu)數(shù)量的增加，局部結(jié)構(gòu)檢索的精度能夠維持在一個(gè)較高的水準(zhǔn)。此外，當(dāng)查全率為1.0時(shí)，查準(zhǔn)率達(dá)到了0.82。理想檢索結(jié)果的曲線應(yīng)該是一條查準(zhǔn)率恒等于1.0的平行直線。顯然，位置靠上的曲線具有較高精度，代表著較好的檢索結(jié)果。因此，本文局部結(jié)構(gòu)檢索算法的性能較好。

圖2 局部結(jié)構(gòu)檢索結(jié)果的查全查準(zhǔn)率曲線Fig．2 Precision-recall curve of part structure retrieval results

為了充分驗(yàn)證本文算法局部結(jié)構(gòu)的檢索性能，圖3給出了2個(gè)查詢局部結(jié)構(gòu)在不同數(shù)量的測試模型庫下的檢索運(yùn)行時(shí)間，該測試在配有 Intel Pentium 4 CPU 3.06GHz和4GB內(nèi)存的計(jì)算機(jī)上運(yùn)行。實(shí)驗(yàn)中通過隨機(jī)抽取的方式構(gòu)建8組測試模型庫，每組模型庫中模型的數(shù)量分別為50、100、…、400。為了保證統(tǒng)計(jì)時(shí)間的可靠性，對于每一個(gè)查詢局部結(jié)構(gòu)與每一個(gè)測試模型庫，先后運(yùn)行100次并將100次檢索時(shí)間的平均值作為該查詢局部結(jié)構(gòu)在該模型庫下的檢索時(shí)間。由圖3可以看出，檢索運(yùn)行時(shí)間與測試模型庫中相關(guān)局部結(jié)構(gòu)的數(shù)量基本呈線性關(guān)系。這主要由于大部分非相關(guān)零件模型在映射匹配矩陣初始化階段就被排除在外，只有保留下來的極少量零件模型才會進(jìn)行后續(xù)的特征精細(xì)化比較。并且在所有的查詢局部結(jié)構(gòu)中，局部結(jié)構(gòu)所包含的特征的數(shù)量越多所需的查詢時(shí)間也越多。當(dāng)測試模型庫包含有400個(gè)模型時(shí)，查詢叉形局部結(jié)構(gòu)的運(yùn)行時(shí)間最長，為10.615 s。對于多數(shù)CAD模型其構(gòu)成特征的數(shù)量是有限的，因此，本文算法運(yùn)行效率較高且是可行的。

圖3 局部結(jié)構(gòu)檢索運(yùn)行時(shí)間Fig．3 Runtime of part structure retrieval

4 設(shè)計(jì)重用實(shí)例

履帶式聯(lián)合收獲機(jī)底盤變速箱主要由箱體、軸類零件、齒輪、軸承及鍵等組成。在變速箱的設(shè)計(jì)過程中，首先根據(jù)收獲機(jī)底盤的功率、轉(zhuǎn)速等設(shè)計(jì)要求得到變速箱的設(shè)計(jì)參數(shù)，并計(jì)算得出所需要的齒輪、軸類等零件，同時(shí)結(jié)合收獲機(jī)底盤傳動系統(tǒng)布置方案規(guī)劃該類零件的空間位置;然后根據(jù)其空間位置要求設(shè)計(jì)變速箱箱體。其中，軸類零件結(jié)構(gòu)簡單，齒輪、軸承及鍵等一般是標(biāo)準(zhǔn)件，不需要進(jìn)行單獨(dú)設(shè)計(jì)，而變速箱箱體形狀復(fù)雜、不規(guī)則，存在重復(fù)設(shè)計(jì)的現(xiàn)象。應(yīng)用本文方法可以使設(shè)計(jì)人員從海量的模型中快速、準(zhǔn)確地找到滿足變速箱箱體設(shè)計(jì)重用需求的可重用模型或局部區(qū)域，從而利用這些資源高效地設(shè)計(jì)出滿足要求的新產(chǎn)品。

首先，根據(jù)變速箱已設(shè)計(jì)零件，考慮其尺寸以及空間位置，設(shè)計(jì)如圖4所示的變速箱箱體簡單設(shè)計(jì)模型局部結(jié)構(gòu)，作為搜索對象，在模型數(shù)據(jù)庫中，執(zhí)行三維CAD模型局部結(jié)構(gòu)檢索，尋找具有相似設(shè)計(jì)特征的模型作為設(shè)計(jì)參考，如表4所示，可以將模型庫中包含局部結(jié)構(gòu)的模型全部檢索出來。通過分析和比較搜索結(jié)果模型與輸入的待搜索簡單模型，由人工在返回相關(guān)模型中挑選出與變速箱箱體簡單設(shè)計(jì)模型基本外形、結(jié)構(gòu)、功能最相似的模型進(jìn)行下一階段的設(shè)計(jì)重用。

圖4 變速箱箱體簡單設(shè)計(jì)模型局部結(jié)構(gòu)Fig．4 Part structure of transmission case body primarymodel

表4 設(shè)計(jì)重用實(shí)例Tab．4 Instance of design reuse

得到設(shè)計(jì)特征匹配的變速箱箱體零件后，需要根據(jù)尺寸、連接判斷能否可以直接重用。若不可以直接重用，則將相似度最高的搜索結(jié)果導(dǎo)入CAD系統(tǒng)后對其進(jìn)行編輯和修改，最后在CAD系統(tǒng)中完成變速箱的數(shù)字化裝配，如圖5所示為在Pro/E軟件系統(tǒng)完成的變速箱設(shè)計(jì)。同理，履帶式聯(lián)合收獲機(jī)底盤的其他零部件，如車架、車橋、懸架、離合器、驅(qū)動橋等，均可以通過本實(shí)例所展示的方法進(jìn)行設(shè)計(jì)重用。設(shè)計(jì)者只需構(gòu)造簡單的基體結(jié)構(gòu)，通過局部檢索及重用可以方便、快速地完成最終設(shè)計(jì)。這種“模糊模式”下的檢索特性為詳細(xì)設(shè)計(jì)階段的用戶提供了很大的方便性和靈活性，圖6所示為在CAD系統(tǒng)中完成的履帶式聯(lián)合收獲機(jī)底盤模型。

5 結(jié)束語

針對目前三維CAD模型檢索方法忽視產(chǎn)品數(shù)字化設(shè)計(jì)中局部結(jié)構(gòu)的檢索需求，同時(shí)為了解決現(xiàn)階段融合語義的三維CAD模型檢索難以捕捉設(shè)計(jì)信息、缺乏對設(shè)計(jì)語義信息深入考慮的問題，實(shí)現(xiàn)產(chǎn)品詳細(xì)設(shè)計(jì)階段設(shè)計(jì)資源的有效重用，提出了融合語義的三維CAD模型局部結(jié)構(gòu)檢索方法。該方法首先以設(shè)計(jì)特征作為設(shè)計(jì)語義信息的基礎(chǔ)載體，將三維CAD模型進(jìn)行具有設(shè)計(jì)語義信息的設(shè)計(jì)特征結(jié)構(gòu)化表征，并且用特征屬性鄰接圖來表示和描述，這樣三維CAD模型局部結(jié)構(gòu)檢索問題就轉(zhuǎn)換為查詢局部結(jié)構(gòu)與模型庫中零件的特征屬性鄰接圖子圖同構(gòu)匹配問題;然后，設(shè)計(jì)包含不同層次信息的特征描述子，構(gòu)建融合語義的設(shè)計(jì)特征相似性評價(jià)模型;最后，基于設(shè)計(jì)特征相似性評價(jià)模型，采用子圖同構(gòu)算法計(jì)算查詢局部結(jié)構(gòu)與模型庫中零件的特征屬性鄰接圖的特征匹配對，計(jì)算相匹配局部結(jié)構(gòu)之間的相似度。實(shí)驗(yàn)結(jié)果表明，融合語義的三維CAD模型局部結(jié)構(gòu)檢索方法能夠?yàn)樵O(shè)計(jì)者提供方便、靈活的查詢方式，幫助其利用簡單的查詢實(shí)例查找滿足設(shè)計(jì)重用需求的完整可重用區(qū)域，能夠極大地加速那些包含較多獨(dú)立功能區(qū)域的復(fù)雜CAD模型的設(shè)計(jì)，且較好地保證相應(yīng)設(shè)計(jì)的正確性。

圖5 變速箱裝配圖Fig．5 Transmission case assembly drawing

圖6 某履帶式聯(lián)合收獲機(jī)底盤模型Fig．6 Tracked combine chassismodel

1 IYER N，JAYANTIS，LOU K，etal．Three-dimensional shape searching:state-of-the-art review and future trends［J］．Computer-Aided Design，2005，37(5):509－530．

2 張開興，黃瑞，劉賢喜．基于距離-夾角形狀分布的三維CAD模型檢索算法［J/OL］．農(nóng)業(yè)機(jī)械學(xué)報(bào)，2014，45(4):317－320．http:∥www．j-csam．org/jcsam/ch/reader/view_abstract．a(chǎn)spx?file_no=20140450＆flag=1．DOI:10．6041/j．issn．1000-1298．2014．04．050．ZHANG Kaixing，HUANG Rui，LIU Xianxi．3D CADmodel retrieval algorithm based on distance and angle distributions［J/OL］．Transactions of the Chinese Society for Agricultural Machinery，2014，45(4):317－320．(in Chinese)

3 REGLIW C，SPAGNUOLO M．Introduction to shape similarity detection and search for CAD/CAE applications［J］．Computer-Aided Design，2006，38(9):937－938．

4 HUANG R，ZHANG S，BAIX，et al．An effective subpart retrieval approach of 3D CAD models formanufacturing process reuse［J］．Computers in Industry，2015，67:38－53．

5 張欣，莫蓉，陳濤，等．面向設(shè)計(jì)意圖不變的三維CAD模型重用方法［J］．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，24(10): 1356－1362．ZHANG Xin，MO Rong，CHEN Tao，et al．Design intent preserved reuse of 3D CAD models［J］．Journal of Computer-Aided Design＆Computer Graphics，2012，24(10):1356－1362．(in Chinese)

6 BESPALOV D，REGLIW C，SHOKOUFANDEH A．Local feature extraction and matching partial objects［J］．Computer-Aided Design，2006，38(9):1020－1037．

7 BIASOTTIS，MARINIS，SPAGNUOLOM，etal．Sub-part correspondence by structural descriptors of3D shapes［J］．Computer-Aided Design，2006，38(9):1002－1019．

8 BAIJ，LIU Y S，GAO SM．Multi-mode solid model retrieval based on partial matching［C］∥The 10th IEEE International Conference on Computer-Aided Design and Computer Graphics，2007:126－131．

9 CHEN X，GAO SM，GUO S，et al．A flexible assembly retrieval approach formodel reuse［J］．Computer-Aided Design，2012，44(6):554－574．

10 陶松橋，王書亭，鄭壇光，等．基于非精確圖匹配的CAD模型搜索方法［J］．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2010，22(3):545－552．TAO Songqiao，WANG Shuting，ZHENG Tanguang，et al．CADmodel retrieval based on inexactgraphmatching［J］．Journal of Computer-Aided Design＆Computer Graphics，2010，22(3):545－552．(in Chinese)11 LIM，ZHANG Y F，QIU Z M．Toward effective mechanical design reuse:CAD model retrieval based on general and partial shapes［J］．Journal of Mechanical Design，2009，131(12):1－8．

12 BAIJ，GAO SM，TANG W H，et al．Design reuse oriented partial retrieval of CAD models［J］．Computer-Aided Design，2010，42(12):1069－1084．

13 SUNIL V B，AGARWAL R，PANDE SS．An approach to recognize interactiong features from B-Rep CAD models of prismatic machined parts using a hybrid(graph and rule based)technique［J］．Computer in Industry，2010，61(7):686－701．

14 QUINTANA V，RIVEST L，PELLERIN R，etal．Willmodel-based definition replace engineering drawings throughout the product lifecycle?A global perspective from aerospace industry［J］．Computers in Industry，2010，61(5):497－508．

15 ALEMANNIM，DESTEFANIS F，VEZZETTI E．Model-based definition design in the product lifecycle management scenario［J］．International Journal of Advanced Manufacturing Technology，2011，52(1):1－14．

16 OSADA R，F(xiàn)UNKHOUSER T，CHAZELLE B，et al．Shape distributions［J］．ACM Transactions on Graphics，2002，21(4): 807－832．

17 陳純．計(jì)算機(jī)圖像處理技術(shù)與算法［M］．北京:清華大學(xué)出版社，2003．

18 JAYANTI S，KALYANARAMAN Y，IYER N，et al．Developing an engineering shape benchmark for CAD models［J］．Computer-Aided Design，2006，38(9):939－953．

19 MA L J，HUANG Z D，WANG Y W．Automatic discovery of common design structures in CAD models［J］．Computers＆Graphics，2010，34(5):545－555．

20 SHAO Y，LIU Y，LI C．Intermediate model based efficient and integrated multidisciplinary simulation data visualization information reuse［J］．Advances in Engineering Software，2015，90:138－151．

Effective Subpart Retrieval Method of 3D CAD Models for Design Reuse

ZHANG Kaixing1HANG Shengyu1ZHAO Xiuyan1WANG Jinxing1SONG Zhenghe2LIU Xianxi1，3
(1．College of Mechanical and Electronic Engineering，Shandong Agricultural University，Taian 271018，China 2．College of Engineering，China Agricultural University，Beijing 100083，China 3．Shandong Provincial Key Laboratory of Horticultural Machineries and Equipments，Taian 271018，China)

With the development of digital design and manufacturing integrated technology，3D CAD model has become the coremedia of expressing product design and manufacturing information，efficiently locating the desired model from massive candidates，fully exploiting and reusing the implicit knowledge had an important role in improving the mechanical design efficiency and quality in the agricultural equipment field．To effectively realize the reuse of design information of 3D CAD models in design domain，an effective subpart retrieval method of 3D CAD models merging with design semantics was proposed．Firstly，design feature was taken as the basic carrier of design semantic information，the 3D CAD model was structuralized and represented by using a feature attribute adjacency graph(FAAG)．Then，amultilevel feature descriptor capturing different levels of information for detailed part design was designed to establish the design feature similarity assessmentmodel．Finally，the matched feature pairs were extracted by using the sub-graph isomorphism algorithm between the FAAGs of the query subpart and the part in the model library to calculate the similarity between matched subparts．Experimental results showed that the proposed method can effectively support subpart retrieval of 3D CAD models merging with design semantics for design reuse．The proposed research results can provide a novel reuse method ofmulti-granularity，precise and intelligent for the agriculturalmachinery digital design，and had an important role in improving themechanical design efficiency and quality in the agricultural equipment field．

3D CAD model;subpart retrieval;design reuse;design semantics;feature attribute adjacency graph;sub-graph isomorphism

TP391

A

1000-1298(2017)07-0405-08

2016-10-28

2016-12-15

國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目(2016YFD0700500)、山東省“雙一流”獎(jiǎng)補(bǔ)資金項(xiàng)目(SYL2017XTTD14)、山東省自然科學(xué)基金項(xiàng)目(ZR2015EL022)和山東省現(xiàn)代農(nóng)業(yè)產(chǎn)業(yè)技術(shù)體系水稻創(chuàng)新團(tuán)隊(duì)項(xiàng)目

張開興(1984—)，男，副教授，博士，主要從事農(nóng)業(yè)CAD和農(nóng)業(yè)信息化研究，E-mail:kaixingzhang@139．com

劉賢喜(1963—)，男，教授，博士生導(dǎo)師，主要從事農(nóng)業(yè)CAD/CAM和虛擬現(xiàn)實(shí)技術(shù)研究，E-mail:wjbliu@sdau．edu．cn

10．6041/j．issn．1000-1298．2017．07．052