基于零件屬性EMD測度的裝配體模型檢索

華順剛，南花梅

（大連理工大學機械工程學院，遼寧 大連116024）

1 引言

隨著CAD技術的發展和應用，工程領域中各企業在設計過程中積累了大量三維模型，快速檢索并充分利用現有模型是實現產品快速設計，提高企業競爭力的重要手段［1］。目前零件模型檢索技術已相對成熟，與單獨機械零件相比，裝配體包含裝配關系，檢索更加復雜，有待進一步的研究。

現有裝配體檢索方法對裝配體的描述主要分為兩類：裝配體整體描述［2-3］和組成裝配體的零件集合描述［4-6］。文獻［2］使用零件、裝配約束、功能信息來描述裝配體，需要提前對裝配體描述進行規范化預處理。文獻［3］等使用包含零件節點、連接關系、零件節點間連接關系及數量組成四元組表示屬性鄰接圖描述裝配體，利用最優二分圖匹配算法計算裝配體間相似度，需提前編碼裝配體零件的連接關系。組成裝配體的零件集合描述將裝配體看做沒有裝配關系的單獨零件的集合，單獨零件使用三維模型描述方法。文獻［4］提出將形狀分布應用在三維模型的描述上，在三維模型表面隨機取點對，使用形狀分布函數計算點對距離，按固定組數對點對距離分組，構成形狀分布直方圖表示三維模型。文獻［5-6］把形狀分布直方圖應用到三維CAD零件模型上，取點多耗時。

使用零件屬性矢量集合描述裝配體，可以直接通過CAD軟件獲取幾何、形狀、位置信息作為裝配體中每個零件模型原始數據。將每個零件各屬性數據占裝配體所有零件中該屬性數據和的百分比作為每個零件各屬性值，達到裝配體歸一化效果，構成屬性矢量，組成集合表示裝配體。最后利用推土機距離（Earth Mover’s Distance，EMD）算法［7］計算裝配體模型間零件匹配的最低成本，也即裝配體間非相似度值以便實現檢索。

2 裝配體模型檢索過程

裝配體模型檢索過程，如圖1所示。

圖1 裝配體模型檢索示意圖Fig.1 Diagram of the Assembly Model Retrieval

檢索過程共三步：

Step1.建立裝配體模型數據庫。包含兩部分：CAD裝配體模型和裝配體模型描述符。

Step2.零件匹配及裝配體檢索。使用EMD算法將目標裝配體模型與數據庫中所有裝配體模型進行零件模型匹配，得到非相似度值，并存儲到結果數據庫中。

Step3.檢索結果顯示。從結果數據庫中獲取目標裝配體模型檢索結果數據，按非相似度值升序（即相似度值降序）在檢索界面上顯示。

3 裝配體模型描述

3.1 基于屬性值的零件模型描述

質心坐標精確標識裝配體中零件的位置；轉動慣量對球體類、圓柱類等裝配體零件起到一定程度識別作用，如球類零件沿著三個坐標軸方向的轉動慣量相同，圓柱形零件沿軸向方向的轉動慣量小，沿其它兩方向轉動慣量較大，柱類零件軸向尺寸越長，差異越明顯；體積和表面積一定程度上識別裝配體中零件外貌。故選擇質心坐標、轉動慣量、體積、表面積屬性描述零件。

描述步驟為：從CAD軟件直接獲取零件模型的質心坐標（x，y，z）、轉動慣量（Ix，Iy，Iz）、體積（v）和表面積（s）數據；生成零件屬性柱狀圖；構建零件屬性矢量描述零件。

生成零件屬性柱狀圖的方法：選用8個參數（x，y，z，Ix，Iy，Iz，v，s）作為每個零件屬性分布狀圖的8個分組。一組代表零件一個屬性，每組高度為零件的該屬性占裝配體中所有零件該屬性和的百分比。相較于直接使用該零件原始屬性值，百分比之后屬性值作為柱狀圖柱子高度可以做到一定程度上的裝配體中零件模型歸一化。

3.2 基于零件屬性集合的裝配體模型描述

裝配體模型由組成它的多個零件構成，故裝配體模型可以由它所包含的零件的集合來描述。基于零件屬性矢量集合的裝配體模型描述，如圖2所示。

圖2 使用零件屬性矢量集合描述裝配體模型Fig.2 Assembly Model Description with Parts’Attributes Vector Set

步驟為：生成裝配體A中各零件對應的屬性柱狀圖和矢量，組成屬性矢量集合描述裝配體A。

由式（1）構建裝配體A中每個零件的屬性矢量p，組合各零件屬性矢量并組成描述該裝配體的矢量集合：

式中：裝配體A共有n個零件，pi—屬性矢量表示的第i個零件。

4 基于EMD的裝配體零件模型匹配

文獻［7］提出EMD算法并用于解決圖片檢索工作中的分布比較問題，用EMD算法求圖片顏色分布之間最小花費得到圖片之間的相似程度。裝配體模型間零件匹配問題也可以通過EMD算法來解決，求解兩裝配體使用屬性柱狀圖表示的零件間匹配的最小花費得到其相似程度，花費值即為兩裝配體間非相似度值。

EMD算法中首先要定義標簽（Signature），設標簽S=表示該標簽共有N個元素，每個元素s包含兩個要素：位置u和重量（或權重）w。j表示第j個。

約束條件如下：

式中：dij—從位置uxi到uyj的距離，fij—uxi位置到位置uyj之間的運輸量。

以裝配體A1、A2的零件匹配計算過程為例，在利用EMD算法計算零件匹配最小花費之前，需做以下四步準備工作：

Step1.根據式（2），構造裝配體A1、A2的零件屬性矢量集合

Step2.A1、A2依次帶入到給定的兩個標簽中，得到

Step3.確定上一步中權重參數w1i和w2j。

將每個零件權重w均選取1，即w1i=w2j=1(1≤i≤m,1≤j≤n)可保證裝配體間零件一對一匹配。

Step4.確認式（3）中dij。

使用歐氏距離作為裝配體A1中第i個零件屬性矢量p1i與裝配體A2中第j個零件屬性矢量p2j之間的距離計算公式：

利用EMD算法計算裝配體A1、A2之間的非相似度：

5 實驗驗證

利用SolidWorks 2016軟件平臺進行裝配體檢索實驗驗證，實驗計算機配置為Win7 64位操作系統，Intel（R）Core（TM）i5-7500 3.4GHz CPU，8.00 GB運行內存，編譯環境VS2017，編程語言C++，實驗中SolidWork裝配體模型（*.sldasm）包括網站［8］下載和自己創建兩部分。

由圖2可知，使用基于零件屬性矢量的EMD算法（EMD屬性矢量算法）獲得的各零件對應屬性柱狀圖區別顯著，確定了零件標識的唯一性，保證了零件匹配的合理性，提供了檢索實驗有效進行的基礎。

實驗的裝配體模型庫中共有52個裝配體模型，其中包含電機系列（6個），輪子系列（6個），夾具系列（4個）。實驗就這3個系列，對基于形狀分布的EMD算法［6］（EMD形狀分布）和EMD屬性矢量算法進行比較，檢索結果中顯示前六個與目標裝配體最相似的模型及其非相似度值，如表1所示。

表1中的EMD形狀分布算法在裝配體各零件表面取點對100萬個，計算點對歐式距離，分為300組，生成形狀分布直方圖描述零件，組成零件集合描述裝配體模型。

使用EMD屬性矢量算法和EMD形狀分布算法就檢索效果的魯棒性、查全率和檢索時間三方面進行比較分析。

（1）查全率比較。就表1中3組檢索實驗的查全率進行比較，如圖3所示。從輪子、夾具檢索實驗的查全率對比中，可明顯發現使用EMD屬性矢量算法查全率、檢索精度更高。

圖3 EMD屬性矢量算法和EMD形狀分布算法前六個檢索結果查全率比較Fig.3 The Recall Ratio of the Top Six Retrieval Results Comparison between the EMD Attribute Vector Algorithm and the EMD Shape Distribution Algorithm

（2）魯棒性比較。對裝配體尺寸大小變化進行魯棒性比較，根據零件匹配完整程度衡量算法魯棒性。電機檢索實驗中定義：當目標電機有底座時，數據庫中有底座電機在檢索結果前面顯示，電機尺寸對檢索結果影響小，視為魯棒性強。表1中，可以通過觀察B電機位置比較兩種算法的魯棒性，EMD屬性矢量和EMD形狀分布算法檢索結果中，B電機分別位于第4、6位，B電機比目標電機尺寸大，其他4個電機與目標電機尺寸相差不大。根據魯棒性的定義，EMD屬性矢量算法下，B電機位于兩個無底座模型之前；而EMD形狀分布算法下B電機則位于兩個無底座模型之后，故EMD屬性矢量算法對裝配體模型尺寸大小變化敏感度小，魯棒性更好。

表1 EMD屬性矢量算法與EMD形狀分布算法的前六個檢索結果比較Tab.1 The Top Six Retrieval Results Comparison between the EMD Attribute Vector Algorithm and the EMD Shape Distribution Algorithm

（3）檢索時間比較。對數據庫中的52個模型計算共計52×52次非相似度值，比較此過程中兩者耗時。EMD屬性矢量算法耗時1.893s，EMD形狀分布耗時35.604min，后者比前者多耗時1127倍，可見EMD屬性矢量算法檢索更加快捷。分析原因：EMD屬性矢量算法僅需的8組屬性數據直接從CAD軟件獲取，只使用屬性柱狀圖中該屬性與裝配體中所有零件該屬性總和的比值就作為每根柱子高度，而EMD形狀分布算法從零件模型表面隨機取高達100萬對點對，按形狀函數計算這些點對距離，分布于300個距離區間，構造形狀分布直方圖，耗時。

6 結論

使用裝配體零件屬性構成柱狀圖，組成集合描述裝配體，利用EMD算法計算裝配體間零件匹配的最小花費，實現檢索。該檢索方法具有以下特點：

（1）使用裝配體各零件屬性，生成屬性矢量，組成集合構成的裝配體描述符簡潔明了，有效合理。

（2）所需的裝配體模型零件屬性可以直接從CAD軟件獲取，無需預處理，直接明了。

（3）對于尺寸大小存在差異的裝配體模型檢索仍然準確、快速，魯棒性能高。