張杰，季寶寧，楊寧，唐文斌,2

1. 西北工業(yè)大學(xué) 機(jī)電學(xué)院，西安 710129 2. 西安工程大學(xué) 機(jī)電工程學(xué)院，西安 710048

隨著近年來計(jì)算機(jī)輔助設(shè)計(jì)(CAD)技術(shù)的不斷發(fā)展，現(xiàn)有基于模型定義(Model Based Definition，MBD)的產(chǎn)品數(shù)字化研制體系中，三維模型廣泛關(guān)聯(lián)了產(chǎn)品全生命周期上、下游的相關(guān)信息，包括工藝設(shè)計(jì)、加工制造和維修/維護(hù)等各個(gè)方面，由此形成了極具實(shí)踐意義的知識(shí)脈絡(luò)[1-2]。在此背景下，重用這些模型及其關(guān)聯(lián)的各類設(shè)計(jì)知識(shí)，如設(shè)計(jì)要求、工藝文檔、仿真數(shù)據(jù)等，已經(jīng)成為新產(chǎn)品快速研制的重要方式。為了支持工程技術(shù)人員進(jìn)行設(shè)計(jì)重用，近年來，以三維CAD模型為對象的檢索技術(shù)已成為人們普遍關(guān)注的熱點(diǎn)之一。

在航空航天等制造企業(yè)中，產(chǎn)品設(shè)計(jì)的最終形態(tài)通常是以裝配體模型的形式存在。裝配體模型是眾多零件模型通過多種連接及層次關(guān)聯(lián)形成的系統(tǒng)，既能夠直觀描述產(chǎn)品的局部細(xì)節(jié)特征和整體外形，也是功能、性能、制造工藝和產(chǎn)品維護(hù)等各類設(shè)計(jì)意圖的集中體現(xiàn)，因而具有極大的信息重用價(jià)值[3]。近年來眾多學(xué)者以裝配體模型為研究對象展開大量模型相似性分析方法等相關(guān)研究。

Deshmukh等[4]較早地給出了一個(gè)基于內(nèi)容的裝配體檢索系統(tǒng)，利用配合圖組織裝配體所包含的零件和裝配信息，并詳細(xì)給出了相關(guān)的檢索條件、檢索算法和檢索策略；Han等[5]提出了一種基于高級語義知識(shí)的裝配模型設(shè)計(jì)重用方法，通過零件語義、裝配約束語義和功能語義3個(gè)方面來描述裝配模型。Chen等[6]提出了基于骨架的裝配體模型相似性分析方法，利用多層次裝配描述符對裝配體進(jìn)行描述；文獻(xiàn)[7-9]也從組件幾何約束、零件接觸面、零件形狀和統(tǒng)計(jì)數(shù)據(jù)等方面，利用編碼等手段進(jìn)行裝配體信息量化等相關(guān)研究，并通過圖匹配算法實(shí)現(xiàn)模型相似性分析。這些方法的研究重點(diǎn)在于零件間連接關(guān)系及工程語義類信息的量化表達(dá)，在相似性分析時(shí)普遍采用圖、子圖同構(gòu)及頻繁子圖挖掘等方法，能夠較為準(zhǔn)確地識(shí)別兩模型中結(jié)構(gòu)相同的部分區(qū)域。但這些方法對結(jié)構(gòu)的差異性較為敏感，兩個(gè)裝配體模型中即使存在較小的差異，如在模型中增加或刪除或更改一個(gè)零件，也會(huì)對匹配結(jié)果產(chǎn)生較大影響，不利于裝配體結(jié)構(gòu)相似性的高效分析。

此外，圖同構(gòu)算法具有較高的時(shí)間復(fù)雜度，如何提高圖搜索效率也是需要關(guān)注的重點(diǎn)問題。目前研究學(xué)者提出了一系列算法，如GraphGrep[10]、GIndex[11]、RWM[12]等，這些方法普遍遵循“剪枝-驗(yàn)證”框架：即通過離散化思想將原始圖數(shù)據(jù)分割為若干個(gè)結(jié)構(gòu)較為簡單的“特征圖”，利用“特征圖”構(gòu)建索引結(jié)構(gòu)；然后利用索引結(jié)構(gòu)對搜索空間進(jìn)行匹配實(shí)現(xiàn)快速剪枝，并在已匹配“特征圖”的聚合過程中驗(yàn)證圖之間的相似性。實(shí)驗(yàn)證明這些方法較傳統(tǒng)的圖同構(gòu)算法具有更好的計(jì)算效率，但這些方法的研究對象多為化學(xué)、道路交通等領(lǐng)域具有明確屬性標(biāo)簽的圖對象，如何將這種方法與裝配體模型相似性分析問題相結(jié)合仍待進(jìn)一步研究。

上述的方法主要采用定性的分析手段，其結(jié)果一般只有“完全相似”、“部分相似”和“完全不相似”幾類，因此也有學(xué)者從定量的角度進(jìn)行相似性分析。例如，考慮到裝配體模型與其中零件模型間的組成關(guān)系，Hu等[13]以零件模型為對象建立幾何信息量化方法，借助向量空間模型將裝配體描述為n維向量；文獻(xiàn)[14-16]考慮零件形狀、空間位置及轉(zhuǎn)動(dòng)慣量等特征屬性，將零件模型量化描述為特征空間中的點(diǎn)，進(jìn)而通過離散點(diǎn)集的匹配實(shí)現(xiàn)裝配體模型檢索。這些方法利用向量間的距離大小作為判斷模型相似性的依據(jù)。對于兩個(gè)越相似的裝配體模型，其特征向量間的距離越相近，因而無需復(fù)雜的圖運(yùn)算即可實(shí)現(xiàn)相似性分析。但是由于離散點(diǎn)集無法表達(dá)零件間的連接關(guān)系，將在一定程度上影響檢索結(jié)果的準(zhǔn)確性。例如，對于兩個(gè)零件組成相同但連接關(guān)系不同的裝配體模型仍被判定為完全相似，但事實(shí)上零件間裝配方式的不同會(huì)對產(chǎn)品功能產(chǎn)生較大差異，而這種差異性無法在檢索結(jié)果中體現(xiàn)。

在上述各類方法的啟發(fā)下，為了將裝配體連接關(guān)系信息融入離散點(diǎn)集的描述過程，進(jìn)而利用高維向量間的距離計(jì)算實(shí)現(xiàn)裝配體結(jié)構(gòu)相似性分析，并支持索引結(jié)構(gòu)的構(gòu)造，本文提出了一種基于結(jié)構(gòu)離散化的裝配體模型信息量化和相似性分析方法。首先，通過分析零件的連接關(guān)系，采用離散化方法將裝配體分割為若干個(gè)結(jié)構(gòu)單元集合；在此基礎(chǔ)上，建立結(jié)構(gòu)-形狀分布函數(shù)并將結(jié)構(gòu)單元的形狀與結(jié)構(gòu)信息描述為特征向量，實(shí)現(xiàn)裝配體模型的量化描述；最后，在特征空間中建立詞袋(Bag of Word，BOW)索引結(jié)構(gòu)進(jìn)行結(jié)構(gòu)單元特征向量間的近似近鄰搜索，并通過Earth Mover Distance(EMD)算法實(shí)現(xiàn)裝配體模型的相似性分析。

1 基于結(jié)構(gòu)離散化的裝配體信息量化方法

提出一種基于結(jié)構(gòu)離散化的裝配體模型量化描述方法，通過構(gòu)建“結(jié)構(gòu)單元”的分割方法與描述過程，能夠?qū)⒀b配體模型的形狀信息和連接信息統(tǒng)一量化表達(dá)為若干個(gè)高維向量構(gòu)成的集合，進(jìn)而支撐索引結(jié)構(gòu)的構(gòu)造和模型間相似性的分析。裝配體模型量化描述過程如圖1所示，可以分為以下3個(gè)步驟：構(gòu)建屬性連接圖、結(jié)構(gòu)單元離散化分割以及裝配體描述符構(gòu)建。

圖1 裝配體模型描述符構(gòu)建過程Fig.1 Process of building assembly model descriptor

1.1 裝配體連接圖構(gòu)建

裝配體模型是由若干個(gè)零件構(gòu)成的系統(tǒng)，其設(shè)計(jì)功能的實(shí)現(xiàn)通過各種零件特征和零件間裝配連接的有機(jī)組合實(shí)現(xiàn)。為了準(zhǔn)確反映裝配體的本質(zhì)屬性，目前研究中通常采用圖的形式對零件形狀信息及連接信息進(jìn)行表征。圖結(jié)構(gòu)具有旋轉(zhuǎn)、縮放和平移不變性，為了便于計(jì)算分析，可將零件定義為圖中的節(jié)點(diǎn)，零件間的連接關(guān)系定義為節(jié)點(diǎn)間的連接邊，進(jìn)而可將裝配體模型表示為四元組形式的連接圖：

G={V,E,Av,Ae}

(1)

式中：V={v1,v2,…,vn}為零件節(jié)點(diǎn)集合，vi表示裝配體模型中第i個(gè)零件，n表示零件數(shù)量；E={ei,j|h(vi,vj)=1}為連接關(guān)系集合，ei,j表示第i個(gè)零件和第j個(gè)零件間存在連接關(guān)系，h(vi,vj)=1為判斷零件vi,vj間存在連接關(guān)系；Av、Ae分別為描述零件形狀信息和連接關(guān)系信息，接下來對這兩種信息進(jìn)行定義。

表面點(diǎn)集是三維模型的一種簡化描述方法，能夠反映模型的凹凸性、表面分布等外形特征，因此本文將表面點(diǎn)集作為零件的形狀信息進(jìn)行提取。零件間的連接關(guān)系根據(jù)具體特性可泛化為剛性連接(鉚接、膠接、過盈配合等)和運(yùn)動(dòng)連接(轉(zhuǎn)動(dòng)副、球面副、齒輪副等)等，在裝配體模型中這些連接關(guān)系通常都能表現(xiàn)為零件幾何區(qū)域間的相互接觸。因此在零件表面點(diǎn)集的基礎(chǔ)上，本文將不同的連接關(guān)系統(tǒng)一用接觸區(qū)域?qū)?yīng)的點(diǎn)集進(jìn)行表達(dá)。Av、Ae可表示為

(2)

1.2 結(jié)構(gòu)單元離散化分割

受文獻(xiàn)[12]的啟發(fā)，本文以連接圖的各條邊為對象作為裝配體結(jié)構(gòu)相似性分析的數(shù)據(jù)基礎(chǔ)，并以此為基礎(chǔ)進(jìn)行索引結(jié)構(gòu)的構(gòu)造。在本文所構(gòu)建連接圖中，每條邊及其關(guān)聯(lián)的頂點(diǎn)能夠表達(dá)裝配體中兩個(gè)零件的形狀和連接信息，利用這些信息將能夠更好地對邊之間的差異性進(jìn)行判別，進(jìn)而提升結(jié)構(gòu)相似性分析過程的剪枝效率。本文將這種節(jié)點(diǎn)對結(jié)構(gòu)定義為連接圖的結(jié)構(gòu)單元。

根據(jù)上述定義，可將裝配體模型對應(yīng)的連接圖G分解為結(jié)構(gòu)單元的集合：

S={si,j|h(vi,vj)=1}

(3)

從圖論的角度分析，本文定義的結(jié)構(gòu)單元分割方法具有以下特性：

1) 唯一性：對于給定的連接圖G，能夠?qū)⑵湮ㄒ坏胤纸鉃槿舾蓚€(gè)結(jié)構(gòu)單元的無序集合。

2) 完整性：能夠覆蓋連接圖G中所有頂點(diǎn)、邊、頂點(diǎn)屬性和邊屬性等信息。

如圖2所示，2個(gè)裝配體模型間存在相似結(jié)構(gòu)c，由于結(jié)構(gòu)單元分割的唯一性和完整性，裝配體模型對應(yīng)的結(jié)構(gòu)單元集合Sa和Sb中存在相似的子集Sa,b，即結(jié)構(gòu)c中所包含的結(jié)構(gòu)單元?？梢园l(fā)現(xiàn)，連接圖中結(jié)構(gòu)單元所代表的模型信息作為一種局部信息，隱含了其上層裝配體模型間的關(guān)聯(lián)線索，這種關(guān)聯(lián)規(guī)律在工程領(lǐng)域模型相似性分析中具有較好的適用性。因此，本文中通過結(jié)構(gòu)離散化形成的結(jié)構(gòu)單元，能夠支撐裝配體模型相似性的分析。

圖2 相似結(jié)構(gòu)單元與相似結(jié)構(gòu)的關(guān)聯(lián)Fig.2 Association between similar structural cells and structure

1.3 裝配體描述符構(gòu)建

通過上述結(jié)構(gòu)離散化方法，本文將裝配體模型分割為若干個(gè)結(jié)構(gòu)單元的集合，進(jìn)而將裝配體模型相似性分析問題轉(zhuǎn)化為以結(jié)構(gòu)單元為基礎(chǔ)的分析過程，因此裝配體描述符構(gòu)建過程需要以結(jié)構(gòu)單元的量化描述為基礎(chǔ)進(jìn)行。

1) 結(jié)構(gòu)單元量化描述

形狀信息的量化描述是分析三維模型相似性的重要方法，目前在三維模型檢索領(lǐng)域已經(jīng)有較為廣泛的應(yīng)用。較為經(jīng)典的算法如Osada等[17]提出的形狀分布直方圖，通過在模型表面上的隨機(jī)采樣計(jì)算采樣點(diǎn)間距離函數(shù)的值，并將函數(shù)值的概率分布表示為直方圖以描述模型的形狀特征，由于具有計(jì)算簡單、魯棒性高、識(shí)別率較高等特點(diǎn)，這種方法逐漸成為三維模型檢索領(lǐng)域較為通用的方法。

本文中的結(jié)構(gòu)單元由于同時(shí)具有裝配體兩零件間的連接信息和零件點(diǎn)云等形狀信息，而已有研究中關(guān)于連接信息的表達(dá)和計(jì)算通常較為復(fù)雜。因此，本文在形狀分布算法的基礎(chǔ)上，提出利用結(jié)構(gòu)-形狀距離函數(shù)將結(jié)構(gòu)單元所包含的結(jié)構(gòu)和形狀信息統(tǒng)一納入一個(gè)向量形式的描述符。如圖3所示，結(jié)構(gòu)-形狀距離可表示為

d=sd+pd1+pd2

(4)

式中：sd為結(jié)構(gòu)單元的空間連接距離，表示兩零件重心gc1、gc2到配合面形心fc的距離之和，gc1、gc2和fc由s的頂點(diǎn)和邊屬性計(jì)算得到；pd1、pd2分別為兩零件上采樣點(diǎn)到該零件形心的距離。

在結(jié)構(gòu)-形狀距離函數(shù)的基礎(chǔ)上，利用文獻(xiàn)[17]中形狀分布函數(shù)的基本思想，通過對模型表面進(jìn)行隨機(jī)點(diǎn)采樣，并統(tǒng)計(jì)距離在尺度范圍內(nèi)的分布情況實(shí)現(xiàn)結(jié)構(gòu)單元的量化描述，其具體步驟如下：

步驟1輸入結(jié)構(gòu)單元s。

步驟3重復(fù)上述步驟，并記錄采樣結(jié)果，通常采樣次數(shù)不低于105次。

圖3 結(jié)構(gòu)-形狀距離Fig.3 Structure-shape distance

步驟4構(gòu)建結(jié)構(gòu)-形狀分布直方圖。以一個(gè)組數(shù)為k的直方圖表示采樣距離值的分布情況，其組距為max(d)/k。根據(jù)文獻(xiàn)[14]，k的取值一般為1 024。直方圖中每組的高度表示了每次采樣計(jì)算的結(jié)構(gòu)-形狀距離落在該組中的概率，可以表示為

(5)

式中：ni為第i個(gè)組的頻數(shù)。

步驟5本文不直接使用直方圖表示結(jié)構(gòu)單元的結(jié)構(gòu)-形狀信息，而是構(gòu)造一個(gè)k維特征向量u=[h1,h2,…,hk]對其進(jìn)行表征。

步驟6結(jié)束。

通過上述步驟能夠得到同時(shí)反映結(jié)構(gòu)單元形狀和空間連接信息的向量描述符。如表1所示，具有相對運(yùn)動(dòng)能力的結(jié)構(gòu)單元a與b相比在零件形狀上具有一定的差異，相應(yīng)的結(jié)構(gòu)-形狀分布直方圖體現(xiàn)為信號形狀的差異性；a與c的直方圖十分接近體現(xiàn)了本文的描述符對于零件間靜態(tài)連接和運(yùn)動(dòng)連接的適用性；而a與d相比，構(gòu)成結(jié)構(gòu)單元的兩個(gè)零件形狀上完全相同但裝配狀態(tài)不同，其相應(yīng)的結(jié)構(gòu)-形狀分布直方圖在波峰信號起始位置存在差異性。由此可以看出，通過上述步驟形成的結(jié)構(gòu)-形狀分布直方圖能區(qū)分不同形狀和連接關(guān)系的結(jié)構(gòu)單元，因此能夠在一定程度上保證特征向量對結(jié)構(gòu)單元量化描述的準(zhǔn)確性。

表1 不同結(jié)構(gòu)單元所對應(yīng)的結(jié)構(gòu)-形狀直方圖Table 1 Structure-shape histograms corresponding to different structural elements

2) 基于高維向量的裝配體描述符

1.2節(jié)中，任意的結(jié)構(gòu)單元都可由k維特征向量進(jìn)行表示，因此本文考慮建立k維特征空間Rk，進(jìn)而將結(jié)構(gòu)單元映射為空間中的點(diǎn)。對于裝配體模型，可根據(jù)其中所包含的結(jié)構(gòu)單元，最終由特征空間中相應(yīng)的k維向量進(jìn)行表征，其描述過程如下：

對于待描述裝配體A，首先構(gòu)建相應(yīng)的連接圖Ga；然后，根據(jù)定義1，按照Ga中節(jié)點(diǎn)間的連接關(guān)系進(jìn)行分割，形成結(jié)構(gòu)單元集合{sa,1,sa,2,…,sa,n}；最后，對于每一個(gè)結(jié)構(gòu)單元sa,i，按照1.2節(jié)的結(jié)構(gòu)-形狀分布函數(shù)將其量化描述為特征向量ua,i，進(jìn)而得到裝配體A的描述符DESa={ua,1,ua,2,…,ua,n}。

通過上述的處理和分析過程可以看出，具有不同形狀及連接關(guān)系的結(jié)構(gòu)單元能夠由特征空間中不同位置的點(diǎn)進(jìn)行區(qū)分，因此不同的裝配體模型間的差異性能夠通過特征空間中兩個(gè)點(diǎn)集進(jìn)行量化分析。

2 裝配體模型相似性分析方法

2.1 結(jié)構(gòu)單元相似性度量

結(jié)構(gòu)單元的相似性分析是進(jìn)行裝配體相似性分析的基礎(chǔ)。通過上述的步驟，本文最終將結(jié)構(gòu)單元的零件形狀及零件間的空間連接關(guān)系等信息統(tǒng)一量化表征為結(jié)構(gòu)-形狀分布向量，因此結(jié)構(gòu)單元的相似性可通過滿足歐氏空間測度公理的距離定義方法進(jìn)行計(jì)算。本文采用L1范式距離(即曼哈頓距離)進(jìn)行結(jié)構(gòu)單元特征向量的相似性度量。

(6)

L1范式距離只與向量中相同維度下的振幅有關(guān)，由于每個(gè)特征向量中各元素之和為1，L1(u1,u2)取值范圍為[0,2]。在此基礎(chǔ)上，可將u1，u2所對應(yīng)的兩個(gè)結(jié)構(gòu)單元間的相似性歸一化表示為

(7)

當(dāng)dis(u1,u2)=1時(shí)，表示兩個(gè)結(jié)構(gòu)單元完全相同；反之則dis(u1,u2)越趨近于0。

2.2 基于BOW的模型匹配

通過結(jié)構(gòu)離散量化描述過程，本文將裝配體檢索問題轉(zhuǎn)化為對相似結(jié)構(gòu)單元的搜索問題，因此在檢索過程中我們主要關(guān)注模型庫中與查詢模型具有相似性的結(jié)構(gòu)單元。本文在結(jié)構(gòu)單元量化描述的基礎(chǔ)上，引入BOW索引與過濾機(jī)制，快速過濾與查詢模型明顯不相關(guān)的結(jié)構(gòu)單元，進(jìn)而提高裝配體模型檢索效率。

1) BOW倒排索引構(gòu)造

BOW倒排索引算法是由Csurka等[18]在2004年提出并應(yīng)用于圖像處理領(lǐng)域，其主要借鑒了文檔檢索的思想。在檢索文檔的過程中，文檔由一系列的基本單元組成，這個(gè)單元通常是單詞。在本文中，可將裝配體模型視為“文檔”，其中結(jié)構(gòu)單元所對應(yīng)的特征向量作為“文檔”中的“單詞”，進(jìn)而構(gòu)建基于BOW的倒排索引結(jié)構(gòu)。主要步驟如下：

步驟1訓(xùn)練碼書。對于特征向量數(shù)據(jù)集，利用K-means算法將特征空間劃分為K個(gè)子空間，以每個(gè)子空間中心點(diǎn)為視覺單詞，形成碼書C={c1,c2,…,cK}。

步驟2根據(jù)碼書C將模型庫中所有特征向量u量化至最近的視覺單詞：

(8)

式中：vi為碼書中第i個(gè)單詞ci對應(yīng)的高維向量。

步驟3建立倒排索引結(jié)構(gòu)。以視覺單詞為索引，將特征向量插入對應(yīng)的索引列表，形成倒排索引結(jié)構(gòu)，每個(gè)索引列表中存儲(chǔ)與該視覺單詞近鄰的所有特征向量，以及包含該特征的裝配體。

在索引結(jié)構(gòu)的基礎(chǔ)上，通過將查詢裝配體模型的特征向量量化至對應(yīng)的視覺單詞，能夠快速縮小查詢范圍。

2) 查詢過濾

對于查詢裝配體模型Q的描述符DESq={uq,1,uq,2,…uq,n}，n為特征向量數(shù)量，其搜索過程可以被近似地視為在倒排索引結(jié)構(gòu)上進(jìn)行n次近似最近鄰查詢。

為了提高查詢結(jié)果的召回率，本文采用超球體軟分配策略，通過查詢點(diǎn)與視覺單詞分布半徑間的距離關(guān)系自適應(yīng)地為查詢樣本分配若干個(gè)匹配視覺單詞，計(jì)算過程見文獻(xiàn)[19]。對于每個(gè)查詢特征向量uq,i，將為其分配的視覺單詞內(nèi)所有特征向量作為匹配候選集：

mi={list(cj)|Bi(c1≤j≤K)=1}

(9)

式中：B為指示函數(shù)，Bi(u1≤j≤K)=1為與查詢向量uq,i匹配的視覺單詞；list(cj)為第j個(gè)索引列表中所包含的所有特征向量。對于查詢裝配體模型Q，可將匹配結(jié)果表示為

M={m1,m2,…,mn}

(10)

對于模型庫中任意裝配體A的描述符DESa={ua,1,ua,2,…,ua,m}，m為特征向量數(shù)量，DESq中每個(gè)特征向量與DESa的匹配關(guān)系可表示為

Ma={ma,1,ma,2,…,ma,n},ma,i=mi∩DESa

(11)

式中：ma,i為裝配體A中與uq,i匹配的特征向量集合。與原始搜索空間相比，集合Ma過濾了特征空間中距離DESq的較遠(yuǎn)的特征向量，進(jìn)而避免對數(shù)據(jù)庫的線性掃描。Ma中匹配特征向量的數(shù)量能夠在一定程度上反映裝配體模型間的相似性。

基于BOW算法通常能夠使查詢復(fù)雜度達(dá)到logN級別，因此在上述計(jì)算過程中，當(dāng)以一個(gè)裝配體模型為查詢對象時(shí)進(jìn)行匹配時(shí)，其復(fù)雜度為O(NMlog(KNM))，其中N，M分別為所有裝配體模型中零件的平均數(shù)量以及每個(gè)零件連接關(guān)系的平均數(shù)量；K為模型庫的規(guī)模。在最差情況下，即模型中任意兩個(gè)零件間都存在連接關(guān)系，此時(shí)匹配過程的時(shí)間復(fù)雜度為O(N2log(KN))。而以Ullmann等子圖同構(gòu)算法對模型庫進(jìn)行匹配時(shí)，其最差情況下時(shí)間復(fù)雜度為O(KN!N2)[20]。由此可見，與已有基于圖匹配的方法相比，本文所提出的模型匹配方法在計(jì)算復(fù)雜度方面有了較大的提升。

2.3 裝配體相似性量化分析

裝配體模型作為若干個(gè)結(jié)構(gòu)單元的集合，模型間的相似性是由相應(yīng)集合中元素間的最優(yōu)匹配所決定的。即建立兩個(gè)裝配體中結(jié)構(gòu)單元的一一對應(yīng)關(guān)系，使得該對應(yīng)關(guān)系下結(jié)構(gòu)單元的相似性總和最大?？紤]到Ma中特征向量間存在一對多或多對一等匹配形式，本文利用Earth Mover Distance算法[21]求解兩集合間的最優(yōu)匹配，進(jìn)而對裝配體模型的相似性進(jìn)行進(jìn)一步量化分析。

(12)

(13)

3 實(shí)驗(yàn)分析

為了驗(yàn)證本文方法的有效性，在CATIA V5R19環(huán)境中通過二次開發(fā)實(shí)現(xiàn)零件幾何信息提取的批量化處理，并在MATLAB R2019b平臺(tái)下實(shí)現(xiàn)零件連接分析、結(jié)構(gòu)-形狀分布函數(shù)、索引過濾和裝配體相似性度量等，實(shí)現(xiàn)了本文所提出的基于結(jié)構(gòu)離散化的裝配體模型檢索方法。實(shí)驗(yàn)數(shù)據(jù)庫包含260個(gè)裝配體模型，共計(jì)1 984個(gè)零件模型，模型庫中部分裝配體模型如圖4所示。

3.1 檢索實(shí)例

本文在模型庫中選取腳輪和夾鉗兩組模型進(jìn)行檢索實(shí)例分析，兩組中模型數(shù)量分別為24和15個(gè)，實(shí)驗(yàn)中分別在其中選擇一個(gè)裝配體模型作為輸入，并對返回結(jié)果的相似性進(jìn)行排序形成檢索結(jié)果，如圖5所示。

圖5 裝配體模型檢索實(shí)例(K=128)Fig.5 Retrieval instances of assembly model (K=128)

從相似度角度分析，2組實(shí)驗(yàn)中第一個(gè)結(jié)果相似度均為1，是因?yàn)樵摍z索結(jié)果是查詢模型本身。(a)組實(shí)驗(yàn)中前4個(gè)與后4個(gè)和(b)組實(shí)驗(yàn)中前5個(gè)與第6個(gè)結(jié)果的值差異較大，說明相似性度量值受匹配結(jié)構(gòu)單元數(shù)量影響較大。對于越相似的裝配體模型，其中存在的匹配結(jié)構(gòu)單元數(shù)量也隨之增多，因而相似度值越大。但從總體來看，排序越靠前的檢索結(jié)果與查詢模型的相關(guān)度越高，證明本文提出的裝配體相似性測度方法具有一定的合理性。由于裝配體描述符在構(gòu)建過程中考慮了零件間的連接關(guān)系信息，在裝配體連接關(guān)系不變的情況下，對不同姿態(tài)下的模型可以得到一致的描述結(jié)果。例如在(b)組實(shí)驗(yàn)中，對于結(jié)構(gòu)較為相似但處于不同姿態(tài)下的裝配體模型，計(jì)算后的排序位置為第2和第3位，可認(rèn)為與查詢模型的相似程度較高。由此可以看出，本文提出的描述方法對于具有相對運(yùn)動(dòng)的裝配體模型也具有一定的識(shí)別能力。

在返回結(jié)果中，模型中灰色部分零件表示其所在的結(jié)構(gòu)單元在索引結(jié)構(gòu)中被過濾。從(a)組實(shí)驗(yàn)5～8個(gè)結(jié)果與查詢模型進(jìn)行對比發(fā)現(xiàn)，黃色部分模型與查詢模型間的相似性較高，說明本文的算法能夠較好地過濾與查詢模型無關(guān)的結(jié)構(gòu)單元，因而在一定程度上具有識(shí)別模型局部結(jié)構(gòu)相似性的能力。

從準(zhǔn)確性角度分析，(a)組實(shí)驗(yàn)檢索效果較好，而(b)組實(shí)驗(yàn)中第7個(gè)結(jié)果出現(xiàn)錯(cuò)誤，一方面是因?yàn)楹笳吲c前者相比模型數(shù)量相對較少，導(dǎo)致出現(xiàn)錯(cuò)誤概率更高；另一方面是由于本文中結(jié)構(gòu)單元的特征向量是利用結(jié)構(gòu)-形狀函數(shù)通過多次采樣形成的概率分布，這種方法不可避免地存在“語義鴻溝”問題，進(jìn)而導(dǎo)致錯(cuò)誤結(jié)果的產(chǎn)生。圖6為以不同數(shù)量結(jié)構(gòu)單元為查詢對象下返回的前6個(gè)檢索結(jié)果。當(dāng)以獨(dú)立的結(jié)構(gòu)單元進(jìn)行查詢時(shí)，第4和第6位結(jié)果出現(xiàn)明顯錯(cuò)誤；但(b)組結(jié)果在準(zhǔn)確率上有了一定的提高，是因?yàn)楸疚牡南嗨菩詼y度過程與結(jié)構(gòu)單元匹配數(shù)量密切相關(guān)。當(dāng)輸入的查詢結(jié)構(gòu)單元數(shù)量越多時(shí)，模型庫中具有相似結(jié)構(gòu)的正樣本模型與其他負(fù)樣本模型相比，前者存在更多的匹配結(jié)構(gòu)單元，因此具有更高的“概率”獲得更高的相似性度量值，進(jìn)而能夠保證檢索結(jié)果的合理性。

圖6 輸入不同數(shù)量結(jié)構(gòu)單元的返回結(jié)果Fig.6 Results for inputting different number of structural cells

3.2 檢索性能

在信息檢索領(lǐng)域，通常將查全率(Recall)與查準(zhǔn)率(Precision)作為反映檢索性能的重要指標(biāo)。其中，查全率反映原有樣本中有多少正例被準(zhǔn)確預(yù)測；查準(zhǔn)率表示預(yù)測為正的樣本中有多少是真正的正樣本(True positives)。圖7給出了本文方法在查詢結(jié)構(gòu)單元數(shù)量n=1，2和以整個(gè)裝配體為查詢對象下的查全率-查準(zhǔn)率(P-R)曲線。

n=1，2時(shí)，其查全率未能達(dá)到1是因?yàn)榇嬖趯?shí)際為真的實(shí)驗(yàn)樣本在索引結(jié)構(gòu)中被過濾，因此被錯(cuò)誤地預(yù)測為假。從總體來看，雖然n=1時(shí)在查全率較高情況下檢索結(jié)果準(zhǔn)確率較低，但隨著查詢結(jié)構(gòu)單元數(shù)量逐漸增多，相同查全率水平下所得的查準(zhǔn)率都相對有所提升，與圖6所得基本結(jié)論一致。由此可見，本文算法在檢索性能上具有一定的柔性：當(dāng)對查詢查準(zhǔn)率要求較高時(shí)，如在模型庫中查找包含一個(gè)常用部件的所有裝配體模型，以部件中包含的所有結(jié)構(gòu)單元作為查詢對象能夠返回更準(zhǔn)確的結(jié)果；而在查詢部分關(guān)鍵結(jié)構(gòu)的演化版本時(shí)不需要很高的查準(zhǔn)率，因此可以以部分結(jié)構(gòu)單元為查詢對象以獲得更多參考。

圖7 查全率-查準(zhǔn)率曲線(K=128)Fig.7 Precision-recall curves (K=128)

3.3 視覺單詞數(shù)量K對檢索的影響

在2.2節(jié)建立索引結(jié)構(gòu)過程中，引入變量K用于構(gòu)建視覺單詞和索引字典。圖8為過濾效率、召回率與視覺單詞數(shù)量K之間的關(guān)系，實(shí)驗(yàn)中所用K的數(shù)量分別為16，32，64，128，180，256。由于索引和過濾計(jì)算過程中是以獨(dú)立的特征向量為查詢對象多次進(jìn)行的，因此本節(jié)只統(tǒng)計(jì)n=1的情況下檢索結(jié)果的過濾效率和召回率指標(biāo)。

從圖8中可以看出，隨著K的不斷增加，過濾效率與召回率增長趨勢相反：K在16～128之間時(shí)，過濾效率迅速提升，召回率始終在95%以上；K超過128時(shí)，過濾效率維持在較高水平而召回率迅速降低。其原因是隨著參數(shù)K的不斷增加，特征空間的劃分也更加精細(xì)，導(dǎo)致同一類結(jié)構(gòu)單元更有可能被劃分至不同的子空間，進(jìn)而導(dǎo)致召回率的降低。因此，本文在實(shí)驗(yàn)中K取值為128，能夠在過濾效率和召回率間取得較好的平衡。

圖8 過濾效率、召回率與K的關(guān)系Fig.8 Relation of filtration ratio, recall ratio and K

4 結(jié) 論

1) 提出了基于結(jié)構(gòu)離散化的裝配體模型信息量化方法，通過模型結(jié)構(gòu)單元的分割和形狀-結(jié)構(gòu)距離分布的統(tǒng)計(jì)等過程，實(shí)現(xiàn)裝配體模型結(jié)構(gòu)特征的向量化描述。

2) 探討了基于BOW算法的倒排索引結(jié)構(gòu)和超球體軟分配算法在裝配體模型檢索領(lǐng)域的應(yīng)用，能夠在查詢過程中快速過濾無關(guān)的對象。

3) 建立了基于EMD算法的模型相似性度量方法，通過相似性度量值的排序獲得查詢結(jié)果，實(shí)例驗(yàn)證了本文方法的有效性。