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

陶松橋，郭順生

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

?

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

陶松橋1,2，郭順生1

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

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

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

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

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

1 面屬性編碼

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

1.1 面特征屬性編碼計算方法

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

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

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

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

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

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

e=eW-rL

(1)

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

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

(2)

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

(2)從任意一條外環(huán)邊出發(fā)，沿逆時針方向連接邊界上的所有外環(huán)邊編碼，形成外環(huán)邊編碼串。選擇不同的外環(huán)邊作為循環(huán)起點時，得到的外環(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的計算過程。面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、相對面積、環(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的值對應于式(1)中的eW編碼,r和s對應于式(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個面與數(shù)據(jù)庫模型d的第k個面的相似度為Sf(fqj,fdk),則模型q和d的相似度S(q,d)為：

(4)

3 CAD模型檢索實驗與分析

3.1 CAD模型檢索實驗

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

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

3.2 實驗結(jié)果分析與計算方法處理

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

表2 CAD模型檢索實驗結(jié)果

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

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

4 結(jié)論

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

[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].計算機工程與應用,2014,50(3):1-5.

[6] 陶松橋,黃正東,馬露杰.基于區(qū)域特征分割的CAD模型局部搜索方法[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].計算機集成制造系統(tǒng),2011,17(4):680 -687.

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

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

[11] 陶松橋,王書亭,鄭壇光,等.基于非精確圖匹配的CAD模型搜索方法[J].計算機輔助設(shè)計與圖形學學報,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-)，男，湖北孝感人，武漢理工大學機電工程學院博士后.

國家自然科學基金資助項目(51475186);湖北省教育廳科研基金資助項目(B2013229).

2095-3852(2015)05-0537-05

A

TP391

10.3963/j.issn.2095-3852.2015.05.003