基于零部件編碼和Hausdorff距離的裝配體檢索技術研究

張 鵾

（銅陵學院機械工程學院, 安徽 銅陵 244061）

隨著工業領域中CAD技術的廣泛應用，各企業積累了大量產品的三維CAD模型。提高現有產品的三維CAD模型復用能力，對加快產品生產周期、提高產品市場適應力和提升企業競爭力有重要意義［1］。CAD模型檢索技術主要分為零件模型檢索和裝配體模型檢索。相較于零件模型檢索，裝配體模型檢索技術能夠實現產品級的模型復用，豐富了復用的內涵，得到了學界更多的關注。

裝配體模型檢索技術可分為基于拓撲結構和基于幾何形狀的方法［2］。在基于拓撲結構的方法中，通過構建裝配體圖或樹的數據模型，將裝配體的檢索轉換為圖或樹的匹配。周煒等［3］提取裝配體模型中零件之間接觸面信息，并對零件接觸面數量、零件接觸面關系進行編碼，構建相似度矩陣，通過最優匹配得到裝配體模型相似度。陶松橋等［4］通過運用復雜網絡原理對裝配體進行分析，建立了基于裝配關系的相似度矩陣，對其鄰居節點進行裝配關系的計算和匹配，從而完成相似性度量。這2種方法都是通過分析裝配體中零件間連接關系度量裝配體的相似性，缺少對零件的相似性判斷?；趲缀涡螤畹难b配體檢索技術一般使用直方圖描述裝配零件形狀分布信息，利用推土機距離［5-6］（Earth Mover’s Distance， EMD）或改進的豪斯多夫距離［7］（Modified Hausdorff Distance， MHD）算法計算分布圖的相似度。此外，Hu等［8］使用向量空間模型建立了針對輕量級裝配體的檢索方法。與基于拓撲的方法相反，基于幾何形狀的方法缺少對裝配體中零部件連接關系的描述，構成的裝配體模型知識仍顯不足。

基于上述方法不能全面表征裝配體信息的缺點，張杰等［9］提出了一種基于結構離散的方法，將裝配體模型信息量化并融入描述符中，最終實現相似性度量。左咪等［10］首先對裝配體模型進行信息的轉化表達并歸類，形成裝配體類碼連接圖，再基于Weisfeiler-Lehman圖核算法，對裝配體類碼圖進行相似度計算，實現裝配體間的分析比較。但上述方法的計算過程較為繁雜，對使用者有一定的技術要求。因此，針對裝配體搜索技術，主要針對以下2個問題進行研究：（1）裝配體信息尚未充分應用，不能同時有效地使用裝配體的隱式信息、零部件屬性及其關聯關系；
（2）計算復雜度較高，主要原因是使用算法較為復雜。

為解決上述2個問題，本文提出一種應用編碼技術和Hausdorff距離的裝配體相似度檢索模型，并給出實例驗證。首先，基于零部件的數字編碼技術，在編碼過程中融入裝配連接信息，將裝配體表示為由其零部件數字碼構成的向量空間點集，再利用改進的Hausdorff距離算法計算點集之間的距離，以點集的距離表征裝配體間的相似度。最后以實例驗證了方法的有效性并進行了總結與展望。

1.1 零部件編碼方案

建立完善的裝配體零部件編碼規則與系統，有利于實現零部件的檢索，加快零部件的復用效率［11-13］。區別于零件的編碼，裝配體中零部件的編碼一方面需要突出零部件特征，但另一方面不需要對零件特征進行詳盡的描述。本文基于成組技術，借鑒萬佳佳［14］、鄭建鑫［15］、Deshmukh 等［16］的裝配體分類編碼思想，保留簡潔有效的裝配體零部件信息，使用通用性較好的數字碼對零部件進行編碼。

為避免裝配體的編碼過長且冗余，在編碼過程中，針對部分不宜拆分為單個零件的部件，如溢流閥等液壓元件或鏈條一類成型組件，本文將其視為廣義上的一個零件進行編碼。零部件編碼碼位示意表如表1所示。

表1 零部件編碼碼位示意表

表1中，零部件編碼主要由零部件種類信息、幾何信息、結構信息及預留碼位4大區分塊構成，每個區分塊向下有各自細分類別，共有9個碼位。表中括號內數字表示不同信息的不同數字碼或范圍。在編碼規則中，既考慮了零部件信息又考慮了零部件間連接關系，并且預留拓展碼位以便針對不同需求的進一步特征細化。

零部件種類由標準類、組件類、功能類3個碼位構成，主要用來表示零部件的來源、分類和功能。其中，對于標準件的定義可以由國標擴展至企標，有利于零部件的歸類。由于本文中針對的是廣義零件，因此需要碼位Ⅱ以區分零部件的組成。零部件的功能主要有連接與傳動，由功能類碼位Ⅲ體現。

在零部件的幾何信息中，主要表征零部件的整體特征，包括零部件的形成方法、外形形狀特征、整體形狀尺寸。零部件的形成方法有回轉形成或非回轉形成。外形形狀特征的縱向編碼如表2所示，列出了9種常見的外形形狀，其他未列項歸于其他類中。對于回轉體的形狀尺寸，記錄回轉體最大直徑φ和最高高度h，其形狀尺寸比值r=h/φ；
對于非回轉體，其尺寸比值為該零部件最長尺寸lmax除以最短尺寸lmin，即r=lmax/lmin。零部件所有尺寸均在笛卡爾坐標系下進行測量。當零部件外形不規則時，則根據零部件的最小包圍盒形狀為回轉或非回轉體進行處理。尺寸的比值結果四舍五入取整，超過9的數值統一記為9。

表2 形狀類別編碼表

在結構信息中，編碼表征了該零部件與其他零部件間的連接數量與連接類型。其中，需要注意的是，連接數量的多少決定了碼位Ⅷ的位數數量，碼位Ⅷ的編碼按數字從小到大排列。表3對部分常見連接類型進行了編碼。

表3 零部件連接關系編碼表

1.2 零部件編碼實例

為有效說明編碼的實際過程，以某一頂桿凸輪機構為例進行編碼。圖1表示的是該凸輪結構，表4是該凸輪的相關參數。

表4 頂桿凸輪零件參數

圖1 頂桿凸輪機構

根據凸輪結構及參數，上述頂桿凸輪數字碼空間集合為G1=｛101139288，100169218，101069248｝，編碼說明如表5所示。

表5 頂桿凸輪的編碼

2.1 Hausdorff距離

Hausdorff距離［17］（Hausdorff Distance， HD）通常用于測量空間中子集之間的距離，它將存在于空間中的非空子集本身作為度量基準。在比較任意2點集間的相似性時，可以有效地處理多個點集的信息，并且不需要在點集之間建立一一對應關系。分別有 2 組非空集合A=｛a1，a2，…，an｝和B=｛b1，b2，…，bm｝，則A和B之間的Hausdorff距離定義為：

其中，

||·||表示點集A和B中各元素之間的距離范式，如歐氏距離等。由定義知，H（A，B）表征的是2個點集間最遠的距離，稱為雙向Hausdorff距離，其是Hausdorff距離的基本形式。h（A，B）和h（B，A）則分別表示的是點集A到B以及點集B到A的單向Hausdorff距離。

本文中，為抵消數字碼數值在定義時的隨機排序影響，改進Hausdorff距離定義中的距離范式為子集元素的歐氏距離與元素中極大值的比值。同時，考慮到零部件不同特征的重要性，可自定義給予不同碼位不同的權重。在計算過程中，由于Hausdorff距離度量的是2點集中最遠距離，這種比較方法會極大影響度量結果，如裝配體A與B其99%占比的零部件完全一致，僅有1%的零部件完全不同，依據Hausdorff距離判定方法，則A與B的相似度較低因其未考慮其99%的零部件相似。因此，本文采用與Zhang等［7］一致的方法將平均距離作為度量距離，降低了比較結果對離群點的敏感性。改進后的雙向Hausdorff距離定義不變，單向Hausdorff距離定義如下：

式（4）和式（5）中，n、m表示裝配體A、B的零部件數量，wi指的是不同碼位的權重值，滿足：

當n≠m時，單向Hausdorff距離不一致，對于雙向Hausdorff距離無影響。為保持一致性，本文使用的是雙向Hausdorff距離。

2.2 裝配體相似性計算

裝配體相似性計算的整個過程是將裝配體數字化編碼為一個點集，并使用改進的Hausdorff距離來解決模型檢索問題。其基本步驟包括：

1）借助數字編碼方法將裝配體轉換為多維空間的點集；

2）使用建立的點集構造裝配體模型的空間集合；

3）通過改進的Hausdorff距離計算點集之間的相似性。

在搜索過程中，輸入要檢索的裝配體模型空間集合后，搜索者可以獲得按相似性降序排列的結果。以檢索裝配體A與B、C間的相似度為例，其檢索過程如表6所示。

表6 裝配體檢索過程

為說明本方法的具體運算過程并驗證方法的有效性，本文利用頂桿凸輪與擺桿凸輪、曲柄滑塊機構進行相似度實例計算驗證。

在驗證前，考慮到頂桿凸輪與擺桿凸輪同屬凸輪機構，因此初步判斷二者的相似度較頂桿凸輪與曲柄滑塊機構間的相似度更高，即二者的距離更小。構成頂桿凸輪機構的向量空間為｛101139288，100169218，101069248｝。擺桿凸輪和曲柄滑塊機構的零部件名稱及編碼等信息如圖2所示。擺桿凸輪和曲柄滑塊機構的向量空間分別為｛101139218，100139218，101069248｝和｛10216511，101139211，101139211，10116310｝。

圖2 檢索裝配體實例

根據上述3個裝配體編碼，分別計算頂桿凸輪與擺桿凸輪、曲柄滑塊機構的相似度。由于幾何信息及結構信息更能凸顯零部件特征，本文定義零部件種類信息、幾何信息、結構信息的權重分別為30%、35%和35%，其中，形狀類別碼位和接觸方式碼位權值為0.15，度的權值為0.2，其他碼位均為0.1。

使用改進后的Hausdorff距離計算，得出頂桿凸輪與擺桿凸輪、曲柄滑塊機構的距離分別為0.025和0.099，即頂桿凸輪與擺桿凸輪的Hausdorff距離較其與曲柄滑塊機構的Hausdorff距離更近，基于距離越近相似度越高的原則，頂桿凸輪與擺桿凸輪的結構相似度更高，方法有效。

通過數字編碼方法構建裝配體的向量空間，將裝配體模型數字化為數字集合，同時，借助改進的Hausdorff距離方法計算數字集合間的距離，從而將裝配體間的相似性檢索問題轉化為一維的集合計算問題。最后通過3個裝配體模型的實例分析，驗證了方法的有效性。

相較于其他相關算法，基于零部件編碼和Hausdorff距離的裝配體檢索過程優勢在于其使用的Hausdorff距離，其計算是在一維集合中進行，速度較快；
且在編碼的同時考慮了裝配體幾何與結構信息，以及這些信息在裝配體特征中的權重占比，對裝配體的信息及特點表征相對全面。但計算之前需要對裝配體零部件及關聯關系進行分析、提取和編碼，方法的預操作階段較為冗雜。

基于上述問題，在后續研究中，提高編碼過程的便捷性以及對碼位特征權值的優化定義是進一步改進的重點。