基于子圖同構(gòu)的三維CAD 模型局部匹配探討

李倩

摘要：為了有效解決結(jié)構(gòu)匹配無(wú)法精確實(shí)施的問(wèn)題，該文將從子圖同構(gòu)原理出發(fā)對(duì)三維CAD模型局部結(jié)構(gòu)匹配算法進(jìn)行探索。在該算法中通過(guò)對(duì)CAD模型的B-Rep信息的提取，用以面作為節(jié)點(diǎn)的屬性連接圖將其展現(xiàn)出來(lái)。局部匹配過(guò)程中用子圖表示用戶輸入的局部結(jié)構(gòu)，用大圖表示帶匹配的整體CAD模型。這樣就可以通過(guò)尋找大圖中同構(gòu)子圖解決檢索局部結(jié)構(gòu)的問(wèn)題。根據(jù)CAD模型的面特征細(xì)分圖頂點(diǎn)，并利用已匹配點(diǎn)之間的臨界關(guān)系對(duì)搜索空間進(jìn)行動(dòng)態(tài)剪裁，這樣同構(gòu)匹配的迅速就會(huì)大大增加。

關(guān)鍵詞：子圖同構(gòu)；三維CAD模型；局部匹配

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）13-0179-02

現(xiàn)階段產(chǎn)品設(shè)計(jì)、產(chǎn)品制造、產(chǎn)品虛擬仿真等機(jī)械設(shè)計(jì)和制造環(huán)節(jié)中已經(jīng)廣泛運(yùn)用了三維建模軟件，這樣企業(yè)內(nèi)容的三維CAD模型數(shù)量就會(huì)迅速增加。設(shè)計(jì)人員在工作中常常需要參照企業(yè)已有模型進(jìn)行新產(chǎn)品設(shè)計(jì)，通過(guò)相似形設(shè)計(jì)或改型設(shè)計(jì)能夠有效帶動(dòng)設(shè)計(jì)效率的提升。然而，對(duì)于一些大型制造企業(yè)而言，由于具備龐大數(shù)量的CAD模型，怎樣讓設(shè)計(jì)人員從中找到所需要的模型就成為另一個(gè)必須解決的問(wèn)題，本文將嘗試通過(guò)三維模型檢索解決這個(gè)問(wèn)題。

1 CAD模型局部匹配總體思路

實(shí)際中，完全自動(dòng)識(shí)別出直接給定任意的兩個(gè)三維CAD模型相思局部結(jié)構(gòu)還存在一定難度，但是還沒有較好的方法能夠解決這個(gè)問(wèn)題，并且這樣的需求在實(shí)際應(yīng)用CAD領(lǐng)域還相對(duì)較少。相反設(shè)計(jì)人員在設(shè)計(jì)的過(guò)程中，往往非常關(guān)注零件上某一個(gè)局部結(jié)構(gòu)，進(jìn)而將具備該局部結(jié)構(gòu)零件從已有產(chǎn)品模型中各發(fā)掘出來(lái)，并依次為依據(jù)和參考。這樣設(shè)計(jì)人員就能夠檢索自己感興趣的局部結(jié)構(gòu)，一般通過(guò)以下兩種方式輸入：將已有CAD模型直接打開，然后拾取局部結(jié)構(gòu)的多個(gè)面；利用建模工具對(duì)局部結(jié)構(gòu)進(jìn)行完全自定義。

為了實(shí)現(xiàn)局部匹配的目標(biāo)，首先需要對(duì)屬性鄰接圖進(jìn)行設(shè)計(jì)，并對(duì)CAD模型中B-Rep信息進(jìn)行提取，這樣就能夠用一個(gè)屬性鄰接圖表示CAD模型。通過(guò)提取已經(jīng)輸入的局部結(jié)構(gòu)B-Rep信息，就能夠產(chǎn)生小屬性鄰接圖，該圖作為“子圖”。同時(shí)還應(yīng)當(dāng)提取待匹配的模型庫(kù)中的每一個(gè)整體三維CAD模型，這樣就能夠獲得一個(gè)大屬性鄰接圖，這樣通過(guò)在大圖中尋找子圖就能夠解決在整體三維CAD模型中檢索制定局部結(jié)構(gòu)的問(wèn)題。

2 構(gòu)建屬性鄰接圖

由于多媒體可視化模型具有較低的精度要求，所以通過(guò)三維網(wǎng)絡(luò)模型近似表示即可。但CAD具有較高的精度要求，所以在表示過(guò)程中通常運(yùn)用B-Rep模型。B-Rep模型中的一個(gè)三維CAD模型包括n各三維空間曲面，多條邊圍成每個(gè)曲面，每個(gè)頂點(diǎn)確定每條邊。通過(guò)對(duì)每個(gè)頂點(diǎn)、每條邊、每個(gè)曲面的精確描述，整個(gè)三維CAD模型就能夠準(zhǔn)確的反映出來(lái)。通過(guò)將三維CAD模型中B-Rep信息轉(zhuǎn)化為屬性鄰接圖，其中每一個(gè)模型的面都存在對(duì)應(yīng)圖頂點(diǎn)，頂點(diǎn)具有面的幾何屬性。頂點(diǎn)之間的關(guān)系反映與模型中的面之間的關(guān)系，共面、垂直、平行、供邊等是常見的關(guān)系。

3 局部匹配

1）圖同構(gòu)概述

看兩個(gè)圖之間是否存在一個(gè)映射是判斷兩個(gè)圖是否同構(gòu)的關(guān)鍵，這樣兩個(gè)圖之間對(duì)應(yīng)的不僅包括點(diǎn)還包括邊。當(dāng)前圖同構(gòu)問(wèn)題計(jì)算還較為復(fù)雜，但是已經(jīng)證明子圖同構(gòu)問(wèn)題是一個(gè)NP問(wèn)題，實(shí)際中包含四種求解方法，其中提出時(shí)間最長(zhǎng)、且應(yīng)用最廣泛的就是ullmann算法。由CAD模型轉(zhuǎn)換得到的一種特定的屬性鄰接圖是本文研究的對(duì)象，所以必須充分運(yùn)用CAD模型自身特征進(jìn)行子圖同構(gòu)匹配算法的設(shè)計(jì)，進(jìn)而推動(dòng)算法匹配效率的提升[1]。

2）子圖同構(gòu)匹配算法思路

為了達(dá)到降低搜索空間雜復(fù)程度的目的，應(yīng)當(dāng)通過(guò)先驗(yàn)知識(shí)的運(yùn)用盡可能增加M元素為0的個(gè)數(shù)，這樣就需要細(xì)分圖的頂點(diǎn)。實(shí)際當(dāng)中從一定規(guī)則出發(fā)將圖的頂點(diǎn)劃分為若干個(gè)子集就是頂點(diǎn)細(xì)分，在同構(gòu)中不可能匹配不同子集的頂點(diǎn)?？梢姴豢赡艿捻旤c(diǎn)對(duì)應(yīng)關(guān)系通過(guò)有效的定點(diǎn)細(xì)分，在一開始就能夠得到有效的排除。本文算法在細(xì)分圖的頂點(diǎn)時(shí)，主要考慮的是CAD模型的面的特征。CAD模型的面與CAD模型轉(zhuǎn)換得到的屬性鄰接圖頂點(diǎn)存在一一對(duì)應(yīng)的關(guān)系，因此在進(jìn)行頂點(diǎn)細(xì)分時(shí)可以運(yùn)用CAD模型面的特征。

3）算法分析

因?yàn)樽訄D同構(gòu)的本質(zhì)是NP完全問(wèn)題，所以相應(yīng)的都是復(fù)雜度高的求解算法，并且還具有算法性能不穩(wěn)定的弊端。為了實(shí)現(xiàn)提升匹配效率，本文從兩個(gè)方面進(jìn)行了優(yōu)化：首先在進(jìn)行細(xì)分圖頂點(diǎn)過(guò)程中充分的結(jié)合和考慮了CAD模型面的特征；在進(jìn)行快速的剪枝搜索中運(yùn)用已匹配上的頂點(diǎn)所組成的子圖對(duì)應(yīng)同構(gòu)這一原理。屬性鄰接圖是本文研究的對(duì)象，主要通過(guò)轉(zhuǎn)化三維CAD模型的面后獲得。應(yīng)當(dāng)以頂點(diǎn)對(duì)應(yīng)模型的面的類型和面的特征出發(fā)，細(xì)分圖頂點(diǎn)，這樣初始時(shí)矩陣元素等于0的數(shù)量就會(huì)增加，搜索空間復(fù)雜程度相應(yīng)的就會(huì)降低[2]。

4 試驗(yàn)及結(jié)果分析

為了在CAD模型局部檢索中驗(yàn)證本算法的效果，本文進(jìn)行了局部結(jié)構(gòu)庫(kù)和三維CAD模型庫(kù)的構(gòu)建。其中，三維CAD模型庫(kù)中包含四百多個(gè)典型CAD模型，例如箱類、軸類、盤類等，這些模型具有不同的復(fù)雜程度，所具備的面數(shù)也在幾個(gè)至幾百個(gè)之間。局部結(jié)構(gòu)庫(kù)中既包含由幾個(gè)面構(gòu)成的孔、槽，也包括由數(shù)十個(gè)面構(gòu)成的用戶自定義結(jié)構(gòu)，共囊括八十個(gè)典型結(jié)構(gòu)。本文針對(duì)該模型和局部結(jié)構(gòu)庫(kù)的試驗(yàn)包括三個(gè)方面。

實(shí)驗(yàn)一。當(dāng)待檢索局部結(jié)構(gòu)具有一定數(shù)量的面時(shí)，對(duì)待匹配的整體三維CAD模型的面數(shù)量進(jìn)行調(diào)整，對(duì)匹配所需時(shí)間進(jìn)行測(cè)量。研究整體三維CAD模型復(fù)雜度的增長(zhǎng)匹配時(shí)間帶來(lái)的影響是進(jìn)行這項(xiàng)實(shí)驗(yàn)的目的，根據(jù)圖1可知實(shí)驗(yàn)結(jié)果，其中整體三維CAD模型面的數(shù)量通過(guò)橫軸表示，匹配所需時(shí)間t通過(guò)縱軸表示。局部結(jié)構(gòu)面的個(gè)數(shù)、也就是圖頂點(diǎn)個(gè)數(shù)表示為m，根據(jù)圖1a可知如果整體三維CAD模型面數(shù)量控制在一定范圍內(nèi)，那么匹配時(shí)間t和面的數(shù)量之間體現(xiàn)為線性關(guān)系[3]。

實(shí)驗(yàn)二。當(dāng)待匹配整體三維CAD模型具有確定數(shù)量的面時(shí)，對(duì)檢索局部結(jié)構(gòu)的面數(shù)量記性調(diào)整，進(jìn)而測(cè)量匹配時(shí)間，研究局部結(jié)構(gòu)復(fù)雜度的增長(zhǎng)給匹配時(shí)間造成的影響是該項(xiàng)試驗(yàn)的目的。圖1a為實(shí)驗(yàn)結(jié)果，其中局部結(jié)構(gòu)面的數(shù)量由橫軸表示，匹配所需時(shí)間由縱軸表示。整體三維CAD模型面的個(gè)數(shù)也就是大圖頂點(diǎn)的個(gè)數(shù)由n表示。根據(jù)圖1b可知，如果三維CAD模型面的數(shù)量不超過(guò)200時(shí)，局部結(jié)構(gòu)復(fù)雜度和匹配時(shí)間存在線性關(guān)系。如果三維CAD模型面數(shù)量大于400時(shí)，局部結(jié)構(gòu)越復(fù)雜匹配時(shí)間增長(zhǎng)幅度越大[4]。

實(shí)驗(yàn)三。以試驗(yàn)一、二維基礎(chǔ)，對(duì)比試驗(yàn)最著名的Ullmann算法和本文算法，兩種算法的綜合性能比較如下。如圖1c、1d為試驗(yàn)結(jié)果，其中相同條件下Ullmann算法匹配時(shí)間與本文算法匹配時(shí)間的比表示為縱軸r。通過(guò)圖1a、1c可知，本算法和ullmann算法在n和m較小的情況下具有相同的效率，但是本算法在n和m較大的情況下具有比ullmann算法更高的效率。例如在m=40、n=400時(shí)，ullmann算法完成一次匹配使用的時(shí)間，本文算法能夠?qū)崿F(xiàn)三百次匹配[5]。

5 結(jié)論

本文中的支持局部匹配的三維CAD模型檢索算法，不同于基于統(tǒng)計(jì)特征提取的檢索算法，它首先用屬性鄰接圖替代CAD模型，然后用子圖同構(gòu)問(wèn)題替代局部結(jié)構(gòu)匹配問(wèn)題。在對(duì)子圖同構(gòu)匹配算法進(jìn)行設(shè)計(jì)時(shí)，首先根據(jù)CAD模型面的特征預(yù)先細(xì)分屬性鄰接圖的頂點(diǎn)，這樣初始搜索空間復(fù)雜度就會(huì)大幅降低。在進(jìn)行動(dòng)態(tài)搜索的過(guò)程中，應(yīng)當(dāng)以匹配上的頂點(diǎn)對(duì)組成的子圖應(yīng)對(duì)應(yīng)同構(gòu)這一原理出發(fā)，將不可能對(duì)應(yīng)關(guān)系盡早排除掉，搜索進(jìn)程就能夠大幅提升，最終達(dá)到提升匹配迅速的目的。根據(jù)實(shí)驗(yàn)結(jié)果可知，精確的局部結(jié)構(gòu)匹配能夠通過(guò)這種算法得到有效實(shí)現(xiàn)，同時(shí)實(shí)際檢索需求也能夠得到充分滿足。

參考文獻(xiàn)：

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

[2] 王成，張樹生，張開興等.基于回轉(zhuǎn)面歸并的CAD模型局部檢索算法[J].微處理機(jī)，2011，32（5）：53-57.

[3] 鄭壇光.三維CAD模型檢索技術(shù)研究[J].華中科技大學(xué)報(bào)2011，32（5）：3-7.

[4] 王洪申，張樹生，白曉亮等.三維CAD模型局部結(jié)構(gòu)檢索屬性圖算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2012，20（3）：316-320.

[5] 陶松橋.面向設(shè)計(jì)的三維CAD模型搜索技術(shù)研究[J].華中科技大學(xué)報(bào)，2012，20（3）：16-20.