白 靜

（北方民族大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，寧夏 銀川 750021）

0 引言

設(shè)計(jì)作為人類智慧集中體現(xiàn)的一種創(chuàng)造性勞動(dòng)，其本質(zhì)就是對(duì)知識(shí)的處理和利用。隨著三維計(jì)算機(jī)輔助設(shè)計(jì)（Computer Aided Design，CAD）系統(tǒng)的推廣應(yīng)用，如今三維CAD 模型已經(jīng)成為設(shè)計(jì)知識(shí)存儲(chǔ)的主要載體之一，為產(chǎn)品設(shè)計(jì)提供了豐富的可重用信息。如何快速、有效地檢索并利用三維CAD 模型及其攜帶的設(shè)計(jì)知識(shí)，成為工業(yè)設(shè)計(jì)領(lǐng)域普遍關(guān)注的熱點(diǎn)之一。

傳統(tǒng)的三維模型檢索方法以模型間的視覺相似性為判斷依據(jù)，提取并比較體現(xiàn)模型視覺特征的幾何形狀和拓?fù)浣Y(jié)構(gòu)，完成模型間的相似比較。典型的工作有基于形狀直方圖［1-2］、二維視圖［3］等幾何形狀及Reeb圖［4］、屬性鄰接圖［5］、拓?fù)溥B接圖［6］等拓?fù)涿枋鲎拥姆椒ā？傮w來說這類方法具有適用范圍廣、計(jì)算效率高等優(yōu)點(diǎn)，非常適合三維模型的一般性檢索。然而，無論是模型的幾何形狀還是拓?fù)浣Y(jié)構(gòu)，其表征的內(nèi)容均為模型較底層的信息；而在工程設(shè)計(jì)領(lǐng)域，人們希望檢索并重用的三維CAD 模型往往需要符合其設(shè)計(jì)的上下文環(huán)境，滿足某種語義相似性，造成現(xiàn)有三維模型檢索方法多卻無法滿足CAD 模型檢索需求的現(xiàn)狀。

為了更加貼近工程設(shè)計(jì)領(lǐng)域用戶的檢索需求，研究者們提出了一系列專門針對(duì)三維CAD 模型的檢索方法。其中一類方法通過提取并比較模型的質(zhì)量、材料和粗糙度等產(chǎn)品綜合信息，實(shí)現(xiàn)模型間的相似比較［7］。因?yàn)榉从沉水a(chǎn)品的語義特征，這類方法很符合工程領(lǐng)域檢索需求，但是往往需要人工輸入模型以外的其他信息，所以存在主觀性較強(qiáng)、穩(wěn)定性不足且難以實(shí)現(xiàn)自動(dòng)化的問題。另外一類方法通過提取并比較三維CAD 模型的加工特征圖，完成三維CAD 模型間的相似評(píng)價(jià)［8-9］。這類方法以加工特征識(shí)別為基礎(chǔ)，能夠較好地實(shí)現(xiàn)自動(dòng)化，同時(shí)其提取的描述符能夠有效地反映加工階段的語義信息，因此非常適合于尋找具有相同加工成本、加工工藝等加工需求的三維CAD 模型，但是仍難以滿足工程設(shè)計(jì)階段的檢索重用需求。為此，有學(xué)者提出了基于設(shè)計(jì)特征表征的三維CAD 模型相似評(píng)價(jià)方法［10］。然而，因?yàn)樵O(shè)計(jì)特征的定義較為自由，同一模型對(duì)應(yīng)的設(shè)計(jì)特征模型可能不同，且基于設(shè)計(jì)特征圖匹配的相似比較方法效率也很低，所以這類方法并沒有得到很好的應(yīng)用。

針對(duì)現(xiàn)有這些檢索方法在支持設(shè)計(jì)階段的檢索及重用方面存在的不足，本文提出一種基于擴(kuò)展特征樹匹配的三維CAD 模型相似評(píng)價(jià)算法。該方法利用擴(kuò)展特征樹表征三維CAD 模型的設(shè)計(jì)信息，利用非精確的樹匹配策略實(shí)現(xiàn)模型間的相似評(píng)價(jià)。相對(duì)于其他三維模型的相似評(píng)價(jià)方法，本文算法具有以下優(yōu)點(diǎn)：

（1）表征能力強(qiáng) 通過對(duì)設(shè)計(jì)特征模型的約束性定義及擴(kuò)展特征關(guān)系的自動(dòng)識(shí)別，確保擴(kuò)展特征樹的穩(wěn)定性和唯一性，對(duì)設(shè)計(jì)特征模型的表征具有非常積極的意義。

（2）匹配速度快 基于非精確樹匹配的三維CAD模型相似評(píng)價(jià)與傳統(tǒng)的圖匹配相比較，具有明顯的效率優(yōu)勢(shì)。

（3）檢索結(jié)果語義性強(qiáng) 適用于面向產(chǎn)品設(shè)計(jì)階段的檢索及重用。

1 方法概述

給定一個(gè)CAD 模型，該模型包含幾何、拓?fù)浜驼Z義三個(gè)不同層面的信息。為有效輔助設(shè)計(jì)人員找到滿足其設(shè)計(jì)重用需求的CAD 模型，需要提取CAD 模型中所包含的設(shè)計(jì)語義信息。這里，最簡(jiǎn)單、直觀的方式就是提取CAD 模型基于形狀特征的描述符。這是因?yàn)樽鳛橐环N具有一定工程意義的幾何形狀，形狀特征能夠?qū)崿F(xiàn)CAD 模型的幾何實(shí)體和其隱含的語義信息的連接。然而，由于形狀特征尤其是設(shè)計(jì)特征定義的自由度很大，基于形狀特征表征的描述符往往難以確保其唯一性，制約了基于形狀特征的描述符在CAD 模型檢索領(lǐng)域的應(yīng)用。白靜等針對(duì)這一問題提出一種擴(kuò)展特征樹的工程零件設(shè)計(jì)特征模型［11］，該模型能夠在一定程度上保證設(shè)計(jì)特征的唯一性及穩(wěn)定性。利用該描述符的層次屬性及局部屬性，白靜等將其用于三維CAD模型的局部檢索中，以支持可重用區(qū)域的有效提取和層次表征，并通過位圖索引及樹匹配實(shí)現(xiàn)多模式的局部檢索［12］。本文利用擴(kuò)展特征樹表征整個(gè)三維CAD 模型，并提出非精確的樹匹配算法及一種自適應(yīng)的權(quán)重分配方案，用以實(shí)現(xiàn)三維CAD 模型之間的相似評(píng)價(jià)，完成三維CAD 模型的全局檢索。圖1所示為本文方法的整體流程示意圖。

2 基于擴(kuò)展特征樹的三維CAD模型表征

2.1 擴(kuò)展特征樹的構(gòu)建

為使零件的設(shè)計(jì)特征模型具有唯一性，一種有效的方式就是限定模型表征中設(shè)計(jì)特征的類型。在擴(kuò)展特征樹的表示中，對(duì)模型的設(shè)計(jì)特征進(jìn)行了如下限定：設(shè)計(jì)特征為簡(jiǎn)單設(shè)計(jì)特征，包括基本設(shè)計(jì)特征及由這些基本設(shè)計(jì)特征組合或按一定規(guī)律排布而成的組合設(shè)計(jì)特征和陣列。另外，為了有效地簡(jiǎn)化模型表征，在擴(kuò)展特征樹的表示中，將特征間的關(guān)系分為兩類，一類是依賴與被依賴的關(guān)系，對(duì)應(yīng)擴(kuò)展特征樹中的父子關(guān)系（如凸臺(tái)上的孔和凸臺(tái)之間的關(guān)系）；另一類是一種平等關(guān)系，包括相交和貼合，作為擴(kuò)展特征樹中兄弟節(jié)點(diǎn)的擴(kuò)展屬性加以記錄，如圖2所示。

作為示例，圖3給出了一個(gè)設(shè)計(jì)特征模型及其對(duì)應(yīng)的擴(kuò)展特征樹。如圖3所示，一個(gè)三維CAD 模型的擴(kuò)展特征樹可以表示為Q（NQ，EQ，RQ）。其中：NQ為節(jié)點(diǎn)集合，EQ為邊的集合，RQ為樹的根節(jié)點(diǎn)。擴(kuò)展特征樹Q 具有以下功能：①通過樹的節(jié)點(diǎn)集合及其層次屬性刻畫設(shè)計(jì)特征模型中不同類型、不同粒度的設(shè)計(jì)特征；②通過樹的邊集合記錄設(shè)計(jì)特征間的依賴關(guān)系；③通過擴(kuò)展節(jié)點(diǎn)屬性、增加兄弟節(jié)點(diǎn)信息來記錄設(shè)計(jì)特征間的其他關(guān)聯(lián)關(guān)系。也就是說，擴(kuò)展特征樹完整地記錄了設(shè)計(jì)特征模型所包含的設(shè)計(jì)特征及其關(guān)聯(lián)信息。本文使用文獻(xiàn)［11］的方法構(gòu)建給定三維實(shí)體模型的擴(kuò)展特征樹，整體流程如圖4所示。

2.2 幾何屬性的獲取

盡管擴(kuò)展特征樹刻畫了模型內(nèi)的設(shè)計(jì)特征及其關(guān)系，但是缺少對(duì)模型幾何層面信息的表征。為準(zhǔn)確刻畫被表征模型，本文對(duì)擴(kuò)展特征樹中的每一個(gè)特征提取了特征尺寸和面數(shù)兩個(gè)幾何屬性。其中：特征尺寸刻畫對(duì)應(yīng)特征的大小信息，由對(duì)應(yīng)特征包圍盒的體積決定；面數(shù)則刻畫對(duì)應(yīng)特征的形狀復(fù)雜性，由對(duì)應(yīng)特征所包含面的數(shù)目決定。需要特別說明的是，本文利用ACIS幾何引擎中提供的api＿get＿entity＿box獲取對(duì)應(yīng)特征的包圍盒，并利用（長(zhǎng)×寬×高）計(jì)算包圍盒體積。作為示例，圖5顯示了三個(gè)包含不同非圓凸臺(tái)特征的實(shí)體模型，表1顯示了對(duì)應(yīng)特征的幾何屬性?？梢钥闯?，新增的尺寸和面數(shù)兩個(gè)屬性可以幫助人們更好地區(qū)分特征類型相同而幾何形狀不同的特征。

表1 圖5所示模型的幾何屬性

3 擴(kuò)展特征樹的相似評(píng)價(jià)

在得到三維CAD 模型擴(kuò)展特征樹的表征后，三維CAD 模型間的相似評(píng)價(jià)問題就轉(zhuǎn)換為擴(kuò)展特征樹間的相似匹配問題。具體地，擴(kuò)展特征樹的相似匹配應(yīng)遵循以下兩點(diǎn)：①查詢模型和目標(biāo)模型并不對(duì)等。所有相似比較均以查詢模型為出發(fā)點(diǎn)，當(dāng)目標(biāo)模型缺少查詢模型所包含的部分特征時(shí)，相似度減少；目標(biāo)模型若完全包含查詢模型中的所有特征，則即使還包含其他特征，相似度也為100%。這樣更加符合設(shè)計(jì)重用過程中的啟發(fā)式搜索及重用特點(diǎn)。②相似比較中，主體特征對(duì)相似度影響大，細(xì)節(jié)特征對(duì)相似度影響小?；谝陨嫌^點(diǎn)，下面分別給出精確求解樹Q 和T 間相似度的匹配方法，以及本文所采用的更加高效的匹配和相似評(píng)價(jià)方法。

3.1 精確的樹匹配和相似評(píng)價(jià)

精確求解樹Q 和樹T 間相似度的算法包括三步：①查找樹Q 和樹T 間的所有匹配方案；②計(jì)算每一個(gè)匹配方案的相似度；③計(jì)算樹Q 和樹T 的相似度。下面分別給出各步驟的詳細(xì)算法。

3.1.1 查找樹Q 和樹T 間的所有匹配方案

由檢索需求可知，樹Q 和樹T 間的匹配f 是樹Q 在樹T 中滿足以下兩個(gè)條件的嵌入［13］：

（1）保持父子關(guān)系，即對(duì)任何節(jié)點(diǎn)u 和v，（f（u），f（v））∈ET當(dāng)且僅當(dāng)（u，v）∈EQ。

（2）保持節(jié)點(diǎn)的層次屬性及粗層次的類型屬性，即對(duì)任何節(jié)點(diǎn)u∈NQ且f（u）∈NT，有depth（u）=depth（f（u））∧CoarseType（u）=CoarseType（f（u））。其中：函數(shù)depth（u）表示節(jié)點(diǎn)u 在特征樹中的深度值；CoarseType（u）表示節(jié)點(diǎn)u 的粗層次類型；“∧”表示“且”運(yùn)算。

基于上述定義，求解樹Q 和樹T 間所有匹配方案的算法步驟如下：

步驟1 利用樹嵌入的求解算法［13］獲得樹Q和樹T 之間的所有嵌入方案。

步驟2 以節(jié)點(diǎn)粗層次的類型和節(jié)點(diǎn)深度必須相同為限制條件，刪除部分不滿足要求的嵌入方案，獲得最終的匹配方案。

3.1.2 計(jì)算每一個(gè)匹配方案的相似度

給定樹Q 和樹T 之間的任一個(gè)匹配方案f，其相似度定義為該匹配方案中所有匹配樹上的節(jié)點(diǎn)對(duì)的相似度加權(quán)和

式中：w（u）為節(jié)點(diǎn)u的權(quán)重，表征節(jié)點(diǎn)對(duì)u 和f（u）間的相似度在整個(gè)相似評(píng)價(jià)中的權(quán)重；SimilarityOfNodePair（u，f（u））為節(jié)點(diǎn)對(duì)u，f（u）間的相似度。下面分別給出詳細(xì)的計(jì)算方法。

（1）節(jié)點(diǎn)權(quán)重的計(jì)算

由匹配方案f 的相似度計(jì)算公式（式（1））可知：對(duì)于給定的匹配方案f，設(shè)定不同的節(jié)點(diǎn)權(quán)重取值方案就會(huì)得到不同的相似度度量結(jié)果，合理權(quán)重的取值方案對(duì)獲得合理、準(zhǔn)確的相似度度量至關(guān)重要。分析CAD 模型檢索的特點(diǎn)，一個(gè)合理的權(quán)重取值方案應(yīng)遵循以下三條原則：

1）樹Q 中深度相同的子樹權(quán)重相等。設(shè)ST 為樹Q 中的一棵子樹，其權(quán)重w（ST）可以通過表達(dá)式計(jì)算。如果子樹ST1和ST2滿足depth（RST1）=depth（RST2），則w（ST1）=w（ST2）。這條原則旨在保證CAD 模型中兩個(gè)相同粒度的子區(qū)域在CAD 模型的相似度量中占有同等重要的地位。

2）對(duì)于任何子樹ST，其根節(jié)點(diǎn)在該子樹中占有的權(quán)重只與該子樹的高度有關(guān)，即子樹越高，根節(jié)點(diǎn)的權(quán)重越小。這條原則很容易理解，因?yàn)樽訕湓礁?，該區(qū)域包含的細(xì)節(jié)信息就越多，在整棵子樹權(quán)重一定的情況下，根節(jié)點(diǎn)占有的份量應(yīng)該越小。

根據(jù)以上三條原則，給定節(jié)點(diǎn)對(duì)u 和f（u），其相似度在整個(gè)匹配方案f 的相似度度量中的權(quán)重w（u）可以通過以下步驟計(jì)算：

步驟1 令子樹CT=樹Q，則有w（CT）=1。

步驟2 計(jì)算子樹CT 的根節(jié)點(diǎn)RCT的權(quán)重，有w（RCT）=w（CT）×γ。其中γ 是子樹CT 的根節(jié)點(diǎn)在該子樹中的權(quán)重因子，由子樹CT 的高度值決定，具體的取值可根據(jù)需要給定。本文中γ=0.5+0.5×0.6（h-1），h取樹的高度。當(dāng)h=1時(shí)，γ=1.0；h=2時(shí)，γ=0.8；h=3時(shí)，γ=0.68；γ 的值隨h 的增加而減小，且永遠(yuǎn)大于0.5，符合擴(kuò)展特征樹匹配的要求。

步驟3 計(jì)算子樹CT 的子孤立真子樹STi的權(quán)重，有（RCT），其中Nc（RCT）為子樹CT 的子孤立真子樹的數(shù)目。將CT 的子孤立子真子樹STi依次入棧Un-SolvedSubtree。

步驟4 如果UnSolvedSubtree 非空，則令CT=POP（UnSolvedSubtree），重復(fù)步驟2和步驟3，計(jì)算其根節(jié)點(diǎn)及其子孤立真子樹的權(quán)重；否則，如果UnSolvedSubtree 為空，則算法結(jié)束，樹Q 和樹T 匹配方案f 中每一個(gè)匹配上的節(jié)點(diǎn)對(duì)u 和f（u）的權(quán)重都已獲得。

（2）節(jié)點(diǎn)對(duì)相似度的計(jì)算

節(jié)點(diǎn)對(duì)u，f（u）間的相似度由節(jié)點(diǎn)對(duì)u，f（u）兄弟關(guān)系的相似程度、特征類型的相似程度及其幾何屬性的相似程度三部分決定，具體計(jì)算方法如下：

式中：Ns（u）和Ns（f（u））分別為節(jié)點(diǎn)u 和節(jié)點(diǎn)f（u）兄弟關(guān)系的數(shù)目；St（u，f（u））為節(jié)點(diǎn)u和節(jié)點(diǎn)f（u）特征類型間的相似度；wr，wn，α和β 分別為特征間關(guān)系的相似度、特征類型的相似度、特征體積的相似度以及特征面數(shù)的相似度在節(jié)點(diǎn)相似度中的權(quán)重，可以根據(jù)不同的檢索需求設(shè)置相應(yīng)的值。

將匹配上的節(jié)點(diǎn)對(duì)的權(quán)重及其相似度代入匹配方案f 的相似評(píng)價(jià)公式（式（1）），就可以獲得匹配方案f 的相似度。

3.1.3 計(jì)算樹Q 和樹T 的相似度

樹Q 和樹T 的相似度被定義為所有匹配方案對(duì)應(yīng)相似度的最大值，即

相應(yīng)地，樹Q 和樹T 間的最終匹配方案被定義為它們之間擁有最大相似度的匹配方案f。

3.2 改進(jìn)的樹匹配和相似評(píng)價(jià)

上述精確的樹匹配和相似評(píng)價(jià)方案能夠保證獲得樹Q 和樹T 間的最佳匹配方案及最大相似度，且匹配過程非常清晰、易于理解。但是，因?yàn)樵撈ヅ浞桨感枰ㄟ^窮舉并比較樹Q 和樹T 間的所有匹配方案來獲得最終匹配方案及相似評(píng)價(jià)結(jié)果，所以計(jì)算復(fù)雜度高，難以保證檢索效率。為此，本文對(duì)該匹配方案進(jìn)行改進(jìn)，提出一種自頂向下逐層尋找局部最優(yōu)匹配的方法，獲得樹Q 和樹T 間的最終匹配方案及相似度，從而減小檢索代價(jià)。具體步驟如下：

步驟1 判斷樹T 中是否存在樹Q 的嵌入。具體地，可以依據(jù)文獻(xiàn)［13］中介紹的樹嵌入求解算法加以判斷。

步驟2 如果樹T 中存在樹Q 嵌入，則通過以下步驟獲得最終匹配方案及其對(duì)應(yīng)的相似度量；否則，不匹配。

（1）取樹Q 與樹T 的根節(jié)點(diǎn)，并依據(jù)最優(yōu)二部圖求解算法［14］獲得樹Q 和樹T 根節(jié)點(diǎn)間的最優(yōu)匹配方案，將最優(yōu)匹配對(duì)放入匹配堆棧Sm中。這里的最優(yōu)匹配方案為對(duì)應(yīng)最大相似度的匹配方案，相似度則為利用式（2）計(jì)算各個(gè)節(jié)點(diǎn)間相似度后的累加和。

（2）如果Sm不為空，則取出Sm中的一組匹配節(jié)點(diǎn)（v，v′），將其加入最終匹配方案隊(duì)列Lfm中，取其孩子節(jié)點(diǎn)集合并按最優(yōu)二部圖求解算法［14］求解其孩子節(jié)點(diǎn)間的最優(yōu)匹配方案，將所有匹配節(jié)點(diǎn)對(duì)一一入棧；如果Sm為空，則匹配結(jié)束。最終匹配隊(duì)列Lfm記錄了最終匹配方案f，將該匹配方案f 代入式（1），可獲得樹Q 和樹T 間的最終相似度量。

雖然在理論上上述算法無法保證獲得樹Q 和樹T 間的最優(yōu)匹配方案，但由于在特征樹中上層特征在匹配中的作用遠(yuǎn)遠(yuǎn)大于下層特征，通常情況下，該匹配算法獲得的匹配方案就是最優(yōu)匹配方案；同時(shí)這種自頂向下的匹配方法避免了窮舉付出的時(shí)間代價(jià)，大大改善了匹配效率。

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

4.1 算法綜合性能分析

針對(duì)三維模型的形狀描述符及相似評(píng)價(jià)，學(xué)者們提出了一系列評(píng)價(jià)標(biāo)準(zhǔn)，包括廣泛性、唯一性、穩(wěn)定性、敏感性、高效性、層次性和局部性。以此為基礎(chǔ)，對(duì)本文所提算法進(jìn)行綜合評(píng)價(jià)，如表2所示。

表2 基于擴(kuò)展特征樹的CAD模型相似評(píng)價(jià)算法綜合性能分析

（1）廣泛性

即形狀描述符能夠描述所有類型的模型。本文的擴(kuò)展特征樹表征方式并未對(duì)被表征模型做任何限定，能夠表征所有B-rep表示的三維CAD 模型，適用于CAD 模型檢索領(lǐng)域。

（2）唯一性

即在形狀和形狀描述符間存在一一對(duì)應(yīng)的映射關(guān)系，包含兩層含義：①如果兩個(gè)形狀相同，則其對(duì)應(yīng)的形狀描述符相同；②如果兩個(gè)形狀描述相同，則其對(duì)應(yīng)的形狀相同。

本文算法滿足含義①，如果兩個(gè)三維CAD 模型的B-rep表示相同，則其所對(duì)應(yīng)的擴(kuò)展特征樹也相同。忽略人工理解的差異，假定在給出三維CAD模型設(shè)計(jì)特征的明確定義后，三維CAD 模型設(shè)計(jì)特征的交互定義具有唯一性，則給定兩個(gè)三維CAD模型，如果相同，則其所對(duì)應(yīng)的設(shè)計(jì)特征集合相同，根據(jù)擴(kuò)展特征樹的構(gòu)建算法可知相同特征間的關(guān)系也相同，故其對(duì)應(yīng)的擴(kuò)展特征樹相同，且該算法產(chǎn)生的形狀描述符對(duì)模型的平移、旋轉(zhuǎn)、縮放具有不變性。

對(duì)于含義②，本文算法并不完全滿足，如圖6所示：①當(dāng)模型A 被模型B 完全包含時(shí)，模型A 到模型B的相似度為1，但是模型B 和模型A 并不相同；②當(dāng)模型A 和模型C擁有相同的特征集合和特征結(jié)構(gòu)、僅是其特征所在位置不同時(shí)，本文算法無法有效區(qū)分其差異性；③當(dāng)模型A 和模型D 擁有相同的特征集合和特征結(jié)構(gòu)，其特征尺寸和特征面的數(shù)目也完全一致但特征本身形狀不同時(shí)，本文算法也無法有效區(qū)分其差異性。但是，針對(duì)設(shè)計(jì)階段的重用，以上情況均可通過修改其中一個(gè)模型較容易地生成另一個(gè)模型，即這種差異性并不影響其設(shè)計(jì)重用價(jià)值，因此該算法在以設(shè)計(jì)重用為目標(biāo)的檢索中仍是合理、可行的。

（3）穩(wěn)定性

即三維CAD 模型B-rep表示中的小改動(dòng)不會(huì)造成相應(yīng)設(shè)計(jì)特征模型的大改變。給定兩三維CAD 模型，如果它們之間存在小的差異，則其對(duì)應(yīng)的設(shè)計(jì)特征集合中會(huì)存在一些不同的局部形狀特征，根據(jù)擴(kuò)展特征樹的構(gòu)建過程可知，這些不同的設(shè)計(jì)特征對(duì)應(yīng)的特征間關(guān)系也會(huì)有所不同，但是其他特征及特征間的關(guān)系仍然相同，體現(xiàn)在擴(kuò)展特征樹中則是：兩模型對(duì)應(yīng)擴(kuò)展特征樹間的公共子樹與其各自的擴(kuò)展特征樹間的差異都很小，即設(shè)計(jì)特征模型間的差異較小。

（4）敏感性

即能夠檢測(cè)出不同物體之間的細(xì)微差別。本文所采用的擴(kuò)展特征樹通過深層次的葉子節(jié)點(diǎn)記錄了模型內(nèi)部小的設(shè)計(jì)特征，而相同深度、類型特征節(jié)點(diǎn)之間，本文又增加了特征“尺寸”和“面數(shù)”兩個(gè)屬性來進(jìn)一步區(qū)分，因此本文算法具有一定的敏感性，能夠較好地區(qū)分模型之間的細(xì)微差別。

（5）高效性

即能夠高效地計(jì)算和比較三維模型的形狀描述符。由于在三維模型的檢索中，只有查詢模型的描述符需要在線提取，其他描述符都可以離線提取，而比較則需要對(duì)庫(kù)內(nèi)每個(gè)模型在線進(jìn)行一次。因此，比較算法的時(shí)間復(fù)雜度對(duì)檢索性能的影響更大。本文擴(kuò)展特征樹構(gòu)建算法的復(fù)雜度為特征數(shù)目的多項(xiàng)式時(shí)間，而樹匹配算法的復(fù)雜度也為多項(xiàng)式時(shí)間，詳細(xì)分析如下。

為了方便評(píng)價(jià)匹配和相似所需時(shí)間，假定參與匹配的樹均為包含p 個(gè)節(jié)點(diǎn)的q 叉樹，即樹中除葉節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)都有q個(gè)孩子；同時(shí)假定樹中包含了t個(gè)非葉節(jié)點(diǎn)，則有p=tq+1。完成一次兩樹間的匹配和相似度度量所需時(shí)間包括以下兩部分：

1）判斷樹T 中是否存在與樹Q 匹配的子樹的復(fù)雜度 由文獻(xiàn)［13］可知求解樹嵌入的算法復(fù)雜度為線性的，即對(duì)于包含p 個(gè)節(jié)點(diǎn)的子樹，所需時(shí)間為o（p）［13］。

2）確定匹配方案和相似度量的復(fù)雜度 如果不存在嵌入，則復(fù)雜度為0；否則，復(fù)雜度計(jì)算如下：根節(jié)點(diǎn)的匹配時(shí)間為常數(shù)1；給定節(jié)點(diǎn)對(duì)孩子節(jié)點(diǎn)間的匹配方案由最優(yōu)二部圖求解算法確定，而最優(yōu)二部圖求解算法的復(fù)雜度為o（n3），故給定節(jié)點(diǎn)對(duì)孩子節(jié)點(diǎn)間的匹配時(shí)間為o（q3），則兩棵樹所需時(shí)間為1+t（o（q3））=1+o（tq3），又有p=tq+1，故兩樹匹配方案及相似度所需時(shí)間為o（p3）。由以上兩步計(jì)算可知，一次完整的匹配和相似評(píng)價(jià)所需時(shí)間為o（p）+o（p3），即復(fù)雜度為o（p3），匹配效率較高。

（6）層次性

能夠建立具有層次性質(zhì)的形狀描述符。顯然，基于擴(kuò)展特征樹的表征方式本身就是一種層次性的描述方式，因此能夠較好地平衡穩(wěn)定性及敏感性的雙重要求。

（7）局部性

能夠?qū)δＰ途植啃畔⑦M(jìn)行表征和比較。顯然，擴(kuò)展特征樹中的每一個(gè)子樹都對(duì)應(yīng)了模型的一個(gè)局部區(qū)域，因此本文方法具有局部表征能力。

綜上所述，基于擴(kuò)展特征樹匹配的三維CAD 模型相似評(píng)價(jià)算法綜合性能良好，適用于CAD模型，具有唯一性、穩(wěn)定性、敏感性、層次性和局部性，能夠在多項(xiàng)式時(shí)間內(nèi)完成相似評(píng)價(jià)，且匹配效率較高。

4.2 實(shí)驗(yàn)與分析

下面驗(yàn)證本文算法。實(shí)驗(yàn)環(huán)境如下：在Pentium4 1.6GHz CPU，2GB 內(nèi)存的PC 機(jī)上，以Microsoft Visual Studio 2003為集成開發(fā)環(huán)境，ACIS 13.0為幾何造型平臺(tái)，設(shè)wr=0.4，wn=0.6，α=β=0.5。

實(shí)驗(yàn)1 兩個(gè)三維CAD 模型的比較。

圖7所示為兩個(gè)相比較的三維CAD 模型，并按照程序運(yùn)行情況給出了模型所對(duì)應(yīng)的擴(kuò)展特征樹。表3所示為擴(kuò)展特征樹中各個(gè)特征的詳細(xì)情況。采用本文算法計(jì)算這兩個(gè)模型間的相似度，可得：模型1到模型2的相似度為90%，模型2到模型1的相似度為100%。這里需要說明的是，模型1到模型2的相似度為90%是因?yàn)槟Ｐ?和模型2整體相似，但是模型1 中所要求的部分特征在模型2 中不存在；90%的相似度合理地體現(xiàn)了模型間的整體相似性，同時(shí)也捕捉到了彼此之間的差別；而模型2到模型1的相似度為100%是因?yàn)槟Ｐ?包含模型2中的所有特征且?guī)缀螌傩韵嗤?，滿足啟發(fā)式檢索需求。

實(shí)驗(yàn)2 多個(gè)模型間的相似評(píng)價(jià)。

表4所示為5個(gè)不同的三維CAD 模型及其相似度。實(shí)驗(yàn)結(jié)果表明本文的相似評(píng)價(jià)算法具有如下特點(diǎn)：①一致性，模型與自身的相似度為100%，同時(shí)模型與完整包含其特征信息的模型間的相似度也為100%，與其他模型的相似度小于100%，符合設(shè)計(jì)重用階段檢索特征。②所計(jì)算的相似度不具有對(duì)稱性。例如模型A 到模型B的相似度為90%，而模型B到模型A 的相似度為100%。這反映了目標(biāo)模型對(duì)查詢模型所包含屬性的匹配程度，符合設(shè)計(jì)階段的啟發(fā)式檢索特征。③相似評(píng)價(jià)具有穩(wěn)定性，且計(jì)算結(jié)果較好地反映了模型設(shè)計(jì)中的特征及其關(guān)系的綜合信息。例如：模型A 和模型B 設(shè)計(jì)較為相似，它們間的相似度遠(yuǎn)遠(yuǎn)大于模型A 到模型C，D，E間的相似度；模型C 和模型D 非常相似，只是一些細(xì)節(jié)設(shè)計(jì)特征上稍有不同，它們之間的相似度也比較高。

表3 圖6中兩個(gè)三維CAD模型的特征信息

表4 一組三維CAD模型的相似度矩陣 %

實(shí)驗(yàn)3 檢索效果測(cè)試。

為進(jìn)一步驗(yàn)證算法的檢索效果，本文以Solid-Works 2007為工具，以ESB 模型庫(kù)為源，建立了一個(gè)包含801個(gè)邊界表示模型、42 個(gè)類的模型庫(kù)，并基于該測(cè)試庫(kù)構(gòu)建檢索結(jié)果的PR 曲線。具體地，分別以三維形狀分布［1］（3D Shape Distribution，3DS）、光場(chǎng)描述子［3］（Light Field Descriptors，LFD）及本文所提的擴(kuò)展特征樹（Extended Feature Tree，EFT）三種不同檢索方法作為測(cè)試對(duì)象；以ESB模型庫(kù)及其平薄壁組件（flat thin walled components）子模型庫(kù)、箱體零件（prismatic parts）子模型庫(kù)、回轉(zhuǎn)體零件（solids of revolution）三個(gè)子模型庫(kù)為測(cè)試庫(kù)。圖8所示為各種算法在相應(yīng)測(cè)試庫(kù)下的檢索PR 曲線，可以看出：①針對(duì)整體測(cè)試庫(kù)，EST 算法檢索效果明顯優(yōu)于3DS，與LFD 相當(dāng)；②針對(duì)箱體零件和回轉(zhuǎn)體零件子模型庫(kù)，EST 算法檢索效果略優(yōu)于LFD 算法；③針對(duì)平薄壁組件，EST算法效果較差，低于LFD 算法和3DS 算法。分析各子模型庫(kù)內(nèi)模型可知：①平薄壁組件子模型庫(kù)中包含的各模型為薄壁件，特征關(guān)系較為簡(jiǎn)單，但是單個(gè)特征往往比較復(fù)雜，而EST 算法能夠更好地捕捉特征間的關(guān)系，但是對(duì)相同類型的單個(gè)特征描述能力有限，造成其檢索效果較差；②箱體類零件和回轉(zhuǎn)體零件內(nèi)各個(gè)特征相對(duì)規(guī)范，但其特征關(guān)系較為復(fù)雜，EST 算法能夠更好地表征這類模型，同時(shí)不受其子特征及特征幾何細(xì)節(jié)信息變化的影響，因此具有更好的檢索效果。

實(shí)驗(yàn)4 效率測(cè)試。

現(xiàn)有的零件庫(kù)規(guī)模較小，零件也比較簡(jiǎn)單，無法有效地測(cè)試算法效率，因此采用隨機(jī)生成擴(kuò)展特征樹的方法來測(cè)試本文算法的效率。實(shí)驗(yàn)中，為了測(cè)試樹的深度和節(jié)點(diǎn)數(shù)對(duì)匹配效率的影響，隨機(jī)生成深度為2，4，6，節(jié)點(diǎn)數(shù)為20，30，40直至90 的多個(gè)擴(kuò)展特征樹，并記錄匹配100次所需的時(shí)間。圖9所示為實(shí)驗(yàn)結(jié)果，其中三條曲線分別對(duì)應(yīng)深度為2，4，6的擴(kuò)展特征樹。實(shí)驗(yàn)結(jié)果表明：①相同深度的擴(kuò)展特征樹，其匹配時(shí)間與節(jié)點(diǎn)數(shù)目成多項(xiàng)式時(shí)間增長(zhǎng)的關(guān)系；②隨著樹深度的增加，其匹配時(shí)間明顯下降。因?yàn)閷?shí)際零件中的特征數(shù)目一般在50個(gè)以內(nèi)，深度在4層左右，所以以①，②兩項(xiàng)觀察為依據(jù)，可推理出一個(gè)包含10 000 個(gè)模型的數(shù)據(jù)庫(kù)，其匹配時(shí)間不足半分鐘，即本文算法具有較高的匹配效率，能夠支持實(shí)時(shí)檢索的需要。

5 結(jié)束語

本文面向設(shè)計(jì)階段對(duì)三維CAD 模型的檢索及重用需求，針對(duì)三維CAD 模型的特點(diǎn)，提出了基于擴(kuò)展特征樹匹配的三維CAD 模型相似評(píng)價(jià)算法。利用擴(kuò)展特征樹刻畫三維CAD 模型內(nèi)的設(shè)計(jì)特征及其關(guān)聯(lián)關(guān)系，完整而有效地表征了三維CAD 模型的設(shè)計(jì)語義信息；非精確的樹匹配算法利用樹嵌入的思想及有效的權(quán)值分配方案確保相似評(píng)價(jià)的高效性和有效性，符合設(shè)計(jì)階段的啟發(fā)式檢索特征。經(jīng)過測(cè)試，效果符合預(yù)定目標(biāo)。

為進(jìn)一步提高三維CAD 模型的檢索效率，下一步工作將考慮引入合理的聚類算法，實(shí)現(xiàn)對(duì)庫(kù)內(nèi)模型的預(yù)先劃分，以更加快速、準(zhǔn)確地定位可重用模型。

［1］OSADA R，F(xiàn)UNKHOUSER T，CHAZELLE B，et al.Shape distributions［J］.ACM Transactions on Graphics，2002，21（4）：807-832.

［2］ZHANG Ruzhen，WANG Wan，ZHOU Xionghui.Three-dimensional model similarity based on improved shape distribution algorithm［J］.Computer Integrated Manufacturing Systems，2007，13（10）：1928-1933（in Chinese）.［張汝珍，王 婉，周雄輝.基于形狀分布算法的三維模型相似性研究［J］.計(jì)算機(jī)集成制造系統(tǒng)，2007，13（10）：1928-1933.］

［3］CHEN D Y，TIAN X P，SHEN Y T，et al.On visual similarity based 3D model retrieval［J］.Computer Graphics Forum，2003，22（3）：223-232.

［4］BESPALOV D，REGLI W C，SHOKOUFANDEH A.Reeb graph based shape retrieval for CAD［C］／／Proceedings of ASME DETC 2003Computers and Information in Engineering.New York，N.Y.，USA：ASME，2003.

［5］TAO Songqiao，HUANG Zhengdong，ZHENG Tanguang.CAD model retrieval based on attributed adjacency graph matching［J］.Computer Integrated Manufacturing Systems，2011，17（4）：680-687（in Chinese）.［陶松橋，黃正東，鄭壇光.基于屬性鄰接圖匹配的三維CAD模型搜索方法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2011，17（4）：680-687.］

［6］PAN Xiang，ZHANG Sanyuan，ZHANG Yin，et al.3D Model retrieval based topology connection graph［J］.Chinese Journal of Computers，2004，27（9）：1250-1255（in Chinese）.［潘翔，張三元，張 引，等.一種基于拓?fù)溥B接圖的三維模型檢索方法［J］.計(jì)算機(jī)學(xué)報(bào)，2004，27（9）：1250-1255.］

［7］TSAI C Y，CHANG C A.A two-stage fuzzy approach to feature-based design retrieval［J］.Computers in Industry，2005，56（5）：493-505.

［8］SEE K Y，HEE J Y，GU K B，et al.Feature-based part similarity assessment method using convex decomposiiton［C］／／Proceedings of ASME DETC 2003Computers and Information in Engineering.New York，N.Y.，USA：ASME，2003.

［9］ANTONIO C，SATYANDRA K G，ABHIJIT D，et al.Machining feature-based similarity assessment algorithms for prismatic machined parts［J］.Computer-Aided Design，2006，38（9）：954-972.

［10］LI M，F(xiàn)UH J Y H，ZHANG Y F，et al.General and partial shape matching approaches on feature-based cad models to support efficient part retrieval［C］／／Proceedings of the 28th Computers and Information in Engineering Conference.New York，N.Y.，USA：ASME，2008：121-130.

［11］BAI Jing，ZHOU Guangping.Design reuse oriented construction of design feature models of engineering［J］.Journal of Computer-Aided Design &Computer Graphics，2011，23（4）：622-632（in Chinese）.［白 靜，周廣平.面向設(shè)計(jì)重用的工程零件設(shè)計(jì)特征模型構(gòu)建［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2011，23（4）：622-632.］

［12］BAI Jing，GAO Shuming，TANG Weihua，et al.Design reuse oriented partial retrieval of CAD models［J］.Computer-Aided Design，2010，42（12）：1069-1084.

［13］PEKKA K.Tree matching problems with applications to structured text database［D］.Helsinki，the Netherlands：the Netherlands University of Helsinki，1992.

［14］MUNKRES J.Algorithms for the assignment and transportation problems［J］.Journal of the Society for Industrial and Applied Mathematics，1957，5（1）：32-38.