吳 強 謝麗萍 董 雁

紹興文理學(xué)院，紹興，312000

0 引言

目前，工程圖紙檢索主要是基于文本的檢索，它充分利用了幾何圖元的屬性和這些圖元之間的空間關(guān)系。Berchtold等［1］開發(fā)的S3系統(tǒng)是一個支持局部相似性檢索和基于文本的圖紙檢索系統(tǒng)。S3系統(tǒng)檢索主要依靠圖形輪廓的匹配，而忽略了空間關(guān)系，使得此檢索方法不適合于復(fù)雜的圖形。Müller等［2］提出了一種新的隨機模型的檢索方法，使用的是偽二維隱馬爾可夫模型（P2DHMM），此方法僅支持簡單的圖形檢索，不適合于大量的圖形。Park等［3］提出了一種基于關(guān)鍵形狀特征的復(fù)雜二維機械零件圖檢索方法，但該方法很難用于處理大量的工程圖紙。

工程圖紙檢索的關(guān)鍵是如何迅速、準(zhǔn)確地完成相似度計算，而相似度計算與圖紙?zhí)卣鞯奶崛∶?切相 關(guān)［4－6］。 Wang 等［7］基 于 圖 匹 配 的 方 法 對零件圖的檢索進(jìn)行了研究，其方法是，首先提取圖形的結(jié)構(gòu)和形狀的特征，然后將圖形匹配問題轉(zhuǎn)換為圖和子圖同構(gòu)問題。子圖同構(gòu)問題被證明是一個NP完全問題，現(xiàn)有解決方案中的算法不僅時間復(fù)雜度相當(dāng)高，且算法的性能不穩(wěn)定。Wang等［7］提出了一種近似圖形匹配方法，即基于任務(wù)嵌套分配的圖形相似性匹配算法。該方法分為兩個步 驟：首 先，使 用 EMD（earth mover’s distance）算法計算頂點之間的距離矩陣，然后根據(jù)距離矩陣使用EMD算法得到頂點間映射匹配矩陣。實驗表明，該方法可以檢索不同相似程度的圖紙，并且搜索精度和搜索的效率滿足實際應(yīng)用的要求。該方法不足之處在于其計算比較粗略。

徐靜等［8］和董雁等［9］提出了一種基于結(jié)構(gòu)相似的零件工程圖檢索方法。該方法將零件工程圖中的幾何圖形標(biāo)記為功能表面，根據(jù)是否共邊、共點或點在邊上，判斷功能表面是否拓?fù)湎噙B，并進(jìn)一步確定功能表面間的位置關(guān)系，生成零件2D結(jié)構(gòu)模型。通過對視圖結(jié)構(gòu)模型公共頂點、公共邊約束定義的“并”運算，構(gòu)造零件3D結(jié)構(gòu)模型。借鑒化學(xué)數(shù)據(jù)庫中化合物的線性符號表示法生成零件工程圖結(jié)構(gòu)碼。以零件工程圖子結(jié)構(gòu)布爾模型表達(dá)檢索要求，通過查詢子結(jié)構(gòu)碼與分支結(jié)構(gòu)碼的匹配，實現(xiàn)零件工程圖的子結(jié)構(gòu)檢索；以零件工程圖表達(dá)檢索要求，通過視圖結(jié)構(gòu)碼的整體匹配，實現(xiàn)零件工程圖的示例檢索；通過零件工程圖3D結(jié)構(gòu)碼與零件三維模型結(jié)構(gòu)碼的匹配，實現(xiàn)零件工程圖的模型檢索。這種方法要求使用者必須熟悉結(jié)構(gòu)碼，編碼基本上是抽象的，在處理復(fù)雜和大量的工程圖紙時，逐一對比耗時且缺乏效率。

本文在文獻(xiàn)［8］的零件工程圖3D結(jié)構(gòu)碼的基礎(chǔ)上，根據(jù)其構(gòu)成的特點（功能面和位置關(guān)系）給出其基于概念格的表示方法，并利用信息熵確定功能面和位置關(guān)系的重要概念對。在此基礎(chǔ)上，結(jié)合結(jié)構(gòu)碼，發(fā)現(xiàn)零件關(guān)鍵結(jié)構(gòu)。

1 零件工程圖結(jié)構(gòu)模型

文獻(xiàn)［8］給出的零件工程圖結(jié)構(gòu)模型是基于功能表面分類的。功能表面的基本類型為平面、圓柱面、圓錐面、球面和孔。功能表面視圖中大寫字母P、C、H和S分別表示平面、圓柱面、孔和槽，小寫字母w、k、h和r分別表示螺紋連接、平鍵連接、半回轉(zhuǎn)面和環(huán)結(jié)構(gòu)。圖1為幾個常見零件和它的功能表面視圖。

圖1 幾個常用機械零件的功能表面視圖表達(dá)

這里功能表面間的拓?fù)潢P(guān)系是通過連接邊的凹凸性來表示的，凹邊用“0”標(biāo)記，凸邊用“1”標(biāo)記。若兩相連功能表面均為回轉(zhuǎn)面時，拓?fù)潢P(guān)系通過回轉(zhuǎn)面是內(nèi)表面還是外表面來定義，并用“！”標(biāo)記。零件工程圖中判斷功能表面是否拓?fù)湎噙B包括共邊、共點或點在邊上三個條件。

功能表面間的位置關(guān)系包括方位關(guān)系和領(lǐng)域關(guān)系。方位關(guān)系通過方位矢量的空間方位關(guān)系來定義，有平行（∥）、同軸（⊙）、垂直（⊥）和偏斜（∠）；領(lǐng)域關(guān)系指功能表面占據(jù)的空間區(qū)域間的關(guān)系，領(lǐng)域關(guān)系的種類與方位關(guān)系類型有關(guān)，二元領(lǐng)域關(guān)系見表1［8］。因為平面功能表面占據(jù)區(qū)域的長度為0，所以平面與回轉(zhuǎn)面間的相遇、重疊、共點關(guān)系合并為相遇。兩垂直平面之間不定義二元領(lǐng)域關(guān)系，并用“！”標(biāo)記。符號“?。！北硎緝晒δ鼙砻嫱?fù)湎噙B，而符號“?！眲t表示拓?fù)洳幌噙B。符號“？”表示功能表面間的位置關(guān)系不能通過單個視圖確定。

將零件工程圖的功能表面進(jìn)行標(biāo)記，再根據(jù)判斷拓?fù)湎噙B功能表面的幾何條件、功能表面間位置關(guān)系的確定方法以及分布關(guān)系的定義，可以得到零件工程圖結(jié)構(gòu)模型［8］。圖2即為圖1的工程圖結(jié)構(gòu)模型。

圖2 圖1的3D零件結(jié)構(gòu)模型

2 零件工程圖結(jié)構(gòu)模型到形式概念格的映射

零件工程圖組成部分主要是功能表面和位置關(guān)系。依據(jù)形式概念分析的特性，我們可以以此構(gòu)建零件工程圖結(jié)構(gòu)的形式背景，進(jìn)而構(gòu)建零件工程圖的概念格（有關(guān)形式概念格的具體內(nèi)容可參見文獻(xiàn)［10］）。

零件工程圖結(jié)構(gòu)模型的功能表面與其關(guān)系可以用互相抵達(dá)來表明，設(shè)SourceSurface、Relation和TargetSurface是PG（Part Graph）中G的三個組成部分，用g.source、g.relation和g.target分別表示。I是構(gòu)成形式背景的對集（Object，Attribute），有

映射是PG的關(guān)系目標(biāo)可以成為另一個關(guān)系的源CG（Concept Graph）概念的傳遞。該傳遞產(chǎn)生隱式映射的推理：

映射算法如下：

該算法的工作原理是最初設(shè)定每個三元組的目標(biāo)概念為MovingTarget和FixedTarget，然后調(diào)用FormContext通過所有的三元組迭代，形成了相應(yīng)的形式概念分析的（Object，Attribute）對，每次MovingTarget匹配一個三元組的目標(biāo)概念。二元轉(zhuǎn)換是由遞歸調(diào)用FormContext形成的，對當(dāng)前的源概念設(shè)置MovingTarget，而留下FixedTarget不變。

3 形式概念分析與零件關(guān)鍵結(jié)構(gòu)

形式概念分析也稱為形式概念格。設(shè)（X，Y，I）表示一個形式背景。（X，Y，I）的對象、屬性對（A，B）（A?X，B?Y）成為一個形式概念的條件是當(dāng)且僅當(dāng)A↑＝B并且B↓＝A，其中A↑＝｛y∈Y｜x∈X∶（x，y）∈I｝，B↓＝ ｛x∈X｜y∈Y：（x，y）∈I｝，分別是A中所有對象的公共屬性集（稱為形式概念（A，B）的內(nèi)涵）和B中所有屬性的公共對象集（稱為形式概念（A，B）的外延）。背景（X，Y，I）的所有形式概念集合表示為b（X，Y，I）。b（X，Y，I）的超概念 －子概念偏序小于等于構(gòu)成（X，Y，I）的概念格。圖2的形式背景和概念格如表2和圖3所示。

表2 圖2c的形式背景

圖3 圖2c的概念格

形式概念分析的基點是形式背景，它的主要研究對象是形式概念和概念格。概念是外延和內(nèi)涵的統(tǒng)一體，概念格在本質(zhì)上描述了對象和屬性之間的聯(lián)系，表明了概念之間的泛化和例化關(guān)系，而它的Hasse圖則實現(xiàn)了對數(shù)據(jù)的可視化。在我們實現(xiàn)了用概念格表示零件結(jié)構(gòu)后，概念格的關(guān)鍵部分（重要概念或稱核概念）就是零件結(jié)構(gòu)的重要部分。由于零件的不同形變關(guān)系直接關(guān)系到零件的功能及作用，因此，零件功能表面的位置關(guān)系的重要程度應(yīng)該是有差別的，或者說這些位置關(guān)系對于形成整個零件來說所起的作用是不同的。完成了零件工程圖結(jié)構(gòu)模型到形式概念格的映射后，這種差別或不同就可以在屬性上體現(xiàn)出來。

在文獻(xiàn)［11］中，針對屬性重要性的不同，給內(nèi)涵引入權(quán)值ω（0≤ω≤1）以標(biāo)識內(nèi)涵的重要性而建立了一種新的概念格結(jié)構(gòu)——加權(quán)概念格。如果一個形式背景可表示為四元組（X，Y，I，W），Y＝ ｛y1，y2，…，yn｝，W為Y中屬性yi（i＝1，2，…，n）的權(quán)值集合，W＝ ｛ω1，ω2，…，ωn｝，W標(biāo)識了屬性yi的重要程度。若（A，B，ω）為（X，Y，I，W）上的一個任意三元組，如果（A，B）是一個形式概念，ω＝W（B）為屬性集B的權(quán)值且0≤ω≤1，稱（A，B，ω）為（X，Y，I，W）上的一個加權(quán)概念。A稱為加權(quán)概念的外延，B稱為加權(quán)概念的內(nèi)涵，其超概念 －子概念與一般概念格相同。

給定一個值θ∈V（V為閾值空間）可得到B（X，Y，I）的部分形式概念Bθ（X，Y，I）＝ ｛（A，B）∈B（X，Y，I，W）｜ω≥θ｝，Bθ（X，Y，I）可以看做是重要形式概念的集合。

信息熵可表示數(shù)據(jù)的統(tǒng)計特征，可以用來描述信息源提供的平均信息量，也可以描述信息源的平均不確定性。參照文獻(xiàn)［12］，信息熵的相關(guān)定義如下。

定義1 設(shè)P在U上導(dǎo)出的劃分為X＝｛X1，X2，…，Xl｝，則P在由U的子集組成的σ的代數(shù)的概率分布為

定義2 屬性集合P的熵E（P）為

根據(jù)系統(tǒng)熵的計算公式，當(dāng)系統(tǒng)可能處于幾種狀態(tài)的概率相等時，即P（Xj）＝1/m時，系統(tǒng)熵 值 最 大，即E（P（X1），P（X2），…，P（Xn）≤E（1/m，1/m，…，1/m）＝log2m。

對于給定的形式背景，各屬性特征取值的概率大小客觀隱含著信息量的大小，由于形式背景中各對象具有獨立性，其提供的共同屬性的信息量具有可加性，因此形式背景中某屬性的信息量為各對象提供的屬性信息之和，即某屬性信息熵的多少隱含了其不確定性程度。對于yi（yi∈Y，i＝1，2，…，n）在X上劃分出的等價類Xj（Xj?X，j＝1，2，…，m），P（｛yi｝/Xj）表示對象為Xj元素，具有屬性yi的概率，E（｛yi｝）表示Xj提供給屬性yi的平均信息量，其可以表示yi的重要性：

在形式背景中屬性集Y＝ ｛y1，y2，…，yn｝，對于 （A，B，ω），若B＝ ｛yi｝（i＝ 1，2，…，n），則E（B）＝ωi。容易看出，在｜X｜＝m的形式背景中，最大熵E（｛yi｝）max＝log2m。使用最大熵E（｛yi｝）max對熵值進(jìn)行歸一化處理，有

對于概念格的多屬性內(nèi)涵權(quán)值的計算，既要能反映多屬性內(nèi)涵的總體重要程度，又要考慮構(gòu)成內(nèi)涵的重要性存在偏差，可進(jìn)一步有效地反映和提取用戶需求的知識。

定義3 對于（A，B，ω），若B＝ ｛y1，y2，…，yk｝，y1，y2，…，yk∈Y，W（yi）＝ωi（i∈1，2，…，k），則A的內(nèi)涵B的重要性權(quán)值定義為

重要性標(biāo)準(zhǔn)偏差定義為

根據(jù)偏差的特點，定義D（B）＝0（n＝1）。

在確立了形式概念的權(quán)值和偏差后，對于一個由零件工程圖結(jié)構(gòu)模型轉(zhuǎn)化而來的形式背景，我們可以求出屬性的信息熵，并進(jìn)行歸一化處理。對于一般形式概念，屬性內(nèi)涵權(quán)值和重要性偏差值由數(shù)據(jù)特征值均值、標(biāo)準(zhǔn)差計算。用戶可以輸入α和β（α、β分別為屬性內(nèi)涵和重要性偏差的閾值），通過判斷生成重要概念集合。由這個概念集合的概念對（功能面，位置關(guān)系），我們就可以得到零件的關(guān)鍵結(jié)構(gòu)。

關(guān)鍵結(jié)構(gòu)的概念格算法如下：

4 零件關(guān)鍵結(jié)構(gòu)獲取實例

為驗證本文提出方法的有效性，筆者就文獻(xiàn)［8］的11個零件工程圖結(jié)構(gòu)模型中的6個進(jìn)行了逐一計算，圖4～圖9是轉(zhuǎn)換后的概念格和各節(jié)點內(nèi)涵權(quán)值及重要性偏差值。其中，我們將得到的任意概念格節(jié)點設(shè)為（A，B）。如果設(shè)β＝0，α取各自最大值，可以得到如表3所示的三維零件結(jié)構(gòu)模型的重要概念與關(guān)鍵結(jié)構(gòu)。

圖4 微調(diào)螺桿概念格各節(jié)點內(nèi)涵權(quán)值及重要性偏差值

圖5 拉桿軸概念格各節(jié)點內(nèi)涵權(quán)值及重要性偏差值

表中“關(guān)鍵結(jié)構(gòu)”表示的整個代碼是取自文獻(xiàn)［8］的零件工程圖結(jié)構(gòu)碼，加黑的部分是用本文方法計算出的關(guān)鍵結(jié)構(gòu)。從表3中可以看出，對于大部分的零件，本文方法不僅能確定重要位置關(guān)系（重要內(nèi)涵），也能確定構(gòu)成這種關(guān)系的功能表面（概念對象），進(jìn)而確定出零件的關(guān)鍵結(jié)構(gòu)。當(dāng)然，對于完全對稱的毫無“特色”的零件，本文的方法也表現(xiàn)出了局限性（如拉桿軸）。究其原因是這些問題中，位置關(guān)系（概念內(nèi)涵）權(quán)值完全相同，也就是說零件圖本身提供的信息不足以將其區(qū)分，因此，只要設(shè)計者提供進(jìn)一步的信息，這個問題就會迎刃而解。

圖6 擺軸概念格各節(jié)點內(nèi)涵權(quán)值及重要性偏差值

圖7 波導(dǎo)開關(guān)轉(zhuǎn)子概念格各節(jié)點內(nèi)涵權(quán)值及重要性偏差值

5 結(jié)束語

本文在零件工程圖結(jié)構(gòu)模型系統(tǒng)框架下利用信息熵和形式概念分析技術(shù)從模型提供的位置關(guān)系的不同重要性信息入手，針對文獻(xiàn)［7］給出的幾個不同類型零件對關(guān)鍵結(jié)構(gòu)進(jìn)行分析，總結(jié)出一般零件結(jié)構(gòu)圖關(guān)鍵結(jié)構(gòu)的確定方法，方便設(shè)計者快速準(zhǔn)確地掌握設(shè)計要點，為今后最大限度地降低搜索零件制圖過程中的重復(fù)性勞動奠定了理論基礎(chǔ)。

圖8 雙鍵套概念格各節(jié)點內(nèi)涵權(quán)值及重要性偏差值

圖9 拔叉概念格各節(jié)點內(nèi)涵權(quán)值及重要性偏差值

在下一步的工作中，我們將用本文的方法來處理CAD 3D零件圖的檢索，開發(fā)相應(yīng)的系統(tǒng)。為了進(jìn)一步提高所提出方法的實用性，可以引入多屬性群決策中基于數(shù)據(jù)穩(wěn)定性與主觀偏好的綜合熵權(quán)方法，以期對無“特色”零件處理有較好的效果。

［1］ Berchtold S，Kriegel H.S3：Similarity in CAD Database Systems［C］∥ACM SIGMOD Int.Conf.on Management of Data.Tucson：ACM Press，1997：564－567.

［2］ Müller S，Rigoll G.Searching an Engineering Drawing Database for User－specied Shapes［C］//Proceedings of the Fifth International Conference on Document Analysis and Recognition，ICDAR ’99.Bangalore：IEEE，1999：697－700.

［3］ Park J，Um B.A New Appaoach to Similarity Retrieval of 2DGraphic Objects Based on Dominant Shapes［J］.Pattern Recognition Letters，1999，20：591－616.

［4］ Zhou L，Xie Q，Ding Q.Engineering Drawing Retrieval Based on Graph Matching［J］.Journal of Nanjing University of Aeronautics ＆ Astronautics，2008，40（3）：354－359.

［5］ 柳玉，賁可榮.基于屬性重要度的案例特征權(quán)重確定方法［J］.計算機集成制造系統(tǒng)，2012，18（6）：1230－1235.Liu Yu，Ben Kerong.Weight Coefficient Determination for Case Feature Based on Attribute Importance［J］.Computer Integrated Manufacturing Systems，2012，18（6）：1230－1235.

［6］ 張勝文，丁玉玲，王貴成，等.基于特征相似性的船用柴油機關(guān)鍵件CAD/CAPP/CAM 集成技術(shù)［J］.計算機集成制造系統(tǒng)，2012，18（2）：291－297.Zhang Shengwen，Ding Yuling，Wang Guicheng，et al.CAD /CAPP/CAM Integrated Components Based Technology for Marine Diesel Key on Feature Similarity［J］.Computer Integrated Manufacturing Systems，2012，18（2）：291－297.

［7］ Wang P，Jiang S.An Engineering Drawing Retrieval Method Based on Nested Assignment Algorithm［J］.Journal of Computational Information Systems，2013，9（2）：713－720.

［8］ 徐靜，董雁.零件工程圖結(jié)構(gòu)檢索方法［J］.機械工程學(xué)報，2011，47（20）：191－198.Xu Jing，Dong Yan.Structure Retrieval Method for Part Engineering Drawing［J］.Journal of Mechanical Engineering，2011，47（20）：191－198.

［9］ 董雁，譚建榮，張樹有.基于符號的零件造型方法研究［J］.中國機械工程，2003，14（9）：773－776.Dong Yan，Tan Jianrong，Zhang Shuyou.Research on Part Modeling Methods Based on Symbols［J］.China Mechanical Engineering，2003，14（9）：773－776.

［10］ Bernhard G，Rudolf W.Formal Concept Analysis.Mathematical Foundations［M］.Berlin：Springer，1999.

［11］ Zhang S，Guo P，Zhang J，et al.A Completeness A－nalysis of Frequent Weighted Concept Lattices and Their Algebraic Properties［J］.Data ＆ Knowledge Engineering，2012，81/82：104－117.

［12］ 傅祖蕓.信息論——基礎(chǔ)理論與應(yīng)用（第2版）［M］.北京：電子工業(yè)出版社，2007.