一種裝配體模型的離散量化與相似性分析方法

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

1. 西北工業大學 機電學院，西安 710129 2. 西安工程大學 機電工程學院，西安 710048

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

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

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

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

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

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

1 基于結構離散化的裝配體信息量化方法

提出一種基于結構離散化的裝配體模型量化描述方法，通過構建“結構單元”的分割方法與描述過程，能夠將裝配體模型的形狀信息和連接信息統一量化表達為若干個高維向量構成的集合，進而支撐索引結構的構造和模型間相似性的分析。裝配體模型量化描述過程如圖1所示，可以分為以下3個步驟：構建屬性連接圖、結構單元離散化分割以及裝配體描述符構建。

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

1.1 裝配體連接圖構建

裝配體模型是由若干個零件構成的系統，其設計功能的實現通過各種零件特征和零件間裝配連接的有機組合實現。為了準確反映裝配體的本質屬性，目前研究中通常采用圖的形式對零件形狀信息及連接信息進行表征。圖結構具有旋轉、縮放和平移不變性，為了便于計算分析，可將零件定義為圖中的節點，零件間的連接關系定義為節點間的連接邊，進而可將裝配體模型表示為四元組形式的連接圖：

G={V,E,Av,Ae}

(1)

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

表面點集是三維模型的一種簡化描述方法，能夠反映模型的凹凸性、表面分布等外形特征，因此本文將表面點集作為零件的形狀信息進行提取。零件間的連接關系根據具體特性可泛化為剛性連接(鉚接、膠接、過盈配合等)和運動連接(轉動副、球面副、齒輪副等)等，在裝配體模型中這些連接關系通常都能表現為零件幾何區域間的相互接觸。因此在零件表面點集的基礎上，本文將不同的連接關系統一用接觸區域對應的點集進行表達。Av、Ae可表示為

(2)

1.2 結構單元離散化分割

受文獻[12]的啟發，本文以連接圖的各條邊為對象作為裝配體結構相似性分析的數據基礎，并以此為基礎進行索引結構的構造。在本文所構建連接圖中，每條邊及其關聯的頂點能夠表達裝配體中兩個零件的形狀和連接信息，利用這些信息將能夠更好地對邊之間的差異性進行判別，進而提升結構相似性分析過程的剪枝效率。本文將這種節點對結構定義為連接圖的結構單元。

根據上述定義，可將裝配體模型對應的連接圖G分解為結構單元的集合：

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

(3)

從圖論的角度分析，本文定義的結構單元分割方法具有以下特性：

1) 唯一性：對于給定的連接圖G，能夠將其唯一地分解為若干個結構單元的無序集合。

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

如圖2所示，2個裝配體模型間存在相似結構c，由于結構單元分割的唯一性和完整性，裝配體模型對應的結構單元集合Sa和Sb中存在相似的子集Sa,b，即結構c中所包含的結構單元。可以發現，連接圖中結構單元所代表的模型信息作為一種局部信息，隱含了其上層裝配體模型間的關聯線索，這種關聯規律在工程領域模型相似性分析中具有較好的適用性。因此，本文中通過結構離散化形成的結構單元，能夠支撐裝配體模型相似性的分析。

圖2 相似結構單元與相似結構的關聯Fig.2 Association between similar structural cells and structure

1.3 裝配體描述符構建

通過上述結構離散化方法，本文將裝配體模型分割為若干個結構單元的集合，進而將裝配體模型相似性分析問題轉化為以結構單元為基礎的分析過程，因此裝配體描述符構建過程需要以結構單元的量化描述為基礎進行。

1) 結構單元量化描述

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

本文中的結構單元由于同時具有裝配體兩零件間的連接信息和零件點云等形狀信息，而已有研究中關于連接信息的表達和計算通常較為復雜。因此，本文在形狀分布算法的基礎上，提出利用結構-形狀距離函數將結構單元所包含的結構和形狀信息統一納入一個向量形式的描述符。如圖3所示，結構-形狀距離可表示為

d=sd+pd1+pd2

(4)

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

在結構-形狀距離函數的基礎上，利用文獻[17]中形狀分布函數的基本思想，通過對模型表面進行隨機點采樣，并統計距離在尺度范圍內的分布情況實現結構單元的量化描述，其具體步驟如下：

步驟1輸入結構單元s。

步驟3重復上述步驟，并記錄采樣結果，通常采樣次數不低于105次。

圖3 結構-形狀距離Fig.3 Structure-shape distance

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

(5)

式中：ni為第i個組的頻數。

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

步驟6結束。

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

表1 不同結構單元所對應的結構-形狀直方圖Table 1 Structure-shape histograms corresponding to different structural elements

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

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

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

通過上述的處理和分析過程可以看出，具有不同形狀及連接關系的結構單元能夠由特征空間中不同位置的點進行區分，因此不同的裝配體模型間的差異性能夠通過特征空間中兩個點集進行量化分析。

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

2.1 結構單元相似性度量

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

(6)

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

(7)

當dis(u1,u2)=1時，表示兩個結構單元完全相同；反之則dis(u1,u2)越趨近于0。

2.2 基于BOW的模型匹配

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

1) BOW倒排索引構造

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

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

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

(8)

式中：vi為碼書中第i個單詞ci對應的高維向量。

步驟3建立倒排索引結構。以視覺單詞為索引，將特征向量插入對應的索引列表，形成倒排索引結構，每個索引列表中存儲與該視覺單詞近鄰的所有特征向量，以及包含該特征的裝配體。

在索引結構的基礎上，通過將查詢裝配體模型的特征向量量化至對應的視覺單詞，能夠快速縮小查詢范圍。

2) 查詢過濾

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

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

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

(9)

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

M={m1,m2,…,mn}

(10)

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

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

(11)

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

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

2.3 裝配體相似性量化分析

裝配體模型作為若干個結構單元的集合，模型間的相似性是由相應集合中元素間的最優匹配所決定的。即建立兩個裝配體中結構單元的一一對應關系，使得該對應關系下結構單元的相似性總和最大。考慮到Ma中特征向量間存在一對多或多對一等匹配形式，本文利用Earth Mover Distance算法[21]求解兩集合間的最優匹配，進而對裝配體模型的相似性進行進一步量化分析。

(12)

(13)

3 實驗分析

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

3.1 檢索實例

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

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

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

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

從準確性角度分析，(a)組實驗檢索效果較好，而(b)組實驗中第7個結果出現錯誤，一方面是因為后者與前者相比模型數量相對較少，導致出現錯誤概率更高；另一方面是由于本文中結構單元的特征向量是利用結構-形狀函數通過多次采樣形成的概率分布，這種方法不可避免地存在“語義鴻溝”問題，進而導致錯誤結果的產生。圖6為以不同數量結構單元為查詢對象下返回的前6個檢索結果。當以獨立的結構單元進行查詢時，第4和第6位結果出現明顯錯誤；但(b)組結果在準確率上有了一定的提高，是因為本文的相似性測度過程與結構單元匹配數量密切相關。當輸入的查詢結構單元數量越多時，模型庫中具有相似結構的正樣本模型與其他負樣本模型相比，前者存在更多的匹配結構單元，因此具有更高的“概率”獲得更高的相似性度量值，進而能夠保證檢索結果的合理性。

圖6 輸入不同數量結構單元的返回結果Fig.6 Results for inputting different number of structural cells

3.2 檢索性能

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

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

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

3.3 視覺單詞數量K對檢索的影響

在2.2節建立索引結構過程中，引入變量K用于構建視覺單詞和索引字典。圖8為過濾效率、召回率與視覺單詞數量K之間的關系，實驗中所用K的數量分別為16，32，64，128，180，256。由于索引和過濾計算過程中是以獨立的特征向量為查詢對象多次進行的，因此本節只統計n=1的情況下檢索結果的過濾效率和召回率指標。

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

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

4 結 論

1) 提出了基于結構離散化的裝配體模型信息量化方法，通過模型結構單元的分割和形狀-結構距離分布的統計等過程，實現裝配體模型結構特征的向量化描述。

2) 探討了基于BOW算法的倒排索引結構和超球體軟分配算法在裝配體模型檢索領域的應用，能夠在查詢過程中快速過濾無關的對象。

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