陶松橋，郭順生

(1.武漢理工大學(xué) 機(jī)電工程學(xué)院，湖北 武漢 430070；2.武漢交通職業(yè)學(xué)院 機(jī)電工程學(xué)院，湖北 武漢 430065)

?

基于面屬性相似的CAD模型檢索方法

陶松橋1,2，郭順生1

(1.武漢理工大學(xué) 機(jī)電工程學(xué)院，湖北 武漢 430070；2.武漢交通職業(yè)學(xué)院 機(jī)電工程學(xué)院，湖北 武漢 430065)

針對(duì)現(xiàn)有基于面屬性圖需要應(yīng)用圖匹配或子圖匹配計(jì)算來實(shí)現(xiàn)CAD模型的形狀匹配，且其模型檢索方法存在檢索效率低下或檢索結(jié)果不夠準(zhǔn)確的問題，提出了一種基于面屬性相似的CAD模型檢索方法。在現(xiàn)有的模型面屬性基礎(chǔ)上，引入了包含較多屬性的面特征屬性和面幾何邊界特征屬性來表達(dá)CAD模型的形狀特征。特別是外環(huán)邊循環(huán)碼可以更詳細(xì)地表達(dá)模型的面幾何邊界特征屬性，只需要采用簡(jiǎn)單的模型面屬性相似性度量方法就能實(shí)現(xiàn)CAD模型的形狀檢索。實(shí)驗(yàn)結(jié)果表明，該方法能夠?qū)崿F(xiàn)CAD 模型的形狀檢索，其檢索效率和精準(zhǔn)程度能夠滿足實(shí)際需要，顯著提高了CAD模型面的形狀辨識(shí)能力。

面屬性圖; 外環(huán)邊循環(huán)碼；模型檢索；子圖匹配

由于CAD模型中蘊(yùn)含豐富的產(chǎn)品設(shè)計(jì)與制造知識(shí)，設(shè)計(jì)工程師可以使用CAD模型數(shù)據(jù)庫檢索到相似產(chǎn)品的CAD模型作為設(shè)計(jì)參考，激發(fā)新產(chǎn)品設(shè)計(jì)的靈感；制造工程師可以通過CAD模型檢索，查找到相關(guān)產(chǎn)品的生產(chǎn)工藝及生產(chǎn)供應(yīng)商。盡管CAD模型數(shù)量連續(xù)不斷地增長(zhǎng)，數(shù)以千計(jì)的CAD模型可以從公共和私人數(shù)據(jù)庫中免費(fèi)獲取，但設(shè)計(jì)和制造工程師面臨如何從這些CAD模型數(shù)據(jù)庫中檢索其所需要的CAD模型的問題[1]。

由于提取三維CAD 模型的邊界表示(boundary representative, B-rep)信息簡(jiǎn)單方便，并且現(xiàn)有的圖與子圖匹配算法可直接應(yīng)用于CAD模型的整體與局部匹配，故用面屬性圖描述CAD模型的形狀是一個(gè)自然而實(shí)用的選擇[2-6]。EI-MEHALAWI等[7]較早用面屬性圖描述 CAD模型的形狀，考慮包括面的幾何類型、邊的幾何類型及邊分別與X軸和Y軸的相對(duì)方位角等面屬性。陶松橋等[8]提出的面屬性圖考慮的面屬性包括面的幾何類型和凸性等,以及邊的幾何類型和凸性等。王飛等[9]提出的面屬性圖考慮的面屬性包括面的幾何類型、法矢、曲率、面積，以及共邊、平行、垂直和共面等面關(guān)系。高藝等[10]用典型面來描述CAD模型的形狀，典型面是同一功能類別的機(jī)械零件中出現(xiàn)頻率較高，具有一定功能和語義的面。面屬性圖描述CAD模型的優(yōu)點(diǎn)是生成過程計(jì)算簡(jiǎn)單，缺點(diǎn)是實(shí)現(xiàn)模型的形狀匹配還需要復(fù)雜的圖匹配或子圖匹配計(jì)算。當(dāng)模型形狀比較復(fù)雜時(shí)，由于模型的面數(shù)量很多，導(dǎo)致面屬性圖的規(guī)模較大，其缺陷更加明顯。筆者在現(xiàn)有的模型面屬性基礎(chǔ)上，引入了包含較多屬性的面特征屬性和面幾何邊界特征屬性來表達(dá)CAD模型的形狀特征。特別是引入的外環(huán)邊循環(huán)碼更詳細(xì)地表達(dá)了模型的面幾何邊界特征屬性，大大提高了用面屬性表達(dá)CAD模型形狀特征的辨識(shí)能力，只需采用簡(jiǎn)單的模型面屬性相似度度量方法就能實(shí)現(xiàn)CAD模型的形狀檢索。

1 面屬性編碼

由于編碼易于生成，進(jìn)行相似性度量比較方便，筆者用面屬性編碼表達(dá)CAD模型的面形狀特征。其中面屬性包括面特征屬性和面幾何邊界特征屬性?？紤]的面特征屬性包括：面的幾何類型(平面、圓柱面、圓錐面和球面等)、相對(duì)面積(該面面積與總表面積的比值)、環(huán)數(shù)(內(nèi)環(huán)數(shù)和外環(huán)數(shù)的和)、面的凸性(凸面、平面和凹面等)[11]和外環(huán)中邊數(shù)。由于實(shí)體模型的面幾何邊界可能由外環(huán)和內(nèi)環(huán)組成，一個(gè)面的內(nèi)環(huán)邊界最終是另一個(gè)面的外環(huán)邊界或外環(huán)邊界的一部分，這里的面幾何邊界僅考慮模型的外環(huán)邊界。引入的面幾何邊界特征值包括：外環(huán)邊的幾何類型(直線和圓弧等)、外環(huán)邊的相對(duì)長(zhǎng)度(外環(huán)邊的邊長(zhǎng)與外環(huán)總長(zhǎng)的比值)、外環(huán)邊起始角和終點(diǎn)角(外環(huán)邊在面上的夾角)，以及外環(huán)邊凸性(外環(huán)邊的中點(diǎn)處所連接的兩個(gè)面在體內(nèi)空間夾角的凹凸性)。

1.1 面特征屬性編碼計(jì)算方法

面特征屬性中的面幾何類型和凸性編碼都為一位十進(jìn)制整數(shù)，其編碼方法如下：用fT表示面的幾何類型編碼，如平面fT=0，圓柱面fT=1，圓錐面fT=2，球面fT=3，其他面fT=4。用fC表示面的凸性編碼，如平面fC=0，凸面fC=1，凹面fC=2，其他面fC=3。

1.2 面幾何邊界特征屬性編碼計(jì)算方法

面幾何邊界特征屬性中的外環(huán)邊幾何類型和凸性編碼都為一位十進(jìn)制整數(shù)，它們的編碼方法如下：用eT表示外環(huán)邊的幾何類型編碼，如直線邊eT=0，圓弧邊eT=1，其他邊eT=2。用eC表示外環(huán)邊的凸性編碼，如直線邊eC=0，凸邊eC=1，凹邊eC=2。用rL表示外環(huán)邊的相對(duì)長(zhǎng)度編碼，為兩位十進(jìn)制整數(shù)，其計(jì)算公式為：rL=(int)(100×relLength)，relLength為外環(huán)邊的相對(duì)長(zhǎng)度。

1.3 外環(huán)邊循環(huán)碼計(jì)算方法

采用單一的面特征屬性和面幾何邊界特征屬性對(duì)模型面進(jìn)行形狀辨識(shí)時(shí)，同樣存在著辨識(shí)能力不足的問題。另外，考慮到模型面的外環(huán)邊界由外環(huán)邊首尾連接形成了一個(gè)封閉區(qū)域，從任意一條外環(huán)邊的端點(diǎn)出發(fā)，沿逆時(shí)針方向遍歷邊界上的所有外環(huán)邊后，最終仍將回到起點(diǎn)。因此，筆者引入外環(huán)邊循環(huán)碼來更詳細(xì)地表達(dá)模型的面幾何邊界特征屬性，以提高模型面屬性的形狀辨識(shí)能力。外環(huán)邊循環(huán)碼計(jì)算方法如下：

(1)計(jì)算每一條外環(huán)邊的屬性編碼e。e的計(jì)算公式為：

e=eW-rL

(1)

式中:rL為外環(huán)邊的相對(duì)長(zhǎng)度編碼;符號(hào)“-”為編碼連接符;eW為兩位十進(jìn)制整數(shù)，其具體計(jì)算方法如下：

eW= 33×eT+ 32×eC+ 31×seC+ 30×eeC

(2)

式中：eT和eC分別為外環(huán)邊的幾何類型和凸性編碼；seC和eeC分別為外環(huán)邊起始角(startAngle)和外環(huán)邊終點(diǎn)角(endAngle)對(duì)應(yīng)的編碼。當(dāng)startAngle=180°時(shí)，seC=0；當(dāng)startAngle﹤180°時(shí)，seC=1；當(dāng)startAngle﹥180°時(shí)，seC=2。類似地，當(dāng)endAngle=180°時(shí)，eeC= 0；當(dāng)endAngle﹤180°時(shí)，eeC= 1；當(dāng)endAngle﹥180°時(shí)，eeC= 2。

(2)從任意一條外環(huán)邊出發(fā)，沿逆時(shí)針方向連接邊界上的所有外環(huán)邊編碼，形成外環(huán)邊編碼串。選擇不同的外環(huán)邊作為循環(huán)起點(diǎn)時(shí)，得到的外環(huán)邊編碼串不同。為了保證模型面的外環(huán)邊循環(huán)碼的唯一性，引入最大編碼串的概念。設(shè)編碼數(shù)組為e[0],e[1],…,e[n-1],n為外環(huán)邊數(shù)。第k條邊的編碼串eS[k]為：

eS[k]=e[k]-e[k+1]-…-

e[n-1]-e[0]-…-e[k-1]=

eW[k]-rL[k]-eW[k+1]-

rL[k+1]-…-eW[n-1]-rL[n-1]-

eW[0]-rL[0]-…-eW[k-1]-rL[k-1]

外環(huán)邊循環(huán)碼Cycle定義為最大編碼串:

Cycle= max {eS[k] |k=0,1,2,…,n-1}，即Cycle=e(e0)-e(e1)-…-e(en-1),e0為最大編碼串的起始邊。

以圖1中CAD模型的面f為例說明外環(huán)邊循環(huán)碼Cycle的計(jì)算過程。面f有4條外環(huán)邊e0,e1,e2和e3，其面幾何邊界特征屬性如表1所示。

圖1 面f及其4條外環(huán)邊示意圖

表1 模型面f的外環(huán)邊特征屬性

由表1和式(1)可知：

e[0]=04-01，e[1]=04-42，e[2]=04-17，e[3]=04-39。

編碼串為：

eS[0]=04-01-04-42-04-17-04-39;

eS[1]=04-42-04-17-04-39-04-01;

eS[2]=04-17-04-39-04-01-04-42;

eS[3]=04-39-04-01-04-42-04-17。

最大編碼串為eS[1]，因此面f的外環(huán)邊循環(huán)碼Cycle為04-42-04-17-04-39-04-01。

2 相似性度量

2.1 面特征屬性相似性度量

假設(shè)相比較面a和b的特征值向量分別為：

Va=(va1,va2,va3,va4,va5)

Vb=(vb1,vb2,vb3,vb4,vb5)

其中，vai和vbi(i=1,2,3,4,5)分別為相比較模型的面幾何類型編碼fT、凸性編碼fC、相對(duì)面積、環(huán)數(shù)和外環(huán)中邊數(shù)，則面a和b的特征值向量相似度SfV(a,b)為：

2.2 外環(huán)邊循環(huán)碼相似性度量

假設(shè)相比較面a和b的外環(huán)邊循環(huán)碼分別為Cyclea=(a1-r1-a2-r2-…-am-rm)和Cycleb=(b1-s1-b2-s2-…-bm-sm),這里a和b的值對(duì)應(yīng)于式(1)中的eW編碼,r和s對(duì)應(yīng)于式(1)中的rL編碼。將Cyclea和Cycleb分解為A=(a1,a2,…,am)，R=(r1,r2,…,rm)，B=(b1,b2,…,bn),S=(s1,s2,…,sn)，則面a和b的外環(huán)邊循環(huán)碼相似度Sfe(a,b)為：

2.3 面相似性度量

假設(shè)相比較面a和b的面特征屬性相似度和外環(huán)邊循環(huán)碼相似度分別為SfV(a,b)和Sfe(a,b)，則面a與b的相似度Sf(a,b)為：

Sf(a,b)=w1×SfV(a,b)+w2×Sfe(a,b)

(3)

式中,w1、w2為權(quán)值，w1≥0,w2≥0,w1+w2=1。

2.4 CAD模型相似性度量

假設(shè)相比較模型q和d的面數(shù)量分別為m和n，檢索模型q的第j個(gè)面與數(shù)據(jù)庫模型d的第k個(gè)面的相似度為Sf(fqj,fdk),則模型q和d的相似度S(q,d)為：

(4)

3 CAD模型檢索實(shí)驗(yàn)與分析

3.1 CAD模型檢索實(shí)驗(yàn)

為了驗(yàn)證所提出的基于面屬性相似的CAD模型檢索方法的有效性，筆者基于Visual C++,ACIS和HOOPS系統(tǒng)開發(fā)了一個(gè)CAD 模型檢索原型系統(tǒng)。實(shí)驗(yàn)所用微機(jī)配置為Intel 3.0 GHz的CPU和1.0 GB內(nèi)存，實(shí)驗(yàn)所用模型數(shù)據(jù)庫中絕大部分模型從美國(guó)普渡大學(xué)的ESB模型數(shù)據(jù)庫下載，包含420個(gè)ACIS格式的CAD模型。

在模型數(shù)據(jù)庫中，選擇了3個(gè)面數(shù)量分別為59、33和11的CAD模型進(jìn)行檢索效果和檢索效率測(cè)試，進(jìn)行局部檢索實(shí)驗(yàn)時(shí)選擇的模型面數(shù)量分別為9、11和11，相關(guān)實(shí)驗(yàn)結(jié)果如表2所示。選擇這兩個(gè)模型是因?yàn)榕c它們具有相似局部特征的CAD模型在模型數(shù)據(jù)庫中較多，能夠充分地反映所提方法的特點(diǎn)。在表2中，模型本身的顏色是淺色，待檢索模型中用于局部檢索的形狀特征用淺灰色標(biāo)記，檢索結(jié)果返回的相關(guān)數(shù)據(jù)庫模型中被成功匹配的面用深灰色標(biāo)記。檢索結(jié)果模型下面的數(shù)字由式(4)計(jì)算得到，相似度數(shù)值越小，說明兩個(gè)相比較模型越相似，相似度為0，表示兩個(gè)模型完全匹配。表2中所列出的時(shí)間沒有包含面屬性編碼和外環(huán)邊循環(huán)碼的生成時(shí)間，僅為待檢索模型與數(shù)據(jù)庫所有模型的面相似度計(jì)算時(shí)間。面屬性編碼、外環(huán)邊循環(huán)碼及其他面屬性在模型檢索前的離線階段批量生成，以記事本的形式保存在模型描述子數(shù)據(jù)庫中，檢索時(shí)直接從描述子數(shù)據(jù)庫中讀取。另外，為了進(jìn)一步說明該方法的有效性，在表2中同時(shí)列出了文獻(xiàn)[9]的實(shí)驗(yàn)結(jié)果，以便進(jìn)行對(duì)照比較。

3.2 實(shí)驗(yàn)結(jié)果分析與計(jì)算方法處理

假設(shè)待檢索模型q用于檢索的局部特征包含的面數(shù)量、邊數(shù)量及外環(huán)邊數(shù)量分別為m、a和k，數(shù)據(jù)庫模型d的面數(shù)量、邊數(shù)量及外環(huán)邊數(shù)量分別為n、b和l。筆者方法中模型檢索時(shí)的面相似度計(jì)算復(fù)雜度是max(m×n×k×l，m×n×5×5)，而現(xiàn)有的面屬性圖匹配方法大多與文獻(xiàn)[9]方法類似，一般要求相比較模型的面和邊分別匹配，模型檢索時(shí)面匹配的計(jì)算復(fù)雜度一般不低于m×n×a×b。明顯地，max(m×n×k×l，m×n×5×5)一般遠(yuǎn)小于m×n×a×b。因此，筆者方法與文獻(xiàn)[9]相比，模型檢索效率具有較大的優(yōu)勢(shì)，表2中的實(shí)驗(yàn)結(jié)果也驗(yàn)證了該結(jié)論。

表2 CAD模型檢索實(shí)驗(yàn)結(jié)果

為了提高模型檢索的效率，在模型面相似度計(jì)算時(shí)設(shè)置了過濾措施和閾值，如相比較面的面幾何類型不同或凸性不同，就直接認(rèn)為它們不匹配，將相似度設(shè)為1；如相比較面的面特征屬性或外環(huán)邊循環(huán)碼相似度計(jì)算結(jié)果大于閾值，就直接認(rèn)為這兩個(gè)面不匹配；如待檢索模型中有一個(gè)面在相比較的數(shù)據(jù)模型中找不到相匹配的面，就直接認(rèn)為這兩個(gè)相比較模型不匹配。

如果相比較的檢索模型和數(shù)據(jù)庫模型中面的外環(huán)邊數(shù)量越多或外環(huán)邊的類型越豐富，通過外環(huán)邊循環(huán)碼相似度計(jì)算篩選掉的面越多，導(dǎo)致模型面的形狀辨識(shí)能力越強(qiáng)。因此，筆者方法可以通過靈活地設(shè)置式(3)中權(quán)值w1和w2，得到不同精度的檢索結(jié)果，以滿足不同用戶的不同檢索需求。對(duì)于處于產(chǎn)品設(shè)計(jì)初始階段，不具備模型詳細(xì)信息的用戶，可以通過設(shè)定較小的權(quán)值w1，查找到數(shù)量較多的、與檢索模型具有不同相似程度的模型作為設(shè)計(jì)參考；對(duì)于擁有精確模型結(jié)構(gòu)的用戶，則可以通過設(shè)定較大的權(quán)值w1，快速地定位某個(gè)模型。

4 結(jié)論

筆者提出的基于面屬性相似的CAD模型檢索方法，通過引入外環(huán)邊循環(huán)碼顯著改善了模型面的形狀辨識(shí)能力，避免了使用圖匹配或子圖匹配來實(shí)現(xiàn)模型的形狀檢索。盡管該方法中CAD模型描述符的生成及編碼的計(jì)算需要一定的時(shí)間，但是它們是在檢索前的離線階段批量生成，類似于大規(guī)模模型庫檢索時(shí)建立的索引體系。實(shí)驗(yàn)結(jié)果表明，該方法能夠?qū)崿F(xiàn)CAD 模型的形狀檢索，檢索效率和精準(zhǔn)程度能夠滿足實(shí)際需要。

[1] GUNN T G. The mechanization of design and manufacturing[J]. Scientific American, 1982,247(3):86-108.

[2] TAO S Q, HUANG Z D, ZUO B Q, et al. Partial retrieval of CAD models based on the gradient flows in Lie group[J]. Pattern Recognition, 2012,45(4):1721-1738.

[3] TAO S Q, HUANG Z D, MA L J, et al. Partial retrieval of CAD models based on local surface region decomposition[J]. Computer-Aided Design, 2013,45(11):1239-1252.

[4] TAO S Q. General and partial retrieval of CAD models based on surface region partition [J]. Computer-Aided Design and Applications, 2014,46(1):32-42.

[5] 陶松橋,郭順生.基于面上下文碼匹配的CAD模型檢索方法[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(3):1-5.

[6] 陶松橋,黃正東,馬露杰.基于區(qū)域特征分割的CAD模型局部搜索方法[J].中國(guó)機(jī)械工程, 2013,24(12):1611-1615.

[7] EL-MEHALAWI M, ALLEN M R. A database system of mechanical components based on geometric and topological similarity, part I: representation[J]. Computer-Aided Design, 2003,35(1):95-105.

[8] 陶松橋,黃正東,鄭壇光.基于屬性鄰接圖匹配的三維CAD模型搜索方法[J].計(jì)算機(jī)集成制造系統(tǒng),2011,17(4):680 -687.

[9] 王飛,張樹生,白曉亮,等.基于子圖同構(gòu)的三維CAD模型局部匹配[J].計(jì)算機(jī)輔設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2008,20(8):1078-1084.

[10] 高藝,王斌,胡楷模,等.基于典型面匹配的機(jī)械零件檢索方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2011(4):640-648.

[11] 陶松橋,王書亭,鄭壇光,等.基于非精確圖匹配的CAD模型搜索方法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2010(3):545-552.

TAO Songqiao:Post Doctor; School of Mechanical and Electronic Engineering, WUT, Wuhan 430070, China.

[編輯：王志全]

CAD Models Retrieval Based on the Similarity of Face Attributes

TAOSongqiao,GUOShunsheng

A CAD model retrieval method based on the similarity of face attributes was presented in order to resolve the problem that graph matching or sub-graph matching realizing the CAD model retrieval based on face attribute graph may not be effective and efficient enough. Based on the existing representations for face attributes, the face attributes and geometry boundary attributes were introduced to represent the shape of CAD models. In particular, cycle code of the outer edges was adopted to describe the shape of CAD models in detail, which greatly increased the resolution of the face shape. Thus, the similar evaluations between the compared models were used for realizing the CAD model retrieval instead of graph matching or sub-graph matching. Experimental results show that this method is able to support CAD model retrieval and its efficiency and effect meets the requirement of practical applications.

face attribute graph; cycle code of the outer edges; model retrieval; sub-graph matching

2015-03-21.

陶松橋(1973-)，男，湖北孝感人，武漢理工大學(xué)機(jī)電工程學(xué)院博士后.

國(guó)家自然科學(xué)基金資助項(xiàng)目(51475186);湖北省教育廳科研基金資助項(xiàng)目(B2013229).

2095-3852(2015)05-0537-05

A

TP391

10.3963/j.issn.2095-3852.2015.05.003