基于投影圖與直方圖的機械零件模型檢索

朱文博 王朝 陳龍

摘 要：為實現資源重復利用與產品創新，通過檢索出數據庫中的相似零件為設計者提供幫助。首先對機械零件模型進行方位歸一化與預處理，以起始點為圓心作最大內切圓，劃分連通區，在連通區內根據距離變換值判定鄰域像素，進而確定新的骨架點，迭代生成完整骨架。將骨架轉換成直方圖曲線，劃分網格生成骨架點數矩陣，根據矩陣特征值和之間的差計算兩模型間的差異度，從而判定機械零件相似度。通過實例驗證以及與D2形狀分布算法及遞歸分割算法比較，發現該方法檢索速度高于遞歸分割算法，準確性高于D2形狀分布算法和遞歸分割算法。

關鍵詞：機械零件;模型檢索;骨架提取;距離變換;直方圖;差異度

DOI：10. 11907/rjdk. 192110 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP319文獻標識碼：A 文章編號：1672-7800（2020）005-0107-05

0 引言

隨著企業的發展與信息數字化應用的逐步深入，零件生產與創新可從許多現有零件模型中獲取靈感，并在原有基礎上進行部分創新，以重用企業資源，避免重復勞動。因此，如何在眾多現有案例中快速、準確地找出所需零件，是目前亟待解決的問題，很多學者也對該問題進行了大量研究。如Liu等[1]提出基于視圖的三維模型檢索方法，該方法利用聚類對模型進行視圖提取，采用游走算法對每個代表視圖進行權重更新，通過圖匹配解決模型相似性度量問題，但檢索過程較為復雜;Zhang等[2]提出從模型外部輪廓和內在結構中提取填充描述符，并采用二分圖匹配算法完成模型檢索，但計算量大，實際應用有一定困難;Wai等[3]提出基于帶次序的歐氏距離圖提取連接良好的骨架，給出一種連通性準則，可用于獨立確定給定像素是否為骨架點，但提取的骨架冗余分支較多;Cheng等[4-5]將模型分解成集合基本體的樹結構，并根據不同類別比較兩個模型的相似性，但對于結構復雜的模型，分解的樹結構將會有不同方案，使得最終的相似度差異較大;萬雅娟等[6]設計一種由骨架種子點開始對鄰域進行判定選出下一輪預備骨架點，迭代生長出完整三維模型骨架的提取算法，但提取的骨架不夠簡化，存在多面結構;劉玉杰等[7]提出一種基于手繪圖像融合信息嫡與CNN的三維模型檢索方法，先計算得到模型的代表性視圖，再與手繪草圖進行特征匹配，但手繪草圖差異度較大，失誤率高，且模型具有一定局限性。

針對上述方法存在的問題，本文提出的骨架生成方法能夠消除冗余分支骨架，基于距離變換生成機械零件骨架，并運用判定方法迭代生成骨架，保證了骨架的連續性，且避免了多面結構，有利于后續相似度計算。骨架檢索過程清晰、簡潔，計算方式簡單，計算量不大，將骨架轉換成直方圖曲線，并生成骨架點數矩陣，計算矩陣特征值和之間的差，隨之得出機械零件三維模型的相似程度。

1 機械零件三維模型預處理

1.1 模型歸一化及簡化

首先計算出機械零件三維模型的幾何中心，并將該幾何中心作為原點建立坐標系。之后將三維模型用最小凸包圍盒[8]，即最小包圍長方體完全包圍起來，過幾何中心作與最小凸包圍盒最長邊平行的直線，即為X軸;X軸線與最小凸包圍盒兩面交于兩點，比較幾何中心到兩點的距離，距離長的一側定義為正方向。利用笛卡爾坐標系建立原則，即可確定Y軸和Z軸，完成三維模型的方位歸一化處理，如圖1（a）所示。

在完成模型的方位歸一化后，對機械三維模型上的諸如倒角、倒圓、锪平沉孔等附加特征進行去除。機械模型相似度主要取決于模型主要特征與主干結構[9]，故通過電腦自動過濾掉這些附加特征。模型簡化后如圖1（b）所示。

1.2 投影與像素化處理

將模型分別投影到坐標平面XOZ、平面XOY與平面YOZ上，得到模型的主視圖、俯視圖和左視圖，保留各視圖外輪廓線及所有通孔的圓形視圖，去除其它圖線。如圖2所示為與圖1模型對應的處理后投影圖。

隨后對處理后投影圖進行像素化。像素是指由數字序列表示數字圖像中的最小單位[10]，根據投影圖尺寸，選取一個最小包絡長方形邊框[11]，并在該邊框內將圖形劃分為若干個等面積的小正方形。正方形邊長越小，后續提取出的骨架精度越高，但計算量也隨之增大。綜合考慮精度與計算量之間的關系，取投影圖長寬中較短邊的1/2 000左右較為適宜。故針對圖1所示模型處理后的投影圖，取邊長為0.1mm進行劃分，如圖3（a）所示為處理后主視圖的像素劃分圖。

1.3 采用距離變換賦值內部像素

最小距離值的計算方法采用歐氏距離[12]方法。圖3（b）為圖3（a）圓圈處的局部放大圖，圖中數字為像素值，填充部分為邊界像素，未填充且標有像素值的方格為內部像素。

2 骨架提取算法

本文提取骨架的方法是針對處理后的投影圖，由骨架起始點開始，對其相鄰像素進行判斷，生成新的骨架點并迭代生成骨架。根據骨架和距離變換的定義[13]，由于骨架中間部位的特征是內部像素值較大，且利于骨架向周圍擴散，故本文選擇具有最大值的內部像素作為骨架起始點。

利用參考文獻[6]中的方法對模型主視圖的迭代過程如圖4（a）所示，粗實線為骨架。同理，對模型俯、左兩個視圖進行骨架提取，完成所有迭代后，骨架如圖4（b）、（c）所示。

3 相似度計算

通過將骨架表示為二維曲線直方圖，再將曲線圖用矩陣形式予以表現，計算兩個矩陣之間的差異度，并判定兩個機械零件模型之間的相似度。

3.1 骨架直方圖描述

設骨架起始點為[P0]，骨架點集合為[Pi（i=1，2，？，][K）]，設[ske（P0，Pi）]為橫坐標，表示從[P0]沿骨架到[Pi]的最短路徑長度[14]，縱坐標[R（Pi）]為[Pi]點的內切圓半徑。圖4（a）中完成迭代的主視圖骨架直方圖見圖5（a）。同理可得該模型俯、左兩個視圖的骨架直方圖見圖5（b）、圖5（c）。

3.2 骨架點數矩陣生成

為了將直方圖轉換成骨架點數矩陣，首先對骨架直方圖進行網格劃分，網格劃分得越密集，矩陣數據表示則越細致，但計算量也隨之陡增。綜合考慮計算量與精準度[15]，選取橫向劃分網格數量在5～15之間，并將每個網格長寬比控制在1～3之間較為合理。按原則劃分后結果如圖5所示。

生成網格之后，依次計算每個網格中的骨架點數量，生成骨架點數矩陣。將網格橫坐標劃分為m等分，縱坐標n等分，每一網格中骨架點數量記為[hij]，生成骨架點數矩陣[H]為：

由于矩陣方陣才有特征值[16]，為便于后續匹配，若[m≠n]，則將行列中較少的一方添0補齊，使列數與行數相等。由于[H]矩陣表示骨架點落在指定區域內的個數，故添0操作相當于在已劃分好的網格右側或上方再添加新的網格，使網格的行與列相等，最后得出的數據矩陣與式（1）意義相同[17]。將圖5（a）按照上述方法生成數據矩陣[H（a）]，添0后為[H（a）']。

3.3 骨架點數矩陣匹配

通過將模型骨架轉換成直方圖，再根據直方圖生成數據矩陣，模型匹配轉換成兩個矩陣之間的匹配。兩個矩陣差異度可以用矩陣特征值之和的差表示。如圖6所示為模型二及完成歸一化與簡化后的模型。

將處理后的投影三視圖用第2節所述方法生成骨架，如圖7（a）中粗實線所示。將3個骨架依次用直方圖進行描述，并用網格劃分好，如圖7（b）所示。

3.2節中[H（a）']特征值之和為4.41，[H（1）']特征值之和為7.260 1，[H（a）']與[H（1）']矩陣特征值和之間的差為：|4.41- 7.260 1|= 2.850 1，即為兩個視圖之間的差異度。

3.4 零件模型匹配

模型骨架直方圖與其骨架點數矩陣特征值之和是互相對應的，故比較兩個模型骨架的相似度，可比較矩陣特征值之和的差。分別比較處理后主、俯、左視圖骨架點數矩陣特征值和的差，取加權值，即為兩個零件模型之間的差異度值[Dif]，如式（2）所示。

4 實例應用

為檢驗本文方法的可行性，將圖1模型數據上傳到自行開發的機械零件檢索系統中，見圖8。

系統運行結果顯示，排序前三的依次為編號0028、0126、0033的零件，即這3個零件差異度值較小，與圖1模型在形狀上很相似[18]，可以參考這幾個模型的設計方案。

5 實驗分析

將本文算法與D2形狀分布算法[19]及遞歸分割算法[20]進行對比分析，以驗證本文算法的可行性與準確性。

首先對計算量進行比較，本文的骨架提取算法是對鄰域像素距離變換值大小的比較，計算量較小，且矩陣特征值計算簡便易行。本文以第4節所述機械零件庫作為測試數據庫，在保證其它細節相同的情況下，依次用3種算法對同一零件模型進行檢索，檢索耗時如表2所示。本文方法計算量不大，耗時比D2形狀分布算法略多0.31s，少于遞歸分割算法。

綜合比較計算量和查準率—查全率后可以得出，本文算法計算量及檢索耗時略高于D2算法，但查準率—查全率優于D2算法;本文算法查準率在查全率大于0.18后，優于遞歸分割算法，且計算量明顯減小。綜合兩方面，本文算法具有很強的實用性。

6 結語

（1）本文的骨架生成方法通過迭代將新生成的骨架點重設為起始點，由起始點出發對鄰域像素進行判定，生成的骨架點相互鄰接，骨架具有連續性，有效避免了現有基于距離變換方法的骨架中斷現象。

（2）將處理后的投影圖像素化，并一次性地賦予像素值，骨架點判定是通過對鄰域像素值大小進行比較，故本文骨架生成算法計算量較小;骨架匹配是將骨架直方圖轉換為骨架點數矩陣，根據矩陣特征值和之間的差計算兩模型間的差異度，數據矩陣特征值計算簡便、快速，因此本文檢索方法效率較高。

（3）本文提出的模型骨架提取方法也適用于有通孔結構分布的機械零件，目前已在自行開發的檢索原型系統中得到應用。然而，如果零件上有盲孔，則處理后的骨架與通孔類零件相同。因此，針對本文的骨架提取部分，對于該情況還需作進一步研究。

參考文獻：

[1] LIU A，WANG Z，NIE W，et al. Graph-based characteristic view set extraction and matching for 3D model retrieval[J]. Information Sciences， 2015， 320： 429-442.

[2] ZHANG Y，JIANG F，RHO S，et al. 3D object retrieval with multi-feature collaboration and bipartite graph matching[J]. Neurocomputing， 2016，195（C）：40-49.

[3] CHOI W P，LAM K M，SIU W C. Extraction of the euclidean skeleton based on a connectivity criterion[J]. Pattern Recognition，2003，36（3）：721-729.

[4] CHENG H C，LO C H，et al. Shape similarity measurement for 3D mechanical part using D2 shape distribution and negative feature decomposition[J]. Computers in Industry，2011，62：269-280.

[5] 徐敬華，張樹有. 基于遞歸分割的機械零件三維形狀結構檢索方法[J]. 機械工程學報，2009，45（11）：176-183.

[6] 萬雅娟，李海生，劉漩，等. 基于距離變換的三維連通骨架提取算法[J]. 計算機仿真，2014，31（6）：256-260.

[7] 劉玉杰，宋陽，李宗民，等. 融合信息熵和CNN的基于手繪的三維模型檢索[J]. 圖學學報，2018，39（4）：735-741.

[8] 劉云，戴光明，王茂才. 基于遺傳算法的封閉輪廓最小面積凸包圍盒生成算法[J]. 湖北工程學院學報，2007，27（3）：63-66.

[9] 周圍，徐慶華，徐賜軍. 面向機械結構形態的三維模型信息處理[J]. 湖北理工學院學報，2018，142（2）：7-10.

[10] 陳永常. 印刷制版工藝原理[M]. 北京：化學工業出版社，2014.

[11] 葉剛. 城市環境基于三維激光雷達的自動駕駛車輛多目標檢測及跟蹤算法研究[D]. 北京：北京理工大學，2016.

[12] MISHCHENKO Y. A fast algorithm for computation of discrete Euclidean distance transform in three or more dimensions on vector processing architectures[J]. Signal，Image and Video Processing，2015， 9（1）： 19-27.

[13] LUO S，GUIBAS L J，ZHAO H K. Euclidean skeletons using closest points[J]. Inverse Problems & Imaging， 2017， 5（1）： 95-113.

[14] 張超，蘆勤，羅述謙. 基于距離變換與路徑規劃的骨架提取算法[J]. 北京生物醫學工程，2012，31（6）：551-555.

[15] 張桂梅，鄭加寬，儲珺. 基于骨架和統計直方圖的形狀匹配算法[J]. 計算機工程與應用，2015，51（16）：183-188.

[16] 陳宇祺. 基于矩陣填充理論的R-D算法[J]. 軟件導刊，2019，18（1）：92-96.

[17] DEMMEL J W. Applied numerical linear algebra[M]. Beijing： Tsinghua University Press，2011.

[18] 林嫻. 實心皮帶輪參數化的設計與實現[J]. 福建電腦，2015，31（1）：108-109.

[19] 趙鵬飛. 針對三維模型檢索中D2形狀分布算法的改進[J]. 煤炭技術，2013，32（7）：150-152.

[20] 吳延海，潘晨，吳楠. 改進的Otsu遞歸分割單幅圖像去霧算法研究[J]. ?西安科技大學學報，2017，37（3）：438-444.

（責任編輯：黃 健）